simudaru's blog

Python, Rなどのメモを残していこうと思います。  よろしくお願いいたします。

【R】e1071パッケージのbclust関数を試しました

Rのe1071パッケージ、bclustを試してみました。
K-meansなどの分割クラスタリング手法をbootstrapで繰り返し、
その結果を階層クラスタリングにより統合する、という手法です。
おなじみのirisデータで試してみました。

# bclustについて
# Bagged Clustering(K-meansなどの分割クラスタリング手法をbaseとして、
#                   baseをbootstrapで繰り返し、
#                   その結果をを階層クラスタリングにより統合する)
library(e1071)

if(0){'
bclust(x, centers=2, iter.base=10, minsize=0,
      dist.method="euclidian",
      hclust.method="average", base.method="kmeans",
      base.centers=20, verbose=TRUE,
      final.kmeans=FALSE, docmdscale=FALSE,
      resample=TRUE, weights=NULL, maxcluster=base.centers, ...)
      
      x:(必須)
      クラスタリングしたいデータ(Matrix)
      
      centers:(default 2)
      クラスタ数
      
      iter.base:(default 10)
      ベースクラスタリングアルゴリズムの実行回数
      
      minsize:(default 0)
      ベースクラスタリングでの、クラスタ内の最小要素数
      
      dist.method:(default "euclidian")
      階層クラスタリングでの距離の測り方
      "euclidean": ユークリッド距離
      "maximum": 上限ノルム(最大距離)
      "manhattan": マンハッタン距離
      "canberra": キャンベラ距離
      "binary": 0をoff, 1をon というバイナリとみなし、「両方onの数/少なくとも一方はoffの数」を距離とする
      "minkowski":ミンコフスキー距離、※pの与え方が不明
      
      hclust.method:(default "average")  
      階層クラスタリングでのアルゴリズム
      # 参考URL http://www.kamishima.net/archive/clustering.pdf
      # 参考URL http://www.mathworks.co.jp/jp/help/stats/linkage.html
      "ward.D": 内部平方距離 (最小分散アルゴリズム) ユークリッド距離にのみ適する
      (3.0.3までのwordに相当。実装に正しくない部分があった。)
      "ward.D2": 内部平方距離 (最小分散アルゴリズム) ユークリッド距離にのみ適する
      (実装を正しくしたもの)
      参考URL http://id.fnshr.info/2014/04/14/r3-1-0/
      "single": 最短距離
      "complete": 最長距離
      "average": 群平均法 (=UPGMA(非加重結合法))
      各クラスタの要素すべての間の距離の平均を、2クラスの距離とする
      "mcquitty": 重み付き群平均法(=WPGMA)
      "median": メディアン法(=WPGMC)
      "centroid": 重心までの距離(=UPGMC) ユークリッド距離にのみ適する
      
      base.method:(default "kmeans")
      分割クラスタリング手法の関数名を与える。
      
      base.centers:(default 20)
      baseのクラスタリングのクラスタ数
      
      verbose:(default TRUE)
      進捗状況を表示
      
      final.kmeans:(default FALSE)
      Trueにすると、最後のkmeansの初期値としてbagged clusteringの結果を用いる
      
      docmdscale:(default FALSE)
      TRUEにすると、主座標分析の結果も返す。
      
      resample:(default TRUE)	
      TRUEの場合、bootstrap sampleを使う。
      
      weights:(default NULL)
      bootstrapのリサンプリングの重み
      
      maxcluster:(default base.centers)
      クラスタの最大数
      '}

# データ準備
d <- iris

# bclsutの結果を確認する関数
CheckResultBclust <- function(obj, d, label, centers=3){
  # クラスタリング結果
  plot(obj);  Sys.sleep(5)
  print( table(clusters.bclust(obj, centers)) )
  
  # irisのSpeciesとの比較
  tmp <- table(d[,label], clusters.bclust(obj, centers));  print(addmargins(tmp))
  plot(d, col=clusters.bclust(obj ,centers));  Sys.sleep(5)
}

# bclust(クラスタリングしたいデータ(Matrix), クラスタ数)
bc1 <- bclust(d[, 1:4], 3)
CheckResultBclust(bc1, d, "Species")

bc2 <- bclust(d[, 1:4], 3, base.centers=3, iter.base=50)
CheckResultBclust(bc2, d, "Species")
CheckResultBclust(bc3, d, "Species", 4)

bc3 <- bclust(d[, 1:4], 3, base.centers=3, hclust.method="ward.D2")
CheckResultBclust(bc3, d, "Species")

# kmeans
km1 <- kmeans(d[, 1:4], 3)
tmp <- table(d[,5], km1$cluster);  print(addmargins(tmp))
plot(d, col=km1$cluster);  Sys.sleep(5)

bc2の結果を例に載せます。
オブジェクトをplotすると、以下のようなグラフが得られ、階層の様子が確認できます。
f:id:simudaru:20140601141304p:plain

Bagged Clusteringで得られた階層クラスタリングの結果を元に、3クラスタに分けた結果です。クラスタリングにはSpeciesは用いていませんが、大体Speciesと同じような分かれ方になっています。
f:id:simudaru:20140601141134p:plain

通常のK-meansでも同じような分かれ方をしており、irisデータだと手法による違いがわかりづらいですね。
f:id:simudaru:20140601141742p:plain


別のデータでも試してみました。

library(e1071)

# データ準備
n1 <- 300
x1 <- rnorm(n1, runif(n1, 0.2, 0.8), 0.1)
y1 <- rnorm(n1, 0.1, 0.1)
z1 <- rep(1, n1)

n2 <- 300
x2 <- rnorm(n2, runif(n2, 0.2, 0.8), 0.1)
y2 <- rnorm(n2, 0.9, 0.1)
z2 <- rep(2, n2)

n3 <- 50 
x3 <- rnorm(n3, 0.5, 0.03)
y3 <- rnorm(n3, 0.5, 0.03)
z3 <- rep(3, n3)

x <- c(x1, x2, x3)
y <- c(y1, y2, y3)
z <- c(z1, z2, z3)

d <- data.frame(x=x, y=y)

# 準備したデータを表示
plot(d, col=z)

# k-means
km1 <- kmeans(d, 3)
tmp <- table(z, km1$cluster);  print(addmargins(tmp))
plot(d, col=km1$cluster);  Sys.sleep(5)

# Bagged Clustering
bc1 <- bclust(d, 3, base.centers=3, iter.base=50)
tmp <- table(z, clusters.bclust(bc1, 3));  print(addmargins(tmp))
plot(d, col=clusters.bclust(bc1 ,3));  Sys.sleep(5)

今回は人工的にデータを作りました。
作ったデータを、作り方の違いで色をつけたのが下記グラフです。
f:id:simudaru:20140601142122p:plain
x軸方向に散らばり、y軸の水準が異なる黒と赤に加え、中央付近に緑が固まっています。

k-meansだと、何度か試してもきれいにわかれません。

こんなのとか
f:id:simudaru:20140601142604p:plain
こんなのとか
f:id:simudaru:20140601142612p:plain
こんなのとか
f:id:simudaru:20140601142620p:plain


それに対し、Bagged Clusteringを用いると、ベースクラスタリングアルゴリズムの実行回数を十分に取れば、このような小さくて明確に離れていないクラスタについても望むクラスタ結果が得られることと、クラスタ結果の頑健性の高さが確認できます。

こんな感じ
f:id:simudaru:20140601143101p:plain
2回目も。
f:id:simudaru:20140601143108p:plain
3回目も。
f:id:simudaru:20140601143118p:plain


ということで、それなりの規模のデータに対する実行時間は試せていないので気になりますが、クラスタリング性能は高そうです。