waashk/dblp huggingface dataset:
prism: a primal-encoding approach for frequent sequence mining. sequence mining is one of the fundamental data mining tasks. in this paper we present a novel approach called prism, for mining frequent sequences. prism utilizes a vertical approach for enumeration and support counting, based on the novel notion of prime block encoding, which in turn is based on prime factorization theory. via an extensive evaluation on both synthetic and real datasets, we show that prism outperforms popular sequence mining methods like spade [10], prefixspan [6] and spam [2], by an order of magnitude or more.
succinct matrix approximation and efficient k-nn classification. this work reveals that instead of the polynomial bounds in previous literatures there exists a sharper bound of exponential form for the l2 norm of an arbitrary shaped random matrix. based on the newly elaborated bound, a nonuniform sampling method is presented to succinctly approximate a matrix with a sparse binary one, and thus relieves the computation loads of k-nn classifier in both time and storage. the method is also pass-efficient because sampling and quantizing are combined together in a single step and the whole process can be completed within one pass over the input matrix. in the evaluations on compression ratio and reconstruction error, the sampling method exhibits impressive capability in providing succinct and tight approximations for the input matrices. the most significant finding in the classification experiment is that the k-nn classifier based on the approximation can even outperform the standard one. this provides another strong evidence for the claim that our method is especially capable in capturing intrinsic characteristics.
incremental subspace clustering over multiple data streams. data streams are often locally correlated, with a subset of streams exhibiting coherent patterns over a subset of time points. subspace clustering can discover clusters of objects in different subspaces. however, traditional subspace clustering algorithms for static data sets are not readily used for incremental clustering, and is very expensive for frequent re-clustering over dynamically changing stream data. in this paper, we present an efficient incremental subspace clustering algorithm for multiple streams over sliding windows. our algorithm detects all the -cc-clusters, which capture the coherent changing patterns among a set of streams over a set of time points. -cc-clusters are incrementally generated by traversing a directed acyclic graph pdag. we propose efficient insertion and deletion operations to update the pdag dynamically. in addition, effective pruning techniques are applied to reduce the search space. experiments on real data sets demonstrate the performance of our algorithm.
bayesian folding-in with dirichlet kernels for plsi. probabilistic latent semantic indexing (plsi) represents documents of a collection as mixture proportions of latent topics, which are learned from the collection by an expectation maximization (em) algorithm. new documents or queries need to be folded into the latent topic space by a simplified version of the em-algorithm. during plsifolding-in of a new document, the topic mixtures of the known documents are ignored. this may lead to a suboptimal model of the extended collection. our new approach incorporates the topic mixtures of the known documents in a bayesian way during foldingin. that knowledge is modeled as prior distribution over the topic simplex using a kernel density estimate of dirichlet kernels. we demonstrate the advantages of the new bayesian folding-in using real text data.
a semantic kernel for semi-structured documents. natural language processing has emerged as an active field of research in the machine learning community. several methods based on statistical information have been proposed. however, with the linguistic complexity of the texts, semantic-based approaches have been investigated. in this paper, we propose a semantic kernel for semistructured biomedical documents. the semantic meanings of words are extracted using the umls framework. the kernel, with a svm classifier, has been applied to a text categorization task on a medical corpus of free text documents. the results have shown that the semantic kernel outperforms the linear kernel and the naive bayes classifier. moreover, this kernel was ranked in the top ten of the best algorithms among 44 classification methods at the 2007 cmc medical nlp international challenge.
community learning by graph approximation. learning communities from a graph is an important problem in many domains. different types of communities can be generalized as link-pattern based communities. in this paper, we propose a general model based on graph approximation to learn link-pattern based community structures from a graph. the model generalizes the traditional graph partitioning approaches and is applicable to learning various community structures. under this model, we derive a family of algorithms which are flexible to learn various community structures and easy to incorporate the prior knowledge of the community structures. experimental evaluation and theoretical analysis show the effectiveness and great potential of the proposed model and algorithms.
detecting fractures in classifier performance. a fundamental tenet assumed by many classification algorithms is the presumption that both training and testing samples are drawn from the same distribution of data this is the stationary distribution assumption. this entails that the past is strongly indicative of the future. however, in real world applications, many factors may alter the one true model responsible for generating the data distribution both significantly and subtly. in circumstances violating the stationary distribution assumption, traditional validation schemes such as ten-folds and hold-out become poor performance predictors and classifier rankers. thus, it becomes critical to discover the fracture points in classifier performance by discovering the divergence between populations. in this paper, we implement a comprehensive evaluation framework to identify bias, enabling selection of a "correct" classifier given the sample bias. to thoroughly evaluate the performance of classifiers within biased distributions, we consider the following three scenarios: missing completely at random (akin to stationary); missing at random; and missing not at random. the latter reflects the canonical sample selection bias problem.
co-ranking authors and documents in a heterogeneous network. recent graph-theoretic approaches have demonstrated remarkable successes for ranking networked entities, but most of their applications are limited to homogeneous networks such as the network of citations between publications. this paper proposes a novel method for co-ranking authors and their publications using several networks: the social network connecting the authors, the citation network connecting the publications, as well as the authorship network that ties the previous two together. the new co-ranking framework is based on coupling two random walks, that separately rank authors and documents following the pagerank paradigm. as a result, improved rankings of documents and their authors depend on each other in a mutually reinforcing way, thus taking advantage of the additional information implicit in the heterogeneous network of authors and documents.
transitional patterns and their significant milestones. mining frequent patterns in transaction databases has been studied extensively in data mining research. however, most of the existing frequent pattern mining algorithms do not consider the time stamps associated with the transactions. in this paper, we extend the existing frequent pattern mining framework to take into account the time stamp of each transaction and discover patterns whose frequency dramatically changes over time. we define a new type of patterns, called transitional patterns, to capture the dynamic behavior of frequent patterns in a transaction database. transitional patterns include both positive and negative transitional patterns. their frequencies increase/decrease dramatically at some time points of a transaction database. we introduce the concept of significant milestones for a transitional pattern, which are time points at which the frequency of the pattern changes most significantly. moreover, we develop an algorithm to mine from a transaction database the set of transitional patterns along with their significant milestones. our experimental studies on real-world databases illustrate that mining positive and negative transitional patterns is highly promising as a practical and useful approach to discovering novel and interesting knowledge from large databases.
failure prediction in ibm bluegene/l event logs. frequent failures are becoming a serious concern to the community of high-end computing, especially when the applications and the underlying systems rapidly grow in size and complexity. in order to develop effective fault-tolerant strategies, there is a critical need to predict failure events. to this end, we have collected detailed event logs from ibm bluegene/l, which has 128k processors, and is currently the fastest supercomputer in the world. in this study, we first show how the event records can be converted into a data set that is appropriate for running classification techniques. then we apply classifiers on the data, including ripper (a rule-based classifier), support vector machines (svms), a traditional nearest neighbor method, and a customized nearest neighbor method. we show that the customized nearest neighbor approach can outperform ripper and svms in terms of both coverage and precision. the results suggest that the customized nearest neighbor approach can be used to alleviate the impact of failures.
sample selection for maximal diversity. the problem of selecting a sample subset sufficient to preserve diversity arises in many applications. one example is in the design of recombinant inbred lines (ril) for genetic association studies. in this context, genetic diversity is measured by how many alleles are retained in the resulting inbred strains. ril panels that are derived from more than two parental strains, such as the collaborative cross [2, 14], present a particular challenge with regard to which of the many existing lab mouse strains should be included in the initial breeding funnel in order to maximize allele retention. a similar problem occurs in the study of customer reviews when selecting a subset of products with a maximal diversity in reviews. diversity in this case implies the presence of a set of products having both positive and negative ranks for each customer. in this paper, we demonstrate that selecting an optimal diversity subset is an np-complete problem via reduction to set cover. this reduction is sufficiently tight that greedy approximations to the set cover problem directly apply to maximizing diversity. we then suggest a slightly modified subset selection problem in which an initial greedy diversity solution is used to effectively prune an exhaustive search for all diversity subsets bounded from below by a specified coverage threshold. extensive experiments on real datasets are performed to demonstrate the effectiveness and efficiency of our approach.
semi-supervised document clustering via active learning with pairwise constraints. this paper investigates a framework that discovers pairwise constraints for semi-supervised text document clustering. an active learning approach is proposed to select informative document pairs for obtaining user feedbacks. a gain directed document pair selection method that measures how much we can learn by revealing the relationships between pairs of documents is designed. three different models, namely, uncertainty model, generation error model, and objective function model are proposed. language modeling is investigated for representing clusters in the semi-supervised document clustering approach.
improving text classification by using encyclopedia knowledge. the exponential growth of text documents available on the internet has created an urgent need for accurate, fast, and general purpose text classification algorithms. however, the "bag of words" representation used for these classification methods is often unsatisfactory as it ignores relationships between important terms that do not co-occur literally. in order to deal with this problem, we integrate background knowledge in our application: wikipedia into the process of classifying text documents. the experimental evaluation on reuters newsfeeds and several other corpus shows that our classification results with encyclopedia knowledge are much better than the baseline "bag of words" methods.
high-speed function approximation. we address a new learning problem where the goal is to build a predictive model that minimizes prediction time (the time taken to make a prediction) subject to a constraint on model accuracy. our solution is a generic framework that leverages existing data mining algorithms without requiring any modifications to these algorithms. we show a first application of our framework to a combustion simulation problem. our experimental evaluation shows significant improvements over existing methods; prediction time typically is improved by a factor between 2 and 6.
maximum entropy based significance of itemsets. we consider the problem of defining the significance of an itemset. we say that the itemset is significant if we are surprised by its frequency when compared to the frequencies of its sub-itemsets. in other words, we estimate the frequency of the itemset from the frequencies of its sub-itemsets and compute the deviation between the real value and the estimate. for the estimation we use maximum entropy and for measuring the deviation we use kullback-leibler divergence. a major advantage compared to the previous methods is that we are able to use richer models whereas the previous approaches only measure the deviation from the independence model. we show that our measure of significance goes to zero for derivable itemsets and that we can use the rank as a statistical test. our empirical results demonstrate that for our real datasets the independence assumption is too strong but applying more flexible models leads to good results.
computing correlation anomaly scores using stochastic nearest neighbors. this paper addresses the task of change analysis of correlated multi-sensor systems. the goal of change analysis is to compute the anomaly score of each sensor when we know that the system has some potential difference from a reference state. examples include validating the proper performance of various car sensors in the automobile industry. we solve this problem based on a neighborhood preservation principle -if the system is working normally, the neighborhood graph of each sensor is almost invariant against the fluctuations of experimental conditions. here a neighborhood graph is defined based on the correlation between sensor signals. with the notion of stochastic neighborhood, our method is capable of robustly computing the anomaly score of each sensor under conditions that are hard to be detected by other naive methods.
noise modeling with associative corruption rules. this paper presents an active learning approach to the problem of systematic noise inference and noise elimination, specifically the inference of associated corruption (ac) rules. ac rules are defined to simulate a common noise formation process in real-world data, in which the occurrence of an error on one attribute is dependent on several other attribute values. our approach consists of two algorithms, associative corruption forward (acf) and associative corruption backward (acb). algorithm acf is proposed for noise inference, and acb is designed for noise elimination. the experimental results show that the acf algorithm can infer the noise formation correctly, and acb indeed enhances the data quality for supervised learning.
local word bag model for text categorization. many text processing applications adopted the bag of words (bow) model representation of documents, in which each document is represented as a vector of weighted terms or n-grams, and then cosine distance between two vectors is used as the similarity measurement. although the great success in information retrieval and text categorization, the conventional bow model ignores the detailed local text information, i.e. the co-occurrence pattern of words at sentence or paragraph level. in this paper, we propose a novel approach to represent a document as a set of local tf-idf vectors, or what we called local word bags (lwb). by encapsulating local information distributed around a document into multiple lwbs, we can measure the similarity of two documents via the partial match of their corresponding local bags. to perform the matching efficiently, we introduce the local word bag kernel (lwb kernel), a variant of vgpyramid match kernel. the new kernel enables the discriminative machine learning methods like svm to compute the partial matching between two sets of lwbs in linear time after an one time hierarchical clustering procedure over all local bags at the initialization stage. experiments on real world datasets demonstrate the effectiveness of our new approach.
clustering needles in a haystack: an information theoretic analysis of minority and outlier detection. identifying atypical objects is one of the traditional topics in machine learning. recently, novel approaches, e.g., minority detection and one-class clustering, have explored further to identify clusters of atypical objects which strongly contrast from the rest of the data in terms of their distribution or density. this paper analyzes such tasks from an information theoretic perspective. based on information bottleneck formalization, these tasks interpret to increasing the averaged atypicalness of the clusters while reducing the complexity of the clustering. this formalization yields a unifying view of the new approaches as well as the classic outlier detection. we also present a scalable minimization algorithm which exploits the localized form of the cost function over individual clusters. the proposed algorithm is evaluated using simulated datasets and a text classification benchmark, in comparison with an existing method.
general averaged divergence analysis. subspace selection is a powerful tool in data mining. an important subspace method is the fisher rao linear discriminant analysis (lda), which has been successfully applied in many fields such as biometrics, bioinformatics, and multimedia retrieval. however, lda has a critical drawback: the projection to a subspace tends to merge those classes that are close together in the original feature space. if the separated classes are sampled from gaussian distributions, all with identical covariance matrices, then lda maximizes the mean value of the kullback leibler (kl) divergences between the different classes. we generalize this point of view to obtain a framework for choosing a subspace by 1) generalizing the kl divergence to the bregman divergence and 2) generalizing the arithmetic mean to a general mean. the framework is named the general averaged divergence analysis (gada). under this gada framework, a geometric mean divergence analysis (gmda) method based on the geometric mean is studied. a large number of experiments based on synthetic data show that our method significantly outperforms lda and several representative lda extensions.
unsupervised face annotation by mining the web. searching for images of people is an essential task for image and video search engines. however, current search engines have limited capabilities for this task since they rely on text associated with images and video, and such text is likely to return many irrelevant results. we propose a method for retrieving relevant faces of one person by learning the visual consistency among results retrieved from text correlation-based search engines. the method consists of two steps. in the first step, each candidate face obtained from a text-based search engine is ranked with a score that measures the distribution of visual similarities among the faces. faces that are possibly very relevant or irrelevant are ranked at the top or bottom of the list, respectively. the second step improves this ranking by treating this problem as a classification problem in which input faces are classified as ’person-x’ or ’non-person-x’; and the faces are re-ranked according to their relevant score inferred from the classifier’s probability output. to train this classifier, we use a bagging-based framework to combine results from multiple weak classifiers trained using different subsets. these training subsets are extracted and labeled automatically from the rank list produced from the classifier trained from the previous step. in this way, the accuracy of the ranked list increases after a number of iterations. experimental results on various face sets retrieved from captions of news photos show that the retrieval performance improved after each iteration, with the final performance being higher than those of the existing algorithms.
a randomized approach for approximating the number of frequent sets. we investigate the problem of counting the number of frequent (item)sets---a problem known to be intractable in terms of an exact polynomial time computation. in this paper, we show that it is in general also hard to approximate. subsequently, a randomized counting algorithm is developed using the markov chain monte carlo method. while for general inputs an exponential running time is needed in order to guarantee a certain approximation bound, we empirically show that the algorithm still has the desired accuracy on real-world datasets when its running time is capped polynomially.
iterative subgraph mining for principal component analysis. graph mining methods enumerate frequent subgraphs efficiently, but they are not necessarily good features for machine learning due to high correlation among features. thus it makes sense to perform principal component analysis to reducethe dimensionality and create decorrelated features. we present a novel iterative mining algorithm that captures informative patterns corresponding to major entries of top principal components. it repeatedly callsweighted substructure mining where example weights are updated in each iteration. the lanczos algorithm, a standard algorithm of eigen decomposition, is employed to update the weights. in experiments, our patterns are shown to approximate the principal components obtained by frequent mining.
redsom: relative density visualization of temporal changes in cluster structures using self-organizing maps. we introduce a self-organizing map (som) based visualization method that compares cluster structures in temporal datasets using relative density som (redsom) visualization. our method, combined with a distance matrix-based visualization, is capable of visually identifying emerging clusters, disappearing clusters, enlarging clusters, contracting clusters, the shifting of cluster centroids, and changes in cluster density. for example, when a region in a som becomes significantly more dense compared to an earlier som, and well separated from other regions, then the new region can be said to represent a new cluster. the capabilities of redsom are demonstrated using synthetic datasets, as well as real-life datasets from the world bank and the australian taxation office. the results on the real-life datasets demonstrate that changes identified interactively can be related to actual changes. the identification of such cluster changes is important in many contexts, including the exploration of changes in population behavior in the context of compliance and fraud in taxation.