Fast and effective methods for pattern mining in complex data

Göbl, Sebastian (2024): Fast and effective methods for pattern mining in complex data. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

Among today's challenges in big data science, called the "Big V's", variety induces an enormous complexity of data. A vast number of portable or stationary devices collect sensor or user information of various types. In medicine, diagnostic tools observe many biological parameters and produce high-dimensional data for each patient. The patterns we are looking for are obscured by correlated attributes and noise. User information collected from the web (e.g., Facebook data) consists of very heterogeneous data domains: for example, age is provided as a natural number and height as a real number — both continuous ranges easily analyzed by distance functions. Heterogeneity is increased by adding dichotomous or general categorical domains (e.g., sex or citizenship) or relational information (e.g., Facebook likes). Very large, complex networks, such as email or authorship connections, are approached using the abstraction of graph representation. Graph mining methods search for patterns and rules that allow us to understand how these networks were created. In realistic settings, such as communication or power networks, graphs exhibit heterogeneous patterns beyond simple clusters or communities. The goal of this thesis is to contribute to tackling the challenges that arise from the complexity of data. Challenges: We take on five key challenges (C 1 to 5) derived from mining complex data and pointed out by the data mining community: graph and network mining (C 1) requires new efficient and effective algorithms for pattern mining due to the complexity of graphs over classic dimensional data, considering edge types, edge weights, or edge numbers following power laws. Explainable data mining (C 2) is required for transparent output and transparent algorithmic decisions since increasing model complexity makes it harder for the user to understand and learn the structure and patterns in the data. High-dimensional data mining (C 3) asks for efficient algorithms to tackle the large data size, increasing noise, and the large number of dimensions. Mining heterogeneous data types (C 4) requires integrated solutions for pattern mining of data with not only numerical but heterogeneous data domains. Parameter-free data mining (C 5) automatically finds suitable parameters for algorithms since complex data and models make it tedious for the user to define good input parameters. Contributions: We present four fast and effective algorithms to address these challenges. Our first two proposals, MeGS and Spectral Lens, focus on graph mining, while our third and fourth methods, FOSSCLU and INTEGRATE, focus on clustering. Our graph mining algorithm MeGS (Partitioning Meaningful Subgraph Structures using Minimum Description Length) looks for homogeneous patterns (subgraph structures) in graphs. It allows a complete understanding of these structures and, thus, the whole graph (C 1). It matches meaningful primitives (clique, hub, tree, bipartite and sparse subgraphs) to all partitions of a graph. Every node of the graph is part of precisely one structure and has an interpretable context (C 2). MeGS is a fast and parameter-free split-and-merge algorithm that automatically finds the optimal structures that achieve the best compression by minimum description length (MDL) (C 5). With weighted and unweighted, directed and undirected networks, the graph challenge (C 1) can take on more complex shapes: With Spectral Lens, we introduce an efficient and effective method to address even very large (C 3) graphs, despite having additional edge weights or directed edges (C 4). Our algorithm identifies connectivity patterns given by a dictionary of rules to gain insights (C 2) into a graph's communities, e.g., their power-law distribution, and discovers anomalies. Spectral Lens can automatically find the optimal number of communities (C 5) that describe the network best. Our algorithm FOSSCLU (Finding the Optimal Subspace for Clustering) takes up the challenge of data dimensionality (C 3) in clustering. For human understanding, it is important to simplify and categorize things. Therefore, it is highly valuable to find clusters in one common low-dimensional subspace where we can study not only the intra-cluster but also the inter-cluster relationships (C 2). We propose FOSSCLU to find this subspace in a joint, alternating process of clustering and dimensionality reduction. FOSSCLU is rendered parameter-free with the aid of MDL (C 5). We approach the difficulties in clustering heterogeneous data (C 4) by proposing INTEGRATE: Our parameter-free algorithm integrates the information supplied by heterogeneous numerical and categorical dimensions and exploits both for clustering. INTEGRATE is efficient and scalable and automatically decides on parameter values (C 5) using MDL. Our four algorithms address key challenges arising from complex data. Our methods are evaluated by extensive experiments on real-world data and provide efficient and effective solutions to contribute to the key tasks of data mining.

Abstract

Eine der aktuellen Herausforderungen des Big-Data-Science, die auch als "Big V's" bezeichnet werden, ist die Vielfalt der Daten (engl.: variety), die zu einer enormen Komplexität führt. Sehr viele tragbare oder stationäre Geräte erfassen unterschiedlichste Sensor- oder Benutzerinformationen. In der Medizin überwachen Diagnosegeräte viele biologische Parameter und erzeugen für jeden einzelnen Patienten hochdimensionale Datensätze. Korrelierte Attribute und Rauschen erschweren das Auffinden relevanter Muster. Im Internet gesammelte Nutzerinformationen, beispielsweise Daten bei Facebook, umfassen sehr heterogene Datendomänen: so wird etwa das Alter als natürliche Zahl und die Körpergröße als reelle Zahl angegeben — beides sind kontinuierliche Wertebereiche, die sich leicht mit Distanzfunktionen analysieren lassen. Die Heterogenität nimmt zu, wenn dichotome oder allgemein kategorische Daten (wie Geschlecht oder Staatsangehörigkeit) oder auch relationale Informationen wie Likes bei Facebook hinzukommen. Sehr große und komplexe Netzwerke – wie E-Mail-Verbindungen oder Publikationsnetzwerke – lassen sich gut mit Hilfe von Graphabstraktion untersuchen. Die Methoden des Graph-Minings suchen nach Mustern und Regeln um zu verstehen, wie Netzwerke entstanden sind. In der Realität zeigen Graphen (z.B. Kommunikationsnetzwerke oder Stromversorgungsnetze) heterogene Strukturen, die komplexer sind als einfache Cluster oder Communities. Die vorliegende Arbeit soll einen Beitrag zur Bewältigung der Herausforderungen leisten, die sich aus der Komplexität der Daten ergeben. Herausforderungen: Wir befassen uns mit fünf zentralen Herausforderungen (C 1 to 5) des Minings komplexer Daten, die in der Data-Mining-Community besonders hervorgehoben werden: Das Graph- und Netzwerk-Mining (C 1) erfordert effiziente und effektive Algorithmen zur Mustersuche, da Graphen deutlich komplexer als klassische, dimensionsbasierte Daten sind. Das liegt an Kantentypen, Kantengewichten und auch daran, dass die Anzahl der Kanten eines Graphen Potenzgesetzen folgen kann. Das erklärbare Data-Mining (C 2) ist nötig für transparente Ergebnisse und transparente Entscheidungsprozesse der Algorithmen, da der Anwender wegen der komplexen Modelle Strukturen und Muster in den Daten nur schwer nachvollziehen kann. Das hochdimensionale Data-Mining (C 3) erfordert effiziente Algorithmen für die großen Datenmengen mit starkem Rauschen und hoher Dimensionalität. Das Mining heterogener Datentypen (C 4) verlangt nach integrierten Lösungen zur Mustererkennung von Daten aus nicht nur numerischen, sondern auch heterogenen Domänen. Das parameterfreie Data-Mining (C 5) findet selbstständig geeignete Eingabeparameter für Algorithmen, da es die Komplexität der Daten und Modelle dem Anwender oft erschwert, selbst gute Parameter festzulegen. Beiträge: Wir stellen vier schnelle und effektive Algorithmen vor, die einen Beitrag zur Bewältigung dieser Herausforderungen leisten. Unsere ersten beiden Methoden, MeGS und Spectral Lens, konzentrieren sich auf das Graph-Mining, die anderen beiden, FOSSCLU und INTEGRATE, auf das Clustering. Unser Graph-Mining-Algorithmus MeGS (Partitionierung aussagekräftiger Subgraphstrukturen unter Verwendung der Minimum-Description-Length, engl.: Partitioning Meaningful Subgraph Structures using Minimum Description Length) sucht nach homogenen Mustern (Subgraphstrukturen) in Graphen und ermöglicht ein umfassendes Verständnis dieser Strukturen und damit des ganzen Graphen (C 1). Allen Partitionen eines Graphen werden aussagekräftige Primitive zugeordnet (Clique, Hub, Baum, bipartite und dünn besetzte Subgraphen). Jeder Knoten eines Graphen gehört zu genau einer Struktur und erhält dadurch einen interpretierbaren Kontext (C 2). MeGS ist ein schneller, parameterfreier Split-and-Merge-Algorithmus; mit Hilfe des Prinzips der Minimum-Description-Length (MDL) findet er automatisch diejenige Partitionierung, die zur besten Komprimierung des Graphen führt (C 5). Durch Graphen mit und ohne Kantengewichten und durch gerichtete und ungerichtete Kanten erhöht sich die Komplexität im Graph-Mining weiter (C 1): Mit Spectral Lens schaffen wir eine effiziente und effektive Möglichkeit, um auch sehr große Graphen (C 3) trotz zusätzlicher Kantengewichte und gerichteter Kanten (C 4) zu verarbeiten. Unser Algorithmus identifiziert Konnektivitätsmuster über ein Verzeichnis von Regeln; dadurch erhält er Einblick (C 2) in die Communities der Graphen, beispielsweise in ihre Potenzgesetzverteilung, und er bringt Anomalien zum Vorschein. Spectral Lens kann automatisch errechnen, durch wie viele Communities (C 5) ein Netzwerk am besten erfasst wird. Unser Algorithmus FOSSCLU (Finden des optimalen Unterraums für das Clustering, engl.: Finding the Optimal Subspace for Clustering) befasst sich mit der Herausforderung der Datendimensionalität (C 3) im Clustering. Für die menschliche Auffassung ist es wichtig, Dinge zu vereinfachen und zu kategorisieren. Daher ist es sehr hilfreich, Cluster in einem gemeinsamen, niedrig-dimensionalen Unterraum zu finden, wo wir Beziehungen innerhalb eines Clusters und auch zwischen den Clustern untersuchen können (C 2). Um diesen Unterraum in einem gemeinsamen, alternierenden Prozess aus Clustering und Dimensionalitätsreduktion zu finden, stellen wir FOSSCLU vor. Durch die Verwendung von MDL muss der Anwender keine Eingabeparameter festlegen (C 5). Den Schwierigkeiten im Clustering heterogener Daten (C 4) begegnen wir mit unserem Algorithmus INTEGRATE: unser parameterfreier Algorithmus integriert Daten mit numerischen und kategorischen Dimensionen, um beide gleichermaßen in das Clustering einzubeziehen. INTEGRATE ist effizient und skalierbar. Eingabeparameter werden mit Hilfe von MDL automatisch bestimmt (C 5). Unsere vier Algorithmen nehmen zentrale Herausforderungen in Angriff, die durch die Komplexität der Daten verursacht werden. Unsere Methoden werden durch umfangreiche Experimente an Echtweltdaten evaluiert und leisten mit effizienten und effektiven Lösungen einen Beitrag zu den Kernaufgaben des Data-Minings.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Themengebiete: 000 Allgemeines, Informatik, Informationswissenschaft ; 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Englisch
• Datum der mündlichen Prüfung: 15. April 2024
• 1. Bericht­erstatter:in: Böhm, Christian