1,721,203 research outputs found
Insight in Information: from Abstract to Anomaly
No full textAs a result of cheap data storage, nowadays it is not the question if a company or institution collects data or not, but rather how much they collect. Transforming data into information and getting insight in this information is perhaps the most important problem in our data rich society. That is, only collecting data serves no goal, but data becomes valuable when insight can be gained from it. Data mining is the subfield of computer science that concerns itself with transforming large amounts of data into information in the form of patterns. The idea is that the identified patterns result in new insights by exposing interesting structure or behaviour in the data. It may be obvious that defining what exactly is interesting is one of the key challenges. One of the main applications of data mining on which we focus in this thesis is exploratory data analysis. In this analysis we make use of summaries and characterisations of a dataset to gain insight. That is, by inspecting and exploring the patterns that comprise these models we can extract important information from the data. In this thesis we employ the Minimum Description Length (MDL) principle to find such models which we call summaries. That is, we find the best summary as the set of patterns that give the best compression of the data. Additionally, these summaries can also be used for other data mining tasks, such as the identification of irregular or abnormal data points. All these deviations from what could be expected are called anomalies. We also focus on anomaly detection in this thesis, for which the goal is to gain more insight in the information we already have. Finally, we conclude that the MDL principle can be successfully employed in the domain of multivariate sequential data. Both for summarisation and anomaly detection successful algorithms have been introduced which are tested on a variety of synthetic and real world datasets
Probabilistic Active Learning with Structure-Sensitive Kernels
No full textThis work proposes two approaches to improve the poolbased active learning strategy ’Multi-Class Probabilistic Active Learning’ (McPAL) by using two kernel functions based on Gaussian mixture models (GMMs). One uses the kernels for the instance selection of the McPAL strategy, the second employs them in the classification step. The results of the evaluation show that using a different classification model from the one that is used for selection, especially an SVM with one of the kernels, can improve the performance of the active learner in some cases
Temporal density extrapolation using a dynamic basis approach
No full textDensity estimation is a versatile technique underlying many data mining tasks and techniques, ranging from exploration and presentation of static data, to probabilistic classification, or identifying changes or irregularities in streaming data. With the pervasiveness of embedded systems and digitisation, this latter type of streaming and evolving data becomes more important. Nevertheless, research in density estimation has so far focused on stationary data, leaving the task of of extrapolating and predicting density at time points outside a training window an open problem. For this task, temporal density extrapolation (TDX) is proposed. This novel method models and predicts gradual monotonous changes in a distribution. It is based on the expansion of basis functions, whose weights are modelled as functions of compositional data over time by using an isometric log-ratio transformation. Extrapolated density estimates are then obtained by extrapolating the weights to the requested time point, and querying the density from the basis functions with back-transformed weights. Our approach aims for broad applicability by neither being restricted to a specific parametric distribution, nor relying on cluster structure in the data. It requires only two additional extrapolation-specific parameters, for which reasonable defaults exist. Experimental evaluation on various data streams, synthetic as well as from the real-world domains of credit scoring and environmental health, shows that the model manages to capture monotonous drift patterns accurately and better than existing methods. Thereby, it requires not more than 1.5 times the run time of a corresponding static density estimation approach
Challenges of Reliable, Realistic and Comparable Active Learning Evaluation
No full textActive learning has the potential to save costs by intelligent use of resources in form of some expert’s knowledge. Nevertheless, these methods are still not established in real-world applications as they can not be evaluated properly in the specific scenario because evaluation data is missing. In this article, we provide a summary of different evaluation methodologies by discussing them in terms of being reproducible, comparable, and realistic. A pilot study which compares the results of different exhaustive evaluations suggests a lack in repetitions in many articles. Furthermore, we aim to start a discussion on a gold standard evaluation setup for active learning that ensures comparability without reimplementing algorithms
Patterns that matter
No full textPattern mining is one of the best-known concepts in Data Mining. A big problem in pattern mining is that humongous amounts of patterns can be mined even from small datasets. This makes it hard for domain experts to discover knowledge using pattern mining, for example in the field of Bioinformatics. In this thesis we address the pattern explosion using compression. We argue that the best pattern set is that set of patterns that compresses the data best. Based on an analysis from MDL (Minimum Description Length) perspective, we introduce a heuristic algorithm, called Krimp, which finds the best set of patterns. High compression ratios and good classification scores confirm that Krimp selects patterns that are very characteristic for the data. After this, we proceed with a series of well-known problems in Knowledge Discovery, which we each unravel with our compression approach. We propose a database dissimilarity measure and show how compression can be used to characterise differences between databases. We present an algorithm that generates synthetic data that is virtually indiscernible from the original data, but can also be used to preserve privacy. Changes in data streams are detected by using a Krimp compressor to check whether the data distribution has been changed or not. Finally, compression is used to identify the components of a database and to find interesting groups in a database. In each chapter, we provide an extensive experimental evaluation to show that the proposed methods perform well on a large variety of datasets. In the end, we conclude that having less, but more characteristic patterns is key to successful Knowledge Discovery and that compression is very useful in this respect. Not as goal in itself, but as means to an end: compression picks the patterns that matter
Characteristic relational patterns
No full textNowadays, relational databases have become the de facto standard to store large quantities of data. As the manual analysis of these large quantities of data is practically impossible, the field of data mining provides methods that attempts to automatically acquire insight into the data. One cornerstone technique is that of pattern mining: finding interesting regularity in data. Despite all good e orts, one can conclude that pattern mining still has a major Achilles' heel, that is, the ease at which patterns can be found. Many found patterns are slight variations on the same underlying theme, although many of them are still designated as interesting. In practice, a user gets swamped by too many similar patterns that do not contribute to a new insight into the database. In this thesis we therefore propose a di erent approach. In contrast to selecting patterns on an individual basis, we propose the selection of pattern sets. In particular, we focus on a selection scheme based on a compression technique called the Minimum Description Length (MDL) principle. The selected pattern set, our model of the data, is used to compress the complete database. According to the MDL principle, the model that compresses the database best is also the one that describes it best. As acquiring the optimal model of a database is simply too complex, we utilise a practical and heuristic approach, named Krimp. Based on this, we designed a toolbox of algorithms that derives models for di erent interpretations of the data. We discuss structured data types such as sequences and trees, the join of the database, and relational databases as a whole. These last models also show to result in good classifiers. We back up the claims in this thesis by experimental evaluation. For many of the used databases, the number of patterns initially is huge. However, we show that from this huge collection of patterns, we select a compact and good set of characteristic relational patterns
Patterns, Models, and Queries
No full textData mining provides methods that help to acquire insight in a data set automatically. One of its problem areas is to select a small set of useful patterns from the huge collection of patterns that can be found in a data set. This thesis presents our results in this area. We show that such a small set of patterns, if well-chosen, allows one to answer queries on the data set without referring to the data itself. Moreover, we show how these pattern sets allow one to built quick and scalable recommender systems. To choose such a small set of patterns, we rely on the Minimum Description Length (MDL) principle: the best model compresses the data best. More precisely, we use the code tables that the heuristic Krimp algorithm induces from the data. Our results show that these code tables are highly characteristic of the data set. Anything one wants to know about the data can be inferred from its code table. In more detail, we show how such a code table can be used to compute the answer to a query on the data set. These answers are almost always very close to the answer one gets by actually computing the query on the data itself. This similarity is verified experimentally and quantified using an asymmetric dissimilarity score which is derived from the Normalised Compression Distance. Next we show how the code tables can be used for the -- predictive -- task of tag recommendation. In particular it is shown that the proposed algorithms show a good trade-off between accuracy and time-efficiency; using the full set of patterns yields only slightly better results but requires infeasible amounts of time. In a social networking context we show how to personalize -- and thus improve -- our tag recommendations. This is achieved by using user-centred knowledge in contrast to the collective knowledge used for the general task. For quality and scalability reasons, we use `social batched personomies' by processing queries in batches, instead of individually, such as done in the standard personomy approach. In each chapter we provide extensive experimental evaluation to show that our methods perform well on a large variety of datasets. From these experiments one cannot but conclude that code tables are highly characteristic of the data
Keeping it Short and Simple: Summarising Complex Event Sequences with Multivariate Patterns
Full text linkWe study how to obtain concise descriptions of discrete multivariate sequential data. In particular, how to do so in terms of rich multivariate sequential patterns that can capture potentially highly interesting (cor)relations between sequences. To this end we allow our pattern language to span over the domains (alphabets) of all sequences, allow patterns to overlap temporally, as well as allow for gaps in their occurrences. We formalise our goal by the Minimum Description Length principle, by which our objective is to discover the set of patterns that provides the most succinct description of the data. To discover high-quality pattern sets directly from data, we introduce Ditto, a highly efficient algorithm that approximates the ideal result very well. Experiments show that Ditto correctly discovers the patterns planted in synthetic data. Moreover, it scales favourably with the length of the data, the number of attributes, the alphabet sizes. On real data, ranging from sensor networks to annotated text, Ditto discovers easily interpretable summaries that provide clear insight in both the univariate and multivariate structure
Probabilistic Active Learning for Active Class Selection.
Full text linkIn machine learning, active class selection (ACS) algorithms aim to actively select a class and ask the oracle to provide an instance for that class to optimize a classifier's performance while minimizing the number of requests. In this paper, we propose a new algorithm (PAL-ACS) that transforms the ACS problem into an active learning task by introducing pseudo instances. These are used to estimate the usefulness of an upcoming instance for each class using the performance gain model from probabilistic active learning. Our experimental evaluation (on synthetic and real data) shows the advantages of our algorithm compared to state-of-the-art algorithms. It effectively prefers the sampling of difficult classes and thereby improves the classification performance
Efficient algorithms for finding optimal binary features in numeric and nominal labeled data
No full textAn important subproblem in supervised tasks such as decision tree induction and subgroup discovery is finding an interesting binary feature (such as a node split or a subgroup refinement) based on a numeric or nominal attribute, with respect to some discrete or continuous target variable. Often one is faced with a trade-off between the expressiveness of such features on the one hand and the ability to efficiently traverse the feature search space on the other hand. In this article, we present efficient algorithms to mine binary features that optimize a given convex quality measure. For numeric attributes, we propose an algorithm that finds an optimal interval, whereas for nominal attributes, we give an algorithm that finds an optimal value set. By restricting the search to features that lie on a convex hull in a coverage space, we can significantly reduce computation time. We present some general theoretical results on the cardinality of convex hulls in coverage spaces of arbitrary dimensions and perform a complexity analysis of our algorithms. In the important case of a binary target, we show that these algorithms have linear runtime in the number of examples. We further provide algorithms for additive quality measures, which have linear runtime regardless of the target type. Additive measures are particularly relevant to feature discovery in subgroup discovery. Our algorithms are shown to perform well through experimentation and furthermore provide additional expressive power leading to higher-quality results
- …
