本章小结

k-近邻算法是分类数据最简单最有效的算法，本章通过两个例子讲述了如何使用k-近邻算法构造分类器。k-近邻算法是基于实例的学习，使用算法是我们必须有接近实际数据的训练样本数据。k-近邻算法必须保存全部数据集，如果训练的数据集很大们必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。

k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。下一章我们使用概率测量方法处理分类问题，该算法可以解决这个问题。

KNN介绍

k近邻法(k-nearest neighbors)是由Cover和Hart于1968年提出的，它是懒惰学习(lazy learning)的著名代表。
它的工作机制比较简单：

给定一个测试样本
计算它到训练样本的距离
取离测试样本最近的k个训练样本
“投票法”选出在这k个样本中出现最多的类别，就是预测的结果

距离衡量的标准有很多，常见的有：LpLp距离、切比雪夫距离、马氏距离、巴氏距离、余弦值等。

什么意思呢？先来看这张图

我们对应上面的流程来说

1.给定了红色和蓝色的训练样本，绿色为测试样本
2.计算绿色点到其他点的距离
3.选取离绿点最近的k个点
4.选取k个点中，同种颜色最多的类。例如：k=1时，k个点全是蓝色，那预测结果就是Class 1；k=3时，k个点中两个红色一个蓝色，那预测结果就是Class 2

优/缺点

优点

简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；
可用于数值型数据和离散型数据；
训练时间复杂度为O(n)；无数据输入假定；
对异常值不敏感。

缺点

计算复杂性高；空间复杂性高；
样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。
最大的缺点是无法给出数据的内在含义。

补充一点：由于它属于懒惰学习，因此需要大量的空间来存储训练实例，在预测时它还需要与已知所有实例进行比较，增大了计算量。

这里介绍一下，当样本不平衡时的影响。

从直观上可以看出X应该属于ω1ω1，这是理所应当的。对于Y看起来应该属于ω1ω1，但事实上在k范围内，更多的点属于ω2ω2，这就造成了错误分类。

代码

from numpy import *
import operator
from os import listdir


# 创建数据和分组
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


# 对输入的inX进行上述数据集的分类
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 = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


# 读取文件数据转化矩阵
def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)
    returnMat = zeros((numberOfLines, 3))
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0: 3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector


# 使数据归一化--归一化特征值
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))
    return normDataSet, ranges, minVals


# 分类器测试代码
def datingClassTest():
    hoRatio = 0.10
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    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)))


# 约会网站预测函数
def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(input("percentage of time spent playing video games?"))
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles, percentTats, iceCream])
    classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)
    print("You will probably like this person: ", resultList[classifierResult - 1])


# 将图像转换为测试向量
def img2vector(filename):
    returnVect = zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0, 32 * i + j] = int(lineStr[j])
    return returnVect


# 手写数字识别系统的测试代码
def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with:%d, the real answer is : %d" % (classifierResult, classNumStr))
        if classifierResult != classNumStr:
            errorCount += 1.0
    print("\nthe total number of errors is: %d" % errorCount)
    print("\nthe total error rate is: %f" % (errorCount / float(mTest)))

参考资料

K-近邻算法介绍与代码实现

勘误

P19 程序清单2-1 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={}          
    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]

代码12行 iteritems() 出错，为Python2.x用法，如果使用Python 3.x应改为**items()**，我这里使用的是Python3.8版本。

P22 在Python命令提示符下输入下面命令

>>> reload(kNN)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'reload' is not defined
    
>>> datingDataMat, datingLabels = kNN.file2matrix('datingTestSet.txt')
# 错误信息
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "D:\JupyterWorkspace\kNN.py", line 37, in file2matrix
    classLabelVector.append(int(listFromLine[-1]))

1、 reload()出错，同样是因为Python2.x与Python3.x的不同，在Pytho3.x中，应变为如下命令行：

1 2	>>> import imp >>> imp.reload(kNN)

2、引入文件出错，文件“datingTestSet.txt”中第四列是字符串，导致代码运行出错，应改为“datingTestSet2.txt”。

P23 重新输入上面代码，调用scatter函数时使用下列参数

>>> ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0*array(datingLabels),15.0*array(datingLabels))
# 错误信息
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'array' is not defined

在使用array时出现错误，原因是没有引入numpy库，在运行此行命令前，输入**from numpy import ***即可运行。

P28 程序清单2-5 约会网站预测函数

>>> kNN.classifyPerson()
# 错误信息
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "D:\JupyterWorkspace\kNN.py", line 76, in classifyPerson
    percentTats = float(raw_input("percentage of time spent playing video games?"))
NameError: name 'raw_input' is not defined

raw_input是2.x版本的输入函数，在新版本环境下会报错，该函数未定义。在3.x版本中应该用**input()代替raw_input()**。

Bo

《机器学习实战》学习心得&勘误--第二章