waashk/dblp huggingface dataset:
succinct summarization of transactional databases: an overlapped hyperrectangle scheme. transactional data are ubiquitous. several methods, including frequent itemsets mining and co-clustering, have been proposed to analyze transactional databases. in this work, we propose a new research problem to succinctly summarize transactional databases. solving this problem requires linking the high level structure of the database to a potentially huge number of frequent itemsets. we formulate this problem as a set covering problem using overlapped hyperrectangles; we then prove that this problem and its several variations are np-hard. we develop an approximation algorithm hyper which can achieve a ln(k) + 1 approximation ratio in polynomial time. we propose a pruning strategy that can significantly speed up the processing of our algorithm. additionally, we propose an efficient algorithm to further summarize the set of hyperrectangles by allowing false positive conditions. a detailed study using both real and synthetic datasets shows the effectiveness and efficiency of our approaches in summarizing transactional databases.
microscopic evolution of social networks. we present a detailed study of network evolution by analyzing four large online social networks with full temporal information about node and edge arrivals. for the first time at such a large scale, we study individual node arrival and edge creation processes that collectively lead to macroscopic properties of networks. using a methodology based on the maximum-likelihood principle, we investigate a wide variety of network formation strategies, and show that edge locality plays a critical role in evolution of networks. our findings supplement earlier network models based on the inherently non-local preferential attachment. based on our observations, we develop a complete model of network evolution, where nodes arrive at a prespecified rate and select their lifetimes. each node then independently initiates edges according to a "gap" process, selecting a destination for each edge according to a simple triangle-closing model free of any parameters. we show analytically that the combination of the gap distribution with the node lifetime leads to a power law out-degree distribution that accurately reflects the true network in all four cases. finally, we give model parameter settings that allow automatic evolution and generation of realistic synthetic networks of arbitrary scale.
finding non-redundant, statistically significant regions in high dimensional data: a novel approach to projected and subspace clustering. projected and subspace clustering algorithms search for clusters of points in subsets of attributes. projected clustering computes several disjoint clusters, plus outliers, so that each cluster exists in its own subset of attributes. subspace clustering enumerates clusters of points in all subsets of attributes, typically producing many overlapping clusters. one problem of existing approaches is that their objectives are stated in a way that is not independent of the particular algorithm proposed to detect such clusters. a second problem is the definition of cluster density based on user-defined parameters, which makes it hard to assess whether the reported clusters are an artifact of the algorithm or whether they actually stand out in the data in a statistical sense. we propose a novel problem formulation that aims at extracting axis-parallel regions that stand out in the data in a statistical sense. the set of axis-parallel, statistically significant regions that exist in a given data set is typically highly redundant. therefore, we formulate the problem of representing this set through a reduced, non-redundant set of axis-parallel, statistically significant regions as an optimization problem. exhaustive search is not a viable solution due to computational infeasibility, and we propose the approximation algorithm statpc. our comprehensive experimental evaluation shows that statpc significantly outperforms existing projected and subspace clustering algorithms in terms of accuracy.
sail: summation-based incremental learning for information-theoretic clustering. information-theoretic clustering aims to exploit information theoretic measures as the clustering criteria. a common practice on this topic is so-called info-k-means, which performs k-means clustering with the kl-divergence as the proximity function. while expert efforts on info-k-means have shown promising results, a remaining challenge is to deal with high-dimensional sparse data. indeed, it is possible that the centroids contain many zero-value features for high-dimensional sparse data. this leads to infinite kl-divergence values, which create a dilemma in assigning objects to the centroids during the iteration process of k-means. to meet this dilemma, in this paper, we propose a summation-based incremental learning (sail) method for info-k-means clustering. specifically, by using an equivalent objective function, sail replaces the computation of the kl-divergence by the computation of the shannon entropy. this can avoid the zero-value dilemma caused by the use of the kl-divergence. our experimental results on various real-world document data sets have shown that, with sail as a booster, the clustering performance of k-means can be significantly improved. also, sail leads to quick convergence and a robust clustering performance on high-dimensional sparse data.
local peculiarity factor and its application in outlier detection. peculiarity oriented mining (pom), aiming to discover peculiarity rules hidden in a dataset, is a new data mining method. in the past few years, many results and applications on pom have been reported. however, there is still a lack of theoretical analysis. in this paper, we prove that the peculiarity factor (pf), one of the most important concepts in pom, can accurately characterize the peculiarity of data with respect to the probability density function of a normal distribution, but is unsuitable for more general distributions. thus, we propose the concept of local peculiarity factor (lpf). it is proved that the lpf has the same ability as the pf for a normal distribution and is the so-called µ-sensitive peculiarity description for general distributions. to demonstrate the effectiveness of the lpf, we apply it to outlier detection problems and give a new outlier detection algorithm called lpf-outlier. experimental results show that lpf-outlier is an effective outlier detection algorithm.
stream prediction using a generative model based on frequent episodes in event sequences. this paper presents a new algorithm for sequence prediction over long categorical event streams. the input to the algorithm is a set of target event types whose occurrences we wish to predict. the algorithm examines windows of events that precede occurrences of the target event types in historical data. the set of significant frequent episodes associated with each target event type is obtained based on formal connections between frequent episodes and hidden markov models (hmms). each significant episode is associated with a specialized hmm, and a mixture of such hmms is estimated for every target event type. the likelihoods of the current window of events, under these mixture models, are used to predict future occurrences of target events in the data. the only user-defined model parameter in the algorithm is the length of the windows of events used during model estimation. we first evaluate the algorithm on synthetic data that was generated by embedding (in varying levels of noise) patterns which are preselected to characterize occurrences of target events. we then present an application of the algorithm for predicting targeted user-behaviors from large volumes of anonymous search session interaction logs from a commercially-deployed web browser tool-bar.
fastanova: an efficient algorithm for genome-wide association study. studying the association between quantitative phenotype (such as height or weight) and single nucleotide polymorphisms (snps) is an important problem in biology. to understand underlying mechanisms of complex phenotypes, it is often necessary to consider joint genetic effects across multiple snps. anova (analysis of variance) test is routinely used in association study. important findings from studying gene-gene (snp-pair) interactions are appearing in the literature. however, the number of snps can be up to millions. evaluating joint effects of snps is a challenging task even for snp-pairs. moreover, with large number of snps correlated, permutation procedure is preferred over simple bonferroni correction for properly controlling family-wise error rate and retaining mapping power, which dramatically increases the computational cost of association study. in this paper, we study the problem of finding snp-pairs that have significant associations with a given quantitative phenotype. we propose an efficient algorithm, fastanova, for performing anova tests on snp-pairs in a batch mode, which also supports large permutation test. we derive an upper bound of snp-pair anova test, which can be expressed as the sum of two terms. the first term is based on single-snp anova test. the second term is based on the snps and independent of any phenotype permutation. furthermore, snp-pairs can be organized into groups, each of which shares a common upper bound. this allows for maximum reuse of intermediate computation, efficient upper bound estimation, and effective snp-pair pruning. consequently, fastanova only needs to perform the anova test on a small number of candidate snp-pairs without the risk of missing any significant ones. extensive experiments demonstrate that fastanova is orders of magnitude faster than the brute-force implementation of anova tests on all snp pairs.
categorizing and mining concept drifting data streams. mining concept drifting data streams is a defining challenge for data mining research. recent years have seen a large body of work on detecting changes and building prediction models from stream data, with a vague understanding on the types of the concept drifting and the impact of different types of concept drifting on the mining algorithms. in this paper, we first categorize concept drifting into two scenarios: loose concept drifting (lcd) and rigorous concept drifting (rcd), and then propose solutions to handle each of them separately. for lcd data streams, because concepts in adjacent data chunks are sufficiently close to each other, we apply kernel mean matching (kmm) method to minimize the discrepancy of the data chunks in the kernel space. such a minimization process will produce weighted instances to build classifier ensemble and handle concept drifting data streams. for rcd data streams, because genuine concepts in adjacent data chunks may randomly and rapidly change, we propose a new optimal weights adjustment (owa) method to determine the optimum weight values for classifiers trained from the most recent (up-to-date) data chunk, such that those classifiers can form an accurate classifier ensemble to predict instances in the yet-to-come data chunk. experiments on synthetic and real-world datasets will show that weighted instance approach is preferable when the concept drifting is mainly caused by the changing of the class prior probability; whereas the weighted classifier approach is preferable when the concept drifting is mainly triggered by the changing of the conditional probability.
asymmetric support vector machines: low false-positive learning under the user tolerance. many practical applications of classification require the classifier to produce a very low false-positive rate. although the support vector machine (svm) has been widely applied to these applications due to its superiority in handling high dimensional data, there are relatively little effort other than setting a threshold or changing the costs of slacks to ensure the low false-positive rate. in this paper, we propose the notion of asymmetric support vectormachine (asvm) that takes into account the false-positives and the user tolerance in its objective. such a new objective formulation allows us to raise the confidence in predicting the positives, and therefore obtain a lower chance of false-positives. we study the effects of the parameters in asvm objective and address some implementation issues related to the sequential minimal optimization (smo) to cope with large-scale data. an extensive simulation is conducted and shows that asvm is able to yield either noticeable improvement in performance or reduction in training time as compared to the previous arts.
quantitative evaluation of approximate frequent pattern mining algorithms. traditional association mining algorithms use a strict definition of support that requires every item in a frequent itemset to occur in each supporting transaction. in real-life datasets, this limits the recovery of frequent itemset patterns as they are fragmented due to random noise and other errors in the data. hence, a number of methods have been proposed recently to discover approximate frequent itemsets in the presence of noise. these algorithms use a relaxed definition of support and additional parameters, such as row and column error thresholds to allow some degree of "error" in the discovered patterns. though these algorithms have been shown to be successful in finding the approximate frequent itemsets, a systematic and quantitative approach to evaluate them has been lacking. in this paper, we propose a comprehensive evaluation framework to compare different approximate frequent pattern mining algorithms. the key idea is to select the optimal parameters for each algorithm on a given dataset and use the itemsets generated with these optimal parameters in order to compare different algorithms. we also propose simple variations of some of the existing algorithms by introducing an additional post-processing step. subsequently, we have applied our proposed evaluation framework to a wide variety of synthetic datasets with varying amounts of noise and a real dataset to compare existing and our proposed variations of the approximate pattern mining algorithms. source code and the datasets used in this study are made publicly available.
semi-supervised learning with data calibration for long-term time series forecasting. many time series prediction methods have focused on single step or short term prediction problems due to the inherent difficulty in controlling the propagation of errors from one prediction step to the next step. yet, there is a broad range of applications such as climate impact assessments and urban growth planning that require long term forecasting capabilities for strategic decision making. training an accurate model that produces reliable long term predictions would require an extensive amount of historical data, which are either unavailable or expensive to acquire. for some of these domains, there are alternative ways to generate potential scenarios for the future using computer-driven simulation models, such as global climate and traffic demand models. however, the data generated by these models are currently utilized in a supervised learning setting, where a predictive model trained on past observations is used to estimate the future values. in this paper, we present a semi-supervised learning framework for long-term time series forecasting based on hidden markov model regression. a covariance alignment method is also developed to deal with the issue of inconsistencies between historical and model simulation data. we evaluated our approach on data sets from a variety of domains, including climate modeling. our experimental results demonstrate the efficacy of the approach compared to other supervised learning methods for long-term time series forecasting.
tagmark: reliable estimations of rfid tags for business processes. radio frequency identification (rfid) promises optimization of commodity flows in all industry segments. but due to physical constraints, rfid technology cannot detect all rfid tags from an assembly of items. this poses problems when integrating rfid data with enterprise-backend systems for tasks like inventory management or shelf replenishment. in this paper we propose the tagmark method to accomplish this integration. tagmark targets at a retailer scenario, where it estimates the number of tagged items from samples like the sales history or the tags read by smart shelves. the problem is challenging because most existing estimation methods depend on assumptions that do not hold in typical rfid applications, e.g., static item sets, simple random samples, or the availability of samples with user-defined sizes. tagmark adapts mark-recapture-methods in order to provide guarantees for the accuracy of the estimation and bounds for the sample sizes. it can be implemented as a database extension, allowing seamless integration into existing enterprise backend systems. a study with rfid-equipped goods acknowledges that our approach is effective in realistic scenarios, and database experiments with up to 1,000,000 items confirm that it can be efficiently implemented. finally, we explore a broad range of extreme conditions that might stress tagmark, including a thief who knows the location of unread items.
partitioned logistic regression for spam filtering. naive bayes and logistic regression perform well in different regimes. while the former is a very simple generative model which is efficient to train and performs well empirically in many applications,the latter is a discriminative model which often achieves better accuracy and can be shown to outperform naive bayes asymptotically. in this paper, we propose a novel hybrid model, partitioned logistic regression, which has several advantages over both naive bayes and logistic regression. this model separates the original feature space into several disjoint feature groups. individual models on these groups of features are learned using logistic regression and their predictions are combined using the naive bayes principle to produce a robust final estimation. we show that our model is better both theoretically and empirically. in addition, when applying it in a practical application, email spam filtering, it improves the normalized auc score at 10% false-positive rate by 28.8% and 23.6% compared to naive bayes and logistic regression, when using the exact same training examples.
automatic record linkage using seeded nearest neighbour and support vector machine classification. the task of linking databases is an important step in an increasing number of data mining projects, because linked data can contain information that is not available otherwise, or that would require time-consuming and expensive collection of specific data. the aim of linking is to match and aggregate all records that refer to the same entity. one of the major challenges when linking large databases is the efficient and accurate classification of record pairs into matches and non-matches. while traditionally classification was based on manually-set thresholds or on statistical procedures, many of the more recently developed classification methods are based on supervised learning techniques. they therefore require training data, which is often not available in real world situations or has to be prepared manually, an expensive, cumbersome and time-consuming process. the author has previously presented a novel two-step approach to automatic record pair classification [6, 7]. in the first step of this approach, training examples of high quality are automatically selected from the compared record pairs, and used in the second step to train a support vector machine (svm) classifier. initial experiments showed the feasibility of the approach, achieving results that outperformed k-means clustering. in this paper, two variations of this approach are presented. the first is based on a nearest-neighbour classifier, while the second improves a svm classifier by iteratively adding more examples into the training sets. experimental results show that this two-step approach can achieve better classification results than other unsupervised approaches.
an integrated system for automatic customer satisfaction analysis in the services industry. text classification has matured well as a research discipline over the years. at the same time, business intelligence over databases has long been a source of insights for enterprises. with the growing importance of the services industry, customer relationship management and contact center operations have become very important. specifically, the voice of the customer and customer satisfaction (c-sat) have emerged as invaluable sources of insights about how an enterprise's products and services are percieved by customers. in this demonstration, we present the ibm technology to automate customer satisfaction analysis (itacs) system that combines text classification technology, and a business intelligence solution along with an interactive document labeling interface for automating c-sat analysis. this system has been successfully deployed in client accounts in large contact centers and can be extended to any services industry setting for analyzing unstructured text data. this demonstration will highlight the importance of intervention and interactivity in real-world text classification settings. we will point out unique research challenges in this domain regarding label-sets, measuring accuracy, and interpretability of results and we will discuss solutions and open questions.
multi-class cost-sensitive boosting with p-norm loss functions. we propose a family of novel cost-sensitive boosting methods for multi-class classification by applying the theory of gradient boosting to p-norm based cost functionals. we establish theoretical guarantees including proof of convergence and convergence rates for the proposed methods. our theoretical treatment provides interpretations for some of the existing algorithms in terms of the proposed family, including a generalization of the costing algorithm, dse and gbse-t, and the average cost method. we also experimentally evaluate the performance of our new algorithms against existing methods of cost sensitive boosting, including adacost, csb2, and adaboost.m2 with cost-sensitive weight initialization. we show that our proposed scheme generally achieves superior results in terms of cost minimization and, with the use of higher order p-norm loss in certain cases, consistently outperforms the comparison methods, thus establishing its empirical advantage.
scalable and near real-time burst detection from ecommerce queries. in large scale online systems like search, ecommerce, or social network applications, user queries represent an important dimension of activities that can be used to study the impact on the system, and even the business. in this paper, we describe how to detect, characterize and classify bursts in user queries in a large scale ecommerce system. we build upon the approaches discussed in kdd 2002 "bursty and hierarchical structure in streams" [3] and apply them to a high volume industrial context. we describe how to identify bursts on a near real-time basis, classify them, and apply them to build interesting merchandizing applications.
mining preferences from superior and inferior examples. mining user preferences plays a critical role in many important applications such as customer relationship management (crm), product and service recommendation, and marketing campaigns. in this paper, we identify an interesting and practical problem of mining user preferences: in a multidimensional space where the user preferences on some categorical attributes are unknown, from some superior and inferior examples provided by a user, can we learn about the user's preferences on those categorical attributes? we model the problem systematically and show that mining user preferences from superior and inferior examples is challenging. although the problem has great potential in practice, to the best of our knowledge, it has not been explored systematically before. as the first attempt to tackle the problem, we propose a greedy method and show that our method is practical using real data sets and synthetic data sets.