教師なしクラスタ分析 吉田 亮 東京大学医科学研究所 ヒトゲノム解析センター 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 ) ID 遺伝子 1 遺伝子 2 遺伝子 3 y1 1 y2 2 i 1 i 2 x11 x12 x21 x22 x31 x32 □ サンプル i の発現パターン y3 1 i3 x13 x23 x33 yn 3 in x1n x2 n x3n 遺伝子 d xd 1 xd 2 xd 3 xdn x1 x2 x3 xn xi R d , i 1,, n □ サンプル i の属性ラベル yi 1,2,, K or yi 1,1 □ 目的: 発現パターンと属 性ラベルの関係を知る． yˆ x : R d 1,2,, K データから学習 教師あり学習 遺伝子1の発現量 属性ラベル（教師）を利用して判 別境界（判別ルール）を作る 正常細胞 A癌細胞 B癌細胞 訓練データ 将来のデータ （テストデータ） 遺伝子2の発現量 教師なし学習 遺伝子1の発現量 □ 属性ラベルの情報を利用せ ずに，判別境界を作る． ○ サンプルの属性に関する情報が 全くない. ○ 一部分の属性ラベルが欠損 ○ 敢えて利用しない（仮説の検証） 遺伝子2の発現量 遺伝子発現解析におけるクラ スタ分析の役割 □ 細胞レベルの知見 □ 分子レベルでの分類 （例)疾病A 癌のサブクラスの同定 疾病A サブクラスの存在仮説を検証 A1 A2 A2に属する患者の内 数パーセントは薬剤 Ｉ に対し て副作用 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) ユークリッド距離 d E u, v d 2 u v i i i 1 d (b) City-Block 距離計量 d CB u, v ui vi i 1 (c) 最大距離計量 d MD u, v max ui vi (d) ピアソンの相関係数 i d c u, v d u i 1 d i u vi v 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個のクラスタに分類 個体間の類似度 クタスタ3 Du,v d u, v 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 □ インデックス関数を求める Ci 1,, K □ グループ内距離の総和を最小化する学習方法 1 K W C 2 k 1 i:C i k d x , x j:C j k i j B遺伝子 B遺伝子 グループ内距離の総和を 小さくするグルーピング A遺伝子 A遺伝子 グループ数の決定 □ ナイーブな方法: Gap 統計量に基づく選択 K個に分類したとき 1 K WK C 2 k 1 i:C i k d x , x j:C j k 1 K 1 K+1個に分類したとき WK 1 C 2 k 1 i:C i k WK 1 C WK C i j d x , x j:C j k i j 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 C i ' k i i' mk xi* k k Step 2. (グルーピング) 各データを最も近い中心に割り付ける． C i arg min d xi , mk k 1,, K Step 3. Step 1に戻る． K-meansについて 局所解の問題．数回初期値を更新してグループ 内総距離が最小になる解を選択．ただし，n<<d の時は注意が必要（過学習）． ガウシアンミクスチュア（混合正規分布）に基づく クラスタリングと密接な関係（３１日の講義） 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 hCi , kC j Cluster 1 Cluster 2 クラスタ間の類似度： Complete Linkage □ 最も遠い二つの個体間の類似度 d Ci , C j : max d xh , xk hCi , kC 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 hCi kC j h k Cluster 2 Cluster 1 アルゴリズム Cut off □各ノードの高さはグ ループ 内距離の総和 に比例 1 K W K 2 k 1 i:C i k d x , x j:C j k i j A B C D E F 第1ステップ 第２ステップ 第３ステップ Ｅ B D A 第４ステップ ・ ・. ・ C G Ｆ G ClusterとTreeView (Eisen)； http://rana.lbl.gov/ GUIイメージ 個体間の類似度を指定 クラスタ間の類似度を指定 樹形図による階層型クラスタリ ングの視覚化 階層型クラスタリングの 実践的側面 □ データのグループ構造の視覚的理解 □ 入れ子状のクラスタを仮定 例．疾病のサブクラスが実際に入れ子になっている 場合, その有効性を発揮する． 25 AML 72症例 47 ALL 38 B-cell 9 T-cell □ 類似度の設定によってクラスタリングの結果が大きく 異なる場合が多い． □ クラスタ数の決定（ナイーブな方法） 自己組織化マップ（ＳＯＭ） □ 高次元空間上のデータの位相構造を２次元の 特徴空間に写像 □ Tamayo et al. Proc. Natl Acad. Sci. USA, 96, 2907-2912 (1999). ２次元特徴空間上 の格子点（４×３） ４ Ａ Ｂ Ｃ ３ Ｄ Ｅ Ｆ ２ Ｇ Ｈ Ｉ １ Ｊ １ Ｋ ２ １２個のノードをデータ空間に配 置 m j Rd , j 1,,12 Ｌ ３ Ｇ Ａ Ｂ Ｋ Ｅ Ｌ Ｄ Ｈ Ｃ Ｉ Ｆ Ｊ ＳＯＭの手順 ＳＯＭ法は次のステップを数千回繰り返す． Ｇ Ａ Ｂ Ｋ For j=1 to N Ｅ Ｌ Ｄ （１）データ x を取り出す． i Ｃ mk mk xi m j , 学習率： 0,1 ＊学習率は１から始めて徐々に０に近づける． 例．線形オーダ Ｊ Ｉ （２）データ点 x i と最も近いノード m j を探す． 例．ユークリッド距離 （３） m jの“近隣”にあるノードを次の式に従い 更新する． Ｈ Ｆ ４ Ａ Ｂ Ｃ ３ Ｄ Ｅ Ｆ ２ Ｇ Ｈ Ｉ １ Ｊ Ｋ Ｌ １ ２ ３ 自己組織化マップのイメージ Ａ Ｇ Ｈ Ｂ Ｌ Ｃ Ｋ Ｅ Ｊ Ｄ Ｆ Ｉ Ａ Ｅ Ｄ Ｃ Ｇ Ｂ Ｌ Ｋ Ｈ Ｊ Ｆ Ｉ ４ Ａ Ｂ Ｃ ３ Ｄ Ｅ Ｆ ２ Ｇ Ｈ Ｉ １ Ｊ Ｋ Ｌ １ ２ ３ □ 各ノードが１クラスタに対応 距離が最も小さいクラスタに割り 付ける． □ 近隣サイズが０ならSOMはＫmeansと同値 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, Set of genes having positive correlation , q 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
© Copyright 2024 ExpyDoc
