Kevin Widholm
27. April 2020
8 Min.

Hierarchical Clustering unserer Confluence-Struktur

Warst Du auch schon einmal in der Situation eine riesige Datenmenge von Hand strukturieren zu müssen? Dann haben wir die perfekte Lösung für Dich! Die Rede ist vom Konzept des Hierarchical Clustering. Bei Novatec haben wir diese Methode zur übersichtlichen Strukturierung unserer internen Confluence-Stuktur bereits erfolgreich umgesetzt. In diesem Blogbeitrag stellen wir dir unsere Vorgehensweise dar und liefern eine Anleitung zur eigenen Programmierung.

Use Case

Das Bilden von Kontext in unstrukturierten Daten ist keine neue Idee. Tatsächlich versucht man schon seit langem, Text zu kontextualisieren. Im Zeitalter von Big Data sammeln sich in Organisationen riesige Mengen unstrukturierter Daten an. In unserem Fall enthält die Confluence-Intranetseite unseres Teams genau 138 Überschriften und Unterüberschriften. Einige davon sind redundant vorhanden, andere Unterseiten sind leer. Daher bestand unsere Herausforderung darin, den gesamten Seiteninhalt in einige wenige Themen umzustrukturieren. Auf diese Weise können unsere Mitarbeiter die gesuchten Themen leichter finden.

Hierarchical Clustering

Die Herausforderung, Texte in einen Kontext zu setzen, lässt sich mit der Technologie Hierarchical Document Clustering lösen. Der Algorithmus für unbeaufsichtigtes Text-Clustering ermöglicht es Unternehmen, ihre Daten programmgesteuert zu binden und eine Hierarchie von Clustern aufzubauen. Dabei kann zwischen agglomerativem und teilendem Clustering unterschieden werden. Wir werden agglomerativ vorgehen und die Objekte nach ihrer Ähnlichkeit in immer größere Cluster gruppieren. Zunächst erzeugt der Algorithmus für jedes Objekt einen eigenen Cluster. Danach werden die Cluster solange gepaart bis alle Cluster mit allen Objekten zu einem einzigen Cluster vereint sind. Alle Vereinigungsschritte werden in einem Dendrogramm, einer baumbasierten Visualisierung, dargestellt. In Bezug auf unseren Use Case erhalten wir demzufolge Dokumenten-Cluster mit ähnlichem Seiteninhalt und eine automatische Gruppierung der Themenüberschriften.

Sammeln der Daten

Die Datenvorbereitung ist oft der mühsamste Teil von Clustering-Projekten. Sobald alle für die Berechnung erforderlichen Daten im richtigen Format vorliegen, müssen wir sie nur noch in unseren Algorithmus eingeben und auf die Ergebnisse warten.

Der Anfang der Vorbereitung ist das Sammeln der Daten. Wir haben zwei Listen mit allen erforderlichen Informationen erstellt:

  • Headings: Die Überschriften der Intranet-Seiten in ihrer Reihenfolge wie sie im Navigationsbaum sortiert waren.
  • Content: Der Inhalt der Seiten in der selben Reihenfolge wie die Headings.

Es ist darauf zu achten, dass beide Listen aufeinander abgestimmt sind. Um die Einträge zueinander abzugrenzen, setzen wir ein Schlüsselwort dazwischen, wie z.B. „BREAKS HERE“.

Vorverarbeitung der Daten

Jetzt verändern wir unseren Datensatz, damit unser Clustering-Algorithmus damit arbeiten kann. Daher haben wir einige Funktionen zur Manipulation des Seiteninhalts definiert. Zuerst laden wir die Liste der englischen und deutschen Stopwords, also Wörter ohne besondere Bedeutung wie Präpositionen, von NLTK in einem Jupyter Notebook. Zusätzlich haben wir eine eigene Stopword-Liste generiert, die Wörter enthält, die in vielen unserer Seiten vorkommen, und nicht in der NLTK-Liste enthalten sind, z.B. unseren Firmennamen. Wir wollen diese Wörter nicht in unsere Analyse aufnehmen, da sie sehr wenig über den eigentlichen Inhalt einer Seite aussagen.


Welches sind die häufigsten Wörter in unseren Seiten? Um unseren Datensatz besser zu verstehen, filtern wir die häufigsten Wörter heraus. Deshalb instanziieren wir ein Wörterbuch und zählen jedes Wort. Das folgende Diagramm veranschaulicht die 10 häufigsten Wörter:

Wir können an den gezählten Werten erkennen, dass verschiedene Wortvariationen mit demselben Wortstamm (z.B. offering und offerings) doppelt angezeigt werden. Um dies im weiteren Verlauf unserer Analyse zu verhindern, wenden wir einen Stemming-Algorithmus an, der jedes Wort auf den Wortstamm kürzt.

Unser Datensatz liegt immer noch nicht in der gewünschten Form vor, wie wir sie in unseren Clustering-Algorithmus eingeben könnten. Wir müssen sie in ein Vektorformat konvertieren. Dazu verwenden wir Term frequency–inverse document frequency (Tf-idf). Tf-idf gewichtet die Wörter entsprechend ihrer Bedeutung im Kontext zum Gesamtinhalt. Die Wörter, die auf fast allen Seiten häufig verwendet werden, haben eine geringere Gewichtung, während seltene Wörter eine höhere Gewichtung haben.

Um unsere Inhalte in eine Tf-idf-Matrix zu konvertieren, zählen wir zunächst die Wörter pro Seite und erhalten eine Dokument-Term-Matrix (DTM).

Nun gewichten wir die Zellen anhand der Zeilen- und Spaltensummen und erhalten unsere Tf-idf-Struktur. Sämtliche Wörter bzw. Tokens, die häufig innerhalb einer Seite, aber nicht häufig im gesamten Dokumentkorpus vorkommen, erhalten eine höhere Gewichtung! Alle diese Schritte lassen sich sehr bequem über den Tf-idf-Vectorizer von Scikit-Learn umsetzen:


Unsere Seitenmenge in unserem Korpus wird dann als eine Menge von Vektoren in einem Vektorraum betrachtet. Jedes Wort hat seine eigene Achse. Mit Hilfe der Cosine Similarity können wir die Ähnlichkeit zwischen zwei beliebigen Dokumenten herausfinden. Es misst, wie ähnlich sich zwei Datenobjekte sind, und wird insbesondere im positiven Raum verwendet.

In unserem Fall berechnen wir den Kosinus-Abstand (dist), der durch die Subtraktion der Kosinus-Ähnlichkeit von eins bestimmt wird. Dadurch können wir eine „Entfernung“ zwischen unseren Inhaltsseiten für das Clustering definieren.

Hierarchical Clustering der Daten

Nun kommt der spannende Teil. Wir speisen unsere generierte Tf-idf-Matrix in den Hierarchical Clustering-Algorithmus ein, um unsere Seiteninhalte zu strukturieren und besser zu verstehen. Hierbei bedienen wir uns bei den Funktionen der Python Scipy Bibliothek Hierarchical Clustering.

In unserem Fall benötigen wir die Funktion Complete, die für Complete-linkage Agglomerative Clustering steht. Zu Beginn des Prozesses befindet sich jedes Element in einem eigenen Cluster. Die Cluster werden dann nacheinander zu größeren Clustern zusammengefasst, bis alle Elemente im selben Cluster landen. Complete versucht die Gruppen dabei möglichst kompakt zu halten und ist auch als Farthest Neighbor Clustering bekannt. Das Ergebnis des Clustering visualisieren wir anschließend als Dendrogramm, das die Abfolge der Clusterfusionen und den Abstand, in dem jede Fusion stattfindet, anzeigt.

In diese Funktion können wir die sog. Leaf_label_function (Kurz: LLf) übergeben, um die Ausgabelabels des Dendrogramms zu manipulieren. In unserem Fall wollen wir die Funktion insofern anpassen, dass folgende Ausgaben angezeigt werden:

  • ID: Position der Seite in der ursprünglichen Struktur.
  • Heading: Überschrift der Seite.
  • Tf-idf-Keys: Charakteristische Worte mit hohem Tf-idf-Wert auf der jeweiligen Seite.


Des Weiteren möchten wir unsere neue Struktur mit der alten Struktur vergleichen können. Hierzu mappen wir die Position in der ursprünglichen Seitenstruktur auf die Farbe. Auf diese Weise können wir erkennen, an welchen Stellen ein großer Unterschied zur ursprünglichen Seitenstruktur besteht. Dies ist genau dann der Fall, wenn verschiedenfarbige Seiten nahe beieinander liegen.

Zur Darstellung unseres Dendrogramms verwenden wir Fancy_dendrogram, eine Implementierung mit einigen sinnvollen Erweiterungen des Dendrogramms.

Visualisierung

Wenn wir nun unser Dendrogramm zeichnen, erhalten wir folgendes Ergebnis:

Aufgrund des Datenschutzes wurde auf der y-Achse lediglich die ID mit der Farbcodierung der alten Struktur gezeichnet. Es existieren mehrere Blöcke, bei denen Seiten aus unterschiedlichen Stellen nebeneinander angeordnet wurden (z.B. bei den schwarzen Linien). Dies bedeutet, dass die alte Struktur an diesen Stellen stark verändert wurde.

Möchte man nun eine Gliederung aus dem Dendrogramm ablesen, so kann man sich für eine maximale Distanz der Seiten innerhalb des Cluster entscheiden. Das zeigt sich im Dendrogramm als horizontale Linie (hier bei d=2.7) und definiert damit aus der kompletten hierarchischen Cluster-Struktur eine konkrete Clusterzuteilung der Seiten. Im Diagramm wird das als die unterschiedlich-farbigen Linien gezeigt. Die neue Struktur lässt sich nun anhand weniger Codezeilen auf eine 2-dimensionalen Abbildung darstellen. Zu diesem Zweck ermitteln wir für jede Seite die Cluster-ID (1-13). Die Scipy-Funktion fcluster gibt uns diese Cluster-ID aus. Zudem verwenden wir eine multidimensionale Skalierung, die unsere Distanz-Matrix in einen 2D-Array umwandelt.


 


Jede Seite wurde zu einem der 13 Cluster zugeordnet. Um ein tieferes Verständnis des Hauptthemas jedes einzelnen Clusters zu gewinnen, identifizieren wir nun die charakteristischen Wörter der Cluster. Diesbezüglich berechnen wir erneut die höchsten Tf-idf-Werte, nur dieses Mal hinsichtlich eines kompletten Clusters. In die folgende Funktion „calculate_tf“ übergeben wir einen Pandas Dataframe, der die Seiten für jeden einzelnen Cluster enthält. Demnach haben wir 13 Dataframes.


Das Ergebnis zeigen wir an dieser Stelle nicht, da es unsere internen Seiten betrifft. Wir konnten hier anhand der Begriffe Cluster zur Ausarbeitung neuer Schulungen und Dienstleistungsangeboten, zur Neugestaltung der Webseite sowie zur Organisation und Darstellung unseres Teams identifizieren.

Fazit

Inwieweit waren diese Ergebnisse hilfreich für unsere Confluence-Struktur bei der Novatec?

Aufgrund der Tatsache, dass unsere Confluence-Daten teilweise über Templates erfasst wurden, existierten mehrere Seiten mit leerem Content bzw. gleichem Muster. Dadurch konnten verschiedene Seiten, die zwar aufgrund ihrer Themen zusammengehören, nicht zu einem Cluster zusammengeführt werden. Trotzdem ist es uns gelungen über den Ansatz des Hierarchischen Clustering eine grobe Neustrukturierung vorzunehmen, die unsere generellen Themenschwerpunkte wiederspiegelt. Wir kommen demnach zu dem Resultat, dass unter der Voraussetzung aussagekräftiger Grunddaten die Methode des Hierarchical Clustering erfolgreich eingesetzt werden kann!

Wir hoffen du kannst bei deiner nächsten Datenstrukturierung einige der Ansätze umsetzen. Denn strukturierte Daten bieten Dir und deinem Umfeld einen erhöhten Mehrwert!

Bei Fragen und Anmerkungen zu diesem Artikel kannst Du dich gerne an die E-Mail machine-learning@novatec-gmbh.de wenden oder, wenn du dich allgemein tiefgehend mit Machine Learning auseinandersetzen möchtest, eine unserer Machine Learning Schulungen besuchen!

Artikel kommentieren