树分类器简介

常用树分类器

树分类器的设计

树分类器简介

树分类器是需要通过多级判别才能确定模式所属类别的一种分类方法。多级判别过程可以用树状结构表示，所以称为树分类器。

常用树分类器

最常用一类树分类器，称为二分树分类器。例如在对0～9十个数字进行识别时，可以先根据某些特征把0，6，8，9，4分成一类（C1）,把1，2，3，5，7分成一类(C2),然后根据这些特征或另外一些特征把0，6，8，9，4这一类再分成0，4，8一类 (C3)和4，6，9一类(C4)等，直到最后把各个数字分开为止（见图）。这种树状结构由节点和树枝所组成，它的特点是除了树根C0没有前级节点(父节点)以外，其余节点都有唯一的父节点（例如C的父节点是C,且所有的节点都可以从树根沿树枝所组成的路径达到。没有后继节点（子节点）的节点叫作叶，如C8，C10，C11等，其余的叫作非终止节点。每个非终止节点都只有两个子节点的树分类器，

每个终止节点对应一个类别，为了提高树分类器的正确识别率，允许有几个叶对应同一个类别。非终止节点对应的类别是它的子节点所对应的类别的总和。

树分类器的设计

树分类器的设计需要解决以下几个问题：

①　确定树的结构。树结构影响正确识别率和平均判别次数，一般根据所研究问题的性质确定某种与正确识别率有联系的目标函数代替正确识别率，作为判断结构是否合理的标准，从树根出发在每个非终止节点寻找使目标函数达到最小（或最大）的子节点和对应的类别配置。

②　对每个非终止节点选择用于判别的特征子集，分枝限界算法能提供选择最佳特征子集的有效方法。

③　为每个非终止节点确定判别函数，最常用的判别函数是线性判别函数。

由于在每个非终止节点需要判别的类别比较少，在多数情况下,可以用较少的特征和较简单的判别函数(因而较少的计算机时间)以达到总体上比较好的分类效果。