バイオ・データ・マイニング/Rで階層クラスタリングを使うの変更点

*はじめに [#w8050692]
『Rによるバイオインフォマティクスデータ解析』の7.8節「階層クラスタリング」を参考にして、階層クラスタリングを行います。
#html{{
<iframe src="http://rcm-jp.amazon.co.jp/e/cm?t=tohgoroh-22&o=9&p=8&l=as1&asins=4320057082&ref=tf_til&fc1=444B4C&IS2=1&lt1=_blank&m=amazon&lc1=444B4C&bc1=FFFFFF&bg1=FFFFFF&f=ifr" style="width:120px;height:240px;" scrolling="no" marginwidth="0" marginheight="0" frameborder="0"></iframe>
}}




*準備 [#i005634f]
Rのインストールについては、次のページを見てください。
-[[MacでRを使う>機械学習/MacでRを使う]]
-[[WindowsでRを使う>機械学習/WindowsでRを使う]]

ここでは、標準で使用できる''irisデータセット''を使います。
#geshi(rsplus){{
> data(iris)
}}

このデータセットは、アヤメの種類（Species）をがく片の長さ（Sepal.Length）、幅（Sepal.Width）、花びらの長さ（Petal.Length）、幅（Petal.Width）によって分類する問題です。
長さと幅は連続値、種類はsetosa, versicolor, virginicaのいずれかをとる離散値です。

このデータセットには、setosa, versicolor, virginicaという3種類のアヤメについて、それぞれ50個ずつ、合計150個のデータが含まれています。
ランダムに10個のデータを選択して、見てみましょう。
#geshi(rsplus){{
> iris[sort(sample(1:150,10)),]
    Sepal.Length Sepal.Width Petal.Length Petal.Width    Species
4            4.6         3.1          1.5         0.2     setosa
22           5.1         3.7          1.5         0.4     setosa
65           5.6         2.9          3.6         1.3 versicolor
97           5.7         2.9          4.2         1.3 versicolor
100          5.7         2.8          4.1         1.3 versicolor
108          7.3         2.9          6.3         1.8  virginica
116          6.4         3.2          5.3         2.3  virginica
122          5.6         2.8          4.9         2.0  virginica
136          7.7         3.0          6.1         2.3  virginica
146          6.7         3.0          5.2         2.3  virginica
}}


*クラスタリング [#j0ec994d]
クラスタリングは、分類対象のデータ集合をいくつかのグループに分割するものです。
分割された部分データ集合を''クラスター''といいます。

クラスタリングの手法には、主に''階層的アプローチ''と''分割最適化アプローチ''があります。
ここでは、前者の階層的アプローチを行います。


*階層クラスタリング [#wbf466ca]
階層クラスタリングには、トップ・ダウンに階層化する''分岐型''とボトム・アップに階層化する''凝集型''があります。
ここでは、後者の凝集型をやります。

''凝集型階層クラスタリング''では、まず、1つのデータだけを含むクラスターをデータと同じ数だけ作ります。
それから、最も近い（似ている）クラスター同士を結合してより大きい新しいクラスターを作ります。
これを全てのクラスターが一つに結合されるまで繰り返します。

Rで階層クラスタリングを用いるには、''hclust''関数を用います。
hclust関数の引数には距離行列を与えます。
距離行列は、''dist''関数で求めることができます。

そこで、まず、irisデータのSepal.Length, Sepal.Width, Petal.Length, Petal.Widthの値から、距離行列を計算します。
#geshi(rsplus){{
> d <- dist(iris[,1:4])
}}

この距離行列を用いて、階層クラスタリングを行います。
#geshi(rsplus){{
> hc <- hclust(d)
}}

結果を''plot''関数を用いてプロットすると''デンドログラム''と呼ばれる図が描かれます。
#geshi(rsplus){{
> plot(hc, labels=iris[,5], xlab="Iris")
}}
#ref(hc.png,nolink,33%)

デンドログラムを見ると、どのクラスターが結合したのかがわかります。


*距離 [#ge6d4b61]
上でも説明したように、凝集型階層クラスタリングでは最も近い（似ている）クラスター同士をくっつけますが、近いか遠いかを決めるのに、距離尺度が必要になります。

一般的な距離尺度としては、''ユークリッド距離''が用いられています。
\[ d({\bf x}_1, {\bf x}_2) = \sqrt{ \sum_{i=1}^p \left( x_{2,i} - x_{1,i} \right)^2 } \]

距離行列を求めるときにmethodオプションを指定しなければ、ユークリッド距離の距離行列になります。
#geshi(rsplus){{
> d <- dist(iris[,1:4])
> hc <- hclust(d)
> plot(hc, labels=iris[,5], xlab="Euclidean")
}}
#ref(hc_euclidean_complete.png,nolink,33%)


ユークリッド距離の他に、''マンハッタン距離''（マンハッタンでのタクシーを利用するときのように、一つの軸と並行に移動することしかできないときの移動距離）
\[ d({\bf x}_1, {\bf x}_2) =\sum_{i=1}^p \left| x_{2,i} - x_{1,i} \right| \]
を使うこともできます。
マンハッタン距離を使うには、dist関数にオプション''method="manhattan"''を指定します。
#geshi(rsplus){{
> d <- dist(iris[,1:4], method="manhattan")
> hc <- hclust(d)
> plot(hc, labels=iris[,5], xlab="Manhattan")
}}
#ref(hc_manhattan_complete.png,nolink,33%)

この他にも、いくつもの距離尺度が提案されています。
類似度と距離尺度に付いてはこちらにたくさんまとめられています。
-[[類似度と距離:http://wikiwiki.jp/cattail/?%CE%E0%BB%F7%C5%D9%A4%C8%B5%F7%CE%A5]] - CatTail Wiki*



*結合方式 [#f30f8931]
ユークリッド距離もマンハッタン距離も二つのデータ同士の間の距離を表していますが、どのクラスターとどのクラスターが最も近い（似ている）のかを直接的には表していません。

求めた距離に基づいて、どのクラスターとどのクラスターを結合するのかを決めなくてはなりません。
これが結合方式です。

上の二つの例でも用いられた標準の方式は''完全連結法'' (''complete'' linkage method) という方式で、クラスター[math]C_1[/math]に含まれるデータとクラスター[math]C_2[/math]に含まれるデータの間の距離の中で最大のもの（つまり、最も離れているもの）を[math]C_1 C_2[/math]間の距離として、最も近い（似ている）クラスターを結合します。
\[ d(C_1, C_2) = \max_{{\bf x}_1 \in C_1, {\bf x}_2 \in C_2} d({\bf x}_1, {\bf x}_2) \]

''単連結法'' (''single'' linkage method) では、反対に、クラスター[math]C_1[/math]に含まれるデータとクラスター[math]C_2[/math]に含まれるデータの間の距離の中で最小のもの（つまり、最も近いもの）を[math]C_1 C_2[/math]間の距離として、最も近い（似ている）クラスターを結合します。
\[ d(C_1, C_2) = \min_{{\bf x}_1 \in C_1, {\bf x}_2 \in C_2} d({\bf x}_1, {\bf x}_2) \]
単連結法を用いるには、hclust関数にオプション''method="single"''を指定します。
#geshi(rsplus){{
> d <- dist(iris[,1:4])
> hc <- hclust(d, method="single")
> plot(hc, labels=iris[,5], xlab="Euclidean")
}}
#ref(hc_euclidean_single.png,nolink,33%)

''群平均法'' (group ''average'' method) では、クラスター[math]C_1[/math]に含まれるデータとクラスター[math]C_2[/math]に含まれるデータの間の距離の平均を[math]C_1 C_2[/math]間の距離として最も近い（似ている）クラスターを結合します。
\[ d(C_1, C_2) = \frac{1}{|C_1||C_2|} \sum_{{\bf x}_1 \in C_1} \sum_{{\bf x_2} \in C_2} d({\bf x}_1 {\bf x}_2) \]
hclust関数にオプション''method="average"''と指定すると、群平均法による結合になります。
参考にしている『Rによるバイオインフォマティクスデータ解析』には、クラスターに含まれるデータの平均同士の距離をクラスター同士の距離としているように書かれていますが、この説明は間違っています。
#geshi(rsplus){{
> d <- dist(iris[,1:4])
> hc <- hclust(d, method="average")
> plot(hc, labels=iris[,5], xlab="Euclidean")
}}
#ref(hc_euclidean_average.png,nolink,33%)

''メジアン法'' (''median'' linkage method) では、クラスター[math]C_1[/math]に含まれるデータの中央値とクラスター[math]C_2[/math]に含まれるデータの中央値の間の距離を[math]C_1 C_2[/math]間の距離として、最も近い（似ている）クラスターを結合します。
メジアン法を用いるには、hclust関数にオプション''method="median"''を指定します。
#geshi(rsplus){{
> d <- dist(iris[,1:4])
> hc <- hclust(d, method="median")
> plot(hc, labels=iris[,5], xlab="Euclidean")
}}
#ref(hc_euclidean_median.png,nolink,33%)

''重心法'' (''centroid'' linkage method) では、クラスター[math]C_1[/math]の重心とクラスター[math]C_2[/math]の重心の間の距離を[math]C_1 C_2[/math]間の距離として、最も近い（似ている）クラスターを結合します。
\[ d(C_1, C_2) = d({\bf c}_1, {\bf c}_2) \]
\[ {\bf c}_{i} =  \frac{ \sum_{x \in C_i} x}{|C_i|} \]
重心法を用いるには、hclust関数にオプション''method="centroid"''を指定します。
#geshi(rsplus){{
> d <- dist(iris[,1:4])
> hc <- hclust(d, method="centroid")
> plot(hc, labels=iris[,5], xlab="Euclidean")
}}
#ref(hc_euclidean_centroid.png,nolink,33%)

''Ward''法では、クラスター[math]C_1, C_2[/math]を結合してクラスター[math]C_1 \cup C_2[/math]を作ったときに、各データとそれが含まれるクラスターの重心との距離の分散の増分を[math]C_1 C_2[/math]間の距離として、最も近い（似ている）クラスターを結合します。
\[ d(C_1, C_2) = {\mathrm E}(C_1 \cup C_2) - {\mathrm E}(C_1) - {\mathrm E}(C_2) \]
\[ {\mathrm E}(C_i) = \sum_{{\bf x} \in C_i} (d({\bf x}, {\bf c_i}))^2 \]
Ward法を用いるには、hclust関数にオプション''method="ward.D"''を指定します（新しい"ward.D2"という方法もあります）。
#geshi(rsplus){{
> d <- dist(iris[,1:4])
> hc <- hclust(d, method="ward.D")
> plot(hc, labels=iris[,5], xlab="Euclidean")
}}
#ref(hc_euclidean_ward.png,nolink,33%)



*距離行列 [#qc646c23]

''hclust''では、距離行列を自分で作成して階層クラスタリングを行うことができます。
距離行列は、（対角要素を除いた）下三角行列から''as.dist''を用いて作成します。

ここでは、例として、A, B, C, Dという4つのデータを含む距離行列を作成します。

まず、名前のベクトルを作成します。
#geshi(rsplus){{
> names = c("A", "B", "C", "D")
}}

つぎに、4次の正方行列を作成します。
#geshi(rsplus){{
> d = matrix(, 4, 4, dimnames=list(names, names))
> d
   A  B  C  D
A NA NA NA NA
B NA NA NA NA
C NA NA NA NA
D NA NA NA NA
}}

対角要素以外の下三角行列の要素に、各データ間の距離を代入します。
#geshi(rsplus){{
> d[2,1] = 1
> d[3,1] = 5
> d[4,1] = 6
> d[3,2] = 4
> d[4,2] = 5
> d[4,3] = 3
> d
   A  B  C  D
A NA NA NA NA
B  1 NA NA NA
C  5  4 NA NA
D  6  5  3 NA
}}


''as.dist''を用いてこの正方行列を距離行列に変換できることを確認します。
#geshi(sh){{
> as.dist(d)
  A B C
B 1    
C 5 4  
D 6 5 3
}}

この距離行列を''hclust''に引数として与えることで、階層クラスタリングができます。
#geshi(sh){{
> hc <- hclust(as.dist(d))
> plot(hc)
}}
#ref(hc_dist.png,nolink,33%)


*クラスター番号 [#c2378c88]

階層クラスタリングによってつけられたクラスター番号を調べるには、''cutree関数''を使います。
cutree関数には、hclust関数によって出力された結果とクラスター数を与えます。
#geshi(rsplus){{
> d <- dist(iris[,1:4])
> hc <- hclust(d, method="ward.D")
> cutree(hc, 3)
  [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 [26] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 [51] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 [76] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[101] 3 2 3 3 3 3 2 3 3 3 3 3 3 2 2 3 3 3 3 2 3 2 3 2 3
[126] 3 2 2 3 3 3 3 3 2 3 3 3 3 2 3 3 3 2 3 3 3 2 3 3 2
}}
これは、Ward法による階層クラスタリングの結果を、クラスター数を3として分けたときのクラスター番号です。


*まとめ [#xba66b81]
凝集型階層クラスタリングでは、最も近いクラスターを結合して新しいクラスターを作成することを繰り返すことによってクラスタリングを行います。

このとき、最も近い2つのクラスターを選び出すために、クラスター間の距離を測る必要があります。
クラスター間の距離尺度の違いにより、完全結合法、単結合法、群平均法、メジアン法、重心法、Ward法という方法に分かれます。
クラスター間の距離を測る方法を結合法といい、完全結合法、単結合法、群平均法、メジアン法、重心法、Ward法という方法があります。

また、クラスター間の距離尺度はデータ間の距離尺度に基づいているため、データ間の距離も測る必要があります。
データ間の距離尺度には、ユークリッド距離、マンハッタン距離、マハラノビス距離、コサイン係数などがあります。

したがって、凝集型階層クラスタリングでは、データ間の距離尺度とクラスター間の距離尺度の二つを選択することになります。
したがって、凝集型階層クラスタリングでは、データ間の距離尺度とクラスター間の距離尺度（結合法）の二つを選択することになります。


*演習 [#icb3dcfe]
irisデータに対して、自分で階層クラスタリングをやってみよう。



*参考文献 [#ubdf2be8]

#html{{
<iframe src="http://rcm-jp.amazon.co.jp/e/cm?t=tohgoroh-22&o=9&p=8&l=as1&asins=4320057082&ref=tf_til&fc1=444B4C&IS2=1&lt1=_blank&m=amazon&lc1=444B4C&bc1=FFFFFF&bg1=FFFFFF&f=ifr" style="width:120px;height:240px;" scrolling="no" marginwidth="0" marginheight="0" frameborder="0"></iframe>
<iframe src="http://rcm-jp.amazon.co.jp/e/cm?t=tohgoroh-22&o=9&p=8&l=as1&asins=4274067033&ref=qf_sp_asin_til&fc1=444B4C&IS2=1&lt1=_blank&m=amazon&lc1=444B4C&bc1=FFFFFF&bg1=FFFFFF&f=ifr" style="width:120px;height:240px;" scrolling="no" marginwidth="0" marginheight="0" frameborder="0"></iframe>
}}

-[[クラスタリングとは（クラスター分析とは）:http://www.kamishima.net/jp/clustering/]] - 神嶌敏弘さん
-[[類似度と距離:http://wikiwiki.jp/cattail/?%CE%E0%BB%F7%C5%D9%A4%C8%B5%F7%CE%A5]] - CatTail Wiki*