waashk/dblp huggingface dataset:
mining distance-based outliers in near linear time with randomization and a simple pruning rule. defining outliers by their distance to neighboring examples is a popular approach to finding unusual examples in a data set. recently, much work has been conducted with the goal of finding fast algorithms for this task. we show that a simple nested loop algorithm that in the worst case is quadratic can give near linear time performance when the data is in random order and a simple pruning rule is used. we test our algorithm on real high-dimensional data sets with millions of examples and show that the near linear scaling holds over several orders of magnitude. our average case analysis suggests that much of the efficiency is because the time to process non-outliers, which are the majority of examples, does not depend on the size of the data set.
towards systematic design of distance functions for data mining applications. distance function computation is a key subtask in many data mining algorithms and applications. the most effective form of the distance function can only be expressed in the context of a particular data domain. it is also often a challenging and non-trivial task to find the most effective form of the distance function. for example, in the text domain, distance function design has been considered such an important and complex issue that it has been the focus of intensive research over three decades. the final design of distance functions in this domain has been reached only by detailed empirical testing and consensus over the quality of results provided by the different variations. with the increasing ability to collect data in an automated way, the number of new kinds of data continues to increase rapidly. this makes it increasingly difficult to undertake such efforts for each and every new data type. the most important aspect of distance function design is that since a human is the end-user for any application, the design must satisfy the user requirements with regard to effectiveness. this creates the need for a systematic framework to design distance functions which are sensitive to the particular characteristics of the data domain. in this paper, we discuss such a framework. the goal is to create distance functions in an automated waywhile minimizing the work required from the user. we will show that this framework creates distance functions which are significantly more effective than popularly used functions such as the euclidean metric.
towards exploratory test instance specific algorithms for high dimensional classification. in an interactive classification application, a user may find it more valuable to develop a diagnostic decision support method which can reveal significant classification behavior of exemplar records. such an approach has the additional advantage of being able to optimize the decision process for the individual record in order to design more effective classification methods. in this paper, we propose the subspace decision path method which provides the user with the ability to interactively explore a small number of nodes of a hierarchical decision process so that the most significant classification characteristics for a given test instance are revealed. in addition, the sd-path method can provide enormous interpretability by constructing views of the data in which the different classes are clearly separated out. even in cases where the classification behavior of the test instance is ambiguous, the sd-path method provides a diagnostic understanding of the characteristics which result in this ambiguity. therefore, this method combines the abilities of the human and the computer in creating an effective diagnostic tool for instance-centered high dimensional classification.
on demand classification of data streams. current models of the classification problem do not effectively handle bursts of particular classes coming in at different times. in fact, the current model of the classification problem simply concentrates on methods for one-pass classification modeling of very large data sets. our model for data stream classification views the data stream classification problem from the point of view of a dynamic approach in which simultaneous training and testing streams are used for dynamic classification of data sets. this model reflects real life situations effectively, since it is desirable to classify test streams in real time over an evolving training and test stream. the aim here is to create a classification system in which the training model can adapt quickly to the changes of the underlying data stream. in order to achieve this goal, we propose an on-demand classification process which can dynamically select the appropriate window of past training data to build the classifier. the empirical results indicate that the system maintains a high classification accuracy in an evolving data stream, while providing an efficient solution to the classification task.
mining massively incomplete data sets by conceptual reconstruction. incomplete data sets have become almost ubiquitous in a wide variety of application domains. common examples can be found in climate and image data sets, sensor data sets and medical data sets. the incompleteness in these data sets may arise from a number of factors: in some cases it may simply be a reflection of certain measurements not being available at the time; in others the information may be lost due to partial system failure; or it may simply be a result of users being unwilling to specify attributes due to privacy concerns. when a significant fraction of the entries are missing in all of the attributes, it becomes very difficult to perform any kind of reasonable extrapolation on the original data. for such cases, we introduce the novel idea of conceptual reconstruction, in which we create effective conceptual representations on which the data mining algorithms can be directly applied. the attraction behind the idea of conceptual reconstruction is to use the correlation structure of the data in order to express it in terms of concepts rather the original dimensions. as a result, the reconstruction procedure estimates only those conceptual aspects of the data which can be mined from the incomplete data set, rather than force errors created by extrapolation. we demonstrate the effectiveness of the approach on a variety of real data sets.
frequent term-based text clustering. text clustering methods can be used to structure large sets of text or hypertext documents. the well-known methods of text clustering, however, do not really address the special problems of text clustering: very high dimensionality of the data, very large size of the databases and understandability of the cluster description. in this paper, we introduce a novel approach which uses frequent item (term) sets for text clustering. such frequent sets can be efficiently discovered using algorithms for association rule mining. to cluster based on frequent term sets, we measure the mutual overlap of frequent sets with respect to the sets of supporting documents. we present two algorithms for frequent term-based text clustering, ftc which creates flat clusterings and hftc for hierarchical clustering. an experimental evaluation on classical text documents as well as on web documents demonstrates that the proposed algorithms obtain clusterings of comparable quality significantly more efficiently than state-of-the- art text clustering algorithms. furthermore, our methods provide an understandable description of the discovered clusters by their frequent term sets.
on privacy preservation against adversarial data mining. privacy preserving data processing has become an important topic recently because of advances in hardware technology which have lead to widespread proliferation of demographic and sensitive data. a rudimentary way to preserve privacy is to simply hide the information in some of the sensitive fields picked by a user. however, such a method is far from satisfactory in its ability to prevent adversarial data mining. real data records are not randomly distributed. as a result, some fields in the records may be correlated with one another. if the correlation is sufficiently high, it may be possible for an adversary to predict some of the sensitive fields using other fields.in this paper, we study the problem of privacy preservation against adversarial data mining, which is to hide a minimal set of entries so that the privacy of the sensitive fields are satisfactorily preserved. in other words, even by data mining, an adversary still cannot accurately recover the hidden data entries. we model the problem concisely and develop an efficient heuristic algorithm which can find good solutions in practice. an extensive performance study is conducted on both synthetic and real data sets to examine the effectiveness of our approach.
a theoretical framework for learning from a pool of disparate data sources. many enterprises incorporate information gathered from a variety of data sources into an integrated input for some learning task. for example, aiming towards the design of an automated diagnostic tool for some disease, one may wish to integrate data gathered in many different hospitals. a major obstacle to such endeavors is that different data sources may vary considerably in the way they choose to represent related data. in practice, the problem is usually solved by a manual construction of semantic mappings and translations between the different sources. recently there have been attempts to introduce automated algorithms based on machine learning tools for the construction of such translations.in this work we propose a theoretical framework for making classification predictions from a collection of different data sources, without creating explicit translations between them. our framework allows a precise mathematical analysis of the complexity of such tasks, and it provides a tool for the development and comparison of different learning algorithms. our main objective, at this stage, is to demonstrate the usefulness of computational learning theory to this practically important area and to stimulate further theoretical and experimental research of questions related to this framework.
mining reference tables for automatic text segmentation. automatically segmenting unstructured text strings into structured records is necessary for importing the information contained in legacy sources and text collections into a data warehouse for subsequent querying, analysis, mining and integration. in this paper, we mine tables present in data warehouses and relational databases to develop an automatic segmentation system. thus, we overcome limitations of existing supervised text segmentation approaches, which require comprehensive manually labeled training data. our segmentation system is robust, accurate, and efficient, and requires no additional manual effort. thorough evaluation on real datasets demonstrates the robustness and accuracy of our system, with segmentation accuracy exceeding state of the art supervised approaches.
exploiting unlabeled data in ensemble methods. an adaptive semi-supervised ensemble method, assemble, is proposed that constructs classification ensembles based on both labeled and unlabeled data. assemble alternates between assigning "pseudo-classes" to the unlabeled data using the existing ensemble and constructing the next base classifier using both the labeled and pseudolabeled data. mathematically, this intuitive algorithm corresponds to maximizing the classification margin in hypothesis space as measured on both the labeled and unlabeled of data. unlike alternative approaches, assemble does not require a semi-supervised learning method for the base classifier. assemble can be used in conjunction with any cost-sensitive classification algorithm for both two-class and multi-class problems. assemble using decision trees won the nips 2001 unlabeled data competition. in addition, strong results on several benchmark datasets using both decision trees and neural networks support the proposed method.
identifying "best bet" web search results by mining past user behavior. the top web search result is crucial for user satisfaction with the web search experience. we argue that the importance of the relevance at the top position necessitates special handling of the top web search result for some queries. we propose an effective approach of leveraging millions of past user interactions with a web search engine to automatically detect "best bet" top results preferred by majority of users. interestingly, this problem can be more effectively addressed with classification than using state-of-the-art general ranking methods. furthermore, we show that our general machine learning approach achieves precision comparable to a heavily tuned, domain-specific algorithm, with significantly higher coverage. our experiments over millions of user interactions for thousands of queries demonstrate the effectiveness and robustness of our techniques.
applications of generalized support vector machines to predictive modeling. the work of the russian mathematician vladimir vapnik (at&t labs) enables us to go back to the roots of theoretical statistics, leaving behind fisher's parameters in favor of the general approaches started in the 1930s by glivenko-cantelli-kolmogorov. nowadays, it has become possible to model millions of events described by thousands of variables, within a reasonable time for a specific application. the srm approach works with a family of models and calibrates the family of models to a point which is the best compromise between accuracy and robustness. it also measures the complexity of the model using vc dimension which is not plagued by number of parameters. hence models for large events described by several parameters can be generalized. this opens up great prospects in numerous fields like customer relationship management, network optimization, risk management, manufacturing yield management, and a number of other data-rich problems.
mark: a boosting algorithm for heterogeneous kernel models. support vector machines and other kernel methods have proven to be very effective for nonlinear inference. practical issues are how to select the type of kernel including any parameters and how to deal with the computational issues caused by the fact that the kernel matrix grows quadratically with the data. inspired by ensemble and boosting methods like mart, we propose the multiple additive regression kernels (mark) algorithm to address these issues. mark considers a large (potentially infinite) library of kernel matrices formed by different kernel functions and parameters. using gradient boosting/column generation, mark constructs columns of the heterogeneous kernel matrix (the base hypotheses) on the fly and then adds them into the kernel ensemble. regularization methods such as used in svm, kernel ridge regression, and mart, are used to prevent overfitting. we investigate how mark is applied to heterogeneous kernel ridge regression. the resulting algorithm is simple to implement and efficient. kernel parameter selection is handled within mark. sampling and "weak" kernels are used to further enhance the computational efficiency of the resulting additive algorithm. the user can incorporate and potentially extract domain knowledge by restricting the kernel library to interpretable kernels. mark compares very favorably with svm and kernel ridge regression on several benchmark datasets.
recovering latent time-series from their observed sums: network tomography with particle filters. hidden variables, evolving over time, appear in multiple settings, where it is valuable to recover them, typically from observed sums. our driving application is 'network tomography', where we need to estimate the origin-destination (od) traffic flows to determine, e.g., who is communicating with whom in a local area network. this information allows network engineers and managers to solve problems in design, routing, configuration debugging, monitoring and pricing. unfortunately the direct measurement of the od traffic is usually difficult, or even impossible; instead, we can easily measure the loads on every link, that is, sums of desirable od flows.in this paper we propose i-filter, a method to solve this problem, which improves the state-of-the-art by (a) introducing explicit time dependence, and by (b) using realistic, non-gaussian marginals in the statistical models for the traffic flows, as never attempted before. we give experiments on real data, where i-filter scales linearly with new observations and out-performs the best existing solutions, in a wide variety of settings. specifically, on real network traffic measured at cmu, and at at&t, i-filter reduced the estimation errors between 15% and 46% in all cases.
a framework for analysis of dynamic social networks. finding patterns of social interaction within a population has wide-ranging applications including: disease modeling, cultural and information transmission, and behavioral ecology. social interactions are often modeled with networks. a key characteristic of social interactions is their continual change. however, most past analyses of social networks are essentially static in that all information about the time that social interactions take place is discarded. in this paper, we propose a new mathematical and computational framework that enables analysis of dynamic social networks and that explicitly makes use of information about when social interactions occur.
interactive training of advanced classifiers for mining remote sensing image archives. advances in satellite technology and availability of downloaded images constantly increase the sizes of remote sensing image archives. automatic content extraction, classification and content-based retrieval have become highly desired goals for the development of intelligent remote sensing databases. the common approach for mining these databases uses rules created by analysts. however, incorporating gis information and human expert knowledge with digital image processing improves remote sensing image analysis. we developed a system that uses decision tree classifiers for interactive learning of land cover models and mining of image archives. decision trees provide a promising solution for this problem because they can operate on both numerical (continuous) and categorical (discrete) data sources, and they do not require any assumptions about neither the distributions nor the independence of attribute values. this is especially important for the fusion of measurements from different sources like spectral data, dem data and other ancillary gis data. furthermore, using surrogate splits provides the capability of dealing with missing data during both training and classification, and enables handling instrument malfunctions or the cases where one or more measurements do not exist for some locations. quantitative and qualitative performance evaluation showed that decision trees provide powerful tools for modeling both pixel and region contents of images and mining of remote sensing image archives.
golden path analyzer: using divide-and-conquer to cluster web clickstreams. this paper describes a novel algorithm and deployed system golden path analyzer (gpa) that analyzes clickstreams of people trying to complete the same task on a website. it finds the shortest, successful paths taken by users - 'golden paths' - and uses these as seeds for clickstream clusters. other users are assigned to a cluster if their clickstream is a supersequence of the golden path. the advantages of this approach are that the resulting clusters are easily comprehended, they are few in number, correspond to semantically different strategies used by the users, and jointly partition all the clickstreams. gpa's key contribution over prior work in process funnels is that by not excluding users that make diversions from the golden path, gpa is able to assign more users to fewer clusters. another key contribution is to use actual full clickstreams as cluster seeds to which supersequences of other users are added. golden paths correspond to complete clickstreams that are based on actual user page transitions. gpa is particularly useful for site designers to improve processes such as shopping, returns and registration. its analyses identify which web pages cause many users to deviate from a golden path, which links distract users and the percentage of users taking each golden path. gpa has demonstrated value on more than twenty client projects in diverse industries.
interactive path analysis of web site traffic. the goal of path analysis is to understand visitors' navigation of a web site. the fundamental analysis component is a path. a path is a finite sequence of elements, typically representing urls or groups of urls. a full path is an abstraction of a visit or a session, which can contain attributes described below. subpaths represent interesting subsequences of the full paths.path analysis provides user-configurable extraction, filtering, preprocessing, noise reduction, descriptive statistics and detailed analysis of three basic specific objects: elements, (sub)paths, and couples of elements. in each case, lists of frequent objects --- subject to particular filtering and sorting --- are available. we call the corresponding interactive tools element, path, and couple analyzers.we also allow in-depth exploration of individual elements, paths, and couples: element explorer investigates composition and convergence of traffic through an element and allows conditioning based on the number of preceding/succeeding steps. path explorer visualizes in and out flows of a path and attrition rate along the path. couple explorer presents distinct paths connecting couple elements, along with measures of their association and some additional statistics.
tivo: making show recommendations using a distributed collaborative filtering architecture. we describe the tivo television show collaborative recommendation system which has been fielded in over one million tivo clients for four years. over this install base, tivo currently has approximately 100 million ratings by users over approximately 30,000 distinct tv shows and movies. tivo uses an item-item (show to show) form of collaborative filtering which obviates the need to keep any persistent memory of each user's viewing preferences at the tivo server. taking advantage of tivo's client-server architecture has produced a novel collaborative filtering system in which the server does a minimum of work and most work is delegated to the numerous clients. nevertheless, the server-side processing is also highly scalable and parallelizable. although we have not performed formal empirical evaluations of its accuracy, internal studies have shown its recommendations to be useful even for multiple user households. tivo's architecture also allows for throttling of the server so if more server-side resources become available, more correlations can be computed on the server allowing tivo to make recommendations for niche audiences.
integration of profile hidden markov model output into association rule mining. scientific models typically depend on parameters. preserving the parameter dependence of models in the pattern mining context opens up several applications. within association rule mining (arm), the choice of parameters can be studied with more flexibly then in traditional model building. studying support, confidence, and other rule metrics as a function of model parameters allows conclusions on assumptions underlying the models. we present efficient techniques to handle multiple model output data sets at little more than the cost of one. we integrate output from hidden markov models into the association rule mining framework, demonstrating the potential for frequent pattern mining in the field of scientific modeling and experimentation.