国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于深度增強學習的網(wǎng)絡數(shù)據(jù)包分類算法研究①

2020-05-18 12:02
關鍵詞:決策樹數(shù)據(jù)包分區(qū)

郭 鵬

(安徽電子信息職業(yè)技術學院 軟件學院,安徽 蚌埠 233000)

0 引 言

數(shù)據(jù)包分類是計算機網(wǎng)絡中的基本問題之一,是許多網(wǎng)絡功能的關鍵構建塊,包括防火墻,訪問控制,流量工程和網(wǎng)絡測量[1-2]。數(shù)據(jù)包分類的目標是將給定的數(shù)據(jù)包與一組規(guī)則中的一個規(guī)則進行匹配,并在規(guī)定的分類時間和/或內(nèi)存占用量進行匹配?,F(xiàn)有的方法依賴于人工對決策樹進行調(diào)整,缺乏一定的可擴展性。因此,設計一種基于深度增強學習方法[3]的數(shù)據(jù)包分類方法,避免人工參加所帶來的問題。

1 DEEPCUT設計

1.1 DeepCut 總體設計

本小節(jié)介紹了DeepCut的總體設計,DeepCut是一種新的基于深度增強學習的數(shù)據(jù)包分類算法。給定一個規(guī)則集和目標函數(shù),DeepCut將學習并建立最小化目標函數(shù)的決策樹。

圖1是基于增強學習的DeepCut系統(tǒng)框架:環(huán)境由規(guī)則集和當前決策樹組成,agent選擇最佳分割或分區(qū)的模型來逐步構建決策樹。分割動作將沿選定維度(即SrcIP,DstIP,SrcPort,DstPort和協(xié)議之一)的節(jié)點劃分為多個子范圍(即2,4,8,16或32個范圍),并且在樹中創(chuàng)建多個子節(jié)點。分區(qū)動作將節(jié)點的規(guī)則劃分為不相交的子集,并為每個子集創(chuàng)建新的子節(jié)點。環(huán)境在每次迭代中都會通告當前節(jié)點的可用動作,agent從中選擇動作以生成樹。隨著時間的推移,agent將學習優(yōu)化其決策以最大程度地從環(huán)境中獲得回報。

圖1 系統(tǒng)框架

1.2 DeepCut 訓練算法

增強學習算法的目標是計算一個策略,以最大程度地從環(huán)境中獲得回報。環(huán)境定義了動作空間A和狀態(tài)空間S。Agent從初始策略開始,使用多個rollout對其進行評估,然后根據(jù)這些rollout的結果(回報)對其進行更新。重復此過程,直到對rollout滿意為止。

將決策樹生成視為單個馬爾可夫決策過程(MDP)。在此框架中,rollout從包含單個節(jié)點的決策樹開始,這是初始狀態(tài)s0∈S。在每個步驟t,agent執(zhí)行動作at∈A并獲得回報rt,然后環(huán)境從當前狀態(tài)st∈S轉(zhuǎn)換到下一個狀態(tài)st+1∈S。目標是最大化agent收到的總獎勵,即∑tγtrt,其中γ是折現(xiàn)因子。

樹節(jié)點的動作僅取決于節(jié)點本身,因此不必在環(huán)境狀態(tài)下對整個決策樹進行編碼。需要根據(jù)全局狀態(tài)做出決策,但這并不意味著狀態(tài)表示需要對整個決策樹進行編碼。給定一個樹節(jié)點,對該節(jié)點的動作只需做出最佳決策即可優(yōu)化以該節(jié)點為根的子樹,并不需要考慮決策樹中的其他樹節(jié)點。

給定一個樹節(jié)點n,令tn和sn分別表示節(jié)點n的分類時間和內(nèi)存使用量,令Tn和Sn分別表示以節(jié)點n為根的子樹的分類時間和內(nèi)存使用量。對于剪枝動作,有以下的關系:

Tn=tn+maxiTi

(1)

Sn=sn+maxiSi

(2)

同理,對于分區(qū)動作,有:

Tn=tn+sumiTi

(3)

Sn=sn+sumiSi

(4)

節(jié)點n的動作a只需要根據(jù)公式(5)來優(yōu)化其子樹。

Vn=argmaxa∈A-(cTn+(1-c)Sn)

(5)

其中,權重參數(shù)c(c∈[0,1])用來權衡分類時間和內(nèi)存使用量之間的重要性。

總而言之,僅需要對當前節(jié)點進行編碼,并作為agent的輸入狀態(tài)。這是因為環(huán)境是以逐個節(jié)點的方式來構建決策樹,節(jié)點只需要考慮自己的狀態(tài)來選擇相應的動作,并且每個節(jié)點都包含其父節(jié)點的規(guī)則子集。給定d個維度,使用長度為2d的編碼來對一個樹節(jié)點的狀態(tài)進行編碼,節(jié)點的狀態(tài)還需要描述節(jié)點上的分區(qū)。另外,節(jié)點狀態(tài)并沒有包含數(shù)據(jù)包分類器的規(guī)則集。DeepCut通過從環(huán)境中獲得的回報來隱式地解釋數(shù)據(jù)包分類器規(guī)則。

使用Actor-Critic算法來訓練agent的策略。DeepCut從決策樹的根節(jié)點s*開始運行,最終目標是學習一個優(yōu)化隨機策略函數(shù)π(a|s;θ)。DeepCut首先初始化所有參數(shù),然后運行N次rollout以對策略和值函數(shù)進行訓練。在每次rollout后,它都會將決策樹重新初始化到根節(jié)點。然后,根據(jù)當前策略,通過在每個非葉子節(jié)點上重復選擇并執(zhí)行動作,以逐步構建樹。葉子節(jié)點是指規(guī)則數(shù)量低于給定閾值的節(jié)點。

更具體地說,DeepCut以深度優(yōu)先搜索(DFS)順序遍歷樹節(jié)點,即算法遞歸地對當前節(jié)點的子節(jié)點進行剪枝,直到該節(jié)點成為葉子節(jié)點為止。構建決策樹后,將重置梯度,然后算法對所有樹節(jié)點進行迭代以聚合梯度。最后,DeepCut使用梯度來更新Actor-Critic網(wǎng)絡的參數(shù),然后進行下一個rollout。

第一個梯度計算對應于策略梯度損失的計算。該損失定義了更新θ以改善預期回報的方向。從rollout回報R中減去狀態(tài)值V(s;θv)的估計值,以減小梯度方差[4]。與此同時,訓練V以使其預測誤差達到最小。

除了剪枝動作之外,DeepCut還包括了兩種類型的分區(qū)動作。一種是簡單分區(qū)動作,即當前節(jié)點沿著一個維度進行分區(qū)。另一種分區(qū)動作是基于啟發(fā)式的分區(qū)方法。Neuro-Cut的單線程實現(xiàn)對于小型分類器就足夠了。但是對于具有數(shù)以萬計的規(guī)則的大型分類器,并行性可以顯著提高訓練速度。

圖2 分類時間

圖3 內(nèi)存占用

2 實現(xiàn)過程

在Python中實現(xiàn)了DeepCut的決策樹數(shù)據(jù)結構。為了確保實現(xiàn)上的細微差別不會影響結果,使用相同的數(shù)據(jù)結構來實現(xiàn)每個基準算法以及實現(xiàn)DeepCut。

DeepCut以遞歸的方式計算所有子狀態(tài)的回報,該過程難以采用一個單獨的MDP進行建模。因此,將DeepCut的環(huán)境看作一系列互相獨立的一步?jīng)Q策問題,每一個決策問題都能產(chǎn)生一個即時回報。當子樹的rollout完成后,就可以得到一步?jīng)Q策的真實回報。

例如,假設從樹的根節(jié)點s1進行rollout?;诓呗驭笑?,agent采用動作a1后,將根節(jié)點s1分裂為子節(jié)點s2,s3以及s4。在這三個子節(jié)點中,假設采用動作a2將子節(jié)點s4分裂為s5和s6。這兩個rollout操作包括了兩個一步?jīng)Q策,即(s1,a1)和(s4,a2)。假設參數(shù)c為1,折扣因子為1。那么,這兩個rollout的總回報分別為2和1。

由于一步?jīng)Q策是互相獨立,因此DeepCut在多agent環(huán)境中實現(xiàn),每個節(jié)點的獨立地進行一步?jīng)Q策問題的求解。由于要為所有狀態(tài)學習策略πθ,因此所有的agent都需要使用相同的隨機神經(jīng)網(wǎng)絡策略。這確保了所有經(jīng)驗都可以優(yōu)化單個共享策略πθ。在利用現(xiàn)成的增強學習算法庫,可以實現(xiàn)DeepCut的一步?jīng)Q策。假設使用簡單的actor-critic算法,并展示了單線程實現(xiàn)的偽代碼。

發(fā)現(xiàn)DeepCut通常會在幾百次rollout中收斂到其最佳解決方案。規(guī)則集的大小不會影響收斂所需的rollout數(shù)量,但會影響每個rollout的運行時間。對于較小的問題(例如1000條規(guī)則),這可能需要幾分鐘的CPU計算時間。大規(guī)模問題的計算開銷由分類器的大小決定。

在學習的初始階段,沒被優(yōu)化的策略會產(chǎn)生一個規(guī)模龐大的決策樹。DeepCut只有在決策樹構建完成后才開始進行學習,因此需要對rollout進行剪枝以加快決策樹的構建。由于有效解決方案所對應的決策樹樹高不會太高,因此當決策樹達到一定的高度,就需要進行剪枝。為了增強學習的穩(wěn)定性和效率,采用Proximal Policy Optimization (PPO)[5]算法來計算actor-critic的誤差。

3 實驗評估

在亞馬遜云服務平臺中運行DeepCut,所使用的計算機實例為m4.16xl。由于神經(jīng)網(wǎng)絡和數(shù)據(jù)集的規(guī)模均比較小,因此本實驗并沒有使用GPU。DeepCut的最大迭代次數(shù)是100萬次。將DeepCut與EffiCuts[6]算法進行對比。采用Classbench,通過分析控制接入列表、防火墻以及IP鏈來生成分類規(guī)則庫和測試所需的trace文件[2]。探討了算法在分類時間和內(nèi)存占用方面的表現(xiàn),結果分別如圖2和圖3所示。DeepCut在學習的過程中,以最小化分類時間和內(nèi)存占用為目標。由實驗結果可知,與現(xiàn)有的方法EffiCuts相比,DeepCut的確可以有效地減少分類時間和內(nèi)存占用。

4 結 語

本研究設計了一個基于深度增強學習的網(wǎng)絡數(shù)據(jù)包分類算法,以減少內(nèi)存占用和分類時間為目標。給定一系列的規(guī)則和目標,本方法能夠自適應地學習最優(yōu)的數(shù)據(jù)包分類策略,避免了基于人工選擇特征的方法所帶來的問題。實驗的結果驗證了深度學習方法在數(shù)據(jù)包分類方面的有效性,說明深度學習方法適用于數(shù)據(jù)包分類問題。

猜你喜歡
決策樹數(shù)據(jù)包分區(qū)
貴州省地質(zhì)災害易發(fā)分區(qū)圖
二維隱蔽時間信道構建的研究*
上海實施“分區(qū)封控”
手診分區(qū)法之原理探析與診斷應用
民用飛機飛行模擬機數(shù)據(jù)包試飛任務優(yōu)化結合方法研究
C#串口高效可靠的接收方案設計
決策樹和隨機森林方法在管理決策中的應用
基于決策樹的出租車乘客出行目的識別
大空間建筑防火分區(qū)設計的探討
基于模糊關聯(lián)規(guī)則和決策樹的圖像自動標注