第１３章　テキストのクラスター分析

Size: px

Start display at page:

Download "第１３章　テキストのクラスター分析"

みりあわにべ
4 years ago
Views:

1 第 13 章テキストのクラスター分析茨城大学工学部高木真

2 概要複数のテキストを分析する際にテキストの何らかの特徴にもとづいて似ているものごとにグループ分けする必要がある場合がある本章ではテキスト間の類似度 ( または距離 ) にもとづいてテキストをグルーピングする方法やその応用例を説明する

3 テキストのクラスター分析テキストのクラスター分析テキストの分散相関類似度や距離の情報を用いてグループ分けすることクラスター分析のアプローチ. 個体の特徴の情報にもとづいて平面や立体空間上で散布図を作成し分布状況からクラスターの形成状況を分析する ( 主成分分析対応分析自己組織化マップ法 ). データの類似度あるいは距離を用いて最も似てる個体を近い位置に配置する方法 ( 多次元尺度法 ) また似ている個体順にグルーピングするクラスタリング法 ( 階層的クラスタリング法 )

4 . 全体が何グループに分けられるかを指定しそれぞれのグループの中心を機械的に求めその中心までの距離が近いグループに属すると判断する方法 (kmeas 法 ) 本章では多次元尺度法クラスタリング法 k-meas 法などについて説明する

5 類似度と距離類似度似ているほど値が大い測度ピアソンの相関係数 ( 最もよく知られている ) : 同じ長さの特徴ベクトルコサイン類似度 ( テキストの処理 ) 2 2 ) ( ) ( ) )( ( ), ( y y x x y y x x y x cor y x, 2 2 cos ), ( y x y x y x s

6 距離似ているほど値が小さい測度ユークリッド距離 d 現実の問題を解決するにはより工夫された類似度距離が必要 E ( x, y) ( x y 距離重み付きのユークリッド距離マハラノビス距離キャンベラ距離など集計したデータが相対頻度である場合 IR 距離 d IR ( x, y) x 2x log x y 2 ) y 2y log x y

7 類似度は距離に変換して用いることも可能コサイン類似度は以下のような変換で距離として用いられる ( 定数 kは1,2が多く用いられる ) d cos 二値データの類似度一致係数 Jaccard 係数表 1 両ベクトル 0,1 の対応表 2つのベクトルにおける1,0を表 1のように集計して計算したとき accard 係数とJaccardの距離は s J 11 となる ( x, y) k(1 scos 11, dj ( x, y)) ベクトル x ベクトル y

8 多次元尺度法多次元尺度法 (MDS) 距離 ( あるいは類似度 ) データから何らかの方法で 2~ 3 次元に配置する方法地図上の地点間の距離データから地点のマップを作成する方法いくつかのアルゴリズムがある ( 古典的多次元尺度法 ) 距離 ( あるいは類似度 ) の測度に依存する

9 古典的多次元尺度法 2 点間の距離行列の要素 d について z d 1 1 d 1 1 d 1 1 のようにあるいはこれに比例するように変換を施したデータの固有値と固有ベクトルを求める方法 1 2 d

10 本章では 11 人が2つのテーマ ( 住まい車 ) について 1000 文字前後で書いた作文をテーマ別にグループ分けすることを例とする作文データを形態素解析し出現頻度が高い名詞 32 項目を抽出して用いる図 1 ユークリッド距離図 2 IR 距離

11 ユークリッド距離を用いた多次元尺度法の結果は主成分分析の主成分得点の結果に等しい古典的多次元尺度法をさらに発展させた多次元尺度法として sammo,somds,metamds などがある

12 階層的クラスタリング階層的クラスタリング距離行列を用いて似ているものを段階的にグルーピングする単連結法完全連結法群平均法重心法メディア法ウォード法などのアルゴリズムがある大量のデータには不向きアルゴリズムごとに距離データから似ている者同士をグルーピングする方法が異なる第 1 段階はすべて同じで最も距離の値が小さい 2 つの個体を 1 つのグループにする形成されたグループ c とグループ c の間の距離を求める方法が異なる

13 説明の便利のためグループ c に属する任意の個体 k(k c ) とグループ c に属する任意の個体 s(s c ) の間の距離を d ks とする単連結法 ( 最近隣法 ) グループc とc の個体間の距離の中で最小の距離をグループ間の距離とする d( c, c ) m( d ), k c, sc ks 完全連結法 ( 最遠隣法 ) グループc とc の個体間の距離の中で最小の距離をグループ間の距離とする d( c, c ) max( d ), k c, sc ks

14 群平均法グループ c と c の個体間の距離の平均値を両グループ間の距離とする d( c, c ウォード法比較的多く用いられている分散の情報を用いるグループ内の分散が小さくかつグループ間の分散大きい組み合わせでグループ分けする全体の偏差の 2 乗和を T グループ内の偏差の 2 乗和を W, グループ間の偏差の 2 乗和を B で表すと T=W+B が成り立つ ) 1 k1 s1 d ks, k c, s c

15 c d d k d ()k c k c d k c 図 3 クラスター間の距離階層的クラスタリング法のグループ間の距離はつぎの式で求めることができる d d d d, d( ) k ( ) k d, d, d k,,, k k k : 左図に示すクラス管の距離 : パラメータ ( 係数 ) d k d k

16 表 2 方法とパラメータの対応表 ( : クラスター c の個体数 ) 方法の名称 α α β γ 最近隣法 1/2 1/2 0-1/2 最遠隣法 1/2 1/2 0 0 群平均法 0 1/2 重心法 0 メディアン法 1/2 1/2-1/4 0 ウォード法 0 k k k k k k

17 階層的クラスターのグラフを樹形図と呼ぶ図 4 作文のクラスター樹形図 ( ユークリッド距離ウォード法 ) 樹形図は大まかに 2 つのグループに分かれている左側のクラスターが車に関する作文であり右側のクラスターのほとんどが住まいに関する作文である実際のテーマごとの分類と完全には一致しない

18 図 5 作文のクラスター樹形図 (IR 距離ウォード法 ) すべての作文がテーマ別に正しく 2 つのクラスターに分かれている

19 クラスター樹形図を作成する際に用いた変数についてクラスター分析が必要な場合変数のクラスター分析データを転置する転置したデータセットのキャンベラ距離を求めるウォード法によるクラスター樹形図を作成するキャンベラ距離 x y d C ( x, y) x y

20 図 6 作文の名詞のクラスター樹形図 ( キャンべりゃ距離ウォード法 ) 左のクラスターは車と関連する語で右側は住まいに関する語階層的クラスタリングは用いる距離および方法によってしばしば得られる結果が異なる如何に客観的に分析するかが大きな課題

21 k-meas k-meas 法比階層的クラスター分析大量のデータのクラスター分析に用いられるデータをいくつのグループに分けるかについてユーザが指定することが必要いくつかのアルゴリズムが提案されている以下に大まかな流れを示す 1. k 個の仮の初期グループの中心を何らかの方法で与える 2. すべてのデータについて k 個のグループの中心との距離を求めそれぞれ最も近いグループに配属させる 3. 新たに形成されたグループの中心を求める 4. ステップ 2,3 を繰り返しグループおよびグループの中心が前の結果と同じであれば終了する

22 akke0 akke5 ataka0 ataka5 kaa0 kaa5 kato0 kato5 kum0 kum5 mar0 mar5 ogu ogu5 oota0 oota5 or0 or5 taka0 taka5 yuka0 yuka > table(rep(2:1,11),sb.km$clust) 誤分類 :7 個 akke0 akke5 ataka0 ataka5 kaa0 kaa5 kato0 kato5 kum0 kum5 mar0 mar5 ogu ogu5 oota0 oota5 or0 or5 taka0 taka5 yuka0 yuka > table(rep(2:1,11),sb.km$clust) 誤分類 :2 個 k-meas 法のグループ分けの精度は決して高くない k-meas 法の長所は大量のデータにおいて計算が速いことである

23 系統樹系統樹有根系統樹と無根系統樹に分類される階層的クラスター樹形図に似ているクラスター分類に用いることもできる分岐させる方法でより妥当な系統関係を求めるという発想距離データをもとに作成する NJ 法というアルゴリズムがある

24 Neghbor-Net 法系統機を発展させたネットワークツリーという方法 NJ 法を発展させたもの

25 参考 1 ヨーロッパの 21 都市間の道路距離のデータをもとに古典的多次元尺度法を R で実行してみる eurodst というヨーロッパの 21 都市間の道路距離が記されているデータセットを用いたデータとして都市間の距離だけをもとにして 2 次元座標を復元している

26 R のコマンド data(eurodst) data <- as.matrx(eurodst) result <- cmdscale(data, k = 2) ctyames <- c(" アテネ ", " バルセロナ ", " ブリュッセル ", " カレー ", " シェルブール ", " ケルン ", " コペンハーゲン ", " ジュネーブ ", " ジブラルタル ", " ハンブルク ", " オランダのフック ", " リスボン "," ライオンズ ", " マドリード ", " マルセイユ ", " ミラノ ", " ミュンヘン ", " パリ "," ローマ ", " ストックホルム ", " ウィーン ") colors <- c(2, 4, 1, 1, 1, 1, 6, 1, 1, 6, 1, 3, 1, 3, 4, 4, 5, 5, 2, 6, 5) plot(result[,1], -result[,2], type = "") text(result[,1], -result[,2], labels = ctyames, col = colors, cex = 0.8, fot = 2) データセット eurodst を利用するには mva パッケージを読み込む必要がある

27 参考 2 7 人の 5 教科の成績データを用いて階層的クラスター分析を R で実行してみる表 3 成績データ算数理科国語英語社会田中佐藤鈴木本田川端吉野斉藤

28 成績データのユークリッド距離を示す田中佐藤鈴木本田川端吉野佐藤 69 鈴木本田川端吉野斉藤

29 R のコマンド sesek<-matrx(c(89,90,67,46,50, 57,70,80,85,90,80,90,35,40,50, 40,60,50,45,55,78,85,45,55,60, 55,65,80,75,85,90,85,88,92,95),7,5,byrow = TRUE) colames(sesek)<-c(" 算数 "," 理科 "," 国語 "," 英語 "," 社会 ") rowames(sesek)<-c(" 田中 "," 佐藤 "," 鈴木 "," 本田 "," 川端 "," 吉野 "," 斉藤 ") sesek.d<-dst(sesek) (se.hc<-hclust(se.d)) par(mfrow=c(2,2)) plot(se.hc,ma=" 最遠隣法 ") plot(se.hc,hag=-1,ma=" 最遠隣法 ") s.hc2<-hclust(se.d,method="cetrod") plot(s.hc2,hag=-1,ma=" 重心法 ") s.hc3<-hclust(se.d,method="ward") plot(s.hc3,hag=-1,ma=" ウォード法 ")

< F55542D303996E291E894AD8CA9365F834E E95AA90CD836D815B>

< F55542D303996E291E894AD8CA9365F834E E95AA90CD836D815B> クラスター分析に関するノート情報学部堀田敬介 2004/7/32008/7/ 改訂, 2009/0/3 改訂 ) 類似度の測定まずはじめに, 各データ間の距離を測るが, 尺度毎に様々な方法が提案されている. 尺度に対応した類似度測定の距離を示す.. 間隔尺度による類似度の測定 n 個の対象があり, 各対象は間隔尺度で m 個の属性変量 ) が測定されているとする. このとき対象と q を x

第１３章 テキストのクラスター分析

第１３章　テキストのクラスター分析