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

統計的テキスト解析(13)~テキストのクラスター分析~

1.テキストのクラスター分析

 図書館の図書は何らかの特徴別にグループ分けしており、新聞の紙面は総合、社会、経済、国際、生活、料理、スポーツ、地域などに分けられている。図書は図書館の管理者が、新聞の紙面は編集者たちがグループ分けしている。しかし、インターネット上の大量のテキストを何らかの特徴別にグループ分けする場合、すべての内容を読み、グループ分けすることは現実的ではない。また、人為的にグループ分けすることは読む側の主観の印象や認識などに左右されるため、客観的なグループ分けが求められている。
 本稿では、テキストがどのグループに属するかに関する情報(外的規準とよぶ)を用いずにグループ分けする方法を説明する。このようなグループ分け方法をクラスター分析と呼ぶ。テキストのクラスター分析は、主に次のようなアプローチ多用されている。
(1)個体の特徴の情報に基づいて、平面や立体空間上で散布図を作成し、分布状況からクラスターの形成状況を分析する。主な方法として前章で述べた主成分分析、対応分析、自己組織化マップ法などがある。
(2)データの類似度、あるいは距離を用いて、最も似ている個体を近い位置に配置する方法と似ている個体順にグルーピングするクラスタリング法がある。代表的な方法として、前者に関しては多次元尺度法、後者に関しては階層的クラスタリング法がある。
(3)全体が何グループに分けられるかを指定し、グループの中心を機械的に求め、その中心までの距離が近いグループに属すると判断する方法。代表的な方法としては、k-means法がある。
 本稿では多次元尺度法、クラスタリンク法、k-means法などについて例を用いて説明する。

2.類似度と距離

 類似度は似ているほど値が大きく、距離は似ているほど値が小さい測度である。類似度として最も知られているのはピアソン相関係数である。

ピアソン相関係数

 テキストの処理には、次に示すコサイン類似度がピアソン相関係数より多用されている。

コサイン類似度

 距離として最も多く使われているのはユークリッド距離

ユークリッド距離

 である。しかし、現実の問題を解決するためには、より工夫された類似度、距離が必要である。
 距離については、重みつきのユークリッド距離、マハラノビス距離、キャンベラ距離などがある。集計したデータが相対頻度である場合は、次に示すIR距離も有効である。

IR距離

 類似度は距離に変換して用いることも可能である。例えば、コサイン類似度は、次のように変換して、距離として用いられる。

コサイン類似度の変換による距離

 集計したデータが0、1の二値データや間隔尺度などでる場合は、それに適した類似度、距離の指標を用いるべきである。二値データの類似度としては、一致係数やJaccard係数などがある。
 Jaccard係数は2つのベクトルにおける1、0の対応関係を表1のように集計して計算する。表の中のn11はベクトルxの要素が1のとき、それに対応するベクトルyの要素も1である数であり、n10はベクトルxの要素が1のとき、それに対応するベクトルyの要素は0である数である。n01はベクトルxの要素が0のとき、それに対応するベクトルyの要素は1である数であり、n00はベクトルxの要素が0のとき、それに対応するベクトルyの要素は0である数である。

表1 両ベクトル0,1の対応表
  ベクトルy
1 0
ベクトルx 1 n11 n10
0 n01 n00

 Jaccard係数とJaccardの距離はそれぞれ次の式で定義されている。

Jaccard係数とJaccardの距離

 一般的に用いられている距離行列、あるいは類似度行列は対称行列である。

3.多次元尺度法

 距離(あるいは類似度)データを何らかの方法で2~3次元に個体を配置する方法として多次元尺度法(MDS: multi- dimensional scaling)がある。多次元尺度法は、地点間の距離データから地点のマップを作成する方法であると理解しても差し支えない。
 多次元尺度法には、いくつかのアルゴリズムがある。最も基本となる方法は、古典的多次元尺度法である。古典的多次元尺度法は、2点間の距離行列の要素dijについて

古典的多次元尺度法

のように、あるいはこれに比例する変換を施したデータの固有値と固有ベクトルを求める方法である。
 本稿では、11人が、2つのテーマ(住まい、車)について、1000文字前後で書いた作文をテーマ別にグループ分けすることを例とする。作文データを形態素解析し、出現頻度が高い名詞32項目を抽出して用いることにする。データは次のサイト掲載されている(http://mjin.doshisha.ac.jp/data/sb2.csv)。
 まず、Rに読み込み、作文の長さに比例するようにデータを加工する。若干荒い手法であるが、説明の便利のため、抽出した名詞の総数を規準とし、相対度数を求めて用いることにする。

> sb<-read.csv("c:/temp/sb2.csv",head=T, row.names=1)
> sb.p<-sb/apply(sb,1,sum)

 ユークリッド距離を用いた古典的多次元尺度法の2次元散布図を作成するRコマンドを次に示し、その結果を図1に示す。

>sb.ed<-dist(sb.p[,1:32])
>sb.mds<- cmdscale(sb.ed,2)
>plot(sb.mds,type="n",xlab="第1固有ベクトル",ylab="第2固有ベクトル")
>text(sb.mds,rownames(sb.mds))

 図1の中のラベルは、書き手のニックネームである。ニックネームの右の数字は、作文のテーマを示している。数値0はテーマ「住まい」、数値5はテーマ「車」を示す。図1では、車に関する作文yuka5、ori5が「住まい」の方に寄っている。


図1 ユークリッド距離のMDS散布図

図1 ユークリッド距離のMDS散布図

 古典的多次元尺度法は、距離行列の固有ベクトルを求めているので、第1、2固有ベクトル (スコアと呼ぶ)以外を用いて分析することも可能である。
 図2にユークリッド距離を用いた古典的多次元尺度法の第1、2、3スコアの3次元の散布図を示す。この図はRパッケージgrlの中の関数plot3dを用いたものである。plot3dで作成した図は、マウスで自由自在に回転しながら考察することができる。

>install.packages("rgl");library(rgl)
>sb.ed<-dist(sb.p[,1:32])
>sb.mds<-cmdscale(sb.ed,3)
>x<-sb.mds[,1];y<-sb.mds[,2];z<-sb.mds[,3]
>plot3d(x,y,z,type="n")
>text3d(x,y,z,text=rownames(sb.mds),adj=0.5)
>grid3d(c("x", "y+", "z"))


図2 多次元尺度法の3次元散布図

図2 多次元尺度法の3次元散布図

 ユークリッド距離を用いた多次元尺度法の結果は、主成分分析の主成分得点の結果に等しい。
 多次元尺度法の結果は用いる距離や類似度に大きく依存する。また、多次元尺度法は古典的多次元尺度を発展させたsammon、isoMDS、 metaMDSなどがある。

4.階層的クラスタリング

 階層的クラスタリングは、基本的には距離行列を用いて似ているものを段階的にグルーピングする。階層的クラスタリング法には、単連結法、完全連結法、群平均法、重心法、メディアン法、ウォード法などのアルゴリズムが提案されている。
 これらの方法は、距離データから似ている同士をグルーピングする方法が異なる。第1段階はすべて同じく、最も距離の値が小さい2つの個体を1つのグループにするが、形成されたグループciとグループcjの間の距離を求める方法が異なる。
 説明の便利のため、グループ に属する任意の個体k(kci)とグループ に属する個体s(scj)の間の距離をdksとする。
 単連結法(Single Linkage Method,最近隣法とも呼ぶ)は、グループcicjの個体間の距離の中で、最小の距離をグループ間の距離とする。

単連結法

 完全連結法(Complete Linkage Method,最遠隣法とも呼ぶ)は、グループcicjの個体間の距離の中で、最大の距離をグループ間の距離とする。

完全連結法

 群平均法(Group Average Method)は、グループciの個体とcjの個体間の距離の平均値を両グループ間の距離とする。式の中のni,njは、それぞれグループci,cjの個体の数である。

群平均法

 提案されたクラスタリング法の中で、比較的に多く用いられているのはウォード法である。
 ウォード法(Ward's Method)は、分散の情報を用いる。データをグループに分けしたとき、全体の分散は、グループ内の分散とクループ間の分散の合計に等しい。偏差の自乗の和を用いても同じのことがいえる。
 全体の偏差の2乗和をT、グループ内の偏差の2乗和をW、グループ間の偏差の2乗和をBで示すと次の式が成り立つ。

T=W+B

 ウォード法では、グループ内の分散が小さく、かつグループ間の分散が大きい組み合わせでグループ分けする。
 これらの階層的クラスタリング法のグループ間の距離は次の式で求めることができる。

階層的クラスタリング法のグループ間の距離

 式の中のdij,d(ij)k,dik,djkは図3に示すクラスター間の距離で、αi,αj,β,γはパラメータ(係数)である。


図3 クラスター間の距離

図3 クラスター間の距離

 パラメータとクラスタリング法との対応関係を表1に示す。

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

表1 パラメータとクラスタリング法との対応関係

 前節で用いた作文データについてユークリッド距離を求め、ウォード法によるクラスターのグラフを作成するRコマンドを次に示し、その結果を図4に示す。階層的クラスターのグラフを樹形図とよぶ。

> sb.ed<-dist(sb.p[,1:32])
> sb.hc<-hclust(sb.ed,"ward")
> plot(sb.hc,hang=-1)
> rect.hclust(sb.hc, k=2, border="red")

 樹形図は、大まかに2つのグループに分かれている。左側のクラスターが「車」に関する作文であり、右側のクラスターのほとんどが「住まい」に関する作文である。ただし、作文が完全に正しくテーマ別にクラスターが形成されていない。


図4 作文のクラスター樹形図(ユークリッド距離、ウォード法)

図4 作文のクラスター樹形図
(ユークリッド距離、ウォード法)

 同じデータを用いたIR距離とウォード法によるクラスターの樹形図を図6に示す。出力された結果から分かるように、全てがテーマ別に正しく2つのクラスターに分かれている。


図5 作文のクラスター樹形図(IR距離、ウォード法)

図5 作文のクラスター樹形図
(IR距離、ウォード法)

 作文のクラスター樹形図を作成する際に用いた語(変数)についてクラスター分析が必要な場合がある。変数のクラスター分析は、データsb.pを転置して作成することができる。転置したデータセットのキャンベラ距離を求め、ウォード法によるクラスター樹形図を作成するコマンドを次に示し、その結果を図7に示す。キャンベラ距離は、次の式で定義されている。

キャンベラ距離

> sb.t<-t(sb[,1:32])
> sb.cd<-dist(sb.t,"can")
> sb.hc<-hclust(sb.cd,"ward")
> plot(sb.hc,hang=-1,main="")

 左のクラスターは、「車」と関連する語であり、右側は「住まい」に関連する語であることがわかる。階層的クラスタリングは、用いる距離および方法によって、しばしば得られる結果が異なるので、如何に客観的に分析するかが大きな課題である。また、階層的クラスタリングは、大量のデータには不向きである。


図6 作文の名詞のクラスター樹形図(キャンベラ距離、ウォード法)

図6 作文の名詞のクラスター樹形図
(キャンベラ距離、ウォード法)

5.k-means法

 大量のデータのクラスター分析にはk-means法という非階層的クラスター分析の方法がよく用いられている。
 k-means法は、ユーザがデータをいくつのグループに分けるかについて指定することが必要である。k-means法には,いくつかのアルゴリズムが提案されているが,その大まかな流れを次に示す。

(1)k個の仮の初期グループ中心を何らかの方法で与える。
(2)すべてのデータをk個のグループの中心との距離を求め、最も近いグループに配属させる。
(3)新たに形成されたグループの中心を求める。
(4)グループの中心が安定するまでステップ(2)、(3)を繰り返す。

 Rに用意されているk-means法の関数kmeansの初期設定のまま、2つのテーマの作文データのクラスター分析を行うコマンドとその結果を次に示す。

> sb.km<-kmeans(sb.p[,1:32], 2)
> sb.km$cluster
sb.km$clusterの結果

 返されたテキストのラベルの下の数値がグループの番号である。数値「0」が付いているテキストをグループ1、数値「5」が付いているテキストをグループ2とすると、いくつが誤分類されていることが計算できる。k-means法は分類の精度は高くないが、アルゴリズムが理解しやすく、かつ計算が速いことから多く用いられている。