基于增益率与堆叠自编码器的并行随机森林优化方法

1.本发明涉及属于大数据挖掘领域，特别是涉及一种基于增益率与堆叠自编码器的并行随机森林优化方法。


背景技术：

2.随机森林算法是一种以决策树为基分类器的集成学习方法，通过对数据集bootstrap抽样得到的样本进行决策树建模后，构建一个包含多棵不相关决策树的分类器，并统计所有树的分类结果来得到最终分类结果。相比于其他分类算法而言，具有分类效果好，鲁棒性强以及运算速度快等特点。因此近些年已广泛应用于环境监控，滑坡预测，网络防御，医学预测，故障检测，生物信息等领域。
3.随着社交媒体、互联网、云计算等信息科学技术的快速发展，各行业积累数据的速度加快，使数据的体量与种类在快速增长并带来了大数据。大数据与传统数据相比，具有4v特性，volume(数量大)、variety(种类多)、velocity(速度快)、value(价值密度低)，这使得大数据下随机森林算法所需的时间复杂度较高，内存容量也较多，同时，通过提升硬件水平来满足现阶段大数据处理需求的方向仍发展缓慢。因此，如何优化大数据下的随机森林算法成为当前研究的重要方向。
4.近年来，mapreduce并行处理模型由于具有操作简易、扩展性强、成本低廉等优点得到了许多关注，通过与mapreduce框架结合的方式，一些优化的并行随机森林模型已成功在大数据处理领域实现。其中，lakshmanaprabu s k等人提出了结合交叉率与蜻蜓算法的随机森林算法idarf算法，该算法使用数学方式描述蜻蜓五个静态群体行为和动态群行为，在使用评估函数对单个特征进行评估后，利用交叉率来产生新个体，并不断迭代逼近最优值来选择合适的特征。idarf在运行时间上和分类效果都要比传统并行随机森林更好。但该算法依然有以下三点问题：数据集中仍有大量的冗余与不相关特征数量，不能有效保证特征子空间信息含量，并行时节点负载不均等问题。


技术实现要素：

5.本发明旨在至少解决现有技术中存在的技术问题，特别创新地提出了一种基于增益率与堆叠自编码器的并行随机森林优化方法。
6.为了实现本发明的上述目的，本发明提供了一种基于增益率与堆叠自编码器的并行随机森林优化方法，包括：
7.s1，对训练数据集进行特征降维：先对各特征计算特征依赖度获得候选特征集，再对候选特征集的各特征使用冗余过滤函数过滤候选特征集之外的冗余与不相关特征，并使用堆叠自编码器对数据集进行特征提取得到降维数据集，有效减少了冗余以及不相关特征数；
8.s2，子空间选择：计算由降维数据集初始化生成的特征子空间的信息含量后判断是否满足设定阈值，并对不满足设定阈值的特征子空间进行重新选取，有效保证了特征子
空间的信息含量；
9.s3，并行构建随机森林：计算各节点分配后的节点数据量以衡量节点负载后，通过节点分配函数选择负载较小的节点分配reduce任务，有效平衡了节点负载并提高并行化效率；
10.s4，将待测数据输入随机森林，得到最终分类结果。
11.进一步地，所述s1包括：
12.s1-1，特征选择：用于减少数据集中的冗余与不相关特征数；
13.1)获取平均信息增益：计算每个特征的信息增益igi，然后根据每个特征增益值的概率计算平均信息增益aig；
14.2)过滤不相关特征：根据aig得到每个特征的增益评估系数gi并计算每个特征的增益率gri，然后根据特征依赖度fd来去除不相关的特征；
15.3)过滤冗余特征：通过冗余过滤函数rff对集合f中对优势特征在类别分类时有较大影响的特征进行过滤，然后重新组合获得优化后的特征集；
16.s1-2，特征提取：对特征选择后的数据集进一步提取优化；
17.1)初始权重矩阵与特征矩阵重构：使用堆叠自编码器获取初始权重矩阵和偏置，通过反向传播调整权重矩阵以及偏置重构特征矩阵，并使用softmax分类器进行分类；
18.2)信息损失量与分类误差估计：采用l2范数对信息损失量与分类误差进行估计；
19.3)参数集优化：为了使信息损失量和分类误差总和达到最小，提出了参数优化函数对参数集进行优化。
20.进一步地，所述平均信息增益aig包括：
[0021][0022]
其中，igi表示第i个特征的信息增益；
[0023]
pi为特征数的倒数；
[0024]
q为特征总个数。
[0025]
进一步地，所述特征依赖度fd包括：
[0026]
fd(di,l)＝gi×
gr(di,l)
[0027][0028]
其中fd(di,l)为在标签集l下特征di的特征依赖度；
[0029]di
表示第i个特征；
[0030]gi
为增益系数；
[0031]
gr(di,l)为标签集l下特征di的增益率；
[0032]
igi为特征的信息增益；
[0033]
aig为平均信息增益；
[0034]
k为去除不相关特征后的特征总个数。
[0035]
进一步地，所述冗余过滤函数rff包括：
[0036]
rff(d
α
,d
β
)＝fd(l,d
α
)-gr(d
α
,d
β
)
[0037]
其中fd(l,d
α
)为标签集l下优势特征d
α
的特征依赖度；
[0038]
gr(d
α
,d
β
)表示特征dj关于特征dk的增益率；
[0039]dα
表示第α个特征；
[0040]dβ
表示第β个特征。
[0041]
进一步地，所述初始权重矩阵与特征矩阵重构包括：
[0042]
首先，设置初始堆叠自动编码器含有一层输入层，一层输出层以及两层隐藏层，其中两层隐藏层的节点个数分别为h，h
′
，然后输入特征矩阵d
′
获取初始的权重矩阵，其中，输入特征矩阵到第一层隐藏层的权重矩阵为w1，偏置为b1，第一层隐藏层到第二层隐藏层的权重矩阵为w2，偏置为b2，第二层隐藏层到输出层的权重矩阵为w3，偏置为b3，则编码与解码过程表示如下：
[0043]
m1＝σ(d
′
w1+b1)
[0044]
m2＝σ(m1w2+b2)
[0045]d″
＝σ(m2w3+b3)
[0046][0047]
其中σ(
·
)为激活函数；
[0048]d″
为重构后的特征矩阵，
[0049]
m1为第一层隐藏层的中间矩阵，
[0050]
m2为第二层隐藏层的中间矩阵；
[0051]
最后，将m2与标签集l合并后得到特征提取后的数据集db
″
，并使用softmax分类器对数据集db
″
进行分类，获得关于m2的分类矩阵c，则可得出m2的预测标签f(m2)为：
[0052]
f(m2)＝m2c
[0053]
f(m2)＝σ(m1w2+b2)c
[0054]
其中f(m2)为重构矩阵d
″
通过softmax分类预测得到的预测标签集。
[0055]
进一步地，所述分类误差包括：
[0056]
l
error
＝||l,f(m2)||2[0057]
其中l
error
为分类误差；
[0058]
l为特征矩阵d
′
的标签集；
[0059]
f(m2)为重构矩阵d
″
通过softmax分类预测得到的预测标签集；
[0060]
||
·
||2表示l2范数。
[0061]
进一步地，所述参数优化函数包括：
[0062]
p(θ,c)＝j(θ)+λl
error
[0063][0064]
其中，p(θ,c)为参数优化函数；
[0065]
j(θ)为信息损失量；
[0066]
λ为分类误差的权重；
[0067]
l
error
为分类误差；
[0068]
s表示特征维数；
[0069]di
′
为第i个重构特征；
[0070]di
为第i个原特征；
[0071]
l为标签集；
[0072]
f(m2)为预测标签集；
[0073]
||
·
||2表示l2范数。
[0074]
进一步地，所述s2包括以下步骤：
[0075]
s2-1，对特征集m
*
＝[d1,d2,
····
,dh′
]进行无放回抽样得到s个特征子集(γ1,γ2,
···
,γs)，然后形成包含s个特征子集的特征子集集合γ；其中dh′
表示第h
′
个特征，h
′
表示第二层隐藏层的节点个数，γs表示第s个特征子集；
[0076]
s2-2，采用子空间信息度量ic来衡量特征子集的信息量，然后根据每个子集γ
l
包含的特征变量计算ic；
[0077][0078]
其中，
[0079]
gr
lj
表示第l个特征子集中第j个特征；
[0080]
sic
l
表示第l个特征子集包含的特征信息量；
[0081]
gri表示表示第i个特征子集；
[0082]
l＝1,2,
···
,s为第l个特征子集的索引；
[0083]
i＝1,2,
···
,h
′
为第i个特征；
[0084]
s2-3，对特征子集按照ic值降序排序，并设置阈值τ移除信息量比例较低的特征子集，然后重新按s2-1，s2-2获取子集，直到获得满足阈值τ的s个特征子集。
[0085]
s2-4，对满足阈值τ的s个特征子集都进行h
′
次有放回的bootstrap采样，然后获得s个用于构建决策树的特征子集τ
l
(l＝1,2,
···
,s)。
[0086]
进一步地，所述s3包括以下步骤：
[0087]
s3-1，节点分配：首先统计map过程各个key出现的次数，然后计算各个key在各节点上的标准差得到键标准差集合sdk，最后提出了节点配分函数ndf按集合sdk中key的顺序计算ndf值，并把key分配到ndf值最小的节点；
[0088]
s3-2，构建随机森林：首先调用map函数将s个特征子集作为训练集构建s个子森林，然后利用子森林对数据集db
″
进行预测后，将所有子森林进行合并获得随机森林模型，最后将各子森林预测获得的结果分配到reducer节点进行合并获得全局分类结果，并与标签集l比较后得到模型的准确度。
[0089]
11、根据权利要求1所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述s3-2包括：
[0090]
1)首先将对特征降维后的特征集使用子空间信息度量策略，得到s个特征子集作为训练集；然后调用map函数以键值对＜key
t
,value
t
＞形式构建决策树(key
t
为决策树编号，value
t
为决策树模型)，待全部mapper节点执行完成后合并成s个子森林；最后使用mapper节点中的子森林对数据集db
″
进行预测并形成新的键值对＜key
′
,value
′
＞(key
′
表示样本的编号以及对应类别的数组，value
′
表示出现的键值对次数)后合并相同key
′
值的
键值对。
[0091]
2)首先调用map函数以键值对＜fkeyf,valuef＞的形式构建全局随机森林(fkeyf为子森林编号，valuef为子森林模型)；然后待全部mapper节点运行完成后，对所有子森林进行合并获得随机森林模型；最后将mapper节点中预测获得的键值对分配到对应的reducer节点进行合并，获得全局分类结果并与标签l比较后得到模型的准确度。
[0092]
进一步地，所述节点分配函数包括：
[0093][0094]
其中ndf表示节点分配函数；
[0095]
z为节点总数；
[0096]
nodedataj为节点j上的数据量；
[0097]
key
x
分到某一节点后各个节点上的平均数据量为
[0098]
综上所述，由于采用了上述技术方案，本发明在分类效果和并行效率上都有显著的提升。
[0099]
本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0100]
本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：
[0101]
图1是本发明的并行构建随机森林示意图。
[0102]
图2是四种算法运行加速比比较图。
[0103]
图3是四种算法运行加速比比较图。
具体实施方式
[0104]
下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。
[0105]
本发明提出一种基于增益率与堆叠自编码器的并行随机森林优化方法，具体实施例如下，包括以下步骤：
[0106]
s1，对图像训练数据集进行特征降维：先对各特征计算特征依赖度获得候选特征集，再对候选特征集的各特征使用冗余过滤函数过滤候选特征集之外的冗余与不相关特征，并使用堆叠自编码器对数据集进行特征提取得到降维图像数据集；
[0107]
s2，子空间选择：计算由降维图像数据集初始化生成的特征子空间的信息含量后判断是否满足设定阈值，并对不满足设定阈值的特征子空间进行重新选取；
[0108]
s3，并行构建随机森林：计算各节点分配后的节点数据量以衡量节点负载后，通过节点分配函数选择负载较小的节点分配reduce任务；
[0109]
s4，将待测图像数据输入随机森林，得到最终分类结果。
[0110]
本发明基于mapreduce编程模型的优点，提出了一种基于增益率与堆叠自编码器的并行随机森林优化方法——prfgrsae。首先，该算法在特征降维阶段提出了一种基于增益率和堆叠自编码器的降维策略drgrsae(dimension reduction based on gain ratio and stacked auto encoders)，对各特征计算特征依赖度后获得候选特征集，再对候选特征集的各特征使用冗余过滤函数过滤候选特征集之外的冗余与不相关特征，并使用堆叠自编码器对数据集进行特征提取得到降维数据集，有效减少了冗余以及不相关特征数；其次，在特征子空间选择阶段提出了基于blb(bootstrap of little bag)抽样方法与增益率的子空间信息度量策略siebg(subspace information evaluation based on bootstrap of little bag and gain ratio)，计算由降维数据集初始化生成的特征子空间的信息含量后判断是否满足设定阈值，并对不满足设定阈值的特征子空间进行重新选取，有效保证了特征子空间的信息含量；最后，提出mapreduce模型优化策略snd(strategy of node distribution)，计算各节点分配后的节点数据量以衡量节点负载后，通过节点分配函数选择负载较小的节点分配reduce任务，有效平衡了节点负载并提高并行化效率。本发明提出的算法无论是在运行效率上还是分类精确度上都有明显的提升。此外通过该方法进行数据挖掘，能够在生物学，医学，目标检测上提供巨大的帮助。
[0111]
1.特征降维
[0112]
目前在大数据环境下的并行随机森林算法中，由于数据的维度越来越高，导致在获取特征子集时会存在特征子集的冗余以及不相关特征数过多的问题，故提出了基于增益率与堆叠自编码器的降维策略drgrsae来减少大数据环境下的冗余以及不相关特征数。该策略主要过程如下：(1)特征选择过程：首先根据平均增益获得每个特征的增益评估系数，然后提出计算特征依赖度来并行删除不相关特征，最后根据冗余特征函数删除冗余特征；(2)特征提取过程：首先根据堆叠自编码器构建特征重构矩阵，然后使用softmax获得分类矩阵并利用l2范数估计重构误差及分类误差，最后对重构过程的参数进行优化后得到特征提取后的训练数据。
[0113]
1.1特征选择
[0114]
在目前的大数据环境下，为了减少数据集中的冗余与不相关特征数，需要对数据集进行特征选择。特征选择过程如下：1)获取平均信息增益：首先计算每个特征的信息增益igi，然后根据每个特征增益值的概率计算平均信息增益aig；2)过滤不相关特征：首先根据aig得到每个特征的增益评估系数gi并计算每个特征的增益率gri，然后提出了特征依赖度fd来去除不相关的特征；3)过滤冗余特征：首先提出了冗余过滤函数rff对集合f中对优势特征在类别分类时有较大影响的特征进行过滤，然后重新组合获得优化后的特征集。给定特征集其中dq表示第q组特征，表示p
×
q维的实数；类别矩阵表示特征矩阵d对应的类别，则有：
[0115]
1)获取平均信息增益
[0116]
在给定的特征集d后，可通过并行计算得到各特征的信息增益，再计算得到平均信息增益。平均信息增益获取过程如下：首先根据hadoop的默认文件块策略将特征集d划分成大小一致的文件块；然后调用map将文件块作为输入数据，统计出每个特征的信息增益igi(i＝1,2,
···
,q)；最后，提出了平均信息增益aig，通过统计igi可得每个特征信息增益值出现的概率并计算获得平均信息增益，以便后续计算特征依赖度过滤不相关特征。
[0117]
定理1(平均信息增益aig)：已知每个特征的信息增益为igi，每个特征信息增益的概率为pi，则平均信息增益aig可如下计算：
[0118][0119]
其中，i＝1,2,
···
,q代表特征个数。
[0120]
证明：已知特征集d以及特征集d中每个特征的信息增益为igi，且pi可知为特征数的倒数，由定义4辛钦大数定律可知，在高维数据中，维数q较高，当q充分大时，有算术平均值且即算术平均值以接近1的概率落在真实平均值μ的极小领域内，此时(ε为一个极小的值)，而μ为ig的期望可表示为可得平均信息增益证毕。其中p(
·
)表示概率，e(
·
)表示期望，n为元素个数，xi为每个元素值。
[0121]
2)过滤不相关特征
[0122]
在得到平均信息增益后，可对增益率改进获得特征依赖度来过滤不相关特征。过滤不相关特征过程如下：首先根据aig得到每个特征的增益评估系数gi并计算各特征的增益率gri；然后提出特征依赖度fd作为指标来过滤不相关特征，对fd＞0的特征以键值对《fi,fdi》()的形式统计各特征组合后进行降序排列，其中fi为第i个特征的特征名称；最后得到特征依赖度集合f＝{《f1,fd1》,《f2,fd2》，
······
,《fk,fdk》}(k为过滤后的特征维数且1＜k≤q)并将前μ个的特征作为优势特征。
[0123]
定理2(特征依赖度fd)：已知在类别l下特征di的增益率为gr(di,l)，且对应的增益系数为gi，平均信息增益为aig，则在类别l下特征di的特征依赖度fd(di,l)可如下计算：
[0124]
fd(di,l)＝gi×
gr(di,l)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(12)
[0125][0126]
其中，i＝1,2,
···
,k为特征个数；j＝1,2,
···
,q，为类别取值的个数。
[0127]
证明：由于增益率倾向于选择取值较少的特征，若要选取合适的特征作为优势特征，需加入增益系数gi来过滤。而取值较少的特征的信息增益igi低于平均水平aig，即ig
i-aig≤0，此时可令g＝0，使fd＝0，那么取值较少的特征在排序时会处于集合f靠后位置，不会被选为优势特征；而ig
i-aig＞0时，令g＝1，并使fd＝gr，则取值适中的特征可以通过排序被选为优势特征。因此，特征依赖度fd可表示为fd(di,l)＝gi×
gr(di,l)，证毕。
[0128]
3)过滤冗余特征
[0129]
在减少了不相关特征数后，为了减少特征集中的冗余特征数，需要再过滤冗余特征。过滤冗余特征过程如下：首先，提出了冗余过滤函数rff对集合f进行过滤，减少了集合中对优势特征在类别分类时有较大影响的冗余特征数；然后重新组合获得优化后的特征集(s为特征选择后的特征维数且1＜s≤k)，最后将特征矩阵d
′
与标签集(类别)l进行列合并后得到的数据集db
′
传入到特征提取阶段。
[0130]
定理3(冗余过滤函数rff)：已知特征对(d
α
,d
β
)的信息增益为ig(d
α
,d
β
)，其中优势特征d
α
是在集合f中有索引的，d
β
是由{d
′‑
f}集合抽取的。优势特征d
α
的特征依赖度为fd(l,d
α
)，则特征d
β
的冗余过滤函数可如下计算：
[0131]
rff(d
α
,d
β
)＝fd(l,d
α
)-gr(d
α
,d
β
)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(14)
[0132]
其中gr(d
α
,d
β
)＝ig(d
α
,d
β
)/si(d
β
)，c表示特征d
β
的取值个数，p(
·
)表示概率，gr(d
α
,d
β
)表示特征d
α
关于特征d
β
的增益率，ig(d
α
,d
β
)表示特征对(d
α
,d
β
)的信息增益。
[0133]
证明：特征依赖度(l,d
α
)本质上是增益率，用以衡量优势特征对类别分类的作用大小，而(d
α
,d
β
)用以衡量特征d
β
与优势特征d
α
的相关性。当gr(d
α
,d
β
)≤fd(l,d
α
)，rff(d
α
,d
β
)≥0，特征对(d
α
,d
β
)的相关性不会影响优势特征di对分类的作用，不构成冗余，则保留特征d
α
；反之，即gr(d
α
,d
β
)＞fd(l,d
α
)，rff(d
α
,d
β
)＜0，特征对(d
α
,d
β
)的相关性会影响优势特征d
α
对分类的作用，d
β
为冗余特征，则剔除特征d
β
，因此，可用特征d
β
的冗余过滤函数rff(d
α
,d
β
)＝fd(l,d
α
)-gr(d
α
,d
β
)来过滤冗余特征，证毕。
[0134]
1.2特征提取
[0135]
在特征提取阶段，对特征选择后的数据集进一步提取优化，过程如下：1)初始权重矩阵与特征矩阵重构：使用堆叠自编码器获取初始权重矩阵和偏置，通过反向传播调整权重矩阵以及偏置重构特征矩阵，并使用softmax分类器进行分类；2)信息损失量与分类误差估计：采用l2范数对信息损失量与分类误差进行估计；3)参数集优化：为了使信息损失量和分类误差总和达到最小，提出了参数优化函数p(θ,c)对参数集进行优化，其中θ＝{w1,w2,w3,b1,b2,b3}，c为分类矩阵。特征提取的具体过程如下：
[0136]
1)初始权重矩阵与特征矩阵重构
[0137]
对于特征选择后得到的特征矩阵d
′
与数据集db
′
，可以利用堆叠自编码器来进行初始权重矩阵的获取以及利用重构矩阵中的中间矩阵进行降维。过程如下：首先，设置初始堆叠自动编码器含有一层输入层，一层输出层以及两层隐藏层，其中两层隐藏层的节点个数分别为h，h
′
，然后输入特征矩阵d
′
获取初始的权重矩阵，其中，输入特征矩阵到第一层隐藏层的权重矩阵为其中表示s
×
h维的实数；偏置为第一层隐藏层到第二层隐藏层的权重矩阵为偏置为第二层隐藏层到输出层的权重矩阵为偏置为则编码与解码过程表示如下：
[0138]
m1＝σ(d
′
w1+b1)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(15)
[0139]
m2＝σ(m1w2+b2)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(16)
[0140]d″
＝σ(m2w3+b3)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(17)
[0141][0142]
其中σ(
·
)为激活函数，为重构后的特征矩阵，为第一层隐藏层的中间矩阵，为第二层隐藏层的中间矩阵。最后，将m2与标签集l合并后得到特征提取后的数据集db
″
，并使用softmax分类器对数据集db
″
进行分类，获得关于m2的分类矩阵则可得出m2的预测标签f(m2)为：
[0143]
f(m2)＝m2c
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(19)
[0144][0145]
2)信息损失量与分类误差估计
[0146]
在获得分类矩阵与重构矩阵后，为了衡量重构矩阵是否能尽可能与原矩阵相等，需要对重构后的信息损失量及分类误差作估计，根据分类矩阵c以及重构矩阵d
″
，利用l-2范数提出信息损失量j(θ)与分类误差l
error
进行估计。
[0147]
定理4(信息损失量j(θ))：已知原特征di∈d
′
，重构特征di′
∈d
″
，则信息损失量j(θ)可如下计算：
[0148][0149]
证明：由于堆叠自动编码器的转换过程是有损的，这个过程矩阵d
′
通过权重矩阵w1，w2，w3转换成d
″
，即d
″
＝σ(σ2d
′
w1w2+σb1w2+σb2)w3+b3≈d
′
，因此获得的重构矩阵d
″
的特征di′
与原特征矩阵d
′
的特征di存在着信息差异，而由定义3可知l2范数可以计算两矩阵中各元素的欧式距离来反映转换产生的信息损失量，因此，矩阵d
′
与重构矩阵d
″
的信息损失量可表示为证毕。
[0150]
定理5(分类误差l
error
)：已知特征矩阵d
′
的标签集为l，重构矩阵d
″
通过softmax分类预测得到的预测标签集为f(m2)，则分类误差l
error
可如下计算：
[0151]
l
error
＝||l,f(m2)||2ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(22)
[0152]
证明：由于矩阵d
′
通过权重矩阵w1，w2，w3转换成重构特征矩阵d
″
的过程是有损的，在对重构特征矩阵d
″
进行分类时，得到的预测标签集为f(m2)＝σ(m1w2+b2)c与特征矩阵d
′
的标签集l存在信息差异，而由定义3可知l2范数可以计算两矩阵中各元素的欧式距离来反映转换产生的信息损失量，因此，分类误差l
error
可表示为||l,f(m2)||2，证毕。
[0153]
3)参数集优化
[0154]
为了使重构矩阵尽可能与原矩阵相等，需要获取最优权重矩阵以及偏置，即需要对j(θ)，l
error
进行最小化，令参数集θ＝{w1,w2,w3,b1,b2,b3}，则可以提出关于参数w1,w2,w3,b1,b2,b3,c的参数优化函数p(θ,c)来对参数进行优化。
[0155]
定理6(参数优化函数p(θ,c))：已知特征矩阵d
′
，标签集l，通过θ参数集与分类矩阵c可得到重构特征矩阵d
″
与预测标签集f(m2)，则得参数优化函数p(θ,c)可如下计算：
[0156]
p(θ,c)＝j(θ)+λl
error
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(23)
[0157][0158]
其中，j(θ)为信息损失量，λ为分类误差的权重，原特征di∈d
′
，重构特征di′
∈d
″
，l为标签集，f(m2)为预测标签集，s表示特征维数。
[0159]
证明：要对p(θ,c)求最优解时，本质上是对重构误差与分类误差之和求最小值，而分类误差是受到重构误差影响的。首先，需要先将分类矩阵c先视作常数，然后利用梯度下降法对参数集θ各个元素求解，最后把各元素最优解代入求解分类矩阵c。对于p(θ,c)，可得到关于wi(i＝1,2,3)的梯度为令可以得到局部最优权重矩阵ωi，即对于都有p(θi,c)≥p(θ
ω
,c)。同理，将求得的各个参数最优解代入p(θ,c)得到p(θ
ω
,c)，此时关于分类矩阵c的梯度为令可求得局部最优分类矩阵c
′
，即对于都有p(θ
ω
,c)≥p(θ
ω
,c
′
)，即得到了使p(θ,c)达到最小的参数集θ
ω
与分类矩阵c
′
，即特征提取过程损失最小，故参数优化函数能够达到最优，证毕。
[0160]
为了得到全局优化参数，需要将定理6中获得的局部最优权重矩阵ωi以及局部最优分类矩阵c
′
代入参数优化函数p(θ,c)进行迭代求解至收敛，即可获取全局最优分类矩阵c
*
和全局最优权重矩阵w
i*
，此时代入(15)(16)式即可获得经特征提取后的特征矩阵与标签l进行列合并后获得特征提取后的数据集db
″
。
[0161]
2.子空间选择
[0162]
目前在大数据环境下的并行随机森林算法中，构建子空间时通常使用随机选择或均匀选择的方式，这些方式都没有很好考虑特征的信息量高低，导致构建的特征子空间存在特征对信息含量不能充分表达原数据的问题。故本文提出了结合blb抽样方法与增益率的子空间信息度量策略siebg，用于度量子空间信息量，通过给定信息量阈值来选取特征子空间，以提高子空间信息量。子空间选择过程如下：
[0163]
(1)首先对特征集进行无放回抽样得到s个特征子集(γ1,γ2,
···
,γs)(每个特征子集含有b个特征(b＜＜h
′
,s
×
b＜h
′
))，然后形成包含s个特征子集的特征子集集合γ。其中表示p
×h′
维的实数，h
′
表示第二层隐藏层的节点个数。
[0164]
(2)首先提出了子空间信息度量ic来衡量特征子集的信息量，然后根据每个子集γ
l
(l＝1,2,
···
,s)包含的特征变量计算ic。
[0165]
定理7(子空间信息度量ic)：已知特征子集γ
l
的信息量为sic
l
，特征集m
*
的信息量为则特征子集γ
l
的子空间信息ic
l
可如下计算：
[0166][0167]
其中，gr
lj
表示第l个特征子集中第j个特征，l＝1,2,
···
,s为第l个特征子集的索引，i＝1,2,
···
,h
′
为第i个特征。
[0168]
证明：令特征集m
*
的总信息量为表示m
*
中h
′
个特征的信息含量总和；同理可得每个特征子集信息含量sic，用来表示特征子集γ
l
中b个特征的信息含量总和，由于特征集的总信息含量熵值h(m
*
)是不变的，所以，通过评估每个特征子集的信息含量sic能够代表特征集m
*
的信息含量的多少，可以反映出每个特征子集所含信息量对特征集的表达程度，当ic值越大时，特征子集所含信息量对特征集的表达程度越高，对类别分类的作用越大；反之ic越低，对类别分类的作用也越小，所以特征子集γ
l
的子空间信息ic
l
可以表示为证毕。
[0169]
(3)首先对特征子集按照ic值降序排序，并设置阈值τ移除信息量比例较低的特征子集，然后重新按(1)(2)获取子集，直到获得满足阈值τ的s个特征子集。
[0170]
(4)首先对满足阈值τ的s个特征子集都进行h
′
次有放回的bootstrap采样，然后获得s个用于构建决策树的特征子集τ
l
(l＝1,2,
···
,s)。
[0171]
3.并行构建随机森林
[0172]
目前在大数据环境下的并行随机森林算法中，在并行构建随机森林算法时由于各个计算节点中构建的决策树不同，得到的预测键值对也不同，所以合并后各个mapper节点上的键值对数量相差也较大，使得reducer节点存在负载不均的问题，影响了并行化效率。故本文提出了节点分配函数ndf对reducer阶段的节点负载进行平衡以优化mapreduce模型，并将优化后mapreduce模型用于并行构建随机森林后对预测数据集进行分类以获得随机森林的准确度。具体过程如下：(1)节点分配：首先统计map过程各个key出现的次数，然后计算各个key在各节点上的标准差得到键标准差集合sdk，最后提出了节点配分函数ndf按集合sdk中key的顺序计算ndf值，并把key分配到ndf值最小的节点；(2)构建随机森林：首先调用map函数将s个特征子集作为训练集构建s个子森林，然后利用子森林对数据集db
″
进行预测后，将所有子森林进行合并获得随机森林模型，最后将各子森林预测获得的结果分配到reducer节点进行合并获得全局分类结果，并与标签集l比较后得到模型的准确度。
[0173]
(1)节点分配
[0174]
在目前的并行构建随机森林过程中，由于各mapper节点上的键值对数量相差较大使得reducer节点负载不均，所以需要对reducer阶段的节点进行合理分配来达到平衡。假定各mapper合并后获得的键值对集合为p1,p2,
···
,po，则节点分配过程如下：
[0175]
1)首先将所有键值对作为中间结果保留到中间文件，并依照键值对对应的键将其降序排列，然后统计各个key的出现次数以键值数据表的形式保存(如表1)。
[0176]
表1键值数据表
[0177]
keyvaluekey120key218
……
keyo0
[0178]
2)首先分析键值数据表计算各键在节点上的数据量标准差，然后根据标准差降序
排列后生成键标准差集合sdk＝{sdkey1,sdkey2,
···
,sdkeyo}
[0179]
3)首先提出节点分配函数ndf按集合sdk对key计算分配到节点后的ndf值，然后将各key分配到ndf值最小的节点上执行reduce操作。
[0180]
定理8(节点分配函数ndf)：已知键key
x
在映射时，假定key
x
分到某一节点后，节点j上的数据量为nodedataj，节点数为z，且key
x
分到某一节点后各个节点上的平均数据量为则key
x
的节点分配函数如下计算：
[0181][0182]
其中
[0183]
证明：对于集合sdk中靠前的key
x
，由于sdkey较大，所以key
x
在节点上分布较为不均匀，要保持节点负载均衡，则分配key
x
到某一个节点后各节点数据分布要最均匀，也就是要衡量将key
x
分配给某个节点后各节点数据量分布的均匀程度，由于各节点数据的均匀程度取决于key分配到某一结点后节点j上的数据量nodedataj与各节点上的平均数据量所以只有当前分配方法下每个节点都有才能使节点数据分布更均匀，使得节点负载均衡，即要求所以要求最小化节点数据量分布的标准差，可得证毕。
[0184]
(2)并行构建随机森林
[0185]
通过节点分配函数可以获得优化后的mapreduce模型，则可以在该模型下并行构建随机森林，在图1中给出总体过程，构建过程如下：
[0186]
1)首先将对特征降维后的特征集使用子空间信息度量策略，得到s个特征子集作为训练集；然后调用map函数以键值对＜key
t
,value
t
＞形式构建决策树(key
t
为决策树编号，value
t
为决策树模型)，待全部mapper节点执行完成后合并成s个子森林；最后使用mapper节点中的子森林对数据集db
″
进行预测并形成新的键值对＜key
′
,value
′
＞(key
′
表示样本的编号以及对应类别的数组，value
′
表示出现的键值对次数)后合并相同key
′
值的键值对。
[0187]
2)首先调用map函数以键值对＜fkeyf,valuef＞的形式构建全局随机森林(fkeyf为子森林编号，valuef为子森林模型)；然后待全部mapper节点运行完成后，对所有子森林进行合并获得随机森林模型；最后将mapper节点中预测获得的键值对分配到对应的reducer节点进行合并，获得全局分类结果并与标签l比较后得到模型的准确度。
[0188]
4.基于增益率与堆叠自编码器的并行随机森林优化方法有效性
[0189]
为了验证prfgrsae的分类效果，我们将prfgrsae方法应用于deepfakes，susy，url及lot_attack四个数据集进行对比实验，数据集具体信息如下表。并与mrrf、idarf和drf算法在分类精准度等方面进行了比较。
[0190]
表2实验数据集
[0191]
数据集名称数据量特征数特点deepfakes20000200000样本量少，特征数多susy500000018样本量多，特征数少url23961303231961样本量多，特征数多lot_attack7062606115样本量多，特征数适中
[0192]
4.1prfgrsae方法的并行性能分析
[0193]
为验证prfgrsae算法的加速比，将prfgrsae算法、mrrf算法、idarf算法与drf算法分别在deepfakes，susy，url及lot_attack四种数据集上进行对比实验，并使用加速比作衡量指标，分别比较各个算法在不同节点数下的加速比，进而对各个算法的性能进行比较分析。其实验结果如图2所示：
[0194]
从图2可以看到，随着节点数的增加，prfgrsae算法在各数据集上逐渐获得最高的加速比。当节点数为5时，在特征数目较多的deepfakes数据集上，prfgrsae算法比mrrf、drf和idarf算法，分别提升了0.53，0.35，0.77；在样本数量较多，特征数较少的susy数据集上，分别提升了0.5，0.25，0.85；而在样本数量较多且特征数较多的url数据集上，分别提升了0.64，0.38，0.79；在样本数量较多且特征数适中的lot_attack数据集上，分别提升了0.51，0.22，0.82。产生这些结果主要是因为使用了drgrsae策略减少了特征集的冗余以及不相关特征数，其特征集的冗余与不相关特征数远少于使用改进蜻蜓算法进行特征选择的idarf算法，所以很大程度地减少了处理冗余与不相关特征的时间，并且在并行阶段使用了snd策略优化mapreduce，使得合并时可以选择负载较小的节点分配reduce任务，从而有效平衡了节点间负载并提高了并行化效率，其并行化效率远高于只使用mapreduce的mrrf算法和drf算法。故相比于上述三种算法，prfgrsae算法在大数据集上的并行性能和鲁棒性更佳。
[0195]
4.2prfgrsae方法的分类效果分析
[0196]
为验证prfgrsae算法的准确度，使用kappa值作为衡量指标，将将prfgrsae算法、mrrf算法、idarf算法与drf算法分别在deepfakes，susy，url及lot_attack四种数据集上进行对比实验，并分别运行20次得出分类结果，将均值作为实验结果。实验结果如图3所示：从图3中可以看到，相较于mrrf、drf和idarf算法，prfgrsae算法在四个数据集上都取得了最高的kappa值。在特征数较多的deepfakes和url数据集上kappa值都远高于其他三种算法，其中，在deepfakes数据集上相较于mrrf、drf和idarf算法分别提高了15.1％，5.2％，8.9％，在url数据集上分别提高了19.2％，8.8％，12.7％；而在lot_attack与susy数据集上kappa值没有很明显的提高，在样本数量较多且特征数适中的lot_attack数据集上相较于mrrf、drf和idarf算法分别提高了5.5％，3.6％，7.4％，在样本数量较多，特征数较少的susy数据集上分别提高了7.3％，3.5％，9.3％。产生这些结果的主要原因是prfgrsae算法在使用drgrsae策略在特征降维阶段有效减少了冗余与不相关特征数，并且在形成特征子空间的时候使用了siebg策略保证了特征子空间的信息含量，而mrrf算法在选择特征构建
决策树时没有考虑到特征的信息量对准确率的影响，idarf使用改进蜻蜓算法进行特征选取则容易选择到局部信息量充足的特征，drf算法使用均匀分层抽样抽取特征则限制了有足够信息量的特征数量。因此，在特征数较多的deepfakes和url数据集上，prfgrsae算法能够取得比其他三种算法更高的kappa值。因此，prfgrsae算法在数据规模较大，特征数较多的数据集上具有最佳的分类效果。
[0197]
尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。

技术特征：
1.一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，包括：s1，对训练数据集进行特征降维：先对各特征计算特征依赖度获得候选特征集，再对候选特征集的各特征使用冗余过滤函数过滤候选特征集之外的冗余与不相关特征，并使用堆叠自编码器对数据集进行特征提取得到降维数据集；s2，子空间选择：计算由降维数据集初始化生成的特征子空间的信息含量后判断是否满足设定阈值，并对不满足设定阈值的特征子空间进行重新选取；s3，并行构建随机森林：计算各节点分配后的节点数据量以衡量节点负载后，通过节点分配函数选择负载较小的节点分配reduce任务；s4，将待测数据输入随机森林，得到最终分类结果。2.根据权利要求1所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述s1包括：s1-1，特征选择：用于减少数据集中的冗余与不相关特征数；1)获取平均信息增益：计算每个特征的信息增益ig
i
，然后根据每个特征增益值的概率计算平均信息增益aig；2)过滤不相关特征：根据aig得到每个特征的增益评估系数g
i
并计算每个特征的增益率gr
i
，然后根据特征依赖度fd来去除不相关的特征；3)过滤冗余特征：通过冗余过滤函数rff对集合f中对优势特征在类别分类时有较大影响的特征进行过滤，然后重新组合获得优化后的特征集；s1-2，特征提取：对特征选择后的数据集进一步提取优化；1)初始权重矩阵与特征矩阵重构：使用堆叠自编码器获取初始权重矩阵和偏置，通过反向传播调整权重矩阵以及偏置重构特征矩阵，并使用softmax分类器进行分类；2)信息损失量与分类误差估计：采用l2范数对信息损失量与分类误差进行估计；3)参数集优化：为了使信息损失量和分类误差总和达到最小，提出了参数优化函数对参数集进行优化。3.根据权利要求2所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述平均信息增益aig包括：其中，ig
i
表示第i个特征的信息增益；p
i
为特征数的倒数；q为特征总个数。4.根据权利要求2所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述特征依赖度fd包括：fd(d
i
,l)＝g
i
×
gr(d
i
,l)其中fd(d
i
,l)为在标签集l下特征d
i
的特征依赖度；d
i
表示第i个特征；
g
i
为增益系数；gr(d
i
,l)为标签集l下特征d
i
的增益率；ig
i
为特征的信息增益；aig为平均信息增益；k为去除不相关特征后的特征总个数。5.根据权利要求2所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述冗余过滤函数rff包括：rff(d
α
,d
β
)＝fd(l,d
α
)-gr(d
α
,d
β
)其中fd(l,d
α
)为标签集l下优势特征d
α
的特征依赖度；gr(d
α
,d
β
)表示特征d
j
关于特征d
k
的增益率；d
α
表示第α个特征；d
β
表示第β个特征。6.根据权利要求2所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述初始权重矩阵与特征矩阵重构包括：首先，设置初始堆叠自动编码器含有一层输入层，一层输出层以及两层隐藏层，其中两层隐藏层的节点个数分别为h，h
′
，然后输入特征矩阵d
′
获取初始的权重矩阵，其中，输入特征矩阵到第一层隐藏层的权重矩阵为w1，偏置为b1，第一层隐藏层到第二层隐藏层的权重矩阵为w2，偏置为b2，第二层隐藏层到输出层的权重矩阵为w3，偏置为b3，则编码与解码过程表示如下：m1＝σ(d
′
w1+b1)m2＝σ(m1w2+b2)d
″
＝σ(m2w3+b3)其中σ(
·
)为激活函数；d
″
为重构后的特征矩阵，m1为第一层隐藏层的中间矩阵，m2为第二层隐藏层的中间矩阵；最后，将m2与标签集l合并后得到特征提取后的数据集db
″
，并使用softmax分类器对数据集db
″
进行分类，获得关于m2的分类矩阵c，则可得出m2的预测标签f(m2)为：f(m2)＝m2cf(m2)＝σ(m1w2+b2)c其中f(m2)为重构矩阵d
″
通过softmax分类预测得到的预测标签集。7.根据权利要求2所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述分类误差包括：l
error
＝||l,f(m2)||2其中l
error
为分类误差；l为特征矩阵d
′
的标签集；f(m2)为重构矩阵d
″
通过softmax分类预测得到的预测标签集；
||
·
||2表示l2范数。8.根据权利要求2所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述参数优化函数包括：p(θ,c)＝j(θ)+λl
error
其中，p(θ,c)为参数优化函数；j(θ)为信息损失量；λ为分类误差的权重；l
error
为分类误差；s表示特征维数；d
i
′
为第i个重构特征；d
i
为第i个原特征；l为标签集；f(m2)为预测标签集；||
·
||2表示l2范数。9.根据权利要求1所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述s2包括以下步骤：s2-1，对特征集m
*
＝[d1,d2,
····
,d
h
′
]进行无放回抽样得到s个特征子集(γ1,γ2,
···
,γ
s
)，然后形成包含s个特征子集的特征子集集合γ；其中d
h
′
表示第h
′
个特征，h
′
表示第二层隐藏层的节点个数，γ
s
表示第s个特征子集；s2-2，采用子空间信息度量ic来衡量特征子集的信息量，然后根据每个子集γ
l
包含的特征变量计算ic；其中，gr
lj
表示第l个特征子集中第j个特征；sic
l
表示第l个特征子集包含的特征信息量；gr
i
表示表示第i个特征子集；l＝1,2,
···
,s为第l个特征子集的索引；i＝1,2,
···
,h
′
为第i个特征；s2-3，对特征子集按照ic值降序排序，并设置阈值τ移除信息量比例较低的特征子集，然后重新按s2-1，s2-2获取子集，直到获得满足阈值τ的s个特征子集；s2-4，对满足阈值τ的s个特征子集都进行h
′
次有放回的bootstrap采样，然后获得s个用于构建决策树的特征子集τ
l
(l＝1,2,
···
,s)。10.根据权利要求1所述的一种基于增益率与堆叠自编码器的并行随机森林优化方法，其特征在于，所述s3包括以下步骤：s3-1，节点分配：首先统计map过程各个key出现的次数，然后计算各个key在各节点上
的标准差得到键标准差集合sdk，最后提出了节点配分函数ndf按集合sdk中key的顺序计算ndf值，并把key分配到ndf值最小的节点；s3-2，构建随机森林：首先调用map函数将s个特征子集作为训练集构建s个子森林，然后利用子森林对数据集db
″
进行预测后，将所有子森林进行合并获得随机森林模型，最后将各子森林预测获得的结果分配到reducer节点进行合并获得全局分类结果，并与标签集l比较后得到模型的准确度。

技术总结
本发明提出了一种基于增益率与堆叠自编码器的并行随机森林优化方法，包括：S1，对训练数据集进行特征降维：先对各特征计算特征依赖度获得候选特征集，再对候选特征集的各特征使用冗余过滤函数过滤候选特征集之外的冗余与不相关特征，并使用堆叠自编码器对数据集进行特征提取得到降维数据集；S2，子空间选择：计算由降维数据集初始化生成的特征子空间的信息含量后判断是否满足设定阈值，并对不满足设定阈值的特征子空间进行重新选取；S3，并行构建随机森林：计算各节点分配后的节点数据量以衡量节点负载后，通过节点分配函数选择负载较小的节点分配Reduce任务；S4，将待测数据输入随机森林，得到最终分类结果。本发明在分类效果和并行效率上都有显著的提升。和并行效率上都有显著的提升。和并行效率上都有显著的提升。


技术研发人员：毛伊敏 戴经国 陈伟达 陈志刚 霍英
受保护的技术使用者：韶关学院
技术研发日：2022.03.21
技术公布日：2022/7/5