階層的クラスタリング
非階層的クラスタリングではクラスタごとに上下の差や関係がないが、階層的クラスタリングではクラスタ間に上下関係や包含関係がある。例えば、動物をクラスタリングする場合、犬と猫は哺乳類に含まれ、哺乳類は動物に含まれる。このような包含関係を考慮することで、より詳細なクラスタリングが可能になる。
階層的クラスタリングには、主に凝集型（ボトムアップ）と分割型（トップダウン）の2つのアプローチがある。
- 凝集（ボトムアップ）型（Agglomerative Hierarchical Clustering）: 各データポイントを個別のクラスタとして開始し、最も近いクラスタ同士を繰り返し結合していく方法
- 分割（トップダウン）型（Divisive Hierarchical Clustering）: 全てのデータポイントを一つのクラスタとして開始し、最も異なるクラスタを繰り返し分割していく方法
凝集型階層的クラスタリング
ステップ について、クラスタの集合を と表す。ここで、 はステップ におけるクラスタ数である。さて、あるデータセット に対して考える。任意の二つのデータ点（ベクトル）に対しその距離を測る距離関数 を決める。さらに、任意の二つのクラスタ と に対しその距離を測るクラスタ間距離関数 を決める。この の定義についてはそのバリエーションで複数の方法がある。
さて、凝集型階層的クラスタリングは総じて、以下の手順で行われる。
- 各データ点を個別のクラスタとして初期化する。すなわち、
とする。
- ステップ
において、最も近い二つのクラスタ
と
を見つける。
- クラスタ
と
を結合し、新しいクラスタ
を作成する。
- クラスタ
と
を削除し、新しいクラスタ
を追加する。
- ステップ におけるクラスタ数を とする。
- であれば、2に戻る。そうでなければ終了する。
このアルゴリズムは、各ステップで最も"近い"クラスタ同士を結合していくことで、階層的なクラスタ構造を形成する。最終的に一つのクラスタになるまで繰り返すことで、デンドログラム（dendrogram）と呼ばれる木構造の図を得ることができる。
デンドログラムは、クラスタの結合過程を視覚的に表現し、どのクラスタがどの段階で結合されたかを示す。横軸に初期のデータ点、縦軸にクラスタ間の距離を取り、二つのクラスがある距離で結合されたことを示す。最終的に1つに統合されるが、途中の段階で切断することで、任意のクラスタ数に分割することができる。
さまざまな距離関数
距離関数 としては、以下の条件を満たす必要がある。
- 非負性:
- 一致性:
- 対称性:
- 三角不等式:
代表的な距離関数としては、以下のようなものがある。
ユークリッド距離
別名L2ノルム距離（L2 norm distance）とも呼ばれる。
マンハッタン距離
別名L1ノルム距離（L1 norm distance）とも呼ばれる。
コサイン類似度
コサイン類似度は距離関数ではなく類似度関数であるが、1から引くことで距離関数として利用できる。
これは三角不等式を満たさない場合があるため、厳密には距離関数ではないことに注意が必要である。
さまざまなクラスタ間距離関数
クラスタ間距離関数 の違いはそのまま凝集型階層的クラスタリングの方法の違いになる。以下はここで紹介する手法の違いである。
| 手法名 | クラスタ間距離関数 | クラスタの特徴 | ノイズ/外れ値 | 弱点 | 性質 |
|---|---|---|---|---|---|
| 最短距離法（単連結法） | 最短距離 | 細長い形状 | 弱い | 鎖状クラスタ形成 | 単調 |
| 最長距離法（完全連結法） | 最長距離 | コンパクトな形状 | 強い | 外れ値に敏感 | 単調 |
| 群平均法 | 平均距離 | バランスの取れた形状 | 中程度 | なし | 単調 |
| 重心法 | 重心間距離 | 多様な形状 | 弱い | 非単調な結合 | 非単調・ユークリッド距離 |
| ウォード法 | クラスタ内平方和の増加量 | コンパクトな形状 | かなり強い | ベクトル内スケールに敏感 | 単調・ユークリッド距離 |
また。ここではベクトルを念頭に置いているが、最短距離法, 最長距離法, 群平均法は適切な距離関数を用いればベクトル以外の特徴量にも適用可能である。
最短距離法（単連結法）
二つのクラスタ と の距離を、それらのクラスタに属するデータ点間の最短距離として定義する。
クラスタが、クラスタ内の最も近いデータ点同士の距離に基づいて結合される。そのため、クラスタが細長く伸びた形状（平たく言えば鎖状）になる傾向がある。その結果、クラスタ内の最も遠い点の距離（これをクラスタの直径と呼ぶ）が大きくなることがある。
最長距離法（完全連結法）
二つのクラスタ と の距離を、それらのクラスタに属するデータ点間の最長距離として定義する。
クラスタが、クラスタ内の最も遠いデータ点同士の距離に基づいて結合される。そのため、クラスタが比較的コンパクトな形状（球状）になる傾向がある。しかし、外れ値に敏感であり、近そうな点があっても外れ値があると結合されないことがある。
群平均法
二つのクラスタ と の距離を、それらのクラスタに属する全てのデータ点間の平均距離として定義する。
クラスタが、クラスタ内の全てのデータ点間の距離の平均に基づいて結合される。そのため、クラスタが比較的バランスの取れた形状になる傾向がある。外れ値に対しても比較的ロバストである。
重心法
二つのクラスタ と の距離を、それらのクラスタの重心間の距離として定義する。各クラスタの重心は、そのクラスタに属するデータ点の平均ベクトルとして計算される。
これを用いて
と定義される。ほとんどの場合、距離関数 としてユークリッド距離が用いられる。重心が、外れ値に敏感であるため、外れ値が存在する場合には注意が必要である。また、状態によっては統合が進むとクラスタ間距離が減少することがあり、非単調なクラスタ結合が発生する可能性がある。
ウォード法
二つのクラスタ と の距離を、クラスタ内平方和の増加量として定義する。クラスタ内平方和は以下で定義されたものであった。なお、ウォード法では距離関数 としてユークリッド距離が用いられる。
ここで はクラスタ の重心ベクトルである。また、一つのクラスタ のクラスタ内平方和も定義しておく。
当然、全体のクラスタ内平方和は各クラスタのクラスタ内平方和の和である。このとき、あることなる二つのクラスタ と を結合したときの全体のクラスタ内平方和の増加量 を考えてみると
である。これを定義に則して展開してみると、 の重心を を用いて
となる。ここで、 について考える。
である。途中、
を用いた。これと同様にして についても計算すると
である。さて、
なので、
となる。これらを用いて、最終的に
となる。 が大きいということは、統合によってクラスタ内平方和が大きく増加することになり、分散が増加することを意味する。したがって、ウォード法では、この が最小となるクラスタ同士を結合する。これはすなわち と のクラスタ間距離関数として が採用できることを意味する。
しかし、そのままではスケールと単点クラスタにおける振る舞いが問題になる。 、つまり各データ点が個別のクラスタであるとき、任意の二つのクラスタ と に対して
となる。これを2点間のユークリッド距離 に一致させるために、ウォード法ではクラスタ間距離関数を以下のように定義する。
動作上、ユークリッド距離に一致させる必要は特にはないが、他の方法との比較を容易にするためにこのように定義されることが多い。ウォード法は、クラスタ内平方和を最小化することを目的としているため、比較的均一でコンパクトなクラスタを形成する傾向がある。また、外れ値に対しても比較的ロバストである。