PROCLUS

PROCLUS †

PROCLUS (PROjected CLUStering) は，トップダウン型の部分空間クラスタリングの先鞭となった手法．k-medoids型のクラスタリングに，各クラスタごとに部分空間を抽出できるようにしたもの．初期化，反復，精錬の3段階で構成される：

初期化

初期 medoid \(m_1,\ldots,m_k\) を選択

反復

medoid の改良，部分空間抽出，データ点のクラスタの割り当てを反復的に行う．

medoid の中で，クラスタ内のデータ点の偏差が大きなものや，medoidに割り当てられたデータ数が小さすぎるものは良くないとみなす．これらは，ランダムに他のデータ点と入れ替えて，クラスタが改良されるなら，medoidを置き換える．この手続きを何回か繰り返す．

部分空間は，各クラスタごとに2個以上で，全クラスタで割り当てる次元の総数が \(kl\) 個（\(l\)はパラメータ）となるようにする．どの次元を選ぶかだが，各medoid \(m_i\) ごとに，一番近い他のmedoidまでを半径とする領域を，そのmedoidの近傍 \(L_i\) とする．そして，各軸に沿った，近傍 \(L_i\) 内の点とmedoid \(m_i\) の間の平均距離に基づき，この距離が小さい，すなわち，よくまとまった軸を選択する．各クラスタごとに選んだ軸の集合を \(D_i\) とする．

medoid 以外のデータ点は，\(D_i\) 中の軸のみを用いて選んで測った距離が一番近いmedoidへ割り当てる．

精錬

クラスタごとの次元を，近傍ではなく，そのクラスタ内のデータ点を使って再計算．また，各クラスタごとに，medoid から遠いデータ点をはずれ値とする．