OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic, real-time forecasting of online auctions via functional models
Authors: Wolfgang Jank, Galit Shmueli, Shanshan Wang
Venue: KDD
Year: 2006

We propose a dynamic model for forecasting price in online auctions. One of the key features of our model is that it operates during the live-auction, which makes it different from previous approaches that only consider static models. Our model is also different with respect to how information about price is incorporated. While one part of the model is based on the more traditional notion of an auction's price-level, another part incorporates its dynamics in the form of a price's velocity and acceleration. In that sense, it incorporates key features of a dynamic environment such as an online auction. The use of novel functional data methodology allows us to measure, and subsequently include, dynamic price characteristics. We illustrate our model on a diverse set of eBay auctions across many different book categories. We find significantly higher prediction accuracy compared to standard approaches.
Polynomial association rules with applications to logistic regression
Authors: Szymon Jaroszewicz
Venue: KDD
Year: 2006

A new class of associations (polynomial itemsets and polynomial association rules) is presented which allows for discovering nonlinear relationships between numeric attributes without discretization. For binary attributes, proposed associations reduce to classic itemsets and association rules. Many standard association rule mining algorithms can be adapted to finding polynomial itemsets and association rules. We applied polynomial associations to add non-linear terms to logistic regression models. Significant performance improvement was achieved over stepwise methods, traditionally used in statistics, with comparable accuracy.
CFI-Stream: mining closed frequent itemsets in data streams
Authors: Nan Jiang, Le Gruenwald
Venue: KDD
Year: 2006

Mining frequent closed itemsets provides complete and condensed information for non-redundant association rules generation. Extensive studies have been done on mining frequent closed itemsets, but they are mainly intended for traditional transaction databases and thus do not take data stream characteristics into consideration. In this paper, we propose a novel approach for mining closed frequent itemsets over data streams. It computes and maintains closed itemsets online and incrementally, and can output the current closed frequent itemsets in real time based on users' specified thresholds. Experimental results show that our proposed method is both time and space efficient, has good scalability as the number of transactions processed increases and adapts very rapidly to the change in data streams.
Introducing perpetual analytics
Authors: Jeff Jonas
Venue: KDD
Year: 2006

Common strategies to liberate an organization's information assets for situational awareness frequently rely on infrastructure components such as data integration, enterprise search, federation, data warehousing, and so on. And while these traditional platforms enable analysts to get better and faster answers to their queries, the next big advance will change this paradigm. Users cannot be expected to formulate and ask every smart question every day. And to escape this impractical and un-scalable model, the new paradigm will involve technologies where "the data finds the data" and "relevance finds the user." Perpetual Analytics describes a class of application whereby enterprise context is assembled, in real-time, on data streams as fast as operational systems record observations. Context construction is a "data finds the data" activity which enables events of interest to be streamed to subscribers. In this talk, I will talk at some depth about the dynamics of such systems including scalability and sustainability.
Capital One's statistical problems: our top ten list
Authors: William Kahn
Venue: KDD
Year: 2006

Capital One is a highly quantitatively driven diversified financial services firm. As such, we make broad and deep use of the entire repertory of highly quantitative techniques. This talk will present our top ten statistical problems. Indeed, one of them has, as a sub point, the data mining dimension, but it will likely be useful for data miners to see how their research needs to complement, and fit into, the entire range of hard statistical issues.
Mining quantitative correlated patterns using an information-theoretic approach
Authors: Yiping Ke, James Cheng, Wilfred Ng
Venue: KDD
Year: 2006

Existing research on mining quantitative databases mainly focuses on mining associations. However, mining associations is too expensive to be practical in many cases. In this paper, we study mining correlations from quantitative databases and show that it is a more effective approach than mining associations. We propose a new notion of Quantitative Correlated Patterns (QCPs), which is founded on two formal concepts, mutual information and all-confidence. We first devise a normalization on mutual information and apply it to QCP mining to capture the dependency between the attributes. We further adopt all-confidence as a quality measure to control, at a finer granularity, the dependency between the attributes with specific quantitative intervals. We also propose a supervised method to combine the consecutive intervals of the quantitative attributes based on mutual information, such that the interval combining is guided by the dependency between the attributes. We develop an algorithm, QCoMine, to efficiently mine QCPs by utilizing normalized mutual information and all-confidence to perform a two-level pruning. Our experiments verify the efficiency of QCoMine and the quality of the QCPs.
Maximally informative k-itemsets and their efficient discovery
Authors: Arno J. Knobbe, Eric K. Y. Ho
Venue: KDD
Year: 2006

In this paper we present a new approach to mining binary data. We treat each binary feature (item) as a means of distinguishing two sets of examples. Our interest is in selecting from the total set of items an itemset of specified size, such that the database is partitioned with as uniform a distribution over the parts as possible. To achieve this goal, we propose the use of joint entropy as a quality measure for itemsets, and refer to optimal itemsets of cardinality k as maximally informative k-itemsets. We claim that this approach maximises distinctive power, as well as minimises redundancy within the feature set. A number of algorithms is presented for computing optimal itemsets efficiently.
Measuring and extracting proximity in networks
Authors: Yehuda Koren, Stephen C. North, Chris Volinsky
Venue: KDD
Year: 2006

Measuring distance or some other form of proximity between objects is a standard data mining tool. Connection subgraphs were recently proposed as a way to demonstrate proximity between nodes in networks. We propose a new way of measuring and extracting proximity in networks called "cycle free effective conductance"(CFEC). Our proximity measure can handle more than two endpoints, directed edges, is statistically well-behaved, and produces an effectiveness score for the computed subgraphs. We provide an efficien talgorithm. Also, we report experimental results and show examples for three large network data sets: a telecommunications calling graph, the IMDB actors graph, and an academic co-authorship network.
Structure and evolution of online social networks
Authors: Ravi Kumar, Jasmine Novak, Andrew Tomkins
Venue: KDD
Year: 2006

In this paper, we consider the evolution of structure within large online social networks. We present a series of measurements of two such networks, together comprising in excess of five million people and ten million friendship links, annotated with metadata capturing the time of every event in the life of the network. Our measurements expose a surprising segmentation of these networks into three regions: singletons who do not participate in the network; isolated communities which overwhelmingly display star structure; and a giant component anchored by a well-connected core region which persists even in the absence of stars. We present a simple model of network growth which captures these aspects of component structure. The model follows our ex-perimental results, characterizing users as either passive members of the network; inviters who encourage offline friends and acquain-tances to migrate online; and linkers who fully participate in the social evolution of the network.
Hierarchical topic segmentation of websites
Authors: Ravi Kumar, Kunal Punera, Andrew Tomkins
Venue: KDD
Year: 2006

In this paper, we consider the problem of identifying and segmenting topically cohesive regions in the URL tree of a large website. Each page of the website is assumed to have a topic label or a distribution on topic labels generated using a standard classifier. We develop a set of cost measures characterizing the benefit accrued by introducing a segmentation of the site based on the topic labels. We propose a general framework to use these measures for describing the quality of a segmentation; we also provide an efficient algorithm to find the best segmentation in this framework. Extensive experiments on human-labeled data confirm the soundness of our framework and suggest that a judicious choice of cost measures allows the algorithm to perform surprisingly accurate topical segmentations.
New EM derived from Kullback-Leibler divergence
Authors: Longin Jan Latecki, Marc Sobel, Rolf Lakämper
Venue: KDD
Year: 2006

We introduce a new EM framework in which it is possible not only to optimize the model parameters but also the number of model components. A key feature of our approach is that we use nonparametric density estimation to improve parametric density estimation in the EM framework. While the classical EM algorithm estimates model parameters empirically using the data points themselves, we estimate them using nonparametric density estimates.There exist many possible applications that require optimal adjustment of model components. We present experimental results in two domains. One is polygonal approximation of laser range data, which is an active research topic in robot navigation. The other is grouping of edge pixels to contour boundaries, which still belongs to unsolved problems in computer vision.
Bias and controversy: beyond the statistical deviation
Authors: Hady Wirawan Lauw, Ee-Peng Lim, Ke Wang
Venue: KDD
Year: 2006

In this paper, we investigate how deviation in evaluation activities may reveal bias on the part of reviewers and controversy on the part of evaluated objects. We focus on a 'data-centric approach' where the evaluation data is assumed to represent the 'ground truth'. The standard statistical approaches take evaluation and deviation at face value. We argue that attention should be paid to the subjectivity of evaluation, judging the evaluation score not just on 'what is being said' (deviation), but also on 'who says it' (reviewer) as well as on 'whom it is said about' (object). Furthermore, we observe that bias and controversy are mutually dependent, as there is more bias if there is higher deviation on a less controversial object. To address this mutual dependency, we propose a reinforcement model to identify bias and controversy. We test our model on real-life data to verify its applicability.
Workload-aware anonymization
Authors: Kristen LeFevre, David J. DeWitt, Raghu Ramakrishnan
Venue: KDD
Year: 2006

Protecting data privacy is an important problem in microdata distribution. Anonymization algorithms typically aim to protect individual privacy, with minimal impact on the quality of the resulting data. While the bulk of previous work has measured quality through one-size-fits-all measures, we argue that quality is best judged with respect to the workload for which the data will ultimately be used.This paper provides a suite of anonymization algorithms that produce an anonymous view based on a target class of workloads, consisting of one or more data mining tasks, as well as selection predicates. An extensive experimental evaluation indicates that this approach is often more effective than previous anonymization techniques.
Sampling from large graphs
Authors: Jure Leskovec, Christos Faloutsos
Venue: KDD
Year: 2006

Given a huge real graph, how can we derive a representative sample? There are many known algorithms to compute interesting measures (shortest paths, centrality, betweenness, etc.), but several of them become impractical for large graphs. Thus graph sampling is essential.The natural questions to ask are (a) which sampling method to use, (b) how small can the sample size be, and (c) how to scale up the measurements of the sample (e.g., the diameter), to get estimates for the large graph. The deeper, underlying question is subtle: how do we measure success?.We answer the above questions, and test our answers by thorough experiments on several, diverse datasets, spanning thousands nodes and edges. We consider several sampling methods, propose novel methods to check the goodness of sampling, and develop a set of scaling laws that describe relations between the properties of the original and the sample.In addition to the theoretical contributions, the practical conclusions from our work are: Sampling strategies based on edge selection do not perform well; simple uniform random node selection performs surprisingly well. Overall, best performing methods are the ones based on random-walks and "forest fire"; they match very accurately both static as well as evolutionary graph patterns, with sample sizes down to about 15% of the original graph.
Rule interestingness analysis using OLAP operations
Authors: Bing Liu, Kaidi Zhao, Jeffrey Benkler, Weimin Xiao
Venue: KDD
Year: 2006

The problem of interestingness of discovered rules has been investigated by many researchers. The issue is that data mining algorithms often generate too many rules, which make it very hard for the user to find the interesting ones. Over the years many techniques have been proposed. However, few have made it to real-life applications. Since August 2004, we have been working on a major application for Motorola. The objective is to find causes of cellular phone call failures from a large amount of usage log data. Class association rules have been shown to be suitable for this type of diagnostic data mining application. We were also able to put several existing interestingness methods to the test, which revealed some major shortcomings. One of the main problems is that most existing methods treat rules individually. However, we discovered that users seldom regard a single rule to be interesting by itself. A rule is only interesting in the context of some other rules. Furthermore, in many cases, each individual rule may not be interesting, but a group of them together can represent an important piece of knowledge. This led us to discover a deficiency of the current rule mining paradigm. Using non-zero minimum support and non-zero minimum confidence eliminates a large amount of context information, which makes rule analysis difficult. This paper proposes a novel approach to deal with all of these issues, which casts rule analysis as OLAP operations and general impression mining. This approach enables the user to explore the knowledge space to find useful knowledge easily and systematically. It also provides a natural framework for visualization. As an evidence of its effectiveness, our system, called Opportunity Map, based on these ideas has been deployed, and it is in daily use in Motorola for finding actionable knowledge from its engineering and other types of data sets.
Clustering pair-wise dissimilarity data into partially ordered sets
Authors: Jinze Liu, Qi Zhang, Wei Wang, Leonard McMillan, Jan F. Prins
Venue: KDD
Year: 2006

Ontologies represent data relationships as hierarchies of possibly overlapping classes. Ontologies are closely related to clustering hierarchies, and in this article we explore this relationship in depth. In particular, we examine the space of ontologies that can be generated by pairwise dissimilarity matrices. We demonstrate that classical clustering algorithms, which take dissimilarity matrices as inputs, do not incorporate all available information. In fact, only special types of dissimilarity matrices can be exactly preserved by previous clustering methods. We model ontologies as a partially ordered set (poset) over the subset relation. In this paper, we propose a new clustering algorithm, that generates a partially ordered set of clusters from a dissimilarity matrix.
Fast mining of high dimensional expressive contrast patterns using zero-suppressed binary decision diagrams
Authors: Elsa Loekito, James Bailey
Venue: KDD
Year: 2006

Patterns of contrast are a very important way of comparing multi-dimensional datasets. Such patterns are able to capture regions of high difference between two classes of data, and are useful for human experts and the construction of classifiers. However, mining such patterns is particularly challenging when the number of dimensions is large. This paper describes a new technique for mining several varieties of contrast pattern, based on the use of Zero-Suppressed Binary Decision Diagrams (ZBDDs), a powerful data structure for manipulating sparse data. We study the mining of both simple contrast patterns, such as emerging patterns, and more novel and complex contrasts, which we call disjunctive emerging patterns. A performance study demonstrates our ZBDD technique is highly scalable, substantially improves on state of the art mining for emerging patterns and can be effective for discovering complex contrasts from datasets with thousands of attributes.
Visual data mining using principled projection algorithms and information visualization techniques
Authors: Dharmesh M. Maniyar, Ian T. Nabney
Venue: KDD
Year: 2006

We introduce a flexible visual data mining framework which combines advanced projection algorithms from the machine learning domain and visual techniques developed in the information visualization domain. The advantage of such an interface is that the user is directly involved in the data mining process. We integrate principled projection algorithms, such as generative topographic mapping (GTM) and hierarchical GTM (HGTM), with powerful visual techniques, such as magnification factors, directional curvatures, parallel coordinates and billboarding, to provide a visual data mining framework. Results on a real-life chemoinformatics dataset using GTM are promising and have been analytically compared with the results from the traditional projection methods. It is also shown that the HGTM algorithm provides additional value for large datasets. The computational complexity of these algorithms is discussed to demonstrate their suitability for the visual data mining framework.
Information extraction, data mining and joint inference
Authors: Andrew McCallum
Venue: KDD
Year: 2006

Although information extraction and data mining appear together in many applications, their interface in most current systems would better be described as serial juxtaposition than as tight integration. Information extraction populates slots in a database by identifying relevant subsequences of text, but is usually not aware of the emerging patterns and regularities in the database. Data mining methods begin from a populated database, and are often unaware of where the data came from, or its inherent uncertainties. The result is that the accuracy of both suffers, and accurate mining of complex text sources has been beyond reach.In this talk I will describe work in probabilistic models that perform joint inference across multiple components of an information processing pipeline in order to avoid the brittle accumulation of errors. After briefly introducing conditional random fields, I will describe recent work in information extraction leveraging factorial state representations, entity resolution, and transfer learning, as well as scalable methods of inference and learning. I'll close with some recent work on probabilistic models for social network analysis, and a demonstration of Rexa.info, a new research paper search engine.
A new multi-view regression approach with an application to customer wallet estimation
Authors: Srujana Merugu, Saharon Rosset, Claudia Perlich
Venue: KDD
Year: 2006

Motivated by the problem of customer wallet estimation, we propose a new setting for multi-view regression, where we learn a completely unobserved target (in our case, customer wallet) by modeling it as a "central link" in a directed graphical model, connecting multiple sets of observed variables. The resulting conditional independence allows us to reduce the maximum discriminative likelihood estimation problem to a convex optimization problem for exponential linear models. We show that under certain modeling assumptions, in particular, when there exist two conditionally independent views and the noise is Gaussian, this problem can be reduced to a single least squares regression. Thus, for this specific, but widely applicable setting, the "unsupervised" multi-view problem can be solved via a simple supervised learning approach. This reduction also allows us to test the statistical independence assumptions underlying the graphical model and perform variable selection. We demonstrate the effectiveness of our approach on our motivating problem of customer wallet estimation and on simulation data.
Efficient multidimensional data representations based on multiple correspondence analysis
Authors: Riadh Ben Messaoud, Omar Boussaid, Sabine Loudcher Rabaséda
Venue: KDD
Year: 2006

In the On Line Analytical Processing (OLAP) context, exploration of huge and sparse data cubes is a tedious task which does not always lead to efficient results. In this paper, we couple OLAP with the Multiple Correspondence Analysis (MCA) in order to enhance visual representations of data cubes and thus, facilitate their interpretations and analysis. We also provide a quality criterion to measure the relevance of obtained representations. The criterion is based on a geometric neighborhood concept and a similarity metric between cells of a data cube. Experimental results on real data proved the interest and the efficiency of our approach.
Aggregating time partitions
Authors: Taneli Mielikäinen, Evimaria Terzi, Panayiotis Tsaparas
Venue: KDD
Year: 2006

Partitions of sequential data exist either per se or as a result of sequence segmentation algorithms. It is often the case that the same timeline is partitioned in many different ways. For example, different segmentation algorithms produce different partitions of the same underlying data points. In such cases, we are interested in producing an aggregate partition, i.e., a segmentation that agrees as much as possible with the input segmentations. Each partition is defined as a set of continuous non-overlapping segments of the timeline. We show that this problem can be solved optimally in polynomial time using dynamic programming. We also propose faster greedy heuristics that work well in practice. We experiment with our algorithms and we demonstrate their utility in clustering the behavior of mobile-phone users and combining the results of different segmentation algorithms on genomic sequences.