k-NNとは？
突然ですが、皆さんは巡回セールスマン問題(TSP)は知っていますか。 最短経路問題の一つですが、その経路決定アルゴリズムの一つに最近傍法というのがあります。 これは現在いる地点から一番近い地点へと経路を決定するアルゴリズムですが、機械学習にも似たようなアルゴリズムが存在します。 それがk近傍法、k-NNと略されるアルゴリズムです。
教師あり学習
k-NNは教師あり学習のアルゴリズムの一つです。 さて、教師あり学習とはなんでしょうか。 教師あり学習は主に未知のデータや将来のデータを予測できるように既知のデータを用いて学習をする機械学習の種類の一つです。 既知のデータから学習するためそのデータを教師に見立てて教師データと呼ぶことにします。
教師ありデータでは予測したいデータを目標変数、その予測に使うデータを説明変数と言います。 目標変数と説明変数の間になにか関係があって、それを数式、あるいは関数として表せないかという問題を扱う分野です。 他にも教師なし学習や強化学習が機械学習の主な種類としてあげられます。
分類と回帰
教師あり学習には大きく分けて二つの分野が存在します。 分類と回帰です。 違いは目標変数が離散値であるか連続値であるか、ということです。 目標変数が離散値をとる場合、教師あり学習で予測したいものは入力したデータがどの値に分類されるかということです。 ]
よって目標変数が離散値である場合を分類(Classification)と言います。 目標変数が連続値をとる場合、目標変数と説明変数との間には数学的関係が存在するのではないか、私たちの多くはそう考えることでしょう。 回帰(Regression)はそうした数学的関数を識別関数として探索し、その識別関数からデータを予測しようとすることを指します。
“怠惰”学習
k-NNは怠惰学習(lazy learner)という学習アルゴリズムの代表例です。 怠惰というのは教師データから識別関数、つまり入力されるデータを直接分類する関数を学習しないということです。
ではどのように分類を行っているのかというと、入力されたデータと類似している上位k個の教師データを参照し、そのデータグループの中で一番多く分類されているクラスに分類するという方式を取っています。 機械学習のアルゴリズムですが教師データを丸暗記するような挙動をとる特徴的なアルゴリズムなんです。
Pythonによるk-NN分類器実装
k-NNを使った分類予測をPythonを使って実装してみます。 機械学習ではscikit-learnというPythonのモジュールが便利です。 まずはプログラムの全容から。
import requests
import io
import pandas as pd
from sklearn import preprocessing
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt
vote_data_url = "https://archive.ics.uci.edu/ml/machine-learning-databases/voting-records/house-votes-84.data"
s = requests.get(vote_data_url).content
vote_data = pd.read_csv(io.StringIO(s.decode('utf-8')),header=None)
vote_data.columns = ['Class Name',
'handicapped-infants',
'water-project-cost-sharing',
'adoption-of-the-budget-resolution',
'physician-fee-freeze',
'el-salvador-aid',
'religious-groups-in-schools',
'anti-satellite-test-ban',
'aid-to-nicaraguan-contras',
'mx-missile',
'immigration',
'synfuels-corporation-cutback',
'education-spending',
'superfund-right-to-sue',
'crime',
'duty-free-exports',
'export-administration-act-south-africa']
label_encode = preprocessing.LabelEncoder()
vote_data_encode = vote_data.apply(lambda x: label_encode.fit_transform(x))
X = vote_data_encode.drop('Class Name', axis=1)
Y = vote_data_encode['Class Name']
X_train, X_test, y_train, y_test = train_test_split(X,Y, random_state=50)
training_accuracy = []
test_accuracy = []
neighbors_settings = [i for i in range(1, 30)]
for n_neighbors in neighbors_settings:
clf = KNeighborsClassifier(n_neighbors = n_neighbors)
clf.fit(X_train, y_train)
training_accuracy.append(clf.score(X_train, y_train) * 100)
test_accuracy.append(clf.score(X_test, y_test) * 100)
plt.plot(neighbors_settings, training_accuracy,label='教師用データの正解率')
plt.plot(neighbors_settings, test_accuracy,label='テスト用データの正解率')
plt.ylabel('正解率')
plt.xlabel('分類に使ったデータの数')
plt.legend()
plt.show()
モジュールの読み込み
import requests
import io
import pandas as pd
from sklearn import preprocessing
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt
今回のプログラムで使うデータはオンラインに公開されているデータを使うため取得するために標準モジュールのrequestsとioを使っています。 pandasは機械学習に使うデータとして扱いやすくするよう加工するために用います。
sklearnはscikit-learnのことで機械学習のためのモジュールです。 このモジュールから様々なアルゴリズムを読み込むことができますが今回はKNNのみです。 最後にグラフを表示させるためにmatplotlibを読み込んでいます。
データの読み込みと前処理
vote_data_url = "https://archive.ics.uci.edu/ml/machine-learning-databases/voting-records/house-votes-84.data"
s = requests.get(vote_data_url).content
vote_data = pd.read_csv(io.StringIO(s.decode('utf-8')),header=None)
vote_data.columns = ['Class Name',
'handicapped-infants',
'water-project-cost-sharing',
'adoption-of-the-budget-resolution',
'physician-fee-freeze',
'el-salvador-aid',
'religious-groups-in-schools',
'anti-satellite-test-ban',
'aid-to-nicaraguan-contras',
'mx-missile',
'immigration',
'synfuels-corporation-cutback',
'education-spending',
'superfund-right-to-sue',
'crime',
'duty-free-exports',
'export-administration-act-south-africa']
label_encode = preprocessing.LabelEncoder()
vote_data_encode = vote_data.apply(lambda x: label_encode.fit_transform(x))
X = vote_data_encode.drop('Class Name', axis=1)
Y = vote_data_encode['Class Name']
X_train, X_test, y_train, y_test = train_test_split(X,Y, random_state=50)
今回のデータはUCI Machine Learning RepositoryにあるCongressional Voting Records datasetを用いました。 これはアメリカ合衆国下院議会において議員が共和党員か民主党員かという立場と議員が政策に対してどのように投票したかということをまとめたデータセットです。
詳しくは以下のリンクを参照してください。
UCI Machine Learning Repository: Congressional Voting Records Data Set
取得してきたデータセットはClass Nameと名付けた項は’democrat'(民主党員)、’republican'(共和党員)のどちらかが、それ以外の項は’y'(yes)、’n'(no)、そして’?‘のどれかが入っています。 このままだと使いづらいので(‘democrat’, ‘republican’) = (0, 1)、(‘?’, ‘n’, ‘y’) = (0, 1, 2)というように数字に変換します。
今回のデータでは分類したい目標はClass Name、そのために使うデータはそれ以外として分類を行うことにします。 つまり、分類を予測したいものは民主党員であるか、共和党員であるかということで、そのために使うデータは教育や保険などの13の政策に対して議員が賛成、反対のどちらに票を投じたのかという投票記録です。
本当はここでデータの選択をするべきですが、入門なのでそこは気にせずやっていきます。 scikit-learnのtrain_test_split関数を使って教師データとテストデータに分割します。 こうして得られたX_trainとy_trainを使って学習をします。
k-NNによる分類と正解率の表示
training_accuracy = []
test_accuracy = []
neighbors_settings = [i for i in range(1, 30)]
for n_neighbors in neighbors_settings:
clf = KNeighborsClassifier(n_neighbors = n_neighbors)
clf.fit(X_train, y_train)
training_accuracy.append(clf.score(X_train, y_train) * 100)
test_accuracy.append(clf.score(X_test, y_test) * 100)
plt.plot(neighbors_settings, training_accuracy,label='教師用データの正解率')
plt.plot(neighbors_settings, test_accuracy,label='テスト用データの正解率')
plt.ylabel('正解率')
plt.xlabel('分類に使ったデータの数')
plt.legend()
plt.show()
k-NN分類器の実装そのものはとてもシンプルです。clf = KNeighborsClassifier() たったこれだけです。
自分で実装する場合はそれなりに数学の知識が必要になりますが、とにかくこれで分類器が作成できました。
続いてfitメソッドを用いて分類器に学習させます。
これで分類器がどのようなデータをどう分類すればいいのか学習します。
あとはデータを使って予測をさせるだけです。 今回は正解率をグラフにプロットするためにscoreメソッドを用いていますが、分類の予測結果が欲しい場合はpridictメソッドを使います。
実行結果
画像を見てみると正解率にブレはあるものの、おおよそkの値が3か4で一番正解率が高く、kの値が大きくなるに従って正解率が下がっているのがわかります。 k-NNにおいては、kの値が大きくなるとデータの類似度がそんなに高くないデータも類似データとして識別処理に使われることになります。
その結果として、分類クラスの境界線が曖昧になってしまうという問題が発生します。 kの値は参照するデータなどにより変えるのが一般的です。
また、正解率がおおよそ90%を超えているのも画像から読み取れますね。 かなり直感的なように思えるこのアルゴリズムですが、機械学習として強力なアルゴリズムであることが分かっていただけたでしょうか？
参考文献
今回記事を作成するにあたり、以下の本を参考にさせていただきました。 Amazon CAPTCHA
