OpenRaiser/Intern-Atlas huggingface dataset:
Finding non-redundant, statistically significant regions in high dimensional data: a novel approach to projected and subspace clustering
Authors: Gabriela Moise, Jörg Sander
Venue: KDD
Year: 2008

Projected and subspace clustering algorithms search for clusters of points in subsets of attributes. Projected clustering computes several disjoint clusters, plus outliers, so that each cluster exists in its own subset of attributes. Subspace clustering enumerates clusters of points in all subsets of attributes, typically producing many overlapping clusters. One problem of existing approaches is that their objectives are stated in a way that is not independent of the particular algorithm proposed to detect such clusters. A second problem is the definition of cluster density based on user-defined parameters, which makes it hard to assess whether the reported clusters are an artifact of the algorithm or whether they actually stand out in the data in a statistical sense.
Morpheus: interactive exploration of subspace clustering
Authors: Emmanuel Müller, Ira Assent, Ralph Krieger, Timm Jansen, Thomas Seidl
Venue: KDD
Year: 2008

Data mining techniques extract interesting patterns out of large data resources. Meaningful visualization and interactive exploration of patterns are crucial for knowledge discovery. Visualization techniques exist for traditional clustering in low dimensional spaces. In high dimensional data, clusters typically only exist in subspace projections. This subspace clustering, however, lacks interactive visualization tools. Challenges arise from typically large result sets in different subspace projections that hinder comparability, visualization and understandability.
Classification with partial labels
Authors: Nam Nguyen, Rich Caruana
Venue: KDD
Year: 2008

In this paper, we address the problem of learning when some cases are fully labeled while other cases are only partially labeled, in the form of partial labels. Partial labels are represented as a set of possible labels for each training example, one of which is the correct label. We introduce a discriminative learning approach that incorporates partial label information into the conventional margin-based learning framework. The partial label learning problem is formulated as a convex quadratic optimization minimizing the L2-norm regularized empirical risk using hinge loss. We also present an efficient algorithm for classification in the presence of partial labels. Experiments with different data sets show that partial label information improves the performance of classification when there is traditional fully-labeled data, and also yields reasonable performance in the absence of any fully labeled data.
A software system for buzz-based recommendations
Authors: Hill Nguyen, Nish Parikh, Neel Sundaresan
Venue: KDD
Year: 2008

In this paper, we present an outline of a software system for buzz-based recommendations. This system is based on a large source of queries in an eCommerce application. The buzz events are detected based on query bursts linked to external entities like news and inventory information. A semantic neighborhood of the chosen buzz query is selected and appropriate recommendations are made on products that relate to this neighborhood. The system follows the paradigm of limited quantity merchandizing, in the sense that on a per-day basis the system shows recommendations around a single buzz query with the intent of increasing user curiosity and promoting user activity and stickiness. The system demonstrates the deployment of an interesting application based on KDD principles applied to a high volume industrial context.
Temporal pattern discovery for trends and transient effects: its application to patient records
Authors: G. Niklas Norén, Andrew Bate, Johan Hopstadius, Kristina Star, I. Ralph Edwards
Venue: KDD
Year: 2008

We introduce a novel pattern discovery methodology for event history data focusing explicitly on the detailed temporal relationship between pairs of events. At the core is a graphical statistical approach to summarising and visualising event history data, which contrasts the observed to the expected incidence of the event of interest before and after an index event. Thus, pattern discovery is not restricted to a specific time window of interest, but encompasses extended parts of the underlying event histories. In order to effectively screen large collections of event history data for interesting temporal relationships, we introduce a new measure of temporal association. The proposed measure contrasts the observed-to-expected ratio in a time period of interest to that in a pre-defined control period. An important feature of both the observed-to-expected graph itself and the measure of association, is a statistical shrinkage towards the null hypothesis of no association. This provides protection against spurious associations and is an extension of the statistical shrinkage successfully applied to large-scale screening for associations between events in cross-sectional data, such as large collections of adverse drug reaction reports. We demonstrate the usefulness of the proposed pattern discovery methodology by a set of examples from a collection of over two million patient records in the United Kingdom. The identified patterns include temporal relationships between drug prescription and medical events suggestive of persistent or transient risks of adverse events, as well as temporal relationships between prescriptions of different drugs.
Bypass rates: reducing query abandonment using negative inferences
Authors: Atish Das Sarma, Sreenivas Gollapudi, Samuel Ieong
Venue: KDD
Year: 2008

We introduce a new approach to analyzing click logs by examining both the documents that are clicked and those that are bypassed-documents returned higher in the ordering of the search results but skipped by the user. This approach complements the popular click-through rate analysis, and helps to draw negative inferences in the click logs. We formulate a natural objective that finds sets of results that are unlikely to be collectively bypassed by a typical user. This is closely related to the problem of reducing query abandonment. We analyze a greedy approach to optimizing this objective, and establish theoretical guarantees of its performance. We evaluate our approach on a large set of queries, and demonstrate that it compares favorably to the maximal marginal relevance approach on a number of metrics including mean average precision and mean reciprocal rank.
Knowledge discovery of semantic relationships between words using nonparametric bayesian graph model
Authors: Issei Sato, Minoru Yoshida, Hiroshi Nakagawa
Venue: KDD
Year: 2008

We developed a model based on nonparametric Bayesian modeling for automatic discovery of semantic relationships between words taken from a corpus. It is aimed at discovering semantic knowledge about words in particular domains, which has become increasingly important with the growing use of text mining, information retrieval, and speech recognition. The subject-predicate structure is taken as a syntactic structure with the noun as the subject and the verb as the predicate. This structure is regarded as a graph structure. The generation of this graph can be modeled using the hierarchical Dirichlet process and the Pitman-Yor process. The probabilistic generative model we developed for this graph structure consists of subject-predicate structures extracted from a corpus. Evaluation of this model by measuring the performance of graph clustering based on WordNet similarities demonstrated that it outperforms other baseline models.
Efficient computation of personal aggregate queries on blogs
Authors: Ka Cheung Sia, Junghoo Cho, Yun Chi, Belle L. Tseng
Venue: KDD
Year: 2008

There is an exploding amount of user-generated content on theWeb due to the emergence of "Web 2.0" services, such as Blogger,MySpace, Flickr, and del.icio.us. The participation of a large number of users in sharing their opinion on the Web has inspired researchers to build an effective "information filter" by aggregating these independent opinions. However, given the diverse groups of users on the Web nowadays, the global aggregation of the information may not be of much interest to different groups of users. In this paper, we explore the possibility of computing personalized aggregation over the opinions expressed on the Web based on a user's indication of trust over the information sources. The hope is that by employing such "personalized" aggregation, we can make the recommendation more likely to be interesting to the users. We address the challenging scalability issues by proposing an efficient method, that utilizes two core techniques: Non-Negative Matrix Factorization and Threshold Algorithm, to compute personalized aggregations when there are potentially millions of users and millions of sources within a system. We show that, through experiments on real-life dataset, our personalized aggregation approach indeed makes a significant difference in the items that are recommended and it reduces the query computational cost significantly, often more than 75%, while the result of personalized aggregation is kept accurate enough.
Semi-supervised approach to rapid and reliable labeling of large data sets
Authors: György J. Simon, Vipin Kumar, Zhi-Li Zhang
Venue: KDD
Year: 2008

In this paper, we propose a method, where the labeling of the data set is carried out in a semi-supervised manner with user-specified guarantees about the quality of the labeling. In our scheme, we assume that for each class, we have some heuristics available, each of which can identify instances of one particular class. The heuristics are assumed to have reasonable performance but they do not need to cover all instances of the class nor do they need to be perfectly reliable. We further assume that we have an infallible expert, who is willing to manually label a few instances. The aim of the algorithm is to exploit the cluster structure of the problem, the predictions by the imperfect heuristics and the limited perfect labels provided by the expert to classify (label) the instances of the data set with guaranteed precision (specificed by the user) with regards to each class. The specified precision is not always attainable, so the algorithm is allowed to classify some instances as dontknow. The algorithm is evaluated by the number of instances labeled by the expert, the number of dontknow instances (global coverage) and the achieved quality of the labeling. On the KDD Cup Network Intrusion data set containing 500,000 instances, we managed to label 96.6% of the instances while guaranteeing a nominal precision of 90% (with 95% confidence) by having the expert label 630 instances; and by having the expert label 1200 instances, we managed to guarantee 95% nominal precision while labeling 96.4% of the data. We also provide a case study of applying our scheme to label the network traffic collected at a large campus network.
Identifying domain expertise of developers from source code
Authors: Renuka Sindhgatta
Venue: KDD
Year: 2008

We are interested in identifying the domain expertise of developers of a software system. A developer gains expertise on the code base as well as the domain of the software system he/she develops. This information forms a useful input in allocating software implementation tasks to developers. Domain concepts represented by the system are discovered by taking into account the linguistic information available in the source code. The vocabulary contained in source code as identifiers such as class, method, variable names and comments are extracted. Concepts present in the code base are identified and grouped based on a well known text processing hypothesis - words are similar to the extent to which they share similar words. The developer's association with the source code and the concepts it represents is arrived at using the version repository information. In this line, the analysis first derives documents from source code by discarding all the programming language constructs. KMeans clustering is further used to cluster documents and extract closely related concepts. The key concepts present in the documents authored by the developer determine his/her domain expertise. To validate our approach we apply it on large software systems, two of which are presented in detail in this paper.
A bayesian mixture model with linear regression mixing proportions
Authors: Xiuyao Song, Chris Jermaine, Sanjay Ranka, John Gums
Venue: KDD
Year: 2008

Classic mixture models assume that the prevalence of the various mixture components is fixed and does not vary over time. This presents problems for applications where the goal is to learn how complex data distributions evolve. We develop models and Bayesian learning algorithms for inferring the temporal trends of the components in a mixture model as a function of time. We show the utility of our models by applying them to the real-life problem of tracking changes in the rates of antibiotic resistance in Escherichia coli and Staphylococcus aureus. The results show that our methods can derive meaningful temporal antibiotic resistance patterns.
Hypergraph spectral learning for multi-label classification
Authors: Liang Sun, Shuiwang Ji, Jieping Ye
Venue: KDD
Year: 2008

A hypergraph is a generalization of the traditional graph in which the edges are arbitrary non-empty subsets of the vertex set. It has been applied successfully to capture high-order relations in various domains. In this paper, we propose a hypergraph spectral learning formulation for multi-label classification, where a hypergraph is constructed to exploit the correlation information among different labels. We show that the proposed formulation leads to an eigenvalue problem, which may be computationally expensive especially for large-scale problems. To reduce the computational cost, we propose an approximate formulation, which is shown to be equivalent to a least squares problem under a mild condition. Based on the approximate formulation, efficient algorithms for solving least squares problems can be applied to scale the formulation to very large data sets. In addition, existing regularization techniques for least squares can be incorporated into the model for improved generalization performance. We have conducted experiments using large-scale benchmark data sets, and experimental results show that the proposed hypergraph spectral learning formulation is effective in capturing the high-order relations in multi-label problems. Results also indicate that the approximate formulation is much more efficient than the original one, while keeping competitive classification performance.
Building semantic kernels for text classification using wikipedia
Authors: Pu Wang, Carlotta Domeniconi
Venue: KDD
Year: 2008

Document classification presents difficult challenges due to the sparsity and the high dimensionality of text data, and to the complex semantics of the natural language. The traditional document representation is a word-based vector (Bag of Words, or BOW), where each dimension is associated with a term of the dictionary containing all the words that appear in the corpus. Although simple and commonly used, this representation has several limitations. It is essential to embed semantic information and conceptual patterns in order to enhance the prediction capabilities of classification algorithms. In this paper, we overcome the shortages of the BOW approach by embedding background knowledge derived from Wikipedia into a semantic kernel, which is then used to enrich the representation of documents. Our empirical evaluation with real data sets demonstrates that our approach successfully achieves improved classification accuracy with respect to the BOW technique, and to other recently developed methods.
A unified approach for schema matching, coreference and canonicalization
Authors: Michael L. Wick, Khashayar Rohanimanesh, Karl Schultz, Andrew McCallum
Venue: KDD
Year: 2008

The automatic consolidation of database records from many heterogeneous sources into a single repository requires solving several information integration tasks. Although tasks such as coreference, schema matching, and canonicalization are closely related, they are most commonly studied in isolation. Systems that do tackle multiple integration problems traditionally solve each independently, allowing errors to propagate from one task to another. In this paper, we describe a discriminatively-trained model that reasons about schema matching, coreference, and canonicalization jointly. We evaluate our model on a real-world data set of people and demonstrate that simultaneously solving these tasks reduces errors over a cascaded or isolated approach. Our experiments show that a joint model is able to improve substantially over systems that either solve each task in isolation or with the conventional cascade. We demonstrate nearly a 50% error reduction for coreference and a 40% error reduction for schema matching.
Information extraction from Wikipedia: moving down the long tail
Authors: Fei Wu, Raphael Hoffmann, Daniel S. Weld
Venue: KDD
Year: 2008

Not only is Wikipedia a comprehensive source of quality information, it has several kinds of internal structure (e.g., relational summaries known as infoboxes), which enable self-supervised information extraction. While previous efforts at extraction from Wikipedia achieve high precision and recall on well-populated classes of articles, they fail in a larger number of cases, largely because incomplete articles and infrequent use of infoboxes lead to insufficient training data. This paper presents three novel techniques for increasing recall from Wikipedia's long tail of sparse classes: (1) shrinkage over an automatically-learned subsumption taxonomy, (2) a retraining technique for improving the training data, and (3) supplementing results by extracting from the broader Web. Our experiments compare design variations and show that, used in concert, these techniques increase recall by a factor of 1.76 to 8.71 while maintaining or increasing precision.
Experimental comparison of scalable online ad serving
Authors: Gang Wu, Brendan Kitts
Venue: KDD
Year: 2008

Online Ad Servers attempt to find best ads to serve for a given triggering user event. The performance of ads may be measured in several ways. We suggest a formulation in which the ad network tries to maximize revenue subject to relevance constraints. We describe several algorithms for ad selection and review their complexity. We tested these algorithms using Microsoft ad network from October 1 2006 to February 8 2007. Over 3 billion impressions, 8 million combinations of triggers with ads, and a number of algorithms were tested over this period. We discover curious differences between ad-servers aimed at revenue versus clickthrough rate.
Asymmetric support vector machines: low false-positive learning under the user tolerance
Authors: Shan-Hung Wu, Keng-Pei Lin, Chung-Min Chen, Ming-Syan Chen
Venue: KDD
Year: 2008

Many practical applications of classification require the classifier to produce a very low false-positive rate. Although the Support Vector Machine (SVM) has been widely applied to these applications due to its superiority in handling high dimensional data, there are relatively little effort other than setting a threshold or changing the costs of slacks to ensure the low false-positive rate. In this paper, we propose the notion of Asymmetric Support VectorMachine (ASVM) that takes into account the false-positives and the user tolerance in its objective. Such a new objective formulation allows us to raise the confidence in predicting the positives, and therefore obtain a lower chance of false-positives. We study the effects of the parameters in ASVM objective and address some implementation issues related to the Sequential Minimal Optimization (SMO) to cope with large-scale data. An extensive simulation is conducted and shows that ASVM is able to yield either noticeable improvement in performance or reduction in training time as compared to the previous arts.
SAIL: summation-based incremental learning for information-theoretic clustering
Authors: Junjie Wu, Hui Xiong, Jian Chen
Venue: KDD
Year: 2008

Information-theoretic clustering aims to exploit information theoretic measures as the clustering criteria. A common practice on this topic is so-called INFO-K-means, which performs K-means clustering with the KL-divergence as the proximity function. While expert efforts on INFO-K-means have shown promising results, a remaining challenge is to deal with high-dimensional sparse data. Indeed, it is possible that the centroids contain many zero-value features for high-dimensional sparse data. This leads to infinite KL-divergence values, which create a dilemma in assigning objects to the centroids during the iteration process of K-means. To meet this dilemma, in this paper, we propose a Summation-based Incremental Learning (SAIL) method for INFO-K-means clustering. Specifically, by using an equivalent objective function, SAIL replaces the computation of the KL-divergence by the computation of the Shannon entropy. This can avoid the zero-value dilemma caused by the use of the KL-divergence. Our experimental results on various real-world document data sets have shown that, with SAIL as a booster, the clustering performance of K-means can be significantly improved. Also, SAIL leads to quick convergence and a robust clustering performance on high-dimensional sparse data.
Succinct summarization of transactional databases: an overlapped hyperrectangle scheme
Authors: Yang Xiang, Ruoming Jin, David Fuhry, Feodor F. Dragan
Venue: KDD
Year: 2008

Transactional data are ubiquitous. Several methods, including frequent itemsets mining and co-clustering, have been proposed to analyze transactional databases. In this work, we propose a new research problem to succinctly summarize transactional databases. Solving this problem requires linking the high level structure of the database to a potentially huge number of frequent itemsets. We formulate this problem as a set covering problem using overlapped hyperrectangles; we then prove that this problem and its several variations are NP-hard. We develop an approximation algorithm HYPER which can achieve a ln(k) + 1 approximation ratio in polynomial time. We propose a pruning strategy that can significantly speed up the processing of our algorithm. Additionally, we propose an efficient algorithm to further summarize the set of hyperrectangles by allowing false positive conditions. A detailed study using both real and synthetic datasets shows the effectiveness and efficiency of our approaches in summarizing transactional databases.
A visual-analytic toolkit for dynamic interaction graphs
Authors: Xintian Yang, Sitaram Asur, Srinivasan Parthasarathy, Sameep Mehta
Venue: KDD
Year: 2008

In this article we describe a visual-analytic tool for the interrogation of evolving interaction network data such as those found in social, bibliometric, WWW and biological applications. The tool we have developed incorporates common visualization paradigms such as zooming, coarsening and filtering while naturally integrating information extracted by a previously described event-driven framework for characterizing the evolution of such networks. The visual front-end provides features that are specifically useful in the analysis of interaction networks, capturing the dynamic nature of both individual entities as well as interactions among them. The tool provides the user with the option of selecting multiple views, designed to capture different aspects of the evolving graph from the perspective of a node, a community or a subset of nodes of interest. Standard visual templates and cues are used to highlight critical changes that have occurred during the evolution of the network. A key challenge we address in this work is that of scalability - handling large graphs both in terms of the efficiency of the back-end, and in terms of the efficiency of the visual layout and rendering. Two case studies based on bibliometric and Wikipedia data are presented to demonstrate the utility of the toolkit for visual knowledge discovery.