第5章 CHAPTER 5 非线性判别分析 在很多情况下，数据分布情况复杂，样本集非线性可分，进行线性判别分析会有较高的错误率，可以利用非线性判别实现分类。非线性判别分析并没有特定函数形式，因此不适合采用类似于线性判别函数设计的参数估计方法。不同的设计思路产生不同的方法，本章主要学习常见的几种非线性判别分析方法，包括近邻法、二次判别函数设计、决策树方法、Logistic回归。 5.1近邻法 近邻法是一种经典的非线性判别分析方法，采用距离度量作为判别函数，直接根据训练样本对未知类别样本进行分类决策。首先了解利用距离度量进行判别的含义，再介绍近邻法决策规则。 5.1.1最小距离分类器 距离度量是模式识别中常用的方法，如果类别可分，则同一类样本差别相对较小，不同类的样本差别相对较大，差别可以采用数据间的距离来衡量，因此，可以设计基于距离的分类器。 对于两类情况，设两类ω1、ω2各自的均值向量为μ1、μ2，待分类样本为x，计算x到两类均值的距离，将x归为距离小的那一类，即 图51两类的最小距离分类器 若g(x)=‖x-μ1‖2-‖x-μ2‖20，x∈ω1 ω2(51) 则分类决策面为μ1、μ2连线的垂直平分面，如图51所示。 对于正态分布模式的贝叶斯决策，在样本集分布呈现特殊情况(P(ωi)=P(ωj)，Σj=σ2I，i,j=1,2,…,c)时，设计的判别函数为最小距离分类器(见2.7节)。 如果是多类情况，则定义各类的判别函数为 gj(x)=‖x-μj‖2，j=1,2,…,c(52) 决策时，哪一类的判别函数(距离)最小，则决策为哪一类，即决策规则为 若gi(x)＜gj(x)，i≠j，i,j=1,2,…,c，则x∈ωi(53) 很明显，最小距离分类器仅适用于类别线性可分且类间有明显距离的特殊情况，但用均值点作为类的代表点，用距离作为判别函数的思路很有启发性。 5.1.2分段线性距离分类器 图52所示为正常血压和高血压数据，采用最小距离分类器，设计的分界面导致很多数据被错分类，如图52(a)所示。将高血压数据分为3个子类，各子类均值点作为该子类的代表点，距离作为判别函数，设计多类情况下的最小距离分类器，得到的分界面由多段线性分界面组成，如图52(b)所示。 图52非线性可分情况下距离分类器示例 对于类别数据呈现多峰分布的情况，将每类划分为若干子类，验证待分类样本x到ωj类各子类均值的距离，最小的距离作为该类的判别函数值，将样本归入最近的子类所属的类别，这种分类器称为分段线性距离分类器。 分段线性距离分类器的判别函数表示为 gj(x)=minl=1,2,…,cj‖x－μlj‖，j=1,2,…,c(54) cj为ωj类的子类数目。 分段线性距离分类器的决策规则为 若gi(x)=minj=1,2,…,cgj(x)，则x∈ωi(55) 分段线性距离分类器分类效果与子类的划分有密切关系，如果对样本没有充足的先验知识，子类划分不一定合理，则会影响分类的效果。 5.1.3近邻法及仿真实现 1. 最近邻法 将分段线性距离分类器的设计思路发展到极端，把每个样本点都作为一个子类，计算各点与待测样本x的距离，将x归入距离最近的点所在的类，这种方法称为最近邻法(Nearest Neighbor，NN)。 最近邻法的判别函数如式(54)所示，仅将变量cj修改为ωj类的样本数目Nj； 决策规则如式(55)所示，不再赘述。 式(54)计算的是欧氏距离，也可以采用不同的距离度量，或者采用相似性度量(见7.2节)，把最小距离变更为最大相似度量，确定最近邻，实现分类。 由于把每个样本点都作为一个子类，因此最近邻法的决策面由不同类样本点间连线的垂直平分面构成，判别函数是分段线性判别函数(Piecewise Linear Discriminant Function)。 2. k近邻法 最近邻法根据距离待测样本最近的一个样本的类别进行归类，容易受到样本分布以及噪声的影响，导致决策错误，因此，引入投票机制，选择距离待测样本最近的k个样本，将待测样本归入多数近邻所在的类别，称为k近邻法(kNN)，最近邻法实际是k=1的特例。 k值需要根据样本情况进行选择，通常选择样本总数的一个很小的比例即可。两类情况下，一般选择k为奇数，避免两类得票相等。 k近邻法(含最近邻法)简单易于决策，根据已知类别的样本直接对待测样本进行决策，不需要事先训练出一个判别函数，在训练样本趋于无穷时接近最优，但计算量大，耗时大，没有考虑决策的风险。 【例51】对样本集ω1： 1 0,0 1,0 -1，ω2： 0 0,0 2,0 -2,-2 0进行下列处理。 (1) 采用样本均值作为两类的代表点，按最小距离法分类； (2) 对样本x=［12］T，按最近邻法分类； (3) 对x=［12］T按3近邻法分类。 解： (1) μ1=［1/30］T、μ2=［-1/20］T，μ1和μ2连线的垂直平分线为x1=-1/12。 (2) g1(x)=min{2,2,10}=2，g2(x)=min{5,1,17,13}=1。 因为 g1(x)＞g2(x) 所以 x∈ω2 (3) 最近的三个距离为1、2、2，对应的3个近邻为［02］T、［01］T、［10］T，3个近邻中有2个属于ω1类，所以x∈ω1。 【例52】导入fisheriris数据集，根据原理设计程序对样本［5.52.341.3］T进行最近邻以及5近邻判别。 设计思路： 计算待测样本与所有样本之间的距离，将距离排序，找最小距离和前5个最小距离，对应的样本类别即为分类类别。 程序如下： clc,clear,close all; load fisheriris; X=［5.5,2.3,4,1.3］;k=5; N=length(meas); distance=pdist2(X,meas); %计算待测样本和各样本之间的欧氏距离 ［D,index］=sort(distance); %距离升序排序 disp('最近邻归类：');celldisp(species(index(1))); %输出最近邻所在的类 n1=sum(count(species(index(1:k)),'setosa')); n2=sum(count(species(index(1:k)),'versicolor')); n3=sum(count(species(index(1:k)),'virginica')); %计算前k个近邻中各类的个数 if n1>n2 && n1>n3 disp('k近邻归类：setosa'); elseif n2>n1 && n2>n3 disp('k近邻归类：versicolor'); else disp('k近邻归类：virginica'); end 运行程序，在命令窗口输出对待测样本归类的结果： 最近邻归类： ans{1} = versicolor k近邻归类： versicolor 3. 近邻法的快速算法 近邻法在样本数目较多时取得好的性能，但计算待测样本与大量训练样本之间的距离，计算量大，导致算法效率降低，因此需要快速算法。Kd树本书统一用n表示样本维数，而Kd树的K表示维数，此处与资料上的名称保持一致，注意与kNN中k的区别。(K Dimensional Tree)是一种对K维空间中的点进行存储以便对其进行快速搜索的二叉树结构，利用Kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。 1) Kd树的构建 取数据的某一维，将数据从小到大排序，以数据点在该维度的中值作为切分超平面，将该维一分为二，小于该中值的数据点挂在其左子树，大于该中值的数据点挂在其右子树。再按同样的方式切分另一维，直到所有维度处理完毕。 【例53】对二维平面点集合{［23］T,［54］T,［96］T,［47］T,［81］T,［72］T}构建Kd树。 解： (1) 选择要切分的维度。分别计算x1维和x2维的方差，选择方差大的x1维做切分。 (2) 切分x1维。 按数据x1维的数值排序： 2、4、5、7、8、9。 确定中值： 7(2、4、5、7、8、9的中值为(5+7)/2=6，由于中值需在点集合之内，取后一个7)。 确定节点： ［72］T。 分割空间： 以x1=7将x1维一分为二，［23］T、［47］T、［54］T挂在［72］T节点的左子树，［81］T、［96］T挂在［72］T节点的右子树。 (3) 切分x2维——［72］T节点的左子树。 按数据x2维的数值排序： 3、4、7。 确定中值： 4。 确定节点： ［54］T。 分割空间： 以x2=4将［72］T节点的左边空间一分为二，［23］T挂在［54］T节点的左子树，［47］T挂在［54］T节点的右子树。 (4) 切分x2维——［72］T节点的右子树。 按数据x2维的数值排序： 1、6。 确定中值： 6。 确定节点： ［96］T。 分割空间： 以x2=6将［72］T节点的右边空间一分为二，［81］T挂在［96］T节点的左子树。 Kd树构建完成，对二维空间的切分如图53(a)所示，构建的Kd树如图53(b)所示。 图53Kd树的构建 2) 最近邻搜索 给定点x，查询数据集中与其距离最近点的过程即为最近邻搜索，采用Kd树实现。过程如下： (1) 在Kd树中找出包含目标点x的叶节点。 从根节点出发，向下访问Kd树，如果x当前维的坐标小于切分点的坐标，则移动到左子节点，否则移动到右子节点，直到叶节点为止，以此叶节点为“当前最近点”。顺序存储经过的节点。 (2) 按存储顺序向上回溯，在每个节点处进行以下操作： ① 如果当前节点比当前最近点距离搜索点更近，则更新当前最近点为当前节点。 ② 以搜索点为圆心，以当前最近点到搜索点的距离为半径，确定圆，判断该圆是否与父节点的超平面相交； 如果相交，则进入父节点的另外一侧搜索最近邻节点； 如果不相交，则继续向上回溯。 当搜索到根节点时，搜索完成，得到最近邻节点。 【例54】利用例53建好的Kd树搜索［24.5］T的最近邻。 解： (1) 在Kd树中找出包含目标点x的叶节点。从根节点［72］T出发，当前维为x1，2＜7，移动到［72］T的左子节点［54］T； 当前维更新为x2，4.5＞4，移动到［54］T的右子节点［47］T； ［47］T为叶节点，设为当前最近点，到待搜索点［24.5］T的距离为10.25。存储经过的节点，即搜索路径为： ［72］T、［54］T、［47］T。 (2) 向上回溯到［54］T，［54］T到待搜索点［24.5］T的距离为9.25，9.25＜10.25，更新当前最近点为［54］T。 (3) 以［24.5］T为圆心、以9.25为半径的圆和父节点［54］T的超平面x2=4相交，如图54(a)所示，进入［54］T的另一侧查找，修改当前点为［23］T； 更新搜索路径为［72］T、［23］T。 (4) ［23］T到待搜索点［24.5］T的距离为2.25，2.25＜9.25，更新当前最近点为［23］T。 (5) 向上回溯到［72］T，［72］T到待搜索点［24.5］T的距离大于2.25，不修改当前最近点。 (6) 以［24.5］T为圆心、以2.25为半径的圆和父节点［72］T的切分平面x1=7不相交，如图54(b)所示，搜索完成，最近邻为当前最近点［23］T。 图54利用Kd树搜索最近邻 4. 仿真实现 近邻法原理简单，主要问题在于如何提高搜索效率。MATLAB中提供了相应的搜索函数，对其进行简要介绍。 1) ExhaustiveSearcher模型 存储训练数据、距离度量和参数值用于穷举最近邻搜索，穷举搜索算法在K值大(K＞10)时比Kd树算法更有效，在距离度量选择方面比Kd树算法更灵活。 (1) NS=CREATENS(X,'NSMethod','exhaustive')： 利用训练样本矩阵X创建ExhaustiveSearcher模型，X的每一行为一个样本，列数为样本维数。 (2) NS=ExhaustiveSearcher(X)： 利用训练样本矩阵X创建ExhaustiveSearcher模型。 (3) NS=ExhaustiveSearcher(X,Name,Value)： 指定参数创建ExhaustiveSearcher模型,参数如表51所示。 表51ExhaustiveSearcher函数参数表 参数名称取值及含义 Distance 距离度量方式，可取'euclidean'(默认)、'chebychev'、'cityblock'、'correlation'、'cosine'、'hamming'、'jaccard'、'minkowski'、'mahalanobis'、'seuclidean'、'spearman'或定制的距离函数 Cov采用马氏距离(mahalanobis)度量时指定n×n的正定协方差矩阵，默认为nancov(X) P采用闵氏距离(minkowski)度量时指定指数，默认为2 Scale采用标准欧氏距离(seuclidean)度量指定尺度参数，默认为nanstd(X) 2) KDTreeSearcher模型 存储使用Kd树算法的最近邻搜索结果，包括训练数据、距离度量及其参数、每个叶节点中的最大数据点数量。 (1) NS=CREATENS(X,'NSMethod','kdtree')： 利用训练样本矩阵X创建KDTreeSearcher模型。 (2) NS=KDTreeSearcher(X)： 利用训练样本矩阵X创建KDTreeSearcher模型。 (3) NS=KDTreeSearcher(X,Name,Value)： 指定参数创建KDTreeSearcher模型，参数如表52所示。 表52KDTreeSearcher函数参数 参数名称取值及含义 Distance距离度量方式，可取： 'euclidean'(默认)、'chebychev'、'cityblock'、'minkowski' P采用闵氏距离(minkowski)度量时指定指数，默认为2 BucketSize每个叶节点中的最大数据点数量，默认为50 3) knnsearch函数 指定模型实现近邻搜索。 (1) IDX=knnsearch(NS,Y)： 从模型NS存储的训练样本X中找到Y中每个样本的最近邻IDX。Y的每行为一个样本； IDX为一个列向量，存储Y中样本在X中的最近邻的索引。 (2) ［IDX,D］=knnsearch(NS,Y)： 同时返回列向量D，存储Y中样本和其最近邻的距离。 (3) ［IDX,D］=knnsearch(NS,Y,'NAME1',VALUE1,...,'NAMEN',VALUEN)： 指定参数实现最近邻搜索，参数如表53所示。 表53knnsearch函数参数 参数名称取值及含义 Distance采用ExhaustiveSearcher模型，取值见表51； 采用KDTreeSearcher模型，取值见表52； 部分距离可以设置参数，见表51和表52 K要搜索的近邻数目，默认为1； K不为1时，IDX和D均为矩阵 IncludeTies逻辑值，指定是否包括和第K个近邻距离并列的邻点，默认为false SortIndices逻辑值，指定输出的距离和索引是否按照距离从小到大排列，默认为true 4) rangesearch函数 指定模型实现一定范围内的近邻搜索。 (1) IDX=rangesearch(NS,Y,RADIUS)： 从模型NS存储的训练样本X中找到和Y中样本距离不超过RADIUS的样本。IDX为元胞数组，每一项存储Y中每一个样本的近邻索引，按距离升序排列。 (2) ［IDX,D］=rangesearch(NS,Y,RADIUS)： 元胞数组D存储Y中样本和各近邻的距离。 (3) ［IDX,D］=rangesearch(NS,Y,RADIUS,'NAME1',VALUE1,...,'NAMEN',VALUEN)： 指定参数搜索，参数有： 'Distance'、'SortIndices'以及距离度量参数，同knnsearch函数。 【例55】导入fisheriris数据集，随机选择147个训练样本，3个测试样本，采用knnsearch、rangesearch函数进行近邻搜索。 程序如下： clc,clear,close all; load fisheriris %导入数据 rng(1); %设定随机数生成模式 N=size(meas,1); %样本数 testIdx=randsample(N,3); %生成1:N的3个随机整数 trainIdx=~ismember(1:N,testIdx); %生成索引向量，随机数对应数值为0，其他数对应数值为1 testing=meas(testIdx,3:4); %测试样本，仅采用原始数据的第3维和第4维 training=meas(trainIdx,3:4); %训练样本 labeltrain=species(trainIdx,:); %训练样本的类别标签 labeltest=species(testIdx,:); %测试样本的类别标签 Mdl=KDTreeSearcher(training); %生成KDTreeSearcher模型 ［Idx1,D1］=knnsearch(Mdl,testing); %搜索最近邻 testresult=labeltrain(Idx1) %最近邻对应的类别即为分类结果 radius=0.2; %设定搜索范围的半径 ［Idx2,D2］=rangesearch(Mdl,testing,radius); %搜索范围 gscatter(training(:,1),training(:,2),labeltrain,'rgb','+.o',3); %绘制训练样本 hold on plot(testing(:,1),testing(:,2),'kx','MarkerSize',6,'LineWidth',2);%绘制测试样本 plot(training(Idx1,1),training(Idx1,2),'m*'); %绘制测试样本的最近邻 for i=1:length(Idx2) viscircles(testing(i,:),radius,'color','k','LineWidth',1,'LineStyle','-.'); end %绘制以测试样本为中心的圆，搜索范围 legend('setosa','versicolor','virginica','待测样本','最近邻点'); xlabel('花瓣长/cm'),ylabel('花瓣宽/cm'); hold off 运行程序，绘制的样本点、近邻点如图55所示，并在命令窗口输出3个待测样本的归类结果。 图55fisheriris数据集的近邻搜索 5.2二次判别函数 二次判别(Quadratic Discriminant)也是一种比较常用的固定函数类型的分类方法，一般形式为 g(x)=xTWx+wTx+w0 =∑ni=1wiix2i+2∑n－1i=1∑nk=i+1wikxixk+∑ni=1wixi+w0 (56) 其中，W是n×n的实对称矩阵，w是n维列向量。 由式(56)可以看出，二次判别函数中有太多的参数需要确定，如果采用类似于线性判别函数设计的方法，则计算复杂，在样本数不足的情况下，不能保证结果的可靠性和推广能力。因此，需要采用其他的设计方法。 在2.7节了解到，在一般正态分布情况下，贝叶斯决策判别函数为二次函数，如果可以用正态分布模拟样本分布，则直接定义ωj类的二次判别函数为 gj(x)=C2j－12x－μjTΣ－1j(x－μj)(57) C2j是一个调节项，受协方差矩阵和先验概率的影响，可以通过调节该参数调整类错误率。 例如，在例215中，针对两类正态分布的样本，利用fitcdiscr函数设计了二次判别函数。 如果只有一类数据可以用正态分布模拟，另一类比较均匀地分布在第一类附近，则可以只对第一类求解二次判别函数，决策规则为 若g(x)0，则决策x∈ω1 ω2(58) 【例56】导入fisheriris数据集，选择其中的两类，采用正态分布模拟样本分布，设计二次判别函数，绘制二次决策面。 程序如下： clc,clear,close all; load fisheriris index1=strcmp(species(:),'versicolor'); index2=strcmp(species(:),'virginica');%确定要选择的两类数据在数据集中的索引 training1=meas(index1,3:4); training2=meas(index2,3:4); %获取两类数据 training=［training1;training2］; index=［species(index1);species(index2)］; %获取训练样本类别标记 gscatter(training(:,1),training(:,2),index,'rb','*o',5); %绘制样本 hold on mu1=mean(training1); mu2=mean(training2); %估计两类样本均值 sigma1=cov(training1); sigma2=cov(training2); %估计两类协方差矩阵 minx=min(training(:,:)); maxx=max(training(:,:));%确定样本的取值范围 step=0.1; ［x1Grid,x2Grid］=meshgrid(minx(:,1):step:maxx(:,1),minx(:,2):step:maxx(:,2)); xGrid=［x1Grid(:),x2Grid(:)］; %确定待测样本 for i=1:length(xGrid) gx(i)=-(xGrid(i,:)-mu1)/(sigma1)*(xGrid(i,:)-mu1)'... (xGrid(i,:)-mu2)/(sigma2)*(xGrid(i,:)-mu2)';%计算各样本对应判别函数取值 end contour(x1Grid,x2Grid,reshape(gx,size(x1Grid)),［0 0］,'k--');%绘制决策面 legend('versicolor','virginica','决策面'); xlabel('花瓣长/cm'),ylabel('花瓣宽/cm'); hold off 程序运行结果如图56所示。程序中两类判别函数中调节项设为0。 图56二次判别函数设计 5.3决策树 人们在决策时，往往会针对多个方面依次判断，模式识别中也可以采用类似的多级决策方式，利用一定的训练样本，依次分类，直到获得最终可以接受的类，用树形表示决策的过程，并形成决策规则。这种从数据中“学习”出决策规则的方法称为决策树(Decision Tree)，是一种非线性分类器。 5.3.1基本概念 一般而言，一棵决策树包含一个根节点、若干内部节点和若干叶节点。根节点包含所要进行分类的样本集，按照某种规则(常用某一种特征测试)，将样本集一分为几个子集，对应几个子节点，称为内部节点； 子节点再分，直到叶节点，对应决策结果。 叶节点有三种情形： (1) 当前节点所含样本全属于同一类别，不需要再划分，该节点为叶节点。 (2) 当前特征为空，或所有样本当前特征取值相同，无法划分，该节点为叶节点，标记类别为该节点所含样本最多的类别。 (3) 当前节点所含样本集为空，无法划分，该节点为叶节点，标记类别为其父节点所含样本最多的类别。 以判断是否是高血压为例，说明决策树的生成以及决策。用x1表示收缩压，用x2表示舒张压，血压为二维样本x=［x1x2］T。图57(a)所示为正常血压ω1和高血压ω2二维样本集{x1,x2,…,xN}，生成的决策树如图57(b)所示。根节点①包括所有样本，考查第一个特征x1，根据是否满足x1＜140将样本集一分为二，即节点①有两个子节点②和③； 节点③中所有样本全部属于高血压ω2类，为叶节点，标记类别为ω2类； 节点②非叶节点，考查第二个特征x2，根据是否满足x2＜90将样本集一分为二，即节点②有两个子节点④和⑤； 节点④中所有样本全部属于正常血压ω1类，为叶节点，标记类别为ω1类； 节点⑤中所有样本全部属于高血压ω2类，为叶节点，标记类别为ω2类。从根节点①到叶节点③④⑤存在3条通路，通路上的判断条件即为决策规则，即 若x1≥140，则x∈ω2。 若x1＜140且x2＜90，则x∈ω1。 若x1＜140且x2≥90，则x∈ω2。 图57所示的决策树生成中，节点采用的分枝准则为“特征xi＜α或者xi≥α”，这种决策树称为普通二进制分类树(Ordinary Binary Classification Tree，OBCT)，也可以根据不同的条件生成不同的决策树。 图57决策树示例 5.3.2决策树的构建 从图57所示的决策树生成可以看出，决策树的构建就是选取特征和确定分枝准则的过程，每一个分枝应该产生比父节点样本集更有利于分类的样本子集，也就是新子集中的样本都更好地属于特定的类。因此，决策树的构建首先要有能衡量分类有利性的指标量，以便合理选择分枝采用的某个特征，以及确定分枝准则。 1. 信息增益 熵(Entropy)用来度量对某个事件进行观察后得到的信息量，设该事件有c种可能，每种可能对应的概率为Pj，j=1,2,…,c，熵为 H=－(P1log2P1+P2log2P2+…+Pclog2Pc)=－∑cj=1Pjlog2Pj(59) 例如，一个4类分类问题，各类样本数相同，根节点包括所有样本，样本属于某一类的不确定性最大，即纯度最低，对应的熵为 H=－4×0.25×log2 0.25=2 如果某个内部节点只包含其中两类的样本且数量相等，则样本属于某一类的不确定性相对于根节点要低，即纯度有所提高，对应的熵为 H=－2×0.5×log2 0.5=1 熵的值较根节点有所下降。而对于叶节点，只包含同一类样本，纯度最高，此时的熵为 H=－1×log21=0 熵最小，不确定性最小，纯度最高。 因此，对于某个节点上的样本，熵也称为熵不纯度，反映了该节点上的特征对样本分类的不纯度，取值越小，不纯度越低。 在决策树分枝的时候，希望分枝后的子集相对于原来的子集纯度有所提高，或说不纯度下降，因此，定义信息增益(Information Gain)为不纯度减少量。 如果某个节点上，把N个样本划分成m组，每组Nm个样本，则信息增益为 ΔH(N)=H(N)－［P1H(N1)+P2H(N2)+…+PmH(Nm)］(510) 其中，Pm=Nm/N。 2. ID3方法 交互式二分法(Interactive Dichotomizer3，ID3)是最早比较著名的决策树构建方法，对于每个非叶节点，计算比较采用不同特征进行分枝的信息增益，选择带来最大信息增益的特征作为分枝特征，以实现决策树的生成与构建，方法步骤如下： (1) 计算当前节点包含的所有样本的熵不纯度。 (2) 比较采用不同特征进行分枝将会得到的信息增益，选取具有最大信息增益的特征赋予当前节点。特征的取值个数决定了该节点下的分枝数目。 (3) 如果后继节点只包含一类样本，则停止该枝的生长，该节点成为叶节点。 (4) 如果后继节点仍包含不同类样本，则再次进行以上步骤，直到每一枝都到达叶节点。 【例57】以表54中的1~14号样本为训练样本，15~19号样本为测试样本，采用ID3算法设计决策树，并对测试样本进行决策。 表54血压数据表 序号年龄/岁体重饮食偏好父辈血压高血压 1 34 超重 油腻 高 是 2 28 正常 均衡 高 是 3 42 偏重 清淡 高 是 续表 序号年龄/岁体重饮食偏好父辈血压高血压 4 45 超重 均衡 正常 是 5 50 偏重 油腻 正常 是 6 61 偏重 油腻 正常 是 7 65 正常 清淡 高 是 8 36 超重 均衡 正常 否 9 31 正常 清淡 高 否 10 27 偏重 油腻 高 否 11 44 偏重 清淡 正常 否 12 43 偏重 均衡 正常 否 13 61 正常 清淡 正常 否 14 66 正常 清淡 正常 否 15 25 正常 均衡 正常 否 16 35 偏重 均衡 正常 是 17 48 超重 油腻 高 是 18 40 正常 清淡 正常 否 19 63 偏重 均衡 高 是 20 62 正常 均衡 正常 否 解： (1) 连续特征数据调整。表54中的年龄取值太多，如果直接按年龄分枝，将导致太多的子节点。因此把年龄分为三个级别，40岁以下为青年，40~59岁为中年，60岁及以上为老年，如表55所示。 表55血压数据表 序号年龄体重饮食偏好父辈血压高血压 1 青年 超重 油腻 高 是 2 青年 正常 均衡 高 是 3 中年 偏重 清淡 高 是 4 中年 超重 均衡 正常 是 5 中年 偏重 油腻 正常 是 6 老年 偏重 油腻 正常 是 7 老年 正常 清淡 高 是 8 青年 超重 均衡 正常 否 9 青年 正常 清淡 高 否 10 青年 偏重 油腻 高 否 11 中年 偏重 清淡 正常 否 12 中年 偏重 均衡 正常 否 13 老年 正常 清淡 正常 否 14 老年 正常 清淡 正常 否 15 青年 正常 均衡 正常 否 16 青年 偏重 均衡 正常 是 17 中年 超重 油腻 高 是 18 中年 正常 清淡 正常 否 19 老年 偏重 均衡 高 是 20 老年 正常 均衡 正常 否 (2) 生成决策树。 首先，计算不考虑任何特征时熵不纯度。14个人中高血压7人，正常血压7人，根节点熵不纯度为 H(14,7)=－［0.5×log2(0.5)+0.5×log2(0.5)］=1 其次，根节点分枝。考查采用不同特征划分样本后的信息增益。 采用“年龄”特征划分样本集： 青年组5人，高血压2人； 中年组5人，高血压3人； 老年组4人，高血压2人，熵不纯度为 Hage=514H(5,2)+514H(5,3)+414H(4,2)=0.9793 信息增益为 ΔHage(14)=H(14,7)－Hage=0.0207 采用“体重”特征划分样本集： 正常组5人，高血压2人； 偏重组6人，高血压3人； 超重组3人，高血压2人，熵不纯度为 Hweight=514H(5,2)+614H(6,3)+314H(3,2)=0.9721 信息增益为 ΔHweight(14)=H(14,7)－Hweight=0.0279 采用“饮食偏好”特征划分样本集： 油腻组4人，高血压3人； 清淡组6人，高血压2人； 均衡组4人，高血压2人，熵不纯度为 Hdiet=414H(4,3)+614H(6,2)+214H(4,2)=0.9111 信息增益为 ΔHdiet(14)=H(14,7)－Hdiet=0.0889 采用“父辈血压”特征划分样本集： 高血压组6人，高血压4人； 正常血压组8人，高血压3人，熵不纯度为 Hparent=614H(6,4)+814H(8,3)=0.9389 信息增益为 ΔHparent(14)=H(14,7)－Hparent=0.0611 采用“饮食偏好”特征划分样本集信息增益最大，用该特征将根节点一分为三，如图58(a)所示。 再次，下一级节点分枝。 节点②，4个样本，为序号1、5、6、10，高血压3人，熵不纯度为 H(4,3)=－34×log234+14×log214=0.8113 依次采用“年龄”“体重”“父辈血压”特征划分样本集，各自的熵不纯度和信息增益为 Hage=24H2,1+14H1,1+14H1,1=0.5000， ΔHage(4)=H(4,3)－Hage=0.311 Hweight=34H3,2+14H1,1=0.6887， ΔHweight(4)=H(4,3)－Hweight=0.1226 Hparent=24H2,1+24H2,2=0.5000， ΔHparent(4)=H(4,3)－Hparent=0.311 采用“年龄”和“父辈血压”划分样本集信息增益一样大，选择“年龄”特征将节点②一分为三，如图58(b)所示，其中，节点⑥和⑦中各有一个高血压类样本，为叶节点，标记为高血压类。 然后，同样的方法依次处理直到叶节点，生成的决策树共有4级，如图58(c)所示，方框表示叶节点。 图58用ID3方法对表54中数据判读是否高血压的决策树 (3) 利用决策树对测试样本进行决策。 首先，确定决策规则。生成的决策树有12个叶节点，从根节点到叶节点12条通路，对应12条决策规则，例如： 若(饮食偏好==油腻)且(年龄==青年)且(体重==超重)，则(血压=高血压)； 若(饮食偏好==油腻)且(年龄==青年)且(体重==偏重)，则(血压=正常血压)； …… 若(饮食偏好==清淡)且(父辈血压==正常)，则(血压=正常血压)。 其次，将待测样本代入决策规则进行判断。 15号样本，饮食偏好==均衡，体重==正常，节点⑧，判断为高血压，判断错误。 16号样本，饮食偏好==均衡，体重==偏重，节点⑩，判断为正常血压，判断错误。 17号样本，饮食偏好==油腻，年龄==中年，节点⑥，判断为高血压，判断正确。 18号样本，饮食偏好==清淡，父辈血压==正常，节点，判断为正常血压，判断正确。 19号样本，饮食偏好==均衡，体重==偏重，节点⑩，判断为正常血压，判断错误。 20号样本，饮食偏好==均衡，体重==正常，节点⑧，判断为高血压，判断错误。 例题中样本过少，叶节点往往只有一个样本，可能会抓住由于偶然性带来的假象，分类器判断准确率较差。可以采用剪枝的方式提高泛化能力，将在下节学习。 ID3方法虽然名为交互式二分法，但实际根据特征的取值可以划分为多个子节点。 【例58】采用例57中的数据，基于ID3方法设计决策树生成程序。 程序如下： clc,clear,close all; X=［"序号" "年龄" "体重" "饮食偏好" "父辈血压";"1" "青年" "超重" "油腻" "高";... "2" "青年" "正常" "均衡" "高";"3" "中年" "偏重" "清淡" "高";... "4" "中年" "超重" "均衡" "正常";"5" "中年" "偏重" "油腻" "正常";... "6" "老年" "偏重" "油腻" "正常";"7" "老年" "正常" "清淡" "高";... "8" "青年" "超重" "均衡" "正常";"9" "青年" "正常" "清淡" "高";... "10" "青年" "偏重" "油腻" "高";"11" "中年" "偏重" "清淡" "正常";... "12" "中年" "偏重" "均衡" "正常";"13" "老年" "正常" "清淡" "正常";... "14" "老年" "正常" "清淡" "正常"］;%训练样本，含序号和特征变量名 Y=［1;1;1;1;1;1;1;2;2;2;2;2;2;2］; %样本类别标签，1：高血压，2：正常血压 code_total=1; %当前节点总数 node{1,1}=1:size(X,1)-1; %存放节点包含的样本序号 node{1,2}=0; %存放节点级别，当前根节点，为0级 node{1,3}=code_total; %存放节点编号 node{1,4}=［］; %内部节点存放节点分枝特征，叶节点存放类别标签 node_cur=1; %当前节点编号 training{1,1}=X; training{1,2}=node_cur; %存放可分枝节点包含的样本及对应节点编号 label{1}=Y; %存放可分枝节点包含的样本对应的类别标签 stacknum=0; %处理到的可分枝节点序号，初始化为0 while stacknum~=size(training,1) %尚有未处理完的可分枝节点时进行循环处理 stacknum=stacknum+1; %当前处理到的可分枝节点序号 level=node{stacknum,2}+1; %当前节点所在级别 label_cur=label{stacknum}; %当前节点样本对应的类别标签 FatherI=calEnt(label_cur); %当前节点的信息熵 code_cur=training{stacknum,1}; %当前节点的训练样本 node_cur=training{stacknum,2}; %当前节点的编号 ［N,n］=size(code_cur(2:end,2:end)); %获取当前样本集的样本数目及可用于分枝的特征变量数 deltaI=zeros(n,1); %各特征对应信息增益初始值 for i=1:n %对每一个可用于分枝的特征进行计算 data=code_cur(2:end,i+1); %获取当前样本集的同一特征 sta=tabulate(data); %统计该特征的取值情况 sonI=0; %子节点信息熵初始值 for j=1:size(sta,1) %对于该特征的每种取值进行处理 templabel=label_cur(strcmp(data,sta(j,1))); %获取各个取值对应的类别标签 sonI=sonI+length(templabel)/N*calEnt(templabel);%计算按该特征分枝对应的熵 end deltaI(i)=FatherI-sonI; %计算按该特征分枝对应的信息增益 end ［~,pos］=max(deltaI); %找最大信息增益 node{node_cur,4}=code_cur(1,pos+1); %存放当前节点的分枝特征变量名 data=code_cur(2:end,pos+1); %获取分枝特征对应的数据 code_cur(:,pos+1)=［］; %从当前数据集中去掉该特征数据，在后续节点不再用该特征分枝 sta=tabulate(data); %统计分枝特征取值情况 for j=1:size(sta,1) %对分枝特征每种取值进行处理，有几种取值就对应几个子节点 code_total=code_total+1; %节点数增加 number=strcmp(data,sta(j,1)); %获取当前取值对应的样本序号 number=［false;number］; %增加一行，对应特征变量名所在行 node{end+1,1}=code_cur(number,1); node{end,2}=level; node{end,3}=code_total; %增加节点，存放样本序号、级别以及编号 templabel=label_cur(number(2:end));%新节点样本对应的类别标签 if length(unique(templabel))==1 %标签只有一种时，为叶节点，存放类别标签 node{end,4}=templabel(1); else %标签有多种时，存储该节点的信息 number(1)=true; training{end+1,1}=code_cur(number,:); %存储数据，含特征变量名 training{end,2}=code_total; %存储数据对应的节点编号 label{end+1}=templabel; %存储数据对应的类别标签 end end end function Entroph=calEnt(source) %计算当前序列的信息熵 Entroph=0; sta=tabulate(source); ［c,k］=size(sta); for j=1:c if sta(j,k)~=0 Entroph=Entroph-sta(j,k)/100*log2(sta(j,k)/100); end end end 运行程序，可以在工作区查看node变量，node为19×4的元胞数组，每一行表示一个节点的信息，分别为节点存放的样本序号、节点的级别、节点的编号、分枝特征(叶节点存放类别标签)，和图58(c)所示一致。 3. C4.5算法 C4.5算法采用信息增益率(Gain Ratio)代替信息增益来选择最优划分特征，增益率的定义为 ΔHR(N)=ΔH(N)H(N)(511) C4.5算法增加了处理连续特征的功能，采用了二分法将连续特征离散化为二值特征。设特征xi，i=1,2,…,n，在训练样本上共包含了m个值，将这些值按照从小到大的顺序排列，记为{x1i,x2i,…,xmi}； 设定一个阈值T，将数据分为两个子集x-i、x+i； 不同的阈值将导致不同的分割子集，对每种情况计算信息增益率，选择信息增益率最大的划分方案实现特征二值化，再进行决策树的生成。 阈值T可以取相邻两个取值的中值 T=xji+xj+1i2，j=1,2,…,m－1(512) 【例59】以表54中的1~14号样本为训练样本，采用C4.5算法生成决策树。 解： (1) 根节点熵不纯度为H(14,7)=1。 (2) 根节点分枝。考查采用不同特征划分样本后的信息增益率。 采用“体重”“饮食偏好”“父辈血压”特征划分样本集，信息增益率分别为0.0279、0.0889、0.0611。 对于“年龄”特征，根节点包含的样本在该特征上的取值排序为{27，28，31，34，36，42，43，44，45，50，61，61，65，66}； 阈值T取值为{27.5，29.5，32.5，35，39，42.5，43.5，44.5，47.5，55.5，63，65.5}，当T=27.5时，“年龄＜T”组1人，高血压0人； “年龄＞T”组13人，高血压7人，熵不纯度为 H1age=114H(1,0)+1314H(13,7)=0.9246 信息增益率为 ΔHR,age(14)=H(14,7)－H1ageH(14,7)=0.0754 依次修改阈值T，计算“年龄”特征最大信息增益率为0.0754，对应阈值T=27.5。 采用“饮食偏好”特征划分样本集信息增益率最大，因此，用该特征将根节点一分为三，如图59(a)所示。 (3) 下一级节点分枝。 节点②，4个样本，高血压3人，熵不纯度为H(4,3)=0.8113。采用“体重”“父辈血压”特征划分样本集，信息增益率分别为0.1511和0.3837。 对于“年龄”特征，节点②包含的样本在该特征上的取值排序为{27，34，50，61}，阈值T取值为{30.5，42，55.5}； 当T=30.5时，“年龄＜T”组1人，高血压0人； “年龄＞T”组3人，高血压3人，熵不纯度为0，信息增益率为1； 当T=42，T=55.5时，信息增益率分别为0.3837和0.1511。采用“年龄T=30.5”划分样本集信息增益率最大，选择“年龄”特征将节点②一分为二，子节点⑤中只有一个正常血压样本，为叶节点，标记为正常血压类； 子节点⑥中有3个高血压类样本，为叶节点，标记为高血压类，如图59(b)所示。 (4) 同样的方法依次处理直到叶节点，生成的决策树如图59(c)所示。 C4.5算法不需要事先将连续特征离散化为少量级别，但在生成决策树的过程中，取不同阈值将连续特征二值化，划分方案增多。另外，C4.5算法还可以处理部分特征缺失的样本。 图59用C4.5算法对表54中数据判读是否高血压的决策树 4. CART算法 分类和回归树(Classification And Regression Tree，CART)算法也是一个很著名的决策树算法，核心思想和ID3方法相同，主要不同之处在于，CART在每一个节点上都采用二分法，最终构成一棵二叉树； CART既可用于分类，也可以用于构造回归树对连续变量进行回归。下面主要介绍CART构建用于分类的决策树。 CART分类树算法使用基尼系数(Gini Index)来选择节点分枝特征。设样本集X={x1,x2,…,xN}有c个类别，其中第j类的概率为Pj，基尼系数定义为 Gini(X)=∑cj=1Pj1－Pj=1－∑cj=1P2j(513) 从定义可以看出，基尼系数反映了从样本中随机抽取两个样本，其类别标记不一样的概率。因此，基尼系数越小，两个样本来自不同类的概率越小，样本集不纯度越低。 如果各类的样本数为Nj，则样本集X的基尼系数为 Gini(X)=1－∑cj=1NjN2(514) 决策树生成中根据某个特征xi，i=1,2,…,n将样本集划分为两部分X1和X2，各自的样本数为N1和N2，按照xi划分的样本集的基尼系数为 Gini(X,xi)=N1NGini(X1)+N2NGini(X2)(515) 使用基尼系数来代替信息熵存在一定的误差，是熵模型的一个近似替代。但是，由于其避免了大量的对数运算，因此减少了计算量，简化了模型的运用。 【例510】以表54中的1~14号样本为训练样本，采用CART算法生成分类决策树。 解： (1) 根节点分枝。考查采用不同特征划分样本后的基尼系数。 采用“体重”特征划分样本集： 正常组5人，高血压2人，非正常组9人，高血压5人； 偏重组6人，高血压3人，非偏重组8人，高血压4人； 超重组3人，高血压2人，非超重组11人，高血压5人。三种划分情况的基尼系数分布为 Gini1weight=5141-252-352+9141-592-492=0.4889 Gini2weight=6141-362-362+8141-482-482=0.5 Gini3weight=3141-232-132+11141-5112-6112=0.4848 最小的基尼系数为0.4848。 同理，采用“饮食偏好”特征划分样本集，按照油腻和非油腻划分，基尼系数最小，为0.4500。 采用“父辈血压”特征划分样本集，基尼系数为0.4583。 对于“年龄”特征，根节点包含的样本在该特征上的取值排序为{27，28，31，34，36，42，43，44，45，50，61，61，65，66}； 阈值T取值为{27.5，29.5，32.5，35，39，42.5，43.5，44.5，47.5，55.5，63，65.5}，当T=27.5时，“年龄＜T”组1人，高血压0人； “年龄＞T”组13人，高血压7人，基尼系数为 Gini1age=1141-12+13141-7132-6132=0.4615 T取其他值情况下，基尼系数依次为0.5、0.4848、0.5、0.4889、0.5、0.4898、0.4583、0.4889、0.5、0.5、0.4615，最小基尼系数为0.4583，对应划分阈值T=44.5。 采用“饮食偏好”特征划分样本集基尼系数最小，用该特征将根节点一分为二。 (2) 下一级节点分枝。 节点②，4个样本，为序号1、5、6、10，高血压3人，采用“体重”特征划分样本集，偏重组3人，高血压2人，超重组1人，高血压1人，基尼系数为0.3333。 采用“父辈血压”特征划分样本集，基尼系数为0.25。 对于“年龄”特征，根节点包含的样本在该特征上的取值排序为{27，34，50，61}； 阈值T取值为{30.5，42，55.5}，当T=30.5时，基尼系数为最小值0。 采用“年龄”特征划分样本集基尼系数最小，用年龄30.5将根节点一分为二。 (3) 同样的方法依次处理直到叶节点，生成的决策树如图510所示，方框表示叶节点。节点⑧采用“饮食偏好”和“年龄”划分基尼系数相等，此处采用“饮食偏好”划分。最终的决策树有8个叶节点，对应8条决策规则。 图510用CART算法对表54中数据判读是否高血压的决策树 5.3.3过学习与决策树的剪枝 从5.3.2节的例子可以看出，决策树构建的同时，建立了决策规则，可以利用决策规则对未知类别的样本进行分类。依据有限样本全部正确划分为准则建立决策规则，需要考虑为未来数据分析时的成功率，即分类器的泛化性能。如果一个算法在训练数据上表现良好，但在测试数据或未来的新数据上的表现与在训练数据上差别很大，称该算法遇到了过学习或过适应。 在有限的样本下，如果决策树生长得很大(分枝多、级别多)，则可能会抓住由于偶然性或噪声带来的假象，导致过学习。例如例57利用ID3算法生成的决策树，仅14个训练样本，却生成了12条决策规则，每条决策规则对应的样本数很少，很有可能是偶然现象，导致了对于5个待测样本进行判断时错误率较高。 因此，要控制决策树规模，即剪枝(Prunning)，防止出现过学习。决策树剪枝的方法有两种基本策略： 先剪枝和后剪枝。 1. 先剪枝 先剪枝指的是在决策树生长过程中判断节点是继续分枝还是直接作为叶节点，某些节点不再分枝，将减小决策树的规模。 先剪枝的关键在于确定节点是否继续分枝的判断条件，有多种方法，比如： 设定信息增益阈值，若小于该值，则停止生长，但该阈值不易设定； 统计已有节点的信息增益分布，若继续生长得到的信息增益与该分布相比不显著，则停止生长等。剪枝主要是为了提高决策树泛化性能，可以通过实时检测当前决策树对于测试样本集的决策性能来判断节点是否继续分枝： 性能有所提高，则继续分枝； 性能没有提高，则直接作为叶节点。 因此，生成先剪枝决策树时，对于每个节点，进行如下操作： (1) 将节点视为叶节点，标记为该节点训练样本中数目最多的类别。 (2) 计算当前决策树对于测试样本集的分类精度。 (3) 寻找进行分枝的最优特征并进行分枝。 (4) 对分枝后的子节点进行标记。 (5) 验证分枝后的决策树分类精度是否有提高： 若有，则进行分枝； 若没有，则剪枝(即禁止分枝)，当前节点作为叶节点。 【例511】以表55中的1~14号样本为训练样本，15~20号样本为测试样本，采用ID3算法生成先剪枝决策树。 解： (1) 根节点是否分枝判断。 首先，标记。当前节点14个样本，7个高血压，7个正常血压，标记为“高血压”。 其次，计算分类精度。当前为根节点，认为所有的样本均为“高血压”，对于测试样本，6个样本3个判断正确，分类精度为3/6。 再次，寻找进行分枝的最优特征并分枝。由例57可知，采用“饮食偏好”特征划分样本集信息增益最大，用该特征将根节点划分为三个子节点②③④，各自的样本数及高血压样本数分别为油腻(4,3)，均衡(4,2)，清淡(6,2)。 然后，节点②③④分别标记为“高血压”“高血压”和“正常血压”。 最后，验证当前决策树的分类精度。测试样本集中16、17、18、19号样本分类正确，分类精度4/6，有提高，进行分枝。 (2) 节点②是否分枝判断。 首先，寻找进行分枝的最优特征并分枝。采用“年龄”特征划分样本集信息增益最大，用该特征将根节点划分为三个子节点，各自的样本数及高血压样本数分别为青年(2,1)，中年(1,1)，老年(1,1)。 其次，标记。三个子节点均被标记为“高血压”。 最后，验证当前决策树的分类精度。测试样本集中16、17、18、19号样本被正确分类，分类精度为4/6，没有提高，禁止该分枝，节点②为叶节点，标记为“高血压”。 (3) 节点③是否分枝判断。 首先，寻找进行分枝的最优特征并分枝。采用“体重”特征划分样本集信息增益最大，用该特征将根节点划分为三个子节点，各自的样本数及高血压样本数分别为正常(1,1)，超重(2,1)，偏重(1,0)。 其次，标记。子节点分别被标记为“高血压”“高血压”和“正常血压”。 最后，验证当前决策树的分类精度。测试样本集中17、18号样本被正确分类，分类精度为2/6，降低了，禁止该分枝，节点③为叶节点，标记为“高血压”。 (4) 节点④是否分枝判断。 首先，寻找进行分枝的最优特征并分枝。采用“父辈血压”特征划分样本集信息增益最大，用该特征将根节点划分为两个子节点，各自的样本数及高血压样本数分别为高血压(3,2)，正常血压(3,0)。 图511基于ID3算法利用表55 中数据生成先剪枝决策树 其次，标记。子节点分别被标记为“高血压”和“正常血压”。 最后，验证当前决策树的分类精度。测试样本集中16、17、18、19号样本被正确分类，分类精度为4/6，没有提高，禁止分枝，节点④为叶节点，标记为“正常血压”。 没有可分枝的节点，决策树生成到此为止，最终形成的先剪枝决策树如图511所示。 由例511可知，构建决策树时进行先剪枝，很多分枝未展开，降低了过学习的风险，减少了训练时间、测试时间开销； 有些分枝虽不能提升泛化性能，但在其基础上的后续划分有可能提高性能，因此，先剪枝有可能带来欠学习的风险。 2. 后剪枝 后剪枝指的是在决策树充分生长后对其进行修剪，核心思想是合并分枝，从叶节点出发，如果消除具有相同父节点的节点后能够提高决策树的泛化性能则消除，并以其父节点作为新的叶节点； 不断地从叶节点往上回溯，直到合并操作不再合适为止。 因此，生成后剪枝决策树时，进行如下操作： (1) 生成一棵完整的决策树，并计算决策树对于测试样本集的分类精度。 (2) 从最高级开始合并节点，对其父节点进行标记。 (3) 计算合并分枝后的决策树分类精度，并判断是否有提高： 若有，则剪枝(即进行合并)； 若没有，则不剪枝(保留分枝)。 (4) 向上回溯，重复(2)、(3)的合并、判断操作，直到不再需要合并为止。 【例512】以表55中的1~14号样本为训练样本，15~20号样本为测试样本，采用ID3算法生成后剪枝决策树。 解： (1) 生成完整的决策树如图512(a)所示，对测试样本进行分类，6个样本，两个正确，分类精度为2/6。 图512基于ID3算法利用表55中数据生成后剪枝决策树 (2) 合并第3级的节点和，其父节点⑤，2个样本中1个高血压样本，标记为“高血压”； 对测试样本进行验证，6个样本中2个判断正确，精度不变，不剪枝。 (3) 合并第3级的节点和，其父节点⑨，2个样本中1个高血压样本，标记为“高血压”； 对测试样本进行验证，6个样本中2个判断正确，精度不变，不剪枝。 (4) 合并第3级的节点、和，其父节点，3个样本中2个高血压样本，标记为“高血压”； 对测试样本进行验证，6个样本中2个判断正确，精度不变，不剪枝。 (5) 合并第2级的节点⑤、⑥和⑦，其父节点②，4个样本中有3个高血压样本，标记为“高血压”； 对测试样本进行验证，6个样本中2个判断正确，精度不变，不剪枝。 (6) 合并第2级的节点⑧、⑨和⑩，其父节点③，4个样本中有2个高血压样本，标记为“高血压”； 对测试样本进行验证，6个样本中4个判断正确，精度提高，剪枝。 (7) 合并第2级的节点和，其父节点④，6个样本中有2个高血压样本，标记为“正常血压”； 对测试样本进行验证，6个样本中4个判断正确，精度没有提高，不剪枝。 (8) 合并第1级的节点②、③和④，其父节点为根节点，标记为“高血压”，对测试样本进行验证，6个样本中3个判断正确，精度没有提高，不剪枝。 至此，没有节点可以再合并，最后生成的后剪枝决策树如图512(b)所示。 由例512可知，构建决策树时进行后剪枝，比先剪枝保留了更多的分支，欠学习风险小，泛化性能一般优于先剪枝决策树； 但是由于需要先生成完整决策树，训练时间和测试时间开销大。 5.3.4仿真实现 MATLAB中提供了生成分类决策树的相应函数，对其进行简要介绍。 1) ClassificationTree类 表示用于分类的二分决策树，使用fitctree函数创建ClassificationTree类对象，使用predict函数对样本进行分类决策，有多种属性和函数。 2) fitctree函数 使用CART算法创建ClassificationTree类对象，调用格式如下。 (1) TREE=fitctree(TBL,Y)： 利用表TBL中的数据训练ClassificationTree类TREE，Y可以是类别标号矩阵、TBL中变量名或者用字符串表示的公式。 (2) TREE=fitctree(X,Y)： 利用X中的数据训练ClassificationTree类TREE。X为N×n的矩阵，Y指定N个样本的类别标号。 (3) TREE=fitctree(...,'PARAM1',val1,'PARAM2',val2,…)： 指定参数训练决策树。部分参数如表56所示。 表56fitctree函数部分参数 参数名称取值及含义 ClassNames类名称矩阵，指定参与训练的类别，使用Y中的全部或部分元素对应的类，默认为全部 Cost方阵，Cost(i,j)为ωi类样本归为ωj类的损失，默认为0~1损失 MaxNumSplits最大分支节点数，默认为size(X,1)-1 续表 参数名称取值及含义 MinLeafSize指定叶节点最少要包含的样本数，默认为1 MinParentSize指定内部节点最少要包含的样本数。默认为10 Prune取'on'(默认)，进行剪枝； 取'off'，不剪枝 PruneCriterion指定剪枝标准，可取'error'(默认)或'impurity' SplitCriterion指定分枝准则，可取'gdi'(基尼的多样性指数，默认)、'twoing'、'deviance' Weights样本权值向量，默认为全1 3) predict函数 (1) label= predict(TREE,X)： 利用训练好的ClassificationTree模型TREE对矩阵或表X中的数据进行分类决策，返回分类标签向量。 (2) label=predict(TREE,X,'Subtrees',value)： 根据Subtrees指定级别的剪枝子树进行预测。'Subtrees'可取按升序排列的非负整数的向量，0表示不修剪的完整决策树，max(TREE.PruneList)表示只含根节点； 取'all'，要在0:max(TREE.PruneList)整个范围的剪枝子树上进行决策。 (3) ［label,score,node,cnum］=predict(…)： 同时返回分类得分矩阵(后验概率)score、预测的节点序号向量node和预测的类别编号向量cnum。 4) view函数 (1) view(TREE)： 在命令窗口输出决策树TREE的文字描述，以查看生成的决策树。 (2) view(TREE,'Mode',Value)： 指定决策树的查看方式。'Mode'可取'text'(默认)或'graph'，后者将打开分类树查看器实现交互式查看。 5) prune函数 (1) tree1= prune(TREE)： 生成决策树TREE的最佳剪枝决策树。 (2) tree1=prune(TREE,Name,Value)： 指定参数生成剪枝决策树。参数包括： 'Alpha'，剪枝代价； 'Level'，0到max(TREE.PruneList)的数值，剪枝级别，叶节点对应0级，内部节点的级别是其到最远叶节点的级差； 'Nodes'，取值在1到TREE.NumNodes的数值向量，指定的节点为tree1的叶节点。 【例513】以表54中的1~14号样本为训练样本，采用fitctree函数生成分类决策树，并对15~20号样本进行测试。 程序如下： clc,clear,close all; Age=［34;28;42;45;50;61;65;36;31;27;44;43;61;66］; %年龄特征 Weight={'超重';'正常';'偏重';'超重';'偏重';'偏重';'正常';… '超重';'正常';'偏重';'偏重';'偏重';'正常';'正常’'}; %体重特征 Diet={'油腻';'均衡';'清淡';'均衡';'油腻';'油腻';'清淡';… '均衡';'清淡';'油腻';'清淡';'均衡';'清淡';'清淡'}; %饮食偏好特征 Parent={'高';'高';'高';'正常';'正常';'正常';'高';… '正常';'高';'高';'正常';'正常';'正常';'正常'}; %父辈血压特征 X=table(Age,Weight,Diet,Parent); %创建表 Y={'是';'是';'是';'是';'是';'是';'是';'否';'否';'否';'否';'否';'否';'否’}; %类别标签 ctree=fitctree(X,Y,'Prune','off','MinParentSize',2); %生成不剪枝决策树，内部节点最少2个样本 view(ctree) %在命令窗口输出决策树的文字描述 view(ctree,'mode','graph') %决策树图形显示 Age=［25;35;48;40;63;62］; Weight={'正常’;’偏重’;’超重’;’正常’;’偏重’;’正常’'}; Diet={'均衡’;’均衡’;’油腻’;’清淡’;’均衡’;’均衡'}; Parent={'正常’;’正常’;’高’;’正常’;’高’;’正常'}; test=table(Age,Weight,Diet,Parent); %测试样本表 ［label,score,node,cnum］=predict(ctree,test); %对测试样本进行决策分类 程序运行，将在命令窗口输出文字描述的决策树，图形显示的决策树如图513所示，和图510一致，最后一个节点采用“饮食偏好”和“年龄”划分基尼系数相等，程序中“年龄”特征在前，因此采用“年龄”划分。6个测试样本分类结果依次为否、否、是、否、是、否，16号样本判断错误。 图513fitctree生成的判读是否高血压的未剪枝决策树 【例514】利用fisheriris数据集设计决策树，生成剪枝决策树，并利用不同剪枝决策树对样本［4.83.51.50.2］T进行判别。 程序如下： clc,clear,close all; load fisheriris ctree=fitctree(meas,species,'Prune','off','MinParentSize',5);%生成不剪枝决策树 view(ctree,'mode','graph') subtree=prune(ctree,'Level',2); %生成2级剪枝决策树 view(subtree,'Mode','graph'); pattern=［4.8 3.5 1.5 0.2］; label1=predict(ctree,pattern) %使用不剪枝决策树决策 label2=predict(ctree,pattern,'Subtrees','all') %使用各级剪枝决策树决策 label3=predict(subtree,pattern) %使用2级剪枝决策树决策 程序运行，生成的决策树如图514所示，同时在命令窗口输出决策结果： label1={'setosa'}； label2 为1×5的元胞数组，5个元素均为{'setosa'}，分别对应0~4级剪枝决策树的决策结果； label3 ={'setosa'}。 图514利用fisheriris数据集生成的决策树 5.4Logistic回归 Logistic回归(Logistic Regression)是一种经典分类方法，也称为对数概率回归(也有文献译为“逻辑回归”“逻辑斯谛回归”等)，是采用对数概率模型描述样本属于某类的可能性与样本特征之间的关系，用训练数据估计模型中的系数，进而实现分类的方法。 5.4.1基本原理 考虑二分类任务，采用线性判别函数g(x)=wTx+w0对样本x进行归类判别，设类别标签y∈{0,1}，将样本归类，需要根据g(x)的值判断y的值，因此，有 y=f［g(x)］(516) f(·)称为Link函数(Link Function)。 例如： 当g(x)＞0时，x∈ω1，y=1； 当g(x)＜0时，x∈ω2，y=0； 当g(x)=0时，可以任意判别。Link函数f(·)实际是单位阶跃函数，即 y=0，g(x)＜0 0.5，g(x)=0 1，g(x)＞0(517) 函数如图515所示。 单位阶跃函数不连续，用单调可微的Logistic函数近似表达单位阶跃函数为 y=11+e－g(x)(518) Logistic函数将g(x)的值转换为一个接近0或1的y值，在g(x)=0附近变化很陡，图形如图515中虚线所示。 图515单位阶跃函数和Logistic函数 由式(517)可知，y可以看作将样本x归为ω1类的可能性，则1-y是将样本归为ω2类的可能性，当y＞1-y时，x∈ω1； 当y＜1-y时，x∈ω2。定义概率为 y1－y=ewTx+w0(519) 反映了x归为ω1类的相对可能性。 对概率取对数得到logit函数 logit(x)=lny1－y=wTx+w0(520) 表明样本属于某类的可能性与样本之间呈线性关系。很明显 当logit(x)0时，x∈ω1 ω2(521) 如果能够确定w和w0，则可以确定logit函数，从而实现分类。 进一步，样本属于某一类的可能性用后验概率来表示，logit函数重写为 lnPy=1|xPy=0|x=wTx+w0(522) 其中， P(y=1|x)=11+e－wTx+w0=ewTx+w01+ewTx+w0(523) P(y=0|x)=1-P(y=1|x)=e－wTx+w01+e－wTx+w0=11+ewTx+w0(524) 采用最大似然估计的方法确定w和w0，给定数据集X={x1,x2,…,xN}，对应的类别标号为Y={y1,y2,…,yN}，对于每一个样本xi，i=1,2,…,N，有yi∈{0,1}，则 P(yi|xi; w,w0)=Pyi=1|xi; w,w0yi 1-Pyi=1|xi; w,w01-yi(525) 定义对数似然函数为 h(w,w0)=∑Ni=1lnP(yi|xi; w,w0)(526) 将式(523)、式(524)和式(525)代入式(526)，得 h(w,w0)=∑Ni=1－yiln1+e－(wTxi+w0)－(1－yi)ln(1+ewTxi+w0)(527) 对数似然函数求最大值得到最优的w和w0，或者对负对数似然函数求最小值，即 -h(w,w0)=∑Ni=1yiln1+e－(wTxi+w0)+1－yiln1+ewTxi+w0(528) 可以通过迭代策略求解。 【例515】三维空间两类分类问题，样本集为 ω1:000T,101T,100T,110T ω2:001T,011T,010T,111T 试用Logistic回归求解判别函数权向量，并对样本［00.60.8］T进行判别。 程序如下： clc,clear,close all; gX=@(W,X) W(1)*X(:,1)+W(2)*X(:,2)+W(3)*X(:,3)+W(4); %线性函数 logisticfun=@(W,X) 1./(1+exp(-gX(W,X))); %Logistic函数 training=［0 0 0;1 0 0;1 0 1;1 1 0;0 0 1;0 1 1;0 1 0;1 1 1］; label=［1;1;1;1;0;0;0;0］; %训练样本集类别标签 negloglikfun=@(W) -sum(label.*log(logisticfun(W,training))+... (1-label).*log(1-logisticfun(W,training)));%负对数似然函数 W0=［0;0;0;0］; %迭代求解初始值 opts=optimset('fminsearch'); opts.MaxFunEvals=Inf; opts.MaxIter=10000; %求最小值的相关设置 WHatML=fminsearch(negloglikfun,W0,opts) %求无约束多变量函数的最小值 pattern=［0 0.6 0.8］; %待测样本 logitX=WHatML(1)*pattern(1)+WHatML(2)*pattern(2)+WHatML(3)*pattern(3)+WHatML(4); if logitX>0 %计算logit函数值并判断类别 result=1; else result=0; end 程序中利用了fminsearch函数实现负对数似然函数求最小值，该函数利用NelderMead单纯性算法求极值。程序中最小值对应的权向量WHatML为［23.5306-24.3546-24.086212.5739］T，但是受初值的影响会发生变化。待测样本类别标签为0，归为第二类。 5.4.2多分类任务 设训练样本集为X={x1,x2,…,xN}，各自的类别标号yi∈{1,2,…,c}，c＞2为类别数。记将样本x标记为j的概率为Pj=P(y=j|x)，j=1,2,…,c，∑cj=1Pj=1，改写式(522)为 lnPj∑l≠jPl=wTjx+wj0(529) Pj=11+e－wTjx+wj0=ewTjx+wj01+ewTjx+wj0(530) ∑l≠jPl=1-Pj=e－wTjx+w01+e－wTjx+w0=11+ewTjx+w0(531) 同样采用最大似然估计的方法确定wTj和wj0。 5.4.3仿真实现 MATLAB提供了mnrfit函数拟合多分类Logistic回归模型，mnrval函数计算预测概率，主要的调用格式如下： (1) B=mnrfit(X,Y)： 根据矩阵X中的数据和对应的响应变量Y拟合多分类Logistic回归模型。X为N×n的矩阵，函数自动实现样本的增广化； Y可以是N×c的矩阵，Y(i,j)表示X中第i行的数据对应第j类的输出； Y可以是一个N维的列向量，元素值为1到c的整数值，也可以是一个N维的categorical数组，表明每个样本的类别； 输出变量B为估计的(n+1)×(c-1)的权向量矩阵，第一行为常数项，其余行依次对应数据的各维变量； B的每一列为该类相对于其余c-1类的Logistic回归分类权向量。 (2) PHAT=mnrval(B,X)： 根据多分类Logistic回归模型系数B，对X中的数据进行预测，返回N×c的预测概率矩阵PHAT。 另有fitglm函数创建广义线性回归模型GeneralizedLinearModel，设置参数'Link'为'logit'，实现Logistic回归分析； 使用predict函数实现预测。 【例516】利用MATLAB函数对例515中的数据进行Logistic回归分析。 程序如下： clc,clear,close all; gX=@(W,X) W(1)+W(2)*X(:,1)+W(3)*X(:,2)+W(4)*X(:,3); %线性函数，常数项为第一项 logisticfun=@(W,X) 1./(1+exp(-gX(W,X))); %Logistic函数P(y=1|X) training=［0 0 0;1 0 0;1 0 1;1 1 0;0 0 1;0 1 1;0 1 0;1 1 1］; label=［1;1;1;1;2;2;2;2］; B=mnrfit(training,label); %拟合模型，输出系数矩阵B，同线性函数中的w pattern=［0 0.6 0.8］; %待测样本 P=mnrval(B,pattern); %预测，输出概率矩阵 Py1=logisticfun(B,pattern); %根据式(5-23)计算P(y=1|X) Py2=1-Py1; %计算P(y=2|X) logitX=log(Py1/Py2); %计算logit函数，或logitX=log(P(1)/P(2))或logitX=gX(B,pattern); if logitX>0 result=1 else result=2 end 程序运行，系数矩阵B为［37.0123148.2485-93.8968-141.8509］T，即 lnP(y=1|x)Py=2|x=37.0123+148.2485x1-93.8968x2-141.8509x3。预测概率矩阵P为［01］，即P(y=1|x)=0，Py=2|x=1，与Py1、Py2一致。对待测样本计算logit函数值为负值，输出result=2，即将待测样本归为第2类。 【例517】利用fisheriris数据集拟合Logistic回归模型，并对样本［6.32.84.91.7］T进行归类。 程序如下： clc,clear,close all; load fisheriris sp=categorical(species); %将类别标记species转化为categorical数组 iris=［"setosa" "versicolor" "virginica"］; %类名称 B=mnrfit(meas,sp); %拟合Logistic回归模型 pattern=［6.3 2.8 4.9 1.7］; %待测样本 P=mnrval(B,pattern); %对待测样本进行预测，输出预测概率矩阵P ［~,pos］=max(P); %找出最大概率对应的类 result=iris(pos); %输出归类结果 disp('Logistic回归分类：') disp(result) 程序运行，预测概率矩阵P为［00.39770.6023］，即待测样本属于setosa、versicolor和virginica类的概率分别为0、0.3977以及0.60230，归入最大概率对应的类，在命令窗口输出： Logistic回归分类： virginica 5.5非线性判别分析的实例 【例518】对由不同字体的数字图像构成的图像集，实现基于最近邻法和Logistic回归的分类器设计及判别。 1. 设计思路 两种分类方法均采用和例216相同的预处理方法，提取同样的特征。在最近邻法中，测试样本在训练样本集中寻找最近邻，根据近邻的类别归类。设计方案如图516所示。Logistic回归分类要先拟合多分类Logistic回归模型，再根据概率实现分类决策，设计方案如图517所示。 图516最近邻归类设计方案框图 图517Logistic回归分类设计方案框图 2. 程序设计 1) 生成训练样本 读取训练图像文件，经过图像预处理，提取特征，生成训练样本。同例216。 2) 拟合多分类Logistic回归模型 Labeltrain1=categorical(labeltrain); %将0~9的数字转换为categorical数组 B=mnrfit(training,labeltrain1); 3) 生成测试样本 读取测试图像文件，经过图像预处理，提取特征，生成测试样本。同例216。 4) 对测试样本进行决策归类 (1) 利用训练样本生成KDTreeSearcher模型，并寻找最近邻，根据最近邻的类别决策归类，并测算检测率。 Mdl=KDTreeSearcher(training); ［Idx,D］=knnsearch(Mdl,testing); testnb=labeltrain(Idx); ratio1=sum(testnb==labeltest)/N (2) 利用Logistic回归模型系数B对测试样本进行预测，根据预测概率大小归类，并测算检测率。 P=mnrval(B,testing); ［~,testlogit］=max(P,［］,2); %预测概率矩阵P每一行求最大，对应的位置即是类别对应的正整数 testlogit=testlogit-1; ratio2=sum(testlogit==labeltest)/N 3. 实验结果 运行程序，采用10个数字的共50幅图像进行训练，采用30幅图像进行测试，在命令窗口输出ratio1=0.7667和ratio2=0.8000，即对于测试图像，最近邻法正确率达到76.67%，Logistic回归分类正确率达到80%。 习题 1. 简述最小距离分类器的分类方法及特点。 2. 简述近邻法的分类思路及特点。 3. 简述决策树方法的分枝过程和决策过程，并说明决策树剪枝优化的思路。 4. 对例510中CART算法生成的决策树进行剪枝。 5. 已知二维空间三类样本均服从正态分布μ1=［11］T，μ2=［44］T，μ3=［81］T，Σ1=Σ2=Σ3=2I，编写程序，基于这三类生成1000个二维向量的数据集，分别采用欧氏距离和马氏距离，利用数据集设计最小距离分类器。 6. 编写程序，随机生成二维向量作为待测样本，利用上题的训练样本，采用最近邻和5近邻方法对待测样本进行归类。 7. 利用3类样本ω1： -5 -5,-5 -4,-4 -5,-5 -6,-6 -5，ω2： 5 5,5 4,4 5,5 6, 6 5，ω3： -5 5,-5 4,-4 5,-5 6,-6 5，拟合Logistic回归模型，并对数据［-2-2］T进行归类。