KBSIs' Blog

Technical memo, play diary

K近傍法をスクラッチ実装してみる

K近傍法をスクラッチ実装する(numpyを用いて)

IDICHI

k近傍法とはなにか

クラス分類の機械学習の一種のアルゴリズムのこと.
k近傍法は学習させるデータ(クラス属性含めて)一つ一つに対して入力データとの類似度(距離)を求め,類似度が高いデータのクラスを入力データのクラスとする.
手順は

  1. すべてのデータに対して類似度を求め,高いものから順にk個データを選ぶ.
  2. それらのデータのクラスを多数決で決定し,そのクラスとする.

なお,距離はユークリッド距離でもよいし,マハラノビス距離でもよい(らしい)
kの値は,線形探索や,交差検証などによって,決定する.(ハイパラメータなので)

スクラッチ実装

上記手順を見ればまったく難しくなさそうなので,簡単に実装してみる.

import numpy as np
## データとクラス(属性)の構造体替わり
class Data:
    def __init__(self,vec:np.array,spector:str) -> None:
        self.vec=vec
        self.spec=spector

## 学習データ
A=np.random.randint(0,100,(10))
B=np.random.randint(0,100,(10))
C=np.random.randint(0,100,(10))
D=np.random.randint(0,100,(10))
E=np.random.randint(0,100,(10))

VectorsArray=[Data(A,'A'),Data(B,'B'),Data(C,'A'),Data(D,'B'),Data(E,'A')]

## 類似度(ユークリッド距離)を求める関数
def getDistance(vec:np.array,vec2:np.array):
    r=np.linalg.norm(vec-vec2,ord=2)
    return r


'''
- K近傍法メインルーチン
引数
vec:入力データ(np.array)
VectorsArray:Data構造体のリスト
k : 整数

返却値
{str(クラス):count(クラスの数)...}
利用時は,max関数でkeyを指定する.
詳細は__main__()で
'''
def getNearVecSpec(vec:np.array,VectorsArray=VectorsArray,k=3)  :
    distance=[]
    for v in VectorsArray:
        d=getDistance(vec,v.vec)
        distance.append((v.spec,d))
    distance.sort(key=lambda X: X[1])
    print(distance)
    diss={}
    for i in range(k):
        v=distance[i]
        spec=v[0]
        if spec in diss:
            diss[spec]+=1
        else:
            diss[spec]=1
    
    return diss
if __name__ == "__main__":
    a=np.random.randint(0,100,size=(10))
    d=getNearVecSpec(a)
    print("予測されたクラス:",max(d,key=d.get))

愚直に実装するとこういう感じになるが,
Numpyのブロードキャストを使えば簡潔で高速動作可能なプログラムになるだろう.

スクラッチ実装とsklearn実装との比較

sklearnはPythonの機械学習ライブラリで,非常に有名である.
今回はそれのk近傍法とスクラッチ実装を比較してみる.
実用性があるか確認するため,比較にはirisデータセットを用いる

同じ結果になることを確認した.

Recent posts

See more

Categories

About

大学2年生 伊地知 翔也 詳細はlearn moreから