K近隣(KNN)アルゴリズムとpython実現
48101 ワード
1.k近隣モデル
k近隣法、k-nearst neighbor、k-NNは、基本的な分類と回帰のアルゴリズムである.その3つの要素:kの選択、距離判別式、分類決定.k近隣法モデル:N k(x)N_k(x)Nk(x)はxに最も近いk個の点の近傍を表す.y=argmax_;cjΣx j∈N k(x)I(y i=c j)y=mag\max_{c}\sum\limits_{xuj\n Nuka(x)}I(yui=cuj)y=argcj max xj_Nk(x)ΣI(yi=cj)
1、kの値は小さくて、構造が複雑で、似たような誤差が小さいですが、フィッティングしやすいです.大きい値をとると構造が簡単で、似たような誤差が大きい.アプリケーションでは、kは一般により小さい値を選択し、交差検証によって最適なk値を決定することができる.また、kは一般に奇数を取り、カテゴリ数が等しい場合を防止する.
2、距離の測定は普通は欧氏の距離を使って、あるいはもっと一般的なL p L_を使います.p Lp距離ですL p(x 1,x 2)=(Σl≦x l−j l≧p)1/p L_p(x_1,x_2)=(\\sum\limitsðxui^l-xuj^l_p)^{1/p}Lp(x 1,x 2)=(lΣxil−xjl咻p)1/p
ここで、l lは特徴次元を表す.
3、分類決定は多数で採決されます.即ち、k個の一番近い点の種類の多くのその種類です.
2.kdツリー
kdツリー、k-dimentional tree、k次元データ空間を分割するデータ構造.
kdツリーを作成します.1、現在の次元でのデータの中央値に対応するサンプルを親ノードとして選択し、残りのデータを左、右のツリーに分割します.2、現在の次元の次の次元を選択し、左、右のサブツリーに対して1を繰り返します.
最近傍検索:1、対象ノードのkdツリーに対応する「最適リーフノード」を検索します.具体的には、ルートノードから出発し、対象ノードのそれぞれの次元における値に基づいて、葉の結点に分割される.2、上に向かって歩きます特に、「最適リーフノード」から出発し、現在の点が「最適リーフノード」よりもターゲットノードに近い場合、ノードは現在の最適点であり、ノードの兄弟ノードをチェックする.ルートノードまで、検索が終了します.
3.実践
3.1暴力法
暴力法を用いて実現され、N N個のサンプル、D D次元データモデリングのアルゴリズム複雑度O(D N 2)O(DN^2)O(DN 2)は、距離計算時の複雑度O(D N)O(DN)O(DN)O(DN)のために、k個の最も領域を見出すときの複雑度O(N)O(N)O(N)O(N)O(N)O)O(N)O)O(N)O)O)O(N)を見つける.
3.2 kdツリー
kdツリーを定義します.時間複雑度:O[D N log_;(N)]O[D N\log(N)]O[DN log(N)]
kdツリーと蛮力法を比較した運行効率カスタムサンプルセット
参考: zhihu knn; マシンで実戦k-近隣アルゴリズムを学ぶ. slearn.neighbors.KNeighbors Class ifier; slearn Neighbor Algorithms; 百科kd-tree; ギthub imyle kd-tree; ギthb python-kNN;
k近隣法、k-nearst neighbor、k-NNは、基本的な分類と回帰のアルゴリズムである.その3つの要素:kの選択、距離判別式、分類決定.k近隣法モデル:N k(x)N_k(x)Nk(x)はxに最も近いk個の点の近傍を表す.y=argmax_;cjΣx j∈N k(x)I(y i=c j)y=mag\max_{c}\sum\limits_{xuj\n Nuka(x)}I(yui=cuj)y=argcj max xj_Nk(x)ΣI(yi=cj)
1、kの値は小さくて、構造が複雑で、似たような誤差が小さいですが、フィッティングしやすいです.大きい値をとると構造が簡単で、似たような誤差が大きい.アプリケーションでは、kは一般により小さい値を選択し、交差検証によって最適なk値を決定することができる.また、kは一般に奇数を取り、カテゴリ数が等しい場合を防止する.
2、距離の測定は普通は欧氏の距離を使って、あるいはもっと一般的なL p L_を使います.p Lp距離ですL p(x 1,x 2)=(Σl≦x l−j l≧p)1/p L_p(x_1,x_2)=(\\sum\limitsðxui^l-xuj^l_p)^{1/p}Lp(x 1,x 2)=(lΣxil−xjl咻p)1/p
ここで、l lは特徴次元を表す.
3、分類決定は多数で採決されます.即ち、k個の一番近い点の種類の多くのその種類です.
2.kdツリー
kdツリー、k-dimentional tree、k次元データ空間を分割するデータ構造.
kdツリーを作成します.1、現在の次元でのデータの中央値に対応するサンプルを親ノードとして選択し、残りのデータを左、右のツリーに分割します.2、現在の次元の次の次元を選択し、左、右のサブツリーに対して1を繰り返します.
最近傍検索:1、対象ノードのkdツリーに対応する「最適リーフノード」を検索します.具体的には、ルートノードから出発し、対象ノードのそれぞれの次元における値に基づいて、葉の結点に分割される.2、上に向かって歩きます特に、「最適リーフノード」から出発し、現在の点が「最適リーフノード」よりもターゲットノードに近い場合、ノードは現在の最適点であり、ノードの兄弟ノードをチェックする.ルートノードまで、検索が終了します.
3.実践
3.1暴力法
暴力法を用いて実現され、N N個のサンプル、D D次元データモデリングのアルゴリズム複雑度O(D N 2)O(DN^2)O(DN 2)は、距離計算時の複雑度O(D N)O(DN)O(DN)O(DN)のために、k個の最も領域を見出すときの複雑度O(N)O(N)O(N)O(N)O(N)O)O(N)O)O(N)O)O)O(N)を見つける.
from sklearn import datasets
import numpy as np
from sklearn.model_selection import train_test_split
## Example 1: iris for classification( 3 classes)
# X, y = datasets.load_iris(return_X_y=True)
# Example 2
X, y = datasets.load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# my k-NN
class KNN():
def __init__(self,data,K=3):
self.X = data[0]
self.y = data[1]
self.K = K
def fit(self, X_test):
diffX = np.repeat(X_test, len(self.X), axis=0) - np.tile(self.X,(len(X_test),1))
square_diffX = (diffX**2).sum(axis=1).reshape(len(X_test),len(self.X))
sorted_index = square_diffX.argsort()
predict = [0 for _ in range(len(X_test))]
for i in range(len(X_test)):
class_count={}
for j in range(self.K):
vote_label = self.y[sorted_index[i][j]]
class_count[vote_label] = class_count.get(vote_label,0) + 1
sorted_count = sorted(class_count.items(), key=lambda x: x[1],reverse=True)
predict[i] = sorted_count[0][0]
return predict
def predict(self, X_test):
return self.fit(X_test)
def score(self,X,y):
y_pred = self.predict(X)
return 1 - np.count_nonzero(y-y_pred)/len(y)
knn = KNN((X_train,y_train), K=3)
print(knn.score(X_test,y_test))
実行結果:0.9415204678362573
.slearnを使用したAPI:# sklearn API
from sklearn.neighbors import KNeighborsClassifier
neigh = KNeighborsClassifier(n_neighbors=3)
neigh.fit(X_train, y_train)
print(neigh.score(X_test,y_test))
運行結果:0.9415204678362573
kNN法が実現上のkの選択及び距離の定義が一致する限り、結果は全く同じである.3.2 kdツリー
kdツリーを定義します.時間複雑度:O[D N log_;(N)]O[D N\log(N)]O[DN log(N)]
# kd-tree
class KDNode:
'''
vaule: [X,y]
'''
def __init__(self, value=None, parent=None, left=None, right=None, index=None):
self.value = value
self.parent = parent
self.left = left
self.right = right
@property
def brother(self):
if not self.parent:
bro = None
else:
if self.parent.left is self:
bro = self.parent.right
else:
bro = self.parent.left
return bro
class KDTree():
def __init__(self,K=3):
self.root = KDNode()
self.K = K
def _build(self, data, axis=0,parent=None):
'''
data:[X,y]
'''
# choose median point
if len(data) == 0:
root = KDNode()
return root
data = np.array(sorted(data, key=lambda x:x[axis]))
median = int(len(data)/2)
loc = data[median]
root = KDNode(loc,parent=parent)
new_axis = (axis+1)%(len(data[0])-1)
if len(data[:median,:]) == 0:
root.left = None
else:
root.left = self._build(data[:median,:],axis=new_axis,parent=root)
if len(data[median+1:,:]) == 0:
root.right = None
else:
root.right = self._build(data[median+1:,:],axis=new_axis,parent=root)
self.root = root
return root
def fit(self, X, y):
# concat X,y
data = np.concatenate([X, y.reshape(-1,1)],axis=1)
root = self._build(data)
def _get_eu_distance(self,arr1:np.ndarray, arr2:np.ndarray) -> float:
return ((arr1 - arr2) ** 2).sum() ** 0.5
def _search_node(self,current,point,result={},class_count={}):
# Get max_node, max_distance.
if not result:
max_node = None
max_distance = float('inf')
else:
# find the nearest (node, distance) tuple
max_node, max_distance = sorted(result.items(), key=lambda n:n[1],reverse=True)[0]
node_dist = self._get_eu_distance(current.value[:-1],point)
if len(result) == self.K:
if node_dist < max_distance:
result.pop(max_node)
result[current] = node_dist
class_count[current.value[-1]] = class_count.get(current.value[-1],0) + 1
class_count[max_node.value[-1]] = class_count.get(max_node.value[-1],1) - 1
elif len(result) < self.K:
result[current] = node_dist
class_count[current.value[-1]] = class_count.get(current.value[-1],0) + 1
return result,class_count
def search(self,point):
# find the point belongs to which leaf node(current).
current = self.root
axis = 0
while current:
if point[axis] < current.value[axis]:
prev = current
current = current.left
else:
prev = current
current = current.right
axis = (axis+1)%len(point)
current = prev
# search k nearest points
result = {}
class_count={}
while current:
result,class_count = self._search_node(current,point,result,class_count)
if current.brother:
result,class_count = self._search_node(current.brother,point,result,class_count)
current = current.parent
return result,class_count
def predict(self,X_test):
predict = [0 for _ in range(len(X_test))]
for i in range(len(X_test)):
_,class_count = self.search(X_test[i])
sorted_count = sorted(class_count.items(), key=lambda x: x[1],reverse=True)
predict[i] = sorted_count[0][0]
return predict
def score(self,X,y):
y_pred = self.predict(X)
return 1 - np.count_nonzero(y-y_pred)/len(y)
def print_tree(self,X_train,y_train):
height = int(math.log(len(X_train))/math.log(2))
max_width = pow(2, height)
node_width = 2
in_level = 1
root = self.fit(X_train,y_train)
from collections import deque
q = deque()
q.append(root)
while q:
count = len(q)
width = int(max_width * node_width / in_level)
in_level += 1
while count>0:
node = q.popleft()
if node.left:
q.append(node.left )
if node.right:
q.append(node.right)
node_str = (str(node.value) if node else '').center(width)
print(node_str, end=' ')
count -= 1
print("
")
kd = KDTree()
kd.fit( X_train, y_train)
print(kd.score(X_test,y_test))
運転結果:0.9590643274853801
Q 1:なぜ上記暴力法と結果が違うのですか?A 1:上流にさかのぼるプロセスであるべきです.ここでは各ノードの兄弟ノードに対して距離を計算します.兄弟ノードが現在の最適ノードであれば、下に検索を続けませんでした.正しいやり方は、現在のノードが最適点である場合、兄弟ノードを検索し、兄弟ノードが最適点になったら、その兄弟ノードを下に検索します.kdツリーと蛮力法を比較した運行効率カスタムサンプルセット
# Example 3
X, y = datasets.make_blobs(n_samples=10000, centers=3,
n_features=3, random_state=0)
import time
#
st = time.time()
knn = KNN((X_train,y_train), K=3)
print(knn.score(X_test,y_test))
et = time.time()
print("use", et-st)
# kd tree
st = time.time()
kd = KDTree()
kd.fit( X_train, y_train)
print(kd.score(X_test,y_test))
et = time.time()
print("use", et-st)
実行結果:#
0.9993333333333333
use 2.8174679279327393
# kd tree
0.9973333333333333
use 0.7757344245910645
精度が近い場合は、kd-treeの運転時間がより短くなります.参考: