教師ありクラスタ分析（判別分析）

教師ありクラスタ分析
（判別分析）
吉田亮
東京大学医科学研究所
ヒトゲノム解析センター
DNA情報解析分野
[email protected]
http://bonsai.ims.u-tokyo.ac.jp/~yoshidar/index.htm
講義の概要
(1) 統計的判別分析の導入と数理的基礎
(2) 判別分析の標準的手法
□ 線形判別
□ 二次判別
□ ロジスティック判別
□ サポートベクターマシン (SVM)
(3) マイクロアレイ解析における実践的側面
最新のバイオインフォマティクス研究の動向
判別分析の目的
遺伝子1の発現量
入力空間
訓練データを使って判別境界
（判別ルール）を作る
正常細胞
A癌細胞
B癌細胞
訓練データ
将来のデータ
（テストデータ）
遺伝子2の発現量
マイクロアレイデータに基づく
ゲノム診断
□ サンプル i の発現パターン
□ データの形式
属性( 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




遺伝子 p x p1
xp2
x p3
x1
x2
x3
 yn  3
 in
 x1n
 x2n
 x3n




  x pn





 
xn
xi  R p , i  1,, n
□ サンプル i の属性
yi 1,2,, K or yi 1,1
(1) 訓練データを使って判別境界を構築
yˆ x : R p  1,2,, K 
(2) テストデータ(患者)の属性ラベル（e.g.
癌細胞 or 正常細胞）を判定
因果グラフに基づくゲノム情報の推論
Tsuda et al. (2004) Learning Kernels from Biological Networks by
Maximizing Entropy, Bioinformatics.
Category: 教師あり学習（判別）
□ Pathway Data: Vert et al. (2003)
Bioinformatis
LIGAND database
Chemical reaction
www.genome.ad.jp/ligand
755 proteins, 7860 edges
□ Pathway Data: S.cerevisiae PPI
Von Mering et al. (2002) Nature
2617 proteins, 11855 edges
Edgeは信頼度によってscoring (H,M,L)
Gold Standard: MIPS Comprehensive
Database (CYGD;
mips.gsf.de/genre/proj/yeast)
多様なデータフォーマットの統
合と遺伝子分類
（例）遺伝子発現プロファイルと因果グラフの統合
Microarray Experiments
Pathways downloaded from
LIGAND database; S.Cerevisiae
統計的決定理論
統計的学習の形式
□ データはある確率分布から生成されていると仮定
xi , yi  ~ px, y  px yp y (条件付確率の公式より)
  y 1
Pr y  2  y2 Pr y  K   yK 
１.属性ラベルの生成1. p y   Pr y  1
 

 
2.　p x y  p1 x y  1
２.発現ベクトルの生成
y 1
p2 x y  2
  y 2 
 pK x y  K 
  yK 
p1:正常細胞
p2:A癌細胞
P3: B癌細胞
ベイズルール
□ ベイズの定理から属性ラベルの事
後分布を導く
pyi  k xi  
pxi yi  k p yi  k 
 px
K
k 1
i
yi  k p yi  k 
, k
事象{ サンプル i の属性がk }
に対する確からしさを表す
□ ベイズルール（事後確率最大化）
yˆ xi   arg maxk log pyi  k xi 
事後確率に基づき入力空間を分割
統計的学習理論に基づくベイズ
ルールの導出
□任意の判別ルール
yˆ xの良さを評価する．
(1)　0 1損失関数を定義
0 if yx  yˆ x 正解
L yx, yˆ x : 
1 if yˆ x  yˆ x 不正解
(2) "平均的な" yˆ xの良さをベイズリスク
で評価
B yˆ  : EX ,Y L yx, yˆ x
K

 L yx, yˆ x px, yx  k  dx

 L yx, yˆ x pyx  k xpx dx
X
X
k 1
K
k 1
pyx  k xpx dx

   
  1  pyx  yˆ x x px dx

X
X
k: y x  yˆ x
(3) arg min yˆ B yˆ はベイズルール
結論: 0-1の損失関数に
よって判別ルールのリス
クを評価した場合，最も
誤判別率が低いのはベ
イズルール
条件付分布推定に対する幾つか
のアプローチ
□ “同時分布” px, y をパラメトリックモデル p x, y  で推定
（例）ガウシアンミクスチュア
□ “同時分布”ノンパラメトリック推定
□ “条件付分布”をモデリング p y x
(例) ニューラルネットワークス，ブースティング，
サポートベクターマシン, ロジスティック判別
 
ガウシアンミクスチュア
Gaussian Mixture
分離超平面と線形判別
x2
判別境界が線形
H
□ 分離平面Hは次式を満
たす入力xの集合
β x   0
T
d-1次元線形分離超平面


H  x β x   0
x1
T
ガウシアンミクスチュア
□ 正規分布（分散共分散行列は全グループ共通）
xi yi  k ~ N μk , Σ,
Pr yi  k    k ,
k  1,, K
k  1,, K
正規分布の確率密度関数
pxi yi  k  
 1

T 1




exp

x

μ
Σ
x

μ
k
k 

2 d / 2 Σ 1/ 2  2
1
□ 事後分布は
log pyi  k xi   log
 k xi ; μk , Σ
pxi 
 const.  log  k 
1
xi  μk T Σ1 xi  μk 
2
対数オッズ
□ 事後分布の対数比は0より大きいor小さい？
 pyi  k xi  

f xi  : log

 pyi  h xi  
 pxi yi  k  
 p yi  k  

  log
 log
 px y  h 
i i
 p yi  h 


 k  1
 log   μk  μh T Σ1 μk  μh   xT Σ1 μk  μh 
 h  2
xの線形関数で書ける
:   xT β
0
判別分析への手続き
(1) パラメータの最尤推定量を計算
□ 混合比率： ̂ k  nk n , k
1
xi , k
□ グループ平均： μˆ k 

nk i in classk
K
1
ˆ   xi  μˆ k xi  μˆ k T
□ 分散共分散行列： Σ
n k 1 i in classg
(2) 推定したパラメータに基づきベイズルールを適用
二次判別関数
x2
H 判別境界が二次関数
x1
ガウシアンミクスチュアと二次判別
□ 制約なしの正規分布を仮定
pxi yi  k  
 1

T 1




exp

x

μ
Σ
x

μ
k
i
k , k  1,, K
1/ 2
 2 i k
d /2

2  Σk
1
□ 属性ラベルの事後分布
  x ; μ , Σ 
log pyi  k xi   log k i k k
pxi 
1
1
 const.  log  k  log Σk  xi  μk T Σ1
k xi  μ k 
2
2
□ 分離超平面は２次


 p yi  k xi 

f xi  : log
判別境界は２次関数で書ける

 pyi  h xi  
  1
1
 log k   xi  μk T Σk1 xi  μk   xi  μh T Σh1 xi  μh   0
2
 h  2
ロジスティック判別
ロジスティック二値判別
□ 事後分布の対数比に対して線形モデリング
pyi  1xi  T
log
 β xi  
pyi  1xi 
□ 属性ラベルの条件付確率は？


exp   βT xi
pyi  1 xi  
1  exp   βT xi
pyi  1 xi  


1
1  exp   βT xi


ロジスティック判別とベイズルール
の関係 (1/2)
□　ベイズルール: yˆ x  k if k  arg max pyx  h x
h
□ 二値判別の問題　y  1,1
□ 部分クラスモデルに指
数分布族を仮定

px y  1  f xexpθ

x  θ 
px y  1  f xexp θT1x  θ1 
T
1
1
□ラベルの条件付確率
はベイズの定理より
px y  1p y  1
py  1 x 
px y  1p y  1  px y  1p y  1

1


1  exp θ1  θ1  x  θ1   θ1   log p y  1 p y  1
1

1  exp βT x  
py  1 x  1  y  1 x
T




exp βT x  

1  exp βT x  


ロジスティック判別とベイズルール
の関係 (2/2)
□ 部分クラスモデルが指数分布族なら，ベイズルー
ルによる判別関数は次のようにあたえられる．


p yi  1 xi
T
log
 β xi   (分離超平面は線形)
pyi  1 xi 
□ パラメータ
最尤推定)
  β,  は訓練データから学習 (c.f.
ロジスティック多値判別
□ 事後分布の対数オッズに対して線形モデルを仮定
 pyi  1 xi  
  1  β1T xi
log



p
y

K
x
i
i


 pyi  2 xi  
   2  βT2 xi
log

 pyi  K xi  

逆ロジット変換を施せばラ
ベルの条件付確率が計
算できる．
pyi  k xi  

exp k  βTk xi
K 1


1   exp l  βTl xi
 pyi  K 1 xi  
   K 1  βTK 1xi
log



p
y

K
x
pyi  K xi  
i
i


l 1

, k  1,, K 1
1
K 1

1  exp l  βTl xi
l 1

ロジスティック回帰のあてはめ
□ 対数尤度関数
n
K
i 1
k 1

L ,  :  log  p yi  k xi

 yi k 
   yi  k log pyi  k xi 
n
K
i 1 k 1
□ Newton-Raphson法 (重み付き最小二乗法)
β
new
β
  Lβ  Lβ

 
T 
 ββ  β
2
old
☆ Rの関数： glm()
1
サポートベクターマシン
サポートベクターマシン
□ 二値の判別問題を解くための学習機（判別関数）
□ 1990年代に発明 (Vapnik et al.)
□ 汎用性が高く，バイオインフォマティクスにおいて
様々な応用研究が行われている．
○ マイクロアレイデータの判別
○ 配列の分類
(a) DNA配列上の翻訳開始点の同定
(b) microRNAの予測
(c) プロモータ領域の予測
○ たんぱく質相互作用の解析
線形分離可能
xi , y 
d
,
x



R
, yi 1,1
i
□ 訓練データ
□ 学習機（線形モデル）
n
i i 1
f x  xT   
線形分離可能なHは無数に存在
*入力と出力の関係を学習
□ 判別ルール
Gx  sign xT   


□ 分離超平面（d-1次元）：
H  x f x  0
2つのクラスの識別面
マージン最大化
サポートベクター
ＳＶＭは2つのクラスの
”真ん中”を通る識別面
を探索する学習方法!
マージン（margin）
訓練サンプルと超平面の最小距離
点と平面の距離
(a) x1, x2  H ,  T x1  x2   0
(b) x0 ,  T x0  
(c) x  Rd とHの符号付距離は次のよ
うに与えられる．
1 T
 *T x  x0  
 x 




1
f x 
f x
x0
*
x
xT     0
学習の形式
□ 訓練サンプルと超平面の最小距離
min
H
xiT   

i 1,,n
ただし，パラメータに冗長性．
xT     0 ~ xT c  c  0
一意性を保つための制約
min xiT     1
i 1,,n
□ 訓練サンプルと超平面の最小距離は
1 
□ 最適化問題の定式化（線形分離可能なとき）
マージンの最大化 min

 ,

2

subject to yi xiT     1, i  1,, n
線形分離可能
1 
ソフトマージン:
線形分離不可能な場合
□ スラック変数を使って制約条件を変更


yi xiT     1 i , i  0,
i  1,, n
H
スラック変数
□ 最適化問題の定式化（線形分離不可能なとき）
n
1 2
min    i
 , , 2
i 1
subject to yi xiT      1  i , i  0 i  1,, n
  0 ：制約の強さを指定するパラメータ
*幾つかの候補を決めて，テストデータの誤判別率
を最小にするものを選ぶ
i
最適化（双対問題の導出）（1/2）
n
1 2
min    i
 , 2
i 1
subject to yi xiT     1  i ,
i  0, i  1,, n

□ 主問題のラグランジュアン
n
1 2
LP     i
2
i 1
n
 


i 1
LP
0

LP
0

LP
0
i

n
i 1
n
   i yi xi
i 1

n
0   i yi
i 1

□ Kuhn-Tucker-Karush条件

  i yi x     1  i   ii
T
i

 i  i , i

(1) i yi xiT     1  i   0, i
(2) ii  0, i
(3) yi xiT     1  i   0, i
最適化（双対問題の導出）（2/2）
凸二次計画問題:
標準的なソフトウェアやライブラリ関数を使える．
n
1 n n
max  i   i  j yi y j xiT x j
i ,i 1,,n
2 i 1 j 1
i 1
subject to 0  i   , i  1,, n
n
 y
i1
i i
0
双対定理やKKT条件について詳しく知りたい人は
Scholkopf et al., (2001)のChap.6もしくは
補助ノートNote_KKT_Yoshida (http://bonsai.ims.utokyo.ac.jp/~yoshidar/index.htm) を見て下さい．
最適化の手順
n
(Step1) ˆi , i  ˆ   ˆi yi xi
H
i 1
(Step2) ˆi    ˆi , i
if ˆi  0, ˆi  0

i  0, i  0
 
(Step3) ˆi  0, yi xiT ˆ    1  ˆi  0
 訓練サンプルiはサポートベクター
(ソフトマージン付き
)
i  0, i  0
カーネル法
・入力ベクトルから特徴ベクトルへの写像
T



x
 1 x,,s x
x   x F
・カーネル : 特徴空間におけるオブジェクトi, jの内積
k xi , x j :  xi , x j 
高次元特徴空間上でＳＶＭを実行（スパース化）
Mercer カーネル (1/2)
特徴空間での内積~対象の類似度
K ij  k xi , x j 
: xi , x j 
〈定義: 対称カーネル〉
k ( xi , x j )  k ( x j , xi ), i, j
〈定義:MercerKernel〉
カーネル行列Kは半正定値
c Kc   ci c j k xi , x j   0,
n
n
T
i 1 j 1
c  Rn
Mercer カーネル (2/2)
〈Mercerの定理〉
カーネル行列Kが半正定値(MercerKernel)
c Kc   ci c j k xi , x j   0,
n
n
T
c  Rn
i 1 j 1
 k xi , x j   xi , x j  を満たす写像 :   Fが存在する．
Kernel関数の設計
(a) 対象の類似性をうまく表現できるように設計
* 半正定値性
* データの事前知識を反映
(b) 写像の形式は明示的でなくてよい
(c) 写像を施すことでデータのフォーマットに依存しない学習
SVMのカーネル化
□ 判別関数 f x  xT   
□ 双対問題
1 n n
T


max  i   i  j yi y j  xi x j 
i ,i 1,,n
2 i 1 j 1
i 1
n
subject to 0  i   , i  1,, n,
n
 kx , x 
 y
i 1
i i
□ 重みに関する条件に基づき判別関数を変更
N
   i yi xi 
i 1
n
 f x  i yi k x, xi 
i 1
i
0
j
カーネルの例
□多項式カーネル


k x, y   c  x y
d  2, c  0の場合
T
d
k x, y   x1 y1  x2 y2 2

 x , x , 2x1x2
□ガウシアンカーネル
 
2
1
2
2
k x, x  exp  x  x'

'
2
 y , y ,
c 

T
2
1
2
2
2 y1 y2

SVMに関する参考文献
□ SVMの入門書
・ Hastie et al., (2001) The Elements of Statistical Learning: Data Mining, Inference, and
Prediction, Springer-Verlag, New York.
・麻生英樹，津田宏治，村田昇 (2003) パターン認識と学習の統計学, 岩波書店
□ 詳しく知りたい人
・ Vapnik et al., (1998) Statistical Learning Theory, Wiley, New York
・ Scholkopf et al., (2001) Learning With Kernels: Support Vector Machines, Regularization,
Optimization and Beyond (Adaptive Computation and Machine Learning Series)
□ 多値判別へのSVM の拡張と遺伝子発現パターンの判別への応用
・ Lee et al., (2004) Multicategory Support Vector Machines: Theory and Application to the
Classification of Microarray Data and Satellite Radiance Data , Journal of the American
Statistical Association, Vol. 99, No. 465, pp.67-81
□ ＤＮＡ配列の翻訳開始点の判別問題
・ Zien et al., (2000) Engineering support vector machine Kernels that recognize translation
initiation sites, Bioinformatics, Vol. 16, No. 8, pp. 799-807.
□ プロモータ領域の予測
・Ｇａｎｇａｌ et al., (2005) Human pol Ⅱ promoter prediction: time series descriptors and
machine learning, Nucleic Acids Res., 33: 1739.
カーネル法に関する情報（文献，ソフトウェアなど）
http://www.kernel-machines.org
バイオインフォマティクスにおける
カーネル法の事例
 因果グラフ（PPI: Protein-Protein Interaction）に
基づくゲノム情報の推論
→ Diffusion Kernel
 DNA配列上の翻訳開始点の同定
→ Locally Improved Kernel
 Genomic Data Fusion
因果グラフに基づくゲノム情報の推論
Tsuda et al. (2004) Learning Kernels from Biological Networks by
Maximizing Entropy, Bioinformatics.
Category: 教師あり学習（判別）
□ Pathway Data: Vert et al. (2003)
Bioinformatis
LIGAND database
Chemical reaction
www.genome.ad.jp/ligand
755 proteins, 7860 edges
□ Pathway Data: S.cerevisiae PPI
Von Mering et al. (2002) Nature
2617 proteins, 11855 edges
Edgeは信頼度によってscoring (H,M,L)
Gold Standard: MIPS Comprehensive
Database (CYGD;
mips.gsf.de/genre/proj/yeast)
Diffusion Kernelに関する文献
因果グラフとカーネル法
Kondor et al. (2002) Diffusion Kernels on Graphs and Other Discrete
Structures, Proceedings of ICLM 2002.
Kondor et al. (2004) Diffusion Kernels, in Kernel Methods in
Computational Biology, MIT press.
URL;http://www1.cs.columbia.edu/~risi/papers/papers.html
Diffusion on Graph
時点ｔにおいて各ノー
ドが保有するシグナル
量: vt   v1 t , v2 t ,, vn t T
1
4
2
シグナルの流入量
3
5
〈定義:フロー関数〉
シグナルの流出量
0
1
Avt   0
1
0
1
1
0
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1 v
0
1

2
0
Dvt   0
0
0
0
4
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
0v
0
3

t 
t 
隣接するノード数
Flowt    A  Dvt 
 Lvt ,
L : GraphLaplacian
熱拡散方程式系
d
vt   Lvt 
dt
〈 Proposition〉
s
 tL 
Matrix exponential　etL : lim I   は拡散方程式を満たす．
s
s

一般解はvt   eLt c0 .
n×n行列: Diffusion Kernel
Matrix　exponentialのマクローリン展開を
使えば自明
e
Lt

Lt 2 Lt 3
 I  Lt 


2!
3!
L2t 2  L3t 3  
d
e Lt  L 
dt
2!
3!
2
3






Lt
Lt
 L I  Lt 

 
2!
3!


Lt
 Le
Diffusionカーネルの正定値性
s
tL 
 tL 

(1) etL  lim I    lim  I  
s 
s  2s 2s 

(2) H  I  tL 2s は対称行列
n
2s
 H   iuiuiT , ここで iは実数
i 1
(3) any evenpower of H
H
n
2s
  i2suiuiT ,
i 1
i2s  0, i
 H 2sは半正定値
計算方法
(1) GraphLaplacianの固有値分解
s
n

T
L    iuiui    isuiuiT
 i 1
 i 1
2
n
n
n




t



tL
T
T
i
(2) e  I   tiuiui    
uiui      eti uiuiT
i 1
 i 1
  i 1 2

n
s
 
*Laplacianの直交化はO n3
翻訳開始点の予測
翻訳開始点
ATG
翻訳開始点ではない
ATG
翻訳開始点
ATG
ATG
翻訳開始点ではない
ATG
?
?
ATG
長さmの窓
多項式カーネル



k x, y    matchp x, y
 p1

m
d
SVM+多項式カーネル
誤判別率13.2%くらい
Locally Improved Kernel
x
y
?
ATG
ATG
ATG
長さmの窓
中心p
長さ l


winp x, y    wj matchp j x, y 
 j  l

l
x
y
重みwは減少
Locally Improved Kernelは


k x, y     winp x, y 
 pl 1

ml
d2
SVM+LIK
誤判別率11.9%くらい
d1
ゲノム情報の多様性とカーネル法
Formatの多様性;
DNAマイクロアレイデータ連続量，time course
プロテインシーケンス 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+シーケンス
Data Fusionとカーネル法
既存の統計的手法にプラグイン
Node1  ATCTGCTA
Node2  ATGC ATGC
K  a1Km RNA  a2 Kseq   aJ K graph
K  Rnn ;正定値
ai  0, i
主成分分析, 因子分析，フィッ
シャー線形判別, 正準相関分析，
サポートベクターマシン，K最近隣
法，線形回帰，ノンパラメトリック
回帰（その多くが既にカーネル法
の一種），ベイジアンネットワーク，
ロジスティック判別，K-medoids,
射影追跡法，有限混合分布に
もとづくクラスタリング, 階層型クラ
スタリング， ARモデル, ARMAX
モデル, 状態空間モデル，混合因
子分析
開発手法の性能評価 (1/3)
（Cross Validation）
(Step 1) チューニングパラメータの決定

例えば
Guassian kernelの
Diffusion kernelの
SVMの
(Step 2) 判別関数を推定
(Step 3) 判別関数の性能評価（比較）


t
KAST2005
開発手法の性能評価 (2/3)
（Cross Validation）
訓練データ
性能評価
………….. S(B)
S(1) S(2) S(3)
□ チューニングパラメータ  は C  予測性能
が最良になるように決定．


1 B 1
C     L yi , fˆ b xi 
B b1 nb iS b 
fˆ b x  : S b以外の訓練データで推定した判別関数
i
nb : S bのサンプル数
0 if yi  Gˆ xi 
ˆ
L yi , f xi   
ˆ
1 if yi  Gxi 


開発手法の性能評価 (3/3)
（Cross Validation）
□ ROC (Receiver Operating Characteristic) カーブ
+1
-1
+1
Correctly
specified
False Positive
(FP)
-1
False Negative
(FN)
Correctly
specified
# yi  1# FN
# yi  1
# yi  1# FP
Specificity 
# yi  1
Sencitivity
真 / 予測
Sensitivity 
Specificity
その他の判別分析の手法
□ K最近隣法
□ ニューラルネットワークス
・ C.M.Bishop (1995) Neural Networks for Pattern Recognition, Oxford Univ.Pr.
□ AdaBoost
・ Hastie et al., (2001) The Elements of Statistical Learning: Data Mining, Inference,
and Prediction, Springer-Verlag, New York.
・麻生英樹，津田宏治，村田昇 (2003) パターン認識と学習の統計学, 岩波書店
□ Kernel Linear Discriminant Analysis (KLDA)
・ Scholkopf et al., (2001) Learning With Kernels: Support Vector Machines,
Regularization, Optimization and Beyond (Adaptive Computation and Machine
Learning Series)
□ Kernelに基づくData Fusionと判別
・ Scholkopf et al., (2001) Kernel Method in Computational Biology (Computational
Molecular Biology)
Rによる実装
Keyword ‘CRAN’を検索
CRAN http://cran.r-project.org/
ソフトウェアや様々な判別
分析を実装するためのパッ
ケージが整備されている．
“Task View”→“Machine Learning”
□ SVM - svm()
□ Neural Networks - nnet()
□ AdaBoost - boost()
おわりに
□ マイクロアレイの判別では，遺伝子選択がとても重
要！第一日目の井元先生の講義を参考にして下さい．
□ 様々な手法を適用して，ROCで最も良い判別機を選
択すべき
□ 今日の講義資料は下記サイト(Lecture Note)からダウ
ンロードできます．
URL; http://bonsai.ims.u-tokyo.ac.jp/~yoshidar/index.htm

Download Report