階層的クラスタリング（hierarchical clustering）は、階層的クラスタ分析（HCA）とも呼ばれ、データマイニングや統計学におけるクラスタ分析の手法の一つであり、クラスタの階層構造を構築することを目的とする。k-meansのような分割型手法がクラスタ数を事前に指定する必要があるのに対し、階層的クラスタリングは入れ子構造を生成し、任意のレベルで切断することで異なる数のクラスタを得ることができる。結果は通常、結合または分割の順序を示す樹状図（デンドログラム）として提示される。このアプローチは、生物学、社会科学、機械学習などの分野で探索的データ分析に広く用いられている。
階層的クラスタリングの主な利点は、その柔軟性にある。任意の有効な距離尺度を使用でき、観測値自体は必要とせず、距離行列のみでよい。しかし、単一リンケージ距離の特別な場合を除き、全探索なしで最適解を見つけることを保証できるアルゴリズムはなく、その時間計算量はO(2^n)である。
凝集型と分割型の戦略
階層的クラスタリングの戦略は、一般に凝集型と分割型の2つのカテゴリに分類される。凝集型クラスタリングは「ボトムアップ」アプローチとも呼ばれ、各データ点を個別のクラスタとして開始する。各ステップで、アルゴリズムは選択された距離指標（例：ユークリッド距離）とリンケージ基準（例：単一リンケージ、完全リンケージ）に基づいて、最も類似した2つのクラスタを結合する。このプロセスは、すべてのデータ点が単一のクラスタに統合されるか、停止基準が満たされるまで続行される。凝集型手法は、その単純さと小規模から中規模のデータセットに対する計算効率の良さから、より一般的に使用される。
分割型クラスタリングは「トップダウン」アプローチとして知られ、すべてのデータ点を単一のクラスタとして開始し、再帰的にクラスタをより小さなものに分割する。各ステップで、アルゴリズムはクラスタを選択し、結果として得られるクラスタ間の距離を最大化するなどの基準を用いて、2つ以上のサブセットに分割する。分割型手法はあまり一般的ではないが、最初に大きく明確なクラスタを特定することが目的の場合に有用である。一般に、結合と分割は貪欲法で決定され、アルゴリズムはグローバル構造を考慮せずに各ステップで局所的に最適な選択を行う。
計算量とアルゴリズム
階層的凝集型クラスタリング（HAC）の標準アルゴリズムは、時間計算量がO(n^3)であり、Ω(n^2)のメモリを必要とするため、中規模のデータセットでも遅すぎる。しかし、いくつかの特別な場合には、O(n^2)の計算量を持つ最適な効率的凝集型手法が知られている。単一リンケージにはSLINK、完全リンケージにはCLINKである。ヒープを使用すると、一般的な場合の実行時間をO(n^3)ではなくO(n^2 log n)に削減できるが、追加のメモリ要件が生じる。多くの場合、このアプローチのメモリオーバーヘッドは大きすぎて実用的に使用できない。四分木を使用してO(n^2)の総実行時間とO(n)の空間を実現する方法も存在する。
分割型クラスタリングの全探索はO(2^n)であるが、k-meansなどのより高速なヒューリスティックを使用して分割を選択することが一般的である。これらのヒューリスティックは、最適性を計算の実現可能性とトレードオフし、分割型手法をより大きなデータセットに適用できるようにする。
距離指標
リンケージ基準が観測値の集合間の非類似度の計算方法を決定する一方で、基礎となる距離指標は個々の観測値間の非類似度の測定方法を決定する。階層的クラスタリングは任意の有効な距離尺度を許可するため、指標の選択はデータの性質によって導かれ、結果のクラスタリングに大きな影響を与える可能性がある。
ユークリッド距離は、連続的な数値データに対して最も広く使用される指標である。これはユークリッド空間における2点間の直線距離に対応し、ほとんどの統計ソフトウェアでデフォルトの選択肢である。マンハッタン距離（市街地距離またはL1距離とも呼ばれる）は、特徴間の絶対差を合計する。これは、特徴が異なるスケールで測定される場合や、データに外れ値が含まれる場合に好まれることが多く、ユークリッド距離よりも大きな偏差に敏感ではない。コサイン距離は、2つの非ゼロベクトル間の角度の非類似度を測定し、テキスト分析やその他の高次元設定で一般的に使用される。
リンケージ基準
リンケージ基準は、2つのクラスタ間の距離が、その個々のメンバー間の距離からどのように計算されるかを決定する。単一リンケージ（最近傍法）は、2つのクラスタ内の任意の2点間の最小距離を使用し、長く鎖状のクラスタを生成する傾向がある。完全リンケージ（最遠傍法）は最大距離を使用し、コンパクトで球状のクラスタを生成する傾向がある。平均リンケージは、すべての点のペア間の平均距離を使用し、この2つの間の妥協点を提供する。ウォード法はクラスタ内分散の合計を最小化し、連続データに人気がある。リンケージ基準の選択は、結果の樹状図の形状と解釈を劇的に変える可能性がある。
応用と限界
階層的クラスタリングは多くの分野で使用されている。生物学では、遺伝的類似性に基づく系統樹の構築に使用される。マーケティングでは、類似した行動を持つ顧客をセグメント化するのに役立つ。画像分析では、ピクセルや特徴をグループ化できる。人工知能では、階層的クラスタリングは探索的データ分析のための教師なし学習手法として、また他のアルゴリズムの前処理ステップとしてよく使用される。
その利点にもかかわらず、階層的クラスタリングには限界がある。アルゴリズムの貪欲な性質により、一度結合または分割が行われると元に戻すことができず、最適ではない結果につながる可能性がある。標準アルゴリズムの計算の複雑さは、中程度のサイズのデータセットへの使用を制限するが、特定のリンケージ基準に対して最適化された実装が存在する。さらに、樹状図の解釈は主観的になる可能性があり、距離指標とリンケージ基準の選択にはドメイン知識が必要である。