整数値データを階層的クラスタリングにかけると、データ全体を定数倍しただけ で結果が変わってしまう場合があります。理由は、ある点から最も近い点が複数生じやすいためと考えられます。並び替えても結果が一致しない こともあります。以下に極端な例を紹介します。
適当に整数値のランダム行列を作る
import numpy as np
import pandas as pd
from scipy.cluster.hierarchy import linkage, leaves_list, fcluster
np.random.seed(123)
X = np.random.randint(0, 3, (100, 4)) # 100 x 4, {0,1,2}
階層的クラスタリングをする
Z = linkage(X, method='average')
データ行列全体に適当な値をかけて、再度クラスタリングをする
Z2 = linkage(0.99*X, method='average')
樹形図の葉の順番を比べてみる
print(leaves_list(Z))
print(leaves_list(Z2))
上の結果
[ 5 37 47 18 50 4 7 36 35 63 27 58 64 33 98 14 61 74 81 89 83 11 66 85
94 68 96 95 92 91 12 54 28 86 49 78 52 6 21 22 62 19 32 87 39 80 51 72
9 55 29 3 40 77 56 76 42 20 41 34 99 30 97 53 79 8 69 45 48 0 44 31
90 84 2 17 59 10 70 82 57 38 13 24 71 46 73 26 88 65 93 16 67 15 43 60
75 25 1 23]
下の結果 (全然違う!!!)
[ 4 7 33 96 62 52 6 21 72 35 63 36 98 14 61 27 58 64 85 94 89 83 11 66
74 81 59 10 70 68 82 57 38 13 24 71 46 73 95 92 91 12 54 28 86 49 78 45
48 0 44 87 90 84 2 17 5 37 47 18 50 19 32 31 39 80 22 77 56 76 42 20
41 34 99 53 79 8 69 51 30 97 26 88 65 93 9 55 29 3 40 16 67 75 25 1
23 15 43 60]
同一ベクトルが沢山あるので、それらをうまく並び替えれば一致する可能性もあります。先へ進んでみましょう。
適当な数のクラスタに分割する
c_arr = fcluster(Z, 5, criterion='maxclust')
c2_arr = fcluster(Z2, 5, criterion='maxclust')
print(c_arr)
print(c2_arr)
上の結果
[4 5 4 3 2 1 3 2 3 3 4 2 3 4 2 5 5 4 1 3 3 3 3 5 4 5 5 2 3 3 3 4 3 2 3 2 2
1 4 3 3 3 3 5 4 4 4 1 4 3 1 3 3 3 3 3 3 4 2 4 5 2 3 2 2 5 2 5 2 3 4 4 3 4
2 5 3 3 3 3 3 2 4 2 4 2 3 3 5 2 4 3 3 5 2 3 2 3 2 3]
下の結果
[3 5 3 5 1 4 2 1 4 5 3 2 3 3 2 5 5 3 4 4 4 2 4 5 3 5 5 2 3 5 4 4 4 1 4 2 2
4 3 4 5 4 4 5 3 3 3 4 3 3 4 4 2 4 3 5 4 3 2 3 5 2 2 2 2 5 2 5 3 4 3 3 2 3
2 5 4 4 3 4 4 2 3 2 3 2 3 3 5 2 3 3 3 5 2 3 1 4 2 4]
クラスタ番号の対応関係が分かりづらいですが、最初の4つを比べると、上が4543、下が3535で、既に違います。2番目と4番目が別々のクラスタに入るか、同じクラスタに入るかで、一致しません。
クラスタ番号の対応関係を調べる
まず、1列目が元データのクラスタ番号、2列目が定数倍したデータのクラスタ番号となるデータフレームを用意します。
df = pd.DataFrame(dict(c=c_arr, c2=c2_arr))
print(df)
こんな感じ
c c2
0 4 3
1 5 5
2 4 3
3 3 5
4 2 1
.. .. ..
95 3 3
96 2 1
97 3 4
98 2 2
99 3 4
次に、2つの値のペアの出現頻度をカウントします。
freq_sr =df.value_counts()
print(freq_sr)
こんな感じ (cとc2は列でなくindexになっています)
c c2
3 4 20
4 3 19
2 2 17
5 5 13
3 3 10
1 4 5
3 2 5
5 5
2 1 4
3 1
4 4 1
見やすいように行列にします。
df2 = freq_sr.unstack().fillna(0).astype(int)
print(df2)
結果
c2 1 2 3 4 5
c
1 0 0 0 5 0
2 4 17 1 0 0
3 0 5 10 20 5
4 0 0 19 1 0
5 0 0 0 0 13
行が元データのクラスタ番号、列が定数倍データのクラスタ番号です。1対1には対応していない ことが分かります。
補足など
この現象が起こる理由について簡単に説明します。階層的クラスタリングでは、近い点同士を順番にくっつけていきます。整数値データの場合、ある点 (またはクラスタ) の最近傍点 (またはクラスタ) が複数存在して一意に定まらない状況が発生しやすく、些細な変化で結果が変わってしまうのだと考えられます。取り込む相手が変わると、クラスタ間の非類似度も変わってしまうので、すぐ次のステップで選ばれなかった方を取り込めるとは限りません。
データ数に対して次元が大きい場合や、整数値の取り得る範囲が広い場合などは、ほとんど起きません。もちろん実数データではまず起きません。