没有合适的资源?快使用搜索试试~ 我知道了~
结合信息论和范数的并行随机森林算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 87 浏览量
2022-11-28
20:29:41
上传
评论
收藏 375KB DOCX 举报
温馨提示
试读
23页
结合信息论和范数的并行随机森林算法.docx
资源推荐
资源详情
资源评论
分类算法是一种有监督的学习算法,它能够根据有标记的信息发现分类规
则、构造分类模型,从而预测未含标记的数据属性特征
[1]
。在分类算法中,随机森
林(random forest,RF)以其具有稳定性强、对噪声和异常值有较好容忍性等
特点
[2]
,近年来已被应用于文本分类
[3]
、环境预测
[4]
、信用评估
[5]
、生物信息
[6]
、
医疗诊断
[7]
等领域,受到人们的广泛关注。
随着信息技术和网络技术的发展,大数据成为研究热点,相 较于 传统 数据 ,
大数据具有 4V 特性——Volume(数量大)、Variety(种类多)、Velocity(速
度快)、Value(价值密度低)
[8]
,这使得传统随机森林算法在处理大数据时所
需运行时间较长,内存容量较多,且通过提升计算机硬件水平来满足人们对大数
据分析与处理的需求,显得尤为困难。此时并行化的计算思想变得非常重要,通
过改进传统的随机森林算法并与分布式计算模型相结合成为当前研究的主要
方向。
近年来在大数据处理方面,Google 开发的 Map-Reduce 并行编程模型由于
操作简单、自动容错、扩展性强等优点深受广大学者和企业的青睐。同时,以
Hadoop、Spark 为代表的分布式计算架构也受到了越来越多的关注
[9]
。目前许
多基于 MapReduce 计算模型的随机森林算法已成功应用到大数据的分析与处
理领域中。其中,基于 MapReduce 的并行化随机森林算法 MR_RF
[10]
,采用分而
治之的思想,调用 Map-Reduce 模型将数据分区后传递给多个计算节点构建基
分类器,汇聚每个计算节点输出的基分类器得到随机森林模型。接着,再次调用
MapReduce 模型,利用构建好的随机森林对测试集进行预测得到分类准确度,
实现了随机森林算法的并行化,但该算法前后调用两次并行化框架,中间结果多
次的读出和写入,消耗了大量的时间。为了降低 MR_RF 算法的时间复杂度,钱
雪忠等人提出了一种改进的 MR_RF 算法
[11]
,利用袋外数据直接计算出分类模
型的泛化误差,以此判断随机森林的分类准确率,减少了调用并行框架的次数。
然而在大数据环境下,数据集中大量的冗余以及不相关特征降低了构建随机森
林模型时决策树所选特征的质量,进而影响了随机森林模型整体的分类准确度。
为降低大数据集中的冗余与不相关特征对模型的影响,Chen 等人提出了一
种并行随机森林算法 (parallel random forest,PRF)
[12]
,通过计算特征信息增
益率的方式,选出最优的 K 个训练特征与其余训练特征随机搭配,对训练特征降
维,并利用袋外数据作为训练集计算出每棵决策树对应的分类准确度作为权重,
用于模型预测阶段。虽然 PRF 算法优化了训练特征,提升了随机森林的分类准
确度,但没有减少数据集本身冗余与不相关特征的个数,故生成的训练特征集依
然还有较多的冗余与不相关特征;针对以上情况,Hu 等人提出了一种基于最大
信息系数的并行随机森林算法 PRFMIC
[13]
,通过计算最大信息系数将特征分为
三个区间,删除低相关区间的特征,选取高相关区间和中相关区间内的特征组成
特征子集,并行构建随机森林模型,算法虽然考虑到了不相关特征对随机森林模
型的影响,但数据中存在的冗余特征在随机森林建模阶段非但不能提供有效的
信息,而且增加了决策树与决策树之间相关性,影响随机森林模型整体的准确度;
此外,上述算法在生成训练特征集时未考虑到训练特征的信息量,由低信息量的
训练特征集训练出的决策树影响了随机森林整体的准确度;同时,算法在预测分
类阶段,由于负载不平衡造成该阶段所需时间过多,影响了随机森林整体的并行
化效率。如何减少大数据集中冗余与不相关特征,如何提高训练特征信息量以
及如何提升算法的并行效率等仍然是目前亟待解决的问题。针对这些问题,本
文 提 出 了 基 于 信 息 论 和 范 数 的 并 行 随 机 森 林 算 法 ( parallel random forest
algorithm based on information theory and norm,PRFITN)。首先,该算法 基
于信息增益和 Frobenius 范数设计了一种混合降维策略 DRIGFN(dimension
reduction based on information gain and Frobenius norm),获得降维后的数
据集,有效减少了冗余及不相关特征数;此外,算法提出了一种基于信息论的特征
分组策略(feature grouping strategy based on information theory,FGSIT),
根据 FGSIT 策略将特征分组,采用分层抽样方法,保证了随机森林中决策树构
建时特征子集的信息量,提高了分类结果的准确度;最后,考虑到集群负载对并行
算法效率的影响,在 Reduce 阶段提出了一种键值对重分配策略(redistribution
of key-value pairs,RSKP),获取全局的分类结果,实现了键值对的快速均匀分
配,从而提高了集群的并行效率。实验结果表明,该算法在大数据环境下,尤其是
针对特征数较多的数据集有更好的分类效果。
1 算法及 相关概念 介绍
1.1 相 关 概 念 介绍
定义 1(信 息增益
[14]
) 已知 离散 变量 X 和其对应的类 别 Z,则信息 增益
IG(Z;X)由下式计算:
IG(Z;X)=H(Z)-H(Z|X)
(1)
其中,H(Z)为关于类别 Z 的信息熵,H(Z|X)为关于变量 X 和类别 Z 的条件熵。
定义 2(互信息
[15]
) 已知离散变量 X、Y,则互信息 I(X;Y)由下式计算:
I(X;Y)=∑i=1l∑j=1mp(xi,yj)lbp(xi,yj)p(xi)p(yj)
(2)
定义 3(条件互信息
[16]
) 已知离散变量 X、Y 以及它们对应的类别 Z,则条
件互信息 I(X;Y|Z)由下式计算:
I(X;Y|Z)=H(X|Z)-H(X|Y,Z)
(3)
其中,H(X|Z)为关于变量 X 和类别 Z 的条件熵,H(X|Y,Z)为关于变量 X、Y
和类别 Z 的条件熵。
定义 4(Frobenius 范数
[17]
) 已知 A=(aij)m×n∈Rm×n 为一个 m×n 维的
矩阵,aij 为矩阵中的元素,则 Frobenius 范数||X||F 可以由下式计算:
||X||F=∑i=1m∑j=1naij2
(4)
1.2 相 关 算 法 介绍
1.2.1 主成 分 分析 算法
主成分分析算法(principal component analysis,PCA)
[18]
是一种降维的多
元统计方法,其主要目的是在保持最大变异条件下,寻找到一个转换矩阵 W,降
低数据集的维度。PCA 算法主要分为 4 个步骤:(1)建立数据矩阵,对原始数
据集进行标准化处理;(2)建立相关系数矩阵并计算各主成分的特征值 λ 与对
应的特征向量个数;(3)依据特征值和累计贡献率,确定所需主成分的个数;(4)
组合主成分对应的特征向量,得到转换矩阵 W 对原数据集降维。
1.2.2 支持 向 量机 算法
支持向量机算法(support vector machine,SVM)
[19]
是建立在统计学理论
基础上的数据挖掘算法,主要通过选择一个满足分类要求的最优分类超平面,使
得 该 超 平 面 在 保 证 分 类 精 度 的 同 时 ,能 够 使 超 平 面 两 侧 的 空 白 区 域 最 大 化 。
SVM 算法主要分为 3 个步骤:(1)构建分类超平面 f(x)=υTX,其中 υ 是超平
面的权值,X 是数据向量矩阵;(2)利用核函数求解分类超平面,得到超平面权
值 υ;(3)利用超平面权值 υ 预测数据分类。
2 PRFITN 算法
PRFITN 算法主要包括三个阶段:数据降维、特征分组和并行构建随机森
林。(1)在数据降维阶段,提出 DRIGFN 策略,准确地识别和删除数据集中的
冗 余 和 不 相 关 特 征 ,获 得 降 维 后 的 数 据 集 DB*;( 2 ) 在 特 征 分 组 阶 段 , 提 出
FGSIT 策略用于度量特征的重要性,并在此基础上循环分配特征,以此获得两组
特征子集、Q、S;(3)在并行构建随机森林阶段,提出 RSKP 策略用于优化
MapReduce 计算模型,提升其并行化效率,并利用优化后的 MapReduce 模型并
行构建随机森林、预测数据集分类,得到随机森林的准确度。
2.1 数 据 降 维
目前,降维算法主要包括特征选择和特征提取两个方向,然而在大数据环境
下,由于数据集中存在大量冗余与不相关特征,故单独使用特征选择或特征提取
方法,都无法获得较优的特征集合。针对这一问题,本文提出 DRIGFN 策略用于
识别和过滤大数据环境下的冗余和不相关数据。首先结合 MapReduce 模型,并
行计算特征信息增益值,以此删除不相关特征;接着利用 Frobenius 范数评估信
息损失量、分类误差以及控制分类器过拟合,并在此基础上提出全局优化函数
用于迭代优化降维参数。假设 X=[x1,x2,…,xd]∈Rn×d 表示原始数据集 DB 的
d 维特征空间中的 n 个样本,数据集 DB 包含 υ 个不同类别,Y∈Rn×1 表示特征
矩阵 X 所对应的标签,则 DRIGFN 策略如下:
2.1.1 特征 选 择
对于数据集 DB,特征选择的主要目的是减少不相关特征的数量。其具体过
程为:首先,使用 Hadoop 中默认的文件块策略,将原始数据集的特征空间划分
成 大 小 相 同 的 文 件 块 Block; 接 着 , 文 件 块 Block 作 为 输 入 数 据 , 根 据 定 义
1,Mapper 节点通过调用 Map 函数以键值对<key,value>的形式统计出每个特
征的信息增益(key 为特征名称,value 为对应特征的信息增益),组合每个键值
对得到特征信息增益集合;最后,根据特征对应的信息增益值对集合 A 中元素降
序 排 列 , 移 除 集 合 A 中 排 序 较 为 靠 后 的 特 征 , 重 新 组 合 得 到 新 的 特 征 矩 阵
剩余22页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3574
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功