模式识别-决策树-人脸识别

百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第1页数学与计算机学院课程名称:模式识别题目:决策树算法-基于人脸数据实现任课老师:王晓明年级专业:2011级计算科学与技术姓名:张x学号:312011080605xxx时间:2013年11月10日百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第1页目录一决策树算法介绍..........................................................................................................1二决策树算法描述..........................................................................................................1三决策树算法Matlab实现-基于人脸数据实现.................................................................71数据读入...............................................................................................................72算法运行结果......................................................................................................10四总结和心得...............................................................................................................12五附录——核心算法的主要源代码...............................................................................13六参考文献..................................................................................................................21百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第2页百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第1页决策树算法一决策树算法介绍决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方法最早产生于上世纪60年代，到70年代末。由JRossQuinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。决策树算法构造决策树来发现数据中蕴涵的分类规则。如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数扼集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。最早比较著名的决策树构建方法就是ID3（交互式二分法InteractiveDichotomizer-3），其名字虽然是二分法，但方法也适用于每个节点下划分多个子节点的情况。方法的原型是Hunt等人提出的概念学习系统（conceptlearningsystem），通过选择有辨别力的特征对数据进行划分，知道每个节点上只包含单一类型的数据为止。二决策树算法描述ID3算法的基础是香农（Shannon）信息论中定义的熵（entropy）。信息论告诉我们，如果一个事件有k种可能的结果，每种结果对应的概率为Pi,i=1，···，k，则我们对此事件的结果进行观察后得到的信息量可以用如下定义的熵来度量百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第2页I=−P1log2P1+P2log2P2+···+Pklog2Pk=−Pklog2Pkki=1对某个节点上的样本，我们把这个度量成为熵不纯度，它反映了该节点上的特征对样本分类的不纯度（impurity）。在应用得到实际问题时，可以用各类样本出现的比例来作为概率的估计。比如，如果k=4，在当前节点上包含的样本属于四类的概率都是0.25，则I=−4×0.25×log20.25=2样本最不纯，即不确定性最大；如果当前节点只包含两类样本且数量相同，不包含另外两类样本，则I=−2×0.5×log20.5=1样本的不确定性减少；而如果当前节点的样本全部属于某一类别，其余三类概率都是0，则I=−1×log21=0样本最纯，没有不确定性。决策树算法ID3方法的伪代码：训练样本集为S；while(没有找出全部叶结点)if(S全为一个类别A)设置叶结点为类别A；contine；end根据S求出总体熵的不纯度I；fori=1:k求出各特征总的熵的不纯度Ii；求出个特征总的熵的不纯度相对样本集总体熵的信息增益di；endfori=1:kif(di=max(d))百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第3页设置特征i为根节点；endend根据特征i的n个取值将S分为n个数据集S1，···,Sn；分别将S1，···,Sn设置为S重复以上步骤；end下面举一个简单的例子对决策树算法的ID3方法进行演示。表1是一个顾客购买汽车的统计表格，根据表格信息构造出决策树，利用决策树进行判别。顾客购买汽车统计表顾客编号性别工资是否教师是否买车1男高否是2男高是是3女高否是4男低是是5女低否否6女低是否7男低否否表11.确定根节点：由表1可知，在不考虑任何特征时，7人中有4人买车，3人不买车，于是可以计算出熵的不纯度为：I(7,4)=−47log247+37log237=0.9852如果采用性别做根节点，则把样本集按性别分为两组，性别为男一组，性别为女一组，见表2和表3。百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第4页男性购买汽车统计表顾客编号性别工资是否教师是否买车1男高否是2男高是是4男低是是7男低否否表2女性购买汽车统计表顾客编号性别工资是否教师是否买车3女高否是5女低否否6女低是否表3由表知，男性组中有4人，其中买车的有3人；女性组有3人，其中买车的有1人。总的熵不纯度是这两组样本上计算的不纯度按照样本比例的加权求和，即Igender=47I4,3+37I3,1=0.8571这样，采用性别作为根节点后，在下一级的熵不纯度比上一级减少的量是∆Igender7=I7,4−Igender=0.1281称作不纯度减少量，或信息增益。同样的方法分别计算出了如果采用工资、是否教师特征作为根节点所能够带来的信息增益∆Isalary7=I7,4−Isalary=0.5216∆Iteacher7=I7,4−Iteacher=0.0202通过计算不难看出，用工资作为第一个特征能够带来不纯度最大的减小，于是决定用工资特征作为决策树的根节点，如图1所示：所有7个样本被按照工资特征分成了两组，高工资组有3人，全部购买了车；低工资组有4人，其中1人购车。百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第5页工资1是3否3是低高34图12.确定根节点的左子节点：由于工资已经作为根节点，所以得到一下的表4。低工资顾客购车统计顾客编号性别是否教师是否买车4男是是5女否否6女是否7男否否表4由表4可知，在不考虑任何特征时，总共有4人，其中1人买车，3人不买。于是可以计算出熵的不纯度为：I(4,1)=−14log214+34log234=0.8113如果采用性别做根节点，则把样本集按性别分为两组，性别为男一组，性别为女一组，见表5和表6。低工资男性顾客购车统计顾客编号性别是否教师是否买车4男是是7男否否表5百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第6页低工资女性顾客购车统计顾客编号性别是否教师是否买车5女否否6女是否表6于是可以算出以性别特征作为根节点的左子节点时，总的熵不纯度为：Igender=12I2,1+12I2,0=0.5信息增益为：∆Igender4=I4,1−Igender=0.3113同理可以计算出以是否教师作特征为根节点的信息增益为：∆Iteacher4=I4,1−Iteacher=0.3113所以此时，任取性别或者是否教师特征作为根节点的左子节点都可以，我们就选取性别特征，此时的到图2所示结果。工资3是低高34性别2否1是1否女男22图23.确定性别特征节点的右子节点：根据以上计算的到的结果，我们可以得到以下表7。低工资男性顾客购车统计顾客编号是否教师是否买车4是是7否否表7由表格可知，如果顾客是教师，则会购买汽车；否则不会购买。至此，决策树构建完毕百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第7页得到如图3所示的决策树。工资低性别男是否教师是否否是高女否是图34.决策树验证：现有一个顾客信息如下表（表8）所示，根据决策树来辅助判别该顾客是否会购买汽车。过程如下：首先查看顾客是否高收入，查看得该顾客是低收入；根据决策树，接下来查看顾客性别信息，查看得知顾客为男；根据决策树走向，继续查看该顾客是否为教师，查表的该顾客是教师，所以可以判定该顾客会购车。顾客信息性别工资是否教师男低是图8三决策树算法Matlab实现-基于人脸数据实现1数据读入程序所使用的人脸数据为22张100*100的灰度图（其中11张为人物甲如图4所示，11张为人物乙如图5所示），如图6所示，在Matlab中使用imread()函数将各个图片读入并存储在22个二维矩阵中。图4百度账号：小样整哪样。模式识别——决策树算法基于人脸数据实现第8页图511001100图6将数据读入到相应的矩阵中后，并不能直接利用算法处理数据，因为对于此时的二维矩阵来说，特征并不明显。一下以一个存储了图片信息的矩阵face为例子讲解处理过程。首先将100*100的face矩阵降维为一个1*10000的行矩阵；然后将每2000个数据为一组求取一个平均数，即得到一个1*5的feature矩阵，此时feature矩阵中存储的是处理后的0~255之间的数，即为特征1、特征2、特征3、特征4、特征5的值，得到一个如表9所示的矩阵。降维后的数据集图片号特征1特征2特征3特征4特征5人物代号人物1227.764265.008291.269248.749229.5943甲2201.95171.624194.945137.234156.8793甲3224.934181.419220.641165.644172.0873甲4299.497283.707205.97193.66361.573甲5206.334175.668186.104136.885134.883甲6206.334175.668186.104136.885134.883甲7208.128166.037255.486287.431332.3593甲8238.901168.59194.15165.441161.1323甲9209.31168.449195.075160.642160.0353甲10177.1153.796166.812146.193157.9233甲11220.237167.35519