学生による学生のためのデータサイエンス勉強会

【さきどりPython#6】scikit-learnでK-最近傍法を実装しながら、特徴やアルゴリズムを学んでみた

 5/16の先取りPython勉強会がありました。今日のLTで、オイラー法を使用した物理計算を実装している方がいて、私が3年生の時に「数値計算プログラミング」という授業で見たような見てないようなことを既に実装している方がいて驚きました(;゚Д゚)。

 さて、私はというと輪読でK-NNの発表を行いました。「K-最近傍法ってK-平均法と何が違うの?」、「なんか教師なし学習のイメージがある」と発表前の私はこのレベルでしたが、機械学習クックブックをベースにアルゴリズムと実装を調べて発表しました。今回はそれを記事にまとめてみようと思います。

 今回はまず、K-NNの概要とscikit-learnでの実装、そして、アルゴリズムを見ていきたいと思います。

K-最近傍法(K-NN)とは

 まず、先ほどからずっとK-NNと言っていますが、K-NNというのはそもそも、K-最近傍法といい、英語ではK-Nearest Neighbors(K-NN)と言います。主な特徴としては以下の点があります。

  • 教師あり学習
  • 分類タスクのみ対象
  • 遅延学習(怠惰学習)器の一つ

 K-NNとは、教師あり学習であり、基本的に分類タスクを対象とします。また、遅延学習器(怠惰学習)器という特徴を持ち、訓練のための計算を行わず、予測の時になって初めて計算を行うものになります。(「怠惰学習」で検索した方が引っかかる)
 
 K-NNの基本的な特徴は以上になります。次にどのように予測・分類を行うのかの流れを見ていきたいと思います。

K-NNの概観

 K-NNの分類方法を具体例で示します。
 例えば、以下のように学習データのクラス(1~3)が散らばっている空間があるとします。ここで、「」が分類したいデータになります。K-NNでは、「」とその他の「1,2,3」のデータとの距離を計算し、近いものをk個取り出します。その中から一番多いクラスを「」のクラスとします。以下の例では、k=5として、抜き出したクラスの中で、「1」が一番多くなっているので、「」のクラスは「1」と分類されることになります。
 これが基本的なK-NNの基本的な分類方法になります。

scikit-learnでのK-NNの実装

 ここで、一度scikit-learnのKNeighborsClassifierでの実装を見てみましょう。このプログラムは「機械学習クックブック」のレシピ15.02のプログラムになっています。データセットはirisを使用しています。

# ライブラリをロード
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn import datasets

# データをロード
iris = datasets.load_iris()
X = iris.data
y = iris.target

# 標準化器を作成
standardizer = StandardScaler()

# 特徴量を標準化
X_std = standardizer.fit_transform(X)

# 近傍値数を5に指定してKNNクラス分類器を訓練
knn = KNeighborsClassifier(n_neighbors=5, n_jobs=-1).fit(X_std, y)

# 2つの観測値を作成
new_observations = [[ 0.75,  0.75,  0.75,  0.75],
                    [ 1,  1,  1,  1]]

# 2つの観測値のクラスを予測
knn.predict(new_observations)

 以上の実装を見ると、データを読み込んだ後に特徴量の標準化を行っています。その後、knn = KNeighborsClassifier(n_neighbors=5,n_jobs=-1).fit(X_std, y)で、k(n_neighbors)の値と計算に使うCPUコア(n_jobs)を指定し、標準化した学習データと正解ラベルをknnインスタンスに持たせています。また、.fitとなっていますが、ここでは、特に訓練のための計算を行っている訳ではありません。パラメータを設定したり、学習データを持たせているだけという認識が正しいかもしれません。最後に、観測値を2つ用意し、predictメソッドで、クラス分類を行っています。

K-NNのアルゴリズムの詳細

 さて、scikit-learnでの実装を見たところで、K-最近傍法の詳細なアルゴリズムをを見ていきましょう。K-NNのアルゴリズムは以下の通りです。

  1. 学習データの特徴量のベクトル化標準化
  2. 分類したいデータと学習データとの距離(類似度)を計算する
  3. 距離の近い(類似度の高い)データをk個取り出して多数決で分割する
  4. 最も性能の良いkを調べる

 このアルゴリズムについて、実装を踏まえながらもう少し詳細に述べたいと思います。

学習データの特徴量をベクトル化と標準化

 まず、初めに学習データの特徴量のベクトル化と標準化というところです。ここで重要な点は以下の点です。

  • 特長量の数(n個)に応じて、n次元ベクトルを作成する
  • 特長量の標準化

 以上の2つについて、具体的に説明していきます。

特長量の数(n個)に応じて、n次元ベクトルを作成する

 特徴量の数(n個)に応じて、n次元の位置ベクトルを作成すると、n次元の特徴量空間が出来ることになります。例えば、irisデータセットには4つの特徴量があるので、4次元の特徴量空間が出来ます。ただ、4次元空間は可視化出来ないので、特徴量が2つの場合と3つの場合で、特徴量空間を見てみます。色分けは、各々「赤:Iris-Setosa」「青:Iris-Versicolor」「緑:Iris-Virginica」となっています。

 以上が2次元と3次元の特徴量空間になります。4次元空間についても可視化出来ないだけで、上記のような感じの空間が作られることになります。そして、次のステップで、この空間内での分類したいデータと学習データの距離(類似度)を計算することになります。

 この特徴量のベクトル化は実装上では、特に処理を行っているわけではありません。これは、iris.dataが1データ(行)ごとに、[sepal length (cm), sepal width (cm), petal length (cm), petal width (cm)]とベクトルとみなせる形式になっているためです。

特長量の標準化

 次に、学習データの特徴量の標準化についてです。まず標準化とは何かと言うと、あるデータ群の平均と分散(と標準偏差)を変換する操作のことを言います。標準化では、平均0と分散(と標準偏差)1の分布になるように変換する場合が多いようです。

 標準化の式は、\(Y\):変換後のデータ, \(X\):変換前のデータ, \(\mu:X\)の平均, \(\sigma:X\)の標準偏差として、以下のようになります。
$$Y=\frac{X-\mu}{\sigma}$$
 このようにすることで、特徴量ごとに異なるデータの単位を、揃えて比較できるようになります。先述した特徴量空間の図は標準化したものをプロットしているので、特徴量の値が0を中心(平均になっています)とした分布になっていることが確認できます。

 実装上では、scikit-learnのStandardScalerによって、標準化を行っています。こちらのクラスやパラメータの説明は次のWebページが分かりやすかったです。Scikit-learnでデータのスケール変換(前処理)する – Helve’s Python memo

分類したいデータと学習データとの距離(類似度)を計算する

 特徴量のベクトル化と標準化、いわゆる前処理が終わったところで、次に、実際に分類をしていきます。ここでは、先ほど作った特徴量空間における、分類したいデータと学習データとの距離を計算します。

 scikit-learnではデフォルトで距離計算に、ミンコフスキー(Minkowski)距離を使用します。\(n\):特徴量の数として、
$$d_{manhattan}=(\sum^{n}_{i=1}|x_i-y_i|^p)^{\frac{1}{p}}$$
 また、scikit-learnには\(p\)のパラメータも設定でき、デフォルトでは\(p=2\)となっているため、自動的に、ユークリッド距離を使用していることになります。
 ユークリッド距離は以下のような式です。
$$d_{euclidean}=\sqrt{\sum^{n}_{i=1}(x_i-y_i)^2}$$
 色々と調査するにあたって、距離計算にはユークリッド距離が良く利用されているということなので、基本的にはデフォルトのままで問題ないかと思われます。

 この距離の計算は、実装上の、knn.predict(new_observations)で行っていますが、距離計算に何を使用するかは、knn = KNeighborsClassifier()の箇所で指定することになります。

距離の近い(類似度の高い)データをk個取り出して多数決で分割する

 さて、距離の計算が出来たら、次は取り出したk個のデータで多数決を行うことになります。これは説明するまでもなく、そのままの意味になります。

 実装上では、knn = KNeighborsClassifier(n_neighbors=5)n_neighbors=5がkの数を指定している処理に相当します。また、デフォルトではn_neighbors=5が設定されています。そして、分類時、つまりknn.predict(new_observations)の箇所で設定したkに応じて多数決を行うことになります。

まとめ

 以上がK-NNの分類までの流れになります。最後に最適なkを指定するということですが、ここは今回の発表では取り扱わなかったことなので、またの機会に私かどなたかがまとめてくれるでしょう。

 最後に、「K-NNって物凄い単純なアルゴリズムだな」というのが率直な感想です。覚えやすい手法である反面、「精度的にどうなの?」感も否めません。もし、あるクラス群とクラス群の境界あたりに分類したいデータが来た場合に、取り出したk個の中に2つのクラスが半々くらいに存在してしまうと間違う確率高くなると思います。正直なところ、あまり使えないのでは感があります。
 また、どうやらK-NNは次元が大きい場合に「次元の呪い」によって、使えなくなるらしいです。

スライド

Cookbook knn-bda-furukawa from FurukawaRyuki

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です