一种基于S_Dbw的可变特征算子的改进随机森林算法

简琤峰，陈嘉诚，张美玉

(浙江工业大学 计算机学院，杭州 310023)

1 引 言

随机森林算法从被提出至今一直备受关注.它在处理高维数据时的精度和效率不输于神经网络和SVM算法[1].对于随机森林的各种改进方式不断被提出.这些方式主要针对三个方面，分别是数据预处理优化、算法自身构建过程优化和决策树输出组合方式优化.数据预处理在模型训练之前，包括原始样本的特征获取，如文献[2]的基于HOG的多特征融合算法，以及数据集平衡性处理，如常用的过采样法.算法自身构建过程优化一般指对节点的分裂方式进行优化，经典算法有阈值法、二分k-means等.而决策树输出组合方式改进有霍夫森林、随机组合等方式.

上述改进方式确实从各自角度较大程度地提高了随机森林的判别能力，然而它们都忽略了一个重要的事实.由于决策树自上而下使用一致的特征算子，数据集在经过若干次分裂之后，子集中的数据会趋向于相似.此时，森林的判别能力不再随着树的深度增加而增加，使得后续分裂产生的节点之间具有较大的相似性，也是所谓的过早收敛.本文从文献[3]中根据新闻话题演化对特征进行演化的算法获得启发，根据数据集的不断划分，提出允许使用上下不一致特征的可变特征随机森林.简言之，将获取原始样本的数据特征这一过程，从算法训练前的数据预处理阶段迁移到模型构建阶段，根据聚类评估指标，使用不同的特征算子进行二分聚类，从而维持节点分裂的可靠性和判别性.本文将使用S_Dbw算法[4]作为聚类评估指标，它不需要引入外部数据，且在2010年Liu Y等人的单调性、噪声、密度、组和偏态分布这五个方面测试中都非常可靠[5].

随机森林被广泛应用于各个领域，如图像中的对象检测.2015年，Xiaolong Zhu等人提出使用结构化随机森林进行手部检测[6].该算法将随机森林的输出形式变为二值遮罩，有效的利用了目标对象像素之间的结构关系，能够以较高精度进行手部检测.本文采用与Xiaolong Zhu等人相同的图像数据集和结构化方式，使用基于S_Dbw的可变特征随机森林进行手部检测，并与Xiaolong Zhu等人的算法进行比较.

2 可变特征随机森林

随机森林算法发展至今有多种改进方式，但其大体的训练过程是相似的.对于原始数据集S，采用特征算子F：S→P，得到P表示S的特征集.令P对应决策树的根节点，使用划分算法φ：P→P1，P2，则P1和P2对应两个子节点.重复分裂过程，直至满足叶子条件.显然的，当划分算法采用某一确定的算法时，选择不同的特征算子来进行数据初始化，模型最终会得到不同的判别效果.一般来说，会选择能使数据集具有尽可能大的离散度的算子.

然而，即使当前数据集具有较大的离散程度，在经过若干次划分后，其生成的子集内部数据的总体差异性会逐渐降低.这样，后续的数据划分很难具有合理性.另外，对于图像数据而言，即使不进行数据集的划分，在使用不同的特征算子时同样会使得数据呈现不同的离散程度.Li C等人[7]对于同一组图像分别使用两种不同特征算子，再使用t-SNE算法可视化对比两种情况下数据的离散程度.而在图1中，原始数据集包含4组图像，分别为r1有噪声(范围在±25之间)，r2无噪声，b1有噪声，b2无噪声.若只采用梯度特征，可以将数据集分为{r1，b1}和{r2，b2}.若只采用色彩特征，可以将数据分为{r1，r2}和{b1，b2}.若先采用梯度，再采用色彩，则决策树可以“良好”生长到两层.

图1 使用不同特征时的划分方式Fig.1 Two criterions for image set split

2.1 可变特征随机森林的本质

在进行决策树训练的过程中，需要对数据集进行多次划分.那么如果每一次划分都使用当前最佳的特征算子从原始数据集中获取特征，那么最终获得的决策树也可以具有更强的判别能力.这也是本文算法的本质.

对于集合F={fi}，其元素fi为特征算子.对于数据集S，disc(f，S)表示特征f在S中的判别能力，那么对于在第k次分裂时，使用特征fk=arg maxf∈Fdisc(f，S).同理，在第k+1次分裂时使用的特征为fk+1.本文的不定特征就是允许fk≠fk+1.

传统随机森林在进行节点分裂时，有时会随机或按照某些条件挑选当前特征数据集的若干属性作为分裂的数据参考.这一过程事实上也可以看做重新从原始数据中以新的特征算子获取数据特征.所以，它也是可变特征这个概念的一个子集.

2.2 可变特征的易扩展性

可变特征具有易扩展的特点.在很多研究工作中，多特征被视为增强算法效果的重要方法.但对多特征的使用方式通常有简单线性加权组合[8-11]、自适应加权[12]等.其中与本文算法最为相似的是自适应加权组合特征.然而，当参与组合的特征种类较多时，组合特征会难以避免的出现维数过大的问题.而可变特征只需扩展备选特征算子库，并从中选择当前最优，对于维数产生的影响并不会过大.

3 本文算法

本文算法对于随机森林进行改进的着重点在于使用上下不一致的特征，即可变特征.那么，如何从备选特征算子库中选取当前最佳算子，是应用可变特征的关键.在传统的改进随机随机森林算法中，部分经典算法使用二分聚类的方式进行数据集的划分.据此，本文算法使用二分k-means进行节点分裂，并使用S_Dbw算法对每次二分k-means的结果进行评估，从而选取最佳算子.S_Dbw的计算公式[4]如下：

S_Dbw(c)=Scat(c)+Dens_bw(c)

(1)

(2)

(3)

在本文算法中，随机森林中的每棵决策树的训练过程并无差异，所以将以一棵决策树的训练过程代表整个随机森林的训练过程.本文算法的训练步骤如下：

输入： 原始样本数据集S，特征算子库F={fi}，非叶节点数据集最小尺寸Gmin.

输出： 决策树Tree={Branchi，Leafi}，Branchi表示非叶节点，Leafi表示叶节点.

Step1.若S的尺寸小于Gmin，则生成一个叶节点Leaf，加入Tree，不进入其它步骤; 否则，生成一个非叶结点Branch;

Step2.使用F对S进行处理，即F(S)={Pi}，集合Pi表示fi(S);

Step3.使用二分k-means算法对Pi进行划分，得到子集Pi1和Pi2;

Step4.根据公式(1)(2)(3)评估Setp3中得到的每对子集，选择最优划分，即

f*=arg maxfigetS_Dbw(Pi1，Pi2);

Step5.分别以f*(S)对应的S1和S2为输入，进入Step1，生成当前节点的子节点;

4 随机森林在图像检测中的结构化方式

传统随机森林用于图像中对象检测和分割的本质，是建立从单个像素p到单个类别标签yp∈{0，1}的映射关系.它

图2 随机森林结构化方式Fig.2 Structured forest

的输入形式是一个特征向量，通常从以像素p为中心的邻域图块中计算得到.它的输出形式为类别标签的概率分布P(y|xp)，其中y∈{0，1}.

而在结构化随机森林中，输出形式被变为P(x，y|xp)，表示图块xp中坐标为(x，y)的像素属于目标对象的概率.其本质是建立从图块到二值图像的映射关系.图2(出自文献[6])很好展示了两者之间的差别.

5 实 验

本文将在图像数据集中，对基于S_Dbw的可变特征随机森林算法的结构化形式进行测试，并将结果与Xiaolong Zhu等人的结构化随机森林算法进行比较.本文使用的数据集为GTEA(Geogia Tech Ego-centric Activity dataset)和EDSH1数据集.前者有Coffee、Tea和Peanut这三个子集，几乎不包含摄像头自身运动.而后者有EDSH1和EDSH2两个子集，存在较多光照条件的改变和摄像头自身的运动.对于实验的结果，根据不同的阈值，求对应的精度(P)和召回率(R)，并求得相应的F值.最终取F值的最大值.F值的计算公式如下：

图3 实验样例Fig.3 Samples of experiments

(4)

5.1 实验1

使用GTEA数据集进行实验，即以Coffee数据作为训练样本集，以Tea和Peanut数据作为测试样本集.首先将全部样本降采样为180×320的图像，再设置图块尺寸为16×16.再文献[6]中，当算法只使用Color和Gradient组合特征时，检测效果明显弱于使用Color、Gradient和Texture(指像素差异)三者组合成的特征.而在表1所示的实验结果中，在同样包含16棵决策树的情况下，三中情况的检测结果不相上下.在本文算法只使用Color和Gradient特征的情况下，与文献[6]使用Color、Gradient和Texture组合特征相比，甚至有微弱的优势.这证明了本文算法确实可以在每一次分裂只使用单一特征的情况下，达到甚至超过组合特征的效果.在图3中给出了实验中若干个样本及相应的检测结果.

表1 在GTEA上进行对比Table 1 Comparcomparation in GTEA dataset

5.2 实验2

使用EDSH数据集进行实验，即以EDSH1作为训练样本集，以EDSH2作为测试样本集.同样将全部样本降采样为180×320的图像，设置图块尺寸为16×16.实验结果如表2所示，b项仍然略优于a项，这证明在样本存在光照条件变化的情况下，本文算法可以降低特征对于光照变化的敏感度.

表2 在EDSH上进行对比Table 2 Comparation in EDSH dataset

6 结 语

本文提出在随机森林中允许上下使用不一样的特征算子，而不仅仅只从统一特征向量中提取不同属性进行节点分裂.此外，本文使用本文算法的结构化形式，并进行了手部检测的实验.实验证明算法是有效的.但在训练过程中，对于当前最佳特征算子的选取需要耗费较多的时间.这一问题在算子库规模较大时会变得更加明显，不能很好的满足可变特征的易于扩展的特点.后续研究将围绕如何以更高效的方式选取最佳特征算子展开.

[1] Caruana R，Karampatziakis N，Yessenalina A.An empirical evalu-ation of supervised learning in high dimensions[C].International Conference on Machine Learning，ACM，San Diego，California，USA，2008：96-103.

[2] Guo Jin-xin，Chen Wei.Face recognition based on HOG multi-feature fusion and random forest[J].Computer Science，2013，40(10)：279-282.

[3] Zhao Xu-jian，Yang Chun-ming，Li Bo，et al.A topic evolution mining algorithm of news text based on feature evolving[J].Chinese Journal of Computers，2014，37(4)：819-832.

[4] Halkidi M，Vazirgiannis M.Clustering validity assessment： finding the optimal partitioning of a data set[C].Proceedings of Institute of Electrical and Electronics Engineers International Conference on Data Mining，San Jose，California，USA，2001：187-194.

[5] Liu Y，Li Z，Xiong H，et al.Understanding of internal clustering validation measures[C].Proceedings of Institute of Electrical and Electronics Engineers International Conference on Data Mining，IEEE，Sydney，Australia，2010：911-916.

[6] Zhu X，Jia X，Wong K Y K.Structured forests for pixel-level hand detection and hand part labelling[J].Computer Vision & Image Understanding，2015，141(C)：95-107.

[7] Li C，Kitani K M.Pixel-level hand detection in ego-centric videos[C].Proceedings of Institute of Electrical and Electronics Engineers Conference on Computer Vision and Pattern Recognition，Portland，Oregon，USA，2013：3570-3577.

[8] Yang Jian，Yang Jing-yu，Wang Zheng-qun，et al.A novel feature extraction method based on feature integration[J].Chinese Journal of Computers，2002，25(6)：570-575.

[9] Mei K，Xu L，Li B，et al.A real-time hand detection system based on multi-feature[J].Neurocomputing，2015，158(C)：184-193.

[10] Wan Yuan，Li Huan-huan，Wu Ke-feng，et al.Fusion with layered features of LBP and HOG for face recognition[J].Journal of Computer-Aided Design & Computer Graphics，2015，27(4)：640-650.

[11] Zhu Yu-lian，Chen Song-can.Sub-image method based on feature sampling and feature fusion for face recognition[J].Journal of Software，2012，23(12)：3209-3220.

[12] Xiang Ru-xi，Li Jian-wei.Particle filter tracking method of multiple features based adaptive fusion[J].Journal of Computer-Aided Design & Computer Graphics，2012，24(1)：97-103.

附中文参考文献：

[2] 郭金鑫，陈 玮.基于HOG多特征融合与随机森林的人脸识别[J].计算机科学，2013，40(10)：279-282.

[3] 赵旭剑，杨春明，李 波，等.一种基于特征演变的新闻话题演化挖掘方法[J].计算机学报，2014，37(4)：819-832.

[8] 杨 健，杨静宇，王正群，等.一种组合特征抽取的新方法[J].计算机学报，2002，25(6)：570-575.

[10] 万 源，李欢欢，吴克风，等.LBP和HOG的分层特征融合的人脸识别[J].计算机辅助设计与图形学学报，2015，27(4)：640-650.

[11] 朱玉莲，陈松灿.特征采样和特征融合的子图像人脸识别方法[J].软件学报，2012，23(12)：3209-3220.

[12] 相入喜，李见为.多特征自适应融合的例子滤波跟踪算法[J].计算机辅助设计与图形学学报，2012，24(1)：97-103.

1http：//www.cs.cmu.edu