CLARANS (Clustering Large Applications based on RANdomized Search)

PAM (Partitioning Around Medoids)

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

CLARA (Clustering LARge Applications)

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

CLARANS (Clustering Large Applications based on RANdomized Search)

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

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

-- しましま

関連項目

リンク集

Freeware

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:10:53