言語処理100本ノック 2015の挑戦記録です。環境はUbuntu 16.04 LTS ＋ Python 3.5.2 :: Anaconda 4.1.1 (64-bit)です。過去のノックの一覧はこちらからどうぞ。
第10章: ベクトル空間法 (II)
第10章では，前章に引き続き単語ベクトルの学習に取り組む．
###98. Ward法によるクラスタリング
96の単語ベクトルに対して，Ward法による階層型クラスタリングを実行せよ．さらに，クラスタリング結果をデンドログラムとして可視化せよ．
####出来上がったコード：
# coding: utf-8
import pickle
from collections import OrderedDict
from scipy import io
import numpy as np
from scipy.cluster.hierarchy import ward, dendrogram
from matplotlib import pyplot as plt
fname_dict_index_t = 'dict_index_country'
fname_matrix_x300 = 'matrix_x300_country'
# 辞書読み込み
with open(fname_dict_index_t, 'rb') as data_file:
dict_index_t = pickle.load(data_file)
# 行列読み込み
matrix_x300 = io.loadmat(fname_matrix_x300)['matrix_x300']
# Ward法でクラスタリング
ward = ward(matrix_x300)
print(ward)
# デンドログラム表示
dendrogram(ward, labels=list(dict_index_t.keys()), leaf_font_size=8)
plt.show()
####実行結果：
ちょっと細かくて国名を読むのが辛いですが...
コンソールにはWard法の実行結果を表示します。終わりにGUI関連と思われるワーニングがいくつか表示されますが、とりあえずデンドログラムが表示できているので見なかったことにしています^^;
[[ 3.20000000e+01 5.50000000e+01 3.53776681e-01 2.00000000e+00]
[ 6.00000000e+00 1.36000000e+02 3.87856834e-01 2.00000000e+00]
[ 1.77000000e+02 1.88000000e+02 4.23449123e-01 2.00000000e+00]
[ 1.54000000e+02 2.10000000e+02 4.27902443e-01 3.00000000e+00]
[ 1.57000000e+02 1.59000000e+02 4.59378255e-01 2.00000000e+00]
[ 3.70000000e+01 1.49000000e+02 4.71549159e-01 2.00000000e+00]
[ 2.80000000e+01 2.11000000e+02 4.87752476e-01 3.00000000e+00]
[ 1.58000000e+02 1.93000000e+02 4.97266503e-01 2.00000000e+00]
[ 3.80000000e+01 6.20000000e+01 5.05332444e-01 2.00000000e+00]
[ 1.20000000e+02 1.60000000e+02 5.24018281e-01 2.00000000e+00]
[ 2.09000000e+02 2.12000000e+02 5.26909455e-01 5.00000000e+00]
[ 2.14000000e+02 2.19000000e+02 5.63841737e-01 7.00000000e+00]
[ 1.01000000e+02 1.78000000e+02 5.74498656e-01 2.00000000e+00]
[ 1.18000000e+02 2.15000000e+02 5.88183758e-01 4.00000000e+00]
[ 1.55000000e+02 2.13000000e+02 6.09433424e-01 3.00000000e+00]
[ 1.51000000e+02 2.20000000e+02 6.57637828e-01 8.00000000e+00]
[ 7.40000000e+01 2.22000000e+02 6.69853809e-01 5.00000000e+00]
[ 4.80000000e+01 7.00000000e+01 6.72731044e-01 2.00000000e+00]
[ 2.17000000e+02 2.21000000e+02 6.88767402e-01 4.00000000e+00]
[ 2.16000000e+02 2.18000000e+02 6.89235190e-01 4.00000000e+00]
（中略）
[ 3.53000000e+02 3.66000000e+02 7.72813958e+00 3.70000000e+01]
[ 8.80000000e+01 3.93000000e+02 7.91160391e+00 3.00000000e+00]
[ 5.90000000e+01 3.95000000e+02 8.36126980e+00 4.00000000e+00]
[ 3.10000000e+01 3.98000000e+02 8.42501966e+00 4.00000000e+00]
[ 3.71000000e+02 3.97000000e+02 8.67427318e+00 1.10000000e+02]
[ 3.84000000e+02 3.87000000e+02 8.73417227e+00 4.90000000e+01]
[ 9.40000000e+01 3.96000000e+02 8.76123102e+00 3.00000000e+00]
[ 3.88000000e+02 3.92000000e+02 9.29959662e+00 1.20000000e+01]
[ 3.86000000e+02 3.89000000e+02 1.00548308e+01 5.00000000e+00]
[ 3.90000000e+02 3.91000000e+02 1.03513479e+01 1.80000000e+01]
[ 8.40000000e+01 4.06000000e+02 1.08361185e+01 1.90000000e+01]
[ 4.02000000e+02 4.04000000e+02 1.22602262e+01 6.10000000e+01]
[ 4.03000000e+02 4.05000000e+02 1.27024876e+01 8.00000000e+00]
[ 3.99000000e+02 4.07000000e+02 1.36985698e+01 2.30000000e+01]
[ 1.98000000e+02 4.00000000e+02 1.39290496e+01 5.00000000e+00]
[ 4.09000000e+02 4.11000000e+02 1.64166647e+01 1.30000000e+01]
[ 3.94000000e+02 4.08000000e+02 1.65142018e+01 6.30000000e+01]
[ 4.10000000e+02 4.12000000e+02 2.02282024e+01 3.60000000e+01]
[ 4.01000000e+02 4.13000000e+02 2.40955381e+01 1.73000000e+02]
[ 4.14000000e+02 4.15000000e+02 4.18596046e+01 2.09000000e+02]]
GLib-GIO-Message: Using the 'memory' GSettings backend. Your settings will not be saved or shared with other applications.
(python:20130): Gtk-WARNING **: GModule (/usr/lib/x86_64-linux-gnu/gtk-2.0/2.10.0/immodules/im-fcitx.so) initialization check failed: GLib version too old (micro mismatch)
(python:20130): Gtk-WARNING **: Loading IM context type 'fcitx' failed
(python:20130): Gtk-WARNING **: GModule (/usr/lib/x86_64-linux-gnu/gtk-2.0/2.10.0/immodules/im-fcitx.so) initialization check failed: GLib version too old (micro mismatch)
(python:20130): Gtk-WARNING **: Loading IM context type 'fcitx' failed
(python:20130): Gtk-WARNING **: GModule (/usr/lib/x86_64-linux-gnu/gtk-2.0/2.10.0/immodules/im-fcitx.so) initialization check failed: GLib version too old (micro mismatch)
(python:20130): Gtk-WARNING **: Loading IM context type 'fcitx' failed
###階層的クラスタリング
階層的クラスタリングは、前問のK-Meansのようにクラスターの数を最初に決めるのではなく、最も似ているものから段階的にまとめていく方法です。
まず各データをバラバラのクラスターとみなし、クラスター間の距離を計算して、距離がもっとも近いクラスター同士を1つにまとめます。これで1回目の処理が終わり、データ数-1のクラスターへの分類が完了です。これを繰り返してクラスターを1つずつ減らしていきます。クラスターをまとめた際は、それに所属するデータの重心などをそのクラスターの代表点として、他のクラスターとの距離を計算します。
###Ward法（ウォード法）
階層的クラスタリングは、クラスター間の距離の計算方法によっていくつかの手法に分かれます。Ward法はその中の1つで、クラスタの各値からその質量中心までの距離を最小化します。それ以外にも群平均法、最短距離法などがあります。
###デンドログラム
デンドログラムは樹形図のことです。
階層的クラスタリングの結果をトーナメント表のような形で見える化します。線の分岐点はまとめたクラスターを示しており、実際の処理は下から上に向かって行われます。縦軸はクラスター内の所属データの距離の和で、上に向かえば向かうほど遠いものをまとめたことを示しています。
実行結果のデンドログラムでは、縦軸の25辺りより上で横に切れば2つのクラスターに分類した結果として使えます。20よりちょっと上なら3つ、20よりちょっと下なら4つになります。このようにデンドログラムを見ながら分類数を決めることができます。
階層的クラスタリングやWard法の解説はググるとたくさん出てきますので、詳細は割愛します。ALBERTさんのホームページの解説データマイニング クラスター分析が分かりやすかったです。
###Ward法の実装
Ward法によるクラスタリングは、問題84で使い始めたSciPyを使うと簡単です。
scipy.cluster.hierarchy.ward()で単語ベクトルを指定すれば完了です。結果として返る行列の行数はまとめた数（＝データ数-1）で、各列の数値は、最初の2つが束ねたクラスターのインデックス、その次がクラスター内の所属データの距離の和、最後が束ねたクラスター内のデータ数です。
例えば実行結果の先頭行の
[ 3.20000000e+01 5.50000000e+01 3.53776681e-01 2.00000000e+00]
は、最初にまとめた処理を示します。インデックス32と55のクラスター（最初は単語そのもの）を1つのクラスターに束ね、クラスター内の所属データの距離の和は0.3537...（＝デンドログラムの縦軸の値）で、束ねたクラスターには2個のデータが所属していることを示しています。束ねられたクラスターには、現在のインデックス最大値+1のインデックスが付与されていきます。
最終行の
[ 4.14000000e+02 4.15000000e+02 4.18596046e+01 2.09000000e+02]
は最後のまとめ処理を示しています。インデックス414と415を束ね、距離の和は41.8596...で、209個（＝全データ数）のデータが所属します。これは実行結果のデンドログラムにおける青色の線に相当します。
###デンドログラムの実装
デンドログラムの表示もSciPyを使うと簡単で、scipy.cluster.hierarchy.dendrogram()にscipy.cluster.hierarchy.ward()の結果を指定するだけです。デフォルトだと文字が小さくなりすぎたのでleaf_font_sizeで調整しています。orientationを指定すると軸を入れ替えることなどもできます。
残念ながら前問と同じで、結果を見てもどんな切り口で分類されたのかはイマイチ分かりませんが...
99本目のノックは以上です。誤りなどありましたら、ご指摘いただけますと幸いです。
実行結果には、100本ノックで用いるコーパス・データで配布されているデータの一部が含まれます。この第10章で用いているコーパス・データのライセンスはクリエイティブ・コモンズ 表示-継承 3.0 非移植（日本語訳）です。また、国名の一覧は、「KIDS外務省 - 世界の国々」（外務省）（http://www.mofa.go.jp/mofaj/kids/ichiran/index.html）と、nationsonline.orgのCountries and Regions of the World from A to Zを加工して作成しています。