[PYTHON] Erklärbare KI ~ Erklärbares k-Mittel- und k-Median-Clustering ~

Dieser Artikel ist eine Einführung und eine einfache Implementierung / ein experimenteller Artikel des kürzlich gelesenen Papiers (angenommen von ICML 2020).

Der Titel lautet "Explainable k-Means and k-Medians Clustering". Arxiv finden Sie unter hier.

In diesem Artikel wird ein Ansatz vorgeschlagen, ** Clustering-Regeln mithilfe eines Entscheidungsbaums ** für k-Mittelwerte oder k-Mediane zu erhalten, bei denen es sich um Clustering-Methoden handelt. Das Erhalten von Clustering, das durch einen Entscheidungsbaum erklärt werden kann, wurde bereits in einigen früheren Studien durchgeführt, aber der Beitrag dieses Papiers ist zum ersten Mal ** ein Algorithmus, der k-Mittelwerte / k-Mediane mit einer theoretischen Garantie approximiert. Wird vorgeschlagen **, und die obere und untere Welt werden gezeigt. Wenn Sie an einer detaillierten Zusammenfassung dieses Artikels (aus diesem Artikel) interessiert sind, lesen Sie bitte die Übersicht über den unten stehenden Link. Zusammenfassung des Papiers

In diesem Artikel gab es keine Experimente in diesem Artikel, daher möchte ich die vorgeschlagenen Algorithmen kurz implementieren und überprüfen (Code. github / matsutakk / EXPLAINable-kmeans / blob / master / XAI_kmeans.ipynb)).

In diesem Artikel wird k-means / k-medians durch einen Entscheidungsbaum approximiert, wie in der folgenden Abbildung gezeigt. Wenn die Anzahl der Cluster $ k $ beträgt, hat der erstellte Baum $ k $ Blätter und jedem Blatt werden Cluster zugewiesen. Auf diese Weise wird ein Baum mit $ k-1 $ Zwischenknoten erstellt, sodass ein gewisses Maß an Erklärung garantiert werden kann (der Baum wird nicht zu tief).

Das Papier diskutiert zwei Fälle, $ k = 2 $ und $ k> 2 $. Erstens, wenn $ k = 2 $ ist, ist die Anzahl der Blätter 2 und der nicht-terminale Knoten ist 1 (nur der Wurzelknoten), daher sollte eine Teilungsregel erhalten werden. In diesem Artikel schlagen wir einen Algorithmus vor, um die optimale Merkmalsmengen-Dimension $ i $ und den Schwellenwert $ \ theta $ durch Sortieren und dynamische Programmierung zu erhalten. Es sieht wie folgt aus. Es wird behauptet, durch Sortieren und dynamische Planung effizient erhalten zu werden. Einzelheiten finden Sie im PDF der Papierzusammenfassung. Ich habe dies in Python implementiert. Bitte besuchen Sie hier für das Notizbuch. Ich habe es für zwei Datensätze gemacht, aber ich werde in diesem Artikel nur einen schreiben. Fügen Sie zunächst den Datensatz in die Variable X ein.

# First dataset
#Geben Sie die Noten für Landessprache, Mathematik und Englisch der Schüler als Array an
X = np.array([
        [  80,  85, 100 ],
        [  96, 100, 100 ],
        [  54,  83,  98 ],
        [  80,  98,  98 ],
        [  90,  92,  91 ],
        [  84,  78,  82 ],
        [  79, 100,  96 ],
        [  88,  92,  92 ],
        [  98,  73,  72 ],
        [  75,  84,  85 ],
        [  92, 100,  96 ],
        [  96,  92,  90 ],
        [  99,  76,  91 ],
        [  75,  82,  88 ],
        [  90,  94,  94 ],
        [  54,  84,  87 ],
        [  92,  89,  62 ],
        [  88,  94,  97 ],
        [  42,  99,  80 ],
        [  70,  98,  70 ],
        [  94,  78,  83 ],
        [  52,  73,  87 ],
        [  94,  88,  72 ],
        [  70,  73,  80 ],
        [  95,  84,  90 ],
        [  95,  88,  84 ],
        [  75,  97,  89 ],
        [  49,  81,  86 ],
        [  83,  72,  80 ],
        [  75,  73,  88 ],
        [  79,  82,  76 ],
        [ 100,  77,  89 ],
        [  88,  63,  79 ],
        [ 100,  50,  86 ],
        [  55,  96,  84 ],
        [  92,  74,  77 ],
        [  97,  50,  73 ],
        ])

Ungefähre k-Mittelwerte mit der vorgeschlagenen Methode (k-Mediane werden nicht durchgeführt).

#K-bedeutet Clustering
kmeans_model = KMeans(n_clusters=2, random_state=10).fit(X)
#Holen Sie sich das Etikett, das klassifiziert wurde
labels = kmeans_model.labels_

#Erhalten durch den Approximationsalgorithmus durch das vorgeschlagene Verfahren
bests_split = optimal_threshold_2means(X)
approx_labels = clustering_2means_by_tree(bests_split,X)
print(bests_split)
print(approx_labels)

Ausführungsergebnis Das obige Ergebnis bedeutet, dass der Entscheidungsbaum, der sich mit der 0. Merkmalsgröße als Schwellenwert 70 teilt, optimal ist. Inwieweit entspricht das Clustering nach der Regel dieses Entscheidungsbaums dem k-Mittel-Clustering? Unten ist der Berechnungscode.

approx_score(approx_labels,kmeans_model,X) #Ungefähre Algorithmuskosten/ k-bedeutet Kosten

Ausführungsergebnis Das obige Ergebnis bedeutet, dass das gleiche Clustering-Ergebnis wie k-means in der Anzahl der Cluster 2 durch die Regel geclustert werden kann, ob die 0. Merkmalsmenge 70 oder weniger beträgt. Mit anderen Worten, als ein Schüler diesen Datensatz aus Landessprache, Mathematik und Englisch fragte: "Warum bin ich Cluster 0 geworden?", "Weil Ihre Landessprache 70 oder weniger beträgt." Ich kann es erklären.

Eines der großartigen Dinge an diesem Artikel ist, dass er einen Approximationsalgorithmus mit theoretischer Garantie vorschlägt. Die Autoren beweisen, dass es in k-means ($ k = 2 $) eine deterministische Baumnäherung (Division $ \ widehat {C} $) mit einer optimalen Regel gibt, die die folgende Gleichung erfüllt. Mit anderen Worten, es gibt eine Teilungsregel, die eine Näherungsgenauigkeit eines konstanten Vielfachen aufweist. Egal wie groß die Dimension ist. Dieser Beweis nutzt den Satz von Hall gut.

\operatorname{cost}(\widehat{C}) \leq 4 \cdot \operatorname{cost}(o p t)

In diesem Artikel diskutieren wir $ k = 2 $ und dann $ k> 2 $. Der Algorithmus, wenn $ k> 2 $ ist, ist wie folgt. Wenn Sie an dem Ablauf und den Experimenten interessiert sind, Zusammenfassung des Papiers und [Code](https: // nbviewer) Schauen Sie sich .jupyter.org / github / matsutakk / EXPLAINable-kmeans / Blob / Master / XAI_kmeans.ipynb) an.

THANK YOU❤️