machine-learning - kmeansには三角不等式が必要ですか？

Question

kmeansで使用される距離測度には、三角不等式が必要かどうか疑問に思います。

Answer 1

古典的なkmeansは、L2距離のユークリッド空間で定義されているため、そこから自動的に三角不等式が得られます（三角不等式は、距離/距離の定義方法の一部です）。非ユークリッド計量を使用している場合は、特に「平均」の意味を定義する必要があります。

三角不等式がない場合は、2つのポイントが互いに非常に離れている可能性がありますが、両方が3番目のポイントに近い可能性があることを意味します。このケースをどのように解釈したいかを考える必要があります。

そうは言っても、私は過去に、とりわけ三角不等式を満たさなかった距離測度を使用した平均リンケージ階層的クラスタリングを使用しましたが、それは私のニーズに非常に役立ちました。

Answer 2

k-meansは、三角不等式を満たすユークリッド距離用に設計されています。

他の距離関数を使用すると、収束が停止する可能性があるため、リスクがあります。ただし、その理由は三角不等式ではありませんが、平均は距離関数を最小化しない可能性があります。（算術平均は、任意の距離ではなく、二乗和を最小化します！）

再計算を回避するために三角不等式を利用するk-meansのより高速な方法があります。しかし、古典的なMacQueenまたはLloyd k-meansに固執する場合は、三角不等式は必要ありません。

無限ループに陥らないように、他の距離関数の使用には注意してください。平均がクラスター中心までの距離を最小化することを証明する必要があります。これを証明できない場合、目的関数が単調に減少しなくなるため、収束に失敗する可能性があります。したがって、距離関数の収束を証明するようにしてください。