K-近邻算法

1. 概述

(1)定义

K-近邻算法采用测量不同特征值之间的距离方法进行分类。

(2) 优缺点

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

(3) 一般流程

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

2. 实施 kNN 分类算法

公式

$ d = \sqrt{(xA_0 - xB_0)^2 + (xA_1 - xB_1)^2}$

伪代码

对未知类别属性的数据集中的每个点依次执行以下操作：
. 计算已知类别数据集中的点和当前点之间的距离；
. 按照距离递增次序排列；
. 选取与当前点距离最小的 k 个点;
. 确定前 k 个点所在类别的出现概率；
. 返回前 k 个点出现频率最高的类别作为当前点的预测分类；

代码

def classify0(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
    
    sortedDistIndicies = distances.argsort()
    classCount = {}
    
    // 选择距离最小的 k 个点
    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]

3. 归一化数值

数值相差太大的属性对计算结果有很大的影响，在处理不同取值范围的特征值时，可以将数值归一化，将任意取值范围的特征值转化为 [0, 1] 区间的值。

$ newValue = (oldValue - min) / (max - min)$

其中 min 和 max 分别是数据集中的最小特征值和最大特征值。

归一化代码

def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    rangeD = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet/tile(rangeD, (m, 1))
    return normDataSet, rangeD, minVals

4. 测试算法

机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的 90% 作为训练分类，使用剩下的 10% 数据去测试分类器，检测分类器的正确率。

5.总结

K-近邻算法是分类数据最简单最有效的算法，但是它的缺陷是无法给出任何数据的基础结构信息。