単一リンククラスタリング

統計学において、単連結クラスタリングは階層的クラスタリングのいくつかの手法の 1 つです。これは、ボトムアップ方式 (凝集型クラスタリング) でクラスターをグループ化することに基づいており、各ステップで、まだ同じクラスターに属していない最も近い要素のペアを含む 2 つのクラスターを結合します。

この方法では、同じクラスター内の近くの要素間の距離が短い細長いクラスターが生成される傾向がありますが、クラスターの反対側の端にある要素は、他のクラスターの2つの要素よりも互いにはるかに離れている可能性があります。一部のデータクラスでは、これにより、データを有効に細分化できるクラスを定義することが困難になる可能性があります。^[1]ただし、この方法は、長い物質のひもを含むことが多い銀河団の分析に天文学でよく使用されています。この用途では、フレンズオブフレンズアルゴリズムとしても知られています。^[2]

凝集型クラスタリング プロセスの開始時には、各要素は独自のクラスターに存在します。その後、クラスターは順次結合されてより大きなクラスターになり、最終的にすべての要素が同じクラスターになります。各ステップで、最短距離で分離された 2 つのクラスターが結合されます。2 つのクラスター間の距離を決定するために使用される関数 (リンク関数)が、凝集型クラスタリング メソッドを区別するものです。

シングルリンククラスタリングでは、2 つのクラスター間の距離は、1 組の要素、つまり互いに最も近い 2 つの要素 (各クラスターに 1 つずつ) によって決定されます。どのステップでも残っているこれらのペアワイズ距離のうち最短のものによって、その要素を含む 2 つのクラスターがマージされます。この方法は、最近傍クラスタリングとも呼ばれます。クラスタリングの結果は、クラスターがマージされた順序と、各マージが行われた距離を示すデンドログラムとして視覚化できます。 ^[3]

数学的には、リンク関数（クラスターXとYの間の距離D（X、Y ））は、次の式で表されます。

${\displaystyle D(X,Y)=\min _{x\in X,y\in Y}d(x,y),}$

ここで、XとYはクラスターとして考えられる任意の2つの要素セットであり、d ( x , y )は2つの要素xとy間の距離を表します。

次のアルゴリズムは、古いクラスターが新しいクラスターにマージされるときに、近接行列の行と列を消去する凝集方式です。近接行列には、すべての距離が含まれます。クラスタリングにはシーケンス番号が割り当てられ、は- 番目のクラスタリングのレベルです。シーケンス番号mのクラスターは( m )で示され、クラスターとクラスター間の近接性はで示されます。 ${\displaystyle N\times N}$${\displaystyle D}$${\displaystyle d(i,j)}$${\displaystyle 0,1,\ldots ,n-1}$${\displaystyle L(k)}$${\displaystyle k}$${\displaystyle (r)}$${\displaystyle (s)}$${\displaystyle d[(r),(s)]}$

シングルリンクアルゴリズムは、次の手順で構成されます。

1. レベルとシーケンス番号を持つ分離クラスタリングから始めます 。${\displaystyle L(0)=0}$${\displaystyle m=0}$
2. 現在のクラスタリング内のすべてのクラスターのペアの中で最小値となる場所に従って、現在のクラスタリングで最も類似したクラスターのペア (ペア とします) を検索します。${\displaystyle (r),(s)}$${\displaystyle d[(r),(s)]=\min d[(i),(j)]}$
3. シーケンス番号を増分します: 。クラスタとを1つのクラスタにマージして次のクラスタリングを形成します。このクラスタリングのレベルを に設定します。${\displaystyle m=m+1}$${\displaystyle (r)}$${\displaystyle (s)}$${\displaystyle m}$${\displaystyle L(m)=d[(r),(s)]}$
4. クラスター および に対応する行と列を削除し、新しく形成されたクラスター に対応する行と列を追加して、近接行列 を更新します。 で示される新しいクラスターと古いクラスター間の近接性は と定義されます。${\displaystyle D}$${\displaystyle (r)}$${\displaystyle (s)}$${\displaystyle (r,s)}$${\displaystyle (k)}$${\displaystyle d[(r,s),(k)]=\min\{d[(k),(r)],d[(k),(s)]\}}$
5. すべてのオブジェクトが 1 つのクラスター内にある場合は停止します。それ以外の場合は手順 2 に進みます。

この実例は、5種類の細菌（枯草菌（）、バチルス・ステアロサーモフィルス（）、ラクトバチルス・ビリデセンス（ ） 、アコレプラズマ・モディカム（）、およびミクロコッカス・ルテウス（））の5SリボソームRNA配列アライメントから計算されたJC69遺伝距離行列に基づいています。 ^{[4] [5]}${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle d}$${\displaystyle e}$

• 最初のクラスタリング

5 つの要素と、それらの間のペアワイズ距離の次の行列があると仮定します。 ${\displaystyle (a,b,c,d,e)}$${\displaystyle D_{1}}$

この例では、は の最低値なので、要素aとb をクラスタ化します。 ${\displaystyle D_{1}(a,b)=17}$${\displaystyle D_{1}}$

• 最初の枝の長さの推定

u は、現在aとbが接続されているノードを表します。設定 により、要素aとb はuから等距離になります。これは、超距離性仮説の期待値に対応します。aとb をuに接続する枝の長さは (最終的な樹形図を参照) になります。${\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}$${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$

• 最初の距離行列の更新

次に、初期の近接行列を新しい近接行列(下記参照) に更新します。この行列は、 aとbがクラスタリングされているため、サイズが 1 行 1 列縮小されます。 の太字の値は、最初のクラスターの各要素と残りの各要素 間の最小距離を維持して計算された新しい距離に対応します。${\displaystyle D_{1}}$${\displaystyle D_{2}}$${\displaystyle D_{2}}$${\displaystyle (a,b)}$

${\displaystyle {\begin{array}{lllllll}D_{2}((a,b),c)&=&\min(D_{1}(a,c),D_{1}(b,c))&=&\min(21,30)&=&21\\D_{2}((a,b),d)&=&\min(D_{1}(a,d),D_{1}(b,d))&=&\min(31,34)&=&31\\D_{2}((a,b),e)&=&\min(D_{1}(a,e),D_{1}(b,e))&=&\min(23,21)&=&21\end{array}}}$

斜体で示された値は、最初のクラスターに含まれない要素間の距離に対応するため、マトリックスの更新による影響を受けません。 ${\displaystyle D_{2}}$

• 2番目のクラスタリング

新しい距離行列から始めて、前の 3 つのアクションを繰り返します 。 ${\displaystyle D_{2}}$

ここで、 および は の最小値であるため、クラスターを要素cと要素eに結合します。 ${\displaystyle D_{2}((a,b),c)=21}$${\displaystyle D_{2}((a,b),e)=21}$${\displaystyle D_{2}}$${\displaystyle (a,b)}$

• 2番目の枝の長さの推定

v は、現在、、c、e が接続されているノードを表します。超距離制約により、aまたはb をvに、cをvに、eをvに接続するブランチは等しく、合計の長さは次のようになります。 ${\displaystyle (a,b)}$

${\displaystyle \delta (a,v)=\delta (b,v)=\delta (c,v)=\delta (e,v)=21/2=10.5}$

欠けている枝の長さを推測します。

${\displaystyle \delta (u,v)=\delta (c,v)-\delta (a,u)=\delta (c,v)-\delta (b,u)=10.5-8.5=2}$（最終的な樹形図を参照）

• 2回目の距離行列更新

次に、行列を新しい距離行列（下記参照）に更新します。この行列は、 cとeのクラスタリングにより、サイズが 2 行 2 列縮小されます 。 ${\displaystyle D_{2}}$${\displaystyle D_{3}}$${\displaystyle (a,b)}$

${\displaystyle D_{3}(((a,b),c,e),d)=\min(D_{2}((a,b),d),D_{2}(c,d),D_{2}(e,d))=\min(31,28,43)=28}$

最終的なマトリックスは次のようになります。 ${\displaystyle D_{3}}$

そこで、クラスターとを結合します。 ${\displaystyle ((a,b),c,e)}$${\displaystyle d}$

とが現在接続されている(ルート) ノードを とします。とを接続するブランチの長さは次のようになります。 ${\displaystyle r}$${\displaystyle ((a,b),c,e)}$${\displaystyle d}$${\displaystyle ((a,b),c,e)}$${\displaystyle d}$${\displaystyle r}$

${\displaystyle \delta (((a,b),c,e),r)=\delta (d,r)=28/2=14}$

残りの枝の長さを推定します。

${\displaystyle \delta (v,r)=\delta (a,r)-\delta (a,v)=\delta (b,r)-\delta (b,v)=\delta (c,r)-\delta (c,v)=\delta (e,r)-\delta (e,v)=14-10.5=3.5}$

これで樹形図が完成しました。すべての先端 ( 、、、、および)が から等距離にあるため、樹形図は超距離です 。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle e}$${\displaystyle d}$${\displaystyle r}$

${\displaystyle \delta (a,r)=\delta (b,r)=\delta (c,r)=\delta (e,r)=\delta (d,r)=14}$

したがって、樹形図は、最も深いノードである によってルート化されます。 ${\displaystyle r}$

単一リンク クラスタリングの単純なアルゴリズムは、基本的に最小全域木のクラスカルのアルゴリズムと同じです。ただし、単一リンク クラスタリングでは、クラスターが形成される順序が重要ですが、最小全域木では、アルゴリズムによって選択された距離を形成するポイントのペアのセットが重要です。

代替のリンケージ スキームには、完全リンケージ クラスタリング、平均リンケージ クラスタリング ( UPGMAおよびWPGMA )、およびWard 法があります。凝集型クラスタリングの単純なアルゴリズムでは、異なるリンケージ スキームを実装するには、アルゴリズムでクラスター間距離を計算するために異なる式を使用するだけで済みます。調整する必要がある式は、上記のアルゴリズムの説明で太字で強調表示されています。ただし、以下で説明するようなより効率的なアルゴリズムは、すべてのリンケージ スキームに同じように一般化されるわけではありません。

単一リンク クラスタリングの単純なアルゴリズムは理解しやすいですが、時間の計算量が で遅くなります。^[6] 1973 年に、R. Sibson は、時間の計算量と空間の計算量(どちらも最適) を持つ SLINK と呼ばれるアルゴリズムを提案しました。SLINK アルゴリズムは、番号付きアイテムのセットに対するクラスタリングを2 つの関数で表します。これらの関数は両方とも、アイテム と少なくとも 1 つの大きな番号のアイテムの両方を含む最小のクラスターを見つけることによって決定されます。最初の関数 は、アイテム を クラスター 内で最も番号の大きいアイテムにマップします。2 番目の関数 は、アイテム を クラスター の作成に関連付けられた距離にマップします。各アイテム番号をその関数値にマップする 2 つの配列にこれらの関数を格納するには スペースが必要であり、この情報でクラスタリング自体を決定するのに十分です。Sibson が示すように、アイテムのセットに新しいアイテムが追加されると、同じ方法で表される、追加セットの新しい単一リンク クラスタリングを表す更新された関数を、時間 で古いクラスタリングから構築できます。 SLINKアルゴリズムは項目を1つずつループし、クラスタリングの表現に追加します。^{[7] [8]}${\displaystyle O(n^{3})}$${\displaystyle O(n^{2})}$${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle C}$${\displaystyle i}$${\displaystyle \pi }$${\displaystyle i}$${\displaystyle C}$${\displaystyle \lambda }$${\displaystyle i}$${\displaystyle C}$${\displaystyle O(n)}$${\displaystyle O(n)}$

同じ最適な時間と空間の境界で実行される代替アルゴリズムは、最小全域木に対する単純なアルゴリズムとクラスカルのアルゴリズムの等価性に基づいています。クラスカルのアルゴリズムを使用する代わりに、与えられたアイテムと距離の最小全域木（クラスタリングではない）を構築するのに時間と空間を要するバイナリヒープのないバリエーションのプリムのアルゴリズムを使用できます。次に、最小全域木のエッジによって形成されたスパースグラフにクラスカルのアルゴリズムを適用すると、追加の時間と空間でクラスタリング自体が生成されます。^[9]${\displaystyle O(n^{2})}$${\displaystyle O(n)}$${\displaystyle O(n\log n)}$${\displaystyle O(n)}$

• クラスター分析
• 完全連鎖クラスタリング
• 階層的クラスタリング
• 分子時計
• 近隣への参加
• 上場企業
• 会員

• Matlab で使用されるリンク