k-近邻算法

开篇

k-近邻算法是比较简单的一种机器学习算法，其核心思想可以用一句话来概括：近朱者赤，近墨者黑。

在具体介绍该算法之前，先通过一个栗子对该算法做一个感性上的认识。

Python爱好者 or C爱好者？

上图中，每一个形状（三角形，圆形）都代表了一个人。总共有两种形状，说明这些人总共可以分为两类：Python爱好者、C爱好者。

三角形一共有7个，代表喜欢写Python的总共有7人；

圆形一共有6个，代表喜欢写C语言的总共有6人。

现在，突然来了一个不知道是喜欢写Python还是C语言（并且只可能属于其中之一）的人—–五角星，要求你来判定这个人所属的类别。

emm…

你可能会说，那看看图上距离这个人（五角星）最近的几个人所属类别就可以了啊！比如就看距离这个人最近的3个人：其中有两个人喜欢写Python，而只有一个人喜欢写C语言（如下图所示）

按照少数服从多数的原则，将这个新来的人（五角星）归类到三角形(Python爱好者)类别就搞定啦！

最终分类结果

上面的栗子其实就使用了k-近邻算法的思想。现在，让我们对该算法做一个完整的定义。

什么是k-近邻算法？

k-近邻算法是一种有监督的机器学习算法，对于有监督的机器学习算法来说，其训练数据集的一般格式如下（0：类别1；1：类别2）：

当n取4，m取3时，就是一个含有4个样本，每个样本有3个特征的数据集了，如下图

k-近邻算法的核心思想为：对于一个给定的训练集，当新的样本到来时，找到训练集中与新样本距离最近的k个样本，然后查看这k个样本所属类别，并将新样本归类到这k个样本中大多数样本所属类别中。

没错，k-近邻算法的思想就是这么简洁。接下来，我们将用Python来实现该算法。

用Python实现k-近邻算法

首先明确，k-近邻算法中的k是我们自己指定的（当然k的选取是有技巧的，这个稍后会说，这里我们仅仅关心如何用Python实现该算法），训练数据集也是自己的（废话，训练集肯定要自行准备的啊），所以有两个参数需要我们自行传入，其一为k，其二为训练集data。

在实现k-近邻算法之前，先自行定义训练集：

class DataSet():
    feature=np.array([[2.3,2.4],
                     [0.1,0.2],
                     [2.4,2.3],
                     [0.2,0.1],
                     [0.2,0.2],
                     [2.4,2.4]
        ])
    target=np.array([1,0,1,0,0,1])

然后查看下训练数据集的分布（0和1代表样本所属的类别）

data=DataSet()
plt.scatter(data.feature[:,0],data.feature[:,1],c=data.target)
for i in range(len(data.feature)):
    plt.text(data.feature[i,0], data.feature[i,1],data.target[i], fontsize=8, color = "b")
plt.show()

现在开始实现k-近邻算法：

class MyKNN():
    def __init__(self,data,k):
        self.samples_feature=data.feature#样本特征
        self.samples_target=data.target#样本所属类别
        self.k=k

由于k-近邻算法涉及到了距离，因此需要写一个计算距离的方法。距离的度量方式有很多，这里我们采用大家最为熟悉的L2距离，也就是欧氏距离：

1 2	def cal_dist(self,sample1,sample2): return np.sqrt(np.sum((sample-sample)**2))

接下来是k-近邻算法的核心实现步骤：

1.分别计算新的样本与训练集中所有样本之间的距离；
2.按照距离从小到大排序；
3.选取距离新样本最近的k个距离及其对应样本所属类别；
4.将新样本归类到与其距离最近的k个样本中大多数样本所属类别。

def run(self,new_sample_feature):
    #对于每一个样本的特征
    all_dists=[]
    for i, sample_feature in enumerate(self.samples_feature):
        #1.分别计算新的样本与训练集中所有样本之间的距离
        dist=self.cal_dist(sample_feature,new_sample_feature)
        all_dists.append((dist,self.samples_target[i]))
    #2.按照距离从小到大排序
    sorted_dist_with_target=sorted(all_dists,key=lambda x:x[0])
    #3.选取距离新样本最近的k个
    top_k=sorted_dist_with_target[0:self.k]
    #4.统计这k个样本中大多数样本所属类别
    dic={}
    for item in top_k:
        if item[1] in dic:
            dic[item[1]]+=1
        else:
            dic[item[1]]=1
    result=sorted(dic.items(),key=lambda x:x[1])[-1][0]
    return result

这样，我们就实现了k-近邻算法，完整代码如下：

import numpy as np
class MyKNN():
    def __init__(self,data,k):
        self.samples_feature=data.feature#样本特征
        self.samples_target=data.target#样本所属类别
        self.k=k
    #计算两个样本之间的欧氏距离（L2距离）
    def cal_dist(self,sample1_feature,sample2_feature):
        return np.sqrt(np.sum((sample1_feature-sample2_feature)**2))
    def run(self,new_sample_feature):
        #对于每一个样本的特征
        all_dists=[]
        for i, sample_feature in enumerate(self.samples_feature):
            #分别计算新的样本与训练集中所有样本之间的距离
            dist=self.cal_dist(sample_feature,new_sample_feature)
            all_dists.append((dist,self.samples_target[i]))
        #按照距离从小到大排序
        sorted_dist_with_target=sorted(all_dists,key=lambda x:x[0])
        #选取距离新样本最近的k个
        top_k=sorted_dist_with_target[0:self.k]
        #统计这k个样本中大多数样本所属类别
        dic={}
        for item in top_k:
            if item[1] in dic:
                dic[item[1]]+=1
            else:
                dic[item[1]]=1
        result=sorted(dic.items(),key=lambda x:x[1])[-1][0]
        return result

测试k-近邻算法

我们前面已经实现了k-近邻算法，那么它的分类能力究竟如何呢？

现在，自定义一个测试集，用刚刚实现的k-近邻算法对测试集样本进行分类(这里的k不妨取3)：

test_samples_feature=np.array([[2.4,2.5],
                               [0.3,0.1],
                               [2.3,1.9],
                               [0.1,0.3]
    ])
for i,item in enumerate(test_samples_feature):
    print('第{}个样本所属类别为{}'.format(i+1,knn.run(item)))

输出：

第1个样本所属类别为1
第2个样本所属类别为0
第3个样本所属类别为1
第4个样本所属类别为0

那这个结果可不可靠呢？我们需要评估一下。千言万语不及一张图，所以这里我们还是用可视化的方式来演示。

在训练数据可视化结果图的基础上，将测试数据也绘制在这张图上，完整代码如下：

data=DataSet()
#训练数据
plt.scatter(data.feature[:,0],data.feature[:,1],c=data.target)
for i in range(len(data.feature)):
    plt.text(data.feature[i,0], data.feature[i,1],data.target[i], fontsize=8, color = "b")
   
#测试数据
plt.scatter(test_samples_feature[:,0],test_samples_feature[:,1])
for i in range(len(test_samples_feature)):
    plt.text(test_samples_feature[i,0], test_samples_feature[i,1], 'sample{}:\n'.format(i+1)+str((test_samples_feature[i,0],test_samples_feature[i,1])), fontsize=10, color = "r")
plt.show()