OpenRaiser/Intern-Atlas huggingface dataset:
Efficient mining of iterative patterns for software specification discovery
Authors: David Lo, Siau-Cheng Khoo, Chao Liu
Venue: KDD
Year: 2007

Studies have shown that program comprehension takes up to 45% of software development costs. Such high costs are caused by the lack-of documented specification and further aggravated by the phenomenon of software evolution. There is a need for automated tools to extract specifications to aid program comprehension. In this paper, a novel technique to efficiently mine common software temporal patterns from traces is proposed. These patterns shed light on program behaviors, and are termed iterative patterns. They capture unique characteristic of software traces, typically not found in arbitrary sequences. Specifically, due to loops, interesting iterative patterns can occur multiple times within a trace. Furthermore, an occurrence of an iterative pattern in a trace can extend across a sequence of indefinite length. Since a program behavior can be manifested in numerous ways, analyzing a single trace will not be sufficient. Iterative pattern mining extends sequential pattern and episode minings to discover frequent iterative patterns which occur repetitively both within a program trace and across multiple traces. In this paper, we present CLIPER (CLosed Iterative Pattern minER) to efficiently mine a closed set of iterative patterns. A performance study on several simulated and real datasets shows the efficiency of our mining algorithm and effectiveness of our pruning strategy. Our case study on JBoss Application Server confirms the usefulness of mined patterns in discovering interesting software behavioral specification.
Distributed classification in peer-to-peer networks
Authors: Ping Luo, Hui Xiong, Kevin Lü, Zhongzhi Shi
Venue: KDD
Year: 2007

This work studies the problem of distributed classification in peer-to-peer(P2P) networks. While there has been a significant amount of work in distributed classification, most of existing algorithms are not designed for P2P networks. Indeed, as server-less and router-less systems, P2P networks impose several challenges for distributed classification: (1) it is not practical to have global synchronization in large-scale P2P networks; (2)there are frequent topology changes caused by frequent failure and recovery of peers; and (3) there are frequent on-the-fly data updates on each peer.
Automatic labeling of multinomial topic models
Authors: Qiaozhu Mei, Xuehua Shen, ChengXiang Zhai
Venue: KDD
Year: 2007

Multinomial distributions over words are frequently used to model topics in text collections. A common, major challenge in applying all such topic models to any text mining problem is to label a multinomial topic model accurately so that a user can interpret the discovered topic. So far, such labels have been generated manually in a subjective way. In this paper, we propose probabilistic approaches to automatically labeling multinomial topic models in an objective way. We cast this labeling problem as an optimization problem involving minimizing Kullback-Leibler divergence between word distributions and maximizing mutual information between a label and a topic model. Experiments with user study have been done on two text data sets with different genres.The results show that the proposed labeling methods are quite effective to generate labels that are meaningful and useful for interpreting the discovered topic models. Our methods are general and can be applied to labeling topics learned through all kinds of topic models such as PLSA, LDA, and their variations.
Joint cluster analysis of attribute and relationship data withouta-priori specification of the number of clusters
Authors: Flavia Moser, Rong Ge, Martin Ester
Venue: KDD
Year: 2007

In many applications, attribute and relationship data areavailable, carrying complementary information about real world entities. In such cases, a joint analysis of both types of data can yield more accurate results than classical clustering algorithms that either use only attribute data or only relationship (graph) data. The Connected k-Center (CkC) has been proposed as the first joint cluster analysis model to discover k clusters which are cohesive on both attribute and relationship data. However, it is well-known that prior knowledge on the number of clusters is often unavailable in applications such as community dentification and hotspot analysis. In this paper, we introduce and formalize the problem of discovering an a-priori unspecified number of clusters in the context of joint cluster analysis of attribute and relationship data, called Connected X Clusters (CXC) problem. True clusters are assumed to be compact and distinctive from their neighboring clusters in terms of attribute data and internally connected in terms of relationship data. Different from classical attribute-based clustering methods, the neighborhood of clusters is not defined in terms of attribute data but in terms of relationship data. To efficiently solve the CXC problem, we present JointClust, an algorithm which adopts a dynamic two-phase approach. In the first phase, we find so called cluster atoms. We provide a probability analysis for thisphase, which gives us a probabilistic guarantee, that each true cluster is represented by at least one of the initial cluster atoms. In the second phase, these cluster atoms are merged in a bottom-up manner resulting in a dendrogram. The final clustering is determined by our objective function. Our experimental evaluation on several real datasets demonstrates that JointClust indeed discovers meaningful and accurate clusterings without requiring the user to specify the number of clusters.
Domain-constrained semi-supervised mining of tracking models in sensor networks
Authors: Rong Pan, Junhui Zhao, Vincent Wenchen Zheng, Jeffrey Junfeng Pan, Dou Shen, Sinno Jialin Pan, Qiang Yang
Venue: KDD
Year: 2007

Accurate localization of mobile objects is a major research problem in sensor networks and an important data mining application. Specifically, the localization problem is to determine the location of a client device accurately given the radio signal strength values received at the client device from multiple beacon sensors or access points. Conventional data mining and machine learning methods can be applied to solve this problem. However, all of them require large amounts of labeled training data, which can be quite expensive. In this paper, we propose a probabilistic semi supervised learning approach to reduce the calibration effort and increase the tracking accuracy. Our method is based on semi-supervised conditional random fields which can enhance the learned model from a small set of training data with abundant unlabeled data effectively. To make our method more efficient, we exploit a Generalized EM algorithm coupled with domain constraints. We validate our method through extensive experiments in a real sensor network using Crossbow MICA2 sensors. The results demonstrate the advantages of methods compared to other state-of-the-art object-tracking algorithms.
Applying collaborative filtering techniques to movie search for better ranking and browsing
Authors: Seung-Taek Park, David M. Pennock
Venue: KDD
Year: 2007

We propose a new ranking method, which combines recommender systems with information search tools for better search and browsing. Our method uses a collaborative filtering algorithm to generate personal item authorities for each user and combines them with item proximities for better ranking. To demonstrate our approach, we build a prototype movie search and browsing engine called MAD6 (Movies, Actors and Directors; 6 degrees of separation). We conduct offline and online tests of our ranking algorithm. For offline testing, we use Yahoo! Search queries that resulted in a click on a Yahoo! Movies or Internet Movie Database (IMDB) movie URL. Our online test involved 44 Yahoo! employees providing subjective assessments of results quality. In both tests, our ranking methods show significantly better recall and quality than IMDB search and Yahoo! Movies current search.
Data mining at the crossroads: successes, failures and learning from them
Authors: Srinivasan Parthasarathy
Venue: KDD
Year: 2007

Since the 1989 workshop on knowledge discovery in databases, the field has seen sustained growth and interest and has attained significant maturity. The main objectives of this panel will be to reflect on the successes and failures in the field of data mining over the last eighteen years and to examine what insights we can take with us as we move forward.
Event summarization for system management
Authors: Wei Peng, Charles Perng, Tao Li, Haixun Wang
Venue: KDD
Year: 2007

In system management applications, an overwhelming amount of data are generated and collected in the form of temporal events. While mining temporal event data to discover interesting and frequent patterns has obtained rapidly increasing research efforts, users of the applications are overwhelmed by the mining results. The extracted patterns are generally of large volume and hard to interpret, they may be of no emphasis, intricate and meaningless to non-experts, even to domain experts. While traditional research efforts focus on finding interesting patterns, in this paper, we take a novel approach called event summarization towards the understanding of the seemingly chaotic temporal data. Event summarization aims at providing a concise interpretation of the seemingly chaotic data, so that domain experts may take actions upon the summarized models. Event summarization decomposes the temporal information into many independent subsets and finds well fitted models to describe each subset.
High-quantile modeling for customer wallet estimation and other applications
Authors: Claudia Perlich, Saharon Rosset, Richard D. Lawrence, Bianca Zadrozny
Venue: KDD
Year: 2007

In this paper we discuss the important practical problem of customer wallet estimation, i.e., estimation of potential spending by customers(rather than their expected spending). For this purpose we utilize quantile modeling, whose goal is to estimate a quantile of the discriminative conditional distribution of the response, rather than the mean, which is the implicit goal of most standard regression approaches. We argue that a notion of wallet can be captured through high quantile modeling (e.g, estimating the 90th percentile), and describe a wallet estimation implementation within IBM's Market Alignment Program (MAP). We also discuss the wide range of domains where high-quantile modeling can be practically important: estimating opportunities in sales and marketing domains, defining 'surprising' patterns for outlier and fraud detection and more. We survey some existing approaches for quantile modeling, and propose adaptations of nearest-neighbor and regression-tree approaches to quantile modeling. We demonstrate the various models' performance in high quantile estimation in several domains, including our motivating problem of estimating the 'realistic' IT wallets of IBM customers.
Active exploration for learning rankings from clickthrough data
Authors: Filip Radlinski, Thorsten Joachims
Venue: KDD
Year: 2007

We address the task of learning rankings of documents from search enginelogs of user behavior. Previous work on this problem has relied onpassively collected clickthrough data. In contrast, we show that anactive exploration strategy can provide data that leads to much fasterlearning. Specifically, we develop a Bayesian approach for selectingrankings to present users so that interactions result in more informativetraining data. Our results using the TREC-10 Web corpus, as well assynthetic data, demonstrate that a directed exploration strategy quicklyleads to users being presented improved rankings in an online learningsetting. We find that active exploration substantially outperformspassive observation and random exploration.
LungCAD: a clinically approved, machine learning system for lung cancer detection
Authors: R. Bharat Rao, Jinbo Bi, Glenn Fung, Marcos Salganicoff, Nancy Obuchowski, David P. Naidich
Venue: KDD
Year: 2007

We present LungCAD, a computer aided diagnosis (CAD) system that employs a classification algorithm for detecting solid pulmonary nodules from CT thorax studies. We briefly describe some of the machine learning techniques developed to overcome the real world challenges in this medical domain. The most significant hurdle in transitioning from a machine learning research prototype that performs well on an in-house dataset into a clinically deployable system, is the requirement that the CAD system be tested in a clinical trial. We describe the clinical trial in which LungCAD was tested: a large scale multi-reader, multi-case (MRMC) retrospective observational study to evaluate the effect of CAD in clinical practice for detecting solid pulmonary nodules from CT thorax studies. The clinical trial demonstrates that every radiologist that participated in the trial had a significantly greater accuracy with LungCAD, both for detecting nodules and identifying potentially actionable nodules; this, along with other findings from the trial, has resulted in FDA approval for LungCAD in late 2006.
Hierarchical mixture models: a probabilistic analysis
Authors: Mark Sandler
Venue: KDD
Year: 2007

Mixture models form one of the most widely used classes of generative models for describing structured and clustered data. In this paper we develop a new approach for the analysis of hierarchical mixture models. More specifically, using a text clustering problem as a motivation, we describe a natural generative process that creates a hierarchical mixture model for the data. In this process, an adversary starts with an arbitrary base distribution and then builds a topic hierarchy via some evolutionary process, where he controls the parameters of the process. We prove that under our assumptions, given a subset of topics that represent generalizations of one another (such as baseball → sports → base), for any document which was produced via some topic in this hierarchy, we can efficiently determine the most specialized topic in this subset, it still belongs to. The quality of the classification is independent of the total number of topics in the hierarchy and our algorithm does not need to know the total number of topics in advance. Our approach also yields an algorithm for clustering and unsupervised topical tree reconstruction. We validate our model by showing that properties predicted by our theoretical results carry over to real data. We then apply our clustering algorithm to two different datasets: (i) "20 newsgroups"[19] and (ii) a snapshot of abstracts of arXiv {2} (15 categories, ~240,000 abstracts). In both cases our algorithm performs extremely well.
Knowledge discovery of multiple-topic document using parametric mixture model with dirichlet prior
Authors: Issei Sato, Hiroshi Nakagawa
Venue: KDD
Year: 2007

Documents, such as those seen on Wikipedia and Folksonomy, have tended to be assigned with multiple topics as a meta-data.Therefore, it is more and more important to analyze a relationship between a document and topics assigned to the document. In this paper, we proposed a novel probabilistic generative model of documents with multiple topics as a meta-data. By focusing on modeling the generation process of a document with multiple topics, we can extract specific properties of documents with multiple topics.Proposed model is an expansion of an existing probabilistic generative model: Parametric Mixture Model (PMM). PMM models documents with multiple topics by mixing model parameters of each single topic. Since, however, PMM assigns the same mixture ratio to each single topic, PMM cannot take into account the bias of each topic within a document. To deal with this problem, we propose a model that considers Dirichlet distribution as a prior distribution of the mixture ratio.We adopt Variational Bayes Method to infer the bias of each topic within a document. We evaluate the proposed model and PMM using MEDLINE corpus.The results of F-measure, Precision and Recall show that the proposed model is more effective than PMM on multiple-topic classification. Moreover, we indicate the potential of the proposed model that extracts topics and document-specific keywords using information about the assigned topics.
Information genealogy: uncovering the flow of ideas in non-hyperlinked document databases
Authors: Benyah Shaparenko, Thorsten Joachims
Venue: KDD
Year: 2007

We now have incrementally-grown databases of text documents ranging back for over a decade in areas ranging from personal email, to news-articles and conference proceedings. While accessing individual documents is easy, methods for overviewing and understanding these collections as a whole are lacking in number and in scope. In this paper, we address one such global analysis task, namely the problem of automatically uncovering how ideas spread through the collection over time. We refer to this problem as Information Genealogy. In contrast to bibliometric methods that are limited to collections with explicit citation structure, we investigate content-based methods requiring only the text and timestamps of the documents. In particular, we propose a language-modeling approach and a likelihood ratio test to detect influence between documents in a statistically well-founded way. Furthermore, we show how this method can be used to infer citation graphs and to identify the most influential documents in the collection. Experiments on the NIPS conference proceedings and the Physics ArXiv show that our method is more effective than methods based on document similarity.
A concept-based model for enhancing text categorization
Authors: Shady Shehata, Fakhri Karray, Mohamed Kamel
Venue: KDD
Year: 2007

Most of text categorization techniques are based on word and/or phrase analysis of the text. Statistical analysis of a term frequency captures the importance of the term within a document only. However, two terms can have the same frequency in their documents, but one term contributes moreto the meaning of its sentences than the other term. Thus, the underlying model should indicate terms that capture these mantics of text. In this case, the model can capture terms that present the concepts of the sentence, which leads todiscover the topic of the document. A new concept-based model that analyzes terms on the sentence and document levels rather than the traditional analysis of document only is introduced. The concept-based model can effectively discriminate between non-important terms with respect to sentence semantics and terms which hold the concepts that represent the sentence meaning. The proposed model consists of concept-based statistical analyzer, conceptual ontological graph representation,and concept extractor. The term which contributes to the sentence semantics is assigned two different weights by the concept-based statistical analyzer and the conceptual ontological graph representation. These two weights are combined into a new weight. The concepts that have maximum combined weights are selected by the concept extractor. A set of experiments using the proposed concept-basedmodel on different datasets in text categorization is conducted. The experiments demonstrate the comparison between traditional weighting and the concept-based weighting obtained by the combined approach of the concept-based statistical analyzer and the conceptual ontological graph. The evaluation of results is relied on two quality measures, the Macro-averaged F1 and the Error rate. These quality measures are improved when the newly developedconcept-based model is used to enhance the quality of thetext categorization.
Partial example acquisition in cost-sensitive learning
Authors: Victor S. Sheng, Charles X. Ling
Venue: KDD
Year: 2007

It is often expensive to acquire data in real-world data mining applications. Most previous data mining and machine learning research, however, assumes that a fixed set of training examples is given. In this paper, we propose an online cost-sensitive framework that allows a learner to dynamically acquire examples as it learns, and to decide the ideal number of examples needed to minimize the total cost. We also propose a new strategy for Partial Example Acquisition (PAS), in which the learner can acquire examples with a subset of attribute values to reduce the data acquisition cost. Experiments on UCI datasets show that the new PAS strategy is an effective method in reducing the total cost for data acquisition.
A spectral clustering approach to optimally combining numericalvectors with a modular network
Authors: Motoki Shiga, Ichigaku Takigawa, Hiroshi Mamitsuka
Venue: KDD
Year: 2007

We address the issue of clustering numerical vectors with a network. The problem setting is basically equivalent to constrained clustering by Wagstaff and Cardie and semi-supervised clustering by Basu et al., but our focus is more on the optimal combination of two heterogeneous data sources. An application of this setting is web pages which can be numerically vectorized by their contents, e.g. term frequencies, and which are hyperlinked to each other, showing a network. Another typical application is genes whose behavior can be numerically measured and a gene network can be given from another data source.We first define a new graph clustering measure which we call normalized network modularity, by balancing the cluster size of the original modularity. We then propose a new clustering method which integrates the cost of clustering numerical vectors with the cost of maximizing the normalized network modularity into a spectral relaxation problem. Our learning algorithm is based on spectral clustering which makes our issue an eigenvalue problem and uses k-means for final cluster assignments. A significant advantage of our method is that we can optimize the weight parameter for balancing the two costs from the given data by choosing the minimum total cost. We evaluated the performance of our proposed method using a variety of datasets including synthetic data as well as real-world data from molecular biology. Experimental results showed that our method is effective enough to have good results for clustering by numerical vectors and a network.