CURE

Clustering Using REpresentatives (CURE) は,超楕円体以外の形状のクラスタを抽出できるクラスタリング手法. そうした形状のクラスタを扱うため,各クラスタを一つの代表点ではなく,c 個の代表点で表す.

クラスタの生成
凝集型階層的クラスタリングである単リンク法に似ている. ただし,単リンク法では,二つのクラスタ中の点の間で最も近い点の対の距離をクラスタの距離とする.それに対し,CURE では,c個の代表点の間の最短距離がクラスタ間の距離となる. それ以外は,各クラスタがデータ点一つの状態から始めて,最も近いクラスタを逐次併合する.

クラスタの併合
クラスタ u と v を併合して,新たなクラスタ w を作る.このとき,w の代表点集合を次の二つの手続きで見つける

  • クラスタ w 中で十分に離れた点の集合を見つける.これは,最初に任意の点を選び,それから離れた点を逐次選ぶ.これを c 回繰り返す.
  • この集合中の点を,w 中の点の重心の方向へ倍収縮する.この操作によって,単リンク法のチェイニング効果のようにノイズに対して脆弱になることが回避できる.

w の代表点を選ぶとき,w 中の全ての点ではなく,u と v の代表点のみを候補として計算量を減らす方法も提案.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-01-08 (火) 16:36:18 (1427d)