クラスター数決定法の比較 志津綾香

指導教員：松田眞一

 最長距離法

はじめに最長距離法とは、各クラスター間の距離における最長
多くの統計解析の調査研究では、類似度の評価を頼り距離を、クラスター間の距離とする方法である。この方に様々な分析を行う。その中でもクラスター分析は、類似度を評価するための基本的な方法であり、誰でも行うこ 法は、 つのクラスターが極端に大きくなるのを抑えらとができる数量的方法である。しかしクラスター分析は、 れ、大きさのそろったクラスターを得ることができる。
解析者自身で適当なクラスター数を決定するため、その ウォード法
判断基準が曖昧である。そこで本研究では、クラスターウォード法は、クラスターとしてサンプルをまとめる数自動決定法の有用性や、各計算方法での特徴を調べ、比ときに生じる、各サンプルの情報の損失量の増加分をク較、評価を与えることを本研究の目的とする。
ラスターの距離とする方法である。すべてのクラスター
 クラスター分析
内の偏差平方和の和を出来るだけ小さくするように組みクラスター分析は、 つ以上のデータがあるとき、類似 合わせていくので、比較的まとまりのあるクラスターが度や距離 非類似度 を手がかりに、データをいくつかの いくつか得られる。



グループに分類させる方法である。まず、クラスター分析  非階層型クラスタリング手法には階層的方法と非階層的方法の つの計算方法がある。
非階層的手法は、あらかじめいくつのクラスター数にす
階層的方法の分類方法には、距離を基準に使うサンプるかを決めておき、その数に従ってサンプルを振り分けルクラスターと相関係数 類似度 を基準に使う変数クラていく方法である。出来るだけクラスター間の距離は大スターがある。階層的手法で主に用いられる方法に、最きく、各クラスターのサンプル間の距離は小さくなるよ
短距離法、最長距離法、群平均法、重心法、メジアン法、うにサンプルを振り分けていく方法であるので、サンプウォード法とよばれるものがあり、これらは距離を基準ル間に包含関係がないことが多い。非階層的手法は、計算に用い、その定義の仕方によってクラスター生成法が違量が膨大な為、処理時間が長くなるのが欠点である。
（神う。距離の指標の種類には、ユークリッド距離やマハラ嶌菅渡辺他 ）ノビス距離等がある。階層的クラスタリング手法は、一般的にはユークリッド距離が使用される。つまり一般的  法に階層的方法は距離とクラスター生成法の組み合わせで法は、あらかじめクラスター数を決めておき、方法が決定する。
各サンプルを分けていく方法である。クラスターに含ままた非階層的方法には、法、超体積法と呼ばれる各サンプルとそのクラスターの重心の距離が、他のれるものがある。非階層的手法の場合、ある評価関数をどのクラスターの重心よりも小さくなるように求める。
基準にクラスターを生成する。（菅渡辺他参照）
 超体積法  

 

 階層型クラスタリング手法



階層型手法は、最初に各サンプルを つのクラスターとして、最も近いサンプルから順に合併させ、新たなクラスターを形成していく方法である。結果は樹形図で表示させることができ、似ているものから順に並べられている。そしてクラスター数は、その樹形図を見て決定させる。クラスター分析において、クラスター間の距離の定義が重要になってくる。（神嶌参照 菅渡辺他 ） 



点集合を凸多面体の集まりとみなし、その体積を最少にすることで、最適な分割をみつけていく非階層的手法である。それ自体がクラスター数決定法としても使われる。

 クラスター数自動決定法
ここでは、本研究でクラスター数自動決定法の精度を比較、評価するために、シミュレーションを行う方法を紹介する。

 最短距離法  最短距離法とは、各クラスター間の距離における最短距離を、クラスター間の距離とする方法である。この方法は、小さいクラスターを徐々に集めていくもので、データをいくつかのクラスター数に分けるというよりは、主流となるクラスターを発見するのに役立つ方法である。また、異常値の発見も可能である。

参照 が提案した以下の基準値を使う方法である。（以下では、法と略す。）

  のクラスター数決定法     ! " ここで

# "  $      "    

分布に従うよう求めているが、カイ 乗分布に従うように計算する。一般的に多変量正規分布に従う 点間の距離の分布はカイ 乗分布に従う事が分かっているからである。
具体的な計算方法は、以下のように を正規化しである。
このとき、 はクラスタ の平均ベクトルで、 はク 
ラスタ とクラスタ の平均距離、 はクラスタ 内の 番目のベクトルで、 はクラスタ 内のベクトルの個数を表している。  の値を、ある範囲内で一番小さ   
くなるようにとる  が、最も最適なクラスター数となる。
ある範囲内とは、この場合、スタージェスの公式を用い それに前節の法を用いている。ここで  はることにした。つまり、
  である。
正規分布の逆関数であり、 は自由度 のカイ二乗分布  $  #本研究では石岡によって改良された法を用いる。
法は、法の拡張である。あらかじめクラスター数を決めておかなければならない法とは違い、最適なクラスター数を推測することができる。
法の考え方は、で再帰的に法を実行していくというもので、クラスタの分割前と分割後で値 ベイズ情報量基準 を比較し、値が改善しなくなるまで分割を続ける。つまり、分割前のベイズ情報量を、分割後のベイズ情報量をとし、# 0の分布関数である。

法

"0  -.. / + 

 その他
その他にも超体積法の判断基準を用い、凸包を拡張することで最適解を推測する凸集合の推測に基づく方法や、尤度比を用いたクラスター数決定法、移動平均品質管理規則、マリオットのテスト、ウォルフのテスト等がある。
参照

#
"
1 /2  %&'  プログラム%&'%&'(
 法は上記の数式を基に、階層的手法の場合と非階層
 %&' %&' ならば  分割する的手法の場合のプログラムを作成した。階層的手法の場合は最長距離法、ウォード法を用いる。非階層的手法の
 %&' %&' ならば  分割しない法を用いる。データを指定し、階層的手を全ての場合で  分割出来なくなるまで繰り返すことに 場合は 法の場合は距離の定義をする。出力結果はデータ、
 の範より最適なクラスター数を決定する。
囲内における   の値、最適なクラスター数  の値、そ詳しいアルゴリズムはここでは省略する。
れに対応する最適な   の値、求められたクラスター数   法
 の場合の各変数の群分け、を表示させるようにした。
* によって提案され、階層的方法 # 法については、石岡  の、既に実装されていこの方法は )における重要なクラスター数決定法である。以下、+  るプログラムを用い、 法と同様の結果を表示させる。
+  法も  法と同様の結果を出すプログラムを作成法と略す。統計的な停止規則を用いてクラスター数を求める。その方法は、大きさ  の標本に対してクラスター した。+  法は階層的手法にのみ適用可能なので、最長を生成するための基準値 が    個あるのを利用する。 距離法とウォード法の  方法のみを用いる。また今回はここでは基準に距離のみを考えるのですべてが一つにな +  法を元に、停止規則を計算をする時のデータがカイる距離  から初めて降順に  までの基準値がある。  乗分布に従う場合を提案したので +  法では従来の正この の分布の平均と標準偏差を計算することによって、 規分布に従っているときの  方法の場合とカイ  乗分布有意な を導くことでクラスター数を決定する方法であ に従っている場合の  方法、計  パターンで作成した。
る。停止規則は、 "  から始めて条件 シミュレーションとその結果,$ 
シミュレーションでは、図 〜 の大きく分けて  パターを満たすまで を増加させることである。停止した が ンのデータ使用する。 次元の乱数を用意し、各乱数の最適なクラスター数となる。, と  はそれぞれ の分布 平均を正三角形、直線、十字型となるように置いたものの平均と不偏分散の平方根をとったものである。この方 を、データとして使用する。乱数は、正規分布、 分布、法は最短距離法、最長距離法、群平均法、ウォード法で ラプラス分布、対数正規分布に従うものを使用する。ま
利用可能である。もし、この不等式を満たす が無い場 た、繰り返し数  回程で  回繰り返した時とほぼ変わりない結果が得られることが分かったので、以後の繰合、クラスターは  つとみなす。
 の値については、 )* では、 の数を使って り返しは  回とすることにした。また、 群の時の  群いる。その時に用いたデータは、データの総数が * のデータ数は  個、 群の時の  群のデータ数は  個のものを、 に分割したものである。本研究では、さ とする。以上のような条件で、分散や相関係数を変化さらに  群のデータ数が多い場合など、 の値について掘 せたときの、各方法における最適なクラスター数の変化の動きを調べていく。また、+  法についてのみ  の値り下げていきたい。
を変化させた時の実験をし、 )* でも明記されてい   法の改良ない  の値について、考察する。以後、主なシミュレー
本研究では、-.. / +  法の改良を提案する。+  法 ション結果を述べる。の停止規則を計算する時、従来の方法ではデータが正規

4 /

0y!



群で他の分布に従う場合−3−2−2−10y21243

法は、三角のデータなどではそれなりに良い結合の果を残しているが、データパターン のように縦長に広がるデータの場合が、かなり苦手と言えるだろう。

−2024−202x46JD 最長
JD ward
JD k−means
x−means
Tail 最長
Tail ward
Tailχ 最長
Tailχ ward

2008180x160

  群正規分布3

図140

  群正規分布3

図

三角形

120
10080

直線上

60
4004620
0.6

0.7

0.8

0.9

11.1

1.2

1.3

1.4

1.5y0

* 対数正規分布3標準偏差を変化させた時
対数正規分布の場合も、 分布の時同様、他の方法が正解率を下げる標準偏差   以降においても、+  のカイ 乗分布を用いた最長距離法と 4 / 法、+  の 4 / 法
図0−41−223y4250.501234567x

図−4−2024x  群対数正規分布 図   群正規分布が圧倒的な強さを見せた。

! 正規分布に従う三角形データの分散変化時

 法を用いた場合で一番良い結果となったのは、法である。+  のカイ  乗分布を用いた時の最長距離法と 4 / 法が、分散が強くなった時にも耐えて良い

結果を出している。

!

群それぞれデータ数の違う場合
JD 最長
JD ward
JD k−means
x−means
Tail 最長
Tail ward
Tailχ 最長
Tailχ ward

200
18016014012010080

JD 最長
JD ward
JD k−means
x−means
Tail 最長
Tail ward
Tailχ 最長
Tailχ ward

2001801601401206040
2000.5 0.6 0.7 0.8 0.9

11.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9210080! 正規分布3分散を変化させた時+  のカイ  乗分布を用いた最長距離法が圧倒的な強さをみせた。しかしこれは  の値がかなりフィットした図  正規分布3分散を変化させた場合からだろう。だからといって、4 / の方は徐々に精度が下がっているので、 の値抜きにしてもカイ  乗分布をグラフは省略するが、分散を  で固定し相関を  から まで変化させた場合も、結果は似たものになった。 用いた最長距離法が、データ数が違う場合に強い事が分 法は極端なデータでなければ安定して良い結果が かる。
得られる。しかし相関が  ! を超え、データの形が極端に !  の値なると、+  のカイ  乗分布を使った最長距離法と 4 /
正規分布に従うデータにおいて、 の値を変化させた。
法が強くなる。
 分布、対数正規分布に従う場合においても  を変化さ!
群の直線上に並ぶデータの相関を変化させた場合 せたが、ほとんど同じ結果になった。 群の場合も同様である。よって  の値は分布よりも各群のデータ数に依存
分散  で固定した場合、データの重なりはそこまで大していると言える。
きくなくても、あまり離れていないため、+  のカイ 乗最長距離法、カイ  乗 4 / 法の  方法がほとんど正解するのに対し、それ以外は全く及ばないという極端な結果になった。一方、分散を   で固定した場合、相関をいくつに変化させても、常にくっきり  群に分かれているデータが得られる。その時の結果では、
法、# 法、+  の最長距離、カイ  乗の最長距離が !
割の正解率を得られるようになった。これらの  方法は、明らかにデータが分かれているような場合でないと、判図  データ数  ×  群の正規分布に従うデータ別するのが難しいことが分かる。また、 法を用いた場60図402000.5 0.6 0.7 0.8 0.911.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.92200

Tail 最長
Tail ward
Tailχ 最長
Tailχ ward

180160140
120
1008060
40
2002.2 2.4 2.6 2.8 3 3.2 3.4 3.6 3.8 4 4.2 4.4 4.6 4.8 5 5.2 5.4 5.6 5.8 6

実際の解析では、各群のデータ数は分からないので、 もある程度の対応が出来るものであると考える。そこで、データの総数と、解析者の予想、希望するクラスター数 実際の場面で有効だと思われる方法に、 の法を想定し、 の値をある程度絞ってから使えば、法の やの法、のカイ 乗分布を用いた法精度が上がるだろう。今回私の行ったシミュレーション があげられる。また、うまく  の値がとれるようであれ
では、一環して と を用いたが、最長距離法 ば、各群の分散やデータ数がばらばらでも、高い正解率か法かでも、最適な  の値が変わってくる。各群の が得られるのカイ 乗分布を用いた最長距離法も実データ数が から 前後の場合、程度がちょうど 用的であると言える。
法や法などで、あるよく、各群のデータ数が前後になると、
 程度 程度の各群のデータ数やクラスター数を予測してから、がちょうどよくなってくる。データ数がもっと多くなる の値を考えてもう一度のカイ 乗分布を用いた最長に従い、 の値も大きくする必要があることが分かった。 距離法で試すと、最適なクラスター数を求められる可能全く結果が予測出来ないような場合は、正解率をとる範 性が高くなるだろう。
囲がかなり広い法が有利である。実際、カイ 乗分
 おわりに布を用いた場合とほとんど同じ程度の精度が得られる。
本研究では、クラスター数決定法が実際のクラスター!" それぞれの方法における結果の群数を当てることを善し悪しの基準にしてきたが、実法を用いた場合、最長距離法では、どの場合もすご 際のデータに対する当てはまりに関してもっと言及出来く良い結果が出たわけではなかった。また、 法よりも ればよかった。しかし法の改良を提案し、良い成績法の方が合っているのかもしれない。
を残すことができ、従来の方法を改善することができた法は、法には劣るが、たいていの場合で と言える。ただそれらの方法も、最終的には、用いる 高い正解率を得られる。縦長なデータに弱く、まとまり の値が正しければ良い結果を得る、という形になった。のある場合であれば何群でも何分布でも、あまり影響を の値に関しては、分けられたクラスター各群のデータ数受けずに良い結果が得られる。に依存することが分かり、その動きも確認できたが、実法は、ウォード法と同じく、かなり安定して高 際の分析でそれは分からないので、その辺りを更に工夫
い正解率で最適なクラスターを求めることが出来る。
することで、クラスター数決定法がより実用的になるの法で試した中では、 番良い結果が出た。データの分布が ではないだろうか。
偏っていたり、相関や分散が少し強めな場合は正解率を下げてしまうが、それでもデータが明確に分かれている 参考文献
場合などは、しっかりあてる事が出来る。
法は、全体としては、あまりよい成績は得ら         れなかった。目で見て明確に判断できるようなデータは分けることができるが、そうでない場合は、信頼できな石岡 恒憲
法改良の一提案
法のいと感じた。
逐次繰り返しとクラスターの再併合 『計算機統計法を用いた場合、最長距離法は、ほとんど良い結学』 #果が得られなかった。唯一、他の方法が苦手とした直線    上にデータが並ぶ時に良い結果を得た。 の高い正解率  ：が得られる範囲もかなり少なく、 の値に結果が大きく神嶌 敏弘 データマイニング分野のクラスタリング
左右され、クラスター数未知の場合に使うには不安要素手法
クラスタリングを使ってみよう！ 『人工が多い。
知能学会誌』#法を用いた法は、今回実験した場合において
菅 民郎 『多変量解析の実践（下）』 現代数学社
は、ほとんどの場合で高い正解率が出た。
カイ 乗を用いた最長距離法は、各群の分散やデータ数が全て違う場合に、圧倒的強さを見せた。実際には、分布や 群の個数が分からないので、 の値を外さなけれ  
ば、かなりよい精度で現実の場面で使えるかもしれない。
 $また、カイ 乗分布を用いる前は、ほとんど機能しない状況だったので、十分改善されたと言える。
カイ 乗分布を用いた法も正規分布使用時から少     
し改善することができ、全体としてかなり良い結果が得られた。他の方法でうまくいかなかった直線上に位置す渡辺 洋 南風原 朝和 大塚 雄作 石塚 智一 山田 文
るデータの時にも、通用する。
康 藤森 進 前川 眞一：『心理・教育のための多変量解析法入門 基礎編』 福村出版
 考察+ 4 /" "

"

+ 

"

4 /

+ 
4 /+  4 /+ +  4 /

4 /

+ 



#+ 

+ 

4 /







4 /

それぞれ得意、不得意があるが、クラスター数決定法として用いやすく実用可能と言える方法は、どんな場合に 1 /2 5 3 6 7  / 8 9  / 
  .. *
*

3 #
:
:
  ..  *    5 ;    < ' 3
 =  4 '>   ?/ 9 1  
3
 ::  .. * 3* )  < 3 1 / /979  /.   7 
..  / 3 @     .. * !!
!  ' A  ?  + '  B7  1  3 6 9 
 /   / / @  8 @  7 7/7  ./  9 2    .. * 