Pythonで凝集型(階層型)クラスタリングをやってみる（Scipy linkage 使い方）

# はじめに
　研究活動の一環でクラスタリング処理について調べる必要があったのでまとめます。この辺の記事はたくさん解説があるので、適宜ググってもらえるとわかると思います。今回は、勉強のためだと思って、アウトプットしたいと思います！
　なお、参考にした記事は以下です。公式は英語のドキュメントです。今回の私の記事を読んでいただいて、公式ドキュメントの理解がスムーズに出来るようになっていただければ幸いです。また、@y-kさんの記事は、凝集型クラスタリングについての、とても分かりやすい解説が載っています。とても参考にさせていただきました！

・参考１：[scipy.cluster.hierarchy.linkage](https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html)
・参考２：[凝集型(階層型)クラスタリングを理解する](https://qiita.com/g-k/items/8f0d9905d3e106caed59)

# 誰向けの記事？
　この記事は、

・凝集型クラスタリングについて知ってる
・pythonで凝集型クラスタリングをやってみたい
・1次元 or 2次元の座標データを凝集型クラスタリングで処理したい
・scipyのlikageメソッドを理解したい（入力・出力）

人向けです。
　機械学習未経験者が初心者向けに書く記事なので、ご指摘などございましたら幸いです。なお、主にlinkageメソッドの使い方を中心に書いていきます。

# scipyのインストール
　一応手順として書いておきます。以下のコマンドなどを打ち込んで、scipyをインポートできる様にしましょう。

```ruby:cmd_install_scipy
pip install scipy
```

# linkageについて理解する
　pythonのscipyから使えるメソッドの一つである、linkageは凝集型クラスタリングのメソッドです。メソッドの使い方、指定できる融合法、結合されていくデータの格納、出力されるデータについて解説していきます。

## メソッドの使い方
　メソッドの使い方は、method_linkageのようになります。入力であるX（座標データのリスト）を受け入れ、出力であるZ（結合手順を示したリスト）を出します。その際、"method_name"を引数に渡すことで、融合法を指定することができます。表１に各変数についてまとめておきます。

```ruby:method_linkage
Z = linkage(X, 'method_name')
```
<div align="center">
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/554112/051f2188-3546-be7c-3960-ee57b87d8a0a.png" align="center">
</div>
<br>
<b>表１　メソッドの変数についての説明</b>

|変数|役割|
|---|---|
|X|入力する座標データ群。リスト型|
|"method_name"|凝集型クラスタリングの融合法を指定する文字列。表２参考。|
|Z|出力されるデータ群。どのような結合手順をたどるかが記載されている。|

## 指定できる融合法
　指定できる融合法は7つです。linkageの引数に、表２の文字列を指定すると、その手法で融合します。
　各手法についての解説は、公式ドキュメントか、@g-kさんの[凝集型(階層型)クラスタリングを理解する](https://qiita.com/g-k/items/8f0d9905d3e106caed59)を読んでいただけると理解できると思います。<br>
<b>表２　指定できる融合法</b>　

|指定する文字列|備考|
|---|---|
|"single"|単連結法(single linkage method)|
|"complete"|完全連結法(complete linkage method)|
|"average"|群平均法(group average method)|
|"weighed"|重み付き平均法(weighed average method)|
|"centroid"|重心法(centroid method)|
|"median"|メディアン法(median method)|
|"ward"|ウォード法(ward method)|

## 結合されていくデータの格納
 linkageでは、結合されていくデータを、以下の図のように管理しています。この図は処理対象の座標が5組あります。
　まず与えられる入力データXは座標のリスト型なので、一番左のように添え字が割り振られています。これら5つの座標のうち、（指定した融合法に従って）一番近い座標どうしを結合します。そのデータは、添え字が6として、データが格納されます。その時、結合した群の中に何個データあるかをカウントします。この結合処理を続けていって、最終的に結合した群の要素数が5になったら、終了です。
　とりあえず、インデックスの動きについて理解してくれればいいです。
　
![図2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/554112/cd92203e-7e6b-464a-1762-0b47f0e89c44.png)

## 出力されるデータ
　出力されるデータは、result_of_linkageのような2次元のリストです。各要素は以下の表のようになっています。結合対象は、さっきの図でいう座標（青）or結合（緑）のどっちかです。distanceは、指定した手法で割り出した距離で、number_of_sub_clusterはさっきの図でいう要素数です。
　result_of_linkageは、上から順に結合していきます。そして、必ず最後はnumber_of_sub_clusterが、元の座標数に等しくなります。

|要素|備考|
|---|---|
|index1  | 結合対象１の添え字|
|index2  | 結合対象２の添え字|
|distance | 結合対象１と結合対象２の距離|
|number_of_sub_cluster |結合対象１と結合対象２の要素数を合計した数|


```ruby:result_of_linkage
Z = [
[index1, index2, distance, number_of_sub_cluster],
[index1, index2, distance, number_of_sub_cluster],
　　　　　　　　　　　　　・
　　　　　　　　　　　　　・
　　　　　　　　　　　　　・
]
```

# サンプルコード
　さあ！いつの間にか記事が長くなりました！サンプルコードを書いてみましょう。ここでは、座標が1次元の場合と、2次元の場合で書いてきます（確か公式には1次元と2次元が対応しているって書いてありました）。

## 入力の座標が1次元の場合
　入力の座標が1次元の場合、以下のようなサンプルコードになります。今回は単連結法を使いました。クラスタされる前の点は5つあり、Xには各点の座標（1次元）が入っています。

```ruby:linkage_1dimension.py
from scipy.cluster.hierarchy import linkage

# 入力データ（1次元）
X = [
    [1],
    [2],
    [4],
    [5],
    [100]
]

# 単連結法によるクラスタリング
Z = linkage(X, method='single')

print(Z)
```

　このコードを実行すると、以下のような表示がされます。これは、出力結果であるZを表示しています。

```ruby:resut_of_1dimension
[[ 0.  1.  1.  2.]
 [ 2.  3.  1.  2.]
 [ 5.  6.  2.  4.]
 [ 4.  7. 95.  5.]]
```
　これを解説すると、

手順１：index0とindex1を結合する（距離は１、結合した時の要素数は２）→index5に格納
手順２：index2とindex3を結合する（距離は１、結合した時の要素数は２）→index6に格納
手順３：index5とindex6を結合する（距離は２、結合した時の要素数は４）→index7に格納
手順４：index4とindex7を結合する（距離は95、結合した時の要素数は５）→要素数が5なので終了

となります。手順１で座標x=1とx=2（距離1）、手順２でx=4とx=5（距離1）が結合されるのは分かりやすいですね。それ以降はindex5以降に格納され、処理されています。最後は要素数が5になり、クラスタが1つになり、すべてがまとまりました。

## 入力座標が2次元の場合
　入力の座標が2次元の場合、以下のようなサンプルコードになります。1次元の時と同様に、単連結法を使いました。クラスタされる前の点は5つあり、Xには各点の座標（2次元）が入っています。


```ruby:linkage_2dimension.py
from scipy.cluster.hierarchy import linkage

# 入力データ（2次元）
X = [
    [1, 1],
    [1, 2],
    [1, 4],
    [2, 4],
    [100, 100]
]

# 単連結法によるクラスタリング
Z = linkage(X, method='single')

# 結果。クラスタリングの途中結果を示したもの。
print(Z)
```
　このコードを実行すると、以下のような表示がされます。これは、出力結果であるZを表示しています。

```ruby:resut_of_1dimension
[[  0.           1.           1.           2.        ]
 [  2.           3.           1.           2.        ]
 [  5.           6.           2.           4.        ]
 [  4.           7.         137.18600512   5.        ]]
```
　1次元の時と同様ですが、これを解説すると、

手順１：index0とindex1を結合する（距離は１、結合した時の要素数は２）→index5に格納
手順２：index2とindex3を結合する（距離は１、結合した時の要素数は２）→index6に格納
手順３：index5とindex6を結合する（距離は２、結合した時の要素数は４）→index7に格納
手順４：index4とindex7を結合する（距離は137、結合した時の要素数は５）→要素数が5なので終了

となります。

# おわりに
　今回、凝集型クラスタリングの関数についてまとめました。linkageはpythonでサクッとできるのでいいですね♪。しかし、機械学習ど素人の私にとって、なんのこっちゃ分からなかったので、まとめました。特に入力と出力が分かりずらかったですね。。。
　とりあえず、自分なりのアウトプットができたので満足です。
それじゃ！