OpenRaiser/Intern-Atlas huggingface dataset:
Identifying non-actionable association rules
Authors: Bing Liu, Wynne Hsu, Yiming Ma
Venue: KDD
Year: 2001

Building predictive models and finding useful rules are two important tasks of data mining. While building predictive models has been well studied, finding useful rules for action still presents a major problem. A main obstacle is that many data mining algorithms often produce too many rules. Existing research has shown that most of the discovered rules are actually redundant or insignificant. Pruning techniques have been developed to remove those spurious and/or insignificant rules. In this paper, we argue that being a significant rule (or a non-redundant rule), however, does not mean that it is a potentially useful rule for action. Many significant rules (unpruned rules) are in fact not actionable. This paper studies this issue and presents an efficient algorithm to identify these non-actionable rules. Experiment results on many real-life datasets show that the number of non-actionable rules is typically quite large. The proposed technique thus enables the user to focus on fewer rules and to be assured that the remaining rules are non-redundant and potentially useful for action.
Discovering unexpected information from your competitors' web sites
Authors: Bing Liu, Yiming Ma, Philip S. Yu
Venue: KDD
Year: 2001

Ever since the beginning of the Web, finding useful information from the Web has been an important problem. Existing approaches include keyword-based search, wrapper-based information extraction, Web query and user preferences. These approaches essentially find information that matches the user's explicit specifications. This paper argues that this is insufficient. There is another type of information that is also of great interest, i.e., unexpected information, which is unanticipated by the user. Finding unexpected information is useful in many applications. For example, it is useful for a company to find unexpected information bout its competitors, e.g., unexpected services and products that its competitors offer. With this information, the company can learn from its competitors and/or design counter measures to improve its competitiveness. Since the number of pages of a typical commercial site is very large and there are also many relevant sites (competitors), it is very difficult for a human user to view each page to discover the unexpected information. Automated assistance is needed. In this paper, we propose a number of methods to help the user find various types of unexpected information from his/her competitors' Web sites. Experiment results show that these techniques are very useful in practice and also efficient.
Funnel report mining for the MSN network
Authors: Teresa Mah, Hank Hoek, Ying Li
Venue: KDD
Year: 2001

Data mining research has long concentrated on the five main areas: clustering, association discovery, classification, forecasting and sequential patterns. Web data mining projects are concerned mainly with text mining, user segmentation, forecasting web usage and analyzing users' clickstream patterns. We present a new type of web usage mining called funnel analysis or funnel report mining. A funnel report is a study of the retention behavior among a series of pages or sites. For example, of all hits on the home page of www.msn.com, what percentages of those are followed by hits to moneycentral.msn.com? What percentage of www.msn.com hits are followed by moneycentral.msn.com, and then www.msnbc.com? What are the most interesting funnels starting with www.msn.com? Where does the greatest drop off rate occur after a user has hit MSNBC? Funnel reports are extremely useful in e-business because they give product planners an idea of how usable and well-structured their site is. From our experience performing web usage mining for the MSN network of sites, funnel reports are requested even more than user segmentation analyses, site affiliation studies and classification exercises. In this paper, we define a framework for funnel analysis and provide a tree-based solution we have been using successfully to extract all relevant funnels using only one scan of the data file.
Finding simple intensity descriptions from event sequence data
Authors: Heikki Mannila, Marko Salmenkivi
Venue: KDD
Year: 2001

Sequences of events are an important type of data arising in various applications, including telecommunications, bio-statistics, web access analysis, etc. A basic approach to modeling such sequences is to find the underlying intensity functions describing the expected number of events per time unit. Typically, the intensity functions are assumed to be piecewise constant. We therefore consider different ways of fitting intensity models to event sequence data. We start by considering a Bayesian approach using Markov chain Monte Carlo (MCMC) methods with varying number of pieces. These methods can be used to produce posterior distributions on the intensity functions and they can also accomodate covariates. The drawback is that they are computationally intensive and thus are not very suitable for data mining applications in which large numbers of intensity functions have to be estimated. We consider dynamic programming approaches to finding the change points in the intensity functions. These methods can find the maximum likelihood intensity function in O(n2k) time for a sequence of n events and k different pieces of intensity. We show that simple heuristics can be used to prune the number of potential change points, yielding speedups of several orders of magnitude. The results of the improved dynamic programming method correspond very closely with the posterior averages produced by the MCMC methods.
Extracting targeted data from the web
Authors: Tom M. Mitchell
Venue: KDD
Year: 2001

Tom M. Mitchell is author of the textbook "Machine Learning" (McGraw Hill, 1997), President of the American Association for Artificial Intelligence and a member of the National Research Council's Computer Science and Telecommunications Board. He is Vice President and Chief Scientist at WhizBang Labs and is currently on a two-year leave of absence from Carnegie Mellon University where he is the Fredkin Professor of Learning and AI in the School of Computer Science and founding Director of CMU's Center for Automated Learning and Discovery. Mitchell's research interests span many areas of Machine Learning theory and practice. His current work at WhizBang Labs involves developing machine learning methods for extracting information from text. For example, WhizBang has developed the world's largest database of job openings by training its software to automatically locate and extract detailed information from job postings on corporate web sites (see www.flipdog.com).
Data filtering for automatic classification of rocks from reflectance spectra
Authors: Jonathan Moody, Ricardo Bezerra de Andrade e Silva, Joseph Vanderwaart
Venue: KDD
Year: 2001

The ability to identify the mineral composition of rocks and soils is an important tool for the exploration of geological sites. For instance, NASA intends to design robots that are sufficiently autonomous to perform this task on planetary missions. Spectrometer readings provide one important source of data for identifying sites with minerals of interest. Reflectance spectrometers measure intensities of light reflected from surfaces over a range of wavelengths. Spectral intensity patterns may in some cases be sufficiently distinctive for proper identification of minerals or classes of minerals. For some mineral classes, carbonates for example, specific short spectral intervals are known to carry a distinctive signature. Finding similar distinctive spectral ranges for other mineral classes is not an easy problem. We propose and evaluate data-driven techniques that automatically search for spectral ranges optimized for specific minerals. In one set of studies, we partition the whole interval of wavelengths available in our data into sub-intervals, or bins, and use a genetic algorithm to evaluate a candidate selection of subintervals. As alternatives to this computationally expensive search technique, we present an entropy-based heuristic that gives higher scores for wavelengths more likely to distinguish between classes, as well as other greedy search procedures. Results are presented for four different classes, showing reasonable improvements in identifying some, but not all, of the mineral classes tested.
Personalization from incomplete data: what you don't know can hurt
Authors: Balaji Padmanabhan, Zhiqiang (Eric) Zheng, Steven Orla Kimbrough
Venue: KDD
Year: 2001

Clickstream data collected at any web site (site-centric data) is inherently incomplete, since it does not capture users' browsing behavior across sites (user-centric data). Hence, models learned from such data may be subject to limitations, the nature of which has not been well studied. Understanding the limitations is particularly important since most current personalization techniques are based on site-centric data only. In this paper, we empirically examine the implications of learning from incomplete data in the context of two specific problems: (a) predicting if the remainder of any given session will result in a purchase and (b) predicting if a given user will make a purchase at any future session. For each of these problems we present new algorithms for fast and accurate data preprocessing of clickstream data. Based on a comprehensive experiment on user-level clickstream data gathered from 20,000 users' browsing behavior, we demonstrate that models built on user-centric data outperform models built on site-centric data for both prediction tasks.
Probabilistic query models for transaction data
Authors: Dmitry Pavlov, Padhraic Smyth
Venue: KDD
Year: 2001

We investigate the application of Bayesian networks, Markov random fields, and mixture models to the problem of query answering for transaction data sets. We formulate two versions of the querying problem: the query selectivity estimation (i.e., finding exact counts for tuples in a data set) and the query generalization problem (i.e., computing the probability that a tuple will occur in new data). We show that frequent itemsets are useful for reducing the original data to a compressed representation and introduce a method to store them using an ADTree data structure. In an extension of our earlier work on this topic we propose several new schemes for query answering based on the compressed representation that avoid direct scans of the data at query time. Experimental results on real-world transaction data sets provide insights into various tradeoffs involving the offline time for model-building, the online time for query-answering, the memory footprint of the compressed data, and the accuracy of the estimate provided to the query.
Mass collaboration and data mining
Authors: Raghu Ramakrishnan
Venue: KDD
Year: 2001

Mass Collaboration is a new "P2P"-style approach to large-scale knowledge sharing, with applications in customer support, focused community development, and capturing knowledge distributed within large organizations. Effectively supporting this paradigm raises many technical challenges, and offers intriguing opportunities for mining massive amounts of data captured continually from user interactions. Data mining offers the promise of increased business intelligence, and also improved user experiences, leading to increased participation and greater quality in the knowledge that is captured, both of which are central objectives in Mass Collaboration. In this talk, I will introduce Mass Collaboration and discuss some important data mining related issues.
Recommender systems in commerce and community
Authors: John Riedl
Venue: KDD
Year: 2001

Recommender systems have been revolutionizing the way shoppers and information seekers find what they want. We will study some of the tremendous successes and spectacular failures of recommenders in E-commerce to understand the causes of the success or failure. We will leverage that understanding into a set of principles for successfully applying recommenders to business problems. Finally, we will study the economic and social forces that are shaping the evolution of recommenders, and peer into the crystal ball to glimpse the directions the technology will be going in the future.
Evaluation of prediction models for marketing campaigns
Authors: Saharon Rosset, Einat Neumann, Uri Eick, Nurit Vatnik, Yizhak Idan
Venue: KDD
Year: 2001

We consider prediction-model evaluation in the context of marketing-campaign planning. In order to evaluate and compare models with specific campaign objectives in mind, we need to concentrate our attention on the appropriate evaluation-criteria. These should portray the model&apos;s ability to score accurately and to identify the relevant target population. In this paper we discuss some applicable model-evaluation and selection criteria, their relevance for campaign planning, their robustness under changing population distributions, and their employment when constructing confidence intervals. We illustrate our results with a case study based on our experience from several projects.
TreeDT: gene mapping by tree disequilibrium test
Authors: Petteri Sevon, Hannu Toivonen, Vesa Ollikainen
Venue: KDD
Year: 2001

We introduce and evaluate TreeDT, a novel gene mapping method which is based on discovering and assessing tree-like patterns in genetic marker data. Gene mapping aims at discovering a statistical connection from a particular disease or trait to a narrow region in the genome. In a typical case-control setting, data consists of genetic markers typed for a set of disease-associated chromosomes and a set of control chromosomes. A computer scientist would view this data as a set of strings.TreeDT extracts, essentially in the form of substrings and prefix trees, information about the historical recombinations in the population. This information is used to locate fragments potentially inherited from a common diseased founder, and to map the disease gene into the most likely such fragment. The method measures for each chromosomal location the disequilibrium of the prefix tree of marker strings starting from the location, to assess the distribution of disease-associated chromosomes.We evaluate experimentally the performance of TreeDT on realistic, simulated data sets, and comparisons to state of the art methods (TDT, HPM) show that TreeDT is very competitive.
Detecting graph-based spatial outliers: algorithms and applications (a summary of results)
Authors: Shashi Shekhar, Chang-Tien Lu, Pusheng Zhang
Venue: KDD
Year: 2001

Identification of outliers can lead to the discovery of unexpected, interesting, and useful knowledge. Existing methods are designed for detecting spatial outliers in multidimensional geometric data sets, where a distance metric is available. In this paper, we focus on detecting spatial outliers in graph structured data sets. We define statistical tests, analyze the statistical foundation underlying our approach, design several fast algorithms to detect spatial outliers, and provide a cost model for outlier detection procedures. In addition, we provide experimental results from the application of our algorithms on a Minneapolis-St.Paul(Twin Cities) traffic dataset to show their effectiveness and usefulness.
Knowledge base maintenance using knowledge gap analysis
Authors: W. Scott Spangler, Jeffrey T. Kreulen
Venue: KDD
Year: 2001

As the web and e-business have proliferated, the practice of using customer facing knowledge bases to augment customer service and support operations has increased. This can be a very efficient, scalable and cost effective way to share knowledge. The effectiveness and cost savings are proportional to the utility of the information within the knowledge base and inversely proportional to the amount of labor required in maintaining the knowledge. To address this issue, we have developed an algorithm and methodology to increase the utility of the information within a knowledge base while greatly reducing the labor required.In this paper, we describe an implementation of an algorithm and methodology for comparing a knowledge base to a set of problem tickets to determine which categories and subcategories are not well addressed within the knowledge base. We utilize text clustering on problem ticket text to determine a set of problem categories. We then compare each knowledge base solution document to each problem category centroid using a cosine distance metric. The distance between the "closest" solution document and the corresponding centroid becomes the basis of that problem category's "knowledge gap". Our claim is that this gap metric serves as a useful method for quickly and automatically determining which problem categories have no relevant solutions in a knowledge base. We have implemented our approach, and we present the results of performing a knowledge gap analysis on a set of support center problem tickets.
Tri-plots: scalable tools for multidimensional data mining
Authors: Agma J. M. Traina, Caetano Traina Jr., Spiros Papadimitriou, Christos Faloutsos
Venue: KDD
Year: 2001

We focus on the problem of finding patterns across two large, multidimensional datasets. For example, given feature vectors of healthy and of non-healthy patients, we want to answer the following questions: Are the two clouds of points separable? What is the smallest/largest pair-wise distance across the two datasets? Which of the two clouds does a new point (feature vector) come from?We propose a new tool, the tri-plot, and its generalization, the pq-plot, which help us answer the above questions. We provide a set of rules on how to interpret a tri-plot, and we apply these rules on synthetic and real datasets. We also show how to use our tool for classification, when traditional methods (nearest neighbor, classification trees) may fail.
Mining user session data to facilitate user interaction with a customer service knowledge base in RightNow Web
Authors: Doug Warner, J. Neal Richter, Stephen D. Durbin, Bikramjit Banerjee
Venue: KDD
Year: 2001

RightNow Web is an integrated software package for web-based customer service that has, at its core, a database of answers to frequently asked questions (FAQs). One major design goal is to facilitate end-user interaction with this dynamic document collection, i.e. make it as easy and efficient as possible for users to browse the collection and locate desired information. To this end, we perform several types of analysis on the session tracking database that records user navigation histories. First, using both explicit and implicit measures of user satisfaction, we infer a "solved count" representing the average utility of an FAQ. Second, using the user navigation patterns we construct a link matrix representing connections between FAQs. The technique of building up the link matrix and using it to advise users on related information amounts to a form of the "swarm intelligence" method of finding optimal paths. Both solved count and the link matrix are continuously updated as users interact with the site; furthermore, they are periodically "aged" to emphasize recent activity. The synergistic combination of these techniques allows users to learn from the database in a more effective manner, as evidenced by usage statistics.
Discovering outlier filtering rules from unlabeled data: combining a supervised learner with an unsupervised learner
Authors: Kenji Yamanishi, Jun&apos, ichi Takeuchi
Venue: KDD
Year: 2001

This paper is concerned with the problem of detecting outliers from unlabeled data. In prior work we have developed SmartSifter, which is an on-line outlier detection algorithm based on unsupervised learning from data. On the basis of SmartSifter this paper yields a new framework for outlier filtering using both supervised and unsupervised learning techniques iteratively in order to make the detection process more effective and more understandable. The outline of the framework is as follows: In the first round, for an initial dataset, we run SmartSifter to give each data a score, with a high score indicating a high possibility of being an outlier. Next, giving positive labels to a number of higher scored data and negative labels to a number of lower scored data, we create labeled examples. Then we construct an outlier filtering rule by supervised learning from them. Here the rule is generated based on the principle of minimizing extended stochastic complexity. In the second round, for a new dataset, we filter the data using the constructed rule, then among the filtered data, we run SmartSifter again to evaluate the data in order to update the filtering rule. Applying of our framework to the network intrusion detection, we demonstrate that 1) it can significantly improve the accuracy of SmartSifter, and 2) outlier filtering rules can help the user to discover a general pattern of an outlier group.
Infominer: mining surprising periodic patterns
Authors: Jiong Yang, Wei Wang, Philip S. Yu
Venue: KDD
Year: 2001

In this paper, we focus on mining surprising periodic patterns in a sequence of events. In many applications, e.g., computational biology, an infrequent pattern is still considered very significant if its actual occurrence frequency exceeds the prior expectation by a large margin. The traditional metric, such as support, is not necessarily the ideal model to measure this kind of surprising patterns because it treats all patterns equally in the sense that every occurrence carries the same weight towards the assessment of the significance of a pattern regardless of the probability of occurrence. A more suitable measurement, information, is introduced to naturally value the degree of surprise of each occurrence of a pattern as a continuous and monotonically decreasing function of its probability of occurrence. This would allow patterns with vastly different occurrence probabilities to be handled seamlessly. As the accumulated degree of surprise of all repetitions of a pattern, the concept of information gain is proposed to measure the overall degree of surprise of the pattern within a data sequence. The bounded information gain property is identified to tackle the predicament caused by the violation of the downward closure property by the information gain measure and in turn provides an efficient solution to this problem. Empirical tests demonstrate the efficiency and the usefulness of the proposed model.
Mining web logs for prediction models in WWW caching and prefetching
Authors: Qiang Yang, Henry Haining Zhang, Tianyi Li
Venue: KDD
Year: 2001

Web caching and prefetching are well known strategies for improving the performance of Internet systems. When combined with web log mining, these strategies can decide to cache and prefetch web documents with higher accuracy. In this paper, we present an application of web log mining to obtain web-document access patterns and use these patterns to extend the well-known GDSF caching policies and prefetching policies. Using real web logs, we show that this application of data mining can achieve dramatic improvement to web-access performance.