画像処理工学

画像処理工学

画像の分類（２） －クラスタリング－

教師なし分類

0 255

255

•

–

–

特徴空間

画像からいくつかの サンプルを取り出し 特徴空間にプロット

0 255

特徴空間

255

サンプル間の 類似度を基に クラスタを 見つけだす

教師なし分類

•

– N

C

–

最短距離にある２つのクラスタを融合していく処理を

C

255

要素数が ２つ以上の クラスタとの 距離は？

255

２つのクラスタ間の距離が 最短となるものどうしを １つのクラスタに

教師なし分類

•

–

–

0 5

5

① ②

③

④ ⑤

⑥

⑦

x ₁ x ₂

x ₁ x ₂

①

1 2

②

3 1

③

2 3

④

3 6

⑤

4 6

⑥

7 2

⑦

7 4

７つのサンプルデータ

特徴空間

教師なし分類

•

–

–

0 5

① ②

③

④ ⑤

⑥

⑦

x x ₂

5 2 20 5 6 40

5 5 26 17 5

10 13 26 26

1 32 20

5 13 2













① ② ③ ④ ⑤ ⑥ ⑦

①

②

③

④

⑤

⑥

サンプル間の距離

最短距離

教師なし分類

•

–

0 5

5

① ②

③

④ ⑤

⑥

⑦

x ₁ x ₂

特徴空間

5 2 20 5 6 40

5 5 26 17 5

10 13 26 26

1 32 20

5 13 2















① ② ③ ④ ⑤ ⑥ ⑦

①

②

③

④

⑤

⑥

⑦

サンプル間の距離

短い方を③と（④，⑤）

との距離とする

こちらを③と（④，⑤）との 距離として採用する

教師なし分類

•

–

その中で最短距離をとる２つのクラスタを融合する

0 5

① ②

③

④ ⑤

⑥

⑦

x x ₂

5 2 20 6 40

5 5 17 5

10 26 26

13 2

 

 

 

   

 



① ② ③ ④ ⑤ ⑥ ⑦

①

②

③

④

⑤

⑥

サンプル間の距離

最短距離

教師なし分類

•

–

0 5

5

① ②

③

④ ⑤

⑥

⑦

x ₁ x ₂

特徴空間

5 20

5 5 17 5

10 26 26

13 2

    

 

 

   

 





① ② ③ ④ ⑤ ⑥ ⑦

①

②

③

④

⑤

⑥

⑦

サンプル間の距離

（①，③）と（④，⑤）の 距離とする

教師なし分類

•

–

0 5

① ②

③

④ ⑤

⑥

⑦

x x ₂

5

5 5 17 5

10 26 26

13 2

     

 

 

   

 



① ② ③ ④ ⑤ ⑥ ⑦

①

②

③

④

⑤

⑥

サンプル間の距離

階層的クラスタリングにおける距離の定義

•

–

c

a

b

–

c

h

互いに最短距離にある要素間の距離を

c

h

[ ]

min ,

ch ah bh

d = d d

クラスタ

c

クラスタ

a

クラスタ

b

クラスタ

h d _bh

d _ah d _ch

＝

階層的クラスタリングにおける距離の定義

•

–

–

階層的クラスタリングにおける距離の定義

•

–

c

h

互いに最長距離にある要素間の距離を

c

h

–

[ ]

max ,

ch ah bh

d = d d

クラスタ

c

クラスタ

a

クラスタ

b

クラスタ

h d _bh

d _ah

d _ch

＝

階層的クラスタリングにおける距離の定義

•

–

d _ch

d _ah

d _bh

–

d _ah

d _bh

–

a

b

とすることに相当する

2 4

ah bh ab

ch

d d d

d +

= −

新たなクラスタ

c

クラスタ

a

クラスタ

クラスタ

h

d _ah

x

x

x x

• k

means

–

C

–

– C

–

N

N

N

教師なし分類

• k

means

① 適当に種子点を

C

② 各サンプルデータを最短距離にあるクラスタに振り分ける

（距離はユークリッド距離を用いる）

教師なし分類

( ) ⁰ ( ) ⁰ ( ) ⁰ ( ) ⁰

1 2

c M =   c M c M  c M K  

ある種子点

c

_c M ⁽⁰⁾

K

• k

means

③ 得られた各クラスタの平均ベクトルをそれぞれ求め，それら を新たなクラスタ重心とする

④ 処理の

i

i + 1

そうでない場合は②，③を繰り返す

教師なし分類

( ) ¹

1

1

^N

i n

c k c k

c n

M X

N

+

=

= ∑ c ⁿ X k

i + 1

c

k

_c M _k ⁽ⁱ⁺¹⁾

クラスタ

c

n

k

：

( ) ( )

( ¹ ) ²

2

1 K

i i

c c k c k

k

D M M ⁺

=

= ∑ −

^c

処理を終了

• k

means

教師なし分類

① 種子点を２個設定し，それらに最短距離にあるサンプルを振り分ける（左）

その後，振り分けたクラスタの平均ベクトルをそれぞれ求める（右）

② 平均ベクトルを新たな重心としてサンプルを振り分けなおす

• k

means

教師なし分類

③ 処理を繰り返し，新たな重心位置と前の重心位置とがほぼ一致 していると見なせるならば処理を終了する

• k

means

–

•

–

•

•

① 与えられた

N

C

② 最終的に得たいクラスタを代表する平均ベクトルを分類対象画像 から抽出するなど，ユーザの主観に基づいて種子点を与える

教師なし分類