作用于大數據處理的級聯分類器泛化設計

李庭燎 劉馨雨 杜寧 符垚晗

摘? 要： 針對級聯分類器的設計主要集中于分類器組合優化等方面，有關自動化設計研究相對較少。為了簡化設計流程，設計一種方法以自動設計具有理想性能的級聯分類器。這種方法不需要分別考慮每個可能的級聯長度并通過最終數值優化來進一步確定每個級聯長度的次優參數，而是向能夠設置級聯的泛化邊界方向來研究，探討如何簡化級聯分類器的設計流程，實現自動化設計。

關鍵詞： 級聯分類器； AdaBoost算法； 大數據； 機器視覺； ROC曲線

中圖分類號：TP391.41? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2023）05-36-04

Cascade classifier generalization design for big data processing

Li Tingliao， Liu Xinyu， Du Ning， Fu Yaohan

（Nanjing Audit University， Nanjing， Jiangsu 211815， China）

Abstract： The design of the cascade classifier mainly focuses on the classifier combination optimization， and there are relatively few studies on the automation design. In order to simplify the design process， a method is designed to automatically design a cascade classifier with ideal performance. Instead of considering each possible cascade length separately and further determining the suboptimal parameters for each cascade length by final numerical optimization， this method is investigated in the direction of being able to set generalization bounds for the cascade， and explores how to simplify the design process of cascade classifiers and achieve automated design.

Key words： cascade classifier; AdaBoost algorithm; big data; machine vision; ROC curve

0 引言

大數據技術的戰略意義不在于掌握龐大的數據信息，而在于對海量快速流轉的低價值密度數據進行專業化處理。伴隨著云計算的興起和社交網絡軟件的整合推進，網絡數據呈現出愈來愈龐大、愈來愈復雜的特點，然而用于構建社交數據以從中對大數據進行理解、分析和推斷的工具很少。近年來，級聯分類算法在數據處理方面吸引了越來越多的關注，其可用于解決幾乎所有需要在某些條件下過濾數據然后再使用另一種條件過濾的問題。由于實時的大型數據集分析需要有效處理大量的容忍經過時間內的數據，級聯分類算法成為了大數據技術應用到實踐領域的一塊基石。

在分類的工作中，研究人員一般會融合多種機器學習算法，進而提升分類的準確性。經過運用不同方法能夠設計實現差異化的分類器，例如對相同分類器使用不同訓練集、對相同分類器調節不同參數等[1]。對于訓練中存在的數據不均衡等情況，傅紅普提出了可以應用等同復雜水平的AdaBoost分類器的級聯來測定行人，其設計實現的朋輩級聯不限制分類器的復雜水平，從而能夠運用更多負訓練樣本[2]。Maale和Nandyal提出了一種基于Haar級聯分類器的3階段人臉檢測系統架構，可以運用Haar級聯分類器對像素人臉開展檢測[3]。Faisal等人對Haar級聯分類器獲取的人臉進行特征化處理，運用LBPH算法提取直方圖特征，進而完成了實時的人臉檢測[4]。李昆侖等設計實現了基于級聯SVM和分類器融合的人臉圖像性別識別方法，把識別難易水平不同的樣本劃分成若干層次來開展訓練[5]。Wu等人提出了一種漏斗結構級聯（FuSt）檢測框架，一方面，其結構使用多個計算有效的分布式分類器，來提出少量的候選窗口，其具有高召回率的多視圖人臉；另一方面，通過使用統一的MLP級聯，以集中的方式檢查所有視圖的建議，為高精度和低時間成本的多視圖人臉檢測提供了有利的解決方案[6]。蘭勝坤認為，AdaBoost算法屬于非常完善的人臉檢測算法，AdaBoost算法內人臉的特征選取的是矩形特征，在大量的樣本集內，提取樣本的矩形特征進行訓練，生成多個弱分類器，然后合并多個弱分類器組合為強分類器，最后級聯強分類器形成最終的分類器，進而當作人臉識別的依據[7]。

通過文獻總結和歸納可以發現，目前國內外學者針對級聯分類器的設計主要集中于分類器組合優化，且在設計層面注重算法的優化，主要關注對級聯分類器進行改進，已具備一定的研究深度。不過目前級聯分類器設計的研究廣度較為狹窄，關于級聯分類器的自動化、智能化設計的研究相對較少。因此，本文主要研究如何簡化級聯分類器的設計流程，實現自動化設計。

1 級聯算法

1.1 級聯算法分析

級聯（cascade）是計算機科學領域里的一個專有名詞，一般是指多個目標之間存在的一種映射關系。計算程序通過搭建各個數據之間的級聯關系，訓練出多個不同的分類器并且將這些所有的分類器聯合起來，最終形成一個高正確率的級聯分類器，從而使得計算效率可以大大提高，并降低了失誤率。因此，級聯算法成為計算機領域非常常見的一個概念。通俗來講就是把多個目標對象按照一定的規則，有等級地或者是有梯度地聯結在一起，類似于樹形結構一樣，有層次地把這些對象組織在一起形成一個完全獨立的算法結構。在這個算法結構里，當你對某個數據進行操作的時候，會影響這個數據關聯的所有數據，即會對這些數據進行相應的操作從而達到所求目的的效果。傳統分類算法的局限性之一在于他們難以處理不平衡的數據，因為傳統的機器學習方法通常將類平衡作為先決條件[8]。而級聯提供了通過對不良學習者決策進行加權平均來訓練極其精確的分類的機會[9]。

通過大量的試驗數據分析，可以得出級聯算法和單個大提升算法之間的主要區別在于這兩種算法對于各自分類器數量和錯誤率的架構要求不同，級聯算法可以做到及時地拒絕真負類，隨時終止程序的運行，從而減少整個計算過程中程序本身所加的負載[10]。考慮到這一特殊情況，本文結合級聯算法的這些優點，從單個大增強分類器作為基點構建出一個級聯算法，以便于篩選計算出大增強分類器中弱分類器的子集，從而可以測試出我們輸入的到底是正還是負。通常來講，如果子集輸出結果顯示為正的，則繼續計算另一個弱分類器子集，并再次測試，以此類推，不斷重復上述計算過程，直到輸入被拒絕或者計算出完整的增強分類器結束程序。

1.2 增強算法架構

假設通過增強一組弱分類器，在給定的數據集上實現期望的真正率和真負率，直到分類器的ROC曲線超過所需的真正負比。以此方式獲得由弱分類器h1（X），…，hT （X） 和權重α1，…，αT定義的增強分類器HB（X）：

[HB（X）=1? ? ? ? ? t=1Tαtht（X）≥0-1? ? ? ?t=1Tαtht（X）<0] ⑴

引入一個數據集X1，…，XN，已知類別y1，…，yN（yN∈{?1，1}）。定義I +為使HB （Xn）=1的角標n的集合，定義I?為使HB （Xn）=-1的角標n的集合。

在實踐中，通常將θ t設置為n∈I+的Gt（Xn）>θ t與大于前式且n∈I?的最小Gt（Xn）之間的中點?？紤]到改進級聯分類算法所示的算法結構的特征是測試時間序列T1，…，TL和閾值θ1，…，θL，于是可以定義中間實值分類器：

[Gt（X）=s=1tαshs（X）] ⑵

又定義閾值θ t，使得其對于任意正例n∈I+，恒有Gt（Xn）>θ t，故可得：

[θl=θ'Tl] ⑶

容易得到通過該選擇且獨立于T1，…，TL時，改進算法中定義的級聯在訓練數據上的輸出與原始增強算法完全相同。

我們通過對分類器的復雜度計算來建構一個模型，并從給定的增強分類器上派生出的所有級聯中，確定一個近乎于最佳的級聯[11]。雖然在這之前已經有不少研究者考慮了評估分類器的成本，但是相比傳統方法，如假設一個增強分類器的計算成本的近似模型是其假正率的函數，很明顯，本文中采用的動態規劃方法只需要采用很少的假設和很少的計算步驟，就能獲得近乎最優的序列，在減少程序計算時間的同時也帶來了更多的便利，大大提高了計算效率。

1.3 級聯分類改進

給定一組弱分類器[h1（）， h2（），…， hT（）]和由增強分類器HB（X）提供的權重，設置級聯調度1=T0

當l ≤ L時，令：

[Fn+1（X）=Fn（X）+αTl-1hTl-1（X）] ⑷

若[Fn（X）<θl]，將X歸類為負，即[H（X）=-1]；若[Fn（X）≥θl]，將X歸類為正，即記[H（X）=1]，本輪計算結束，輸出結果。定義[l=l+1]，繼續重復以上步驟直至[l>L]。從而得到最終的強分類器：[H（X）=sign（Fn（X））]。

從上述改進級聯分類算法中可以看出，所提供的分類器[H（X）]的正輸入集合包含在了其增強分類器[HB（X）]的正輸入集合中。[H（X）]的真正率比[HB（X）]低，而它的真負率比[HB（X）]要高得多。因此，由ROC（Receiver Operating Characteristic，接收者操作特征曲線）可以得知與[H（X）]對應的點的分布位于[HB（X）]對應點的分布的下方和左側區域。

這種算法的特點在于權重選擇和上面引用的級聯分類器方面與AdaBoost有明顯的相似之處。對比當下討論的三種不同的體系架構，在傳統AdaBoost算法中，所有弱分類器被一次性計算出來并分類；而在上述所提出的計算方法和傳統級聯算法中，在每次測試之間只計算弱分類器中的單獨一個子集，后者中只需進行幾次弱分類器評估即可實現負分類。從單個大增強分類器作為基點構建出的級聯算法，與傳統級聯算法的主要區別在于：假設權值和弱分類器相同，前者將上一個分類器的輸出結果保留成為了下一個分類器的輸入。結果顯示，所提方法中最后一個分類器的輸出就達到了與傳統AdaBoost增強算法的輸出完全相同的效果[12]。而改進版本的級聯算法與傳統級聯方法之間的區別在于，該方法在每個決策中都考慮了先前決策階段的輸出，這樣在保證算法準確性的同時有效提高了算法效率。

2 計算優化級聯設計

2.1 動態規劃

再次回到改進級聯分類算法中去，H （X）的輸出由弱分類器[h1（X），…，hT（X）]和權重α1，…，αT ，這些定義了增強分類器中的HB （X），但同時這些數據也由測試的時間點[T1，…，TL]和它的閾值[θ1，…，θL]來定義。Tl和θl的選擇是能夠獲得計算效率高的分類器的決定性因素。表面上，設置這些參數似乎和設置常規級聯分類器的參數一樣都比較困難。然而，使用動態規劃可以保留提升分類器在任何給定數據集上的輸出，在驗證其的所有級聯中，就分類器的計算成本而言，幾乎是最優的。上述方法除了參數設置更加簡便的優點，還可以更容易地選擇檢測器的真正率和真負率。實際上，在增強的分類器中，只有一個惟一的閾值，這個閾值決定了ROC曲線上分類器所處的位置點的集合。在構建級聯之前只需要設置好這個閾值就足夠了，從而能夠保證級聯可以達到ROC曲線上這個分類器的位置（對于給定的數據集）。由于構建級聯的計算成本相對于增強的計算成本完全可以忽略不計，因此對于原始增強算法所能達到的ROC曲線上的任何點位，都很容易構建出來一個分類器。相比之下，以前的級聯方法，要么需要為每個期望的ROC點訓練一個新的級聯，要么使用一種特別的方法來調整增強分類器的閾值，就要復雜很多。

使用改進級聯分類算法的體系結構構建出一個計算最優級聯，該級聯在訓練數據上具有與增強分類器完全相同的輸出，也同時描述了構建分類器級聯的重要步驟。此外，所提出的級聯方法并不局限于某些特定的增強方法，可以使用針對給定成本指標的增強分類器，或旨在提高計算的效率。

2.2 級聯成本

與以往成效較低的推銷策略相比，當前缺乏能精準推薦，減少資源浪費的大數據分析工具。當前應用較多的能夠在眾多數據中找到有效信息的技術是策略樹，它可以按照客戶的偏好為其推薦更貼合他們需求的產品，同時能夠對他們的需求進行有效預測。但在數據過于宏大，客戶資料過于龐雜的情況下，決策樹也暴露其缺點：想要及時準確的對客戶的偏好和需求等情況進行正確的預測，就必然以高昂的計算成本作為代價。如何平衡精準度和計算成本之間的關系成為當前種子集合所面臨的重大難題之一。

設置試驗序列[T1，…，TL]，從級別t ∈{1，…，T }開始的最優級聯的成本Ct可以從成本Cs >t遞歸定義，由此使用動態規劃可以有效地獲得最優計算成本，節約計算時間?？梢灶A測從t開始的最優級聯必然存在以下情況之一：

⑴ 由計算所有剩余分類器和測試結果組成的普通級聯；

⑵ 由計算分類器t，…，T-1組成的級聯，在T-1處進行測試，并遵循從T-1到T的最佳順序，直至在（T-t+1）處計算第t個弱分類器，測試并遵循從t+1到T的最優順序。

考慮改進級聯分類算法類型的任何級聯，At是第t個弱分類器的計算成本，B是在目標計算機上執行測試的成本，滿足條件：

[Al=Tl-1≤t≤TlAt] ⑸

可得期望實際輸入的計算成本C：

[C=l=1L（ATl-1+B）qTl-1]? ⑹

設置t時刻最小級聯計算成本[Ct=minCt，st

[Ct，s=qt s=tTAs? ? ? ? ? ? ? ?s=Tqts=tTAs +Cs+1? ? ? t ≤s≤T-1] ⑺

盡管這是增強分類器的預期行為，但是有的時候對于給定的數據集卻不一定是這種預期的情況。在實踐中通過大量的試驗可以發現，這些序列往往并不存在單調性，故可以使用平滑法對其進行處理。由于發現非平穩序列的一般線性趨勢是單調的，所以可以認為結果序列的成本接近真正的最小值。

3 結束語

本文提出一種方法來自動設計具有理想性能的級聯分類器，特別針對于某些給定類型的輸入和給定的計算機架構來進行計算。這種方法適用于任何底層的增強方法，包括以自適應增強為特征的AdaBoost算法以及針對ROC空間給定區域的增強方法。由于產生的級聯與其底層的增強分類器密切相關，故可以預期這種級聯的理論屬性將比臨時級聯更容易進行研究。相較于它在給定數據集上的性能，這種方法更傾向于探究級聯的泛化邊界問題，在大數據實用領域作為其他特化級聯增強算法的基礎。在未來的研究中仍然需要找到設置級聯水平閾值更加合適的方法，以便更好地去附和原始分類器的ROC，從而能達到比實驗部分顯示的更好的一個水準。

參考文獻（References）：

[1] 馮昊，李樹青.基于多種支持向量機的多層級聯式分類器研究及其在信用評分中的應用[J].數據分析與知識發現，2021，5（10）：28-36

[2] 傅紅普，鄒北驥，朱承璋，等.基于朋輩AdaBoost分類器級聯的行人檢測（英文）[J].Journal of Central South University，2020，27（8）：2269-2279

[3] Bhavana R. Maale，Dr. Suvarna Nandyal. Face RecognitionBased on Haar Cascade Classifier[J].Journal of Research in Science and Engineering，2021，3（5）

[4] Izhar Faisal，Ali Sajid，Ponum Mahvish，MahmoodMuhammad Tahir，Ilyas Hamida，Iqbal Amna. Detection & recognition of veiled and unveiled human face on the basis of eyes using transfer learning.[J]. Multimedia tools and applications，2022

[5] 李昆侖，張炘.級聯SVM和分類器融合的人臉性別識別方法[J].計算機工程與應用，2017，53（8）：154-158

[6] Shuzhe Wu， Meina Kan， Zhenliang He，et al. Funnel-structured cascade for multi-view face detection with alignment-awareness[J]. Neurocomputing，2017，221

[7] 蘭勝坤.基于AdaBoost算法的人臉檢測實現[J]. 電腦與信息技術，2021，29（2）：16-19

[8] Fu Y G， Huang H Y， Guan Y， et al. EBRB cascade classifierfor imbalanced data via rule weight updating[J]. Knowledge-Based Systems，2021，223：107010

[9] Hassen O A， Abu N A， Abidin Z Z， et al. A new descriptorfor smile classification based on cascade classifier in unconstrained scenarios[J]. Symmetry，2021，13（5）：805

[10] Mohamed Soha Abd ElMoamen，Mohamed MarghanyHassan，Farghally Mohammed F.. A New Cascade-Correlation Growing Deep Learning Neural Network Algorithm[J]. Algorithms，2021，14（5）

[11] Chia-Chi Wu，Yen-Liang Chen，Kwei Tang. Cost-sensitive decision tree with multiple resource constraints[J]. Applied Intelligence，2019，49（10）

[12] 金相宏，李琳，鐘珞.基于主題模型和情感分析的垃圾評論識別方法研究[J].計算機科學，2017，44（10）：254-258