素人の言語処理100本ノック:97


[言語処理100本ノック 2015](http://www.cl.ecei.tohoku.ac.jp/nlp100/)の挑戦記録です。環境はUbuntu 16.04 LTS ＋ Python 3.5.2 \:\: Anaconda 4.1.1 (64-bit)です。過去のノックの一覧は[こちら](http://qiita.com/segavvy/items/fb50ba8097d59475f760)からどうぞ。

## 第10章: ベクトル空間法 (II)
>第10章では，前章に引き続き単語ベクトルの学習に取り組む．

### 97. k-meansクラスタリング
>96の単語ベクトルに対して，k-meansクラスタリングをクラスタ数$ k=5 $として実行せよ．

#### 出来上がったコード：

```python:main.py
# 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の分類番号と国名をタブ区切りで出力しています。

```console:実行結果
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](https://www.coursera.org/learn/machine-learning)ではWeek8で学べます。

### K-Meansの実装
K-Meansによるクラスタリングは、[問題85](http://qiita.com/segavvy/items/f1a7f3200c3b771e8568)で使い始めた[scikit-learn](http://scikit-learn.org/stable/)を使うと簡単です。
[`sklearn.cluster.KMeans`](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html)クラスでクラスターの数を指定し、[`fit_predict()`](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html#sklearn.cluster.KMeans.fit_predict)で行列を渡せばクラスタリングが実行されて、各行に対する分類番号の配列（値の範囲は0からクラスター数-1）を取得できます。

なお、最初に選ばれるクラスターの中心点はランダムです。そのため、実行の度に微妙に結果が変わることがあります。変えたくない場合は、[`sklearn.cluster.KMeans`](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html)の`random_state`を指定することで乱数のシード値を指定できます。

今回のプログラムでは、分類番号でソートして表示してみました。ただ、結果を見ても、どんな切り口で分類されたのかイマイチ分かりません。なんとなく分類番号1はヨーロッパの国が集まっているようですが「Republic_of_Austria」などの正式名では分類番号0になってしまっています。「United_States_of_America」と「United_States」も別の分類ですね。[問題96](http://qiita.com/segavvy/items/650c3e1254d8c5aef8e1)の国の抽出がイマイチだったかも...

　
98本目のノックは以上です。誤りなどありましたら、ご指摘いただけますと幸いです。
<hr>

*実行結果には、[100本ノックで用いるコーパス・データ](http://www.cl.ecei.tohoku.ac.jp/nlp100/#data)で配布されているデータの一部が含まれます。この第10章で用いているコーパス・データのライセンスは[クリエイティブ・コモンズ 表示-継承 3.0 非移植](https://creativecommons.org/licenses/by-sa/3.0/legalcode)（[日本語訳](https://creativecommons.org/licenses/by-sa/3.0/deed.ja)）です。また、国名の一覧は、「KIDS外務省 - 世界の国々」（外務省）（[http://www.mofa.go.jp/mofaj/kids/ichiran/index.html](http://www.mofa.go.jp/mofaj/kids/ichiran/index.html)）と、[nationsonline.org](http://www.nationsonline.org/index.html)の[Countries and Regions of the World from A to Z](http://www.nationsonline.org/oneworld/countries_of_the_world.htm)を加工して作成しています。*