CLARANS

CLARANS (Clustering Large Applications based on RANdomized Search)†

↑

PAM (Partitioning Around Medoids)†

k-medoids法のように各クラスタは，そのクラスタ中の一つデータ点である medoid で代表する．各クラスタの medoid と，そのクラスタ内の点の非類似度の総和を最小にするクラスタを求める．

最初はランダムに k 個の medoid を選ぶ．
各 medoid と，それ以外の点とを交換し，最も評価値を改善する交換を実行する．
どの点を交換しても評価値が改善されなくなったら終了．

↑

CLARA (Clustering LARge Applications)†

全ての点から medoid を探すのではなく，ランダムサンプリングした点の中から探すことで高速化．

40+2k個のサンプルをランダムにデータ集合からとりだし，アルゴリズムPAMでk個のmedoidを見つける．
サンプルされた以外の点を medoid に分類する．
前の回より，評価値が改善されたら新しい medoid を採用．
以上の手続きを5回ぐらい反復する．

↑

CLARANS (Clustering Large Applications based on RANdomized Search)†

クラスタに割り当てられているデータ点が一つだけ違うような分割を隣接した分割と考える．n 個のデータ点を k 個に分ける可能な分割全てをノードとし，隣接した分割を辺で結んだグラフ \(G_{nk}\) を考える．PAMではこのグラフの全ての隣接ノードを探索するが，CLARANSではランダムに選んだ隣接ノードをチェックする．また，CLARAのように，何度か反復して一番良い結果を最終結果とする．

パラメータ numlocal と maxneighbor を与える．\(i=1\)．mincostを大きな数に
currentノードを \(G_{nk}\) の任意のノードに
j=1
currentのランダムな近隣Sについて，コストの差を求める．
Sのコストの方が小さければ，currentをSにしてステップ(3)へ
jを1増やす．もし \(j\le\mathrm{maxneighbor}\) ならステップ(4)へ
\(j\gt\mathrm{maxneighbor}\) なら，currentのコストとmincostを比較．currentのコストの方が小さければ，mincostをcurrentのコストにして，bestnodeをcurrentにする．
iを1加える．もし \(i\le\mathrm{numlocal}\) なら，bestnodeを出力して停止．そうでなければステップ(2)へ．