階層的クラスタリングとは

クラスタリングは、データ分析において類似したオブジェクトを検知してグループ化するために使用される教師なし機械学習手法です。階層クラスター分析（HCA）または階層クラスタリングでは、オブジェクトをクラスター階層にグループ化しますが、その中で線形の順序を強制することはありません。生物学、画像分析、社会科学などの多くの分野では、階層的クラスタリング手法を使用して、データセット内のパターンを探索および認識しています。ユースケースには、臨床研究における集団の分類、顧客セグメンテーション、ネットワーク・モデルにおけるノードのコミュニティの検出などがあります。

階層的クラスタリングには2つのタイプがあります。

- 凝集型またはボトムアップアプローチ¹：単一のクラスターが出現するまでクラスターをより大きなものに繰り返しマージします。

- 分割またはトップダウンのアプローチ²：単一クラスター内のすべてのデータから始まり、すべてのクラスターが単集合になるまで、連続するクラスターを分割し続けます。

階層的クラスター分析には高い計算コストがかかります。ヒープを使用すると計算時間は短縮されますが、メモリ要件は増加します。分割タイプと凝集タイプのクラスタリングはどちらも「貪欲」です。つまり、アルゴリズムは、プロセスの各段階で局所的な最適な選択を行うことで、どのクラスターがマージまたは分割されるかを決定します。また、アルゴリズムが所定のクラスター数に到達したときにクラスターの集約または分割を停止する停止基準を適用することもできます。

クラスターの階層を視覚化するために、樹形図³と呼ばれる木のような図がよく使用されます。クラスターがマージまたは分割された順序が表示され、データ・ポイント間の類似性や距離が表示されます。樹形図は、属性を持つリスト⁴が入れ子になったものとして理解することもできます。

階層的クラスタリング・アルゴリズムは、非類似度行列の概念を使用して、マージまたは分割するクラスターを決定します。非類似度は、選択した連結方法で測定された2つのデータ点間の距離です。非類似度行列の値は、次の式を表します。

- 距離⁵：一例がユークリッド距離であり、これは1つのセット内の単独点の間の距離です。

- 連結クラスタリング基準：セット間のペアワイズ距離の関数として非類似度を指定します。

最も一般的なユークリッド距離連結法について見ていきましょう。他に使用できる距離メトリクスの例には、ミンコフスキー距離、ハミング距離、マハラノビス距離、ハウスドルフ距離、マンハッタン距離などがあります。各連結方式は、同じデータセットから異なるクラスターを生成することに注意してください。適切な連結クラスタリング手法の選択は、クラスタリングされるデータの種類、データ密度、クラスターの形状、データセットに外れ値やノイズがあるかどうかなどの要素によって異なります。

単連結法では、2つのクラスター内のアイテム間のペアごとの距離を分析し、クラスター間の最小距離を使用します。Min メソッドは非楕円クラスター形状を適切に処理しますが、ノイズや外れ値の影響を受けます。これには鎖効果⁶として知られる限界があります。クラスター間のブリッジを作成するいくつかのポイントにより、2つのクラスターが1つにマージされる場合があります。最小連結の基準は、次のように表すことができます。

 mina∈A,b∈Bd(a,b)

ここで、AとBは2つの観測値のセットで、dは距離関数です。

クラスター距離は、互いに最も離れた点に基づいて計算することもできます。最長距離法は、最短距離法よりもノイズや外れ値に対する影響を受けにくくなりますが、球体クラスターまたは大規模なクラスターがある場合、結果に歪みが生じることがあります。最縁隣法（Max-linkage）は多くの場合、最近隣法（min-linkage）よりも多くの球形クラスターを生成します。最遠隣法は次の式で表すことができます。

 maxa∈A,b∈Bd(a,b)

ここで、AとBは2つの観測値のセットで、dは距離です。

SokalおよびMichener⁷が紹介したこれらの手法では、クラスター間の距離を、クラスター内のすべての点のペアにわたるペア間の平均距離として定義します。アルゴリズムは、算術平均を使用した無重み付けペアグループ方法（UPGMA）または算術平均を使用した加重ペアグループ方法（WPGMA）のいずれかです。ここで「重み付けされていない」とは、すべての距離が各平均に等しく寄与するということを意味します。

UPGMAは、次の式で表されます。

 1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

ここで、*A*と*B*は2組の観測値、*d*は距離です。

WPGMAは、次の式で表されます。

 d(i∪j,k)=d(i,k)+d(j,k)2

ここで、iとjは、各ステップで結合される最も近いクラスターであり、iとjの連合の新しいクラスターを形成します。次に、別のクラスターへの距離kを計算できます。これは、kとi、およびkとjのデータ・ポイント間の平均距離の算術平均です。

ここでは、クラスターの中心または重心間の距離を使用します。重心間の距離は、距離関数を使用して計算されます。

∥μA-μB∥2

ここで、μ_AはAの重心、μ_BはBの重心です。

Joe H. Wardは1960年代に最小二乗和増加法（MISSQ）⁸を発表しました。すべてのデータポイントは、独自のクラスターから始まります。このアプローチは、データ・ポイント間の二乗和が最初はゼロであり、クラスターをマージするにつれて増加することを意味します。Wardの手法では、マージされるときに、クラスター中心からのポイントの二乗距離の合計が最小化されます。Wardの手法は定量的な変数⁹ に適しており、ノイズや外れ値の影響が少なくなります。これは次のように表すことができます。

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

ここで、Aの平均とBの平均はそれぞれAとBの重心であり、xはAとBの和集合に属するデータ点です。

Wardの最小分散法は、 Lance-Williamsアルゴリズムを使用して改良できます。これらのアルゴリズムは、再帰式を使用してクラスター距離を更新し、マージする最適なクラスター・ペアを見つけます。

集約型階層クラスタリング（AGNES）とも呼ばれる集約型階層クラスタリングでは、各データ・ポイントはクラスターとして開始されます。このアルゴリズムは、異種行列に基づいて選択されたリンケージー・クラスタリング基準を使用して、どのクラスターのペアを結合するかを決定します。アルゴリズムは階層の上方に動き、すべてがリンクされるまでクラスターのペアリングを維持し、ネストされたクラスターの階層的な一連を作成します。大まかに言うと、クラスターのステップ¹⁰は次のとおりです。

1. 特定の距離メトリクスを使用して非類似度行列を計算します。

2. 各データ点をクラスターに割り当てます。

3. クラスター間の類似性の連鎖基準に基づいてクラスターをマージします。

4. 距離行列を更新します。

5. クラスターが1つになるか、停止基準に達するまでステップ3と4を繰り返します。

分割階層クラスターの背後にある原理は、1964年にMacnaughton-Smithら¹¹によって開発され、1990年にKaufmanとRousseuwが、DIANA（分割分析クラスター）アルゴリズム¹²でさらに探求したものです。分割クラスタリングは、集約的クラスタリングとは逆のアプローチを使用します。すべてのデータ・ポイントは単一のクラスターから始まり、その後さらに多くのクラスターに繰り返し分割されます。分割は、残りのクラスターが単集合になるか、事前に定義されたクラスター数などの停止基準に達するまでに行われます。分割法は大規模なクラスター¹³を特定するのに優れており、アルゴリズムがプロセスの開始時からデータ・セット分布全体を考慮するため、集約的方法よりも正確です。

効率を向上させるために、分割法では、k平均などのフラット・クラスタリング・アルゴリズムを使用して、データセットをクラスターに分割します。クラスターの数は事前に指定する必要があります。k平均法アルゴリズムは、クラスター内の重心点間の二乗和を最小化することによってクラスターを分割します。これは慣性（イナーシャ）基準¹⁴として知られています。クラスター分割のステップ¹⁵は次のとおりです。

1. 1つのクラスターのデータセット・サイズN（d1、d2、d3 ...dN）のすべてのデータ点から開始します。

2。K平均法アルゴリズムなどのフラット・クラスタリング手法を使用して、クラスターを2つの異なるクラスターまたは異種クラスターに分割します。

3. ステップ2を繰り返し、分割する最適なクラスターを選択し、各反復の後に最も一貫性の低いクラスターから外れ値を除去します。

4. 各例が独自の単一クラスター内にある場合は終了し、それ以外の場合はステップ3を繰り返します。

クラスターの結果は通常、インフラストラクチャー（2分ツリー構造）で表示されます。インフラストラクチャーのx軸はデータ・ポイントを表し、 y軸 （線の高さ）は、マージされたときにクラスターがどれだけ離れていたかを示します。

樹形図を使用して、最終的なクラスタリング・モデルのクラスター¹⁶の数を決定できます。戦略の1つは、枝が減少して長くなる木の自然な切断点を特定することです。あるいは、クラスター数は、水平線が樹形図を切断したときに交差する垂直線の数で与えられます。

ここに示した画像例では、水平線H1が2本の垂直線を横断しています。これは、プロセスのこの時点に2つのクラスターがあることを示しています。1つはポイント5、8、2を持つクラスターで、もう1つは残りのポイントを含むクラスターです。樹形図内の他の水平線を切断することなく、水平線が上または下に動きできるほど、この数のクラスターの選択がクラスタリング・モデルにとって適切になります。以下の例では、水平線H24つのクラスターを選択しています。H2 は、他の水平線を横断する前にH1まで動くことはできません。このシナリオでは、2クラスターの選択肢（ H1 ）の方がクラスタリングモデルに適していると考えられます。

堅牢なクラスタリングモデル¹⁷は、高いクラス内の類似性と低いクラス間の類似性を持つクラスターを作成します。しかし、クラスターの品質を定義することは困難な場合があり、リンク基準とクラスター数の選択は成果に大きな影響を与える可能性があります。したがって、クラスター化モデルを構築する際には、さまざまなオプションを試し、将来の検討のためにデータセット内のパターンをはこちらおよび明らかにするのに最も役立つオプションを選択してください。考慮すべき要素¹⁸には以下が含まれます。

- データセットにとって実用的または論理的なクラスターの数（特定のデータセットのサイズ、クラスターの形状、ノイズなど）

- 統計値：各クラスターの平均値、最大値、最小値など

- 適用する最適な非類似性メトリクスまたは連結基準

- 外れ値または結果変数の影響

- 特定のドメインまたはデータセットに関する知識

クラスター¹⁹の最適な数を決定するのに役立つ他の方法には、次のものがあります。

- エルボー法：クラスター数に対してクラスター内平方和をプロットし、「エルボー」 （プロットが水平になる点）を決定します。

- ギャップ統計量：実際のクラスター内平方和を、ヌル参照分布に対して予期されるクラスター内平方和と比較し、最大のギャップを特定します。

階層的クラスタリングは、データサイエンティストにデータセット内の構造と関係についての知見を提供し、さまざまなユースケースに適用できます。

階層的クラスタリングは、傾向を分析し、顧客データをセグメント化するのに役立ちます。例えば、製品の選択、人口統計、購買行動、リスクプロファイル、ソーシャル・メディアとのインタラクションによってグループ化することができます。

臨床試験に参加する患者数は、数千人に上ることがあります。階層的クラスターは、診断基準、生理学的な反応、DNA 変異などを使用することにより、異種混交的な集団をより均質なグループに分類するのに役立ちます²⁰。また、進化的発展を理解するために、生物学的主要な機能によって種のグループをグループ化することもできます。

階層的クラスタリングは、画像ベースのテキスト認識アプリケーションで、手書きの文字を形状によってグループ化するために使用されます。また、特定の基準を用いて情報を保管および取得したり、検索成果を分類したりするためにも使用されます。

PythonとRプログラミング言語はどちらもデータサイエンスで広く使用されています。Pythonは柔軟性があり、幅広いタスクを処理できます。あるいは、Rは統計コンピューティング専用に設計されており、階層クラスタリング分析を視覚化するための豊富なオプションを提供します。

Python は AgglomerativeCluster 関数²¹（sklearn の集約クラスタリングの例²² も参照）、SciPy はデベログラム²³をプロットする関数を提供します。dendextend²⁴のようなパッケージは、Rの樹形図機能を強化し、感度分析を改善し、異なる樹形図を比較・操作できるようにします。実践的なエクスペリエンスについては、ステップバイステップのチュートリアルをご覧ください。Python で階層的クラスタリングを実装する方法については、こちら、R で階層的クラスタリングを実装する方法については、こちらをご覧ください。