k近邻算法

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

用官方的话来说，所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

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

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

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

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

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

KNN算法的Python代码实现 KNN.py


#encoding:utf-8

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


def classify0(inX,dataSet,labels,k):
    #返回“数组”的行数，如果shape[1]返回的则是数组的列数
    dataSetSize = dataSet.shape[0]
    #两个“数组”相减，得到新的数组
    diffMat = tile(inX,(dataSetSize,1)) - dataSet
    #求平方
    sqDiffMat = diffMat **2
    #求和，返回的是一维数组
    sqDistances = sqDiffMat.sum(axis=1)
    #开方，即测试点到其余各个点的距离
    distances = sqDistances **0.5
    #排序，返回值是原数组从小到大排序的下标值
    sortedDistIndices = distances.argsort()
    #定义一个空的字典
    classCount = {}
    for i in range(k):
        #返回距离最近的k个点所对应的标签值
        voteIlabel = labels[sortedDistIndices[i]]
        #存放到字典中
        classCount[voteIlabel] = classCount.get(voteIlabel,0)+1
        #排序 
        classCount.iteritems() 
    输出键值对 key代表排序的关键字 True代表降序
    sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse = True)
    #返回距离最小的点对应的标签
    return sortedClassCount[0][0]

调用方式：打开CMD，进入KNN.py文件所在的目录，输入Python，依次输入


    >>> import kNN
    >>> group,labels = kNN.createDataSet()
    >>> kNN.classify0([0,0],group,labels,3)
    'B'
Loading Disqus comments...
Table of Contents