説明できるAI ~Explainable k-Means and k-Medians Clustering~

この記事は，最近読んだ論文(ICML 2020採択)の紹介&簡単な実装・実験記事です．

タイトルは"Explainable k-Means and k-Medians Clustering"で，arxivは[こちら](https://arxiv.org/pdf/2002.12538.pdf)からどうぞ．


本論文は，クラスタリングの手法であるk-meansまたはk-mediansに対して，**決定木を用いてクラスタリングのルールを得る**というアプローチを提案しています．決定木で説明可能なクラスタリングを得るというのは，先行研究としてはいくつか既にあるのですが，この論文の貢献は，初めて**理論的保証付きのk-means/k-mediansを近似するアルゴリズムを提案**し，その上界と下界を示しています．この論文の(この記事よりかは)詳しいまとめに関して興味がある方は，是非以下のリンクから概要だけでも読んでみてください．
[論文のまとめ](https://drive.google.com/file/d/1gEPmBCM6pXQIYvIgVYICOguZELGDjYVK/view?usp=sharing)

本記事では，この論文では実験などは全くなかったため，提案されたアルゴリズムを簡単にですが実装し，それらを確認してみようと思います([コード](https://nbviewer.jupyter.org/github/matsutakk/explainable-kmeans/blob/master/XAI_kmeans.ipynb))．

この論文では，以下の図のように，k-means/k-mediansを決定木で近似します．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223338/aa919fff-6b08-f8ec-2593-c1839b4c2891.png)
クラスタ数を$k$としたとき，作成される木は葉を$k$個として，それぞれの葉にクラスタが振られるようにします．そうすることで，$k-1$個の中間ノードによる木が作成されるので，ある程度の説明性が担保できます(木が深くなりすぎない)．

論文では，$k=2$と$k>2$の2つの場合について，論じています．まず，$k=2$の場合，葉の数2,非終端ノード1(rootノードだけ)なので，1つの分割ルールを得ればいいことになります．これをこの論文では，ソートと動的計画法によって，最適な特徴量の次元$i$と閾値$\theta$を得るアルゴリズムを提案しています．以下のような感じです．ソートと動的計画法によって，効率よく求められると主張されています．詳しくは論文まとめのpdfを見てみてください．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223338/f3062917-3ce5-b471-0f33-dee881cc102f.png)
これをpythonで実装しました．ノートブックは[ここ](https://nbviewer.jupyter.org/github/matsutakk/explainable-kmeans/blob/master/XAI_kmeans.ipynb)からどうぞ．2つのデータセットに対して行いましたが，この記事内では1つだけ書きます．まず，データセットを変数Xに入れます．

```python
# First dataset
# 生徒の国語・数学・英語の各得点を配列として与える
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 ],
        ])
```

提案手法でk-meansを近似します（k-mediansはやってません）．

```python
#K-meansクラスタリングをおこなう
kmeans_model = KMeans(n_clusters=2, random_state=10).fit(X)
#分類先となったラベルを取得する
labels = kmeans_model.labels_

#提案手法による近似アルゴリズムで取得する
bests_split = optimal_threshold_2means(X)
approx_labels = clustering_2means_by_tree(bests_split,X)
print(bests_split)
print(approx_labels)
```
実行結果
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223338/11cd8517-990c-7d54-44a2-4ac4c1166419.png)
上の結果はつまり，0番目の特徴量で閾値70として分割する決定木が最適だということです．では，この決定木のルールによるクラスタリングはどのくらいk-meansのクラスタリングを近似しているのでしょうか．以下が計算コードです．

```python
approx_score(approx_labels,kmeans_model,X) #近似アルゴリズムのコスト / k-meansのコスト
```
実行結果
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223338/f3209df1-2f81-cc80-cae3-e553265ffb57.png)
上の結果は，クラスタ数2におけるk-meansと同じクラスタリング結果を,0番目の特徴量が70以下か否かのルールでクラスタリングできていることになります．つまり，この国語，数学，英語のデータセットに対して，ある生徒が，「なぜ僕はクラスタ0になったんですか？」と質問をしてきたとき，「それは君の国語の点が70以下だからだよ」と説明してあげることができます．

この論文の1つの良さは，理論的保証つきの近似アルゴリズムを提案しているところです．著者らはk-means($k=2$)において，以下の式を満たすような最適な1ルールによる決定木近似（分割$\widehat{C}$）が存在することを証明しています．つまり，定数倍の近似精度であるような分割ルールが存在するということです．次元がいくら大きくてもです．この証明は，ホールの定理をうまく使って証明しています．

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

```

この論文では，$k=2$について論じた後，$k>2$について論じています．$k>2$の場合のアルゴリズムは以下になります．これの流れや実験などに興味がございましたら，[論文のまとめ](https://drive.google.com/file/d/1gEPmBCM6pXQIYvIgVYICOguZELGDjYVK/view?usp=sharing)と[コード](https://nbviewer.jupyter.org/github/matsutakk/explainable-kmeans/blob/master/XAI_kmeans.ipynb)をみてみてください．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223338/d2d1f475-f0f8-2412-efde-6b2b2d3d8b9e.png)


THANK YOU