简单易懂的KNN算法详解：从入门到实践，原理、案例与代码演示

beginning

    盆友们都喜欢看电影的叭？大家都喜欢什么题材的片呢？爱情片、喜剧片还是动作片？那大家有没有想过这些题材本身是如何定义的呢？也就是说同一题材的电影有哪些公共特征？动作片中也会存在接吻镜头，爱情片中也会有打斗场景，我们不能单纯依靠是否存在打斗或亲吻来判断影片类型。但是爱情片中亲吻镜头更多，动作片中的打斗场景也更频繁，所以咱们可以基于此类场景在某部电影中出现的次数，使用K-近邻（KNN）算法构造程序，实现自动划分电影的题材。说到这你是不是对KNN感兴趣了呢，那就跟我一起看下去叭????????????

---

1.原理

    kNN 的$\color{blue}{工作原理}$是：存在一个数据样本集合，也称为训练样本集，其中每个数据都带有标签，这意味着我们知道每个数据与其所属分类之间的对应关系。当我们输入新的未带标签的数据时，算法会将该数据的每个特征与样本集中数据的特征进行比较，并提取与样本集中最相似数据（即最近邻）的分类标签。通常情况下，我们只考虑样本数据集中前k个最相似的数据，其中k是不大于20的整数，这也是k-近邻算法命名的来源。最后，我们选择k个最相似数据中出现次数最多的分类作为新数据的分类。

    我们已经了解到k-近邻算法的原理，现在让我们回到之前提到的电影分类的例子中，使用这种算法来划分爱情片和动作片。有人曾经对许多电影的打斗镜头和接吻镜头进行了统计，并记录在下表中。假设我们现在面临一个从未见过的电影，我们该如何确定它是属于爱情片还是动作片呢？我们可以使用kNN算法来解决这个问题????????????

    即使不知道未知电影属于哪种类型，咱们也可以通过某种方法计算出来。首先计算未知电影与样本集中其他电影的距离，如下表所示。此处呢咱们暂且先不要关心如何计算得到这些距离值，使用Python实现电影分类应用时，会提供具体的计算方法滴????????????

    现在咱们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影依次是He's Not Really into Dudes、Beautiful Woman和California Man。k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此咱们就可以判定未知电影属于爱情片片啦????????????

2.实例（包含代码）

总结一下kNN算法的$\color{blue}{一般流程}$叭：

0. 收集数据：可以使用任何的方法
1. 准备数据：距离计算所需要的数值，数据格式最好是结构化的
2. 分析数据：可以使用任何的方法
3. 训练算法：此步骤不适用于咱们的k-近邻算法
4. 测试算法：来计算错误率
5. 使用算法：首先需要输入样本数据和结构化的输出结果，然后使用k-近邻算法对输入数据进行分类判断，并确定其所属类别，最后根据分类结果对数据进行进一步的处理。

2.1准备数据

首先创建kNN.py文件：

from numpy import * # 科学计算包numpy
import operator # 运算符模块
def createDataSet(): #创建数据集和标签
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

为了方便使用createDataSet()函数，咱们依次执行以下步骤哈：保存kNN.py文件，改变当前路径到存储kNN.py文件的位置，打开Python开发环境。

进入Python交互式开发环境后，输入下列命令导入上面编辑的程序模块：

 >>>import kNN

导入之后，在Python命令提示符下输入下列命令：

group,labels = kNN.createDataSet()

这一命令创建了变量group和labels，在Python命令提示符下输入变量的名字以检验是否正确的定义变量：

>>>group
array([[1. , 1.1],
       [1. , 1. ],
       [0. , 0. ],
       [0. , 0.1]])
>>>labels
['A','A','B','B']

这里有4组数据，每组数据有两个我们已知的属性或者特征值。group矩阵每行包含一个不同的数据，我们可以把它想象为某个日志文件中不同的测量点或者入口。向量labels包含了每个数据点的标签信息，labels包含的元素数据等于group矩阵行数。这里咱们将数据点（1，1.1）定义为类A，数据点（0，0.1）定义为类B。

2.2构造KNN分类器

下面使用kNN算法将每组数据划分到某个类中，$\color{blue}{伪代码}$如下：

对未知类别属性的数据集中的每个点依次执行以下操作：

$\color{green}{（1）}$计算已知类别数据集中的点与当前点之间的距离；

$\color{green}{（2）}$按照距离递增次序排序；

$\color{green}{（3）}$选取与当前点距离最小的k个点；

$\color{green}{（4）}$确定前k个点所在类别的出现频率；

$\color{green}{（5）}$返回前k个点出现频率最高的类别作为当前点的预测分类。

python函数classify()如下所示：

def createDataSet():
        group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
        labels = ['A','A','B','B']
        return group,labels
        
def classify0(inX, dataSet, labels, k): 
        #用于分类的输入向量inX，输入的训练样本集dataSet，标签向量labels，k表示用于选择最近邻居的数目
        dataSetSize = dataSet.shape[0]
        diffMat = tile(inX, (dataSetSize,1)) - dataSet #距离计算，使用欧式距离公式
        aqDiffMat = diffMat ** 2
        aqDistances = aqDiffMat.sum(axis=1)
        distances = aqDistances ** 0.5
        sortedDistIndicies = distances.argsort()
        classCount = {}
        for i in range(k):
            voteIlabel = labels[sortedDistIndicies[i]]
            classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #选择距离最小的k个点
        sortedClassCount = sorted(classCount.items(), #iteritems 用于python2
                                  key = operator.itemgetter(1),reverse = True) #排序
        return sortedClassCount[0][0]

• classify0()函数有四个输入参数：用于分类的输入向量是intX，输入的训练样本集为dataSet，标签向量为labels，k表示用于选择最近邻居的数目。
• 使用$\color{blue}{欧氏距离}$计算完所有点之间的距离后，可以按照从小到大的次序对数据进行排序，然后确定前k个距离最小元素所在的主要分类，输入的k总是正整数。
• 最后需要将classCount字典分解为元组列表，然后运用程序第二行导入运算符模块的itemgetter方法，按照第二个元素的次序对元组进行排序。此处咱们使用逆序排序，即按照从最大到最小排序，最后返回出现频率最高的元素标签。

为了预测所在分类，在Python提示符中输入下列命令：

>>>KNN.classify0([0,0],group,labels,3)
Out: 'B'

大家可以看到输出的结果是B，也可以改变输入[0,0]为其他值，测试程序的运行结果嗷⛳⛳⛳

2.3测试分类器

    咱们已经通过k-近邻算法构建了一个分类器。此时，盆友们可能会问“该分类器的输出是否总是100％正确？”很遗憾，答案是否定的。分类器不能保证百分之百的准确率。为了评估分类器的性能，我们可以使用包含已知答案的数据集进行测试。当然，在测试时不能向分类器提供这些答案，而是检查分类器给出的结果是否与预期结果相符。通过大量的测试数据，我们可以计算出分类器的错误率——即$\color{blue}{分类器给出错误结果的次数除以测试执行的总数}$。完美分类器的错误率为0，而最差分类器的错误率达到1.0????????????在最差情况下，分类器根本无法找到正确的答案。

---

ending

关于kNN的讲解介绍就到这里啦，盆友们学废了叭，如果觉得我的分享还不错，please一键三连嗷????????????下期见