前言

这是机器学习最简单的算法，当然并不是说简单就没人用。knn算法的优点就是简单而且便于实现，并且有一定好的效果。

算法原理

K近邻的算法思路很简单。

背景

假设 有两个类别散落在这个特征空间中。

image.png

现在有一个新的样本需要预测它属于哪个类别。

image.png

思路介绍

step1: 暴力的求出新样本与其余所有样本的“距离”。
step2: 找到距离它最近的k的点。（这就是k近邻的名称由来）
step3: 进行类别打分，新样本属于分数最高的哪个类别。

然后展开细节讲：

距离

欧式距离

欧式距离的计算就是每个维度的平方和开跟号也就是直线距离。这里用二维的比较好理解。就是其实x(p)是预测的样本，x(t)训练样本。

image.png

当然x，y只有两个特征，现实往往有很多个特征也就是说有很多个维度。

image.png

其中的下标标号就是对应的不同维度。

简写就是

image.png

曼哈顿距离

曼哈顿距离的由来是在城市中的行车距离。

image.png

在现实生活中两点之间并不是都是直线可达的，这样可以把区域分成单元的小块。就像开出租车一样。直线绿色的就是欧式距离，蓝色、红色、黄色都是曼哈顿距离。（图来自 维基百科）

image.png

明可夫斯基定理

仔细看曼哈顿距离和欧氏距离
曼哈顿距离

image.png

欧氏距离

image.png

image.png

K

K值是KNN的一个超参数。（超参数：也就是模型运行前需要确定的参数，K就是KNN算法最为直观的一个超参数）。这个参数需要人为的去调，这也就是人工在其中起的最重要的作用（调参狗）。至于怎么调参？一般需要经验和专业的领域知识。当然也可以老中医式的调参。如果计算量比较小可以使用网格搜索的方法去调参。

分类决策

一般思路是这样的，就是把测试数据丢进去，计算与训练集所有点的距离，找到前K个点的类别。然后进行PK算出类别。

image.png

黑色点：测试样本。
紫色点：类别A。
蓝色点：类别B
如图所示，不管使用的什么距离计算方式，我们可以找到与黑色点与所有点的距离。那么我们就可以找到距离它最近的K个点。然后进行类别打分，明显蓝色的分数比较高。那么该点就属于蓝色点。

这样做是没有问题的。但是机器学习目前还是很依赖数据的而且不同的场景下的应用也是不一样的。
举个栗子

image.png

由图所示虽然蓝色类的得分高，但是黑色点距离紫色点的距离更近一点。或许它更有可能是紫色类。那么我们的距离或许需要一个权重（注意：或许。因为这个距离权重不一定有用，要去试）。这个距离权重一般采用距离的倒数作为权重。
重新计算得分表

模型实现

这里自己造的数据，自己做的最简单的实现。只供理解参考。

import numpy as np
import matplotlib.pyplot as plt
import math
from collections import Counter

rad_1=np.random.randint(1,10,size=(5,2))
rad_1

array([[9, 3],
       [6, 6],
       [3, 6],
       [6, 7],
       [7, 1]])

rad_2=np.random.randint(11,20,size=(5,2))
rad_2

array([[13, 18],
       [15, 15],
       [14, 19],
       [13, 11],
       [11, 17]])

raw_data_X=np.vstack([rad_1,rad_2])
raw_data_X

array([[ 9,  3],
       [ 6,  6],
       [ 3,  6],
       [ 6,  7],
       [ 7,  1],
       [13, 18],
       [15, 15],
       [14, 19],
       [13, 11],
       [11, 17]])

raw_data_y=[0,0,0,0,0,1,1,1,1,1]

y_train=np.array(raw_data_y)
y_train

array([0, 0, 0, 0, 0, 1, 1, 1, 1, 1])

plt.scatter(raw_data_X[y_train==0,0],raw_data_X[y_train==0,1],color='b')
plt.scatter(raw_data_X[y_train==1,1],raw_data_X[y_train==1,1],color='r',alpha=0.5)
plt.show()

output_6_0.png

x=np.array([13,14])
x

array([13, 14])

plt.scatter(raw_data_X[y_train==0,0],raw_data_X[y_train==0,1],color='b')
plt.scatter(raw_data_X[y_train==1,1],raw_data_X[y_train==1,1],color='r')
plt.scatter(x[0],x[1],color='g',alpha=0.5,marker='*')
plt.show()

output_8_0.png

KNN过程

X_train=raw_data_X
distance=[]
for x_train in X_train:
    d=np.sum((x-x_train)**2)**0.5
    distance.append(d)
distance

[11.704699910719626,
 10.63014581273465,
 12.806248474865697,
 9.8994949366116654,
 14.317821063276353,
 4.0,
 2.2360679774997898,
 5.0990195135927845,
 3.0,
 3.6055512754639891]

distance1=[math.sqrt(np.sum((x_train-x)**2)) for x_train in X_train]
distance1

[11.704699910719626,
 10.63014581273465,
 12.806248474865697,
 9.899494936611665,
 14.317821063276353,
 4.0,
 2.23606797749979,
 5.0990195135927845,
 3.0,
 3.605551275463989]

distance=[(np.sum((x_train-x)**2)**0.5)for x_train in X_train]
distance

[11.704699910719626,
 10.63014581273465,
 12.806248474865697,
 9.8994949366116654,
 14.317821063276353,
 4.0,
 2.2360679774997898,
 5.0990195135927845,
 3.0,
 3.6055512754639891]

nearest=np.argsort(distance)
nearest

array([6, 8, 9, 5, 7, 3, 1, 0, 2, 4])

k=6

topK_y=y_train[nearest[:6]]
topK_y

array([1, 1, 1, 1, 1, 0])

Votes=Counter(topK_y)

Votes.most_common(1)[0][0]

1

pwd

'/Users/zhangyan/Documents/SystemEnv/anaconda3/bin/boboML'

def knn(k,X_train,y_train,x):
    assert 1<=k<= X_train.shape[0], "k不能大于训练样本的个数"
    assert X_train.shape[0]==y_train.shape[0], "训练样本个数要等于标签数"
    assert X_train.shape[1]==x.shape[0],"测试数据特征个数要与训练样本相同"
    distance=[]
    distance=[(np.sum((x_train-x)**2)**0.5)for x_train in X_train]
    nearest = np.argsort(distance)
    topK_y = y_train[nearest[:6]]
    Votes = Counter(topK_y)
    return Votes.most_common(1)[0][0]

knn(6,X_train,y_train,x)

1

from KNN_function import knn_fun1

from mymodule import FirstML

FirstML.predict(1)

1

knn_fun1.knn(6,X_train,y_train,x)

1

scikit-learn的kNN

from sklearn.neighbors import KNeighborsClassifier

kNN_classifier=KNeighborsClassifier(n_neighbors=6)

kNN_classifier.fit(X_train,y_train)

KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
           metric_params=None, n_jobs=1, n_neighbors=6, p=2,
           weights='uniform')

kNN_classifier.predict(x.reshape(1,-1))

array([1])

class KNNClassifier:
    def __init__(self,k):
        assert k>0,"k不能小于0"
        self.k=k
    def fit(self,X_train,y_train):
        assert X_train.shape[0] == y_train.shape[0], "训练样本个数要等于标签数"

        self.X_train=X_train
        self.y_train=y_train
        
        return self
    def prdict(self,x_predict):
        assert self.X_train.shape[1] == x_predict.shape[1], "测试数据特征个数要与训练样本相同"
        return np.array([self._predict(x) for x in x_predict])
        
    
    def _predict(self,x):
        distance = [(np.sum((x_train - x) ** 2) ** 0.5) for x_train in X_train]
        nearest = np.argsort(distance)
        topK_y = y_train[nearest[:6]]
        Votes = Counter(topK_y)
        return Votes.most_common(1)[0][0]
    

cls=KNNClassifier(k=6)

cls.fit(X_train,y_train)

<__main__.KNNClassifier at 0x1094f3b00>

cls.prdict(x.reshape(1,-1))

array([1])

cls1=knn_fun1.KNNClassifier(6)

cls1.fit(X_train,y_train)

<KNN_function.knn_fun1.KNNClassifier at 0x1094f3320>

cls1.predict(x.reshape(1,-1))

array([1])

x=np.array([[1,4],[5,6],[12,12]])
x.shape[1]

2

X_train.shape[1]

2

cls1.predict(x)

array([0, 0, 1])