[發明專利]基于增量樸素貝葉斯網多分類器集成方法

有效

• 申請號: 200810050425.8
• 申請日: 2008-02-29
• 公開（公告）號: CN101251851A
• 公開（公告）日: 2008-08-27
• 發明（設計）人: 劉大有;關菁華;黃晶;齊紅
• 申請（專利權）人: 吉林大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 吉林長春新紀元專利代理有限責任公司
• 代理人: 余巖

技術領域

本發明屬于數據挖掘與機器學習領域，涉及一種用于概念漂移數據建模的基于增量樸素貝葉斯網多分類器集成方法。

背景技術

眾多應用領域數據不斷增加，其包含的模式會隨時間和應用環境而變化，被稱為“概念漂移”。目前國內外在處理概念漂移方面已進行了大量研究，提出了多種模式學習方法。它們可歸結成兩類：基于實例選擇的方法，如Widmer和Kubat等人提出的FLORA系列算法、Lazarescu等人提出的自適應調整窗口大小的算法和Salganicoff的TMF(Time-Windowed?Forgetting)算法等?；趯嵗x擇的方法由于使用一個全局分類器，遺忘了所有的歷史信息，所以不能很好的處理概念漂移問題。

基于集成的方法通過保留過去學習到的概念，既避免了災難性遺忘又避免了因保存大量實例所需占用的計算資源。為了處理概念漂移問題，這類方法需根據原有概念與當前數據的一致性動態刪除一些舊的分類器，生成新的分類器。這類方法主要包括Littlestone等人提出的Weighted?Majority(WM)算法、Freund等人提出的Hedge算法、Street和Kim提出的算法、Kolter等人提出的AddExp(Additiveexpert)集成算法、KBS和Wang?H.等人提出的用于處理概念漂移數據流的集成算法等。已有的基于集成的方法不能及時丟棄無用分類器，造成錯誤概念的干擾，影響分類預測結果。

發明內容

本發明的目的是提供一種用于處理概念漂移問題的集成方法，該方法一方面通過動態改變(Kolter等人提出的)AddExp算法中的參數來提高算法的分類性能，另一方面利用基于KL距離的剪枝策略刪除集成中冗余的個體分類器，從而及時丟棄無用分類器。

為達到上述目的，本發明提供一種基于增量樸素貝葉斯網多分類器集成方法，其特征在于包括下列步驟：

初始化集成分類器及各主要參數；

如果沒有新數據，結束；

使用當前集成分類器預測新數據項的類別；

動態更新所有個體分類器的參數值；

更新所有個體分類器的權重；

如果當前集成分類器對新數據的類別預測不發生錯誤；則使用新數據項訓練集成分類器中的所有個體分類器；

根據KL剪枝策略刪除冗余個體分類器；

增加一個新個體分類器；

使用新數據項訓練所有個體分類器。

采用增量式樸素貝葉斯網算法完成給個體分類器的建模任務。

為每個分類器分配一個β值，β_i表示第i個分類器的β值，β_i能度量分類器i在發生預測錯誤時，其權重變化的幅度。β_i隨分類器i連續未發生預測錯誤的實例個數而變化，用于動態改變個體分類器權重。

采用基于KL距離的剪枝方法刪除冗余個體分類器。

采用加權投票的方法融合多個分類器。

本發明方法保留不同時間段產生的多個個體分類器，從而保留住必要的歷史信息，避免了災難性遺忘。本發明還能及時丟棄無用分類器，有效改善發生概念漂移時的分類預測結果。

附圖說明

圖1是本發明實施方式的流程圖；

圖2是在STAGGER數據集上的預測準確性比較。

具體實施方式

下面將對本發明進行詳細說明。

本發明的基本思想是為每個分類器分配一個權重，分類器都使用相同的訓練和預測算法，但被創建的時間步不同。分類結果融合采用加權投票的方法。當一個分類器發生預測錯誤時，其權重乘以常數β。為每個分類器都分配一個β值，β_i表示分類器i的β值，其能度量分類器i在發生預測錯誤時，其權重變化的幅度。β_i隨對應分類器連續沒發生預測錯誤的實例個數變化而變化。當集成算法發生預測錯誤時，使用KL剪枝策略刪除冗余個體分類器，增加一個新分類器。

參照圖1，該實施方式流程開始于步驟101；然后，在步驟102初始化集成分類器及各主要參數N₁←1，w_1，1←1，β₁←βMax(N_t表示t時間步，集成分類器中個體分類器的個數；w_t，i表示t時間步，分類器i的權重；β_i表示分類器i的β值，其能度量分類器i在發生預測錯誤時，其權重變化的幅度)；