數據流決策樹集成分類算法綜述

申明堯 韓 萌 杜詩語 孫 蕊 張春硯

(北方民族大學計算機科學與工程學院 寧夏 銀川 750021)

0 引 言

近年來，隨著技術的快速發展，互聯網每天都會產生海量的數據，如超市交易、互聯網搜索請求、電話記錄、衛星數據和天文學等。數據流的出現改變了人們存儲、通信和處理數據的方式。與傳統的數據集相比，數據流呈現出連續、高容量、開放式和概念漂移的新特征[1]。在數據流中，數據到達的速度遠快于傳統算法中多遍掃描和重復分析的速度，因此傳統算法無法有效處理數據流。目前，數據流模型已廣泛應用于生活中的各個領域，逐漸成為數據傳輸的主流趨勢。決策樹算法作為數據流分類最有效的方法之一，具有速度快、實用、易于理解、容易提取規則等優點[2]，在醫療診斷、天氣預報、行為分析和網絡安全等領域發揮出越來越重要的作用。

數據流決策樹分類算法按照分類模型可分為決策樹單分類算法和決策樹集成分類算法。相較于單分類算法，決策樹集成分類算法具有更好的時空效率和更高的準確性，因此被廣泛應用于各種分類任務。其中，隨機決策樹(Random Decision Tree, RDT)[3]和隨機森林(Random Forest, RF)[4]是經典的兩個算法，后續出現的大部分算法都是基于它們實現的。例如，數據流的半隨機多決策樹算法(Semi-Random Multiple decision Trees for Data Streams, SRMTDS)[5]、多個半隨機決策樹算法(Multiple SemiRandom Decision Trees, MSRT)[6]、隨機普通集成算法(Random Ordinality Ensembles, ROE)[7]、基于聚類的分類器選擇算法(Classifier Selection Based on Clustering, CSBC)[8]和在線隨機森林算法(Online Random Forest, ORF)[9]等。此外，用于概念漂移檢測和處理的決策樹集成算法有基于隨機決策樹的概念漂移檢測算法(Concept Drifting Detection Based on Random Ensembling Decision Tree, CDRDT)[10]、不確定處理概念漂移快速決策樹算法(Uncertainty-handling Concept-adapting Very Fast Decision Tree, UCVFDT)[11]、基于概念漂移數據流的集成決策樹算法(Ensemble Random Decision Trees for Concept-drifting Data Streams, EDTC)[12]、隨機決策樹算法(Random Decision Tree, RDT)和霍夫丁選項樹算法(Hoeffding Option Tree, HOT)[13]等。

本文的主要貢獻如下：(1) 分別從Bagging、Boosting和Stacking三種集成學習框架的角度對決策樹集成分類算法進行了詳細的分類和總結。(2) 對數據流中存在的概念漂移問題及其處理方法進行了分析和總結。(3) 從多角度對文章中所提及的算法進行分析，有助于研究者們根據算法的優缺點選擇合適的算法進行下一步研究工作。

1 集成學習框架

集成學習的思路是通過合并多個模型來提升機器學習性能，這種方法相較于單個模型通常能夠獲得更好的預測結果。集成方法是目前最有前途的研究方向之一[14]，已經被證明是提高預測精度或者可以將復雜、困難的學習問題分解為更簡單、容易的子問題的有效方法[15]。其目標為將不同的分類器組成一個元分類器，與單分類器相比，元分類器具有更好的泛化性能。集成分類器的大致圖解如圖1所示。

圖1 集成分類器圖解

一般來說，集成學習框架主要分為三大類，分別為用于減少方差的Bagging、用于減少偏差的Boosting和用于提升預測結果的Stacking。

1.1 Bagging

Bagging是一種簡單而有效的方法，用于生成獨立模型的集合，其中使用從原始數據集中取得的實例樣本來訓練每個誘導器[16]。它從訓練集中進行子抽樣組成每個基模型所需要的子訓練集，對所有基模型預測的結果進行綜合產生最終的預測結果。算法具體過程如圖2所示。

圖2 Bagging算法圖解

(1)

國內外的研究者們已對基于Bagging集成學習框架的決策樹分類算法進行了相關研究，開發并更新了大量的算法模型，以滿足人們的需求。Fan等[3]提出了一種隨機決策樹(RDT)算法，該算法只需掃描一次訓練數據，以更新多個隨機樹中的統計數據，且所構造樹的結構完全獨立于訓練數據。結果表明，隨機樹算法的存儲器需求明顯少于學習單個最佳樹，即使非常大的訓練數據也可能完全保存在主存儲器中。此外，基于Breiman提出的隨機森林算法[18]，Abdulsalam等[19]提出了一種擴展的在線流隨機森林算法，使用節點窗口和樹窗口來決定何時構建新樹、轉換邊界節點或執行有限形式的修剪。同時，Hu等[5]設計了一種用于數據流的半隨機多決策樹增量(Semi-Random Multiple decision Trees for Data Streams, SRMTDS)算法，其在葉片處引入樸素貝葉斯分類器，提高了樹的預測精度。在此基礎上，Li等[6]提出了一種基于半隨機多決策樹的MSRT概念漂移數據流算法。與SRMTDS算法相反，它首先生成不同類型節點對應的備選子樹，然后利用Hoeffding界的不等式，使用兩個閾值來區分真正的概念漂移和噪聲。但是，由于在構建原始樹時需要準備額外的子樹，因此對空間和運行時開銷的要求更高。Oza等[20]引入了在線套袋，它提出了標準套袋的限制，要求提供預先提供的整套訓練套件用于學習。假設在線學習中，每個新的傳入實例可以在每個基類分類器的更新過程中被復制零次、一次或多次。Lee等[21]進一步發展了這種方法的理論基礎，提出了一個貝葉斯在線Bagging，相當于批量貝葉斯版本，與無損學習算法相結合，獲得了無損的在線裝袋方法。Bifet等介紹了Oza算法的兩種修改，稱為自適應大小Hoeffding樹(Adaptive-Size Hoeffding Tree, ASHT)[22]和Leveraging Bagging[23]，旨在為基類分類的輸入和輸出增加更多隨機化。霍夫丁選項樹(Hoeffding Option Trees, HOT)[24]可以看作是Kirkby選項樹的擴展。它允許每個訓練示例更新一組選項節點而不僅僅是一個單獨的葉子。它提供了一個緊湊的結構，就像一組加權分類器一樣。和常規的Hoeffding樹相似，它們是以增量方式構建的。Gama等[25]提出了一種超快速樹木森林(Ultra Fast Forest of Trees, UFFT)算法，使用Hoeffding樹的集合進行在線學習。它們的拆分標準僅適用于二元分類任務。為了處理多類問題，應用二進制分解，為每個可能的類對構造二叉樹。當新實例到達時，只有當二進制基類分類器使用此實例的真實類標簽時，才會更新每個分類器[26]。裝袋算法的另一種變型是改進的裝袋算法(Improved Bagging Algorithm, IBA)[27]。IBA通過用信息熵標記每個樣本來改進重采樣過程。Bagging++[28]是通過利用Bagging從傳入的數據塊構建新模型而設計的，作為對Learn++的優化。

1.2 Boosting

Boosting指的是通過算法集合將弱學習器轉換為強學習器，其主要原則是訓練一系列的弱學習器。所謂弱學習器是指僅比隨機猜測好一點點的模型，例如較小的決策樹，訓練的方式是利用加權的數據，在訓練的早期對于錯分數據給予較大的權重。Boosting是一個迭代的過程，每次在新分類器中強調上一個分類器中被錯誤分類的樣本(增加錯誤分類樣本的權重)，最后將這些模型組合起來的方法。每次對正確分類的樣本降權，對錯誤分類的樣本加權，最后分類器是多個弱分類器的加權組合。算法具體過程如圖3所示。Boosting不是像Bagging那樣重新采樣訓練數據集，而是調整訓練數據集的分布[29]。

圖3 Boosting算法圖解

Boosting方法大多采用加性模型來組合弱學習器，即可以將集成的學習器表示為如下形式[30]：

(2)

式中：hm表示第m個基學習器；βm表示第m個基學習器的系數；am表示第m個基學習器的參數；M表示基學習器的個數。對于Boosting樹方法，由于基學習器的系數βm為1，可將加性模型簡寫為：

(3)

在給定損失函數L及訓練數據的條件下，學習加性模型就是一個搜尋參數使得損失函數極小化的過程，即：

(4)

此時，直接求解這個極小值是個很復雜的優化問題，采用前向分步算法來簡化這一問題。前向分步算法本質上是一種貪心算法，它通過每一步只學習一個基函數及其系數，逐步逼近優化目標來簡化復雜度。

首先，重寫一下加性模型的表達形式，共生成M個基分類器，當前迭代次數為m，即在第m個循環中，Boosting樹的加性模型可以寫為：

Hm(x)=Hm-1(x)+hm(x;am)

(5)

前向分步算法只要求在第m輪時，優化當前輪次的基學習器的參數，使得損失函數最小以簡化算法，即：

(6)

這里優化當前輪次的基學習器的參數，在經典的GBDT[31]算法中，采取的是非常暴力的遍歷的方式，即在每個節點劃分的時候，遍歷所有屬性和可能的節點劃分數值，在當前指定的損失函數下使損失達到最小。

當采用平方損失函數，即：

L(y,Hm)=(y-Hm)2

(7)

得到：

L(y,Hm-1(x)+hm(x;am))=

[y-Hm-1(x)-hm(x;am)]2=

[r-hm(x;am)]2

(8)

式中：r=y-Hm-1(x)即上一輪基學習器訓練完成以后，m-1個基學習器與標簽的殘差。所以，對于回歸問題的Boosting樹而言，每一步只需要擬合當前模型的殘差即可。

在應用Boosting進行分類的決策樹集成算法中，最經典的算法便是梯度提升決策樹算法(Gradient Boosting Decision Tree, GBDT)[31]。它是建立在一堆回歸決策樹之上的集合模型，具有眾所周知的泛化能力。作為基于迭代積累的監督決策樹算法，它構造了一組弱學習器(樹)并將結果累積為最終預測輸出。它具有適應性，易于理解。此外，它產生高度精確的模型[32]，并成功應用于各種應用中。XGBoost[33]是一個相當成熟的基于GBDT的機器學習范例。它是一個大規模的分布式梯度提升庫，實現了尋找近似分裂點并允許并行計算的GBDT算法。此外，基于Online Boosting算法，Pocock等[34]提出了一種在線非平穩提升算法(Online Non-Stationary Boosting, ONSBoost)，該算法提供了一種應對流數據中概念漂移的方法，同時保持在線提升的有用屬性，即處理流數據的增量學習的能力，以及固定數量的分類，從而固定內存使用。Freund等[35]提出了一種自適應提升算法(AdaBoost)，它是用于構建集合模型的著名的依賴算法之一，其主要思想是關注以前在訓練新誘導器時錯誤分類的實例。Chu等[36]提出了數據流自適應挖掘的快速輕增壓算法。它基于動態樣本權重分配方案，該方案通過變化檢測進行擴展以處理概念漂移。變化檢測方法旨在實現可能導致整體性能嚴重惡化的重要數據變化，并將過時的集合替換為從頭開始構建的集合。

1.3 Stacking

Stacking是通過一個元分類器或者元回歸器來整合多個分類模型或回歸模型的集成學習技術。與投票和平均不同，Stacking是一個通用的組合過程，其中基本分類器在一個串行模型中非線性組合。在疊加過程中，基分類器稱為一級分類器，組合器稱為二級分類器(或元分類器)。Stacking的基本思想是利用原始訓練數據集訓練多個一級分類器，然后利用第一級分類器生成的新數據集訓練第二級分類器，將第一級分類器的輸出作為新訓練數據集的輸入特征，原始標簽仍然是新訓練數據的標簽[29]。

Stacking最初來源于Wolpert[37]提出的“堆疊泛化”思想，它通常可以通過從元數據中提取知識來提高分類性能。然而，疊加泛化是非常耗時的，因為通常依賴于V-fold交叉驗證過程來估計作為元分類器輸入的每個樣本的后驗類概率，以及許多其他疊加方法[38-39]。Bifet等[40]提出了一種使用堆疊結合受限制的Hoeffding樹算法，該算法使用堆疊結合有限屬性集樹分類的窮舉集合，可為給定用戶指定大小k的所有可能屬性子集生成樹分類。此外，由于其算法局限性，該算法僅適用于具有少量屬性的數據集。Mashayekhi等[41]根據規則選擇的規則準確性和覆蓋率計算了決策樹集合獲得的規則得分，并使用爬山法搜索了一組好的規則。在另一項研究中，Mashayekhi等[42]基于具有下坡移動的爬山方法和稀疏組套索方法，設計了一種啟發式搜索方法，從黑箱隨機森林模型中提取有效規則。Wang等[43]提出了一種基于XGBoost-LR的Stacking集合信用評分模型。該模型使用XGBoost作為基類分類器，并結合隨機子空間和Bootstrap算法來增加基類分類之間的多樣性。Logistic回歸模型用作次要學習者，將每個XGBoost的結果作為特征變量學習以獲得評估模型。Necati等[44]通過修改模型生成和選擇技術，采用不同的分類算法作為組合器方法，對Stacking方法進行了改進，與純機器學習技術相比，該方法始終能提供更高的精度結果。

2 概念漂移問題

2.1 問題描述

概念漂移(Concept Drift)表示目標變量的統計特性隨著時間的推移以不可預見的方式變化的現象。隨著時間的推移，模型的預測精度將降低。

根據預測分類的類別，概念漂移問題可以分為兩類，分別為真實概念漂移和虛假概念漂移,如圖4所示。

(a) 原始數據 (b) 真實漂移 (c) 虛假漂移圖4 概念漂移類型

研究發現，許多學習算法都被用于處理概念漂移，它們分別是基于規則的學習、決策樹、樸素貝葉斯和基于實例的徑向基函數學習。此外，Cunningham等[45]提出了一種基于實例的動態用于處理概念漂移。Schlimmer等[46]提出了一種基于增量學習的新方法。該方法基于分布式概念描述，分布式概念描述由一組加權符號描述組成。該方法通過在實例描述中為每個學習到的概念添加一個屬性，從而在隨后的學習中利用先前獲得的概念定義。Bifet等[47]提出了一種基于自適應窗口的方法，該方法可以檢測不同類型的漂移，其基礎是對數據塊進行逐塊處理，測量連續兩個批次之間的差異，作為漂移指示器。實驗結果表明，該方法具有較好的漂移檢測能力，可以近似地找到概念漂移位置。

2.2 概念漂移處理方法

DDM(漂移檢測方法)[48]是數據流概念漂移檢測方法中經典算法之一，它使用二項分布來檢測變化，并可以處理在預測期間由學習模型產生的分類錯誤。在DDM的基礎上，Manuel等[49]提出了早期漂移檢測方法(Early drift detection method, EDDM)，該方法是對DDM的改進，用以檢測概念漂移。其基本思想為找出分類錯誤之間的距離以檢測變化。它可以在不增加誤報率的情況下檢測變化，并能夠檢測緩慢的漸變。該研究表明，它將改善預測的結果。Bifet等[50]提出了一種基于自適應窗口(ADWIN)的方法，該方法可以檢測不同類型的漂移，基于通過塊處理數據塊并測量兩個連續批次之間的差異，作為漂移指示器。實驗結果表明，該方法能夠檢測漂移并且可以近似地找到概念漂移位置。Frias等[51]提出了一種基于Hoeffding邊界的漂移檢測方法(HDDM)，該方法是基于窗口的方法，它涉及移動平均線以檢測突然變化，主要使用加權移動平均值來檢測漸變。累積和檢測方法(CUSUM)[52]是一種順序分析技術，在漂移檢測中，它可用于監視變化檢測，而且不需要存儲數據。同時，Ross等[53]提出了一種指數加權移動平均線圖檢測方法(EWMAChartDM)，用于檢測概念漂移。該方法的設計使其能夠監控流分類器的錯誤分類率，同時還可以在不增加預測期間誤報率的情況下檢測變化。此外，Li等[10]提出了一種基于隨機決策樹的概念漂移檢測算法(CDRDT)，該算法可以有效且高效地檢測來自嘈雜流數據的概念漂移，并可以有效地區分不同類型的概念漂移與噪聲。常見的概念漂移處理技術如表1所示。

表1 常見概念漂移處理技術

3 算法分析與總結

為了更好地分析和總結數據流決策樹集成分類算法的性能，本節從集成學習框架、是否可以處理概念漂移、對比算法、數據集和算法優缺點等幾個角度分析總結決策樹集成分類算法，算法性能比較結果如表2所示。

表2 決策樹集成分類算法性能比較

續表2

4 算法應用

4.1 典型應用

數據流決策樹集成分類算法由于其高效的時空效率和較高的準確率，被廣泛應用于生活中的各個領域，在生物醫療、信用評價、電力預測和濕地測繪等均有突出表現。

在生物醫療領域的最新研究中，Yadav等[54]利用決策樹、隨機森林、額外樹對甲狀腺疾病進行分類和預測，并利用Bagging集成框架對得到的結果進行提升，提高了預測的精度。該集成方法在特定參數下，數據集的預測精度達到了100%。Geurts等[55]提出了一種基于隨機森林的決策樹集成算法對蛋白質組質譜的分析和知識提取，用于識別臨床蛋白質組學的生物標志物，從而完成蛋白質組質譜的分類和預測任務。此外，在藥物設計方面，數據流決策樹集成分類算法也有所涉足。Pu等[56]通過對約160 000個特定藥物設計問題的親和力預測實驗對比，LightGBM[57]和XGBoost均表現出比神經網絡更高的效率，并可以提取出比傳統方法更多的蛋白質-配體結合信息，將藥物設計的篩選效率提高到原來的200～1 000倍。

在信用評價領域，Wang等[43]提出了一種基于Stacking的個人信用風險評估模型，該模型使用不同的訓練子集及特征采樣和參數擾動方法對個人的信用進行風險評估預測。結合上述方法和企業信用評價模型研究的短缺，Sun等[58]提出了一種用于不平衡企業信用評價預測的新決策樹集成模型——DTE-SBD，該模型可以處理高風險企業與低風險企業之間的階級不平衡問題。對552家中國上市公司的財務數據進行了100次實證實驗，證明對企業信用評價的不均衡性是有效的，并提高了企業信用評價的正確率。

在電力消耗預測方面，Galicia等[59]對西班牙10年的電力消耗數據進行訓練和預測，平均相對誤差達到了2%，并已將該模型應用于澳大利亞的太陽能預測。在濕地測繪和分類方面，Berhane等[60]對俄羅斯貝加爾湖塞倫加河三角洲22種復雜淡水三角洲濕地植被和水生生境進行有效監督分類，隨機森林算法在大多數情況下都表現出較高的精度，取得了理想的效果。

4.2 主要平臺

由于流數據具有連續性和實時性的特點，因此流數據處理平臺需要具有實時處理的特點，其將實時數據逐條加載至高性能內存數據庫中進行分析和處理，數據遲滯低。目前應用較為廣泛的流數據處理平臺有Storm[61]、Spark Streaming[62]和Flink[63]等。

作為最佳的流式計算框架之一，Storm平臺是Twitter支持開發，并由Clojure語言和Java語言寫成，其優點是全內存計算。Storm可以用來處理源源不斷的數據，并在處理之后將結果保存在某個存儲中。此外，由于Storm的處理組件是分布式的，而且處理延遲極低，因此Storm可以作為分布式RPC框架進行計算。

Spark Streaming是構建在Spark基礎之上的流數據處理框架，具有吞吐量高和容錯能力強的特點，同時支持多種數據輸入和輸出格式。Spark Streaming是將流式數據分解為一系列的微小數據集，形成離散流，并將其轉化為短小的批處理作業進行計算。它是一個基于內存的迭代計算框架，適用于需要多次操作特定數據集的應用場合。需要反復操作的次數越多，所需的數據量越大，受益越大；數據量小且計算密集度較大時，受益相對較小。

Flink是一個用Java語言和Scala語言編寫的開源分布式流處理和批處理系統，在傳統數據庫系統和大數據分析框架之間起到鏈接的作用。Flink的核心功能是在數據流上提供數據分發、通信、具備容錯的分布式計算。同時，Flink在流處理引擎上構建了批處理引擎，原生支持了迭代計算、內存管理和程序優化。

以上三種平臺分別具有不同的功能特點，對特定場景下的流數據處理均有理想的表現，在國內外的研究中應用廣泛。

5 結 語

本文以三種集成學習框架的角度介紹了數據流決策樹集成分類的相關算法及研究現狀，同時對數據流中的概念漂移問題及其處理算法做了詳細的闡述。文章的最后，分別以集成學習框架、處理概念漂移的能力、對比算法、數據集和優缺點等角度對所提及的決策樹集成分類相關算法進行了分析與總結，并以此分析出集成學習的趨勢和未來的研究方向。

可以預見，集成學習方法將得到進一步改進，更適用于大數據流的學習，特別是不依賴于基礎學習器并且可以處理高維度的方法，因為這些方法可以很容易并行化并且可擴展。這些努力通常涉及實現分布式機器學習以及平臺計算資源利用支撐和應用模型的部署。此外，另一個有前途的研究方向是將集合模型轉換為更簡單和更全面的模型，同時保持它們所源自的集合的預測準確性[64]。新數據流集成學習方法應該從傳統的分類設置轉向處理具有挑戰性的真實世界場景的新方法，尤其是半監督(部分標記)和不平衡分類的數據流，使得集成學習應用的靈活性和準確性得到更好的價值體現。