waashk/dblp huggingface dataset:
a robust and scalable clustering algorithm for mixed type attributes in large database environment. clustering is a widely used technique in data mining applications to discover patterns in the underlying data. most traditional clustering algorithms are limited to handling datasets that contain either continuous or categorical attributes. however, datasets with mixed types of attributes are common in real life data mining problems. in this paper, we propose a distance measure that enables clustering data with both continuous and categorical attributes. this distance measure is derived from a probabilistic model that the distance between two clusters is equivalent to the decrease in log-likelihood function as a result of merging. calculation of this measure is memory efficient as it depends only on the merging cluster pair and not on all the other clusters. zhang et al [8] proposed a clustering method named birch that is especially suitable for very large datasets. we develop a clustering algorithm using our distance measure based on the framework of birch. similar to birch, our algorithm first performs a pre-clustering step by scanning the entire dataset and storing the dense regions of data records in terms of summary statistics. a hierarchical clustering algorithm is then applied to cluster the dense regions. apart from the ability of handling mixed type of attributes, our algorithm differs from birch in that we add a procedure that enables the algorithm to automatically determine the appropriate number of clusters and a new strategy of assigning cluster membership to noisy data. for data with mixed type of attributes, our experimental results confirm that the algorithm not only generates better quality clusters than the traditional k-means algorithms, but also exhibits good scalability properties and is able to identify the underlying number of clusters in the data correctly. the algorithm is implemented in the commercial data mining tool clementine 6.0 which supports the pmml standard of data mining model deployment.
efficient data reduction with ease. a variety of mining and analysis problems --- ranging from association-rule discovery to contingency table analysis to materialization of certain approximate datacubes --- involve the extraction of knowledge from a set of categorical count data. such data can be viewed as a collection of "transactions," where a transaction is a fixed-length vector of counts. classical algorithms for solving count-data problems require one or more computationally intensive passes over the entire database and can be prohibitively slow. one effective method for dealing with this ever-worsening scalability problem is to run the algorithms on a small sample of the data. we present a new data-reduction algorithm, called ease, for producing such a sample. like the fast algorithm introduced by chen et al., ease is especially designed for count data applications. both ease and fast take a relatively large initial random sample and then deterministically produce a subsample whose "distance" --- appropriately defined --- from the complete database is minimal. unlike fast, which obtains the final subsample by quasi-greedy descent, ease uses epsilon-approximation methods to obtain the final subsample by a process of repeated halving. experiments both in the context of association rule mining and classical &chi;2 contingency-table analysis show that ease outperforms both fast and simple random sampling, sometimes dramatically.
parallel mining of closed sequential patterns. discovery of sequential patterns is an essential data mining task with broad applications. among several variations of sequential patterns, closed sequential pattern is the most useful one since it retains all the information of the complete pattern set but is often much more compact than it. unfortunately, there is no parallel closed sequential pattern mining method proposed yet. in this paper we develop an algorithm, called par-csp (parallel closed sequential pattern mining), to conduct parallel mining of closed sequential patterns on a distributed memory system. par-csp partitions the work among the processors by exploiting the divide-and-conquer property so that the overhead of interprocessor communication is minimized. par-csp applies dynamic scheduling to avoid processor idling. moreover, it employs a technique, called selective sampling to address the load imbalance problem. we implement par-csp using mpi on a 64-node linux cluster. our experimental results show that par-csp attains good parallelization efficiencies on various input datasets.
model compression. often the best performing supervised learning models are ensembles of hundreds or thousands of base-level classifiers. unfortunately, the space required to store this many classifiers, and the time required to execute them at run-time, prohibits their use in applications where test sets are large (e.g. google), where storage space is at a premium (e.g. pdas), and where computational power is limited (e.g. hea-ring aids). we present a method for "compressing" large, complex ensembles into smaller, faster models, usually without significant loss in performance.
dualminer: a dual-pruning algorithm for itemsets with constraints. constraint-based mining of itemsets for questions such as "find all frequent itemsets where the total price is at least $50" has received much attention recently. two classes of constraints, monotone and antimonotone, have been identified as very useful. there are algorithms that efficiently take advantage of either one of these two classes, but no previous algorithms can efficiently handle both types of constraints simultaneously. in this paper, we present the first algorithm (called dualminer) that uses both monotone and antimonotone constraints to prune its search space. we complement a theoretical analysis and proof of correctness of dualminer with an experimental study that shows the efficacy of dualminer compared to previous work.
out-of-core frequent pattern mining on a commodity pc. in this work we focus on the problem of frequent itemset mining on large, out-of-core data sets. after presenting a characterization of existing out-of-core frequent itemset mining algorithms and their drawbacks, we introduce our efficient, highly scalable solution. presented in the context of the fpgrowth algorithm, our technique involves several novel i/o-conscious optimizations, such as approximate hash-based sorting and blocking, and leverages recent architectural advancements in commodity computers, such as 64-bit processing. we evaluate the proposed optimizations on truly large data sets,up to 75gb, and show they yield greater than a 400-fold execution time improvement. finally, we discuss the impact of this research in the context of other pattern mining challenges, such as sequence mining and graph mining.
data mining criteria for tree-based regression and classification. this paper is concerned with the construction of regression and classification trees that are more adapted to data mining applications than conventional trees. to this end, we propose new splitting criteria for growing trees. conventional splitting criteria attempt to perform well on both sides of a split by attempting a compromise in the quality of fit between the left and the right side. by contrast, we adopt a data mining point of view by proposing criteria that search for interesting subsets of the data, as opposed to modeling all of the data equally well. the new criteria do not split based on a compromise between the left and the right bucket; they effectively pick the more interesting bucket and ignore the other.as expected, the result is often a simpler characterization of interesting subsets of the data. less expected is that the new criteria often yield whole trees that provide more interpretable data descriptions. surprisingly, it is a "flaw" that works to their advantage: the new criteria have an increased tendency to accept splits near the boundaries of the predictor ranges. this so-called "end-cut problem" leads to the repeated peeling of small layers of data and results in very unbalanced but highly expressive and interpretable trees.
predicting customer shopping lists from point-of-sale purchase data. this paper describes a prototype that predicts the shopping lists for customers in a retail store. the shopping list prediction is one aspect of a larger system we have developed for retailers to provide individual and personalized interactions with customers as they navigate through the retail store. instead of using traditional personalization approaches, such as clustering or segmentation, we learn separate classifiers for each customer from historical transactional data. this allows us to make very fine-grained and accurate predictions about what items a particular individual customer will buy on a given shopping trip.we formally frame the shopping list prediction as a classification problem, describe the algorithms and methodology behind our system, its impact on the business case in which we frame it, and explore some of the properties of the data source that make it an interesting testbed for kdd algorithms. our results show that we can predict a shopper's shopping list with high levels of accuracy, precision, and recall. we believe that this work impacts both the data mining and the retail business community. the formulation of shopping list prediction as a machine learning problem results in algorithms that should be useful beyond retail shopping list prediction. for retailers, the result is not only a practical system that increases revenues by up to 11%, but also enhances customer experience and loyalty by giving them the tools to individually interact with customers and anticipate their needs.
classification features for attack detection in collaborative recommender systems. collaborative recommender systems are highly vulnerable to attack. attackers can use automated means to inject a large number of biased profiles into such a system, resulting in recommendations that favor or disfavor given items. since collaborative recommender systems must be open to user input, it is difficult to design a system that cannot be so attacked. researchers studying robust recommendation have therefore begun to identify types of attacks and study mechanisms for recognizing and defeating them. in this paper, we propose and study different attributes derived from user profiles for their utility in attack detection. we show that a machine learning classification approach that includes attributes derived from attack models is more successful than more generalized detection algorithms previously studied.
discovery net: towards a grid of knowledge discovery. this paper provides a blueprint for constructing collaborative and distributed knowledge discovery systems within grid-based computing environments. the need for such systems is driven by the quest for sharing knowledge, information and computing resources within the boundaries of single large distributed organisations or within complex virtual organisations (vo) created to tackle specific projects. the proposed architecture is built on top of a resource federation management layer and is composed of a set of different resources. we show how this architecture will behave during a typical kdd process design and deployment, how it enables the execution of complex and distributed data mining tasks with high performance and how it provides a community of e-scientists with means to collaborate, retrieve and reuse both kdd algorithms, discovery processes and knowledge in a visual analytical environment.
adversarial classification. essentially all data mining algorithms assume that the data-generating process is independent of the data miner's activities. however, in many domains, including spam detection, intrusion detection, fraud detection, surveillance and counter-terrorism, this is far from the case: the data is actively manipulated by an adversary seeking to make the classifier produce false negatives. in these domains, the performance of a classifier can degrade rapidly after it is deployed, as the adversary learns to defeat it. currently the only solution to this is repeated, manual, ad hoc reconstruction of the classifier. in this paper we develop a formal framework and algorithms for this problem. we view classification as a game between the classifier and the adversary, and produce a classifier that is optimal given the adversary's optimal strategy. experiments in a spam detection domain show that this approach can greatly outperform a classifier learned in the standard way, and (within the parameters of the problem) automatically adapt the classifier to the adversary's evolving manipulations.
probabilistic modeling of transaction data with applications to profiling, visualization, and prediction. transaction data is ubiquitous in data mining applications. examples include market basket data in retail commerce, telephone call records in telecommunications, and web logs of individual page-requests at web sites. profiling consists of using historical transaction data on individuals to construct a model of each individual's behavior. simple profiling techniques such as histograms do not generalize well from sparse transaction data. in this paper we investigate the application of probabilistic mixture models to automatically generate profiles from large volumes of transaction data. in effect, the mixture model represents each individual's behavior as a linear combination of "basis transactions." we evaluate several variations of the model on a large retail transaction data set and show that the proposed model provides improved predictive power over simpler histogram-based techniques, as well as being relatively scalable, interpretable, and flexible. in addition we point to applications in outlier detection, customer ranking, interactive visualization, and so forth. the paper concludes by comparing and relating the proposed framework to other transaction-data modeling techniques such as association rules.
mining rank-correlated sets of numerical attributes. we study the mining of interesting patterns in the presence of numerical attributes. instead of the usual discretization methods, we propose the use of rank based measures to score the similarity of sets of numerical attributes. new support measures for numerical data are introduced, based on extensions of kendall's tau, and spearman's footrule and rho. we show how these support measures are related. furthermore, we introduce a novel type of pattern combining numerical and categorical attributes. we give efficient algorithms to find all frequent patterns for the proposed support measures, and evaluate their performance on real-life datasets.
feature selection in scientific applications. numerous applications of data mining to scientific data involve the induction of a classification model. in many cases, the collection of data is not performed with this task in mind, and therefore, the data might contain irrelevant or redundant features that affect negatively the accuracy of the induction algorithms. the size and dimensionality of typical scientific data make it difficult to use any available domain information to identify features that discriminate between the classes of interest. similarly, exploratory data analysis techniques have limitations on the amount and dimensionality of the data they can process effectively. in this paper, we describe applications of efficient feature selection methods to data sets from astronomy, plasma physics, and remote sensing. we use variations of recently proposed filter methods as well as traditional wrapper approaches, where practical. we discuss the general challenges of feature selection in scientific datasets, the strategies for success that were common among our diverse applications, and the lessons learned in solving these problems.
probabilistic discovery of time series motifs. several important time series data mining problems reduce to the core task of finding approximately repeated subsequences in a longer time series. in an earlier work, we formalized the idea of approximately repeated subsequences by introducing the notion of time series motifs. two limitations of this work were the poor scalability of the motif discovery algorithm, and the inability to discover motifs in the presence of noise.here we address these limitations by introducing a novel algorithm inspired by recent advances in the problem of pattern discovery in biosequences. our algorithm is probabilistic in nature, but as we show empirically and theoretically, it can find time series motifs with very high probability even in the presence of noise or "don't care" symbols. not only is the algorithm fast, but it is an anytime algorithm, producing likely candidate motifs almost immediately, and gradually improving the quality of results over time.
gaining insights into support vector machine pattern classifiers using projection-based tour methods. this paper discusses visual methods that can be used to understand and interpret the results of classification using support vector machines (svm) on data with continuous real-valued variables. svm induction algorithms build pattern classifiers by identifying a maximal margin separating hyperplane from training examples in high dimensional pattern spaces or spaces induced by suitable nonlinear kernel transformations over pattern spaces. svm have been demonstrated to be quite effective in a number of practical pattern classification tasks. since the separating hyperplane is defined in terms of more than two variables it is necessary to use visual techniques that can navigate the viewer through high-dimensional spaces. we demonstrate the use of projection-based tour methods to gain useful insights into svm classifiers with linear kernels on 8-dimensional data.
belief state approaches to signaling alarms in surveillance systems. surveillance systems have long been used to monitor industrial processes and are becoming increasingly popular in public health and anti-terrorism applications. most early detection systems produce a time series of p-values or some other statistic as their output. typically, the decision to signal an alarm is based on a threshold or other simple algorithm such as cusum that accumulates detection information temporally.we formulate a pomdp model of underlying events and observations from a detector. we solve the model and show how it is used for single-output detectors. when dealing with spatio-temporal data, scan statistics are a popular method of building detectors. we describe the use of scan statistics in surveillance and how our pomdp model can be used to perform alarm signaling with them. we compare the results obtained by our method with simple thresholding and cusum on synthetic and semi-synthetic health data.
scalable discovery of hidden emails from large folders. the popularity of email has triggered researchers to look for ways to help users better organize the enormous amount of information stored in their email folders. one challenge that has not been studied extensively in text mining is the identification and reconstruction of hidden emails. a hidden email is an original email that has been quoted in at least one email in a folder, but does not present itself in the same folder. it may have been (un)intentionally deleted or may never have been received. the discovery and reconstruction of hidden emails is critical for many applications including email classification, summarization and forensics. this paper proposes a framework for reconstructing hidden emails using the embedded quotations found in messages further down the thread hierarchy. we evaluate the robustness and scalability of our framework by using the enron public email corpus. our experiments show that hidden emails exist widely in that corpus and also that our optimization techniques are effective in processing large email folders.
variable latent semantic indexing. latent semantic indexing is a classical method to produce optimal low-rank approximations of a term-document matrix. however, in the context of a particular query distribution, the approximation thus produced need not be optimal. we propose vlsi, a new query-dependent (or "variable") low-rank approximation that minimizes approximation error for any specified query distribution. with this tool, it is possible to tailor the lsi technique to particular settings, often resulting in vastly improved approximations at much lower dimensionality. we validate this method via a series of experiments on classical corpora, showing that vlsi typically performs similarly to lsi with an order of magnitude fewer dimensions.
making holistic schema matching robust: an ensemble approach. the web has been rapidly "deepened" by myriad searchable databases online, where data are hidden behind query interfaces. as an essential task toward integrating these massive "deep web" sources, large scale schema matching (i.e., discovering semantic correspondences of attributes across many query interfaces) has been actively studied recently. in particular, many works have emerged to address this problem by "holistically" matching many schemas at the same time and thus pursuing "mining" approaches in nature. however, while holistic schema matching has built its promise upon the large quantity of input schemas, it also suffers the robustness problem caused by noisy data quality. such noises often inevitably arise in the automatic extraction of schema data, which is mandatory in large scale integration. for holistic matching to be viable, it is thus essential to make it robust against noisy schemas. to tackle this challenge, we propose a data-ensemble framework with sampling and voting techniques, which is inspired by bagging predictors. specifically, our approach creates an ensemble of matchers, by randomizing input schema data into many independently downsampled trials, executing the same matcher on each trial and then aggregating their ranked results by taking majority voting. as a principled basis, we provide analytic justification of the effectiveness of this data-ensemble framework. further, empirically, our experiments on real web data show that the "ensemblization" indeed significantly boosts the matching accuracy under noisy schema input, and thus maintains the desired robustness of a holistic matcher.
mining citizen science data to predict orevalence of wild bird species. the cornell laboratory of ornithology's mission is to interpret and conserve the earth's biological diversity through research, education, and citizen science focused on birds. over the years, the lab has accumulated one of the largest and longest-running collections of environmental data sets in existence. the data sets are not only large, but also have many attributes, contain many missing values, and potentially are very noisy. the ecologists are interested in identifying which features have the strongest effect on the distribution and abundance of bird species as well as describing the forms of these relationships. we show how data mining can be successfully applied, enabling the ecologists to discover unanticipated relationships. we compare a variety of methods for measuring attribute importance with respect to the probability of a bird being observed at a feeder and present initial results for the impact of important attributes on bird prevalence.