k-メドイド

k -メドイド問題は、 k -平均法に似たクラスタリング問題です。この名前は、Leonard Kaufman とPeter J. RousseeuwがPAM (Partitioning Around Medoids) アルゴリズムで作ったものです。^[1] k -平均法とk -メドイド法は両方ともパーティション (データセットをグループに分割) であり、クラスター内にあるとラベル付けされた点と、そのクラスターの中心として指定された点の間の距離を最小化しようとします。k -平均法アルゴリズムとは対照的に、k -メドイド法は実際のデータ点を中心 (メドイドまたは標本) として選択するため、 k -平均法よりもクラスター中心の解釈可能性が高まります。k -平均法では、クラスターの中心は必ずしも入力データ点の 1 つではありません (クラスター内の点間の平均です)。さらに、k -メドイド法は任意の相違度尺度で使用できますが、k -平均法では通常、効率的なソリューションを得るためにユークリッド距離が必要です。 k -medoids は、ユークリッド距離の二乗の合計ではなく、ペアワイズ相違度の合計を最小化するため、 k -meansよりもノイズや外れ値に対して堅牢です。

k -medoids は、 n個のオブジェクトのデータ セットをk個のクラスターに分割するクラスタリングの古典的な分割手法です。クラスターの数k は事前にわかっているものと想定されます(つまり、プログラマーはk -medoids アルゴリズムを実行する前に k を指定する必要があります)。指定されたkの値の「良さ」は、シルエット法などの方法で評価できます。

クラスターのメドイドは、クラスター内のすべてのオブジェクトとの相違点の合計 (および、同等に平均) が最小であるクラスター内のオブジェクトとして定義されます。つまり、クラスター内で最も中心に位置するポイントです。

一般に、kメドイド問題は正確に解くことが NP 困難です。そのため、多くのヒューリスティックな解決法が存在します。

PAM ^[1]は貪欲探索法を採用しており、最適解が見つからない可能性はあるものの、網羅的探索法よりも高速である。その仕組みは以下の通りである。

1. （ビルド）初期化：コストを最小化するために、 n個のデータポイントのうちk個をメドイドとして貪欲に選択する
2. 各データ ポイントを最も近い medoid に関連付けます。
3. (SWAP) 構成コストは減少しますが、
   1. 各メドイドmおよび各非メドイドデータポイントoについて:
      1. mとoの交換を考慮し、コストの変化を計算する
      2. コスト変更が現在最善である場合は、このmとoの組み合わせを覚えておいてください
   2. コスト関数が減少する場合は、との最適なスワップを実行します。それ以外の場合は、アルゴリズムは終了します。${\displaystyle m_{\text{best}}}$${\displaystyle o_{\text{best}}}$

元のPAMアルゴリズムの(3)の反復あたりの実行時複雑度は、コストの変化のみを計算することで です。毎回コスト関数全体を再計算する単純な実装では になります。この実行時間は、コストの変化を3つの部分に分割して計算を共有または回避することで までさらに短縮できます(FastPAM)。実行時間は、スワップを積極的に実行することでさらに短縮できます(FasterPAM)。^[2]その時点で、ランダム初期化がBUILDの実行可能な代替手段になります。 ${\displaystyle O(k(nk)^{2})}$${\displaystyle O(n^{2}k^{2})}$${\displaystyle O(n^{2})}$

文献ではPAM以外のアルゴリズムも提案されており、その中には2つの最適化ステップを交互に行うため文献では「交互」ヒューリスティックとして知られる次のボロノイ反復法が含まれる: ^{[3] [4] [5]}

1. 初期メドイドをランダムに選択する
2. コストが減少する間、繰り返します。
   1. 各クラスターにおいて、クラスター内の距離の合計を最小にする点をメドイドとする。
   2. 各ポイントを、前のステップで決定された最も近いメドイドによって定義されたクラスターに再割り当てします。

k平均法のボロノイ反復法は、結果が悪くなり、「不規則な動作」を示す傾向があります。^{[6] : 957}平均を更新する際に他のクラスターにポイントを再割り当てできないため、より小さな検索空間のみを探索します。単純なケースでも、このヒューリスティックはスワップベースの方法で解決できる劣ったソリューションを見つけることが示されています。^[2]

「メドイドリンク」を用いた階層的クラスタリングには、複数のバリエーションが提案されている。最小和リンク基準^[7]はメドイドの目的を直接使用するが、最小和増加リンクの方がより良い結果を生み出すことが示された（Wardリンクが二乗誤差の増加を使用する方法と同様）。以前のアプローチでは、リンク尺度として前のメドイドのクラスターメドイドの距離を単純に使用していたが^{[8] [9]}、2つのメドイドの距離では組み合わせに適したメドイドが存在するとは限らないため、結果が悪くなる傾向がある。これらのアプローチの実行時複雑度は であり、デンドログラムが特定のクラスター数kでカットされると、結果は通常、PAM によって見つかった結果よりも悪くなる。^[7]したがって、これらの方法は主に階層ツリー構造が必要な場合に興味深い。 ${\displaystyle O(n^{3})}$

CLARAやCLARANSなどの他の近似アルゴリズムは、実行時間と品質をトレードオフします。CLARAは複数のサブサンプルにPAMを適用し、最良の結果を維持します。CLARANSはデータセット全体で機能しますが、サンプリングを使用してメドイドと非メドイドの可能なスワップのサブセットのみを探索します。BanditPAMは、CLARANSのような均一なサンプリングではなく、マルチアームバンディットの概念を使用して候補スワップを選択します。^[10]

• ELKI には、ボロノイ反復k -medoids、オリジナルの PAM アルゴリズム、レイノルズの改善、O(n²) FastPAM および FasterPAM アルゴリズム、CLARA、CLARANS、FastCLARA、FastCLARANS など、いくつかのk -medoid バリアントが含まれています。
• Julia には、JuliaStats/Clustering.jl パッケージに、k-means スタイル アルゴリズム (高速ですが、結果の品質ははるかに劣ります) のk -medoid 実装が含まれています。
• KNIMEには、さまざまな効率的な行列距離測定をサポートするk -medoid実装と、多数のネイティブ（および統合されたサードパーティ）k -means実装が含まれています。
• Python には「kmedoids」パッケージに FasterPAM やその他のバリエーションが含まれており、追加の実装は他の多くのパッケージで見つけることができます。
• R には、オプションvariant = "faster"とによる FasterPAM の改善を含む、"cluster" パッケージに PAM が含まれていますmedoids = "random"。また、"fastkmedoids" パッケージも存在します。
• RapidMiner には KMedoids という演算子がありますが、上記の KMedoids アルゴリズムはいずれも実装されていません。代わりに、これは k-means のバリアントであり、平均値を最も近いデータ ポイント (medoid ではない) に置き換えます。これは、k-means の欠点 (座標データに限定) と平均値に最も近いポイントを見つける追加コストを組み合わせたものです。
• Rust には、 FasterPAM バリアントも含まれる「kmedoids」クレートがあります。
• MATLAB は、 k -medoid クラスタリング問題を解決するために PAM、CLARA、およびその他の 2 つのアルゴリズムを実装します。