基于Spark和三路交互信息的并行深度森林算法.pdf
《基于Spark和三路交互信息的并行深度森林算法.pdf》由会员分享,可在线阅读,更多相关《基于Spark和三路交互信息的并行深度森林算法.pdf(13页珍藏版)》请在咨信网上搜索。
1、2023 年 8 月 Journal on Communications August 2023 第 44 卷第 8 期 通 信 学 报 Vol.44 No.8基于 Spark 和三路交互信息的并行深度森林算法 毛伊敏1,2,周展1,陈志刚3(1.江西理工大学信息工程学院,江西 赣州 341000;2.韶关学院信息工程学院,广东 韶关 512026;3.中南大学计算机学院,湖南 长沙 410083)摘 要:针对并行深度森林在处理大数据时存在冗余及无关特征过多、类向量过长、模型收敛速度慢以及并行化训练效率低等问题,提出了基于 Spark 和三路交互信息的并行深度森林(PDF-STWII)算法。首
2、先,提出基于特征交互的特征选择(FSFI)策略过滤原始特征,剔除无关及冗余特征;其次,提出多粒度向量消除(MGVE)策略,融合相似类向量,缩短类向量长度;再次,提出级联森林特征增强(CFFE)策略提高信息利用率,加快模型收敛速度;最后,结合 Spark 框架提出多级负载均衡(MLB)策略,通过自适应子森林划分和异构倾斜数据划分,提高并行化训练效率。实验结果表明,所提算法能显著提升模型分类效果,缩短并行化训练时间。关键词:Spark 框架;并行深度森林算法;特征选择;多级负载均衡 中图分类号:TN92 文献标志码:A DOI:10.11959/j.issn.1000436x.2023143 Pa
3、rallel deep forest algorithm based on Spark and three-way interactive information MAO Yimin1,2,ZHOU Zhan1,CHEN Zhigang3 1.School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou 341000,China 2.College of Information Engineering,Shaoguan University,Shaoguan 512026,China
4、 3.College of Computer Science and Engineering,Central South University,Changsha 410083,China Abstract:To address issues such as excessive redundancy and irrelevant features,long class vectors,slow model con-vergence,and low efficiency of parallel training in parallel deep forests,a parallel deep fo
5、rest algorithm based on Spark and three-way interactive information was proposed.Firstly,a feature selection based on feature interaction(FSFI)strat-egy was proposed to filter the original features and eliminate irrelevant and redundant features.Secondly,a mul-ti-granularity vector elimination(MGVE)
6、strategy was proposed,which fused similar class vectors and shortened the class vector length.Subsequently,the cascade forest feature enhancement(CFFE)strategy was proposed to improve the utilization of information and accelerate the convergence speed of the model.Finally,a multi-level load balancin
7、g(MLB)strategy was proposed,combined with the Spark framework,to improve the parallelization efficiency through adaptive sub-forest division and heterogeneous skew data partitioning.Experimental results demonstrate that the proposed algo-rithm significantly improves the model classification effect a
8、nd reduces the parallelization training time.Keywords:Spark framework,parallel deep forest algorithm,feature selection,multilevel load balancing 收稿日期:20230417;修回日期:20230701 通信作者:陈志刚, 基金项目:广东省重点提升基金资助项目(No.2022ZDJS048);科技创新 2030-“新一代人工智能”重大基金资助项目(No.2020AAA0109605)Foundation Items:Key Promotion Proje
9、ct of Guangdong Province(No.2022ZDJS048),“2030 Innovation Megaprojects”-NewGeneration Artificial Intelligence Project(No.2020AAA0109605)第 8 期 毛伊敏等:基于 Spark 和三路交互信息的并行深度森林算法 229 0 引言 深度森林是 Zhou 等1提出的一种基于决策树结构的深度学习模型,其包含多粒度扫描和级联森林两大组成部分,因其超参数少、参数敏感度低及模型深度自适应等优点,已被广泛应用于网络流量分类2、文本分类3、故障诊断4、目标识别5、恶意代码分类6
10、等领域。然而,随着新一代信息技术的革新和大数据时代的来临,各领域将产生亟待处理的海量数据,这些数据通常表现出数据量大、数据价值密度低等特性,深度森林难以有效处理这类数据,因此如何设计出适合处理大数据问题的深度森林算法已成为一大研究热点。Spark7作为专门处理大规模数据问题开发的并行计算框架,因其出色的计算能力和良好的通用性,被广泛应用于企业项目开发和学术研究中。文献8提出了用于退网用户预测的并行深度森林(PDF-OGUP,parallel deep forest for off-grid user prediction)算法,为节省多粒度扫描阶段的空间占用,设计了基于下标的扫描算法,并以随机
11、采样构建随机森林的方式减少所需内存空间。针对网络入侵问题,文献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)算法。首
12、先,该算法使用 BLB(bag of little bootstrap)自助采样法替换传统采样法,减少了大量特征在级联森林各层级中的传输,提高了计算效率和通信效率;其次,提出自适应子森林划分算法,以确保每个子森林并行计算的资源利用率最大化;最后,利用轮询机制来实现节点的负载均衡。以上列举的3 种并行深度森林算法虽然在训练效率上有了一定的提升,但仍然存在以下不足。1)在特征选择阶段,无法有效去除原始数据携带的大量冗余和无关特征,导致后续模型训练过程中存在冗余及无关特征问题。2)在多粒度扫描阶段,输入的原始特征经过滑动窗口扫描后,将产生大量的特征子序列,拼接多个输出的类向量将导致类向量过长问题。3
13、)在级联森林训练阶段,级联森林的每一层都将拼接原始特征和上层特征作为本层输入,但相对于原始特征的维度,每层转化后的增广特征的维度则要小得多,这将导致增广特征被淹没11,使模型收敛速度缓慢。4)在模型并行化训练阶段,子森林的划分粒度不能依据模型训练效果自适应确定,加之异构节点情况下存在中间数据倾斜,将导致模型并行训练效率低下。针对上述问题,本文提出了基于 Spark 和三路交互信息的并行深度森林(PDF-STWII,parallel deep forest algorithm based on spark and three-way interactive information)算法,其主要工
14、作如下。1)提出基于特征交互的特征选择(FSFI,fea-ture selection based on feature interaction)策略,通过消除原始特征中存在的大量冗余及无关特征,解决了冗余及无关特征过多的问题。2)提 出 多 粒 度 向 量 消 除(MGVE,mul-ti-granularity vector elimination)策略,通过将多粒度扫描产生的任意 2 个相似类向量融合为一个向量,解决了多粒度扫描过程中产生的类向量过长问题。3)提出了级联森林增强(CFFE,cascade forest feature enhancement)策略,密集连接所有级联层输出的增
15、广特征的同时动态缩减部分原始特征,解决了模型收敛速度慢的问题。4)提出了多级负载均衡(MBL,multi-level load balancing)策略,通过自适应子森林划分(ASFS,adaptive sub-forest splitting)算法控制森林划分粒度和异构倾斜数据划分(HSDP,heterogeneous skew data partition)算法平衡异构数据的倾斜,提高了模型的并行化训练效率。1 相关概念介绍 定义 1 互信息12常用来衡量变量之间的相关性程度,互信息越大,变量间的相关性越强,反之,则相关性越弱。反映随机变量if和jf 相关性的互信息(;)ijI ff可定义
16、为 (;)()(|)ijiijI ffH fH ff(1)其中,()iH f为变量if 的信息熵,表示变量不确定性程度;(|)ijH ff为变量jf 确定时if的条件熵(;)min(),()ijijI ffH ff。定义 2 对称不确定性13常用于相关特征选取,其通过归一化互信息修正了互信息在选取特征时存在的偏置。2个随机变量if和jf的对称不确定230 通 信 学 报 第 44 卷 性SU(,)ijff可定义为 2(;)SU(,)()()ijijijI ffffH fH f(2)从式(2)可知,SU(,)0,1ijff。定义 3 三路交互信息14作为互信息的扩展可用来度量特征之间的交互性,其
17、值可为正数、零和负数。当三路交互信息为正数时,2个特征共同对标签提供的信息大于它们单独对标签提供信息的和,此时2个特征存在互补性;当三路交互信息为负数时,2个特征对标签提供的信息存在冗余;当三路交互信息为零时,2个特征提供给标签的信息是独立的。对于特征if和jf及标签C,三路交互信息(;)ijI ff C可表示为 (;)(,)ijijI ff Cp ff C (,)(,)(,)log()()()ijijijp ffp f C p f Cp fp fp C(3)其中,()()()ijp fp fp C为三者的联合概率。定义 4 近似马尔可夫毯15可用于冗余特征的检验,如果特征jf是特征if的近似
18、马尔可夫毯,则2个特征之间存在冗余,SU(,)SU(,)jif Cf C和SU(,)SU(,)jiifff C同时成立。定义 5 皮尔逊相关系数常用来衡量2个向量之间的相似程度,取值范围为 1,1,其绝对值越大,相关性越强。当取值为正时,2个向量呈正相关,当取值为负时,2个向量呈负相关;当取值为零时,2个向量无关。皮尔逊相关系数定义为 E()()cov(,)(,)XYXYXYXYX YP X Y 2222E()E()()E()E()E()E()XYX E YXXYY(4)其中,cov(,)X Y表示2个向量之间的协方差,X和Y分别表示向量X和向量Y的标准差,表示向量均值,E表示数学期望值。2
19、PDF-STWII 算法说明 PDF-STWII算法主要包括4个阶段:特征选择、多粒度扫描、级联森林训练、模型并行化训练。各阶段的主要任务如下。1)特征选择。提出FSFI策略,通过度量特征的相关性和冗余度,消除大量冗余及无关特征,同时挖掘出存在交互作用的特征,过滤大量冗余及无关特征。2)多粒度扫描。提出MGVE策略,融合任意2个相似类向量,缩短类向量长度。3)级联森林训练。提出CFFE策略,密集连接各层增广特征,同时逐层削减部分特征,防止增广特征被淹没,加快模型收敛速度。4)模型并行化训练。提出了MBL策略,其包含两方面内容。在算法并行处理层面,提出ASFS算法,通过分析子森林训练效果,自适应
20、确定森林的划分粒度,提高算法并行度。在数据并行化处理方面,提出了HSDP算法,分析分布式异构环境中各计算节点的性能差异,将中间数据合理分配到各节点,以平衡中间数据倾斜,最终从算法和数据两方面提高模型并行化训练效率。2.1 特征选择 针对原始数据集包含大量冗余及无关特征问题,提出的FSFI策略从特征相关性、冗余度和特征交互三方面综合考虑特征选取,高效剔除冗余无关特征。FSFI包括无关特征过滤、冗余特征消除和特征综合评分。2.1.1 无关特征过滤 在特征选择过程中,由于相对于特征的冗余度和交互性计算,特征的相关性计算更快,所以在特征选择的初始阶段,提出特征相关性系数(FRC)过滤大量无关特征,删除
21、小于相关性阈值的特征,并利用FRC对特征排序。定理 1 特征相关性系数(FRC)。已知数据集n mDR,其中n和m分别为数据的样本量和特征,则if与标签C的相关性系数FRCi定义为 (,)FRCmin(),()iiiI f CDH fH C(5)211111nnsisissDffnn(6)其中,sif表示样本s中if的值。证明 对标签具有较强区分度的特征,通常存在较大的方差,可用标准差反映特征if对类别的区分能力。D为特征if的标准差,标准差越大,特征区分标签类别的能力越强;由互信息定义可知(;)min(),()iiI f CH fH C,互信息的大小受特征和标签信息熵的限制,直接使用互信息来
22、衡量相关性时,具有越大信息熵的特征越有可能被选取,因第 8 期 毛伊敏等:基于 Spark 和三路交互信息的并行深度森林算法 231 此将互信息(;)iI f C除以特征if和标签C的最小信息熵以消除偏置,最终将反映特征区分度的标准差和消除偏置的互信息相乘获得特征相关性系数FRC,证毕。2.1.2 冗余特征消除 经过无关特征初步过滤过程,特征的维度大幅缩减,但冗余特征并未消除,为此,在特征消除阶段提出冗余度指标R来衡量特征之间的冗余程度。冗余消除过程如下。首先,利用近似马尔可夫毯快速判断冗余特征并消除;然后,利用冗余度指标R计算特征间的冗余度,对比冗余度指标和冗余度阈值,进一步消除冗余特征。定
23、理 2 冗余度指标R。已知存在特征if和特征jf,则计算特征间的冗余度指标R可表示为 SU(,)ijRPff(7)SU(,)SU(,)1()()2jiijf Cf CPH fH f(8)证明 SU(,)if C为特征if与标签C的对称不确定性,根据对称不确定性定义可知,SU(,)if C可度量特征if与标签C的相关信息量,同理,SU(,)ijff可度量2个特征之间的相关信息量,反映特征信息重叠大小。()iH f为if的信息熵,表示特征自身信息量的大小。当SU(,)()iif CH f和SU(,)()jjf CH f越大时,在一个确定信息空间中的特征if和特征jf的信息重叠概率也就越大,即越可能
24、存在信息冗余。综上,P可表示冗余概率,SU(,)ijff可表示冗余信息量,冗余概率和冗余信息量联立获得冗余度指标R,证毕。2.1.3 特征综合评分 经过无关特征过滤和冗余特征消除过程,剩余的特征都具有较高质量,为了进一步挖掘出更高质量的特征子集,从特征相关性、冗余度和特征交互性出发,设计特征综合评估函数FSFIJ,获取更优特征子集。定理 3 特征综合评估函数FSFIJ。假设候选特征if与标签C的相关性为(;)iI f C,与已选特征jf的冗余度为(;)ijI ff,候选特征if和已选特征jf对标签的交互性为(;)ijI ff C,特征综合评估函数FSFIJ可表示为 FSFIargmax(;)i
25、ifFJI f C(;)(;)(;)max(;)jsiijijfFiI f CI ffI ff CI f C(9)其中,F表示候选特征集,sF表示已选特征集。证明 特征评估函数FSFIJ的目标在于每次从候选特征集F中选取好的特征if使评估函数FSFIJ的值最大,好的特征应具有高相关性,且与已选特征具有低冗余度和高交互性,反映在函数中分别对应(;)iI f C、(;)(;)(;)iijiI f CI ffI f C、(;)ijI ff C。当候选特征if与标签C的相关性较高时,(;)iI f C越大,(;)(;)(;)iijiI f CI ffI f C越大,FSFIJ越大,候选特征if越容易被
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 Spark 交互 信息 并行 深度 森林 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。