OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic syslog mining for network failure monitoring
Authors: Kenji Yamanishi, Yuko Maruyama
Venue: KDD
Year: 2005

Syslog monitoring technologies have recently received vast attentions in the areas of network management and network monitoring. They are used to address a wide range of important issues including network failure symptom detection and event correlation discovery. Syslogs are intrinsically dynamic in the sense that they form a time series and that their behavior may change over time. This paper proposes a new methodology of dynamic syslog mining in order to detect failure symptoms with higher confidence and to discover sequential alarm patterns among computer devices. The key ideas of dynamic syslog mining are 1) to represent syslog behavior using a mixture of Hidden Markov Models, 2) to adaptively learn the model using an on-line discounting learning algorithm in combination with dynamic selection of the optimal number of mixture components, and 3) to give anomaly scores using universal test statistics with a dynamically optimized threshold. Using real syslog data we demonstrate the validity of our methodology in the scenarios of failure symptom detection, emerging pattern identification, and correlation discovery.
Summarizing itemset patterns: a profile-based approach
Authors: Xifeng Yan, Hong Cheng, Jiawei Han, Dong Xin
Venue: KDD
Year: 2005

Frequent-pattern mining has been studied extensively on scalable methods for mining various kinds of patterns including itemsets, sequences, and graphs. However, the bottleneck of frequent-pattern mining is not at the efficiency but at the interpretability, due to the huge number of patterns generated by the mining process.In this paper, we examine how to summarize a collection of itemset patterns using only K representatives, a small number of patterns that a user can handle easily. The K representatives should not only cover most of the frequent patterns but also approximate their supports. A generative model is built to extract and profile these representatives, under which the supports of the patterns can be easily recovered without consulting the original dataset. Based on the restoration error, we propose a quality measure function to determine the optimal value of parameter K. Polynomial time algorithms are developed together with several optimization heuristics for efficiency improvement. Empirical studies indicate that we can obtain compact summarization in real datasets.
Enhancing the lift under budget constraints: an application in the mutual fund industry
Authors: Lian Yan, Michael Fassino, Patrick Baldasare
Venue: KDD
Year: 2005

A lift curve, with the true positive rate on the y-axis and the customer pull (or contact) rate on the x-axis, is often used to depict the model performance in many data mining applications, especially in the area of customer relationship management (CRM). Typically, these applications concern only the model accuracy at a relatively small pull or contact/intervention rate of the whole customer base, which is predetermined by a budget constraint for the project, e.g., how many customers can be contacted every month. In this paper, we address the important problem of enhancing the lift (true positive rate) at a specified pull rate. We propose two distinct algorithms, which are applicable to different scenarios. In particular, when the binary class label of the training set is extracted from a continuous variable, we can optimize a training objective which takes into account the specified pull rate rather than the class prior, based on the often ignored continuous variable. In those cases where only the binary class label is available during training, we propose a constrained optimization algorithm to maximize the true positive rate related to a specific decision threshold at which the specified pull rate is achieved. We applied both algorithms to our projects of predicting defection (decline in account value) of mutual fund accounts for two major U.S. mutual fund companies and achieved substantial enhancement of the lift at the specified pull rate.
Building connected neighborhood graphs for isometric data embedding
Authors: Li Yang
Venue: KDD
Year: 2005

Neighborhood graph construction is usually the first step in algorithms for isometric data embedding and manifold learning that cope with the problem of projecting high dimensional data to a low space. This paper begins by explaining the algorithmic fundamentals of techniques for isometric data embedding and derives a general classification of these techniques. We will see that the nearest neighbor approaches commonly used to construct neighborhood graphs do not guarantee connectedness of the constructed neighborhood graphs and, consequently, may cause an algorithm fail to project data to a single low dimensional coordinate system. In this paper, we review three existing methods to construct k-edge-connected neighborhood graphs and propose a new method to construct k-connected neighborhood graphs. These methods are applicable to a wide range of data including data distributed among clusters. Their features are discussed and compared through experiments.
A generalized framework for mining spatio-temporal patterns in scientific data
Authors: Hui Yang, Srinivasan Parthasarathy, Sameep Mehta
Venue: KDD
Year: 2005

In this paper, we present a general framework to discover spatial associations and spatio-temporal episodes for scientific datasets. In contrast to previous work in this area, features are modeled as geometric objects rather than points. We define multiple distance metrics that take into account objects ’ extent and thus are more robust in capturing the influence of an object on other objects in spatial neighborhood. We have developed algorithms to discover four different types of spatial object interaction (association) patterns. We also extend our approach to accommodate temporal information and propose a simple algorithm to derive spatio-temporal episodes. We show that such episodes can be used to reason about critical events. We evaluate our framework on real datasets to demonstrate its efficacy. The datasets originate from two different areas: Computational Molecular Dynamics and Computational Fluid Flow. We present results highlighting the importance of the identified patterns and episodes by using knowledge from the underlying domains. We also show that the proposed algorithms scale linearly with respect to the dataset size.
Anonymity-preserving data collection
Authors: Zhiqiang Yang, Sheng Zhong, Rebecca N. Wright
Venue: KDD
Year: 2005

Protection of privacy has become an important problem in data mining. In particular, individuals have become increasingly unwilling to share their data, frequently resulting in individuals either refusing to share their data or providing incorrect data. In turn, such problems in data collection can affect the success of data mining, which relies on sufficient amounts of accurate data in order to produce meaningful results. Random perturbation and randomized response techniques can provide some level of privacy in data collection, but they have an associated cost in accuracy. Cryptographic privacy-preserving data mining methods provide good privacy and accuracy properties. However, in order to be efficient, those solutions must be tailored to specific mining tasks, thereby losing generality. In this paper, we propose efficient cryptographic techniques for online data collection in which data from a large number of respondents is collected anonymously, without the help of a trusted third party. That is, our solution allows the miner to collect the original data from each respondent, but in such a way that the miner cannot link a respondent’s data to the respondent. An advantage of such a solution is that, because it does not change the actual data, its success does not depend on the underlying data mining problem. We provide proofs of the correctness and privacy of our solution, as well as experimental data that demonstrates its efficiency. We also extend our solution to tolerate certain kinds of malicious behavior of the participants. 1.
Cross-relational clustering with user's guidance
Authors: Xiaoxin Yin, Jiawei Han, Philip S. Yu
Venue: KDD
Year: 2005

Clustering is an essential data mining task with numerous applications. However, data in most real-life applications are high-dimensional in nature, and the related information often spreads across multiple relations. To ensure effective and efficient high-dimensional, cross-relational clustering, we propose a new approach, called CrossClus, which performs cross-relational clustering with user's guidance. We believe that user's guidance, even likely in very simple forms, could be essential for effective high-dimensional clustering since a user knows well the application requirements and data semantics. CrossClus is carried out as follows: A user specifies a clustering task and selects one or a small set of features pertinent to the task. CrossClus extracts the set of highly relevant features in multiple relations connected via linkages defined in the database schema, evaluates their effectiveness based on user's guidance, and identifies interesting clusters that fit user's needs. This method takes care of both quality in feature extraction and efficiency in clustering. Our comprehensive experiments demonstrate the effectiveness and scalability of this approach.
SVM selective sampling for ranking with application to data retrieval
Authors: Hwanjo Yu
Venue: KDD
Year: 2005

Learning ranking (or preference) functions has been a major issue in the machine learning community and has produced many applications in information retrieval. SVMs (Support Vector Machines) - a classification and regression methodology - have also shown excellent performance in learning ranking functions. They effectively learn ranking functions of high generalization based on the large-margin principle and also systematically support nonlinear ranking by the kernel trick. In this paper, we propose an SVM selective sampling technique for learning ranking functions. SVM selective sampling (or active learning with SVM) has been studied in the context of classification. Such techniques reduce the labeling effort in learning classification functions by selecting only the most informative samples to be labeled. However, they are not extendable to learning ranking functions, as the labeled data in ranking is relative ordering, or partial orders of data. Our proposed sampling technique effectively learns an accurate SVM ranking function with fewer partial orders. We apply our sampling technique to the data retrieval application, which enables fuzzy search on relational databases by interacting with users for learning their preferences. Experimental results show a significant reduction of the labeling effort in inducing accurate ranking functions.
Pattern lattice traversal by selective jumps
Authors: Osmar R. Zaïane, Mohammad El-Hajj
Venue: KDD
Year: 2005

Regardless of the frequent patterns to discover, either the full frequent patterns or the condensed ones, either closed or maximal, the strategy always includes the traversal of the lattice of candidate patterns. We study the existing depth versus breadth traversal approaches for generating candidate patterns and propose in this paper a new traversal approach that jumps in the search space among only promising nodes. Our leaping approach avoids nodes that would not participate in the answer set and reduce drastically the number of candidate patterns. We use this approach to efficiently pinpoint maximal patterns at the border of the frequent patterns in the lattice and collect enough information in the process to generate all subsequent patterns.
CLICKS: an effective algorithm for mining subspace clusters in categorical datasets
Authors: Mohammed Javeed Zaki, Markus Peters, Ira Assent, Thomas Seidl
Venue: KDD
Year: 2005

We present a novel algorithm called CLICKS, that finds clusters in categorical datasets based on a search for k-partite maximal cliques. Unlike previous methods, CLICKS mines subspace clusters. It uses a selective vertical method to guarantee complete search. CLICKS outperforms previous approaches by over an order of magnitude and scales better than any of the existing method for high-dimensional datasets. These results are demonstrated in a comprehensive performance study on real and synthetic datasets.
Reasoning about sets using redescription mining
Authors: Mohammed Javeed Zaki, Naren Ramakrishnan
Venue: KDD
Year: 2005

Redescription mining is a newly introduced data mining problem that seeks to find subsets of data that afford multiple definitions. It can be viewed as a generalization of association rule mining, from finding implications to equivalences; as a form of conceptual clustering, where the goal is to identify clusters that afford dual characterizations; and as a form of constructive induction, to build features based on given descriptors that mutually reinforce each other. In this paper, we present the use of redescription mining as an important tool to reason about a collection of sets, especially their overlaps, similarities, and differences. We outline algorithms to mine all minimal (non-redundant) redescriptions underlying a dataset using notions of minimal generators of closed itemsets. We also show the use of these algorithms in an interactive context, supporting constraint-based exploration and querying. Specifically, we showcase a bioinformatics application that empowers the biologist to define a vocabulary of sets underlying a domain of genes and to reason about these sets, yielding significant biological insight.
A new scheme on privacy-preserving data classification
Authors: Nan Zhang, Shengquan Wang, Wei Zhao
Venue: KDD
Year: 2005

We address privacy-preserving classification problem in a distributed system. Randomization has been the approach proposed to preserve privacy in such scenario. However, this approach is now proven to be insecure as it has been discovered that some privacy intrusion techniques can be used to reconstruct private information from the randomized data tuples. We introduce an algebraic-technique-based scheme. Compared to the randomization approach, our new scheme can build classifiers more accurately but disclose less private information. Furthermore, our new scheme can be readily integrated as a middleware with existing systems.
Outlier detection by active learning
Authors: Naoki Abe, Bianca Zadrozny, John Langford
Venue: KDD
Year: 2006

Most existing approaches to outlier detection are based on density estimation methods. There are two notable issues with these methods: one is the lack of explanation for outlier flagging decisions, and the other is the relatively high computational requirement. In this paper, we present a novel approach to outlier detection based on classification, in an attempt to address both of these issues. Our approach isbased on two key ideas. First, we present a simple reduction of outlier detection to classification, via a procedure that involves applying classification to a labeled data set containing artificially generated examples that play the role of potential outliers. Once the task has been reduced to classification, we then invoke a selective sampling mechanism based on active learning to the reduced classification problem. We empirically evaluate the proposed approach using a number of data sets, and find that our method is superior to other methods based on the same reduction to classification, but using standard classification methods. We also show that it is competitive to the state-of-the-art outlier detection methods in the literature based on density estimation, while significantly improving the computational complexity and explanatory power.
Outlier detection by sampling with accuracy guarantees
Authors: Mingxi Wu, Chris Jermaine
Venue: KDD
Year: 2006

An effective approach to detecting anomalous points in a data set is distance-based outlier detection. This paper describes a simple sampling algorithm to effciently detect distance-based outliers in domains where each and every distance computation is very expensive. Unlike any existing algorithms, the sampling algorithm requires a xed number of distance computations and can return good results with accuracy guarantees. The most computationally expensive aspect of estimating the accuracy of the result is sorting all of the distances computed by the sampling algorithm. The experimental study on two expensive domains as well as ten additional real-life datasets demonstrates both the effciency and effectiveness of the sampling algorithm in comparison with the state-of-the-art algorithm and there liability of the accuracy guarantees.
Deriving quantitative models for correlation clusters
Authors: Elke Achtert, Christian Böhm, Hans-Peter Kriegel, Peer Kröger, Arthur Zimek
Venue: KDD
Year: 2006

Correlation clustering aims at grouping the data set into correlation clusters such that the objects in the same cluster exhibit a certain density and are all associated to a common arbitrarily oriented hyperplane of arbitrary dimensionality. Several algorithms for this task have been proposed recently. However, all algorithms only compute the partitioning of the data into clusters. This is only a first step in the pipeline of advanced data analysis and system modelling. The second (post-clustering) step of deriving a quantitative model for each correlation cluster has not been addressed so far. In this paper, we describe an original approach to handle this second step. We introduce a general method that can extract quantitative information on the linear dependencies within a correlation clustering. Our concepts are independent of the clustering model and can thus be applied as a post-processing step to any correlation clustering algorithm. Furthermore, we show how these quantitative models can be used to predict the probability distribution that an object is created by these models. Our broad experimental evaluation demonstrates the beneficial impact of our method on several applications of significant practical importance.
On privacy preservation against adversarial data mining
Authors: Charu C. Aggarwal, Jian Pei, Bo Zhang
Venue: KDD
Year: 2006

Privacy preserving data processing has become an important topic recently because of advances in hardware technology which have lead to widespread proliferation of demographic and sensitive data. A rudimentary way to preserve privacy is to simply hide the information in some of the sensitive fields picked by a user. However, such a method is far from satisfactory in its ability to prevent adversarial data mining. Real data records are not randomly distributed. As a result, some fields in the records may be correlated with one another. If the correlation is sufficiently high, it may be possible for an adversary to predict some of the sensitive fields using other fields.In this paper, we study the problem of privacy preservation against adversarial data mining, which is to hide a minimal set of entries so that the privacy of the sensitive fields are satisfactorily preserved. In other words, even by data mining, an adversary still cannot accurately recover the hidden data entries. We model the problem concisely and develop an efficient heuristic algorithm which can find good solutions in practice. An extensive performance study is conducted on both synthetic and real data sets to examine the effectiveness of our approach.
Identifying "best bet" web search results by mining past user behavior
Authors: Eugene Agichtein, Zijian Zheng
Venue: KDD
Year: 2006

The top web search result is crucial for user satisfaction with the web search experience. We argue that the importance of the relevance at the top position necessitates special handling of the top web search result for some queries. We propose an effective approach of leveraging millions of past user interactions with a web search engine to automatically detect "best bet" top results preferred by majority of users. Interestingly, this problem can be more effectively addressed with classification than using state-of-the-art general ranking methods. Furthermore, we show that our general machine learning approach achieves precision comparable to a heavily tuned, domain-specific algorithm, with significantly higher coverage. Our experiments over millions of user interactions for thousands of queries demonstrate the effectiveness and robustness of our techniques.
Next frontier
Authors: Rakesh Agrawal
Venue: KDD
Year: 2006

This talk is about the next frontier in knowledge discovery and data mining.
CCCS: a top-down associative classifier for imbalanced class distribution
Authors: Bavani Arunasalam, Sanjay Chawla
Venue: KDD
Year: 2006

In this paper we propose CCCS, a new algorithm for classification based on association rule mining. The key innovation in CCCS is the use of a new measure, the "Complement Class Support (CCS)" whose application results in rules which are guaranteed to be positively correlated. Furthermore, the anti-monotonic property that CCS possesses has very different semantics vis-a-vis the traditional support measure. In particular, "good" rules have a low CCS value. This makes CCS an ideal measure to use in conjunction with a top-down algorithm. Finally, the nature of CCS allows the pruning of rules without the setting of any threshold parameter! To the best of our knowledge this is the first threshold-free algorithm in association rule mining for classification.
Detecting outliers using transduction and statistical testing
Authors: Daniel Barbará, Carlotta Domeniconi, James P. Rogers
Venue: KDD
Year: 2006

Outlier detection can uncover malicious behavior in fields like intrusion detection and fraud analysis. Although there has been a significant amount of work in outlier detection, most of the algorithms proposed in the literature are based on a particular definition of outliers (e.g., density-based), and use ad-hoc thresholds to detect them. In this paper we present a novel technique to detect outliers with respect to an existing clustering model. However, the test can also be successfully utilized to recognize outliers when the clustering information is not available. Our method is based on Transductive Confidence Machines, which have been previously proposed as a mechanism to provide individual confidence measures on classification decisions. The test uses hypothesis testing to prove or disprove whether a point is fit to be in each of the clusters of the model. We experimentally demonstrate that the test is highly robust, and produces very few misdiagnosed points, even when no clustering information is available. Furthermore, our experiments demonstrate the robustness of our method under the circumstances of data contaminated by outliers. We finally show that our technique can be successfully applied to identify outliers in a noisy data set for which no information is available (e.g., ground truth, clustering structure, etc.). As such our proposed methodology is capable of bootstrapping from a noisy data set a clean one that can be used to identify future outliers.