OpenRaiser/Intern-Atlas huggingface dataset:
Learning a complex metabolomic dataset using random forests and support vector machines
Authors: Young Truong, Xiaodong Lin, Chris Beecher
Venue: KDD
Year: 2004

Metabolomics is the "omics" science of biochemistry. The associated data include the quantitative measurements of all small molecule metabolites in a biological sample. These datasets provide a window into dynamic biochemical networks and conjointly with other "omic" data, genes and proteins, have great potential to unravel complex human diseases. The dataset used in this study has 63 individuals, normal and diseased, and the diseased are drug treated or not, so there are three classes. The goal is to classify these individuals using the observed metabolite levels for 317 measured metabolites. There are a number of statistical challenges: non-normal data, the number of samples is less than the number of metabolites; there are missing data and the fact that data are missing is informative (assay values below detection limits can point to a specific class); also, there are high correlations among the metabolites. We investigate support vector machines (SVM), and random forest (RF), for outlier detection, variable selection and classification. We use the variables selected with RF in SVM and visa versa. The benefit of this study is insight into interplay of variable selection and classification methods. We link our selected predictors to the biochemistry of the disease.
1-dimensional splines as building blocks for improving accuracy of risk outcomes models
Authors: David S. Vogel, Morgan C. Wang
Venue: KDD
Year: 2004

Transformation of both the response variable and the predictors is commonly used in fitting regression models. However, these transformation methods do not always provide the maximum linear correlation between the response variable and the predictors, especially when there are non-linear relationships between predictors and the response such as the medical data set used in this study. A spline based transformation method is proposed that is second order smooth, continuous, and minimizes the mean squared error between the response and each predictor. Since the computation time for generating this spline is O(n), the processing time is reasonable with massive data sets. In contrast to cubic smoothing splines, the resulting transformation equations also display a high level of efficiency for scoring. Data used for predicting health outcomes contains an abundance of non-linear relationships between predictors and the outcomes requiring an algorithm for modeling them accurately. Thus, a transformation that fits an adaptive cubic spline to each of a set of variables is proposed. These curves are used as a set of transformation functions on the predictors. A case study of how the transformed variables can be fed into a simple linear regression model to predict risk outcomes is presented. The results show significant improvement over the performance of the original variables in both linear and non-linear models.
Scalable mining of large disk-based graph databases
Authors: Chen Wang, Wei Wang, Jian Pei, Yongtai Zhu, Baile Shi
Venue: KDD
Year: 2004

Mining frequent structural patterns from graph databases is an interesting problem with broad applications. Most of the previous studies focus on pruning unfruitful search subspaces effectively, but few of them address the mining on large, disk-based databases. As many graph databases in applications cannot be held into main memory, scalable mining of large, disk-based graph databases remains a challenging problem. In this paper, we develop an effective index structure, ADI (for <u>ad</u>jacency <u>i</u>ndex), to support mining various graph patterns over large databases that cannot be held into main memory. The index is simple and efficient to build. Moreover, the new index structure can be easily adopted in various existing graph pattern mining algorithms. As an example, we adapt the well-known gSpan algorithm by using the ADI structure. The experimental results show that the new index structure enables the scalable graph pattern mining over large databases. In one set of the experiments, the new disk-based method can mine graph databases with one million graphs, while the original gSpan algorithm can only handle databases of up to 300 thousand graphs. Moreover, our new method is faster than gSpan when both can run in main memory.
Privacy-preserving Bayesian network structure computation on distributed heterogeneous data
Authors: Rebecca N. Wright, Zhiqiang Yang
Venue: KDD
Year: 2004

As more and more activities are carried out using computers and computer networks, the amount of potentially sensitive data stored by business, governments, and other parties increases. Different parties may wish to benefit from cooperative use of their data, but privacy regulations and other privacy concerns may prevent the parties from sharing their data. Privacy-preserving data mining provides a solution by creating distributed data mining algorithms in which the underlying data is not revealed.In this paper, we present a privacy-preserving protocol for a particular data mining task: learning the Bayesian network structure for distributed heterogeneous data. In this setting, two parties owning confidential databases wish to learn the structure of Bayesian network on the combination of their databases without revealing anything about their data to each other. We give an efficient and privacy-preserving version of the K2 algorithm to construct the structure of a Bayesian network for the parties' joint data.
Mining scale-free networks using geodesic clustering
Authors: Andrew Y. Wu, Michael Garland, Jiawei Han
Venue: KDD
Year: 2004

Many real-world graphs have been shown to be scale-free--- vertex degrees follow power law distributions, vertices tend to cluster, and the average length of all shortest paths is small. We present a new model for understanding scale-free networks based on multilevel geodesic approximation, using a new data structure called a multilevel mesh. Using this
Incorporating prior knowledge with weighted margin support vector machines
Authors: Xiaoyun Wu, Rohini K. Srihari
Venue: KDD
Year: 2004

Like many purely data-driven machine learning methods, Support Vector Machine (SVM) classifiers are learned exclusively from the evidence presented in the training dataset; thus a larger training dataset is required for better performance. In some applications, there might be human knowledge available that, in principle, could compensate for the lack of data. In this paper, we propose a simple generalization of SVM: Weighted Margin SVM (WMSVMs) that permits the incorporation of prior knowledge. We show that Sequential Minimal Optimization can be used in training WMSVM. We discuss the issues of incorporating prior knowledge using this rather general formulation. The experimental results show that the proposed methods of incorporating prior knowledge is effective.
Exploiting a support-based upper bound of Pearson's correlation coefficient for efficiently identifying strongly correlated pairs
Authors: Hui Xiong, Shashi Shekhar, Pang-Ning Tan, Vipin Kumar
Venue: KDD
Year: 2004

Given a user-specified minimum correlation threshold θ and a market basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold θ. However, when the number of items and transactions are large, the computation cost of this query can be very high. In this paper, we identify an upper bound of Pearson's correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson's correlation coefficient but also exhibits a special monotone property which allows pruning of many item pairs even without computing their upper bounds. A Two-step All-strong-Pairs corrElation que Ry (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent or improves when the number of items is increased in data sets with common Zipf or linear rank-support distributions. Experimental results from synthetic and real data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives.
IMMC: incremental maximum margin criterion
Authors: Jun Yan, Benyu Zhang, Shuicheng Yan, Qiang Yang, Hua Li, Zheng Chen, Wensi Xi, Weiguo Fan, Wei-Ying Ma, QianSheng Cheng
Venue: KDD
Year: 2004

Subspace learning approaches have attracted much attention in academia recently. However, the classical batch algorithms no longer satisfy the applications on streaming data or large-scale data. To meet this desirability, Incremental Principal Component Analysis (IPCA) algorithm has been well established, but it is an unsupervised subspace learning approach and is not optimal for general classification tasks, such as face recognition and Web document categorization. In this paper, we propose an incremental supervised subspace learning algorithm, called Incremental Maximum Margin Criterion (IMMC), to infer an adaptive subspace by optimizing the Maximum Margin Criterion. We also present the proof for convergence of the proposed algorithm. Experimental results on both synthetic dataset and real world datasets show that IMMC converges to the similar subspace as that of batch approach.
2PXMiner: an efficient two pass mining of frequent XML query patterns
Authors: Liang Huai Yang, Mong-Li Lee, Wynne Hsu, Xinyu Guo
Venue: KDD
Year: 2004

Caching the results of frequent query patterns can improve the performance of query evaluation. This paper describes a 2-pass mining algorithm called 2PXMiner to discover frequent XML query patterns. We design 3 data structures to expedite the mining process. Experiments results indicate that 2PXMiner is both efficient and scalable.
IDR/QR: an incremental dimension reduction algorithm via QR decomposition
Authors: Jieping Ye, Qi Li, Hui Xiong, Haesun Park, Ravi Janardan, Vipin Kumar
Venue: KDD
Year: 2004

Dimension reduction is a critical data preprocessing step for many database and data mining applications, such as efficient storage and retrieval of high-dimensional data. In the literature, a well-known dimension reduction algorithm is linear discriminant analysis (LDA). The common aspect of previously proposed LDA-based algorithms is the use of singular value decomposition (SVD). Due to the difficulty of designing an incremental solution for the eigenvalue problem on the product of scatter matrices in LDA, there has been little work on designing incremental LDA algorithms that can efficiently incorporate new data items as they become available. In this paper, we propose an LDA-based incremental dimension reduction algorithm, called IDR/QR, which applies QR decomposition rather than SVD. Unlike other LDA-based algorithms, this algorithm does not require the whole data matrix in main memory. This is desirable for large data sets. More importantly, with the insertion of new data items, the IDR/QR algorithm can constrain the computational cost by applying efficient QR-updating techniques. Finally, we evaluate the effectiveness of the IDR/QR algorithm in terms of classification error rate on the reduced dimensional space. Our experiments on several real-world data sets reveal that the classification error rate achieved by the IDR/QR algorithm is very close to the best possible one achieved by other LDA-based algorithms. However, the IDR/QR algorithm has much less computational cost, especially when new data items are inserted dynamically.
Analytical view of business data
Authors: Adam Yeh, Jonathan Tang, Youxuan Jin, Sam Skrivan
Venue: KDD
Year: 2004

This paper describes a logical extension to Microsoft Business Framework (MBF) called Analytical View (AV). AV consists of three components: Model Service for design time, Business Intelligence Entity (BIE) for programming model, and IntellDrill for runtime navigation between OLTP and OLAP data sources. AV feature-set fulfills enterprise application requirements for Analysis and Decision Support, complementing the transactional feature-set currently provided by MBF. Model Service automatically transforms an "object oriented model (transactional view)" to a "multi-dimensional model (analytical view)" without the traditional Extraction/Transformation/Loading (ETL) overhead and complexity. It infers dimensionality from the object layer where richer metadata is stored, eliminating the "guesswork" that a traditional data warehousing process requires when going through physical database schema. BI Entities are classes code-generated by Model Service. As an intrinsic part of the framework, BI Entities enable a consistent object oriented way of programming model with strong types and rich semantics for OLAP, similar to what MBF object persistence technology does for OLTP data. More importantly, data contained in BI Entities have a higher degree of "application awareness," such as the integrated application level security and customizability. IntelliDrill links together all the information islands in MBF using metadata. Because of the automatic transformation from transactional view to analytical view enabled by Model Service, we have the ability to understand natively what kind of drill-ability an object would have, thus making information navigation in MBF fully discover-able with built-in ontology.
Density-based spam detector
Authors: Kenichi Yoshida, Fuminori Adachi, Takashi Washio, Hiroshi Motoda, Teruaki Homma, Akihiro Nakashima, Hiromitsu Fujikawa, Katsuyuki Yamazaki
Venue: KDD
Year: 2004

The volume of mass unsolicited electronic mail, often known as spam, has recently increased enormously and has become a serious threat to not only the Internet but also to society. This paper proposes a new spam detection method which uses document space density information. Although it requires extensive e-mail traffic to acquire the necessary information, an unsupervised learning engine with a short white list can achieve a 98% recall rate and 100% precision. A direct-mapped cache method contributes handling of over 13,000 e-mails per second. Experimental results, which were conducted using over 50 million actual e-mails of traffic, are also reported in this paper.
Redundancy based feature selection for microarray data
Authors: Lei Yu, Huan Liu
Venue: KDD
Year: 2004

In gene expression microarray data analysis, selecting a small number of discriminative genes from thousands of genes is an important problem for accurate classification of diseases or phenotypes. The problem becomes particularly challenging due to the large number of features (genes) and small sample size. Traditional gene selection methods often select the top-ranked genes according to their individual discriminative power without handling the high degree of redundancy among the genes. Latest research shows that removing redundant genes among selected ones can achieve a better representation of the characteristics of the targeted phenotypes and lead to improved classification accuracy. Hence, we study in this paper the relationship between feature relevance and redundancy and propose an efficient method that can effectively remove redundant genes. The efficiency and effectiveness of our method in comparison with representative methods has been demonstrated through an empirical study using public microarray data sets.
On the discovery of significant statistical quantitative rules
Authors: Hong Zhang, Balaji Padmanabhan, Alexander Tuzhilin
Venue: KDD
Year: 2004

In this paper we study market share rules, rules that have a certain market share statistic associated with them. Such rules are particularly relevant for decision making from a business perspective. Motivated by market share rules, in this paper we consider statistical quantitative rules (SQ rules) that are quantitative rules in which the RHS can be any statistic that is computed for the segment satisfying the LHS of the rule. Building on prior work, we present a statistical approach for learning all significant SQ rules, i.e., SQ rules for which a desired statistic lies outside a confidence interval computed for this rule. In particular we show how resampling techniques can be effectively used to learn significant rules. Since our method considers the significance of a large number of rules in parallel, it is susceptible to learning a certain number of "false" rules. To address this, we present a technique that can determine the number of significant SQ rules that can be expected by chance alone, and suggest that this number can be used to determine a "false discovery rate" for the learning procedure. We apply our methods to online consumer purchase data and report the results.
A data mining approach to modeling relationships among categories in image collection
Authors: Ruofei Zhang, Zhongfei (Mark) Zhang, Sandeep Khanzode
Venue: KDD
Year: 2004

This paper proposes a data mining approach to modeling relationships among categories in image collection. In our approach, with image feature grouping, a visual dictionary is created for color, texture, and shape feature attributes respectively. Labeling each training image with the keywords in the visual dictionary, a classification tree is built. Based on the statistical properties of the feature space we define a structure, called α-Semantics Graph, to discover the hidden semantic relationships among the semantic categories embodied in the image collection. With the α-Semantics Graph, each semantic category is modeled as a unique fuzzy set to explicitly address the semantic uncertainty and semantic overlap among the categories in the feature space. The model is utilized in the semantics-intensive image retrieval application. An algorithm using the classification accuracy measures is developed to combine the built classification tree with the fuzzy set modeling method to deliver semantically relevant image retrieval for a given query image. The experimental evaluations have demonstrated that the proposed approach models the semantic relationships effectively and the image retrieval prototype system utilizing the derived model is promising both in effectiveness and efficiency.
V-Miner: using enhanced parallel coordinates to mine product design and test data
Authors: Kaidi Zhao, Bing Liu, Thomas M. Tirpak, Andreas Schaller
Venue: KDD
Year: 2004

Analyzing data to find trends, correlations, and stable patterns is an important task in many industrial applications. This paper proposes a new technique based on parallel coordinate visualization. Previous work on parallel coordinate methods has shown that they are effective only when variables that are correlated and/or show similar patterns are displayed adjacently. Although current parallel coordinate tools allow the user to manually rearrange the order of variables, this process is very time-consuming when the number of variables is large. Automated assistance is required. This paper introduces an edit-distance based technique to rearrange variables so that interesting change patterns can be easily detected visually. The Visual Miner (V-Miner) software includes both automated methods for visualizing common patterns and a query tool that enables the user to describe specific target patterns to be mined or displayed by the system. In addition, the system can filter data according to rules sets imported from other data mining tools. This feature was found very helpful in practice, because it enables decision makers to visually identify interesting rules and data segments for further analysis or data mining. This paper begins with an introduction to the proposed techniques and the V-Miner system. Next, a case study illustrates how V-Miner has been used at Motorola to guide product design and test decisions.
A DEA approach for model combination
Authors: Zhiqiang (Eric) Zheng, Balaji Padmanabhan, Haoqiang Zheng
Venue: KDD
Year: 2004

This paper proposes a novel Data Envelopment Analysis (DEA) based approach for model combination. We first prove that for the 2-class classification problems DEA models identify the same convex hull as the popular ROC analysis used for model combination. For general k-class classifiers, we then develop a DEA-based method to combine multiple classifiers. Experiments show that the method outperforms other benchmark methods and suggest that DEA can be a promising tool for model combination.
The architecture of complexity: the structure and the dynamics of networks, from the web to the cell
Authors: Albert-László Barabási
Venue: KDD
Year: 2005

Networks with complex topology describe systems as diverse as the cell, the World Wide Web or the society. The emergence of most networks is driven by self-organizing processes that are governed by simple but generic laws. The analysis of the cellular network of various organisms shows that cells and complex man-made networks, such as the Internet or the world wide web, and many social and collaboration networks share the same large-scale topology. I will show that the scale-free topology of these complex webs have important consequences on their robustness against failures and attacks, with implications on drug design, the Internet's ability to survive attacks and failures, and the ability of ideas and innovations to spread on the network.
Integration of profile hidden Markov model output into association rule mining
Authors: Christopher Besemann, Anne Denton
Venue: KDD
Year: 2005

Scientific models typically depend on parameters. Preserving the parameter dependence of models in the pattern mining context opens up several applications. Within association rule mining (ARM), the choice of parameters can be studied with more flexibly then in traditional model building. Studying support, confidence, and other rule metrics as a function of model parameters allows conclusions on assumptions underlying the models. We present efficient techniques to handle multiple model output data sets at little more than the cost of one. We integrate output from hidden Markov models into the association rule mining framework, demonstrating the potential for frequent pattern mining in the field of scientific modeling and experimentation.
LIPED: HMM-based life profiles for adaptive event detection
Authors: Chien Chin Chen, Meng Chang Chen, Ming-Syan Chen
Venue: KDD
Year: 2005

In this paper, the proposed LIPED (LIfe Profile based Event Detection) employs the concept of life profiles to predict the activeness of event for effective event detection. A group of events with similar activeness patterns shares a life profile, modeled by a hidden Markov model. Considering the burst-and-diverse property of events, LIPED identifies the activeness status of event. As a result, LIPED balances the clustering precision and recall to achieve better F1 scores than other well known approaches evaluated on the official TDT1 corpus.