机器学习实战—第2章 k-近邻算法
2.1 K-近邻算法概述
k-近邻算法
- 优点：
- 精度高、对异常值不敏感、无数据输入假定
- 缺点
- 计算复杂度高、空间复杂度高
- 使用数据范围：
- 数值型和标称型
k-近邻算法的工作原理：
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即知道样本集中每一数据与所属分类的关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，只选择样本数据集中前k个最相似的数据，通常k不大于20，选择k个最相似数据中出现次数最多的分类，作为数据的分类。
k-近邻算法的一般流程：
- 收集数据：可以使用任何方法
- 准备数据：距离计算所需要的数值，最好是结构化的数据格式
- 分析数据：可以使用任何方法
- 训练算法：此步骤不适用于k-近邻算法
- 测试算法：计算错误率
- 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理
# -*- coding: utf-8 -*-
"""
Created on Wed May 24 21:42:55 2017
@name: kNN.py
@author: L. D. Xiao
"""
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
#================================ kNN算法 ======================================
# kNN对未知类别属性的数据集中的每个点依次执行以下操作：
# 计算已知类别数据集中的点与当前点之间的距离；
# 按照距离递增次序排序；
# 选取与当前点距离最小的k个点；
# 确定前k个点所在类别的出现频率；
# 返回前k个点出现频率最高的类别作为当前点的预测分类
#==============================================================================
def classify0(inX, dataSet, labels,k):
dataSetSize = dataSet.shape[0]
#numpy.tile(A,(m,n)):在行方向上重复A m次，列方向上重复A n次
diffMat = tile(inX, (dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5
sortedDistIndices = distances.argsort()
classCount={}
for i in range(k):
voteIlabel = labels[sortedDistIndices[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]2.2 示例：使用k-近邻算法改进约会网站的配对效果
- 收集数据：提供文本文件
- 准备数据：使用Python解析文本文件
- 分析数据：使用Matplotlib画二维散点图
- 训练算法：此步骤不适用于k-近邻算法
- 测试算法：使用提供的部分数据作为测试样本
- 使用算法：产生简单的命令行程序，然后可以输入一些特征数据以判断对方是否为喜欢的类型
利用Python处理文本文件数据：
#==============================================================================
# 将文本文件记录转换为NumPy矩阵
#==============================================================================
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使用Matplotlib可视化分析数据：
#==============================================================================
# 分析数据：使用Matplotlib创建散点图
#==============================================================================
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(returnMat[:,4], returnMat[:,5], 15*array(returnMat[:,4]), 15*array(returnMat[:,4]))
针对各特征归一化，以有效的计算各样本间的距离：
#==============================================================================
# 将数值特征归一化处理 newValue = (oldValue - min) / (max - min)
#==============================================================================
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构建分类器针对约会网站的测试代码：
#==============================================================================
# 程序清单2-4：分类器针对约会网站的测试代码
#==============================================================================
def datingClassTest():
hoRatio = 0.10
datingDataMat,datingLabels = file2matrix('datingTestSet.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))
使用算法：构建完整可用系统：
#==============================================================================
# 程序清单2-5：约会网站预测函数
#==============================================================================
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
percentTats = float(raw_input(\
"percentage of time spent playing video games ?"))
ffMiles = float(raw_input("frequent flier miles earned per year ?"))
iceCream = float(raw_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]2.3 示例：手写识别系统
- 收集数据：提供文本文件
- 准备数据：编写函数classify0()，将图像格式转换为分类器使用的list格式
- 分析数据：在Python命令提示符中检查数据，确保它符合要求
- 训练算法：此步骤不适用于k-近邻算法
- 测试算法：编写函数使用提供的部分数据集作为测试样本
- 使用算法：本示例未完成
#==============================================================================
# 将32*32的二进制图像转换为1*1024的向量
#==============================================================================
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
#==============================================================================
# 程序清单2-6：手写数字识别系统的测试代码
#==============================================================================
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: %d" % (errorCount/float(mTest))2.4 本章小结
k-近邻算法是分类数据最简单最有效的算法。k-近邻算法是基于实例的学习，使用算法时必须有接近实际数据的训练数据样本数据。k-近邻算法必须保存全部数据集，如果训练数据集很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时很可能非常耗时。
k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此也无法知晓平均实例样本和典型实例样本具有什么特征。
参考文献
Harrington, Peter. “机器学习实战.” 人民邮电出版社, 北京 (2013).