[連載]フリーソフトによるデータ解析・マイニング第28回

　我々は、物事を整理整頓する際には、機能、形状などの側面から似ているものを同じのところに集めて、片付ける。これと同じくデータについてもデータ構造の側面から似ている個体を同じのグループに仕分けることが必要である場合がある。データサイエンスにおける分類のための方法は、学習(教師、訓練)データがある分類方法と学習データがない方法に大別される。
　ここで言う学習データとは、どの個体がどのグループに属するかが既知であるデータである。グループの所属を示すデータは外的基準とも呼ばれている。学習データがある場合の分類方法は、どの個体がどのグループに属するかが既知であるデータから、分類に関するモデルを作成し、そのモデルに基づいて、グループの属性が未知であるデータを最も似ていると判断されるグループに割り当てる判別分析のような方法である。
　学習データがない分類方法は、どの個体がどのグループに属するかに関する事前情報がないデータについて、グループ分けする方法で、外的基準がない分類法である。通常この種の分類方法をクラスター分析と呼ぶ。ここのクラスター(cluster)とは、花やブドウなどの房の意味で、クラスター分析とは、データの構造が似ている個体を同じの房(グループ)にまとめて、そうでないものを異なる房に集めるデータの処理方法である。
　学習データがない分類方法は、どの個体がどのグループに属するかに関する事前情報がないデータについて、グループ分けする方法で、外的基準がない分類法である。通常この種の分類方法をクラスター分析と呼ぶ。ここのクラスター(cluster)とは、花やブドウなどの房の意味で、クラスター分析とは、データの構造が似ている個体を同じの房(グループ)にまとめて、そうでないものを異なる房に集めるデータの処理方法である。
　本稿では、グループの形成状態を房の形で示す樹形図を用いる階層的クラスター分析の方法と、どの個体がどのグループに属するかを示す非階層的クラスター分析方法の一種であるk-means法について紹介する。

　階層的クラスター分析とは、個体間の類似度あるいは非類似度(距離)に基づいて、最も似ている個体から順次に集めてクラスターを作っていく方法である。クラスターが作られていく様子を図1に示すような樹形図で示すことができる。樹形図はデンドログラム(dendrogram)とも呼ばれている。また、階層的クラスター分析はクラスタリング法、凝集型階層手法とも呼ばれている。
　図１の樹形図は、芥川龍之介と夏目漱石のそれぞれの20作品における各々の助詞の使用率を用いた樹形図である。

　樹形図は文字どおり木の構造に似たグラフであり、ラベルが付いている部分を葉と言う。葉と葉との距離（葉から上に伸びている線が連結するまでの高さ）が短いほど個体が似ていると言える。樹形図では、幾つかの個体が階層的集まり１つのクラスター(房、枝)を形成し、複数のクラスターが最終的には１つのクラスター（木）となる様子が見て取れる。
　また樹形図をある高さ（距離）のところで線を引いて切断することによって、クラスターの数が定まり個体の分類が定まる。例えば、図1において、点線前後の高い位置で樹形図を切断すると、樹形図は芥川氏の作品と夏目氏の作品が分類される。

　階層的クラスター分析には幾つかの方法があるが、いずれも次のようなステップを踏む。

　　①距離(あるいは類似度)を求める方法を選択し、個体間の距離(類似度)を計算する。
　　②クラスター分析の方法（最近隣法、最遠隣法など）を選択する。
　　③選択された方法のコーフェン（Cophenetic）行列を求める。
　　④コーフェン行列に基づいて樹形図を作成する。
　　⑤結果について検討を行う。

　①では、多次元尺度法を説明する際に示したような距離(あるいは類似度)をデータから求める。②では、次の節で述べる階層的クラスター分析方法を選択する。

　階層的クラスター分析では、データから距離の行列を求め、距離の行列を用いて樹形図を描くためのコーフェン行列を求め、コーフェン行列に基づいて樹形図を描くというプロセスを経る。

　距離行列からコーフェン行列を生成する際の第1段階はすべての方法が同じで、最も距離が近い２つの個体間の距離をコーフェン距離とする。第１段階が終わった後、どのようにコーフェン距離を求めるかはクラスター分析の方法によって異なる。
　ここでは具体的な例を用いて、そのイメージを説明する。データは、因子分析を説明する際に用いた7人の5教科の成績データを用いることにする。そのデータを表1に再掲する。

　このデータのユークリッド距離を次に示す。

　このような距離データからコーフェン行列の計算過程の主なステップを説明する。
　上記の距離行列では、最も距離が近いのは、吉野と佐藤の12である。そこでこの２人がまずクラスターc1{吉野,佐藤}を形成する。
　次に距離の値が小さいのは川端と鈴木との距離である。川端と鈴木が１つのクラスター{川端,鈴木}を形成すべきか、それともc1に川端を加えたクラスター{ c1,川端}, c1に鈴木を加えたクラスター｛c1,鈴木｝が新しいクラスターを形成すべきであるかは何らかの決まりに従って計算する必要がある。
　説明の便利のため、この7人の距離関係を図2のように平面上で示すことができると仮定する。
　川端と鈴木の距離は既に分かっているので求める必要がない。問題は、c1と川端の距離、c1と鈴木との距離をどのように求めるかである。c1と川端の距離を考える場合でも図2(a)に示すように幾つかの方法が考えられる。
　この問題では、どのような方法を採っても明らかに、川端と鈴木の距離が短いので新しいクラスターc2は｛川端,鈴木｝となる。このようにc2に田中が加えられ新たなクラスターc3｛c2,田中｝=｛川端,鈴木,田中｝が形成される。階層的クラスター法はこのように階層的クラスターを形成する。
　クラスターを形成する際には、クラスターとクラスターとの間の距離を計算しなければならない問題に遭遇する。例えば、クラスターc1とクラスターc３との距離を考えてみよう。クラスター間の距離は図2(b)に示すように、クラスターの間で最も近い個体同士の距離をクラスター間の距離にするか(最近隣法)、最も距離が遠い個体同士の距離をクラスター間の距離にするか(最遠隣法)など、クラスター間の距離の求め方は唯一ではない。このようなクラスター間の距離を求める方法の違いで、階層的クラスター分析の方法が異なる。このように何らかの方法で求めた距離行列がコーフェン行列である。階層的クラスター分析の樹形図はコーフェン行列に基づく。

　階層的クラスター分析の方法はクラスター間の距離をどのように求めるかで、最近隣法、最遠隣法、群平均法、メディアン法 、重心法、ウォード法などに分かれる。

■　最近隣法
　最近隣法(nearest neighbor method)は、最短距離法、単連結法(single linkagr)法とも呼ばれる。最近隣法は、２つのクラスターのそれぞれの中から１個ずつ個体を選んで個体間の距離を求め、それらの中で、最も近い個体間の距離をこの２つのクラスター間の距離とする方法である。

■　最遠隣法
　最遠隣法(furthest neighbor method)は、最遠距離法、完全連結(complete linkage)法とも呼ばれる。最遠隣法は、最近隣法とは逆に、２つのクラスターの中のそれぞれの中から１個ずつ個体を選んで個体間の距離を求め、それらの中で、最も遠い個体間の距離をこの２つのクラスター間の距離とする方法である。

■　群平均法
　群平均法（group average method）は、最近隣法と最遠隣法を折衷した方法で、２つのクラスターのそれぞれの中から１個ずつ個体を選んで個体間の距離を求め、それらの距離の平均値を２つのクラスター間の距離とする。

■　重心法
　重心法(centroid method)は、クラスターのそれぞれの重心（例えば、平均ベクトル）を求め、その重心間の距離をクラスターの間の距離とする。重心を求める際には、クラスターに含まれる個体数が反映されるように、個体数を重みとして用いる。

■　メディアン法
　メディアン(median method)法は、重心法の変形で、２つのクラスターの重心の間の重み付きの距離を求めるとき、重みを等しくして求めた距離の値を、２つのクラスター間の距離とする。

■　ウォード法
　ウォード法(Ward's method)は、２つのクラスターを融合した際に、群内の分散と群間の分散の比を最大化する基準でクラスターを形成していく方法である。ウォード法は最小分散法(minimum variance method)とも呼ばれている。

　これらのコーフェン行列作成過程で、新しいクラスターを形成する際のクラスター間の距離は次の式で求める。式の中のdij,d(ij)k,dik,djkは図3に示すクラスター間の距離で、αi,αj,β,γはパラメータ(係数)である。パラメータと上述の方法との対応関係を表2に示す。

表2 方法とパラメータとの対応表　(niクラスターciの個体数)

方法の名称	αi	αj	β	γ
最近隣法			0
最遠隣法			0
群平均法			0	0
重心法				0
メディアン法				0
ウォード法				0

3．階層的クラスター分析のR関数

(1)関数 hclust

�