邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。
kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。

---

数据预备，这里使用random函数生成10*2的矩阵作为两列特征值，1个10个元素数组作为类别值

import numpy as np
import matplotlib.pyplot as plt

x_train = np.random.rand(10,2)*8
y_train = np.random.randint(0,2,10)
x = np.array([3,4])
k=3
plt.scatter(x_train[y_train==1,0],x_train[y_train==1,1],color="red")
plt.scatter(x_train[y_train==0,0],x_train[y_train==0,1],color="green")
plt.scatter(x[0],x[1],marker='+',color="blue")
plt.show()

X_train = np.array(x_train)

Y_train = np.array(y_train)

from math import sqrt
distances = []
for x_train in X_train:
    d = sqrt(np.sum((x-x_train)**2))
    distances.append(d)

distances = [sqrt(np.sum((x-x_train)**2)) for x_train in X_train]
argindex = np.argsort(distances)

from collections import Counter

topK_Y = [Y_train[i] for i in argindex[:k]]

votes = Counter(topK_Y)
votes.most_common(1)[0][0]

执行结果为判断x点大概率为类别0（绿点）

---

使用sklearn中封装的knn算法

from sklearn.neighbors import KNeighborsClassifier

knn_clf = KNeighborsClassifier(n_neighbors=3)

knn_clf.fit(X_train,Y_train)

knn_clf.predict(x.reshape(1,-1))[0]

封装自己的knn算法

# _*_ encoding:utf-8 _*_
import numpy as np
from math import sqrt
from collections import Counter

class KNNClassifier:
    def __init__(self,k):
        assert k>=1, "k must be valid"
        self.k = k
        self._X_train = None
        self._Y_train = None

    def fit(self,X_train,Y_train):
        assert X_train.shape[0] == Y_train.shape[0],\
                                                     "The size of X_train must be equals to the size of Y-Train"
        assert self.k <= X_train.shape[0]
        self._X_train = X_train
        self._Y_train = Y_train
        return self

    def predict(self,x_predict):
        return np.array([self._predict(x) for x in x_predict])

    def _predict(self,x):
        distances = [ sqrt(np.sum((x_train-x)**2)) for x_train in self._X_train]
        nearest = np.argsort(distances)
        votes = [i for i in self._Y_train[nearest[:self.k]]]
        return Counter(votes).most_common(1)[0][0]

    def __repr__(self):
        return "knn(k=%d)" %self.k

---

测试与训练数据集分类

为了能够确认模型的准确性，我们需要将已有数据集按一定比例分类为测试数据集和训练数据集

# _*_ encoding:utf-8 _*_
import numpy as np

def train_test_split(X,y,test_radio=0.2,seed=None):
    assert X.shape[0]==y.shape[0],"The size of X and y must be equal"
    assert 0.0<=test_radio<=1.0,"test radio must be valid"
    if(seed):
        np.random.seed(seed)

    shuffled_indexes = np.random.permutation(len(X))
    test_size = int(X.shape[0]*test_radio)
    test_indexes = shuffled_indexes[:test_size]
    train_indexes = shuffled_indexes[test_size:]

    X_test = X[test_indexes]
    y_test = y[test_indexes]
    X_train = X[train_indexes]
    y_train = y[train_indexes]
    return X_train,X_test,y_train,y_test

---

使用knn算法测试数据集digits

import numpy as np
from sklearn import datasets
import matplotlib.pyplot as plt
import matplotlib
%run MyScripts/KNN.py
%run MyScripts/metrics.py
%run MyScripts/model_selection.py

digits = datasets.load_digits()
X = digits.data
y = digits.target

some_digit = X[666]
some_digit_image = some_digit.reshape(8,8)
plt.imshow(some_digit_image,cmap=matplotlib.cm.binary)

knn_clf = KNNClassifier(k=6)
X_train,X_test,y_train,y_test = train_test_split(X,y)
knn_clf.fit(X_train,y_train)
knn_clf.score(X_test,y_test)

---

超参数

超参数是模型运行前必须要决定的参数，例如k近邻算法中的k值和距离
确定超参数一般使用的方法：

领域知识
经验数值
实验探索

确定knn算法用于digits数据集的最佳超参数

//使用网格搜索法确定weights和k超参数
best_k = -1
best_score = -1
methods = ["uniform","distance"]
best_method = ""
for method in methods:
    for k in range(1,11):
        knn_clf = KNeighborsClassifier(n_neighbors=k,weights=method)
        knn_clf.fit(X_train,y_train)
        score = knn_clf.score(X_test,y_test)
        if(score>best_score):
            best_k = k
            best_score = score
            best_method = method
print("best_k = ",best_k)
print("best_score = ",best_score)
print("best_method = ",best_method)

best_k = 3
best_score = 0.9888888888888889
best_method = uniform

best_k = -1
best_score = -1
best_p=-1
for p in range(1,6):
    for k in range(1,11):
        knn_clf = KNeighborsClassifier(n_neighbors=k,weights="distance",p=p)
        knn_clf.fit(X_train,y_train)
        score = knn_clf.score(X_test,y_test)
        if(score>best_score):
            best_k = k
            best_score = score
            best_p = p
print("best_k = ",best_k)
print("best_score = ",best_score)
print("best_p = ",best_p)

best_k = 3
best_score = 0.9888888888888889
best_p = 2