クラスタリング (lec2005_clustering)

Report
教師なしクラスタ分析
吉田 亮
東京大学医科学研究所
ヒトゲノム解析センター
DNA情報解析分野
[email protected]
http://bonsai.ims.u-tokyo.ac.jp/~yoshidar/index.htm
自己紹介
□ 専門分野: 統計科学(パターン認識,クラスタリング,
時系列解析,カーネル法)
□ 2004.9 博士(統計科学),総合研究大学院大学(統
計数理研究所,樋口知之教授)
2004.10~2005.3 統計数理研究所 特任研究員
2005.4~ 東京大学医科学研究所 特任助手
講義の趣旨
□ クラスタリングの様々な手法を直感的に理解
□ 確率モデルベースのクラスタリングについては
10/31 (月) 「混合分布」 講師: 樋口知之教授
□ 実装できること,結果解釈できることを目指す
講義の概要
□ 遺伝子発現解析におけるクラスタリングの役割
□ 標準的な手法について概観
○ 階層型クラスタリング
○ K-means法 (K-medoids)
○ 自己組織化マップ
□ Mixed Factors AnalysisとArrayClusterの紹介
データのかたまり(クラス
タ)を見つける
遺伝子1の発現量
□ クラスタリング
データのグループ構
造を理解するための
統計技法
□ クラスタを形成するサ
ンプル群は類似性が
高い集団
□ クラスタの個数は?
遺伝子2の発現量
遺伝子発現解析
2
3
3
2
2
3
2
2
3
3
3
2
2
3
2
2
2
2
2
2
2
2
3
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
2
2
1
1
2
1
1
1
1
1
1
1
3
2
2
2
2
2
白血病患者72症例
350遺伝子
各遺伝子の発現レベル(mRNAの合成量)
Golub et al. (1999) Science
http://www.broad.mit.edu/cancer/
□ 遺伝子のクラスタリング
サンプル数=遺伝子数
データベクトルの次元=アレイ数
□ マイクロアレイのクラスタリング
サンプル数=アレイ数
データベクトルの次元=遺伝子数
アレイ数<<遺伝子数 !
学習の形式
□ データの形式
属性( y) y1  1 y2  2 y3  1
ID
i 1 i  2 i  3
遺伝子1 x11
x12
x13
遺伝子2 x21
x22
x23
遺伝子3 x31
x32
x33




遺伝子d xd1
xd 2
xd 3
x1
x2
x3
□ サンプル i の発現パターン
 yn  3
 in
 x1n
 x2n
 x3n




  xdn
 
xn





xi  Rd , i  1,, n
□ サンプル i の属性ラベル
yi 1,2,, K or yi 1,1
□ 目的: 発現パターンと属
性ラベルの関係を知る.
yˆ x : Rd  1,2,, K 
データから学習
教師あり学習
遺伝子1の発現量
属性ラベル(教師)を利用して判
別境界(判別ルール)を作る
正常細胞
A癌細胞
B癌細胞
訓練データ
将来のデータ
(テストデータ)
遺伝子2の発現量
教師なし学習
遺伝子1の発現量
□ 属性ラベルの情報を利用せ
ずに,判別境界を作る.
○ サンプルの属性に関する情報が
全くない.
○ 一部分の属性ラベルが欠損
○ 敢えて利用しない(仮説の検証)
遺伝子2の発現量
遺伝子発現解析におけるクラ
スタ分析の役割
□ 細胞レベルの知見
□ 分子レベルでの分類
(例)疾病A
癌のサブクラスの同定 疾病A
サブクラスの存在仮説を検証
A1
A2
A2に属する患者の内
数パーセントは薬剤 I に対し
て副作用
A1
A2
A2a
A2b
サンプルの類似度
特徴ベクトルと類似度
特徴ベクトル
xi , x j  R
遺伝子B
Cluster
350
特徴空間
遺伝子A
Cluster
類似度
類似度を評価する尺度
をどのように定義するか
が重要
標準的な類似度(1/3)
u  u1,, ud 
v  v1,, vd 
□ 疑距離: Du,v  d u, v *距離の公理を満たす必要はない
(a) ユークリッド距離
dE u, v 
d
2


u

v
 i i
i 1
d
(b) City-Block 距離計量 dCB u, v   ui  vi
i 1
(c) 最大距離計量
dMDu, v  maxui  vi 
(d) ピアソンの相関係数
i
dc u, v 
d
 u  u v  v 
i 1
d
i
i
d
2




u

u
v

v
 i
 i
i 1
2
i 1
標準的な類似度(2/3)
遺伝子B
最大距離計量
City-Block 距離計量
遺伝子A
□ 重み付き距離
(例)City-Block距離計量
d
d u, v   wi ui  vi
i 1
wi  0 i,
d
w 1
i 1
i
遺伝子1の発現量
標準的な類似度(3/3)
グループ寄与率が高い
遺伝子2の発現量
□ グループに関連する遺伝子に高い重みをあたえる(特徴抽出)
□ 重みの決め方?
Friedman (2004) Clustering Objects on Subsets of attributes,
Journal of Royal Statistical Society B.
K-means法
K-means 法
□ 特徴空間上にn個のサンプル(個体)
□ K個のクラスタに分類
個体間の類似度
Du,v  d u, v
クタスタ3
centroid
クタスタ2
クタスタ1
centroid
centroid
アルゴリズム
Step 0. (初期化)n個の個体に適当なグループ付け.
Step 1. (中心の計算) K個のグループ平均を計算.
Step 2. (再グルーピング) データ点から最も近いグループを割り付ける.
Step 3. Step 1に戻る.
(1) 初期化+グループ平均
(2) 再グルーピング
(3) グループ平均
B遺伝子
B遺伝子
B遺伝子
A遺伝子
グループ1
グループ2
A遺伝子
A遺伝子
K-meansは何をしているか?
□ サンプルを表すインデックス i  1,, n
□ インデックス関数を求める Ci1,, K
□ グループ内距離の総和を最小化する学習方法
1 K
W C     d xi , x j 
2 k 1 i:Ci k j:C j k
B遺伝子
B遺伝子
グループ内距離の総和を
小さくするグルーピング
A遺伝子
A遺伝子
グループ数の決定
□ ナイーブな方法: Gap 統計量に基づく選択
K個に分類したとき
1 K
WK C      d xi , xj 
2 k 1 i:C i k j:C  j k
1 K 1
K+1個に分類したとき WK 1 C  2   d xi , xj 
k 1 i:C i k j:C j k
WK 1C WK C
B遺伝子
急激にグループ内距
離の総和が減少する
点を選択
A遺伝子
2
3
4
K
K-medoids
□ データ値が明示的に分からないが,類似度のみ既知
□ K-meansでは”中心”=“グループ平均”と定義
□ K-medoidsでは”中心”=“代表的サンプル”と定義
k-medoids
k-means
centroid
centroid
K-medoidsが有効な例
□ プロテイン間の相互作用 □ 遺伝子の配列情報
Gene1 ATCCGTAGTAGCCCTGAA
Gene2 TTCTCAAATATATGCGTCA
Gene3 ATTTTGCAGCCGGTTAAGT
□ カーネル法に基づき類似度を計算
(カーネル法については明日午前の講義)
ゲノム情報の多様性とカーネル法
フォーマットの多様性;
DNAマイクロアレイデータ 連続量
プロテインシーケンス 20-アルファベットの列
geneシーケンス 4-アルファベットの列
Protein-Protein Interactions
Lanckriet et al. (M. Jordan), 2004, A statistical framework for genomic
data fusion, Bioinformatics.
“In the near future, research in bioinformatics will focus more and more
heavily on methods of data fusion.”
(例) PPI+mRNA
PPI+mRNA+microRNA
mRNA+シーケンス
多様なデータフォーマットの統
合と遺伝子分類
(例) 遺伝子発現プロファイルと因果グラフの統合
Microarray Experiments
Pathways downloaded from
LIGAND database; S.Cerevisiae
アルゴリズム
Step 0. (初期化)n個の個体に適当なグループ付け.
Step 1. (中心の計算) K個の代表サンプル(中心)を探索.
ik*  arg min
i:C i k
d x , x 


i
C i ' k
i'
mk  xik* k
Step 2. (グルーピング) 各データを最も近い中心に割り付ける.
Ci   arg min d xi , mk 
k 1,, K
Step 3. Step 1に戻る.
K-meansについて


局所解の問題.数回初期値を更新してグループ
内総距離が最小になる解を選択.ただし,n<<d
の時は注意が必要(過学習).
ガウシアンミクスチュア(混合正規分布)に基づく
クラスタリングと密接な関係(31日の講義)
ClusterとTreeView (Eisen);
http://rana.lbl.gov/
Leukemia data (Golub et al., Science,
1999) 72 samples / 350 genes
階層型クラスタリング
□ 階層状のクラスタを形成
□ 樹形図(tree diagram)によるクラ
スタの視覚化
遺伝子発現解析で最も広範に使
われている手法
Michael B. Eisen, Paul T.
Spellman, Patrick O. Brown,
David Botstein:
Cluster analysis and display of
genome-wide expression
patterns
Proc. Natl. Acad. Sci. USA
95,(1998) pp. 14863–14868.
2 groups
3 groups
クラスタ間の類似度
□ K個のクラスタ(集合) C1,, CK
□ 個体間の類似度 Du,v  d u, v

□ クラスタ間の類似度 Dij  d Ci , C j

Cluster 2
Cluster 1
?
クラスタ間の類似度:
Single Linkage
□ 最も近い二つの個体間の類似度
d Ci , C j : min d xh , xk 
hCi ,kC j
Cluster 1
Cluster 2
クラスタ間の類似度:
Complete Linkage
□ 最も遠い二つの個体間の類似度
d Ci , C j : max d xh , xk 
hCi ,kC j
Cluster 2
Cluster 1
クラスタ間の類似度:
Centroid Linkage
Cluster 2
Cluster 1
クラスタ間の距離:
Average Linkage
□ 2クラスタに属する全個体の組合わせによって与
えられる平均類似度
1
d Ci , C j :
ni n j
  d x , x 
hCi kC j
h
k
Cluster 2
Cluster 1
アルゴリズム
Cut off
□各ノードの高さはグ
ループ 内距離の総和
に比例
1 K
W K      d xi , x j 
2 k 1 i:C i k j:C  j k
A
B
C
D
E
F
第1ステップ
第2ステップ
第3ステップ
E
B
D
A
第4ステップ
・
・.
・
C
G
F
G
ClusterとTreeView (Eisen);
http://rana.lbl.gov/
GUIイメージ
個体間の類似度を指定
クラスタ間の類似度を指定
樹形図による階層型クラスタリ
ングの視覚化
階層型クラスタリングの
実践的側面
□ データのグループ構造の視覚的理解
□ 入れ子状のクラスタを仮定
例.疾病のサブクラスが実際に入れ子になっている
場合, その有効性を発揮する.
25 AML
72症例
47 ALL
38 B-cell
9 T-cell
□ 類似度の設定によってクラスタリングの結果が大きく
異なる場合が多い.
□ クラスタ数の決定(ナイーブな方法)
自己組織化マップ(SOM)
□ 高次元空間上のデータの位相構造を2次元の
特徴空間に写像
□ Tamayo et al. Proc. Natl Acad. Sci. USA, 96,
2907-2912 (1999).
2次元特徴空間上
の格子点(4×3)
4
A
B
C
3
D
E
F
2
G
H
I
1
J
1
K
2
12個のノードをデータ空間に配
置 m j  Rd , j  1,,12
L
3
G
A
B
K
E
L
D
H
C
I
F
J
SOMの手順
SOM法は次のステップを数千回繰り返す.
G
A
B
K
For j=1 to N
E
L
D
(1)データ x を取り出す.
i
C
mk  mk   xi  m j ,
学習率:
  0,1
*学習率は1から始めて徐々に0に近づける.
例.線形オーダ
J
I
(2)データ点 xi と最も近いノード m j を探す.
例.ユークリッド距離
(3) m jの“近隣”にあるノードを次の式に従い
更新する.
H
F
4
A
B
C
3
D
E
F
2
G
H
I
1
J
K
L
1
2
3
自己組織化マップのイメージ
A
G
H
B
L
C
K
E
J
D
F
I
A
E D
C
G
B
L K
H
J F
I
4
A
B
C
3
D
E
F
2
G
H
I
1
J
K
L
1
2
3
□ 各ノードが1クラスタに対応
距離が最も小さいクラスタに割り
付ける.
□ 近隣サイズが0ならSOMはKmeansと同値
SOMの実装にあたって
□ Cluster3.0:http://www-genome.wi.mit.edu/cancer/
software/genecluster2/gc2.html
□ som(): Rのパッケージ,http://www.stat.uni-
muenchen.de/~strimmer/rexpress.html
参考文献:
□ Hastie et al., (2001) The Elements of Statistical Learning:
Data Mining, Inference, and Prediction, Springer-Verlag,
New York.
□ Ripley (1996) Pattern Recognition and Neural Networks,
Cambridge University Press.
Cluster3.0とJavaTreeView

Open Source
Clustering Software
http://bonsai.ims.utokyo.ac.jp/~mdehoon/softwar
e/cluster/software.htm#ctv
National Center for Biotechnology
Information (NCBI)が正式採用
De Hoon M. J., Imoto S., Nolan J., and
Miyano S. Open source clustering
software. Bioinformatics, Feb. (2004)
http://www.ncbi.nlm.nih.gov/geo/in
fo/cluster.html
ArrayCluster:遺伝子発現
解析におけるクラスタリング
ソフトウェア
吉田亮a, 樋口知之b, 井元清哉a, 宮野悟a
a 東京大学, 医科学研究所, ヒトゲノム解析センター
b 情報システム研究機構, 統計数理研究所
遺伝子発現解析にお
ける次元の呪い
N
マイクロアレイの個数 (N)
対象遺伝子の個数 (d)
N << d !
d
Nは医療体制,研究施設の諸
問題から数十から数百が限界
教師なし学習では遺伝子選択
(t-test, 生物学的知識)は現実
的ではない.
: Expression Level
Leukemia data, Golub et al. (1999)
主成分分析による次元圧縮
PCs sometimes fail to
reveal the presence of
clusters, since PCA only
takes into consideration
the second order
characteristics of data.
ALL
第一主成分
Cluster 1
射影の方向
Cluster 2
AML
AML→1
B-cell→2
T-cell→3
クラスターの消失
Rq
Mixed Factors Analysis
□ R.Yoshida, T.Higuchi and S.Imoto (2004), A Mixed Factors Model for
Dimension Reduction and Extraction of A Group Structure in Gene
Expression Data, Proc. IEEE 3rd Computational Systems Bioinformatics
(CSB2004: Refereed Coference), 161-172. * Full text of this paper is
available from CSB2004's website
http://conferences.computer.org/bioinformatics/CSB2004/Program4.htm
□ R.Yoshida, S.Imoto and T.Higuchi (2005), A Penalized Likelihood
Estimation on Transcriptional Module-based Clustering, Proc.1st
International Workshop on Data Mining and Bioinformatics (DMBIO
2005: Refereed Conference), Lecture Note in Computer Science vol.
3482, Springer-Verlag, 389-401.
□ 手法の数理的理解は樋口先生の「混合分布」の講義
Mixed Factors Model
d-dimensional observed data
(d-expression values)
“Mixed Factors”
(Latent variable)
Hierarchical Modeling
Class label vector of length G
d-observations
x1
Mixed Factors Model
……….
x2
Mixed Factors
f
Stage 1
Stage 2
Class Label
Stage 3
l
xd
学習アルゴリズムのイ
メージ
Step1. 次元圧縮
Rd
射影の方向
q-directions
Grouping
Step 2. 圧縮したデータに対
してクラスタリングを行う.
データ圧縮システムの
デザイン
グループ間総分散を最
大化するように射影の方
向を決める
射影の方向
PCAでは分散が最大
になるように射影の方
向を決定 !
射影の方向
Mixed Factors Analysis
Step 1. Determination of
(a) the number of clusters (G)
(b) the dimension of the mixed
factors (q)
Step 2. Dimension reduction of data: Posterior
expectation of the mixed factors
Step 3. Clustering : Bayes rule
Relevant Gene Profiling
Causal link between
and
Step 1.
Step 2. Select sets of genes as to give top L of the highest
positive and the negative correlation and list them
into,
k , k , k 1, , q
Set of genes having
positive correlation
Set of genes having
negative correlation
Application to Leukemia Data
Leukemia dataset, Golub
et al. 1999, Science
The normalized data matrix
is of order 1994×72.
Diagnostic categories
of 72 patients:
(a) AML cases (25)
(b) ALL B-cells (38)
(c) ALL T-cells (9)
Clustering
Relevant Gene Profiling
MFAでできること
□ マイクロアレイのクラスタリング
□ データの次元削減(グループ構造の視覚的理解)
□ クラスター数の決定(情報量規準)
□ 遺伝子のモジュール化
□ グループに関連する遺伝子群の同定
□ 欠損値の自動補間
ArrayCluster 1.0
Current version is now
available at our website.
Final version
Release from 1 September 2005 !
Search “ArrayCluster” by
Google.
‘ArrayCluster’
http://www.ism.ac.jp/~hig
uchi/arraycluster.htm
Software Description
□ The ArrayCluster is free software.
□ The current version is executable for Windows only.
□ The source codes are written by FORTRAN.
□ The ArrayCluster runs on Lunascape (Lunascape Co. Ltd.)
おわりに
□ K-means, 階層型クラスタリング,SOMについて概観
□ 詳細について
○ Hastie et al., (2001) The Elements of Statistical Learning:
Data Mining, Inference, and Prediction, Chapter 14, Springer-Verlag,
New York.
○Ripley (1996) Pattern Recognition and Neural Networks,
Cambridge University Press.
□ 確率モデルベースのクラスタリングについては
10/31 (月) 「混合分布」 講師: 樋口知之教授
□ Genomic Data Fusionに関しては
10/26 (水) 「教師ありクラスタ分析」 吉田 亮
Contact Info.
□ 今日の講義資料
http://bonsai.ims.u-tokyo.ac.jp/~yoshidar/lecture.htm
□ ArrayClusterのウェブサイト
http://www.ism.ac.jp/~higuchi/arraycluster.htm
□ R.Yoshida
[email protected]
http://bonsai.ims.u-tokyo.ac.jp/~yoshidar/index.htm

similar documents