行う $k$-手段、dbscan、および階層的クラスタリングはすべて(疑似)メトリックに依存していますか?

Aug 21 2020

クラスタリング手法は $k$-means、dbscan、および階層的クラスタリングはすべて距離測度で機能します $d$ つまり、(疑似)メトリックです。つまり、次の要件を満たします。 $$ d(x,x)=0 $$ $$ d(x,y) = d(y,x) $$ $$ d(x,z) \leqslant d(x,y) + d(y,z) $$

このアルゴリズムは、たとえば三角不等式を満たさないなど、これらの要件を満たさない2つのデータポイント間の距離測度でも機能するかどうか疑問に思っています。

回答

1 Lewian Aug 21 2020 at 22:00

$k$-は、標準形式ではユークリッド距離を使用することを意味します。これが必要なのは、そうでなければ、最適にクラスターを表す重心が平均と名前ではないためです。$k$-手段は正当化されないでしょう。残念ながら、最近では多くの著者がこの用語を使用しています$k$-他のタイプの距離を含むより一般的なものを意味しますが、それは用語の誤解を招く使用です。

原則として、dbscanや単一、平均、または完全なリンケージ階層的クラスタリングなどの適切な距離ベースの方法を使用できます(ただし、ウォード法は使用できません。 $k$-は、三角形の不等式を満たさない一般的な非類似度を持つユークリッド距離に依存することを意味します。これが適切かどうかは、特定の状況と非類似性によって異なります。dbscanは近隣に基づいているため、解釈が難しい結果を生成する可能性があると思います。可能であれば、近隣の概念は奇妙になります。$d(x,z)=100$ だが $d(x,y)=d(y,z)=0.1$ そのため $x$ そして $z$ どちらも近くにあります $y$しかし、お互いに非常に遠いです。とはいえ、三角不等式に違反するいくつかの非類似性は、かなり穏やかな方法でしかそうしません。