OpenRaiser/Intern-Atlas huggingface dataset:
Effective label acquisition for collective classification
Authors: Mustafa Bilgic, Lise Getoor
Venue: KDD
Year: 2008

Information diffusion, viral marketing, and collective classification all attempt to model and exploit the relationships in a network to make inferences about the labels of nodes. A variety of techniques have been introduced and methods that combine attribute information and neighboring label information have been shown to be effective for collective labeling of the nodes in a network. However, in part because of the correlation between node labels that the techniques exploit, it is easy to find cases in which, once a misclassification is made, incorrect information propagates throughout the network. This problem can be mitigated if the system is allowed to judiciously acquire the labels for a small number of nodes. Unfortunately, under relatively general assumptions, determining the optimal set of labels to acquire is intractable. Here we propose an acquisition method that learns the cases when a given collective classification algorithm makes mistakes, and suggests acquisitions to correct those mistakes. We empirically show on both real and synthetic datasets that this method significantly outperforms a greedy approximate inference approach, a viral marketing approach, and approaches based on network structural measures such as node degree and network clustering. In addition to significantly improving accuracy with just a small amount of labeled data, our method is tractable on large networks.
An inductive database prototype based on virtual mining views
Authors: Hendrik Blockeel, Toon Calders, Élisa Fromont, Bart Goethals, Adriana Prado, Céline Robardet
Venue: KDD
Year: 2008

We present a prototype of an inductive database. Our system enables the user to query not only the data stored in the database but also generalizations (e.g. rules or trees) over these data through the use of virtual mining views. The mining views are relational tables that virtually contain the complete output of data mining algorithms executed over a given dataset. The prototype implemented into PostgreSQL currently integrates frequent itemset, association rule and decision tree mining. We illustrate the interactive and iterative capabilities of our system with a description of a complete data mining scenario.
Topical query decomposition
Authors: Francesco Bonchi, Carlos Castillo, Debora Donato, Aristides Gionis
Venue: KDD
Year: 2008

We introduce the problem of query decomposition, where we are given a query and a document retrieval system, and we want to produce a small set of queries whose union of resulting documents corresponds approximately to that of the original query. Ideally, these queries should represent coherent, conceptually well-separated topics.
Land cover change detection: a case study
Authors: Shyam Boriah, Vipin Kumar, Michael S. Steinbach, Christopher Potter, Steven A. Klooster
Venue: KDD
Year: 2008

The study of land cover change is an important problem in the Earth Science domain because of its impacts on local climate, radiation balance, biogeochemistry, hydrology, and the diversity and abundance of terrestrial species. Most well-known change detection techniques from statistics, signal processing and control theory are not well-suited for the massive high-dimensional spatio-temporal data sets from Earth Science due to limitations such as high computational complexity and the inability to take advantage of seasonality and spatio-temporal autocorrelation inherent in Earth Science data. In our work, we seek to address these challenges with new change detection techniques that are based on data mining approaches. Specifically, in this paper we have performed a case study for a new change detection technique for the land cover change detection problem. We study land cover change in the state of California, focusing on the San Francisco Bay Area and perform an extended study on the entire state. We also perform a comparative evaluation on forests in the entire state. These results demonstrate the utility of data mining techniques for the land cover change detection problem.
Using tagflake for condensing navigable tag hierarchies from tag clouds
Authors: Luigi Di Caro, K. Selçuk Candan, Maria Luisa Sapino
Venue: KDD
Year: 2008

We present the tagFlake system, which supports semantically informed navigation within a tag cloud. tagFlake relies on TMine for organizing tags extracted from textual content in hierarchical organizations, suitable for navigation, visualization, classification, and tracking. TMine extracts the most significant tag/terms from text documents and maps them onto a hierarchy in such a way that descendant terms are contextually dependent on their ancestors within the given corpus of documents. This provides tagFlake with a mechanism for enabling navigation within the tag space and for classification of the text documents based on the contextual structure captured by the created hierarchy. tagFlake is language neutral, since it does not rely on any natural language processing technique and is unsupervised.
Generating succinct titles for web URLs
Authors: Deepayan Chakrabarti, Ravi Kumar, Kunal Punera
Venue: KDD
Year: 2008

How can a search engine automatically provide the best and most appropriate title for a result URL (link-title) so that users will be persuaded to click on the URL? We consider the problem of automatically generating link-titles for URLs and propose a general statistical framework for solving this problem. The framework is based on using information from a diverse collection of sources, each of which can be thought of as contributing one or more candidate link-titles for the URL. It can also incorporate the context in which the link-title will be used, along with constraints on its length. Our framework is applicable to several scenarios: obtaining succinct titles for displaying quicklinks, obtaining titles for URLs that lack a good title, constructing succinct sitemaps, etc. Extensive experiments show that our method is very effective, producing results that are at least 20% better than non-trivial baselines.
Partitioned logistic regression for spam filtering
Authors: Ming-Wei Chang, Wen-tau Yih, Christopher Meek
Venue: KDD
Year: 2008

Naive Bayes and logistic regression perform well in different regimes. While the former is a very simple generative model which is efficient to train and performs well empirically in many applications,the latter is a discriminative model which often achieves better accuracy and can be shown to outperform naive Bayes asymptotically. In this paper, we propose a novel hybrid model, partitioned logistic regression, which has several advantages over both naive Bayes and logistic regression. This model separates the original feature space into several disjoint feature groups. Individual models on these groups of features are learned using logistic regression and their predictions are combined using the naive Bayes principle to produce a robust final estimation. We show that our model is better both theoretically and empirically. In addition, when applying it in a practical application, email spam filtering, it improves the normalized AUC score at 10% false-positive rate by 28.8% and 23.6% compared to naive Bayes and logistic regression, when using the exact same training examples.
Tagmark: reliable estimations of RFID tags for business processes
Authors: Leonardo Weiss Ferreira Chaves, Erik Buchmann, Klemens Böhm
Venue: KDD
Year: 2008

Radio Frequency Identification (RFID) promises optimization of commodity flows in all industry segments. But due to physical constraints, RFID technology cannot detect all RFID tags from an assembly of items. This poses problems when integrating RFID data with enterprise-backend systems for tasks like inventory management or shelf replenishment. In this paper we propose the TagMark method to accomplish this integration. TagMark targets at a retailer scenario, where it estimates the number of tagged items from samples like the sales history or the tags read by smart shelves. The problem is challenging because most existing estimation methods depend on assumptions that do not hold in typical RFID applications, e.g., static item sets, simple random samples, or the availability of samples with user-defined sizes. TagMark adapts mark-recapture-methods in order to provide guarantees for the accuracy of the estimation and bounds for the sample sizes. It can be implemented as a database extension, allowing seamless integration into existing enterprise backend systems. A study with RFID-equipped goods acknowledges that our approach is effective in realistic scenarios, and database experiments with up to 1,000,000 items confirm that it can be efficiently implemented. Finally, we explore a broad range of extreme conditions that might stress TagMark, including a thief who knows the location of unread items.
Learning subspace kernels for classification
Authors: Jianhui Chen, Shuiwang Ji, Betul Ceran, Qi Li, Mingrui Wu, Jieping Ye
Venue: KDD
Year: 2008

Kernel methods have been applied successfully in many data mining tasks. Subspace kernel learning was recently proposed to discover an effective low-dimensional subspace of a kernel feature space for improved classification. In this paper, we propose to construct a subspace kernel using the Hilbert-Schmidt Independence Criterion (HSIC). We show that the optimal subspace kernel can be obtained efficiently by solving an eigenvalue problem. One limitation of the existing subspace kernel learning formulations is that the kernel learning and classification are independent and the subspace kernel may not be optimally adapted for classification. To overcome this limitation, we propose a joint optimization framework, in which we learn the subspace kernel and subsequent classifiers simultaneously. In addition, we propose a novel learning formulation that extracts an uncorrelated subspace kernel to reduce the redundant information in a subspace kernel. Following the idea from multiple kernel learning, we extend the proposed formulations to the case when multiple kernels are available and need to be combined. We show that the integration of subspace kernels can be formulated as a semidefinite program (SDP) which is computationally expensive. To improve the efficiency of the SDP formulation, we propose an equivalent semi-infinite linear program (SILP) formulation which can be solved efficiently by the column generation technique. Experimental results on a collection of benchmark data sets demonstrate the effectiveness of the proposed algorithms.
FAST: a roc-based feature selection metric for small samples and imbalanced data classification problems
Authors: Xue-wen Chen, Michael Wasikowski
Venue: KDD
Year: 2008

The class imbalance problem is encountered in a large number of practical applications of machine learning and data mining, for example, information retrieval and filtering, and the detection of credit card fraud. It has been widely realized that this imbalance raises issues that are either nonexistent or less severe compared to balanced class cases and often results in a classifier's suboptimal performance. This is even more true when the imbalanced data are also high dimensional. In such cases, feature selection methods are critical to achieve optimal performance. In this paper, we propose a new feature selection method, Feature Assessment by Sliding Thresholds (FAST), which is based on the area under a ROC curve generated by moving the decision boundary of a single feature classifier with thresholds placed using an even-bin distribution. FAST is compared to two commonly-used feature selection methods, correlation coefficient and RELevance In Estimating Features (RELIEF), for imbalanced data classification. The experimental results obtained on text mining, mass spectrometry, and microarray data sets showed that the proposed method outperformed both RELIEF and correlation methods on skewed data sets and was comparable on balanced data sets; when small number of features is preferred, the classification performance of the proposed method was significantly improved compared to correlation and RELIEF-based methods.
The persuasive phase of visualization
Authors: Christine H. Chih, Douglas Stott Parker Jr.
Venue: KDD
Year: 2008

Research in visualization often revolves around visualizing information. However, visualization is a process that extends over time from initial exploration to hypothesis confirmation, and even to result presentation. It is rare that the final phases of visualization are solely about information. In this paper we present a more biased kind of visualization, in which there is a message or set of assumptions behind the presentation that is of interest to both the presenter and the viewer, and emphasizes points that the presenter wants to convey to the viewer. This kind of persuasive visualization -- presenting data in a way that emphasizes a point or message -- is not only common in visualization, but also often expected by the viewer. Persuasive visualization is implicit in the deliberate emphasis on interestingness and also in the deliberate use of graphical elements that are processed preattentively by the human visual system, which automatically groups these elements and guiding attention so that they "stand out". We discuss how these ideas have been implemented in the Morpherspective system for automated generation of information graphics.
Reconstructing chemical reaction networks: data mining meets system identification
Authors: Yong Ju Cho, Naren Ramakrishnan, Yang Cao
Venue: KDD
Year: 2008

We present an approach to reconstructing chemical reaction networks from time series measurements of the concentrations of the molecules involved. Our solution strategy combines techniques from numerical sensitivity analysis and probabilistic graphical models. By modeling a chemical reaction system as a Markov network (undirected graphical model), we show how systematically probing for sensitivities between molecular species can identify the topology of the network. Given the topology, our approach next uses detailed sensitivity profiles to characterize properties of reactions such as reversibility, enzyme-catalysis, and the precise stoichiometries of the reactants and products. We demonstrate applications to reconstructing key biological systems including the yeast cell cycle. In addition to network reconstruction, our algorithm finds applications in model reduction and model comprehension. We argue that our reconstruction algorithm can serve as an important primitive for data mining in systems biology applications.
Learning methods for lung tumor markerless gating in image-guided radiotherapy
Authors: Ying Cui, Jennifer G. Dy, Gregory C. Sharp, Brian M. Alexander, Steve B. Jiang
Venue: KDD
Year: 2008

In an idealized gated radiotherapy treatment, radiation is delivered only when the tumor is at the right position. For gated lung cancer radiotherapy, it is difficult to generate accurate gating signals due to the large uncertainties when using external surrogates and the risk of pneumothorax when using implanted fiducial markers. In this paper, we investigate machine learning algorithms for markerless gated radiotherapy with fluoroscopic images. Previous approach utilizes template matching to localize the tumor position. Here, we investigate two ways to improve the precision of tumor target localization by applying: (1) an ensemble of templates where the representative templates are selected by Gaussian mixture clustering, and (2) a support vector machine (SVM) classifier with radial basis kernels. Template matching only considers images inside the gating window, but images outside the gating window might provide additional information. We take advantage of both states and re-cast the gating problem into a classification problem. Thus, we are able to use the SVM classifier for gated radiotherapy. To verify the effectiveness of the two proposed techniques, we apply them on five sequences of fluoroscopic images from five lung cancer patients against the gating signal of manually contoured tumors as ground truth. Our five-patient case study shows that both ensemble template matching and SVM are reasonable tools for image-guided markerless gated radiotherapy with an average of approximately 95% precision in terms of delivered target dose at approximately 35% duty cycle.
De-duping URLs via rewrite rules
Authors: Anirban Dasgupta, Ravi Kumar, Amit Sasturkar
Venue: KDD
Year: 2008

A large fraction of the URLs on the web contain duplicate (or near-duplicate) content. De-duping URLs is an extremely important problem for search engines, since all the principal functions of a search engine, including crawling, indexing, ranking, and presentation, are adversely impacted by the presence of duplicate URLs. Traditionally, the de-duping problem has been addressed by fetching and examining the content of the URL; our approach here is different. Given a set of URLs partitioned into equivalence classes based on the content (URLs in the same equivalence class have similar content), we address the problem of mining this set and learning URL rewrite rules that transform all URLs of an equivalence class to the same canonical form. These rewrite rules can then be applied to eliminate duplicates among URLs that are encountered for the first time during crawling, even without fetching their content.
Internet advertising and optimal auction design
Authors: Benjamin Edelman, Michael Schwarz
Venue: KDD
Year: 2008

This talk describes the optimal (revenue maximizing) auction for sponsored search advertising. We show that a search engine's optimal reserve price is independent of the number of bidders. Using simulations, we consider the changes that result from a search engine's choice of reserve price and from changes in the number of participating advertisers.
Scaling up text classification for large file systems
Authors: George Forman, Shyamsundar Rajaram
Venue: KDD
Year: 2008

We combine the speed and scalability of information retrieval with the generally superior classification accuracy offered by machine learning, yielding a two-phase text classifier that can scale to very large document corpora. We investigate the effect of different methods of formulating the query from the training set, as well as varying the query size. In empirical tests on the Reuters RCV1 corpus of 806,000 documents, we find runtime was easily reduced by a factor of 27x, with a somewhat surprising gain in F-measure compared with traditional text classification.
SPIRAL: efficient and exact model identification for hidden Markov models
Authors: Yasuhiro Fujiwara, Yasushi Sakurai, Masashi Yamamuro
Venue: KDD
Year: 2008

Hidden Markov models (HMMs) have received considerable attention in various communities (e.g, speech recognition, neurology and bioinformatic) since many applications that use HMM have emerged. The goal of this work is to identify efficiently and correctly the model in a given dataset that yields the state sequence with the highest likelihood with respect to the query sequence. We propose SPIRAL, a fast search method for HMM datasets. To reduce the search cost, SPIRAL efficiently prunes a significant number of search candidates by applying successive approximations when estimating likelihood. We perform several experiments to verify the effectiveness of SPIRAL. The results show that SPIRAL is more than 500 times faster than the naive method.
Banded structure in binary matrices
Authors: Gemma C. Garriga, Esa Junttila, Heikki Mannila
Venue: KDD
Year: 2008

A 0--1 matrix has a banded structure if both rows and columns can be permuted so that the non-zero entries exhibit a staircase pattern of overlapping rows. The concept of banded matrices has its origins in numerical analysis, where entries can be viewed as descriptions between the problem variables; the bandedness corresponds to variables that are coupled over short distances. Banded data occurs also in other applications, for example in the physical mapping problem of the human genome, in paleontological data, in network data and in the discovery of overlapping communities without cycles.
Text classification, business intelligence, and interactivity: automating C-Sat analysis for services industry
Authors: Shantanu Godbole, Shourya Roy
Venue: KDD
Year: 2008

Text classification has matured as a research discipline over the last decade. Independently, business intelligence over structured databases has long been a source of insights for enterprises. In this work, we bring the two together for Customer Satisfaction(C-Sat) analysis in the services industry. We present ITACS, a solution combining text classification and business intelligence integrated with a novel interactive text labeling interface. ITACS has been deployed in multiple client accounts in contact centers. It can be extended to any services industry setting to analyze unstructured text data and derive operational and business insights. We highlight importance of interactivity in real-life text classification settings. We bring out some unique research challenges about label-sets, measuring accuracy, and interpretability that need serious attention in both academic and industrial research. We recount invaluable experiences and lessons learned as data mining researchers working toward seeing research technology deployed in the services industry.
Data mining using high performance data clouds: experimental studies using sector and sphere
Authors: Robert L. Grossman, Yunhong Gu
Venue: KDD
Year: 2008

We describe the design and implementation of a high performance cloud that we have used to archive, analyze and mine large distributed data sets. By a cloud, we mean an infrastructure that provides resources and/or services over the Internet. A storage cloud provides storage services, while a compute cloud provides compute services. We describe the design of the Sector storage cloud and how it provides the storage services required by the Sphere compute cloud. We also describe the programming paradigm supported by the Sphere compute cloud. Sector and Sphere are designed for analyzing large data sets using computer clusters connected with wide area high performance networks (for example, 10+ Gb/s). We describe a distributed data mining application that we have developed using Sector and Sphere. Finally, we describe some experimental studies comparing Sector/Sphere to Hadoop.
Unsupervised deduplication using cross-field dependencies
Authors: Robert J. Hall, Charles Sutton, Andrew McCallum
Venue: KDD
Year: 2008

Recent work in deduplication has shown that collective deduplication of different attribute types can improve performance. But although these techniques cluster the attributes collectively, they do not model them collectively. For example, in citations in the research literature, canonical venue strings and title strings are dependent -- because venues tend to focus on a few research areas -- but this dependence is not modeled by current unsupervised techniques. We call this dependence between fields in a record a cross-field dependence. In this paper, we present an unsupervised generative model for the deduplication problem that explicitly models cross-field dependence. Our model uses a single set of latent variables to control two disparate clustering models: a Dirichlet-multinomial model over titles, and a non-exchangeable string-edit model over venues. We show that modeling cross-field dependence yields a substantial improvement in performance -- a 58% reduction in error over a standard Dirichlet process mixture.
Regularization paths and coordinate descent
Authors: Trevor Hastie, Jerome H. Friedman, Robert Tibshirani
Venue: KDD
Year: 2008

In a statistical world faced with an explosion of data, regularization has become an important ingredient. In a wide variety of problems we have many more input features than observations, and the lasso penalty and its hybrids have become increasingly useful for both feature selection and regularization. This talk presents some effective algorithms based on coordinate descent for fitting large scale regularization paths for a variety of problems.