多変量解析ゼミ 第10回

多変量解析ゼミ 第10回
第12章クラスター分析
発表者
直江 宗紀
クラスター分析

クラスター分析とは



大量のデータの中に存在するクラスター(集落)をデー
タ同士の距離によって分類していく、 分析方法
扱う対象は分析目的により、サンプルの場合、変数の
場合と場合によって変わるが分析は可能
分析で用いられる方法は大別すると「階層的方法」と
「非階層的方法」がある
分析の流れ

大雑把な分析の流れ



個々の対象間の距離を測る
「近い」と判断できる対象間の距離、及び「クラスター」
と判断する距離を決め、測った対象間の距離との比
較、併合を行う
適当な距離でグループ分けできたクラスターに含まれ
る対象を調べ、グループの特徴を把握する
デンドログラム

デンドログラム(樹形図)とは


クラスター分析において対象間の距離を樹形図にお
いてグラフ化された物
計算手法によって対象間の距離、配置は変わる
(よってデンドログラムの形が変わる)
デンドログラムの例
図1 デンドログラム図例(左図はデンドログラム例に用いたデータプロット図)
最短距離法

最短距離法とは




階層的手法の一つ
最も近い対象間の距離を、
クラスター間の距離として
比較、併合を行う方法
欠点:鎖効果が起こりやすい
鎖効果とは、ある一つのクラ
スターに対象が1つずつ順に
吸収されてクラスター形成が
される状態
図2 鎖効果が起こってしまっている
デンドログラム
1つでも近い対象があればクラス
ターに統合されるため、鎖効果
が起こりやすい
様々な距離計算方法

クラスター分析では


分析する際、対象間の距離を計算する必要がある
クラスター分析で用いる「距離」は以下の物がある





ユークリッド距離(Euclidean distance)
重み付きユークリッド距離(Standardized Euclidean
distance)
マハラノビス距離(Mahalanobis distance)
ミンコフスキー距離(Minkowsky distance)
本解説では、最短距離法の距離計算に
ユークリッド距離を用いることとする
ユークリッド距離

ユークリッド距離の計算方法

変数が2個の場合(要素i番から要素j番までの時)
dij  ( xi1  x j1 )2  ( xi 2  x j 2 )2 ・・・(1)

変数がp個の場合の一般式
dij 
p
(x
k 1
ik
 x jk )
2
・・・(2)
最短距離法による分析(1)

変数2個の場合の分析


実際の分析の流れを示す
ため、以下の例題を用意
例題:国語と英語の成績
表1 5段階評価の国語、英語成績表
生徒No.
国語x1
英語x2
1
5
1
2
4
2
3
1
5
4
5
4
5
5
5
図3 表1データのプロット図
(Rを用いて描画)
最短距離法による分析(2)

対象間の距離を計算

ユークリッド距離で計算
表2 対象間のユークリッド距離(1)
生徒No.
1
2
3
4
1
2
1.41
3
5.66
4.24
4
3.00
2.24
4.12
5
4.00
3.16
4.00
1.00
最短距離法による分析(3)

クラスター形成



一番値の小さい要素を探し、初期クラスタとする
表2よりNo.4とNo.5が一番小さい→クラスターC1(4,5)とする
この時クラスターと各対象の距離も一番短い方を選ぶ
表3 対象間のユークリッド距離(2)
生徒No.
1
2
3
1
2
1.41
3
5.66
4.24
C1(4,5)
3.00
2.24
4.00
最短距離法による分析(4)

クラスター形成



遂次一番小さい値を選択してクラスター形成
2番目にNo.1,No.2の距離が短いためクラスターC2(1,2)形成
3番目にC1,C2の距離が短いためクラスターC3(1,2,4,5)形成
表4 対象間のユークリッド距離(3)
生徒No.
C2
3
C2(1,2)
3
4.24
C1(4,5)
2.24
表5 対象間のユークリッド距離(4)
生徒No.
C3
C3(1,2,4,5)
4.00
3
4.24
最短距離法による分析(5)

デンドログラムを作成


先程のクラスター形成時
に選択した最短距離値を
元にデンドログラムを作成
する
クラスター評価


任意の距離で区切ること
によりデンドログラムから
クラスタの分類が出来る
ただし解析者の意図によ
り任意で区切る距離、グ
ループの意味が変わる
図4 例題のデンドログラム
(Rを用いて作成)
最短距離法による分析(6)

変数がp個の場合の分析






ほとんど変数が2個の場合と変わらない
ユークリッド距離変数p個の場合の距離計算を行う
表2と同様に対象間距離表を作成
最短距離値を遂次抜き取りクラスター形成
デンドログラムの作成
デンドログラムからデータの評価
最短距離法による分析(7)

解析例題:試験成績
表6 試験成績データ
生徒No.
国語x1
英語x2
数学x3
理科x4
1
86
79
67
68
2
71
75
78
84
3
42
43
39
44
4
62
58
98
95
5
96
97
61
63
6
39
33
45
50
7
50
53
64
72
8
78
66
52
47
9
51
44
76
72
10
89
92
93
91
最短距離法による分析(7)
表7 表1のデータの対象間ユークリッド距離
生徒
No.
1
2
3
4
5
6
7
8
9
1
2
24.86
3
67.76
70.61
4
52.03
29.85
81.90
5
22.02
42.88
81.71
71.20
6
71.64
70.94
13.45
77.38
88.15
7
44.69
35.57
39.66
43.06
64.36
36.96
8
29.98
46.64
44.75
68.85
40.27
51.65
41.50
9
50.47
38.85
47.28
36.47
71.69
41.35
15.03
49.13
10
37.19
29.78
98.67
43.89
43.38
99.83
65.15
66.44
66.32
最短距離法による分析(8)
図5 表7から得られるデンドログラム(Rを用いて描画)
他の階層的手法

階層的手法として用いられる代表的な手法

最短距離法(nearest neighbor method)


最長距離法(furthest neighbor method)


最も遠い対象間の距離をクラスター間の距離とする
群平均法(group average method)


最も近い対象間の距離をクラスター間の距離とする
すべての対象間距離の平均をクラスター間の距離とする
重心法(centroid method)

各クラスターの代表点を重心とし、重心間の距離をクラス
ター間の距離とする
ウォード法(1)

ウォード法(ward’s
method)とは



階層的手法の1つ
他の階層的手法よりクラス
ター内の集まりが良く、鎖効
果が起こりにくく、そのため良
いクラスター分析結果が得ら
れやすい
クラスター形成は、クラスター
内の平方和を最も小さくする
という基準によって形成
図6 良いクラスター分析の結果
を示すデンドログラム例
ウォード法(2)

変数が2個の場合のウォード法

ウォード法で用いる距離は平方和距離
2
Sij   ((xik  x.k )2  ( x jk  x.k )2 ) ・・・(3)
k 1

上記式で求めた距離表を元にクラスターを結合
クラスター内平方和の増加分が最小のものを統合し
ていく
ウォード法(3)

表1の例題を元に計算

No.1とNo.2の生徒のクラスター内平方和
S12  (5  4.5)  (4  4.5)  (1 1.5)  (2 1.5)
S12  1.00
2

2
2
2
上記のようにして計算していく
平均値は計算する同変数の対象要素同士の平均値
ウォード法(4)


右図はウォード法による
計算により作成できた距
離表
クラスター形成


平方和の増加が最小であ
る、No.4,No.5をクラスター
として統合する
この際クラスターと対象間
の距離が変化するため計
算をしなおす必要がある
表8 対象間のウォード法による距離(1)
生徒
No.
1
2
3
4
1
2
1.00
3
16.00
9.00
4
4.50
2.50
8.50
5
8.00
5.00
8.00
0.50
ウォード法(5)

クラスター統合後の距離算出



統合したクラスターと元のクラスターの平方和を算出
例としてクラスターC1(4,5)と要素1の距離算出
結合後の平方和S145は
S145  (5  5.00)2  (5  5.00)2  (5  5.00)2
(1  3.33)2  (4  3.33)2  (5  3.33)2  8.67

平方和増加分ΔS145は
S145  S145  S1  S45  8.67  0  0.50  8.17
ウォード法(6)

同様にして計算して距離の計算を算出する

下表はクラスターC1と各対象間の距離値に直した表
表9 対象間のウォード法による距離(2)
生徒No.
1
2
3
1
2
1.00
3
16.00
9.00
C1
8.17
4.83
10.83
ウォード法(7)

他のクラスターについて


同様にして平方和の増加分が最小の物を選ぶ
下表は最終段階までの計算結果
表10 対象間のウォード法による距離(3)
生徒No.
C2
3
C2
3
16.33
C1
9.25
表11 対象間のウォード法による距離(4)
生徒No.
C3
C3
10.83
3
14.45
ウォード法(7)

以上の結果から得られるデンドログラム
図7 表1例題のウォード法から得られたデンドログラム(Rを用いて作成)
ウォード法(8)

変数がp個の場合のウォード法


考え方は変数が2個の時と変わらない
一般式は以下の通り
nl
p
Sl  ( xlik  xl .k )2
・・・(4)
i 1 k 1
nm
p
Sm  ( xm ik  xm.k )2
・・・(5)
Slm  Sl  Sm  Slm
・・・(6)
i 1 k 1
ウォード法(9)

式(4)~(6)をまとめると

以下の式が成り立つ
ni nm p
2
Slm 
(
x

x
)
・・・(7)

l .k
m.k
nl  nm k 1

これらの式を用いて例題の表6を解析する
ウォード法(10)
表12 表6のウォード法における距離
生徒
No.
1
2
3
4
5
6
7
8
9
1
2
309
3
3365
2493
4
4229.5 4786.5 3353.5
5
2253.5 2011.5 7153.5
2535
6
2405.5 1971.5
689.5
1986
3885
7
1812.5 2007.5
540.5
2924
2661
683
8
513.5
619.5
2001.5
1387
1072
2112
861
9
2158.5 2303.5
730.5
2969
3186
762
1026
1207
10
462.5
3706.5
1774
515
4038
1918
1324
705.5
1623
ウォード法(11)

表12からクラスター統合をして得られるデンドログラム
図8 例題表6のデンドログラム(ウォード法)
最後に

本発表に関し、以下の解析ソフトを利用した



Lucent Technology R
Microsoft
Excel
R




統計計算、グラフィックスのための言語・環境
GNUプロジェクトの一つ
オープンソースのため、無料で提供されている
Official Site URL
http://www.r-project.org/