waashk/dblp huggingface dataset:
resource management for networked classifiers in distributed stream mining systems. networks of classifiers are capturing the attention of system and algorithmic researchers because they offer improved accuracy over single model classifiers, can be distributed over a network of servers for improved scalability, and can be adapted to available system resources. this work provides a principled approach for the optimized allocation of system resources across a networked chain of classifiers. we begin with an illustrative example of how complex classification tasks can be decomposed into a network of binary classifiers. we formally define a global performance metric by recursively collapsing the chain of classifiers into one combined classifier. the performance metric trades off the end-to-end probabilities of detection and false alarm, both of which depend on the resources allocated to each individual classifier. we formulate the optimization problem and present optimal resource allocation results for both simulated and state-of-the-art classifier chains operating on telephony data.
mining generalized graph patterns based on user examples. there has been a lot of recent interest in mining patterns from graphs. often, the exact structure of the patterns of interest is not known. this happens, for example, when molecular structures are mined to discover fragments useful as features in chemical compound classification task, or when web sites are mined to discover sets of web pages representing logical documents. such patterns are often generated from a few small subgraphs (cores), according to certain generalization rules (grs). we call such patterns "generalized patterns"(gps). while being structurally different, gps often perform the same function in the network. previously proposed approaches to mining gps either assumed that the cores and the grs are given, or that all interesting gps are frequent. these are strong assumptions, which often do not hold in practical applications. in this paper, we propose an approach to mining gps that is free from the above assumptions. given a small number of gps selected by the user, our algorithm discovers all gps similar to the user examples. first, a machine learning-style approach is used to find the cores. second, generalizations of the cores in the graph are computed to identify gps. evaluation on synthetic data, generated using real cores and grs from biological and web domains, demonstrates effectiveness of our approach.
corrective classification: classifier ensembling with corrective and diverse base learners. empirical studies on supervised learning have shown that ensembling methods lead to a model superior to the one built from a single learner under many circumstances [1], especially when learning from imperfect, such as biased or noise infected, information sources. in this paper, we provide a novel corrective classification (c2) design, which incorporates error detection, data cleansing and bootstrap sampling to construct base learners that constitute the classifier ensemble. the essential goal is to reduce noise impacts and eventually enhance the learners built from noise corrupted data. we further analyze the importance of both the accuracy and diversity of base learners in ensembling, in order to shed some light on the mechanism under which c2 works. experimental comparisons will demonstrate that c2 is not only superior to the learner built from the original noisy sources, but also more reliable than bagging [2] or the aggressive classifier ensemble (ace) [3], which are two degenerate components/variants of c2.
minimum enclosing spheres formulations for support vector ordinal regression. we present two new support vector approaches for ordinal regression. these approaches find the concentric spheres with minimum volume that contain most of the training samples. both approaches guarantee that the radii of the spheres are properly ordered at the optimal solution. the size of the optimization problem is linear in the number of training samples. the popularsmo algorithm is adapted to solve the resulting optimization problem. numerical experiments on some real-world data sets verify the usefulness of our approaches for data mining.
personalization in context: does context matter when building personalized customer models? the idea that context is important when predicting customer behavior has been maintained by scholars in marketing and data mining. however, no systematic study measuring how much the contextual information really matters in building customer models in personalization applications have been done before. in this paper, we address this problem. to this aim, we collected data containing rich contextual information by developing a special-purpose browser to help users to navigate a well-known e-commerce retail portal and purchase products on its site. the experimental results show that context does matter for the case of modeling behavior of individual customers. the granularity of contextual information also matters, and the effect of contextual information gets diluted during the process of aggregating customers' data.
bregman bubble clustering: a robust, scalable framework for locating multiple, dense regions in data. in traditional clustering, every data point is assigned to at least one cluster. on the other extreme, one class clustering algorithms proposed recently identify a single dense cluster and consider the rest of the data as irrelevant. however, in many problems, the relevant data forms multiple natural clusters. in this paper, we introduce the notion of bregman bubbles and propose bregman bubble clustering (bbc) that seeks k dense bregman bubbles in the data. we also present a corresponding generative model, soft bbc, and show several connections with bregman clustering, and with a one class clustering algorithm. empirical results on various datasets show the effectiveness of our method.
loci: load shedding through class-preserving data acquisition. an avalanche of data available in the stream form is overstretching our data analyzing ability. in this paper, we propose a novel load shedding method that enables fast and accurate stream data classification. we transform input data so that its class information concentrates on a few features, and we introduce a progressive classifier that makes prediction with partial input. we take advantage of stream data's temporal locality . for example, readings from a temperature sensor usually do not change dramatically over a short period of time . for load shedding. we first show that temporal locality of the original data is preserved by our transform, then we utilize positive and negative knowledge about the data (which is of much smaller size than the data itself) for classification. we employ both analytical and empirical analysis to demonstrate the advantage of our approach.
lazy associative classification. decision tree classifiers perform a greedy search for rules by heuristically selecting the most promising features. such greedy (local) search may discard important rules. associative classifiers, on the other hand, perform a global search for rules satisfying some quality constraints (i.e., minimum support). this global search, however, may generate a large number of rules. further, many of these rules may be useless during classification, and worst, important rules may never be mined. lazy (non-eager) associative classification overcomes this problem by focusing on the features of the given test instance, increasing the chance of generating more rules that are useful for classifying the test instance. in this paper we assess the performance of lazy associative classification. first we demonstrate that an associative classifier performs no worse than the corresponding decision tree classifier. also we demonstrate that lazy classifiers outperform the corresponding eager ones. our claims are empirically confirmed by an extensive set of experimental results. we show that our proposed lazy associative classifier is responsible for an error rate reduction of approximately 10% when compared against its eager counterpart, and for a reduction of 20% when compared against a decision tree classifier. a simple caching mechanism makes lazy associative classification fast, and thus improvements in the execution time are also observed.
how bayesians debug. manual debugging is expensive. and the high cost has motivated extensive research on automated fault lo- calization in both software engineering and data mining communities. fault localization aims at automatically locating likely fault locations, and hence assists manual debugging. a number of fault localization algorithms have been developed in recent years, which prove effec- tive when multiple failing and passing cases are avail- able. however, we notice what is more commonly en- countered in practice is the two-sample debugging prob- lem, where only one failing and one passing cases are available. this problem has been either overlooked or insufficiently tackled in previous studies. in this paper, we develop a new fault localization al- gorithm, named bayesdebug, which simulates some manual debugging principles through a bayesian ap- proach. different from existing approaches that base fault analysis on multiple passing and failing cases, bayesdebug only requires one passing and one failing cases. we reason about why bayesdebug fits the two- sample debugging problem and why other approaches do not. finally, an experiment with a real-world program grep-2.2 is conducted, which exemplifies the effective- ness of bayesdebug.
converting output scores from outlier detection algorithms into probability estimates. current outlier detection schemes typically output a numeric score representing the degree to which a given observation is an outlier. we argue that converting the scores into well-calibrated probability estimates is more favorable for several reasons. first, the probability estimates allow us to select the appropriate threshold for declaring outliers using a bayesian risk model. second, the probability estimates obtained from individual models can be aggregated to build an ensemble outlier detection framework. in this paper, we present two methods for transforming outlier scores into probabilities. the first approach assumes that the posterior probabilities follow a logistic sigmoid function and learns the parameters of the function from the distribution of outlier scores. the second approach models the score distributions as a mixture of exponential and gaussian probability functions and calculates the posterior probabilites via the bayes' rule. we evaluated the efficacy of both methods in the context of threshold selection and ensemble outlier detection. we also show that the calibration accuracy improves with the aid of some labeled examples.
margin: maximal frequent subgraph mining. the exponential number of possible subgraphsmakes the problem of frequent subgraph mining a challenge. the set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs, thus providing ample scope for pruning. margin is a maximal subgraph mining algorithm that moves among promising nodes of the search space along the "border" of the infrequent and frequent subgraphs. this drastically reduces the number of candidate patterns considered in the search space. experimental results validate the efficiency and utility of the technique proposed.
cluster analysis of time-series medical data based on the trajectory representation and multiscale comparison techniques. this paper presents a cluster analysis method for multi-dimensional time-series data on clinical laboratory examinatios. our method represents the time series of test results as trajectories in multidimensional space, and compares their structural similarity by using the multiscale comparison technique. it enables us to find the part-to-part correspondences between two trajectories, taking into account the relationships between different tests. the resultant dissimilarity can be further used with clustering algorithms for finding the groups of similar cases. the method was applied to the cluster analysis of albumin-platelet data in the chronic hepatitis dataset. the results denonstrated that it could form interesting groups of cases that have high correspondence to the fibrotic stages.
speedup clustering with hierarchical ranking. many clustering algorithms in particular hierarchical clustering algorithms do not scale-up well for large data-sets especially when using an expensive distance function. in this paper, we propose a novel approach to perform approximate clustering with high accuracy. we introduce the concept of a pairwise hierarchical ranking to efficiently determine close neighbors for every data object. empirical results on synthetic and real-life data show a speedup of up to two orders of magnitude over optics while maintaining a high accuracy and up to one order of magnitude over the previously proposed data bubbles method, which also tries to speedup optics by trading accuracy for speed.
a parameterized probabilistic model of network evolution for supervised link prediction. we introduce a new approach to the problem of link prediction for network structured domains, such as the web, social networks, and biological networks. our approach is based on the topological features of network structures, not on the node features. we present a novel parameterized probabilistic model of network evolution and derive an efficient incremental learning algorithm for such models, which is then used to predict links among the nodes. we show some promising experimental results using biological network data sets.
improving grouped-entity resolution using quasi-cliques. the entity resolution (er) problem, which identifies duplicate entities that refer to the same real world entity, is essential in many applications. in this paper, in particular, we focus on resolving entities that contain a group of related elements in them (e.g., an author entity with a list of citations, a singer entity with song list, or an intermediate result by group by sql query). such entities, named as grouped-entities, frequently occur in many applications. the previous approaches toward grouped-entity resolution often rely on textual similarity, and produce a large number of false positives. as a complementing technique, in this paper, we present our experience of applying a recently proposed graph mining technique, quasi-clique, atop conventional er solutions. our approach exploits contextual information mined from the group of elements per entity in addition to syntactic similarity. extensive experiments verify that our proposal improves precision and recall up to 83% when used together with a variety of existing er solutions, but never worsens them.
integrating features from different sources for music information retrieval. efficient and intelligent music information retrieval is a very important topic of the 21st century. with the ultimate goal of building personal music information retrieval systems, this paper studies the problem of identifying "similar" artists using both lyrics and acoustic data. in this paper, we present a clustering algorithm that integrates features from both sources to perform bimodal learning. the algorithm is tested on a data set consisting of 570 songs from 53 albums of 41 artists using artist similarity provided by all music guide. experimental results show that the accuracy of artist similarity classifiers can be significantly improved and that artist similarity can be efficiently identified.
semantic smoothing for model-based document clustering. a document is often full of class-independent "general" words and short of class-specific 'core" words, which leads to the difficulty of document clustering. we argue that both problems will be relieved after suitable smoothing of document models in agglomerative approaches and of cluster models in partitional approaches, and hence improve clustering quality. to the best of our knowledge, most model-based clustering approaches use laplacian smoothing to prevent zero probability while most similarity-based approaches employ the heuristic tf*idf scheme to discount the effect of "general" words. inspired by a series of statistical translation language model for text retrieval, we propose in this paper a novel smoothing method referred to as context-sensitive semantic smoothing for document clustering purpose. the comparative experiment on three datasets shows that model-based clustering approaches with semantic smoothing is effective in improving cluster quality.
anytime classification using the nearest neighbor algorithm with applications to stream mining. for many real world problems we must perform classification under widely varying amounts of computational resources. for example, if asked to classify an instance taken from a bursty stream, we may have from milliseconds to minutes to return a class prediction. for such problems an anytime algorithm may be especially useful. in this work we show how we can convert the ubiquitous nearest neighbor classifier into an anytime algorithm that can produce an instant classification, or if given the luxury of additional time, can utilize the extra time to increase classification accuracy. we demonstrate the utility of our approach with a comprehensive set of experiments on data from diverse domains.
stability region based expectation maximization for model-based clustering. in spite of the initialization problem, the expectation- maximization (em) algorithm is widely used for estimating the parameters in several data mining related tasks. most popular model-based clustering techniques might yield poor clusters if the parameters are not initialized properly. to reduce the sensitivity of initial points, a novel algorithm for learning mixture models from multivariate data is introduced in this paper. the proposed algorithm takes advantage of trust-tech (transformation under stability-retaining equilibra characterization) to compute neighborhood local maxima on likelihood surface using stability regions. basically, our method coalesces the advantages of the traditional em with that of the dynamic and geometric characteristics of the stability regions of the corresponding nonlinear dynamical system of the log-likelihood function. two phases namely, the em phase and the stability region phase, are repeated alternatively in the parameter space to achieve improvements in the maximum likelihood. though applied to gaussian mixtures in this paper, our technique can be easily generalized to any other parametric finite mixture model. the algorithm has been tested on both synthetic and real datasets and the improvements in the performance compared to other approaches are demonstrated. the robustness with respect to initialization is also illustrated experimentally.
similarity of temporal query logs based on arima model. a challenging issue faced by modern information retrieval is that of determining and satisfying users' requirements relying only on very short text queries. in this paper, we propose an algorithm to find out related queries based on auto-regressive integrated moving average (arima) model. first, we select and estimate arima model of the temporal query logs. and then each query is denoted by a sequence of coefficients. we use the correlation of arima coefficients as the similarity measurement. we call it as the arima temporal similarity (arima ts). this similarity describes how strongly two time series are linearly related. on the other hand, the arima model could also be treated as a dimensionality reduction procedure. it can save storage space for a large database of the query logs. in addition, arima model could be used as a tool to predict the trend of a query. the experimental results on two query logs of msn search engine 1 demonstrate that the proposed approach can achieve better similarity measurement efficiently.
enhancing text clustering using concept-based mining model. most of text mining techniques are based on word and/or phrase analysis of the text. the statistical analysis of a term (word or phrase) frequency captures the importance of the term within a document. however, to achieve a more accurate analysis, the underlying mining technique should indicate terms that capture the semantics of the text from which the importance of a term in a sentence and in the document can be derived. a new concept-based mining model that relies on the analysis of both the sentence and the document, rather than, the traditional analysis of the document dataset only is introduced. the proposed mining model consists of a concept-based analysis of terms and a concept-based similarity measure. the term which contributes to the sentence semantics is analyzed with respect to its importance at the sentence and document levels. the model can efficiently find significant matching terms, either words or phrases, of the documents according to the semantics of the text. the similarity between documents relies on a new concept-based similarity measure which is applied to the matching terms between documents. experiments using the proposed concept-based term analysis and similarity measure in text clustering are conducted. experimental results demonstrate that the newly developed concept-based mining model enhances the clustering quality of sets of documents substantially.
distances and (indefinite) kernels for sets of objects. the main disadvantage of most existing set kernels is that they are based on averaging, which might be inappropriate for problems where only specific elements of the two sets should determine the overall similarity. in this paper we propose a class of kernels for sets of vectors directly exploiting set distance measures and, hence, incorporating various semantics into set kernels and lending the power of regularization to learning in structural domains where natural distance functions exist. these kernels belong to two groups: (i) kernels in the proximity space induced by set distances and (ii) set distance substitution kernels (non-psd in general). we report experimental results which show that our kernels compare favorably with kernels based on averaging and achieve results similar to other state-of-the-art methods. at the same time our kernels systematically improve over the naive way of exploiting distances.
latent friend mining from blog data. the rapid growth of blog (also known as "weblog") data provides a rich resource for social community mining. in this paper, we put forward a novel research problem of mining the latent friends of bloggers based on the contents of their blog entries. latent friends are defined in this paper as people who share the similar topic distribution in their blogs. these people may not actually know each other, but they have the interest and potential to find each other out. three approaches are designed for latent friend detection. the first one, called cosine similarity-based method, determines the similarity between bloggers by calculating the cosine similarity between the contents of the blogs. the second approach, known as topic-based method, is based on the discovery of latent topics using a latent topic model and then calculating the similarity at the topic level. the third one is two-level similarity-based, which is conducted in two stages. in the first stage, an existing topic hierarchy is exploited to build a topic distribution for a blogger. then, in the second stage, a detailed similarity comparison is conducted for bloggers that are close in interest to each other which are discovered in the first stage. our experimental results show that both the topic-based and two-level similarity-based methods work well, and the last approach performs much better than the first two. in this paper, we give a detailed analysis of the advantages and disadvantages of different approaches.