基于TAN的文本分类集成方法

1、基于TAN 的文本分类集成方法    基于TAN 的文本分类集成方法#刘佳，贾彩燕*基金项目：本文受高等学校博士学科点专项科研基金项目（20070004038）资助作者简介：刘佳，（1985-），男，硕士，主要研究方向：文本挖掘通信联系人：贾彩燕，（1976-），女，讲师，主要研究方向：数据挖掘、生物信息学、复杂网络分析等. E-mail: EBag-TAN 与单个最优TAN 分类器的分类性能相当。进一步说明了集成方法适用于弱分类器，即如果单个分类器的分类能力越强，集成后的效果越差。需要给出有效的方法增加不同的单分类器之间的分类差异，从而提高集

2、成分类器的分类性能。而对于文本分类问题，基于特征集选取的集成方法可以构造出单个分类器多样性较大的集成分类方法。45 1 集成学习目前，集成学习分为基于数据的集成方法和基于特征的集成方法两种。基于数据的集成主要使用随机取样的方法获取训练数据，它是集成学习算法获取差异性个体经常使用的方法，包括有放回随机取样、无放回随机取样与混合取样（包括无放回随机取样与有放回随机取样）。比较经典的算法包括：Boosting 和Bagging。基于特征集的集成方法通过提取不同50 的特征子集来训练集成模型中的个体，是提高集成个体差异性的一种较好的方法，适用于学习性能较稳定的分类器。1.1 Boosting 算法Bo

3、osting 算法的基本思想是试图通过产生数个简单的、精度比随机猜测略好的粗糙估计（Boosting 算法中称为弱规则T h , h ,.h 1 2 ），再将这些规则集成构造出一个高精度的估计。55 这种思想起源于Valiant 提出的PAC 学习模型4。在PAC 模型中定义了两个概念：强学习和弱学习。Keams 和Valiant 提出了弱学习算法与强学习算法间的等价问题5，即是否能把弱学习算法转化为强学习算法？如果两者等价，那么只要找到一个比随机猜测略好的弱学习算法就可以直接将其提升为强学习算法，而不必直接去找很难获得的强学习算法。Keams和Valiant6证明只要有足够的数据，弱学习算法

4、就能通过集成的方式生成任意高精度的估60 计。1990 年，Schapire7最先构造出一种多项式级的算法，即最初的Boosting 算法。1991年，Freund8提出了一种效率更高的Boosting 算法。由于早期的Boosting 算法在解决实际问题时要求事先知道弱学习算法学习正确率的下限，这实际上很难做到。1995 年，Freund和Schapire9提出了AdaBoost（Adaptive Boosting）算法，这种算法的效率和原来Boosting算法的效率一样，但不需要任何关于弱学习器性能的先验知识，可以非常容易地应用到实际65 问题中。因此，该算法已成为目前最流行的Boosti

5、ng 算法。AdaBoost 算法的主要思想是给定一个训练集( , ), ( , ),.( , ) 1 1 2 2 m m x y x y x y ，1,+1 i y 。初始化时AdaBoost 指定训练集上的分布为1/m，并按照该分布调用弱学习器对训练集进行训练。每次训练后，根据训练结果更新训练集上的分布，并按照新的样本分布进行训练。反复迭代T 轮，最终得到一个估计序列T h , h ,.h 1 2 ，每个估计都具有一定的权70 重，最终的估计H 是采用有权重的投票方式获得。AdaBoost 算法9的伪代码如下：输入：训练集( , ),., ( , ) 1 1 m m S = x y x y

6、 ，其中x X i ， 1,+1 i y ，X 表示一个实例空间；迭代次数T 和弱分类器。初始化：权重D (i) 1/ m 1 = ，i = 1, , m。执行：For t = 1, , T1) 对有权重分布的训练集进行学习，得到一个估计t h ： 1,+1 i 75 x ；2) 计算t h 训练偏差= mit t t i i D i h x y1 ( ) ( )，如果= 0 t或者 1/ 2 t，令T = t-1 并跳出循环；3) 令0.5 ln(1 ) / t t t = × ；4) 更新权重： t t t i t i t D (i) D (i)exp y h (x )

7、 / Z 1 = + ，其中t Z 是标准化因子。输出： ( ) ( ( )1 =Ttt t 80 H x sign h x 。上面给出的算法是针对于两分类问题的，关于如何将Boosting 算法应用到多分类问题，研究者提出了多种不同的方法，包括AdaBoost.M191、AdaBoost.M291和AdaBoost.MH92等算法。其中，AdaBoost.M1 是最直接的应用于多分类问题的方法，其算法步骤如下：输入：训练集( , ),., ( , ) 1 1 m m S = x y x y ， y Y 1,2,., k i = ，迭代次数T 和弱学习85 算法。初始化：权重D (i) 1/

8、m 1 = ，i = 1, , m。执行：For t = 1, , T1) 用弱学习算法对有权重分布的训练集进行学习；2) 得到一个估计t h ： X Y ；3) 计算t h 训练偏差=: ( )( )i ht xi yit t D i ，如果> 1/ 2 t 90 ，令T = t-1 并跳出循环；4) 令/(1 ) t t t = ；5) 更新权重： = × +t i it t i ittt h x yh x yZD iD i1 ( )( ) ( )( ) 1，其中t Z 是标准化因子。输出： =t h x y ty YtH x: ( )( ) argmax log 1。1.

9、2 Bagging 算法95 Bagging11（Bootstrap aggregating）是Breiman 在1996 年提出的与Boosting 相似的技术。Bagging 的基础是重复取样，它通过产生样本的重复Bootstrap 实例作为训练集，每次运行Bagging 都随机地从大小为m 的原始训练集中抽取l 个样本作为此次训练的集合。这种训练集被称作原始集合的Bootstrap 复制，这种技术也叫Bootstrap 综合，即Bagging。平均来说，每个Bootstrap 复制包含原始训练集的63.2%，原始训练集中的某些样本可能在新的训100 练集中出现多次，而另外一些样本则可能一

10、次也不出现。Bagging 通过重新选取训练集增加了分量学习器集成的差异度，从而提高了泛化能力。Breiman11同时指出，稳定性是Bagging 能否提高预测准确率的关键因素。Bagging 对不稳定的学习算法能提高预测的准确度，而对稳定的学习算法效果不明显，有时甚至会使预测精度降低，学习算法的不稳定性是指如果训练有较小的变化，学习算法产生的预测函数将105 发生较大的变化。Bagging 算法的原理如下，给定一个数据集( , ),., ( , ) 1 1 l l L = x y x y ，基础学习器为h(x, L) 。如果输入为x，就通过h(x, L) 来预测y。现在，假定有一个数据集序列

11、 k L ，每个序列都有l 个与L 从同样分布数据集得来的独立观察组成，任务是使用 k L 来得到一个更好的学习器，它比单个数据集学习器h(x, L) 要强。Bagging 算法的伪代码如下： 输入：训练集( , ),.,( , ) 1 1 m m 110 S = x y x y ，迭代次数T 和弱学习算法。执行：For t = 1, , T1) 从初始的训练集中采用bootstrap 方法抽取l 个训练实例组成的子集S ' ；2) 在S ' 上，利用弱学习算法训练得到弱分类器，得到预测函数t h ： X Y ；输出： = =Tiiy YH x h x y1( ) a

12、rg max ( ( ) )115 Bagging 算法与Boosting 算法的主要区别在于Bagging 训练集的选择是随机的，各轮的训练集之间是相互独立的，而Boosting 训练集的选择不是独立的，各轮训练集的选择与前面各轮的学习结果有关；Bagging 的各个预测函数没有权重，而Boosting 是有权重的；Bagging的各个预测函数可以并行生成，而Boosting 的各个预测函数只能顺序生成。对于像神经网络这样极为耗时的学习方法，Bagging 可以通过并行训练节省大量时间开销。另外，一些研120 究者发现1213，一般情况下，Bagging 方法总是可以改善学习系统的性能；而B

13、oosting方法在有效时效果比Bagging 还好，但在无效时却可能使学习系统的性能恶化。值得注意的是，Boosting 和Bagging 的轮数并非越多越好，实验表明13，学习系统性能的改善主要发生在最初的若干轮中。1.3 基于特征集的集成方法125 基于不同特征集选取的集成方法是用来提高集成个体差异性的另一类方法，通过提取不同的特征子集来训练集成中的个体。为了提高集成个体的差异性，通常采取不同的技术获取这组特征子集。最直接的方法就是在大小为n 的特征集合中，求出所有的特征子集，然后在其中选取所需要的特征子集集合。但由于特征子集所构成的搜索空间由2n 种可能状态构成，显然，即使在特征数目不

14、多的情况下，搜索空间也是庞大的。在实际应用中，这种穷尽130 式搜索是不可行的，因此，研究者们致力于用启发式搜索算法寻找特征子集集合。Ho14提出了构建决策森林的随机子空间方法，在这种方法中，随机选择特征子集，并分配给学习算法，然后在这个子空间中生成分类器，最后根据分类器的正确率使用加权投票方法进行集成。Opitz 提出了基于遗传算法的特征选择的集成学习算法15；Oliveira 等人运用了多目标的遗传算法16。135 另外，Tumer 与Oza17提出了ID( Input Decimation) 方法，这种方法目的是减少集成成员产生错误的相关性，通过使用不同的特征子集训练集成中的成员，这种方

15、法与随机子空间方法是不同的，因为对于每一类，要计算每个特征与类的输出间的相关性，并且仅在特征最相关的子集上训练集成成员。Bryll 等人18提出的AB(Attribute Bagging)算法是基于特征选择的集成学习方法的代表140 性算法。该算法通过对属性进行随机扰动，可以得到较强的泛化能力，AB 算法主要有两步：(1) 寻找最优的属性集规模。所用方法为随机投影出不同大小属性集规模的训练数据，对每份训练数据用可重复取样技术生成多个子训练集，构建分类器，再用集成测试其精度，这样可以得到不同属性集规模的精度曲线，最高精度所对应的属性集规模被认为是最优的属性集规模，为了得到较为平滑的精度曲线，通常

16、需要在数据集上循环计算若干遍，然后求得145 平均值。(2) 提高投票精度。在(1)的基础上用随机投影的方法生成大量的具有最优属性规模的训练数据，针对每份训练数据构建分类器，然后根据这些分类器在原始训练数据或原始训练数 据的子集上的分类精度进行排序，取精度最高的一部分参加投票。可以看出，由于AB 算法在第(2)步中需要寻找最优的属性集规模，而这又需要对所有可150 能规模的属性子集进行多遍考察，其时间开销很大。综上所述，对于上面的这些基于特征集的集成学习方法可以概括为如下的集成学习框架：1) 选取不同的特征集以构成特征集的集合；2) 使用这组特征集集合生成集成中的个体；155 3)

17、选取一种结论生成方法对个体结论融合。2 TAN 文本分类集成方法根据上一节中介绍的Boosting、Bagging 和基于特征集的集成方法的思想，我们分别结合TAN 模型进行了TAN 集成的三次尝试，得到的三种集成模型分别为：AdaBoost.M1 TAN，简称AdaM1-TAN；Extended Bagging TAN，简称EBag-TAN；Feature Random Subspace TAN，160 简称FRS-TAN。2.1 TAN 集成模型之一：AdaM1-TAN首先，我们将Boosting 与TAN 模型相结合来对TAN 集成。由于本文研究的是文本的多分类问题，为简便起见，我们利用

18、Boosting 多分类问题的最直接方法AdaBoost.M1作为集成算法；为避免阈值选取的麻烦，基分类器采用ATAN 框架19，得到各阈值下分类165 性能最优的TAN 分类器（具体利用CR-ATAN 算法19）；结论生成时采用投票方法。我们给该集成模型命名为AdaBoost.M1 TAN，为方便叙述，简称为AdaM1-TAN。AdaM1-TAN 的算法流程叙述如下：输入：训练文档集( , ),( , ),.,( , ) 1 1 2 2 N N D = d y d y d y ， y C 1,2,.,| C | i = ，其中N 表示训练集文档的个数，C 表示文档所属的类别集合，|C|表示类

19、别数目；另设迭代次数T。1) 利用ATAN 框架中的CR-ATAN 算法从训练文档集学习ATAN 结构模型ATAN 170 G ；2) 初始化每个训练集文档的权重：D (i) 1/ N 1 = ，i = 1, , N；3) For t = 1, , Ta) 从有权重分布的训练文档集中学习ATAN G 结构的参数；b) 得到一个分类器t h ；c) 利用分类器t h 对训练集文档进行分类，并计算偏差=: ( )( )i ht di yit t 175 D i ，如果> 1/ 2 t，令T = t-1 并跳出循环；d) 令/(1 ) t t t = ；e) 更行训练集文档的权重： = 

20、15; +t i it t i ittt h x yh x yZD iD i1 ( )( ) ( )1 ( )，其中t Z 是标准化因子。输出：终分类器=t h d y ty CtH d: ( )( ) argmax log 1180 。需要说明的是，在对ATAN G 进行参数学习时，三组概率值的估计中， P(c j ) 仍与(4-6) 相同，对于P(wt | c j ) 和P(wt | c j ,ws ) 的估计则必须采用基于权重分布的估计，如(5-4)和(5-5)所示：| | ( | ) ( )1 ( | ) ( )( | ) | |1| |1| |1V N B c d D iN

21、 B c d D iP w clVsDiis j iDiit j i lt j= =+= (5-4)| | ( | ) ( )1 ( | ) ( )( | , ) | |1| |1| |1V N B B c d D iN B B c d D iP w c wlVsDiit is j iDiit is j i lt j s= =+185 = (5-5)其中，D (i) l 表示的是第l 次迭代中，第i 个文档i d 的权重（这里用l 表示迭代的次数而不用算法描述中t，主要是避免与公式中t w 表达的第t 个单词冲突），其它符号的说明同第四章。2.2 TAN 集成模型之二：EBag-TAN190

22、一般来说，Bagging 是从原始训练集合中重复Bootstrap 实例作为新的训练集，分别训练生成多个分类器，然后再将其集成的方法。它通过重新选取训练集来增加分量学习器集成的差异度，从而提高了泛化能力。对于文本分类来说，重复抽取训练子集进行训练，就意味着要对每一个训练子集都进行文本预处理，包括分词、特征选择和文档向量生成等操作，虽然Bagging 可以并行处理，但这个过程过于繁琐，因此我们不考虑直接利用Bagging 方法进行195 集成。换个角度想，Bagging 不断进行重抽样的目的无非就是学习得到多个有差异性的分类器，因此，我们只要能得到多个有差异性的分类器就可以了，而不一定要通过重抽

23、样的方法。本节我们正是利用这个思想来对TAN 进行集成的，基分类器同AdaM1-TAN，仍然选用CR-ATAN，结论生成时采用投票方法，与基于Bagging 的集成区分，我们将该模型命名为Extended Bagging TAN，简称为EBag-TAN。200 如何得到多个有差异性的分类器是EBag-TAN 所要考虑的最主要问题。在TAN 模型的基于分布的构造算法中，我们需要“通过选择一个根变量，在每条边上添加方向，将由此生成的无向树转换为有向树”，当选择不同的根变量时，在边上添加方向时可能会产生不同的方向，从而使得形成的有向树结构不同，最终导致形成的TAN 结构模型不一样。我们在实验中发现，

24、选取不同的根变量形成不同的结构在分类性能上会有或多或少的差异，而且有的205 差异还比较显著。我们尝试用选择不同的根变量带来的性能差异生成的多个分类器来进行集成，算法流程叙述如下：输入：训练文档集D；预生成的分类器个数T。1) 利用基于分布的TAN 构造算法执行到第三步，即完成最大加权生成树的构造，最大加权树用MAX_TREE 表示。210 2) 执行：For t = 1, , Ta) 初始化一个新的TAN 结构为朴素贝叶斯的结构，即NBtTAN G = G ；b) 将MAX_TREE 结构完全复制到tTAN G 中，然后在tTAN G 的最大加权树结构中随机选择一个结点作为根变量，在每条边上

25、添加方向，将无向树转换为有向树； c) 将tTAN G 替代4.6.2 节中ATAN 算法中的完整的TAN 结构TAN G ，然后利用ATAN 算法学习得到ATAN 结构模型tATAN G ，设t215 GATAN 所对应的分类器为ht ；输出：终分类器= =Tiiy CH d h d y1( ) argmax ( ( ) ) 。以上通过选择不同的根变量产生分类器间的差异来达到集成的目的，这种方法应该说只能算是EBag-TAN 的一种，诸如此类的通过一定的方法生成有差异性的分类器来进行的集成，我们都视为EBag-TAN 方法。220 2.3 TAN 集成模型之三 ：FRS-TAN与基

26、于数据的集成相比，基于特征集的集成方法的研究和应用都相对较少，通常是通过一定的策略对特征空间进行搜索，得到多个特征子集，然后学习生成多个分类器进行集成。这种方法往往复杂度比较高，特别是对于文本这种高维数据来说，显然不大实用。为降低复杂性，我们采用Ho14提出的随机子空间方法，在这种方法中，随机选择特征子集，并分225 配给学习算法，然后在这个子空间中生成分类器，最后根据分类器的正确率使用加权投票方法进行集成。用随机子空间方法对TAN 进行集成时，基分类器的选取同AdaM1-TAN 和EBag-TAN，结论生成时也采用投票方法，我们将该TAN 集成模型命名为Feature RandomSubsp

27、ace TAN，简称为FRS-TAN。FRS-TAN 的算法流程如下：230 输入：训练文档集D；预设特征子空间的特征数目M；预生成的分类器个数T。执行：For t = 1, , T1) 从特征空间中随机抽取M 个特征；2) 利用文献19中ATAN 框架中的CR-ATAN 算法从训练文档集学习ATAN 模型tATAN G ，设tATAN G 所对应的分类器为t h ；输出：终分类器= =Tiiy CH d h d y1235 ( ) argmax ( ( ) ) 。需要说明的是，在第一步的随机抽取特征子空间中，可以采用“放回取样”和“不放回取样”两种，“放回取样”允许某一个特征在该特征子集中多

28、次出现，而“不放回取样”则不允许同一特征子集中有重复的特征。我们在实验中发现，“放回取样”得到的集成分类器的性能普遍好于“不放回取样”方法，因此，本文统一采用“放回取样”选择特征子集。240 3 实验结果及分析本节我们对上文提出的三种基于TAN 的集成模型：AdaM1-TAN、EBag-TAN 和FRS-TAN 在Reuters-21578-12 和CNLP-19637-12 语料上进行文本分类实验， 并与CR-ATAN19构造的单个分类器的分类性能进行对比。其中，Reuters-21578-12 是从国际通用的英文文本分类测试集Reuters-215781中的挑选样例最多的前12 个类别所形

29、成的数据集；245 CNLP-19637-12 选取中国科学院计算技术研究所的中文自然语言处理开放平台2（ChineseNatural Language Processing Open Platform，CNLP Platform）发布的由复旦大学计算机信息1 2  与技术系国际数据库中心自然语言处理小组所提供的中文语料库中的前12 个类别所构成的文本集。语料预处理过程中，中文分词利用中科院计算所提供的ICTCLAS 工具3。特征选择采用信息增益（Information Gain，IG）方法，不做特别说明，特征数目取1000 个（当特征250 数目选择1000 时，单个分类器在这两个

30、语料上的整体分类性能最佳）。在实验中我们发现，当EBag-TAN 和FRS-TAN 模型中个体分类器的数量超过25 时，集成分类器的性能基本稳定，因此以下的实验中个体分类器的数量统一选取25。对于FRS-TAN 模型来说，涉及特征个数M 的选取问题，在Reuters-21578-12 语料上，我们把M取为600，CNLP-19637-12 语料M 取200，因为当M 分别取对应的这些值时，FRS-TAN 集255 成模型的分类性能最好。实验结果参见表1 和表2。表1 三种TAN 集成模型在Reuters-21578-12 语料上的分类性能Table 1 Comparison of three

31、ensemble learning methods based on TAN on Reuters-21578-12算法 Macro-avg（Recall）Macro-avg（Precision）Macro-avg（F1-Measure） Micro-avgAdaM1-TAN 0.781629 0.66373 0.689306 0.869078EBag-TAN 0.801581 0.795337 0.794582 0.931094FRS-TAN 0.818879 0.807126 0.810812 0.937123CR-ATAN 0.816383 0.797519 0.804459 0.933

32、678260 表2 三种TAN 集成模型在CNLP-19637-12 语料上的分类性能Table 2 Comparison of three ensemble learning methods based on TAN on CNLP-19637-12算法 Macro-avg（Recall）Macro-avg（Precision）Macro-avg（F1-Measure） Micro-avgAdaM1-TAN 0.797786 0.782053 0.765346 0.881119EBag-TAN 0.827237 0.812656 0.813187 0.897727FRS-TAN 0.8463

33、84 0.83104 0.836224 0.910839CR-ATAN 0.859237 0.789097 0.81951 0.893357从实验结果，我们可以看到：在Reuters-21578-12 语料上，AdaM1-TAN 的宏平均1 F 相对于CR-ATAN 单分类器下降了11.5%，微平均下降了6.46%；EBag-TAN 的宏平均1 F 下降了0.98%，微平均下降了0.26%；FRS-TAN 的宏平均1 265 F 上升了0.64%，微平均上升了0.35%。在CNLP-19637-12 语料上，AdaM1-TAN 的宏平均1 F 相对于CR-ATAN 单分类器下降了5.42%，微平均下降了1.22%；EBag-TAN 的宏平均1 F 下降了0.63%，而微平均上升了0.44%；FRS-TAN 的宏平均1 F 上升了1.67%，微平均上升了1.74%。总体来说，AdaM1-TAN 显示了较差的性能，EBag-TAN 与CR-ATAN 的性能相当，270 FRS-TAN 相比于CR-ATAN 单分类器性能有所提升。从语料层面上来讲，三种