反転距離を使用したK平均クラスタリング

Question

まず、宿題プロジェクトを解決するためにこのアルゴリズムを適用する方法を理解しようとしています。だから、私は宿題の解決策を探していません、問題を解決する私のアルゴリズムを完了するのを助けるだけです。

私はK平均クラスタリングを使用して、大きなセット（2^6）のアレイをクラスタリングしようとしています。これらの配列はシーケンス[0,1,2 ... 31]のユニークな順列です。しかし、ユークリッド距離を使用する代わりに、私は反転距離を使用する必要があります。

k-meansの最初のステップは、データセットからk = 10のランダムな点を選択することです。次に、ランダムk-ポイントのそれぞれに対するデータセットの各値の反転距離を計算します。これにより、最初のクラスタリングが行われます。

今、私は次のステップをユークリッド距離から反転距離に変換する方法を理解できません。これらのクラスタのそれぞれの中心を（反転距離の点で）どのように見つけることができるので、クラスタリングのステップを繰り返すことができますか？

コンパクトな質問として、ユークリッド距離は、（または同等の）逆転距離の良い近似ですか？私はそれが信じていないが、私はそれを証明する方法についてはわからない。

ありがとうございます。

Answer 1

一般に、はでは非ユークリッド距離のk-meansを使用できません。アルゴリズムを実行しようとすることはできますが、アルゴリズムが終了するときの収束の意味についてはほとんど言いません。

the Wikipedia entryのように、ユークリッド距離はアルゴリズム固有のものです。これは、EタイプとMタイプのステップ（the EM algorithmのように）を交互に行うことによって機能し、ユークリッド距離については、両方のステップが同じ目的関数を最小限に抑えることが示され得る。他の距離では、コードが同じに見えるにもかかわらず、一般的には保持されません。

this question in Cross Validatedも参照してください。

距離が異なる場合は、別のもの、たとえばhierarchical clusteringまたはk-medoidsを使用する必要があります。