Now showing 1 - 10 of 19
  • Publication
    Constructing Spaces and Times for Tactical Analysis in Football
    ( 2021)
    Andrienko, Gennady
    ;
    Andrienko, Natalia
    ;
    Anzer, Gabriel
    ;
    Bauer, Pascal
    ;
    Budziak, Guido
    ;
    ; ;
    Weber, Hendrik
    ;
    A possible objective in analyzing trajectories of multiple simultaneously moving objects, such as football players during a game, is to extract and understand the general patterns of coordinated movement in different classes of situations as they develop. For achieving this objective, we propose an approach that includes a combination of query techniques for flexible selection of episodes of situation development, a method for dynamic aggregation of data from selected groups of episodes, and a data structure for representing the aggregates that enables their exploration and use in further analysis. The aggregation, which is meant to abstract general movement patterns, involves construction of new time-homomorphic reference systems owing to iterative application of aggregation operators to a sequence of data selections. As similar patterns may occur at different spatial locations, we also propose constructing new spatial reference systems for aligning and matching movements irrespective of their absolute locations. The approach was tested in application to tracking data from two Bundesliga games of the 2018/2019 season. It enabled detection of interesting and meaningful general patterns of team behaviors in three classes of situations defined by football experts. The experts found the approach and the underlying concepts worth implementing in tools for football analysts.
  • Publication
    Effective approximation of parametrized closure systems over transactional data streams
    Strongly closed itemsets, defined by a parameterized closure operator, are a generalization of ordinary closed itemsets. Depending on the strength of closedness, the family of strongly closed itemsets typically forms a tiny subfamily of ordinary closed itemsets that is stable against changes in the input. In this paper we consider the problem of mining strongly closed itemsets from transactional data streams. Utilizing their algebraic and algorithmic properties, we propose an algorithm based on reservoir sampling for approximating this type of itemsets in the landmark streaming setting, prove its correctness, and show empirically that it yields a considerable speed-up over a straightforward naive algorithm without any significant loss in precision and recall. We motivate the problem setting considered by two practical applications. In particular, we first experimentally demonstrate that the above properties, i.e., compactness and stability, make strongly closed itemsets an excellent indicator of certain types of concept drifts in transactional data streams. As a second application we consider computer-aided product configuration, a real-world problem raised by an industrial project. For this problem, which is essentially exact concept identification, we propose a learning algorithm based on a certain type of subset queries formed by strongly closed itemsets and show on real-world datasets that it requires significantly less query evaluations than a naive algorithm based on membership queries.
  • Publication
    Probabilistic and exact frequent subtree mining in graphs beyond forests
    ( 2019)
    Welke, Pascal
    ;
    ;
    Motivated by the impressive predictive power of simple patterns, we consider the problem of mining frequent subtrees in arbitrary graphs. Although the restriction of the pattern language to trees does not resolve the computational complexity of frequent subgraph mining, in a recent work we have shown that it gives rise to an algorithm generating probabilistic frequent subtrees, a random subset of all frequent subtrees, from arbitrary graphs with polynomial delay. It is based on replacing each transaction graph in the input database with a forest formed by a random subset of its spanning trees. This simple technique turned out to be quite powerful on molecule classification tasks. It has, however, the drawback that the number of sampled spanning trees must be bounded by a polynomial of the size of the transaction graphs, resulting in less impressive recall even for slightly more complex structures beyond molecular graphs. To overcome this limitation, in this work we propose an algorithm mining probabilistic frequent subtrees also with polynomial delay, but by replacing each graph with a forest formed by an exponentially large implicit subset of its spanning trees. We demonstrate the superiority of our algorithm over the simple one on threshold graphs used e.g. in spectral clustering. In addition, providing sufficient conditions for the completeness and efficiency of our algorithm, we obtain a positive complexity result on exact frequent subtree mining for a novel, practically and theoretically relevant graph class that is orthogonal to all graph classes defined by some constant bound on monotone graph properties.
  • Publication
    A review of machine learning for the optimization of production processes
    Due to the advances in the digitalization process of the manufacturing industry and the resulting available data, there is tremendous progress and large interest in integrating machine learning and optimization methods on the shop floor in order to improve production processes. Additionally, a shortage of resources leads to increasing acceptance of new approaches, such as machine learning to save energy, time, and resources, and avoid waste. After describing possible occurring data types in the manufacturing world, this study covers the majority of relevant literature from 2008 to 2018 dealing with machine learning and optimization approaches for product quality or process improvement in the manufacturing industry. The review shows that there is hardly any correlation between the used data, the amount of data, the machine learning algorithms, the used optimizers, and the respective problem from the production. The detailed correlations between these criteria and the recent progress made in this area as well as the issues that are still unsolved are discussed in this paper.
  • Publication
    Probabilistic frequent subtrees for efficient graph classification and retrieval
    ( 2018)
    Welke, Pascal
    ;
    ;
    Frequent subgraphs proved to be powerful features for graph classification and prediction tasks. Their practical use is, however, limited by the computational intractability of pattern enumeration and that of graph embedding into frequent subgraph feature spaces. We propose a simple probabilistic technique that resolves both limitations. In particular, we restrict the pattern language to trees and relax the demand on the completeness of the mining algorithm, as well as on the correctness of the pattern matching operator by replacing transaction and query graphs with small random samples of their spanning trees. In this way we consider only a random subset of frequent subtrees, called probabilistic frequent subtrees, that can be enumerated efficiently. Our extensive empirical evaluation on artificial and benchmark molecular graph datasets shows that probabilistic frequent subtrees can be listed in practically feasible time and that their predictive and retrieval performance is very close even to those of complete sets of frequent subgraphs. We also present different fast techniques for computing the embedding of unseen graphs into (probabilistic frequent) subtree feature spaces. These algorithms utilize the partial order on tree patterns induced by subgraph isomorphism and, as we show empirically, require much less evaluations of subtree isomorphism than the standard brute-force algorithm. We also consider partial embeddings, i.e., when only a part of the feature vector has to be calculated. In particular, we propose a highly effective practical algorithm that significantly reduces the number of pattern matching evaluations required by the classical min-hashing algorithm approximating Jaccard-similarities.
  • Publication
    Big Data, Big Opportunities
    Angetrieben von den technischen Innovationen in der Informatik stehen in allen Bereichen von Wirtschaft, Gesellschaft und Privatleben heute immer mehr Daten zur Verfügung, die potenziell übertragen, gespeichert und analysiert werden könnten, um daraus nützliche Informationen als Grundlage für neue Dienste zu gewinnen. Technische Neuerungen wie die verteilte oder speicherresidente Verarbeitung von Daten haben dazu geführt, dass unsere Analysefähigkeiten so stark gewachsen sind, dass eine neue Klasse von Anwendungen möglich erscheint. Unter dem Schlagwort ,,Big Data"" scheint sich daher zurzeit eine Revolution bei der Nutzung von Daten in allen Bereichen anzukündigen. Der vorliegende Artikel versucht angesichts aktueller Studien zur Nutzung von Big Data-Ansätzen zu beleuchten, inwieweit die großen öffentlichen Erwartungen sich tatsächlich schon im praktischen Ansatz insbesondere in Unternehmen niederschlagen. Er identifiziert darüber hinaus auf Basis allgemeiner und in den Studien zu beobachtender Trends die wichtigsten Herausforderungen, denen sich das Thema Big Data in den nächsten Jahren stellen muss, wenn es die hohen aktuellen Erwartungen auch längerfristig einlösen will.
  • Publication
    Spatiotemporal modeling and analysis. Introduction and overview
    Over the past ve to seven years the analysis of trajectory data has established itself as an independent research discipline within the area of data mining. In this article we provide an overview on data characteristics, state-of-the-art preprocessing and analysis methods of trajectory data. We conclude the article with a collection of challenges that arise due to the increasing variety of spatiotemporal data sources and which have to be solved for the application of spatiotemporal analysis methods in practice.
  • Publication
    Challenging problems of geospatial visual analytics
    ( 2011)
    Andrienko, Gennady
    ;
    Andrienko, Natalia
    ;
    Keim, Daniel A.
    ;
    MacEachren, Alan M.
    ;
  • Publication
    A conceptual framework and taxonomy of techniques for analyzing movement
    ( 2011)
    Andrienko, Gennady
    ;
    Andrienko, Natalia
    ;
    Bak, Peter
    ;
    Keim, Daniel A.
    ;
    Kisilevich, S.
    ;
    Movement data link together space, time, and objects positioned in space and time. They hold valuable and multifaceted information about moving objects, properties of space and time as well as events and processes occurring in space and time. We present a conceptual framework that describes in a systematic and comprehensive way the possible types of information that can be extracted from movement data and on this basis defines the respective types of analytical tasks. Tasks are distinguished according to the type of information they target and according to the level of analysis, which may be elementary (i.e. addressing specific elements of a set) or synoptic (i.e. addressing a set or subsets). We also present a taxonomy of generic analytic techniques, in which the types of tasks are linked to the corresponding classes of techniques that can support fulfilling them. We include techniques from several research fields: visualization and visual analytics, geographic informa tion science, database technology, and data mining. We expect the taxonomy to be valuable for analysts and researchers. Analysts will receive guidance in choosing suitable analytic techniques for their data and tasks. Researchers will learn what approaches exist in different fields and compare or relate them to the approaches they are going to undertake.