waashk/dblp huggingface dataset:
outlier detection by active learning. most existing approaches to outlier detection are based on density estimation methods. there are two notable issues with these methods: one is the lack of explanation for outlier flagging decisions, and the other is the relatively high computational requirement. in this paper, we present a novel approach to outlier detection based on classification, in an attempt to address both of these issues. our approach isbased on two key ideas. first, we present a simple reduction of outlier detection to classification, via a procedure that involves applying classification to a labeled data set containing artificially generated examples that play the role of potential outliers. once the task has been reduced to classification, we then invoke a selective sampling mechanism based on active learning to the reduced classification problem. we empirically evaluate the proposed approach using a number of data sets, and find that our method is superior to other methods based on the same reduction to classification, but using standard classification methods. we also show that it is competitive to the state-of-the-art outlier detection methods in the literature based on density estimation, while significantly improving the computational complexity and explanatory power.
model-based overlapping clustering. while the vast majority of clustering algorithms are partitional, many real world datasets have inherently overlapping clusters. several approaches to finding overlapping clusters have come from work on analysis of biological datasets. in this paper, we interpret an overlapping clustering model proposed by segal et al. [23] as a generalization of gaussian mixture models, and we extend it to an overlapping clustering model based on mixtures of any regular exponential family distribution and the corresponding bregman divergence. we provide the necessary algorithm modifications for this extension, and present results on synthetic data as well as subsets of 20-newsgroups and eachmovie datasets.
outlier detection by sampling with accuracy guarantees. an effective approach to detecting anomalous points in a data set is distance-based outlier detection. this paper describes a simple sampling algorithm to effciently detect distance-based outliers in domains where each and every distance computation is very expensive. unlike any existing algorithms, the sampling algorithm requires a xed number of distance computations and can return good results with accuracy guarantees. the most computationally expensive aspect of estimating the accuracy of the result is sorting all of the distances computed by the sampling algorithm. the experimental study on two expensive domains as well as ten additional real-life datasets demonstrates both the effciency and effectiveness of the sampling algorithm in comparison with the state-of-the-art algorithm and there liability of the accuracy guarantees.
an objective evaluation criterion for clustering. we propose and test an objective criterion for evaluation of clustering performance: how well does a clustering algorithm run on unlabeled data aid a classification algorithm? the accuracy is quantified using the pac-mdl bound [3] in a semisupervised setting. clustering algorithms which naturally separate the data according to (hidden) labels with a small number of clusters perform well. a simple extension of the argument leads to an objective model selection method. experimental results on text analysis datasets demonstrate that this approach empirically results in very competitive bounds on test set performance on natural datasets.
deriving quantitative models for correlation clusters. correlation clustering aims at grouping the data set into correlation clusters such that the objects in the same cluster exhibit a certain density and are all associated to a common arbitrarily oriented hyperplane of arbitrary dimensionality. several algorithms for this task have been proposed recently. however, all algorithms only compute the partitioning of the data into clusters. this is only a first step in the pipeline of advanced data analysis and system modelling. the second (post-clustering) step of deriving a quantitative model for each correlation cluster has not been addressed so far. in this paper, we describe an original approach to handle this second step. we introduce a general method that can extract quantitative information on the linear dependencies within a correlation clustering. our concepts are independent of the clustering model and can thus be applied as a post-processing step to any correlation clustering algorithm. furthermore, we show how these quantitative models can be used to predict the probability distribution that an object is created by these models. our broad experimental evaluation demonstrates the beneficial impact of our method on several applications of significant practical importance.
data mining case study: modeling the behavior of offenders who commit serious sexual assaults. this paper looks at the use of a self organizing map (som), to link of records of crimes of serious sexual attacks. once linked a profile can be derived of the offender(s) responsible.the data was drawn from the major crimes database at the national crime faculty of the national police staff college bramshill uk. the data was encoded from text by a small team of specialists working to a well-defined protocol. the encoded data was analyzed using soms. two exercises were conducted. these resulted in the linking of several offences in to clusters each of which were sufficiently similar to have possibly been committed by the same offender(s). a number of clusters were used to form profiles of offenders. some of these profiles were confirmed by independent analysts as either belonging to known offenders or appeared sufficiently interesting to warrant further investigation.the prototype was developed over 10 weeks. this contrasts with an in-house study using a conventional approach, which took 2 years to reach similar results. as a consequence of this study the ncf intends to pursue an in-depth follow up study.
extracting decision trees from trained neural networks. neural networks are successful in acquiring hidden knowledge in datasets. their biggest weakness is that the knowledge they acquire is represented in a form not understandable to humans. researchers tried to address this problem by extracting rules from trained neural networks. most of the proposed rule extraction methods required specialized type of neural networks; some required binary inputs and some were computationally expensive. craven proposed extracting mofn type decision trees from neural networks. we believe mofn type decision trees are only good for mofn type problems and trees created for regular high dimensional real world problems may be very complex. in this paper, we introduced a new method for extracting regular c4.5 like decision trees from trained neural networks. we showed that the new method (dectext) is effective in extracting high fidelity trees from trained networks. we also introduced a new discretization technique to make dectext be able to handle continuous features and a new pruning technique for finding simplest tree with the highest fidelity.
global distance-based segmentation of trajectories. this work introduces distance-based criteria for segmentation of object trajectories. segmentation leads to simplification of the original objects into smaller, less complex primitives that are better suited for storage and retrieval purposes. previous work on trajectory segmentation attacked the problem locally, segmenting separately each trajectory of the database. therefore, they did not directly optimize the inter-object separability, which is necessary for mining operations such as searching, clustering, and classification on large databases. in this paper we analyze the trajectory segmentation problem from a global perspective, utilizing data aware distance-based optimization techniques, which optimize pairwise distance estimates hence leading to more efficient object pruning. we first derive exact solutions of the distance-based formulation. due to the intractable complexity of the exact solution, we present anapproximate, greedy solution that exploits forward searching of locally optimal solutions. since the greedy solution also imposes a prohibitive computational cost, we also put forward more light weight variance-based segmentation techniques, which intelligently "relax" the pairwise distance only in the areas that affect the least the mining operation.
detecting outliers using transduction and statistical testing. outlier detection can uncover malicious behavior in fields like intrusion detection and fraud analysis. although there has been a significant amount of work in outlier detection, most of the algorithms proposed in the literature are based on a particular definition of outliers (e.g., density-based), and use ad-hoc thresholds to detect them. in this paper we present a novel technique to detect outliers with respect to an existing clustering model. however, the test can also be successfully utilized to recognize outliers when the clustering information is not available. our method is based on transductive confidence machines, which have been previously proposed as a mechanism to provide individual confidence measures on classification decisions. the test uses hypothesis testing to prove or disprove whether a point is fit to be in each of the clusters of the model. we experimentally demonstrate that the test is highly robust, and produces very few misdiagnosed points, even when no clustering information is available. furthermore, our experiments demonstrate the robustness of our method under the circumstances of data contaminated by outliers. we finally show that our technique can be successfully applied to identify outliers in a noisy data set for which no information is available (e.g., ground truth, clustering structure, etc.). as such our proposed methodology is capable of bootstrapping from a noisy data set a clean one that can be used to identify future outliers.
approximating a collection of frequent sets. one of the most well-studied problems in data mining is computing the collection of frequent item sets in large transactional databases. one obstacle for the applicability of frequent-set mining is that the size of the output collection can be far too large to be carefully examined and understood by the users. even restricting the output to the border of the frequent item-set collection does not help much in alleviating the problem.in this paper we address the issue of overwhelmingly large output size by introducing and studying the following problem: what are the k sets that best approximate a collection of frequent item sets? our measure of approximating a collection of sets by k sets is defined to be the size of the collection covered by the the k sets, i.e., the part of the collection that is included in one of the k sets. we also specify a bound on the number of extra sets that are allowed to be covered. we examine different problem variants for which we demonstrate the hardness of the corresponding problems and we provide simple polynomial-time approximation algorithms. we give empirical evidence showing that the approximation methods work well in practice.
shrinkage estimator generalizations of proximal support vector machines. we give a statistical interpretation of proximal support vector machines (psvm) proposed at kdd2001 as linear approximaters to (nonlinear) support vector machines (svm). we prove that psvm using a linear kernel is identical to ridge regression, a biased-regression method known in the statistical community for more than thirty years. techniques from the statistical literature to estimate the tuning constant that appears in the svm and psvm framework are discussed. better shrinkage strategies that incorporate more than one tuning constant are suggested. for nonlinear kernels, the minimization problem posed in the psvm framework is equivalent to finding the posterior mode of a bayesian model defined through a gaussian process on the predictor space. apart from providing new insights, these interpretations help us attach an estimate of uncertainty to our predictions and enable us to build richer classes of models. in particular, we propose a new algorithm called psvmmix which is a combination of ridge regression and a gaussian process model. extension to the case of continuous response is straightforward and illustrated with example datasets.
architecting a knowledge discovery engine for military commanders utilizing massive runs of simulations. the marine corps' project albert seeks to model complex phenomenon by observing the behavior of relatively simple simulations over thousands of runs. a rich data base is developed by running the simulations thousands of times, varying the agent and scenario input parameters as well as the random seeds. exploring this result space may provide significant insight into nonlinear, surprising, and emergent behaviors. capturing these results can provide a path for making the results usable for decision support to a military commander. this paper presents two data mining approaches, rule discovery and bayesian networks, for analyzing the albert simulation data. the first approach generates rules from the data and then uses them to create descriptive model. the second generates bayesian networks which provide a quantitative belief model for decision support. both of these approaches as well as the project albert simulations are framed in the context of a system architecture for decision support.
a probabilistic framework for semi-supervised clustering. unsupervised clustering can be significantly improved using supervision in the form of pairwise constraints, i.e., pairs of instances labeled as belonging to same or different clusters. in recent years, a number of algorithms have been proposed for enhancing clustering quality by employing such supervision. such methods use the constraints to either modify the objective function, or to learn the distance measure. we propose a probabilistic model for semi-supervised clustering based on hidden markov random fields (hmrfs) that provides a principled framework for incorporating supervision into prototype-based clustering. the model generalizes a previous approach that combines constraints and euclidean distance learning, and allows the use of a broad range of clustering distortion measures, including bregman divergences (e.g., euclidean distance and i-divergence) and directional similarity measures (e.g., cosine similarity). we present an algorithm that performs partitional semi-supervised clustering of data by minimizing an objective function derived from the posterior energy of the hmrf model. experimental results on several text data sets demonstrate the advantages of the proposed framework.
learning to rank networked entities. several algorithms have been proposed to learn to rank entities modeled as feature vectors, based on relevance feedback. however, these algorithms do not model network connections or relations between entities. meanwhile, pagerank and variants find the stationary distribution of a reasonable but arbitrary markov walk over a network, but do not learn from relevance feedback. we present a framework for ranking networked entities based on markov walks with parameterized conductance values associated with the network edges. we propose two flavors of conductance learning problems in our framework. in the first setting, relevance feedback comparing node-pairs hints that the user has one or more hidden preferred communities with large edge conductance, and the algorithm must discover these communities. we present a constrained maximum entropy network flow formulation whose dual can be solved efficiently using a cutting-plane approach and a quasi-newton optimizer. in the second setting, edges have types, and relevance feedback hints that each edge type has a potentially different conductance, but this is fixed across the whole network. our algorithm learns the conductances using an approximate newton method.
evaluating the novelty of text-mined rules using lexical knowledge. in this paper, we present a new method of estimating the novelty of rules discovered by data-mining methods using wordnet, a lexical knowledge-base of english words. we assess the novelty of a rule by the average semantic distance in a knowledge hierarchy between the words in the antecedent and the consequent of the rule - the more the average distance, more is the novelty of the rule. the novelty of rules extracted by the discotex text-mining system on amazon.com book descriptions were evaluated by both human subjects and by our algorithm. by computing correlation coefficients between pairs of human ratings and between human and automatic ratings, we found that the automatic scoring of rules based on our novelty measure correlates with human judgments about as well as human judgments correlate with one another. @text mining
spatial scan statistics: approximations and performance study. spatial scan statistics are used to determine hotspots in spatial data, and are widely used in epidemiology and biosurveillance. in recent years, there has been much effort invested in designing efficient algorithms for finding such "high discrepancy" regions, with methods ranging from fast heuristics for special cases, to general grid-based methods, and to efficient approximation algorithms with provable guarantees on performance and quality.in this paper, we make a number of contributions to the computational study of spatial scan statistics. first, we describe a simple exact algorithm for finding the largest discrepancy region in a domain. second, we propose a new approximation algorithm for a large class of discrepancy functions (including the kulldorff scan statistic) that improves the approximation versus run time trade-off of prior methods. third, we extend our simple exact and our approximation algorithms to data sets which lie naturally on a grid or are accumulated onto a grid. fourth, we conduct a detailed experimental comparison of these methods with a number of known methods, demonstrating that our approximation algorithm has far superior performance in practice to prior methods, and exhibits a good performance-accuracy trade-off.all extant methods (including those in this paper) are suitable for data sets that are modestly sized; if data sets are of the order of millions of data points, none of these methods scale well. for such massive data settings, it is natural to examine whether small-space streaming algorithms might yield accurate answers. here, we provide some negative results, showing that any streaming algorithms that even provide approximately optimal answers to the discrepancy maximization problem must use space linear in the input.
a human-computer cooperative system for effective high dimensional clustering. high dimensional data has always been a challenge for clustering algorithms because of the inherent sparsity of the points. therefore, techniques have recently been proposed to find clusters in hidden subspaces of the data. however, since the behavior of the data may vary considerably in different subspaces, it is often difficult to define the notion of a cluster with the use of simple mathematical formalizations. in fact, the meaningfulness and definition of a cluster is best characterized with the use of human intuition. in this paper, we propose a system which performs high dimensional clustering by effective cooperation between the human and the computer. the complex task of cluster creation is accomplished by a combination of human intuition and the computational support provided by the computer. the result is a system which leverages the best abilities of both the human and the computer in order to create very meaningful sets of clusters in high dimensionality.
on effective classification of strings with wavelets. in recent years, the technological advances in mapping genes have made it increasingly easy to store and use a wide variety of biological data. such data are usually in the form of very long strings for which it is difficult to determine the most relevant features for a classification task. for example, a typical dna string may be millions of characters long, and there may be thousands of such strings in a database. in many cases, the classification behavior of the data may be hidden in the compositional behavior of certain segments of the string which cannot be easily determined apriori. another problem which complicates the classification task is that in some cases the classification behavior is reflected in global behavior of the string, whereas in others it is reflected in local patterns. given the enormous variation in the behavior of the strings over different data sets, it is useful to develop an approach which is sensitive to both the global and local behavior of the strings for the purpose of classification. for this purpose, we will exploit the multi-resolution property of wavelet decomposition in order to create a scheme which can mine classification characteristics at different levels of granularity. the resulting scheme turns out to be very effective in practice on a wide range of problems.
using randomized response techniques for privacy-preserving data mining. privacy is an important issue in data mining and knowledge discovery. in this paper, we propose to use the randomized response techniques to conduct the data mining computation. specially, we present a method to build decision tree classifiers from the disguised data. we conduct experiments to compare the accuracy of our decision tree with the one built from the original undisguised data. our results show that although the data are disguised, our method can still achieve fairly high accuracy. we also show how the parameter used in the randomized response techniques affects the accuracy of the results.
collaborative crawling: mining user experiences for topical resource discovery. the rapid growth of the world wide web had made the problem of topic specific resource discovery an important one in recent years. in this problem, it is desired to find web pages which satisfy a predicate specified by the user. such a predicate could be a keyword query, a topical query, or some arbitrary contraint. several techniques such as focussed crawling and intelligent crawling have recently been proposed for topic specific resource discovery. all these crawlers are linkage based, since they use the hyperlink behavior in order to perform resource discovery. recent studies have shown that the topical correlations in hyperlinks are quite noisy and may not always show the consistency necessary for a reliable resource discovery process. in this paper, we will approach the problem of resource discovery from an entirely different perspective; we will mine the significant browsing patterns of world wide web users in order to model the likelihood of web pages belonging to a specified predicate. this user behavior can be mined from the freely available traces of large public domain proxies on the world wide web. we refer to this technique as collaborative crawling because it mines the collective user experiences in order to find topical resources. such a strategy is extremely effective because the topical consistency in world wide web browsing patterns turns out to very reliable. in addition, the user-centered crawling system can be combined with linkage based systems to create an overall system which works more effectively than a system based purely on either user behavior or hyperlinks.