end0tknr's kipple - 新web写経開発

http://d.hatena.ne.jp/end0tknr/ から移転しました

pythonでのk近傍法( k-nearest neighbor algorithm, k-NN )

O'Reilly Japan - 実践 コンピュータビジョン

実践コンピュータビジョン サンプルプログラム

相変わらずの上記urlの写経。

k近傍法とは?

次のurlが視覚的にもとっても分かりやすいです

qiita.com

教師データとテストデータの作成

…といっても、中身は同じである points_normal.pkl と points_normal_test.pkl が 以下のscriptで作成されます。

#!/usr/local/bin/python
# -*- coding: utf-8 -*-
import numpy
import pickle

n = 200

def main():
    #2組の点の集合が距離を置いて配置
    make_dots_pair_1()
    #1組の点の集合のまわりに、もう1組の点の集合を
    #土星の輪のように配置
    make_dots_pair_2()

def make_dots_pair_1():
    # 標準正規分布による nx2 の行列
    class_1 = 0.6 * numpy.random.randn(n,2)
    class_2 = 1.2 * numpy.random.randn(n,2) + numpy.array([5,1])
    # ones()で作成した要素が全てnの配列を hstack()で連結
    labels = numpy.hstack((numpy.ones(n),-numpy.ones(n)))

    # pickleで保存
    with open('points_normal.pkl', 'w') as f:
        pickle.dump(class_1,f)
        pickle.dump(class_2,f)
        pickle.dump(labels,f)
    with open('points_normal_test.pkl', 'w') as f:
        pickle.dump(class_1,f)
        pickle.dump(class_2,f)
        pickle.dump(labels,f)

def make_dots_pair_2():
    # 正規分布と、その周りに輪を描くように点を配置
    class_1 = 0.6 * numpy.random.randn(n,2)
    r = 0.8 * numpy.random.randn(n,1) + 5
    angle = 2*numpy.pi * numpy.random.randn(n,1)
    class_2 = numpy.hstack((r*numpy.cos(angle),r*numpy.sin(angle)))
    labels = numpy.hstack((numpy.ones(n),-numpy.ones(n)))
    # pickleで保存
    with open('points_ring.pkl', 'w') as f:
        pickle.dump(class_1,f)
        pickle.dump(class_2,f)
        pickle.dump(labels,f)

if __name__ == '__main__':
    main()

k-NN実行

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy
import pickle
import matplotlib
matplotlib.use('Agg')
import matplotlib.pylab as plb

KNN_MODEL = None

def load_model_and_test_data():
    # pickleからmodel dataをload
    with open('points_normal.pkl', 'r') as f:
        class_1 = pickle.load(f)
        class_2 = pickle.load(f)
        labels = pickle.load(f)
        # k近傍法でクラスタリングするmodel作成
        global KNN_MODEL
        KNN_MODEL = KnnClassifier(labels, numpy.vstack((class_1,class_2)))

    # pickleからtest dataをload
    with open('points_normal_test.pkl', 'r') as f:
        class_1 = pickle.load(f)
        class_2 = pickle.load(f)
        labels = pickle.load(f)

    return class_1, class_2, labels


# 描画用関数の定義
def my_classify(x,y):
    return numpy.array([KNN_MODEL.classify([xx,yy]) for (xx,yy) in zip(x,y)])


def plot_2D_boundary(plot_range,points,decisionfcn,labels,values=[0]):
    """ plot_range:(xmin,xmax,ymin,ymax)、points:クラスの点のリスト、
    decisionfcn:評価関数、
    labels:各クラスについてdecisionfcnが返すラベルのリスト、
    values:表示する判別の輪郭のリスト """

    clist = ['b','r','g','k','m','y'] # 各classの描画色

    # 等差数列( arange() )からmeshgrid作成
    x = numpy.arange(plot_range[0],plot_range[1],.1)
    y = numpy.arange(plot_range[2],plot_range[3],.1)
    xx,yy = numpy.meshgrid(x,y)
    xxx,yyy = xx.flatten(),yy.flatten()
    zz = numpy.array(decisionfcn(xxx,yyy))
    zz = zz.reshape(xx.shape)
    
    plb.contour(xx,yy,zz)   #等高線描画

    # クラスごとに正しい点には*、間違った点には'o'を描画する
    for i in range(len(points)):
        d = decisionfcn(points[i][:,0],points[i][:,1])
        correct_ndx = labels[i]==d
        incorrect_ndx = labels[i]!=d
        plb.plot(points[i][correct_ndx,0],points[i][correct_ndx,1],
                 '*',color=clist[i])
        plb.plot(points[i][incorrect_ndx,0],points[i][incorrect_ndx,1],
                 'o',color=clist[i])

    plb.axis('equal')


class KnnClassifier(object):
  def __init__(self,labels,samples):
    """ 教師データを使って分類器を初期化する """
    self.labels = labels
    self.samples = samples

  def classify(self,point,k=3):
    """ pointを教師データ中のk個の最近傍を使って分類し、
        ラベルを返す """

    # 全教師データへの距離を計算する
    dist = numpy.array([L2dist(point,s) for s in self.samples])
    # ソートする
    ndx = dist.argsort()
    # k個の最近傍を保持するのに辞書を用いる
    votes = {}
    for i in range(k):
      label = self.labels[ndx[i]]
      votes.setdefault(label,0)
      votes[label] += 1

    return max(votes, key=lambda x: votes.get(x))

def L2dist(p1,p2):
  return numpy.sqrt( sum( (p1-p2)**2) )


def main():
    class_1, class_2, labels = load_model_and_test_data()
    # 分類の境界を描画
    plot_2D_boundary([-6,6,-6,6], [class_1,class_2], my_classify,[1,-1])
    plb.savefig( '8_1_1.png' )


if __name__ == '__main__':
    main()

↑こう書くと↓こう出力されます f:id:end0tknr:20170923112633p:plain