OpenRaiser/Intern-Atlas huggingface dataset:
Privacy-preserving distributed k-means clustering over arbitrarily partitioned data
Authors: Geetha Jagannathan, Rebecca N. Wright
Venue: KDD
Year: 2005

Advances in computer networking and database technologies have enabled the collection and storage of vast quantities of data. Data mining can extract valuable knowledge from this data, and organizations have realized that they can often obtain better results by pooling their data together. However, the collected data may contain sensitive or private information about the organizations or their customers, and privacy concerns are exacerbated if data is shared between multiple organizations.Distributed data mining is concerned with the computation of models from data that is distributed among multiple participants. Privacy-preserving distributed data mining seeks to allow for the cooperative computation of such models without the cooperating parties revealing any of their individual data items. Our paper makes two contributions in privacy-preserving data mining. First, we introduce the concept of arbitrarily partitioned data, which is a generalization of both horizontally and vertically partitioned data. Second, we provide an efficient privacy-preserving protocol for k-means clustering in the setting of arbitrarily partitioned data.
Fast discovery of unexpected patterns in data, relative to a Bayesian network
Authors: Szymon Jaroszewicz, Tobias Scheffer
Venue: KDD
Year: 2005

We consider a model in which background knowledge on a given domain of interest is available in terms of a Bayesian network, in addition to a large database. The mining problem is to discover unexpected patterns: our goal is to find the strongest discrepancies between network and database. This problem is intrinsically difficult because it requires inference in a Bayesian network and processing the entire, potentially very large, database. A sampling-based method that we introduce is efficient and yet provably finds the approximately most interesting unexpected patterns. We give a rigorous proof of the method's correctness. Experiments shed light on its efficiency and practicality for large-scale Bayesian networks and databases.
Generation of synthetic data sets for evaluating the accuracy of knowledge discovery systems
Authors: Daniel R. Jeske, Behrokh Samadi, Pengyue J. Lin, Lan Ye, Sean Cox, Rui Xiao, Ted Younglove, Minh Ly, Douglas Holt, Ryan Rich
Venue: KDD
Year: 2005

Information Discovery and Analysis Systems (IDAS) are designed to correlate multiple sources of data and use data mining techniques to identify potential significant events. Application domains for IDAS are numerous and include the emerging area of homeland security.Developing test cases for an IDAS requires background data sets into which hypothetical future scenarios can be overlaid. The IDAS can then be measured in terms of false positive and false negative error rates. Obtaining the test data sets can be an obstacle due to both privacy issues and also the time and cost associated with collecting a diverse set of data sources.In this paper, we give an overview of the design and architecture of an IDAS Data Set Generator (IDSG) that enables a fast and comprehensive test of an IDAS. The IDSG generates data using statistical and rule-based algorithms and also semantic graphs that represent interdependencies between attributes. A credit card transaction application is used to illustrate the approach.
Simultaneous optimization of complex mining tasks with a knowledgeable cache
Authors: Ruoming Jin, Kaushik Sinha, Gagan Agrawal
Venue: KDD
Year: 2005

With an increasing use of data mining tools and techniques, we envision that a Knowledge Discovery and Data Mining System (KDDMS) will have to support and optimize for the following scenarios: 1) Sequence of Queries: A user may analyze one or more datasets by issuing a sequence of related complex mining queries, and 2) Multiple Simultaneous Queries: Several users may be analyzing a set of datasets concurrently, and may issue related complex queries.This paper presents a systematic mechanism to optimize for the above cases, targeting the class of mining queries involving frequent pattern mining on one or multiple datasets. We present a system architecture and propose new algorithms to simultaneously optimize multiple such queries and use a knowledgeable cache to store and utilize the past query results. We have implemented and evaluated our system with both real and synthetic datasets. Our experimental results show that our techniques can achieve a speedup of up to a factor of 9, compared with the systems which do not support caching or optimize for multiple queries.
Data mining in the chemical industry
Authors: Alex N. Kalos, Tim Rey
Venue: KDD
Year: 2005

In this paper we describe the experience of introducing data mining to a large chemical manufacturing company. The multi-national nature of doing business with multiple business units, presents a unique opportunity for the deployment of data mining. While each business unit has its own objectives and challenges, which may be at odds with those of other units, they also share many common interests and resources. In this environment, data mining can be used to identify potential value-creating opportunities, through large site integration of multiple assets and synergies from the use of common assets, such as site-wide manufacturing facilities, and world-wide supply-chain, purchasing and other shared services. However, issues arise, on one hand from overly complex systems, and on the other hand, from the danger of reaching sub-optimal solutions, if a big enough picture is not considered when executing projects. The company-wide initiative and use of Six Sigma at all levels of the company provided a fertile ground for making the case for data mining and facilitating its acceptance. The Six Sigma mindset of measuring the performance of processes and analyzing data promotes data-based decision making, therefore making data mining a natural extension of this methodology. We will describe the approach for launching a data mining capability within this framework, the strategy for securing upper management support, drawing from internal modeling, statistical, and other communities, and from external consultants and universities. Lessons learned from industrial case studies, enterprise-wide tool evaluation and peer benchmarking will be discussed.
Information retrieval based on collaborative filtering with latent interest semantic map
Authors: Noriaki Kawamae, Katsumi Takahashi
Venue: KDD
Year: 2005

In this paper, we propose an information retrieval model called Latent Interest Semantic Map (LISM), which features retrieval composed of both Collaborative Filtering(CF) and Probabilistic Latent Semantic Analysis (PLSA). The motivation behind this study is that the relation between users and documents can be explained by the two different latent classes, where users belong probabilistically in one or more classes with the same interest groups, while documents also belong probabilistically in one or more class with the same topic groups. The novel aspect of LISM is that it simultaneously provides a user model and latent semantic analysis in one map. This benefit of LISM is to enable collaborative filtering in terms of user interest and document topic and thus solve the cold start problem.
Local sparsity control for naive Bayes with extreme misclassification costs
Authors: Aleksander Kolcz
Venue: KDD
Year: 2005

In applications of data mining characterized by highly skewed misclassification costs certain types of errors become virtually unacceptable. This limits the utility of a classifier to a range in which such constraints can be met. Naive Bayes, which has proven to be very useful in text mining applications due to high scalability, can be particularly affected. Although its 0/1 loss tends to be small, its misclassifications are often made with apparently high confidence. Aside from efforts to better calibrate Naive Bayes scores, it has been shown that its accuracy depends on document sparsity and feature selection can lead to marked improvement in classification performance. Traditionally, sparsity is controlled globally, and the result for any particular document may vary. In this work we examine the merits of local sparsity control for Naive Bayes in the context of highly asymmetric misclassification costs. In experiments with three benchmark document collections we demonstrate clear advantages of document-level feature selection. In the extreme cost setting, multinomial Naive Bayes with local sparsity control is able to outperform even some of the recently proposed effective improvements to the Naive Bayes classifier. There are also indications that local feature selection may be preferable in different cost settings.
Determining an author's native language by mining a text for errors
Authors: Moshe Koppel, Jonathan Schler, Kfir Zigdon
Venue: KDD
Year: 2005

In this paper, we show that stylistic text features can be exploited to determine an anonymous author's native language with high accuracy. Specifically, we first use automatic tools to ascertain frequencies of various stylistic idiosyncrasies in a text. These frequencies then serve as features for support vector machines that learn to classify texts according to author native language.
Density-based clustering of uncertain data
Authors: Hans-Peter Kriegel, Martin Pfeifle
Venue: KDD
Year: 2005

In many different application areas, e.g. sensor databases, location based services or face recognition systems, distances between odjects have to be computed based on vague and uncertain data. Commonly, the distances between these uncertain object descriptions are expressed by one numerical distance value. Based on such single-valued distance functions standard data mining algorithms can work without any changes. In this paper, we propose to express the similarity between two fuzzy objects by distance probability functions. These fuzzy distance functions assign a probability value to each possible distance value. By integrating these fuzzy distance functions directly into data mining algorithms, the full information provided by these functions is exploited. In order to demonstrate the benefits of this general approach, we enhance the density-based clustering algorithm DBSCAN so that it can work directly on these fuzzy distance functions. In a detailed experimental evaluation based on artificial and real-world data sets, we show the characteristics and benefits of our new approach.
A multiple tree algorithm for the efficient association of asteroid observations
Authors: Jeremy Kubica, Andrew W. Moore, Andrew J. Connolly, Robert Jedicke
Venue: KDD
Year: 2005

In this paper we examine the problem of efficiently finding sets of observations that conform to a given underlying motion model. While this problem is often phrased as a tracking problem, where it is called track initiation, it is useful in a variety of tasks where we want to find correspondences or patterns in spatial-temporal data. Unfortunately, this problem often suffers from a combinatorial explosion in the number of potential sets that must be evaluated. We consider the problem with respect to large-scale asteroid observation data, where the goal is to find associations among the observations that correspond to the same underlying asteroid. In this domain, it is vital that we can efficiently extract the underlying associations. We introduce a new methodology for track initiation that exhaustively considers all possible linkages. We then introduce an exact tree-based algorithm for tractably finding all compatible sets of points. Further, we extend this approach to use multiple trees, exploiting structure from several time steps at once. We compare this approach to a standard sequential approach and show how the use of multiple trees can provide a significant benefit.
Mining risk patterns in medical data
Authors: Jiuyong Li, Ada Wai-Chee Fu, Hongxing He, Jie Chen, Huidong Jin, Damien McAullay, Graham J. Williams, Ross Sparks, Chris Kelman
Venue: KDD
Year: 2005

In this paper, we discuss a problem of finding risk patterns in medical data. We define risk patterns by a statistical metric, relative risk, which has been widely used in epidemiological research. We characterise the problem of mining risk patterns as an optimal rule discovery problem. We study an anti-monotone property for mining optimal risk pattern sets and present an algorithm to make use of the property in risk pattern discovery. The method has been applied to a real world data set to find patterns associated with an allergic event for ACE inhibitors. The algorithm has generated some useful results for medical researchers.
An integrated framework on mining logs files for computing system management
Authors: Tao Li, Feng Liang, Sheng Ma, Wei Peng
Venue: KDD
Year: 2005

Traditional approaches to system management have been largely based on domain experts through a knowledge acquisition process that translates domain knowledge into operating rules and policies. This has been well known and experienced as a cumbersome, labor intensive, and error prone process. In addition, this process is difficult to keep up with the rapidly changing environments. In this paper, we will describe our research efforts on establishing an integrated framework for mining system log files for automatic management. In particular, we apply text mining techniques to categorize messages in log files into common situations, improve categorization accuracy by considering the temporal characteristics of log messages, develop temporal mining techniques to discover the relationships between different events, and utilize visualization tools to evaluate and validate the interesting temporal patterns for system management.
Automated detection of frontal systems from numerical model-generated data
Authors: Xiang Li, Rahul Ramachandran, Sara J. Graves, Sunil Movva, Bilahari Akkiraju, David Emmitt, Steven Greco, Robert Atlas, Joseph Terry, Juan-Carlos Jusem
Venue: KDD
Year: 2005

Fronts are significant meteorological phenomena of interest. The extraction of frontal systems from observations and model data can greatly benefit many kinds of research and applications in atmospheric sciences. Due to the huge amount of observational and model data available nowadays, automated extraction of front systems is necessary. This paper presents an automated method to detect frontal systems from numerical model-generated data. In this method, a frontal system is characterized by a vector of features, comprised of parameters derived from the model wind field. K-means clustering is applied to the generated sample set of the feature vectors to partition the feature space and to identify clusters representing the fronts. The probability that a model grid belongs to a front is estimated based on its feature vector. The probability image is generated corresponding to the model grids. A hierarchical thresholding technique is applied to the probability image to identify the frontal systems and a Gaussian Bayes classifier is trained to determine the proper threshold value. This is followed by post processing to filter out false signatures. Experiment results from this method are in good agreement with the ones identified by the domain experts.
Adversarial learning
Authors: Daniel Lowd, Christopher Meek
Venue: KDD
Year: 2005

Many classification tasks, such as spam filtering, intrusion detection, and terrorism detection, are complicated by an adversary who wishes to avoid detection. Previous work on adversarial classification has made the unrealistic assumption that the attacker has perfect knowledge of the classifier [2]. In this paper, we introduce the adversarial classifier reverse engineering (ACRE) learning problem, the task of learning sufficient information about a classifier to construct adversarial attacks. We present efficient algorithms for reverse engineering linear classifiers with either continuous or Boolean features and demonstrate their effectiveness using real data from the domain of spam filtering.
Estimating missed actual positives using independent classifiers
Authors: Sandeep Mane, Jaideep Srivastava, San-Yih Hwang
Venue: KDD
Year: 2005

Data mining is increasingly being applied in environments having very high rate of data generation like network intrusion detection [7], where routers generate about 300,000 -- 500,000 connections every minute. In such rare class data domains, the cost of missing a rare-class instance is much higher than that of other classes. However, the high cost for manual labeling of instances, the high rate at which data is collected as well as real-time response constraints do not always allow one to determine the actual classes for the collected unlabeled datasets. In our previous work [9], this problem of missed false negatives was explained in context of two different domains -- "network intrusion detection" and "business opportunity classification". In such cases, an estimate for the number of such missed high-cost, rare instances will aid in the evaluation of the performance of the modeling technique (e.g. classification) used. A capture-recapture method was used for estimating false negatives, using two or more learning methods (i.e. classifiers). This paper focuses on the dependence between the class labels assigned by such learners. We define the conditional independence for classifiers given a class label and show its relation to the conditional independence of the features sets (used by the classifiers) given a class label. The later is a computationally expensive problem and hence, a heuristic algorithm is proposed for obtaining conditionally independent (or less dependent) feature sets for the classifiers. Initial results of this algorithm on synthetic datasets are promising and further research is being pursued.
A distributed learning framework for heterogeneous data sources
Authors: Srujana Merugu, Joydeep Ghosh
Venue: KDD
Year: 2005

We present a probabilistic model-based framework for distributed learning that takes into account privacy restrictions and is applicable to scenarios where the different sites have diverse, possibly overlapping subsets of features. Our framework decouples data privacy issues from knowledge integration issues by requiring the individual sites to share only privacy-safe probabilistic models of the local data, which are then integrated to obtain a global probabilistic model based on the union of the features available at all the sites. We provide a mathematical formulation of the model integration problem using the maximum likelihood and maximum entropy principles and describe iterative algorithms that are guaranteed to converge to the optimal solution. For certain commonly occurring special cases involving hierarchically ordered feature sets or conditional independence, we obtain closed form solutions and use these to propose an efficient alternative scheme by recursive decomposition of the model integration problem. To address interpretability concerns, we also present a modified formulation where the global model is assumed to belong to a specified parametric family. Finally, to highlight the generality of our framework, we provide empirical results for various learning tasks such as clustering and classification on different kinds of datasets consisting of continuous vector, categorical and directional attributes. The results show that high quality global models can be obtained without much loss of privacy.
Optimizing time series discretization for knowledge discovery
Authors: Fabian Mörchen, Alfred Ultsch
Venue: KDD
Year: 2005

Knowledge Discovery in time series usually requires symbolic time series. Many discretization methods that convert numeric time series to symbolic time series ignore the temporal order of values. This often leads to symbols that do not correspond to states of the process generating the time series and cannot be interpreted meaningfully. We propose a new method for meaningful unsupervised discretization of numeric time series called Persist. The algorithm is based on the Kullback-Leibler divergence between the marginal and the self-transition probability distributions of the discretization symbols. Its performance is evaluated on both artificial and real life data in comparison to the most common discretization methods. Persist achieves significantly higher accuracy than existing static methods and is robust against noise. It also outperforms Hidden Markov Models for all but very simple cases.
Key semantics extraction by dependency tree mining
Authors: Satoshi Morinaga, Hiroki Arimura, Takahiro Ikeda, Yosuke Sakao, Susumu Akamine
Venue: KDD
Year: 2005

We propose a new text mining system which extracts characteristic contents from given documents. We define Key semantics as characteristic sub-structures of syntactic dependencies in the given documents, and consider the following three tasks in this paper: 1)Key semantics extraction: extracting characteristic syntactic dependency structures not only as ordered trees but also as unordered trees and free trees, 2)Redundancy reduction: from the result of extraction, deleting redundant dependency structures such as sub-structures or equivalent structures of the others, and 3)Phrase/sentence reconstruction: generating a phrase or sentence in a natural language corresponding to the extracted structure.Our system is a combination of natural language processing techniques and tree mining techniques. The system consists of the following five units: 1) syntactic dependency analysis unit, 2) input filters, 3) characteristic ordered subtree extraction unit, 4) output filters, and 5) phrase/sentence reconstruction unit. Although ordered trees are extracted in the third unit, the overall behavior of the system can be switched into the extraction of ordered trees, unordered trees, or free trees depending on which of the input filters is/are applied in the second step. The output filters delete redundant trees from the extraction result for efficient knowledge discovery. Finally, phrases or sentences corresponding to the extracted subtrees are reconstructed by utilizing the input documents.We demonstrate the validity of our system by showing experimental results using real data collected at a help desk and TDT pilot corpus.
Using retrieval measures to assess similarity in mining dynamic web clickstreams
Authors: Olfa Nasraoui, Cesar Cardona, Carlos Rojas
Venue: KDD
Year: 2005

While scalable data mining methods are expected to cope with massive Web data, coping with evolving trends in noisy data in a continuous fashion, and without any unnecessary stoppages and reconfigurations is still an open challenge. This dynamic and single pass setting can be cast within the framework of mining evolving data streams. In this paper, we explore the task of mining mass user profiles by discovering evolving Web session clusters in a single pass with a recently proposed scalable immune based clustering approach (TECNO-STREAMS), and study the effect of the choice of different similarity measures on the mining process and on the interpretation of the mined patterns. We propose a simple similarity measure that has the advantage of explicitly coupling the precision and coverage criteria to the early learning stages, and furthermore requiring that the affinity of the data to the learned profiles or summaries be defined by the minimum of their coverage or precision, hence requiring that the learned profiles are simultaneously precise and complete, with no compromises.In our experiments, we study the task of mining evolving user profiles from Web clickstream data (web usage mining) in a single pass, and under different trend sequencing scenarios, showing that compared oto the cosine similarity measure, the proposed similarity measure explicitly based on precision and coverage allows the discovery of more correct profiles at the same precision or recall quality levels.