k近邻算法Machine Learning In Action学习笔记

优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高。 

适用数据范围：数值型和标称型。

k近邻算法的一般流程

收集数据：可以使用任何方法。

准备数据：距离计算所需要的数值，最好是结构化的数据格式。

分析数据：可以使用任何方法。

训练算法：此步骤不适用于k近邻算法。

测试算法：计算错误率。

使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

工作原理：

1.存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。

2.输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。

3.一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。

4.最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

伪代码：

对未知类别属性的数据集中的每个点依次执行以下操作：

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

    2. 按照距离递增次序排序；

    3. 选取与当前点距离最小的k个点；

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

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

示例1：在约会网站上使用k近邻算法

收集数据：提供文本文件。

准备数据：使用Python解析文本文件。

分析数据：使用Matplotlib画二维扩散图。

训练算法：此步骤不适用于k近邻算法。

测试算法：使用海伦提供的部分数据作为测试样本。

注意：

1.测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。

2.必须明确地通知解释器，告诉它列表中存储的元素值为整型，否则Python语言会将这些元素当作字符串处理。

归一化数值：

数字差值最大的属性对计算结果的影响最大，但是特征是同等重要的，因此作为等权重的特征之一，不应该如此严重地影响到计算结果。

在处理这种不同取值范围的特征值时，我们通常采用的方法是将数值归一化，如将取值范围处理为0到1或者-1到1之间。

下面的公式可以将任意取值范围的特征值转化为0到1区间内的值：

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

全部代码：

# -*- coding: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
group, labels = createDataSet()
# 4个输入参数：需要分类的输入向量是inX，输入的训练样本集为dataSet，标签向量为labels，k表示用于选择最近邻居的数目
def classify0(inX, dataSet=group, labels=labels, k=3):
    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 = {}
    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]
# 处理输入的文件到适用的数据格式
def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())
    returnMat = zeros((numberOfLines, 3))  # prepare matrix to return
    classLabelVector = []  # prepare labels return
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector
# 归一化数据到0-1之间
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))  # element wise divide
    return normDataSet, ranges, minVals
# 分类器针对约会网站的测试代码
def datingClassTest():
    hoRatio = 0.50  # hold out 10%
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')  # load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m * hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
        if (classifierResult != datingLabels[i]):
            errorCount += 1.0
    print "the total error rate is: %f" % (errorCount / float(numTestVecs))
    print errorCount

参考资料：

1. Peter Harrington《机器学习实战》第二章

来自为知笔记(Wiz)