模式识别-第五章-关于树状分类器和分段线性分类器-1_84.pdf

《模式识别-第五章-关于树状分类器和分段线性分类器-1_84.pdf》由会员分享，可在线阅读，更多相关《模式识别-第五章-关于树状分类器和分段线性分类器-1_84.pdf（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器12010/3第五章 关于树状分类器和分段线性分类器第五章 关于树状分类器和分段线性分类器Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器22010/35.1 多类线性判别和树状分类器多类线性判别和树状分类器（边书（边书P112）?多类问题中的线性判别函数（共有s2个类）把把s类问题转化成类问题转化成(s-1)个两类问题个两类问题第第i个问题：用一个线性判别函数分开属于个问题：用一个线性判别函数分开属于i 类的样本和不属于类的样本和不属

2、于i 类的样本类的样本斜线阴影为不确定区域斜线阴影为不确定区域Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器32010/3多类问题中的线性判别函数（续多类问题中的线性判别函数（续1）中间和四角区域为不确定区域中间和四角区域为不确定区域把把s类问题转化成类问题转化成 s个两类问题（续）个两类问题（续）Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器42010/3多类问题中的线性判别函数（续多类问题中的线性判别函数（续2）用个线性函数两两成对地进行判别用个线性函数两两成对地进行判别()

3、2/12=ssCs每个线性函数只对其中两个类别分类每个线性函数只对其中两个类别分类斜线阴影为不确定区域斜线阴影为不确定区域Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器52010/3多类问题中的线性判别函数（续多类问题中的线性判别函数（续3）用个线性函数两两成对地进行判别用个线性函数两两成对地进行判别（续）（续）()2/12=ssCs中间区域为不确定区域中间区域为不确定区域Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器62010/3多类问题中的线性判别函数（续多类问题中的线性判别

4、函数（续4）如果R如果Ri与R与Rj相邻，该两类间的界面为超平面相邻，该两类间的界面为超平面 Hij的一部分的一部分线性机器：定义线性机器：定义s 个识别函数个识别函数()siwXWXdiTii,.,2,1 ,0=+=如果对于所有如果对于所有ji，存在，存在()()XdXdji则则iX整个特征空间分割为整个特征空间分割为s个决策区域R个决策区域R1,RR2,RRs当当X在区域R在区域Ri中时，中时，di(X)最大最大超平面超平面 Hij的方程，或的方程，或()()XdXdji=()()000=+jiTjiwwXWW超平面超平面 Hij的法向量为，的法向量为，X 到到Hij的距离为的距离为()j

5、iWW()()jiiiWWXdXdr=（见（见3.2最小欧氏距离分类）最小欧氏距离分类）权向量的差比权向量本身更重要权向量的差比权向量本身更重要Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器72010/3多类问题中的线性判别函数（续多类问题中的线性判别函数（续5）虽有个决策区域的虽有个决策区域的“对对”，只有相邻区域有界面 实际界面上的超平面个数常常少于个，只有相邻区域有界面 实际界面上的超平面个数常常少于个()2/12=ssCs()2/12=ssCs例例1Xinggang Lin,Tsinghua University 第五章 关于树

6、状分类器和分段线性分类器82010/3多类问题中的线性判别函数（续多类问题中的线性判别函数（续6）例例2线性机器：决策区域为凸形、单连通，简单、便于分析线性机器：决策区域为凸形、单连通，简单、便于分析Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器92010/3简单的二叉树分类器简单的二叉树分类器?把复杂的多类分类问题，转化成分层次的两类问题把复杂的多类分类问题，转化成分层次的两类问题?不试图用一种算法在不试图用一种算法在n维特征空间同时分开多个类别维特征空间同时分开多个类别?每次使用一个特征（或特征集），把每次使用一个特征（或特征集），

7、把“当前的当前的”模式类候选集一分为二个候选子集（即：作为一个两类问题处理）模式类候选集一分为二个候选子集（即：作为一个两类问题处理）?以此类推，直到把所有的类都分开（每个候选子集中只有一个候选模式类）以此类推，直到把所有的类都分开（每个候选子集中只有一个候选模式类）Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器102010/3简单的二叉树分类器（续）简单的二叉树分类器（续）s,.,21ifif1,.,1sss,.,11+jfkfjfkfpfpf lm例：共有例：共有s个类个类s,.,21和和根据是否具有特征（集）根据是否具有特征（集）

8、fi分成两个子集分成两个子集1,.,1sss,.,11+再根据是否具有特征（集）再根据是否具有特征（集）fj，把再分成两个子集，把再分成两个子集1,.,1s再根据是否具有特征（集）再根据是否具有特征（集）fk，把再分成两个子集，把再分成两个子集ss,.,11+每次一分为二（两类问题分类），直到每个子集只有一类为止每次一分为二（两类问题分类），直到每个子集只有一类为止同一层特征同一层特征fj和和fk可以相同，也可以不同可以相同，也可以不同若能找到同一层特征都相同，划分若能找到同一层特征都相同，划分s个类至少要个特征个类至少要个特征S2logXinggang Lin,Tsinghua Univer

9、sity 第五章 关于树状分类器和分段线性分类器112010/3简单二叉分类树设计简单二叉分类树设计?考虑减少错误概率考虑减少错误概率?在分类树的较在分类树的较“上层上层”（接近树根）若分类错误，则在下层不易纠正 可利用（接近树根）若分类错误，则在下层不易纠正 可利用4.2“分层聚类分层聚类”所获得的分类树所获得的分类树越接近树根相似度越小，易获较小错误概率越接近树根相似度越小，易获较小错误概率关键能否在分叉处找到合适的特征（集）和分类规则关键能否在分叉处找到合适的特征（集）和分类规则如有必要，分叉两侧的集合的如有必要，分叉两侧的集合的“交集交集”也可不为空集也可不为空集Xinggang Li

10、n,Tsinghua University 第五章 关于树状分类器和分段线性分类器122010/3简单二叉分类树设计（续）简单二叉分类树设计（续）?考虑提高分类速度：让类先验概率较大的靠近树根考虑提高分类速度：让类先验概率较大的靠近树根设中的类先验概率满足设中的类先验概率满足s,.,21()()()sPPP.21将与合成为一个候选集，令将与合成为一个候选集，令s1s1s()()()sssPPP+=11重复上述操作，直到最终只剩下一个集合（树根）例重复上述操作，直到最终只剩下一个集合（树根）例（利用（利用Huffman编码原理）编码原理）：类别类别165432()P4.03.01.01.006.

11、004.04.03.01.01.01.04.03.02.01.04.03.03.06.04.00 Level4 Level1 Level2 Level3 Level有助于提高分类速度，减少特征提取所需费用有助于提高分类速度，减少特征提取所需费用关键能否在分叉处找到合适的特征（集）和分类规则关键能否在分叉处找到合适的特征（集）和分类规则Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器132010/31n图分类树（决策树）示意一般分类树（决策树）的定义一般分类树（决策树）的定义（边书（边书P113）分类树分类树T的组成：的组成：一个根节点一个

12、根节点n1一组非终止节点一组非终止节点ni一组终止节点一组终止节点tjtj：与各个类别对应：与各个类别对应不同的终止节点也可与相同类别对应不同的终止节点也可与相同类别对应分类树分类树T对应于特征空间一种划分对应于特征空间一种划分某个被划分区域中某类样本最多，该节点就与该类样本对应某个被划分区域中某类样本最多，该节点就与该类样本对应对于一般分类树，某节点的子节点不限于两个（对于一般分类树，某节点的子节点不限于两个（e.g.图中图中n5）候选子集的划分条件不限于某特征（集）候选子集的划分条件不限于某特征（集）fi的的“有有”或或“无无”不限于转化为不限于转化为“两类两类”的分类问题（也可能为多类问

13、题）的分类问题（也可能为多类问题）Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器142010/3一般分类树（决策树）的数学表述一般分类树（决策树）的数学表述对于全体样本集对于全体样本集S，其中每个样本，其中每个样本X分别属于分别属于s个类中的某一类，个类中的某一类，Si 表示属于第表示属于第 i 类的样本的集合类的样本的集合为便于表述各个类，定义一个与各类的为便于表述各个类，定义一个与各类的“标记标记”（序号）对应的标记集，以及一个（序号）对应的标记集，以及一个 I 的非空子集的非空子集 Ii 的集合的集合sI,.,2,1=ipIII,

14、.,21=为便于论述，可令为便于论述，可令jiIIji=空集），当(（注：实际上为避免上层分类错误在下层不可纠正，也可令）（注：实际上为避免上层分类错误在下层不可纠正，也可令）jiIIji，广义决策规则，表示全体样本集广义决策规则，表示全体样本集 S 到与各个类相对应的子样本集到与各个类相对应的子样本集 Si 的一个映射的一个映射（即：将样本分配到相应各类）（即：将样本分配到相应各类）Sf:若将属于第若将属于第 i 类的样本映射到包含类的样本映射到包含 i 的那个子集的那个子集Ik，则识别正确，则识别正确设设T(S,I)是由全体样本集是由全体样本集S和类别标记集和类别标记集 I 所形成的所有可

15、能映射的集合，则所形成的所有可能映射的集合，则T(S,I)可表示为由二元组组成的集合，集合的每个元素称作一个节点可表示为由二元组组成的集合，集合的每个元素称作一个节点()iia,()iia,Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器152010/3一般分类树（决策树）的数学表述（续一般分类树（决策树）的数学表述（续1）：该节点上表征这种映射的参数：该节点上类别标记集：该节点上表征这种映射的参数：该节点上类别标记集 Ii 的非空子集的集合的非空子集的集合iaipiiiIII,.,21=（二元组：表示用什么样的参数将样本（二元组：表示用

16、什么样的参数将样本“映射映射”到哪一些类中）到哪一些类中）()iia,设设 ni和和 nj为为T(S,I)的两个节点：的两个节点：()iipiiiiiiIIIan,.,21=()jjpjjjjjjIIIan,.,21=若若Ujpliikjlpk II=11 ,则称则称 ni为为 nj的父节点，的父节点，nj为为 ni的子节点的子节点设是节点的有穷集，且。设是节点的有穷集，且。()ISTB,Bn若若B中没有一个元素是中没有一个元素是n的父节点，则称的父节点，则称n是是B的根节点的根节点Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器1620

17、10/3一般分类树（决策树）的数学表述（续一般分类树（决策树）的数学表述（续2）若满足如下条件，则称若满足如下条件，则称B为一棵分类树（决策树）：为一棵分类树（决策树）：()ISTB,1)B中有且只有一个根节点中有且只有一个根节点2)设设 ni和和 nj是是 B 中的两个不同元素，则中的两个不同元素，则UUjipljlpkikII11（不同节点与不同的模式类候选集相对应）（不同节点与不同的模式类候选集相对应）3)对于每一个类别标记，集合对于每一个类别标记，集合 B 中存在一个节点中存在一个节点Ii()kpkkkkkkIIIan,.,21=且且k 中的一个元素就是中的一个元素就是 i。（nk的子

18、节点中，与该元素对应的那个子节点称作的子节点中，与该元素对应的那个子节点称作“叶节点叶节点”或或“终止节点终止节点”）（意即：每个）（意即：每个“终止节点终止节点”对应于一个类）对应于一个类）注：若规定，则每个类别标记只在一个终止节点处出现。若允许同一类别标记在多个不同终止节点出现，则可取消此规定。注：若规定，则每个类别标记只在一个终止节点处出现。若允许同一类别标记在多个不同终止节点出现，则可取消此规定。jiIIji=空集），当(（意即：同一个模式类可经由不同途径来判别）（意即：同一个模式类可经由不同途径来判别）Xinggang Lin,Tsinghua University 第五章 关于树状

19、分类器和分段线性分类器172010/3简单二叉树分类器示例简单二叉树分类器示例43x21x3n2n52x1n235t4t22x14n3t322t1t一个的一个的3类问题类问题3,2,1=I每次选用一个特征分类每次选用一个特征分类最终确定最终确定X所属类别所属类别Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器182010/3二叉树分类器对特征空间的划分二叉树分类器对特征空间的划分（每次只用一个特征时）（每次只用一个特征时）ifkfjf示意图示意图看成用与特征轴垂直的超平面来划分特征空间，每次一分为二看成用与特征轴垂直的超平面来划分特征空间

20、，每次一分为二关键在于能否找到相应特征把所有类分开关键在于能否找到相应特征把所有类分开Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器192010/3讨论讨论?简化特征空间的划分，判别简单明确简化特征空间的划分，判别简单明确?便于用硬件或软件实现便于用硬件或软件实现?特别对超多类的分类问题，大幅度提高分类速度特别对超多类的分类问题，大幅度提高分类速度?例：汉字识别，常采用例：汉字识别，常采用3-4级分类级分类?例：例：10万人大样本库人脸识别万人大样本库人脸识别?PCA特征脸粗分类、级联精细弹性匹配：允许识别率下降特征脸粗分类、级联精细弹

21、性匹配：允许识别率下降0.5%时速度提高约时速度提高约50倍倍（丁嵘，清华大学博士论文，（丁嵘，清华大学博士论文，2002年年10月）月）?树结构设计、特征选择、分类规则确定都不容易树结构设计、特征选择、分类规则确定都不容易?整体优化的理论和实践都比较复杂，有兴趣者可参阅边书整体优化的理论和实践都比较复杂，有兴趣者可参阅边书P115-116（一般同学不作为要求）（一般同学不作为要求）?近年有近年有AdaBoost分类器，级联弱分类器来组成强分类器分类器，级联弱分类器来组成强分类器Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器202010

22、/35.2 分段线性分类器分段线性分类器（边书（边书P120）?若树状分类器各节点采用线性判别规则，就构成分段线性分类器若树状分类器各节点采用线性判别规则，就构成分段线性分类器1a11ax 211cx 12b22bx 22a22ax 1B1x2x0例：例：1:2:若每次只用一个特征，则界面为与特征轴垂直的超平面（图中粗线）若每次只用一个特征，则界面为与特征轴垂直的超平面（图中粗线）BoundaryB:Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器212010/3其他单一特征界面举例其他单一特征界面举例若每次只用一个特征，则界面为与特征轴

23、垂直的超平面若每次只用一个特征，则界面为与特征轴垂直的超平面Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器222010/3用分段线性界面逼近非线性界面用分段线性界面逼近非线性界面分段线性判别函数：决策面由若干段超平面组成，用于逼近各分段线性判别函数：决策面由若干段超平面组成，用于逼近各种形状的超曲面种形状的超曲面（边书（边书P120）通常比高次超曲面简单可能获得任意精度逼近通常比高次超曲面简单可能获得任意精度逼近Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器232010/35.2

24、.1 基于到类中心距离的分段线性判别基于到类中心距离的分段线性判别（边书（边书P120）?基于最小欧氏距离的分类判别（复习）基于最小欧氏距离的分类判别（复习）01x2x1M2MX()0=Xd()12221 ,0X则正态分布正态分布各类协方差矩阵相同各类协方差矩阵相同各类先验概率相同各类先验概率相同各特征统计独立且方差相同均值各特征统计独立且方差相同均值M代表类，用距离判别相似度界面：两类中心连线的中垂面代表类，用距离判别相似度界面：两类中心连线的中垂面适用于贝叶斯最小错误概率判别适用于贝叶斯最小错误概率判别Xinggang Lin,Tsinghua University 第五章 关于树状分类器

25、和分段线性分类器242010/3基于到类中心距离的分段线性判别（续基于到类中心距离的分段线性判别（续1）?当各类具有多峰分布时的两类问题当各类具有多峰分布时的两类问题例：例：21111mm 和有两个密度峰值点3222122,3mmm个密度峰值点有若以两类中心和为代表点分类，得线性界面若以两类中心和为代表点分类，得线性界面，错误率大，错误率大1m2m若第若第1类取两个代表点和，第类取两个代表点和，第2类取类取3个代表点来分类，得分段线性界面个代表点来分类，得分段线性界面，虽然每段仍是最小欧氏距离判别，但整体可减小错误率，虽然每段仍是最小欧氏距离判别，但整体可减小错误率11m21m322212,m

26、mm关键：如何找出各类多个代表点关键：如何找出各类多个代表点Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器252010/3基于到类中心距离的分段线性判别（续基于到类中心距离的分段线性判别（续2）?分段最小欧氏距离线性分类器分段最小欧氏距离线性分类器（例如）可用聚类把具有多峰分布的类（例如）可用聚类把具有多峰分布的类i分割为分割为 li个子类，或者说把该类样本区域个子类，或者说把该类样本区域RRi分成为分成为li个子区域个子区域iliiiiRRRR,.,21=iliiii,.,21=每个子类取一个代表点（例如均值）每个子类取一个代表点（例

27、如均值）liilillM,.,2,1,=定义识别函数定义识别函数()siMXXdlillii,.,2,1 ,min,.,2,1=判别规则：若判别规则：若()()XdXdisij,.,2,1min=则则jX一种可能的应用：字符识别一种可能的应用：字符识别若（语义意义上的）每个字符作为一类，则可将该字符的不同字体作为不同的子类（例如多字体数字识别）若（语义意义上的）每个字符作为一类，则可将该字符的不同字体作为不同的子类（例如多字体数字识别）Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器262010/301x2xiM1jM2?虽将一类分割为若

28、干子类，但仍假定了各子类符合最小欧氏距离判别的前提条件（正态、等方差等）虽将一类分割为若干子类，但仍假定了各子类符合最小欧氏距离判别的前提条件（正态、等方差等）5.2.2 基于到界面距离的分段线性判别基于到界面距离的分段线性判别（边书（边书P121）X例：例：子类符合正态分布、但协方差矩阵不同子类符合正态分布、但协方差矩阵不同X到欧氏距离较小，但属于概率更高到欧氏距离较小，但属于概率更高iM1j2iM1改进：参照改进：参照3/4，为每个子类定义一个线性识别函数，取代到类中心欧氏距离，为每个子类定义一个线性识别函数，取代到类中心欧氏距离()liTliliwXWXd0+=silli,.,2,1,.

29、,2,1=的阈值权：子类的权向量，：子类lilililiwW0类的线性判别函数：类的线性判别函数：i()()siXdXdlillii,.,2,1 ,max,.,2,1=判别规则：若判别规则：若()()XdXdisij,.,2,1max=则则jX识别界面：若与相邻，则界面为识别界面：若与相邻，则界面为limj()()XdXdmjli=分段线性分段线性Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器272010/3?利用训练样本确定各子类的识别函数中权向量和常数项阈值权两个参数，利用训练样本确定各子类的识别函数中权向量和常数项阈值权两个参数，

30、生成相应分段线性识别函数的算法生成相应分段线性识别函数的算法（3种）种）（边书（边书P122）liWliliw0silli,.,2,1 ,.,2,1=1.利用多类线性识别函数算法利用多类线性识别函数算法已知子类数目和训练样本所属子类时已知子类数目和训练样本所属子类时（边书（边书P122）各子类看成一个独立的类，利用各子类看成一个独立的类，利用5.1 多类线性判别算法，确定各子类识别函数多类线性判别算法，确定各子类识别函数()sillXdili,.,2,1 ,.,2,1 ,=例：若（语义意义上的）每个字符作为一类，则可将该字符的不同字体作为不同的子类（例如多字体数字识别）例：若（语义意义上的）每

31、个字符作为一类，则可将该字符的不同字体作为不同的子类（例如多字体数字识别）例：用聚类分析来确定子类所属样本例：用聚类分析来确定子类所属样本2.利用多类问题的迭代修正求权向量算法（梯度下降法）利用多类问题的迭代修正求权向量算法（梯度下降法）已知子类数目、但不知各子类样本划分时已知子类数目、但不知各子类样本划分时（参阅（参阅2类情况、复习类情况、复习3.2、3.4）设扩展特征向量（设扩展特征向量（n+1维）维）()TnxxxX1,.,21=设扩展权向量（设扩展权向量（n+1维）维）()siwwwwWTiiniii,.,2,1 ,.,021=线性识别函数线性识别函数()siXWXdTii,.,2,1

32、 ,=Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器282010/3利用多类问题的迭代修正求权向量算法（续利用多类问题的迭代修正求权向量算法（续1）算法算法（边书（边书P122最后）最后）il1)设定各子类的识别函数的的初始扩展权向量设定各子类的识别函数的的初始扩展权向量（为类中的子类个数，括号中数字为迭代次数）（为类中的子类个数，括号中数字为迭代次数）()()()siWWWiliii,.,2,1 ,1,.,1,121=ili2)用训练样本迭代修正权向量用训练样本迭代修正权向量在第在第k次迭代中，设次迭代中，设j 类中的样本与类中的样本

33、与j 类的某个子类的权向量的内积值最大，即类的某个子类的权向量的内积值最大，即jX()kWmj()()jjjTljlljTmjXXkWXkWj=,max,.,2,1若若()()ijTlijTmjlljisiXkWXkW,.,2,1 ,.,2,1 ,=则说明权向量组不影响正确分类，所以各权向量保持不变，即则说明权向量组不影响正确分类，所以各权向量保持不变，即()()()kWkWkWiliii21,.,jX()()ililillsikWkW,.,2,1 ,.,2,1 ,1=+Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器292010/3利用

34、多类问题的迭代修正求权向量算法（续利用多类问题的迭代修正求权向量算法（续2）()()jiXkWXkWjTkijTmj ,若存在某个或某几个子类的识别函数不满足上述条件，即存在，使若存在某个或某几个子类的识别函数不满足上述条件，即存在，使ki说明被相应的识别函数错分，这些函数的权向量要修改说明被相应的识别函数错分，这些函数的权向量要修改jX设设()(),maxmaxmaxjTkikijTkiXkWXkW=则作如下修正则作如下修正()()1jkmjmjXckWkW+=+()()maxmaxmaxmax1jkkikiXckWkW=+（ck为一任意正常数，例如为一任意正常数，例如 c=1，或由计算得到

35、，参阅，或由计算得到，参阅3.4）其他权向量保持不变，即其他权向量保持不变，即()()maxmax ,1kliimljikWkWlili=+且且3)重复上述迭代过程，直到不再有权向量被修正，或达到预定迭代次数重复上述迭代过程，直到不再有权向量被修正，或达到预定迭代次数（对于给定的子类数目分段线性不可分，即算法不收敛）（对于给定的子类数目分段线性不可分，即算法不收敛）Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器302010/34W3W2W1WX树状分段线性分类方法（逐块二分）树状分段线性分类方法（逐块二分）（边书（边书P123）3.树状

36、分段线性分类方法树状分段线性分类方法未知子类数目时未知子类数目时一般情况下子类数目未知，下述为方法之一。两类分布如图一般情况下子类数目未知，下述为方法之一。两类分布如图先用两类线性函数判别算法找出一个扩展权向量，它对应的超平面将全体样本分为两部分，称为样本子集先用两类线性函数判别算法找出一个扩展权向量，它对应的超平面将全体样本分为两部分，称为样本子集1W1H由于样本集线性不可分，所以每部分仍然包含两类样本由于样本集线性不可分，所以每部分仍然包含两类样本继续用上述算法找出第二、第三个扩展权向量、，对应的超平面、分别把相应的样本子集分成两部分继续用上述算法找出第二、第三个扩展权向量、，对应的超平面

37、、分别把相应的样本子集分成两部分3H2W3W2H若任一部分仍包含两类样本，则重复上述操作，直到某一扩展权向量（图中）把两类样本完全分开为止若任一部分仍包含两类样本，则重复上述操作，直到某一扩展权向量（图中）把两类样本完全分开为止4W最终界面分段线性（图中粗线）最终界面分段线性（图中粗线）Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器312010/3树状分段线性分类方法（续）树状分段线性分类方法（续）（边书（边书P123）?识别过程是一个二叉树分类过程，如图识别过程是一个二叉树分类过程，如图01XWT04XWT03XWT02XWTYNNN

38、NYYY11122对图中样本，经过三步判别，得对图中样本，经过三步判别，得（图中粗线）（图中粗线）X1X?讨论讨论结果随初始权向量不同而不同结果随初始权向量不同而不同寻找权向量方法不同结果也不同寻找权向量方法不同结果也不同通常可取分属两类样本欧氏距离最小的一对样本，取其垂直平分面的法向量作为的初始值通常可取分属两类样本欧氏距离最小的一对样本，取其垂直平分面的法向量作为的初始值1W对包含两类样本的子类也可如此对包含两类样本的子类也可如此然后求得局部最优解作为第一个超平面的法向量然后求得局部最优解作为第一个超平面的法向量*1WXinggang Lin,Tsinghua University 第五章

39、 关于树状分类器和分段线性分类器322010/35.2.3 利用区域利用区域“交交”和和“并并”的方法的方法（边书（边书P124）两类问题中两类问题中一类具有多峰分布，或可分成若干孤立子域一类具有多峰分布，或可分成若干孤立子域或一个类域包含另一个类域或一个类域包含另一个类域设设1 类可划分为类可划分为r 个子类个子类r121111.=jiji=,11假定子类能用假定子类能用mi 段线性界面将其与段线性界面将其与2分开分开i1()0=XLijimjri,.,2,1 ,.,2,1=每个界面都把整个特征空间分成两个半空间，设子类在界面的每个界面都把整个特征空间分成两个半空间，设子类在界面的i正半空间

40、的正半空间的“交交”空间中，则所有都在该交空间之外，即每个界面要：空间中，则所有都在该交空间之外，即每个界面要：1()0=XLijiX1()XWXLTijij=imjri,.,2,1 ,.,2,1=iXj1 ;,0若iXj1 ;,0若Xinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器332010/3利用区域利用区域“交交”和和“并并”的方法（续的方法（续1）()XWXLTijij=imjri,.,2,1 ,.,2,1=iXj1 ;,0若iXj1 ;,0若上式等价于上式等价于()()()0,.,min211XLXLXLPXiimiiii，则函

41、数若01iiPX，则函数若函数函数 Pi在特征空间中，界定了子类所在的区域在特征空间中，界定了子类所在的区域i1i1R类类1在特征空间中所在的区域在特征空间中所在的区域r121111.RRRR=若，虽然，但是若，虽然，但是()ilXXli11,()(,0minilXLPljjl=()0min=XLPijji由此由此()()()0,.,.,max1XPXPXPPri若，则与上述同理，可推出若，则与上述同理，可推出2X()()()0,.,.,max1=XPXPXPPri所以，函数所以，函数 P 可以用作识别函数可以用作识别函数Xinggang Lin,Tsinghua University 第五章

42、 关于树状分类器和分段线性分类器342010/3推广到一般两类问题推广到一般两类问题“析取析取”和和“合取合取”符号符号：和 对逻辑运算，表示对逻辑运算，表示“析取析取”（OR）和）和“合取合取”（AND）对集合运算，表示）对集合运算，表示“并并”(union)和和“交交”(intersection)对数值运算，表示对数值运算，表示“取大取大”(max)和和“取小取小”(min)设设1 类可划分为类可划分为r 个子类个子类r121111.=对每个子类可定义一个识别函数对每个子类可定义一个识别函数()()()XLXLXLPiimiii,.,min21根据前述界面对特征空间的划分可知，根据前述界面

43、对特征空间的划分可知，Pi 定义了子类的区域，可记作定义了子类的区域，可记作i1()0=XLiji1RriLLLPiimiii,.,2,1 ,.21=()XWXLTijij=imjri,.,2,1 ,.,2,1=iXj1 ;,0若iXj1 ;,0若其中每个线性识别函数需满足条件：其中每个线性识别函数需满足条件：类类1在特征空间中所在的区域为，可定义在特征空间中所在的区域为，可定义()()()rriPPPXPXPXPP=.,.,.,max211r121111.RRRR=可得分段线性识别函数可得分段线性识别函数1 ,0XP若2 ,0XP若Xinggang Lin,Tsinghua Universi

44、ty 第五章 关于树状分类器和分段线性分类器352010/3分段线性函数的递归定义分段线性函数的递归定义设设Li 是线性函数，是线性函数，i=1,2,r，则分段线性函数可递归定义为：，则分段线性函数可递归定义为：（1）L1,L2,Lr都是分段线性函数都是分段线性函数（2）如果）如果A和和B都是分段线性函数，那么都是分段线性函数，那么AB和和AB也是分段线性函数也是分段线性函数（3）分段线性函数只能由（）分段线性函数只能由（1）和（）和（2）的形式给出）的形式给出由此，任何分段线性函数都可表示为如下两种一般形式：由此，任何分段线性函数都可表示为如下两种一般形式：()()ppmppmLLLLLLP

45、=.21112111()()qqmqqmLLLLLLQ=.21112111和和前者称为分段线性函数的前者称为分段线性函数的“析取范式析取范式”，后者称为，后者称为“合取范式合取范式”析取范式中的每个称为一个析取范式中的每个称为一个“凹函数凹函数”()iimiiLLL.21P是是p个凹函数的个凹函数的“并并”，即在，即在p个凹函数中求最大的凹函数个凹函数中求最大的凹函数用分段线性函数递归定义表达识别函数，且令用分段线性函数递归定义表达识别函数，且令p=r，有：，有：riLLLPiimiii,.,2,1 ,.21=rPPPP=.21()XWXLTijij=imjri,.,2,1 ,.,2,1=iX

46、j1 ;,0若iXj1 ;,0若则个扩展权向量就能对样本正确分类则个扩展权向量就能对样本正确分类=riimt121,.,tWWWXinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器362010/3利用分段线性函数进行分类利用分段线性函数进行分类分段线性函数分段线性函数P是全体训练样本集是全体训练样本集S和扩展权向量的函数和扩展权向量的函数21,.,tWWW()21,.,;tWWWSP如何利用训练样本集如何利用训练样本集 S 求出求出 t 个扩展权向量满足：个扩展权向量满足：21,.,tWWW()()0,.,;,0,.,;,212211ttWW

47、WSPXWWWSPX有对于有对于例：分布如图，例：分布如图，r=3，m1=5，m2=4，m3=4分段线性函数分段线性函数P为为()()()34333231242322211514131211 LLLLLLLLLLLLLP=也即也即,min ,min ,minmax34333231242322211514131211LLLLLLLLLLLLLP=共有个线性函数共有个线性函数13321=+=mmmtXinggang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器372010/3求取分段线性函数的算法步骤求取分段线性函数的算法步骤可知，这样选出的样本可知，这样

48、选出的样本X一定最接近由所确定的超平面。一定最接近由所确定的超平面。()kWi设分属于设分属于1 类和类和2 类的训练样本集分别为和类的训练样本集分别为和)1(1iXS=)2(2jXS=T设总共需要设总共需要 t 个线性识别函数个线性识别函数()tiXWXLii,.,2,1 ,=1)任意给定初始扩展权向量任意给定初始扩展权向量()()()0,.,0,021tWWW2)令为第令为第k次迭代时得到的扩展权向量，次迭代时得到的扩展权向量，()()()kWkWkWt21,.,按如下方法计算第按如下方法计算第k+1次迭代时的扩展权向量次迭代时的扩展权向量()()()1,.,1,121+kWkWkWt选择

49、训练样本集和。选择训练样本集和。()kAi1()kAi2若若k=0，则令和，分别为从，则令和，分别为从S1和和S2中任意选出的一些第一类和第二类样本的非空子集。中任意选出的一些第一类和第二类样本的非空子集。()01iA()tiAi,.,2,1 ,02=若若k0,则令和，分别为则令和，分别为S1和和S2中所有满足下式的样本组成的样本子集：中所有满足下式的样本组成的样本子集：()kAi1()tikAi,.,2,1 ,2=()()()()()kWkWXPXkWSXXkAtTii122,.,;=且()()()()()kWkWXPXkWSXXkAtTii111,.,;=且ti,.,2,1=式中Xingg

50、ang Lin,Tsinghua University 第五章 关于树状分类器和分段线性分类器382010/3求取分段线性函数的算法步骤（续）求取分段线性函数的算法步骤（续）以和为训练样本集，求第以和为训练样本集，求第k+1次迭代的最优扩展权向量次迭代的最优扩展权向量()kAi1()kAi2()tikWi,.,2,1 ,1*=+即寻找即寻找 t 个线性判别函数，能将和的样本有效地分开。个线性判别函数，能将和的样本有效地分开。()kAi1()kAi2这可用前述各种线性判别算法求解，例如，可将作为初始扩展权向量，用类似这可用前述各种线性判别算法求解，例如，可将作为初始扩展权向量，用类似3.4所述迭