OpenRaiser/Intern-Atlas huggingface dataset:
A unifying framework for detecting outliers and change points from non-stationary time series data
Authors: Kenji Yamanishi, Jun&apos, ichi Takeuchi
Venue: KDD
Year: 2002

We are concerned with the issues of outlier detection and change point detection from a data stream. In the area of data mining, there have been increased interest in these issues since the former is related to fraud detection, rare event discovery, etc., while the latter is related to event/trend by change detection, activity monitoring, etc. Specifically, it is important to consider the situation where the data source is non-stationary, since the nature of data source may change over time in real applications. Although in most previous work outlier detection and change point detection have not been related explicitly, this paper presents a unifying framework for dealing with both of them on the basis of the theory of on-line learning of non-stationary time series. In this framework a probabilistic model of the data source is incrementally learned using an on-line discounting learning algorithm, which can track the changing data source adaptively by forgetting the effect of past data gradually. Then the score for any given data is calculated to measure its deviation from the learned model, with a higher score indicating a high possibility of being an outlier. Further change points in a data stream are detected by applying this scoring method into a time series of moving averaged losses for prediction using the learned model. Specifically we develop an efficient algorithms for on-line discounting learning of auto-regression models from time series data, and demonstrate the validity of our framework through simulation and experimental applications to stock market data analysis.
CLOPE: a fast and effective clustering algorithm for transactional data
Authors: Yiling Yang, Xudong Guan, Jinyuan You
Venue: KDD
Year: 2002

This paper studies the problem of categorical data clustering, especially for transactional data characterized by high dimensionality and large volume. Starting from a heuristic method of increasing the height-to-width ratio of the cluster histogram, we develop a novel algorithm -- CLOPE, which is very fast and scalable, while being quite effective. We demonstrate the performance of our algorithm on two real world datasets, and compare CLOPE with the state-of-art algorithms.
Efficiently mining frequent trees in a forest
Authors: Mohammed Javeed Zaki
Venue: KDD
Year: 2002

Mining frequent trees is very useful in domains like bioinformatics, web mining, mining semistructured data, and so on. We formulate the problem of mining (embedded) subtrees in a forest of rooted, labeled, and ordered trees. We present TREEMINER, a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list. We contrast TREEMINER with a pattern matching tree mining algorithm (PATTERNMATCHER). We conduct detailed experiments to test the performance and scalability of these methods. We find that TREEMINER outperforms the pattern matching approach by a factor of 4 to 20, and has good scaleup properties. We also present an application of tree mining to analyze real web logs for usage patterns.
Towards systematic design of distance functions for data mining applications
Authors: Charu C. Aggarwal
Venue: KDD
Year: 2003

Distance function computation is a key subtask in many data mining algorithms and applications. The most effective form of the distance function can only be expressed in the context of a particular data domain. It is also often a challenging and non-trivial task to find the most effective form of the distance function. For example, in the text domain, distance function design has been considered such an important and complex issue that it has been the focus of intensive research over three decades. The final design of distance functions in this domain has been reached only by detailed empirical testing and consensus over the quality of results provided by the different variations. With the increasing ability to collect data in an automated way, the number of new kinds of data continues to increase rapidly. This makes it increasingly difficult to undertake such efforts for each and every new data type. The most important aspect of distance function design is that since a human is the end-user for any application, the design must satisfy the user requirements with regard to effectiveness. This creates the need for a systematic framework to design distance functions which are sensitive to the particular characteristics of the data domain. In this paper, we discuss such a framework. The goal is to create distance functions in an automated way while minimizing the work required from the user. We will show that this framework creates distance functions which are significantly more effective than popularly used functions such as the Euclidean metric.
Golden Path Analyzer: using divide-and-conquer to cluster Web clickstreams
Authors: Kamal Ali, Steven P. Ketchpel
Venue: KDD
Year: 2003

This paper describes a novel algorithm and deployed system Golden Path Analyzer (GPA) that analyzes clickstreams of people trying to complete the same task on a website. It finds the shortest, successful paths taken by users - 'golden paths' - and uses these as seeds for clickstream clusters. Other users are assigned to a cluster if their clickstream is a supersequence of the golden path. The advantages of this approach are that the resulting clusters are easily comprehended, they are few in number, correspond to semantically different strategies used by the users, and jointly partition all the clickstreams. GPA's key contribution over prior work in process funnels is that by not excluding users that make diversions from the golden path, GPA is able to assign more users to fewer clusters. Another key contribution is to use actual full clickstreams as cluster seeds to which supersequences of other users are added. Golden paths correspond to complete clickstreams that are based on actual user page transitions. GPA is particularly useful for site designers to improve processes such as shopping, returns and registration. Its analyses identify which web pages cause many users to deviate from a golden path, which links distract users and the percentage of users taking each golden path. GPA has demonstrated value on more than twenty client projects in diverse industries.
An adaptive nearest neighbor search for a parts acquisition ePortal
Authors: Rafael Alonso, Jeffrey A. Bloom, Hua Li, Chumki Basu
Venue: KDD
Year: 2003

One of the major hurdles in maintaining long-lived electronic systems is that electronic parts become obsolete, no longer available from the original suppliers. When this occurs, an engineer is tasked with resolving the problem by finding a replacement that is "as similar as possible" to the original part. The current approach involves a laborious manual search through several electronic portals and data books. The search is difficult because potential replacements may differ from the original and from each other by one or more parameters. Worse still, the cumbersome nature of this process may cause the engineers to miss appropriate solutions amid the many thousands of parts listed in industry catalogs.In this paper, we address this problem by introducing the notion of a parametric "distance" between electronic components. We use this distance to search a large parts data set and recommend likely replacements. Recommendations are based on an adaptive nearest-neighbor search through the parametric data set. For each user, we learn how to scale the axes of the feature space in which the nearest neighbors are sought. This allows the system to learn each user's judgment of the phrase "as similar as possible."
Architecting a knowledge discovery engine for military commanders utilizing massive runs of simulations
Authors: Philip S. Barry, Jianping Zhang, Mary McDonald
Venue: KDD
Year: 2003

The Marine Corps' Project Albert seeks to model complex phenomenon by observing the behavior of relatively simple simulations over thousands of runs. A rich data base is developed by running the simulations thousands of times, varying the agent and scenario input parameters as well as the random seeds. Exploring this result space may provide significant insight into nonlinear, surprising, and emergent behaviors. Capturing these results can provide a path for making the results usable for decision support to a military commander. This paper presents two data mining approaches, rule discovery and Bayesian networks, for analyzing the Albert simulation data. The first approach generates rules from the data and then uses them to create descriptive model. The second generates Bayesian Networks which provide a quantitative belief model for decision support. Both of these approaches as well as the Project Albert simulations are framed in the context of a system architecture for decision support.
Mining high dimensional data for classifier knowledge
Authors: Raj Bhatnagar, Goutham Kurra, Wen Niu
Venue: KDD
Year: 2003

We present in this paper the problem of discovering sets of attribute-value pairs in high dimensional data sets that are of interest not because of co-occurrence alone, but due to their value in serving as cores for potential classifiers of clusters. We present our algorithm in the context of a gene-expression dataset. Gene expression data, in most situations, is insufficient for clustering algorithms and any statistical inference because for 6000+ genes, typically only 10s and at most 100s of data points become available. It is difficult to use statistical techniques to design a classifier for such immensely under-specified data. The observed data, though statistically, insufficient contains some information about the domain. Our goal is to discover as much information about all potential classifiers as possible from the data and then summarize this knowledge. This summarization provides insights into the composition of potential classifiers. We present here algorithms and methods for mining a high dimensional data set, exemplified by a gene expression data set, for mining such information.
An iterative hypothesis-testing strategy for pattern discovery
Authors: Richard J. Bolton, Niall M. Adams
Venue: KDD
Year: 2003

Pattern discovery has emerged as a direct result of increased data storage and analytic capabilities available to the data analyst. Without a massive amount of data, we do not have the evidence to support the discovery of the local deterministic structures that we call patterns. As such, pattern discovery is one of the few areas of data mining that cannot be considered simply as a 'scaling-up' of current statistical methodology to analyze large data sets. However, the philosophies of hypothesis testing and modeling in traditional statistics do lend themselves to forming a framework for pattern discovery, and we can also draw from ideas relating to outlier discovery and residual analysis to discover patterns. We illustrate an iterative strategy in a statistical framework by way of its application to one simulated and two real data sets.
Efficient data reduction with EASE
Authors: Hervé Brönnimann, Bin Chen, Manoranjan Dash, Peter J. Haas, Peter Scheuermann
Venue: KDD
Year: 2003

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 χ2 contingency-table analysis show that EASE outperforms both FAST and simple random sampling, sometimes dramatically.
Extracting semantics from data cubes using cube transversals and closures
Authors: Alain Casali, Rosine Cicchetti, Lotfi Lakhal
Venue: KDD
Year: 2003

In this paper we propose a lattice-based approach intended for extracting semantics from datacubes: borders of version spaces for supervised classification, closed cube lattice to summarize the semantics of datacubes w.r.t. COUNT, SUM, and covering graph of the quotient cube as a visualization tool of minimal multidimensional associations. With this intention, we introduce two novel concepts: the cube transversals and the cube closures over the cube lattice of a categorical database relation. We propose a levelwise merging algorithm for mining minimal cube transversals with a single database scan. We introduce the cube connection, show that it is a Galois connection and derive a closure operator over the cube lattice. Using cube transversals and closures, we define a new characterization of boundary sets which provide a condensed representation of version spaces used to enhance supervised classification. The algorithm designed for computing such borders improves the complexity of previous proposals. We also introduce the concept of closed cube lattice and show that it is isomorph to on one hand the Galois lattice and on the other hand the quotient cube w.r.t. COUNT, SUM. Proposed in [16], the quotient cube is a succinct summary of a datacube preserving the Rollup/Drilldown semantics. We show that the quotient cube w.r.t. COUNT, SUM and the closed cube lattice have a similar expression power but the latter has the smallest possible size. Finally we focus on the multidimensional association issue and introduce the covering graph of the quotient cube which provides the user with a visualization tool of minimal multidimensional associations.
Finding recent frequent itemsets adaptively over online data streams
Authors: Joong Hyuk Chang, Won Suk Lee
Venue: KDD
Year: 2003

A data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate. Consequently, the knowledge embedded in a data stream is more likely to be changed as time goes by. Identifying the recent change of a data stream, specially for an online data stream, can provide valuable information for the analysis of the data stream. In addition, monitoring the continuous variation of a data stream enables to find the gradual change of embedded knowledge. However, most of mining algorithms over a data stream do not differentiate the information of recently generated transactions from the obsolete information of old transactions which may be no longer useful or possibly invalid at present. This paper proposes a data mining method for finding recent frequent itemsets adaptively over an online data stream. The effect of old transactions on the mining result of the data steam is diminished by decaying the old occurrences of each itemset as time goes by. Furthermore, several optimization techniques are devised to minimize processing time as well as main memory usage. Finally, the proposed method is analyzed by a series of experiments.
Translation-invariant mixture models for curve clustering
Authors: Darya Chudova, Scott Gaffney, Eric Mjolsness, Padhraic Smyth
Venue: KDD
Year: 2003

In this paper we present a family of algorithms that can simultaneously align and cluster sets of multidimensional curves defined on a discrete time grid. Our approach uses the Expectation-Maximization (EM) algorithm to recover both the mean curve shapes for each cluster, and the most likely shifts, offsets, and cluster memberships for each curve. We demonstrate how Bayesian estimation methods can improve the results for small sample sizes by enforcing smoothness in the cluster mean curves. We evaluate the methodology on two real-world data sets, time-course gene expression data and storm trajectory data. Experimental results show that models that incorporate curve alignment systematically provide improvements in predictive power and within-cluster variance on test data sets. The proposed approach provides a non-parametric, computationally efficient, and robust methodology for clustering broad classes of curve data.
Data quality through knowledge engineering
Authors: Tamraparni Dasu, Gregg T. Vesonder, Jon R. Wright
Venue: KDD
Year: 2003

Traditionally, data quality programs have acted as a preprocessing stage to make data suitable for a data mining or analysis operation. Recently, data quality concepts have been applied to databases that support business operations such as provisioning and billing. Incorporating business rules that drive operations and their associated data processes is critically important to the success of such projects. However, there are many practical complications. For example, documentation on business rules is often meager. Rules change frequently. Domain knowledge is often fragmented across experts, and those experts do not always agree. Typically, rules have to be gathered from subject matter experts iteratively, and are discovered out of logical or procedural sequence, like a jigsaw puzzle. Our approach is to impement business rules as constraints on data in a classical expert system formalism sometimes called production rules. Our system works by allowing good data to pass through a system of constraints unchecked. Bad data violate constraints and are flagged, and then fed back after correction. Constraints are added incrementally as better understanding of the business rules is gained. We include a real-life case study.
Information-theoretic co-clustering
Authors: Inderjit S. Dhillon, Subramanyam Mallela, Dharmendra S. Modha
Venue: KDD
Year: 2003

Two-dimensional contingency or co-occurrence tables arise frequently in important applications such as text, web-log and market-basket data analysis. A basic problem in contingency table analysis is co-clustering: simultaneous clustering of the rows and columns. A novel theoretical formulation views the contingency table as an empirical joint probability distribution of two discrete random variables and poses the co-clustering problem as an optimization problem in information theory---the optimal co-clustering maximizes the mutual information between the clustered random variables subject to constraints on the number of row and column clusters. We present an innovative co-clustering algorithm that monotonically increases the preserved mutual information by intertwining both the row and column clusterings at all stages. Using the practical example of simultaneous word-document clustering, we demonstrate that our algorithm works well in practice, especially in the presence of sparsity and high-dimensionality.
Applications of sampling and fractional factorial designs to model-free data squashing
Authors: William DuMouchel, Deepak K. Agarwal
Venue: KDD
Year: 2003

The concept of "data squashing" was introduced by DuMouchel et al [4] as a method of summarizing massive data sets that preserves statistical relationships among variables. The idea is to create a smaller data set that allows statistical modeling to take place using in-memory algorithms, and to preserve the modeling results more accurately than would a same-size random sample from the massive data set. This research attempts to avoid several limitations of previous approaches to data squashing. Our method avoids the curse of dimensionality by a double use of principal components transformations that makes computing time linear in the number of cases and quadratic in the number of variables. Categorical and continuous variables are smoothly integrated. Because the binning is based on principal components, which are uncorrelated, we can use fractional factorial designs that sample less than one point per bin. We also investigate various weighting schemes for the squashed sample to see whether matching moments or matching subregion data counts is more effective. Finally, previous work required the specification of a statistical model, either to perform the squashing algorithm or to compare the worth of different squashing methods. Our approach to evaluation is model free and does not even require the specification of variables as responses or predictors. Instead, we develop a chi-squared like measure of accuracy to compare the closeness of various discrete densities (the squashed data sets) to the discrete massive data set.
Using randomized response techniques for privacy-preserving data mining
Authors: Wenliang Du, Justin Zhijun Zhan
Venue: KDD
Year: 2003

Privacy is an important issue in data mining and knowledge discovery. In this paper, we propose to use the randomized response techniques to conduct the data mining computation. Specially, we present a method to build decision tree classifiers from the disguised data. We conduct experiments to compare the accuracy of our decision tree with the one built from the original undisguised data. Our results show that although the data are disguised, our method can still achieve fairly high accuracy. We also show how the parameter used in the randomized response techniques affects the accuracy of the results.
SEWeP: using site semantics and a taxonomy to enhance the Web personalization process
Authors: Magdalini Eirinaki, Michalis Vazirgiannis, Iraklis Varlamis
Venue: KDD
Year: 2003

Web personalization is the process of customizing a Web site to the needs of each specific user or set of users, taking advantage of the knowledge acquired through the analysis of the user's navigational behavior. Integrating usage data with content, structure or user profile data enhances the results of the personalization process. In this paper, we present SEWeP, a system that makes use of both the usage logs and the semantics of a Web site's content in order to personalize it. Web content is semantically annotated using a conceptual hierarchy (taxonomy). We introduce C-logs, an extended form of Web usage logs that encapsulates knowledge derived from the link semantics. C-logs are used as input to the Web usage mining process, resulting in a broader yet semantically focused set of recommendations.