[發明專利]一種兩方決策樹訓練方法和系統

有效

• 申請號: 202010723916.5
• 申請日: 2020-07-24
• 公開（公告）號: CN111738360B
• 公開（公告）日: 2020-11-27
• 發明（設計）人: 方文靜;王力;周俊
• 申請（專利權）人: 支付寶（杭州）信息技術有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N20/00
• 代理公司: 成都七星天知識產權代理有限公司 51253
• 代理人: 袁春曉

1.一種兩方決策樹訓練方法，其中，所述方法由第一方的設備執行，所述第一方為持有樣本集中各樣本的至少一個特征的特征值及標簽值的一方和持有所述樣本集中各樣本的至少一個特征的特征值的一方中的任一方，第二方為兩方中的另一方；所述方法包括：

按以下分裂步驟對任一節點進行分裂：

獲得所述節點的標志向量的第一分片、第一梯度向量的第一分片以及第二梯度向量的第一分片；標志向量指示屬于相應節點的樣本，第一梯度向量包括屬于相應節點的樣本對應的第一梯度，第二梯度向量包括屬于相應節點的樣本對應的第二梯度；

對于第一方持有的任一特征：

對于按該特征的特征值劃分樣本集得到的多個第一分組中的每一個：根據各樣本的該特征的特征值生成該第一分組對應的標識向量，該標識向量指示屬于該第一分組的樣本；將該第一分組對應的標識向量拆分成第一分片和第二分片，并將該第一分組對應的標識向量的第二分片發送給第二方的設備；按照多方安全計算協議與第二方的設備交互，以基于所述節點的第一梯度向量的第一分片以及該第一分組對應的標識向量的第一分片，計算該第一分組對應的第一梯度和的第一分片，該第一分組對應的第一梯度和基于所述節點的第一梯度向量的第一分片和第二分片之和與該第一分組對應的標識向量的第一分片和第二分片之和的內積得到；按照多方安全計算協議與第二方的設備交互，以基于所述節點的第二梯度向量的第一分片以及該第一分組對應的標識向量的第一分片，計算該第一分組對應的第二梯度和的第一分片，該第一分組對應的第二梯度和基于所述節點的第二梯度向量的第一分片和第二分片之和與該第一分組對應的標識向量的第一分片和第二分片之和的內積得到；

對于第二方持有的任一特征：

對于按該特征劃分樣本集得到的多個第二分組中的每一個：從所述第二方的設備獲得該第二分組對應的標識向量的第一分片，該標識向量指示屬于該第二分組的樣本；按照多方安全計算協議與第二方的設備交互，以基于所述節點的第一梯度向量的第一分片以及該第二分組對應的標識向量的第一分片，計算該第二分組對應的第一梯度和的第一分片，該第二分組對應的第一梯度和基于所述節點的第一梯度向量的第一分片和第二分片之和與該第二分組對應的標識向量的第一分片和第二分片之和的內積得到；按照多方安全計算協議與第二方的設備交互，以基于所述節點的第二梯度向量的第一分片以及該第二分組對應的標識向量的第一分片，計算該第二分組對應的第二梯度和的第一分片，該第二分組對應的第二梯度和基于所述節點的第二梯度向量的第一分片和第二分片之和與該第二分組對應的標識向量的第一分片和第二分片之和的內積得到；

按照多方安全計算協議與第二方的設備交互，以基于各特征下的各分組分別對應的第一梯度和的第一分片以及第二梯度和的第一分片，計算各特征下的各分組分別對應的分裂增益的第一分片；

按照多方安全比較協議與第二方的設備交互，以基于各特征下的各分組分別對應的分裂增益的第一分片，確定最大分裂增益，并根據所述最大分裂增益對應的特征及分組記錄所述節點的分裂信息；

當所述最大分裂增益對應第一方的特征時，生成所述節點的左子樹向量和右子樹向量，所述左子樹向量指示根據所述最大分裂增益對應的特征及分組劃分所述樣本集得到的左子集中的樣本，所述右子樹向量指示根據所述最大分裂增益對應的特征及分組劃分所述樣本集得到的右子集中的樣本，左子集與左子樹對應，右子集與右子樹對應；將所述左子樹向量拆分成第一分片和第二分片，并將所述左子樹向量的第二分片發送給第二方的設備；將所述右子樹向量拆分成第一分片和第二分片，并將所述右子樹向量的第二分片發送給第二方的設備；當所述最大分裂增益對應第二方的特征時，從第二方的設備接收所述節點的左子樹向量的第一分片和右子樹向量的第一分片；

按照多方安全計算協議與第二方的設備交互，以基于所述節點的標志向量的第一分片以及所述左子樹向量的第一分片，計算所述節點的左子樹的標志向量的第一分片；按照多方安全計算協議與第二方的設備交互，以基于所述節點的標志向量的第一分片以及所述右子樹向量的第一分片，計算所述節點的右子樹的標志向量的第一分片；

按照多方安全計算協議與第二方的設備交互，以基于所述節點的第一梯度向量的第一分片以及所述節點的左子樹的標志向量的第一分片，計算所述節點的左子樹的第一梯度向量的第一分片；按照多方安全計算協議與第二方的設備交互，以基于所述節點的第二梯度向量的第一分片以及所述節點的左子樹的標志向量的第一分片，計算所述節點的左子樹的第二梯度向量的第一分片；

按照多方安全計算協議與第二方的設備交互，以基于所述節點的第一梯度向量的第一分片以及所述節點的右子樹的標志向量的第一分片，計算所述節點的右子樹的第一梯度向量的第一分片；按照多方安全計算協議與第二方的設備交互，以基于所述節點的第二梯度向量的第一分片以及所述節點的右子樹的標志向量的第一分片，計算所述節點的右子樹的第二梯度向量的第一分片。