Python3：《机器学习实战》之k近邻算法（1）算法概述

ゞ浴缸里的玫瑰 2022-06-09 08:49 231阅读 0赞

# Python3：《机器学习实战》之k近邻算法（1）算法概述 #

--------------------

*  **转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net_u011475210]**
 *  **代码地址：[https://github.com/WordZzzz/ML/tree/master/Ch02][https_github.com_WordZzzz_ML_tree_master_Ch02]**
 *  **操作系统：WINDOWS 10**
 *  **软件版本：python-3.6.2-amd64**
 *  **编  者：WordZzzz**

--------------------

*  Python3机器学习实战之k近邻算法1算法概述
    
     *  前言
     *  一算法介绍
        
         *  k-近邻算法
         *  一般流程
     *  二代码实现与详解
     *  三主要区分函数

## 前言： ##

本渣渣（WordZzzz直接被舍友叫成了“我的渣”，所以以后我在博客中就以此自居了！），最近在学习Peter Harrington的*Machine Learning in Action*，一边看书一边用Python3.6实现课本中的算法（原书中使用的是Python2.x）。好记性不如烂笔头，奈何本渣渣连烂笔头都买不起，所以就来这不费笔墨的地方费尽心思写博客。本渣渣记性不是一般的差，在此记下每个算法的学习要点及Python代码实现，一方面方便自己以后复习，另一方面贴出来和大家一起学习，共同进步~~~

**注意：python3.x与python2.x的部分函数库有较大差异，针对这个问题，本渣渣会将代码版本升级中遇到的问题在每篇博文的最后列出来，并加以解释说明，帮助大家区分理解。**

原著代码（python2.x）地址：[https://www.manning.com/books/machine-learning-in-action][https_www.manning.com_books_machine-learning-in-action]  
本渣渣代码（python3.x）地址：[https://github.com/WordZzzz/ML/tree/master/Ch02][https_github.com_WordZzzz_ML_tree_master_Ch02]

博客中的代码都会在本渣渣的GitHub上贴出，欢迎*Watch、Star、Fork*。

## 一、算法介绍： ##

k-近邻算法（kNN）的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法的中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。  
  简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。

### k-近邻算法： ###

*  优点：精度高、对异常值不敏感、无数据输入假定。
 *  缺点：计算复杂度高、空间复杂度高。
 *  使用数据范围：数值型和标称型。

书上有个电影分类的例子，使用k-近邻算法分类爱情片和工作片。书中给出了6部电影的打斗镜头数和接吻镜头数，如图2-1所示。

![SouthEast][]

假如有一部未看过的电影，如何确定它是爱情片还是动作片呢？下面我们将使用kNN来解决这个问题。

首先，我们需要数据，即这个未知电影存在多少个打斗镜头和接吻镜头，图2-1中间问号位置是该电影出现的镜头数图像化的结果，具体数字参见表2-1。

<table> 
 <thead> 
  <tr> 
   <th align="center">电影名称</th> 
   <th align="center">打斗镜头</th> 
   <th align="center">接吻镜头</th> 
   <th align="center">电影类型</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">California Man</td> 
   <td align="center">3</td> 
   <td align="center">104</td> 
   <td align="center">爱情片</td> 
  </tr> 
  <tr> 
   <td align="center">He is Not Really into Dudes</td> 
   <td align="center">2</td> 
   <td align="center">100</td> 
   <td align="center">爱情片</td> 
  </tr> 
  <tr> 
   <td align="center">Beautiful Woman</td> 
   <td align="center">1</td> 
   <td align="center">81</td> 
   <td align="center">爱情片</td> 
  </tr> 
  <tr> 
   <td align="center">Kevin Longblade</td> 
   <td align="center">101</td> 
   <td align="center">10</td> 
   <td align="center">动作片</td> 
  </tr> 
  <tr> 
   <td align="center">Robo Slayer 3000</td> 
   <td align="center">99</td> 
   <td align="center">5</td> 
   <td align="center">动作片</td> 
  </tr> 
  <tr> 
   <td align="center">Amped Ⅱ</td> 
   <td align="center">98</td> 
   <td align="center">2</td> 
   <td align="center">动作片</td> 
  </tr> 
  <tr> 
   <td align="center">？</td> 
   <td align="center">18</td> 
   <td align="center">90</td> 
   <td align="center">未知型</td> 
  </tr> 
 </tbody> 
</table>

\[表2-1 每部电影的镜头统计及电影评估类型\]

计算未知电影和样本集中其他电影的距离，如表2-2所示。我们暂且不关心如何计算得到这些距离值，后面会提供具体的计算方法。

<table> 
 <thead> 
  <tr> 
   <th align="center">电影名称</th> 
   <th align="center">与未知电影的距离</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">California Man</td> 
   <td align="center">20.5</td> 
  </tr> 
  <tr> 
   <td align="center">He is Not Really into Dudes</td> 
   <td align="center">18.7</td> 
  </tr> 
  <tr> 
   <td align="center">Beautiful Woman</td> 
   <td align="center">19.2</td> 
  </tr> 
  <tr> 
   <td align="center">Kevin Longblade</td> 
   <td align="center">115.3</td> 
  </tr> 
  <tr> 
   <td align="center">Robo Slayer 3000</td> 
   <td align="center">117.4</td> 
  </tr> 
  <tr> 
   <td align="center">Amped Ⅱ</td> 
   <td align="center">9118.9</td> 
  </tr> 
 </tbody> 
</table>

\[表2-2 已知电影与未知电影的距离\]

现在我们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到k个距离最近的电影。假定`k = 3`，则三个最靠近的电影依次是*He is Not Really into Dudes*、*Beautiful Woman*、*California Man*。k-近邻算法按照距离最近的三部电影的类型，决定位置电影的类型，而这三部电影全是爱情片，所以我们判定未知电影为爱情片。

### 一般流程： ###

*  收集数据：可以使用任何方法。
 *  准备数据：距离计算所需要的数值，最好是结构化的数据格式。
 *  分析数据：可以使用任何方法。
 *  训练算法：此步骤不适用于k-近邻算法。
 *  测试算法：计算错误率。
 *  使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续处理。

## 二、代码实现与详解： ##

首先，创建名为kNN.py的Python模块。所有代码都已做出详细注释，所以不再赘述，如有疑问可以在下方评论哦~

2.1 创建数据集和标签：

代码实现：

# -*- coding: UTF-8 -*-
    """
    Created on Aug 18, 2017
    kNN: k Nearest Neighbors
    
    Input:      inX: vector to compare to existing dataset (1xN)
                dataSet: size m data set of known vectors (NxM)
                labels: data set labels (1xM vector)
                k: number of neighbors to use for comparison (should be an odd number)
    
    Output:     the most popular class label
    
    @author: wordzzzz
    """
    
    from numpy import *
    import operator
    
    def createDataSet():
        """
        Function：   创建数据集和标签
    
        Args：       无
    
        Returns：    group：创建的数据集
                    labels：创建的标签
        """
    
        #创建数据集
        group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
        #创建标签
        labels = ['A', 'A', 'B', 'B']
        #返回创建的数据集和标签                        
        return group, labels

保存编写好的kNN.py模块，在Windows下打开命令提示符。如果不想在终端通过命令行一步一步敲到当前目录，可以直接在当前文件夹按住shift+右键，这个时候便会出现命令提示符的选项，单击后终端内直接显示当前文件夹。然后输入python，进入python编译开发环境。

输出结果：

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

向量labels包含了每个数据点的标签信息，labels包含的元素个数等于group矩阵行数。这里我们将数据点(1, 1.1)定义为类A，数据点(0, 0.1)定义为类B。为了说明方便，例子中的数值是任意选择的，并没有给出轴标签，图2-2是带有标签信息的四个数据点。

![SouthEast 1][]

2.2 实施kNN分类算法：

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

*  (1).计算已知类别数据集中的点与当前点之间的距离；
 *  (2).按照距离递增次序排序；
 *  (3).选取与当前点距离最小的k个点；
 *  (4).确定前k个点所在类别的出现频率；
 *  (5).返回前k个点出现频率最高的类别作为当前点的预测分类。

这里我们使用欧氏距离公式，计算两个向量点xA和xB之间的距离：

d=(xA0−xB0)2\+(xA1−xB1)2−−−−−−−−−−−−−−−−−−−−−−−√

如果特征值有多个，那公式就变成了这个样子：

d=∑i=0N(xAi−xBi)2−−−−−−−−−−−−−⎷

代码实现：

def classify0(inX, dataSet, labels, k):
        """
        Function：   创建数据集和标签
    
        Args：       inX：用于分类的输入向量 (1xN)
                    dataSet：输入的训练样本集 (NxM)
                    labels：标签向量 (1xM vector)
                    k：用于比较的近邻数量 (should be an odd number)
    
        Returns：    sortedClassCount[0][0]：分类结果
        """
        #dataSet.shape[0]：求dataSet矩阵的行数
        #dataSet.shape[1]：求dataSet矩阵的列数
        #dataSet.shape：元组形式输出矩阵行数、列数
        dataSetSize = dataSet.shape[0]
        #tile(A, B)：将A重复B次，其中B可以是int类型也可以是元组类型
        #这句话相当于向量inX与矩阵dataSet里面的每组数据做差
        diffMat = tile(inX, (dataSetSize, 1)) - dataSet
        #对求差后的矩阵求平方
        sqDiffMat = diffMat**2
        #sqDiffMat.sum(axis=0)：对矩阵的每一列求和
        #sqDiffMat.sum(axis=1)：对矩阵的每一行求和
        #sqDiffMat.sum()：对整个矩阵求和
        sqDistances = sqDiffMat.sum(axis=1)
        #求平方根
        distances = sqDistances**0.5
        #对上式结果进行排序
        sortedDistIndicies = distances.argsort()
        #创建字典
        classCount = {}
        #给字典赋值
        for i in range(k):
            #字典的key
            voteIlabel = labels[sortedDistIndicies[i]]
            #classCount.get(voteIlabel,0)：如果字典键的值中有voteIlabel，则返回0（第二个参数的值）
            classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        #对classCount进行排序，sroted、items以及itermgetter随后讲解@1
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        #返回分类结果
        return sortedClassCount[0][0]

保存编写好的kNN.py模块，此时如果你不重新加载模块，你的命令提示符里面已经加载过的模块是不会自动更新的。所以我们需要调用imp模块中的reload来重新加载新保存的模块。我们输入两个不同的例子\[0.9, 0.9\]\[0.1, 0.1\]，得到相应的分类结果并输出。

输出结果：

>>> from imp import reload
    >>> reload(kNN)
    
    >>> kNN.classify0([0.9,0.9], group, labels, 3)
    'A'
    >>> kNN.classify0([0.1,0.1], group, labels, 3)
    'B'

## 三、主要区分函数： ##

详解：  
1.sorted,sort以及argsort：

[http://blog.csdn.net/u011475210/article/details/77769245][http_blog.csdn.net_u011475210_article_details_77769245]

[http://blog.csdn.net/u011475210/article/details/77770751][http_blog.csdn.net_u011475210_article_details_77770751]

2.items等：

[http://blog.csdn.net/u011475210/article/details/77770145][http_blog.csdn.net_u011475210_article_details_77770145]

3.itemgetter等：

[http://blog.csdn.net/u011475210/article/details/77770772][http_blog.csdn.net_u011475210_article_details_77770772]

**系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～**

**完的汪(∪｡∪)｡｡｡zzz**

[http_blog.csdn.net_u011475210]: http://blog.csdn.net/u011475210
[https_github.com_WordZzzz_ML_tree_master_Ch02]: https://github.com/WordZzzz/ML/tree/master/Ch02
[https_www.manning.com_books_machine-learning-in-action]: https://www.manning.com/books/machine-learning-in-action
[SouthEast]: /images/20220609/13bbe09f7da04627964a75059c9c6ea8.png
[SouthEast 1]: /images/20220609/2faca988caec47c1ac428d67580a8671.png
[http_blog.csdn.net_u011475210_article_details_77769245]: http://blog.csdn.net/u011475210/article/details/77769245
[http_blog.csdn.net_u011475210_article_details_77770751]: http://blog.csdn.net/u011475210/article/details/77770751
[http_blog.csdn.net_u011475210_article_details_77770145]: http://blog.csdn.net/u011475210/article/details/77770145
[http_blog.csdn.net_u011475210_article_details_77770772]: http://blog.csdn.net/u011475210/article/details/77770772