waashk/dblp huggingface dataset:
mining time-changing data streams. most statistical and machine-learning algorithms assume that the data is a random sample drawn from a stationary distribution. unfortunately, most of the large databases available for mining today violate this assumption. they were gathered over months or years, and the underlying processes generating them changed during this time, sometimes radically. although a number of algorithms have been proposed for learning time-changing concepts, they generally do not scale well to very large databases. in this paper we propose an efficient algorithm for mining decision trees from continuously-changing data streams, based on the ultra-fast vfdt decision tree learner. this algorithm, called cvfdt, stays current while making the most of old data by growing an alternative subtree whenever an old one becomes questionable, and replacing the old with the new when the new becomes more accurate. cvfdt learns a model which is similar in accuracy to the one that would be learned by reapplying vfdt to a moving window of examples every time a new example arrives, but with o(1) complexity per example, as opposed to o(w), where w is the size of the window. experiments on a set of large time-changing data streams demonstrate the utility of this approach.
eigenspace-based anomaly detection in computer systems. we report on an automated runtime anomaly detection method at the application layer of multi-node computer systems. although several network management systems are available in the market, none of them have sufficient capabilities to detect faults in multi-tier web-based systems with redundancy. we model a web-based system as a weighted graph, where each node represents a "service" and each edge represents a dependency between services. since the edge weights vary greatly over time, the problem we address is that of anomaly detection from a time sequence of graphs.in our method, we first extract a feature vector from the adjacency matrix that represents the activities of all of the services. the heart of our method is to use the principal eigenvector of the eigenclusters of the graph. then we derive a probability distribution for an anomaly measure defined for a time-series of directional data derived from the graph sequence. given a critical probability, the threshold value is adaptively updated using a novel online algorithm.we demonstrate that a fault in a web application can be automatically detected and the faulty services are identified without using detailed knowledge of the behavior of the system.
adaptive event detection with time-varying poisson processes. time-series of count data are generated in many different contexts, such as web access logging, freeway traffic monitoring, and security logs associated with buildings. since this data measures the aggregated behavior of individual human beings, it typically exhibits a periodicity in time on a number of scales (daily, weekly,etc.) that reflects the rhythms of the underlying human activity and makes the data appear non-homogeneous. at the same time, the data is often corrupted by a number of bursty periods of unusual behavior such as building events, traffic accidents, and so forth. the data mining problem of finding and extracting these anomalous events is made difficult by both of these elements. in this paper we describe a framework for unsupervised learning in this context, based on a time-varying poisson process model that can also account for anomalous events. we show how the parameters of this model can be learned from count time series using statistical estimation techniques. we demonstrate the utility of this model on two datasets for which we have partial ground truth in the form of known events, one from freeway traffic data and another from building access data, and show that the model performs significantly better than a non-probabilistic, threshold-based technique. we also describe how the model can be used to investigate different degrees of periodicity in the data, including systematic day-of-week and time-of-day effects, and make inferences about the detected events (e.g., popularity or level of attendance). our experimental results indicate that the proposed time-varying poisson model provides a robust and accurate framework for adaptively and autonomously learning how to separate unusual bursty events from traces of normal human activity.
solving regression problems with rule-based ensemble classifiers. we describe a lightweight learning method that induces an ensemble of decision-rule solutions for regression problems. instead of direct prediction of a continuous output variable, the method discretizes the variable by k-means clustering and solves the resultant classification problem. predictions on new examples are made by averaging the mean values of classes with votes that are close in number to the most likely class. we provide experimental evidence that this indirect approach can often yield strong results for many applications, generally outperforming direct approaches such as regression trees and rivaling bagged regression trees.
application of kernels to link analysis. the application of kernel methods to link analysis is explored. in particular, kandola et al.'s neumann kernels are shown to subsume not only the co-citation and bibliographic coupling relatedness but also kleinberg's hits importance. these popular measures of relatedness and importance correspond to the neumann kernels at the extremes of their parameter range, and hence these kernels can be interpreted as defining a spectrum of link analysis measures intermediate between co-citation/bibliographic coupling and hits. we also show that the kernels based on the graph laplacian, including the regularized laplacian and diffusion kernels, provide relatedness measures that overcome some limitations of co-citation relatedness. the property of these kernel-based link analysis measures is examined with a network of bibliographic citations. practical issues in applying these methods to real data are discussed, and possible solutions are proposed.
recommendation method for extending subscription periods. online stores providing subscription services need to extend user subscription periods as long as possible to increase their profits. conventional recommendation methods recommend items that best coincide with user's interests to maximize the purchase probability, which does not necessarily contribute to extend subscription periods. we present a novel recommendation method for subscription services that maximizes the probability of the subscription period being extended. our method finds frequent purchase patterns in the long subscription period users, and recommends items for a new user to simulate the found patterns. using survival analysis techniques, we efficiently extract information from the log data for finding the patterns. furthermore, we infer user's interests from purchase histories based on maximum entropy models, and use the interests to improve the recommendations. since a longer subscription period is the result of greater user satisfaction, our method benefits users as well as online stores. we evaluate our method using the real log data of an online cartoon distribution service for cell-phone in japan.
transforming data to satisfy privacy constraints. data on individuals and entities are being collected widely. these data can contain information that explicitly identifies the individual (e.g., social security number). data can also contain other kinds of personal information (e.g., date of birth, zip code, gender) that are potentially identifying when linked with other available data sets. data are often shared for business or legal reasons. this paper addresses the important issue of preserving the anonymity of the individuals or entities during the data dissemination process. we explore preserving the anonymity by the use of generalizations and suppressions on the potentially identifying portions of the data. we extend earlier works in this area along various dimensions. first, satisfying privacy constraints is considered in conjunction with the usage for the data being disseminated. this allows us to optimize the process of preserving privacy for the specified usage. in particular, we investigate the privacy transformation in the context of data mining applications like building classification and regression models. second, our work improves on previous approaches by allowing more flexible generalizations for the data. lastly, this is combined with a more thorough exploration of the solution space using the genetic algorithm framework. these extensions allow us to transform the data so that they are more useful for their intended purpose while satisfying the privacy constraints.
on detecting space-time clusters. detection of space-time clusters is an important function in various domains (e.g., epidemiology and public health). the pioneering work on the spatial scan statistic is often used as the basis to detect and evaluate such clusters. state-of-the-art systems based on this approach detect clusters with restrictive shapes that cannot model growth and shifts in location over time. we extend these methods significantly by using the flexible square pyramid shape to model such effects. a heuristic search method is developed to detect the most likely clusters using a randomized algorithm in combination with geometric shapes processing. the use of monte carlo methods in the original scan statistic formulation is continued in our work to address the multiple hypothesis testing issues. our method is applied to a real data set on brain cancer occurrences over a 19 year period. the cluster detected by our method shows both growth and movement which could not have been modeled with the simpler cylindrical shapes used earlier. our general framework can be extended quite easily to handle other flexible shapes for the space-time clusters.
a model for discovering customer value for e-content. there exists a huge demand for multimedia goods and services in the internet. currently available bandwidth speeds can support sale of downloadable content like cds, e-books, etc. as well as services like video-on-demand. in the future, such services will be prevalent in the internet. since costs are typically fixed, maximizing revenue can maximize profits. a primary determinant of revenue in such e-content markets is how much value the customers associate with the content. though marketing surveys are useful, they cannot adapt to the dynamic nature of the internet market. in this work, we examine how to learn customer valuations in close to real-time. our contributions in this paper are threefold: (1) we develop a probabilistic model to describe customer behavior, (2) we develop a framework for pricing e-content based on basic economic principles, and (3) we propose a price discovering algorithm that learns customer behavior parameters and suggests prices to an e-content provider. we validate our algorithm using simulations. our simulations indicate that our algorithm generates revenue close to the maximum expectation. further, they also indicate that the algorithm is robust to transient customer behavior.
privacy-preserving distributed k-means clustering over arbitrarily partitioned data. advances in computer networking and database technologies have enabled the collection and storage of vast quantities of data. data mining can extract valuable knowledge from this data, and organizations have realized that they can often obtain better results by pooling their data together. however, the collected data may contain sensitive or private information about the organizations or their customers, and privacy concerns are exacerbated if data is shared between multiple organizations.distributed data mining is concerned with the computation of models from data that is distributed among multiple participants. privacy-preserving distributed data mining seeks to allow for the cooperative computation of such models without the cooperating parties revealing any of their individual data items. our paper makes two contributions in privacy-preserving data mining. first, we introduce the concept of arbitrarily partitioned data, which is a generalization of both horizontally and vertically partitioned data. second, we provide an efficient privacy-preserving protocol for k-means clustering in the setting of arbitrarily partitioned data.
nomograms for visualizing support vector machines. we propose a simple yet potentially very effective way of visualizing trained support vector machines. nomograms are an established model visualization technique that can graphically encode the complete model on a single page. the dimensionality of the visualization does not depend on the number of attributes, but merely on the properties of the kernel. to represent the effect of each predictive feature on the log odds ratio scale as required for the nomograms, we employ logistic regression to convert the distance from the separating hyperplane into a probability. case studies on selected data sets show that for a technique thought to be a black-box, nomograms can clearly expose its internal structure. by providing an easy-to-interpret visualization the analysts can gain insight and study the effects of predictive factors.
dynamic, real-time forecasting of online auctions via functional models. we propose a dynamic model for forecasting price in online auctions. one of the key features of our model is that it operates during the live-auction, which makes it different from previous approaches that only consider static models. our model is also different with respect to how information about price is incorporated. while one part of the model is based on the more traditional notion of an auction's price-level, another part incorporates its dynamics in the form of a price's velocity and acceleration. in that sense, it incorporates key features of a dynamic environment such as an online auction. the use of novel functional data methodology allows us to measure, and subsequently include, dynamic price characteristics. we illustrate our model on a diverse set of ebay auctions across many different book categories. we find significantly higher prediction accuracy compared to standard approaches.
polynomial association rules with applications to logistic regression. a new class of associations (polynomial itemsets and polynomial association rules) is presented which allows for discovering nonlinear relationships between numeric attributes without discretization. for binary attributes, proposed associations reduce to classic itemsets and association rules. many standard association rule mining algorithms can be adapted to finding polynomial itemsets and association rules. we applied polynomial associations to add non-linear terms to logistic regression models. significant performance improvement was achieved over stepwise methods, traditionally used in statistics, with comparable accuracy.
interestingness of frequent itemsets using bayesian networks as background knowledge. the paper presents a method for pruning frequent itemsets based on background knowledge represented by a bayesian network. the interestingness of an itemset is defined as the absolute difference between its support estimated from data and from the bayesian network. efficient algorithms are presented for finding interestingness of a collection of frequent itemsets, and for finding all attribute sets with a given minimum interestingness. practical usefulness of the algorithms and their efficiency have been verified experimentally.
fast discovery of unexpected patterns in data, relative to a bayesian network. we consider a model in which background knowledge on a given domain of interest is available in terms of a bayesian network, in addition to a large database. the mining problem is to discover unexpected patterns: our goal is to find the strongest discrepancies between network and database. this problem is intrinsically difficult because it requires inference in a bayesian network and processing the entire, potentially very large, database. a sampling-based method that we introduce is efficient and yet provably finds the approximately most interesting unexpected patterns. we give a rigorous proof of the method's correctness. experiments shed light on its efficiency and practicality for large-scale bayesian networks and databases.
simrank: a measure of structural-context similarity. the problem of measuring "similarity" of objects arises in many applications, and many domain-specific measures have been developed, e.g., matching text across documents or computing overlap among item-sets. we propose a complementary approach, applicable in any domain with object-to-object relationships, that measures similarity of the structural context in which objects occur, based on their relationships with other objects. effectively, we compute a measure that says "two objects are similar if they are related to similar objects:" this general similarity measure, called simrank, is based on a simple and intuitive graph-theoretic model. for a given domain, simrank can be combined with other domain-specific similarity measures. we suggest techniques for efficient computation of simrank scores, and provide experimental results on two application domains showing the computational feasibility and effectiveness of our approach.
mining the space of graph properties. existing data mining algorithms on graphs look for nodes satisfying specific properties, such as specific notions of structural similarity or specific measures of link-based importance. while such analyses for predetermined properties can be effective in well-understood domains, sometimes identifying an appropriate property for analysis can be a challenge, and focusing on a single property may neglect other important aspects of the data. in this paper, we develop a foundation for mining the properties themselves. we present a theoretical framework defining the space of graph properties, a variety of mining queries enabled by the framework, techniques to handle the enormous size of the query space, and an experimental system called f-miner that demonstrates the utility and feasibility of property mining.
why collective inference improves relational classification. procedures for collective inference make simultaneous statistical judgments about the same variables for a set of related data instances. for example, collective inference could be used to simultaneously classify a set of hyperlinked documents or infer the legitimacy of a set of related financial transactions. several recent studies indicate that collective inference can significantly reduce classification error when compared with traditional inference techniques. we investigate the underlying mechanisms for this error reduction by reviewing past work on collective inference and characterizing different types of statistical models used for making inference in relational data. we show important differences among these models, and we characterize the necessary and sufficient conditions for reduced classification error based on experiments with real and simulated data.
information awareness: a prospective technical assessment. recent proposals to apply data mining systems to problems in law enforcement, national security, and fraud detection have attracted both media attention and technical critiques of their expected accuracy and impact on privacy. unfortunately, the majority of technical critiques have been based on simplistic assumptions about data, classifiers, inference procedures, and the overall architecture of such systems. we consider these critiques in detail, and we construct a simulation model that more closely matches realistic systems. we show how both the accuracy and privacy impact of a hypothetical system could be substantially improved, and we discuss the necessary and sufficient conditions for this improvement to be achieved. this analysis is neither a defense nor a critique of any particular system concept. rather, our model suggests alternative technical designs that could mitigate some concerns, but also raises more specific conditions that must be met for such systems to be both accurate and socially desirable.
playing hide-and-seek with correlations. we present a method for very high-dimensional correlation analysis. the method relies equally on rigorous search strategies and on human interaction. at each step, the method conservatively "shaves off" a fraction of the database tuples and attributes, so that most of the correlations present in the data are not affected by the decomposition. instead, the correlations become more obvious to the user, because they are hidden in a much smaller portion of the database. this process can be repeated iteratively and interactively, until only the most important correlations remain.the main technical difficulty of the approach is figuring out how to "shave off" part of the database so as to preserve most correlations. we develop an algorithm for this problem that has a polynomial running time and guarantees result quality.
generation of synthetic data sets for evaluating the accuracy of knowledge discovery systems. information discovery and analysis systems (idas) are designed to correlate multiple sources of data and use data mining techniques to identify potential significant events. application domains for idas are numerous and include the emerging area of homeland security.developing test cases for an idas requires background data sets into which hypothetical future scenarios can be overlaid. the idas can then be measured in terms of false positive and false negative error rates. obtaining the test data sets can be an obstacle due to both privacy issues and also the time and cost associated with collecting a diverse set of data sources.in this paper, we give an overview of the design and architecture of an idas data set generator (idsg) that enables a fast and comprehensive test of an idas. the idsg generates data using statistical and rule-based algorithms and also semantic graphs that represent interdependencies between attributes. a credit card transaction application is used to illustrate the approach.
cfi-stream: mining closed frequent itemsets in data streams. mining frequent closed itemsets provides complete and condensed information for non-redundant association rules generation. extensive studies have been done on mining frequent closed itemsets, but they are mainly intended for traditional transaction databases and thus do not take data stream characteristics into consideration. in this paper, we propose a novel approach for mining closed frequent itemsets over data streams. it computes and maintains closed itemsets online and incrementally, and can output the current closed frequent itemsets in real time based on users' specified thresholds. experimental results show that our proposed method is both time and space efficient, has good scalability as the number of transactions processed increases and adapts very rapidly to the change in data streams.
mining coherent gene clusters from gene-sample-time microarray data. extensive studies have shown that mining microarray data sets is important in bioinformatics research and biomedical applications. in this paper, we explore a novel type of gene-sample-time microarray data sets, which records the expression levels of various genes under a set of samples during a series of time points. in particular, we propose the mining of coherent gene clusters from such data sets. each cluster contains a subset of genes and a subset of samples such that the genes are coherent on the samples along the time series. the coherent gene clusters may identify the samples corresponding to some phenotypes (e.g., diseases), and suggest the candidate genes correlated to the phenotypes. we present two efficient algorithms, namely the sample-gene search and the gene-sample search, to mine the complete set of coherent gene clusters. we empirically evaluate the performance of our approaches on both a real microarray data set and synthetic data sets. the test results have shown that our approaches are both efficient and effective to find meaningful coherent gene clusters.