[發明專利]一種基于動態快速決策樹算法的數據流分類方法及裝置

在審

• 申請號: 202010767031.5
• 申請日: 2020-08-03
• 公開（公告）號: CN111881992A
• 公開（公告）日: 2020-11-03
• 發明（設計）人: 趙曦濱;萬海;孫劍;賈宏宇
• 申請（專利權）人: 清華大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F17/18
• 代理公司: 北京科領智誠知識產權代理事務所(普通合伙) 11782
• 代理人: 陳士騫;王曉婷

1.一種基于動態快速決策樹算法的數據流分類方法，其特征在于，包括：

設置預設快速決策樹的葉子結點選擇錯誤的用于分裂的屬性的第一概率為預設最小概率，其中，所述預設快速決策樹至少包括一個根結點；

實時接收數據流中的數據實例，利用所述數據實例、所述數據實例的標注類型、所述數據實例中的每個屬性的統計信息和預設空屬性初始化所述根結點，其中，所述數據實例包括多個屬性；

利用所述預設快速決策樹對所述數據實例進行分類得到所述數據實例所屬的第一類別，并將所述數據實例、所述統計信息和預設空屬性存入所述第一類別對應的葉子結點；

根據所述第一類別和所述數據實例的標注類別確定分類錯誤指示變量；

通過預設漂移檢測器基于所述分類錯誤指示變量計算得到調整系數；

根據所述調整系數、所述預設最小概率、葉子結點選擇錯誤的用于分裂的屬性的預設最大概率計算得到第二概率，將所述第一概率更新為所述第二概率；

對于所述數據實例在分類時所經過路徑中的每個結點，如果該結點為葉子結點，基于所述數據實例到達該結點后的該結點中的每個屬性的統計信息計算每個屬性的啟發式度量值，將啟發式度量值最大的屬性作為第一最佳屬性，基于該結點當前累積的數據實例數據量和所述第二概率計算第一當前分裂閾值，計算所述第一最佳屬性的啟發式度量值與所述空屬性的啟發式度量值之間的差值是否大于所述第一當前分裂閾值，如果大于，則將該結點替換為內部結點，使用所述第一最佳屬性對所述內部結點進行分裂生成新的葉子結點并得到所述數據實例所屬的第二類別，將所述數據實例、所述統計信息和除所述第一最佳屬性外的屬性存入所述第二類別對應的新的葉子結點；

如果該結點為內部結點，基于所述數據實例到達該結點后的該結點中的每個屬性的統計信息計算每個屬性的啟發式度量值，將啟發式度量值最大的屬性作為第二最佳屬性，基于該結點當前累積的數據實例數據量和所述第一概率計算第二當前分裂閾值，計算所述第二最佳屬性的啟發式度量值與該結點的分裂屬性的啟發式度量值之間的差值是否大于所述第二當前分裂閾值，如果大于且所述第二最佳屬性為空屬性，按照預設替換規則將該結點替換為葉子結點，如果大于且所述第二最佳屬性不為分裂屬性，使用所述第二最佳屬性對該結點進行分裂生成新的葉子結點并得到所述數據實例所屬的第三類別，將所述數據實例、所述統計信息和除所述第二最佳屬性和所述分裂屬性外的屬性存入所述第三類別對應的新的葉子結點，其中，所述分裂屬性為該結點在所述數據實例未到達前所使用的對該結點進行分裂的屬性。

2.如權利要求1所述的方法，其特征在于，所述根據所述第一類別和所述數據實例的標注類別確定分類錯誤指示變量的步驟，包括：

判斷所述第一類別和所述數據實例的標注類別是否相同；

如果是，確定所述分類錯誤指示變量為1；

如果否，確定所述分類錯誤指示變量為0。

3.如權利要求1所述的方法，其特征在于，所述通過預設漂移檢測器基于所述分類錯誤指示變量計算得到調整系數的步驟，包括：

通過預設漂移檢測器基于所述分類錯誤指示變量計算得到當前概念漂移程度；

根據所述當前概念漂移程度和預設概念漂移警告閾值得到調整系數。

4.如權利要求1所述的方法，其特征在于，所述根據所述調整系數、所述預設最小概率、葉子結點選擇錯誤的用于分裂的屬性的預設最大概率計算得到第二概率的步驟，包括：

計算所述調整系數和所述預設最小概率的第一乘積；

比較所述第一乘積與葉子結點選擇錯誤的用于分裂的屬性的預設最大概率，確定兩者中的最小值；

比較所述最小值與所述預設最小概率，將兩者中的最大值作為第二概率。

5.如權利要求1所述的方法，其特征在于，所述基于該結點當前累積的數據實例數據量和所述第二概率計算第一當前分裂閾值的步驟，包括：

計算所述第二概率的倒數的自然對數；

計算預設隨機變量的取值的平方與所述自然對數的第二乘積；

計算所述第二乘積與二倍的該結點當前累積的數據實例數據量的商；

將所述商的平方根作為第一當前分裂閾值。