* '''k'''-medoids法 ('''k'''-medoids method) [#u8e44729]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

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乗で評価するため,はずれ値の影響は少ない.

> -- しましま

**関連項目 [#oa32269e]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.

-[[k-medoids method]]
#br
-[[medoid]]
#br
-[[クラスタリング]]
-[[分割最適化クラスタリング]]
-[[CLARANS]] (PAM, CLARA)
-[[k-means法]]
#br
-[[検索:k-medoids法]]

**リンク集 [#a5a058e9]

//関連するWWW資源があればリンクしてください.

**関連文献 [#a10eac13]

//この%項目%に関連する書籍や論文を紹介してください.

-基本文献~
H.Vinod "Integer Programming and The Theory of Grouping" Journal Amererican Statististical Association, vo.64, pp.506-517 (1969)~
[[GoogleScholarAll:Integer Programming and The Theory of Grouping]]
-[[Book/Pattern Recognition and Machine Learning]] 9.1章

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS