APP下载

基于Spark 和三路交互信息的并行深度森林算法

2023-09-19毛伊敏周展陈志刚

通信学报 2023年8期
关键词:级联粒度向量

毛伊敏,周展,陈志刚

(1.江西理工大学信息工程学院,江西 赣州 341000;2.韶关学院信息工程学院,广东 韶关 512026;3.中南大学计算机学院,湖南 长沙 410083)

0 引言

深度森林是Zhou 等[1]提出的一种基于决策树结构的深度学习模型,其包含多粒度扫描和级联森林两大组成部分,因其超参数少、参数敏感度低及模型深度自适应等优点,已被广泛应用于网络流量分类[2]、文本分类[3]、故障诊断[4]、目标识别[5]、恶意代码分类[6]等领域。然而,随着新一代信息技术的革新和大数据时代的来临,各领域将产生亟待处理的海量数据,这些数据通常表现出数据量大、数据价值密度低等特性,深度森林难以有效处理这类数据,因此如何设计出适合处理大数据问题的深度森林算法已成为一大研究热点。

Spark[7]作为专门处理大规模数据问题开发的并行计算框架,因其出色的计算能力和良好的通用性,被广泛应用于企业项目开发和学术研究中。文献[8]提出了用于退网用户预测的并行深度森林(PDF-OGUP,parallel deep forest for off-grid user prediction)算法,为节省多粒度扫描阶段的空间占用,设计了基于下标的扫描算法,并以随机采样构建随机森林的方式减少所需内存空间。针对网络入侵问题,文献[9]设计了基于特征分割和深度并行随机森林(FS-DPRF,feature segmentation and deep structure of parallelized random forest)检测模型,提出了RDD(resilient distributed datasets)层次替换策略解决了RDD 重用问题,提高了作业效率。为进一步提高并行深度森林算法的计算能力,文献[10]结合Spark 框架设计了一种全新的并行深度森林BLB-gcForest(bag of little bootstraps-gcForest)算法。首先,该算法使用BLB(bag of little bootstrap)自助采样法替换传统采样法,减少了大量特征在级联森林各层级中的传输,提高了计算效率和通信效率;其次,提出自适应子森林划分算法,以确保每个子森林并行计算的资源利用率最大化;最后,利用轮询机制来实现节点的负载均衡。以上列举的3 种并行深度森林算法虽然在训练效率上有了一定的提升,但仍然存在以下不足。1) 在特征选择阶段,无法有效去除原始数据携带的大量冗余和无关特征,导致后续模型训练过程中存在冗余及无关特征问题。2) 在多粒度扫描阶段,输入的原始特征经过滑动窗口扫描后,将产生大量的特征子序列,拼接多个输出的类向量将导致类向量过长问题。3) 在级联森林训练阶段,级联森林的每一层都将拼接原始特征和上层特征作为本层输入,但相对于原始特征的维度,每层转化后的增广特征的维度则要小得多,这将导致增广特征被淹没[11],使模型收敛速度缓慢。4) 在模型并行化训练阶段,子森林的划分粒度不能依据模型训练效果自适应确定,加之异构节点情况下存在中间数据倾斜,将导致模型并行训练效率低下。

针对上述问题,本文提出了基于Spark 和三路交互信息的并行深度森林(PDF-STWII,parallel deep forest algorithm based on spark and three-way interactive information)算法,其主要工作如下。

1) 提出基于特征交互的特征选择(FSFI,feature selection based on feature interaction)策略,通过消除原始特征中存在的大量冗余及无关特征,解决了冗余及无关特征过多的问题。

2) 提出多粒度向量消除(MGVE,multi-granularity vector elimination)策略,通过将多粒度扫描产生的任意2 个相似类向量融合为一个向量,解决了多粒度扫描过程中产生的类向量过长问题。

3) 提出了级联森林增强(CFFE,cascade forest feature enhancement)策略,密集连接所有级联层输出的增广特征的同时动态缩减部分原始特征,解决了模型收敛速度慢的问题。

4) 提出了多级负载均衡(MBL,multi-level load balancing)策略,通过自适应子森林划分(ASFS,adaptive sub-forest splitting)算法控制森林划分粒度和异构倾斜数据划分(HSDP,heterogeneous skew data partition)算法平衡异构数据的倾斜,提高了模型的并行化训练效率。

1 相关概念介绍

定义1互信息[12]常用来衡量变量之间的相关性程度,互信息越大,变量间的相关性越强,反之,则相关性越弱。反映随机变量fi和fj相关性的互信息I(fi;fj)可定义为

其中,H(fi)为变量fi的信息熵,表示变量不确定性程度;H(fi|fj)为变量fj确定时fi的条件熵I(fi;fj) <min{H(fi),(fj)}。

定义2对称不确定性[13]常用于相关特征选取,其通过归一化互信息修正了互信息在选取特征时存在的偏置。2 个随机变量fi和fj的对称不确定性SU(fi,fj)可定义为

从式(2)可知,SU(fi,fj)∈[0,1]。

定义3三路交互信息[14]作为互信息的扩展可用来度量特征之间的交互性,其值可为正数、零和负数。当三路交互信息为正数时,2 个特征共同对标签提供的信息大于它们单独对标签提供信息的和,此时2 个特征存在互补性;当三路交互信息为负数时,2 个特征对标签提供的信息存在冗余;当三路交互信息为零时,2 个特征提供给标签的信息是独立的。对于特征fi和fj及标签C,三路交互信息I(fi;fj;C)可表示为

其中,p(fi)p(fj)p(C)为三者的联合概率。

定义4近似马尔可夫毯[15]可用于冗余特征的检验,如果特征fj是特征fi的近似马尔可夫毯,则2 个特征之间存在冗余,SU(fj,C) ≥SU(fi,C)和SU(fj,fi) ≥SU(fi,C)同时成立。

定义5皮尔逊相关系数常用来衡量2 个向量之间的相似程度,取值范围为[-1,1],其绝对值越大,相关性越强。当取值为正时,2 个向量呈正相关,当取值为负时,2 个向量呈负相关;当取值为零时,2 个向量无关。皮尔逊相关系数定义为

其中,cov(X,Y)表示2 个向量之间的协方差,σX和σY分别表示向量X和向量Y的标准差,μ表示向量均值,E 表示数学期望值。

2 PDF-STWII 算法说明

PDF-STWII 算法主要包括4 个阶段:特征选择、多粒度扫描、级联森林训练、模型并行化训练。各阶段的主要任务如下。

1) 特征选择。提出FSFI 策略,通过度量特征的相关性和冗余度,消除大量冗余及无关特征,同时挖掘出存在交互作用的特征,过滤大量冗余及无关特征。

2) 多粒度扫描。提出MGVE 策略,融合任意2 个相似类向量,缩短类向量长度。

3) 级联森林训练。提出CFFE 策略,密集连接各层增广特征,同时逐层削减部分特征,防止增广特征被淹没,加快模型收敛速度。

4) 模型并行化训练。提出了MBL 策略,其包含两方面内容。在算法并行处理层面,提出ASFS算法,通过分析子森林训练效果,自适应确定森林的划分粒度,提高算法并行度。在数据并行化处理方面,提出了HSDP 算法,分析分布式异构环境中各计算节点的性能差异,将中间数据合理分配到各节点,以平衡中间数据倾斜,最终从算法和数据两方面提高模型并行化训练效率。

2.1 特征选择

针对原始数据集包含大量冗余及无关特征问题,提出的FSFI 策略从特征相关性、冗余度和特征交互三方面综合考虑特征选取,高效剔除冗余无关特征。FSFI 包括无关特征过滤、冗余特征消除和特征综合评分。

2.1.1无关特征过滤

在特征选择过程中,由于相对于特征的冗余度和交互性计算,特征的相关性计算更快,所以在特征选择的初始阶段,提出特征相关性系数(FRC)过滤大量无关特征,删除小于相关性阈值的特征,并利用FRC 对特征排序。

定理1特征相关性系数(FRC)。已知数据集D∈Rn×m,其中n和m分别为数据的样本量和特征,则fi与标签C的相关性系数FRCi定义为

其中,fsi表示样本s中fi的值。

证明对标签具有较强区分度的特征,通常存在较大的方差,可用标准差反映特征fi对类别的区分能力。D为特征fi的标准差,标准差越大,特征区分标签类别的能力越强;由互信息定义可知I(fi;C) <min{H(fi),H(C)},互信息的大小受特征和标签信息熵的限制,直接使用互信息来衡量相关性时,具有越大信息熵的特征越有可能被选取,因此将互信息I(fi;C)除以特征fi和标签C的最小信息熵以消除偏置,最终将反映特征区分度的标准差和消除偏置的互信息相乘获得特征相关性系数FRC,证毕。

2.1.2冗余特征消除

经过无关特征初步过滤过程,特征的维度大幅缩减,但冗余特征并未消除,为此,在特征消除阶段提出冗余度指标R来衡量特征之间的冗余程度。冗余消除过程如下。首先,利用近似马尔可夫毯快速判断冗余特征并消除;然后,利用冗余度指标R计算特征间的冗余度,对比冗余度指标和冗余度阈值,进一步消除冗余特征。

定理2冗余度指标R。已知存在特征fi和特征fj,则计算特征间的冗余度指标R可表示为

证明SU(fi,C)为特征fi与标签C的对称不确定性,根据对称不确定性定义可知,SU(fi,C)可度量特征fi与标签C的相关信息量,同理,SU(fi,fj)可度量2 个特征之间的相关信息量,反映特征信息重叠大小。H(fi)为fi的信息熵,表示特征自身信息量的大小。当越大时,在一个确定信息空间中的特征fi和特征fj的信息重叠概率也就越大,即越可能存在信息冗余。综上,P可表示冗余概率,SU(fi,fj)可表示冗余信息量,冗余概率和冗余信息量联立获得冗余度指标R,证毕。

2.1.3特征综合评分

经过无关特征过滤和冗余特征消除过程,剩余的特征都具有较高质量,为了进一步挖掘出更高质量的特征子集,从特征相关性、冗余度和特征交互性出发,设计特征综合评估函数JFSFI,获取更优特征子集。

定理3特征综合评估函数JFSFI。假设候选特征fi与标签C的相关性为I(fi;C),与已选特征fj的冗余度为I(fi;fj),候选特征fi和已选特征fj对标签的交互性为I(fi;fj;C),特征综合评估函数JFSFI可表示为

其中,F′表示候选特征集,Fs表示已选特征集。

综上,特征评估函数JFSFI在选择特征时能够有效挖掘出高相关性、低冗余度且具有交互作用的候选特征,证毕。

FSFI 的伪代码如算法1 所示。

算法1FSFI

2.2 多粒度扫描

多粒度扫描[16]利用多种尺寸的滑动窗口对原始特征进行切片,随后将切片得到的多个窗口尺寸大小的特征子序列传入随机森林中进行训练,最后将训练得到的类向量拼接传入级联森林中训练。然而由于滑动窗口扫描得到的特征子序列存在大量相同特征,训练得到的大量类向量也相似,拼接大量相似类向量将使传入级联森林的类向量过长,增加级联森林训练开销。

针对多粒度扫描过程中产生的类向量过长问题,本节设计了MGVE 策略将相似类向量融合。其具体过程如图1 所示。

图1 MGVE 过程

定理4相似类向量判定函数S(P(A,B),δ)。已知在多粒度扫描阶段随机森林输出类向量A和B,则2 个向量的相似性判定表示为

其中,P(A,B)为向量A和B的皮尔逊相关系数,δ为设定的相似度阈值。当P(A,B)>δ时,S(P(A,B),δ)=1表明2 个向量相似,反之不相似。

证明由于P(A,B)能直接反映2 个向量之间的线性相关程度,同时每个随机森林输出的类向量为各个类别的概率,这使每个向量的内部概率值的和为1。当用皮尔逊相关系数测得2 个向量相关性越大时,2 个向量方向越趋于一致,此时2 个向量内对应的各数值就越接近,2 个向量相似度越高,因此用皮尔逊相关系数与设定的阈值δ相比可判定2 个向量是否相似,证毕。

MGVE 的伪代码如算法2 所示。

算法2MGVE

2.3 级联森林训练

针对级联森林训练过程中模型收敛速度慢的问题,本节提出了CFFE 策略,其主要过程如下。首先,密集连接每一层级联森林产生的增广特征;其次,为维持总的输入特征的维度不变,每一层级联森林训练后都根据训练效果给原始特征赋予不同的特征重要性权重w,去除部分权重低的特征。具体过程如图2 所示。

图2 CFFE 过程

定理5特征j重要性权重w(j)。假设表示特征j是级联森林中第i个随机森林RFi中的权重,m个随机森林训练使用了特征j,则特征j在本层的重要性权重w(j)为

证明假设在构建决策树时,决策树τ内部的节点i被预测为类别c的概率为p(c),则节点i的信息熵E(i)可表示为

特征j将节点i划分为左右子节点,左右子节点的信息熵分别为El(i)和Er(i),则节点i被j划分的效果Q(i,j)可表示为

决策树τ总共有N个节点,特征j在决策树τ中的局部权重wτ(j)可表示为

为评估决策树权重,使用袋外误差δ作为评估标准。设决策树τ的袋外误差为δτ,则随机森林中决策树τ的归一化权重γτ可表示为

通过式(14)和式(15),获得特征j在决策树τ中的局部权重wτ(j)和决策树权重γτ,则特征j在单个随机森林RF 中的权重wRF(j)可表示为

证毕。

2.4 模型并行化训练

针对模型并行化训练效率低的问题,本节提出了MLB 策略,从算法和数据2 个层面提升模型的并行化训练效率,包含算法层面的ASFS 算法和数据层面的HSDP 算法。

2.4.1自适应子森林划分

在算法层面,为提高模型的并行化训练效率,本节提出了ASFS 算法,其主要过程为如下。首先,采用自助采样法将采样特征分配到子森林中;然后,根据各个子森林的训练结果给每个子森林设定子森林权重系数WSF;最后,利用子森林的权重WSF计算出整个森林划分得分因子 scoreF以确定森林划分粒度。具体过程如图3 所示。

图3 子森林划分

定理6子森林权重系数WSF(r)。设第r个子森林中包含Q个决策树,利用OOB 数据集验证获得第i个决策树的袋外误差errOOBi,则第r个子森林的权重系数WSF(r)可表示为

定理7 森林划分得分因子 scoreF(s)。将第s个森林划分为r个子森林,则第s个森林的森林划分得分因子为

证明为第i个子森林的平均预测准确率,准确率越高,子森林整体的分类能力越强。WSF(i)为子森林权重系数,权重越大,子森林的稳定性越强、准确率越高,一个森林包含多个子森林,每个子森林的预测效果又包含准确率和稳定性两方面特性,因此结合两方面特性的 scoreF(s)可表示子森林的整体预测效果,证毕。

ASFS 的伪代码如算法3 所示。

算法3ASFS

输入级联层数T,每层森林数S,预设最大子森林数R,子森林中树的数量Q

输出子森林划分矩阵P[][]

2.4.2异构倾斜数据划分

在数据层面,由于Spark 在Shuffle 阶段采用默认的哈希分区策略极易引起中间数据倾斜,严重影响模型的并行化训练效率,为此本文提出HSDP 算法。平衡中间数据倾斜需进行如下操作。

1) 倾斜评估。Spark 以哈希分区作为默认的分区方式将产生2 种数据倾斜情况:同一键值包含大量键值对,经过Shuffle 过程被分配到同一分区,导致这一分区数据量巨大;大量不同键值对应同一分区索引,导致大量不同键对应的键值对分配到同一分区。以上2 种数据倾斜情况在节点异构环境下将更加严重,对此,本文提出异构倾斜度量因子D来评估在节点异构条件下中间数据的倾斜程度。

定理8异构倾斜度量因子D。假设中间数据包含m个不同的key,且第i个key 对应的数据容量为Qi,N个桶对应N个计算节点,第j个桶包含的key 表示为 {K1,j,K2,j,…,Km,j},每个桶的数据量依次表示为q1,…,qj,…,qN,qavg为所有桶的平均数据量,则异构倾斜度量因子D可表示为

其中,RCj表示第j个计算节点的相对计算能力。

证明由于qavg和avg_capability 是实际环境中的固定值,于是可设定系数α表示两者的比例,即qavg=αa vg_capability。qj-αc apabilityj为第j个桶的理论最大负载和实际负载的差值,D′为实际负载和理论负载的标准差,实际负载和理论负载越接近,异构倾斜度量因子D越小,因此可用D作为异构倾斜度量因子来衡量中间数据倾斜程度,证毕。

2) 中间数据预测。为降低数据统计耗时,采用主从整体采样法预测中间数据。首先,从节点通过RDD操作计算所有Map 任务的mapPartitionsRddSize ;然后,设置采样率r,通过sampleSize=rmapPartionsRddSize 计算总共的采样大小,根据sampleSizePerPartion 计算每个Map任务采样的样本大小;其次,每个从节点利用sampleSizePartion 的大小调用RDD 的sample 函数对RDD 数据分区进行采样,统计出本地样本中key 值记录,随后将(Ki,Qi)传输到主节点;最后,主节点汇总每个Map 任务的所有样本数量,根据采样率得到中间数据集{(K1,Q1),(K2,Q2),…,(Km,Qm)}的整体分布情况。

3) 异构倾斜数据划分。通过整体采样方法获得中间数据的预测,根据节点的异构情况采用贪心策略将中间数据合理分配到各个桶中。

HSDP 的伪代码如算法4 所示。

算法4HSDP

2.5 算法时间复杂度分析

PDF-OGUP、FS-DPRF 和BLB-gcForest 等算法都基于Spark 框架设计,且各自采用不同的优化策略提高算法性能,因此选取这3 种算法与本文算法进行实验对比。

PDF-STWII 算法主要包括特征选择、多粒度扫描、级联森林训练、级联森林并行化训练。各阶段的时间复杂度分别标记为T1、T2、T3、T4。

特征选择包括无关特征过滤、冗余特征消除、特征综合评分。已知数据样本量为n,特征数目为m,无关特征过滤遍历所有样本和特征,其时间复杂化度为O(nm) ;冗余特征消除需要计算近似马尔可夫毯和三路交互信息,需要的时间复杂度为O(m2);特征综合评分阶段需要的时间复杂度为O(m2n),因此特征选择时间T1为

在多粒度扫描阶段,时间复杂度主要取决于特征子集在随机森林训练以及类向量融合的时间开销。假设经过特征选择后的特征个数为s,滑动窗口大小为w,样本数目为n,随机森林的个数为N,则T2为

其中,O(s-w)为窗口扫描时间复杂度,O(s(s-w)nN)为特征子集训练时间复杂度,O(N2)为类向量融合的时间复杂度。

在级联森林训练阶段,假设传入级联森林的原始特征的个数为v,样本数目为n,每一层森林的个数为N,每个森林包含Q棵树,级联森林层数为L,则T3为

在模型并行化训练阶段中,时间复杂度主要由子森林划分、异构数据分区两部分组成。假设每一层森林的个数为N,每个森林包含Q棵树,级联森林的层数为L,每个森林可划分为r子森林,并行节点数量同样为r,则T4为

其中,O(NLQ)为自适应子森林划分的时间复杂度,O(r2)为异构数据分区的时间复杂度。

综上,PDF-STWII 算法的时间复杂度为

其中,r为单个森林划分的子森林个数。

在大数据环境下,深度森林模型训练的时间复杂度主要取决于多粒度扫描阶段中输出的类向量长度和级联森林训练层数,即算法的时间复杂度T主要由T3中的v和L决定。由于算法PDF-OGUP、FS-DPRF 和BLB-gcForest 都没在多粒度扫描阶段对相似类向量进行融合,从而使vPFG-OGUP>vPDF-STWII,vFS-DPRF>vPDF-STWII,vBLB-gcForest>vPDF-STWII。又由于本文在级联森林中使用了CFFE 策略加快了模型收敛,因此需要的训练层数相对更少,从而使LPFG-OGUP>LPDF-STWII,LFS-DPRF>LPDF-STWII,LBLB-gcForest>LPDF-STWII。综上,相较于PDF-OGUP、FS-DPRF 和BLB-gcForest 算法,PDF-STWII 算法具有更低的时间复杂度。

3 实验结果分析

3.1 实验环境

为验证本文算法的性能表现,本文设计了相关实验。在硬件方面,本文实验设置8 个计算节点,其中包括1 个主节点和7 个从节点。各个计算节点的硬件配置均为Intel(R) Core(TM) i7-11800H CPU、16 GB DDR4 RAM、1 TB SSD,实验中的计算节点处于同一局域网内,通过1 GB/s 的以太网相连。在软件方面,各计算节点配置均为Ubuntu16.04、Hadoop 2.7.4、JDK 1.8.0。各节点的详细配置如表1 所示。

表1 节点详细配置

3.2 实验数据与设置

实验数据。所有算法采用4个来自UC(Iuniversity of California Irvine)公共数据库的数据集,分别为Farm Ads、Susy、Connect-4 和FMA,其中Farm Ads是从12 个网站文本中搜集的各种有关农场动物的话题;Susy 是记录粒子在加速器条件下是否产生超对称粒子信号过程的数据集;Connect-4 数据集记录了四子棋游戏中所有合法的8 层位置信息;FMA 记录了包括歌曲标题、专辑、艺术家等众多曲目信息。各数据集的详细信息如表2 所示。

表2 实验数据集

实验设置。对于实验数据划分,采用所有算法数据划分一致性原则,即70%为训练集,30%为测试集;对于模型参数,设数据的特征长度为d,在多粒度扫描阶段中滑动窗口大小依次设置为每个子森林中的决策树的数量初始化为随机森林中决策树数量的开方,每一层级联森林包含2 个随机森林和2 个完全随机森林。

3.3 评价指标

3.3.1加速比

加速比是指同一任务在单处理器系统和在并行处理器系统中运行消耗的时间的比率,常用来衡量并行系统或程序并行化的性能和效果,加速比越大,算法的并行化程度越高,其定义如下

其中,Ts表示在串行系统中的执行时间,TP表示在并行系统中的执行时间。

3.3.2准确率

准确率(Accuracy)是指在分类模型中正确分类的样本数与总的样本数的比值,能够反映算法的分类能力,其定义为

其中,TP、TN、FP、FN 在混淆矩阵中分别表示真正例、真反例、假正例、假反例。

3.4 算法性能的比较分析

算法整体性能需考虑多方面指标,为综合衡量算法性能,利用算法运行时间来度量算法训练速度,利用加速比来度量算法并行处理能力,利用准确率来度量算法分类性能。

3.4.1算法运行时间对比分析

为检验4 种算法训练速度,将PDF-OGUP、FS-DPRF、BLB-gcForest 与本文算法(PDF-STWII)在上述4 个数据集上进行对比实验,森林中决策树数量为200,实验采用10 折交叉验证方式,实验结果如图4 所示。

图4 不同数据集上4 种算法的运行时间

从图4 中可知,在对4 个数据集的测试中,本文算法所需要的运行时间最低,并且当数据集的特征数量越多时,本文算法相对其他算法缩短的运行时间比例也越大,在特征量最少的数据集Susy 中,本文算法相比PDF-OGUP、FS-DPRF、BLB-gcForest运行时间分别减少了2.62%、10.41%、3.41%;在特征量最多的数据集Farm Ads 中,PDF-STWII 算法相比PDF-OGUP、FS-DPRF、BLB-gcForest 运行时间分别减少了13.8%、19.12%、10.76%。产生以上结果的主要原因如下。1) 本文算法设计了FSFI策略,消除了大量冗余及无关的特征,在不影响分类精度的前提下极大地减少了后续多粒度扫描和级联森林训练过程中输入的特征量,加快了模型的训练速度;2) 本文算法设计了MGVE 策略,通过将2 个相似的类向量融合为一个类向量,减少了级联森林训练过程中的特征维度,进而减少级联森林的训练开销。实验结果表明,PDF-FSIF 算法在处理高维大数据问题时具有良好性能。

3.4.2加速比对比分析

为验证本文算法的并行计算能力,本文利用上述的4 个数据集分别对PDF-OGUP、FS-DPRF、BLB-gcForest 和本文算法在不同计算节点下进行算法加速比实验,实验采用10 折交叉验证方式进行,森林中决策树数量设置为200,实验结果如图5 所示。

图5 不同数据集上4 种算法的加速比

从图5 可知,各算法的加速比均随着计算节点数量的增加而呈现不同程度的上升。当节点个数为8 时,本文算法的加速比高于对比算法,在特征量最少的数据集Farms Ads 中,本文算法的加速比分别比PDF-OGUP、FS-DPRF、BLB-gcForest 高0.32、0.52、0.18;在特征量最大的数据集Susy 中,本文算法的加速比分别高0.88、1.18、0.465;本文算法取得最高加速比的原因在于设计了MLB 策略,从算法结构划分和中间数据合理分配2 个层面的同时提高了模型的并行化训练效率,从而使算法在处理数据时具有更高的加速比。实验结果表明,PDF-STWII 算法在处理大数据问题时,具有较高加速比。

3.4.3准确率对比分析

为验证本文算法的分类性能,实验选取准确率作为评估指标,将本文算法与对比的PDF-OGUP、FS-DPRF和BLB-gcForest 算法在4 个数据集上进行10 折交叉验证实验,实验结果如图6 所示。

图6 不同数据集上4 种算法的分类精确度

从图6 中可知,随着决策树数量的增加,4 种算法模型的分类准确率都有一定的提升,其主要原因在于随着决策树数量的增加,算法的泛化能力得到了增强,准确率随之提高。实验发现本文算法具有更高的准确率,当森林中决策树数量为200 时,本文算法在 4 个数据集上的平均准确率相比PDF-OGUP、FS-DPRF 和BLB-gcForest 分别提高了1.24%、1.43%、0.96%,产生以上结果的原因如下。1) 本文算法设计了 FSFI 策略,消除大量冗余和无关特征,同时挖掘出具有交互作用的特征,提高了算法分类准确率;2) 本文算法设计了CFFE 策略,密集连接增广特征,充分利用每一层级联森林的分类贡献,提高了模型的预测能力。实验结果表明,本文算法在大数据环境下具有优良的分类性能。

3.5 消融实验

为验证算法各策略的有效性和对算法模型的贡献,选取准确率和加速比作为评价指标,在上述4 个数据集上设计消融实验,实验采用8 个计算节点,森林中决策树数量为200,实验结果由10 折交叉验证获得,实验结果如表3 所示。

表3 消融实验结果

从表3 可知,各策略对加速比和准确率具有不同影响,其中,MBL 策略对算法加速比提升最明显,其次分别是FSFI、MGVE 和CFFE,在处理4 类数据集时,相比无任何策略,使用了MBL、FSFI、MGVE 和CFFE 策略可将算法的平均加速比分别提升19.04%、5.56%、3.64%和1.98%。产生以上结果的原因如下。1) MBL 策略对森林自适应划分和平衡中间数据倾斜,能有效提高模型并行计算能力;2) FSFI 策略消除了原始特征中大量冗余无关特征,从而提高各计算节点的训练效率;3) MGVE策略融合相似类向量,降低子森林训练开销,因此能一定程度提高加速比;4) CFFE 策略在级联森林训练过程中能够逐层削减少量特征,因此对加速比也有细微影响。

对算法准确率提升最大的是 CFFE 策略和FSFI 策略,其次是MGVE 策略和MBL 策略,在处理4 个数据集时,使用CFFE、FSFI、MGVE和MBL 策略相比无任何策略,分别可将算法的平均准确率提升1.98%、1.94%、0.45%和0.21%。产生以上结果的原因如下。1) CFFE 策略密集连接各层增广特征,利用了每层森林的预测贡献;2) FSFI策略消除了冗余无关特征并挖掘特征之间的交互信息;3) MGVE 策略将相似类向量融合对特征进行了转化,因此对准确率的提升有一定影响;4) MBL 策略主要划分森林结构和平衡中间数据倾斜,因此对准确率影响不大。综上,以上4 种策略能有效应对大数据分类问题,且能有效提高算法加速比和准确率。

4 结束语

为解决深度森林算法在处理大数据存在的不足,本文提出了PDF-STWII 算法。首先,提出了FSFI 策略以消除原始特征中存在的大量冗余及无关特征;其次,提出了MGVE 策略,通过将相似的2 个类向量合并为一个类向量,解决了多粒度阶段中产生的类向量过长问题;随后,提出了CFFE策略,通过密集连接增广特征,提高信息利用率,加快了模型收敛速度;最后,提出了MLB 策略,通过自适应子森林划分和异构倾斜数据划分,解决了模型并行化训练效率低的问题。实验结果表明,PDF-STWII 算法在处理大数据问题时具有良好的并行化训练效率和分类性能。

虽然PDF-STWII 算法在并行化训练效率和分类精度上有了一定的提升,但仍存在以下不足:1)在多粒度向量消除策略中,利用求均值的方式将2 个向量融合为一个向量会丢失部分信息;2) 在大数据环境中,本文算法难以有效处理不平衡数据分类问题。上述问题将作为未来的重点研究对象。

猜你喜欢

级联粒度向量
向量的分解
粉末粒度对纯Re坯显微组织与力学性能的影响
聚焦“向量与三角”创新题
基于矩阵的多粒度粗糙集粒度约简方法
级联LDPC码的STBC-OFDM系统
基于粒度矩阵的程度多粒度粗糙集粒度约简
向量垂直在解析几何中的应用
基于级联MUSIC的面阵中的二维DOA估计算法
向量五种“变身” 玩转圆锥曲线
LCL滤波器在6kV级联STATCOM中的应用