Identifizieren des Unbekannten mit Clustering-Metriken

Clustering ist eine unbeaufsichtigte Methode des maschinellen Lernens, um bestimmte Daten in Gruppen zu unterteilen, die ausschließlich auf den Merkmalen jeder Probe basieren. Das Sortieren von Daten in Cluster kann helfen, unbekannte Ähnlichkeiten zwischen Proben zu identifizieren oder Ausreißer im Datensatz aufzudecken. In der realen Welt ist Clustering in verschiedenen Bereichen von Marketing bis Biologie von Bedeutung: Clustering-Anwendungen umfassen Marktsegmentierung, Analyse sozialer Netzwerke und diagnostische medizinische Bildgebung.

Da dieser Prozess nicht überwacht wird, können sich mehrere Clustering-Ergebnisse um verschiedene Features herum bilden. Stellen Sie sich zum Beispiel vor, Sie haben einen Datensatz, der aus verschiedenen Bildern von roten Hosen, schwarzen Hosen, roten Hemden und schwarzen Hemden besteht. Ein Algorithmus könnte Cluster basierend auf der Kleidungsform finden, während ein anderer Gruppen basierend auf der Farbe erstellen könnte.

Bei der Analyse eines Datensatzes benötigen wir eine Möglichkeit, die Leistung verschiedener Clustering-Algorithmen genau zu messen. Vielleicht möchten wir die Lösungen zweier Algorithmen gegenüberstellen oder sehen, wie nahe ein Clustering-Ergebnis an einer erwarteten Lösung liegt. In diesem Artikel werden wir einige der Metriken untersuchen, die zum Vergleichen verschiedener Clustering-Ergebnisse verwendet werden können, die aus denselben Daten gewonnen wurden.

Clustering verstehen: Ein kurzes Beispiel

Lassen Sie uns einen Beispieldatensatz definieren, den wir verwenden werden, um verschiedene Clustering-Metrikkonzepte zu erklären und zu untersuchen, welche Arten von Clustern er erzeugen könnte.

Zunächst einige gängige Notationen und Begriffe:

• $D$: der Datensatz
• $A$, $B$: zwei Cluster, die Teilmengen unseres Datensatzes sind
• $C$: das Ground-Truth-Clustering von $D$, mit dem wir ein anderes Cluster vergleichen werden
  • Clustering $C$ hat $K$ Cluster, $C = {C_1, …, C_k}$
• $C'$: ein zweites Clustering von $D$
  • Clustering $C'$ hat $K'$ Cluster, $C' = {C^\prime_1, …, C^\prime_{k^\prime}}$

Clustering-Ergebnisse können nicht nur basierend auf den Sortierfunktionen, sondern auch auf der Gesamtzahl der Cluster variieren. Das Ergebnis hängt vom Algorithmus, seiner Empfindlichkeit gegenüber kleinen Störungen, den Parametern des Modells und den Merkmalen der Daten ab. Unter Verwendung unseres zuvor erwähnten Datensatzes von schwarzen und roten Hosen und Hemden gibt es eine Vielzahl von Clustering-Ergebnissen, die von verschiedenen Algorithmen erzeugt werden können.

Um zwischen dem allgemeinen Clustering $C$ und unseren Beispiel-Clusterings zu unterscheiden, verwenden wir einen Kleinbuchstaben $c$, um unsere Beispiel-Clusterings zu beschreiben:

• $c$, mit Clustern basierend auf der Form: $c = {c_1, c_2}$, wobei $c_1$ Hosen und $c_2$ Hemden darstellt
• $c'$, mit Clustern basierend auf Farbe: $c' = {c'_1, c'_2}$, wobei $c'_1$ für rote Kleidung und $c'_2$ für schwarze Kleidung steht
• $c''$, mit Clustern basierend auf Form und Farbe: $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3, {c^{\prime \prime}}_4}$, wobei ${c^{\prime \prime}}_1$ für rote Hosen steht, ${c^{\prime \prime}}_2 $ steht für schwarze Hosen, ${c^{\prime \prime}}_3$ für rote Hemden und ${c^{\prime \prime}}_4$ für schwarze Hemden

Zusätzliche Clusterings können mehr als vier Cluster umfassen, die auf unterschiedlichen Merkmalen basieren, z. B. ob ein Hemd ärmellos oder mit Ärmeln ist.

Wie in unserem Beispiel zu sehen ist, teilt eine Clustering-Methode alle Stichproben in einem Datensatz in nicht leere, disjunkte Teilmengen. In Cluster $c$ gibt es kein Bild, das sowohl zur Untermenge der Hosen als auch zur Untermenge der Hemden gehört: $c_1 \cap c_2 = \emptyset$. Dieses Konzept kann erweitert werden; Keine zwei Teilmengen eines Clusters haben dieselbe Stichprobe.

Ein Überblick über Clustering-Vergleichsmetriken

Die meisten Kriterien für den Vergleich von Clustern lassen sich mit der Konfusionsmatrix des Paares $C, C'$ beschreiben. Die Konfusionsmatrix wäre eine $K \times K'$-Matrix, deren $kk'$-tes Element (das Element in der $k$-ten Zeile und der $k'$-ten Spalte) die Anzahl der Stichproben im Schnittpunkt der Cluster $ ist C_k$ von $C$ und $C'_{k'}$ von $C'$:

\[n_{kk'} = |C_k \cap C'_{k'}|\]

Wir werden dies anhand unseres vereinfachten Beispiels für schwarze und rote Hosen und Hemden aufschlüsseln, wobei wir davon ausgehen, dass der Datensatz $D$ 100 rote Hosen, 200 schwarze Hosen, 200 rote Hemden und 300 schwarze Hemden enthält. Untersuchen wir die Konfusionsmatrix von $c$ und $c''$:

Da $K = 2$ und $K'' = 4$ ist, ist dies eine $2 \times 4$ Matrix. Wählen wir $k = 2$ und $k'' = 3$. Wir sehen das Element $n_{kk'} = n_{23} = 200$. Das bedeutet, dass die Schnittmenge von $c_2$ (Hemden) und ${c^{\prime\prime}}_3$ (rote Hemden) 200 ist, was richtig ist, da $c_2 \cap {c^{\prime\prime} }_3$ wäre einfach das Set aus roten Hemden.

Clustering-Metriken können basierend auf der zugrunde liegenden Cluster-Vergleichsmethode grob in drei Gruppen eingeteilt werden:

In diesem Artikel gehen wir nur auf einige wenige der vielen verfügbaren Metriken ein, aber unsere Beispiele dienen dazu, die drei gruppierten Metrikgruppen zu definieren.

Paarzählung

Beim Pair-Counting müssen alle Probenpaare untersucht und dann die Paare gezählt werden, bei denen die Clusterings übereinstimmen und nicht übereinstimmen. Jedes Probenpaar kann zu einem von vier Sätzen gehören, wobei die Anzahl der Satzelemente ($N_{ij}$) aus der Konfusionsmatrix erhalten wird:

• $S_{11}$, mit $N_{11}$ Elementen: Die Elemente des Paars befinden sich im selben Cluster unter $C$ und $C'$
  • Ein Paar aus zwei roten Hemden würde beim Vergleich von $c$ und $c''$ unter $S_{11}$ fallen
• $S_{00}$, mit $N_{00}$ Elementen: Die Elemente des Paares befinden sich in verschiedenen Clustern unter $C$ und $C'$
  • Ein rotes Hemd und eine schwarze Hose würden beim Vergleich von $c$ und $c''$ unter $S_{00}$ fallen
• $S_{10}$, mit $N_{10}$ Elementen: Die Elemente des Paars befinden sich in $C$ im selben Cluster und in $C'$ in verschiedenen Clustern
  • Ein rotes und ein schwarzes Hemd würden beim Vergleich von $c$ und $c''$ unter $S_{10}$ fallen
• $S_{01}$, mit $N_{01}$ Elementen: Die Elemente des Paars befinden sich in verschiedenen Clustern in $C$ und demselben Cluster in $C'$
  • $S_{01}$ hat keine Elemente ($N_{01} = 0$), wenn $c$ und $c''$ verglichen werden

Der Rand-Index ist definiert als $(N_{00} + N_{11})/(n(n-1)/2)$, wobei $n$ die Anzahl der Samples darstellt; es kann auch gelesen werden als (Anzahl ähnlich behandelter Paare)/(Gesamtzahl der Paare). Obwohl sein Wert theoretisch zwischen 0 und 1 liegt, ist sein Bereich in der Praxis oft viel enger. Ein höherer Wert bedeutet mehr Ähnlichkeit zwischen den Clusterings. (Ein Rand-Index von 1 würde eine perfekte Übereinstimmung darstellen, bei der zwei Clusterings identische Cluster haben.)

Eine Einschränkung des Rand-Index ist sein Verhalten, wenn die Anzahl der Cluster steigt, um sich der Anzahl der Elemente anzunähern; In diesem Fall konvergiert es gegen 1, was zu Herausforderungen bei der genauen Messung der Cluster-Ähnlichkeit führt. Mehrere verbesserte oder modifizierte Versionen des Rand-Index wurden eingeführt, um dieses Problem zu beheben. Eine Variante ist der angepasste Rand-Index ; es wird jedoch davon ausgegangen, dass zwei Cluster mit einer festen Anzahl von Clustern und Clusterelementen zufällig gezogen werden.

Informationstheorie

Diese Metriken basieren auf allgemeinen Begriffen der Informationstheorie. Wir werden zwei davon diskutieren: Entropie und gegenseitige Information (MI).

Die Entropie beschreibt, wie viele Informationen in einem Clustering enthalten sind. Wenn die einer Clusterbildung zugeordnete Entropie 0 ist, dann gibt es keine Unsicherheit über die Cluster einer zufällig ausgewählten Stichprobe, was zutrifft, wenn es nur einen Cluster gibt.

MI beschreibt, wie viele Informationen ein Clustering über das andere gibt. MI kann angeben, wie sehr die Kenntnis des Clusters einer Stichprobe in $C$ die Unsicherheit über die Cluster der Stichprobe in $C'$ reduziert.

Normalisierte gegenseitige Informationen sind MI, die durch das geometrische oder arithmetische Mittel der Entropien von Clustern normalisiert sind. Standard-MI ist nicht an einen konstanten Wert gebunden, sodass normalisierte gegenseitige Informationen eine besser interpretierbare Clustering-Metrik bieten.

Eine weitere beliebte Metrik in dieser Kategorie ist die Informationsvariation (VI), die sowohl von der Entropie als auch vom MI der Clusterbildung abhängt. Sei $H(C)$ die Entropie einer Clusterbildung und $I(C, C')$ der MI zwischen zwei Clusterbildungen. VI zwischen zwei Clustern kann definiert werden als $VI(C,C') = H(C)+H(C')-2I(C,C')$. Ein VI von 0 repräsentiert eine perfekte Übereinstimmung zwischen zwei Clusterings.

Überlappung einstellen

Das Festlegen von Überlappungsmetriken beinhaltet das Bestimmen der besten Übereinstimmung für Cluster in $C$ mit Clustern in $C'$ basierend auf der maximalen Überlappung zwischen den Clustern. Für alle Metriken in dieser Kategorie bedeutet eine 1, dass die Clusterings identisch sind.

Das Maximum-Übereinstimmungsmaß durchsucht die Konfusionsmatrix in absteigender Reihenfolge und stimmt zuerst mit dem größten Eintrag der Konfusionsmatrix überein. Es entfernt dann die übereinstimmenden Cluster und wiederholt den Vorgang sequentiell, bis die Cluster erschöpft sind.

Das F-Maß ist eine weitere Satzüberlappungsmetrik. Im Gegensatz zum maximalen Übereinstimmungsmaß wird das F-Maß häufig verwendet, um ein Clustering mit einer optimalen Lösung zu vergleichen, anstatt zwei Clusterings zu vergleichen.

Anwenden von Clustering-Metriken mit F-Maß

Da das F-Maß häufig in maschinellen Lernmodellen und wichtigen Anwendungen wie Suchmaschinen verwendet wird, werden wir das F-Maß anhand eines Beispiels genauer untersuchen.

F-Maß-Definition

Nehmen wir an, dass $C$ unsere Grundwahrheit oder optimale Lösung ist. Für jeden $k$-ten Cluster in $C$, wobei $k \in [1, K]$ ist, berechnen wir ein individuelles F-Maß mit jedem Cluster im Clustering-Ergebnis $C'$. Dieses individuelle F-Maß gibt an, wie gut der Cluster $C^\prime_{k'}$ den Cluster $C_k$ beschreibt und lässt sich durch Precision und Recall (zwei Modellbewertungsmetriken) für diese Cluster bestimmen. Definieren wir $I_{kk'}$ als Schnittpunkt der Elemente im $k$-ten Cluster von $C$ und im $k'$-ten Cluster von $C'$ und $\lvert C_k \rvert$ als Zahl von Elementen im $k$ten Cluster.

• Genauigkeit $p = \frac{I_{kk'}}{\lvert C'_{k'} \rvert}$

  

• Erinnere dich an $r = \frac{I_{kk'}}{\lvert C_{k} \rvert}$

Dann kann das einzelne F-Maß des $k$th- und $k'$th-Clusters als harmonischer Mittelwert der Präzision und des Abrufs für diese Cluster berechnet werden:

\[F_{kk'} = \frac{2rp}{r+p} = \frac{2I_{kk'}}{|C_k|+|C'_{k'}|}\]

Um nun $C$ und $C'$ zu vergleichen, schauen wir uns das gesamte F-Maß an. Zunächst erstellen wir eine Matrix ähnlich einer Kontingenztabelle, deren Werte die einzelnen F-Maße der Cluster sind. Nehmen wir an, wir haben die Cluster von $C$ als Zeilen einer Tabelle und die Cluster von $C'$ als Spalten abgebildet, wobei die Tabellenwerte einzelnen F-Kennzahlen entsprechen. Identifizieren Sie das Cluster-Paar mit dem maximalen individuellen F-Maß und entfernen Sie die Zeile und Spalte, die diesen Clustern entsprechen. Wiederholen Sie dies, bis die Cluster erschöpft sind. Schließlich können wir das gesamte F-Maß definieren:

\[F(C, C') = \frac{1}{n} \sum_{i=1}^K n_imax(F(C_i, C'_j)) \forall j \in {1, K'}\ ]

Wie Sie sehen können, ist das Gesamt-F-Maß die gewichtete Summe unserer maximalen individuellen F-Maßnahmen für die Cluster.

Dateneinrichtung und erwartete Ergebnisse

Jedes für maschinelles Lernen geeignete Python-Notebook, z. B. ein Jupyter-Notebook, funktioniert als unsere Umgebung. Bevor wir beginnen, sollten Sie sich die README-Datei, die erweiterte Beispieldatei „ readme_help_example.ipynb “ und die Datei „ requirements.txt “ (die erforderlichen Bibliotheken) meines GitHub-Repositorys ansehen.

Wir verwenden die Beispieldaten im GitHub-Repository, das aus Nachrichtenartikeln besteht. Die Daten sind mit Informationen wie category , headline , date und short_description :

Wir können Pandas verwenden, um die Daten zu lesen, zu analysieren und zu manipulieren. Wir sortieren die Daten nach Datum und wählen eine kleine Stichprobe (10.000 Schlagzeilen) für unsere Demo aus, da der vollständige Datensatz groß ist:

 import pandas as pd df = pd.read_json("./sample_data/example_news_data.json", lines=True) df.sort_values(by='date', inplace=True) df = df[:10000] len(df['category'].unique())

Beim Ausführen sollte das Notebook das Ergebnis 30 ausgeben, da dieses Datenbeispiel 30 Kategorien enthält. Sie können auch df.head(4) , um zu sehen, wie die Daten gespeichert werden. (Sie sollte mit der Tabelle in diesem Abschnitt übereinstimmen.)

Optimierung der Clustering-Funktionen

Bevor wir das Clustering anwenden, sollten wir zunächst den Text vorverarbeiten, um redundante Funktionen unseres Modells zu reduzieren, einschließlich:

• Aktualisierung des Textes, um einen einheitlichen Fall zu haben.
• Entfernen von Zahlen oder Sonderzeichen.
• Lemmatisierung durchführen.
• Stoppwörter entfernen.

 import re import nltk from nltk.corpus import stopwords from nltk.stem import WordNetLemmatizer wordnet_lemmatizer = WordNetLemmatizer() nltk.download('stopwords') stop_words = stopwords.words('english') nltk.download('wordnet') nltk.download('omw-1.4') def preprocess(text: str) -> str: text = text.lower() text = re.sub('[^az]',' ',text) text = re.sub('\s+', ' ', text) text = text.split(" ") words = [wordnet_lemmatizer.lemmatize(word, 'v') for word in text if word not in stop_words] return " ".join(words) df['processed_input'] = df['headline'].apply(preprocess)

Die resultierenden vorverarbeiteten Schlagzeilen werden als „ processed_input “ angezeigt, was Sie beobachten können, indem Sie erneut df.head(4) :

Jetzt müssen wir jede Überschrift als numerischen Vektor darstellen, um ein beliebiges maschinelles Lernmodell darauf anwenden zu können. Es gibt verschiedene Merkmalsextraktionstechniken, um dies zu erreichen; Wir werden TF-IDF (Term Frequency-Inverse Document Frequency) verwenden. Diese Technik reduziert die Wirkung von Wörtern, die mit hoher Häufigkeit in Dokumenten vorkommen (in unserem Beispiel Nachrichtenschlagzeilen), da diese eindeutig nicht die entscheidenden Merkmale bei der Clusterung oder Klassifizierung sein sollten.

 from sklearn.cluster import AgglomerativeClustering, KMeans from sklearn.feature_extraction.text import TfidfVectorizer vectorizer = TfidfVectorizer(max_features=300, tokenizer=lambda x: x.split(' ')) tfidf_mat = vectorizer.fit_transform(df['processed_input']) X = tfidf_mat.todense() X[X==0]=0.00001

Als nächstes werden wir unsere erste Clustering-Methode, das agglomerative Clustering, an diesen Merkmalsvektoren ausprobieren.

Clustering-Methode 1: Agglomeratives Clustering

Betrachten wir die gegebenen Nachrichtenkategorien als optimale Lösung und vergleichen wir diese Ergebnisse mit denen des agglomerativen Clustering (mit der gewünschten Anzahl von Clustern von 30, da der Datensatz 30 Kategorien enthält):

 clusters_agg = AgglomerativeClustering(n_clusters=30).fit_predict(X) df['class_prd'] = clusters_agg.astype(int)

Wir werden die resultierenden Cluster durch Integer-Labels identifizieren; Schlagzeilen, die zu demselben Cluster gehören, wird dasselbe Integer-Label zugewiesen. Die Funktion „ cluster_measure aus dem Modul compare_clusters unseres GitHub-Repositorys gibt das aggregierte F-Maß und die Anzahl der perfekt übereinstimmenden Cluster zurück, damit wir sehen können, wie genau unser Clustering-Ergebnis war:

 from clustering.compare_clusters import cluster_measure # 'cluster_measure` requires given text categories to be in the column 'text_category` df['text_category'] = df['category'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.19858339749319176, 0)

Beim Vergleich dieser Cluster-Ergebnisse mit der optimalen Lösung erhalten wir ein niedriges F-Maß von 0,198 und 0 Cluster, die mit tatsächlichen Klassengruppen übereinstimmen, was zeigt, dass die agglomerativen Cluster nicht mit den von uns gewählten Überschriftenkategorien übereinstimmen. Schauen wir uns einen Cluster im Ergebnis an, um zu sehen, wie er aussieht.

 df[df['class_prd'] == 0]['category'].value_counts()

Bei der Untersuchung der Ergebnisse sehen wir, dass dieser Cluster Schlagzeilen aus allen Kategorien enthält:

 POLITICS 1268 ENTERTAINMENT 712 THE WORLDPOST 373 HEALTHY LIVING 272 QUEER VOICES 251 PARENTS 212 BLACK VOICES 211 ... FIFTY 24 EDUCATION 23 COLLEGE 14 ARTS 13

Unser niedriges F-Maß ist also sinnvoll, wenn man bedenkt, dass die Cluster unseres Ergebnisses nicht mit der optimalen Lösung übereinstimmen. Es ist jedoch wichtig, sich daran zu erinnern, dass die von uns gewählte gegebene Kategorieklassifizierung nur eine mögliche Unterteilung des Datensatzes widerspiegelt. Ein niedriges F-Maß bedeutet hier nicht, dass das Clustering-Ergebnis falsch ist, sondern dass das Clustering-Ergebnis nicht mit unserer gewünschten Methode zum Partitionieren der Daten übereinstimmt.

Clustering-Methode 2: K-Means

Lassen Sie uns einen anderen beliebten Clustering-Algorithmus für denselben Datensatz ausprobieren: k-Means-Clustering. Wir erstellen einen neuen Datenrahmen und verwenden erneut die Funktion cluster_measure :

 kmeans = KMeans(n_clusters=30, random_state=0).fit(X) df2 = df.copy() df2['class_prd'] = kmeans.predict(X).astype(int) res_df, fmeasure_aggregate, true_matches = cluster_measure(df2) fmeasure_aggregate, len(true_matches) # Outputs: (0.18332960871141976, 0)

Wie das agglomerative Clustering-Ergebnis hat unser k-Means-Clustering-Ergebnis Cluster gebildet, die sich von unseren gegebenen Kategorien unterscheiden: Es hat ein F-Maß von 0,18 im Vergleich zur optimalen Lösung. Da die beiden Clustering-Ergebnisse ähnliche F-Maße haben, wäre es interessant, sie miteinander zu vergleichen. Wir haben bereits die Clusterings, also müssen wir nur das F-Maß berechnen. Zuerst bringen wir beide Ergebnisse in eine Spalte, wobei class_gt die agglomerative Clustering-Ausgabe und class_prd die k-Means-Clustering-Ausgabe hat:

 df1 = df2.copy() df1['class_gt'] = df['class_prd'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df1, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.4030316435020922, 0)

Bei einem höheren F-Maß von 0,4 können wir beobachten, dass die Clusterings der beiden Algorithmen einander ähnlicher sind als der optimalen Lösung.

Erfahren Sie mehr über verbesserte Clustering-Ergebnisse

Ein Verständnis der verfügbaren Clustering-Vergleichsmetriken wird Ihre Modellanalyse für maschinelles Lernen erweitern. Wir haben die F-Measure-Clustering-Metrik in Aktion gesehen und Ihnen die Grundlagen vermittelt, die Sie benötigen, um diese Erkenntnisse auf Ihr nächstes Clustering-Ergebnis anzuwenden. Um noch mehr zu erfahren, hier sind meine Top-Picks zum Weiterlesen:

• Clusterings vergleichen – Ein Überblick von Dorothea Wagner und Silke Wagner
• Clusterings vergleichen – eine informationsbasierte Distanz von Marina Meila
• Informationstheoretische Maße für den Vergleich von Clusterings: Varianten, Eigenschaften, Normalisierung und Zufallskorrektur von Nguyen Xuan Vinh, Julien Epps und James Bailey

---

Weiterführende Literatur im Toptal Engineering Blog:

• Graph Data Science mit Python/NetworkX
• Halbüberwachte Bildklassifizierung mit unbeschrifteten Daten
• Einbettungen in maschinelles Lernen: Komplexe Daten einfach machen

Der Toptal Engineering Blog dankt Luis Bronchal für die Überprüfung der in diesem Artikel vorgestellten Codebeispiele.