一種分類器集成方法
2023-05-27 05:28:21
專利名稱：一種分類器集成方法
技術領域：
本發明屬於模式識別方法，具體涉及一種通過對子分類器的集成來提高分類器的性能的方法。
背景技術：
分類器集成是目標流行的一種提高分類器性能的技術。我們知道分類器性能在模式識別中的重要性，但是有時候單個分類器的精度是有限的，而分類器集成方法正是通過集成各個分類器，構造一個更高性能的分類器，其中常用的是自助聚集(Bagging，bootstrap aggregation)方法和增強法(Boosting)方法。
Bagging從訓練集中獨立隨機選擇一定個數的數據組成自助數據集，每個自助數據集都被獨立地用於訓練一個子分類器，最終分類結果根據這些子分類器的判決結果來投票決定。
Boosting方法在訓練中先後產生一系列分類器，各個分類器所使用的訓練集都是從總訓練集提出來的一個子集，各個樣本是否出現在該子集中取決於此前產生過的分類器的表現，已有分類器判斷出錯的樣本將以較大的概率出現在新的訓練子集中。這使得其後產生的分類器更加專注於處理對已有分類器來說較為困難的樣本區分問題。
Bagging與Boosting的區別在於Bagging的訓練集的選擇是隨機的，各輪訓練集之間相互獨立，而Boosting的訓練集的選擇不是獨立的，各輪訓練集的選擇與前面各輪的學習結果有關；Bagging的各個預測函數沒有權重，而Boosting是有權重的；Bagging的各個預測函數可以並行生成，而Boosting的各個預測函數只能順序生成。
Bagging和Boosting都可以有效地提高分類器性能，但是在大多數的數據集中Boosting的準確性比Bagging要高，而在大多數應用中，準確率比運算速度更為重要，因為計算機的性價比提高很快，而且數據的訓練是離線的。因此實際中Boosting比Bagging更廣泛的應用。
Boosting方法可以增強給定算法的泛化能力，但是還存在兩個缺點該方法需要知道子分類器學習正確率的下限，而這在實際問題中是很難做到的；其次，這一方法可能導致後來的分類器過分集中於少數特別困難的樣本，導致表現不穩定。
自適應的Boosting方法(AdaBoostAdaptive Boosting)算法的基本思想是利用多個子分類器通過一定的方法疊加起來，構成一個分類能力很強的強分類器。AdaBoost算法是以Boosting算法為基礎的。AdaBoost算法不再需要預先知道子分類器的訓練錯誤率，而是通過動態調節各個子分類器的權值來對基本算法的訓練錯誤率自動適應，因而引起了廣泛的關注。與Boosting算法類似，AdaBoost方法根據既有分類器對總訓練集中的各個樣本的分類情況來調整各個樣本出現在新訓練子集中的概率。不同的是，AdaBoost不需要預先知道子分類器預測準確率的範圍，而是自動根據子分類器的預測準確率設定相應的權值。在使用AdaBoost訓練的時候，訓練錯誤率上限是一個單調下降的函數，這樣，只要基本的分類器的性能能夠穩定的超過隨機猜想，並且循環足夠長時間，就能使經驗錯誤率降至任意低的水平，並有可能保證泛化錯誤率也低於一個近似的上限。它通過建立多分類器組合使得子分類器的性能得到提升，由於其獨有的對分類器性能的自適應和對過學習現象的免疫性，近年來引起了極大的關注，並已在目標檢測中得到廣泛應用。
AdaBoost在理論上非常有優越性，但是AdaBoost在實際應用中也有很多模糊的地方(1)如何選擇最好的子分類器；(2)如何更好組合這些子分類器。
發明內容
本發明的目的是提出一種分類器集成方法，運用更有效的分類器性能評價準則選擇性能好的子分類器，減少分類器訓練時間和循環次數。
一種分類器集成方法，具體步驟為 (1)給訓練樣本權值賦初值； (2)對訓練樣本進行分類器訓練得到C個最佳子分類器，C為訓練次數； (2.1)令訓練周期t＝1； (2.2)採用權值歸一法確定各訓練樣本在第t輪訓練時的權值； (2.3)針對訓練樣本的每個特徵採取預定分類器設計方法生成相應的子分類器，從中選出最佳子分類器，並計算採用最佳子分類器對所有訓練樣本分類產生的錯誤率； (2.4)根據錯誤率更新訓練樣本權值； (2.5)如果t＜C，t＝t+1，返回步驟(2.2)，否則進入步驟(3)； (3)組合C個最佳子分類器； 其特徵在於， 所述步驟(2.3)採用以下兩種方式之一選出最佳子分類器 i、計算訓練樣本的第j個特徵對應的子分類器hj的錯誤程度 其中n表示訓練樣本的個數，xi表示訓練樣本，
wt，i表示第t輪訓練時的第i個樣本的權值，fj(xi)表示分類器hj對樣本xi的分類響應，θj表示分類閾值； 選出最小錯誤程度對應的子分類器作為最佳子分類器。
ii、計算訓練樣本的第j個特徵對應的子分類器hj的錯誤程度 其中n表示訓練樣本的個數，xi表示訓練樣本，
wt，i表示第t輪訓練時的第i個樣本的權值，fj(xi)表示分類器hj對樣本xi的分類響應，θj表示分類閾值； 計算第j個特徵對應的子分類器hj的泛化能力
，其中fj(x+)表示子分類器hj對離分類閾值θj或分類面最近的正樣本的分類響應，fj(x-)表示子分類器hj對離分類閾值θj或分類面最近的負樣本的分類響應； 計算錯誤度總和Errorj＝emj+Gj，選擇最小錯誤度總和Errorj對應的子分類器作為最佳子分類器。
本發明採用的分類器性能評價準則能夠準確地選出性能好的子分類器，子分類器性能越好，組合得到相同性能的分類器需要的子分類器數量就越少，即訓練循環的次數和時間均越少。另外，本發明還通過反饋調整組合分類器，進一步增強分類器性能。
圖1是本發明流程圖； 圖2是分層描述的分類器性能評價準則示意圖； 圖3是兩組實驗數據的分布情況，圖3(a)正負樣本為理想均勻分布，圖3(b)正負樣本為高斯分布； 圖4是使用分類器錯誤率評價準則對實驗數據的分類性能描述，圖4(a)是對圖3(a)所示數據的分類性能描述，圖4(b)是對圖3(b)所示數據的分類性能描述； 圖5是使用錯誤程度度量的分類器性能評價準則對實驗數據的分類器性能描述，圖5(a)是對圖3(a)所示數據的分類性能描述，圖5(b)是對圖3(b)所示數據的分類性能描述； 圖6是泛化能力的分類器性能評價準則對實驗數據的分類器性能描述，圖6(a)是對圖3(a)所示數據的分類性能描述，圖6(b)是對圖3(b)所示數據的分類性能描述； 圖7是使用分層結構的分類器性能評價準則對實驗數據的分類器性能描述，圖7(a)是對圖3(a)所示數據的分類性能描述，圖7(b)是對圖3(b)所示數據的分類性能描述； 圖8是本發明實施例分類訓練樣本分布示意圖； 圖9是經過優化的組合分類器性能與未優化的組合分類器性能比較圖； 圖10是經過優化且由十個以上子分類器構成的組合分類器性能和未優化的組合分類器性能比較圖。
具體實施例方式 本發明步驟流程如圖1所示，現舉例說明 設輸入n個訓練樣本(xi，yi)，i＝1，……，n，其中xi表示訓練樣本的特徵值集合，即xi＝{xi1，xi2，……，xiq}，集合中的一個元素表示一個特徵，該特徵可能是數值也可能是向量，q為特徵的個數；
已知訓練樣本中有m個負樣本，l個正樣本。
(1)設計子分類器步驟。根據已知訓練樣本確定子分類器的構造方法，訓練樣本第j個特徵生成的子分類器形式為
其中hj表示子分類器的分類結果，只能是±1，hj＝1表示子分類器分類結果為正樣本，hj＝-1表示子分類器分類結果為負樣本；fj為子分類器對樣本的分類響應，即當特徵為一個數值時fj表示特徵值，當特徵為一個向量時fj表示特徵到這個子分類器分類面的距離；θj為子分類器閾值，得到一個子分類器的同時就得到了θj，它隨著子分類器設計方法的不同而不同；pj取±1，當pj＝1時，pjfj＜pjθj表示fj＜θj，當pj＝-1時，pjfj＜pjθj表示fj＞θj。獲得分類器閾值或者分類面的子分類器可以有不同的設計方法，如神經網絡方法、最小平方誤差方法(MSE)、支持向量機(SVM)和隱馬爾可夫模型(HMM)等。
(2)初始化訓練樣本權值步驟。初始化誤差權重，w1，i表示第i個樣本的權值初始值，對於yi＝-1的樣本對於yi＝1的樣本此處沒有採用所有樣本置相同權值的方法，而是正負樣本各佔1/2。
(3)訓練分類器步驟。對於每個t＝1，...C，其中C為訓練的次數，C越大分類器性能越好，理論上隨著C增大可以達到任意高的精度，一般情況50次左右就可以得到接近90％的正確率。
(3.1)權值歸一化，使得所有權值的和為1，wt，i表示第t輪訓練時的第i個樣本的權值； (3.2)令j＝1，...q，針對特徵集合中的第j個特徵按照(1)的方法生成相應的子分類器hj，計算當前權重的分類器性能度量，使用分層描述的分類器性能評價準則評價子分類器好壞； (3.3)選擇具有最好性能的子分類器
加入到強分類器中去，並計算其錯誤率
表示子分類器
對第i個樣本的分類結果； (3.4)更新每個樣本所對應的權值 其中，wt+1，i表示第t輪訓練更新後第i個樣本的權值；如果
對第i個樣本xi正確分類，則ei＝0，反之ei＝1， (4)組合分類器步驟。生成的強分類器為
其中最佳子分類器權值 (5)優化分類器步驟。通過反饋的方法，調整分類器係數，增強分類器性能。本發明使用反饋的前向神經網絡方法，度量網絡的訓練誤差，根據誤差調整神經網絡權值，使分類器性能達到最優。
本發明設計的子分類器形式描述如下 分類器的設計實際上是一種尋優的策略，最小平方誤差方法是尋找平方誤差最小的分類器，Fisher線性判別是尋找類間散度和類內散度比例最大的分類器，神經網絡是尋找誤差函數最小時的分類器，支持向量機時最大化分類間隔的分類器。但是這些分類器的設計考慮每個樣本時平等的，但是在AdaBoost框架下，樣本的權值和前面分類器的性能時密切相關的，分類器的設計應該更專注於那些錯分的樣本，即權值比較大的樣本，權值大小不同樣本錯分的代價是不同的，因此本發明使用的最小平方誤差方法實現的，即第j個特徵按照最小平方誤差方法生成相應的子分類器hj。最小平方誤差方法中分類函數是通過分類面各分量的權值d來描述的。以mt表示當前訓練中採樣得到的樣本個數，則當前樣本的第j個特徵為xrjsj，0＜r＜mt，0＜sj＜gj，gj為第j個特徵的維數。則d＝{ds}，0＜sj＜gj。第j個特徵對應的子分類器按下面方法得到 (1)設置初始分類函數d0，設置為較小的非零隨機數，b＝{br}，0＜r＜mt表示樣本的裕量，本發明將br均置為1； (2)輸入新的樣本； (3)第u個輸入樣本為 (4)修正分類函數，按下式修正 d←d+η(u)ωu(bu-dtxuj)xuj； (5)如果分類函數的分類誤差小於一定閾值，或者迭代次數達到一定值時學習過程結束，否則轉到(2)。
η(u)控制第u次迭代中分類函數的調整幅度，本發明中採用η(u)＝η(0)/(u+1)，其中η(0)＝0.002；ωu為第u個輸入樣本的權值；dut表示du的轉置；本發明中用迭代次數控制學習的結束，當迭代次數達到10000次時迭代停止。
上述算法就得到了第j個特徵對應的子分類器，對應步驟(1)所述的子分類器設計公式
即dtxuj＞0時表示第j個特徵對應的子分類器對第u個樣本分類結果為正樣本，dtxuj＜0時表示第j個特徵對應的子分類器對第u個樣本分類結果為負樣本。
這樣可以保證樣本相同，對應權值不同的情況下得到不同的分類，這樣才能保證不會總是選擇出相同的分類器，而且該算法適合特徵為數值和特徵為向量的情況。
本發明提出的分層描述的分類器性能評價準則描述如下 分類器性能的好壞在模式分類中至關重要，因此如何描述分類器的性能直接關係到分類的好壞。在本發明中，越好的描述準則保證每次循環得到的子分類器性能越好，組合得到相同性能的分類器需要的分類器數量就少，循環的次數就少，減少了訓練的時間。
分層描述的分類器性能評價準則的結構示意圖如圖2所示。
本發明實際實施時，只要找到最好的分類器，而不需要對所有的分類器性能都詳細描述，為了說明分類器的評價準則，我們對每個分類器性能進行詳細描述，而不只是找到最好的子分類器。對於不同情況的分類器性能準則描述如下 (1)在很多情況下不同的子分類器的錯誤率是不同的，使用錯誤率性能準則就可以描述分類器的性能； (2)當有相同錯誤率的多個子分類器時，原始的錯誤率性能準則並不能很好的描述分類器的好壞，使用加入錯誤程度的性能評價準則來描述分類器的性能； (3)當多個子分類器的加入錯誤程度的性能評價準則相同時，加入泛化能力來描述分類器的性能，即使用加入錯誤程度度量和泛化能力描述結合的分類器評價準則。
這樣分層描述的分類器性能評價準則的最後一層就可以完全描述子分類器的性能。
下面以簡單的數據分布來說明本發明中提出的分類器性能準則的優越性。圖3顯示了兩組數據的分布情況，圖3(a)所示正負樣本為理想的均勻分布，圖3(b)正負樣本為高斯分布。其中圖3(a)中負樣本從0.1到1.1均勻分布，正樣本從0.9到1.9均勻分布；圖3(b)中負樣本為均值為0.6方差為0.1的高斯分布，正樣本為均值為1.4方差為0.1的高斯分布。
原算法中分類器的性能準則是分類的錯誤率，採用第j個特徵對應的子分類器hj對所有樣本分類的錯誤率描述εj為 其中n表示樣本的個數；xi表示訓練樣本的特徵值；yi＝{-1，1}對應負樣本和正樣本；wt，i表示第t輪訓練時的第i個樣本的權值；hj(xi)表示第j個特徵對應的分類器對第i個樣本的分類結果；yi表示第i個樣本的類別，即第i個樣本為正樣本或者負樣本。同一次循環中每個樣本的權值都是固定的，與特徵無關。使用該準則對上述數據的分類器性能描述如圖4所示，圖4(a)，圖4(b)分別對應中圖3(a)，圖3(b)圖。
從圖4可以看出只考慮錯誤率描述的分類器性能是比較差的，在錯誤率相同情況可能得不到最好的分類器，圖4(a)和圖4(b)中最小錯誤率對應的分類器均有多個，圖4(b)中非最小的錯誤率也有多個的情況。本發明接著嘗試使用統計錯誤樣本的同時，加入錯誤程度度量。第j個特徵對應的子分類器hj的加入錯誤程度度量描述emj形式如下 其中n表示樣本的個數；xi表示訓練樣本；yi＝{-1，1}對應負樣本和正樣本；wt，i表示第t輪訓練時的第i個樣本的權值；fj(xi)表示子分類器hj對樣本xi的分類響應；θj表示分類閾值；|fj(xi)-θj|越大表示離分類閾值或者分類面距離越遠，則錯誤程度越大。使用該準則對原始數據的分類器性能描述如圖5所示，(a)(b)分別對應圖3中的(a)(b)圖。
可以看出圖5(a)中找到了理想的分類器，但是圖5(b)仍然不能得到最好的分類器。因此在樣本錯誤率相同但不為零的情況下，加入錯誤程度度量是一個可行的方法，但是樣本錯誤率同為零時則失效。本發明考慮了分類器的泛化能力描述，在樣本錯誤率為零時加入分類器泛化能力的度量，而在樣本錯誤率不為零時，泛化能力描述為常數，判斷準則形式如下
其中Gj表示第j個特徵對應的子分類器hj泛化能力描述；fj(x+)表示離分類閾值或分類面最近的正樣本對當前子分類器的響應；fj(x-)表示離分類閾值或分類面最近的負樣本對當前子分類器的響應；θj表示分類閾值。當泛化能力描述Gj越小時分類器性能越好。使用該準則對原始數據的分類器性能描述如圖6所示，圖6(a)，圖6(b)分別對應圖3中的圖3(a)，圖3(b)。
整個分層的分類器性能評價準則最後一層的加入錯誤程度度量和泛化能力描述結合的分類器性能評價準則形式如下 Errorj＝emj+Gj 其中Errorj表示第j個特徵對應的子分類器hj分層描述的最後一層的加入錯誤程度度量和泛化能力描述結合的分類器性能，emj加入錯誤程度度量的性能描述，Gj表示該分類器泛化能力描述。Errorj越小，其對應的子分類器性能越好。整個分層的分類器性能評價準則描述如圖7所示，圖7(a)，圖7(b)分別對應圖3中的圖3(a)，圖3(b)。
從上述實驗可以看出分層描述的分類器性能評價準則能夠更好地描述分類器的性能。
最後通過反饋調整各個子分類器係數，提高分類器整體的分類性能。本發明提出的通過反饋更好組合子分類器的原理如下 沒有理論可以證明AdaBoost經典方法中依賴於獲得分類器的樣本錯誤率的設計方法是最優的，很明顯最優的分類器組合方法可以減少自分類器的個數。因此需要要尋找最優的分類器組合方法，本發明使用反饋的前向神經網絡方法，度量網絡的誤差，根據誤差調整神經網絡權值，使分類器性能達到最優。
本發明使用的神經網絡採用有監督的學習算法，即用來學習的樣本的類別是已知的。當依次輸入學習樣本時，網絡以迭代方式，根據神經元的實際輸出與期望輸出的偏差對權值進行修正，最終得到期望的權值。實際實施中，使用單層感知器網絡來實現，選擇出的子分類器作為感知器的一個神經元。本發明組合的分類器在優化前形式為 組合分類器權值α＝{αt}，t＝1，…，C，αt表示用於組合的最佳分類器權值。本發明使用的單層感知器網絡共有C個神經元，使用該方法更新權值α具體算法如下 (1)獲取初始權值α＝{αt}，t＝1，…，C，令k＝1； (2)輸入學習樣本xk； (3)計算神經元的實際輸出。設第k次輸入的學習樣本為xk，與第t個神經元連接的權值為αt，第t個神經元的實際輸出為
為訓練分類器步驟中選擇的第t個最佳子分類器對樣本xk的分類結果。
(4)更新權值。由於每個樣本只有正負樣本兩種情況，因此C個神經元的期望輸出均為yk，權值按下式更新 (5)如果採用權值α得到正確分類結果，或者k大於或等於迭代次數時結束，否則k＝k+1，轉到步驟(2)。
其中調整參數λ∈(0，1)控制權值調整的大小，若λ取值太大，算法可能出現振蕩；若λ取值太小，收斂速度很慢。本發明中當k超過迭代次數2000時學習結束。
本發明使用的實驗數據描述如下共5000個樣本，正負各2500個，分布如圖8所示，每個樣本有兩個特徵組成，每個特徵的維數均為1。按照本發明的流程，使用最小平方誤差方法來設計子分類器，用分層的分類器性能評價準則來選擇最好的分類器，然後本發明比較了優化和沒有優化的分類器性能經過反饋神經網絡優化後(本發明在此實驗中λ取0.002)分類器組合性能和沒有優化的分類器組合性能比較如圖9所示，對應圖8的樣本數據。圖10顯示超過十個分類器後的比較情況。
從圖9和圖10的實驗結果可以看出，優化後的分類器分類後錯誤樣本數比優化前的小，而且增加一個子分類器後增大的情況在優化前分類器中比較明顯，優化後的分類器則減緩了很多，理論上優化可以完全消除這種情況。通過反饋調整分類器係數後，分類器的性能得到了提高。
權利要求
1.一種分類器集成方法，包括以下步驟
(1)給訓練樣本權值賦初值；
(2)對訓練樣本進行分類器訓練得到C個最佳子分類器，C為訓練次數；
(2.1)令訓練周期t＝1；
(2.2)採用權值歸一法確定各訓練樣本在第t輪訓練時的權值；
(2.3)針對訓練樣本的每個特徵採取預定分類器設計方法生成相應的子分類器，從中選出最佳子分類器，並計算採用最佳子分類器對所有訓練樣本分類產生的錯誤率；
(2.4)根據錯誤率更新訓練樣本權值；
(2.5)如果t＜C，t＝t+1，返回步驟(2.2)，否則進入步驟(3)；
(3)組合C個最佳子分類器；
其特徵在於，
所述步驟(2.3)採用以下兩種方式之一選出最佳子分類器
i、計算訓練樣本的第j個特徵對應的子分類器hj的錯誤程度
其中n表示訓練樣本的個數，xi表示訓練樣本，
wt，i表示第t輪訓練時的第i個樣本的權值，fj(xi)表示分類器hj對樣本xi的分類響應，θj表示分類閾值；
選出最小錯誤程度對應的子分類器作為最佳子分類器。
ii、計算訓練樣本的第j個特徵對應的子分類器hj的錯誤程度
其中n表示訓練樣本的個數，xi表示訓練樣本，
wt，i表示第t輪訓練時的第i個樣本的權值，fj(xi)表示分類器hj對樣本xi的分類響應，θj表示分類閾值；
計算第j個特徵對應的子分類器hj的泛化能力
，其中fj(x+)表示子分類器hj對離分類閾值θj或分類面最近的正樣本的分類響應，fj(x-)表示子分類器hj對離分類閾值θj或分類面最近的負樣本的分類響應；
計算錯誤度總和Errorj＝emj+Gj，選擇最小錯誤度總和Errorj對應的子分類器作為最佳子分類器。
2.根據權利要求1所述的分類器集成方法，其特徵在於，所述方法還包括步驟(4)調整組合分類器權值，具體為，
(4.1)獲取組合分類器權值α＝{αt}，t＝1，…，C，αt表示用於組合的最佳子分類器權值，令k＝1；
(4.2)輸入已知類別訓練樣本xk；
(4.3)獲取採用組合分類器對訓練樣本xk的分類結果
(4.4)更新權值λ為調整參數，
為所述步驟(2)在第t個訓練周期內選擇的最佳子分類器對樣本xk的分類結果，yk為所述步驟(2)在第t個訓練周期內選擇的最佳子分類器對樣本xk的期望分類結果；
(4.5)如果採用權值α得到正確分類結果或者k大於或等於迭代次數，結束，否則k＝k+1，轉到步驟(4.2)。
全文摘要
一種分類器集成方法，包括(1)初始化訓練樣本權值；(2)對訓練樣本進行分類器訓練，採用錯誤程度和泛化能力描述的分類器性能評價準則選出多個最佳子分類器；(3)組合最佳子分類器。本發明採用的分類器性能評價準則能夠準確地選出性能好的子分類器，子分類器性能越好，組合得到相同性能的分類器需要的子分類器數量就越少，即訓練循環的次數和時間均越少。另外本發明還通過反饋調整組合分類器，進一步增強分類器性能。
文檔編號G06K9/62GK101231702SQ200810046789
公開日2008年7月30日 申請日期2008年1月25日 優先權日2008年1月25日
發明者高常鑫, 農 桑, 王嶽環, 唐奇伶, 密 李, 峻 高, 笪邦友 申請人:華中科技大學