データマイニングにおけるクラスタリングの研究東北大学工学部情報工学科徳山研究室４年鈴木晶子研究の背景―データマイニング―  データマイニング – 巨大なデータベースから知識を抽出する技術膨大な量のデータから…  役に立つ知識を発見!! データマイニング技術の１つ⇒クラスタリング 2004/03/03 卒論発表会 2 クラスタリング入力されたデータを「クラスタ」に分割すること  クラスタ  – データの部分集合 – 類似したパターンを持つデータのみが含まれる x2 x2 x1 2004/03/03 卒論発表会クラスタ C1 クラスタ C2 x1 3 本研究で扱うクラスタリング数値属性をもつデータに対するクラスタリング  d 個の属性をもつデータ ⇒d 次元空間に存在する点  表. ある商店の売り上げ 2004/03/03 商品価格売れた数 A 120 1200 B 980 750 C 4500 100 D 380 1500 E 2000 450 F 650 1000 G 1350 800 売れた数 D A F G B E C 価格卒論発表会 4 本研究の目的  大規模データを扱う２つのクラスタリングアルゴリズムを取り上げる – BIRCH [Zhang et al. 1996]  全ての要素によって特徴づけられたクラスタを作る – DOC [Procopiuc et al. 2002]   一部の要素のみによって特徴づけられたクラスタを作る実験を行い、各手法の特徴を明らかにする 2004/03/03 卒論発表会 5 発表の流れ  BIRCHの紹介 – Clustering Feature(CF)とCF木 – アルゴリズム  DOCの紹介 – 最適なクラスタの定義 – アルゴリズム実験  まとめ  2004/03/03 卒論発表会 6 BIRCH [Zhang et al. 1996]  “Clustering Feature”という概念を用いて階層木構造を作る全てのデータ集合 A∪B データの集合 A 2004/03/03 データの集合 B 卒論発表会 7 Clustering Feature (CF)  クラスタに含まれるデータの情報を要約したもの  d 次元データ（d 次元実ベクトル） : X i  ( x1, x2 ,, xd )  N個のデータからなるクラスタ : {X i }, i  1, 2, , N  クラスタのCFベクトル  CF  ( N , LS, SS) – N : クラスタに含まれるデータの数 – LS : N 個のデータの線形和 – SS : N 個のデータの二乗和 2004/03/03 卒論発表会  (i 1 X i ) N  2 (i 1 X i ) N 8 CF木各ノードが“エントリー” を持った平衡木  エントリー : CFベクトルによって表される  各ノードのエントリー数には上限がある  [CFA + CFB] [CFX + CFY] [CFA] [CFB] A∪B A 2004/03/03 B A 卒論発表会 [CFX] [CFY] B 9 CF木の構築  CF木は、初めは1つのノードしかない。  葉ノードに1つずつデータを挿入していくことにより、動的に木を構築する。 2004/03/03 卒論発表会 10 CF木の構築方法 (1/2) １つのデータ“data”を CF木に挿入するまでの過程 data 1. データを挿入する葉ノードを決定する – “data”とエントリーとの距離に基づき決定される 2. 辿り着いた葉のエントリーに“data”を挿入する – 既存のエントリーに挿入できない場合は新しいエントリーを追加 2004/03/03 卒論発表会 [CF1] [CF2] data [CF1] [CF2] [CF3] 11 CF木の構築方法 (2/2) 3. ノードの持つエントリーが増えすぎた場合、木のバランシングを行う以上の操作をデータがなくなるまで繰り返し、 CF木を構築 2004/03/03 [CF1] data [CF2] [CF3] 卒論発表会 [CF4] [CF5] [CF6] 12 BIRCHアルゴリズムデータ Phase 1 : CF木を構築する CF木 Phase 2(optional) : CF木を縮小する Phase 3 : 大域的クラスタリングクラスタ Phase 4(optional) : クラスタを精錬する 2004/03/03 卒論発表会 13 DOC [Procopiuc et al. 2002]  射影を用いたクラスタリング – データを低次元の部分空間に射影 – その射影に対してクラスタリングを行う x x 3 x 3 x 3 x 2 x 2 x 1 2004/03/03 x 2 1 卒論発表会 x 1 14 射影クラスタの定義   幅wの射影クラスタ： (C, D) – C : データの集合 – D : 座標軸の集合集合C : クラスタに含まれるデータの集合 x 3 x 2 w  集合D : クラスタの幅がwに制限される座標軸の集合 2004/03/03 卒論発表会 w x 1 ：集合Cの要素 x1 , x2：集合Dの要素 15 最適な射影クラスタの定義  射影クラスタの良さ :  ( C , D ) – |C|が大きいほど  も大きい（⇒クラスタに含まれるデータ数が多いほど良いクラスタ） – |D|が大きいほど  も大きい（⇒幅を制限する座標軸の数が多いほど良いクラスタ）  “最適なクラスタ” – 幅wをもつ射影クラスタのうち、良さ  が最大となるものしかし最適なクラスタを求めることはNP困難 ⇒ランダムアルゴリズムを用いて近似的に求める 2004/03/03 卒論発表会 16 DOCアルゴリズム 1. 2. 3. 4. データの中からランダムに１点 p を選ぶ x2 4321 q1∈X さらにデータの中からランダムに数点選び、集合Xとする点pと点q∈Xの射影について距離を測り、クラスタの形を決める w 全データをスキャンし、クラスタの中に入る点を求める q3∈X pp q2∈X w クラスタの中心 p x12軸方向の幅は2w 軸方向の幅は∞ x1 5. 2～4の操作を繰り返す 6. 点pを選びなおして、さらに2～4の操作を繰り返す 7. 最後に、クラスタの“良さ”が最大となるものを１つ出力する 2004/03/03 卒論発表会 17 DOCアルゴリズムの出力   DOCアルゴリズムによって得られるクラスタ ⇒幅2wをもつクラスタ定理 DOCアルゴリズムは1/2より高い確率で、 x 3 (C, D* ) 最適なクラスタよりも“良さ”の値が大きいクラスタを出力する。  最適なクラスタより“良さ”が大きくなる例 * * – 最適なクラスタ (C , D ) に含まれる点 p を中心としたクラスタ – 形は最適なクラスタと同じ – 最適なクラスタを全て含む 2004/03/03 卒論発表会 wp w (C * , D* ) x 2 w x 1 18 アルゴリズムの計算時間 n : データ数, d : データの次元数とすると、全体の計算時間 : O(ndC+1) （ただし、Cは定数） 2004/03/03 卒論発表会 19 実験  目的 BIRCH, DOCのクラスタリング精度を測定するただしDOCアルゴリズムは時間がかかるため、アルゴリズムを高速化させるヒュ―リスティクス FastDOCを用いた  方法 – 各アルゴリズムにデータセットを入力し、クラスタリングを行う – FastDOCでは、一度クラスタリングされた点を取り除くことにする 2004/03/03 卒論発表会 20 実験に用いたデータセット  実験1 : 人工生成データを用いた実験 – データ数 : 100,000 – 次元数 : 10~200 – クラスタ数 : 5 – 20,000点 / １クラスタ  実験2 : 実際のデータを用いた実験 – アルファベットの発音に関する音声データ – データ数 : 6,238 ; 属性数 : 617 ; クラス数 : 26 2004/03/03 卒論発表会 21 実験結果（実験１）  人工生成データに対する実験結果 100 95 90 精度（％） 85 80 BIRCH FastDOC 75 70 65 60 55 50 10 25 50 100 150 200 データの次元数 2004/03/03 卒論発表会 22 実験結果（実験２）  実際のデータに対する実験結果 – 音声データに対するクラスタリング精度 BIRCH : 53.6%  FastDOC : 30.7%   FastDOCのほうが精度が低い原因 – データを射影することにより考慮する属性の数が減り、一部の情報が失われた – クラスタの幅が2wか∞かの２つしかないので、データセットを正確に分割できない 2004/03/03 卒論発表会 23 まとめ    2つのクラスタリングアルゴリズム – BIRCH : 階層構造を用いたボトムアップ的クラスタリング – DOC : 射影を用いたトップダウン的クラスタリングクラスタの数が多く、クラスタ１個あたりに含まれるデータの数が少ないデータセットには不向き今後の課題―アルゴリズムの改良― – パラメータの設定方法の検討 – BIRCHとDOCの融合 2004/03/03 卒論発表会 24 fin.