VF-CART算法：垂直联邦学习下的通信高效决策树与随机森林

沙特国王大学学报VF-CART：一种用于CART算法的杨旭a，胡学贤a，魏江红a，b，杨宏建a，李科佳a数学工程与高级计算国家重点实验室，郑州，中国b西安电子科技大学综合业务网络国家重点实验室阿提奇莱因福奥文章历史记录：2022年9月26日收到2022年10月29日修订2022年11月25日接受2022年12月8日网上发售保留字：垂直联邦学习CART决策树同态加密A B S T R A C T随着人们对隐私的日益关注以及现实场景中数据分布在多方之间的事实，垂直联邦学习（VFL）变得越来越重要。使机器学习算法适应VFL设置的趋势越来越明显。决策树和随机森林算法作为一类流行的机器学习算法，在VFL中引起了广泛的兴趣。然而，现有的框架遭受潜在的隐私泄露或高通信消耗。为了缩小这一差距，我们提出了一个通信高效的垂直联邦框架的分类和回归树（CART）算法称为VF-CART，并将其扩展到随机森林（RF）。具体来说，我们将特征值转换为bin值，并为每个特征构建直方图。通过采用哈希函数和同态加密来秘密地选择最佳分割，具有标签的参与者无法获得每个分割的样本子集。此外，在训练和预测阶段，实体之间传输的密文的数量显着减少。没有标签的参与者在树构建阶段仅与第三方服务器通信一次。在预测阶段，只有一个密文必须被发送来预测一个样本。最后，我们使用真实世界和合成数据集进行了实验。实验结果表明，VF-CART算法大大减少了通信量。©2022作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY许可下的文章（http://creativecommons.org/licenses/by/4.0/）。1. 介绍随着大数据的快速发展，机器学习在各个领域发挥着越来越重要的作 用 ， 包 括 自 然 语 言 处 理 （ LeCun et al. （ 2015 ） ; MesonandToutanova（2019）; Raffel et al.（2020）），语音识别（Abdel-Hamid et al. （2014 ）; Hou et al. （2021 b ））和金融风险管理（Andersen et al.（2013）; Yang et al.（2019 b））。数据的可用性是机器学习性能的基础，但它也成为了一个瓶颈。在现实世界的场景中，很难获得大规模的数据集，数据可能分布在*通讯作者。电子邮件地址：xuexian_hu@hotmail.com（X. 胡）。沙特国王大学负责同行审查制作和主办：Elsevier多方参与此外，对数据安全和隐私的关注已成为全球趋势，并已出台法规来规范数据的管理和使用，例如《通用数据保护条例》（Voigt andVon dem Bussche（2017））。因此，数据无法直接传输和共享，这导致了数据孤岛。最近，联邦学习（FL ）（Konecny`etal. （2016 b）;Konecny`etal.（2016 a）;McMahan etal. （2017））由于其能够支持多方协作构建共享模型而受到了相当大的关注。联邦学习的主要思想是在分布于多方的数据集上构建机器学习模型，而不会泄露任何参与者的隐私。为了实现这一目标，必须将一些隐私保护技术应用于联邦学习，例如同态加密 （ HE ） （ Acar et al. （ 2018 ） ） ， 安 全 多 方 计 算 （ MPC ）（Goldreich（1998））和差分隐私（DP）（Dwork（2008））。根据数据分布的特征，联邦学习通常可以分为水平联邦学习（HFL）和垂直联邦学习（VFL）（Yang et al.（2019 a）; Li et al.（2020））。https://doi.org/10.1016/j.jksuci.2022.11.0131319-1578/©2022作者。由Elsevier B.V.代表沙特国王大学出版。这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comY. Xu，X. Hu，J. Wei等人沙特国王大学学报238大多数现有研究（Zhao et al.（2018）; Zhang et al. （2019）;Hamer et al.（2020）; Rothchild et al.（2020）; Ghoshet al.（2020）; Thapa et al.（2022））对FL的研究主要集中在HFL上，HFL假设不同的参与方具有相同的特征空间，但样本ID空间不同然而，与HFL相比例如，在医疗保健的情况下，一组专科医院（传染病医院、心脏病医院、癌症医院等）需要机器学习模型来预测疾病或感染，如COVID。由于工作领域的差异，这些医院从相同的样本中获得不同的特征，并且其中只有一家医院持有标签信息。由于医疗数据的保密性，数据不能共享或汇总给一方。在这种情况下，VFL使这些医院能够打破数据孤岛，扩展特征空间，并在确保数据私密性的同时构建联合模型。因此，已经有许多关于VFL算法的研究，Hardy等人（2017）; Yang等人（2019 c）; Zhou等人（2019）。（2020）; Xia等人（2021）; Xu等人（2021）;Romanini等人（2021）。作为一类流行的机器学习算法，VFL中的决策树和随机森林（Wu et al. （2020）; Liu et al.（2021）;Hou等人（2021 a））引起了广泛的兴趣。然而，这些范例要么有潜在的隐私泄露，要么是通信效率低下。特别是，数据持有者（Liu et al.（2021）; Hou et al. （2021 a））必须将每个分割的样本子集发送给标签的所有者（活动方），这可能导致破坏隐私并导致繁重的通信。基于划分的样本子集，主动方可以找到相似的样本，并且可以能够通过将它们与标签信息组合来推断其他私有信息与上述算法相反，Wu et al. （2020）通过组合HE和MPC是足够安全的。不幸的是，MPC的使用引入了大量的通信，因为计算的加密统计数据需要转换为秘密共享用于后续安全计算的值为了克服这些问题，我们提出了一个通信高效的垂直联邦框架的分类和回归树（CART）算法称为VF-CART。基于CART的特点，整个训练过程只依赖于特征值的顺序而不是它们的实际值，我们将所有的特征值转换为bin值，并为每个特征建立在对样本ID进行散列之后，所有参与者将生成的包含散列ID的直方图发送到第三方服务器。然后，活动方和服务器进行交互并基于直方图构建树。在训练过程中，主动方只能通过同态加密获得关于每个分裂的统计信息，这减少了通信并保护隐私。为了预测一个样本，只需要传输一个密文。安全性分析表明，我们的框架可以保证每个参与者的隐私的假设下，所有参与者是半诚实的。通信分析表明，VF-CART比现有的最先进的算法更有效。我们将我们的贡献总结如下：我们提出了一个垂直的联邦学习框架的CART 算法，称为VF-CART。通过使用散列函数和同态加密来保护粒子的隐私，在这种情况下，VF-CART可以保证活动方不能获得每个分割的样本子集。此外，我们将这一概念扩展到随机森林，并提出了VF-RF。VF-CART通过将特征值转换为bin值并为每个特征构建直方图来显着减少通信量没有标签的被动方在训练阶段只需要与服务器进行一次通信，并且在预测样本时只需要发送一个密文我们在几个真实世界和合成数据集上评估了VF-CART和VF-RF的性能。结果表明，与垂直联邦学习中现有的树模型相比，我们的框架显着提高了训练和预测效率。本文的其余部分组织如下。在第二节中，我们讨论了相关的工作。第3节介绍了这些术语。在第四节中，我们定义了VF-CART的系统模型和威胁模型。第5节详细描述了我们的框架。VF-CART的安全性分析见第6节。第7节描述了实验。最后，我们在第8节结束了本文。2. 相关工作对于垂直分区数据上的隐私保护树模型，Vaidya等人（2008）提出了ID3算法的一个变体。然而，这揭示了给定属性上的类分布。Shen等人（2009）提出了垂直分布数据集上的C4.5算法的一个变体，该变体使双方能够在半诚实第三方的帮助下协作构建决策树。Vaidya等人（2013年）开发了实现隐私保护RF的协议，这些协议能够实现通用和有效的分布式隐私保护知识发现。Dansana等人（2013）证明了CART算法可以用于多方垂直分区环境。为了保护隐私，使用了集合交集协议的安全和和安全大小。Li et al.（2019）介绍了C4.5的一种隐私保护变体，用于多方垂直分区数据。为了安全地计算相关值，基于BCP同态密码系统（Bresson et al. （2003））。Liu et al.（2020）在VFL上下文中考虑了随机森林算法，并提出了联邦森林，其中活动方在加密后将其标签复制给其他方，每一方计算杂质增益并将最大值发送给第三方。然而，一种用于计算不提供基于加密标签的增益。Wu等人（2020）提出了一种新的隐私保护垂直决策树方案，称为Pivot。与Liu等人（2020年）不同，Pivot确保不会披露任何中间信息，但同意发布的参与者除外。然而，在确定每个最佳分割时使用MPC导致大量通信。除了将传统的树模型应用于VFL设置之外，还提出了具有特定特征的算法。例如，RevFRF（Liu et al. （2021））支持参与者撤销，并确保经训练的RF中被撤销的参与者的记忆被安全地移除。 VPRF（Hou et al. （2021 a））是可验证的隐私保护垂直联合随机森林。然而，这两个向量都表示样本划分●●●Y. Xu，X. Hu，J. Wei等人沙特国王大学学报239FG2f···G1/1j·j结果发送给活动方，这导致大量的通信。此外，样本子集对主动方的可用性可能导致灾难性的隐私泄露。SecureBoost（Cheng et al.（2021））是一种使用提升策略的它可以达到与非联邦梯度树提升算法相同的精度Feng等人（2019）提出 了 SecureGBM ， 其 使 得 两 个 参 与 者 能 够 共 同 构 建 共享的LightGBM 模 型 。 Tian 等 人 （2020 ） 提 出 了一 个名 为 VerticalFederBoost的方案，该方案支持运行-在垂直分区的数据上执行GBDT。 如果没有密码-分类和回归任务，考虑到现实的需要，我们主要集中在VFL设置的分类问题假设存在具有n个样本x;y的训练数据集D，其中x的特征集索引由F表示，并且y1; 2;;c表示相应的标签。取第j个特征作为分裂特征，其第t个值作为分裂值，样本集D可以分裂为两个子集Dl和Dr.基尼系数定义为：基尼D;j;t基尼Dlj基尼Dlj基尼Drj基尼Drj;基尼Dr j图形操作，垂直FederBoost使用差分隐私来保护隐私。 Fu等（ 2021）探索GB D T 的效率jDjc0。DjDjI. 12在VFL场景下，提出了一种新颖高效的垂直联邦GBDT系统VF2Boost。1/4-X@。jDj.一ð1Þ3. 预赛3.1. 基于树的算法经典的决策树算法包括ID3（Quinlan（1986））、C4.5（Quinlan（2014））和CART（Breiman et al. （ 2017））。这些算法按照自顶向下的方法递归地构建树。如果不满足修剪条件，例如，当树的深度达到预设的最大值时，它通过度量确定最佳分割，并相应地分割数据集。与ID3和C4.5相比，CART生成的树具有二进制结构，并且CART使用基尼指数作为度量来确定最佳分裂。基尼指数的计算不需要对数运算，比ID3和C4.5的方法更简洁。因此，我们采用CART算法作为我们的基本树模型。此外，尽管CART可以用于其中Di表示D中标记有类别i的样本，并且表示集合中的元素的数量。具有最大基尼系数的分割被认为是最佳分割。构建CART分类树的过程如图1所示，其中<$jω;tω<$表示第jω个特征的第tω个值是最佳分割。算法1. CART（D;F）RF算法使用决策树作为基本分类器，并生成多个树来进行预测（Breiman（2001））。这些树使用决策树算法独立训练。特别是，为了构建树，RF不是基于整个数据集和特征集，而是基于采样生成的子集。 生成训练样本通过装袋策略（带替换的采样），并且整个数据集中的样本可以被选择多次或甚至不被选择一次。在训练阶段中使用的特征是从整个特征集中随机Tubeim2显示Y. Xu，X. Hu，J. Wei等人沙特国王大学学报240半]12Mn22 f·· ·gRF的训练步骤。对于预测，每棵树都可以得到一个预测结果，并且RF的最终预测是大多数的预测。算法2. 随机森林3.2. 同态加密同态加密是一种特殊的加密算法，它支持对加密数据的计算。同态运算后的解密结果与对明文执行的结果相同。根据所支持的操作，HE可分为部分同态和部分同态两类.● 加 密 向 量 与 明 文 向 量 之 间 的 点 积 ： 给 定 密 文 向 量 ：<$a]<$<$a1];<$a2];·· ·;<$an]T 和纯文本向量b<$b1;b2;·· ·;b nnn[bn½an][b½b·a]。在我们的框架中，我们主要使用第三个操作来计算统计数据，同时保护隐私。4. VF-CART系统模型4.1. 系统模型phic加密（PHE）和全同态加密（FHE）（Acar et al.（2018））。我们考虑一组数据所有者fp;p;... ;pg谁想要作 为 最 流 行 的 PHE 算 法 之 一 ， Paillier 密 码 系 统 （ Paillier（1999））已被广泛用于许多隐私保护联邦学习方案（Hardy et al.（2017）; Yang等人（2019 c）; Cheng et al.（2021）; Liu et al.（2020）; Wu etal.以协作方式训练CART模型，而无需共享他们的响应，动态数据集fD1;D2;. ;Dmg直接。所有数据集都有关于样本的ID信息，并且Di的特征集索引是表示为Fi。标签集Y1/fyign1由一个参与者持有，I¼其中y1 2c.（2020））。考虑到我们提出的框架中涉及的操作及其效率，我们使用Paillier密码系统来保护隐私并计算相关值。具体而言，它包含三种算法：● 随机选择两个大素数p和q，计算n<$pq;k<$lcm<$p-1;q-1 <$p，并选择一个正整数g，其中g2Zω。计算l/4Lkmod n2模kmod n，其中L_（？）x_（？）输出公钥pk;g;n，以及密钥● 加密pk;m：给定消息m2Zn，随机选择一个整数R、哪里0

下载后可阅读完整内容，剩余1页未读，立即下载