分数: ___________
任课教师签字:___________
课程作业
学年学期:2017——2018学年第二学期
课程名称:模式识别
作业名称:作业七
学生姓名:
学号:
提交时间:
一、问题重述
编写手写体识别大作业程序,要求做到以下几点内容:
(1)针对“002手写数字数据集(1934+946)”数据包,进行手写体辨识。要求使用之前作业中用到的各类平均值为类中心的最小距离法、KNN近邻法(K取1,3,5)等等。
(2)尝试使用神经网络方法进行辨识过程。
(3)尝试70000个样本的数据集进行辨识,其中60000个用于训练,10000个用于测试。
二、方法原理
1、特征选择准则——类别可分性准则
类别可分性准则值可以衡量样本的可分程度,取值越大表明样本可分程度越小,可以在一定程度上减小最终的分类错误率。
类别可分性准则函数值J的计算公式如下所示
其中C为类别数,m为总样本均值,mi为某一类均值,X表示样本数据。
值得注意的是,并非J取值越大,最终的分类错误率就一定越小。最终的分类结果还与数据的分布特性以及分类器的选择有关。因此在J值取值只需满足条件即可,并非一定要取到最大值。
2、特征提取方法——PCA降维
当样本数据维数较高时,程序当中涉及到矩阵的运算会有很大负荷,算法的执行效率会大幅降低。因此在训练之前,需要将样本数据进行降维处理。
主成分分析法(简称PCA)可以减少样本数据的相关性,突出差异性,是分类、辨识当中常用的降维方法。
PCA可以将高维的数据降到任意低的维度上。但是为了保证样本数据不失真,一般要求PCA算法降维中,特征值占比不小于所有特征值之和75%。
PCA算法的流程如下图所示。
图1 PCA降维算法流程图
3、分类器
分类器是整个分类环节当中的最后一项,也是分类过程的关键所在。分类器分为训练和测试两个环节,相应的算法有很多。常用的有基于类均值的最小距离法、KNN近邻法等基本线性分类算法,以及向量机、神经网络等更为复杂的算法。
分类结束之后,计算训练错误率和测试错误率,以此为
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
检验分类器算法的优劣以及整个分类过程的好坏。
(1)基于类均值的最小距离法
基于类均值的最小距离法首先计算每类训练样本的均值点,再分别计算每个均值点到测试样本的距离,测试样本归属于距其最近的均值点所在的数据类型。
基于类均值的最小距离法算法流程如下:
图2基于类均值的最小距离法流程图
(2)KNN近邻法
KNN近邻法源自近邻法。KNN近邻法不再单单寻找距测试样本最近的一个点,而是寻找距其最近的K个点,然后按这K个点类型确定测试样本的类型。判断原则往往是少数服从多数。
K的取值一般取技术。特别的当K取1,这种方法就是常见的最近邻法。
KNN近邻法算法流程如下:
图3KNN近邻法流程图
(3)BP神经网络
BP网络是一类多层的前馈神经网络。它的名字源于网络训练的过程中,调整网络的权值的算法是误差的反向传播的学习算法,即为BP学习算法。BP算法的结构简单,可调的参数多,训练的算法也多,而且操作性好。BP网是前向网络的核心部分算法,是神经网络中最精华、最完美的部分。
本次作业利用BP神经网络算法对样本进行训练测试,并将结果与其他方法进行对比。
三、处理流程
本次数据处理的数据集为32*32的二值图,保存格式为文本格式。训练样本数为1934,每个数字大约有200个;测试样本数为926个,每个数字个数从80到120不等。
整个手写体辨识过程可以分为以下四个阶段:
图4 手写体辨识过程
1、数据采集
本次作业所用到的数据为二值化后的文本文档,所以数据采集过程只需要将文档中的数据读取到工作空间即可。
本阶段将训练样本和测试样本分别存到两个元胞数组的变量当中,每个元胞含有10个元胞元素,依次对应0~9;每个元胞元素中存放n*1024的矩阵,其中n代表该类数据的样本数,1024代表二值化后的点阵数。
2、特征生成
本阶段将原始数据进行处理,提取出16个特征元素。特征生成过程如下。
将32*32的二值化矩阵平均分成16块,求出每块矩阵当中非零元素的个数,作为相应的特征元素。如,将下图所示的一组数据(类型为0)提取特征值后为[3 43 25 0 14 30 19 6 5 30 8 22 0 37 40 11]。
图5 一组类型为0的原始数据
图6 将二值均值分块过程
3、特征选择与提取
为了减小计算量需要对样本进行降维处理。降维方式选择PCA算法,在保证类别可分性准则值满足要求的条件下,特征值占比不小于75%即可。设n表示PCA处理后的维度。
表1 1934与70000两个数据集PCA降维后不同维度下特征值占比和可分性准则
PCA处理后的维度
1934个样本的数据集
70000个样本的数据集
特征值占比(%)
可分性准则值
特征值占比(%)
可分性准则值
1
23.93
2.1504
24.57
0.9538
2
43.93
2.1665
44.99
1.0704
3
59.91
1.8514
60.02
0.7927
4
68.87
1.6222
69.66
0.7709
5
76.87
1.4695
77.50
0.7644
6
82.67
1.3072
83.80
0.6956
7
88.09
1.2197
88.93
0.6667
8
90.79
1.1991
92.74
0.6298
9
93.15
1.1681
95.46
0.6068
10
95.32
1.1245
97.01
0.5941
11
96.79
1.0915
97.94
0.5872
12
97.92
1.0703
98.77
0.5798
13
98.80
1.0539
99.31
0.5757
14
99.42
1.0416
99.65
0.5728
15
99.82
1.0353
99.93
0.5707
16
100
1.0316
100
0.5700
图71934样本集PCA降维后的特征值占比和可分性函数值
图870000样本集PCA降维后的特征值占比和可分性函数值
为了减少计算量,选择特征值占比大于75%维度最小的情况。因此针对1934数据集,利用PCA将其降成5维;针对70000数据集,也利用PCA降成5维。
4、分类器
将PCA降维后的数据(5维)和不进行PCA降维的数据(16维),分别利用基于类均值的最小距离法训练、KNN近邻法(K取1、3、5)、BP神经网络算法,对样本进行训练、测试,得到的错误率如下:
表2 分类错误率
分类器
1934样本集
70000样本集
PCA降维后
原始数据
PCA降维后
原始数据
训练
测试
训练
测试
训练
测试
训练
测试
最小距离
0.2291
0.1681
0.1680
0.0655
0.3903
0.3228
0.3295
0.1739
最近邻
0.2718
0.1189
0.1586
0.0362
0.3832
0.2526
0.3219
0.1254
3NN
0
0.1755
0
0.0708
0
0.3169
0
0.1731
5NN
0.167
0.1070
0.0655
0.0103
0.3441
0.3420
0.1867
0.2738
BP网络
0.1034
0.1543
0.0290
0.0507
0.2127
0.2803
0.1001
0.1690
对分类结果以及之前的
工作总结
关于社区教育工作总结关于年中工作总结关于校园安全工作总结关于校园安全工作总结关于意识形态工作总结
,如下:
(1) 当数据集规模变大时,各种算法的错误率会增加;
(2) PCA降维后虽然会减小运算量,但是会增大分类错误率;
(3) 几种方法中,基于类均值的最小距离分类算法的效果相对最差,BP神经网络的分类效果相对最好。
(4) 对于基于类均值的最小距离法、KNN近邻法来说,训练错误率一般是略高于测试错误率的。
(5) 本作业次设计的分类器对于1934样本集分类效果比较令人满意,但是对于70000样本集分类效果很差,针对大样本数据,算法需要改进
四、代码附录:
1、 数据采集程序:
%手写体识别:1934训练样本+946个测试样本
%每个txt文件对应32*32的矩阵,转换为一条行向量。
clear all
close all;
clc;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%保存训练数据
PathTrain=[cd,'\trainingDigits\'];
TrainList=dir([PathTrain,'*.txt']);
TrainData_Original=cell(10,1);%保存原始训练数据
for i=1:length(TrainList)
fid=fopen([PathTrain,TrainList(i).name],'r');
temp_1=textscan(fid,'%s');
fclose(fid);
temp_2=cell2mat(temp_1{1});
temp_3=str2num(reshape(temp_2,[],1))';%存成行向量
label=str2num(TrainList(i).name(1));%该行数据的数据类型
TrainData_Original{label+1}=[TrainData_Original{label+1};temp_3];
end
save('TrainData','TrainData_Original');
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%保存测试数据
PathTest=[cd,'\testDigits\'];
TestList=dir([PathTest,'*.txt']);
TestData_Original=cell(10,1);%保存原始测试数据
for i=1:length(TestList)
fid=fopen([PathTest,TestList(i).name],'r');
temp_1=textscan(fid,'%s');
fclose(fid);
temp_2=cell2mat(temp_1{1});
temp_3=str2num(reshape(temp_2,[],1))';%存成行向量
label=str2num(TestList(i).name(1));%该行数据的数据类型
TestData_Original{label+1}=[TestData_Original{label+1};temp_3];
end
save('TestData','TestData_Original');