言語処理100本ノック 2015の挑戦記録です。環境はUbuntu 16.04 LTS ＋ Python 3.5.2 :: Anaconda 4.1.1 (64-bit)です。過去のノックの一覧はこちらからどうぞ。
第10章: ベクトル空間法 (II)
第10章では，前章に引き続き単語ベクトルの学習に取り組む．
###97. k-meansクラスタリング
96の単語ベクトルに対して，k-meansクラスタリングをクラスタ数$ k=5 $として実行せよ．
####出来上がったコード：
# coding: utf-8
import pickle
from collections import OrderedDict
from scipy import io
import numpy as np
from sklearn.cluster import KMeans
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']
# KMeansクラスタリング
predicts = KMeans(n_clusters=5).fit_predict(matrix_x300)
# (国,分類番号)のリスト作成
result = zip(dict_index_t.keys(), predicts)
# 分類番号でソートして表示
for country, category in sorted(result, key=lambda x: x[1]):
print('{}\t{}'.format(category, country))
####実行結果：
0〜4の分類番号と国名をタブ区切りで出力しています。
0 Andorra
0 Antarctica
0 Antigua_and_Barbuda
0 Bahamas
0 Bahrain
0 Barbados
0 Belarus
0 Belize
0 Benin
0 Bermuda
0 Bhutan
0 Bosnia_and_Herzegovina
0 Botswana
0 Burkina_Faso
0 Burundi
0 Cameroon
0 Central_African_Republic
0 Chad
0 Commonwealth_of_Australia
0 Comoros
0 Congo
0 Cook_Islands
0 Democratic_Republic_of_the_Congo
0 Djibouti
0 Dominica
0 Dominican_Republic
0 Ecuador
0 Eritrea
0 Estonia
0 Federal_Republic_of_Germany
0 Federated_States_of_Micronesia
0 French_Republic
0 Gabon
0 Gambia
0 Gibraltar
0 Greenland
0 Grenada
0 Guadeloupe
0 Guam
0 Guatemala
0 Guinea-Bissau
0 Guyana
0 Haiti
0 Honduras
0 Jamaica
0 Jordan
0 Kazakhstan
0 Kingdom_of_the_Netherlands
0 Kiribati
0 Kuwait
0 Kyrgyzstan
0 Lao
0 Latvia
0 Lesotho
0 Liberia
0 Liechtenstein
0 Luxembourg
0 Macau
0 Madagascar
0 Malawi
0 Maldives
0 Mali
0 Martinique
0 Mauritania
0 Mauritius
0 Mayotte
0 Micronesia
0 Moldova
0 Monaco
0 Mongolia
0 Montenegro
0 Mozambique
0 Myanmar
0 Namibia
0 Nauru
0 Nicaragua
0 Niger
0 Niue
0 Oman
0 Palau
0 Paraguay
0 Qatar
0 Republic_of_Albania
0 Republic_of_Armenia
0 Republic_of_Austria
0 Republic_of_Congo
0 Republic_of_Croatia
0 Republic_of_Estonia
0 Republic_of_Korea
0 Republic_of_Poland
0 Republic_of_Singapore
0 Republic_of_South_Africa
0 Republic_of_Turkey
0 Republic_of_the_Philippines
0 Russian_Federation
0 Rwanda
0 Saint_Lucia
0 Senegal
0 Seychelles
0 Slovenia
0 Solomon_Islands
0 Somalia
0 State_of_Israel
0 Suriname
0 Swaziland
0 Tajikistan
0 Tibet
0 Timor-Leste
0 Togo
0 Tokelau
0 Tonga
0 Tunisia
0 Turkmenistan
0 Tuvalu
0 United_Arab_Emirates
0 United_States_of_America
0 Uzbekistan
0 Vanuatu
0 Vatican
0 Yemen
0 Zambia
0 Zimbabwe
1 Austria
1 Belgium
1 Bulgaria
1 Denmark
1 Egypt
1 France
1 Germany
1 Greece
1 Hungary
1 Ireland
1 Italy
1 Macedonia
1 Netherlands
1 Norway
1 Poland
1 Portugal
1 Romania
1 Spain
1 Sweden
2 Afghanistan
2 China
2 India
2 Iraq
2 Israel
2 Korea
2 Pakistan
2 Taiwan
2 United_States
2 Vietnam
3 Argentina
3 Australia
3 Brazil
3 Canada
3 Japan
3 Mexico
3 New_Zealand
3 Switzerland
4 Albania
4 Algeria
4 Angola
4 Armenia
4 Azerbaijan
4 Bangladesh
4 Bolivia
4 Cambodia
4 Chile
4 Colombia
4 Croatia
4 Cuba
4 Cyprus
4 Czech_Republic
4 Ethiopia
4 Fiji
4 Finland
4 Georgia
4 Ghana
4 Guinea
4 Iceland
4 Indonesia
4 Iran
4 Kenya
4 Kosovo
4 Lebanon
4 Libya
4 Lithuania
4 Malaysia
4 Malta
4 Morocco
4 Nepal
4 Nigeria
4 Panama
4 People's_Republic_of_China
4 Peru
4 Philippines
4 Samoa
4 Serbia
4 Singapore
4 Slovakia
4 Sudan
4 Syria
4 Tanzania
4 Thailand
4 Turkey
4 Uganda
4 Ukraine
4 Uruguay
4 Venezuela
###データを分類する手法
データの分類には、大きくクラシフィケーション（classification、クラス分類）とクラスタリング（clustering）という2つの手法があります。
####クラシフィケーション（classification、クラス分類）
クラシフィケーションは、事前にグループ（class）を定義しておく方法で、例えばニュースを「政治」、「経済」、「スポーツ」などの事前定義のグループに振り分ける時に使います。クラス分類とも呼ばれます。
####クラスタリング（clustering）
クラスタリングは、事前のグループの定義はせず、似た者同士の塊（cluster、クラスター）を抽出する手法です。大量のデータを分析する時に、1つ1つは見ていられないのでざっくり似たような塊にまとめさせて、その塊ごとに性質や傾向を見てみよう、みたいな使い方をします。
今回の問題は5つに分けろというだけで、どのようなグループに？という定義はありません。そのためクラスタリングを使います。
クラスタリングの手法は、今回使うK-Meansのような非階層的クラスタリングと、次の問題98で使うWard法のような階層的クラスタリングに分かれます。
###K-Meansクラスタリング
K-Meansの基本アルゴリズムは単純です。
まず最初に指定された数のクラスターの中心をベクトル空間上に適当に選びます。そして、各データに対して各クラスターの中心までの距離を調べ、中心が一番近いクラスターに振り分けます。これで1回目の振り分けが完了です。
振り分け終わったら、今度はクラスターごとに所属するデータの平均点を調べて、そのクラスターの新たな中心点とします。
ここでデータの振り分けを一度リセットし、再び各データに対して、各クラスターの新しい中心までの距離を調べ、中心が一番近いクラスターに振り分け直します。これで2回目の振り分けが完了です。
これを中心がほとんど移動しなくなるまで繰り返せば完了です。
K-Meansの解説はググるとたくさん出てきますので、詳細は割愛します。CourseraのMachine LearningではWeek8で学べます。
###K-Meansの実装
K-Meansによるクラスタリングは、問題85で使い始めたscikit-learnを使うと簡単です。
sklearn.cluster.KMeansクラスでクラスターの数を指定し、fit_predict()で行列を渡せばクラスタリングが実行されて、各行に対する分類番号の配列（値の範囲は0からクラスター数-1）を取得できます。
なお、最初に選ばれるクラスターの中心点はランダムです。そのため、実行の度に微妙に結果が変わることがあります。変えたくない場合は、sklearn.cluster.KMeansのrandom_stateを指定することで乱数のシード値を指定できます。
今回のプログラムでは、分類番号でソートして表示してみました。ただ、結果を見ても、どんな切り口で分類されたのかイマイチ分かりません。なんとなく分類番号1はヨーロッパの国が集まっているようですが「Republic_of_Austria」などの正式名では分類番号0になってしまっています。「United_States_of_America」と「United_States」も別の分類ですね。問題96の国の抽出がイマイチだったかも...
98本目のノックは以上です。誤りなどありましたら、ご指摘いただけますと幸いです。
実行結果には、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を加工して作成しています。