決策樹算法用于動態決策服務器推送機制的可行性研究與分析*

羅明皓李 偉

（1.武漢郵電科學研究院 武漢 430074）（2.武漢烽火信息集成技術有限公司 武漢 430074）

1 引言

基于瀏覽器的Web通信機制較基于定制客戶端的C/S通信方式而言，具有跨平臺、跨硬件、操作簡單、易于維護的特點，越來越多的應用開始兼容B/S通信方式。和C/S通信方式相比，早期B/S結構的明顯局限在于，瀏覽器獲取信息需要主動發送HTTP請求，HTTP是一種無狀態的單向協議，服務器接受請求并響應，瀏覽器獲取請求內容，連接隨后便斷開。客戶每一次都只能采用拉拽方式獲取信息，這在人們對網絡服務實時性、高效性的要求下表現出了明顯的短板。服務器推送技術的出現解決了此類問題。不同的服務器推送方式各有優劣，往往不能同時兼顧通信的高實時性和網絡資源的高利用率。根據不同推送方式的特點，不同的應用場景宜選擇不同的推送方式實現客戶端與服務器的交互，從而達到充分利用資源、提高服務質量的目的。一般的服務器推送技術框架為用戶采用單一、固定的傳輸模式，在一定程度上不夠靈活和全面，本文實驗部分使用機器學習算法解決這種單一推送方式造成的不足，構建一種基于決策樹算法的決策模型，討論該算法在模擬場景下用于服務器推送方法動態決策問題的可行性。實驗模擬實際使用場景，動態選擇服務器推送方式。由用戶對實時性的需求、事件的發生頻率及服務器本身負載承受能力和其他一些未知因素組成決策樹訓練集，利用訓練出的的決策樹進行推送方式的動態選取，充分利用網絡資源的同時兼顧服務推送的質量。

2 相關知識

2.1 服務器推送方法現狀

服務推送技術主要可分為兩大類：基于客戶端套接字的服務器推送技術，通過在瀏覽器上安裝插件，該插件與服務器間建立socket套接字實現數據反向推送；通過在HTTP頭部加入Connection屬性，服務器接收這個HTTP請求后根據Connection屬性決定是否保持當前連接［1］。需要安裝插件的推送方式本身會帶來跨平臺、版本兼容問題，并使B/S架構不再具備優勢，增大了系統維護成本，對于這類推送方式本文不做討論。本文主要討論第二種推送方式，具體到技術應用的幾種主流方法有如下幾種：

1）Ajax poll實現輪詢［11］

Ajax是通過HTTP請求與服務器進行輕量級的數據交互，使瀏覽器支持異步更新，而不需要刷新整個頁面。其實現原理在于在瀏覽器端設置一個時鐘周期，每隔一段時間就向服務器發送請求，獲取服務器端最新的數據，實現“輪詢”。該技術的性能取決于如何設置時鐘周期。

2）基于長輪詢的Comet技術long polling［11］

長輪詢同poll方式相似，也是客戶端不斷向服務器發送請求，與poll不同之處在于客戶端不需要按照時間間隔不斷地發送請求，而是發起1個請求到服務器之后，客戶端和服務器之間的HTTP連接保持打開，直到服務器有數據更新就通過這個連接向客戶端響應數據，隨后關閉這個連接，相比短輪詢，長輪詢發起的HTTP請求次數少，但HTTP長期阻塞在服務端也會耗費網絡資源。

3）基于ifream的Comet技術HTTP streaming［11］

HTTP streaming流基于ifream，需要在頁面嵌入一個隱藏的ifream，服務器和瀏覽器的長連接建立在這個ifream上，數據傳輸通過這個長連接完成［1］。HTTP streaming重復使用同一個連接，永不關閉，B/S間的TCP一直保持連接狀態，直至其中一方發送一條明顯的關閉信息或發生網絡錯誤。客戶端周期性通過這個連接向服務器獲取數據查看更新。

4）Websocket通信原理

Websocket是HTML5提出的新協議。它在B/S間架設了全雙工的通信信道，使用套接字來傳送數據。Websocket還是基于HTTP連接來實現，但與傳統HTTP區別主要在于頭部信息，Websocket請求會在頭部添加“Upgrade：Websocket”，經服務器解析后就可以建立起一個全雙工通信信道，Websocket的不足在于需要專有的后臺處理程序，維護和使用耗費的資源過多。

2.2 決策樹算法介紹

決策樹是一種有監督的分類模型，其本質是選擇一個能帶來最大信息增益的特征值進行結果集的分割，直到到達結束條件，或葉子結點純度到達一定閾值。按照分割指標和分割方法，決策樹的具體算法模型分為ID3、C4.5和CART［10］。不同決策樹算法選取不同分割指標，這些指標基于信息論理論，信息論中最基本的概念是信息熵H（X）：

從式（1）中可看出，變量不確定性和熵值成正相關。我們還可以對兩個或以上變量求聯合熵：

并從聯合熵得到條件熵的表達式：

條件熵反映了X在確定Y的前提下，X剩下的不確定性。決策樹算法就建立在這些信息論基礎之上。

1）ID3算法

ID3算法中我們使用互信息作為結果集分割指標：

式（4）度量了X在知道Y后的不確定性，ID3中也將互信息稱為信息增益。

在構建決策樹時，我們使用輸出樣本集合D和特征集合A作為訓練集，ID3針對離散特征構建決策樹，從根節點開始，依次進行增益閾值判斷、樣本類別標記、選擇該層信息增益最大的特征作為分類依據，并在分類后反復按照同樣步驟不斷分類，直至所有樣本分配到葉節點。

2）C4.5算法

C4.5在ID3的基礎上進行了改進。ID3有如下不足：

（1）ID3沒有考慮連續特征，比如長度，密度都是連續值，無法在ID3運用；

（2）ID3采用信息增益大的特征優先建立決策樹的節點。從ID3算法的分割依據中可推知，在相同條件下，取值多的特征比取值少的特征信息增益大；

（3）ID3算法對于缺失值的情況沒有做考慮；

（4）沒有考慮過擬合的問題［10］。

針對特征值連續的問題，C4.5選擇將連續的特征離散化，對相鄰的特征值取中值。

針對ID3選取的分割指標不能完全反映出特征值對樣本的影響情況的不足，C4.5引入了信息增益比作為分割指標：

其中HA()

D為特征熵：

特征數作為分母，可以校正信息增益容易偏向于取值較多的特征的問題。

對于缺失值處理的問題，有兩種解決角度，一是在樣本某些特征缺失的情況下選擇劃分的屬性，二是選定了劃分屬性，對在該屬性上缺失特征的樣本的處理。

3）CART算法

CART算法與前兩種算法的顯著區別表現在：采用剪枝方法解決ID3和C4.5都存在的過擬合問題；采取構建二叉樹的方式取代之前構建的多叉樹，提高搜索效率；選取基尼系數作為分割依據：

其中Ck指代樣本D中第k各類別的數量。

根據式（7）和CART算法將決策樹構建為二叉樹的特性，可以得出針對CART算法的基尼系數計算公式：

綜合式（4）、（5）、（8），可知CART算法減少了大量耗時的對數運算，減輕運算負擔，提高了構建樹的效率。

除引入基尼系數外，CART算法在ID3、C4.5的基礎上引入了剪枝的構建步驟，來防止對訓練集的過擬合。CART算法采用后剪枝方法，即建立好決策樹后，根據任一棵子樹的損失函數值判定是否剪枝：

其中，Tt是葉子節點數量，C()Tt為訓練集預測誤差，α是正則化參數。α越大，剪枝剪的越厲害，剪枝后的子樹就越小。當α滿足子樹單一葉節點和子樹損失函數相等時，由于單一葉節點數小于子樹節點數，此時可以進行剪枝。

3 決策樹用于服務器推送機制動態決策實驗設計

3.1 試驗設計思路

不同推送方式優劣分析：

四種不同推送方法有著不同的使用場景，輪詢適合簡單、請求周期固定、對實施性要求不高的服務場景，長輪詢適合事件頻率和實時性要求都一般的服務，性能比較適中，HTTP流模式則能滿足事件發生頻率高并且實時性要求也較高的情況，但對內存消耗過大。Websocket是一種新標準，也能保持服務端、瀏覽期間長久的連接，但對前期后臺開發要求高，需要獨立的后臺服務程序。

根據各推送方式的優缺點，選取四種用途最廣的推送方式組成結果集：Ajaxpoll輪詢、long-polling長輪詢、HTTP streaming、Websocket。

客戶端、服務端要建立連接、維護連接均需耗費自身資源，因此選取服務器負載和客戶端負載為特征。不同的推送方式在服務的實施性需求上表現各有不同，因此選取服務實時性需求、用戶權限、平均服務時間為特征，這幾種特征最終具體表現為以下七個特征：

用戶權限值（authority），服務實時性要求（real-time），服務器負載（load），系統吞吐量（throughput），服務可靠性（reliability），平均服務時間（time），客戶端線程數（threads）。

對這七個特征整合后得到特征集A，可知特征集中包含連續特征，選取可以處理連續特征集的C4.5算法和CART算法分別進行算法實現和結果比較。

C4.5和CART算法的計算步驟分別如圖1、圖2所示。

3.2 實驗數據設置

決策樹是一種機器學習算法，通過訓練集生成決策樹，生成的決策樹可對動態環境中的事件決策自動得出結果。

本文在設置訓練集數據時，首先在某一特征值的取值范圍內根據不同推送方式的適用場景進行進一步的范圍劃分。設置該推送方式的特征參數時會在劃分范圍中的某一范圍內隨機取參數，隨后協同各特征參數得出分類結果，協同依據：特征值對結果的影響權值設定為用戶權限值>服務可靠性>服務實時性要求>服務器負載>系統吞吐量>客戶端線程數>平均服務時間，權值由1至7遞增。

例如，若系統吞吐量在某一較低范圍內，則不選取提高系統吞吐量的Ajax輪詢推送方法，再結合其他特征值選取推送方法；而當用戶權限值要求較高時，優先選取響應速度、服務質量都較高的HTTP streaming模式，而現代大多服務器都能承載較高的用戶數，可以弱化對吞吐量等性能方面的考慮。

圖1 C4.5算法的計算步驟

圖2 CART算法剪枝過程的計算步驟

具體訓練集數據范圍設置和結果獲取方式如下所示。

驗證方法：

驗證數據集：使用與隨機生成訓練數據集相同規律生成的驗證數據驗證決策樹，計算決策誤差。

驗證算法性能：使用單一推送方式Ajax poll、long polling、HTTP streaming、Websocket進行推送，從服務器負載、吞吐量、實時性能等多方面與本文動態推送機制進行對比。提供的部分訓練數據集如表1所示。

4 實驗數據和結果分析

C4.5算法和CART算法生成決策樹決策結果誤差如圖3所示，兩種算法誤差相持平，且誤差值在較理想范圍內。

圖3 C4.5與CART算法誤差對比圖

模擬實驗中服務端負載計算方法：

不同推送方式設置不同負載量，Ajax poll設為2，long polling設為1，HTTP streaming設為3，Websocket設為4，對于動態推送機制取多種推送方式下服務端負載的平均值；以測試數據量為橫軸坐標，統計結果如圖4所示。

表1 部分訓練數據集

圖4 不同推送方式下的服務端負載

模擬實驗中實時性能計算方法：

不同推送方式設置不同實時性衡量數值，本文選擇響應時間，Ajax poll設為4，long polling設為3，HTTP streaming設為2，Websocket設為1，對于動態推送機制取多種推送方式下響應時間平均值；以測試數據量為橫軸坐標，統計結果如圖5所示。

圖5 不同推送方式下的響應時間

5 結語

C4.5和CART算法作為決策樹經典算法，對服務器推送機制的動態決策表現出了良好的性能，兩種算法主要區別在于甄選分割依據時使用指標不同，C4.5使用了信息增益比，CART算法使用基尼系數，從計算公式可直觀看出，從構建決策樹的計算量上比較，CART算法有優勢。同時，CART算法對生成決策樹進行剪枝操作，在對測試數據集進行決策的過程中可減少由于過擬合造成的多余比較步驟，總體而言，CART算法對計算機的負載更小。

從結果誤差角度比較兩種算法可推知，從結果準確角度評估兩種算法運用在服務器推送機制決策問題上表現出的性能，C4.5和CART算法無明顯區別，可以得出兩種經典算法在此類問題上都比較適用的結論。

從圖4、圖5可看出，動態決策服務器推送方式在較復雜環境中能將服務器負載、實時性能方面的表現基本維持在最優和次優推送方式之間，能較好地綜合每種推送方式的性能，但在單一網絡環境中，仍宜選擇最適宜該環境的推送方式。