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

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

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

図1　芥川と夏目の作品の樹形図

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

2.1　階層的クラスター分析プロセス

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

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

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

2.2　クラスターの形成とコーフェン行列

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

データ行列　⇒　距離行列　⇒　コーフェン行列　⇒　結果

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

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

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

　　　　

(a)　クラスターと個体　　　　　　　　　　　　　　　　　　　(b)　クラスターの間

図2　コーフェン距離

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

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

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

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

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

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

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

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

図3　 クラスター間の距離

　 これら以外にも、可変 (flexible) 法、McQuitty法、重みつき群平均法などがある。

　 Rのパッケージ stats には階層的クラスター分析の関数 hclust がる。その書き式を次に示す。

　 引数 d は、距離構造のデータで、引数 method にはクラスター分析の方法を指定する。デフォルトには complete 法が指定されている。関数 hclust で扱う方法及びその引数を表3に示す。

　 関数 hclust を用いてクラスター分析を行う際に必要となる幾つかの関数を表4に示す。

■　関数 hclust の結果
　 まずユークリッド距離を用いた関数 hclust の使用例を示す。データは、表1のデータ (seiseki) を用いる。

　 返された結果から、用いた方法は "complete" (最遠隣法)、距離は "euclidean" (ユークリッド) であることが分かる。また、用いたデータの個体数に関する情報も返される。
　 関数 summary で、結果のオブジェクトに格納されたリストを確認することができる。

　 merge は、クラスター形成の履歴のマトリックスである。

　 このデータは、階層的クラスターを形成する階層の情報である。マイナス符号が付いているのが個体の番号、マイナス符号が付いていないのがクラスターの番号である。行番号がクラスター形成の順番である。
　 用いた最遠隣法 (complete) では、ステップ1 (第1行) は、個体2 (佐藤) と個体6 (吉野) がクラスター1を形成する。ステップ2 (第2行) は、個体3 (鈴木) と個体6 (川端) がクラスター2を形成する。ステップ3 (第3行) は、個体1 (田中) とクラスター2が新しいクラスター3を形成する。
　 height はクラスターを形成する際の、樹形図の枝の長さ (高さ) を返す。

　 この値は、merge の結果と対応する。例えば、個体2 (佐藤) と個体6 (吉野) の距離 (枝の長さ) は12.40967である。
　 order は樹形図の左から右方向の個体の番号を返し、labels は個体のラベル、method は用いた方法、call は用いた関数 hclust の書き式、dist.method は用いた距離の方法の名称を返す。

■　樹形図 　 関数 plot あるいは plclust を用いて hclust の結果の樹形図を作成することができる。次に関数 plot を用いた4つの樹形図を示す。引数 hang = - 1 はラベルの高さを揃える。

図4　ユークリッド距離の樹形図

（続く）