1. No category

バイオプログラミング第２
慶應義塾大学理工学部
生命情報学科
榊原康文、佐藤健吾
クラスタリング Ø  データを似たもの同士に分ける
Ø  例. 空間上の点を距離が近いもの同士に分ける
Ø  クラスタ : 似たもの同士の集まり クラスタリング Ø  データを似たもの同士に分ける
Ø  例. 空間上の点を距離が近いもの同士に分ける
4 個のクラスタ Ø  クラスタ : 似たもの同士の集まり 生物における様々なクラスタ 蛍光タンパク 哺乳類 糖分解酵素 魚類 機能の類似したタンパク質 進化的に近縁な生物種 k-means クラスタリング Ø  空間上の点をクラスタリングする手法の 1 つ
Ø  あらかじめクラスタの個数を指定する (k 個)
Ø  クラスタリングの手順
1. 各点を k 個のクラスタのどれかへランダムに割り当てる
2. k 個のクラスタそれぞれについて中心点を求める
3. 各点について k 個のクラスタ中心点との距離を計算する。
各点を最も近い中心点のクラスタへ割り当て直す
4. 2. と 3. を繰り返す
5. クラスタの割り当てが変化しなくなったら終了する 具体例 Ø  まずはデータを散布図で眺めてみる
Ø  クラスタの個数を指定する (k = 4 が良さそう)
具体例 Ø  各点を 4 個のクラスタのどれかへランダムに割り当てる
(赤、紫、水、緑)
具体例 Ø  4 個のクラスタそれぞれについて中心点を求める
(◆ : クラスタ中心点)
具体例 Ø  各点について k 個のクラスタ中心点との距離を計算する。
各点を最も近い中心点のクラスタへ割り当て直す
具体例 Ø  クラスタの中心点を求める。各点をクラスタに割り当て直す
(2 回目)
具体例 Ø  クラスタの中心点を求める。各点をクラスタに割り当て直す
(3 回目)
具体例 Ø  クラスタの中心点を求める。各点をクラスタに割り当て直す
(4 回目)
具体例 Ø  クラスタの割り当てが変化しなくなったら終了する
(8 回目で終了した)
プログラムのヒント Ø  空間上の点を構造体で表現する
struct point {
double x, y; /* 2 次元空間の座標 */
int clust; /* 現時点でのクラスタの番号 */
};
Ø  構造体の配列を使って、複数の点を格納する
Ø  i 番目のクラスタ中心点の座標
(clust==i な点の座標の和) / (clust==i な点の個数)
Ø  点 p と点 q の距離
sqrt( (p.x － q.x)^2 + (p.y － q.y)^2 )
レポート課題 Ø  使用する点のデータ (200 個)
Ø  http://www.dna.bio.keio.ac.jp/lecture/progen2/data/kadai.points
Ø  1 行につき 1 個の点の座標が書かれている
1.39297476767153 -1.83731892533098
-11.9737970429392 9.80189535609729
0.633617920304605 -5.66327735378856
4.93843116171288 3.18323357449407
-1.89887681640184 11.1991822051262
...
x 座標 y 座標 Ø  これらの点を散布図で示し、クラスタの個数を決める
レポート課題 Ø  k-means クラスタリングを行う
Ø  途中経過を図で示す (このスライドの図を参考に)
Ø  各点をクラスタへランダムに割り当てた
Ø  クラスタの中心点を求めた
Ø  各点をクラスタへ割り当て直した
...
Ø  クラスタリングが終了した
Ø  今回の課題は、今週来週と 2 週間かけて行う