机器学习_Python

机器学习_1:K-近领算法

文章目录

实验背景
1.k-近邻算法
- 1.1算法原理
- 1.2算法解析
- 1.3算法实验
2.基于k-近邻算法的手写体识别
- 2.1代码解析
- 2.2代码实现
3.实验总结

实验背景

本次实验基于机器学习经典的k-近邻算法，我会先介绍k-近邻算法的原理和基础的分类实验，然后介绍如何使用k-近邻算法进行手写体识别。

1.k-近邻算法 1.1算法原理

什么是k-近邻算法，就是根据给定的要判断的点，找出k个与它距离最近的点，而这k个点中，哪种标签出现次数最多，这个要判断的点就属于那个标签。如图所示，这里的k取值为5，而这5个点中，有四个w1，所以这个判断点属于w1，这就是k-近邻算法。
伪代码：
对测试数据集中的每个点依次执行以下操作：
(1)计算训练数据集中的点与当前点之间的距离;
(2)按照距离从小到大递增排序;
(3)选取与当前点距离最小的k个点;
(4)确定这k个点所在类别的出现频率(即统计k个点中每个种类的数量)
(5)返回这k个点中出现频率最高的类别作为当前点的预测分类

1.2算法解析

以下代码为k-近邻算法的原理代码，我会尽量解析大部分代码，争取让阅读本文章的所有人都能看懂

#科学计算包numpy
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

#四个参数，输入向量inx（输入的测试坐标点），训练样本集dataSet（上面的那个数组group）,标签向量labels（上面那个labels），k为最近邻居的数目（kNN算法中的k）
def classify0(inx,dataSet,labels,k):
    #读取矩阵第一维的长度
    dataSetSize=dataSet.shape[0]
    #diffMat存储通过tile计算输入向量inx与样本集dataSet的差值
    diffMat=tile(inx,(dataSetSize,1))-dataSet
    #将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
    #再次排序，根据第二个元素次序，降序排序
    sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    #返回频率最高的标签
    return sortedClassCount[0][0]

距离的计算公式采取欧式距离公式，公式如下：

可以简单理解为对应坐标之差的平方和再开根号

1.3算法实验

如图点击上方路径，输入cmd打开命令提示符，按顺序依次输入
python
import KNN（你命名的保存k-近邻算法的文件）
group,labels=KNN.createDataSet()（创建group和labels）
KNN.classify0([0,0],group,labels,3)
这里可能会出现报错

原因是新版的python不再支持iteritems，将其改成items即可
测试结果如图，结果为B（不是B的注意下代码是否有出入）

2.基于k-近邻算法的手写体识别 2.1代码解析

#将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

#手写体识别测试集代码
def handwritingClassTest():
    #创建空的标签数组
    hwLabels=[]
    #获取目录内容
    trainingFileList=listdir('trainingDigits')
    #得到训练集数量
    m=len(trainingFileList)
    #初始化
    trainingMat=zeros((m,1024))
    #循环m次
    for i in range(m):
        #获取文件名
        fileNameStr=trainingFileList[i]
        #去除文件后缀
        fileStr=fileNameStr.split('.')[0]
        #文件命名格式为k_x，比如9_45（表示这个图片是数字9，在这类图像中排第45个），获取类别
        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])
        #转换成1*1024向量
        vectorUnderTest=img2vector('testDigits/%s'%fileNameStr)
        #用classify0进行判断
        classifierResult=classify0(vectorUnderTest,trainingMat,hwLabels,3)
        #显示判断结果和真实结果
        print ("the classifier came back with:%d,the real answer is :%d"%(classifierResult,classNumStr))
        #判断是否一致，不一致错误数+1
        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)))

2.2代码实现

跟之前的实验一样，在代码目录输入cmd打开命令提示符后
依次输入：
python
import KNN
KNN.handwritingClassTest()

如图所示，测试结果一般在1%左右波动。

3.实验总结

本次实验可以很明显的看出k近邻算法的优缺点
优点：
1.简单有效
2.便于理解
缺点：
1.必须保存全部数据集，如果训练数据集很大，会耗费大量存储空间
2.相比其他算法，因为需要计算每个数据的距离，会非常耗时
3.无法给出任何数据的基础结构信息，因此无法知晓平均实例样本和典型样本具有什么特征
通过优缺点我们可以发现，k近邻算法很明显是适合初学者进行机器学习的基础算法，也许可以对其进一步优化，但它的设计思路决定了它的上限，很难有巨大的突破。

机器学习

Python相关栏目本月热门文章