MLA Review之一： KNN算法

在看完Machine Learning in Action一书之后，觉得还是需要进行一些回顾，而且由于第一次看的时候Python基础并不牢固，所以这次也当做是Python一些知识回顾和运用的过程。

在回到主题之前插几句话，MLA 一书并不是一本理论著作，相反是使用了一些现成的机器学习方法使用了Python在具体的问题上进行了运用，整书没有使用繁琐的公式和证明过程，属于一本实战类的非学院派著作，因此在网上也有一些人对这本书多有微词，但是不管怎样，作为一个不想搞学术的渣硕，我对偏应用类的东西比较感兴趣，但是终究是要硕士搞搞学术的，所以这一专题也回加一些我所仅知的理论知识。

这是背景，OK，话不多说，回顾这本书的第一章，KNN算法。

 

KNN算法作为一种有监督的学习算法，以其简单易操作，但是时间复杂度和空间复杂度都比较高，其适用的范围为数值型和标称型

 

简单的描述下KNN算法：在给定的训练数据和训练标签情况下，对测试数据进行比较，为了描述简单，我们假设每一个测试数据都是一个向量，训练数据是一个向量组，而且训练数据带有标签。算法是：将测试向量与训练数据的每一个向量进行比较“距离”，选出训练数据中与测试数据向量“距离”最近的K个向量，然后在这K个向量中，统计标签出现的次数，选取次数最高的标签作为测试向量的返回结果。需要说明的是向量之间的距离有多种计算方式，常见的方法是“欧氏距离”，a=(1,2,3),b=(2,3,4)，其欧氏距离了就是sqrt((2-1)^2+(3-2)^2+(4-3)^2)，和向量空间的计算距离方法差不多。

 

具体问题描述：

手写问题识别：训练数据是多张32*32手写图像的二维矩阵，所谓二维矩阵就是整个图像空白的地方使用0描述，写字的地方使用1描述，现在有一些未经标注的测试图像，已经转换二维矩阵，现在需要识别出其结果。

 

上图就是为0的图像的二维矩阵描述

 

 

KNN代码如下：

 

# -*- coding: UTF8 -*-
"""
KNN算法
author:luchi
date:16/2/4
背景:识别手写数字
"""
from numpy import *
import operator
from os import listdir

#将图片转换成数组
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
#KNN算法
"""
inVec:输入的向量
dataSet:输入样本数据集
labels:输入样本标签
k:k个近邻
使用最简单的欧氏距离
"""
def KNN(inVec,dataSet,labels,k):
    datasetSize=dataSet.shape[0];
    diffMat=tile(inVec,(datasetSize,1))-dataSet
    sqDiffmat=diffMat**2
    sqDistance=sqDiffmat.sum(axis=1)
    distance=sqDistance**0.5
    sortDistance=distance.argsort()
    classCount={}  #定义一个元组
    for i in range(k):
        label=labels[sortDistance[i]]
        if not classCount.has_key(label):
            classCount[label]=1;
        else:
            classCount[label]=classCount[label]+1
    # print classCount

    sortedClassCount=sorted(classCount.iteritems(),key= operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]


# 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
#
# group,labels=createDataSet();
# result=KNN([0,0],group,labels,3)
# print result

#手写问题识别
def handwriting():
    hwLabels=[]
    trainingFileList=listdir('trainingDigits')
    m=len(trainingFileList)
    trainingMat=zeros((m-1,1024))
    for i in range(m):
        fileNameStr=trainingFileList[i]
        if(fileNameStr=='.DS_Store'):
            continue
        fileStr=fileNameStr.split('.')[0]
        classNumStr=int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)#获取标签
        trainingMat[i:]=img2vector('trainingDigits/%s' % fileNameStr)#获取训练向量
    testFileList=listdir('testDigits')#获取测试数据
    errorCount=0
    print (len(hwLabels))
    mTest=len(testFileList)
    for i in range(mTest):
        fileNameStr=testFileList[i]
        if(fileNameStr=='.DS_Store'):
            continue
        fileStr=fileNameStr.split('.')[0]
        classNumStr=int(fileStr.split('_')[0])
        vectorUnderTest=img2vector('testDigits/%s' % fileNameStr)
        classifierResult=KNN(vectorUnderTest,trainingMat,hwLabels,3)
        print('分类器返回值为:%d ,正确的结果应该是:%d' %(classifierResult,classNumStr))
        if(classifierResult!=classNumStr):
            errorCount+=1
    print('错误率是%f' % ((errorCount)/float(mTest)))

if __name__=='__main__':
    handwriting()

 测试结果如下：

 

 

可见其识别率也是相当之高。

 

需要说明的是：程序中的

 

 trainingMat=zeros((m-1,1024))
    for i in range(m):
        fileNameStr=trainingFileList[i]
        if(fileNameStr=='.DS_Store'):
            continue

 是因为程序跑在Mac操作系统中，使用listdir会带出.DS_Store这一个文件夹，因此程序中将其过滤掉了，如果是windows，应该改成

 

 trainingMat=zeros((m,1024))
    for i in range(m):
        fileNameStr=trainingFileList[i]

 当然其他的可以相应的做修改，并不影响程序功能。

 

其实可以比较一下神经网络的训练和KNN的训练，我们可以看出神经网络其复杂度比KNN要高出不少，乍看之下，KNN是比较好的方法，但是对于很对问题，KNN是没办法处理的，比如回归问题，所以KNN在数值类的分类问题上算是一种比较好得方法，但是其运用的范围远没有神经网络那么广，而且神经网络在近些年的发展中也渐渐形成了多个分支，包括深度学习。

 

最后说一说Python中得一些语法：

首先是需要说明的是，程序中计算欧氏距离使用的是numpy提供的array方法，而不是Python自带的list，array能够进行一些类似矩阵运算的方法，而list是不能的，因此需要将向量数据，转换成array，这就使用到了zeros方法