Python K最近邻从原理到实现的方法

本来这篇文章是5月份写的，今天修改了一下内容，就成今天发表的了，CSDN这是出BUG了还是什么改规则了。。。

引文 ：决策树和基于规则的分类器都是 积极学习方法 （eager learner）的例子，因为一旦训练数据可用，他们就开始学习从输入属性到类标号的映射模型。一个相反的策略是推迟对训练数据的建模，直到需要分类测试样例时再进行。采用这种策略的技术被称为 消极学习法 （lazy learner）。 最近邻分类器 就是这样的一种方法。

注：KNN既可以用于分类，也可以用于回归。

1.K最近邻分类器原理

首先给出一张图，根据这张图来理解最近邻分类器，如下：

根据上图所示，有两类不同的样本数据，分别用 蓝色的小正方形 和 红色的小三角形 表示，而图正中间的那个 绿色的圆 所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。

我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他or她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到：

• 如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
• 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。其关键还在于K值的选取，所以应当谨慎。

KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

KNN 算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。

前面的例子中强调了选择合适的K值的重要性。如果太小，则最近邻分类器容易受到训练数据的噪声而产生的过分拟合的影响；相反，如果K太大，最近分类器可能会误会分类测试样例，因为最近邻列表中可能包含远离其近邻的数据点。（如下图所示）

K较大时的最近邻分类

            
from numpy import *
import operator

class KNN:
  def createDataset(self):
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

  def KnnClassify(self,testX,trainX,labels,K):
    [N,M]=trainX.shape

  #calculate the distance between testX and other training samples
    difference = tile(testX,(N,1)) - trainX # tile for array and repeat for matrix in Python, == repmat in Matlab
    difference = difference ** 2 # take pow(difference,2)
    distance = difference.sum(1) # take the sum of difference from all dimensions
    distance = distance ** 0.5
    sortdiffidx = distance.argsort()

  # find the k nearest neighbours
    vote = {} #create the dictionary
    for i in range(K):
      ith_label = labels[sortdiffidx[i]];
      vote[ith_label] = vote.get(ith_label,0)+1 #get(ith_label,0) : if dictionary 'vote' exist key 'ith_label', return vote[ith_label]; else return 0
    sortedvote = sorted(vote.iteritems(),key = lambda x:x[1], reverse = True)
    # 'key = lambda x: x[1]' can be substituted by operator.itemgetter(1)
    return sortedvote[0][0]

k = KNN() #create KNN object
group,labels = k.createDataset()
cls = k.KnnClassify([0,0],group,labels,3)
print cls
          

            
>>>import os
>>>os.chdir("/home/liudiwei/code/data_miningKNN/")
>>>execfile("KNN.py")
          

            
$ python KNN.py
          

            
>>>import KNN
>>> KNN.k.KnnClassify([0,0],KNN.group,KNN.labels,3)