ｽﾗｲﾄﾞﾀｲﾄﾙなし

知能システム論
ークラスタリング－
クラスタリングとは、データ間に距離を定義し、
距離が近いデータ同士をグループ（クラスター）にまとめる作業
例
• 顧客のクラスタリング
• 化学物質のクラスタリング
• 遺伝子のクラスタリング
階層的クラスタリング
ボトムアップ型
近いクラスター同士を融合するプロセスを繰り返す
クラスターCi , Cj 間の距離に結果が依存
距離の例：
  

Dmin (Ci , C j )  min{d ( x , y ) | x  Ci , y  C j }
  

Dmax (Ci , C j )  max{d ( x , y) | x  Ci , y  C j }
7
5
9
8
6
3
1
2
4
1
2
3
4
5
6
Dendrogram
7
8
9
階層的クラスタリング: トップダウン分割型
与えられた集合を分割することを繰り返す
確率的モデル型クラスタリング
複数の（正規）分布が重なり全データが分布していると
仮定し、各分布を予測
k - クラスタリング（本講義で紹介）
k - クラスタリング
d 次元ユークリッド空間
R d 内の点集合 S を、 S を覆い
S  S1  S 2    S k 　かつ
（クラスターと呼ぶ）
、互いに交わらない
S1 , S 2 ,  , S k に分解すること。
クラスター
S i の評価 : 直径
   
diam eter( S i ) ＝ max x1  x 2 | x1 , x 2  S i
x1 ,, x d 


x
i 1,, d
2
i

1
2
S i の評価：重心からの距離の分散
c( S i ) 
1
Si
var(S i ) 

x

xSi
1
Si


xSi

x  c( S i )
2

k 個の部分集合
S1
S2
diameter(S1) = diameter(S2)
var(S1) >> var(S2)
誤差二乗平均によるクラスターの評価
S の k  クラスタリングを
{S1 , , S k }
 各クラスターの重心は
1
c( S i ) 
Si

y

yS i


 Sの各点 x と、 x が属するクラスターの
1
S
 

i {1,, k } xS i

x  c( S i )
重心間の距離の分散
2
を m eansquared error (誤差二乗平均) と呼ぶ
誤差二乗平均を最小化する k-クラスタリングを計算する
問題はＮＰ困難
できるだけ小さくすると言われているアルゴリズムとして
k-means 法がある
k-means 法の様々な変形が広く使われている
k  m eans法
クラスターの代表点の集合を T、

T の点 y を代表点とするクラスターを S y と表現 .
1. （初期化） S から k 個の点を選択し、 Tの初期集合とする .

2. （再クラスタリング）
各代表点 y  T について S y を空集合にリセット .　
  
 

S の各点 x に最も近い T の点 y x  y  min
x  z を計算し、 x を S y に追加.


z T


3. （代表点を再計算） S y に登録された点全体の重心は代表点 y から

1
ずれている可能性がある . 各代表点 y  T を重心 cS y  
S y
4. 誤差二乗平均が改善しなくなるまで、ステッ

u
 に更新.

uS y
プ２と３を繰返す
.
k-means 法による
2-クラスタリング
初期の選択
次ページ
重心を再計算
再クラスタリング
重心を再計算
再クラスタリング
誤差二乗平均は収束
クラスターの評価に直径を使う場合
S の k クラスタリング
C  {S1 , S 2 , , S k } に対して
q (C )  max{diam eter( Si ) | i  1, , k } と定義
q(C ) を最小化する k クラスタリング
Cを
効率的に計算できるか？
与えられた B に対して q (C )  B となる k クラスタリングが
存在するか否かを決定する問題はＮＰ完全
近似的解法
opt  minq (C ) | C は S の k  クラスタリング
q (C )  2  opt となる k  クラスタリング
アルゴリズムが存在する

とおく
C を生成する
Gonzalez’s farthestpoint heuristics
 T を S のクラスターの代表元の集合とし、空集合で初期化

 S から１点 c1 を選択し T に追加
 各 j  2, , k について以下のステップを実行


1. x　 S  T に最も近い T の点を neighbor( x )と記述


x は neighbor( x ) を代表元とするクラスターに属すると定義

2. 属するクラスターの代表元との距離が最大の点 c j  S  T
(farthestpoint)を T に追加



 
c j  neighbor(c j )  max x  neighbor( x ) | x  S  T 

c1

c3

c2
代表点
代表点以外の点
 

補題 T  c1 , c2 , , c j 1 のとき、
1  h  i  j について


 
neighbor(c j )  c j  ch  ci

つまり、 T  {c j } の任意の２点は


neighbor(c j )  c j 以上離れている


neighbor(c3 )  c2 の場合

c1

c3

c2


 
neighbor(c3 )  c2なので c2  c3 


c2 が c3 より先に選択されたので
 
c1  c3
 
 
c1  c3  c1  c2


neighbor(c3 )  c1 の場合

c1

c3

c2


neighbor(c3 )  c1 なので
 
 
c1  c3  c2  c3


c2 が c3 より先に選択されたので
 
 
c1  c3  c1  c2
補題
 


T  c , c , , c のとき、
1
2
j 1
1  h  i  j について


 
neighbor(c j )  c j  ch  ci



つまり、 T  {c j } の任意の２点間距離は neighbor(c j )  c j 以上
j に関する帰納法．　一般の場合を証明


 i  j のとき、 Tの中で最も c j に近いのは neighbor(c j ) なので


 
neighbor(c j )  c j  ch  c j

neighbor(c j )

cj

ch
代表点
代表点以外の点
i  j のとき：

j  2個の代表元を選択した一つ前のステップでの状態、
 

つまり T  c1 , c2 , , c j  2  を考える。



この時点での c j 1の属するクラスターの
とすれば、帰納法の仮定より

a


代表元 neighbor(c j 1 ) を a
 
 
a  c j 1  ch  ci

b

この時点で c j の属する
クラスターの代表元を

c j 1

cj

b
 
 
 T 
c
,
c
,

,
c
j  1個代表点を選択後に
1 2
j 1 　のとき、つまり




 
neighbor(c j )  c j  a  c j 1 となることを示せ
ば十分


neighbor(c j ) c j 1のとき

a

b

a

b

c j 1

cj

c j 1

cj

c j 1が代表元として選択されたので


c j がより近い代表元 c j 1 の
 
 
b  c j  a  c j 1
クラスターに移動した
ので
 


neighbor(c j )  c j  b  c j


neighbor(c j )  b のとき、つまりクラス
ターを移動しないとき

a

b

a

b

c j 1

cj

c j 1

cj

c j 1が代表元として選択さ
れたので


 
neighbor (c j )  c j  a  c j 1
定理　Gonzalez’s farthestpoint heuristicsが生成する k クラスタリングを
q(C )が最小のk クラスタリングを
Copt とすれば
CG
q(CG )  2  q(Copt )
 Gonzalez’s farthestpoint heuristicsから k 個の代表元を選び


T  c1 , , ck  とする

 もう一回ステップ２を実行して得られる ck 1 に対して


D  ck 1  neighbor(ck 1 ) とおく
 各クラスターの直径は 2 D 以下に注意すると

ci
直径
q(CG )  2 D


D  ck 1  neighbor(ck 1 ) なので
任意のクラスターの直径は 2D 以下

 補題より T  ck 1 の任意の２点間の距離は D 以上である
 すると Coptのどれかのクラスター
その２点間の距離を D'とすれば

は T  ck 1の２点を含む．
D  D'  q(Copt )
 q(CG )  2 D より、 q(CG )  2  q(Copt )

Download Report