分布式随机森林框架的构建

第3章分布式随机森林框架的构建大规模数据的出现对数据的存储和处理能力提出了新的挑战，传统基于单机的方法已无法满足大数据的需要，所以基于分布式的数据存储与处理框架被提出本章节提出了分布式交替方向乘子法用于处理不平衡大数据的分布式优化问题，将数据不平衡问题转化为两个子问题，即单节点正负样本不平衡问题与节点间数据样本不平衡问题。本文在单节点内部使用随机森林作为分类器，在节点间使用ADMM算法的全局一致性框架解决不平衡大数据分类问题。分布式随机森林算法框架随着大数据的兴起，分布式机器学习算法作为机器学习算法的扩展被提出。往往因为大数据的数量巨大，结构复杂等特性，传统的机器学习算法已不再能够满足其需求。分布式机器学习通过分布式与并行化处理大数据的全局优化问题，将一个全局任务分割为若干个不同的小规模任务，在各节点并行化的基础上，通过建立全局一致性框架来得到最终模型。目前采用的分布式机器学习算法往往基于各节点之间的全局一致性，即在各节点独立计算的基础上添加一致性约束，因此在各节点得到自身局部变量后，通过节点间的协调一致来实现全局优化。图3.1为本文提出的分布式随机森林算法框架。图3.1分布式随机森林算法框架如上文所说构建本文的分布式随机森林框架，如图，各子节点内采取上文中代价敏感随机森林算法进行局部样本子集分类，从而得到局部变量w，然后在i各子节点之间应用交替方向乘子法，通过更新局部变量得到全局变量Z,并通过不断迭代得到全局最优值。3.2基于CS-ADMM的全局一致性框架ADMM算法在进行机器学习过程中，是一种非常常见的优化方法，能够用来处理携带约束最小化问题，因为该法具备可分解性和优秀的收敛性，从而被用于求解分布式优化问题。其通过将原始问题分解为若干个较小的子问题，并通过子问题之间的协调一致实现全局优化。本章节将对ADMM算法的分解过程进行具体论述。原始ADMM主要用于求解两个函数之和最小化的凸优化问题，且函数之间具有一定线性约束。在分布式ADMM中,原始问题应该是可分解的，假设此时两个目标函数为f(x)和Q(x)，且两个目标函数之一f(x)是可分解的，那么可以得到原始目标函数:(3.1)min工f(x)+o(z)(3.1)iixiA,xn,xAls.t.Ax+Bz=C,i=1,2,K,n.i其中x=(x,A,x)。函数(3.15)即为分布式ADMM的全局目标函数。其最优解1 n可表示为：(3.2)p*=inf{f(x)+0(z)IAx+Bz=C}(3.2)本文采用代价敏感随机森林算法作为分类模型，由于对损失函数的重新构造,原始问题可表示为：min1IIWII2+C(c工 g+c工g)w2 pxjeD+jnxjeDrj其中C是惩罚参数且大于0，g表示误分类样本x的代价，c和c分别是j j p n正样本和负样本的误分类代价参数。通过将原始问题转化为全局一致性问题，原始问题可以重构为：min1IIzII2+C工(c工g+c工g) (3.3)2w. WnzP j n ji=1 xgD+ xeD~ji jis.t.w=z,i=1,2,...,n.i其中w为局部变量，应满足全局变量z的全局一致性。可以通过增广拉格朗i日函数可将上式表示为:TOC\o"1-5"\h\z\o"CurrentDocument"Lp(w,z,九)=—IIzII2+C工(c +c) (3.4)2 pjnji=1 xgD+ xgD_ji ji+工(Xt(w一z)+—IIw一zII2)ii 2ii=1其中X是对偶变量，p是增广拉格朗日函数的惩罚系数。将一次项和二次项合并,i上式可以重新表示为：TOC\o"1-5"\h\z\o"CurrentDocument"Lp(w,z,u)=0(z)+Z(f(w)+PIIw-z+qII2) (3.5)ii2i ii=1其中f(w)是子问题i的数据集D在当前训练模型下的损失函数。因此可得到ii iCS-ADMM框架的优化步骤为：wk+1=argminf(w)+PIIw一zk+耳kII2i wjii2i i\o"CurrentDocument"zk+1=argming(z)+-P^nIIwk+1一z+耳kII2 (3.6)z 2 i=1i i耳k+1=耳k+wk+1—zk+1i i iCS-ADMM算法的大概流程如算法1所示：_算法1CS-ADMM Input:Output:optimizationvariables,1：fork=0,l,...,do5:endfor3.3基于对偶坐标下降法的子节点优化在本章内容中，本文采用对偶坐标下降法算法进行子节点的优化，这一种算法主要是由子问题逐渐转变成对偶问题［25］，按照对偶变量来对问题进行优化处理进而实现子问题的局部变量更新。一般来说，原始问题的拉格朗日函数可以表示为：3.7)Lp(w,g)=EIIw-vII2+3.7)i 2ii pj njxgD+ xgD-jiji+ylia(1-g-ywx)-ylipgj jjij jjTOC\o"1-5"\h\zj=1 j=1jj个变量分别进行求导其中a和B是拉格朗日乘子，l是数据集D中样本的个数，对于w和g两jj个变量分别进行求导ol(w,g) / 、y一pi二p(w-v)-2Layx二0,ow ii jjji j=13.8)3.9)3.10)o3.8)3.9)3.10)p二c*C-a-p二0,xgD+,og p jj jijoL(w,g)p二c*C-a-p二0,xgD-.Og n jjjij将上述求偏导的公式合并，可以将原始问题的拉格朗日函数写为L(w,g)=--^工为aayyxtx+ylia(1-yvTx)pi 2p jtjtjt j jijTOC\o"1-5"\h\zj=1t=1 j=1对偶坐标下降法的优化过程首先将上式改写为其对偶问题，可得到minf(a)=—aTQa-bra,a 2ps.t・0<a<C, j=1,・・・,ljj i其中Q=yyxTx。当x为正样本时，误分类代价参数C=c*C；为负样jtjtjt j jp本时，C=c*C。对于上式的优化，对偶坐标下降法通过控制对偶变量的其他jn维度来优化某一特定维度。因此在第k次迭代中，关于a的偏导为：

(3.11)Vf(w)二1史wQ-b二ywrx-1

j p (3.11)然后将Vf(ar)在ar的取值范围内进行映射，由此可得a的更新可以表示为:Vf(ak)ak+i=min(max(ak一j,0),C).

j j为:Vf(ak)ak+i=min(max(ak一j,0),C).

j jQ j(3.12)映射梯度可以重构为:Vf(ak)=ywkx一1(3.13)因此可以得到局部变量w的更新步骤:wk+1=wk+(ak+1—ak)yx(3.14)得到局部变量后，根据局部变量和其对偶变量对全局变量进行更新。在分布式ADMM算法中，全局变量zk+1的目标函数可表示为：zk+1=argming(z)+ 乙IIwk+1一z+耳k||22 i iz i=1(3.15)因此，通过对ws和耳s两个变量的简单平均，可以全局变量zk+1。显然，目标i i函数对于全局变量应该是可微的，因此，通过对其目标函数求关于zk+1的偏导，则可由wk+1和qk两个变量的加权之和得到全局变量：zk+1=工(wk+1+qk)(3.16)很显然，本文提出的对偶问题(3.10)和文献［25］中提出的SVM-ADMM算法的对偶问题具有一定相似性。同时一些研究［25-26］己经证明了对偶坐标下降算法够在o(log(1/Y))迭代中收敛到y精度，即f(a)<f(a*)+Y。所以本文通过将单节点的对偶问题(3.10)和对文献的分析成果相联系，然后在子问题的优化过程中，对偶坐标下降法同样可以获得y精度的收敛结果。第4章分布式随机森林框架的应用数据集与实验环境在实验部分，本文采用公开广泛使用的不平衡数据集dosvsnormal,并从这些数据集里面随机选择一个二分类数据集来为分类提供研究。此数据集共包含4856151个样本，共有41维特征，正负样本的不平衡率为3.99。本文使用Hadoop与KVM虚拟化平台搭建虚拟化集群环境，实验环境共包括五个节点。每个节点的内存为4GB,操作系统为CentOS6.2,节点间采用MPI并行化接口。分布式框架中各节点可以采取不同的体系结构,即节点之间的逻辑结构。也可以采取不同的通信协议。体系结构和通信协议影响着节点间的消息传递机制和通信。本文采用基于同步通信模式的中心化网络结构,如图4.1所示。图4.1节点网络拓扑结构如图所示,中心化结构采取主从模式,即节点体系结构中有4个从节点和一个主节点,通过从节点之间的传递信息以及主节点进行调控。每个从节点自行进行分类任务,后将自身局部变量传递至主节点,主节点基于所有子节点的局部变量进行全局变量的优化,后广播至所有节点,此过程在得到全局最优解之前将不断迭代。同步通信是分布式ADMM的通信协议之一，同步通信要求主节点在接收到所有从节点的局部变量之后,才进行全局变量的更新。这是一种较为严苛的全局约束,因为它要求网络中的所有节点采用协作的模式,同步的执行子问题的优化。

实验结果分析为了评估本文提出的基于代价敏感的随机森林算法(CSRF)对于不平衡数据样本的分类有效性，本文在单节点上进行了分类实验，与原始随机森林算法图4.2CSRF与RF算法对比(RF)进行了对比。实验设置节点内样本个数为10a5不变，采用随机抽样的方法，分别抽取正负样本的不平衡率为1,1.5,2,2.5,3,3.5,4。误分类代价参数(c,c)按照经验设置为(IR,图4.2CSRF与RF算法对比如图所示，随着不平衡率的增加，原始随机森林算法(RF)与代价敏感随机森林算法(CSRF)的分类准确度都有所下降，但是CSRF算法的F-值始终高于RF算法。而且当不平衡率为2.5至4时，CSRF算法的F-值只有轻微下降，证明了该算法具有一定的鲁棒性。可见，本文提出的代价敏感随机森林算法在不平衡分类任务上是更有效的。基于此结果，本文在多节点环境中评估了分布式框架对于不平衡大数据的分类效果。以证明本文所提及的CS-ADMM算法的分类效果，把几种ADMM算法和本论文中的算法进行比对。对比分布式算法的具体情况为：ADMM—DCD:在分布式ADMM算法中，对偶坐标下降算法被用来解决子问题的优化。ADMM—TRON:在分布式ADMM算法中，对于优化子问题，选择信任域牛顿法。CS—ADMM—DCD：在分布式ADMM中，采用扩展对偶坐标下降对子问题进行优化，同时子节点内部采用基于代价敏感的随机森林算法。CS—ADMM—TRON:在分布式ADMM算法中，通过信任域牛顿法对子问题进行优化，同时子节点内部采用基于代价敏感的随机森林算法。实验中设置每个节点的样本数量为5x10a5不变，且在每个节点内部抽取正负样本比率为3:1，实验反复进行十次，主要是为了提高研究结果的准确性，并且最终选择最终结果的平均值，对本文的算法和其他对比算法的分类性能进行对比。本文采用几何平均值(GeometricMean，GM)和卩-F值(F-Measure，FM)作为准确度评估标准，采用训练时间作为算法效率评估指标，其中训练时间包括节点内部的计算时间与节点之间的通信时间。实验结果如表4.1所示。表4.1CS-ADMM算法实验结果ADMM-DCDADMM-TRONCS-ADMM-DCDCS-ADMM-TRONFM(%):F-值95.7694.9296.9395.57GM(%):几何平均数96.9195.0797.2596.33Ttim(s):训练时间72.5071.7479.1780.25由实验结果可得，DCD算法的精度相对TRON相对较高，且具有较少的训练时间，即可证明此算法对于不平衡大数据分类的有效性。因为在进行优化时，对偶坐标下降法的时间复杂度是O(nk),nk是所有训练样本中非零元素之和。但是信任域牛顿法算法的复杂度是O(dnk)，其中d代表共轭梯度的迭代次数。而且，牛顿法采用海森矩阵，但是在样本数量较大时，海森矩阵是一个庞大的方阵，对其计算需要花费巨大开销。综上所述，使用牛顿法来解决大规模数据的分布式分类问题的局限性。对于超参数的取值，本文通过五折交叉验证从区间2i(i=-3，..,8)选取超参数C。另外，为了验证超参数对CS-ADMM-DCD算法的影响，本文分析了超参数C的取值从2-3到28，GM和FM曲线的变化趋势，实验结果如图4.3。当超参数C逐渐变大，FM和GM值也随之变大，波动逐渐平缓。总而言之，本文提出的基于对偶坐标下降法的CS-ADMM框架在不平衡大数据分类上效果较好，具有一定的鲁棒性。图4.3F值和几何平均数随着超参数C的变化趋势算法鲁棒性分析如前文提到的，在实际生活中，数据来源复杂混乱，本身具有一定的不平衡性。在将数据