[發明專利]一種數據流決策樹分類中的缺失值處理方法

在審

• 申請號: 201410295212.7
• 申請日: 2014-06-25
• 公開（公告）號: CN104035779A
• 公開（公告）日: 2014-09-10
• 發明（設計）人: 呂品;侯旭珊
• 申請（專利權）人: 中國科學院軟件研究所
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 成金玉;孟卜娟

技術領域

本發明屬于數據流挖掘技術領域，具體涉及一種數據流決策樹分類中的缺失值處理方法。

背景技術

隨著大數據時代的到來，應用系統高速且連續不斷地產生數據流，如何從數據流中挖掘出有用信息，已成為技術人員關心的熱點。數據流決策樹分類技術是數據流挖掘中的重要研究方向，該技術能夠應用到網絡入侵檢測和信用卡欺詐等很多方面。實際中的數據流會因網絡傳輸故障、傳感器失靈或人工操作失誤等原因出現缺失值。在數據流決策樹分類中，數據流中的缺失值會對分類準確率造成嚴重影響。然而，數據流在挖掘過程中只能被掃描一次，無法在挖掘過程前預先采取處理缺失值的措施。

文獻[1](參考Domingos?P,Hulten?G.Mining?high-speed?data?streams[C]//Proceedings?of?the?Sixth?ACM?SIGKDD?International?Conference?on?Knowledge?Discovery?and?Data?Mining.2000:71-80.)提出了Hoeffding決策樹分類方法，利用Hoeffding界定理增量學習數據流中的數據樣本。Hoeffding決策樹分類方法依據當前構造的決策樹將數據樣本分配到葉子節點，葉子節點依據存儲的樣本信息和Hoeffding界定理確定最優分裂屬性，繼而分裂成為內部節點。通過不斷重復上述過程來動態地構造決策樹，直至決策樹達到穩定。

文獻[2](參考Yang?H,Fong?S.Aerial?root?classifiers?for?predicting?missing?values?in?data?stream?decision?tree?classification[C]//2011SIAM?International?Conference?on?Data?Mining(SDM2011).2011:28-30.)提出了ARC(Aerial?Root?Classifiers)方法，在Hoeffding決策樹分類方法的基礎上增加了缺失值處理機制。ARC方法利用滑動窗口保存最新的數據樣本，當檢測到缺失屬性值時，利用滑動窗口中的樣本為該屬性建立子分類器并預測缺失的屬性值，然后再依據Hoeffding決策樹分類方法來構造決策樹。ARC方法同時設計了更新機制，用于解決子分類器過時的問題。依據決策樹分裂節點時的屬性度量值為每個屬性分配權重，按權重相加每個屬性對應子分類器的錯誤率，從而得到總體錯誤率。當總體錯誤率超過預設的閾值時，依次選擇權重最大的屬性來更新其對應的子分類器，直到總體錯誤率滿足要求。

但是，ARC方法的時間性能在數據樣本的特征屬性較多時顯著下降，而時間性能是數據流挖掘中的重要衡量指標，因此嚴重影響了ARC方法的時間性能，使傳輸效率降低，影響了實際中的應用價值。

發明內容

本發明技術解決問題：克服現有技術的不足，提供一種數據流決策樹分類中的缺失值處理方法，根據數據特點自適應選擇缺失值處理方法，采用改進的貝葉斯分類模型，同時優化更新機制，從而降低時間開銷，提升時間性能，提高數據流的分類處理速度，從而滿足實際數據流處理的應用。

本發明的技術方案為：一種數據流決策樹分類中的缺失值處理方法，其步驟為：

步驟1：讀取數據流中的數據樣本，并使用固定容量的滑動窗口W保存最新到達的數據樣本；

步驟2：當前數據樣本中的屬性X_i存在缺失值時，建立或更新屬性X_i對應的缺失處理器。若屬性X_i的缺失處理器已存在，則跳至步驟4更新缺失處理器，否則進入步驟3建立缺失處理器；

步驟3：計算滑動窗口W中同類樣本關于屬性X_i的標準差σ(X_i)，若σ(X_i)不超過閾值σ_m，則選擇使用眾數或平均值代替缺失值，否則建立子分類器來預測缺失值。根據此方法建立缺失處理器并跳至步驟5；

步驟4：計算缺失處理器的加權總錯誤率E，若E超過閾值β，則選擇權重最大且錯誤率e_i＞β^*的缺失處理器進行更新，直到E低于閾值β；

步驟5：利用缺失處理器補充屬性X_i的缺失值，得到完整的數據樣本；

步驟6：依據Hoeffding決策樹分類方法訓練完整的數據樣本，動態地構造決策樹模型，并根據決策樹分裂葉子節點時的屬性度量值為每個屬性X_i更新權重；