決策樹報文分類算法

呂高鋒，譚 靖，喬冠杰，嚴錦立

(國防科技大學 計算機學院， 湖南 長沙 410073)

報文分類是各種網(wǎng)絡服務所需的基本技術(shù)之一，如安全防護、策略路由和服務質(zhì)量(quality of service，QOS)等。因此，報文分類在云服務提供商、互聯(lián)網(wǎng)服務提供商(internet service provider，ISP)和互聯(lián)網(wǎng)交換中心(internet exchange point，IXP)的核心網(wǎng)絡設備中廣泛部署[1]。報文分類的目的是根據(jù)網(wǎng)絡報文頭部的多個字段值來區(qū)分報文類型，從而對報文執(zhí)行相應的差異化操作。

報文分類解決方案可分為兩大類：硬件方案和軟件方案[2]。其中基于三態(tài)內(nèi)容可尋址存儲器(ternary content addressable memory，TCAM)的硬件方案[3-6]在行業(yè)中占據(jù)主導地位，其利用TCAM將所有規(guī)則存儲在相聯(lián)存儲器中，然后將報文與這些規(guī)則并行匹配，優(yōu)點是提供了常量的分類時間、實現(xiàn)了線速查找，但存在高成本、高功耗、可擴展性較差等缺點[7]。軟件方案主要有決策樹算法、元組空間搜索算法[8-10]等，其中決策樹算法由于具有吞吐量高、適用于多字段和可流水線化[11]等特點，被認為是最有希望替代TCAM方案的方案之一。

由于報文分類具有重要的研究和實用價值，近十年一直是人們的研究熱點。并且網(wǎng)絡帶寬的持續(xù)增長和網(wǎng)絡應用復雜性的不斷增加[12]，給報文分類帶來了高維度和動態(tài)性等新挑戰(zhàn)，研究人員仍在尋求新的、更高效的報文分類解決方案。近年來決策樹報文分類算法研究取得了重要進展，新的算法層出不窮，并且出現(xiàn)了跨領(lǐng)域的趨勢，例如與機器學習結(jié)合取得了初步成果，但是相關(guān)研究的綜述性文章[13-15]并未涉及決策樹算法新的研究進展，對近年來優(yōu)秀的研究成果也缺乏系統(tǒng)的分析與總結(jié)。

為進一步推動基于決策樹的報文分類算法的研究與發(fā)展，本文從節(jié)點切割技術(shù)、規(guī)則集分組技術(shù)兩個維度對決策樹算法進行了系統(tǒng)的分析和總結(jié)，并對比了各類算法的設計思路和特點。

1 決策樹算法分析

1.1 報文分類問題

報文分類器含有一個規(guī)則列表，其中每條規(guī)則由優(yōu)先級、匹配域(match field)和匹配報文時采取的動作(action)組成。報文分類問題是從規(guī)則列表中找到報文所匹配的規(guī)則，并返回其中優(yōu)先級最高的匹配規(guī)則。

對報文分類問題的正式定義[16]如下：

規(guī)則列表中含有n條規(guī)則，每條規(guī)則由d個匹配域(維度)和動作域組成，其中每個匹配域f[i](1 ≤i≤d)都是關(guān)于報文頭部的第ith字段的表達式。表達式的形式可以為精確匹配、前綴匹配或范圍匹配形式。如標準IPv4五元組中的源和目的IP地址屬于前綴匹配，源和目的端口號屬于范圍匹配，協(xié)議類型則屬于精確匹配。

如果?i(1 ≤i≤d)，報文P的第ith報頭字段值都能滿足規(guī)則Rt(1 ≤t≤n)的第i個匹配域f[i]，則認為報文P與特定規(guī)則Rt匹配。如果報文P同時匹配了多條規(guī)則，則返回優(yōu)先級最高的匹配規(guī)則。

表1給出了含有6條規(guī)則的二維分類器示例。其中每個維度的位寬為4，“*”表示通配符，優(yōu)先級數(shù)值越小的規(guī)則對應的優(yōu)先級越高。

表1 二維分類器示例

1.2 算法基本思想

報文分類問題可等價為計算幾何中的多維空間點定位問題，即報文頭部中的字段(如源和目的IP地址、源和目的端口號以及協(xié)議類型)表示幾何空間中的維度，報文被表示為該空間中的點，而規(guī)則被表示為空間中的超立方體。然后，報文分類問題等價于找到包含點(報文)的優(yōu)先級最高的超立方體(規(guī)則)：如果報文P與特定規(guī)則R匹配，則表示報文P的點將落入規(guī)則R指定的超立方體中。

經(jīng)過數(shù)學推導[17]，在具有n個互不重疊的超立方體的d維幾何空間中，當d>3時，多維空間點定位問題理論上具有O(log2n)時間復雜度和O(nd)空間復雜度，或者具有O(log2n)d-1時間和O(n)空間復雜度。而對于五元組或更高維度的報文分類，這兩個選擇都不具吸引力。因此，需要采取有效的數(shù)據(jù)結(jié)構(gòu)來組織規(guī)則集，決策樹算法便是理想的選擇之一。

在基于決策樹算法的方案中，對報文分類問題采取幾何視圖，并構(gòu)建決策樹。樹的根節(jié)點覆蓋了包含所有規(guī)則的整個搜索空間，然后遞歸地將搜索空間切割為更小的子空間，直到每個子空間包含的規(guī)則數(shù)不大于預定義的閾值時停止切割，并將當前子空間對應的節(jié)點設為葉節(jié)點。如果規(guī)則了跨越多個子空間，則在切割時會發(fā)生不必要的規(guī)則復制。當有報文到達時，基于報文頭部字段中的關(guān)鍵字值遍歷決策樹，以在葉節(jié)點處找到匹配規(guī)則。表1中的二維規(guī)則集對應的幾何視圖如圖1所示。

圖1 表1中規(guī)則集的幾何視圖Fig.1 Geometric view of rules in Tab.1

1.3 算法類型

現(xiàn)有報文分類問題解決方案主要分為硬件方案和軟件方案，基本框架如圖2所示。

其中硬件方案主要有TCAM和位向量[18-19]，決策樹算法屬于軟件解決方案。構(gòu)建決策樹有兩類常用技術(shù)：節(jié)點切割和規(guī)則集分組。

1.3.1 節(jié)點切割

節(jié)點切割基本思想是將整個多維規(guī)則集視為樹的根節(jié)點，然后沿一個或多個特定的維度切割節(jié)點構(gòu)建決策樹。算法從包含所有規(guī)則的根節(jié)點開始，迭代地切割節(jié)點，直到每個葉節(jié)點包含的規(guī)則數(shù)不大于預定義的閾值時停止切割，從而構(gòu)建單棵決策樹。各類決策樹算法在節(jié)點切割方面的主要區(qū)別為：

圖2 報文分類解決方案的基本框架Fig.2 Basic framework for the solution of packet classification problems

1)切割維度的選擇。選擇哪個維度切割最優(yōu)；一次選擇單個維度還是多個維度進行切割。

2)切割端點的選擇。包括對節(jié)點進行等分切割或者等密切割。等分切割能快速將節(jié)點等分為2n個子節(jié)點，但會帶來嚴重的規(guī)則復制問題，即同一條規(guī)則分布在多個子節(jié)點中；而等密切割能夠緩解規(guī)則復制問題，但也存在樹深度增加、節(jié)點索引復雜等問題。

此外，新提出的比特切割技術(shù)使用比特級視圖(bit-level view)，利用規(guī)則每一位都可表示為0、1或者*(通配符)的特點，選擇其中有效比特將規(guī)則映射到各個子節(jié)點中，從而避免了盲目地切割整個搜索空間。從另一個角度看，等分切割也是一種特殊的比特切割，但只允許使用連續(xù)的最高有效位。

1.3.2 規(guī)則集分組

事實上，規(guī)則集中部分規(guī)則之間存在明顯的差異。對訪問控制列表(access control list, ACL)、防火墻(firewall, FW)和IP鏈(IP chain, IPC)類型規(guī)則集進行統(tǒng)計分析，結(jié)果如圖3所示。從圖中可得，IP地址字段前綴長度為邊緣分布，即大部分位于0附近或32附近。

(a) 源IP地址前綴分布(a) Distribution of source IP address

(b) 目的IP地址前綴分布(b) Distribution of destination IP address圖3 地址前綴分布Fig.3 Distribution of address

因此不加任何區(qū)分直接切割整個搜索空間將導致嚴重的規(guī)則復制，其中一個解決方案便是分治思想，即將具有相似特征的規(guī)則放到一個規(guī)則子集中，然后應用節(jié)點切割技術(shù)為每個子集單獨構(gòu)建決策樹，最后形成多棵決策樹。規(guī)則集分組的主要方法有：

1)按字段大小分組。根據(jù)規(guī)則在每個字段覆蓋的范圍來劃分規(guī)則子集，該類方法應用最廣泛。

2)按前綴長度分組。根據(jù)規(guī)則在特定字段的前綴長度來劃分規(guī)則集。

3)基于聚類算法分組。使用聚類算法來劃分規(guī)則子集。

4)基于深度神經(jīng)網(wǎng)絡模型分組。將機器學習技術(shù)應用到報文分類問題中，如使用深度神經(jīng)網(wǎng)絡模型來學習優(yōu)化節(jié)點切割和規(guī)則集分組，以獲得最大的獎勵函數(shù)(分類速度、內(nèi)存消耗等)，從而構(gòu)建性能優(yōu)異的決策樹。

按字段大小、前綴長度分組等啟發(fā)式策略建立在對規(guī)則集分布特征觀察的基礎之上，原理相對簡單、容易實現(xiàn)，但對于不同的規(guī)則集，往往需要手動調(diào)整部分參數(shù)以獲得理想結(jié)果；聚類算法、神經(jīng)網(wǎng)絡模型則可以使用機器學習來替代人工調(diào)整，實現(xiàn)對規(guī)則子集的自適應劃分，但需要經(jīng)過大量的訓練和迭代才能收斂。

1.4 面臨的挑戰(zhàn)

設計高效的決策樹算法面臨的最大挑戰(zhàn)是規(guī)則復制問題和數(shù)據(jù)結(jié)構(gòu)更新問題。

決策樹算法犧牲了線性空間來獲得較高的分類速度，是典型的以空間換時間。規(guī)則復制問題是困擾決策樹類型解決方案的主要問題之一，早期的決策樹算法在規(guī)則集規(guī)模較大的時候產(chǎn)生大量規(guī)則復制，甚至耗盡系統(tǒng)內(nèi)存。規(guī)則集分組技術(shù)的主要目的就是解決規(guī)則復制問題。

決策樹算法存在的另一大挑戰(zhàn)是規(guī)則更新速度較慢。在軟件定義網(wǎng)絡中，虛擬交換機得到大規(guī)模部署，目前主流的虛擬交換機如Open vSwitch，要求算法的數(shù)據(jù)結(jié)構(gòu)規(guī)則更新時間復雜度為常量級別，即時間復雜度為O(1),因此采用了優(yōu)先級元組空間搜索(priority sorted tuple space search, PSTSS)算法。而決策樹算法由于存在規(guī)則復制問題，導致數(shù)據(jù)結(jié)構(gòu)更新困難，甚至在更新時需要重新構(gòu)造決策樹。更新速度較慢已經(jīng)成為限制決策樹算法應用的關(guān)鍵因素之一。

決策樹算法目前的研究熱點是在保證算法性能的基礎上，解決規(guī)則復制問題和更新速度問題，在算法吞吐量、內(nèi)存消耗和更新速度等重要指標之間取得更好的折中。

1.5 測試基準

報文分類算法的測試基準為ClassBench[20]和ClassBench-ng[21]。

ClassBench是2007年由Taylor等提出，用于對報文分類算法進行基準測試的開源工具。ClassBench能夠接收規(guī)則集參數(shù)配置文件，生成精確模擬實際規(guī)則集分布特征的規(guī)則集。ClassBench中共提供了12個參數(shù)文件，支持生成ACL、FW和 IPC三種類型、不同規(guī)模的IPv4 五元組規(guī)則集。此外，ClassBench還能夠針對規(guī)則集生成特定長度的報文頭部序列，以對算法性能進行測試。

IPv6協(xié)議和軟件定義網(wǎng)絡(software defined network, SDN)技術(shù)的發(fā)展給報文分類問題帶來了新的挑戰(zhàn)，而ClassBench僅支持生成IPv4環(huán)境下的規(guī)則集。針對這一問題，Matou?ek等于2017年提出了新的開源基準測試工具ClassBench-ng，能夠生成IPv4、IPv6規(guī)則集和OpenFlow[22]1.0流表。此外，ClassBench-ng還提供了一種從實際規(guī)則集提取參數(shù)文件的機制，并可上傳至ClassBench-ng工具庫，以生成不同應用環(huán)境下的規(guī)則集，適應不同研究人員的需求。

2 基于節(jié)點切割的單棵決策樹

節(jié)點切割技術(shù)采用幾何視圖，將包含所有規(guī)則的整個搜索空間視作根節(jié)點，利用啟發(fā)式等策略選擇合適的切割維度和端點切割當前節(jié)點，獲得子空間，然后遞歸地將搜索子空間分解為更小的空間，直到滿足特定條件停止遞歸，最終構(gòu)建基本的單棵決策樹。節(jié)點切割方案主要有等分切割、等密切割和比特切割。

2.1 等分切割

HiCuts算法[23]是由Gupta等提出的最早用于報文分類的決策樹算法，一次選擇單個切割維度來等分規(guī)則空間，目的是將規(guī)則盡可能均勻地分離到樹的葉節(jié)點中。HiCuts從覆蓋整個規(guī)則空間的根節(jié)點開始，在單個維度上切割搜索空間，以創(chuàng)建一組大小相等的子空間。HiCuts算法中應用了多種啟發(fā)式策略來選擇最優(yōu)的切割維度和切割次數(shù)。

HiCuts算法存在兩個主要缺陷：首先， HiCuts算法僅考慮在一個節(jié)點處切割一個維度，這將增加樹的深度，從而增加了樹遍歷所需的時間。其次，算法在構(gòu)建決策樹后存在大量的規(guī)則冗余，消耗了大量內(nèi)存。針對上述缺陷， Singh等提出了HyperCuts算法[24]，改進了樹的深度和內(nèi)存消耗問題。HyperCuts算法提出同時切割多個維度，而不是在一個節(jié)點處只切割單個維度，從而減少了樹的深度。其次，HyperCuts提出了公共規(guī)則向上推送的優(yōu)化方法，允許將所有同級子節(jié)點通用的規(guī)則向上移動到父節(jié)點處，以緩解規(guī)則復制問題。

HyperCuts算法雖然在一定程度上緩解了樹的深度較大和規(guī)則復制問題，但仍存在相當大的規(guī)則冗余，尤其是對于大規(guī)模的規(guī)則集。其問題在于等分切割本身的局限性，即等分切割適用于規(guī)則分布均勻的場合，而實際上規(guī)則集的分布并不是均勻的。

2.2 等密切割

針對HiCuts和HyperCuts算法等分切割搜索空間導致大量規(guī)則冗余的問題，Qi等提出了HyperSplit算法[25]。HyperSplit的思想是構(gòu)建一個平衡的二叉樹，以便規(guī)則均勻地分布在其子節(jié)點中，并沿著規(guī)則邊界進行切割，從而防止過多的規(guī)則復制。HyperSplit算法在每個內(nèi)部節(jié)點處采用啟發(fā)式策略選擇一個最佳的切割維度和切割端點，將搜索空間拆分成兩個大小不等的子空間，其中包含的規(guī)則數(shù)近似相等。選擇切割端點的策略包括規(guī)則平衡、范圍平衡和加權(quán)分段平衡。

HyperSplit算法提出了等密切割的思路，進一步緩解了規(guī)則復制問題，但由于算法構(gòu)建的決策樹為二叉樹，且每次只能判斷一次維度，因此隨著規(guī)則集規(guī)模的擴大和維度的增加，樹的深度也會增加，相應的遍歷決策樹所需的訪存次數(shù)也將增加。

2.3 比特切割

Liu等提出的BitCuts算法[26]是對節(jié)點切割技術(shù)一次新的嘗試。不同于等分切割和等密切割算法，BitCuts算法充分利用了規(guī)則的二進制特點，即對于精確值和前綴表達式的字段，其每一位取值均為0、1或*，而范圍表達式可轉(zhuǎn)換為前綴表達式，然后通過貪心策略迭代地選擇其中的有效比特，將規(guī)則分離到葉節(jié)點中。

BitCuts算法利用了規(guī)則的二進制特點，迭代地選擇有效比特來構(gòu)建決策樹，在內(nèi)存訪問次數(shù)上相比HiCuts、HyperCuts和HyperSplit算法有了大幅度減少，因此吞吐量更高。但比特選擇策略的效率很大程度上決定著算法性能。典型的比特選擇策略有暴力策略、啟發(fā)式策略等。

對表1中的規(guī)則集分別使用HiCuts算法、HyperCuts算法、HyperSplit算法和BitCuts算法構(gòu)建決策樹，結(jié)果如圖4～7所示，其中葉節(jié)點中最多可包含的規(guī)則數(shù)量為4。采用不同節(jié)點切割方案的決策算法設計思路及特點如表2所示。

圖4 HiCuts算法構(gòu)建的決策樹Fig.4 Decision tree built by HiCuts

圖5 HyperCuts算法構(gòu)建的決策樹Fig.5 Decision tree built by HyperCuts

圖6 HyperSplit算法構(gòu)建的決策樹Fig.6 Decision tree built by HyperSplit

圖7 BitCuts算法構(gòu)建的決策樹Fig.7 Decision tree built by BitCuts

表2 節(jié)點切割的決策樹算法

總的來說，三類節(jié)點切割算法中，等分切割優(yōu)點在于簡單快速，分類速度較快，但是內(nèi)存消耗較大，適用于對分類速度要求高而對內(nèi)存消耗不敏感的場景。而等密切割則在內(nèi)存消耗方面占有優(yōu)勢，但算法吞吐量有所下降，適用于對內(nèi)存要求嚴格的場景。比特切割是一種更新穎和靈活的切割算法，在時間性能和空間性能之間實現(xiàn)了更好的折中，能夠以合理的內(nèi)存消耗提供較高的分類速度。

3 基于規(guī)則集分組的多棵決策樹

研究人員在節(jié)點切割技術(shù)方面開展了深入的研究，充分挖掘了單棵決策樹的性能，但仍無法有效解決規(guī)則復制問題。針對單棵樹的固有缺陷，提出了規(guī)則集分組的想法。根據(jù)規(guī)則集的某些特征來劃分子集，將具有相似特征的規(guī)則放在一個子集里單獨構(gòu)建決策樹，最終形成多棵決策樹。將規(guī)則集分成子集的規(guī)則集分組技術(shù)可減少每個子集中的規(guī)則重疊，從而改善單棵樹中嚴重的規(guī)則復制問題。

規(guī)則集分組的主要方法有：按字段大小分組、按前綴長度分組、基于聚類算法分組和基于深度神經(jīng)網(wǎng)絡分組。

3.1 按字段大小分組

EffiCuts算法[27]是使用規(guī)則集分組最具代表性的算法。EffiCuts算法基于兩個關(guān)鍵結(jié)論：①規(guī)則大小的變化：規(guī)則集中有許多規(guī)則重疊，重疊的規(guī)則在大小上差異很大。因此，具有重疊的小規(guī)則和大規(guī)則的單棵樹需要精細切割來分隔小規(guī)則，但會復制大規(guī)則。②規(guī)則空間密度的變化。針對重疊規(guī)則大小變化的情況，EffiCuts算法提出了“可分離樹”的思想，通過將小規(guī)則和大規(guī)則放在不同的樹中減少復制，再應用HyperCuts算法為每個子集構(gòu)建決策樹。例如對于圖2中的6條規(guī)則，可根據(jù)規(guī)則在X、Y兩個域上的大小，分為4個子集{R1，R2}、{R3，R4}、{R5}和{R6}。

對于字段大小的區(qū)分，算法通過規(guī)則投影到每個字段上的覆蓋區(qū)間的大小來界定，定義了一個稱為大分數(shù)(largeness fraction)的分界點，一般情況下取值為0.5。對于d維規(guī)則集，EffiCuts算法最多能產(chǎn)生2d個子集，呈指數(shù)級別增長。EffiCuts算法雖然考慮子樹過多的情況，采用子樹合并方法來消除部分子樹，但仍然會生成大量的子樹，這將導致較多的內(nèi)存訪問次數(shù)，不利于算法的擴展。使用EffiCuts算法為表1中的二維規(guī)則集構(gòu)建的決策樹如圖8所示。

圖8 EffiCuts算法構(gòu)建的決策樹Fig.8 Decision tree built by EffiCuts

HybridCuts算法[28]和SmartSplit算法[29]針對EffiCuts算法中子類別過多的問題進行改進。在這兩個算法中僅使用了源IP地址和目的IP地址兩個字段而不是全部的字段來劃分規(guī)則集，限制了規(guī)則子集的數(shù)量最多為4。

Li等將按字段大小分組擴展到OpenFlow等多維規(guī)則集，提出了CutSplit算法[30]。CutSplit的基本思想是基于很少的幾個字段對規(guī)則集進行分組，然后預切割和后拆分結(jié)合構(gòu)建決策樹。CutSplit算法的框架如圖9所示。

圖9 CutSplit算法框架Fig.9 Framework of CutSplit

算法具體實現(xiàn)為：根據(jù)小的維度將整個規(guī)則集劃分為若干子集，劃分依據(jù)是從F維中挑選前m個包含最多的小規(guī)則數(shù)量的維度，保證這m個小維度覆蓋絕大部分的規(guī)則(≥95%)，并且在算法中定義了閾值向量，使得規(guī)則“大”“小”定義更多靈活；在劃分子集后，對每個子規(guī)則集運用簡單、快速的固定小字段等分切割，以得到更小的子空間；對每個子空間運用HyperSplit算法，以盡量減小冗余并且達到最壞情況下的有界性能。

CutSplit算法相比EffiCuts算法，通過精心挑選少數(shù)維度劃分規(guī)則子集，性能有了改善，但存在切割和拆分的邊界難以確定、算法性能不穩(wěn)定等缺點。

TabTree算法[31]是繼CutSplit算法之后的一項新的研究成果，其規(guī)則集分組方法類似CutSplit，但對于每個子集使用了平衡位選擇的方法來構(gòu)建決策樹，而不是預切割和后拆分的組合，從而實現(xiàn)了高速分類和規(guī)則快速更新。

3.2 按前綴長度分組

Daly 等提出的ByteCuts算法[32]，根據(jù)規(guī)則在IP地址字段的前綴長度來劃分規(guī)則子集。算法將具有相同的核心位集合的所有規(guī)則放在同一樹中，然后對單棵樹使用字節(jié)切割(以半字節(jié)為單位的比特切割)構(gòu)建決策樹。ByteCuts算法對子樹數(shù)量與子樹大小之間的平衡進行了深入研究：子樹數(shù)量過多會導致訪存次數(shù)增加；過少會使得單棵樹的體積大，從而在單棵樹內(nèi)部產(chǎn)生更多的規(guī)則復制。ByteCuts算法定義了兩個閾值：切割效率(決定子樹內(nèi)部沖突率)和樹大小，目標是最大化樹中規(guī)則的數(shù)量(最小化樹的數(shù)量)，同時滿足一定的平衡要求。

算法具體實現(xiàn)為：通過兩個閾值(切割效率和決策樹大小)來選擇字段長度對(f，Wf)；然后將為字段f上前綴長度至少為Wf的所有規(guī)則放入同一個子集中，并創(chuàng)建單個決策樹；對剩下規(guī)則重復該過程，直到剩余規(guī)則的數(shù)量低于某個特定閾值τ(如5%)停止。

ByteCuts算法因以半個字節(jié)為單位切割搜索空間，構(gòu)建決策樹數(shù)據(jù)結(jié)構(gòu)所需時間較短。此外，算法還具有較強的靈活性，可通過調(diào)整閾值參數(shù)在時間性能和空間性能之間取得較好的折中。

3.3 基于聚類算法分組

Fong 等提出的ParaSplit算法[33]的基本思想是使用聚類算法劃分子集，然后對每個子集使用HyperSplit 算法構(gòu)建決策樹。ParaSplit算法首先使用范圍-點轉(zhuǎn)換算法，通過將每個字段的起點和終點視為單獨的維度，從而將F維空間中的超矩形轉(zhuǎn)化為2F維空間中的點(F維規(guī)則被表示為2F維空間中的點)。然后利用K-means聚類算法有效劃分規(guī)則子集，應用模擬退火算法來尋找最優(yōu)劃分，并對每個子集使用HyperSplit算法構(gòu)建決策樹。在使用K-means聚類算法劃分子集時，提出了最小距離、最大距離和距離原點距離三種啟發(fā)式策略，其中最小距離策略的性能更優(yōu)。

ParaSplit算法通過聚類算法實現(xiàn)了規(guī)則集的自適應劃分，但K-means算法的性能受初始k個中心點的選擇影響較大，且算法需要上萬次的迭代才能獲得理想結(jié)果，預處理時間較長。

3.4 基于深度神經(jīng)網(wǎng)絡分組

NeuroCuts算法[34]使用了深度神經(jīng)網(wǎng)絡模型來學習構(gòu)建高效的決策樹，算法框架如圖10所示。神經(jīng)網(wǎng)絡模型的環(huán)境由規(guī)則集和當前決策樹組成；代理使用一個神經(jīng)網(wǎng)絡模型，選擇最佳的切割或規(guī)則集分組操作來增量地構(gòu)建樹；當前節(jié)點的可用操作(節(jié)點切割或規(guī)則集分組)在每個步驟由環(huán)境通告，代理選擇其中一個操作生成決策樹。隨著時間推移，代理學會優(yōu)化其決策，以最大化從環(huán)境中獲得的獎勵函數(shù)，最終構(gòu)建性能優(yōu)異的決策樹。獎勵函數(shù)可以是分類速度、消耗內(nèi)存或兩者的結(jié)合。NeuroCuts算法在訓練過程中使用了馬爾可夫決策過程，并且結(jié)合了已有的研究成果，如按字段分組等策略。

圖10 NeuroCuts算法框架Fig.10 Framework of NeuroCuts

NeuroCuts算法在報文分類和機器學習結(jié)合方面開創(chuàng)先河，是一次有益的大膽嘗試，有助于啟發(fā)新一代基于機器學習的分類算法。

表3給出了采用不同規(guī)則集分組方案的決策樹算法的設計思路和特點?？偟膩碚f，按字段大小分組和按前綴長度分組原理簡單，容易實現(xiàn)，較好地利用了規(guī)則集的幾何分布特征，達到了較好的性能，且更新速度也有優(yōu)勢。但缺點在于需要自定義閾值參數(shù)，且在面對不同的規(guī)則集時可能需要重新調(diào)整參數(shù)。按字段大小分組適用于規(guī)則集更新頻繁，或者面向特定應用領(lǐng)域和特定規(guī)則集的場景。

表3 規(guī)則集分組的決策樹算法

而基于聚類算法分組和基于深度神經(jīng)網(wǎng)絡分組則將報文分類問題與機器學習較好結(jié)合在一起，利用機器學習技術(shù)來解決經(jīng)典的網(wǎng)絡問題，實現(xiàn)了規(guī)則集的自適應分組，通用性較強。但預處理速度較慢，往往需要大量的計算和迭代才能收斂，從而獲得理想的性能。適用于規(guī)則更新頻率較低，但對算法性能要求較高的場景。

4 決策樹算法研究方向

網(wǎng)絡技術(shù)的進步以及網(wǎng)絡應用的復雜性和多樣性，給報文分類帶來了新挑戰(zhàn)，研究人員仍致力于提出更高效的決策樹報文分類算法。決策樹下一步的研究方向主要有以下四個方面：

一是節(jié)點切割技術(shù)創(chuàng)新。利用規(guī)則集分布特征，提出新穎的、更高效的節(jié)點切割技術(shù)或者規(guī)則集分組技術(shù)，例如新的比特切割技術(shù)等。目前常用的有效比特選擇標準有規(guī)則可分離性[26]、子節(jié)點內(nèi)規(guī)則數(shù)量最少化[35]、信息熵[36]和子節(jié)點內(nèi)規(guī)則數(shù)量平衡[37]等，但以上方法存在預處理時間較長、容易陷入局部最優(yōu)等缺點，因此研究更好的比特切割技術(shù)，有助于提升決策樹算法的時間性能和空間性能。

二是規(guī)則集分組與節(jié)點切割技術(shù)結(jié)合使用。根據(jù)各類規(guī)則集分組技術(shù)與節(jié)點切割技術(shù)的特點，積極嘗試將它們結(jié)合使用以得到性能更優(yōu)的決策樹，這是當前研究的熱點，新的研究成果也多集中在該方向上。如按字段大小分組與等分切割結(jié)合使用能夠取得較好效果[30]，而按前綴長度分組后則更適合使用比特切割來構(gòu)建決策樹。

三是異構(gòu)的算法架構(gòu)。即各類軟件方案、軟件方案和硬件方案的結(jié)合使用。如Partition Sort算法[38]就充分利用了元組空間搜索(tuple space search, TSS)算法和決策樹算法的優(yōu)點，從而兼顧了決策樹算法的高吞吐量和TSS算法的快速更新。CutTSS算法[39]則創(chuàng)造性地將等分切割與元組空間搜索算法結(jié)合使用，因此能夠同時支持高速分類和快速更新。此外，軟硬件協(xié)同處理也是一個研究熱點，首先設計高性能的決策樹算法，再將決策樹映射到FPGA等硬件平臺上[40-41]，利用硬件大規(guī)模并行、流水線架構(gòu)的特點來提升算法性能，以兼顧軟件算法靈活性和硬件高性能的優(yōu)點。

四是跨領(lǐng)域研究。將決策樹算法與機器學習等技術(shù)結(jié)合，借助于其他領(lǐng)域的專業(yè)知識來解決報文分類問題。如使用深度神經(jīng)網(wǎng)絡模型學習構(gòu)建高效的決策樹是一個新的研究方向，對神經(jīng)網(wǎng)絡模型的研究和改進也有助于提升決策樹算法的性能。

5 結(jié)論

本文主要介紹了最新的決策樹研究成果，從節(jié)點切割和規(guī)則集分組技術(shù)兩個方面對決策樹算法進行了系統(tǒng)分析和總結(jié)。總的來說，構(gòu)建單棵決策樹的技術(shù)主要包括等分切割、等密切割和比特切割等，已經(jīng)得到了較為深入的研究。規(guī)則集分組技術(shù)主要包括按字段大小分組、按前綴長度分組、基于聚類算法分組和基于深度神經(jīng)網(wǎng)絡分組等，目前仍是研究熱點。一個好的規(guī)則集分組方案能夠有效解決困擾決策樹算法已久的規(guī)則復制問題，同時提高算法的數(shù)據(jù)結(jié)構(gòu)更新速度，從而提升算法的應用價值。

隨著網(wǎng)絡帶寬的持續(xù)增長和網(wǎng)絡應用復雜性的不斷增加，決策樹報文分類算法的發(fā)展趨勢是更高的吞吐量、更小的內(nèi)存消耗和更快的更新速度，并支持高維度擴展，尤其是在數(shù)據(jù)中心等規(guī)則集頻繁更新的應用環(huán)境中，算法的更新性能顯得越來越重要。