CLARANS の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• CLARANS へ行く。

* CLARANS (Clustering Large Applications based on RANdomized Search) [#o38783d2]

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

*** PAM (Partitioning Around Medoids) [#m912c568]

k-medoids法のように各クラスタは，そのクラスタ中の一つデータ点である medoid で代表する．各クラスタの medoid と，そのクラスタ内の点の非類似度の総和を最小にするクラスタを求める．
- 最初はランダムに k 個の medoid を選ぶ．
- 各 medoid と，それ以外の点とを交換し，最も評価値を改善する交換を実行する．
- どの点を交換しても評価値が改善されなくなったら終了．

*** CLARA (Clustering LARge Applications) [#wc212ebd]

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

*** CLARANS (Clustering Large Applications based on RANdomized Search) [#p7187bce]

クラスタに割り当てられているデータ点が一つだけ違うような分割を隣接した分割と考える．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)へ．

> -- しましま

** 関連項目 [#r63f568a]

//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[PAM]]
-[[CLARA]]
#br
-[[クラスタリング]]
-[[k-medoids法]]
#br
-[[検索:CLARANS CLARA PAM]]

** リンク集 [#n5fdafe5]

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

*** Freeware [#kb091fb0]

-[[cluster@CRAN>http://cran.r-project.org/web/packages/cluster/index.html]]：PAM と CLARA を含む [[R]] のパッケージ

** 関連文献 [#s12f4ad0]

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

-PAM と CLARA~
L.Kaufman and P.J.Rousseeuw "Finding Groups in Data: an Introduction to Cluster Analysis" John Wiley & Sons (1990)~
[[GoogleScholarAll:inding Groups in Data: an Introduction to Cluster Analysis]]
-CLARANS の基本文献~
R.T.Ng and J.Han, "Efficient and Effective Clustering Methods for Spatial Data Mining" VLDB1994~
[[GoogleScholarAll:Efficient and Effective Clustering Methods for Spatial Data Mining]]
-[[Book/データマイニング(データサイエンスシリーズ3)]] 6.2.1節
-[[Book/Data Mining - Concepts and Techniques]] 7.4.2節