[發明專利]基于分布式并行決策樹的高維特征數據分類方法及系統

有效

• 申請號: 202010022431.3
• 申請日: 2020-01-09
• 公開（公告）號: CN111259933B
• 公開（公告）日: 2023-06-13
• 發明（設計）人: 孫瑩;莊福振;敖翔;何清
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F18/2431
• 分類號: G06F18/2431;G06N5/01;G06F16/27;G06F16/28;G06F16/2458
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國

1.一種基于分布式并行決策樹的高維特征數據分類方法，其特征在于，包括：

步驟1、獲取包括多個樣本高維特征數據的訓練數據，且該樣本高維特征數據具有對應的標簽類別，將該訓練數據存儲在分布式文件系統中，通過對該訓練數據的樣本在分布式集群上進行并行采樣統計，獲取該訓練數據上的特征分布信息，獲得支撐決策樹計算的元數據，并對連續型特征進行預處理；

步驟2、通過對該元數據進行采樣計算，為分布式集群中各計算節點分配特征組，建立樹的根節點，分布式集群各工作節點聯合統計樣本的標簽類別分布，以得到根節點初始信息熵；

步驟3、對所有樣本高維特征數據在分布式集群上各個工作節點上分別對各自儲存的樣本數據進行統計，根據各樣本的特征的向量及決策樹的劃分規則獲得各樣本當前所屬樹節點，同時統計四元組(所屬節點，特征，特征值，標簽)的出現次數，各節點將各四元組按照(節點，特征組)進行分組聚合，各工作節點分布式存儲(節點，特征組),(特征，特征值，標簽)的鍵值對的統計信息，根據該統計信息得到各特征值的信息熵；

步驟4、將特征值按照各自標簽的信息熵排序，將所有標簽的統計值歸于右節點，然后順序遍歷特征值作為左節點特征值，每次遍歷保留信息增益最大的特征值，得到(節點，特征組)，最優劃分鍵值對，將相同節點各個特征組的最優劃分聚合并取最優，得到節點，最優劃分鍵值對，選擇最優劃分對節點進行劃分；

步驟5、循環步驟2到步驟4直到對決策樹中全部節點完成劃分，保存當前決策樹作為分類模型，將待分類數據輸入該分類模型，得到該待分類數據對應的類別。

2.如權利要求1所述的基于分布式并行決策樹的高維特征數據分類方法，其特征在于，該訓練數據為文本數據或圖像數據。

3.如權利要求1所述的基于分布式并行決策樹的高維特征數據分類方法，其特征在于，該步驟2包括：

將特征按照特征值數量排序后可得序列二分特征值總數的最大值K，使用動態規劃算法得到G組總數不超過K的特征，找到最小的K，此時的G組即為最優特征分組。

4.如權利要求1所述的基于分布式并行決策樹的高維特征數據分類方法，其特征在于，步驟1中該預處理包括：對連續特征進行采樣，把采樣樣本的特征值匯集到主節點，統計各個特征值的樣本數，將所有特征值按照值的大小排序后得到序列，根據預設的最大特征劃分數，將樣本分組，每組作為連續特征的一個桶，相鄰兩組特征值的最小差別的中位數作為候選劃分。

5.如權利要求1所述的基于分布式并行決策樹的高維特征數據分類方法，其特征在于，該元數據由訓練數據統計得到，包括特征數、樣本數、標簽數、最大特征劃分、離散特征取值范圍、無序離散特征、最大深度、節點最小樣本數和分裂最小信息增益。