ORCLUS

ORCLUS†

ORCLUS (arbitrarily ORiented projected CLUSter generation) はトップダウン型の部分空間クラスタリング手法． ORCLUS と同じ戦略だが，各クラスタの部分空間が軸に平行である制限がない．

初期的には，多数の小さな，比較的高次元の部分空間をもつクラスタに分割．これらのクラスタを反復的に併合して，少数の低次元部分空間をもつクラスタを見つけてゆく．

軸に平行でない部分空間を見つけるために，主成分分析の逆である，minor component analysis (MCA) を利用する．主成分分析では，固有値の大きな軸から選ぶが，小さな軸から選ぶことで，分散の小さな軸を見つけることができる．

各反復は，以下の3ステップ

(1) データ点のクラスタへの割り当て
各データを，そのseed点までの距離が一番近いクラスタへ分類．ただし，距離は，各クラスタの現在の部分空間中で測る
(2) 部分空間の再計算
MCAを用いて，クラスタ内の分散が小さくなるような部分空間を選択する
(3) クラスタの併合
- クラスタを仮に併合したとして，併合後の部分空間を求める
- 併合前と併合後の部分空間が近いと併合されやすい性質をもつ評価関数に基づいて併合するクラスタを決定

事前に定めた数になるまで，クラスタ数が減ったら停止．

さらに，BIRCH のように各クラスタごとに十分統計量のみを保持することで，大規模化も行う．