[發明專利]一種面向決策樹的縱向聯邦學習方法

有效

• 申請號: 202011224742.4
• 申請日: 2020-11-05
• 公開（公告）號: CN112364908B
• 公開（公告）日: 2022-11-11
• 發明（設計）人: 張睿;田志華;侯瀟揚;劉健;任奎
• 申請（專利權）人: 浙江大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/04;G06N3/08
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 邱啟旺

1.一種面向決策樹的縱向聯邦學習方法，其特征在于，該方法包括以下步驟：

(1)每個參與者分別根據其本地包含的樣本的每一個特征，對本地的樣本進行排序，隨后將排序后的樣本按順序等分為不同的塊，將每一塊稱為一個桶并按順序編號，每個桶中含有數量相同的樣本；包括如下子步驟：

(1.1)對每一個參與者，該參與者對其本地包含的樣本的每一個特征，依次根據對應特征的數值進行升序或降序排列，共需排序次數與特征數量相同；

(1.2)排序完成后，對每一個特征對應的排好序的樣本均勻分割，將每一份分割后的樣本稱為一個桶，每一個特征均有相同數量的桶，保留分割后的桶的順序，將該順序記為桶號；

(2)對于每一個特征所對應的一組樣本，每一個樣本在該特征下的桶號有一定概率被替換為其它桶號，重新調整樣本對應的桶號進行加密；其中，選取的概率使得這種加密方式滿足差分隱私的定義；

(3)每個參與者將本地的所有樣本在不同特征下分到的桶的序號，發送給協調者，所述協調者為持有標簽的參與者；

(4)協調者根據本地的標簽信息計算每個樣本的梯度，并匯總每個特征對應的每個桶的梯度；對于每一個特征所對應的一組樣本，按桶分割數據并計算信息增益，最后記錄最大信息增益對應的分割位置和當前特征，返還給對應具有該特征數據的參與者；

(5)對每一個節點重復(4),訓練第一棵樹；

(6)更新參數，重復(4),(5)，訓練整個模型。

2.根據權利要求1所述的面向決策樹的縱向聯邦學習方法，其特征在于，所述步驟(2)包括如下子步驟：

(2.1)對每一個參與者，每一個樣本在每一個特征下的桶號，有一定概率變為其它的桶號，該概率與桶的數量有非線性關系；

(2.2)根據不同的桶的數量，根據差分隱私原理，計算(2.1)中的概率，重新調整樣本對應的桶號進行加密。

3.根據權利要求2所述的面向決策樹的縱向聯邦學習方法，其特征在于，所述步驟(3)包括如下子步驟:

(3.1)所有參與者將步驟(2)中得到的樣本對應的桶號按照樣本序順序發送給協調者；

(3.2)協調者接收所有數據后，根據樣本的唯一標識，將同一樣本的所有特征組合起來，建立新的數據表，存儲為DataFrame數據格式。

4.根據權利要求3所述的面向決策樹的縱向聯邦學習方法，其特征在于，所述步驟(4)包括如下子步驟：

(4.1)協調者根據建立的數據表，使用標簽計算每個樣本的梯度，通過接收到的以及本地的桶號，對每一個特征，匯總處于同一桶里的樣本梯度；

(4.2)協調者遍歷所有可能的分割，其中，協調者將每個桶作為一個單元參與遍歷，找到最大增益所對應的分割，記錄當前的特征與分割處的桶號并返還給對應具有該特征數據的參與者。

5.根據權利要求4所述的面向決策樹的縱向聯邦學習方法，其特征在于，所述步驟(5)包括如下子步驟：

(5.1)根據步驟(4)獲得的最大增益所對應的分割位置，協調者將每個特征對應的樣本數據分為兩部分，分別記為左節點與右節點，左右節點分別持有不同的樣本以及樣本對應的數據，對任意一個節點，對該節點內的數據進行如下處理：對每一個特征，匯總處于同一桶里的樣本梯度；

(5.2)協調者分別在左右節點進行步驟(5.1)后，在左右節點分別遍歷所有可能的分割，找到最大增益所對應的分割，記錄當前的特征與分割處的桶號并返還給對應具有該特征數據的參與者；重復分割遍歷，直到決策樹深度達到設定的最大值。

6.根據權利要求5所述的面向決策樹的縱向聯邦學習方法，其特征在于，所述步驟(6)包括如下子步驟：

(6.1)協調者根據前一棵樹的結果，計算殘差，更新所有樣本的梯度；

(6.2)協調者根據更新后的梯度，重復步驟(4)與步驟(5)構建新的樹，直到決策樹數量達到設定的最大數量。