データマイニングにおける
クラスタリングの研究
東北大学工学部情報工学科
徳山研究室 4年 鈴木 晶子
研究の背景―データマイニング―

データマイニング
– 巨大なデータベースから知識を抽出する技術
膨大な量のデータから…

役に立つ知識を発見!!
データマイニング技術の1つ⇒クラスタリング
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
本研究の目的

大規模データを扱う2つのクラスタリングア
ルゴリズムを取り上げる
– 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)
1つのデータ“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.
データの中からランダムに1点 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.
最後に、クラスタの“良さ”が最大となるものを1つ出力する
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点 / 1クラスタ

実験2 : 実際のデータを用いた実験
– アルファベットの発音に関する音声データ
– データ数 : 6,238 ; 属性数 : 617 ; クラス数 : 26
2004/03/03
卒論発表会
21
実験結果(実験1)

人工生成データに対する実験結果
100
95
90
精度(%)
85
80
BIRCH
FastDOC
75
70
65
60
55
50
10
25
50
100
150
200
データの次元数
2004/03/03
卒論発表会
22
実験結果(実験2)

実際のデータに対する実験結果
– 音声データに対するクラスタリング精度
BIRCH : 53.6%
 FastDOC : 30.7%


FastDOCのほうが精度が低い原因
– データを射影することにより考慮する属性の数
が減り、一部の情報が失われた
– クラスタの幅が2wか∞かの2つしかないので、
データセットを正確に分割できない
2004/03/03
卒論発表会
23
まとめ



2つのクラスタリングアルゴリズム
– BIRCH : 階層構造を用いた
ボトムアップ的クラスタリング
– DOC : 射影を用いた
トップダウン的クラスタリング
クラスタの数が多く、クラスタ1個あたりに含まれる
データの数が少ないデータセットには不向き
今後の課題―アルゴリズムの改良―
– パラメータの設定方法の検討
– BIRCHとDOCの融合
2004/03/03
卒論発表会
24
fin.
ダウンロード

PPT