シルエット（クラスタリング）

シルエットは、データのクラスター内の一貫性を解釈および検証する方法です。この手法は、各オブジェクトがどの程度適切に分類されているかを簡潔にグラフで表します。^[1]これは、1987年に ベルギーの統計学者ピーター・ルセウによって提案されました。

シルエット値は、オブジェクトが自身のクラスター（凝集度）と他のクラスター（分離度）とでどの程度類似しているかを示す尺度です。シルエットの範囲は -1 から +1 で、値が高いほど、オブジェクトは自身のクラスターとよく一致し、隣接するクラスターとは一致していないことを示します。ほとんどのオブジェクトの値が高い場合、クラスタリング構成は適切です。多くのポイントの値が低いか負の値である場合、クラスタリング構成のクラスターが多すぎるか少なすぎる可能性があります。平均シルエット幅が 0.7 を超えるクラスタリングは「強力」、0.5 を超える値は「妥当」、0.25 を超える値は「弱い」と見なされますが、データの次元が増えると、距離がより類似するため、次元の呪いのためにこのような高い値を達成することが難しくなります。^{[引用が必要]}シルエットスコアは、クラスターが凸形状の場合のクラスター品質の測定に特化しており、データクラスターの形状が不規則であったりサイズが変動したりすると、パフォーマンスが低下する可能性があります。^{[2]シルエットは}ユークリッド距離やマンハッタン距離などの任意の距離測定基準で計算できます。

データがk-medoidsやk-meansなどの任意の手法によってクラスターにクラスタ化されていると想定します。 ${\displaystyle k}$

データポイント（クラスター内のデータポイント）については、 ${\displaystyle i\in C_{I}}$${\displaystyle i}$${\displaystyle C_{I}}$

${\displaystyle a(i)={\frac {1}{|C_{I}|-1}}\sum _{j\in C_{I},i\neq j}d(i,j)}$

は、 と同じクラスター内の他のすべてのデータ ポイント間の平均距離です。ここで、はクラスターに属するポイントの数、 はクラスター内のデータ ポイントと間の距離です(合計に距離を含めないため、で割ります)。 は、クラスターへの割り当ての適切さの尺度として解釈できます(値が小さいほど、割り当てが適切です)。 ${\displaystyle i}$${\displaystyle |C_{I}|}$${\displaystyle C_{I}}$${\displaystyle d(i,j)}$${\displaystyle i}$${\displaystyle j}$${\displaystyle C_{I}}$${\displaystyle |C_{I}|-1}$${\displaystyle d(i,i)}$${\displaystyle a(i)}$${\displaystyle i}$

次に、あるクラスターに対する点の平均相違度を、から内のすべての点までの距離の平均として定義します(ただし)。 ${\displaystyle i}$${\displaystyle C_{J}}$${\displaystyle i}$${\displaystyle C_{J}}$${\displaystyle C_{J}\neq C_{I}}$

各データポイントについて、次のように定義します。 ${\displaystyle i\in C_{I}}$

${\displaystyle b(i)=\min _{J\neq I}{\frac {1}{|C_{J}|}}\sum _{j\in C_{J}}d(i,j)}$

は、他の任意のクラスター（つまり、 がメンバーではない任意のクラスター）内のすべての点に対する の平均距離が最小となる（したがって、式の演算子） 。この平均相違度が最小となるクラスターは、点 に次ぐ最適なクラスターであるため、の「隣接クラスター」と呼ばれます。 ${\displaystyle \min}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$

ここで、1つのデータポイントのシルエット（値）を定義します。${\displaystyle i}$

${\displaystyle s(i)={\frac {b(i)-a(i)}{\max\{a(i),b(i)\}}}}$、 もし${\displaystyle |C_{I}|>1}$

そして

${\displaystyle s(i)=0}$、 もし${\displaystyle |C_{I}|=1}$

これは次のように書くこともできます:

${\displaystyle s(i)={\begin{cases}1-a(i)/b(i),&{\mbox{if }}a(i)<b(i)\\0,&{\mbox{if }}a(i)=b(i)\\b(i)/a(i)-1,&{\mbox{if }}a(i)>b(i)\\\end{cases}}}$

上記の定義から、

${\displaystyle -1\leq s(i)\leq 1}$

はサイズ = 1 のクラスターに対しては明確に定義されていないことに注意してください。その場合は と設定します。この選択は任意ですが、境界 -1 と 1 の中間点にあるという意味で中立的です。^[1]${\displaystyle a(i)}$${\displaystyle s(i)=0}$

が 1 に近づくためにはが必要です。は が自身のクラスターとどれほど類似していないかを示す尺度であり、値が小さいということはよく一致していることを意味します。また、 が大きいということはが近隣のクラスターとあまり一致していないことを意味します。したがって、 が 1 に近いということは、データが適切にクラスター化されていることを意味します。 が-1 に近い場合、同じ論理により が近隣のクラスターにクラスター化されている方が適切であることがわかります。 がゼロに近いということは、データが 2 つの自然なクラスターの境界上にあることを意味します。 ${\displaystyle s(i)}$${\displaystyle a(i)\ll b(i)}$${\displaystyle a(i)}$${\displaystyle i}$${\displaystyle b(i)}$${\displaystyle i}$${\displaystyle s(i)}$${\displaystyle s(i)}$${\displaystyle i}$${\displaystyle s(i)}$

クラスターのすべてのポイントの平均は、クラスター内のすべてのポイントがどれだけ密にグループ化されているかの尺度です。したがって、データセット全体のすべてのデータの平均は、データがどれだけ適切にクラスタリングされているかの尺度です。クラスタリングアルゴリズムで不適切な が選択された場合 (例: k-means ) に発生する可能性があるように、クラスターが多すぎたり少なすぎたりすると、一部のクラスターは通常、他のクラスターよりもはるかに狭いシルエットを表示します。したがって、シルエットプロットと平均を使用して、データセット内のクラスターの自然数を決定することができます。クラスター固有の特徴重みを使用してデータを再スケーリングすることにより、シルエットが正しいクラスター数で最大化される可能性を高めることもできます。^[3]${\displaystyle s(i)}$${\displaystyle s(i)}$${\displaystyle k}$

カウフマンらは、データセット全体のデータの平均の最大値を表すシルエット係数という用語を導入した^[4]。すなわち、 ${\displaystyle s(i)}$

${\displaystyle SC=\max _{k}{\tilde {s}}\left(k\right),}$

ここで、特定の数のクラスターについて、データセット全体のすべてのデータの平均を表します。 ${\displaystyle {\tilde {s}}\left(k\right)}$${\displaystyle s(i)}$${\displaystyle k}$

シルエット係数を計算するにはすべてのペアワイズ距離が必要なので、この評価は k-means によるクラスタリングよりもはるかにコストがかかります。各クラスターの中心を持つクラスタリングの場合、代わりに各ポイントに対して次の簡略化されたシルエットを使用できます。これは距離のみを使用して計算できます。 ${\displaystyle {\mathcal {O}}(N^{2})}$${\displaystyle \mu_{C_{I}}}$${\displaystyle C_{I}}$${\displaystyle i\in C_{I}}$${\displaystyle {\mathcal {O}}(Nk)}$

${\displaystyle a'(i)=d(i,\mu _{C_{I}})}$そして、${\displaystyle b'(i)=\min _{C_{J}\neq C_{I}}d(i,\mu _{C_{J}})}$

常に定義される追加の利点があり、それに応じて簡略化されたシルエットと簡略化されたシルエット係数^{[5]を定義する。}${\displaystyle a'(i)}$

${\displaystyle s'(i)={\frac {b'(i)-a'(i)}{\max\{a'(i),b'(i)\}}}}$

${\displaystyle SC'=\max _{k}{\frac {1}{N}}\sum _{i}s'\left(i\right)}$。

クラスター中心が算術平均（k-meansクラスタリングなど）ではなくメドイド（k-medoidsクラスタリングなど）である場合、これはメドイドベースシルエット^[6]またはメドイドシルエット^{[7]とも呼ばれます。}

すべてのオブジェクトが最も近いメドイドに割り当てられている場合（k-メドイドクラスタリングのように）、であり、したがってであることがわかります。^[7]${\displaystyle a'(i)\leq b'(i)}$${\displaystyle s'(i)={\frac {b'(i)-a'(i)}{b'(i)}}=1-{\frac {a'(i)}{b'(i)}}}$

平均シルエットを使用して、例えば k-medoids や k-means から得られたクラスタリングを評価する代わりに、シルエットを最大化するソリューションを直接見つけることもできます。これを最大化する閉じた形式のソリューションはありませんが、通常は、これらの方法で行われるように、ポイントを最も近いクラスターに割り当てるのが最善です。Van der Laan ら^{[6] は、}この目的のために k-medoids の標準アルゴリズム PAM を適応させ、このアルゴリズムを PAMSIL と呼ぶことを提案しました。

1. PAMを使用して初期メドイドを選択する
2. この初期解の平均シルエットを計算する
3. メドイドmと非メドイドxの各ペアについて
   1. mとxを入れ替える
   2. 結果の解の平均シルエットを計算する
   3. 最高のスワップを覚えておく
   4. 次の反復のためにmとxの交換を解除する
4. 最適なスワップを実行して 3 に戻ります。改善が見つからない場合は停止します。

ステップ 3 のループはペアに対して実行され、 のシルエットを計算するため、このアルゴリズムには時間がかかります ( iは反復回数)。 ${\displaystyle {\mathcal {O}}(Nk)}$${\displaystyle {\mathcal {O}}(N^{2})}$${\displaystyle {\mathcal {O}}(N^{3}ki)}$

これはかなりコストのかかる操作であるため、著者らはメドイドベースのシルエットも使用し、その結果得られるアルゴリズムをPAMMEDSILと呼ぶことを提案している。^[6]これには時間が必要である。 ${\displaystyle {\mathcal {O}}(N^{2}k^{2}i)}$

BatoolらはOSilという名前で同様のアルゴリズムを提案し、より大きなデータセットに対してサブサンプルのみの問題を解決するCLARAのようなサンプリング戦略を提案している。^[8]

PAMアルゴリズムの最近の改良を採用することで、FastMSCはメドイドシルエットを使用した実行時間をわずか に短縮しました。^[7]${\displaystyle {\mathcal {O}}(N^{2}i)}$

クラスターの最大数 k _maxから始めて、最悪の中心（シルエットの変化の観点から）を繰り返し削除し、再最適化することで、最良の（最高のmedoidシルエット）クラスタリングを自動的に決定できます。データ構造を再利用できるため、異なる数のクラスターに対してアルゴリズムを繰り返し実行するよりも計算コストが大幅に削減されます。^[9] このアルゴリズムはペアワイズ距離を必要とし、通常はペアワイズ距離行列を使用して実装されます。メモリ要件は、これを非常に大きなデータセットに適用する場合の主な制限要因です。 ${\displaystyle {\mathcal {O}}(N^{2})}$

• クラスター分析
• デイヴィス・ボールディン指数
• カリンスキー・ハラバシュ指数
• ダン指数
• データセット内のクラスターの数を決定する