本文核心算法根据[美]Peter Harrington著《Machine Learning in Action(中文版译作“机器学习实战”)》整理。
理论作为铺垫,实战更激动人心。
看书和教程过了一周,终于愿意尝试一下真正的算法实现了,不得不说,这个过程非常愉快。
直接进入正题:k-近邻算法。
一、工作原理
存在一个样本数据集合,也称作训练样本集(Training DataSet),并且样本集中每个数据都存在标签(Label),即我们知道样本集中每一数据与所属分类的对应关系。/*回顾监督学习的定义:提供一组“正确答案的数据”。很明显这个算法是监督学习的一种/*
输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,/*后面我们会注意到,这种比较的过程恰恰是整个算法中最耗时的过程/* 然后算法提取样本集中特征最相似的数据(最近邻)的分类标签。一般来说,我们只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的整数。最后,选择k个相似数据中出现次数最多的分类,作为新数据的分类。
简单地说,k-近邻算法采用测量不同特征值之间的距离方法进行分类。
开发机器学习应用的通用步骤:
收集数据->准备数据(结构化的数据格式,例如矩阵)->分析数据(通常可以使用图表使数据的展示更清晰)->训练算法(将得到的知识存储为计算机可以使用的格式)->测试算法(计算错误率)->使用算法
将k-近邻算法对应到以上通用步骤中,其实只有训练算法这一步是可以省略的,后面我们会讲到原因。
二、实现过程
相关环境
操作系统:macOS Sierra 10.12.3
python版本:Python 2.7.10
扩展包:Numpy Matplotlib
IDE:PyCharm CE
1.导入数据
首先建立工程文件夹,并创建名为kNN.py的文件。之后输入以下代码
# coding=utf-8
from numpy import *
import operator
'''-------------------------创建第一个训练用数据集------------------------------'''
def createDataSet():
group = array([[1.0,1.1],[1.0,1.0],[0.0,0.0],[0,0.1]])
labels = ['A','A','B','B']
return group,labels
'''------------------------测试----------------------------------------------'''
group,labels = createDataSet()
print group
print labels
如果能正常输出结果,则这一步ok。
这一步创建了这样一个训练集合:二维空间中有四个点,坐标分别是(1.0,1.1),(1.0,1.0),(0.0,0.0),(0,0.1),我们把前两个点标识为A类点,后两个点标识为B类点。
这时我们给出一个未标识的点,如何判定它应该(更可能)是哪类点呢?
2.实施kNN算法
将工作原理中的描述转换成算法。
对未知类别属性的数据集中的每个点一次执行以下操作:
(1)计算已知类别数据中的点雨当前点的距离;
(2)按照距离递增次序排序;
(3)选取与当前点距离最小的k个点;
(4)确定前k个点所在类别的出现频率;
(5)返回前k个点出现频率最高的类别作为当前点的预测分类
'''-------------------------训练算法--------------------------------------------'''
def classify0(inX,dataSet,labels,k):
#inX是未标识的输入向量,dataSet是已知数据集,labels是数据集对应的标识,k即是k-近邻算法中定义的k
dataSetSize = dataSet.shape[0] #shape[0]:读取矩阵第一维的长度,即训练实例的个数
diffMat = tile(inX,(dataSetSize,1)) - dataSet
#tile(A,reps):reps的数字从后往前分别对应A的第N个维度的重复次数
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1) #矩阵第一行元素值求和
distances = sqDistances**0.5
sortedDistIndices = distances.argsort() #返回数组元素值从小到大排序的索引值
classCount={} #数据字典
for i in range(k): #选择距离最小的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]
group,labels = createDataSet()
a = classify0([0,0.2],group,labels,3)
print a
仔细理解这个算法之后,k-近邻的核心思想就掌握了。
在测试算法时我们输入了一个坐标为(0,0.2)的未标识点,显然它应该属于B类点(肉眼目测)。
若执行后发现输出确实如此,则证明这个分类器算法在原理上没有差错。
三、应用:手写数字识别系统
我们先考虑一个问题:一张数字图像包含的信息是十分庞杂的,如何进行结构化?
首先将每个手写数字图像转化成一个32*32的图像(确保每个数字的大小近似以取得较好的效果),再将图像中笔画经过的像素点记作1,笔画未经过的像素点记作0,保存为一个32行、32列的文本文件,这便可以作为训练集合来输入了。
图书的作者已经在官网上提供了相关训练用例和源码(https://www.manning.com/books/machine-learning-in-action),这里为了方便我放置了训练集合和测试用例的文本文件的链接(链接: https://pan.baidu.com/s/1jIdVUlw 密码: 5erd)。
把解压得到的两个文件夹放在工程目录下。
在kNN.py的基础上,加入以下代码。(注意在文件头部额外加入from os import listdir)
关于代码里的listdir和split细节可以查看相关函数的用法。
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
'''测试转换效果,可手动打开文件观察是否一致
testVector = img2vector('testDigits/0_13.txt')
print testVector[0,0:32] #第一行1-32位
'''
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)
#将测试用矩阵、训练矩阵、标签矩阵和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 error is: %d" % errorCount
print "\nthe total error rate is: %f" %(errorCount/float(mTest))
handwritingClassTest()
这样,第一个小应用程序就设计好了,希望大家可以看到实现的效果~
测试中一些有趣的现象:
数字1容易被算法识别为7;
数字8被认错的概率最高,5其次;
数字0、4被识别的准确率极高。
另外很明显的一点:k-近邻算法不存在”训练算法”这一步骤,因此它的运行效率很低(每一次运行都需要把测试用例和所有的训练样本全部计算),用上文应用的例子来说:每个距离计算包括1024个维度的浮点计算,总共执行900次。还需要为所有的训练样本留下大约2.1MB的存储空间,导致k-近邻算法的时间和空间复杂度都很高。 希望在后面的学习中能够找到更优的算法来解决图像处理问题(肯定会有的)。
End.