呂高鋒，譚 靖，喬冠杰，嚴(yán)錦立

(國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長(zhǎng)沙 410073)

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

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

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

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

1 決策樹算法分析

1.1 報(bào)文分類問題

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

對(duì)報(bào)文分類問題的正式定義[16]如下：

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

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

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

表1 二維分類器示例

1.2 算法基本思想

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

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

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

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

1.3 算法類型

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

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

1.3.1 節(jié)點(diǎn)切割

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

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

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

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

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

1.3.2 規(guī)則集分組

事實(shí)上，規(guī)則集中部分規(guī)則之間存在明顯的差異。對(duì)訪問控制列表(access control list, ACL)、防火墻(firewall, FW)和IP鏈(IP chain, IPC)類型規(guī)則集進(jìn)行統(tǒng)計(jì)分析，結(jié)果如圖3所示。從圖中可得，IP地址字段前綴長(zhǎng)度為邊緣分布，即大部分位于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ū)分直接切割整個(gè)搜索空間將導(dǎo)致嚴(yán)重的規(guī)則復(fù)制，其中一個(gè)解決方案便是分治思想，即將具有相似特征的規(guī)則放到一個(gè)規(guī)則子集中，然后應(yīng)用節(jié)點(diǎn)切割技術(shù)為每個(gè)子集單獨(dú)構(gòu)建決策樹，最后形成多棵決策樹。規(guī)則集分組的主要方法有：

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

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

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

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

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

1.4 面臨的挑戰(zhàn)

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

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

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

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

1.5 測(cè)試基準(zhǔn)

報(bào)文分類算法的測(cè)試基準(zhǔn)為ClassBench[20]和ClassBench-ng[21]。

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

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

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

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

2.1 等分切割

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

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

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

2.2 等密切割

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

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

2.3 比特切割

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

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

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

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

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

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

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

3.1 按字段大小分組

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

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

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

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

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

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

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

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

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

3.2 按前綴長(zhǎng)度分組

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

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

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

3.3 基于聚類算法分組

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

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

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

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

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

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

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

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

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

4 決策樹算法研究方向

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

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

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

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

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

5 結(jié)論

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

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