k-means法と類似した分割最適化クラスタリング型の手法. k-means法は任意のベクトルの間の非類似度が計算できないと適用できないが,k-medoids法は分類する任意のデータ対の非類似度が,非類似度行列の形で与えられていれば適用可能. k-means法との具体的な相違点は次の二つ.
クラスタはセントロイドではなくmedoidで代表される. medoidとは,クラスタ内のデータ点で,その点以外のクラスタ内の点でまでの非類似度の総和が最小になる点.クラスタを \(X_i=\{x\}\),データ間の非類似度を \(d(x,y)\) で表すとき,medoidは次式 \[\arg\min_{x\in X_i}\sum_{y\in (X_i-\{x\})} d(x,y)\]
k-means法は,クラスタを代表するセントロイドとクラスタ内のデータ点の距離の二乗の総和を最小にする.一方,k-medoids法では,medoidとデータ点の距離の総和(二乗の総和ではない)を最小化する.
アルゴリズムはk-means法とほぼ同じだが,クラスタのセントロイドの代わりにmedoidを求める点のみが異なる.サンプル数を \(N\) とクラスタ数を \(k\) として,計算量は \(O(N^2k)\) となり,k-means法より遅い.距離の2乗でエラーを評価するk-meansより,距離の1乗で評価するため,はずれ値の影響は少ない.
-- しましま