六本木で働くデータサイエンティストのブログ

元祖「銀座で働くデータサイエンティスト」です / 道玄坂→銀座→東京→六本木

パッケージユーザーのための機械学習(6):階層的クラスタリング

さて、教師あり学習の方はひと段落ついたので、今度は教師なし学習の話をやっていこうかと思います。と言っても僕が知っている範囲でなおかつ常用するような教師なし学習はRでの実装が割と貧弱なので、シリーズとしてはあまり面白くない感じになりそうです(笑)*1。一応、単なるプランですが


あたりを取り上げれば良いのかなと思ってます*2。教師あり学習5編との比較のために、相変わらずサンプルデータにXORパターンとか使おうかなとは考えてますが、もしかしたら面白くないからとかいう理由でサンプルデータは変えるかもしれませんので悪しからず。


今回は階層的クラスタリングからいってみましょう。あれですよ、ウォード法とか出てくるアレです。僕は実は怠慢なのであまり教師なし学習に関する書籍は持っていなくてですね*3、お薦めできる参考図書はこちらの2点に限りますということで。


はじめてのパターン認識

はじめてのパターン認識

Rによるデータサイエンス - データ解析の基礎から最新手法まで

Rによるデータサイエンス - データ解析の基礎から最新手法まで


ってかPRMLは全然階層的クラスタリング取り上げてないんですね。。。今読んでみて初めて知りました。あとデータが大量になると使えなくなる(≒「ビッグデータ*4時代には使いにくい)という問題点もあるので、今後はどんどん出番が限られるのかなぁという気も。


まずRでどんなものか見てみる


というわけで、まずは教師あり学習シリーズの時と同様にGitHubに置いてある以前のサンプルデータを使って階層的クラスタリングの挙動を見てみましょう。サンプルデータはdという名前にでもしておきましょう。

> d <- read.table("~/Dev/R/conflict_sample.txt", header=T, quote="\"")
> d2<-d[sample(3000,size=100,replace=F),-8]
# 多過ぎるので100個までsample関数を使ってダウンサンプリングする
# 教師ラベルは要らないので削除
> d2.dist<-dist(d2)
> d2.hcl<-hclust(d2.dist)
> plot(d2.hcl)

f:id:TJO:20140203161855p:plain


何を言ってるのか全く訳の分からないデンドログラムが出てきました(笑)。まぁ、これって本当は多変量の分類問題のデータなのでこんなもので無理やりやってもしょうがないんですけどね。


階層的クラスタリングとは何ぞや


一応、はじパタがものすごく親切な説明をしてくれているので、踏襲して説明してみましょう。端的に言えば階層的クラスタリングというのは「クラスタリングされていないN個のデータから、類似度の高い順に融合して次第に大きなクラスタを作り、最終的にはN個のデータを一つのクラスタに統合する手法」(p.157)です。そのアルゴリズムは以下の通り。

  1. n = Nとする
  2. n×nの距離行列を作る
  3. もっとも距離が近い二つのデータやクラスタをまとめて、一つのクラスタにする
  4. n = n-1にする
  5. n > 1であれば2へ、n = 1であれば終了する

これを何となく図示すると、

f:id:TJO:20140203181841p:plain:w300

↓↓↓

f:id:TJO:20140203181849p:plain

(wikipedia:en:Hierarchical_clustering)


こんな感じでデンドログラムを描く要領でクラスタごとに分けていくわけです。で、クラスタ間の類似度を定義する方法が色々あって、これはhclust(){stats}関数の引数として与えることで選ぶことができます。リストにしておくと、

引数 方法の名称
single 最近隣法
complete 最遠隣法
average 群平均法
centroid 重心法
median メディアン法
ward ウォード法
mcquitty McQuitty法


というラインナップになってます。どれを選ぶかはお好みで良いのですが、一応ウォード法が「クラスタ内変動の増加分で距離を定義しているので、階層法の中でもっとも精度が高い」(はじパタp.163)ということになっています。もちろん万全な方法と言うわけではないので、状況に応じて使い分ければ良いかと思います。


ちなみに類似度は既出の通りデータ間・クラスタ間の「距離」で判定するので、必ず最初にdist(){stats}関数で距離行列を求めてから、それをhclust()に投げることでクラスタリングさせるという流れを取るようになっています。その他細かいことははじパタpp.157-164を読んで下さい、ということで。


真の分布の分かっているデータをクラスタリングしてみる


そんなわけで実際にやってみましょう。これまで同様にGitHubからXORパターンのシンプルパターン複雑パターンのデータを取ってきて、クラスタリングしてみます。それぞれxors, xorcという名前でインポートしておきましょう。


今回は学習ラベルは使わないので、ラベルの列は削除しておきます。その代わり、それぞれのデータの真の分布に注目することにしましょう。これは以前も書いてますが、

# シンプルなXORパターン
> p11<-cbind(rnorm(n=25,mean=1,sd=0.5),rnorm(n=25,mean=1,sd=0.5))
> p12<-cbind(rnorm(n=25,mean=-1,sd=0.5),rnorm(n=25,mean=1,sd=0.5))
> p13<-cbind(rnorm(n=25,mean=-1,sd=0.5),rnorm(n=25,mean=-1,sd=0.5))
> p14<-cbind(rnorm(n=25,mean=1,sd=0.5),rnorm(n=25,mean=-1,sd=0.5))
> t<-as.factor(c(rep(0,50),rep(1,50)))
> xors<-as.data.frame(cbind(rbind(p11,p13,p12,p14),t))
> names(xors)<-c("x","y","label")

# 複雑なXORパターン
> p21<-cbind(rnorm(n=25,mean=1,sd=1),rnorm(n=25,mean=1,sd=1))
> p22<-cbind(rnorm(n=25,mean=-1,sd=1),rnorm(n=25,mean=1,sd=1))
> p23<-cbind(rnorm(n=25,mean=-1,sd=1),rnorm(n=25,mean=-1,sd=1))
> p24<-cbind(rnorm(n=25,mean=1,sd=1),rnorm(n=25,mean=-1,sd=1))
> t<-as.factor(c(rep(0,50),rep(1,50)))
> xorc<-as.data.frame(cbind(rbind(p21,p23,p22,p24),t))
> names(xorc)<-c("x","y","label")


ということで(1,1), (-1,1), (-1,-1), (1,-1)のそれぞれを中心とする標準偏差0.5ないし1.0の二次元正規分布が4つ配置されたデータであることがお分かりいただけるかと思います。それが分かったところで、実際にhclust()で階層的クラスタリングをやってみましょう。

> xors<-xors[,-3]
> xorc<-xorc[,-3]
# 教師ラベルを削除する
> xors.dist<-dist(xors)
> xorc.dist<-dist(xorc)
# 距離行列を出す。デフォルトなのでユークリッド距離
> xors.hcl<-hclust(xors.dist,method="ward")
> xorc.hcl<-hclust(xorc.dist,method="ward")
# とりあえずウォード法にしておく
> plot(xors.hcl)
> plot(xorc.hcl)
# デンドログラムをプロットする

f:id:TJO:20140203182930p:plain

シンプルパターンのデンドログラムと、

f:id:TJO:20140203182943p:plain

複雑パターンのデンドログラム。


デンドログラムだけを見た感じでは、シンプルパターンは割と綺麗に4つのクラスタに分類できてる気がするんですが、複雑パターンはちょっと違うかな?という気もしますね。階層も何だか変な気がするし。。。


そこで、cutree(){stats}関数を使って4クラスタに分かれたところで階層を打ち切り、クラスタ振り分けのインデックスを得るようにして、教師あり学習の時に分離超平面・決定境界を描いたのに倣ってそれっぽい分類結果の可視化をやってみましょう。

> c1<-cutree(xors.hcl,k=4)
> c2<-cutree(xorc.hcl,k=4)
# 推定した階層クラスタリングの結果を第一引数に、kに打ち切りたいクラスタ数を入れると、
# クラスタ振り分けのインデックスのベクトルが返される
> head(c1)
[1] 1 1 1 1 1 1
> head(c2)
[1] 1 1 1 2 1 1
> plot(xors,pch=19,col=c1,cex=3,xlim=c(-3,3),ylim=c(-3,3))
> plot(xorc,pch=19,col=c2,cex=3,xlim=c(-3,3),ylim=c(-3,3))
# col引数にクラスタのインデックスを与えて自動的に色を割り振る

f:id:TJO:20140203183755p:plain

シンプルパターンのプロットと、

f:id:TJO:20140203183804p:plain


複雑パターンのプロット。


見れば分かりますが、シンプルパターンは当然のように真の分布を反映するように分かれていますが、複雑パターンはとんでもない感じ(笑)。まぁまぁ、そんな厳密なものではないので仕方ないですね。


最後に


冒頭にも書きましたが、階層的クラスタリングは直観的に分かりやすい手法なんですがいかんせん大容量データに弱い*5ので、webデータ分析というか、いかにも機械学習でゴリゴリしたくなるような局面では使いにくいですね。。。ということで、案外アドホック分析系にこそ使い道があるのかな?とかぼんやり思ってます。

*1:物足りないと思う方は是非僕にRで実装されている範囲でもっと面白い手法を教えてください。。。

*2:混合ディリクレ過程はやり過ぎかもしれませんが

*3:つまり教師あり学習を使うケースの方が実務でも圧倒的に多いということ

*4:定義の存在しないものを引き合いに出してどうするんだと怒られそうですが(笑)、まぁ仮に1億レコードとかにしておきますかね

*5:4ケタ以上のレコード数になったらもう無理