データセット内のクラスターの数を決定する

データ セット内のクラスターの数( k平均法アルゴリズムではkと表示されることが多い量)を決定することは、データ クラスタリングで頻繁に発生する問題であり、クラスタリング問題を実際に解決するプロセスとは別の問題です。

特定のクラスのクラスタリング アルゴリズム(特にk平均法、kメドイド法、期待値最大化アルゴリズム) には、検出するクラスターの数を指定する、一般にkと呼ばれるパラメーターがあります。 DBSCANやOPTICS アルゴリズムなどの他のアルゴリズムでは、このパラメーターを指定する必要はなく、階層的クラスタリングではこの問題は完全に回避されます。

kの正しい選択は曖昧な場合が多く、その解釈はデータ セット内のポイントの分布の形状とスケール、およびユーザーが希望するクラスタリング解像度によって異なります。さらに、ペナルティなしでk を増やすと、結果のクラスタリングにおけるエラーの量が常に減少し、各データ ポイントが独自のクラスターと見なされる場合は (つまり、 k がデータ ポイントの数nに等しい場合)、極端な場合はエラーがゼロになります。直感的には、kの最適な選択は、単一のクラスターを使用したデータの最大圧縮と、各データ ポイントを独自のクラスターに割り当てることによる最大精度との間でバランスが取れたものになります。データ セットの特性に関する事前の知識からkの適切な値が明らかでない場合は、何らかの方法でそれを選択する必要があります。この決定を行う方法にはいくつかのカテゴリがあります。

エルボー法は、説明される分散のパーセンテージをクラスター数の関数として調べます。クラスター数を選択する際には、クラスターをもう 1 つ追加してもデータのモデリングがあまり良くならないような数を選択する必要があります。より正確には、クラスター数に対してクラスターによって説明される分散のパーセンテージをプロットすると、最初のクラスターは多くの情報を追加します (多くの分散を説明します) が、ある時点で限界ゲインが低下し、グラフに角度が生じます。この時点でクラスター数が選択されるため、「エルボー基準」と呼ばれます。ほとんどのデータセットでは、この「エルボー」はあいまいであるため、^[1]この方法は主観的で信頼性が低くなります。軸のスケールは任意であるため、角度の概念は明確に定義されておらず、均一なランダム データであっても曲線は「エルボー」を生成するため、この方法は信頼性が低くなります。^[2] 説明された分散の割合は、グループ間の分散と全体の分散の比率であり、F検定とも呼ばれます。この方法のわずかなバリエーションは、グループ内の分散の曲率をプロットします。^[3]

この方法は、1953年にロバート・L・ソーンダイクが考案した推測にまで遡ることができます。 ^[4] エルボー法の考え方は単純明快に聞こえますが、他の方法（以下に詳述）の方がより良い結果が得られます。

統計学とデータマイニングにおいて、X平均法クラスタリングはk平均法クラスタリングの一種で、赤池情報量基準（AIC）やベイズ情報量基準（BIC）などの基準に達するまで、繰り返し細分化を試行し、最良の結果の分割を維持することでクラスターの割り当てを改良します。^[5]

クラスターの数を決定するための別の方法セットは、赤池情報量基準(AIC)、ベイズ情報量基準(BIC)、または逸脱情報量基準(DIC) などの情報量基準です (クラスタリング モデルの尤度関数を作成できる場合)。たとえば、k平均モデルは「ほぼ」ガウス混合モデルであり、ガウス混合モデルの尤度を構築して情報量基準値を決定することもできます。^[6]

速度歪み理論は、情報理論的基準によりエラーを最小化しながら効率を最大化するクラスターの数を決定する「ジャンプ」法と呼ばれるk の選択に適用されています。^[7]このアルゴリズムの戦略は、 1 からnまでのすべてのkの値に対してk-meansなどの標準的なクラスタリング アルゴリズムを実行し、結果として得られるクラスタリングの歪み (後述) を計算することにより、入力データの歪み曲線を生成することです。次に、歪み曲線は、データの次元に基づいて選択された負の累乗によって変換されます。結果の値のジャンプは、kの妥当な選択を意味し、最大のジャンプは最良の選択を表します。

入力データのクラスタリングによる歪みは、正式には次のように定義されます。データ セットを、共通の共分散 Γ を持つ G 個のコンポーネントの混合分布で構成されるp次元のランダム変数Xとしてモデル化します。 を、 Xの特定のサンプルに最も近い中心を持つK 個のクラスター中心のセットとすると、 K個の中心をデータに 適合させるときの次元あたりの最小平均歪みは次のようになります。${\displaystyle c_{1}\ldots c_{K}}$${\displaystyle c_{X}}$

${\displaystyle d_{K}={\frac {1}{p}}\min _{c_{1}\ldots c_{K}}{E[(X-c_{X})^{T}\Gamma ^{-1}(X-c_{X})]}}$

これは、 Xと最も近いクラスター中心との間の次元あたりの平均マハラノビス距離でもあります。クラスター中心のすべての可能なセットを最小化するのは非常に複雑なため、実際には、標準的なクラスタリング アルゴリズムを使用してクラスター中心のセットを生成し、その結果を使用して歪みを計算することによって歪みを計算します。p 次元のデータ ポイント X の入力セットを使用したジャンプ メソッドの疑似コードは次のとおりです。 ${\displaystyle c_{X}}$

JumpMethod(X):
     Y = (p/2)
    とし、サイズn+1のリストDを
    初期化します。 D[0] = 0
    とし、k = 1 ... nの場合:
        k 個のクラスターを持つクラスター X (例: k 平均法)
        d = 結果として得られるクラスタリングの歪みとする
        D[k] = d^(-Y)
    J(i) = D[i] - D[i-1]
    と定義し、 J(k)を最大化する1からnまでのkを
返します。

変換のべき乗の選択は、速度歪み理論からの結果を使用した漸近的推論によって動機付けられます。データX が単一の任意のp次元ガウス分布を持ち、 を0 より大きいあるαに対して固定するとします。すると、 p が無限大に近づくにつれて、極限におけるK個のクラスターのクラスタリングの歪みは になります。漸近的に、べき乗に対するクラスタリングの歪みはに比例し、これは定義によりクラスターの数Kにほぼ比例することがわかります。言い換えると、単一のガウス分布の場合、クラスターの実際の数 (1 であるはず) を超えてK を増やすと、歪みが線形に増加します。この動作は、複数の分布成分が混在する一般的なケースで重要です。 ${\displaystyle Y=(p/2)}$${\displaystyle K=\lfloor \alpha ^{p}\rfloor }$${\displaystyle \alpha^{-2}}$${\displaystyle (-p/2)}$${\displaystyle \alpha^{p}}$

X を、共通の共分散を持つG 個の p次元ガウス分布の混合とします。この場合、 G未満の任意の固定Kに対して、 p が無限大に近づくにつれてクラスタリングの歪みは無限大になります。直感的には、これは、正しいクラスター数未満のクラスタリングでは、漸近的に高次元のデータを記述できず、歪みが際限なく増加することを意味します。上記のように、Kをpの増加関数、つまり にすると、上記と同じ結果が得られ、 p が無限大に近づくにつれて極限での歪みの値は に等しくなります。同様に、変換された歪みとクラスター数Kの間にも同じ比例関係があります。 ${\displaystyle K=\lfloor \alpha ^{p}\rfloor }$${\displaystyle \alpha^{-2}}$

上記の結果をまとめると、 pの値が十分に高い場合、変換された歪みはK < Gではほぼゼロですが、その後突然ジャンプし、K ≥ Gでは線形に増加し始めることがわかります。 K を選択するためのジャンプ アルゴリズムは、これらの動作を利用して、クラスターの実際の数に最も適した値を特定します。 ${\displaystyle d_{K}^{-p/2}}$

この方法の数学的裏付けは漸近的な結果によって与えられていますが、このアルゴリズムは妥当な次元を持つさまざまなデータ セットでうまく機能することが経験的に検証されています。上記の局所的なジャンプ法に加えて、同じ変換された歪み値を使用してK を選択するための、破線法と呼ばれる 2 番目のアルゴリズムが存在します。破線法では、2 つの線分の単純な最小二乗誤差近似を行うことで、変換された歪みのグラフ内のジャンプ ポイントが特定されます。理論的には、 K < Gの場合はx軸に沿い、 K ≥ Gの場合は変換された歪みプロットの線形増加位相に沿います。破線法は、決定が局所的ではなくグローバルであるという点でジャンプ法よりも堅牢ですが、ガウス混合成分の仮定にも依存します。一方、ジャンプ法は完全にノンパラメトリックであり、一般的な混合分布で実行可能であることが示されています。

データの平均シルエットは、クラスターの自然数を評価するためのもう 1 つの有用な基準です。データ インスタンスのシルエットは、そのクラスター内のデータとどれだけ密接に一致しているか、および隣接クラスター (データからの平均距離が最も短いクラスター) のデータとどれだけ緩く一致しているかを示す尺度です。^{[8]シルエットが 1 に近い場合、データは適切なクラスター内にあることを意味し、シルエットが -1 に近い場合、データは間違ったクラスター内にあることを意味します。}遺伝的アルゴリズムなどの最適化手法は、最大のシルエットを生み出すクラスターの数を決定するのに役立ちます。^[9] また、正しいクラスターの数でシルエットが最大化される可能性が高くなるように、データを再スケーリングすることもできます。^[10]

クロスバリデーションのプロセスを使用して、クラスターの数を分析することもできます。このプロセスでは、データがv個の部分に分割されます。各部分は順番にテスト セットとして取り分けられ、他のv  − 1 個のトレーニング セットでクラスタリング モデルが計算され、テスト セットの目的関数の値 (たとえば、k平均法の重心までの二乗距離の合計) が計算されます。これらのv値は、クラスターの数ごとに計算され、平均化されます。クラスター数は、クラスターの数が増えても目的関数がわずかに減少するだけになるように選択されます。^{[引用が必要]}

文書-用語行列D （サイズm×n、mは文書数、nは用語数）で定義される文書コレクションのカバー係数を使用してテキストデータベースをクラスタリングする場合、クラスタの数は、 tがD内のゼロ以外のエントリの数である式で大まかに推定できます。Dでは、各行と各列に少なくとも1つのゼロ以外の要素が含まれている必要があることに注意してください。^[11]${\displaystyle {\tfrac {mn}{t}}}$

カーネル行列は、入力情報の近接性を定義します。たとえば、ガウス放射基底関数では、特徴空間と呼ばれる高次元空間での入力のドット積を決定します。特徴空間ではデータがより線形に分離可能になると考えられており、そのため、線形アルゴリズムをデータに適用すると、より高い成功率が得られます。

カーネル行列を解析することで、最適なクラスター数を見つけることができる。^[12]この方法は、カーネル行列の固有値分解によって進められる。次に、固有値と固有ベクトルを解析して、入力分布のコンパクトさの尺度を取得する。最後に、プロットが描かれ、そのプロットの曲線がデータセット内の最適なクラスター数を示す。これまでの方法とは異なり、この手法では事前にクラスタリングを実行する必要はなく、データから直接クラスター数を見つける。

Robert Tibshirani、Guenther Walther、およびTrevor Hastieは、ギャップ統計量を使用してデータセット内のクラスターの数を推定することを提案しました。^[13] ギャップ統計量は、理論的根拠に基づいて、クラスター中心の周りのクラスター内平方和が、データのヌル参照分布の下で期待される平方和からどれだけ離れているかを測定します。期待値は、元のデータの特性を持つがクラスターが存在しないヌル参照データをシミュレートすることによって推定されます。次に、クラスターの最適数は、観測された平方和がヌル参照を最も下回る kの値として推定されます。

これまでの多くの方法とは異なり、ギャップ統計は、クラスタリングが良好なkの値が存在しないことを教えてくれますが、信頼性は、与えられたデータに対して想定されるヌル分布（例えば、一様分布）がどれだけ妥当であるかに依存します。これは合成設定ではうまく機能する傾向がありますが、すべての属性が同等に重要であると想定しているため、例えば情報価値のない属性を持つ難しいデータセットをうまく処理することはできません。^[14]

ギャップ統計はRのクラスターパッケージ^[15]のclusGap関数として実装されています。

• クラスターグラム - クラスター診断プロット - ( k )個のクラスターを選択するための視覚的な診断 ( Rコード)
• k-means 分析の最適な k 値を決定する 8 つの方法 – k - means クラスター分析の k の最適値を計算するいくつかの方法のRコードを含むstackoverflowの回答