読者です 読者をやめる 読者になる 読者になる

データ・サイエンティストは可視化の夢を見るか?

Does Data Scientist Dream of Visualization?

ひきつづき併読してみる —— k 最近傍法——

前掲書を読み進めています。第 12 章 “k-Nearest Neighbours” (k 最近傍法)です。

Data Science from Scratch

Data Science from Scratch


先ず、概説を『朱鷺の杜』から引用してきます。
朱鷺の杜Wiki

k 最近傍法 (k-nearest neighbor method)
クラスのラベルが付加された訓練事例が与えられているクラス分類の場合: 分類したい事例から近い方から順にk個の事例を見つける.これら,k個の事例のうち,最も多数をしめるクラスに分類する.

各データ点での関数値が付加された訓練事例が与えられている回帰分析の場合: 分類したい事例から近い方から順にk個の事例を見つける. これら,k個の事例の関数値を,その事例までの距離に対して減少するような重みをつけた,加重平均して推定値とする.

分類のたびに訓練事例全体を走査するため,分類に必要な計算量は大きい. 事前に学習を全く行わず,蓄えた訓練事例から直接,計算するので,こうした手法をメモリベース (memory-based) 法やアプローチと呼ぶ. k=1のときを特に 最近傍法 (nearest neighbor method) という. 単純な方法だが,その予測精度は結構よい.

成る程、「『隣近所』の動向をうかがって多数決で決める」——みたいなイメージを持ちました。


では、“Data Science from Scratch” のソースコードを写経したうえで、例題を解いた結果を示します。
最初にこれが基礎となる入力データです。
f:id:renpoo:20160830200335p:plain

全米 75 都市に『R, Python, Java』それぞれのユーザーが分布している(人工?)データです。
これを k-NN 法の関数で分類してやります。
そして計算結果を再度入力データと照らし合わせ、正答数を算出してみます。

def knn_classify(k, labeled_points, new_point):
    """each labeled point should be a pair (point, label)"""
    
    # order the labeled points from nearest to farthest
    by_distance = sorted(labeled_points,
                        key = lambda point_label: distance(point_label[0], new_point))
    
    # find the labels for the k closest
    k_nearest_labels = [label for _, label in by_distance[:k]]
    
    # and let them vote
    return majority_vote( k_nearest_labels )

そこで「参照する近隣ノードの数: k」は 1, 3, 5, 7 のそれぞれを与えて比較してみます。
結果グラフは以下の 4 種です。
但し、グラフは Photoshop で透明度を調整して合成してみました。75 都市とその分類との一致・不一致が多少は解りやすくなるといいのですが…。

正答数: 1 neighbor[s]: 40 correct out of 75

f:id:renpoo:20160830202829j:plain

正答数: 3 neighbor[s]: 44 correct out of 75

f:id:renpoo:20160830202901j:plain

正答数: 5 neighbor[s]: 41 correct out of 75

f:id:renpoo:20160830202930j:plain

正答数: 7 neighbor[s]: 35 correct out of 75

f:id:renpoo:20160830203330j:plain


k の数が多ければ分類が正しくなる、というものでもありませんね。
塗り絵を塗り分けているみたいな感じですが、その分布のちがいを言葉であらわすのはなかなか難しいものがあります。

ただ、

  1. k 個の近傍ノードを距離に従って pick up して
  2. その多数決から自己ノードのラベルを決定し
  3. 近傍ノードとのあいだを(線形補間で)塗り分ける

といった次第で『ラベルの分類・予測をしている』と理解しました。


正直、こんな初歩的なことをいまさらやり直している自分を率直に恥じています。しかし、将来の役に立ちそうなことを勉強するのは楽しいですね。それも簡素なソースコードを写経しながら進めているので、いかに簡単なコードから統計分析の基礎が成り立っているか解って、非常に勉強になります。Jupyter ではデバッグ環境がありませんが、ソースコードの好きな場所にデバッグ・プリント文を書き込んでやれば、計算途中の変数(往々にして list)の内容をプリントしてチェックできます。
ですからこのまま、ただ急ぎ足で独習を進めます。