waashk/dblp huggingface dataset:
ordering patterns by combining opinions from multiple sources. pattern ordering is an important task in data mining because the number of patterns extracted by standard data mining algorithms often exceeds our capacity to manually analyze them. in this paper, we present an effective approach to address the pattern ordering problem by combining the rank information gathered from disparate sources. although rank aggregation techniques have been developed for applications such as meta-search engines, they are not directly applicable to pattern ordering for two reasons. first, the techniques are mostly supervised, i.e., they require a sufficient amount of labeled data. second, the objects to be ranked are assumed to be independent and identically distributed (i.i.d), an assumption that seldom holds in pattern ordering. the method proposed in this paper is an adaptation of the original hedge algorithm, modified to work in an unsupervised learning setting. techniques for addressing the i.i.d. violation in pattern ordering are also presented. experimental results demonstrate that our unsupervised hedge algorithm outperforms many alternative techniques such as those based on weighted average ranking and singular value decomposition.
selecting the right interestingness measure for association patterns. many techniques for association rule mining and feature selection require a suitable metric to capture the dependencies among variables in a data set. for example, metrics such as support, confidence, lift, correlation, and collective strength are often used to determine the interestingness of association patterns. however, many such measures provide conflicting information about the interestingness of a pattern, and the best metric to use for a given application domain is rarely known. in this paper, we present an overview of various measures proposed in the statistics, machine learning and data mining literature. we describe several key properties one should examine in order to select the right measure for a given application domain. a comparative study of these properties is made using twenty one of the existing measures. we show that each measure has different properties which make them useful for some application domains, but not for others. we also present two scenarios in which most of the existing measures agree with each other, namely, support-based pruning and table standardization. finally, we present an algorithm to select a small set of tables such that an expert can select a desirable measure by looking at just this small set of tables.
mining long-term search history to improve search accuracy. long-term search history contains rich information about a user's search preferences, which can be used as search context to improve retrieval performance. in this paper, we study statistical language modeling based methods to mine contextual information from long-term search history and exploit it for a more accurate estimate of the query language model. experiments on real web search data show that the algorithms are effective in improving search accuracy for both fresh and recurring queries. the best performance is achieved when using clickthrough data of past searches that are related to the current query.
email data cleaning. addressed in this paper is the issue of 'email data cleaning' for text mining. many text mining applications need take emails as input. email data is usually noisy and thus it is necessary to clean it before mining. several products offer email cleaning features, however, the types of noises that can be eliminated are restricted. despite the importance of the problem, email cleaning has received little attention in the research community. a thorough and systematic investigation on the issue is thus needed. in this paper, email cleaning is formalized as a problem of non-text filtering and text normalization. in this way, email cleaning becomes independent from any specific text mining processing. a cascaded approach is proposed, which cleans up an email in four passes including non-text filtering, paragraph normalization, sentence normalization, and word normalization. as far as we know, non-text filtering and paragraph normalization have not been investigated previously. methods for performing the tasks on the basis of support vector machines (svm) have also been proposed in this paper. features in the models have been defined. experimental results indicate that the proposed svm based methods can significantly outperform the baseline methods for email cleaning. the proposed method has been applied to term extraction, a typical text mining processing. experimental results show that the accuracy of term extraction can be significantly improved by using the data cleaning method.
mining phenotypes and informative genes from gene expression data. mining microarray gene expression data is an important research topic in bioinformatics with broad applications. while most of the previous studies focus on clustering either genes or samples, it is interesting to ask whether we can partition the complete set of samples into exclusive groups (called phenotypes) and find a set of informative genes that can manifest the phenotype structure. in this paper, we propose a new problem of simultaneously mining phenotypes and informative genes from gene expression data. some statistics-based metrics are proposed to measure the quality of the mining results. two interesting algorithms are developed: the heuristic search and the mutual reinforcing adjustment method. we present an extensive performance study on both real-world data sets and synthetic data sets. the mining results from the two proposed methods are clearly better than those from the previous methods. they are ready for the real-world applications. between the two methods, the mutual reinforcing adjustment method is in general more scalable, more effective and with better quality of the mining results.
hierarchical model-based clustering of large datasets through fractionation and refractionation. the goal of clustering is to identify distinct groups in a dataset. compared to non-parametric clustering methods like complete linkage, hierarchical model-based clustering has the advantage of offering a way to estimate the number of groups present in the data. however, its computational cost is quadratic in the number of items to be clustered, and it is therefore not applicable to large problems. we review an idea called fractionation, originally conceived by cutting, karger, pedersen and tukey for non-parametric hierarchical clustering of large datasets, and describe an adaptation of fractionation to model-based clustering. a further extension, called refractionation, leads to a procedure that can be successful even in the difficult situation where there are large numbers of small groups.
assessment and pruning of hierarchical model based clustering. the goal of clustering is to identify distinct groups in a dataset. the basic idea of model-based clustering is to approximate the data density by a mixture model, typically a mixture of gaussians, and to estimate the parameters of the component densities, the mixing fractions, and the number of components from the data. the number of distinct groups in the data is then taken to be the number of mixture components, and the observations are partitioned into clusters (estimates of the groups) using bayes' rule. if the groups are well separated and look gaussian, then the resulting clusters will indeed tend to be "distinct" in the most common sense of the word - contiguous, densely populated areas of feature space, separated by contiguous, relatively empty regions. if the groups are not gaussian, however, this correspondence may break down; an isolated group with a non-elliptical distribution, for example, may be modeled by not one, but several mixture components, and the corresponding clusters will no longer be well separated. we present methods for assessing the degree of separation between the components of a mixture model and between the corresponding clusters. we also propose a new clustering method that can be regarded as a hybrid between model-based and nonparametric clustering. the hybrid clustering algorithm prunes the cluster tree generated by hierarchical model-based clustering. starting with the tree corresponding to the mixture model chosen by the bayesian information criterion, it progressively merges clusters that do not appear to correspond to different modes of the data density.
weighted association rule mining using weighted support and significance framework. we address the issues of discovering significant binary relationships in transaction datasets in a weighted setting. traditional model of association rule mining is adapted to handle weighted association rule mining problems where each item is allowed to have a weight. the goal is to steer the mining focus to those significant relationships involving items with significant weights rather than being flooded in the combinatornal explosion of insignificant relationships. we identify the challenge of using weights in the iterative process of generating large itemsets. the problem of invalidation of the "downward closure property" in the weighted setting is solved by using an improved model of weighted support measurements and exploiting a "weighted downward closure property". a new algorithm called warm (weighted association rule mining) is developed based on the improved model. the algorithm is both scalable and efficient in discovering significant relationships in weighted settings as illustrated by experiments performed on simulated datasets.
mining distance-based outliers from large databases in any metric space. let r be a set of objects. an object o ∈ r is an outlier, if there exist less than k objects in r whose distances to o are at most r. the values of k, r, and the distance metric are provided by a user at the run time. the objective is to return all outliers with the smallest i/o cost.this paper considers a generic version of the problem, where no information is available for outlier computation, except for objects' mutual distances. we prove an upper bound for the memory consumption which permits the discovery of all outliers by scanning the dataset 3 times. the upper bound turns out to be extremely low in practice, e.g., less than 1% of r. since the actual memory capacity of a realistic dbms is typically larger, we develop a novel algorithm, which integrates our theoretical findings with carefully-designed heuristics that leverage the additional memory to improve i/o efficiency. our technique reports all outliers by scanning the dataset at most twice (in some cases, even once), and significantly outperforms the existing solutions by a factor up to an order of magnitude.
mining comparable bilingual text corpora for cross-language information integration. integrating information in multiple natural languages is a challenging task that often requires manually created linguistic resources such as a bilingual dictionary or examples of direct translations of text. in this paper, we propose a general cross-lingual text mining method that does not rely on any of these resources, but can exploit comparable bilingual text corpora to discover mappings between words and documents in different languages. comparable text corpora are collections of text documents in different languages that are about similar topics; such text corpora are often naturally available (e.g., news articles in different languages published in the same time period). the main idea of our method is to exploit frequency correlations of words in different languages in the comparable corpora and discover mappings between words in different languages. such mappings can then be used to further discover mappings between documents in different languages, achieving cross-lingual information integration. evaluation of the proposed method on a 120mb chinese-english comparable news collection shows that the proposed method is effective for mapping words and documents in english and chinese. since our method only relies on naturally available comparable corpora, it is generally applicable to any language pairs as long as we have comparable corpora.
learning domain-independent string transformation weights for high accuracy object identification. the task of object identification occurs when integrating information from multiple websites. the same data objects can exist in inconsistent text formats across sites, making it difficult to identify matching objects using exact text match. previous methods of object identification have required manual construction of domain-specific string transformations or manual setting of general transformation parameter weights for recognizing format inconsistencies. this manual process can be time consuming and error-prone. we have developed an object identification system called active atlas [18], which applies a set of domain-independent string transformations to compare the objects' shared attributes in order to identify matching objects. in this paper, we discuss extensions to the active atlas system, which allow it to learn to tailor the weights of a set of general transformations to a specific application domain through limited user input. the experimental results demonstrate that this approach achieves higher accuracy and requires less user involvement than previous methods across various application domains.
paintingclass: interactive construction, visualization and exploration of decision trees. decision trees are commonly used for classification. we propose to use decision trees not just for classification but also for the wider purpose of knowledge discovery, because visualizing the decision tree can reveal much valuable information in the data. we introduce paintingclass, a system for interactive construction, visualization and exploration of decision trees. paintingclass provides an intuitive layout and convenient navigation of the decision tree. paintingclass also provides the user the means to interactively construct the decision tree. each node in the decision tree is displayed as a visual projection of the data. through actual examples and comparison with other classification methods, we show that the user can effectively use paintingclass to construct a decision tree and explore the decision tree to gain additional knowledge.
a generative probabilistic approach to visualizing sets of symbolic sequences. there is a notable interest in extending probabilistic generative modeling principles to accommodate for more complex structured data types. in this paper we develop a generative probabilistic model for visualizing sets of discrete symbolic sequences. the model, a constrained mixture of discrete hidden markov models, is a generalization of density-based visualization methods previously developed for static data sets. we illustrate our approach on sequences representing web-log data and chorals by j.s. bach.
center-piece subgraphs: problem definition and fast solutions. given q nodes in a social network (say, authorship network), how can we find the node/author that is the center-piece, and has direct or indirect connections to all, or most of them? for example, this node could be the common advisor, or someone who started the research area that the q nodes belong to. isomorphic scenarios appear in law enforcement (find the master-mind criminal, connected to all current suspects), gene regulatory networks (find the protein that participates in pathways with all or most of the given q proteins), viral marketing and many more.connection subgraphs is an important first step, handling the case of q=2 query nodes. then, the connection subgraph algorithm finds the b intermediate nodes, that provide a good connection between the two original query nodes.here we generalize the challenge in multiple dimensions: first, we allow more than two query nodes. second, we allow a whole family of queries, ranging from 'or' to 'and', with 'softand' in-between. finally, we design and compare a fast approximation, and study the quality/speed trade-off.we also present experiments on the dblp dataset. the experiments confirm that our proposed method naturally deals with multi-source queries and that the resulting subgraphs agree with our intuition. wall-clock timing results on the dblp dataset show that our proposed approximation achieve good accuracy for about 6:1 speedup.
regression error characteristic surfaces. this paper presents a generalization of regression error characteristic (rec) curves. rec curves describe the cumulative distribution function of the prediction error of models and can be seen as a generalization of roc curves to regression problems. rec curves provide useful information for analyzing the performance of models, particularly when compared to error statistics like for instance the mean squared error. in this paper we present regression error characteristic (rec) surfaces that introduce a further degree of detail by plotting the cumulative distribution function of the errors across the distribution of the target variable, i.e. the joint cumulative distribution function of the errors and the target variable. this provides a more detailed analysis of the performance of models when compared to rec curves. this extra detail is particularly relevant in applications with non-uniform error costs, where it is important to study the performance of models for specific ranges of the target variable. in this paper we present the notion of rec surfaces, describe how to use them to compare the performance of models, and illustrate their use with an important practical class of applications: the prediction of rare extreme values.
tri-plots: scalable tools for multidimensional data mining. we focus on the problem of finding patterns across two large, multidimensional datasets. for example, given feature vectors of healthy and of non-healthy patients, we want to answer the following questions: are the two clouds of points separable? what is the smallest/largest pair-wise distance across the two datasets? which of the two clouds does a new point (feature vector) come from?we propose a new tool, the tri-plot, and its generalization, the pq-plot, which help us answer the above questions. we provide a set of rules on how to interpret a tri-plot, and we apply these rules on synthetic and real datasets. we also show how to use our tool for classification, when traditional methods (nearest neighbor, classification trees) may fail.
learning a complex metabolomic dataset using random forests and support vector machines. metabolomics is the "omics" science of biochemistry. the associated data include the quantitative measurements of all small molecule metabolites in a biological sample. these datasets provide a window into dynamic biochemical networks and conjointly with other "omic" data, genes and proteins, have great potential to unravel complex human diseases. the dataset used in this study has 63 individuals, normal and diseased, and the diseased are drug treated or not, so there are three classes. the goal is to classify these individuals using the observed metabolite levels for 317 measured metabolites. there are a number of statistical challenges: non-normal data, the number of samples is less than the number of metabolites; there are missing data and the fact that data are missing is informative (assay values below detection limits can point to a specific class); also, there are high correlations among the metabolites. we investigate support vector machines (svm), and random forest (rf), for outlier detection, variable selection and classification. we use the variables selected with rf in svm and visa versa. the benefit of this study is insight into interplay of variable selection and classification methods. we link our selected predictors to the biochemistry of the disease.
time and sample efficient discovery of markov blankets and direct causal relations. data mining with bayesian network learning has two important characteristics: under conditions learned edges between variables correspond to casual influences, and second, for every variable t in the network a special subset (markov blanket) identifiable by the network is the minimal variable set required to predict t. however, all known algorithms learning a complete bn do not scale up beyond a few hundred variables. on the other hand, all known sound algorithms learning a local region of the network require an exponential number of training instances to the size of the learned region.the contribution of this paper is two-fold. we introduce a novel local algorithm that returns all variables with direct edges to and from a target variable t as well as a local algorithm that returns the markov blanket of t. both algorithms (i) are sound, (ii) can be run efficiently in datasets with thousands of variables, and (iii) significantly outperform in terms of approximating the true neighborhood previous state-of-the-art algorithms using only a fraction of the training size required by the existing methods. a fundamental difference between our approach and existing ones is that the required sample depends on the generating graph connectivity and not the size of the local region; this yields up to exponential savings in sample relative to previously known algorithms. the results presented here are promising not only for discovery of local causal structure, and variable selection for classification, but also for the induction of complete bns.
efficient kernel feature extraction for massive data sets. maximum margin discriminant analysis (mmda) was proposed that uses the margin idea for feature extraction. it often outperforms traditional methods like kernel principal component analysis (kpca) and kernel fisher discriminant analysis (kfd). however, as in other kernel methods, its time complexity is cubic in the number of training points m, and is thus computationally inefficient on massive data sets. in this paper, we propose an (1+ε)2-approximation algorithm for obtaining the mmda features by extending the core vector machines. the resultant time complexity is only linear in m, while its space complexity is independent of m. extensive comparisons with the original mmda, kpca, and kfd on a number of large data sets show that the proposed feature extractor can improve classification accuracy, and is also faster than these kernel-based methods by more than an order of magnitude.
handling very large numbers of association rules in the analysis of microarray data. the problem of analyzing microarray data became one of important topics in bioinformatics over the past several years, and different data mining techniques have been proposed for the analysis of such data. in this paper, we propose to use association rule discovery methods for determining associations among expression levels of different genes. one of the main problems related to the discovery of these associations is the scalability issue. microarrays usually contain very large numbers of genes that are sometimes measured in 10,000s. therefore, analysis of such data can generate a very large number of associations that can often be measured in millions. the paper addresses this problem by presenting a method that enables biologists to evaluate these very large numbers of discovered association rules during the post-analysis stage of the data mining process. this is achieved by providing several rule evaluation operators, including rule grouping, filtering, browsing, and data inspection operators, that allow biologists to validate multiple individual gane regulation patterns at a time. by iteratively applying these operators, biologists can explore a significant part of all the initially generated rules in an acceptable period of time and thus answer biological questions that are of a particular interest to him or her. to validate our method, we tested our system on the microarray data pertaining to the studies of environmental hazards and their influence of gane expression processes. as a result, we managed to answer several questions that were of interest to the biologists that had collected this data.