OpenRaiser/Intern-Atlas huggingface dataset:
Disease progression modeling from historical clinical databases
Authors: Ronald K. Pearson, Robert J. Kingan, Alan Hochberg
Venue: KDD
Year: 2005

This paper considers the problem of modeling disease progression from historical clinical databases, with the ultimate objective of stratifying patients into groups with clearly distinguishable prognoses or suitability for different treatment strategies. To meet this objective, we describe a procedure that first fits clinical variables measured over time to a disease progression model. The resulting parameter estimates are then used as the basis for a stepwise clustering procedure to stratify patients into groups with distinct survival characteristics. As a practical illustration, we apply this procedure to survival prediction, using a liver transplant database from the National Institute of Diabetes and Digestive and Kidney Diseases (NIDDK).
On mining cross-graph quasi-cliques
Authors: Jian Pei, Daxin Jiang, Aidong Zhang
Venue: KDD
Year: 2005

Joint mining of multiple data sets can often discover interesting, novel, and reliable patterns which cannot be obtained solely from any single source. For example, in cross-market customer segmentation, a group of customers who behave similarly in multiple markets should be considered as a more coherent and more reliable cluster than clusters found in a single market. As another example, in bioinformatics, by joint mining of gene expression data and protein interaction data, we can find clusters of genes which show coherent expression patterns and also produce interacting proteins. Such clusters may be potential pathways.In this paper, we investigate a novel data mining problem, mining cross-graph quasi-cliques, which is generalized from several interesting applications such as cross-market customer segmentation and joint mining of gene expression data and protein interaction data. We build a general model for mining cross-graph quasi-cliques, show why the complete set of cross-graph quasi-cliques cannot be found by previous data mining methods, and study the complexity of the problem. While the problem is difficult, we develop an efficient algorithm, Crochet, which exploits several interesting and effective techniques and heuristics to efficaciously mine cross-graph quasi-cliques. A systematic performance study is reported on both synthetic and real data sets. We demonstrate some interesting and meaningful cross-graph quasi-cliques in bioinformatics. The experimental results also show that algorithm Crochet is efficient and scalable.
Mining rare and frequent events in multi-camera surveillance video using self-organizing maps
Authors: Valery A. Petrushin
Venue: KDD
Year: 2005

This paper describes a method for unsupervised classification of events in multi-camera indoors surveillance video. This research is a part of the Multiple Sensor Indoor Surveillance (MSIS) project which uses 32 AXIS-2100 webcams that observe an office environment. The research was inspired by the following practical problem: how automatically classify and visualize a 24 hour long video captured by 32 cameras? Raw data are sequences of JPEG images captured by webcams at the rate 2-6 Hz. The following features are extracted from the image data: foreground pixels' spatial distribution and color histogram. The data are integrated by event by averaging motion and color features and creating a "summary" frame which accumulates all foreground pixels of frames of the event into one image. The self-organizing map (SOM) approach is applied to event data for clustering and visualization. One-level and two-level SOM clustering are used. A tool for browsing results allows exploring units of the SOM maps at different levels of hierarchy, clusters of units and distances between units in 3D space. A special technique has been developed to visualize rare events. The results are presented and discussed.
Short term performance forecasting in enterprise systems
Authors: Rob Powers, Moisés Goldszmidt, Ira Cohen
Venue: KDD
Year: 2005

We use data mining and machine learning techniques to predict upcoming periods of high utilization or poor performance in enterprise systems. The abundant data available and complexity of these systems defies human characterization or static models and makes the task suitable for data mining techniques. We formulate the problem as one of classification: given current and past information about the system's behavior, can we forecast whether the system will meet its performance targets over the next hour? Using real data gathered from several enterprise systems in Hewlett-Packard, we compare several approaches ranging from time series to Bayesian networks. Besides establishing the predictive power of these approaches our study analyzes three dimensions that are important for their application as a stand alone tool. First, it quantifies the gain in accuracy of multivariate prediction methods over simple statistical univariate methods. Second, it quantifies the variations in accuracy when using different classes of system and workload features. Third, it establishes that models induced using combined data from various systems generalize well and are applicable to new systems, enabling accurate predictions on systems with insufficient historical data. Together this analysis offers a promising outlook on the development of tools to automate assignment of resources to stabilize performance, (e.g., adding servers to a cluster) and allow opportunistic job scheduling (e.g., backups or virus scans).
Query chains: learning to rank from implicit feedback
Authors: Filip Radlinski, Thorsten Joachims
Venue: KDD
Year: 2005

This paper presents a novel approach for using clickthrough data to learn ranked retrieval functions for web search results. We observe that users searching the web often perform a sequence, or chain, of queries with a similar information need. Using query chains, we generate new types of preference judgments from search engine logs, thus taking advantage of user intelligence in reformulating queries. To validate our method we perform a controlled user study comparing generated preference judgments to explicit relevance judgments. We also implemented a real-world search engine to test our approach, using a modified ranking SVM to learn an improved ranking function from preference data. Our results demonstrate significant improvements in the ranking given by the search engine. The learned rankings outperform both a static ranking function, as well as one trained without considering query chains.
Incentive networks
Authors: Prabhakar Raghavan
Venue: KDD
Year: 2005

We propose a notion of incentive networks, modeling online settings in which multiple participants in a network help each other find information. Within this general setting, we study query incentive networks, a natural abstraction of question-answering systems with rewards for finding answers. We analyze strategic behavior in such networks and under a simple model of networks, show that the Nash equilibrium for participants' strategies exhibits an unexpected threshold phenomenon.
Predicting the product purchase patterns of corporate customers
Authors: Bhavani Raskutti, Alan Herschtal
Venue: KDD
Year: 2005

This paper describes TIPPPS (Time Interleaved Product Purchase Prediction System), which analyses billing data of corporate customers in a large telecommunications company in order to predict high value upsell opportunities. The challenges presented by this prediction problem are significant. Firstly, the diversity of products used by corporate telecommunications customers is huge. This, coupled with low product take-up rates, makes this a problem of learning from a very high dimensional feature space with very few minority examples. Further, it is important to give priority specifically to the identification of those new customers who are of high value. These challenges are overcome by introducing a number of modifications to standard data pre-processing and machine learning algorithms, the most important of which are time-interleaving of data and value weighting. Time interleaving is the concatenation of examples from multiple time periods, thus increasing the number of training examples, and hence the number of minority examples. Value weighting assigns importance to minority examples in proportion to the dollar value of take-up, thus biasing the system to identify high value customers. These modifications create a novel algorithm that makes the prediction system practical and usable.Comparison with other techniques designed for similar problems shows that the expected average improvement in ranking accuracy achieved using these modifications is 3.7%. TIPPPS has been in operation for several months and has been successful in identifying many upsell opportunities that were not identified by using the previous manual system.
On the use of linear programming for unsupervised text classification
Authors: Mark Sandler
Venue: KDD
Year: 2005

We propose a new algorithm for dimensionality reduction and unsupervised text classification. We use mixture models as underlying process of generating corpus and utilize a novel, L1-norm based approach introduced by Kleinberg and Sandler [19]. We show that our algorithm performs extremely well on large datasets, with peak accuracy approaching that of supervised learning based on Support Vector Machines (SVMs) with large training sets. The method is based on the same idea that underlies Latent Semantic Indexing (LSI). We find a good low-dimensional subspace of a feature space and project all documents into it. However our projection minimizes different error, and unlike LSI we build a basis, that in many cases corresponds to the actual topics. We present results of testing of our algorithm on the abstracts of arXiv - an electronic repository of scientific papers, and the 20 Newsgroup dataset - a small snapshot of 20 specific newsgroups.
A multinomial clustering model for fast simulation of computer architecture designs
Authors: Kaushal Sanghai, Ting Su, Jennifer G. Dy, David R. Kaeli
Venue: KDD
Year: 2005

Computer architects utilize simulation tools to evaluate the merits of a new design feature. The time needed to adequately evaluate the tradeoffs associated with adding any new feature has become a critical issue. Recent work has found that by identifying execution phases present in common workloads used in simulation studies, we can apply clustering algorithms to significantly reduce the amount of time needed to complete the simulation. Our goal in this paper is to demonstrate the value of this approach when applied to the set of industry-standard benchmarks most commonly used in computer architecture studies. We also look to improve upon prior work by applying more appropriate clustering algorithms to identify phases, and to further reduce simulation time.We find that the phase clustering in computer architecture simulation has many similarities to text clustering. In prior work on clustering techniques to reduce simulation time, K-means clustering was used to identify representative program phases. In this paper we apply a mixture of multinomials to the clustering problem and show its advantages over using K-means on simulation data. We have implemented these two clustering algorithms and evaluate how well they can characterize program behavior. By adopting a mixture of multinomials model, we find that we can maintain simulation result fidelity, while greatly reducing overall simulation time. We report results for a range of applications taken from the SPEC2000 benchmark suite.
Sampling-based sequential subgroup mining
Authors: Martin Scholz
Venue: KDD
Year: 2005

Subgroup discovery is a learning task that aims at finding interesting rules from classified examples. The search is guided by a utility function, trading o# the coverage of rules against their statistical unusualness. One shortcoming of existing approaches is that they do not incorporate prior knowledge. To this end a novel generic sampling strategy is proposed. It allows to turn pattern mining into an iterative process. In each iteration the focus of subgroup discovery lies on those patterns that are unexpected with respect to prior knowledge and previously discovered patterns. The result of this technique is a small diverse set of understandable rules that characterise a specified property of interest. As another contribution this article derives a simple connection between subgroup discovery and classifier induction. For a popular utility function this connection allows to apply any standard rule induction algorithm to the task of subgroup discovery after a step of stratified resampling. The proposed techniques are empirically compared to state of the art subgroup discovery algorithms.
Modeling and predicting personal information dissemination behavior
Authors: Xiaodan Song, Ching-Yung Lin, Belle L. Tseng, Ming-Ting Sun
Venue: KDD
Year: 2005

In this paper, we propose a new way to automatically model and predict human behavior of receiving and disseminating information by analyzing the contact and content of personal communications. A personal profile, called CommunityNet, is established for each individual based on a novel algorithm incorporating contact, content, and time information simultaneously. It can be used for personal social capital management. Clusters of CommunityNets provide a view of informal networks for organization management. Our new algorithm is developed based on the combination of dynamic algorithms in the social network field and the semantic content classification methods in the natural language processing and machine learning literatures. We tested CommunityNets on the Enron Email corpus and report experimental results including filtering, prediction, and recommendation capabilities. We show that the personal behavior and intention are somewhat predictable based on these models. For instance, "to whom a person is going to send a specific email" can be predicted by one's personal social network and content analysis. Experimental results show the prediction accuracy of the proposed adaptive algorithm is 58% better than the social network-based predictions, and is 75% better than an aggregated model based on Latent Dirichlet Allocation with social network enhancement. Two online demo systems we developed that allow interactive exploration of CommunityNet are also discussed.
Evaluating similarity measures: a large-scale study in the orkut social network
Authors: Ellen Spertus, Mehran Sahami, Orkut Buyukkokten
Venue: KDD
Year: 2005

Online information services have grown too large for users to navigate without the help of automated tools such as collaborative filtering, which makes recommendations to users based on their collective past behavior. While many similarity measures have been proposed and individually evaluated, they have not been evaluated relative to each other in a large real-world environment. We present an extensive empirical comparison of six distinct measures of similarity for recommending online communities to members of the Orkut social network. We determine the usefulness of the different recommendations by actually measuring users' propensity to visit and join recommended communities. We also examine how the ordering of recommendations influenced user selection, as well as interesting social issues that arise in recommending communities within a real social network.
Mining comparable bilingual text corpora for cross-language information integration
Authors: Tao Tao, ChengXiang Zhai
Venue: KDD
Year: 2005

Integrating information in multiple natural languages is a challenging task that often requires manually created linguistic resources such as a bilingual dictionary or examples of direct translations of text. In this paper, we propose a general cross-lingual text mining method that does not rely on any of these resources, but can exploit comparable bilingual text corpora to discover mappings between words and documents in different languages. Comparable text corpora are collections of text documents in different languages that are about similar topics; such text corpora are often naturally available (e.g., news articles in different languages published in the same time period). The main idea of our method is to exploit frequency correlations of words in different languages in the comparable corpora and discover mappings between words in different languages. Such mappings can then be used to further discover mappings between documents in different languages, achieving cross-lingual information integration. Evaluation of the proposed method on a 120MB Chinese-English comparable news collection shows that the proposed method is effective for mapping words and documents in English and Chinese. Since our method only relies on naturally available comparable corpora, it is generally applicable to any language pairs as long as we have comparable corpora.
Regression error characteristic surfaces
Authors: Luís Torgo
Venue: KDD
Year: 2005

This paper presents a generalization of Regression Error Characteristic (REC) curves. REC curves describe the cumulative distribution function of the prediction error of models and can be seen as a generalization of ROC curves to regression problems. REC curves provide useful information for analyzing the performance of models, particularly when compared to error statistics like for instance the Mean Squared Error. In this paper we present Regression Error Characteristic (REC) surfaces that introduce a further degree of detail by plotting the cumulative distribution function of the errors across the distribution of the target variable, i.e. the joint cumulative distribution function of the errors and the target variable. This provides a more detailed analysis of the performance of models when compared to REC curves. This extra detail is particularly relevant in applications with non-uniform error costs, where it is important to study the performance of models for specific ranges of the target variable. In this paper we present the notion of REC surfaces, describe how to use them to compare the performance of models, and illustrate their use with an important practical class of applications: the prediction of rare extreme values.
Finding partial orders from unordered 0-1 data
Authors: Antti Ukkonen, Mikael Fortelius, Heikki Mannila
Venue: KDD
Year: 2005

In applications such as paleontology and medical genetics the 0-1 data has an underlying unknown order (the ages of the fossil sites, the locations of markers in the genome). The order might be total or partial: for example, two sites in different parts of the globe might be ecologically incomparable, or the ordering of certain markers might be different in different subgroups of the data. We consider the following problem. Given a table over a set of 0-1 variables, find a partial order for the rows minimizing a score function and being as specific as possible. The score function can be, e.g., the number of changes from 1 to 0 in a column (for paleontology) or the likelihood of the marker sequence (for genomic data). Our solution for this task first constructs small totally ordered fragments of the partial order, then finds good orientations for the fragments, and finally uses a simple and efficient heuristic method for finding a partial order that corresponds well with the collection of fragments. We describe the method, discuss its properties, and give empirical results on paleontological data demonstrating the usefulness of the method. In the application the use of the method highlighted some previously unknown properties of the data and pointed out probable errors in the data.
Web object indexing using domain knowledge
Authors: Muyuan Wang, Zhiwei Li, Lie Lu, Wei-Ying Ma, Naiyao Zhang
Venue: KDD
Year: 2005

A web object is defined to represent any meaningful object embedded in web pages (e.g. images, music) or pointed to by hyperlinks (e.g. downloadable files). In many cases, users would like to search for information of a certain 'object', rather than a web page containing the query terms. To facilitate web object searching and organizing, in this paper, we propose a novel approach to web object indexing, by discovering its inherent structure information with existed domain knowledge. In our approach, first, Layered LSI spaces are built for a better representation of the hierarchically structured domain knowledge, in order to emphasize the specific semantics and term space in each layer of the domain knowledge. Meanwhile, the web object representation is constructed by hyperlink analysis, and further pruned to remove the noises. Then an optimal matching between the web object and the domain knowledge is performed, in order to pick out the structure attributes of the web object from the knowledge. Finally, the obtained structure attributes are used to re-organize and index the web objects. Our approach also indicates a new promising way to use trust-worthy Deep Web knowledge to help organize dispersive information of Surface Web.
Pattern-based similarity search for microarray data
Authors: Haixun Wang, Jian Pei, Philip S. Yu
Venue: KDD
Year: 2005

One fundamental task in near-neighbor search as well as other similarity matching efforts is to find a distance function that can efficiently quantify the similarity between two objects in a meaningful way. In DNA microarray analysis, the expression levels of two closely related genes may rise and fall synchronously in response to a set of experimental stimuli. Although the magnitude of their expression levels may not be close, the patterns they exhibit can be very similar. Unfortunately, none of the conventional distance metrics such as the Lp norm can model this similarity effectively. In this paper, we study the near-neighbor search problem based on this new type of similarity. We propose to measure the distance between two genes by subspace pattern similarity, i.e., whether they exhibit a synchronous pattern of rise and fall on a subset of dimensions. We then present an efficient algorithm for subspace near-neighbor search based on pattern similarity distance, and we perform tests on various data sets to show its effectiveness.
Formulating distance functions via the kernel trick
Authors: Gang Wu, Edward Y. Chang, Navneet Panda
Venue: KDD
Year: 2005

Tasks of data mining and information retrieval depend on a good distance function for measuring similarity between data instances. The most effective distance function must be formulated in a context-dependent (also application-, data-, and user-dependent) way. In this paper, we propose to learn a distance function by capturing the nonlinear relationships among contextual information provided by the application, data, or user. We show that through a process called the "kernel trick," such nonlinear relationships can be learned efficiently in a projected space. Theoretically, we substantiate that our method is both sound and optimal. Empirically, using several datasets and applications, we demonstrate that our method is effective and useful.