waashk/dblp huggingface dataset:
cvs: a correlation-verification based smoothing technique on information retrieval and term clustering. as information volume in enterprise systems and in the web grows rapidly, how to accurately retrieve information is an important research area. several corpus based smoothing techniques have been proposed to address the data sparsity and synonym problems faced by information retrieval systems. such smoothing techniques are often unable to discover and utilize the correlations among terms.we propose cvs, a correlation-verification based smoothing method, that considers co-occurrence information in smoothing. strongly correlated terms in a document are identified by their co-occurrence frequencies in the document. to avoid missing correlated terms with low co-occurrence frequencies but specific to the theme of the document, the joint distributions of terms in the document are compared with those in the corpus for statistical significance.a common approach to apply corpus based smoothing techniques to information retrieval is by refining the vector representations of documents. this paper investigates the effects of corpus based smoothing on information retrieval by query expansion using term clusters generated from a term clustering process. the results can also be viewed in light of the effects of smoothing on clustering.empirical studies show that our approach outperforms previous corpus based smoothing techniques. it improves retrieval effectiveness by 14.6%. the results demonstrate that corpus based smoothing can be used for query expansion by term clustering.
a general model for clustering binary data. clustering is the problem of identifying the distribution of patterns and intrinsic correlations in large data sets by partitioning the data points into similarity classes. this paper studies the problem of clustering binary data. this is the case for market basket datasets where the transactions contain items and for document datasets where the documents contain "bag of words". the contribution of the paper is three-fold. first a general binary data clustering model is presented. the model treats the data and features equally, based on their symmetric association relations, and explicitly describes the data assignments as well as feature assignments. we characterize several variations with different optimization procedures for the general model. second, we also establish the connections between our clustering model with other existing clustering methods. third, we also discuss the problem for determining the number of clusters for binary clustering. experimental results show the effectiveness of the proposed clustering model.
liped: hmm-based life profiles for adaptive event detection. in this paper, the proposed liped (life profile based event detection) employs the concept of life profiles to predict the activeness of event for effective event detection. a group of events with similar activeness patterns shares a life profile, modeled by a hidden markov model. considering the burst-and-diverse property of events, liped identifies the activeness status of event. as a result, liped balances the clustering precision and recall to achieve better f1 scores than other well known approaches evaluated on the official tdt1 corpus.
co-clustering documents and words using bipartite spectral graph partitioning. both document clustering and word clustering are well studied problems. most existing algorithms cluster documents and words separately but not simultaneously. in this paper we present the novel idea of modeling the document collection as a bipartite graph between documents and words, using which the simultaneous clustering problem can be posed as a bipartite graph partitioning problem. to solve the partitioning problem, we use a new spectral co-clustering algorithm that uses the second left and right singular vectors of an appropriately scaled word-document matrix to yield good bipartitionings. the spectral algorithm enjoys some optimality properties; it can be shown that the singular vectors solve a real relaxation to the np-complete graph bipartitioning problem. we present experimental results to verify that the resulting co-clustering algorithm works well in practice.
pva: a self-adaptive personal view agent system. in this paper, we present pva, an adaptive personal view information agent system to track, learn and manage, user's interests in internet documents. when user's interests change, pva, in not only the contents, but also in the structure of user profile, is modified to adapt to the changes. experimental results show that modulating the structure of user profile does increase the accuracy of personalization systems.
kernel k-means: spectral clustering and normalized cuts. kernel k-means and spectral clustering have both been used to identify clusters that are non-linearly separable in input space. despite significant research, these methods have remained only loosely related. in this paper, we give an explicit theoretical connection between them. we show the generality of the weighted kernel k-means objective function, and derive the spectral clustering objective of normalized cut as a special case. given a positive definite similarity matrix, our results lead to a novel weighted kernel k-means algorithm that monotonically decreases the normalized cut. this has important implications: a) eigenvector-based algorithms, which can be computationally prohibitive, are not essential for minimizing normalized cuts, b) various techniques, such as local search and acceleration schemes, may be used to improve the quality as well as speed of kernel k-means. finally, we present results on several interesting data sets, including diametrical clustering of large gene-expression matrices and a handwriting recognition data set.
a fast kernel-based multilevel algorithm for graph clustering. graph clustering (also called graph partitioning) --- clustering the nodes of a graph --- is an important problem in diverse data mining applications. traditional approaches involve optimization of graph clustering objectives such as normalized cut or ratio association; spectral methods are widely used for these objectives, but they require eigenvector computation which can be slow. recently, graph clustering with a general cut objective has been shown to be mathematically equivalent to an appropriate weighted kernel k-means objective function. in this paper, we exploit this equivalence to develop a very fast multilevel algorithm for graph clustering. multilevel approaches involve coarsening, initial partitioning and refinement phases, all of which may be specialized to different graph clustering objectives. unlike existing multilevel clustering approaches, such as metis, our algorithm does not constrain the cluster sizes to be nearly equal. our approach gives a theoretical guarantee that the refinement step decreases the graph cut objective under consideration. experiments show that we achieve better final objective function values as compared to a state-of-the-art spectral clustering algorithm: on a series of benchmark test graphs with up to thirty thousand nodes and one million edges, our algorithm achieves lower normalized cut values in 67% of our experiments and higher ratio association values in 100% of our experiments. furthermore, on large graphs, our algorithm is significantly faster than spectral methods. finally, our algorithm requires far less memory than spectral methods; we cluster a 1.2 million node movie network into 5000 clusters, which due to memory requirements cannot be done directly with spectral methods.
a bayesian network classifier with inverse tree structure for voxelwise magnetic resonance image analysis. we propose a bayesian-network classifier with inverse-tree structure (bncit) for joint classification and variable selection. the problem domain of voxelwise magnetic-resonance image analysis often involves millions of variables but only dozens of samples. judicious variable selection may render classification tractable, avoid over-fitting, and improve classifier performance. bncit embeds the variable-selection process within the classifier-training process, which makes this algorithm scalable. bncit is based on a bayesian-network model with inverse-tree structure, i.e., the class variable c is a leaf node, and predictive variables are parents of c; thus, the classifier-training process returns a parent set for c, which is a subset of the markov blanket of c. bncit uses voxels in the parent set, and voxels that are probabilistically equivalent to them, as variables for classification of new image data. since the data set has a limited number of samples, we use the jackknife method to determine whether the classifier generated by bncit is a statistical artifact. in order to enhance stability and improve classification accuracy, we model the state of the probabilistically equivalent voxels with a latent variable. we employ an efficient method for determining states of hidden variables, thus reducing dramatically the computational cost of model generation. experimental results confirm the accuracy and efficiency of bncit.
nemofinder: dissecting genome-wide protein-protein interactions with meso-scale network motifs. recent works in network analysis have revealed the existence of network motifs in biological networks such as the protein-protein interaction (ppi) networks. however, existing motif mining algorithms are not sufficiently scalable to find meso-scale network motifs. also, there has been little or no work to systematically exploit the extracted network motifs for dissecting the vast interactomes.we describe an efficient network motif discovery algorithm, nemofinder, that can mine meso-scale network motifs that are repeated and unique in large ppi networks. using nemofinder, we successfully discovered, for the first time, up to size-12 network motifs in a large whole-genome s. cerevisiae (yeast) ppi network. we also show that such network motifs can be systematically exploited for indexing the reliability of ppi data that were generated via highly erroneous high-throughput experimental methods.
enhanced word clustering for hierarchical text classification. in this paper we propose a new information-theoretic divisive algorithm for word clustering applied to text classification. in previous work, such "distributional clustering" of features has been found to achieve improvements over feature selection in terms of classification accuracy, especially at lower number of features [2, 28]. however the existing clustering techniques are agglomerative in nature and result in (i) sub-optimal word clusters and (ii) high computational cost. in order to explicitly capture the optimality of word clusters in an information theoretic framework, we first derive a global criterion for feature clustering. we then present a fast, divisive algorithm that monotonically decreases this objective function value, thus converging to a local minimum. we show that our algorithm minimizes the "within-cluster jensen-shannon divergence" while simultaneously maximizing the "between-cluster jensen-shannon divergence". in comparison to the previously proposed agglomerative strategies our divisive algorithm achieves higher classification accuracy especially at lower number of features. we further show that feature clustering is an effective technique for building smaller class models in hierarchical classification. we present detailed experimental results using naive bayes and support vector machines on the 20 newsgroups data set and a 3-level hierarchy of html documents collected from dmoz open directory.
a new two-phase sampling based algorithm for discovering association rules. this paper introduces fast, a novel two-phase sampling-based algorithm for discovering association rules in large databases. in phase i a large initial sample of transactions is collected and used to quickly and accurately estimate the support of each individual item in the database. in phase ii these estimated supports are used to either trim "outlier" transactions or select "representative" transactions from the initial sample, thereby forming a small final sample that more accurately reflects the statistical characteristics (i.e., itemset supports) of the entire database. the expensive operation of discovering association rules is then performed on the final sample. in an empirical study, fast was able to achieve 90--95% accuracy using a final sample having a size of only 15--33% of that of a comparable random sample. this efficiency gain resulted in a speedup by roughly a factor of 10 over previous algorithms that require expensive processing of the entire database --- even efficient algorithms that exploit sampling. our new sampling technique can be used in conjunction with almost any standard association-rule algorithm, and can potentially render scalable other algorithms that mine "count" data.
information-theoretic co-clustering. two-dimensional contingency or co-occurrence tables arise frequently in important applications such as text, web-log and market-basket data analysis. a basic problem in contingency table analysis is co-clustering: simultaneous clustering of the rows and columns. a novel theoretical formulation views the contingency table as an empirical joint probability distribution of two discrete random variables and poses the co-clustering problem as an optimization problem in information theory---the optimal co-clustering maximizes the mutual information between the clustered random variables subject to constraints on the number of row and column clusters. we present an innovative co-clustering algorithm that monotonically increases the preserved mutual information by intertwining both the row and column clusterings at all stages. using the practical example of simultaneous word-document clustering, we demonstrate that our algorithm works well in practice, especially in the presence of sparsity and high-dimensionality.
failure detection and localization in component based systems by online tracking. the increasing complexity of today's systems makes fast and accurate failure detection essential for their use in mission-critical applications. various monitoring methods provide a large amount of data about system's behavior. analyzing this data with advanced statistical methods holds the promise of not only detecting the errors faster, but also detecting errors which are difficult to catch with current monitoring tools. two challenges to building such detection tools are: the high dimensionality of observation data, which makes the models expensive to apply, and frequent system changes, which make the models expensive to update. in this paper, we present algorithms to reduce the dimensionality of data in a way that makes it easy to adapt to system changes. we decompose the observation data into signal and noise subspaces. two statistics, the hotelling t2 score and squared prediction error (spe) are calculated to represent the data characteristics in signal and noise subspaces respectively. instead of tracking the original data, we use a sequentially discounting expectation maximization (sdem) algorithm to learn the distribution of the two extracted statistics. a failure event can then be detected based on the abnormal change of the distribution. applying our technique to component interaction data in a simple e-commerce application shows better accuracy than building independent profiles for each component. additionally, experiments on synthetic data show that the detection accuracy is high even for changing systems.
a spectral method to separate disconnected and nearly-disconnected web graph components. separation of connected components from a graph with disconnected graph components mostly use breadth-first search (bfs) or depth-first search (dfs) graph algorithms. here we propose a new algebraic method to separate disconnected and nearly-disconnected components. this method is based on spectral graph partitioning, following a key observation that disconnected components will show up, after properly sorted, as step-function like curve in the lowest eigenvectors of the laplacian matrix of the graph. following an perturbative analysis framework, we systematically analyzed the graph structures, first on the disconnected subgraph case, and second on the effects of adding edges sparsely connecting different subgraphs as a perturbation. several new results are derived, providing insights to spectral methods and related clustering objective function. examples are given illustrating the concepts and results our methods. comparing to the standard graph algorithms, this method has the same o(&verbar;e &verbar; + &verbar;v&verbar;log(&verbar;v&verbar;)) complexity, but is easier to implement (using readily available eigensolvers). further more the method can easily identify articulation points and bridges on nearly-disconnected graphs. segmentation of a real example of web graph for query amazon is given. we found that each disconnected or nearly-disconnected components forms a cluster on a clear topic.
orthogonal nonnegative matrix t-factorizations for clustering. currently, most research on nonnegative matrix factorization (nmf)focus on 2-factor $x=fg^t$ factorization. we provide a systematicanalysis of 3-factor $x=fsg^t$ nmf. while it unconstrained 3-factor nmf is equivalent to it unconstrained 2-factor nmf, itconstrained 3-factor nmf brings new features to it constrained 2-factor nmf. we study the orthogonality constraint because it leadsto rigorous clustering interpretation. we provide new rules for updating $f,s, g$ and prove the convergenceof these algorithms. experiments on 5 datasets and a real world casestudy are performed to show the capability of bi-orthogonal 3-factornmf on simultaneously clustering rows and columns of the input datamatrix. we provide a new approach of evaluating the quality ofclustering on words using class aggregate distribution andmulti-peak distribution. we also provide an overview of various nmf extensions andexamine their relationships.
gess: a scalable similarity-join algorithm for mining large data sets in high dimensional spaces. the similarity join is an important operation for mining high-dimensional feature spaces. given two data sets, the similarity join computes all tuples (x, y) that are within a distance &egr;.one of the most efficient algorithms for processing similarity-joins is the multidimensional-spatial join (msj) by koudas and sevcik. in our previous work --- pursued for the two-dimensional case --- we found however that msj has several performance shortcomings in terms of cpu and i/o cost as well as memory-requirements. therefore, msj is not generally applicable to high-dimensional data.in this paper, we propose a new algorithm named generic external space sweep (gess). gess introduces a modest rate of data replication to reduce the number of expensive distance computations. we present a new cost-model for replication, an i/o model, and an inexpensive method for duplicate removal. the principal component of our algorithm is a highly flexible replication engine.our analytical model predicts a tremendous reduction of the number of expensive distance computations by several orders of magnitude in comparison to msj (factor 107). in addition, the memory requirements of gess are shown to be lower by several orders of magnitude. furthermore, the i/o cost of our algorithm is by factor 2 better (independent from the fact whether replication occurs or not). our analytical results are confirmed by a large series of simulations and experiments with synthetic and real high-dimensional data sets.
web mining from competitors' websites. this paper presents a framework for user-oriented text mining. it is then illustrated with an example of discovering knowledge from competitors' websites. the knowledge to be discovered is in the form of association rules. a user's background knowledge is represented as a concept hierarchy developed from documents on his/her own website. the concept hierarchy captures the semantic usage of words and relationships among words in background documents. association rules are identified among the noun phrases extracted from documents on competitors' websites. the interestingness measure, i.e. novelty, which measures the semantic distance between the antecedent and the consequent of a rule in the background knowledge, is computed from the co-occurrence frequency of words and the connection lengths among words in the concept hierarchy. a user evaluation of the novelty of discovered rules demonstrates that the correlation between the algorithm and the human judges is comparable to that between human judges.
incspan: incremental mining of sequential patterns in large database. many real life sequence databases grow incrementally. it is undesirable to mine sequential patterns from scratch each time when a small set of sequences grow, or when some new sequences are added into the database. incremental algorithm should be developed for sequential pattern mining so that mining can be adapted to incremental database updates. however, it is nontrivial to mine sequential patterns incrementally, especially when the existing sequences grow incrementally because such growth may lead to the generation of many new patterns due to the interactions of the growing subsequences with the original ones. in this study, we develop an efficient algorithm, incspan, for incremental mining of sequential patterns, by exploring some interesting properties. our performance study shows that incspan outperforms some previously proposed incremental algorithms as well as a non-incremental one with a wide margin.
secret: a scalable linear regression tree algorithm. developing regression models for large datasets that are both accurate and easy to interpret is a very important data mining problem. regression trees with linear models in the leaves satisfy both these requirements, but thus far, no truly scalable regression tree algorithm is known. this paper proposes a novel regression tree construction algorithm (secret) that produces trees of high quality and scales to very large datasets. at every node, secret uses the em algorithm for gaussian mixtures to find two clusters in the data and to locally transform the regression problem into a classification problem based on closeness to these clusters. goodness of split measures, like the gini gain, can then be used to determine the split variable and the split point much like in classification tree construction. scalability of the algorithm can be achieved by employing scalable versions of the em and classification tree construction algorithms. an experimental evaluation on real and artificial data shows that secret has accuracy comparable to other linear regression tree algorithms but takes orders of magnitude less computation time for large datasets.
instability of decision tree classification algorithms. the instability problem of decision tree classification algorithms is that small changes in input training samples may cause dramatically large changes in output classification rules. different rules generated from almost the same training samples are against human intuition and complicate the process of decision making. in this paper, we present fundamental theorems for the instability problem of decision tree classifiers. the first theorem gives the relationship between a data change and the resulting tree structure change (i.e. split change). the second theorem, instability theorem, provides the cause of the instability problem. based on the two theorems, algorithmic improvements can be made to lessen the instability problem. empirical results illustrate the theorem statements. the trees constructed by the proposed algorithm are more stable, noise-tolerant, informative, expressive, and concise. our proposed sensitivity measure can be used as a metric to evaluate the stability of splitting predicates. the tree sensitivity is an indicator of the confidence level in rules and the effective lifetime of rules.