waashk/dblp huggingface dataset:
dimac: a disguised missing data cleaning tool. in some applications such as filling in a customer information form on the web, some missing values may not be explicitly represented as such, but instead appear as potentially valid data values. such missing values are known as disguised missing data, which may impair the quality of data analysis severely. the very limited previous studies on cleaning disguised missing data highly rely on domain background knowledge in specific applications and may not work well for the cases where the disguise values are inliers. recently, we have studied the problem of cleaning disguised missing data systematically, and proposed an effective heuristic approach [2]. in this paper, we present a demonstration of dimac, a disguised missing data cleaning tool which can find the frequently used disguise values in data sets without any domain background knowledge. in this demo, we will show (1) the critical techniques of finding suspicious disguise values; (2) the architecture and user interface of dimac system; (3) an empirical case study on both real and synthetic data sets, which verifies the effectiveness and the efficiency of the techniques; and (4) some challenges arising from real applications and several direction for future work.
mining favorable facets. the importance of dominance and skyline analysis has been well recognized in multi-criteria decision making applications. most previous studies assume a fixed order on the attributes. in practice, different customers may have different preferences on nominal attributes. in this paper, we identify an interesting data mining problem, finding favorable facets, which has not been studied before. given a set of points in a multidimensional space, for a specific target point p we want to discover with respect to which combinations of orders (e.g., customer preferences) on the nominal attributes p is not dominated by any other points. such combinations are called the favorable facets of p. we consider both the effectiveness and the efficiency of the mining. a given point may have many favorable facets. we propose the notion of minimal disqualifying condition (mdc) which is effective in summarizing favorable facets. we develop efficient algorithms for favorable facet mining for different application scenarios. the first method computes favorable facets on the fly. the second method pre-computes all minimal disqualifying conditions so that the favorable facets can be looked up in constant time. an extensive performance study using both synthetic and real data sets is reported to verify their effectiveness and efficiency.
a bayesian mixture model with linear regression mixing proportions. classic mixture models assume that the prevalence of the various mixture components is fixed and does not vary over time. this presents problems for applications where the goal is to learn how complex data distributions evolve. we develop models and bayesian learning algorithms for inferring the temporal trends of the components in a mixture model as a function of time. we show the utility of our models by applying them to the real-life problem of tracking changes in the rates of antibiotic resistance in escherichia coli and staphylococcus aureus. the results show that our methods can derive meaningful temporal antibiotic resistance patterns.
a spectral clustering approach to optimally combining numericalvectors with a modular network. we address the issue of clustering numerical vectors with a network. the problem setting is basically equivalent to constrained clustering by wagstaff and cardie and semi-supervised clustering by basu et al., but our focus is more on the optimal combination of two heterogeneous data sources. an application of this setting is web pages which can be numerically vectorized by their contents, e.g. term frequencies, and which are hyperlinked to each other, showing a network. another typical application is genes whose behavior can be numerically measured and a gene network can be given from another data source.we first define a new graph clustering measure which we call normalized network modularity, by balancing the cluster size of the original modularity. we then propose a new clustering method which integrates the cost of clustering numerical vectors with the cost of maximizing the normalized network modularity into a spectral relaxation problem. our learning algorithm is based on spectral clustering which makes our issue an eigenvalue problem and uses k-means for final cluster assignments. a significant advantage of our method is that we can optimize the weight parameter for balancing the two costs from the given data by choosing the minimum total cost. we evaluated the performance of our proposed method using a variety of datasets including synthetic data as well as real-world data from molecular biology. experimental results showed that our method is effective enough to have good results for clustering by numerical vectors and a network.
xproj: a framework for projected structural clustering of xml documents. xml has become a popular method of data representation both on the web and in databases in recent years. one of the reasons for the popularity of xml has been its ability to encode structural information about data records. however, this structural characteristic of data sets also makes it a challenging problem for a variety of data mining problems. one such problem is that of clustering, in which the structural aspects of the data result in a high implicit dimensionality of the data representation. as a result, it becomes more difficult to cluster the data in a meaningful way. in this paper, we propose an effective clustering algorithm for xml data which uses substructures of the documents in order to gain insights about the important underlying structures. we propose new ways of using multiple sub-structuralinformation in xml documents to evaluate the quality of intermediate cluster solutions, and guide the algorithms to a final solution which reflects the true structural behavior in individual partitions. we test the algorithm on a variety of real and synthetic data sets.
unsupervised feature selection for principal components analysis. principal components analysis (pca) is the predominant linear dimensionality reduction technique, and has been widely applied on datasets in all scientific domains. we consider, both theoretically and empirically, the topic of unsupervised feature selection for pca, by leveraging algorithms for the so-called column subset selection problem (cssp). in words, the cssp seeks the "best" subset of exactly k columns from an m x n data matrix a, and has been extensively studied in the numerical linear algebra community. we present a novel two-stage algorithm for the cssp. from a theoretical perspective, for small to moderate values of k, this algorithm significantly improves upon the best previously-existing results [24, 12] for the cssp. from an empirical perspective, we evaluate this algorithm as an unsupervised feature selection strategy in three application domains of modern statistical data analysis: finance, document-term data, and genetics. we pay particular attention to how this algorithm may be used to select representative or landmark features from an object-feature matrix in an unsupervised manner. in all three application domains, we are able to identify k landmark features, i.e., columns of the data matrix, that capture nearly the same amount of information as does the subspace that is spanned by the top k "eigenfeatures."
hierarchical mixture models: a probabilistic analysis. mixture models form one of the most widely used classes of generative models for describing structured and clustered data. in this paper we develop a new approach for the analysis of hierarchical mixture models. more specifically, using a text clustering problem as a motivation, we describe a natural generative process that creates a hierarchical mixture model for the data. in this process, an adversary starts with an arbitrary base distribution and then builds a topic hierarchy via some evolutionary process, where he controls the parameters of the process. we prove that under our assumptions, given a subset of topics that represent generalizations of one another (such as baseball → sports → base), for any document which was produced via some topic in this hierarchy, we can efficiently determine the most specialized topic in this subset, it still belongs to. the quality of the classification is independent of the total number of topics in the hierarchy and our algorithm does not need to know the total number of topics in advance. our approach also yields an algorithm for clustering and unsupervised topical tree reconstruction. we validate our model by showing that properties predicted by our theoretical results carry over to real data. we then apply our clustering algorithm to two different datasets: (i) "20 newsgroups"[19] and (ii) a snapshot of abstracts of arxiv {2} (15 categories, ~240,000 abstracts). in both cases our algorithm performs extremely well.
factorization meets the neighborhood: a multifaceted collaborative filtering model. recommender systems provide users with personalized suggestions for products or services. these systems often rely on collaborating filtering (cf), where past transactions are analyzed in order to establish connections between users and products. the two more successful approaches to cf are latent factor models, which directly profile both users and products, and neighborhood models, which analyze similarities between products or users. in this work we introduce some innovations to both approaches. the factor and neighborhood models can now be smoothly merged, thereby building a more accurate combined model. further accuracy improvements are achieved by extending the models to exploit both explicit and implicit feedback by the users. the methods are tested on the netflix data. results are better than those previously published on that dataset. in addition, we suggest a new evaluation metric, which highlights the differences among methods, based on their performance at a top-k recommendation task.
efficient and effective explanation of change in hierarchical summaries. dimension attributes in data warehouses are typically hierarchical (e.g., geographic locations in sales data, urls in web traffic logs). olap tools are used to summarize the measure attributes (e.g., total sales) along a dimension hierarchy, and to characterize changes (e.g., trends and anomalies) in a hierarchical summary over time. when thenumber of changes identified is large (e.g., total sales in many stores differed from their expected values), a parsimonious explanation of the most significant changes is desirable. in this paper, we propose a natural model of parsimonious explanation, as a composition of node weights along the root-to-leaf paths in a dimension hierarchy, which permits changes to be aggregated with maximal generalization along the dimension hierarchy. we formalize this model of explaining changes in hierarchical summaries and investigate the problem of identifying optimally parsimonious explanations on arbitrary rooted one dimensional tree hierarchies. we show that such explanations can be computed efficiently in time essentially proportional to the number of leaves and the depth of the hierarchy. further, our method can produce parsimonious explanations from the output of any statistical model that provides predictions and confidence intervals, making it widely applicable. our experiments use real data sets to demonstrate the utility and robustness of our proposed model for explaining significant changes, as well as its superior parsimony compared to alternatives.
predictive discrete latent factor models for large scale dyadic data. we propose a novel statistical method to predict large scale dyadic response variables in the presence of covariate information. our approach simultaneously incorporates the effect of covariates and estimates local structure that is induced by interactions among the dyads through a discrete latent factor model. the discovered latent factors provide a redictive model that is both accurate and interpretable. we illustrate our method by working in a framework of generalized linear models, which include commonly used regression techniques like linear regression, logistic regression and poisson regression as special cases. we also provide scalable generalized em-based algorithms for model fitting using both "hard" and "soft" cluster assignments. we demonstrate the generality and efficacy of our approach through large scale simulation studies and analysis of datasets obtained from certain real-world movie recommendation and internet advertising applications.
a framework for classification and segmentation of massive audio data streams. in recent years, the proliferation of voip data has created a number of applications in which it is desirable to perform quick online classification and recognition of massive voice streams. typically such applications are encountered in real time intelligence and surveillance. in many cases, the data streams can be in compressed format, and the rate of data processing can often run at the rate of gigabits per second. all known techniques for speaker voice analysis require the use of an offline training phase in which the system is trained with known segments of speech. the state-of-the-art method for text-independent speaker recognition is known as gaussian mixture modeling (gmm), and it requires an iterative expectation maximization procedure for training, which cannot be implemented in real time. in this paper, we discuss the details of such an online voice recognition system. for this purpose, we use our micro-clustering algorithms to design concise signatures of the target speakers. one of the surprising and insightful observations from our experiences with such a system is that while it was originally designed only for efficiency, we later discovered that it was also more accurate than the widely used gaussian mixture model (gmm). this was because of the conciseness of the micro-cluster model, which made it less prone to over training. this is evidence of the fact that it is often possible to get the best of both worlds and do better than complex models both from an efficiency and accuracy perspective.
topical query decomposition. we introduce the problem of query decomposition, where we are given a query and a document retrieval system, and we want to produce a small set of queries whose union of resulting documents corresponds approximately to that of the original query. ideally, these queries should represent coherent, conceptually well-separated topics. we provide an abstract formulation of the query decomposition problem, and we tackle it from two different perspectives. we first show how the problem can be instantiated as a specific variant of a set cover problem, for which we provide an efficient greedy algorithm. next, we show how the same problem can be seen as a constrained clustering problem, with a very particular kind of constraint, i.e., clustering with predefined clusters. we develop a two-phase algorithm based on hierarchical agglomerative clustering followed by dynamic programming. our experiments, conducted on a set of actual queries in a web scale search engine, confirm the effectiveness of the proposed solutions.
on string classification in data streams. string data has recently become important because of its use in a number of applications such as computational and molecular biology, protein analysis, and market basket data. in many cases, these strings contain a wide variety of substructures which may have physical significance for that application. for example, such substructures could represent important fragments of a dna string or an interesting portion of a fraudulent transaction. in such a case, it is desirable to determine the identity, location, and extent of that substructure in the data. this is a much more difficult generalization of the classification problem, since the latter problem labels entire strings rather than deal with the more complex task of determining string fragments with a particular kind of behavior. the problem becomes even more complicated when different kinds of substrings show complicated nesting patterns. therefore, we define a somewhat different problem which we refer to as the generalized classification problem. we propose a scalable approach based on hidden markov models for this problem. we show how to implement the generalized string classification procedure for very large data bases and data streams. we present experimental results over a number of large data sets and data streams.
calculating latent demand in the long tail. an analytical framework for using powerlaw theory to estimate market size for niche products and consumer groups.
temporal causal modeling with graphical granger methods. the need for mining causality, beyond mere statistical correlations, for real world problems has been recognized widely. many of these applications naturally involve temporal data, which raises the challenge of how best to leverage the temporal information for causal modeling. recently graphical modeling with the concept of "granger causality", based on the intuition that a cause helps predict its effects in the future, has gained attention in many domains involving time series data analysis. with the surge of interest in model selection methodologies for regression, such as the lasso, as practical alternatives to solving structural learning of graphical models, the question arises whether and how to combine these two notions into a practically viable approach for temporal causal modeling. in this paper, we examine a host of related algorithms that, loosely speaking, fall under the category of graphical granger methods, and characterize their relative performance from multiple viewpoints. our experiments show, for instance, that the lasso algorithm exhibits consistent gain over the canonical pairwise graphical granger method. we also characterize conditions under which these variants of graphical granger methods perform well in comparison to other benchmark methods. finally, we apply these methods to a real world data set involving key performance indicators of corporations, and present some concrete results.
an event-based framework for characterizing the evolutionary behavior of interaction graphs. interaction graphs are ubiquitous in many fields such as bioinformatics, sociology and physical sciences. there have been many studies in the literature targeted at studying and mining these graphs. however, almost all of them have studied these graphs from a static point of view. the study of the evolution of these graphs over time can provide tremendous insight on the behavior of entities, communities and the flow of information among them. in this work, we present an event-based characterization of critical behavioral patterns for temporally varying interaction graphs. we use nonoverlapping snapshots of interaction graphs and develop a framework for capturing and identifying interesting events from them. we use these events to characterize complex behavioral patterns of individuals and communities over time. we show how semantic information can be incorporated to reason about community-behavior events. we also demonstrate the application of behavioral patterns for the purposes of modeling evolution, link prediction and influence maximization. finally, we present a diffusion model for evolving networks, based on our framework.
extracting semantic relations from query logs. in this paper we study a large query log of more than twenty million queries with the goal of extracting the semantic relations that are implicitly captured in the actions of users submitting queries and clicking answers. previous query log analyses were mostly done with just the queries and not the actions that followed after them. we first propose a novel way to represent queries in a vector space based on a graph derived from the query-click bipartite graph. we then analyze the graph produced by our query log, showing that it is less sparse than previous results suggested, and that almost all the measures of these graphs follow power laws, shedding some light on the searching user behavior as well as on the distribution of topics that people want in the web. the representation we introduce allows to infer interesting semantic relationships between queries. second, we provide an experimental analysis on the quality of these relations, showing that most of them are relevant. finally we sketch an application that detects multitopical urls.
modeling relationships at multiple scales to improve accuracy of large recommender systems. the collaborative filtering approach to recommender systems predicts user preferences for products or services by learning past user-item relationships. in this work, we propose novel algorithms for predicting user ratings of items by integrating complementary models that focus on patterns at different scales. at a local scale, we use a neighborhood-based technique that infers ratings from observed ratings by similar users or of similar items. unlike previous local approaches, our method is based on a formal model that accounts for interactions within the neighborhood, leading to improved estimation quality. at a higher, regional, scale, we use svd-like matrix factorization for recovering the major structural patterns in the user-item rating matrix. unlike previous approaches that require imputations in order to fill in the unknown matrix entries, our new iterative algorithm avoids imputation. because the models involve estimation of millions, or even billions, of parameters, shrinkage of estimated values to account for sampling variability proves crucial to prevent overfitting. both the local and the regional approaches, and in particular their combination through a unifying model, compare favorably with other approaches and deliver substantially better results than the commercial netflix cinematch recommender system on a large publicly available data set.
content-based document routing and index partitioning for scalable similarity-based searches in a large corpus. we present a document routing and index partitioning scheme for scalable similarity-based search of documents in a large corpus. we consider the case when similarity-based search is performed by finding documents that have features in common with the query document. while it is possible to store all the features of all the documents in one index, this suffers from obvious scalability problems. our approach is to partition the feature index into multiple smaller partitions that can be hosted on separate servers, enabling scalable and parallel search execution. when a document is ingested into the repository, a small number of partitions are chosen to store the features of the document. to perform similarity-based search, also, only a small number of partitions are queried. our approach is stateless and incremental. the decision as to which partitions the features of the document should be routed to (for storing at ingestion time, and for similarity based search at query time) is solely based on the features of the document. our approach scales very well. we show that executing similarity-based searches over such a partitioned search space has minimal impact on the precision and recall of search results, even though every search consults less than 3% of the total number of partitions.