waashk/dblp huggingface dataset:
balancing spectral clustering for segmenting spatio-temporal observations of multi-agent systems. we examine the application of spectral clustering for breaking up the behavior of a multi-agent system in space and time into smaller, independent elements. we cluster observations of individualentities in order to identify significant changes in the parameter space (like spatial position)and detect temporal alterations of behavior within the same framework. data is also influenced byknowledge about important events. clusters are pre-processed at each step of the iterative subdivision to make the algorithm invariant against spatial scaling, rotation, replay speed andvarying sampling frequency. a method is presented to balance spatial and temporal segmentation based on the expected group size. we demonstrate our results by analyzing the outcomes of acomputer game.
seqstream: mining closed sequential patterns over stream sliding windows. previous studies have shown mining closed patterns provides more benefits than mining the complete set of frequent patterns, since closed pattern mining leads to more compact results and more efficient algorithms. it is quite useful in a data stream environment where memory and computation power are major concerns. this paper studies the problem of mining closed sequential patterns over data stream sliding windows. a synopsis structure ist (inverse closed sequence tree) is designed to keep inverse closed sequential patterns in current window. an efficient algorithm seqstream is developed to mine closed sequential patterns in stream windows incrementally, and various novel strategies are adopted in seqstream to prune search space aggressively. extensive experiments on both real and synthetic data sets show that seqstream outperforms prefixspan, clospan and bide by a factor of about one to two orders of magnitude.
on locally linear classification by pairwise coupling. locally linear classification by pairwise coupling addresses a nonlinear classification problem by three basic phases: decompose the classes of complex concepts into linearly separable subclasses, learn a linear classifier for each pair, and combine pairwise classifiers into a single classifier. a number of methods have been proposed in this framework. however, these methods have two major deficiencies: 1) lack of systematic evaluation of this framework; 2) naive application of clustering algorithms to generate subclasses. this paper proves the equivalence between three popular combination schemas under general settings, defines several global criterion functions for measuring the goodness of subclasses, and presents a supervised greedy clustering algorithm to optimize the proposed criterion functions. extensive experiments were conducted to validate the effectiveness of the proposed techniques.
interpreting pet scans by structured patient data: a data mining case study in dementia research. one of the goals of medical research in the area of dementia is to correlate images of the brain with other variables, for instance, demographic information or outcomes of clinical tests. the usual approach is to select a subset of patients based on such variables and analyze the images associated with those patients. in this paper, we apply data mining techniques to take the opposite approach: we start with the images and explain the differences and commonalities in terms of the other variables. in the first step, we cluster pet scans of patients to form groups sharing similar features in brain metabolism. to the best of our knowledge, it is the first time ever that clustering is applied to whole pet scans. in the second step, we explain the clusters by relating them to non-image variables. to do so, we employ rsd, an algorithm for relational subgroup discovery, with the cluster membership of patients as target variable. our results enable interesting interpretations of differences in brain metabolism in terms of demographic and clinical variables. the approach was implemented and tested on an exceptionally large pre-existing data collection of patients with different types of dementia. it comprises 10 gb of image data from 454 pet scans, and 42 variables from psychological and demographical data organized in 11 relations of a relational database. we believe that explaining medical images in terms of other variables (patient records, demographic information, etc.) is a challenging new and rewarding area for data mining research.
text cube: computing ir measures for multidimensional text database analysis. since jim gray introduced the concept of ”data cube” in 1997, data cube, associated with online analytical processing (olap), has become a driving engine in data warehouse industry. because the boom of internet has given rise to an ever increasing amount of text data associated with other multidimensional information, it is natural to propose a data cube model that integrates the power of traditional olap and ir techniques for text. in this paper, we propose a text-cube model on multidimensional text database and study effective olap over such data. two kinds of hierarchies are distinguishable inside: dimensional hierarchy and term hierarchy. by incorporating these hierarchies, we conduct systematic studies on efficient text-cube implementation, olap execution and query processing. our performance study shows the high promise of our methods.
clustering uncertain data using voronoi diagrams. we study the problem of clustering uncertain objects whose locations are described by probability density functions (pdf). we show that the uk-means algorithm, which generalises the k-means algorithm to handle uncertain objects, is very inefficient. the inefficiency comes from the fact that uk-means computes expected distances (ed) between objects and cluster representatives. for arbitrary pdf's, expected distances are computed by numerical integrations, which are costly operations. we propose pruning techniques that are based on voronoi diagrams to reduce the number of expected distance calculation. these techniques are analytically proven to be more effective than the basic bounding-box-based technique previous known in the literature. we conduct experiments to evaluate the effectiveness of our pruning techniques and to show that our techniques significantly outperform previous methods.
scs: a new similarity measure for categorical sequences. measuring the similarity between categorical sequences is a fundamental process in many data mining applications. a key issue is to extract and make use of significant features hidden behind the chronological and structural dependencies found in these sequences. almost all existing algorithms designed to perform this task are based on the matching of patterns in chronological order, but such sequences often have similar structural features in chronologically different positions. in this paper we propose scs, a novel method for measuring the similarity between categorical sequences, based on an original pattern matching scheme that makes it possible to capture chronological and non-chronological dependencies. scs captures significant patterns that represent the natural structure of sequences, and reduces the influence of those representing noise. it constitutes an effective approach for measuring the similarity of data such as biological sequences, natural language texts and financial transactions. to show its effectiveness, we have tested scs extensively on a range of datasets, and compared the results with those obtained by various mainstream algorithms.
direct zero-norm optimization for feature selection. zero-norm, defined as the number of non-zero elements in a vector, is an ideal quantity for feature selection. however, minimization of zero-norm is generally regarded as a combinatorially difficult optimization problem. in contrast to previous methods that usually optimize a surrogate of zero-norm, we propose a direct optimizationmethod to achieve zero-norm for feature selection in this paper. based on expectation maximization (em), this method boils down to solving a sequence of quadratic programming problems and hence can be practically optimized in polynomial time. we show that the proposed optimization technique has a nice bayesian interpretation and converges to the true zero norm asymptotically, provided that agood starting point is given. following the scheme of our proposed zero-norm, we even show that an arbitrary-norm based support vector machine can be achieved in polynomial time. a series of experiments demonstrate that our proposed em based zero-norm outperforms other state-of-the-art methods for feature selection on biological microarray data and uci data, in terms of both the accuracy and the learning efficiency.
support vector regression for censored data (svrc): a novel tool for survival analysis. a crucial challenge in predictive modeling for survival analysis is managing censored observations in the data. the cox proportional hazards model is the standard tool for the analysis of continuous censored survival data. we propose a novel machine learning algorithm, support vector regression for censored data (svrc) for improved analysis of medical survival data. svrc leverages the high-dimensional capabilities of traditional svr while adapting it for use with censored data through a modified asymmetric loss/penalty function which allows censored (left and right censored) data to be processed. we applied the new algorithm to predict the recurrence and disease progression of prostate cancer, breast cancer and lung cancer. compared with the traditional cox model, svrc achieves significant improvement in overall accuracy as well as in the ability to identify high-risk and low-risk patient populations.
mining large networks with subgraph counting. the problem of mining frequent patterns in networks has many applications, including analysis of complex networks, clustering of graphs, finding communities in social networks, and indexing of graphical and biological databases. despite this wealth of applications, the current state of the art lacks algorithmic tools for counting the number of subgraphs contained in a large network. in this paper we develop data-stream algorithms that approximate the number of all subgraphs of three and four vertices in directed and undirected networks. we use the frequency of occurrence of all subgraphs to prove their significance in order to characterize different kinds of networks: we achieve very good precision in clustering networks with similar structure. the significance of our method is supported by the fact that such high precision cannot be achieved when performing clustering based on simpler topological properties, such as degree, assortativity, and eigenvector distributions. we have also tested our techniques using swap randomization.
exploiting local and global invariants for the management of large scale information systems. this paper presents a data oriented approach to modeling the complex computing systems, in which an ensemble of correlation models are discovered to represent the system status. if the discovered correlations can continually hold under different user scenarios and workloads, they are regarded as invariants of the information system. in our previous work, we have developed an algorithm to automatically search the invariants between any pair of system attributes, which we call local invariants. however that method is unable to deal with the high order dependency models due to the combinatorial explosion of search space. in this paper we use bayesian regression technique to discover those high order correlation models, called global invariants. we treat each attribute as a response variable in turn and express its dependency with the other attributes in a regression model. by adding the prior constraint of laplacian distribution to the regression coefficients, we can find the solution in which only the correlated attributes with respect to the response have nonzero regression coefficients. after that we further consider the temporal dependencies of those extracted attributes by incorporating their past observations. we also provide a confidence metric and a validation procedure to measure the reliability of learned models. if the model does not break down in the validation, it is regarded as a true invariant of the system. experimental results on a real wireless networking system show that the discovered invariants can be used to effectively detect system failures as well as provide valuable information about the failure source.
collaborative filtering for implicit feedback datasets. a common task of recommender systems is to improve customer experience through personalized recommendations based on prior implicit feedback. these systems passively track different sorts of user behavior, such as purchase history, watching habits and browsing activity, in order to model user preferences. unlike the much more extensively researched explicit feedback, we do not have any direct input from the users regarding their preferences. in particular, we lack substantial evidence on which products consumer dislike. in this work we identify unique properties of implicit feedback datasets. we propose treating the data as indication of positive and negative preference associated with vastly varying confidence levels. this leads to a factor model which is especially tailored for implicit feedback recommenders. we also suggest a scalable optimization procedure, which scales linearly with the data size. the algorithm is used successfully within a recommender system for television shows. it compares favorably with well tuned implementations of other known methods. in addition, we offer a novel way to give explanations to recommendations given by this factor model.
collective latent dirichlet allocation. in this paper, we propose a new variant of latent dirichlet allocation (lda): collective lda (c-lda), for multiple corpora modeling. c-lda combines multiple corpora during learning such that it can transfer knowledge from one corpus to another; meanwhile it keeps a discriminative node which represents the corpus id to constrain the learned topics in each corpus. compared with lda locally applied to the target corpus, c-lda results in refined topic-word distribution, while compared with applying lda globally and straightforwardly to the combined corpus, c-lda keeps each topic only for one corpus. we demonstrate that c-lda has improved performance with these advantages by experiments on several benchmark document data sets.
alert detection in system logs. we present nodeinfo, an unsupervised algorithm for anomaly detection in system logs. we demonstrate nodeinfo's effectiveness on data from four of the world's most powerful supercomputers: using logs representing over 746 million processor-hours, in which anomalous events called alerts were manually tagged for scoring, we aim to automatically identify the regions of the log containing those alerts. we formalize the alert detection task in these terms, describe how nodeinfo uses the information entropy of message terms to identify alerts, and present an online version of this algorithm, which is now in production use. this is the first work to investigate alert detection on (several) publicly-available supercomputer system logs, thereby providing a reproducible performance baseline.
temporal-relational classifiers for prediction in evolving domains. many relational domains contain temporal information and dynamics that are important to model (e.g., social networks, protein networks). however, past work in relational learning has focused primarily on modeling static "snapshots" of the data and has largely ignored the temporal dimension of these data. in this work, we extend relational techniques to temporally-evolving domains and outline a representational framework that is capable of modeling both temporal and relational dependencies in the data. we develop efficient learning and inference techniques within the framework by considering a restricted set of temporal-relational dependencies and using parameter-tying methods to generalize across relationships and entities. more specifically, we model dynamic relational data with a two-phase process, first summarizing the temporal-relational information with kernel smoothing, and then moderating attribute dependencies with the summarized relational information. we develop a number of novel temporal-relational models using the framework and then show that the current approaches to modeling static relational data are special cases within the framework. we compare the new models to the competing static relational methods on three real-world datasets and show that the temporal-relational models consistently outperform the relational models that ignore temporal information - achieving significant reductions in error ranging from 15% to 70%.
on-line lda: adaptive topic models for mining text streams with applications to topic detection and tracking. this paper presents online topic model (olda), a topic model that automatically captures the thematic patterns and identifies emerging topics of text streams and their changes over time. our approach allows the topic modeling framework, specifically the latent dirichlet allocation (lda) model, to work in an online fashion such that it incrementally builds an up-to-date model (mixture of topics per document and mixture of words per topic) when a new document (or a set of documents) appears. a solution based on the empirical bayes method is proposed. the idea is to incrementally update the current model according to the information inferred from the new stream of data with no need to access previous data. the dynamics of the proposed approach also provide an efficient mean to track the topics over time and detect the emerging topics in real time. our method is evaluated both qualitatively and quantitatively using benchmark datasets. in our experiments, the olda has discovered interesting patterns by just analyzing a fraction of data at a time. our tests also prove the ability of olda to align the topics across the epochs with which the evolution of the topics over time is captured. the olda is also comparable to, and sometimes better than, the original lda in predicting the likelihood of unseen documents.
comparison of cluster representations from partial second- to full fourth-order cross moments for data stream clustering. under seven external clustering evaluation measures, a comparison is made for cluster representations from the partial second order to the fourth order in data stream clustering. two external clustering evaluation measures, purity and cross entropy, adopted for data stream clustering performance evaluation in the past, penalize the performance of an algorithm when each hypothesized cluster contains points in different target classes or true clusters, while ignoring the issue of points in a target class falling into different hypothesized clusters. the seven measures will address both sides of the clustering performance. the represented geometry by the partial second-order statistics of a cluster is non-oblique ellipsoidal and cannot describe the orientation, asymmetry, or peakedness of a cluster. the higher-order cluster representation presented in this paper introduces the third and fourth cross moments, enabling the cluster geometry to be beyond an ellipsoid. the higher-order statistics allow two clusters with different representations to merge into a multivariate normal cluster, using normality tests based on multivariate skewness and kurtosis. the clustering performance under the seven external clustering evaluation measures with a synthetic and two real data streams demonstrates the effectiveness of the higher-order cluster representations.
a generative probabilistic model for multi-label classification. traditional discriminative classification method makes little attempt to reveal the probabilistic structure and the correlation within both input and output spaces. in the scenario of multi-label classification, most of the classifiers simply assume the predefined classes are independently distributed, which would definitely hinder the classification performance when there are intrinsic correlations between the classes. in this article, we propose a generative probabilistic model, the correlated labeling model (col model), to formulate the correlation between different classes. the col model is presented to capture the correlation between classes and the underlying structures via the latent random variables in a supervised manner. we develop a variational procedure to approximate the posterior distribution and employ the em algorithm for the empirical bayes parameter estimation. in our evaluations, the proposed model achieved promising results on various data sets.
finding alternative clusterings using constraints. the aim of data mining is to find novel and actionable insights. however, most algorithms typically just find a single explanation of the data even though alternatives could exist. in this work, we explore a general purpose approach to find an alternative clustering of the data with the aid of must-link and cannot-link constraints. this problem has received little attention in the literature and since our approach can be incorporated into the many clustering algorithms that use a distance function, compares favorably with existing work.
releasing the svm classifier with privacy-preservation. support vector machine (svm) is a widely used tool in classification problem. svm solves a quadratic optimization problem to decide which instances of training dataset are support vectors, i.e., the necessarily informative instances to form the classifier. the support vectors are intact tuples taken from the training dataset. releasing the svm classifier to public use or shipping the svm classifier to clients will disclose the private content of support vectors, violating the privacy-preservation requirement in some legal or commercial reasons. to the best of our knowledge, there has not been work extending the notion of privacy-preservation to releasing the svm classifier. in this paper, we propose an approximation approach which post-processes the svm classifier to protect the private content of support vectors. this approach is designed for the commonly used gaussian radial basis function kernel. by applying this post-processor on the svm classifier, the resulted privacy-preserving svm classifier can be publicly released without exposing the private content of support vectors and is able to provide comparable classification accuracy to the original svm classifier.
learning by propagability. in this paper, we present a novel feature extraction framework, called learning by propagability. the whole learning process is driven by the philosophy that the data labels and optimal feature representation can constitute a harmonic system, namely, the data labels are invariant with respect to the propagation on the similarity-graph constructed by the optimal feature representation. based on this philosophy, a unified formulation for learning by propagability is proposed for both supervised and semi-supervised configurations. specifically, this formulation offers the semi-supervised learning two characteristics: 1) unlike conventional semi-supervised learning algorithms which mostly include at least two parameters, this formulation is parameter-free; and 2) the formulation unifies the label propagation and optimal representation pursuing, and thus the label propagation is enhanced by benefiting from the graph constructed with the derived optimal representation instead of the original representation. extensive experiments on uci toy data, handwritten digit recognition, and face recognition all validate the effectiveness of our proposed learning framework compared with the state-of-the-art methods for feature extraction and semi-supervised learning.