机器学习K近邻算法的实现主要是参考《机器学习实战》这本书。

一、K近邻（KNN）算法

K最近邻(k-Nearest Neighbour，KNN)分类算法，理解的思路是：如果一个样本在特征空间中的K个最相似（即特征空间最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。

我们采用一个图来进行说明（如下）：

图中的蓝色小正方形和红色的小正方形属于两类不同的样本数据，图正中间的绿色的圆代表的是待分类的数据。现在我们可以根据K最近邻算法来判断绿色的圆属于哪一类数据？

• 如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，由于红色三角形所占比例为2/3，选择概率大的一类，我们可以认为绿色的这个待分类点属于红色的三角形一类。
• 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，由于蓝牙正方形所占比例为3/5，选择概率大的一类，我们可以认为绿色的这个待分类点属于蓝色的正方形一类。

以上就是对K最近邻算法的理解。

K-近邻算法的特点是：

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

二、算法实践

现在我们对《机器学习实战》中K最近邻的代码进行实现

首先要导入样本数据，我们建立KNN.py的模块，用来生成数据库，代码如下：

 from numpy import *

 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

在代码中，我们导入了Python的两个模块：科学计算包Numpy和运算符模块。Python中导入Nump模块可以参考之前的Python安装reque模块文章。

然后实现K-近邻算法，

K-近邻算法的具体思想如下：

（1）计算已知类别数据集中的点与当前点之间的距离

（2）按照距离递增次序排序

（3）选取与当前点距离最小的k个点

（4）确定前k个点所在类别的出现频率

（5）返回前k个点中出现频率最高的类别作为当前点的预测分类

Python代码如下：

 # coding : utf-8

 from numpy import *

 import operator

 import kNN

 group, labels = kNN.createDataSet()

 def classify(inX, dataSet, labels, k):

     dataSetSize = dataSet.shape[0]                    #得到数组的行数，即知道有几个数据集

     diffMat = tile(inX, (dataSetSize,1)) - dataSet    #样本与训练集的差值矩阵

     sqDiffMat = diffMat**2                            #各元素分别平方

     sqDistances = sqDiffMat.sum(axis=1)               #每一行元素求和

     distances = sqDistances**0.5                      #开方，得到距离

     sortedDistances = distances.argsort()             #按照distances中元素进行升序排列后得到相应下表的列表

     classCount = {}                                   #选择距离最小的k个点

     for i in range(k):

         numOflabel = labels[sortedDistances[i]]

         classCount[numOflabel] = classCount.get(numOflabel,0) + 1

     sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1),reverse=True) #按classCount字典的value（类别出现次数）降序排列

     return sortedClassCount[0][0]

 test = classify([0,0], group, labels, 3)

 print test

运算结果为：

B

输出结果是B：说明我们新的数据（[0,0]）是属于B类。

代码解析：

classify函数的参数为：

• inX：用于分类的输入向量
• dataSet：训练样本集合
• labels：标签向量
• k：K-近邻算法中的k

shape函数：是numpy.core.fromnumeric中的函数，它的功能是读取矩阵的长度，比如shape[0]就是读取矩阵第一维度的长度。它的输入参数可以是一个整数表示维                       度，也可以是一个矩阵。如下所示：

>>> from numpy import *

>>> shape([1])

(1L,)

>>> shape([[1],[2]])

(2L, 1L)

>>> shape(3)

()

>>>

>>> e=eye(3)

>>> e

array([[ 1.,  0.,  0.],

       [ 0.,  1.,  0.],

       [ 0.,  0.,  1.]])

>>> e.shape

(3L, 3L)

>>> e.shape[0]

3L

>>>

一维矩阵，shape([1])，结果为(1L,);

　   二维矩阵，shape([1],[2]), 结果为(2L,1L);

　　单独的数字，返回值为空；

　　创建一个单位矩阵e,可以判断e的形状，e.shape的结果为(3L,3L); 我们只取第一维度长度（即行数）e.shape[0]的值为3L。

tile函数：tile函数是模板numpy.lib.shape_base中的函数。函数的形式是tile(A,reps)。
             A的类型众多，几乎所有类型都可以：array, list, tuple, dict, matrix以及基本数据类型int, string, float以及bool类型。
             reps的类型也很多，可以是tuple，list, dict, array, int,bool.但不可以是float, string, matrix类型。

　   tile函数是为了扩充数组元素，看一下举例：

>>> from numpy import *

>>> a=array([1,2])

>>> tile(a,(3,2))      #构造3X2个copy

array([[1, 2, 1, 2],

       [1, 2, 1, 2],

       [1, 2, 1, 2]])

>>> tile(7,(3,2))

array([[7, 7],

       [7, 7],

       [7, 7]])

>>>

　　简单理解tile(a,(3,2))就是对a进行3X2的复制。具体的理解可以参考这篇文章：http://blog.sina.com.cn/s/blog_6bd0612b0101cr3u.html。

在算法程序中tile（inX, (dataSetSize,1)）就是对inX进行了复制了dataSetSize行，1表示列的倍数。

diffMat = tile(inX, (dataSetSize,1)) - dataSet 这一行代码表示前一个二维数组矩阵的每一个元素减去后一个数组对应的元素值，实现了矩阵之间的减法。

sqDistances = sqDiffMat.sum(axis=1)这一行代码中，axis=1：参数等于1的时候，表示矩阵中行之间的数的求和，等于0的时候表示列之间数的求和。

classCount.get(numOflabel,0) + 1：这一行代码中使用了字典的get方法，在这里需要理解，get方法可以访问字典中键对应的值。key存在则返回对应value，键不存在返回None，也可以设定自己的返回参数，设置的方法是：变量名.get（键名,参数）。在这里我们设置的参数为0，说明在访问不到键对应值时，返回的参数为0，然后对其加1，如此循环，便可以得到key出现的频率。

sorted函数：

为Python内置的排序函数，可以对list或者iterator进行排序，官网文档见：http://docs.python.org/2/library/functions.html?highlight=sorted#sorted，该函数原型为：

sorted(iterable[, cmp[, key[, reverse]]])

参数解释：

（1）iterable指定要排序的list或者iterable；

（2）cmp为函数，指定排序时进行比较的函数，可以指定一个函数或者lambda函数，如：

students为类对象的list，每个成员有三个域，用sorted进行比较时可以自己定cmp函数，例如这里要通过比较第三个数据成员来排序，代码可以这样写：
      students = [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
      sorted(students, key=lambda student : student[2])
（3）key为函数，指定取待排序元素的哪一项进行排序，函数用上面的例子来说明，代码如下：
      sorted(students, key=lambda student : student[2])

key指定的lambda函数功能是去元素student的第三个域（即：student[2]），因此sorted排序时，会以students所有元素的第三个域来进行排序。

　　也可以用operator.itemgetter函数来实现，例如要通过student的第三个域排序，可以这么写：
　　sorted(students, key=operator.itemgetter(2)) 
　　sorted函数也可以进行多级排序，例如要根据第二个域和第三个域进行排序，可以这么写：
　　sorted(students, key=operator.itemgetter(1,2))  即先跟句第二个域排序，再根据第三个域排序。

（4）reverse参数就不用多说了，是一个bool变量，表示升序还是降序排列，默认为false（升序排列），定义为True时将按降序排列。

在算法程序中，我们也可以用另一种方法来获得最大概率的分类，代码修改如下：

     classCount = {}

     for i in range(k):

         numOflabel = labels[sortedDistances[i]]

         classCount[numOflabel] = classCount.get(numOflabel,0) + 1

     maxCount = 0

     for key, value in classCount.items():

         if value > maxCount:

             maxCount = value

             maxIndex = key

     return maxIndex

同样可以实现。