[PYTHON] AI explicable ~ Clustering k-moyennes et k-médianes explicables ~

Cet article est une introduction et une mise en œuvre simple / un article expérimental du document récemment lu (adopté par ICML 2020).

Le titre est "K-Means et k-Medians Clustering explicables", et arxiv peut être trouvé à partir ici.

Cet article propose une approche ** d'obtention de règles de clustering à l'aide d'un arbre de décision ** pour les k-moyennes ou k-médianes, qui sont des méthodes de clustering. L'obtention d'un clustering qui peut être expliqué par un arbre de décision a déjà été fait dans certaines études précédentes, mais la contribution de cet article est pour la première fois ** un algorithme qui approche les k-moyennes / k-médianes avec une garantie théorique. Est proposé **, et les mondes supérieur et inférieur sont affichés. Si vous êtes intéressé par un résumé détaillé de cet article (à partir de cet article), veuillez lire l'aperçu à partir du lien ci-dessous. Résumé du document

Dans cet article, il n'y a pas eu d'expérimentation dans cet article, donc je vais brièvement implémenter les algorithmes proposés et les vérifier (Code github / matsutakk / explicable-kmeans / blob / master / XAI_kmeans.ipynb)).

Dans cet article, les k-moyennes / k-médianes sont approximées par un arbre de décision comme le montre la figure ci-dessous. Lorsque le nombre de clusters est de $ k $, l'arbre créé aura $ k $ feuilles et les clusters seront affectés à chaque feuille. Ce faisant, un arbre avec des nœuds intermédiaires $ k-1 $ est créé, donc un certain degré d'explication peut être garanti (l'arbre ne devient pas trop profond).

Le papier discute deux cas, $ k = 2 $ et $ k> 2 $. Premièrement, si $ k = 2 $, le nombre de feuilles est 2 et le nœud non terminal est 1 (uniquement le nœud racine), donc une règle de division doit être obtenue. Dans cet article, nous proposons un algorithme pour obtenir la dimension optimale de la quantité de caractéristiques $ i $ et le seuil $ \ theta $ par tri et programmation dynamique. Cela ressemble à ce qui suit. Il est prétendu être efficacement obtenu par tri et planification dynamique. Pour plus de détails, veuillez consulter le pdf du résumé papier. J'ai implémenté cela en python. Veuillez visiter ici pour le cahier. Je l'ai fait pour deux ensembles de données, mais je n'en écrirai qu'un dans cet article. Tout d'abord, placez l'ensemble de données dans la variable X.

# First dataset
#Donnez les scores des élèves en langue nationale, en mathématiques et en anglais sous forme de tableau
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 ],
        ])

Approximer les k-moyennes avec la méthode proposée (les k-médianes ne sont pas effectuées).

#K-signifie regroupement
kmeans_model = KMeans(n_clusters=2, random_state=10).fit(X)
#Obtenez l'étiquette classée
labels = kmeans_model.labels_

#Obtenu par l'algorithme d'approximation par la méthode proposée
bests_split = optimal_threshold_2means(X)
approx_labels = clustering_2means_by_tree(bests_split,X)
print(bests_split)
print(approx_labels)

Résultat d'exécution Le résultat ci-dessus signifie que l'arbre de décision qui se divise avec la 0ème quantité de caractéristiques comme seuil 70 est optimal. Alors, dans quelle mesure le clustering par la règle de cet arbre de décision se rapproche-t-il du clustering k-means? Voici le code de calcul.

approx_score(approx_labels,kmeans_model,X) #Coût approximatif de l'algorithme/ k-signifie coût

Résultat d'exécution Le résultat ci-dessus signifie que le même résultat de clustering que k-means dans le nombre de clusters 2 peut être groupé par la règle de savoir si la 0ème quantité d'entités est de 70 ou moins. En d'autres termes, lorsqu'un élève a demandé à cet ensemble de données sur la langue nationale, les mathématiques et l'anglais, «Pourquoi suis-je devenu le groupe 0?», «Parce que votre score en langue nationale est de 70 ou moins.» Je peux l'expliquer.

L'un des grands avantages de cet article est qu'il propose un algorithme d'approximation avec une garantie théorique. Les auteurs prouvent que dans k-means ($ k = 2 $), il y a une approximation d'arbre déterministe (division $ \ widehat {C} $) avec une règle un optimale qui satisfait l'équation suivante. En d'autres termes, il existe une règle de division qui a une précision d'approximation d'un multiple constant. Peu importe la taille de la dimension. Cette preuve fait bon usage du théorème de Hall.

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

Dans cet article, nous discutons $ k = 2 $ puis $ k> 2 $. L'algorithme lorsque $ k> 2 $ est le suivant. Si vous êtes intéressé par le déroulement et les expériences de celui-ci, Résumé de l'article et [Code](https: // nbviewer) Jetez un œil à .jupyter.org / github / matsutakk / explicable-kmeans / blob / master / XAI_kmeans.ipynb).

THANK YOU❤️