OpenRaiser/Intern-Atlas huggingface dataset:
Computer aided detection via asymmetric cascade of sparse hyperplane classifiers
Authors: Jinbo Bi, Senthil Periaswamy, Kazunori Okada, Toshiro Kubota, Glenn Fung, Marcos Salganicoff, R. Bharat Rao
Venue: KDD
Year: 2006

This paper describes a novel classification method for computer aided detection (CAD) that identifies structures of interest from medical images. CAD problems are challenging largely due to the following three characteristics. Typical CAD training data sets are large and extremely unbalanced between positive and negative classes. When searching for descriptive features, researchers often deploy a large set of experimental features, which consequently introduces irrelevant and redundant features. Finally, a CAD system has to satisfy stringent real-time requirements.This work is distinguished by three key contributions. The first is a cascade classification approach which is able to tackle all the above difficulties in a unified framework by employing an asymmetric cascade of sparse classifiers each trained to achieve high detection sensitivity and satisfactory false positive rates. The second is the incorporation of feature computational costs in a linear program formulation that allows the feature selection process to take into account different evaluation costs of various features. The third is a boosting algorithm derived from column generation optimization to effectively solve the proposed cascade linear programs.We apply the proposed approach to the problem of detecting lung nodules from helical multi-slice CT images. Our approach demonstrates superior performance in comparison against support vector machines, linear discriminant analysis and cascade AdaBoost. Especially, the resulting detection system is significantly sped up with our approach.
Robust information-theoretic clustering
Authors: Christian Böhm, Christos Faloutsos, Jia-Yu Pan, Claudia Plant
Venue: KDD
Year: 2006

How do we find a natural clustering of a real world point set, which contains an unknown number of clusters with different shapes, and which may be contaminated by noise? Most clustering algorithms were designed with certain assumptions (Gaussianity), they often require the user to give input parameters, and they are sensitive to noise. In this paper, we propose a robust framework for determining a natural clustering of a given data set, based on the minimum description length (MDL) principle. The proposed framework, Robust Information-theoretic Clustering (RIC), is orthogonal to any known clustering algorithm: given a preliminary clustering, RIC purifies these clusters from noise, and adjusts the clusterings such that it simultaneously determines the most natural amount and shape (subspace) of the clusters. Our RIC method can be combined with any clustering technique ranging from K-means and K-medoids to advanced methods such as spectral clustering. In fact, RIC is even able to purify and improve an initial coarse clustering, even if we start with very simple methods such as grid-based space partitioning. Moreover, RIC scales well with the data set size. Extensive experiments on synthetic and real world data sets validate the proposed RIC framework.
Efficient anonymity-preserving data collection
Authors: Justin Brickell, Vitaly Shmatikov
Venue: KDD
Year: 2006

The output of a data mining algorithm is only as good as its inputs, and individuals are often unwilling to provide accurate data about sensitive topics such as medical history and personal finance. Individuals maybe willing to share their data, but only if they are assured that it will be used in an aggregate study and that it cannot be linked back to them. Protocols for anonymity-preserving data collection provide this assurance, in the absence of trusted parties, by allowing a set of mutually distrustful respondents to anonymously contribute data to an untrusted data miner.To effectively provide anonymity, a data collection protocol must be collusion resistant, which means that even if all dishonest respondents collude with a dishonest data miner in an attempt to learn the associations between honest respondents and their responses, they will be unable to do so. To achieve collusion resistance, previously proposed protocols for anonymity-preserving data collection have quadratically many communication rounds in the number of respondents, and employ (sometimes incorrectly) complicated cryptographic techniques such as zero-knowledge proofs.We describe a new protocol for anonymity-preserving, collusion resistant data collection. Our protocol has linearly many communication rounds, and achieves collusion resistance without relying on zero-knowledge proofs. This makes it especially suitable for data mining scenarios with a large number of respondents.
Model compression
Authors: Cristian Bucila, Rich Caruana, Alexandru Niculescu-Mizil
Venue: KDD
Year: 2006

Often the best performing supervised learning models are ensembles of hundreds or thousands of base-level classifiers. Unfortunately, the space required to store this many classifiers, and the time required to execute them at run-time, prohibits their use in applications where test sets are large (e.g. Google), where storage space is at a premium (e.g. PDAs), and where computational power is limited (e.g. hea-ring aids). We present a method for "compressing" large, complex ensembles into smaller, faster models, usually without significant loss in performance.
Out-of-core frequent pattern mining on a commodity PC
Authors: Gregory Buehrer, Srinivasan Parthasarathy, Amol Ghoting
Venue: KDD
Year: 2006

In this work we focus on the problem of frequent itemset mining on large, out-of-core data sets. After presenting a characterization of existing out-of-core frequent itemset mining algorithms and their drawbacks, we introduce our efficient, highly scalable solution. Presented in the context of the FPGrowth algorithm, our technique involves several novel I/O-conscious optimizations, such as approximate hash-based sorting and blocking, and leverages recent architectural advancements in commodity computers, such as 64-bit processing. We evaluate the proposed optimizations on truly large data sets,up to 75GB, and show they yield greater than a 400-fold execution time improvement. Finally, we discuss the impact of this research in the context of other pattern mining challenges, such as sequence mining and graph mining.
Onboard classifiers for science event detection on a remote sensing spacecraft
Authors: Rebecca Castaño, Dominic Mazzoni, Nghia Tang, Ronald Greeley, Thomas Doggett, Benjamin Cichy, Steve A. Chien, Ashley Davies
Venue: KDD
Year: 2006

Typically, data collected by a spacecraft is downlinked to Earth and pre-processed before any analysis is performed. We have developed classifiers that can be used onboard a spacecraft to identify high priority data for downlink to Earth, providing a method for maximizing the use of a potentially bandwidth limited downlink channel. Onboard analysis can also enable rapid reaction to dynamic events, such as flooding, volcanic eruptions or sea ice break-up. Four classifiers were developed to identify cryosphere events using hyperspectral images. These classifiers include a manually constructed classifier, a Support Vector Machine (SVM), a Decision Tree and a classifier derived by searching over combinations of thresholded band ratios. Each of the classifiers was designed to run in the computationally constrained operating environment of the spacecraft. A set of scenes was hand-labeled to provide training and testing data. Performance results on the test data indicate that the SVM and manual classifiers outperformed the Decision Tree and band-ratio classifiers with the SVM yielding slightly better classifications than the manual classifier. The manual and SVM classifiers have been uploaded to the EO-1 spacecraft and have been running onboard the spacecraft for over a year. Results of the onboard analysis are used by the Autonomous Sciencecraft Experiment (ASE) of NASA’s New Millennium Program onboard EO-1 to automatically target the spacecraft to collect follow-on imagery. The software demonstrates the potential for future deep space missions to use onboard decision making to capture short-lived science events.
Data mining challenges in the automotive domain
Authors: Michael Cavaretta
Venue: KDD
Year: 2006

Automotive companies, such as Ford Motor Company, have no shortage of large databases with abundant opportunities for cost reduction and revenue enhancement. The Data Mining Group at Ford has worked in the areas of Quality, Customer Satisfaction and Warranty Analytics for close to ten years. In this time, we have developed a number of methods for building systems to help the business. One area of particular success has been in warranty analysis. While traditional hazard analysis has been applied at Ford for a number of years, we have used techniques from other industries (e.g. retail), as well as text mining to view warranty analytics in a new way. However, our success has been tempered by serious challenges particularly in the areas of data understanding, computing meaningful aggregations and implementation. Case studies from the automobile industry (warranty, quality, forecasting, etc.) as well as from other industries will be used.
Evolutionary clustering
Authors: Deepayan Chakrabarti, Ravi Kumar, Andrew Tomkins
Venue: KDD
Year: 2006

We consider the problem of clustering data over time. An evolutionary clustering should simultaneously optimize two potentially conflicting criteria: first, the clustering at any point in time should remain faithful to the current data as much as possible; and second, the clustering should not shift dramatically from one timestep to the next. We present a generic framework for this problem, and discuss evolutionary versions of two widely-used clustering algorithms within this framework: k-means and agglomerative hierarchical clustering. We extensively evaluate these algorithms on real data sets and show that our algorithms can simultaneously attain both high accuracy in capturing today's data, and high fidelity in reflecting yesterday's clustering.
NeMoFinder: dissecting genome-wide protein-protein interactions with meso-scale network motifs
Authors: Jin Chen, Wynne Hsu, Mong-Li Lee, See-Kiong Ng
Venue: KDD
Year: 2006

Recent works in network analysis have revealed the existence of network motifs in biological networks such as the protein-protein interaction (PPI) networks. However, existing motif mining algorithms are not sufficiently scalable to find meso-scale network motifs. Also, there has been little or no work to systematically exploit the extracted network motifs for dissecting the vast interactomes.We describe an efficient network motif discovery algorithm, NeMoFinder, that can mine meso-scale network motifs that are repeated and unique in large PPI networks. Using NeMoFinder, we successfully discovered, for the first time, up to size-12 network motifs in a large whole-genome S. cerevisiae (Yeast) PPI network. We also show that such network motifs can be systematically exploited for indexing the reliability of PPI data that were generated via highly erroneous high-throughput experimental methods.
Estimating the global pagerank of web communities
Authors: Jason V. Davis, Inderjit S. Dhillon
Venue: KDD
Year: 2006

Localized search engines are small-scale systems that index a particular community on the web. They offer several benefits over their large-scale counterparts in that they are relatively inexpensive to build, and can provide more precise and complete search capability over their relevant domains. One disadvantage such systems have over large-scale search engines is the lack of global PageRank values. Such information is needed to assess the value of pages in the localized search domain within the context of the web as a whole. In this paper, we present well-motivated algorithms to estimate the global PageRank values of a local domain. The algorithms are all highly scalable in that, given a local domain of size n, they use O(n) resources that include computation time, bandwidth, and storage. We test our methods across a variety of localized domains, including site-specific domains and topic-specific domains. We demonstrate that by crawling as few as n or 2n additional pages, our methods can give excellent global PageRank estimates.
A component-based framework for knowledge discovery in bioinformatics
Authors: Julien Etienne, Bernd Wachmann, Lei Zhang
Venue: KDD
Year: 2006

Motivation: In the field of bioinformatics there is an emerging need to integrate all knowledge discovery steps into a standardized modular framework. Indeed, component-based development can significantly enhance reusability and productivity for short timeline projects with a small team. We present Interactive Knowledge Discovery and Data mining (iKDD), an application framework written in Java that was specifically designed for these purposes.Results: iKDD consists of a component-based architecture and a web-based tool for pre-clinical research and prototype development. The platform provides an intuitive and consistent interface to create and maintain components, e.g., data structures, algorithms and utilities to load, save and visualize data and pipelines. The rich-featured tool supplies database connectivity, workflow processing and rapid prototype building. The architecture was carefully designed using an object-oriented approach that respects crucial goals: usability, openness, robustness and functionality, especially in the abstraction and description of the components, which distinguishes it from other packages. iKDD is well-suited to serve as a public repository of components, to run scientific experiments with a high-level of reproducibility, and also to rapidly build prototypes. This paper describes the general architecture, and demonstrates through examples the ease by which a complex scenario implementation can be facilitated with iKDD.
A general framework for accurate and fast regression by data summarization in random decision trees
Authors: Wei Fan, Joe McCloskey, Philip S. Yu
Venue: KDD
Year: 2006

Predicting the values of continuous variable as a function of several independent variables is one of the most important problems for data mining. A very large number of regression methods, both parametric and nonparametric, have been proposed in the past. However, since the list is quite extensive and many of these models make rather explicit, strong yet different assumptions about the type of applicable problems and involve a lot of parameters and options, choosing the appropriate regression methodology and then specifying the parameter values is a none-trivial, sometimes frustrating, task for data mining practitioners. Choosing the inappropriate methodology can have rather disappointing results. This issue is against the general utility of data mining software. For example,linear regression methods are straightforward and well-understood. However, since the linear assumption is very strong, its performance is compromised for complicated non-linear problems. Kernel-based methods perform quite well if the kernel functions are selected correctly. In this paper, we propose a straightforward approach based on summarizing the training data using an ensemble of random decisions trees. It requires very little knowledge from the user, yet is applicable to every type of regression problem that we are currently aware of. We have experimented on a wide range of problems including those that parametric methods performwell, a large selection of benchmark datasets for nonparametric regression, as well as highly non-linear stochastic problems. Our results are either significantly better than or identical to many approaches that are known to perform well on these problems.
Quantifying trends accurately despite classifier error and class imbalance
Authors: George Forman
Venue: KDD
Year: 2006

This paper promotes a new task for supervised machine learning research: quantification—the pursuit of learning methods for accurately estimating the class distribution of a test set, with no concern for predictions on individual cases. A variant for cost quantification addresses the need to total up costs according to categories predicted by imperfect classifiers. These tasks cover a large and important family of applications that measure trends over time. The paper establishes a research methodology, and uses it to evaluate several proposed methods that involve selecting the classification threshold in a way that would spoil the accuracy of individual classifications. In empirical tests, Median Sweep methods show outstanding ability to estimate the class distribution, despite wide disparity in testing and training conditions. The paper addresses shifting class priors and costs, but not concept drift in general.
Pragmatic text mining: minimizing human effort to quantify many issues in call logs
Authors: George Forman, Evan Kirshenbaum, Jaap Suermondt
Venue: KDD
Year: 2006

We discuss our experiences in analyzing customer-support issues from the unstructured free-text fields of technical-support call logs. The identification of frequent issues and their accurate quantification is essential in order to track aggregate costs broken down by issue type, to appropriately target engineering resources, and to provide the best diagnosis, support and documentation for most common issues. We present a new set of techniques for doing this efficiently on an industrial scale, without requiring manual coding of calls in the call center. Our approach involves (1) a new text clustering method to identify common and emerging issues; (2) a method to rapidly train large numbers of categorizers in a practical, interactive manner; and (3) a method to accurately quantify categories, even in the face of inaccurate classifications and training sets that necessarily cannot match the class distribution of each new month's data. We present our methodology and a tool we developed and deployed that uses these methods for tracking ongoing support issues and discovering emerging issues at HP.
Mining relational data through correlation-based multiple view validation
Authors: Hongyu Guo, Herna L. Viktor
Venue: KDD
Year: 2006

Commercial relational databases currently store vast amounts of real-world data. The data within these relational repositories are represented by multiple relations, which are inter-connected by means of foreign key joins. The mining of such interrelated data poses a major challenge to the data mining community. Unfortunately, traditional data mining algorithms usually only explore one relation, the so-called target relation, thus excluding crucial knowledge embedded in the related so-called background relations. In this paper, we propose a novel approach for classifying relational such domains. This strategy employs multiple views to capture crucial information not only from the target relation, but also from related relations. This information is integrated into the relational mining process. The framework presented here, firstly, explore the relational domain to partition its features space into multiple subsets. Subsequently, these subsets are used to construct multiple uncorrelated views, based on a novel correlation-based view validation method, against the target concept. Finally, the knowledge possessed by multiple views are incorporated into a meta-learning mechanism to augment one another. Based on this framework, a wide range of conventional data mining methods can be applied to mine relational databases. Our experiments on benchmark real-world data sets show that the proposed method achieves promising results both in terms of overall accuracy obtained and run time, when compared with two other relational data mining approaches.
A new efficient probabilistic model for mining labeled ordered trees
Authors: Kosuke Hashimoto, Kiyoko F. Aoki-Kinoshita, Nobuhisa Ueda, Minoru Kanehisa, Hiroshi Mamitsuka
Venue: KDD
Year: 2006

Mining frequent patterns is a general and important issue in data mining. Complex and unstructured (or semi-structured) datasets have appeared in major data mining applications, including text mining, web mining and bioinformatics. Mining patterns from these datasets is the focus of many of the current data mining approaches. We focus on labeled ordered trees, typical datasets of semi-structured data in data mining, and propose a new probabilistic model and its efficient learning scheme for mining labeled ordered trees. The proposed approach significantly improves the time and space complexity of an existing probabilistic modeling for labeled ordered trees, while maintaining its expressive power. We evaluated the performance of the proposed model, comparing it with that of the existing model, using synthetic as well as real datasets from the field of glycobiology. Experimental results showed that the proposed model drastically reduced the computation time of the competing model, keeping the predictive power and avoiding overfitting to the training data. Finally, we assessed our results using the proposed model on real data from a variety of biological viewpoints, verifying known facts in glycobiology.
Learning the unified kernel machines for classification
Authors: Steven C. H. Hoi, Michael R. Lyu, Edward Y. Chang
Venue: KDD
Year: 2006

Kernel machines have been shown as the state-of-the-art learning techniques for classification. In this paper, we propose a novel general framework of learning the Unified Kernel Machines (UKM) from both labeled and unlabeled data. Our proposed framework integrates supervised learning, semi-supervised kernel learning, and active learning in a unified solution. In the suggested framework, we particularly focus our attention on designing a new semi-supervised kernel learning method, i.e., Spectral Kernel Learning (SKL), which is built on the principles of kernel target alignment and unsupervised kernel design. Our algorithm is related to an equivalent quadratic programming problem that can be efficiently solved. Empirical results have shown that our method is more effective and robust to learn the semi-supervised kernels than traditional approaches. Based on the framework, we present a specific paradigm of unified kernel machines with respect to Kernel Logistic Regresions (KLR), i.e., Unified Kernel Logistic Regression (UKLR). We evaluate our proposed UKLR classification scheme in comparison with traditional solutions. The promising results show that our proposed UKLR paradigm is more effective than the traditional classification approaches.
Frequent subgraph mining in outerplanar graphs
Authors: Tamás Horváth, Jan Ramon, Stefan Wrobel
Venue: KDD
Year: 2006

In recent years there has been an increased interest in algorithms that can perform frequent pattern discovery in large databases of graph structured objects. While the frequent connected subgraph mining problem for tree datasets can be solved in incremental polynomial time, it becomes intractable for arbitrary graph databases. Existing approaches have therefore resorted to various heuristic strategies and restrictions of the search space, but have not identified a practically relevant tractable graph class beyond trees. In this paper, we define the class of so called tenuous outerplanar graphs, a strict generalization of trees, develop a frequent subgraph mining algorithm for tenuous outerplanar graphs that works in incremental polynomial time, and evaluate the algorithm empirically on the NCI molecular graph dataset.