OpenRaiser/Intern-Atlas huggingface dataset:
Evaluating classifiers' performance in a constrained environment
Authors: Anna Olecka
Venue: KDD
Year: 2002

In this paper, we focus on methodology of finding a classifier with a minimal cost in presence of additional performance constraints. ROCCH analysis, where accuracy and cost are intertwined in the solution space, was a revolutionary tool for two-class problems. We propose an alternative formulation, as an optimization problem, commonly used in Operations Research. This approach extends the ROCCH analysis to allow for locating optimal solutions while outside constraints are present. Similarly to the ROCCH analysis, we combine cost and class distribution while defining the objective function. Rather than focusing on slopes of the edges in the convex hull of the solution space, however, we treat cost as an objective function to be minimized over the solution space, by selecting the best performing classifier(s) (one or more vertex in the solution space). The Linear Programming framework provides a theoretical and computational methodology for finding the vertex (classifier) which minimizes the objective function.
Discovering word senses from text
Authors: Patrick Pantel, Dekang Lin
Venue: KDD
Year: 2002

Inventories of manually compiled dictionaries usually serve as a source for word senses. However, they often include many rare senses while missing corpus/domain-specific senses. We present a clustering algorithm called CBC (Clustering By Committee) that automatically discovers word senses from text. It initially discovers a set of tight clusters called committees that are well scattered in the similarity space. The centroid of the members of a committee is used as the feature vector of the cluster. We proceed by assigning words to their most similar clusters. After assigning an element to a cluster, we remove their overlapping features from the element. This allows CBC to discover the less frequent senses of a word and to avoid discovering duplicate senses. Each cluster that a word belongs to represents one of its senses. We also present an evaluation methodology for automatically measuring the precision and recall of discovered senses.
Bayesian analysis of massive datasets via particle filters
Authors: Greg Ridgeway, David Madigan
Venue: KDD
Year: 2002

Markov Chain Monte Carlo (MCMC) techniques revolutionized statistical practice in the 1990s by providing an essential toolkit for making the rigor and flexibility of Bayesian analysis computationally practical. At the same time the increasing prevalence of massive datasets and the expansion of the field of data mining has created the need to produce statistically sound methods that scale to these large problems. Except for the most trivial examples, current MCMC methods require a complete scan of the dataset for each iteration eliminating their candidacy as feasible data mining techniques.In this article we present a method for making Bayesian analysis of massive datasets computationally feasible. The algorithm simulates from a posterior distribution that conditions on a smaller, more manageable portion of the dataset. The remainder of the dataset may be incorporated by reweighting the initial draws using importance sampling. Computation of the importance weights requires a single scan of the remaining observations. While importance sampling increases efficiency in data access, it comes at the expense of estimation efficiency. A simple modification, based on the "rejuvenation" step used in particle filters for dynamic systems models, sidesteps the loss of efficiency with only a slight increase in the number of data accesses.To show proof-of-concept, we demonstrate the method on a mixture of transition models that has been used to model web traffic and robotics. For this example we show that estimation efficiency is not affected while offering a 95% reduction in data accesses.
Customer lifetime value modeling and its use for customer retention planning
Authors: Saharon Rosset, Einat Neumann, Uri Eick, Nurit Vatnik, Yizhak Idan
Venue: KDD
Year: 2002

We present and discuss the important business problem of estimating the effect of retention efforts on the Lifetime Value of a customer in the Telecommunications industry. We discuss the components of this problem, in particular customer value and length of service (or tenure) modeling, and present a novel segment-based approach, motivated by the segment-level view marketing analysts usually employ. We then describe how we build on this approach to estimate the effects of retention on Lifetime Value. Our solution has been successfully implemented in Amdocs' Business Insight (BI) platform, and we illustrate its usefulness in real-world scenarios.
Interactive deduplication using active learning
Authors: Sunita Sarawagi, Anuradha Bhamidipaty
Venue: KDD
Year: 2002

Deduplication is a key operation in integrating data from multiple sources. The main challenge in this task is designing a function that can resolve when a pair of records refer to the same entity in spite of various data inconsistencies. Most existing systems use hand-coded functions. One way to overcome the tedium of hand-coding is to train a classifier to distinguish between duplicates and non-duplicates. The success of this method critically hinges on being able to provide a covering and challenging set of training pairs that bring out the subtlety of deduplication function. This is non-trivial because it requires manually searching for various data inconsistencies between any two records spread apart in large lists.We present our design of a learning-based deduplication system that uses a novel method of interactively discovering challenging training pairs using active learning. Our experiments on real-life datasets show that active learning significantly reduces the number of instances needed to achieve high accuracy. We investigate various design issues that arise in building a system to provide interactive response, fast convergence, and interpretable output.
ADMIT: anomaly-based data mining for intrusions
Authors: Karlton Sequeira, Mohammed Javeed Zaki
Venue: KDD
Year: 2002

Security of computer systems is essential to their acceptance and utility. Computer security analysts use intrusion detection systems to assist them in maintaining computer system security. This paper deals with the problem of differentiating between masqueraders and the true user of a computer terminal. Prior efficient solutions are less suited to real time application, often requiring all training data to be labeled, and do not inherently provide an intuitive idea of what the data model means. Our system, called ADMIT, relaxes these constraints, by creating user profiles using semi-incremental techniques. It is a real-time intrusion detection system with host-based data collection and processing. Our method also suggests ideas for dealing with concept drift and affords a detection rate as high as 80.3% and a false positive rate as low as 15.3%.
Query, analysis, and visualization of hierarchically structured data using Polaris
Authors: Chris Stolte, Diane Tang, Pat Hanrahan
Venue: KDD
Year: 2002

... in a variety of applications such as corporate data warehouses and scientific computing. To support interactive analysis, many of these databases are augmented with hierarchical structures that provide meaningful levels of abstraction that can be leveraged by both the computer and analyst. This hierarchical structure generates many challenges and opportunities in the design of systems for the query, analysis, and visualization of these databases. In this
Exploiting response models: optimizing cross-sell and up-sell opportunities in banking
Authors: Andrew Storey, Marc-David Cohen
Venue: KDD
Year: 2002

The banking industry regularly mounts campaigns to improve customer value by offering new products to existing customers. In recent years this approach has gained significant momentum because of the increasing availability of customer data and the improved analysis capabilities in data mining. Typically, response models based on historical data are used to estimate the probability of a customer purchasing an additional product and the expected return from that additional purchase. Even with these computational improvements and accurate models of customer behavior, the problem of efficiently using marketing resources to maximize the return on marketing investment is a challenge. This problem is compounded because of the capability to launch multiple campaigns through several distribution channels over multiple time periods. The combination of alternatives creates a complicated array of possible actions. This paper presents a solution that answers the question of what products, if any, to offer to each customer in a way that maximizes the marketing return on investment. The solution is an improvement over the usual approach of picking the customers that have the largest expected value for a particular product because it is a global maximization from the viewpoint of the bank and allows for the effective implementation of business constraints across customers and business units. The approach accounts for limited resources, multiple sequential campaigns, and other business constraints. Furthermore, the solution provides insight into the cost of these constraints, in terms of decreased profits, and thus is an effective tool for both tactical campaign execution and strategic planning.
Hierarchical model-based clustering of large datasets through fractionation and refractionation
Authors: Jeremy Tantrum, Alejandro Murua, Werner Stuetzle
Venue: KDD
Year: 2002

The goal of clustering is to identify distinct groups in a dataset. Compared to non-parametric clustering methods like complete linkage, hierarchical model-based clustering has the advantage of offering a way to estimate the number of groups present in the data. However, its computational cost is quadratic in the number of items to be clustered, and it is therefore not applicable to large problems. We review an idea called Fractionation, originally conceived by Cutting, Karger, Pedersen and Tukey for non-parametric hierarchical clustering of large datasets, and describe an adaptation of Fractionation to model-based clustering. A further extension, called Refractionation, leads to a procedure that can be successful even in the difficult situation where there are large numbers of small groups.
Learning domain-independent string transformation weights for high accuracy object identification
Authors: Sheila Tejada, Craig A. Knoblock, Steven Minton
Venue: KDD
Year: 2002

The task of object identification occurs when integrating information from multiple websites. The same data objects can exist in inconsistent text formats across sites, making it difficult to identify matching objects using exact text match. Previous methods of object identification have required manual construction of domain-specific string transformations or manual setting of general transformation parameter weights for recognizing format inconsistencies. This manual process can be time consuming and error-prone. We have developed an object identification system called Active Atlas [18], which applies a set of domain-independent string transformations to compare the objects' shared attributes in order to identify matching objects. In this paper, we discuss extensions to the Active Atlas system, which allow it to learn to tailor the weights of a set of general transformations to a specific application domain through limited user input. The experimental results demonstrate that this approach achieves higher accuracy and requires less user involvement than previous methods across various application domains.
Handling very large numbers of association rules in the analysis of microarray data
Authors: Alexander Tuzhilin, Gediminas Adomavicius
Venue: KDD
Year: 2002

The problem of analyzing microarray data became one of important topics in bioinformatics over the past several years, and different data mining techniques have been proposed for the analysis of such data. In this paper, we propose to use association rule discovery methods for determining associations among expression levels of different genes. One of the main problems related to the discovery of these associations is the scalability issue. Microarrays usually contain very large numbers of genes that are sometimes measured in 10,000s. Therefore, analysis of such data can generate a very large number of associations that can often be measured in millions. The paper addresses this problem by presenting a method that enables biologists to evaluate these very large numbers of discovered association rules during the post-analysis stage of the data mining process. This is achieved by providing several rule evaluation operators, including rule grouping, filtering, browsing, and data inspection operators, that allow biologists to validate multiple individual gane regulation patterns at a time. By iteratively applying these operators, biologists can explore a significant part of all the initially generated rules in an acceptable period of time and thus answer biological questions that are of a particular interest to him or her. To validate our method, we tested our system on the microarray data pertaining to the studies of environmental hazards and their influence of gane expression processes. As a result, we managed to answer several questions that were of interest to the biologists that had collected this data.
What's the code?: automatic classification of source code archives
Authors: Secil Ugurel, Robert Krovetz, C. Lee Giles
Venue: KDD
Year: 2002

There are various source code archives on the World Wide Web. These archives are usually organized by application categories and programming languages. However, manually organizing source code repositories is not a trivial task since they grow rapidly and are very large (on the order of terabytes). We demonstrate machine learning methods for automatic classification of archived source code into eleven application topics and ten programming languages. For topical classification, we concentrate on C and C++ programs from the Ibiblio and the Sourceforge archives. Support vector machine (SVM) classifiers are trained on examples of a given programming language or programs in a specified category. We show that source code can be accurately and automatically classified into topical categories and can be identified to be in a specific programming language class.
Non-linear dimensionality reduction techniques for classification and visualization
Authors: Michail Vlachos, Carlotta Domeniconi, Dimitrios Gunopulos, George Kollios, Nick Koudas
Venue: KDD
Year: 2002

In this paper we address the issue of using local embeddings for data visualization in two and three dimensions, and for classification. We advocate their use on the basis that they provide an efficient mapping procedure from the original dimension of the data, to a lower intrinsic dimension. We depict how they can accurately capture the user's perception of similarity in high-dimensional data for visualization purposes. Moreover, we exploit the low-dimensional mapping provided by these embeddings, to develop new classification techniques, and we show experimentally that the classification accuracy is comparable (albeit using fewer dimensions) to a number of other classification procedures.
On interactive visualization of high-dimensional data using the hyperbolic plane
Authors: Jörg A. Walter, Helge J. Ritter
Venue: KDD
Year: 2002

We propose a novel projection based visualization method for high-dimensional datasets by combining concepts from MDS and the geometry of the hyperbolic spaces. Our approach Hyperbolic Multi-Dimensional Scaling (H-MDS) extends earlier work [7] using hyperbolic spaces for visualization of tree structures data ( "hyperbolic tree browser" ).By borrowing concepts from multi-dimensional scaling we map proximity data directly into the 2-dimensional hyperbolic space (H2). This removes the restriction to "quasihierarchical", graph-based data -- limiting previous work. Since a suitable distance function can convert all kinds of data to proximity (or distance-based) data this type of data can be considered the most general.We used the circular Poincaré model of the H2 which allows effective human-computer interaction: by moving the "focus" via mouse the user can navigate in the data without loosing the "context". In H2 the "fish-eye" behavior originates not simply by a non-linear view transformation but rather by extraordinary, non-Euclidean properties of the H2. Especially, the exponential growth of length and area of the underlying space makes the H2 a prime target for mapping hierarchical and (now also) high-dimensional data.We present several high-dimensional mapping examples including synthetic and real world data and a successful application for unstructured text. By analyzing and integrating multiple film critiques from news:rec.art.movies.reviews and the internet movie database, each movie becomes placed within the H2. Here the idea is, that related films share more words in their reviews than unrelated. Their semantic proximity leads to a closer arrangement. The result is a kind of high-level content structured display allowing the user to explore the "space of movies".
Item selection by "hub-authority" profit ranking
Authors: Ke Wang, Ming-Yen Thomas Su
Venue: KDD
Year: 2002

A fundamental problem in business and other applications is ranking items with respect to some notion of profit based on historical transactions. The difficulty is that the profit of one item not only comes from its own sales, but also from its influence on the sales of other items, i.e., the "cross-selling effect". In this paper, we draw an analogy between this influence and the mutual reinforcement of hub/authority web pages. Based on this analogy, we present a novel approach to the item ranking problem.We apply this ranking approach to solve two selection problems. In size-constrained selection, the maximum number of items that can be selected is fixed. In cost-constrained selection, there is no maximum number of items to be selected, but there is some cost associated with the selection of each item. In both cases, the question is what items should be selected to maximize the profit. Empirically, we show that this method finds profitable items in the presence of cross-selling effect.
A system for real-time competitive market intelligence
Authors: Sholom M. Weiss, Naval K. Verma
Venue: KDD
Year: 2002

A method is described for real-time market intelligence and competitive analysis. News stories are collected online for a designated group of companies. The goal is to detect critical differences in the text written about a company versus the text for its competitors. A solution is found by mapping the task into a non-stationary text categorization model. The overall design consists of the following components: (a) a real-time crawler that monitors newswires for stories about the competitors (b) a conditional document retriever that selects only those documents that meet the indicated conditions (c) text analysis techniques that convert the documents to a numerical format (d) rule induction methods for finding patterns in data (e) presentation techniques for displaying results. The method is extended to combine text with numerical measures, such as those based on stock prices and market capitalizations, that allow for more objective evaluations and projections.
Making every bit count: fast nonlinear axis scaling
Authors: Leejay Wu, Christos Faloutsos
Venue: KDD
Year: 2002

Existing axis scaling and dimensionality methods focus on preserving structure, usually determined via the Euclidean distance. In other words, they inherently assume that the Euclidean distance is already correct. We instead propose a novel nonlinear approach driven by an information-theoretic viewpoint, which we show is also strongly linked to intrinsic dimensionality, or degrees of freedom; and uniformity. Nonlinear transformations based on common probability distributions, combined with information-driven selection, simultaneously reduce the number of dimensions required and increase the value of those we retain. Experiments on real data confirm that this approach reveals correlations, finds novel attributes, and scales well.
B-EM: a classifier incorporating bootstrap with EM approach for data mining
Authors: Xintao Wu, Jianping Fan, Kalpathi R. Subramanian
Venue: KDD
Year: 2002

This paper investigates the problem of augmenting labeled data with unlabeled data to improve classification accuracy. This is significant for many applications such as image classification where obtaining classification labels is expensive, while large unlabeled examples are easily available. We investigate an Expectation Maximization (EM) algorithm for learning from labeled and unlabeled data. The reason why unlabeled data boosts learning accuracy is because it provides the information about the joint probability distribution. A theoretical argument shows that the more unlabeled examples are combined in learning, the more accurate the result. We then introduce B-EM algorithm, based on the combination of EM with bootstrap method, to exploit the large unlabeled data while avoiding prohibitive I/O cost. Experimental results over both synthetic and real data sets that the proposed approach has a satisfactory performance.
A refinement approach to handling model misfit in text categorization
Authors: Haoran Wu, Tong-Heng Phang, Bing Liu, Xiaoli Li
Venue: KDD
Year: 2002

Text categorization or classification is the automated assigning of text documents to pre-defined classes based on their contents. This problem has been studied in information retrieval, machine learning and data mining. So far, many effective techniques have been proposed. However, most techniques are based on some underlying models and/or assumptions. When the data fits the model well, the classification accuracy will be high. However, when the data does not fit the model well, the classification accuracy can be very low. In this paper, we propose a refinement approach to dealing with this problem of model misfit. We show that we do not need to change the classification technique itself (or its underlying model) to make it more flexible. Instead, we propose to use successive refinements of classification on the training data to correct the model misfit. We apply the proposed technique to improve the classification performance of two simple and efficient text classifiers, the Rocchio classifier and the naïve Bayesian classifier. These techniques are suitable for very large text collections because they allow the data to reside on disk and need only one scan of the data to build a text classifier. Extensive experiments on two benchmark document corpora show that the proposed technique is able to improve text categorization accuracy of the two techniques dramatically. In particular, our refined model is able to improve the naïve Bayesian or Rocchio classifier's prediction performance by 45% on average.