机器学习实战――K近邻算法

本博客基于机器学习实战这本书，主要是对机器学习的算法原理及Python实现进行详细解释，若是有些没有阐述清楚的，看到的请指出。

第二章的K近邻算法是一个简单的机器学习算法。

K近邻算法：

原理：收集一个样本数据集合，并且样本集中每个数据都存在标签。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据(最近邻)的分类标签。选择样本数据集中前K个最相似的数据，这就是K近邻算法中K的出处，通常k是不大于20的整数。选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

算法实现：新建一个kNN.py文件

1. 导入数据

#-*- coding: utf-8 -*- #表示使用这个编码

from numpy import * #导入科学计算包NumPy，没安装赶紧百度安装

import operator #运算符模块，k近邻算法执行排序操作时将使用这个模块提供的函数

import pdb #在Python交互环境中启用调试

from os import listdir # os 模块包含了许多对目录操作的函数 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

保存后import kNN

group,labels = kNN.createDataSet()，然后就可以得到group，labels

具体的kNN算法：

思想：计算已知类别数据集中的点和当前点之间的距离;

按照距离递增次序排序;

选取与当前点距离最小的k个点;

确定前k个点所在类别的出现频率;

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

def classify0(inX,dataSet,labels,k):#inX是测试向量，dataSet是样本向量，labels是样本标签向量，k用于选择最近邻居的数目

dataSetSize = dataSet.shape[0] #得到数组的行数。即知道有几个训练数据，0是行，1是列

diffMat = tile(inX,(dataSetSize,1)) - dataSet #tile将原来的一个数组，扩充成了dataSetSize个一样的数组。diffMat得到了目标与训练数值之间的差值。

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#得到距离最小的前k个点的分类标签

sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse = True)#对classCount字典分解为元素列表，使用itemgetter方法按照第二个元素的次序对元组进行排序，返回频率最高的元素标签，计数前k个标签的分类，返回频率最高的那个标签

return sortedClassCount[0][0]

这样就可以使用该程序进行数据预测了。

kNN.classify0([0,0],group,labels,3)输出结果为B。

测试kNN算法

这个测试是作者提供的文本文件，先解析文本，画二维扩散图，kNN不用进行训练，直接调用文本数据计算k近邻就可以。

将文本记录转换为NumPy的解析程序

def file2matrix(filename):#将文本记录转换成numpy的解析程序

fr = open(filename) #这是python打开文件的方式

arrayOLines = fr.readlines()#自动将文件内容分析成一个行的列表

numberOfLines = len(arrayOLines)#得到文件的行数

returnMat = zeros((numberOfLines,3))

classLabelVector = []

enumLabelVector = []

index = 0

for line in arrayOLines:

line = line.strip()#截掉所有的回车符

listFromLine = line.split('t')#使用tab字符t将上一步得到的整行数据分割成元素列表

returnMat[index,:] = listFromLine[0:3]#选取前三个元素存储到特征矩阵中

classLabelVector.append(listFromLine[-1])#用-1表示最后一列元素，把标签放入这个向量中

if cmp(listFromLine[-1],'didntLike')==0:

enumLabelVector.append(1)

elif cmp(listFromLine[-1],'smallDoses')==0:

enumLabelVector.append(2)

elif cmp(listFromLine[-1],'largeDoses')==0:

enumLabelVector.append(3)

index += 1

return returnMat,enumLabelVector #返回数据矩阵和标签向量

可以使用reload(kNN)

datingDataMat,datingLabels = kNN.file2matrix(‘datingTestSet.txt’)得到数据矩阵和标签向量。

使用Matplotlib制作原始数据的散点图

fig = plt.figure()

ax = fig.add_subplot(131)

ax.scatter(datingDataMat[:,1],datingDataMat[:,2])

ax = fig.add_subplot(132)

ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(vector),15.0*array(vector))

ax = fig.add_subplot(133)

ax.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0*array(vector),15.0*array(vector))

plt.show()

在计算KNN距离时，若某一列的数值远大于其他列， 那这一列对计算距离时的影响最大。将数据归一化，每一列的数据取值范围处理为0-1之间，这样每一列的数据对结果影响都一样。

归一化特征值：

def autoNorm(dataSet):

minVals = dataSet.min(0)#获得最小值，(0)是从列中获取最小值，而不是当前行，就是每列都取一个最小值

maxVals = dataSet.max(0)#获得最大值

ranges = maxVals - minVals#获得取值范围

normDataSet = zeros(shape(dataSet))#初始化新矩阵

m = dataSet.shape[0]#获得列的长度

normDataSet = dataSet - tile(minVals,(m,1))#特征值是1000×3,而最小值和范围都是1×3,用tile函数将变量内容复制成输入矩阵一样大小的矩阵

normDataSet = normDataSet/tile(ranges,(m,1))#/可能是除法，在numpy中，矩阵除法要用linalg.solve(matA,matB).

return normDataSet,ranges,minVals

将数据集分为测试数据和样本数据

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)#前m×hoRatio个数据是测试的，后面的是样本

print the calssifier 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(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('datingTestSet.txt') #读入样本文件，其实不算是样本，是一个标准文件

normMat, ranges, minVals = autoNorm(datingDataMat)#归一化

inArr = array([ffMiles, percentTats, iceCream])#组成测试向量

# pdb.set_trace()#可debug

classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels,3)#进行分类

# return test_vec_g,normMat,datingLabels

print 'You will probably like this person:', resultList[classifierResult - 1]#打印结果

在python下输入kNN.classifyPerson()，输入某人的信息，就可以得到该人的标签。

8.手写识别系统的示例：

收集数据时，要将手写的字符图像转换成向量。

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)#把标签添加进list

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)#对向量进行k近邻测试

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))

使用kNN.handwritingClassTest()测试该函数的输出结果，依次测试每个文件，输出结果，计算错误率，因为分类算法不是绝对的，只是一个概率问题，所以对每一组数据都有错误率。

至此，第二章基本阐述完毕，k近邻算法是分类数据最简单有效的算法，使用算法时，我们必须有接近实际数据的训练样本数据。k近邻算法必须保存全部数据集，如果训练数据集很大的话，必须使用大量的存储空间。

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

缺点：nisan复杂度高，空间复杂度高。

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