OpenRaiser/Intern-Atlas huggingface dataset:
New cached-sufficient statistics algorithms for quickly answering statistical questions
Authors: Andrew W. Moore
Venue: KDD
Year: 2006

This talk is about recent work on new ways to exploit preprocessed views of data tables for tractably solving big statistical queries. We'll describe deployments of these new algorithms in the realms of detecting killer asteroids and unnatural disease outbreaks.In recent years, several groups have looked at methods for pre-storing general sufficient statistics of the data in spatial data structures such as kd-trees and ball-trees so that both frequentist and Bayesian statistical operations become fast for large datasets. In this talk we will look at two other classes of optimization required in important statistical queries.The first involves iterating over all spatial regions (big and small). The second involves detection of tracks from noisy intermittent observations separated far apart in time and space. We will also discuss the implications that have arisen from making these operations tractable. We will focus particularly on
Algorithms for time series knowledge mining
Authors: Fabian Mörchen
Venue: KDD
Year: 2006

Temporal patterns composed of symbolic intervals are commonly formulated with Allen's interval relations originating in temporal reasoning. This representation has severe disadvantages for knowledge discovery. The Time Series Knowledge Representation (TSKR) is a new hierarchical language for interval patterns expressing the temporal concepts of coincidence and partial order. We present effective and efficient mining algorithms for such patterns based on itemset techniques. A novel form of search space pruning effectively reduces the size of the mining result to ease interpretation and speed up the algorithms. On a real data set a concise set of TSKR patterns can explain the underlying temporal phenomena, whereas the patterns found with Allen's relations are far more numerous yet only explain fragments of the data.
Understandable models Of music collections based on exhaustive feature generation with temporal statistics
Authors: Fabian Mörchen, Ingo Mierswa, Alfred Ultsch
Venue: KDD
Year: 2006

Data mining in large collections of polyphonic music has recently received increasing interest by companies along with the advent of commercial online distribution of music. Important applications include the categorization of songs into genres and the recommendation of songs according to musical similarity and the customer's musical preferences. Modeling genre or timbre of polyphonic music is at the core of these tasks and has been recognized as a difficult problem. Many audio features have been proposed, but they do not provide easily understandable descriptions of music. They do not explain why a genre was chosen or in which way one song is similar to another. We present an approach that combines large scale feature generation with meta learning techniques to obtain meaningful features for musical similarity. We perform exhaustive feature generation based on temporal statistics and train regression models to summarize a subset of these features into a single descriptor of a particular notion of music. Using several such models we produce a concise semantic description of each song. Genre classification models based on these semantic features are shown to be better understandable and almost as accurate as traditional methods.
Clustering based large margin classification: a scalable approach using SOCP formulation
Authors: J. Saketha Nath, Chiranjib Bhattacharyya, M. Narasimha Murty
Venue: KDD
Year: 2006

This paper presents a novel Second Order Cone Programming (SOCP) formulation for large scale binary classification tasks. Assuming that the class conditional densities are mixture distributions, where each component of the mixture has a spherical covariance, the second order statistics of the components can be estimated efficiently using clustering algorithms like BIRCH. For each cluster, the second order moments are used to derive a second order cone constraint via a Chebyshev-Cantelli inequality. This constraint ensures that any data point in the cluster is classified correctly with a high probability. This leads to a large margin SOCP formulation whose size depends on the number of clusters rather than the number of training data points. Hence, the proposed formulation scales well for large datasets when compared to the state-of-the-art classifiers, Support Vector Machines (SVMs). Experiments on real world and synthetic datasets show that the proposed algorithm outperforms SVM solvers in terms of training time and achieves similar accuracies.
Using structure indices for efficient approximation of network properties
Authors: Matthew J. Rattigan, Marc E. Maier, David D. Jensen
Venue: KDD
Year: 2006

Statistics on networks have become vital to the study of relational data drawn from areas such as bibliometrics, fraud detection, bioinformatics, and the Internet. Calculating many of the most important measures - such as betweenness centrality, closeness centrality, and graph diameter-requires identifying short paths in these networks. However, finding these short paths can be intractable for even moderate-size networks. We introduce the concept of a network structure index (NSI), a composition of (1) a set of annotations on every node in the network and (2) a function that uses the annotations to estimate graph distance between pairs of nodes. We present several varieties of NSIs, examine their time and space complexity, and analyze their performance on synthetic and real data sets. We show that creating an NSI for a given network enables extremely efficient and accurate estimation of a wide variety of network statistics on that network.
Self-Organizing wireless sensor networks in action
Authors: John A. Stankovic
Venue: KDD
Year: 2006

Wireless sensor networks (WSN) composed of large numbers of small devices that self-organize are being investigated for a wide variety of applications. Two key advantages of these networks over more traditional sensor networks are that they can be dynamically and quickly deployed, and that they can provide fine-grained sensing. Applications, such as emergency response to natural or manmade disasters, detection and tracking, and fine grained sensing of the environment are key examples of applications that can benefit from these types of WSN. Current research for these systems is widespread. However, many of the proposed solutions are developed with simplifying assumptions about wireless communication and the environment, even though the realities of wireless communication and environmental sensing are well known. Many of the solutions are evaluated only by simulation. In this talk I describe a fully implemented system consisting of a suite of more than 30 synthesized protocols. The system supports a power aware surveillance, tracking and classification application running on 203 XSM motes and evaluated in a realistic, large-area environment. Technical details and evaluations are presented. I end with a discussion of opportunities and problems for data mining related to WSN.
Acclimatizing taxonomic semantics for hierarchical content classification from semantics to data-driven taxonomy
Authors: Lei Tang, Jianping Zhang, Huan Liu
Venue: KDD
Year: 2006

Hierarchical models have been shown to be effective in content classification. However, we observe through empirical study that the performance of a hierarchical model varies with given taxonomies; even a semantically sound taxonomy has potential to change its structure for better classification. By scrutinizing typical cases, we elucidate why a given semantics-based hierarchy does not work well in content classification, and how it could be improved for accurate hierarchical classification. With these understandings, we propose effective localized solutions that modify the given taxonomy for accurate hierarchical classification. We conduct extensive experiments on both toy and real-world data sets, report improved performance and interesting findings, and provide further analysis of algorithmic issues such as time complexity, robustness, and sensitivity to the number of features.
Efficient kernel feature extraction for massive data sets
Authors: Ivor W. Tsang, András Kocsor, James T. Kwok
Venue: KDD
Year: 2006

Maximum margin discriminant analysis (MMDA) was proposed that uses the margin idea for feature extraction. It often outperforms traditional methods like kernel principal component analysis (KPCA) and kernel Fisher discriminant analysis (KFD). However, as in other kernel methods, its time complexity is cubic in the number of training points m, and is thus computationally inefficient on massive data sets. In this paper, we propose an (1 + ε) <sup>2</sup>-approximation algorithm for obtaining the MMDA features by extending the core vector machines. The resultant time complexity is only linear in m, while its space complexity is independent of m. Extensive comparisons with the original MMDA, KPCA, and KFD on a number of large data sets show that the proposed feature extractor can improve classification accuracy, and is also faster than these kernel-based methods by more than an order of magnitude.
Camouflaged fraud detection in domains with complex relationships
Authors: Sankar Virdhagriswaran, Gordon Dakin
Venue: KDD
Year: 2006

We describe a data mining system to detect frauds that are camouflaged to look like normal activities in domains with high number of known relationships. Examples include accounting fraud detection for rating and investment, insider attacks on corporate networks, and health care insurance fraud. Our goal is to help analysts who are overwhelmed with information about companies or on-line system access logs or insurance claims to focus their attentions on features that cause damage in the future. We focused on accounting fraud where the task is to detect the subset of companies that were potentially committing accounting fraud within the total population of public companies that file quarterly and annual filings with the Securities and Exchange Commission (SEC). Using (a) Representation of changes, (b) A mix of decision tree learning, locally weighted logistic regression, k-means clustering, and constant regression in a two phase pipe line, we developed models that rank companies based on the probability of forecasting future damaging performance. The learned models were tested extensively over four years with public data available from SEC filings and private data available from rating companies and investment firms. Cross validation experiments and analyst based validation of private experiments were found to show that the approach performed as well as or better than domain experts and discovered new relationships that domain experts did not use on a regular basis. Finally, the detections preceded public knowledge of such problems by six to eighteen months.
Summarizing itemset patterns using probabilistic models
Authors: Chao Wang, Srinivasan Parthasarathy
Venue: KDD
Year: 2006

In this paper, we propose a novel probabilistic approach to summarize frequent itemset patterns. Such techniques are useful for summarization, post-processing, and end-user interpretation, particularly for problems where the resulting set of patterns are huge. In our approach items in the dataset are modeled as random variables. We then construct a Markov Random Fields (MRF) on these variables based on frequent itemsets and their occurrence statistics. The summarization proceeds in a level-wise iterative fashion. Occurrence statistics of itemsets at the lowest level are used to construct an initial MRF. Statistics of itemsets at the next level can then be inferred from the model. We use those patterns whose occurrence can not be accurately inferred from the model to augment the model in an iterative manner, repeating the procedure until all frequent itemsets can be modeled. The resulting MRF model affords a concise and useful representation of the original collection of itemsets. Extensive empirical study on real datasets show that the new approach can effectively summarize a large number of itemsets and typically significantly outperforms extant approaches.
Suppressing model overfitting in mining concept-drifting data streams
Authors: Haixun Wang, Jian Yin, Jian Pei, Philip S. Yu, Jeffrey Xu Yu
Venue: KDD
Year: 2006

Mining data streams of changing class distributions is important for real-time business decision support. The stream classifier must evolve to reflect the current class distribution. This poses a serious challenge. On the one hand, relying on historical data may increase the chances of learning obsolete models. On the other hand, learning only from the latest data may lead to biased classifiers, as the latest data is often an unrepresentative sample of the current class distribution. The problem is particularly acute in classifying rare events, when, for example, instances of the rare class do not even show up in the most recent training data. In this paper, we use a stochastic model to describe the concept shifting patterns and formulate this problem as an optimization one: from the historical and the current training data that we have observed, find the most-likely current distribution, and learn a classifier based on the most-likely distribution. We derive an analytic solution and approximate this solution with an efficient algorithm, which calibrates the influence of historical data carefully to create an accurate classifier. We evaluate our algorithm with both synthetic and real-world datasets. Our results show that our algorithm produces accurate and efficient classification.
(alpha, k)-anonymity: an enhanced k-anonymity model for privacy preserving data publishing
Authors: Raymond Chi-Wing Wong, Jiuyong Li, Ada Wai-Chee Fu, Ke Wang
Venue: KDD
Year: 2006

Privacy preservation is an important issue in the release of data for mining purposes. The k-anonymity model has been introduced for protecting individual identification. Recent studies show that a more sophisticated model is necessary to protect the association of individuals to sensitive information. In this paper, we propose an (α, k)-anonymity model to protect both identifications and relationships to sensitive information in data. We discuss the properties of (α, k)-anonymity model. We prove that the optimal (α, k)-anonymity problem is NP-hard. We first presentan optimal global-recoding method for the (α, k)-anonymity problem. Next we propose a local-recoding algorithm which is more scalable and result in less data distortion. The effectiveness and efficiency are shown by experiments. We also describe how the model can be extended to more general case.
Incremental approximate matrix factorization for speeding up support vector machines
Authors: Gang Wu, Edward Y. Chang, Yen-Kuang Chen, Christopher J. Hughes
Venue: KDD
Year: 2006

Traditional decomposition-based solutions to Support Vector Machines (SVMs) suffer from the widely-known scalability problem. For example, given a one-million training set, it takes about six days for SVMLight to run on a Pentium-4 sever with 8G-byte memory. In this paper, we propose an incremental algorithm, which performs approximate matrix-factorization operations, to speed up SVMs. Two approximate factorization schemes, Kronecker and incomplete Cholesky, are utilized in the primal-dual interior-point method (IPM) to directly solve the quadratic optimization problem in SVMs. We found out that a coarse approximate algorithm enjoys good speedup performance but may suffer from poor training accuracy. Conversely, a fine-grained approximate algorithm enjoys good training quality but may suffer from long training time. We subsequently propose an incremental training algorithm, which uses the approximate IPM solution of a coarse factorization to initialize the IPM of a fine-grained factorization. Extensive empirical studies show that our proposed incremental algorithm with approximate factorizations substantially speeds up SVM training while maintaining high training accuracy. In addition, we show that our proposed algorithm is highly parallelizable on an Intel dual-coreprocessor.
Discovering interesting patterns through user's interactive feedback
Authors: Dong Xin, Xuehua Shen, Qiaozhu Mei, Jiawei Han
Venue: KDD
Year: 2006

In this paper, we study the problem of discovering interesting patterns through user’s interactive feedback. We assume a set of candidate patterns (i.e., frequent patterns) has already been mined. Our goal is to help a particular user effectively discover interesting patterns according to his specific interest. Without requiring a user to explicitly construct a prior knowledge to measure the interestingness of patterns, we learn the user’s prior knowledge from his interactive feedback. We propose two models to represent a user’s prior: the log-linear model and biased belief model. The former is designed for item-set patterns, whereas the latter is also applicable to sequential and structural patterns. To learn these models, we present a two-stage approach, progressive shrinking and clustering, to select sample patterns for feedback. The experimental results on real and synthetic data sets demonstrate the effectiveness of our approach.
K-means clustering versus validation measures: a data distribution perspective
Authors: Hui Xiong, Junjie Wu, Jian Chen
Venue: KDD
Year: 2006

K-means is a widely used partitional clustering method. While there are considerable research efforts to characterize the key features of K-means clustering, further investigation is needed to reveal whether and how the data distributions can have the impact on the performance of K-means clustering. Indeed, in this paper, we revisit the K-means clustering problem by answering three questions. First, how the "true" cluster sizes can make impact on the performance of K-means clustering? Second, is the entropy an algorithm-independent validation measure for K-means clustering? Finally, what is the distribution of the clustering results by K-means? To that end, we first illustrate that K-means tends to generate the clusters with the relatively uniform distribution on the cluster sizes. In addition, we show that the entropy measure, an external clustering validation measure, has the favorite on the clustering algorithms which tend to reduce high variation on the cluster sizes. Finally, our experimental results indicate that K-means tends to produce the clusters in which the variation of the cluster sizes, as measured by the Coefficient of Variation(CV), is in a specific range, approximately from 0.3 to 1.0.
Beyond classification and ranking: constrained optimization of the ROI
Authors: Lian Yan, Patrick Baldasare
Venue: KDD
Year: 2006

Classification has been commonly used in many data mining projects in the financial service industry. For instance, to predict collectability of accounts receivable, a binary class label is created based on whether a payment is received within a certain period. However, optimization of the classifier does not necessarily lead to maximization of return on investment (ROI), since maximization of the true positive rate is often different from maximization of the collectable amount which determines the ROI under a fixed budget constraint. The typical cost sensitive learning does not solve this problem either since it involves an unknown opportunity cost due to the budget constraint. Learning the ranks of collectable amount would ultimately solve the problem, but it tries to tackle an unnecessarily difficult problem and often results in poorer results for our specific target. We propose a new algorithm that uses gradient descent to directly optimize the related monetary measure under the budget constraint and thus maximizes the ROI. By comparison with several classification, regression, and ranking algorithms, we demonstrate the new algorithm's substantial improvement of the financial impact on our clients in the financial service industry.
Regularized discriminant analysis for high dimensional, low sample size data
Authors: Jieping Ye, Tie Wang
Venue: KDD
Year: 2006

Linear and Quadratic Discriminant Analysis have been used widely in many areas of data mining, machine learning, and bioinformatics. Friedman proposed a compromise between Linear and Quadratic Discriminant Analysis, called Regularized Discriminant Analysis (RDA), which has been shown to be more flexible in dealing with various class distributions. RDA applies the regularization techniques by employing two regularization parameters, which are chosen to jointly maximize the classification performance. The optimal pair of parameters is commonly estimated via cross-validation from a set of candidate pairs. It is computationally prohibitive for high dimensional data, especially when the candidate set is large, which limits the applications of RDA to low dimensional data.In this paper, a novel algorithm for RDA is presented for high dimensional data. It can estimate the optimal regularization parameters from a large set of parameter candidates efficiently. Experiments on a variety of datasets confirm the claimed theoretical estimate of the efficiency, and also show that, for a properly chosen pair of regularization parameters, RDA performs favorably in classification, in comparison with other existing classification methods.
Integration of semantic-based bipartite graph representation and mutual refinement strategy for biomedical literature clustering
Authors: Illhoi Yoo, Xiaohua Hu, Il-Yeol Song
Venue: KDD
Year: 2006

We introduce a novel document clustering approach that overcomes those problems by combining a semantic-based bipartite graph representation and a mutual refinement strategy. The primary contributions of this paper are the following. First, we introduce a new representation of documents using a bipartite graph between documents and co-occurrence concepts in the documents. Second, we show how to enhance clustering quality by applying the mutual refinement strategy to the initial clustering results. Third, through the experiments on MEDLINE documents, we show that our integrated method significantly enhances cluster quality and clustering reliability compared to existing clustering methods. Our approach improves on the average 29.5 cluster quality and 26.3 clustering reliability, in terms of misclassification index, over Bisecting K-means with the best parameters.
Supervised probabilistic principal component analysis
Authors: Shipeng Yu, Kai Yu, Volker Tresp, Hans-Peter Kriegel, Mingrui Wu
Venue: KDD
Year: 2006

Principal component analysis (PCA) has been extensively applied in data mining, pattern recognition and information retrieval for unsupervised dimensionality reduction. When labels of data are available, e.g., in a classification or regression task, PCA is however not able to use this information. The problem is more interesting if only part of the input data are labeled, i.e., in a semi-supervised setting. In this paper we propose a supervised PCA model called SPPCA and a semi-supervised PCA model called S2PPCA, both of which are extensions of a probabilistic PCA model. The proposed models are able to incorporate the label information into the projection phase, and can naturally handle multiple outputs (i.e., in multi-task learning problems). We derive an efficient EM learning algorithm for both models, and also provide theoretical justifications of the model behaviors. SPPCA and S2PPCA are compared with other supervised projection methods on various learning tasks, and show not only promising performance but also good scalability.