面向非獨立同分布數據的聯邦梯度提升決策樹

摘 要：隨著聯邦學習的不斷興起，梯度提升決策樹（GBDT）作為一種傳統的機器學習方法，逐漸應用于聯邦學習中以達到理想的分類效果。針對現有GBDT的橫向聯邦學習模型，存在精度受非獨立同分布數據的影響較大、信息泄露和通信成本高等問題，提出了一種面向非獨立同分布數據的聯邦梯度提升決策樹（federated GBDT for non-IID dataset，nFL-GBDT）。首先，采用局部敏感哈希（LSH）來計算各個參與方之間的相似樣本，通過加權梯度來構建第一棵樹。其次，由可靠第三方計算只需要一輪通信的全局葉權重來更新樹模型。最后，實驗分析表明了該算法能夠實現對原始數據的隱私保護，并且通信成本低于simFL和FederBoost。同時，實驗按照不平衡比率來劃分三組公共的數據集，結果表明該算法與Individual、TFL及F-GBDT-G相比，準確率分別提升了3.53%、5.46%和4.43%。

關鍵詞：聯邦學習；梯度提升決策樹；非獨立同分布；局部敏感哈希

中圖分類號：TP309

文獻標志碼：A

文章編號：1001-3695（2023）07-040-2184-08

doi：10.19734/j.issn.1001-3695.2022.12.0764

Federated gradient boosting decision tree for non-IID dataset

Zhao Xue，Li Xiaohui^?

（School of Electronics amp; Information Engineering，Liaoning University of Technology，Jinzhou Liaoning 121000，China）

Abstract：With the continuous rise of federated learning，gradient boosting decision tree（GBDT） ，as a traditional machine learning method，is gradually applied to federated learning to achieve ideal classification results.Aiming at the problems of the existing horizontal federated learning model of GBDT，such as the accuracy is greatly influenced by non-IID dataset，information leakage and high communication cost，the paper proposed a federated gradient boosting decision tree for non-IID dataset，called nFL-GBDT.Firstly，the algorithm calculated similar samples among the participants by utilizing the LSH，and using weighted gradient constructed the first tree.Secondly，a reliable third party calculated the global leaf weight that only needed one round of communication.Finally，the experimental analysis shows that the algorithm can protect the privacy of the original data，and its communication cost is lower than that of simFL and FederBoost.At the same time，the experiment divides three groups of public data sets according to the imbalance ratio.The results show that the accuracy of this algorithm is improved by 3.53%，5.46% and 4.43% respectively compared with Individual，TFL and F-GBDT-G.

Key words：federated learning；gradient boosting decision tree；non-independent and identical distribution（non-IID）；locality sensitive hash（LSH）

0 引言

目前，利用數據驅動的人工智能（AI）技術來進行預測和自動化任務，逐漸受到了越來越多的關注。機器學習（ML）是人工智能的核心技術，它可以根據各種數據建立統計模型來執行特定任務。一個訓練良好的ML模型在很大程度上依賴于海量數據。然而，在現實中，數據集可能會存在敏感信息，增加了人們對個人隱私甚至國家安全的擔憂。由此，文獻［1］提出了聯邦學習（FL）技術。聯邦學習是在保證用戶隱私數據安全的前提下實現共同建模，使模型效果盡量接近于大規模集中式訓練的機器學習模型，可以分為橫向聯邦學習、縱向聯邦學習和聯邦遷移學習^［2］。然而，由于客戶端的地理位置、時間等分布的差異性，聯邦學習系統的原始數據往往是非獨立同分布（non-IID）的，會對模型準確率和收斂速度造成不利影響^［3］，已被確定為是FL的一個基本挑戰^［4］。目前，許多聯邦深度學習算法對non-IID數據引發的問題進行了優化研究^［5～8］。

梯度提升決策樹（GBDT）^［9］是目前比較流行的機器學習模型，該模型由多棵決策樹組成，通過梯度提升的方法對決策樹進行訓練，具有訓練速度快、精確度高、可解釋性強等諸多優點。重要的GBDT實現包括XGBoost^［10］、LightGBM^［11］和CatBoost^［12］，它們已經在不同的領域中^{［13～15］}使用并且具有較高的學習效率和預測性能。

在跨組織場景下的聯邦學習系統中，醫療、金融業、工業等各個參與方的數據多為結構化數據，例如電子病歷、信用記錄、工業設備狀態等。因此，最近有幾項研究將梯度提升決策樹與聯邦學習相結合^{［16～21］}，以實現理想的分類效果，彌補了聯邦深度學習類算法在結構化數據挖掘中訓練速度慢、模型不可解釋等不足。

然而，現有的橫向聯邦GBDT存在一定的局限性。Zhao等人^［18］提出了基于樹的FL（TFL），各方輪流訓練一個差分隱私決策樹，該方法只使用了參與方的本地數據來更新樹，導致模型精度不高。Yamamoto等人^［19］提出了基于梯度的模型選擇的聯邦GBDT（F-GBDT-G），該方法通過在TFL中引入一個決定更新模型所有者的函數，其預測性能受non-IID數據集的影響較大。Tian等人^［20］提出一種私有聯邦的GBDT（FederBoost），通過聚合所有數據參與方的梯度直方圖來構建精確的樹，但是，這一特性帶來了信息泄露等問題。Li等人^［21］提出了SimFL，該方法使用了哈希表加密原始數據，用加權梯度來訓練提升樹。然而，在對大規模數據集進行訓練時，每次更新迭代的通信開銷都非常大。因此，現有GBDT的橫向聯邦學習模型存在預測準確率不足、模型精度受non-IID數據集的影響較大、信息泄露和通信成本高等問題。

針對以上問題，本文提出了一種面向非獨立同分布數據的聯邦梯度提升決策樹。該方案可以更好地擬合non-IID數據，同時，提高模型的預測準確率，并最大限度地減少信息泄露和通信成本。本文方案的主要貢獻總結如下：

a）在構建第一棵樹的過程中，通過局部敏感哈希（LSH）來收集數據擁有者的相似樣本，采用加權梯度的方法來構建樹。這樣不僅能保護數據擁有者的原始數據不被泄露，還能夠充分吸收所有數據擁有者的梯度信息，以緩解non-IID數據集對決策樹模型的影響。

b）在后續更新迭代的過程中，由于葉權重與模型的輸出直接相關，所以該算法聚集各個數據擁有者的本地梯度來計算全局葉權重，通過提升樹的屬性機制來補償訓練數據分布不均衡導致的精度損失。這樣不僅保證了預測準確性，還大大提高了通信效率。

c）本文采用三組公共的數據集，通過調整不平衡比率來進行性能評估，實驗結果表明，該算法相較于Individual、TFL及F-GBDT-G三種方法具有更高的預測準確率。

1 相關工作

1.1 局部敏感哈希（LSH）

LSH最早由Gionis等人^［22］提出用于近似最鄰近搜索。LSH的主要思想是選擇一個哈希函數，使之滿足兩個相鄰點的哈希值大概率相等，兩個非相鄰點的哈希值大概率不相等。LSH的一個很好的特性是，對于相同的散列值，有無限個輸入數據。因此，LSH已被用于在關鍵字搜索^［23］和推薦系統^［24］等應用中保護用戶隱私。

Datar等人^［25］提出了基于p穩定的局部敏感哈希（p-stable LSH family），并被廣泛應用。哈希函數F_a，b可以形式化地表示為F_a，b（v）=∟（a×v+b）/γ」。其中：a是從p穩定分布中獨立選取的k維映射向量；b是0～γ間均勻選取的實數；γ是直線上分段的段長。哈希函數將一條直線分成等長為γ的若干段，給映射到同一段的點賦予相同的哈希值，映射到不同段的點賦予不同的哈希值。

1.2 聯邦梯度提升決策樹

1.2.1 梯度提升決策樹（GBDT）

梯度提升決策樹是一種改進決策樹的機器學習算法，由多個弱學習者在通過本地數據集訓練回歸樹，然后按照特定的順序聚合成一組樹，最終形成強學習者。

以圖1為例，某個弱學習者輸入樣本數據后，其預測結果被劃分到每棵樹的某個葉子節點中，然后將對應的葉子權重進行累加，得到強分類器的預測結果。

其中：T表示決策樹的數量；f_t（x）表示第T棵決策樹的預測結果。

GBDT雖然能夠得到較好的預測效果，但不能充分地利用弱學習的本地硬件資源，也對于弱學習者的數據安全帶來挑戰。因此文獻［16］將GBDT與聯邦學習相互結合，取得了較好的效果。

1.2.2 橫向聯邦梯度提升決策樹

GBDT盡管被應用到聯邦學習中，但弱學習者的數據分布會導致對應的訓練過程存在差異。針對數據分布是水平的，橫向聯邦梯度提升決策樹被提出，其中心化的訓練過程如圖2所示。

接下來，簡要介紹聯邦GBDT的訓練算法。形式上，給定一個損失函數l和一個具有n個實例和d個k特征的數據集D={（x_i，y_i）}（|D|=n，x_i∈R^d，y_i∈R），GBDT最小化目標函數^［10］如式（2）所示。

1.3 聯邦優化

聯邦學習中隱含的優化問題稱為聯邦優化。聯邦優化有以下幾個關鍵屬性，使其區別于典型的分布式優化問題：

a）non-IID。

給定客戶機上的訓練數據通常基于特定用戶對移動設備的使用，因此任何特定用戶的本地數據集都不能代表總體分布。

b）不平衡性。

由于某些用戶大量使用產生訓練數據的服務或應用程序，會導致一些客戶端擁有大量的本地訓練數據集，而另一些客戶端只有很少或沒有數據。

c）大規模分布式。

在現實的場景中，參與優化的客戶端樣本數量要比每個客戶端的平均樣本數量大得多。

本文將重點放在non-IID和不平衡屬性上，提出了一種面向非獨立同分布數據的基于聯邦學習的梯度提升決策樹方法，該方法對自然產生的non-IID和不平衡數據分布具有魯棒性。

2 nFL-GBDT：面向非獨立同分布數據的聯邦梯度提升決策樹

2.1 nFL-GBDT框架

本文主要研究橫向聯邦學習的應用場景。各方都有自己的數據，這些數據具有相同的特性集。由于對數據隱私的要求，數據擁有者不愿意與其他方分享私人數據。然而，所有數據擁有者都希望利用協作，通過各方數據聯合訓練出一個更準確的模型。因此，聯邦學習應該生成一個比單獨從各方的本地數據生成的模型更好的學習模型，同時，更好的模型精度是橫向聯邦學習中協作的目的。該場景^［26］已存在于

銀行和醫療保健等各種應用中。

當前橫向聯邦GBDT的前沿研究的大概遵循以下方式：由第一個數據擁有者訓練一棵決策樹后，發送給其他方，接收到決策樹的各方會更新自己的本地梯度，并訓練下一棵決策樹，依次輪流直到完成最終的任務結束。然而，當某個數據擁有者的本地數據集非常偏斜時，訓練出來的決策樹質量較低，更嚴重的是低質量決策樹會影響到后續所有的訓練過程（這一過程是不可逆的，因為后續的決策樹都將依賴之前所有模型的預測殘差）。綜上所述，第一棵決策樹的構建尤其重要。

因此，在構建第一棵樹的過程中需要充分吸收所有數據擁有者的梯度信息，以緩解non-IID數據對決策樹模型的影響。在nFL-GBDT中，首先使用LSH來收集相似樣本信息，再采用梯度聚合的方法來構建樹。此外，在隱私保護方面，沒有暴露任何數據擁有者的原始數據。

在后續更新迭代的過程中，若每次都需要獲取樣本梯度，通信代價將與樣本數量直接相關，并不適用于大規模數據集的實際應用場景。因此，nFL-GBDT計算只需要一輪通信的全局葉權重來更新樹模型，以降低通信成本。此外，在精度方面，由于葉權重與模型的輸出直接相關，在面對non-IID數據時，它們對模型準確率的提升貢獻更大。

nFL-GBDT框架的示意圖如圖3所示，它包括構建者、聚集器和數據擁有者。構建者（builder）是數據擁有者之一，負責確定樹結構；聚集器（agg）負責建立全局哈希表和聚合局部梯度計算全局葉權；數據擁有者（data owners）負責計算哈希值和梯度，并將其發送給聚集器。

2.2 nFL-GBDT算法設計

nFL-Boost主要有構建樹和更新樹兩個階段。在第一階段，數據擁有者首先使用隨機生成的局部敏感哈希（LSH）函數計算哈希值并上傳至聚集器；然后，聚集器通過收集到的哈希值建立全局哈希表，并向所有數據擁有者廣播，數據擁有者根據全局哈希表計算相似實例梯度；最后，構建者（數據擁有者之一）計算加權梯度來構建樹T₁。在第二階段，首先，數據擁有者根據構建者共享的樹結構計算出本地梯度，并將其發送給聚集器；然后，聚集器聚合梯度計算葉權重并共享；最后，每個數據擁有者再將樹結構和葉權重組合，得到一棵新的樹，并將其添加到全局模型中。值得注意的是，一旦在一方構建了一棵樹，它將被發送給所有方來更新梯度。得到所有的決策樹將會作為最終的學習模型。

2.2.1 構建樹階段

對于每個實例，使用局部敏感哈希的目的是獲取其他方的相似實例ID。例如，對于構建者B_m，需要得到相似矩陣S^m∈R^N_m^×M，其中S^m_ij是數據擁有者B_j中與X^m_i相似的實例ID。為了在不暴露原始數據的前提下獲得聯合數據中任意兩個實例的相似性，采用了P穩定LSH函數。根據LSH，如果兩個實例相似，那么它們被哈希到相同值的概率就更高。因此，通過應用多個LSH函數，兩個實例的相同哈希值的數量越多，它們就越有可能相似。為了保護其他數據擁有者的個人數據，構建者只使用本地實例集I_m并采用梯度聚合的方法來構建第一棵樹，然后將構建好的樹分享給其他數據擁有者。

算法1給出了構建樹階段的過程。給定L個隨機生成的P穩定哈希函數，每個數據擁有者首先計算其實例的哈希值并上傳至聚集器agg，然后由agg構建L個全局哈希表并廣播。最后，各數據擁有者通過全局哈希表計算相似度信息。具體來說，在構建者B_m中，給定一個實例X^m_i，另一個數據擁有者B_j中的類似實例是具有最高相同哈希值計數的實例。利用不同方實例之間的相似信息，如果一個實例與許多其他實例相似，那么它就是重要并且具有代表性的。文獻［10］表明，梯度可以代表一個實例的重要性，因此采用梯度聚合的方法來構建樹T₁。對于一個實例X^m_q∈I_m，設Wⁿ_mq={k|Sⁿ_km=q}，其中包含I_n中與X^m_q類似的實例IDs。設g^m_q和h^m_q分別表示損失函數在X^m_q處的一階和二階梯度。在第t次迭代后最小化以下目標函數：

2.2.2 更新樹階段

決策樹可以被分為樹結構和葉權重兩部分。其中，樹結構T是由多個節點組成的具有閾值的圖，葉權重ω是模型的輸出。在通信成本方面，全局樹結構的通信成本與樹的深度相關，而全局葉權重的計算則只需要一輪通信。在精度方面，由于葉權重與輸出直接相關，所以在面對non-IID數據集時，計算全局葉權重對預測性能的提升貢獻更大。

算法2給出了更新樹階段的過程。每個數據擁有者d∈D基于之前構建的樹{T₁，…，T_i-1}更新每個數據的梯度（g_d和h_d），再根據g_d、h_d和數據集X_d計算出G_d和H_d，即每個葉子節點數據對應的梯度之和，并將其發送給agg。agg根據每個參與方之間相似樣本的數量差異（相似樣本越多代表其梯度對于更新樹模型越重要），聚合G_d和H_d來計算出G=∑d∈D（n_d/n）G_d和H=∑d∈D（n_d/n）H_d，其中，n為所有數據擁有者的相似樣本總數，n_d為第d個擁有者的相似樣本數量，n=∑j-1d=0n_d，n_d/n可以衡量出某個參與方的梯度對于更新樹模型的重要程度。當n趨于不變的情況下，n_d越大，表示該參與方有更好的數據分布。因此，在各擁有者數據質量和分布存在明顯偏差的情況下，n_d/n可以提升高質量數據集的貢獻，從而加快模型的收斂速度。然后，agg用G和H來計算全局葉權重ω，并將ω返回給數據擁有者D。最后，每個數據擁有者d將樹結構T和葉權重ω組合，得到第i棵樹T_i，并將其添加到全局模型中。

算法2 更新樹算法

輸入：決策樹T₁，更新次數U；數據擁有者d∈D的數據集（x_d，y_d）；正則化參數λ。

輸出：全局模型{T₁，…，TU}。

for i←2 to U do

for each data owner d∈D do

agg selects builder B_j∈D（j=1 to m，j！=m）；/*聚集器每次更新選擇不同的構建者B_j*/

end for

for each data owner d∈D do

d updates gradiends g_d and h_d according to T_i-1 and （x_d，y_d）；/*數據擁有者根據前一棵樹和本地數據集更新梯度*/

end for

B_j computes T_i from T_i-1，g_j and h_j；/*B_j根據前一樹、g_j和h_j構建出樹結構T_i*/

B_j sends T_i to D；//B_j發送樹結構給所有的數據擁有者

for each data owner d∈D do

d computes G_d and H_d from X_d，g_d and h_d；

d sends G_d and H_d to agg；//數據擁有者發送G_d、H_d至聚集器

end for

agg computes G=∑d∈D（n_d/n） G_d and H=∑d∈D（n_d/n）H_d；/*聚集器聚合G_d、H_d*/

agg computes ω_i=-G/（H+λ）；//聚集器計算全局葉權重

agg sends ω_i to D；

for each data owner d∈D do

d combines T_i and ω_i to obtain T_i；/*數據擁有者將樹結構T_i和葉權重ω_i組合得到新的決策樹T_i*/

end for

end for

2.3 算法性能分析

本節從安全性、通信成本和復雜度方面對nFL-GBDT進行分析，并將其與現有方案進行比較。

2.3.1 安全性分析

1）構建樹階段

隱私保護模型。Du等人^［27］提出了一個兩方安全模型，2020年，Liu等人^［28］也采用了該模型。將模型擴展到多方，得到以下隱私定義：

當遇到推理攻擊等潛在風險時，定義1與安全多方計算^［29］中的安全定義相比隱私級別較弱。因此在文獻［21］根據該隱私模型提出相應的啟發式模型：

定義2 啟發式模型。如果Llt;e，其中L為哈希函數的個數，e為訓練數據的維數。簡而言之，如果未知數的數量（e）大于方程的數量（L），則存在無窮多個解。

根據定義2，當Llt;e時，本文提出的nFL-GBDT對于相同的輸出，存在無限個可能的輸入。因此，不誠實的一方無法獲取其他參與方的原始數據。根據文獻［21］，nFL-GBDT在該階段可能存在潛在的后臺知識攻擊。解決這個問題的一個可選方法是減小L，以得到更少的方程數量，這將導致相同的輸出有更多的輸入。例如，知道一個特征的背景知識，如果只有e-1個未知數，可以將L設置為e-2或更小，以確保原始數據仍然不能提取。

2）更新樹階段

在該階段，根據信息泄露給其他數據擁有者的情況，對nFL-GBDT進行安全性分析。

假設D和agg在以下條件下試圖從其他數據所有者那里獲取敏感信息：a）攻擊者不使用復雜的技術；b）所有參與者使用安全通信通道，內容不被其他方截獲；c）所有參與者之間不相互勾結。在nFL-GBDT中，除了這些參與者，還有構建者B；由于B包含在D中，所以B和D被視為相同的。在更新樹階段，agg得到G_d和H_d，即每個所有者計算的每個葉子數據的梯度之和。然而，由于Agg不具有樹型結構，不能將聚合的梯度與其他信息關聯起來，所以agg無法獲得任何有用的信息。針對數據擁有者D，在該階段，除了全局模型外，沒有獲得任何其他的信息。

表1顯示了各方案中D和agg獲得的信息。在nFL-GBDT中，除了數據擁有者D，還有構建者B；由于B包含在D中，所以在表格中B和D是一樣的。TFL^［18］中沒有agg條目，因為在TFL中沒有聚集器agg。其中Hist為梯度直方圖，T為樹結構，T_d為所有者d的決策樹，Hist_d為數據擁有者d的梯度直方圖，Sel為F-GBDT-G^［19］中進行選擇時使用的指標。

首先，對于聚集器agg，所有方案只泄露低風險信息。在F-GBDT-G和FederBoost^［20］中，加密的全局模型和直方圖被泄露，但是如果沒有相應的密鑰，就無法獲得有用的信息。在nFL-GBDT中，agg得到G_d和H_d，即每個數據擁有者計算的每個葉子的梯度之和。但是，由于agg沒有樹結構，不能將G_d和H_d的每個聚合梯度與其他信息關聯起來。所以在nFL-GBDT中，agg無法獲得任何有用的信息。

其次，對于數據擁有者D，nFL-GBDT在現有方案中的隱私風險最低。下面分別討論所有方案中的全局模型和其他信息泄露給D的情況。

與TFL和F-GBDTG相比，nFL-GBDT和FederBoost中的全局模型具有更低的隱私泄露風險。nFL-GBDT和FederBoost中的全局模型不同于TFL和F-GBDT-G中的全局模型，這取決于每棵樹是基于全局分布還是局部分布。GBDT中的每棵樹都包含一個樹結構和葉權重，其中葉權重由損失函數的梯度計算。在葉節點中，當梯度的方差減小時，可以從葉權重中推斷出目標變量y；因此，全局模型將與閾值相關聯的目標變量y泄露給d。如果每個葉子對應的數據量很小，則與閾值相關聯的目標變量y表示少數群體，這將導致隱私泄露風險。因此，基于全局分布的全局模型（使用更多數據訓練）被認為具有較低的隱私風險。

在nFL-GBDT中，除了全局模型外，沒有任何其他信息泄露給D；而在FederBoost中，除了全局模型外，每個節點對應的梯度直方圖也會泄露給D。FederBoost在訓練之前，直方圖的形成是這樣的：每個桶包含幾個數據點，隨著分割的進行，梯度的方差和每個桶中的數據量都會減少。因此，在靠近葉子節點的直方圖中，目標變量y可以從梯度中推斷出來（目標變量y可以表示個體或少數群體）。在這種情況下，與閾值或桶相關聯的目標變量y可能被泄露給D，因此，在FederBoost中，個人數據可能會出現隱私泄露風險。

2.3.2 通信成本分析

1） 構建樹階段 首先各個數據擁有者D需要將計算好的NL個哈希值和對應的實例ID上傳至agg，假設有M個參與方，通信開銷為MNL，然后，各個數據擁有者發送聚合的梯度給構建者B_m，通信代價為N。最后，構建者B_m建立好決策樹后，將樹共享給各方。一棵決策樹的大小為2H-1，其中H為樹的深度，由于每棵樹要發送給M-1方，所以構建第一棵樹的通信成本為（2H-1）（M-1）。

2）更新樹階段 在該階段nFL-GBDT每次需要三次通信。首先構建者B將構建好的樹結構共享給各個數據擁有者D，然后D傳輸本地梯度給agg，最后agg計算全局葉權重并傳遞。

由于構建樹階段只確定第一棵樹，所以在U次更新迭代后，nFL-GBDT的總通信代價為O（U），與TFL和F-GBDT-G相同。然而，由于FederBoost在每次更新中，每個節點對應的梯度直方圖必須根據樹的深度進行多次通信，總通信代價為O（HU）。simFL^［21］每次更新都需要獲取樣本梯度，總通信代價為O（|I_m|U）。因此，nFL-GBDT可以用比FederBoost和simFL更低的通信成本來訓練模型。表2列出了每個方案每次更新全局模型所需的通信成本，其中H表示樹的深度，I_m表示本地實例集。

2.3.3 復雜度分析

1）構建樹階段

首先各個數據擁有者需要計算本地數據中各個實例的哈希值，該過程的復雜度為O（Ne）。然后需要通過合并相同哈希值的實例ID來統計相似度信息。例如，在統計實例X^m_i的相似度信息時，需要將L桶的實例ID與通過哈希函數得到的哈希值{F_k（X^m_i）}_k=1，2，…，L進行線性探測，找到具有最高相似實例計數的實例ID，因此，每個實例可以在O（L）的復雜度下完成線性探測。由于該過程總共需要遍歷NL個哈希值，所以該操作可以在O（NL）復雜度內完成。最后，需要通過簡單的和運算來計算加權梯度，即O（N）。因此，構建樹階段的總計算開銷平均為O（Ne+NL+N）。

2）更新樹階段

nFL-GBDT每更新一次需要進行三次計算：首先構建者B確定樹結構，其第d個數據擁有者擁有的數據總數和特征總數分別為N_d和N_f，因此，該過程的計算復雜度為O（N_dN_f）；其次由各個數據參與方D計算每個葉子數據的梯度，假設每個數據擁有者的數據數量為N，共有M個數據參與方，因此，該操作可以在O（MN）的計算復雜度下完成；最后由agg聚合梯度來計算葉子權重，該過程的計算復雜度為O（2H）（2Hgt;gt;NM），其中H為樹的深度。因此，由B確定樹結構的過程是最主要的。

各方案更新樹所需的計算復雜度如表3所示。在TFL和F-GBDT-G中，每次更新都使用與普通GBDT算法相同，計算復雜度為O（N_dN_f）。FederBoost需要構造樹和直方圖的加密，計算復雜度也是O（N_dN_f）。因此，在所有方案中，所有數據擁有者共享完整的GBDT，推理出所需的計算復雜度與正常GBDT所需的計算復雜度相等。

3 實驗

3.1 實驗設置

在本實驗中，硬件采用128 GB內存的云服務器，采用Python語言實現nFL-GBDT算法。

本實驗使用三個公共數據集來評估nFL-GBDT（https：//www.csie.ntu.edu.tw/cjlin/libsvmtools/datasets/），如表4所示，其中75%的數據集用于訓練，其余用于測試。為了按照現實場景的要求分配傾斜的本地數據集，使用前面工作^［30］中的劃分方法，根據不平衡比例θ∈{0，1}為每一方分配數據集。分配后，一半的數據擁有者獲得了（θ×N_class0）/M個標簽為0實例，以及[（1-θ）×N_class1]/M個標簽為1的實例，剩余數據擁有者的情況正好相反。這種分區方法很好地代表了聯邦場景中的數據分布。

本實驗選擇Non、Individual、TFL^［18］、F-GBDT-G^［19］和FederBoost^［20］五種GBDT方案進行比較。Non表示一方對所有數據擁有者提供的數據集進行GBDT訓練，而不考慮隱私保護的情況；Individual是指由個體數據擁有者只用本地數據集獨立進行訓練的情況；

由于FederBoost中的訓練過程與GBDT中的訓練過程是相同的，所以它與Non有相同的準確性，也就沒有顯示FederBoost的實驗結果。

3.2 實驗結果

在聯邦學習的實際使用中，參與方的數據質量和分布往往是不可控的，無法要求所有參與方的數據滿足獨立同分布^［30］。因此，根據文獻［31］，本實驗考慮兩種方法來劃分訓練數據集，以模擬聯邦學習中的不同數據分布，即不平衡分區和平衡分區。

實驗采用比例為θ=80%的不平衡分割法將數據集分成兩部分，分別分配給A和B兩方。測試誤差如表5所示。實驗結果表明：a）nFL-GBDT在數據方A和B（分別記為IndividualA和IndividualB）上的測試誤差始終低于Individual，通過nFL-GBDT可以提高預測準確率；b）nFL-GBDT的測試誤差接近Non；c）與TFL和F-GBDT-G相比，nFL-GBDT具有更低的測試誤差。TFL和F-GBDT-G的測試誤差總是比Individual大，這阻礙了它們在實踐中的采用。

表6顯示了設置平衡分區時的訓練誤差。結果表明，nFL-GBDT的性能優于Individual和TFL，有時甚至接近于Non的測試誤差。因此，即使在平衡分區中，nFL-GBDT仍然具有良好的性能。

3.2.1 不平衡比率θ對性能的影響

在現實中，數據擁有者提供的數據數量往往是不同的，因此，聯邦學習算法對不平衡的數據分布應具有魯棒性。在本實驗中，通過調整不平衡比率θ，對各模型的準確性進行評估。

實驗結果如圖4所示。圖中的橫坐標表示不平衡比率θ，隨著θ的增大，nFL-GBDT與Individual、TFL和F-GBDT-G相比，具有較好的預測性能。

3.2.2 參與方數量對性能的影響

聯邦學習的核心思想是使多個參與方共同訓練模型，以提高預測準確性。因此，為了研究聯邦學習的有效性，在本實驗中，固定每個參與方的數據量，通過調整參與方的數量，對各模型的準確性進行評估。

圖5、6顯示了不同參與方數量下的測試誤差。

圖中的橫坐標表示參與方的數量。對于不平衡分區，比率θ設置為80%。隨著參與方數量的增加，nFL-GBDT泛化誤差的上限可能增大。盡管如此，在大多數情況下，nFL-GBDT的測試誤差比Individual的最小誤差要低。TFL的測試誤差隨著參與方數量的增加而急劇變化，而nFL-GBDT在平衡和不平衡數據分區中都要穩定得多。

3.2.3 數據量大小對性能影響

在大多數情況下，機器學習模型的性能受訓練數據數量的影響。因此，本實驗固定的參與方數量為三個，通過改變每個參與方的訓練數據量，對各模型進行準確性評估。

圖7、8顯示了不同數據量的測試誤差。對于不平衡分區，比率θ設置為80%。圖中的橫坐標表示原始數據集的數據比率，每個參與方的數據量是總數據量的10%、20%和33%。實驗結果表明，在平衡和不平衡數據分區中，隨著數據量的增加，所有GBDT方案預測性能都有所提高。其中，nFL-GBDT始終優于Individual、TFL和F-GBDT-G。

4 結束語

近年來，在跨機構聯邦場景中，聯邦GBDT算法逐漸取代傳統的GBDT，承擔了結構化數據挖掘任務，成為學術、應用領域的研究熱點。但考慮到數據擁有者的數據質量和分布往往是不可控的，無法要求數據擁有者的數據滿足獨立同分布。

本文提出了一種面向非獨立同分布數據的聯邦梯度提升決策樹（nFL-GBDT）。首先，在構建第一棵樹的過程中通過局部敏感哈希（LSH）收集各個數據擁有者數據的相似樣本，累計梯度衡量樣本的重要程度，這樣不僅能防止原始數據泄露，也能減少數據傾斜給模型準確率及其收斂速度帶來的影響。其次，在更新樹的過程中，由于葉權重與每個數據擁有者的數據息息相關，所以可靠第三方對它們的梯度信息進行積累，計算全局葉權重來更新全局模型。這樣不僅提高了模型的準確率，也減少了訓練期間的通信成本。最后，實驗按照不平衡比率來劃分三組公共的數據集，證明了該算法相較于其他聯邦GBDT方案具有更高的預測準確率，通信成本低，甚至接近于非隱私保護的GBDT方案。因此，nFL-GBDT能夠通過聯邦學習實現性能增強，即使在參與方的數據是非獨立同分布的情況下也是如此。在整個訓練過程中，由于數據擁有者在提升樹的更新時需要共享本地數據的梯度信息，所以仍然存在信息泄露的風險。以后的研究將側重于聯邦梯度提升決策樹模型更新過程中的隱私安全問題，保護本地模型參數的安全。

參考文獻：

［1］Kone?ny J，McMahan H B，Yu F X，et al.Federated learning：strategies for improving communication efficiency［EB/OL］.（2017-10-30）.https：//arxiv.org/abs/1610.05492.

［2］孫爽，李曉會，劉妍，等.不同場景的聯邦學習安全與隱私保護研究綜述［J］.計算機應用研究，2021，38（12）：3527-3534.（Sun Shuang，Li Xiaohui，Liu Yan，et al.Review of federated learning secu-rity and privacy protection studies in different scenarios［J］.Application Research of Computers，2021，38（12）：3527-3534.）

［3］Li Xiang，Huang Kaixuan，Yang Wenhao，et al.On the convergence of FedAvg on non-IID data［EB/OL］.（2020-06-25）.https：//arxiv.org/abs/ 1907.02189.

［4］Kairouz P，McMahan H B，Avent B，et al.Advances and open pro-blems in federated learning［M］.［S.l.］：Now Foundations and Trends，2021.

［5］Sattler F，Wiedemann S，Müller K R，et al.Robust and communication-efficient federated learning from non-IID data［J］.IEEE Trans on Neural Networks and Learning Systems，2019，31（9）：3400-3413.

［6］Wang Hao，Kaplan Z，Niu Di，et al.Optimizing federated learning on non-IID data with reinforcement learning［C］//Proc of IEEE Confe-rence on Computer Communications.Piscataway，NJ：IEEE Press，2020：1698-1707.

［7］Li Qinbin，Diao Yiqun，Chen Quan，et al.Federated learning on non-IID data silos：an experimental study［C］//Proc of the 38th International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2022：965-978.

［8］王惜民，范睿.基于類別不平衡數據聯邦學習的設備選擇算法［J］.計算機應用研究，2021，38（10）：2968-2973.（Wang Ximin，Fan Rui.Device selection algorithm based on federated learning of category-unbalanced data［J］.Applications Research of Compu-ters，2021，38（10）：2968-2973.）

［9］Friedman J H.Greedy function approximation：a gradient boosting machine［J］.Annals of Statistics，2001，29（5）：1189-1232.

［10］Chen Tianqi，Guestrin C.XGBoost：a scalable tree boosting system［C］//Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2016：785-794.

［11］Ke Guolin，Meng Qi，Finley T，et al.LightGBM：a highly efficient gradient boosting decision tree［C］//Proc of the 31st International Conference on Neural Information Processing Systems.2017：3149-3157.

［12］Prokhorenkova L，Gusev G，Vorobev A，et al.CatBoost：unbiased boosting with categorical features［C］//Proc of the 32nd International Conference on Neural Information Processing Systems.2018：6639-6649.

［13］Sun Rui，Wang Guanyu，Zhang Wenyu，et al.A gradient boosting decision tree based GPS signal reception classification algorithm［J］.Applied Soft Computing，2020，86：105942.

［14］Cheng Juan，Li Gen，Chen Xianhua.Research on travel time prediction model of freeway based on gradient boosting decision tree［J］.IEEE Access，2018，7：7466-7480.

［15］Hu Jianfeng，Min Jianliang.Automated detection of driver fatigue based on EEG signals using gradient boosting decision tree model［J］.Cognitive Neurodynamics，2018，12：431-440.

［16］Cheng Kewei，Fan Tao，Jin Yilun，et al.SecureBoost：a lossless federated learning framework［J］.IEEE Intelligent Systems，2021，36（6）：87-98.

［17］Liu Yang，Ma Zhuo，Liu Ximeng，et al.Boosting privately：privacy-preserving federated extreme boosting for mobile crowdsensing［EB/OL］.（2020-04-10）.https：//arxiv.org/abs/1907.10218.

［18］Zhao Lingchen，Ni Lihao，Hu Shengshan，et al.Inprivate digging：enabling tree-based distributed data mining with differential privacy［C］//Proc of IEEE Conference on Computer Communications.Pisca-taway，NJ：IEEE Press，2018：2087-2095.

［19］Yamamoto F，Wang Lihua，Ozawa S.New approaches to federated XGboost learning for privacy-preserving data analysis［C］//Proc of International Conference on Neural Information Processing.Berlin：Springer，2020：558-569.

［20］Tian Zhihua，Zhang Rui，Hou Xiaoyang，et al.FederBoost：private fe-derated learning for GBDT［EB/OL］.（2022-12-21）.https：//arxiv.org/abs/2011.02796.

［21］Li Qinbin，Wen Zeyi，He Bingsheng.Practical federated gradient boosting decision trees［C］//Proc of AAAI Conference on Artificial Intelligence.2020：4642-4649.

［22］Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing［C］//Proc of the 25th International Conference on Very Large Data Bases.1999：518-529.

［23］Wang Bing，Yu Shucheng，Lou Wenjing，et al.Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud［C］//Proc of IEEE Conference on Computer Communications.Piscataway，NJ：IEEE Press，2014：2112-2120.

［24］Qi Lianyong，Zhang Xuyun，Dou Wanchun，et al.A distributed locality-sensitive hashing-based approach for cloud service recommendation from multi-source data［J］.IEEE Journal on Selected Areas in Communications，2017，35（11）：2616-2624.

［25］Datar M，Immorlica N，Indyk P，et al.Locality-sensitive hashing scheme based on p-stable distributions［C］//Proc of the 20th Annual Symposium on Computational Geometry.2004：253-262.

［26］Yang Qiang，Liu Yang，Chen Tianjian，et al.Federated machine lear-ning：concept and applications［J］.ACM Trans on Intelligent Systems and Technology，2019，10（2）：1-19.

［27］Du Wenliang，Han Y S，Chen Shigang.Privacy-preserving multivariate statistical analysis：linear regression and classification［C］//Proc of the 4th SIAM International Conference on Data Mining.2004：222-233.

［28］Liu Yang，Kang Yan，Xing Chaoping，et al.A secure federated transfer learning framework［J］.IEEE Intelligent Systems，2020，35（4）：70-82.

［29］Yao A C.Protocols for secure computations［C］//Proc of the 23rd Annual Symposium on Foundations of Computer Science.1982：160-164.

［30］Zhao Yue，Li Meng，Lai Liangzhen，et al.Federated learning with non-IID data［EB/OL］.（2018-06-02）.https：//arxiv.org/abs/1806.00582.

［31］Yurochkin M，Agarwal M，Ghosh S，et al.Bayesian nonparametric federated learning of neural networks［C］//Proc of the 36th International Conference on Machine Learning.2019：7252-7261.