Back
Texte intégral
Doctoral thesis

Unsupervised and Parameter-Free Clustering of Large Graphs for Knowledge Exploration and Recommendation

    2020

1 ressource en ligne (137 p.)

Thèse de doctorat: Université de Fribourg, 2020

Analyse de Cluster
Stabilité de Cluster
Intégration de Graphiques Interprétables
Évaluation de Clustering
Mesures de Précision
Découverte de la Structure de la Communauté
Clustering Réseau
Analyse Visuelle
Exploration des Connaissances
Cluster Analysis
Cluster Stability
Interpretable Graph Embedding
Clustering Evaluation
Accuracy Metrics
Community Structure Discovery
Network Clustering
Visual Analytics
Knowledge Exploration
English French We live in an Information Age, facing a rapid increase in the amount of information that is exchanged. This permanently growing amount of data makes the ability to store, analyze, and act upon information a primary concern (in addition to the obvious privacy, legal and ethical issues that are related), raising the question: “How can one consume Big Data and transformit into actionable knowledge?”. Knowledge in the field of Information Systems can be characterized as explicit and processible information in a given context; information can be defined as data organized in a meaningful way, whereas data represents raw facts. Any complex system can be represented as a graph, which is human-readable for individuals without any mathematical background. Graph clustering provides a way to automatically identify complex structures and build a taxonomy, transforming information into knowledge. Taxonomies enable searching for specific knowledge items by navigating a hierarchy of concepts (i.e., topics) without knowing the exact title or original terminology of the item itself. However, neither the availability of comprehensive but also overwhelming information by itself nor its taxonomy are sufficient for effective information search, knowledge exploration and recommendation. The crucial aspect here is the approach to transformthe abundance of the retrieved information in a usable (i.e., human-adapted) and efficient way. In this thesis, we first overview existing research on human perception and visual analytics in Chapter 1 and Chapter 2, which leads to a set of criteria according to which the information should be transformed into knowledge to become human-readable while reflectingmultiple viewpoints. Then, in Chapter 3, we discuss existing approaches to construct such a transformation and propose our novel clustering algorithm, DAOC. Our method efficiently produces a human- adapted hierarchy of clusters (i.e., a taxonomy) for any input graph without any manual tuning and is on average 25% more accurate than the state-of-the-art analogs. The former feature is especially important for its direct applicability and seamless integration into various data mining pipelines as shown in Chapter 6 and 7. To ensure that the results are accurate besides being human-readable, in Chapter 4 we analyze existing approaches of the clustering results validation, taking into account the criteria formulated in Chapter 2. In addition, we extend the existing accuracy measures in Chapter 4, yielding both a) the implementation of theMean F1 score evaluation that works faster on a single CPU than stateof- the-art implementations running on high-performance servers and b) implementations of the Generalized NMI and Omega Index that address certain constraints of the original versions. In Chapter 5, we introduce Clubmark, a new framework for benchmarking and profiling clustering algorithms on NUMA architectures. Clubmark is designed for a long-term and crash-resistant benchmarking, and provides both console and web interfaces for process inspection. Our framework includes a dozen of state-of-the-art clustering algorithms and evaluates them on standard real-world and synthetic datasets avoiding biases (in terms of both the order of items and particular statistical distributions in a dataset). In Chapter 6, we propose an effective and efficient approach, StaTIX, to infer and complete entity types in Linked Open Data (including knowledge graphs) based on our DAOC clustering algorithm. In Chapter 7, we bridge a gap between graph clusters (also known as network communities) and a low-dimensional representation of the graph nodes, presenting our novel graph embedding technique, DAOR. DAOR is a highly efficient and parameter-free graph embedding technique producing metric space-robust, compact and interpretable embeddings without any manual tuning. Compared to a dozen state-of-the-art graph embedding algorithms, DAOR yields competitive results on diverse graph analysis tasks, while being several orders ofmagnitude more efficient. Our approach has the ambition to greatly simplify and speed up data analysis tasks involving graph representation learning (e.g., information recommendation and search). We conclude the thesis by suggesting the integration of our innovative clustering method, DAOC, into Visual Analytics frameworks and data search interfaces in Chapter 8. In the future, our approach may bridge a gap in Visual Analytics tools between a coarse-grained view on data (e.g., using the UMAP or t-SNE techniques) and a fine- grained inspection of selected points (e.g., GLC techniques). In the context of search interfaces, our approach might provide a higher diversity of the results without sacrificing their accuracy, making usersmore comprehensively informed on a topic (i.e., consideringmultiple view-points on the issue) and, hopefully, reducing social polarization. Nous vivons une ère où la quantité d’informations échangées augmente rapidement. Cette quantité croissante de données fait que la capacité de stocker, d’analyser et d’agir sur les informations une préoccupation principale (en plus des problèmes apparents de confidentialité, juridiques et éthiques qui y sont liés), soulevant la question : “Comment peut-on consommer des Big Data et la transformer en connaissances exploitables ?”. Les connaissances dans le domaine des systèmes d’information peuvent être caractérisées comme des informations explicites et traitables dans un contexte donné; les informations peuvent être définies comme des données organisées de manière significative, tandis que les données représentent des faits bruts. Tout système complexe, y compris les informations elles- mêmes, à une représentation universelle sous forme de graphique, qui est à la fois mathématiquement strict et lisible par l’Homme, même sans aucune compétence préalable. Le clustering de graphes permet d’identifier automatiquement des structures complexes et de construire une taxonomie, transformant les informations de traitement en connaissances. Les taxonomies permettent de rechercher des éléments de connaissances spécifiques en parcourant une hiérarchie de concepts (c’est-à-dire des sujets) sans connaître le titre exact ou la terminologie originale de l’élément lui-même. Cependant, ni la disponibilité d’informations complètes ni sa taxonomie ne sont suffisantes pour une recherche d’informations, une exploration des connaissances et des recommandations efficaces. L’aspect crucial ici est l’approche pour transformer l’abondance des informations récupérées d’une manière utilisable (c’est-à-dire adaptée à la perception humaine) et efficace. Dans cette thèse, nous commençons par résumer les recherches récentes sur la perception humaine et l’analyse visuelle. Ces recherches formulent les critères, selon lesquels l’information doit être transformée en connaissances pour devenir lisibles par l’homme tout en reflétant plusieurs points de vue. Ensuite, dans le chapitre 3, nous discutons des approches existantes pour construire une telle transformation et proposons notre nouvel algorithme de clustering, DAOC. Notreméthode produit efficacement une hiérarchie de groupes adaptée à la perception humaine (c’est-à-dire une taxonomie) pour tout graphe sans aucun réglage manuel et est en moyenne 25% plus précis que les méthodes analogues. Le fait que notre approche ne nécessite aucune intervention manuelle est particulièrement important pour son applicabilité et son intégration dans divers pipelines d’exploration de données, comme indiqué dans les chapitres 6 et 7. Pour garantir l’exactitude des résultats en plus d’être lisibles par l’homme, au chapitre 4, nous analysons les approches de la validation des résultats du clustering, en tenant compte des critères formulés au chapitre 2. De plus, nous étendons les mesures de précision existantes au chapitre 4, produisant à la fois a) la mise en oeuvre de l’évaluation du score moyen F1 qui fonctionne plus rapidement sur un seul processeur que des implémentations de pointe fonctionnant sur des serveurs hautes performances et b) des implémentations de NMI généralisé et Omega Index qui répondent à certaines contraintes des versions originales. Dans le chapitre 5, nous présentons Clubmark, un nouveau cadre pour l’analyse comparative et le profilage des algorithmes de clustering sur les architectures NUMA. Clubmark est conçu pour une analyse comparative à long terme et résistante aux chocs, et fournit à la fois des interfaces de console et Web pour l’inspection des processus. Notre cadre comprend une douzaine d’algorithmes de clustering de pointe (les implémentations originales par les auteurs d’algorithmes) et les évalue sur des ensembles de données standard et synthétiques évitant les biais (en termes d’ordre des éléments et de distributions statistiques particulières dans un ensemble de données). Dans le chapitre 6, nous proposons une approche efficace, StaTIX, et rapide pour déduire et compléter des types d’entités dans des données ouvertes liées (y compris des graphiques de connaissances) sur la base de notre algorithme de clustering DAOC. Dans le chapitre 7, nous comblons un fossé entre les groupes de graphes (également appelées communautés de réseaux) et une représentation à basse dimension des noeuds de graphe, présentant notre nouvelle technique d’intégration de graphes, DAOR. DAOR est une technique d’intégration graphique très efficace et sans paramètres produisant des intégrations métriques robustes, compactes et interprétables sans aucun réglagemanuel. Comparé à une douzaine d’algorithmes d’intégration de graphiques de pointe, DAOR donne des résultats compétitifs sur diverses tâches d’analyse de graphiques, tout en étant plus efficace de plusieurs ordres de grandeur. Notre approche a pour ambition de simplifier et d’accélérer considérablement les tâches d’analyse de données impliquant l’apprentissage de la représentation graphique (par exemple, la recommandation et la recherche d’informations). Nous concluons la thèse suggérant l’intégration de notre méthode innovante de clustering, DAOC, dans les frameworks Visual Analytics et les interfaces de recherche de données. À l’avenir, notre approche pourrait combler un fossé dans les outils Visual Analytics entre la vue à granularité grossière sur les données (par exemple, les techniques UMAP et t-SNE) et l’inspection à grain fin des points sélectionnés (par exemple, les techniques GLC). Dans le contexte des interfaces de recherche, notre approche fournira une plus grande diversité des résultats de livraison qui ne s’échangent pas avec leur précision, ce qui informera les utilisateurs de manière exhaustive (c’est-à-dire en considérant plusieurs points de vue sur le problème) et, espérons-le, réduira la polarisation sociale.
Faculty
Faculté des sciences et de médecine
Language
  • English
Classification
Applied sciences
Notes
  • Ressource en ligne consultée le 18.08.2020
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/308769
Statistics
Document views: 105 File downloads:
  • LutovA.pdf: 181