素晴らしいクラスタリングアルゴリズムがサイエンス誌に掲載されました

著者 (Alex Rodriguez、Alessandro Laio) は、さまざまな形状のクラスターを識別でき、ハイパーパラメータを簡単に決定できる非常にシンプルでエレガントなクラスタリング アルゴリズムを提案しました。

アルゴリズムのアイデア

このアルゴリズムでは、クラスターの中心が比較的低い局所密度を持ついくつかの点に囲まれており、これらの点は他の高い局所密度を持つ点から遠く離れていると想定しています。まず、局所密度 ρi と高い局所密度の点までの距離 δi という 2 つの値を定義します。

で

dc はカットオフ距離で、ハイパーパラメータです。したがって、ρi は、ポイント i からの距離が dc 未満のポイントの数に相当します。アルゴリズムは ρi の相対値にのみ敏感なので、dc の選択は比較的堅牢です。推奨されるアプローチは、各ポイントの近傍の平均数がすべてのポイントの 1% ～ 2% になるように dc を選択することです。

最も密度の高いポイントについては、局所的または全体的に極端な密度を持つポイントのみ、隣接するポイント間の間隔が通常よりも大きくなることに注意してください。

クラスタリングプロセス

比較的大きな局所密度 ρi と大きな δi を持つポイントは、クラスターの中心と見なされます。局所密度は小さいが δi が大きいポイントは外れ値です。クラスターの中心を決定した後、他のすべてのポイントは、最も近いクラスターの中心によって表されるクラスターに属します。次に例を示します。

左の図は2次元空間におけるすべての点の分布を示し、右の図はρを水平座標、δを垂直座標として示しています。このような図は決定木と呼ばれます。点1と10のρiとδiはどちらも比較的大きく、クラスターの中心点であることがわかります。点26、27、28のδiも比較的大きいですが、ρiは小さいため外れ値です。

クラスター分析

クラスター分析では、通常、特定のクラスターに割り当てられる各ポイントの信頼性を判断する必要があります。このアルゴリズムでは、まず各クラスターの境界領域、つまりクラスターに割り当てられているが、他のクラスターのポイントとの差が dc 未満のポイントを定義します。次に、各クラスターについて、境界領域内で最もローカル密度が高いポイントを見つけ、そのローカル密度を ρh とします。クラスター内でローカル密度が ρh より大きいすべてのポイントは、クラスター コアの一部であると見なされます (つまり、ポイントをクラスターに割り当てる信頼性が非常に高い)。残りのポイントは、クラスターのハローであると見なされます (つまり、ノイズと見なすことができます)。次に例を示します。

図 A は生成されたデータの確率分布であり、図 B と C はそれぞれ分布から 4000 と 1000 のポイントを生成します。図 D と E はそれぞれ 2 つのデータ グループ B と C の決定木です。両方のデータ グループには、ρi と δi が比較的大きいポイントが 5 つしかないことがわかります。これらのポイントはクラスターの中心です。クラスターの中心を決定した後、各ポイントはさまざまなクラスター (色付きのポイント) またはクラスター ハロー (黒いポイント) に分割されます。図 F は、サンプリングされたポイントの数が増えるにつれて、クラスタリング エラー率が徐々に低下し、アルゴリズムが堅牢であることを示しています。

***さまざまなデータ分布に対するアルゴリズムのクラスタリング効果を示します。非常に優れています。

参考文献:

[1] 密度ピークの高速探索と発見によるクラスタリング。アレックス・ロドリゲス、アレッサンドロ・ライオ

この記事はKemaswill のブログから引用しました