【机器学习实战笔记】第一个算法:k-近邻算法

本文核心算法根据[美]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()

这样,第一个小应用程序就设计好了,希望大家可以看到实现的效果~

img

测试中一些有趣的现象:

数字1容易被算法识别为7;

数字8被认错的概率最高,5其次;

数字0、4被识别的准确率极高。

另外很明显的一点:k-近邻算法不存在”训练算法”这一步骤,因此它的运行效率很低(每一次运行都需要把测试用例和所有的训练样本全部计算),用上文应用的例子来说:每个距离计算包括1024个维度的浮点计算,总共执行900次。还需要为所有的训练样本留下大约2.1MB的存储空间,导致k-近邻算法的时间和空间复杂度都很高。 希望在后面的学习中能够找到更优的算法来解决图像处理问题(肯定会有的)。


End.