机器学习笔记1_KNN算法（k-近邻）

简介：

k-NearestNeighbor算法是一种基本分类与回归方法，原理是根据提供样本数据集（包含了数据项和数据项所属的分类），然后在输入了未知数据项后， 根据已有的数据集，计算出每个数据项和未知数据项的距离，再取前k个最相似的数据，以此来确定未知数据项的分类。（通常k不大于20） 我们可以得知KNN是比较简单的一种分类回归方法（回归的部分之后在说，这篇主要是讲分类），根据已经确认的输入和输出来对新的输入进行分类，属于监督学习。

我们来举一个简单的例子来理解下KNN，假设我们要区分大屏幕手机和小屏幕的手机，然后我们看下下面的表格（数据随便写的，不要太在意真实性）

这时候我们来了一台4.5寸的手机，我们能看出来是小屏幕手机.通过KNN算法就是计算4.5和样本数据的每台手机的距离，假设我们这里k设为3， 距离4.5最近的就是5.0（差0.5），4.0（差0.5），3.5（差1）,这里有两个小屏幕，一个大屏幕，所以4.5是小屏幕手机。KNN算法的思想就是用存在的数据和 未知分类数据的相似度去比较，最后得出未知分类的类型。

优缺点：

从上面的例子其实我们可以简单的看出来一些KNN算法的问题，首先未知数据得和所有的样本数据进行比较，确定距离也就是相似度，这样就计算成本很大，每次有未知分类的数据 进来就得计算一遍。然后因为数据集是一开始就给好的，如果数据集里面的数据有些比较特殊的数据距离特别大或者特别小，或者数据的密度差别很大也会影响预测的准确性。 优点：精度高，对异常数据不敏感，无数据输入假定 缺点：计算复杂度高，空间复杂度高 试用数据范围：数值型和标称型

KNN算法的实现：

kNN 算法伪代码： 对于新输入的每一个在数据集中的数据点item： 计算样本数据与数据点item的距离 将距离排序：从小到大 选取前K个最短距离 选取这K个中最多的分类类别 返回该类别来作为目标数据点的预测值

def knn(item, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(item, (dataSetSize,1)) – dataSet
    # 类似中学里面的两点之间的距离公式
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5

    # 将距离排序：从小到大
    sortedDistIndicies = distances.argsort()
    # 选取前K个最短距离， 选取这K个中最多的分类类别
    classCount={}
    for i in range(k)：
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]
复制代码

参考资料：

1.机器学习---周志华
2.机器学习实战---Peter