OpenRaiser/Intern-Atlas huggingface dataset:
Scaling multi-class support vector machines using inter-class confusion
Authors: Shantanu Godbole, Sunita Sarawagi, Soumen Chakrabarti
Venue: KDD
Year: 2002

Support vector machines (SVMs) excel at two-class discriminative learning problems. They often outperform generative classifiers, especially those that use inaccurate generative models, such as the naïve Bayes (NB) classifier. On the other hand, generative classifiers have no trouble in handling an arbitrary number of classes efficiently, and NB classifiers train much faster than SVMs owing to their extreme simplicity. In contrast, SVMs handle multi-class problems by learning redundant yes/no (one-vs-others) classifiers for each class, further worsening the performance gap. We propose a new technique for multi-way classification which exploits the accuracy of SVMs and the speed of NB classifiers. We first use a NB classifier to quickly compute a confusion matrix, which is used to reduce the number and complexity of the two-class SVMs that are built in the second stage. During testing, we first get the prediction of a NB classifier and use that to selectively apply only a subset of the two-class SVMs. On standard benchmarks, our algorithm is 3 to 6 times faster than SVMs and yet matches or even exceeds their accuracy.
A model for discovering customer value for E-content
Authors: Srinivasan Jagannathan, Jayanth Nayak, Kevin C. Almeroth, Markus Hofmann
Venue: KDD
Year: 2002

There exists a huge demand for multimedia goods and services in the Internet. Currently available bandwidth speeds can support sale of downloadable content like CDs, e-books, etc. as well as services like video-on-demand. In the future, such services will be prevalent in the Internet. Since costs are typically fixed, maximizing revenue can maximize profits. A primary determinant of revenue in such econtent markets is how much value the customers associate with the content. Though marketing surveys are useful, they cannot adapt to the dynamic nature of the Internet market. In this work, we examine how to learn customer valuations in close to real-time. Our contributions in this paper are threefold: (1) we develop a probabilistic model to describe customer behavior, (2) we develop a framework for pricing e-content based on basic economic principles, and (3) we propose a price discovering algorithm that learns customer behavior parameters and suggests prices to an e-content provider. We validate our algorithm using simulations. Our simulations indicate that our algorithm generates revenue close to the maximum expectation. Further, they also indicate that the algorithm is robust to transient customer behavior. 1.
Similarity measure based on partial information of time series
Authors: Xiaoming Jin, Yuchang Lu, Chunyi Shi
Venue: KDD
Year: 2002

Similarity measure of time series is an important subroutine in many KDD applications. Previous similarity models mainly focus on the prominent series behaviors by considering the whole information of time series. In this paper, we address the problem: which portion of information is more suitable for similarity measure for the data collected from a certain field. We propose a model for the retrieval and representation of the partial information in time series data, and a methodology for evaluating the similarity measurements based on partial information. The methodology is to retrieve various portions of information from the raw data and represent it in a concise form, then cluster the time series using the partial information and evaluate the similarity measurements through comparing the results with a standard classification. Experiments on data set from stock market give some interesting observations and justify the usefulness of our approach.
Predicting rare classes: can boosting make any weak learner strong?
Authors: Mahesh V. Joshi, Ramesh C. Agarwal, Vipin Kumar
Venue: KDD
Year: 2002

Boosting is a strong ensemble-based learning algorithm with the promise of iteratively improving the classification accuracy using any base learner, as long as it satisfies the condition of yielding weighted accuracy > 0.5. In this paper, we analyze boosting with respect to this basic condition on the base learner, to see if boosting ensures prediction of rarely occurring events with high recall and precision. First we show that a base learner can satisfy the required condition even for poor recall or precision levels, especially for very rare classes. Furthermore, we show that the intelligent weight updating mechanism in boosting, even in its strong cost-sensitive form, does not prevent cases where the base learner always achieves high precision but poor recall or high recall but poor precision, when mapped to the original distribution. In either of these cases, we show that the voting mechanism of boosting falls to achieve good overall recall and precision for the ensemble. In effect, our analysis indicates that one cannot be blind to the base learner performance, and just rely on the boosting mechanism to take care of its weakness. We validate our arguments empirically on variety of real and synthetic rare class problems. In particular, using AdaCost as the boosting algorithm, and variations of PNrule and RIPPER as the base learners, we show that if algorithm A achieves better recall-precision balance than algorithm B, then using A as the base learner in AdaCost yields significantly better performance than using B as the base learner.
Mining intrusion detection alarms for actionable knowledge
Authors: Klaus Julisch, Marc Dacier
Venue: KDD
Year: 2002

In response to attacks against enterprise networks, administrators increasingly deploy intrusion detection systems. These systems monitor hosts, networks, and other resources for signs of security violations. The use of intrusion detection has given rise to another difficult problem, namely the handling of a generally large number of alarms. In this paper, we mine historical alarms to learn how future alarms can be handled more efficiently. First, we investigate episode rules with respect to their suitability in this approach. We report the difficulties encountered and the unexpected insights gained. In addition, we introduce a new conceptual clustering technique, and use it in extensive experiments with real-world data to show that intrusion detection alarms can be handled efficiently by using previously mined knowledge.
Efficient handling of high-dimensional feature spaces by randomized classifier ensembles
Authors: Aleksander Kolcz, Xiaomei Sun, Jugal K. Kalita
Venue: KDD
Year: 2002

Handling massive datasets is a difficult problem not only due to prohibitively large numbers of entries but in some cases also due to the very high dimensionality of the data. Often, severe feature selection is performed to limit the number of attributes to a manageable size, which unfortunately can lead to a loss of useful information. Feature space reduction may well be necessary for many stand-alone classifiers, but recent advances in the area of ensemble classifier techniques indicate that overall accurate classifier aggregates can be learned even if each individual classifier operates on incomplete "feature view" training data, i.e., such where certain input attributes are excluded. In fact, by using only small random subsets of features to build individual component classifiers, surprisingly accurate and robust models can be created. In this work we demonstrate how these types of architectures effectively reduce the feature space for submodels and groups of sub-models, which lends itself to efficient sequential and/or parallel implementations. Experiments with a randomized version of Adaboost are used to support our arguments, using the text classification task as an example.
A parallel learning algorithm for text classification
Authors: Canasai Kruengkrai, Chuleerat Jaruskulchai
Venue: KDD
Year: 2002

Text classification is the process of classifying documents into predefined categories based on their content. Existing supervised learning algorithms to automatically classify text need sufficient labeled documents to learn accurately. Applying the Expectation-Maximization (EM) algorithm to this problem is an alternative approach that utilizes a large pool of unlabeled documents to augment the available labeled documents. Unfortunately, the time needed to learn with these large unlabeled documents is too high. This paper introduces a novel parallel learning algorithm for text classification task. The parallel algorithm is based on the combination of the EM algorithm and the naive Bayes classifier. Our goal is to improve the computational time in learning and classifying process. We studied the performance of our parallel algorithm on a large Linux PC cluster called PIRUN Cluster. We report both timing and accuracy results. These results indicate that the proposed parallel algorithm is capable of handling large document collections.
Instability of decision tree classification algorithms
Authors: Ruey-Hsia Li, Geneva G. Belford
Venue: KDD
Year: 2002

The instability problem of decision tree classification algorithms is that small changes in input training samples may cause dramatically large changes in output classification rules. Different rules generated from almost the same training samples are against human intuition and complicate the process of decision making. In this paper, we present fundamental theorems for the instability problem of decision tree classifiers. The first theorem gives the relationship between a data change and the resulting tree structure change (i.e. split change). The second theorem, Instability Theorem, provides the cause of the instability problem. Based on the two theorems, algorithmic improvements can be made to lessen the instability problem. Empirical results illustrate the theorem statements. The trees constructed by the proposed algorithm are more stable, noise-tolerant, informative, expressive, and concise. Our proposed sensitivity measure can be used as a metric to evaluate the stability of splitting predicates. The tree sensitivity is an indicator of the confidence level in rules and the effective lifetime of rules.
Construct robust rule sets for classification
Authors: Jiuyong Li, Rodney W. Topor, Hong Shen
Venue: KDD
Year: 2002

We study the problem of computing classification rule sets from relational databases so that accurate predictions can be made on test data with missing attribute values. Traditional classifiers perform badly when test data are not as complete as the training data because they tailor a training database too much. We introduce the concept of one rule set being more robust than another, that is, able to make more accurate predictions on test data with missing attribute values. We show that the optimal class association rule set is as robust as the complete class association rule set. We then introduce the k-optimal rule set, which provides predictions exactly the same as the optimal class association rule set on test data with up to k missing attribute values. This leads to a hierarchy of k-optimal rule sets in which decreasing size corresponds to decreasing robustness, and they all more robust than a traditional classification rule set. We introduce two methods to find k-optimal rule sets, i.e. an optimal association rule mining approach and a heuristic approximate approach. We show experimentally that a k-optimal rule set generated by the optimal association rule mining approach performs better than that by the heuristic approximate approach and both rule sets perform significantly better than a typical classification rule set (C4.5Rules) on incomplete test data.
Mining heterogeneous gene expression data with time lagged recurrent neural networks
Authors: Yulan Liang, Arpad Kelemen
Venue: KDD
Year: 2002

Heterogeneous types of gene expressions may provide a better insight into the biological role of gene interaction with the environment, disease development and drug effect at the molecular level. In this paper for both exploring and prediction purposes a Time Lagged Recurrent Neural Network with trajectory learning is proposed for identifying and classifying the gene functional patterns from the heterogeneous nonlinear time series microarray experiments. The proposed procedures identify gene functional patterns from the dynamics of a state-trajectory learned in the heterogeneous time series and the gradient information over time. Also, the trajectory learning with Backpropagation through time algorithm can recognize gene expression patterns vary over time. This may reveal much more information about the regulatory network underlying gene expressions. The analyzed data were extracted from spotted DNA microarrays in the budding yeast expression measurements, produced by Eisen et al. The gene matrix contained 79 experiments over a variety of heterogeneous experiment conditions. The number of recognized gene patterns in our study ranged from two to ten and were divided into three cases. Optimal network architectures with different memory structures were selected based on Akaike and Bayesian information statistical criteria using two-way factorial design. The optimal model performance was compared to other popular gene classification algorithms such as Nearest Neighbor, Support Vector Machine, and Self-Organized Map. The reliability of the performance was verified with multiple iterated runs.
A robust and efficient clustering algorithm based on cohesion self-merging
Authors: Cheng-Ru Lin, Ming-Syan Chen
Venue: KDD
Year: 2002

Data clustering has attracted a lot of research attention in the field of computational statistics and data mining. In most related studies, the dissimilarity between two clusters is defined as the distance between their centroids, or the dis-tance between two closest (or farthest) data points. How-ever, all of these measurements are vulnerable to outliers, and removing the outliers precisely is yet another difficult task. In view of this, we propose a new similarity measure-ment, referred to as cohesion, to measure the inter-cluster distances. By using this new measurement of cohesion, we design a two-phase clustering algorithm, called cohesion-based self-merging (abbreviated as CSM), which runs in lin-ear time to the size of input data set. Combining the features of partitional and hierarchical clustering methods, algorithm CSM partitions the input data set into several small subclus-ters in the first phase, and then continuously merges the sub-clusters based on cohesion in a hierarchical manner in the second phase. As shown by our performance studies, the cohesion-based clustering is very robust and possesses the excellent tolerance to outliers in various workloads. More importantly, algorithm CSM is shown to be able to cluster the data sets of arbitrary shapes very efficiently, and provide better clustering results than those by prior methods.
Distributed data mining in a chain store database of short transactions
Authors: Cheng-Ru Lin, Chang-Hung Lee, Ming-Syan Chen, Philip S. Yu
Venue: KDD
Year: 2002

In this paper, we broaden the horizon of traditional rule mining by introducing a new framework of causality rule mining in a distributed chain store database. Specifically, the causality rule explored in this paper consists of a sequence of triggering events and a set of consequential events, and is designed with the capability of mining non-sequential, inter-transaction information. Hence, the causality rule mining provides a very general framework for rule derivation. Note, however, that the procedure of causality rule mining is very costly particularly in the presence of a huge number of candidate sets and a distributed database, and in our opinion, cannot be dealt with by direct extensions from existing rule mining methods. Consequently, we devise in this paper a series of level matching algorithms, including Level Matching (abbreviatedly as LM), Level Matching with Selective Scan (abbreviatedly as LMS), and Distributed Level Matching (abbreviatedly as Distibuted LM), to minimize the computing cost needed for the distributed data mining of causality rules. In addition, the phenomena of time window constraints are also taken into consideration for the development of our algorithms. As a result of properly employing the technologies of level matching and selective scan, the proposed algorithms present good efficiency and scalability in the mining of local and global causality rules. Scale-up experiments show that the proposed algorithms scale well with the number of sites and the number of customer transactions.Index Terms: knowledge discovery, distributed data mining causality rules, triggering events, consequential events
Collusion in the U.S. crop insurance program: applied data mining
Authors: Bertis B. Little, Walter L. Johnston, Ashley C. Lovell, Roderick M. Rejesus, Steve A. Steed
Venue: KDD
Year: 2002

This paper quantitatively analyzes indicators of Agent (policy seller), Adjuster (indemnity claim adjuster), Producer (policy purchaser/holder) indemnity behavior suggestive of collusion in the United States Department of Agriculture (USDA) Risk Management Agency (RMA) national crop insurance program. According to guidance from the federal law and using six indicator variables of indemnity behavior, those entities equal to or exceeding 150% of the county mean (computed using a simple jackknife procedure) on all entity-relevant indicators were flagged as "anomalous." Log linear analysis was used to test (I) hierarchical node-node arrangements and (2) a non-recursive model of node information sharing. Chi-square distributed deviance statistic identified the optimal log linear model. The results of the applied data mining technique used here suggest that the non-recursive triplet and Agent-producer doublet collusion probabilistically accounts for the greatest proportion of waste, fraud, and abuse in the federal crop insurance program. Triplet and Agent-producer doublets need detailed investigation for possible collusion. Hence, this data mining technique provided a high level of confidence when 24 million records were quantitatively analyzed for possible fraud, waste, or other abuse of the crop insurance program administered by the USDA RMA, and suspect entities reported to USDA. This data mining technique can be applied where vast amounts of data are available to detect patterns of collusion or conspiracy as may be of interest to the criminal justice or intelligence agencies.
Incremental context mining for adaptive document classification
Authors: Rey-Long Liu, Yun-Ling Lu
Venue: KDD
Year: 2002

Automatic document classification (DC) is essential for the management of information and knowledge. This paper explores two practical issues in DC: (1) each document has its context of discussion, and (2) both the content and vocabulary of the document database is intrinsically evolving. The issues call for adaptive document classification (ADC) that adapts a DC system to the evolving contextual requirement of each document category, so that input documents may be classified based on their contexts of discussion. We present an incremental context mining technique to tackle the challenges of ADC. Theoretical analyses and empirical results show that, given a text hierarchy, the mining technique is efficient in incrementally maintaining the evolving contextual requirement of each category. Based on the contextual requirements mined by the system, higher-precision DC may be achieved with better efficiency.
Mining frequent item sets by opportunistic projection
Authors: Junqiang Liu, Yunhe Pan, Ke Wang, Jiawei Han
Venue: KDD
Year: 2002

In this paper, we present a novel algorithm Opportune Project for mining complete set of frequent item sets by projecting databases to grow a frequent item set tree. Our algorithm is fundamentally different from those proposed in the past in that it opportunistically chooses between two different structures, array-based or tree-based, to represent projected transaction subsets, and heuristically decides to build unfiltered pseudo projection or to make a filtered copy according to features of the subsets. More importantly, we propose novel methods to build tree-based pseudo projections and array-based unfiltered projections for projected transaction subsets, which makes our algorithm both CPU time efficient and memory saving. Basically, the algorithm grows the frequent item set tree by depth first search, whereas breadth first search is used to build the upper portion of the tree if necessary. We test our algorithm versus several other algorithms on real world datasets, such as BMS-POS, and on IBM artificial datasets. The empirical results show that our algorithm is not only the most efficient on both sparse and dense databases at all levels of support threshold, but also highly scalable to very large databases.
Learning nonstationary models of normal network traffic for detecting novel attacks
Authors: Matthew V. Mahoney, Philip K. Chan
Venue: KDD
Year: 2002

Traditional intrusion detection systems (IDS) detect attacks by comparing current behavior to signatures of known attacks. One main drawback is the inability of detecting new attacks which do not have known signatures. In this paper we propose a learning algorithm that constructs models of normal behavior from attack-free network traffic. Behavior that deviates from the learned normal model signals possible novel attacks. Our IDS is unique in two respects. First, it is nonstationary, modeling probabilities based on the time since the last event rather than on average rate. This prevents alarm floods. Second, the IDS learns protocol vocabularies (at the data link through application layers) in order to detect unknown attacks that attempt to exploit implementation errors in poorly tested features of the target software. On the 1999 DARPA IDS evaluation data set [9], we detect 70 of 180 attacks (with 100 false alarms), about evenly divided between user behavioral anomalies (IP addresses and ports, as modeled by most other systems) and protocol anomalies. Because our methods are unconventional there is a significant non-overlap of our IDS with the original DARPA participants, which implies that they could be combined to increase coverage.
Mining product reputations on the Web
Authors: Satoshi Morinaga, Kenji Yamanishi, Kenji Tateishi, Toshikazu Fukushima
Venue: KDD
Year: 2002

Knowing the reputations of your own and/or competitors&apos; products is important for marketing and customer relationship management. It is, however, very costly to collect and analyze survey data manually. This paper presents a new framework for mining product reputations on the Internet. It automatically collects people&apos;s opinions about target products from Web pages, and it uses text mining techniques to obtain the reputations of those products. On the basis of human-test samples, we generate in advance syntactic and linguistic rules to determine whether any given statement is an opinion or not, as well as whether such any opinion is positive or negative in nature. We first collect statements regarding target products using a general search engine, and then, using the rules, extract opinions