第六章-其他分类方法

模式识别第六章其他分类方法中国矿业大学信电学院蔡利梅第六章其他分类方法6.1近邻法6.2决策树与随机森林6.3罗杰斯特回归6.4Boosting方法6.1近邻法（1）昀近邻法„分段线性距离分类器分类效果与所选择的代表点有密切关系，找到的代表点不一定能很好的代表该类„对于分段线性距离分类器的弱点，采用一种极端的解法。„把每个样本点都作为代表点，计算各点与所求模式的距离，该模式归入距离昀近的点所在的类。这种方法称为昀近邻法。()()()。则决策规则：类的判别函数个，，每一类有样本个模式类：有jiijikikiiicxcixgxgNkxxxgωN，ω，，ωωcω∈===−=,,,2,1,min21min21，，，，：（2）k-近邻法„近邻法的推论„取未知样本x的k个近邻，看这k个近邻中大多数属于哪一类，则x归入该类。„例6.1：有两类样本，()()(){}()()()(){}TTTTTTT02,20,20,00:10,10,01:21−−−ωω1）采用样本均值作为两类的代表点，按昀小距离法分类，并画出决策面。2）模式x=(12)T，按昀近邻法分类，并画出决策面。3）模式x=(12)T，按3近邻法分类。)即为决策面的垂直平分线：12102103112121−=⎟⎠⎞⎜⎝⎛−=⎟⎠⎞⎜⎝⎛=xmmmmTT.2m.1m)(){}(){}()()()2212121113,17,1,5min210,2,2min2ω∈∴====Txgxgxgxg∵x实际上，也是分段线性函数)()()()()。类，三个近邻中有两个属于三个近邻分别为：：昀近的三个距离分别为与所有样本的距离为：样本110110202211317151022213ω∈∴xωTTTT；，，；，，；，，，，，，„近邻法的特点‡理论简单，易于决策‡分类结果较好，在训练样本趋于无穷时接近昀优‡计算量大，耗时大‡没有考虑到决策的风险‡错误率的分析建立在样本数趋于无穷大的假设上，样本数有限的情况，缺乏理论上的分析‡决策面：不同类各个样本点连线的垂直平分线构成大分段线性判别面。„近邻法的改进‡缩小计算范围‹对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目的与样本集中样本间的距离计算‡减少样本总数‹在训练样本集中挑选出对分类计算有效的样本，使样本总数合理减少（3）剪辑近邻法„近邻法的改进算法„基本思想‡去除两类数据重叠区域的样本，使近邻法的决策面更接近于昀优分类面第一类第二类重叠区域如图所示，重叠区域的样本将会误导决策，使分类错误；而且由于这个区域内两类已知样本都存在，使分类面的形状变得非常复杂。„算法实现‡识别出处于交界区的样本‹用部分训练样本进行预分类，检测出可能处在交界区的样本：将已知样本集划分为考试集ANT和训练集ANR，用训练集ANR中的样本对考试集ANT中的样本进行近邻法分类，从ANT中除去被错误分类的样本，剩余样本构成剪辑样本集ANTE，用ANTE对未来样本进行近邻法分类。‡再用近邻法分类„多重剪辑方法MULTIEDIT‡划分把样本集随机划分为s个子集‡分类用A(i+1)mod(s)对Ai中的样本分类‡剪辑从各个子集中去掉在上一步被分错的样本‡混合把剩下的样本合在一起，形成新的样本集ANE‡迭代用新的样本集ANE替代原样本集，转第一步。如果在昀近的m次迭代中都没有样本被剪掉，则终止迭代，用昀后的ANE作为剪辑后的样本集。3,,,1≥sAAssi,,1=„例6.2：有两类样本，()()(){}()()()(){}TTTTTTT02,20,20,00:10,10,01:21−−−ωω用MULTIEDIT方法分类。‡划分()(){}()(){}()()(){}TTTTTTTAAA02,20:,10:20:,10:00:,01:213212211−−−===ωωωωωω‡分类‡用A2对A1分类，A1中的(00)T分类错误‡用A3对A2分类，无错误‡用A1对A3分类，A3中的(0-1)T分类错误‡剪辑混合：去掉分类错误样本，形成新样本集()(){}()()(){}⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧−−=TTTTTNEA02,20,20:10,01:211ωω‡划分()(){}()(){}()(){}TTTTTTAAA02:,10:20:,10:20:,01:213212211−=−==ωωωωωω‡分类‡用A2对A1分类，A1中的(02)T分类错误‡用A3对A2分类，无错误‡用A1对A3分类，A3中的(01)T分类错误‡剪辑混合：去掉分类错误样本，形成新样本集()(){}()(){}⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧−−=TTTTNEA02,20:10,01:211ωω‡划分()(){}()(){}()(){}TTTTTTAAA02:,01:02:,10:20:,01:213212211−=−=−=ωωωωωω‡分类‡用A2对A1分类，无错误‡用A3对A2分类，无错误‡用A1对A3分类，无错误‡剪辑混合：无样本被剪掉，迭代终止，昀后的样本集为()(){}()(){}⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧−−=TTTTNEA02,20:10,01:21ωω两类混杂样本完全被消除，两类之间分界变得十分清楚。（4）压缩近邻法„近邻法的改进算法„基本思想‡远离分类边界的样本对昀后的分类决策没有贡献，设法找出各类样本中昀有利于用来与其他类区分的代表性样本，可去掉很多训练样本，简化计算。„算法实现‡将已知样本集划分为储存集AS和备选集AG，算法开始时，AS中只有一个样本，其余在AG中，考查AG中的每一个样本，若AS中的样本能够对它正确分类，则该样本保留在AG中，否则移到AS中，直到没有样本再需要被搬移为止。昀后用AS中的样本作为代表样本，对未来样本进行近邻法分类„例6.3：有两类样本，()()(){}()()()(){}TTTTTTT02,20,20,00:10,10,01:21−−−ωω对模式x=(12)T，按压缩近邻法分类。‡划分()(){}()()()()(){}TTTTTGTTSAA02,20,20:,10,10:00:,01:2121−−−==ωωωω‡考查‹(01)T,(0-1)T被错误分类，移到AS中()()()(){}TTTTSA00:,10,10,01:21ωω−=‡分类‹(12)T距离ω1中的(10)T昀近，归为ω1类„算法分析‡在不牺牲分类准确度的前提下大大压缩近邻法决策时的训练样本，如果与剪辑近邻法配合使用可以得到非常好的效果‡2005年有学者把剪辑和压缩近邻法中的思想运用到改进支持向量机的复杂性上，取得了很好的结果6.2决策树与随机森林（1）非数值特征„Nonmetricfeatures‡名义特征(nominalfeatures)：如物体的颜色、形状，人的性别、民族，字符串中的字符等，只能比较相同或不同，无法比较相似性、大小‡序数特征(ordinalfeatures)：如序号、分级等，本身是一种数值，可能有顺序，却不能看作欧氏空间的数值‡区间数据：如年龄、考试成绩、温度等，本身是数值特征，但在某些问题中，与研究目标之间的关系呈现出明显的非线性，需分区段处理„利用前面的方法对这样的样本进行模式分类，首先要对这些特征进行编码，把非数值的特征转换成数值特征„转换方法有多种，但可能会损失数据中的信息，也可能引入人为的信息„寻求直接利用非数值特征分类的方法。（2）决策树„面对非数值特征，人们的很多决策过程都是按照一定的树状结构进行。„决策树(decisiontree)方法是利用一定的训练样本，从数据中“学习”出决策规则，自动构造出决策树。„决策树结构‡根节点：所要进行分类的样本集‡子节点：按照某一个规则把原始样本集分成几个区域，对应几个子节点‡叶节点：对每一个子节点再分，找到满足要求，昀末端的样本集称为叶节点„设计决策树应解决的问题‡选择合适的树结构‡确定在每个节点上要使用的特征‡在每个节点(叶节点除外)上选择合适的决策规则决策树构建过程就是选取特征和确定决策规则的过程（3）决策树的构造„ID3，交互式二分法：InteractiveDichotomizer-3‡熵：如果一个事件有k中可能的结果，每种结果对应的概率为Pi，i=1,…,k，则对此事件的结果进行观察后得到的信息量可以用熵来度量：()∑=−=+++−=kiiikkPPPPPPPPI122222121loglogloglog‡构造决策树时，对于某个节点上的样本，上式称为熵不纯度，反映了该节点上的特征对样本分类的不纯度。实际问题中，可以用样本出现的比例作为对概率的估计。‡信息增益：也称不纯度减少量，如果特征把N个样本划分成m组，每组Nm个样本，则不纯度减少量为：()()()()()[]NNPNIPNIPNIPNINImmmm=+++−=Δ2211‡ID3算法步骤‹计算当前节点包含的所有样本的熵不纯度‹比较采用不同特征进行分枝将会得到的信息增益，选取具有昀大信息增益的特征赋予当前节点，该特征的取值个数决定了该节点下的分枝数目‹如果后继节点只包含一类样本，则停止该枝的生长，该节点成为叶节点‹如果后继节点仍包含不同类样本，则再次进行以上步骤，直到每一枝都到达叶节点„例6.4：有顾客数据，根据这些数据建立能够估计客户是否会购买汽车的决策树编号年龄性别月收入是否购买121男4000否233女5000否330女3800否438女2000否525男7000否632女2500否720女2000否826女9000是932男5000是1024男7000否1140女4800否1228男2800否1335女4500否1433男2800是1537男4000是1631女2500否编号年龄性别月收入是否购买130男中否2≥30女中否3≥30女中否4≥30女低否530男高否6≥30女低否730女低否830女高是9≥30男中是1030男高否11≥30女中否1230男低否13≥30女中否14≥30男低是15≥30男中是16≥30女低否‡计算不考虑任何特征时熵不纯度‹16人中有4人买车，12人不买()8113.01612log1612164log1644,1622=⎥⎦⎤⎢⎣⎡⎟⎠⎞⎜⎝⎛+⎟⎠⎞⎜⎝⎛−=I‡考查采用不同特征划分样本后的信息增益‹采用年龄划分样本，30岁以下组6人，1人购车；30岁以上组10人，3人购车()()7946.03,1016101,6166=+=IIIage()()0167.04,1616=−=ΔageageIII‹采用性别划分样本，男性组7人，3人购车；女性组9人，1人购车()()7142.01,91693,7167=+=IIIgender()()0972.04,1616=−=ΔgendergenderIII‹采用月收入划分样本，高收入组3人，1人购车；中收入组7人，2人购车；低收入组6人，1人购车()()()7936.01,61662,71671,3163=++=IIIIincome()()0177.04,1616=−=ΔincomeincomeIII采用性别特征划分样本带来的信息增益昀大，用性别特征作为根节点性别‡构建决策树的下一层节点‹对于女性组和男性组，分别考查年龄和月收入作为特征所得到的信息增益。计算结果表明：男性组采用年龄特征，女性组采用月收入特征划分信息增益昀大，分别用这两个特征构建下一级的决策树节点‡新一级节点都是同一类样本，即叶节点，决策树构建完成月收入年龄女男低否中否高是30否≥30是左下角两个叶节点可以合并从决策树得到的分类规则为：‹若(性别==女)且(月收入6000)，则(买车=否)‹若(性别==女)且(月收入6000)，则(买车=是)‹若(性别==男)且(年龄30)，则(买车=否)‹若(性别==男)且(年龄≥30)，则(买车=是)性别月收入年龄女男中低否高是30否≥30是实际上是从根节点到叶节点的四条通路„其他不纯度度量方法‡Gini不纯度度量（方差不纯度）()()()()∑∑=≠−==kjjnmnmPPPNI121ωωω‡误差不纯度()()jjPNIωmax1−=多数情况下，采用