第 2 章 k-近邻算法
[TOC]
本章内容：
- k-近邻分类算法
- 从文本文件中解析和导入数据
- 使用 Matplotlib 创建扩散图
- 归一化数值
1. k-近邻算法概述
简单地说，k-近邻算法 采用测量不同特征值之间的距离方法进行分类。
- 优点：精度高、对异常值部敏感、无数据输入假定
- 缺点：计算复杂度高、空间复杂度高
- 适用数据范围：数值型和标称型
k-近邻算法（kNN）：它的工作原理是存在一个样本数据集合（训练样本集），并且样本集中每个数据都存在标签，即我们知道样本集中每一数据域所属分类的对应关系。输入每一标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前 k 个最相似的数据，这就是 k-近邻算法中 k 的出处，通常 k 是不大于 20 的整数。最后，选择 k 个最相似数据中出现次数最多的分类，作为新数据的分类。
示例：基于电影中出现的亲吻、打斗出现的次数，使用 k-近邻算法构造程序，自动划分电影的题材类型。有人统计过很多电影的打斗镜头和接吻镜头，图2-1 显示了 6 部电影的打斗和接吻镜头数。假如有一部未看过的电影，如何确定的它是爱情片还是动作片呢？可以使用 kNN 来解决这个问题：
首先我们需要知道这个未知电影存在多少个打斗镜头和接吻镜头，图2-1 问号位置是该未知电影出现的镜头数图形化展示，具体数字参见表2-1：
计算未知电影与样本集中其他电影的距离，如表2-2 所示：
现在得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到 k 个距离最近的电影。假定 k=3 ，则三个最近的电影依次是He...、Bea...、Cal...。k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影都是爱情片，因此判定未知电影是爱情片。
k-近邻算法的一般流程：
- 收集数据：可以使用任何方法；
- 准备数据：距离计算所需要的数值，最好是结构化的数据格式；
- 分析数据：可以使用任何方法；
- 训练算法：此步骤不适用于 k-近邻算法；
- 测试算法：计算错误率；
- 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行 k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。
1.1 准备：使用 Python 导入数据
s_1_kNN.py文件（创建数据集和标签）：
import numpy as np
import operator
def createDataSet():
group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
print(group)
labels = ['A','A','B','B']
print(labels)
return group, labels
图2-2 是带有类标签信息的四个数据点：
现在我们已经知道 Python 如何解析数据，如何加载数据，以及 kNN 算法的工作原理，接下来将使用这些方法完成分类任务。
1.2 从文本文件中解析数据
本节使用程序中的 classify0() 函数运行 kNN 算法，为每组数据分类。该函数的功能是使用 k-近邻算法将每组数据划分到某个类中，其伪代码如下：
对未知类别属性的数据集中的每个点依次执行以下的操作：
- 计算已知类别数据集中的点与当前点之间的距离
- 按照距离递增次序排序
- 选取与当前点距离最小的 k 个点
- 确定前 k 个点所在类别的出现频率
- 返回前 k 个点出现频率最高的类别作为当前点的预测分类
classify0() 如下：
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0] # dataSet 的长度
diffMat = np.tile(inX, (dataSetSize,1)) - dataSet # 分别求出 测试数据的向量减去训练数据的向量
sqDiffMat = diffMat ** 2 # 求平方
sqDistances = sqDiffMat.sum(axis=1) # 求和
distances = sqDistances ** 0.5 # 求出距离
sortedDistIndicies = np.argsort(distances) # 升序的索引值
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]
classify0() 护士中有 4 个输入参数：用于分类的输入向量是 inX，输入训练样本集是 dataSet，标签向量是 labels，最后的参数 k 表示用于选择最近邻居的数目，其中标签向量的元素数目和矩阵 dataSet 的行数相同。通过使用欧式距离公式，计算两个向量点 xA 和 xB 之间的距离：
计算完所有点之间的距离后，可以对数据按照从小到大的次序排序。然后确定前 k 个距离最小元素所在的主要分类，输入 k 总是正整数；最后，将 classCount 字典分解为元组列表，然后使用工程需第二行导入运算符模块的 itemgetter 方法，按照第二个元素的次序对元组进行排序。此处的排序为逆序，即按照从最大到最小次序排序，最后返回发生频率最高的元素标签。
进行预测：
group, labels = createDataSet()
result = classify0([0.4,0.2], group, labels, 3)
print(result) # B
1.3 如何测试分类器
通过大量的测试数据，我们可以得到分类器的 错误率 ：分类器给出错误结果的次数除以测试执行的总数。错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果
2. 示例：使用 k-近邻算法改进约会网站的配对效果
将约会网站上的人选进行分类：不喜欢的人、魅力一般的人、极具魅力的人
示例：在约会网站上使用 k-近邻算法：
- 收集数据：提供文本文件
- 准备数据：使用 pyhton 解析文本文件
- 分析数据：使用 Matplotlib 画二维扩散图
- 训练算法：使用部分数据作为测试样本。测试样本和非测试样本的区别在于：测试样本是一件完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误
- 使用算法：产生简单的命令行程序，然后可以输入一些特征数据以判断对方是否为自己喜欢的类型
2.1 准备数据：从文本文件中解析数据
样本主要包含以下3种特征：
- 每年获得的飞行常客里程数
- 玩视频游戏所耗时间百分比
- 每周消费的冰淇淋公升数
在将特征数据输入到分类器之前，必须将待处理数据的格式改变为分类器可接受的格式。
file2matrix 函数用来处理输入数据的格式。该函数的输入为文本文件名字符串，输出为训练样本矩阵和类标签向量。
def file2matrix(filename):
fr = open(filename)
arrayOLines = fr.readlines() # 读取文件
numberOfLines = len(arrayOLines) # 行数
returnMat = np.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
2.2 分析数据：使用 Matplotlib 创建散点图
scatter 函数支持个性化标记散点图上的点
filename = 'datingTestSet2.txt'
datingDataMat, datingLabels = file2matrix(filename)
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0 * np.array(datingLabels),15.0 * np.array(datingLabels))
plt.show()
2.3 准备数据：归一化数值
在处理不同取值范围的特征值时，通常采用的方法是将数值归一化，如将取值范围处理为 0 到 1 或者 -1 到 1 之间。下面的公式可以将任意取值范围的特征值转化为 0 到 1 区间内的值：
newValue = (oldValue - min) / (max - min)
其中 min 和 max 分别是数据集中的最小特征值和最大特征值。
添加 autoNorm 函数，来自动将数字特征值转化为 0 到 1 的区间：
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals # 差值
normDataSet = np.zeros(np.shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - np.tile(minVals, (m,1)) # 数据 - 最小值
normDataSet = normDataSet / np.tile(ranges, (m,1)) # 上面的值 / 最小值
# normDataSet = np.linalg.solve(normDataSet,np.tile(ranges, (m,1)))
return normDataSet,ranges,minVals
2.4 测试算法：作为完整程序验证分类器
添加 ditingClassTest 函数：
def datingClassTest():
hoRatio = 0.10
filename = 'datingTestSet2.txt'
datingDataMat, datingLabels = file2matrix(filename)
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("classifierResult:" , classifierResult)
print('datingLabels[i]:',datingLabels[i])
if(classifierResult != datingLabels[i]):
errorCount += 1.0
print('the total error rate is: %f' % (errorCount / float(numTestVecs)))
可以改变函数 datingClassTest 内变量 hoRatio 和变量 k 的值，检测错误率是否随着变量值得变化而增加。依赖于分类算法、数据集和程序设置，分类器的输出结果可能有很大的不同。
2.5 使用算法：构建完整可用系统
添加 classifyPerson 函数，来输入个人信息，判断分类：
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
percenTats = float(input('percentage of time spent playing video games?'))
ffMiles = float(input('freguent flier miles earned per year?'))
iceCream = float(input('liters of ice cream consumed per year?'))
filename = 'datingTestSet2.txt'
datingDataMat, datingLabels = file2matrix(filename)
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = np.array([ffMiles, percenTats, iceCream])
classifierResult = classify0((inArr - minVals) / ranges,normMat, datingLabels, 3)
print('you will probably like this person:',resultList[classifierResult - 1])
3. 示例：手写识别系统
示例说明：构造使用 k-近邻分类器的手写识别系统，来识别数字 0 到 9.需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小的黑白图像。
示例：使用 k-近邻算法的手写识别系统
- 收集数据：提供文本文件；
- 准备数据：编写函数 classify()，将图像格式转换为分类器使用的 list 格式；
- 分析数据：在 python 命令提示符中检查数据，确保它符合要求；
- 训练算法：此步骤不适用 k-近邻算法；
- 测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误；
- 使用算法：本例没有完成此步骤。
3.1 准备数据：将图像转换为测试向量
添加 img2vector 函数，将图像转换为向量：该函数创建 1 X 1024 的 numpy 数组，然后打开给定的文件，循环独处文件的前 32 行，并将每行的头 32 个字符值存储在 numpy 数组中，最后返回数组：
def img2vector(filename):
returnVect = np.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
3.2 测试算法：使用 k-近邻算法识别手写数字
添加 handwritingClassTest 函数，来测试分类器：
def handwritingClassTest():
hwLabels = []
trainingFileList = listdir('trainingDigits')
m = len(trainingFileList)
trainingMat = np.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('classifierResult:',classifierResult)
print('classNumStr:',classNumStr)
if(classifierResult != classNumStr):
errorCount += 1.0
print('errorCount:',errorCount)
print('rate:',errorCount/float(mTest))
改变变量 k 的值、修改函数 handwritingClassTest 随机选取训练样本、改变训练样本的数目，都会对 k-近邻算法的错误率产生影响。
4. 本章小结
k-近邻算法是分类数据最简单最有效的算法。k-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据上的训练样本数据。k-近邻算法必须保存全部数据集，如果训练数据集很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。
另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本具有什么特征。
