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

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

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

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

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

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

樹形図³と呼ばれるツリー状の図は、クラスターの階層を視覚化するためによく使用されます。クラスターがマージまたは分割された順序が表示され、データ点間の類似性または距離が表示されます。樹形図は、属性を持つリスト⁴がネストされたリストとして捉えることもできます。

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

- 距離⁵：たとえば、ユークリッド距離で、セット内の1つの点の間があります。

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

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

単連結法は、2つのクラスター内の項目間のペアワイズ距離を分析し、クラスター間の最小距離を使用します。最短距離法は、非楕円形のクラスター形状を適切に処理しますが、ノイズや外れ値の影響を受けます。この方法には、鎖効果⁶と呼ばれる制限があります。クラスター・ペアの間にブリッジを作るいくつかの点により、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：minimal increase of sum of squares）法⁸を導入しました。すべてのデータ点は独自のクラスターから始まります。このアプローチは、データ点間の二乗和が最初はゼロであり、クラスターをマージするにつれて増加することを意味します。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の最小分散法は、ランス-ウィリアムズ・アルゴリズムを使用して改良できます。これらのアルゴリズムは、再帰式を使用してクラスター距離を更新し、マージする最適なクラスター・ペアを見つけます。

凝集型階層的クラスタリング（凝集型ネスティング(AGNES)とも呼ばれる）では、各データ点はクラスターとして開始します。このアルゴリズムは、非類似度行列に基づいて選択された連結クラスタリング基準を使用して、どのクラスターのペアを結合するかを決定します。このアルゴリズムは階層の上方に動き、すべてが結合されるまでクラスターのペアリングを続け、階層的にネストされた一連のクラスターを作成します。凝集型クラスタリングのステップ¹⁰は、大まかに次のようになります。

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

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

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

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

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

分割型階層的クラスタリングの背後にある原理は、1964年にMacnaughton-Smithら¹¹によって開発され、さらにKaufmanとRousseeuwによって1990年にDIANA（Divisive ANAlysis clustering [分割型分析クラスタリング]）アルゴリズム¹²によって開発されました。分割型クラスタリングは、凝集型クラスタリングとは逆のアプローチを使用します。すべてのデータ点は、1 つのクラスターで開始され、そのクラスターは繰り返し複数のクラスターに分割されます。分割は、残りすべてのクラスターがシングルトンであるか、事前定義されたクラスター数などの停止基準が満たされるまで続きます。分割法は、大きなクラスター¹³の特定に優れており、プロセスの開始からデータセット全体の分布を考慮するため、凝集法よりも正確な場合があります。

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

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

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

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

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

クラスターの結果は通常、樹形図（二分木構造）で表されます。樹形図のX軸はデータ点を表し、Y軸（線の高さ）は、クラスターがマージされたときにクラスターがどれだけ離れていたかを示します。

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

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

堅牢なクラスタリング・モデル¹⁷は、クラス内の高い類似性とクラス間の低い類似性を持つクラスターを作成します。ただし、クラスターの品質を定義することは困難な場合があり、連結基準とクラスター番号の選択は結果に大きな影響を及ぼす可能性があります。したがって、クラスタリング・モデルを構築する際には、さまざまな選択肢を試し、今後の検討のためにデータセット内のパターンを明らかにするのに最も役立つ選択肢を選んでください。考慮すべき要素¹⁸は次のとおりです。

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

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

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

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

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

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

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

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

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

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

臨床研究の患者集団は、数千人にのぼることもあります。階層的クラスタリングは、例えば、診断基準、生理学的反応、またはDNA突然変異を用いて、混合集団をより均質なグループに分類するのに役立ちます²⁰。また、進化的発達を理解するために、生物学的特徴によって種群に適用することもできます。

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

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

Pythonは、AgglomerativeCluster関数²¹（sklearnの凝集型クラスタリングの例²²も参照）を提供し、SciPyは、樹形図²³をプロットする関数を提供します。dendextend²⁴などのパッケージは、Rの樹形図機能を強化し、感度分析を改善し、さまざまな樹形図の比較と操作を可能にします。実践的な体験については、段階的に学べるチュートリアル「Pythonで階層的クラスタリングを実装する方法」と「Rで階層的クラスタリングを実装する方法」を参照してください。