19 research outputs found
Direct local pattern sampling by efficient two-step random procedures
No full textWe present several exact and highly scalable local pattern sampling algorithms. They can be used as an alternative to exhaustive local pattern discovery methods (e.g, frequent set mining or optimistic-estimator-based subgroup discovery) and can substantially improve efficiency as well as controllability of pattern discovery processes. While previous sampling approaches mainly rely on theMarkov chainMonte Carlo method, our procedures are direct, i.e., non processsimulating, sampling algorithms. The advantages of these direct methods are an almost optimal time complexity per pattern as well as an exactly controlled distribution of the produced patterns. Namely, the proposed algorithms can sample (item-)sets according to frequency, area, squared frequency, and a class discriminativity measure. Experiments demonstrate that these procedures can improve the accuracy of pattern-based models similar to frequent sets and often also lead to substantial gains in terms of scalability. Copyright 2011 ACM
Intuitive Exploration of Multivariate Data
No full textApproaching a dataset with an analysis question is usually not a trivial process. Apart from integrating, cleaning and pre-processing the data, typical issues are to generate and validate hypotheses, to understand which algorithms to apply, to estimate parameter settings and to interpret intermediate analysis results. To this end, it is often helpful to explore the data at first in order to find and understand its main characteristics, the driving influences, structures and relations among the data records, as well as revealing outliers. Exploratory data analysis, a term coined by John W. Tukey (Tukey, 1977), is a loose set of methods, mostly of graphical nature, to summarize and understand the main characteristics of the data at hand. This work extends the set of exploratory data analysis methods by proposing several new methods that support the analyst in his, or her task of understanding the data. Over the course of this thesis, two conceptually different approaches are investigated. The first approach studies pattern mining algorithms, a family of methods that find and report hypotheses which describe interesting sub-populations of the dataset to the analyst, where the interestingness is measured by different quality functions. As the results of pattern mining methods are interpretable by a human expert, these algorithms are often utilized to study a dataset in an exploratory way. Note that many pattern mining algorithms address the problem of finding a small set of diverse high patterns. To this end, this work introduces two new algorithms, one for relevant and one for Δ-relevant subgroup discovery. In addition an algorithmic framework for sampling patterns according to different pattern quality measures is introduced. The second approach towards exploratory data analysis leaves the discovery of interesting sub-populations to the analyst and enables him, or her to study a two dimensional projection of the data and interact with it. A scatter plot visualization of the projected data lets the analyst observe the data collection as a whole and visually uncover interesting structures. Manipulating the locations of individual data records within the plot further enables the analyst to alter the projection angle and to actively steer the projection. This way relations among the data records can be set, or discovered and aspects of the data’s underlying distribution can be explored in a visual manner. Finding the according projections is not trivial and throughout this thesis three novel approaches are proposed to do so. The thesis concludes with a synthesis of both approaches. Classical pattern mining algorithms often aim at reducing the output of patterns to a small set of highly interesting and diverse patterns. However, by discarding most of the patterns, a trade-off has to be made between ruling out potentially insightful patterns and possibly drowning the analyst in results. Combining interactive visual exploration techniques with pattern discovery, on the other hand, excels on working with larger pattern collections, as the underlying pattern-distribution emerges more clearly. This way, the analyst does not only retain an overview on the underlying structure of the dataset, but can also survey the relations among the interesting aspects of the dataset
Fast and memoryefficient discovery of the top-k relevant subgroups in a reduced candidate space
No full textAbstract. We consider a modified version of the top-k subgroup discov-ery task, where subgroups dominated by other subgroups are discarded. The advantage of this modified task, known as relevant subgroup discov-ery, is that it avoids redundancy in the outcome. Although it has been applied in many applications, so far no efficient exact algorithm for this task has been proposed. Most existing solutions do not guarantee the exact solution (as a result of the use of non-admissible heuristics), while the only exact solution relies on the explicit storage of the whole search space, which results in prohibitively large memory requirements. In this paper, we present a new top-k relevant subgroup discovery al-gorithm which overcomes these shortcomings. Our solution is based on the fact that if an iterative deepening approach is applied, the relevance check – which is the root of the problems of all other approaches – can be realized based solely on the best k subgroups visited so far. The ap-proach also allows for the integration of admissible pruning techniques like optimistic estimate pruning. The result is a fast, memory-efficient algorithm which clearly outperforms existing top-k relevant subgroup discovery approaches. Moreover, we analytically and empirically show that it is competitive with simpler approaches which do not consider the relevance criterion.
Fast discovery of relevant subgroups using a reduced search space
No full textWe consider a modified version of the local pattern discovery task of subgroup discovery, where subgroups dominated by other subgroups are discarded. The advantage of this modified task, known as relevant subgroup discovery, is that it avoids redundancy in the outcome. Although it was considered in many applications, so far no efficient and exact algorithm for this task has been proposed. One particular problem is that the correctness is not guaranteed if the standard pruning approach is applied. In this paper, we devise a new algorithm based on two ideas: For one, we use the theory of closed sets for labeled data to reduce the candidate space; for another we introduce a special search space traversal which allows the use of optimistic estimate pruning while guaranteeing the correctness of the solution. We show that although our algorithm solves a more valuable task than other (classical) approaches, it outperforms all existing subgroup discovery algorithms
InVis: A tool for interactive visual data analysis
No full textS.672-676We present InVis, a tool to visually analyse data by interactively shaping a two dimensional embedding of it. Traditionally, embedding techniques focus on finding one fixed embedding, which emphasizes a single aspects of the data. In contrast, our application enables the user to explore the structures of a dataset by observing and controlling a projection of it. Ultimately it provides a way to search and find an embedding, emphasizing aspects that the user desires to highlight
Interactive Knowledge-Based Kernel PCA
No full textData understanding is an iterative process in which domain experts combine their knowledge with the data at hand to explore and confirm hypotheses. One important set of tools for exploring hypotheses about data are visualizations. Often, however, traditional, unsupervised dimensionality reduction algorithms are used for visualization. These tools allow for interaction, i.e., exploring different visualizations, only by means of manipulating some technical parameters of the algorithm. Therefore, instead of being able to intuitively interact with the visualization, domain experts have to learn and argue about these technical parameters. In this paper we propose a knowledge-based kernel PCA approach that allows for intuitive interaction with data visualizations. Each embedding direction is given by a non-convex quadratic optimization problem over an ellipsoid and has a globally optimal solution in the kernel feature space. A solution can be found in polynomial time using the algorithm presented in this paper. To facilitate direct feedback, i.e., updating the whole embedding with a sufficiently high frame-rate during interaction, we reduce the computational complexity further by incremental up- and down-dating. Our empirical evaluation demonstrates the flexibility and utility of this approach
Model-based data exploration
No full textS.729-740Data exploration is an approach of visually exploring data in order to understand the characteristics of the dataset. As both size and complexity of datasets increase substantially, data scientists take less look at the data directly but conduct experiments by training models and assess the outcome when applying these models on test data. We denote the use of ML models to experimentally obtain insights into the data at hand as model-based data exploration and show some examples from a recent industrial project
Interactive knowledge-based kernel PCA
No full textS.501-516Data understanding is an iterative process in which domain experts combine their knowledge with the data at hand to explore and confirm hypotheses. One important set of tools for exploring hypotheses about data are visualizations. Often, however, traditional, unsupervised dimensionality reduction algorithms are used for visualization. These tools allow for interaction, i.e., exploring different visualizations, only by means of manipulating some technical parameters of the algorithm. Therefore, instead of being able to intuitively interact with the visualization, domain experts have to learn and argue about these technical parameters. In this paper we propose a knowledge-based kernel PCA approach that allows for intuitive interaction with data visualizations. Each embedding direction is given by a non-convex quadratic optimization problem over an ellipsoid and has a globally optimal solution in the kernel feature space. A solution can be found in polynomial time using the algorithm presented in this paper. To facilitate direct feedback, i.e., updating the whole embedding with a sufficiently high frame-rate during interaction, we reduce the computational complexity further by incremental up- and down-dating. Our empirical evaluation demonstrates the flexibility and utility of this approach
