waashk/dblp huggingface dataset:
global and componentwise extrapolation for accelerating data mining from large incomplete data sets with the em algorithm. the expectation-maximization (em) algorithm is one of the most popular algorithms for data mining from incomplete data. however, when applied to large data sets with a large proportion of missing data, the em algorithm may converge slowly. the triple jump extrapolation method can effectively accelerate the em algorithm by substantially reducing the number of iterations required for em to converge. there are two options for the triple jump method, global extrapolation (tjem) and componentwise extrapolation (ctjem). we tried these two methods for a variety of probabilistic models and found that in general, global extraplolation yields a better performance, but there are cases where componentwise extrapolation yields very high speedup. in this paper, we investigate when componentwise extrapolation should be preferred. we conclude that, when the jacobian of the em mapping is diagonal or block diagonal, ctjem should be preferred. we show how to determine whether a jacobian is diagonal or block diagonal and experimentally confirm our claim. in particular, we show that ctjem is especially effective for the semi-supervised bayesian classifier model given a highly sparse data set.
latent dirichlet co-clustering. we present a generative model for simultaneously clustering documents and terms. our model is a four-level hierarchical bayesian model, in which each document is modeled as a random mixture of document topics , where each topic is a distribution over some segments of the text. each of these segments in the document can be modeled as a mixture of word topics where each topic is a distribution over words. we present efficient approximate inference techniques based on markov chain monte carlo method and a moment-matching algorithm for empirical bayes parameter estimation. we report results in document modeling, document and term clustering, comparing to other topic models, clustering and co-clustering algorithms including latent dirichlet allocation (lda), model-based overlapping clustering (moc), model-based overlapping co-clustering (mocc) and information-theoretic co-clustering (itcc).
adaptive parallel graph mining for cmp architectures. mining graph data is an increasingly popular challenge, which has practical applications in many areas, including molecular substructure discovery, web link analysis, fraud detection, and social network analysis. the problem statement is to enumerate all subgraphs occurring in at least \sigmagraphs of a database, where \sigmais a user specified parameter. chip multiprocessors (cmps) provide true parallel processing, and are expected to become the de facto standard for commodity computing. in this work, building on the state-of-the-art, we propose an efficient approach to parallelize such algorithms for cmps. we show that an algorithm which adapts its behavior based on the runtime state of the system can improve system utilization and lower execution times. most notably, we incorporate dynamic state management to allow memory consumption to vary based on availability. we evaluate our techniques on current day shared memory systems (smps) and expect similar performance for cmps. we demonstrate excellent speedup, 27- fold on 32 processors for several real world datasets. additionally, we show our dynamic techniques afford this scalability while consuming up to 35% less memory than static techniques.
co-clustering documents and words using bipartite isoperimetric graph partitioning. in this paper, we present a novel graph theoretic approach to the problem of document-word co-clustering. in our approach, documents and words are modeled as the two vertices of a bipartite graph. we then propose isoperimetric co-clustering algorithm (ica) - a new method for partitioning the document-word bipartite graph. ica requires a simple solution to a sparse system of linear equations instead of the eigenvalue or svd problem in the popular spectral co-clustering approach. our extensive experiments performed on publicly available datasets demonstrate the advantages of ica over spectral approach in terms of the quality, efficiency and stability in partitioning the document-word bipartite graph.
comparison of descriptor spaces for chemical compound retrieval and classification. in recent years the development of computational techniques that build models to correctly assign chemical compounds to various classes or to retrieve potential drug-like compounds has been an active area of research. many of the best-performing techniques for these tasks utilize a descriptor-based representation of the compound that captures various aspects of the underlying molecular graph's topology. in this paper we compare different set of descriptors that are currently used for chemical compound classification. in this process, we also introduce four different descriptors derived from all connected fragments present in the molecular graphs. in addition, we introduce an extension to existing vector-based kernel functions to take into account the length of the fragments present in the descriptors. we experimentally evaluate the performance of the previously introduced and the new descriptors in the context of svm-based classification and ranked-retrieval on 28 classification and retrieval problems derived from 18 datasets. our experiments show that for both these tasks, the new descriptors consistently and statistically outperform previously developed schemes based on the widely used fingerprint- and maccs keys-based descriptors, as well as recently introduced descriptors obtained by mining and analyzing the structure of the molecular graphs.
cluster based core vector machine. core vector machine(cvm) is suitable for efficient large-scale pattern classification. in this paper, a method for improving the performance of cvm with gaussian kernel function irrespective of the orderings of patterns belonging to different classes within the data set is proposed. this method employs a selective sampling based training of cvm using a novel kernel based scalable hierarchical clustering algorithm. empirical studies made on synthetic and real world data sets show that the proposed strategy performs well on large data sets.
efficient clustering of uncertain data. we study the problem of clustering data objects whose locations are uncertain. a data object is represented by an uncertainty region over which a probability density function (pdf) is defined. one method to cluster uncertain objects of this sort is to apply the uk-means algorithm, which is based on the traditional k-means algorithm. in uk-means, an object is assigned to the cluster whose representative has the smallest expected distance to the object. for arbitrary pdf, calculating the expected distance between an object and a cluster representative requires expensive integration computation. we study various pruning methods to avoid such expensive expected distance calculation.
relational ensemble classification. relational classification aims at including relations among entities, for example taking relations between documents such as a common author or citations into account. however, considering more than one relation can further improve classification accuracy. in this paper we introduce a new approach to make use of several relations as well as both relations and attributes for classification using ensemble methods. to accomplish this, we present a generic relational ensemble model, that can use different relational and local classifiers as components. furthermore, we discuss solutions for several problems concerning relational data such as heterogeneity, sparsity, and multiple relations. finally, we provide empirical evidence, that our relational ensemble methods outperform existing relational classification methods, even rather complex models such as relational probability trees (rpts), relational dependency networks (rdns) and relational bayesian classifiers (rbcs).
detection of interdomain routing anomalies based on higher-order path analysis. anomalous interdomain border gateway protocol (bgp) events including misconfigurations, attacks and large-scale power failures often affect the global routing infrastructure. thus, the ability to detect and categorize such events is extremely useful. in this article we present a novel anomaly detection technique for bgp that distinguishes between different anomalies in bgp traffic. this technique is termed higher order path analysis (hopa) and focuses on the discovery of patterns in higher order paths in supervised learning datasets. our results demonstrate that not only worm events but also different types of worms as well as blackout events are cleanly separable and can be classified in real time based on our incremental approach. this novel approach to supervised learning has potential applications in cybersecurity/forensics and text/data mining in general.
discovery of collocation episodes in spatiotemporal data. given a collection of trajectories of moving objects with different types (e.g., pumas, deers, vultures, etc.), we introduce the problem of discovering collocation episodes in them (e.g., if a puma is moving near a deer, then a vulture is also going to move close to the same deer with high probability within the next 3 minutes). collocation episodes catch the inter-movement regularities among different types of objects. we formally define the problem of mining collocation episodes and propose two scaleable algorithms for its efficient solution. we empirically evaluate the performance of the proposed methods using synthetically generated data that emulate real-world object movements.
linear and non-linear dimensional reduction via class representatives for text classification. we address the problem of building fast and effective text classification tools. we describe a "representatives methodology" related to feature extraction and illustrate its performance using as vehicles a centroid based method and a method based on clustered lsi that were recently proposed as useful tools for low rank matrix approximation and cost effective alternatives to lsi. the methodology is very flexible, providing the means for accelerating existing algorithms. it is also combined with kernel techniques to enable the analysis of data for which linear techniques are insufficient. numerous classification examples indicate that the proposed technique is effective and efficient with an overall performance superior than existing linear and nonlinear lsi-based approaches.
comparisons of k-anonymization and randomization schemes under linking attacks. recently k-anonymity has gained popularity as a privacy quantification against linking attacks, in which attackers try to identify a record with values of some identifying attributes. if attacks succeed, the identity of the record will be revealed and potential confidential information contained in other attributes of the record will be disclosed. k-anonymity counters this attack by requiring that each record must be indistinguishable from at least k -1 other records with respect to the identifying attributes. randomization can also be used for protection against linking attacks. in this paper, we compare the performance of k-anonymization and randomization schemes under linking attacks. we present a new privacy definition that can be applied to both k-anonymization and randomization. we compare these two schemes in terms of both utility and risks of privacy disclosure, and we promote to use r-u confidentiality map for such comparisons. we also compare various randomization schemes.
the pdd framework for detecting categories of peculiar data. peculiar data are objects that are relatively few in number and significantly different from the other objects in a data set. in this paper, we propose the pdd framework for detecting multiple categories of peculiar data. this framework provides an extensible set of perspectives for viewing data, currently including viewing data as a set of records, attributes, frequencies, intervals, sequences, or sequences of changes. by using these six views of the data, multiple categories of peculiar data can be detected to reveal different aspects of the data. for each view, the framework provides an extensible set of peculiarity measures to detect outliers and other kinds of peculiar data. the pdd framework has been implemented for oracle and access. experiments are reported for data sets concerning regina weather and nhl hockey.
discovering unrevealed properties of probability estimation trees: on algorithm selection and performance explanation. there has been increasing interest to design better probability estimation trees, or pets, for ranking and probability estimation. capable of generating class membership probabilities, pets have been shown to be highly accurate and flexible for many difficult problems, such as cost-sensitive learning and matching skewed distributions. there are a large number of pet algorithms available, and about ten of them are well-known. this large number provides an advantage, but it also creates confusion in practice. one would ask "given a new dataset, which algorithm to choose and what performance to expect and not to expect? what are the reasons to explain either good or bad performance under different situations?" in this paper, we systematically, for the first time, answer these important questions by conducting a large-scale empirical comparison of five popular pets by examining their auc, mse and error rate "learning curves" (instead of training-test split based cross-validation). using the maximum auc achieved by any of the evaluated probability estimation tree algorithms, we demonstrate that the preference of a probability estimation tree on different evaluation metrics can be accurately characterized by the "signal-noise separability" of the dataset, as well as some other observable statistics of the dataset explained further in the paper. moreover, in order to understand their relative performance, many important and previously unrevealed properties of each pet's mechanism and heuristics are analyzed and evaluated. importantly, a practical guide for choosing the most appropriate pet algorithm given a new data mining problem is provided.
newscats: a news categorization and trading system. newscats is an automated text categorization (atc) prototype using a hand-made thesaurus to forecast intraday stock price trends from information contained in press releases. due to a unique labeling approach and by carefully selecting the appropriate training data news- cats achieves a performance which is clearly superior to other atc prototypes used for stock price trend forecasting. in this paper we describe the architecture, training, and testing of newscats as well as the results of an extensive robustness analysis.
adaptive kernel principal component analysis with unsupervised learning of kernels. choosing an appropriate kernel is one of the key problems in kernel-based methods. most existing kernel selection methods require that the class labels of the training examples are known. in this paper, we propose an adaptive kernel selection method for kernel principal component analysis, which can effectively learn the kernels when the class labels of the training examples are not available. by iteratively optimizing a novel criterion, the proposed method can achieve nonlinear feature extraction and unsupervised kernel learning simultaneously. moreover, a noniterative approximate algorithm is developed. the effectiveness of the proposed algorithms are validated on uci datasets and the coil-20 object recognition database.
rapid identification of column heterogeneity. data quality is a serious concern in every data management application, and a variety of quality measures have been proposed, e.g., accuracy, freshness and completeness, to capture common sources of data quality degradation. we identify and focus attention on a novel measure, column heterogeneity, that seeks to quantify the data quality problems that can arise when merging data from different sources. we identify desiderata that a column heterogeneity measure should intuitively satisfy, and describe our technique to quantify database column heterogeneity based on using a novel combination of cluster entropy and soft clustering. finally, we present detailed experimental results, using diverse data sets of different types, to demonstrate that our approach provides a robust mechanism for identifying and quantifying database column heterogeneity.
accelerating newton optimization for log-linear models through feature redundancy. log-linear models are widely used for labeling feature vectors and graphical models, typically to estimate robust conditional distributions in presence of a large number of potentially redundant features. limited-memory quasi-newton methods like lbfgs or blmvm are optimization workhorses for such applications, and most of the training time is spent computing the objective and gradient for the optimizer. we propose a simple technique to speed up the training optimization by clustering features dynamically, and interleaving the standard optimizer with another, coarse-grained, faster optimizer that uses far fewer variables. experiments with logistic regression training for text classification and conditional random field (crf) training for information extraction show promising speed-ups between 2× and 9× without any systematic or significant degradation in the quality of the estimated models.
recommendation on item graphs. a novel scheme for item-based recommendation is proposed in this paper. in our framework, the items are described by an undirected weighted graph g = (v, e). v is the node set which is identical to the item set, and e is the edge set. associate with each edge e_ij \ine is a weight w_ij \geqslant0, which represents similarity between items i and j. without the loss of generality, we assume that any user's ratings to the items should be sufficiently smooth with respect to the intrinsic structure of the items, i.e., a user should give similar ratings to similar items. a simple algorithm is presented to achieve such a "smooth" solution. encouraging experimental results are provided to show the effectiveness of our method.
direct marketing when there are voluntary buyers. in traditional direct marketing, the implicit assumption is that customers will only purchase the product if they are contacted. in real business environments, however, there are "voluntary buyers," who will still make the purchase in the absence of a contact. while no direct promotion is needed for voluntary buyers, the traditional response-driven paradigm tends to target such customers. this paper presents "influential marketing," targeting only those whose purchase decisions can be positively influenced, i.e. buyers who are non-voluntary. our novel, practical solution to this problem gives promising results.
getting the most out of ensemble selection. we investigate four previously unexplored aspects of ensemble selection, a procedure for building ensembles of classifiers. first we test whether adjusting model predictions to put them on a canonical scale makes the ensembles more effective. second, we explore the performance of ensemble selection when different amounts of data are available for ensemble hillclimbing. third, we quantify the benefit of ensemble selection's ability to optimize to arbitrary metrics. fourth, we study the performance impact of pruning the number of models available for ensemble selection. based on our results we present improved ensemble selection methods that double the benefit of the original method.
the influence of class imbalance on cost-sensitive learning: an empirical study. in real-world applications the number of examples in one class may overwhelm the other class, but the primary interest is usually on the minor class. cost-sensitive learning has been deeded as a good solution to these class-imbalanced tasks, yet it is not clear how does the class-imbalance affect cost-sensitive classifiers. this paper presents an empirical study using 38 data sets, which discloses that class-imbalance often affects the performance of cost-sensitive classifiers: when the misclassification costs are not seriously unequal, cost-sensitive classifiers generally favor natural class distribution although it might be imbalanced; while when misclassification costs are seriously unequal, a balanced class distribution is more favorable.
fast random walk with restart and its applications. how closely related are two nodes in a graph? how to compute this score quickly, on huge, disk-resident, real graphs? random walk with restart (rwr) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the "connection subgraphs", personalized pagerank, and many more. however, the straightforward implementations of rwr do not scale for large graphs, requiring either quadratic space and cubic pre-computation time, or slow response time on queries. we propose fast solutions to this problem. the heart of our approach is to exploit two important properties shared by many real graphs: (a) linear correlations and (b) blockwise, community-like structure. we exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the sherman- morrison lemma for matrix inversion. experimental results on the corel image and the dblp dabasets demonstrate that our proposed methods achieve significant savings over the straightforward implementations: they can save several orders of magnitude in pre-computation and storage cost, and they achieve up to 150x speed up with 90%+ quality preservation.
gradual cube: customize profile on mobile olap. olap is supported by more and more environment as a powerful analysis tool. with the rapid development of mobile and wireless technologies, users wish to enjoy the olap service on these devices. however, there are many issues on mobile olap against the traditional ones, e.g. the transmission bottleneck, unstable network connection, etc. moreover, the mobile device owners have raised increasing requirements to customize the service such as transmitting the data on demand or asap to support their activities. all these challenges provide new chances for olap. in this paper, a new mechanism gradual cube is proposed to face such challenges. it can reduce the transmission data size, provide customized transmission strategy and enable users to conduct off-line browsing. we assume the users' precision requirement follows some distribution so that three methods, namely random, optimal and heuristic, are developed to customize the transmission plan. the experiments show that such methods are both effective and efficient.
boosting kernel models for regression. this paper proposes a general boosting framework for combining multiple kernel models in the context of both classification and regression problems. our main approach is built on the idea of gradient boosting together with a new regularization scheme and aims at reducing the cubic com- plexity of training kernel models. we focus mainly on using the proposed boosting framework to combine kernel ridge regression (krr) models for regression tasks. numerical experiments on four large-scale data sets have shown that boosting multiple small krr models is superior to training a single large krr model on both improving generalization performance and reducing computational requirements.