层次分类算法设计

10．2　层次分类算法设计

根据以上分析，我们进行了层次分类的算法实验^［6—7］。

基于层次分类的训练算法和常规算法相比，主要区别在于增加了逐层进行类向量的构造上。可以根据类别体系的层次结构，逐类将属于该类及其子类的所有文献的特征向量相加，便可得到各个文献类的原始特征向量。

在多层次的分类算法中，算法总是在并列关系的类别之间进行，即有可能在第一层的“政策法律信息”到“房地产装修业”等类之间，或第二层的“法律”到“招商”等类目之间，或第二层的“房产”到“建材”等类目之间。

在层级分类过程中，当确定的类别没有与之有父子上下层关系的子类时，分类结束；反之，分类算法转到其子类进行，在有并列关系的子类之间确定类别。从整体看，分类的过程是一个从上而下的广度搜索过程，其终止条件为各层级的分类均完成。在这一过程中，前一级分类结果成为下一级分类的限定条件。

训练算法如下：

输入：原始文档抽词结果

输出：分层级的训练结果（各层类结点的模型向量库）

步骤：

对叶子结点到根结点每一层的所有结点自下而上进行处理。

Step1：统计本层范围类内类间词频

Step2：计算本层各类中心向量

1．若是叶子层结点，则统计该结点对应的类文档中的词频信息，包括各特征项的词频统计、总词数和总词频，并生成向量权值

2．若非叶子层结点，则采用下层的向量权值累加方法计算本层结点向量权值

Step3：生成本层知识向量矩阵表

Step4：若未到顶层转Step2，否则训练结束

分类过程算法如下：

输入：类目结点体系集合V、向量知识矩阵表T、待分类文档D

输出：分配好合适类别的文档

Step1：待分类文档的向量化

Step2：根结点→叶子结点

1．依次计算待分类文档与本层各类结点之间的相似度

2．确定最相似结点V^max，作为下层的次根结点

3．若到根结点，结束匹配，否则转1

Step3：输出D所属类别C或给出无法分类结论

具体过程如图10－2所示。

图10－2　多层次分类过程流程示意图

分类过程示意如图10－3（假设分类体系为三层：｛0，1，2，3｝，｛01，02，03，04，05｝，｛021，022，023，024｝，其中打阴影部分示意分类过程）。从图10－3中可以看出，对待分类文本不是直接进行最终类别的确定，而是先从根结点出发。按照平均每个大类含20个小类计算，则第一层分类的类别数缩简率为75%。经过第一层分类，将该文档限定在第02小类中，将不再与其余小类发生混淆。依次可类推出其余层次分类情况。

图10－3　分类过程示例图