Top 5 This Week

関連記事

階層的クラスター分析とk-means法

- 本サイト運営者のサービスの紹介 -

顧客の購買記録や植物の測定値のように、正解のラベルがないデータを似たものの群に分けたい場面があります。統計ソフトのメニューを開くと階層的クラスター分析とk-means法が並んでおり、この記事で使う150件のデータでも、両方の3群の分け方は一致しませんでした。

その場合に、どちらの結果を採るかは、群の数を前もって決められるか、データの件数がどれほどか、群がどんな形をしていると考えるかで決まります。

Fisherのirisデータで比べる2つの手法

比較には、datasetsパッケージのirisデータセットを使います。Fisher(1936)が判別の例に用いた3種のアヤメ各50本の萼片と花弁の長さと幅を測った150件で、種の名前は群を作る計算には使わず、出来上がった群と照らし合わせる目的だけに使います。

また、4つの測定値は単位が同じcmでも散らばりの大きさが異なり、標準化をしないとばらつきの大きい花弁の長さが距離の大部分を占めるため、平均0、標準偏差1に標準化してから距離を計算しました。この事情は、変数を要約する手法で相関行列を使うか共分散行列を使うかの判断と同じ構造で、主成分分析とは何か:多くの変数を要約するでも扱っています。

群の中心を動かすk-means法

k-means法は、群の数$k$を最初に決め、各点を最も近い中心の群に割り当てる操作と、群ごとに中心を平均へ置き直す操作を交互に繰り返します。この反復で小さくしようとしている量は次の群内平方和です。

$$W = \sum_{k=1}^{K} \sum_{i \in C_k} \lVert \mathbf{x}_i – \boldsymbol{\mu}_k \rVert^2 \tag{1}$$

ここで$C_k$は$k$番目の群に属する点の集合、$\mathbf{x}_i$は$i$番目の点の測定値ベクトル、$\boldsymbol{\mu}_k$は群$k$の中心です。式(1)は、各点から自分の群の中心までの距離の二乗を全部足し合わせた量で、この値が小さいほど群の内側がまとまっていると読みます。

この反復の基本形はLloyd(1982)が量子化の問題として定式化したもので、HartiganとWong(1979)は点を1件ずつ別の群へ移して$W$が減るかを調べる改良版を示しました。どちらの算法も$W$を減らす方向にしか動かないため、最初に置いた中心の位置によっては、全体の最小ではない局所解で止まります。

近い群から結合していく階層的クラスター分析

これに対して凝集型の階層的クラスター分析は、150件をそれぞれ1件だけの群として始め、最も近い2つの群を結合する操作を群が1つになるまで繰り返します。結合の履歴は樹形図(デンドログラム)として描かれ、縦軸の高さはその結合が起きた時の群間距離を表すため、どの高さで横に切るかによって2群にも3群にも分けられます。

ここで結果を大きく左右するのが、群と群の距離をどう測るかという連結法の選択です。最短距離法は2つの群の中で最も近い2点の距離、最長距離法は最も遠い2点の距離、群平均法はあらゆる点の組の距離の平均を使い、Ward法は結合によって群内の平方和がどれだけ増えるかを基準にします。

そのWard法について、Ward(1963)は群Aと群Bを結合した時の群内平方和の増加を次の量として扱いました。

$$\Delta(A, B) = \frac{n_A n_B}{n_A + n_B}\,\lVert \bar{\mathbf{x}}_A – \bar{\mathbf{x}}_B \rVert^2 \tag{2}$$

ここで$n_A$と$n_B$は2つの群の件数、$\bar{\mathbf{x}}_A$と$\bar{\mathbf{x}}_B$は各群の平均ベクトルです。式(2)は、2つの中心が離れているほど、また両方の群が大きいほど結合の代償が大きくなることを表しており、Ward法は代償の最も小さい組から順に結合していきます。

もっとも、MurtaghとLegendre(2014)は、Ward法を名乗る実装の中に距離を二乗せずに入力するものがあり、式(2)の基準を満たすかどうかが実装によって異なると指摘しており、Rの階層的クラスター分析では、2種類あるWard法の指定のうち距離を二乗して扱う方が式(2)に対応します。

連結法4種類で群の分かれ方が変わる

実際に4つの連結法で樹形図を作り、3群で切った結果を種と照らし合わせると、連結法ごとに群の大きさが大きく異なりました。一致割合は、各群を最も多く含まれる種に割り当てた時に正しく割り当たる割合で、最短距離法0.667、最長距離法0.787、群平均法0.687、Ward法0.827でした。

# 4つの測定値を標準化して距離を計算する
measures <- scale(iris[, 1:4])
species <- iris$Species
dist_iris <- dist(measures)
match_rate <- function(tab) sum(apply(tab, 1, max)) / sum(tab)
for (method in c("single", "complete", "average", "ward.D2")) {
  fit <- hclust(dist_iris, method = method)
  tab <- table(cluster = cutree(fit, k = 3), species = species)
  print(tab)
  cat(method, "match:", round(match_rate(tab), 3),
      "cophenetic:", round(cor(dist_iris, cophenetic(fit)), 2), "\n")
}
#>        species
#> cluster setosa versicolor virginica
#>       1     49          0         0
#>       2      1          0         0
#>       3      0         50        50
#> single match: 0.667 cophenetic: 0.83
#>        species
#> cluster setosa versicolor virginica
#>       1     49          0         0
#>       2      1         21         2
#>       3      0         29        48
#> complete match: 0.787 cophenetic: 0.75
#>        species
#> cluster setosa versicolor virginica
#>       1     50          0         0
#>       2      0         50        47
#>       3      0          0         3
#> average match: 0.687 cophenetic: 0.85
#>        species
#> cluster setosa versicolor virginica
#>       1     49          0         0
#>       2      1         27         2
#>       3      0         23        48
#> ward.D2 match: 0.827 cophenetic: 0.82

この差の中身を表で見ると、最短距離法は49件、1件、100件という群を作り、versicolorとvirginicaの100件を1つの群にまとめていました。最短距離法では1組の点が近いだけで群が結合されるため、点が鎖のようにつながって細長い群が育ちやすく、Ward法は群内平方和の増加を抑えるため、まとまりの良い丸い群を作りやすい傾向があり、このデータでは49件、30件、71件の群になりました。

一方、最長距離法はsetosaの49件の群のほかに、setosa 1件、versicolor 21件、virginica 2件からなる24件の群と、versicolor 29件、virginica 48件からなる77件の群を作りました。群内の最も遠い2点の距離で結合を判断するため群の広がりは抑えられますが、このデータではversicolorが21件と29件に割れ、2つの群にまたがっています。

群の大きさとは別の指標として、樹形図がもとの距離をどれだけ保っているかを測るコーフェン相関係数は、SokalとRohlf(1962)が樹形図の比較のために導入した量で、2点が樹形図上で初めて同じ群になる高さと、もとの距離との相関を計算します。今回は最短距離法0.83、最長距離法0.75、群平均法0.85、Ward法0.82でした。

ここで群平均法の結果を見ると、setosaの50件のほかに97件と3件という群を作っており、コーフェン相関係数が最も高いのに一致割合は0.687にとどまりました。樹形図が距離をよく保つことと、3群で切った時に種に近い群が得られることは、このデータでは別の性質として現れています。

なお、種のラベルを正解とする一致割合は、このデータで種が群として分かれているという前提に立った指標なので、ラベルのない実データでは使えません。そうした場面では、Ward法の3群に枠を重ねた図1のような樹形図で、結合の高さの差から群の数を検討します。

ward_fit <- hclust(dist_iris, method = "ward.D2")
plot(ward_fit, labels = FALSE, hang = -1, main = "Ward linkage on standardized iris",
     xlab = "", sub = "", ylab = "Merge height")
rect.hclust(ward_fit, k = 3, border = c("#D55E00", "#0072B2", "#009E73"))
標準化したirisデータにWard法を当てはめた樹形図で、3群で切った位置に3色の枠が描かれ、左側の49件の群が他の2群から高い位置で分かれています
図1 Ward法の樹形図と3群の枠です。49件の群は高い位置で他から分かれ、残る2群は低い位置で結合しています。

図1では、49件の群と残り101件が最も高い位置で分かれ、30件と71件の群はそれより低い位置で結合しています。2群で切るか3群で切るかの判断は、この結合の高さの差を見て行うことになり、群の数を後から選べるという階層的クラスター分析の性質が図の上で確認できます。

初期値によって止まる場所が変わるk-means法

次にk-means法を$k=3$で、初期値を1組だけ置く設定のまま乱数の種を1から10まで変えて10回実行しました。群内平方和は最小値138.89、最大値189.75で、10回のうち9回は138.89に到達し、1回だけ189.75で止まっていました。

wss_single <- sapply(1:10, function(seed) {
  set.seed(seed)
  kmeans(measures, centers = 3, nstart = 1)$tot.withinss
})
table(round(wss_single, 2))
set.seed(42)
km25 <- kmeans(measures, centers = 3, nstart = 25)
round(km25$tot.withinss, 2)
table(cluster = km25$cluster, species = species)
# Ward法の3群の中心を初期値にする
ward_groups <- cutree(ward_fit, k = 3)
ward_centers <- apply(measures, 2, function(col) tapply(col, ward_groups, mean))
round(kmeans(measures, centers = ward_centers)$tot.withinss, 2)
#> 
#> 138.89 189.75 
#>      9      1 
#> [1] 138.89
#>        species
#> cluster setosa versicolor virginica
#>       1     50          0         0
#>       2      0         39        14
#>       3      0         11        36
#> [1] 138.89

この189.75の解は、反復がそれ以上$W$を下げられない状態に入っただけで、群の分け方としては劣っています。初期値を25組置き、そのうち$W$が最も小さい解を採る設定にすると群内平方和は138.89となり、10回の中の最小値と同じ値でした。

もっとも、25組の結果が10回の最小値と一致したことは、138.89が全体の最小値だと確かめた結果ではありません。このデータで、複数の出発位置から同じ解に集まったという観察にとどまります。

その138.89の解を種と照らし合わせると、setosaの50件は1つの群にまとまり、残り100件は53件と47件の群に分かれ、versicolorは39件と11件、virginicaは14件と36件に割れて、一致割合は(50+39+36)/150=0.833でした。この割れ方を確かめるため、花弁の長さと幅の散布図にk-means法の群を色、種を点の形で描き分けたのが図2です。

plot(iris$Petal.Length, iris$Petal.Width, col = c("#D55E00", "#0072B2", "#009E73")[km25$cluster],
     pch = c(16, 17, 15)[species], xlab = "Petal length (cm)", ylab = "Petal width (cm)",
     xlim = c(1, 7), ylim = c(0, 2.8))
legend("topleft", legend = levels(species), pch = c(16, 17, 15), bty = "n", cex = 0.8)
花弁の長さと幅の散布図で、k-means法の3群を色、3種を点の形で描き分けており、左下のsetosaは1色にまとまり、右上ではversicolorとvirginicaが2色に混ざっています
図2 花弁の長さと幅の散布図です。色がk-means法の群、点の形が種を表し、右上の2種が接する部分で色と形が一致しない点が集まっています。

図2では、setosaが左下に離れて1色にまとまり、versicolorとvirginicaの接する花弁の長さ5cm前後で色と形の対応が崩れています。今回は25組の初期値でもWard法の中心から始めても同じ138.89の解に収まり、この重なり部分の点は種と異なる群に入っていました。

群の数・計算量・再現性で見た2つの手法の違い

ここまでの結果を、手法を選ぶ時に効いてくる観点で並べると次の表になります。

観点 階層的クラスター分析 k-means法
群の数 後から樹形図の切る高さで決める 実行前に$k$を決める
入れ子の構造 2群、3群、4群の関係が樹形図で得られる $k$ごとに別々の解で、入れ子にならない
大きなデータでの計算量 あらゆる組の距離を保持するため、件数の2乗で記憶量が増える 1回の反復が件数に比例するため、大きなデータでも扱える
群の形の想定 連結法によって異なり、最短距離法は細長い群も作る 中心からの二乗距離を使うため、球状で大きさの近い群を想定する
結果の再現性 同じ距離と連結法なら同じ樹形図になる 初期値によって局所解が変わる

群の数の見当がつかない段階では、樹形図の高さの変化を見ながら切る位置を検討できる階層的クラスター分析の方が扱いやすく、件数が増えると距離行列の要素数が件数の2乗に比例して増える(150件で11,175組)ため、k-means法を選ぶ理由が生まれます。この表の中で判断の中心になるのは、群の数を先に決める必要があるかどうかと、件数の規模です。

この2つを組み合わせる進め方もあります。Ward法の3群の中心をk-means法の初期値にすると群内平方和は138.89となり、初期値を25組置いた場合と同じ値に到達したため、階層的クラスター分析で群の数と中心のおおまかな位置を決め、k-means法で各点の所属を調整する分担が成り立ちます。

論文や報告書でのクラスター分析の扱い

Ward(1963)が群分けを目的関数の最適化として定式化した時の目的関数は式(1)と同じ群内平方和で、Ward法とk-means法は同じ量を、結合のたびに増加分を最小にする貪欲な手順と、$k$を固定した反復改善という別々の方法で小さくしています。同じ目的関数を共有する手法が複数の算法で実装されているため、報告ではどの算法を使ったかを明記する必要が生じます。

この関係に沿って、結果を報告する時に書き残すべき情報も見えてきます。階層的クラスター分析では、変数の標準化の有無、距離の種類、連結法、そしてWard法なら実装がどちらの基準に従うかを、MurtaghとLegendre(2014)の整理に沿って明記する必要があり、k-means法では$k$の値と選んだ理由、初期値の組数、HartiganとWong(1979)とLloyd(1982)のどちらの算法かを記載します。

手法を選ぶ時の判断

距離行列を保持できる規模のデータで群の構造を見たい場合は、変数を標準化したうえでWard法または群平均法の階層的クラスター分析を行い、連結法を変えて群の大きさと樹形図を比べる進め方を推奨します。今回のirisデータでも連結法によって一致割合が0.667から0.827まで動いたため、1つの連結法の結果だけを報告すると、その分け方が手法の選択に依存していることが読者に伝わりません。

反対に、件数が多く距離行列を保持できないデータでは、初期値を多数置いたk-means法を使います。今回の10回の実行で1回が189.75で止まり、最短距離法が100件を1つの群にまとめたように、初期値1組だけのk-means法や最短距離法は設定次第で群の分け方が大きく変わるため、まとまった群を探す目的でこの2つの設定を使うのは避けます。

参考文献

  1. Fisher RA. The use of multiple measurements in taxonomic problems. Annals of Eugenics. 1936;7(2):179-188.
  2. Ward JH Jr. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association. 1963;58(301):236-244.
  3. Sokal RR, Rohlf FJ. The comparison of dendrograms by objective methods. Taxon. 1962;11(2):33-40.
  4. Hartigan JA, Wong MA. Algorithm AS 136: A K-means clustering algorithm. Journal of the Royal Statistical Society Series C (Applied Statistics). 1979;28(1):100-108.
  5. Lloyd SP. Least squares quantization in PCM. IEEE Transactions on Information Theory. 1982;28(2):129-137.
  6. Murtagh F, Legendre P. Ward’s hierarchical agglomerative clustering method: which algorithms implement Ward’s criterion? Journal of Classification. 2014;31(3):274-295.

Popular Articles