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

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

大规模数据的出现对数据的存储和处理能力提出了新的挑战，传统基于单机的方法已无法满足大数据的需要，所以基于分布式的数据存储与处理框架被提出。本章节提出了分布式交替方向乘子法用于处理不平衡大数据的分布式优化问题，将数据不平衡问题转化为两个子问题，即单节点正负样本不平衡问题与节点间数据样本不平衡问题。本文在单节点内部使用随机森林作为分类器，在节点间使用ADMM算法的全局一致性框架解决不平衡大数据分类问题。

3.1 分布式随机森林算法框架

随着大数据的兴起，分布式机器学习算法作为机器学习算法的扩展被提出。往往因为大数据的数量巨大，结构复杂等特性，传统的机器学习算法已不再能够满足其需求。分布式机器学习通过分布式与并行化处理大数据的全局优化问题，将一个全局任务分割为若干个不同的小规模任务，在各节点并行化的基础上，通过建立全局一致性框架来得到最终模型。目前采用的分布式机器学习算法往往基于各节点之间的全局一致性，即在各节点独立计算的基础上添加一致性约束，因此在各节点得到自身局部变量后，通过节点间的协调一致来实现全局优化。图3.1为本文提出的分布式随机森林算法框架。

图3.1 分布式随机森林算法框架

如上文所说构建本文的分布式随机森林框架，如图，各子节点内采取上文中代价敏感随机森林算法进行局部样本子集分类，从而得到局部变量wi，然后在各子节点之间应用交替方向乘子法，通过更新局部变量得到全局变量z，并通过不断迭代得到全局最优值。

3.2 基于CS-ADMM的全局一致性框架

ADMM算法在进行机器学习过程中，是一种非常常见的优化方法，能够用来处理携带约束最小化问题，因为该法具备可分解性和优秀的收敛性，从而被用于求解分布式优化问题。其通过将原始问题分解为若干个较小的子问题，并通过子问题之间的协调一致实现全局优化。

本章节将对ADMM算法的分解过程进行具体论述。原始ADMM主要用于求解两个函数之和最小化的凸优化问题，且函数之间具有一定线性约束。在分布式ADMM中，原始问题应该是可分解的，假设此时两个目标函数为f(x)和?(x)，且两个目标函数之一f(x)是可分解的，那么可以得到原始目标函数：

min?f(x)??(z)iixi,?,xn,xi?1n （3.1）

s.t.Axi?Bz?C,i?1,2,?,n.其中x?(x1,?,xn)。函数（3.15）即为分布式ADMM的全局目标函数。其最优解可表示为：

p??inf{f(x)??(z)|Ax?Bz?C} （3.2）

本文采用代价敏感随机森林算法作为分类模型，由于对损失函数的重新构造，原始问题可表示为：

1 min||W||2?C(cp?x?D??j?cn?x?D??j)jijiw2

其中C是惩罚参数且大于0，?j表示误分类样本xj的代价，cp和cn分别是正样本和负样本的误分类代价参数。通过将原始问题转化为全局一致性问题，原始问题可以重构为：

n12 min||z||?C?(cp??j?cn??j) （3.3）

wi,...,wn,z2??i?1xj?Dixj?Dis.t.wi?z,i?1,2,...,n.

其中wi为局部变量，应满足全局变量z的全局一致性。可以通过增广拉格朗日函数可将上式表示为：

n12 L?(w,z,?)?||z||?C?(cp??j?cn??j) （3.4）

??2i?1xj?Dixj?Din??(?Ti(wi?z)?i?1?2||wi?z||2)

其中?i是对偶变量，将一次项和二次项合并，?是增广拉格朗日函数的惩罚系数。上式可以重新表示为：

L?(w,z,u)??(z)??(fi(wi)?i?1n?2||wi?z??i||2) （3.5）

其中fi(wi)是子问题i的数据集Di在当前训练模型下的损失函数。因此可得到CS-ADMM框架的优化步骤为：

wik?1?argminwifi(wi)?zk?1?argminzg(z)??2||wi?zk??ik||2

k?1k2 ||w?z??|| （3.6）iii?1n??2?ik?1??ik?wik?1?zk?1

CS-ADMM算法的大概流程如算法1所示：

算法1 CS-ADMM Input: , Output: optimization variables 1：for k=0,1,..., do 2: 3: 4: 5: end for

3.3 基于对偶坐标下降法的子节点优化

在本章内容中，本文采用对偶坐标下降法算法进行子节点的优化，这一种算法主要是由子问题逐渐转变成对偶问题[25]，按照对偶变量来对问题进行优化处理，进而实现子问题的局部变量更新。

一般来说，原始问题的拉格朗日函数可以表示为：

L?(wi,?)??2||wi?vi||2?C(?c??j?xj?Di?lilixj?Di? ?c?) （3.7）

nj???j(1??j?yjwixj)???j?j

j?1j?1 其中?j和?j是拉格朗日乘子，li是数据集Di中样本的个数，对于wi和?j两个变量分别进行求导：

li?L?(wi,?) ??(wi?vi)???jyjxj?0,

?wij?1?L?(w,?) ?c??C??j??j?0,xj?Di?, （3.8）

??j?L?(w,?)?cn?C??j??j?0,xj?Di?. ??j将上述求偏导的公式合并，可以将原始问题的拉格朗日函数写为：

li1liliT L?(wi,?)???j?tyjytxjxt???j(1?yjviTxj) （3.9）??2?j?1t?1j?1对偶坐标下降法的优化过程首先将上式改写为其对偶问题，可得到：

minf(?)??1T?Q??bT?, （3.10） 2?s.t. 0??j?Cj, j?1,...,li

其中Qjt?yjytxTjxt。当xj为正样本时，误分类代价参数Cj?cp?C；为负样本时，Cj?cn?C。对于上式的优化，对偶坐标下降法通过控制对偶变量的其他维度来优化某一特定维度。因此在第k次迭代中，关于?j的偏导为：

?jf(?)????Q??tt?11lijt?bj?yjw?jxj?1 （3.11）

然后将?jf(??)在??j的取值范围内进行映射，由此可得?j的更新可以表示为：

?k?1j?min(max(??kj?jf(?k)Qjj ,0),Cj). （3.12）

映射梯度可以重构为：

?jf(?k)?yjwkjxj?1 （3.13）

因此可以得到局部变量wi的更新步骤：

?1k wik?1?wik?(?k??jj)yjxj （3.14）

得到局部变量后，根据局部变量和其对偶变量对全局变量进行更新。在分布式ADMM算法中，全局变量zk?1的目标函数可表示为：

zk?1

?argming(z)?z??||w2i?1nk?1i?z??ik||2 （3.15）

因此，通过对wis和?is两个变量的简单平均，可以全局变量zk?1。显然，目标函数对于全局变量应该是可微的，因此，通过对其目标函数求关于zk?1的偏导，则可由wik?1和?ik两个变量的加权之和得到全局变量：

zk?1??(wik?1??ik)i?1n (3.16)

很显然，本文提出的对偶问题（3.10）和文献［25］中提出的SVM-ADMM算法的对偶问题具有一定相似性。同时一些研究［25-26］己经证明了对偶坐标下降算法够在?(log(1/?))迭代中收敛到?精度，即f(?)?f(??)??。所以本文通过将单节点的对偶问题（3.10）和对文献的分析成果相联系，然后在子问题的优化过程中，对偶坐标下降法同样可以获得?精度的收敛结果。