waashk/dblp huggingface dataset:
mining statistical information of frequent fault-tolerant patterns in transactional databases. constraints applied on classic frequent patterns are too strict and may cause interesting patterns to be missed. hence, researchers have proposed to mine a more relaxed version of frequent patterns, where transactions are allowed to miss some items in the itemset they support. patterns exhibiting such "faults" are called frequent fault-tolerant patterns (fft-patterns) if they are significant in number. in this paper, the term "pattern" is distinguished from "itemset" as referring to a pair (tidset × itemset). unlike classical frequent patterns, the number of fftpatterns grows exponentially not only with the number of items, but also with the number of transactions. since the latter may reach millions, mining fft-patterns by enumerating them becomes infeasible. hence, the challenge is to represent fft-patterns concisely without losing any useful information. to address this, we draw on the observation that, in transactional databases, the transactions themselves are not important from the data mining point-ofview; i.e. researchers are interested in finding itemsets contained in lots of transactions, rather than in the transactions per se. therefore, we propose to mine only the frequent itemsets along with the statistical information of the supporting transaction sets, rather than enumerate entire fftpatterns. then we present our approach the bias framework, consisting of backtracking algorithm, integer linear programming (ilp) constraints, and aggregation statistics to solve this problem. algorithms under this framework not only increase the efficiency of the fft-patterns mining process by more than an order of magnitude, but also provide a more comprehensive analysis of fft-patterns.
on appropriate assumptions to mine data streams: analysis and practice. recent years have witnessed an increasing number of studies in stream mining, which aim at building an accurate model for continuously arriving data. somehow most existing work makes the implicit assumption that the training data and the yet-to-come testing data are always sampled from the "same distribution, and yet this "same distribution evolves over time. we demonstrate that this may not be true, and one actually may never know either "how or "when the distribution changes. thus, a model that fits well on the observed distribution can have unsatisfactory accuracy on the incoming data. practically, one can just assume the bare minimum that learning from observed data is better than both random guessing and always predicting exactly the same class label. importantly, we formally and experimentally demonstrate the robustness of a model averaging and simple voting-based framework for data streams, particularly when incoming data "continuously follows significantly different distributions. on a real streaming data, this framework reduces the expected error of baseline models by 60%, and remains the most accurate compared to those baseline models.
can the content of public news be used to forecast abnormal stock market behaviour? a popular theory of markets is that they are efficient: all available information is deemed to provide an accurate valuation of an asset at any time. in this paper, we consider how the content of marketrelated news articles contributes to such information. specifically, we mine news articles for terms of interest, and quantify this degree of interest. we then incorporate this measure into traditional models for market index volatility with a view to forecasting whether the incidence of interesting news is correlated with a shock in the index, and thus if the information can be captured to value the underlying asset. we illustrate the methodology on stock market indices for the usa, the uk, and australia.
a pairwise covariance-preserving projection method for dimension reduction. dimension reduction is critical in many areas of pattern classification and machine learning and many discriminant analysis algorithms have been proposed. in this paper, a pairwise covariance-preserving projection method (pcpm) is proposed for dimension reduction. pcpm maximizes the class discrimination and also preserves approximately the pairwise class covariances. the optimization involved in pcpm can be solved directly by eigenvalues decomposition. our theoretical and empirical analysis reveals the relationship between pcpm and linear discriminant analysis (lda), sliced average variance estimator (save), heteroscedastic discriminant analysis (hda) and covariance preserving projection method (cpm). pcpm can utilize class mean and class covariance information at the same time. furthermore, pairwise weight scheme can be incorporated naturally with the pairwise summarization form. the proposed methods are evaluated by both synthetic and real-world datasets.
preserving privacy through data generation. many databases will not or can not be disclosed without strong guarantees that no sensitive information can be extracted. to address this concern several data perturbation techniques have been proposed. however, it has been shown that either sensitive information can still be extracted from the perturbed data with little prior knowledge, or that many patterns are lost. in this paper we show that generating new data is an inherently safer alternative. we present a data generator based on the models obtained by the mdlbased krimp [12] algorithm. these are accurate representations of the data distributions and can thus be used to generate data with the same characteristics as the original data. experimental results show a very large patternsimilarity between the generated and the original data, ensuring that viable conclusions can be drawn from the anonymised data. furthermore, anonymity is guaranteed for suited databases and the quality privacy trade-off can be balanced explicitly.
efficient discovery of frequent approximate sequential patterns. we propose an efficient algorithm for mining frequent approximate sequential patterns under the hamming distance model. our algorithm gains its efficiency by adopting a "break-down-and-build-up" methodology. the "breakdown" is based on the observation that all occurrences of a frequent pattern can be classified into groups, which we call strands. we developed efficient algorithms to quickly mine out all strands by iterative growth. in the "build-up" stage, these strands are grouped up to form the support sets from which all approximate patterns would be identified. a salient feature of our algorithm is its ability to grow the frequent patterns by iteratively assembling building blocks of significant sizes in a local search fashion. by avoiding incremental growth and global search, we achieve greater efficiency without losing the completeness of the mining result. our experimental studies demonstrate that our algorithm is efficient in mining globally repeating approximate sequential patterns that would have been missed by existing methods.
mining interpretable human strategies: a case study. this paper focuses on mining human strategies by observing their actions. our application domain is an hci study aimed at discovering general strategies used by software users and understanding how such strategies relate to gender and success. we cast this as a sequential pattern discovery problem, where user strategies are manifested as sequential patterns. problematically, we found that the patterns discovered by standard algorithms were difficult to interpret and provided limited information about high-level strategies. to help interpret the patterns and extract general strategies, we examined multiple ways of clustering the patterns into meaningful groups, which collectively led to interesting findings about user behavior both in terms of gender differences and problem-solving success. as a real-world application of data mining techniques, our work led to the discovery of new strategic patterns that are linked to user success and had not been revealed in more than nine years of manual empirical work. as a case study, our work highlights important research directions for making data mining more accessible to non-experts.
disk aware discord discovery: finding unusual time series in terabyte sized datasets. the problem of finding unusual time series has recently attracted much attention, and several promising methods are now in the literature. however, virtually all proposed methods assume that the data reside in main memory. for many real-world problems this is not be the case. for example, in astronomy, multi-terabyte time series datasets are the norm. most current algorithms faced with data which cannot fit in main memory resort to multiple scans of the disk/tape and are thus intractable. in this work we show how one particular definition of unusual time series, the time series discord, can be discovered with a disk aware algorithm. the proposed algorithm is exact and requires only two linear scans of the disk with a tiny buffer of main memory. furthermore, it is very simple to implement. we use the algorithm to provide further evidence of the effectiveness of the discord definition in areas as diverse as astronomy, web query mining, video surveillance, etc., and show the efficiency of our method on datasets which are many orders of magnitude larger than anything else attempted in the literature.
incorporating user provided constraints into document clustering. document clustering without any prior knowledge or background information is a challenging problem. in this paper, we propose ss-nmf: a semi-supervised nonnegative matrix factorization framework for document clustering. in ss-nmf, users are able to provide supervision for document clustering in terms of pairwise constraints on a few documents specifying whether they "must" or "cannot" be clustered together. through an iterative algorithm, we perform symmetric tri-factorization of the documentdocument similarity matrix to infer the document clusters. theoretically, we show that ss-nmf provides a general framework for semi-supervised clustering and that existing approaches can be considered as special cases of ss-nmf. through extensive experiments conducted on publicly available data sets, we demonstrate the superior performance of ss-nmf for clustering documents.
a support vector approach to censored targets. censored targets, such as the time to events in survival analysis, can generally be represented by intervals on the real line. in this paper, we propose a novel support vector technique (named svcr) for regression on censored targets. svcr inherits the strengths of support vector methods, such as a globally optimal solution by convex programming, fast training speed and strong generalization capacity. in contrast to ranking approaches to survival analysis, our approach is able not only to achieve superior ordering performance, but also to predict the survival time very well. experiments show a significant performance improvement when the majority of the training data is censored. experimental results on several survival analysis datasets demonstrate that svcr is very competitive against classical survival analysis models.
supervised learning by training on aggregate outputs. supervised learning is a classic data mining problem where one wishes to be be able to predict an output value associated with a particular input vector. we present a new twist on this classic problem where, instead of having the training set contain an individual output value for each input vector, the output values in the training set are only given in aggregate over a number of input vectors. this new problem arose from a particular need in learning on mass spectrometry data, but could easily apply to situations when data has been aggregated in order to maintain privacy. we provide a formal description of this new problem for both classification and regression. we then examine how k-nearest neighbor, neural networks, and support vector machines can be adapted for this problem.
cocktail ensemble for regression. this paper is motivated to improve the performance of individual ensembles using a hybrid mechanism in the regression setting. based on an error-ambiguity decomposition, we formally analyze the optimal linear combination of two base ensembles, which is then extended to multiple individual ensembles via pairwise combinations. the cocktail ensemble approach is proposed based on this analysis. experiments over a broad range of data sets show that the proposed approach outperforms the individual ensembles, two other methods of ensemble combination, and two stateof-the-art regression approaches.
how much noise is too much: a study in automatic text classification. noise is a stark reality in real life data. especially in the domain of text analytics, it has a significant impact as data cleaning forms a very large part of the data processing cycle. noisy unstructured text is common in informal settings such as on-line chat, sms, email, newsgroups and blogs, automatically transcribed text from speech, and automatically recognized text from printed or handwritten material. gigabytes of such data is being generated everyday on the internet, in contact centers, and on mobile phones. researchers have looked at various text mining issues such as pre-processing and cleaning noisy text, information extraction, rule learning, and classification for noisy text. this paper focuses on the issues faced by automatic text classifiers in analyzing noisy documents coming from various sources. the goal of this paper is to bring out and study the effect of different kinds of noise on automatic text classification. does the nature of such text warrant moving beyond traditional text classification techniques? we present detailed experimental results with simulated noise on the reuters21578 and 20-newsgroups benchmark datasets. we present interesting results on real-life noisy datasets from various crm domains.
topical n-grams: phrase and topic discovery, with an application to information retrieval. most topic models, such as latent dirichlet allocation, rely on the bag-of-words assumption. however, word order and phrases are often critical to capturing the meaning of text in many text mining tasks. this paper presents topical n-grams, a topic model that discovers topics as well as topical phrases. the probabilistic model generates words in their textual order by, for each word, first sampling a topic, then sampling its status as a unigram or bigram, and then sampling the word from a topic-specific unigram or bigram distribution. thus our model can model "white house" as a special meaning phrase in the `politics' topic, but not in the `real estate' topic. successive bigrams form longer phrases. we present experiments showing meaningful phrases and more interpretable topics from the nips data and improved information retrieval performance on a trec collection.
consensus clusterings. in this paper we address the problem of combining multiple clusterings without access to the underlying features of the data. this process is known in the literature as clustering ensembles, clustering aggregation, or consensus clustering. consensus clustering yields a stable and robust final clustering that is in agreement with multiple clusterings. we find that an iterative em-like method is remarkably effective for this problem. we present an iterative algorithm and its variations for finding clustering consensus. an extensive empirical study compares our proposed algorithms with eleven other consensus clustering methods on four data sets using three different clustering performance metrics. the experimental results show that the new ensemble clustering methods produce clusterings that are as good as, and often better than, these other methods.
spectral regression: a unified approach for sparse subspace learning. recently the problem of dimensionality reduction (or, subspace learning) has received a lot of interests in many fields of information processing, including data mining, information retrieval, and pattern recognition. some popular methods include principal component analysis (pca), linear discriminant analysis (lda) and locality preserving projection (lpp). however, a disadvantage of all these approaches is that the learned projective functions are linear combinations of all the original features, thus it is often difficult to interpret the results. in this paper, we propose a novel dimensionality reduction framework, called unified sparse subspace learning (ussl), for learning sparse projections. ussl casts the problem of learning the projective functions into a regression framework, which facilitates the use of different kinds of regularizers. by using a l1-norm regularizer (lasso), the sparse projections can be efficiently computed. experimental results on real world classification and clustering problems demonstrate the effectiveness of our method.
data discretization unification. data discretization is defined as a process of converting continuous data attribute values into a finite set of intervals with minimal loss of information. in this paper, we prove that discretization methods based on informational theoretical complexity and the methods based on statistical measures of data dependency are asymptotically equivalent. furthermore, we define a notion of generalized entropy and prove that discretization methods based on minimal description length principle, gini index, aic, bic, and pearson&#x2019;s x 2 and g 2 statistics are all derivable from the generalized entropy function. we design a dynamic programming algorithm that guarantees the best discretization based on the generalized entropy notion. furthermore, we conducted an extensive performance evaluation of our method for several publicly available data sets. our results show that our method delivers on the average 31% less classification errors than many previously known discretization methods.
temporal analysis of semantic graphs using asalsan. asalsan is a new algorithm for computing three-way dedicom, which is a linear algebra model for analyzing intrinsically asymmetric relationships, such as trade among nations or the exchange of emails among individuals, that incorporates a third mode of the data, such as time. asalsan is unique because it enables computing the three-way dedicom model on large, sparse data. a nonnegative version of asalsan is described as well. when we apply these techniques to adjacency arrays arising from directed graphs with edges labeled by time, we obtain a smaller graph on latent semantic dimensions and gain additional information about their changing relationships over time. we demonstrate these techniques on international trade data and the enron email corpus to uncover latent components and their transient behavior. the mixture of roles assigned to individuals by asalsan showed strong correspondence with known job classifications and revealed the patterns of communication between these roles. changes in the communication pattern over time, e.g., between top executives and the legal department, were also apparent in the solutions.
discovering temporal communities from social network documents. this paper studies the discovery of communities from social network documents produced over time, addressing the discovery of temporal trends in community memberships. we first formulate static community discovery at a single time period as a tripartite graph partitioning problem. then we propose to discover the temporal communities by threading the statically derived communities in different time periods using a new constrained partitioning algorithm, which partitions graphs based on topology as well as prior information regarding vertex membership. we evaluate the proposed approach on synthetic datasets and a real-world dataset prepared from the citeseer.
optimizing frequency queries for data mining applications. data mining algorithms use various trie and bitmap-based representations to optimize the support (i.e., frequency) counting performance. in this paper, we compare the memory requirements and support counting performance of fp tree, and compressed patricia trie against several novel variants of vertical bit vectors. first, borrowing ideas from the vldb domain, we compress vertical bit vectors using wah encoding. second, we evaluate the gray code rankbased transaction reordering scheme, and show that in practice, simple lexicographic ordering, obtained by applying lsb radix sort, outperforms this scheme. led by these results, we propose hdo, a novel hamming-distance-based greedy transaction reordering scheme, and ahdo, a linear-time approximation to hdo. we present results of experiments performed on 15 common datasets with varying degrees of sparseness, and show that hdoreordered, wah encoded bit vectors can take as little as 5% of the uncompressed space, while ahdo achieves similar compression on sparse datasets. finally, with results from over a billion database and data mining style frequency query executions, we show that bitmap-based approaches result in up to hundreds of times faster support counting, and hdo-wah encoded bitmaps offer the best space-time tradeoff.
training conditional random fields by periodic step size adaptation for large-scale text mining. for applications with consecutive incoming training examples, on-line learning has the potential to achieve a likelihood as high as off-line learning without scanning all available training examples and usually has a much smaller memory footprint. to train crfs on-line, this paper presents the periodic step size adaptation (psa) method to dynamically adjust the learning rates in stochastic gradient descent. we applied our method to three large scale text mining tasks. experimental results show that psa outperforms the best off-line algorithm, l-bfgs, by many hundred times, and outperforms the best on-line algorithm, smd, by an order of magnitude in terms of the number of passes required to scan the training data set.
latent dirichlet conditional naive-bayes models. in spite of the popularity of probabilistic mixture models for latent structure discovery from data, mixture models do not have a natural mechanism for handling sparsity, where each data point only has a few non-zero observations. in this paper, we introduce conditional naive-bayes (cnb) models, which generalize naive-bayes mixture models to naturally handle sparsity by conditioning the model on observed features. further, we present latent dirichlet conditional naive-bayes (ld-cnb) models, which constitute a family of powerful hierarchical bayesian models for latent structure discovery from sparse data. the proposed family of models are quite general and can work with arbitrary regular exponential family conditional distributions. we present a variational inference based em algorithm for learning along with special case analyses for gaussian and discrete distributions. the efficacy of the proposed models are demonstrated by extensive experiments on a wide variety of different datasets.