waashk/dblp huggingface dataset:
frequent closed itemset mining using prefix graphs with an efficient flow-based pruning strategy. this paper presents pgminer, a novel graph-based algorithm for mining frequent closed itemsets. our approach consists of constructing a prefix graph structure and decomposing the database to variable length bit vectors, which are assigned to nodes of the graph. the main advantage of this representation is that the bit vectors at each node are relatively shorter than those produced by existing vertical mining methods. this facilitates fast frequency counting of itemsets via intersection operations. we also devise several internode and intra-node pruning strategies to substantially reduce the combinatorial search space. unlike other existing approaches, we do not need to store in memory the entire set of closed itemsets that have been mined so far in order to check whether a candidate itemset is closed. this dramatically reduces the memory usage of our algorithm, especially for low support thresholds. our experiments using synthetic and real-world data sets show that pgminer outperforms existing mining algorithms by as much as an order of magnitude and is scalable to very large databases.
mining latent associations of objects using a typed mixture model--a case study on expert/expertise mining. this paper studies the problem of discovering latent associations among objects in text documents. specifically, given two sets of objects and various types of co-occurrence data concerning the objects existing in texts, we aim to discover the hidden or latent associative relationships between the two sets of objects. existing methods are not directly applicable as they are unable to consider all this information. for example, the probabilistic mixture model called separable mixture model (smm) proposed by hofmann can use only one type of co-occurrences to mine latent associations. this paper proposes a more general probabilistic mixture model called the typed separable mixture model (tsmm), which is able to use all types of co-occurrences within a single framework. experimental results based on the expert/expertise mining task show that tsmm outperforms smm significantly.
boosting the feature space: text classification for unstructured data on the web. the issue of seeking efficient and effective methods for classifying unstructured text in large document corpora has received much attention in recent years. traditional document representation like bag-of-words encodes documents as feature vectors, which usually leads to sparse feature spaces with large dimensionality, thus making it hard to achieve high classification accuracies. this paper addresses the problem of classifying unstructured documents on the web. a classification approach is proposed that utilizes traditional feature reduction techniques along with a collaborative filtering method for augmenting document feature spaces. the method produces feature spaces with an order of magnitude less features compared with a baseline bag-of-words feature selection method. experiments on both real-world data and benchmark corpus indicate that our approach improves classification accuracy over the traditional methods for both support vector machines and adaboost classifiers.
an information theoretic approach to detection of minority subsets in database. detection of rare and exceptional occurrences in large-scale databases have become an important practice in the field of knowledge discovery and information retrieval. many databases include large amount of noise or irrelevant data, whose distribution often overlaps with the subsets of exceptional data containing useful knowledge. this paper addresses the problem of finding a small subset of "minority" data whose distribution overlaps with, but are exceptional to or inconsistent with that of the majority of the database. in such a case, conventional distance-based or density-based approaches in outlier detection are ineffective due to their dependence on the structure of the majority or the prerequisite of critical parameters. we formalize the task as an estimation of a model of the minority subset which provides a simple description of the subset and yet maintains divergence from that of the majority. this estimation is formalized as a minimization problem using an information theoretic framework of rate distortion theory. we further introduce conditions of the majority to derive an objective function which factorizes the property of the minority and dependence to the structure of the majority. the proposed method shows improvements from conventional approaches in artificial data and a promising result in document retrieval problem.
fast on-line kernel learning for trees. kernel methods have been shown to be very effective for applications requiring the modeling of structured objects. however kernels for structures usually are too computational demanding to be applied to complex learning algorithms, e.g. support vector machines. consequently, in order to apply kernels to large amount of structured data, we need fast on-line algorithms along with an efficiency optimization of kernel-based computations. in this paper, we optimize this computation by representing set of trees by minimal direct acyclic graphs (dags) allowing us i) to reduce the storage requirements and ii) to speed up the evaluation on large number of trees as it can be done 'one-shot' by computing kernels over dags. the experiments on predicate argument subtrees from propbank data show that substantial computational savings can be obtained for the perceptron algorithm.
learning to use a learned model: a two-stage approach to classification. association rule-based classifiers have recently emerged as competitive classification systems. however, there are still deficiencies that hinder their performance. one defi- ciency is the use of rules in the classification stage. current systems assign classes to new objects based on the best rule applied or on some predefined scoring of multiple rules. in this paper we propose a new technique where the system automatically learns how to use the rules. we achieve this by developing a two-stage classification model. first, we use association rule mining to discover classification rules. second, we employ another learning algorithm to learn how to use these rules in the prediction process. our two-stage approach outperforms c4.5 and ripper on the uci datasets in our study, and outperforms other rule-learning methods on more than half the datasets. the versatility of our method is also demonstrated by applying it to text classification, where it equals the performance of the best known systems for this task, svms.
bayesian state space modeling approach for measuring the effectiveness of marketing activities and baseline sales from pos data. analysis of point of sales (pos) data is an important research area of marketing science and knowledge discovery, which may enable marketing managers to attain the effective marketing activities. to measure the effectiveness of marketing activities and baseline sales, we develop the multivariate time series modeling method in the framework of a general state space model. a multivariate poisson model and a multivariate correlated auto-regressive model are used for a system model and an observation model. the bayesian approach via markov chain monte carlo (mcmc) algorithm is employed for estimating model parameters. to evaluate the goodness of the estimated models, the bayesian predictive information criterion is utilized. the proposed model is evaluated with its application to actual pos data.
detecting link spam using temporal information. how to effectively protect against spam on search ranking results is an important issue for contemporary web search engines. this paper addresses the problem of combating one major type of web spam: 'link spam.' most of the previous work on anti link spam managed to make use of one snapshot of web data to detect spam, and thus it did not take advantage of the fact that link spam tends to result in drastic changes of links in a short time period. to overcome the shortcoming, this paper proposes using temporal information on links in detection of link spam, as well as other information. specifically, it defines temporal features such as in-link growth rate (igr) and in-link death rate (idr) in a spam classification model (i.e., svm). experimental results on web domain graph data show that link spam can be successfully detected with the proposed method.
confident identification of relevant objects based on nonlinear rescaling method and transductive inference. we present a novel machine learning algorithm to identify relevant objects from a large amount of data. this approach is driven by linear discrimination based on nonlinear rescaling (nr) method and transductive inference. the nr algorithm for linear discrimination (nrld) computes both the primal and the dual approximation at each step. the dual variables associated with the given labeled dataset provide important information about the objects in the data-set and play the key role in ordering these objects. a confidence score based on a transductive inference procedure using nrld is used to rank and identify the relevant objects from a pool of unlabeled data. experimental results on an unbalanced protein data-set for the drug target prioritization and identification problem are used to illustrate the feasibility of the proposed identification algorithm.
lazy bagging for classifying imbalanced data. in this paper, we propose a lazy bagging (lb) design, which builds bootstrap replicate bags based on the characteristics of the test instances. upon receiving a test instance ik, lb will trim bootstrap bags by taking ik's nearest neighbors in the training set into consideration. our hypothesis is that an unlabeled instance's nearest neighbors provide valuable information for learners to refine their local decision boundaries for classifying this instance. by taking full advantage of ik's nearest neighbors, the base learners are able to receive less bias and variance in classifying ik. this strategy is beneficial for classifying imbalanced data because refining local decision boundaries can help a learner reduce its inherent bias towards the majority class and improve its performance on minority class examples. our experimental results will confirm that lb outperforms c4.5 and tb in terms of reducing classification error, and most importantly this error reduction is largely contributed from lb's improvement on minority class examples. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
efficient algorithms for mining significant substructures in graphs with quality guarantees. graphs have become popular for modeling scientific data in recent years. as a result, techniques for mining graphs are extremely important for understanding inherent data and domain characteristics. one such exploratory mining paradigm is the k-mst (minimum spanning tree over k vertices) problem that can be used to discover significant local substructures. in this paper, we present an efficient approximation algorithm for the k-mst problem in large graphs. the algorithm has an o (k) approximation ratio and o (n log n + m log m log k + nk2 log k) running time, where n and m are the number of vertices and edges respectively. experimental results on synthetic graphs and protein interaction networks show that the algorithm is scalable to large graphs and useful for discovering biological pathways. the highlight of the algorithm is that it offers both analytical guarantees and empirical evidence of good running time and quality.
finding predictive runs with laps. we present an extension to the lasso [6] for binary classification problems with ordered attributes. inspired by the fused lasso [5] and the group lasso [7, 3] models, we aim to both discover and model runs (contiguous subgroups of the variables) that are highly predictive. we call the extended model laps (the lasso with attribute partition search). such problems commonly arise in financial and medical domains, where predictors are time series variables, for example. this paper outlines the formulation of the problem, an algorithm to obtain the model coefficients and experiments showing applicability to practical problems of this type.
mining frequent itemsets in a stream. we study the problem of finding frequent itemsets in a continuous stream of transactions. the current frequency of an itemset in a stream is defined as its maximal frequency over all possible windows in the stream from any point in the past until the current state that satisfy a minimal length constraint. properties of this new measure are studied and an incremental algorithm that allows, at any time, to immediately produce the current frequencies of all frequent itemsets is proposed. experimental and theoretical analysis show that the space requirements for the algorithm are extremely small for many realistic data distributions.
extracting product comparisons from discussion boards. in recent years, product discussion forums have become a rich environment in which consumers and potential adopters exchange views and information. researchers and practitioners are starting to extract user sentiment about products from user product reviews. users often compare different products, stating which they like better and why. extracting information about product comparisons offers a number of challenges; recognizing and normalizing entities (products) in the informal language of blogs and discussion groups require different techniques than those used for entity extraction in the more formal text of newspapers and scientific articles. we present a case study in extracting information about comparisons between running shoes and between cars, describe an effective methodology, and show how it produces insight into how consumers view the running shoe and car markets.
dusc: dimensionality unbiased subspace clustering. to gain insight into today's large data resources, data mining provides automatic aggregation techniques. clustering aims at grouping data such that objects within groups are similar while objects in different groups are dissimilar. in scenarios with many attributes or with noise, clusters are often hidden in subspaces of the data and do not show up in the full dimensional space. for these applications, subspace clustering methods aim at detecting clusters in any subspace. existing subspace clustering approaches fall prey to an effect we call dimensionality bias. as dimensionality of subspaces varies, approaches which do not take this effect into account fail to separate clusters from noise. we give a formal definition of dimensionality bias and analyze consequences for subspace clustering. a dimensionality unbiased subspace clustering (dusc) definition based on statistical foundations is proposed. in thorough experiments on synthetic and real world data, we show that our approach outperforms existing subspace clustering algorithms.
block-iterative algorithms for non-negative matrix approximation. in this paper we present new algorithms for non-negative matrix approximation (nma), commonly known as the nmf problem. our methods improve upon the well-known methods of lee \& seung~\cite{lee00} for both the frobenius norm as well the kullback-leibler divergence versions of the problem. for the latter problem, our results are especially interesting because it seems to have witnessed much lesser algorithmic progress as compared to the frobenius norm nma problem. our algorithms are based on a particular \textbf {block-iterative} acceleration technique for em, which preserves the multiplicative nature of the updates and also ensures monotonicity. furthermore, our algorithms also naturally apply to the bregman-divergence nma algorithms of~\cite{suv.nips}. experimentally, we show that our algorithms outperform the traditional lee/seung approach most of the time.
cross-mining binary and numerical attributes. we consider the problem of relating itemsets mined on binary attributes of a data set to numerical attributes of the same data. an example is biogeographical data, where the numerical attributes correspond to environmental variables and the binary attributes encode the presence or absence of species in different environments. from the viewpoint of itemset mining, the task is to select a small collection of interesting itemsets using the numerical attributes; from the viewpoint of the numerical attributes, the task is to constrain the search for local patterns (e.g. clusters) using the binary attributes. we give a formal definition of the problem, discuss it theoretically, give a simple constant-factor approximation algorithm, and show by experiments on biogeographical data that the algorithm can capture interesting patterns that would not have been found using either itemset mining or clustering alone.
efficient kernel discriminant analysis via spectral regression. linear discriminant analysis (lda) has been a popular method for extracting features which preserve class separability. the projection vectors are commonly obtained by maximizing the between class covariance and simultaneously minimizing the within class covariance. lda can be performed either in the original input space or in the reproducing kernel hilbert space (rkhs) into which data points are mapped, which leads to kernel discriminant analysis (kda). when the data are highly nonlinear distributed, kda can achieve better performance than lda. however, computing the projective functions in kda involves eigen-decomposition of kernel matrix, which is very expensive when a large number of training samples exist. in this paper, we present a new algorithm for kernel discriminant analysis, called spectral regression kernel discriminant analysis (srkda). by using spectral graph analysis, srkda casts discriminant analysis into a regression framework which facilitates both efficient computation and the use of regularization techniques. specifically, srkda only needs to solve a set of regularized regression problems and there is no eigenvector computation involved, which is a huge save of computational cost. our computational analysis shows that srkda is 27 times faster than the ordinary kda. moreover, the new formulation makes it very easy to develop incremental version of the algorithm which can fully utilize the computational results of the existing training samples. experiments on face recognition demonstrate the effectiveness and efficiency of the proposed algorithm.
improving knowledge discovery in document collections through combining text retrieval and link analysis techniques. in this paper, we present concept chain queries (ccq), a special case of text mining in document collections focusing on detecting links between two topics across text documents. we interpret such a query as finding the most meaningful evidence trails across documents that connect these two topics. we propose to use link-analysis techniques over the extracted features provided by information extraction engine for finding new knowledge. a graphical text representation and mining model is proposed which combines information retrieval, association mining and link analysis techniques. we present experiments on different datasets that demonstrate the effectiveness of our algorithm. specifically, the algorithm generates ranked concept chains and evidence trails where the key terms representing significant relationships between topics are ranked high1.
the chosen few: on identifying valuable patterns. constrained pattern mining extracts patterns based on their individual merit. usually this results in far more patterns than a human expert or a machine learning technique could make use of. often different patterns or combinations of patterns cover a similar subset of the examples, thus being redundant and not carrying any new information. to remove the redundant information contained in such pattern sets, we propose a general heuristic approach for selecting a small subset of patterns. we identify several selection techniques for use in this general algorithm and evaluate those on several data sets. the results show that the technique succeeds in severely reducing the number of patterns, while at the same time apparently retaining much of the original information. additionally the experiments show that reducing the pattern set indeed improves the quality of classification results. both results show that the approach is very well suited for the goals we aim at.
change-point detection in time-series data based on subspace identification. in this paper, we propose series of algorithms for detecting change points in time-series data based on subspace identification, meaning a geometric approach for estimating linear state-space models behind time-series data. our algorithms are derived from the principle that the subspace spanned by the columns of an observability matrix and the one spanned by the subsequences of time-series data are approximately equivalent. in this paper, we derive an batchtype algorithm applicable to ordinary time-series data, i.e. consisting of only output series, and then introduce the online version of the algorithm and the extension to be available with input-output time-series data. we illustrate the effectiveness of our algorithms with comparative experiments using some artificial and real datasets.
using burstiness to improve clustering of topics in news streams. specialists who analyze online news have a hard time separating the wheat from the chaff. moreover, automatic data-mining techniques like clustering of news streams into topical groups can fully recover the underlying true class labels of data if and only if all classes are well separated. in reality, especially for news streams, this is clearly not the case. the question to ask is thus this: if we cannot recover the full c classes by clustering, what is the largest k \le c clusters we can find that best resemble the k underlying classes? using the intuition that bursty topics are more likely to correspond to important events that are of interest to analysts, we propose several new bursty vector space models (b-vsm) for representing a news document. b-vsm takes into account the burstiness (across the full corpus and whole duration) of each constituent word in a document at the time of publication. we benchmarked our b-vsm against the classical tfidf-vsm on the task of clustering a collection of news stream articles with known topic labels. experimental results show that b-vsm was able to find the burstiest clusters/topics. further, it also significantly improved the recall and precision for the top k clusters/topics.