Clustering

In vielen Kontexten der Datenverarbeitung kommt es vor, dass man Einheiten eines Typs gruppieren möchte. Clustering bezeichnet eine Analyse der vorliegenden Daten, bei der jedem Datenpunkt eine Klasse zugewiesen wird. In einem Cluster werden Daten zusammengefasst, die sich ähnlich sind. Man kann Clusteringverfahren benutzen, um neue Daten automatisch in vorhandene Gruppen hinzuzufügen oder um vorhandene Daten auf ihre Gruppierung hin zu analysieren. Dafür braucht man keine Beispieldaten, die man vorher per Hand in vorgegebene Gruppen eingeteilt hat. Also handelt es sich um ein unüberwachtes Lernverfahren.

Anwendung bei Chatbots

Im Kontext von Chatbots ist Clustering hilfreich zur initialen Datenanalyse, sofern historische Daten gegeben sind. So kann man zum Beispiel aus der Chathistorie bestimmen, welche Intents erstellt werden sollten. Im Betrieb eines Chatbots können außerdem gesammelte Sätze, die keinen Intent getroffen haben, durch Clustering in eine Struktur gebracht und so neue Intents identifiziert werden.

Funktionsweise:
Für ein Clustering braucht man zunächst eine Datenrepräsentation. Im Normalfall werden Daten als Zahlenvektoren dargestellt, wobei einzelne Dimensionen des Vektors Eigenschaften der Daten widerspiegeln. Um diese nun sinnvoll zu gruppieren, benötigt man ein Maß für Ähnlichkeit. In den meisten Fällen wird hierfür die euklidische Distanz benutzt. [1] Je nach Algorithmus kann diese Metrik und die Art wie die Daten den Gruppen zugeteilt werden variieren.

Nearest Neighbor

Die einfachste Art wäre, dass man am Anfang einer gewissen Anzahl an Datenpunkten zufällig eine Klasse zuweist und daraufhin für allen anderen Punkten die Klasse annimmt, die ihr nächster Nachbar hat.

Wenn diese Methode aber zu ungenau ist, kann man sie erweitern, indem man statt nur einem Nachbar die Klassen von mehreren Nachbarn in Betracht zieht und die Klasse wählt, die am häufigsten vorkommt.[2]

Centroid-basierte Verfahren

Noch besser werden die Ergebnisse, wenn man Centroid-basierte Verfahren benutzt. Hierbei wird für jedes Cluster ein Zentrumspunkt bestimmt (zum Beispiel der Mittelwert aller Punkte eines Clusters) und dieser als Referenzpunkt für die Zuweisung benutzt. Am Anfang können diese Centroids zufällig gesetzt werden. Für die Daten wird dann jeweils die Entfernung zu allen Zentren berechnet. Der Datenpunkt kommt dann in das Cluster zu dem er die geringsten Entfernung hat. Daraufhin wird der Centroid entsprechend angepasst, weil durch das Hinzufügen eines Punkts ein neuer Mittelwert entsteht. Das Zentrum wandert mit der Zeit. Sobald ein Konvergenzkriterium erfüllt ist (zum Beispiel wenn die Änderungen der Centroids zu klein sind), stoppt der Algorithmus. [3][4]

Textrepräsentation: Bag of Words

Textdaten können auf verschiedene Weisen in Vektoren repräsentiert werden. In einfachen Anwendungsfällen kann man zum Beispiel ein Vokabular definieren, das man sich wie eine Tabelle vorstellen kann, in dem jedes Wort einer ganzen Zahl (wie eine ID) entspricht. Mit Hilfe einer solchen Tabelle kann nun ein Satz in ein Vektor umgewandelt werden. Jeder Satz entspricht einem Vektor, bei dem jede Dimension einem Wort des Vokabulars entspricht. Für jedes Wort, das im Satz vorkommt, erhält die Dimension den Wert 1, alle nicht vorhandenen Worte bleiben auf 0. [5] 

Textrepräsentation: Deep Learning Modelle 

Für eine Repräsentation, die mehr semantische Eigenschaften des Texts beinhaltet benutzt man Vektoren, die durch Deep Learning-Verfahren entstehen. Für diese Art von Verfahren werden viele Daten benötigt. Zum Beispiel kann man mit recurrent neural networks (RNNs) Sprachmodelle trainieren, indem man immer das nächste Wort für eine gegebene Wortsequenz vorhersagt. Dies funktioniert so, dass man die Sequenz in einem Encoder-RNN zu einem Vektor umwandelt und mit einem Decoder-RNN den Vektor in das folgende Wort übersetzt. Wenn man jetzt nur den Encoder benutzt, erhält man eine Vektorrepräsentation des Satzes, die deutlich weniger Dimensionen als bei einem Bag-of-Words Ansatz hat und mehr semantischen Inhalt besitzt.

> Zurück zum BOTwiki - Das Chatbot Wiki

Quellen

[1] https://sites.google.com/a/erhard-rainer.com/erhard-rainer/mathematik/distanz-zwischen-zwei-punkten
[2] k-nearest neighbors, https://towardsdatascience.com/k-nearest-neighbours-introduction-to-machine-learning-algorithms-18e7ce3d802a
[3] https://www.youtube.com/watch?v=_aWzGGNrcic
[4] https://www-m9.ma.tum.de/material/felix-klein/clustering/Methoden/K-Means.php
[5] https://machinelearningmastery.com/gentle-introduction-bag-words-model/