OpenRaiser/Intern-Atlas huggingface dataset:
Estimating business targets
Authors: Piew Datta, James Drew, Andrew Betz, D. R. Mani, Jeffery Howard
Venue: KDD
Year: 2001

Determining and setting maximal revenue expectations or other business performance targets---whether it is for regional company divisions or individual customers---can have profound financial implications. Operational techniques are changed, staffing levels are altered and management attention is re-focused---all in the name of expectations. In practice these expectations are often derived in an ad hoc manner. To address this unsupervised task, we combine nearest neighbor methods and classical statistical methods and derive a new solution to the classical econometric task of frontier analysis. We apply our methodology to two real world business problems in Verizon, a major telecommunications provider in the United States, more specifically in the print yellow page division Verizon Information Services: (1) identifying under marketed customers for targeted upselling campaigns and focused sales attention, and (2) benchmarking regional directory divisions to incent performance improvements. Our analysis uncovers some commercially useful aspects of these domains and by conservative estimates can increase revenue by several million dollars in each domain.
Co-clustering documents and words using bipartite spectral graph partitioning
Authors: Inderjit S. Dhillon
Venue: KDD
Year: 2001

Both document clustering and word clustering are well studied problems. Most existing algorithms cluster documents and words separately but not simultaneously. In this paper we present the novel idea of modeling the document collection as a bipartite graph between documents and words, using which the simultaneous clustering problem can be posed as a bipartite graph partitioning problem. To solve the partitioning problem, we use a new spectral co-clustering algorithm that uses the second left and right singular vectors of an appropriately scaled word-document matrix to yield good bipartitionings. The spectral algorithm enjoys some optimality properties; it can be shown that the singular vectors solve a real relaxation to the NP-complete graph bipartitioning problem. We present experimental results to verify that the resulting co-clustering algorithm works well in practice.
A spectral method to separate disconnected and nearly-disconnected web graph components
Authors: Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha
Venue: KDD
Year: 2001

Separation of connected components from a graph with disconnected graph components mostly use breadth-first search (BFS) or depth-first search (DFS) graph algorithms. Here we propose a new algebraic method to separate disconnected and nearly-disconnected components. This method is based on spectral graph partitioning, following a key observation that disconnected components will show up, after properly sorted, as step-function like curve in the lowest eigenvectors of the Laplacian matrix of the graph. Following an perturbative analysis framework, we systematically analyzed the graph structures, first on the disconnected subgraph case, and second on the effects of adding edges sparsely connecting different subgraphs as a perturbation. Several new results are derived, providing insights to spectral methods and related clustering objective function. Examples are given illustrating the concepts and results our methods. Comparing to the standard graph algorithms, this method has the same O(VE V + VVVlog(VVV)) complexity, but is easier to implement (using readily available eigensolvers). Further more the method can easily identify articulation points and bridges on nearly-disconnected graphs. Segmentation of a real example of Web graph for query amazon is given. We found that each disconnected or nearly-disconnected components forms a cluster on a clear topic.
GESS: a scalable similarity-join algorithm for mining large data sets in high dimensional spaces
Authors: Jens-Peter Dittrich, Bernhard Seeger
Venue: KDD
Year: 2001

The similarity join is an important operation for mining high-dimensional feature spaces. Given two data sets, the similarity join computes all tuples (x, y) that are within a distance ε.One of the most efficient algorithms for processing similarity-joins is the Multidimensional-Spatial Join (MSJ) by Koudas and Sevcik. In our previous work --- pursued for the two-dimensional case --- we found however that MSJ has several performance shortcomings in terms of CPU and I/O cost as well as memory-requirements. Therefore, MSJ is not generally applicable to high-dimensional data.In this paper, we propose a new algorithm named Generic External Space Sweep (GESS). GESS introduces a modest rate of data replication to reduce the number of expensive distance computations. We present a new cost-model for replication, an I/O model, and an inexpensive method for duplicate removal. The principal component of our algorithm is a highly flexible replication engine.Our analytical model predicts a tremendous reduction of the number of expensive distance computations by several orders of magnitude in comparison to MSJ (factor 107). In addition, the memory requirements of GESS are shown to be lower by several orders of magnitude. Furthermore, the I/O cost of our algorithm is by factor 2 better (independent from the fact whether replication occurs or not). Our analytical results are confirmed by a large series of simulations and experiments with synthetic and real high-dimensional data sets.
Mining the network value of customers
Authors: Pedro M. Domingos, Matthew Richardson
Venue: KDD
Year: 2001

One of the major applications of data mining is in helping companies determine which potential customers to market to. If the expected profit from a customer is greater than the cost of marketing to her, the marketing action for that customer is executed. So far, work in this area has considered only the intrinsic value of the customer (i.e, the expected profit from sales to her). We propose to model also the customer's network value: the expected profit from sales to other customers she may influence to buy, the customers those may influence, and so on recursively. Instead of viewing a market as a set of independent entities, we view it as a social network and model it as a Markov random field. We show the advantages of this approach using a social network mined from a collaborative filtering database. Marketing that exploits the network value of customers---also known as viral marketing---can be extremely effective, but is still a black art. Our work can be viewed as a step towards providing a more solid foundation for it, taking advantage of the availability of large relevant databases.
Data mining: are we there yet?
Authors: Herb Edelstein
Venue: KDD
Year: 2001

Data mining started its move out of the statistics and machine learning ghettos and into the mainstream almost 10 years ago. With great fanfare and a large influx of venture capital, data mining was going to change the very nature of business. Yet data mining products have had relatively modest success in the marketplace. The reasons include limitations and misplaced emphasis in the products' features and functions, unrealistic expectations set by messages from the data mining community, and a lack of readiness by many prospective users. This session will look at where vendors have succeeded and failed with their products, what expectations users should have, and suggestions for achieving the potential of this exciting and valuable technology.
Magical thinking in data mining: lessons from CoIL challenge 2000
Authors: Charles Elkan
Venue: KDD
Year: 2001

CoIL challenge 2000 was a supervised learning contest that attracted 43 entries. The authors of 29 entries later wrote explanations of their work. This paper discusses these reports and reaches three main conclusions. First, naive Bayesian classifiers remain competitive in practice: they were used by both the winning entry and the next best entry. Second, identifying feature interactions correctly is important for maximizing predictive accuracy: this was the difference between the winning classifier and all others. Third and most important, too many researchers and practitioners in data mining do not appreciate properly the issue of statistical significance and the danger of overfitting. Given a dataset such as the one for the CoIL contest, it is pointless to apply a very complicated learning algorithm, or to perform a very time-consuming model search. In either ease, one is likely to overfit the training data and to fool oneself in estimating predictive accuracy and in discovering useful correlations.
Proximal support vector machine classifiers
Authors: Glenn Fung, Olvi L. Mangasarian
Venue: KDD
Year: 2001

Instead of a standard support vector machine (SVM) that classifies points by assigning them to one of two disjoint half-spaces, points are classified by assigning them to the closest of two parallel planes (in input or feature space) that are pushed apart as far as possible. This formulation, which can also be interpreted as regularized least squares and considered in the much more general context of regularized networks [8, 9], leads to an extremely fast and simple algorithm for generating a linear or nonlinear classifier that merely requires the solution of a single system of linear equations. In contrast, standard SVMs solve a quadratic or a linear program that require considerably longer computational time. Computational results on publicly available datasets indicate that the proposed proximal SVM classifier has comparable test set correctness to that of standard SVM classifiers, but with considerably faster computational time that can be an order of magnitude faster. The linear proximal SVM can easily handle large datasets as indicated by the classification of a 2 million point 10-attribute set in 20.8 seconds. All computational results are based on 6 lines of MATLAB code.
Data mining with sparse grids using simplicial basis functions
Authors: Jochen Garcke, Michael Griebel
Venue: KDD
Year: 2001

Recently we presented a new approach [18] to the classi- cation problem arising in data mining. It is based on the regularization network approach but, in contrast to other methods which employ ansatz functions associated to data points, we use a grid in the usually high-dimensional feature space for the minimization process. To cope with the curse of dimensionality, we employ sparse grids [49]. Thus, only O(h
REVI-MINER, a KDD-environment for deviation detection and analysis of warranty and goodwill cost statements in automotive industry
Authors: Edgar Hotz, Udo Grimmer, Wolfgang Heuser, Gholamreza Nakhaeizadeh, Michael Wieczorek
Venue: KDD
Year: 2001

REVI-MINER is a KDD-environment which supports the detection and analysis of deviations in warranty and goodwill cost statements. The system was developed within the framework of a cooperation between DaimlerChrysler Research & Technology and Global Service and Parts (GSP) and is based upon the CRISP-DM methodology as a widely accepted process model for the solution of Data Mining problems. Also, we have implemented different approaches based on Machine learning and statistics which can be utilized for data cleaning in the preprocessing phase. The Data Mining models applied have been developed by using a statistical deviation detection approach. The tool supports controllers in their task of auditing the authorized repair shops. In this paper we describe the development phases which have led to REVI-MINER.
Data mining techniques to improve forecast accuracy in airline business
Authors: Christoph Hueglin, Francesco Vannotti
Venue: KDD
Year: 2001

Predictive models developed by applying Data Mining techniques are used to improve forecasting accuracy in the airline business. In order to maximize the revenue on a flight, the number of seats available for sale is typically higher than the physical seat capacity (overbooking). To optimize the overbooking rate, an accurate estimation of the number of no-show passengers (passengers who hold a valid booking but do not appear at the gate to board for the flight) is essential. Currently, no-shows on future flights are estimated from the number of no-shows on historical flights averaged on booking class level. In this work, classification trees and logistic regression models are applied to estimate the probability that an individual passenger turns out to be a no-show. Passenger information stored in the reservation system of the airline is either directly used as explanatory variable or used to create attributes that have an impact on the probability of a passenger to be a no-show. The total number of no-shows in each booking class or on the total flight is then obtained by accumulating the individual no-show probabilities over the entity of interest. We show that this forecasting approach is more accurate than the currently used method. In addition, the selected models lead to a deepened insight into passenger behavior.
Mining time-changing data streams
Authors: Geoff Hulten, Laurie Spencer, Pedro M. Domingos
Venue: KDD
Year: 2001

Most statistical and machine-learning algorithms assume that the data is a random sample drawn from a stationary distribution. Unfortunately, most of the large databases available for mining today violate this assumption. They were gathered over months or years, and the underlying processes generating them changed during this time, sometimes radically. Although a number of algorithms have been proposed for learning time-changing concepts, they generally do not scale well to very large databases. In this paper we propose an efficient algorithm for mining decision trees from continuously-changing data streams, based on the ultra-fast VFDT decision tree learner. This algorithm, called CVFDT, stays current while making the most of old data by growing an alternative subtree whenever an old one becomes questionable, and replacing the old with the new when the new becomes more accurate. CVFDT learns a model which is similar in accuracy to the one that would be learned by reapplying VFDT to a moving window of examples every time a new example arrives, but with O(1) complexity per example, as opposed to O(w), where w is the size of the window. Experiments on a set of large time-changing data streams demonstrate the utility of this approach.
Solving regression problems with rule-based ensemble classifiers
Authors: Nitin Indurkhya, Sholom M. Weiss
Venue: KDD
Year: 2001

We describe a lightweight learning method that induces an ensemble of decision-rule solutions for regression problems. Instead of direct prediction of a continuous output variable, the method discretizes the variable by k-means clustering and solves the resultant classification problem. Predictions on new examples are made by averaging the mean values of classes with votes that are close in number to the most likely class. We provide experimental evidence that this indirect approach can often yield strong results for many applications, generally outperforming direct approaches such as regression trees and rivaling bagged regression trees.
Mining top-n local outliers in large databases
Authors: Wen Jin, Anthony K. H. Tung, Jiawei Han
Venue: KDD
Year: 2001

Outlier detection is an important task in data mining with numerous applications, including credit card fraud detection, video surveillance, etc. A recent work on outlier detection has introduced a novel notion of local outlier in which the degree to which an object is outlying is dependent on the density of its local neighborhood, and each object can be assigned a Local Outlier Factor (LOF) which represents the likelihood of that object being an outlier. Although the concept of local outliers is a useful one, the computation of LOF values for every data objects requires a large number of &kgr;-nearest neighbors searches and can be computationally expensive. Since most objects are usually not outliers, it is useful to provide users with the option of finding only n most outstanding local outliers, i.e., the top-n data objects which are most likely to be local outliers according to their LOFs. However, if the pruning is not done carefully, finding top-n outliers could result in the same amount of computation as finding LOF for all objects. In this paper, we propose a novel method to efficiently find the top-n local outliers in large databases. The concept of "micro-cluster" is introduced to compress the data. An efficient micro-cluster-based local outlier mining algorithm is designed based on this concept. As our algorithm can be adversely affected by the overlapping in the micro-clusters, we proposed a meaningful cut-plane solution for overlapping data. The formal analysis and experiments show that this method can achieve good performance in finding the most outstanding local outliers.
Generalized clustering, supervised learning, and data assignment
Authors: Annaka Kalton, Pat Langley, Kiri Wagstaff, Jungsoon P. Yoo
Venue: KDD
Year: 2001

Clustering algorithms have become increasingly important in handling and analyzing data. Considerable work has been done in devising effective but increasingly specific clustering algorithms. In contrast, we have developed a generalized framework that accommodates diverse clustering algorithms in a systematic way. This framework views clustering as a general process of iterative optimization that includes modules for supervised learning and instance assignment. The framework has also suggested several novel clustering methods. In this paper, we investigate experimentally the efficacy of these algorithms and test some hypotheses about the relation between such unsupervised techniques and the supervised methods embedded in them.
Ensemble-index: a new approach to indexing large databases
Authors: Eamonn J. Keogh, Selina Chu, Michael J. Pazzani
Venue: KDD
Year: 2001

The problem of similarity search (query-by-content) has attracted much research interest. It is a difficult problem because of the inherently high dimensionality of the data. The most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a multidimensional index structure. Many dimensionality reduction techniques have been proposed, including Singular Value Decomposition (SVD), the Discrete Fourier Transform (DFT), the Discrete Wavelet Transform (DWT) and Piecewise Polynomial Approximation. In this work, we introduce a novel framework for using ensembles of two or more representations for more efficient indexing. The basic idea is that instead of committing to a single representation for an entire dataset, different representations are chosen for indexing different parts of the database. The representations are chosen based upon a local view of the database. For example, sections of the data that can achieve a high fidelity representation with wavelets are indexed as wavelets, but highly spectral sections of the data are indexed using the Fourier transform. At query time, it is necessary to search several small heterogeneous indices, rather than one large homogeneous index. As we will theoretically and empirically demonstrate this results in much faster query response times.
Robust space transformations for distance-based operations
Authors: Edwin M. Knorr, Raymond T. Ng, Ruben H. Zamar
Venue: KDD
Year: 2001

For many KDD operations, such as nearest neighbor search, distance-based clustering, and outlier detection, there is an underlying κ-D data space in which each tuple/object is represented as a point in the space. In the presence of differing scales, variability, correlation, and/or outliers, we may get unintuitive results if an inappropriate space is used.The fundamental question that this paper addresses is: "What then is an appropriate space?" We propose using a robust space transformation called the Donoho-Stahel estimator. In the first half of the paper, we show the key properties of the estimator. Of particular importance to KDD applications involving databases is the stability property, which says that in spite of frequent updates, the estimator does not: (a) change much, (b) lose its usefulness, or (c) require re-computation. In the second half, we focus on the computation of the estimator for high-dimensional databases. We develop randomized algorithms and evaluate how well they perform empirically. The novel algorithm we develop called the Hybrid-random algorithm is, in most cases, at least an order of magnitude faster than the Fixed-angle and Subsampling algorithms.
Mining e-commerce data: the good, the bad, and the ugly
Authors: Ron Kohavi
Venue: KDD
Year: 2001

Organizations conducting Electronic Commerce (e-commerce) can greatly benefit from the insight that data mining of transactional and clickstream data provides. Such insight helps not only to improve the electronic channel (e.g., a web site), but it is also a learning vehicle for the bigger organization conducting business at brick-and-mortar stores. The e-commerce site serves as an early alert system for emerging patterns and a laboratory for experimentation. For successful data mining, several ingredients are needed and e-commerce provides all the right ones (the Good). Web server logs, which are commonly used as the source of data for mining e-commerce data, were designed to debug web servers, and the data they provide is insufficient, requiring the use of heuristics to reconstruct events. Moreover, many events are never logged in web server logs, limiting the source of data for mining (the Bad). Many of the problems of dealing with web server log data can be resolved by properly architecting the e-commerce sites to generate data needed for mining. Even with a good architecture, however, there are challenging problems that remain hard to solve (the Ugly). Lessons and metrics based on mining real e-commerce data are presented.
Mining a stream of transactions for customer patterns
Authors: Diane Lambert, José C. Pinheiro
Venue: KDD
Year: 2001

Transaction data can arrive at a ferocious rate in the order that transactions are completed. The data contain an enormous amount of information about customers, not just transactions, but extracting up-to-date customer information from an ever changing stream of data and mining it in real-time is a challenge. This paper describes a statistically principled approach to designing short, accurate summaries or signatures of high dimensional customer behavior that can be kept current with a stream of transactions. A signature database can then be used for data mining and to provide approximate answers to many kinds of queries about current customers quickly and accurately, as an empirical study of the calling patterns of 96,000 wireless customers who made about 18 million wireless calls over a three month period shows.
Mining from open answers in questionnaire data
Authors: Hang Li, Kenji Yamanishi
Venue: KDD
Year: 2001

Surveys are an important part of marketing and customer relationship management, and open answers (i.e., answers to open questions) in particular may contain valuable information and provide an important basis for making business decisions. We have developed a text mining system that provides a new way for analyzing open answers in questionnaire data. The product is able to perform the following two functions: (A) accurate extraction of characteristics for individual analysis targets, (B) accurate extraction of the relationships among characteristics of analysis targets. In this paper, we describe the working of our text mining system. It employs two statistical learning techniques: rule analysis and Correspondence Analysis for performing the two functions. Our text mining system has already been put into use by a number of large corporations in Japan in the performance of text mining on various types of survey data, including open answers about brand images, open answers about company images, complaints about products, comments written on home pages, business reports, and help desk records. In this it has been found to be useful in forming a basis for effective business decisions.