KNN算法

本篇将介绍knn算法，knn算法因为思想非常简单，运用的数学知识比较浅显，是非常适合机器学习入门的算法。不仅如此，knn算法在很多分类问题上表现优异， k近邻算法最基本的可以解决分类问题，不过也可以解决回归问题（以后会介绍）。借助此算法，可以解释机器学习算法使用过程中的很多细节问题，从而更加完整地刻画机器学习应用的流程。

下面以一个简单的肿瘤判别问题介绍knn是做什么的。

knn1

如上图所示，假设横轴方向表示肿瘤大小，纵轴方向表示肿瘤存在多久时间，绿色表示良性肿瘤，红色表示恶性肿瘤。现在有一个新的样本不知是良性还是恶性，要对它作出判断。knn算法的做法是，检查它周围的k个数据点，如果良性居多则判断为良性，否则判断为恶性。
下面生成模拟数聚集：

#展示算法原理（肿瘤判别）
import numpy as np
import matplotlib.pyplot as plt
#生成模拟数据
raw_data_x=[
    [3.393,2.331]
    ,[3.110,1.782]
    ,[1.344,3.368]
    ,[3.582,4.679]
    ,[2.281,2.867]
    ,[7.423,4.697]
    ,[5.745,3.534]
    ,[9.172,2.511]
    ,[7.793,3.424]
    ,[7.940,0.792]
]
raw_data_y=[0,0,0,0,0,1,1,1,1,1]#0表示良性，1恶性
x_train=np.array(raw_data_x)#制作训练集
y_train=np.array(raw_data_y)

数聚集共包含10个样本点，首先对数聚集做图得到直观的分布情况：

'''首先作散点图观察数据分布'''
plt.scatter(x_train[y_train==0,0],x_train[y_train==0,1],color='g')
plt.scatter(x_train[y_train==1,0],x_train[y_train==1,1],color='r')
plt.show()

traindata

现在新来了一个样本点[8.094,3.366]，要判断是良性还是恶性，首先将它画入图中：

''' knn算法要作的是，判断新来的数据点属于哪一类'''
x=np.array([8.094,3.366])
'''为了看清楚新来点与其它点位置关系，上色为blue'''
plt.scatter(x_train[y_train==0,0],x_train[y_train==0,1],color='g')
plt.scatter(x_train[y_train==1,0],x_train[y_train==1,1],color='r')
plt.scatter(x[0],x[1],color='b')
plt.show()

sample

我们可以直观地判断这是恶性肿瘤，因为它周围几乎都是恶性肿瘤样本点，下面从原理的角度来看一下KNN流程：
首先计算新的样本点与训练集各样本的距离，距离可以选用曼哈顿距离、欧式距离、明氏距离等，这里选用欧式距离：

from math import sqrt
distances=[]#欧式距离，曼哈顿距离，明式距离
#计算新的样本点与训练集中每个样本点的距离
for x_t in x_train:
    d = sqrt(np.sum((x_t - x)**2))#universal function，结果向量的每个元素都平方，再求和，然后开方
    distances.append(d)
distances

out:[4.813587643327999,
 5.2296569677178635,
 6.750000296296289,
 4.699160882540626,
 5.834378287358473,
 1.4905710315177867,
 2.354999999999999,
 1.37590297623052,
 0.30653711031455805,
 2.5786027224060706]

或者生成表达式一步到位：

#上面的过程python中一句话搞定
distances=[sqrt(np.sum((x_t-x)**2)) for x_t in x_train]
distances

下面对距离进行排序，而且要知道排序对应的是哪个样本，使用argsort返回排序索引：

#下面要进行排序，而且要知到排序结果是哪些点，用argsort
np.argsort(distances)#sort默认升序排列
out:array([8, 7, 5, 6, 9, 3, 0, 1, 4, 2])#即离x最近的是索引为8的点

进行预测：
nearest=np.argsort(distances)
k=6
返回与新来样本前6近的数据集样本类别：

topk_y=[y_train[i] for i in nearest[:k]]#返回与给定样本点最近的k个样本的分类
topk_y
out:[1, 1, 1, 1, 1, 0]

计数投票：

#计数
from collections import Counter
Counter(topk_y)
out:Counter({1: 5, 0: 1})

上述结果表示最近的6个中，为1（恶性）有5个，为0（良性）有一个。于是给出预测结果：

predict

预测结果为1，即为恶性肿瘤。

sklearn中的分类器

实现我们的knn分类器

新建文件夹play_Ml，在其中新建knn.py，内容如下：

import numpy as np
from math import sqrt
from collections import Counter
def kNN_classify(k,x_train,y_train,x):
    assert 1<=k<=x_train.shape[0],"k must be valid"
    assert x_train.shape[0] == y_train.shape[0],"must be same"
    assert x_train.shape[1]==x.shape[0],"must be the same"

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

    topk_y=[y_train[i] for i in nearest[:k]]
    votes=Counter(topk_y)
    predict_y=votes.most_common(1)[0][0]#knn预测结果
    return predict_y

在jupyter notebook中：

%run knn.py
predict_y=kNN_classify(6,x_train,y_train,x)
predict_y
out:1

可以得到相同的预测结果。

不是说机器学习算法都需要建模之后训练模型吗，没错，但knn算法比较特殊，可以说knn是唯一一个不需要训练过程的算法，输入样例可直接送给训练数剧集得到输出预测。由此也可以看出，knn算法是非常特殊的，可以被认为是没有模型的算法，为了和其它算法统一，可以认为训练集就是模型本身。这也是scikit-learn中的处理方式，为了所有机器学习算法有统一的宏观流程，都有fit和predict过程。knn的fit过程算是最简单的。

sklearn中的knn

上述过程也可以用sklearn中封装的机器学习算法实现，如实现knn算法：

from sklearn.neighbors import KNeighborsClassifier
kNN_classifier = KNeighborsClassifier(n_neighbors=6)#创建knnclassifier实例
kNN_classifier.fit(x_train,y_train)#fit过程训练数据集，得到模型
'''将x整理为矩阵格式'''
x_new=x.reshape(1,-1)
kNN_classifier.predict(x_new)
out:array([1])

注意：在sklearn中，输入进行预测的数据从version_19之后只支持矩阵格式的数据，不再支持单个数据预测了，如果要预测单个数据需要整理为矩阵格式。
sklearn中实现机器学习的基本步骤一般包括三个：

• 实例化分类器
• 执行fit训练过程
• 执行predict预测过程

如上述代码调用sklearn封装的类实现knn算法执行过程。

改造我们的代码为sklearn代码调用格式

我们可以修改自己的knn代码，使得在调用形式上和sklearn中调用knn算法是一样的，这能让我们更加理解knn算法和理解sklearn进行机器学习的流程。

'''kNN.py'''
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],"must be same"
        assert self.k<=x_train.shape[0],"k must be valid"

        self._x_train=x_train
        self._y_train=y_train

        return self
        

    def predict(self,x_predict):
        '''给定待预测数剧集，给出预测结果向量'''
        assert self._x_train is not None and self._y_train is not None,"must fit before predict"
        assert x_predict.shape[1]==self._x_train.shape[1],"must be the same"
        
        y_predict=[self._predict(x) for x in x_predict]
        return np.array(y_predict)


    def _predict(self,x):
        '''给定单个的x，返回x的预测值'''
        assert x.shape[0]==self._x_train.shape[1],"must be the same"
        distances=[sqrt(np.sum((x_t-x)**2)) for x_t in self._x_train]
        nearest=np.argsort(distances)

        topk_y=[self._y_train[i] for i in nearest[:self.k]]
        votes=Counter(topk_y)
        return votes.most_common(1)[0][0]#knn预测结果
    

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

然后就可以使用我们自己写的knn分类器了

%run kNN.py

实例化、fit、预测

knn_clf=kNNClassifier(k=6)
knn_clf.fit(x_train,y_train)
out:kNN(k=6)
y_predict=knn_clf.predict(x_new)
y_predict
out:array([1])
y_predict[0]
out:1

实际sklearn中的算法为了在格式上统一并在运算上优化，比这个要复杂的多，这里只是简单模拟了sklearn的底层。