決策樹算法用于動態(tài)決策服務(wù)器推送機制的可行性研究與分析*

羅明皓李 偉

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

1 引言

基于瀏覽器的Web通信機制較基于定制客戶端的C/S通信方式而言，具有跨平臺、跨硬件、操作簡單、易于維護的特點，越來越多的應(yīng)用開始兼容B/S通信方式。和C/S通信方式相比，早期B/S結(jié)構(gòu)的明顯局限在于，瀏覽器獲取信息需要主動發(fā)送HTTP請求，HTTP是一種無狀態(tài)的單向協(xié)議，服務(wù)器接受請求并響應(yīng)，瀏覽器獲取請求內(nèi)容，連接隨后便斷開?？蛻裘恳淮味贾荒懿捎美Х绞将@取信息，這在人們對網(wǎng)絡(luò)服務(wù)實時性、高效性的要求下表現(xiàn)出了明顯的短板。服務(wù)器推送技術(shù)的出現(xiàn)解決了此類問題。不同的服務(wù)器推送方式各有優(yōu)劣，往往不能同時兼顧通信的高實時性和網(wǎng)絡(luò)資源的高利用率。根據(jù)不同推送方式的特點，不同的應(yīng)用場景宜選擇不同的推送方式實現(xiàn)客戶端與服務(wù)器的交互，從而達到充分利用資源、提高服務(wù)質(zhì)量的目的。一般的服務(wù)器推送技術(shù)框架為用戶采用單一、固定的傳輸模式，在一定程度上不夠靈活和全面，本文實驗部分使用機器學(xué)習(xí)算法解決這種單一推送方式造成的不足，構(gòu)建一種基于決策樹算法的決策模型，討論該算法在模擬場景下用于服務(wù)器推送方法動態(tài)決策問題的可行性。實驗?zāi)M實際使用場景，動態(tài)選擇服務(wù)器推送方式。由用戶對實時性的需求、事件的發(fā)生頻率及服務(wù)器本身負載承受能力和其他一些未知因素組成決策樹訓(xùn)練集，利用訓(xùn)練出的的決策樹進行推送方式的動態(tài)選取，充分利用網(wǎng)絡(luò)資源的同時兼顧服務(wù)推送的質(zhì)量。

2 相關(guān)知識

2.1 服務(wù)器推送方法現(xiàn)狀

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

1）Ajax poll實現(xiàn)輪詢［11］

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

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

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

3）基于ifream的Comet技術(shù)HTTP streaming［11］

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

4）Websocket通信原理

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

2.2 決策樹算法介紹

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

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

并從聯(lián)合熵得到條件熵的表達式：

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

1）ID3算法

ID3算法中我們使用互信息作為結(jié)果集分割指標(biāo)：

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

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

2）C4.5算法

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

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

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

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

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

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

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

其中HA()

D為特征熵：

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

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

3）CART算法

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

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

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

綜合式（4）、（5）、（8），可知CART算法減少了大量耗時的對數(shù)運算，減輕運算負擔(dān)，提高了構(gòu)建樹的效率。

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

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

3 決策樹用于服務(wù)器推送機制動態(tài)決策實驗設(shè)計

3.1 試驗設(shè)計思路

不同推送方式優(yōu)劣分析：

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

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

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

用戶權(quán)限值（authority），服務(wù)實時性要求（real-time），服務(wù)器負載（load），系統(tǒng)吞吐量（throughput），服務(wù)可靠性（reliability），平均服務(wù)時間（time），客戶端線程數(shù)（threads）。

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

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

3.2 實驗數(shù)據(jù)設(shè)置

決策樹是一種機器學(xué)習(xí)算法，通過訓(xùn)練集生成決策樹，生成的決策樹可對動態(tài)環(huán)境中的事件決策自動得出結(jié)果。

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

例如，若系統(tǒng)吞吐量在某一較低范圍內(nèi)，則不選取提高系統(tǒng)吞吐量的Ajax輪詢推送方法，再結(jié)合其他特征值選取推送方法；而當(dāng)用戶權(quán)限值要求較高時，優(yōu)先選取響應(yīng)速度、服務(wù)質(zhì)量都較高的HTTP streaming模式，而現(xiàn)代大多服務(wù)器都能承載較高的用戶數(shù)，可以弱化對吞吐量等性能方面的考慮。

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

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

具體訓(xùn)練集數(shù)據(jù)范圍設(shè)置和結(jié)果獲取方式如下所示。

驗證方法：

驗證數(shù)據(jù)集：使用與隨機生成訓(xùn)練數(shù)據(jù)集相同規(guī)律生成的驗證數(shù)據(jù)驗證決策樹，計算決策誤差。

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

4 實驗數(shù)據(jù)和結(jié)果分析

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

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

模擬實驗中服務(wù)端負載計算方法：

不同推送方式設(shè)置不同負載量，Ajax poll設(shè)為2，long polling設(shè)為1，HTTP streaming設(shè)為3，Websocket設(shè)為4，對于動態(tài)推送機制取多種推送方式下服務(wù)端負載的平均值；以測試數(shù)據(jù)量為橫軸坐標(biāo)，統(tǒng)計結(jié)果如圖4所示。

表1 部分訓(xùn)練數(shù)據(jù)集

圖4 不同推送方式下的服務(wù)端負載

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

不同推送方式設(shè)置不同實時性衡量數(shù)值，本文選擇響應(yīng)時間，Ajax poll設(shè)為4，long polling設(shè)為3，HTTP streaming設(shè)為2，Websocket設(shè)為1，對于動態(tài)推送機制取多種推送方式下響應(yīng)時間平均值；以測試數(shù)據(jù)量為橫軸坐標(biāo)，統(tǒng)計結(jié)果如圖5所示。

圖5 不同推送方式下的響應(yīng)時間

5 結(jié)語

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

從結(jié)果誤差角度比較兩種算法可推知，從結(jié)果準(zhǔn)確角度評估兩種算法運用在服務(wù)器推送機制決策問題上表現(xiàn)出的性能，C4.5和CART算法無明顯區(qū)別，可以得出兩種經(jīng)典算法在此類問題上都比較適用的結(jié)論。

從圖4、圖5可看出，動態(tài)決策服務(wù)器推送方式在較復(fù)雜環(huán)境中能將服務(wù)器負載、實時性能方面的表現(xiàn)基本維持在最優(yōu)和次優(yōu)推送方式之間，能較好地綜合每種推送方式的性能，但在單一網(wǎng)絡(luò)環(huán)境中，仍宜選擇最適宜該環(huán)境的推送方式。