決策樹算法在應(yīng)急預(yù)案評估中的應(yīng)用分析

柴偉杰,付志兵,王志芳

(河北遠東哈里斯通信有限公司,河北石家莊050081)

0 引言

近些年來國內(nèi)外發(fā)生了不少重大特大的突發(fā)事件,面對這些事件,世界各國政府采取了積極有效的應(yīng)急措施,相應(yīng)的各類應(yīng)急預(yù)案的編制工作也在不斷的進行著,建立健全了應(yīng)對突發(fā)公共事件的應(yīng)急預(yù)案機制。

然而,應(yīng)急預(yù)案能否成功的運用于突發(fā)事件將直接影響應(yīng)急救援效率。這就需要對預(yù)案的有效性進行預(yù)先評估,目前這方面的研究非常缺乏。文獻[3]提出了基于改進的多屬性群決策方法的突發(fā)事件應(yīng)急預(yù)案評估,文獻[4]進行了基于模糊綜合評判的突發(fā)公共事件應(yīng)急預(yù)案評估的研究分析,采用模糊評估理論的多級評估方法對應(yīng)急預(yù)案的評估進行了大量的研究,第六屆中國管理科學(xué)學(xué)術(shù)年會中提出的基于模糊綜合評價方法的突發(fā)事件應(yīng)急預(yù)案評估。這些的評估方法大都需要相關(guān)評估指標或?qū)傩缘臋?quán)重,而權(quán)重是由專家設(shè)定的,不同的專家由于主觀性給出的權(quán)值會不同,最終得到的評估結(jié)果也可能會有很大的出入。決策樹算法是一種基于大樣本的算法,它能對所有樣本數(shù)據(jù)的高度概括,即決策樹能準確地識別所有樣本的類別,也能有效地識別新樣本的類別,可以減少人為因素的影響。

1 評價指標的建立

應(yīng)急預(yù)案的實施可以看作是一個項目的實施,因此可以借鑒項目管理中后評估的方法。項目后評估可以分為:項目跟蹤評估、實施效果評估和項目影響評估。應(yīng)急預(yù)案的實施是為了減少突發(fā)事件造成的影響和損失,因此對應(yīng)急預(yù)案實施的后評估主要從應(yīng)急預(yù)案的實施過程和效果2個方面進行評估。

對應(yīng)急預(yù)案的后評估是在應(yīng)急預(yù)案實施后對其實施效果進行的評估,比如在應(yīng)急預(yù)案實施過程中出現(xiàn)資源未能滿足需求的情況,是由于地區(qū)資源布局不足,還是資源調(diào)度過程事件耽誤,或者是應(yīng)急指揮者的判斷失誤等等。對應(yīng)急預(yù)案的一個評估主要是針對應(yīng)急預(yù)案的操作步驟以及由此帶來的結(jié)果的,由于不同類別不同級別的響應(yīng)流程所對應(yīng)的操作步驟的要求不一樣,所以對應(yīng)的評估指標也是不一樣的。

根據(jù)應(yīng)急預(yù)案的執(zhí)行流程,能夠知道應(yīng)急響應(yīng)的接警出警時間,各個部門的救援人員到位情況以及到位時間,應(yīng)急預(yù)案實施過程中所需要的設(shè)備資源,凡是能夠影響突發(fā)事件的一切資源,還有應(yīng)急響應(yīng)流程執(zhí)行結(jié)束后的傷亡人數(shù)、經(jīng)濟損失,以及所帶來的社會影響,這里將它們篩選后作為評估指標。由于主要研究的是應(yīng)用決策樹算法對應(yīng)急預(yù)案進行評估,暫時使用分析得到的如下一些指標作為評估指標來進行試驗:①接警時間;②各個部門的應(yīng)急人員情況;③應(yīng)急資源數(shù)量及配備情況;④經(jīng)濟損失;⑤傷亡人數(shù);⑥救援時間。

對應(yīng)急預(yù)案進行評估,其中所涉及的指標不止這些,為了簡單起見,這里只拿這些指標做實驗,更多的評估指標該算法同樣適用。

2 決策樹算法

決策樹是用樣本的屬性作為結(jié)點,用屬性的取值作為分支的樹結(jié)構(gòu)。它是利用信息論原理對大量樣本的屬性進行分析和歸納而產(chǎn)生的。決策樹的根結(jié)點是所有樣本中信息量最大的屬性,樹的中間結(jié)點是以該結(jié)點為根的子樹所包含的樣本子集中信息量最大的屬性,決策樹的葉節(jié)點代表一個類或類分布。從根節(jié)點到葉子節(jié)點的一條路徑形成一條分類規(guī)則。

決策樹用于對新樣本的分類,即通過決策樹對新樣本屬性值的測試,從樹的根結(jié)點開始,按照樣本屬性的取值,逐漸沿著決策樹向下,直到樹的葉節(jié)點。決策樹方法是數(shù)據(jù)挖掘中非常有效的分類方法。

2.1 信息論相關(guān)計算

信息熵:

式中類別ui出現(xiàn)概率為:

條件熵:

其中屬性Ai取值vi時,類別ui的條件概率為:

互信息:

互信息的大小即是判定樣本中哪個屬性作為決策樹根節(jié)點的依據(jù),該運算中互信息大的屬性就是這顆樹的根結(jié)點。樹的中間結(jié)點是以該結(jié)點為根的子樹所包含的樣本子集中信息量最大的屬性。

2.2 ID3算法

決策樹ID3主算法的主要步驟如下:

①從訓(xùn)練集中隨機選擇一個含有正例集和反例集的子集(稱為“窗口”);

②用“建樹算法”對當前窗口形成一棵決策樹;

③對訓(xùn)練集(窗口除外)中例子用所得決策樹進行類別判定,找出判錯的例子;

④若存在判錯的例子,把它們插入窗口,重復(fù)步驟②,否則結(jié)束。

主算法流程如圖 1所示。其中PE、NE分別表示正例集和反例集,它們共同組成訓(xùn)練集。PE1,PE2和NE1,NE2分別表示正例集和反例集的子集。

圖1 決策樹主算法流程

建樹算法的具體步驟如下:

①對當前例子集合,計算各特征的互信息;

②選擇互信息最大的特征AK;

③把在AK處取值相同的例子歸為同一子集,AK取幾個值就是幾個子集;

④對既含正例又含反例的子集,遞歸調(diào)用建樹算法;

⑤若子集僅含正例和反例的,對應(yīng)分枝標上P或N,返回調(diào)用處。

測試中,預(yù)案的最終評價結(jié)果暫定為優(yōu)、良、中、差4類,用它們代表上面所說的正例和反例的分類。

2.3 評估指標離散化處理

決策樹是用在預(yù)案評價中,所以針對評價指標數(shù)據(jù)的特點(數(shù)據(jù)的連續(xù)性),需要實現(xiàn)連續(xù)數(shù)據(jù)的離散化處理,這里使用K-Means(K均值)聚類算法來實現(xiàn)。K-Means算法接受輸入量k;然后將n個數(shù)據(jù)對象劃分為k個聚類以便使得所獲得的聚類滿足:同一聚類中的對象相似度較高;而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”(引力中心)來進行計算的。

K-means算法的工作過程說明如下:首先從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心;而對于所剩下其他對象,則根據(jù)它們與這些聚類中心的相似度(距離),分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然后再計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值);不斷重復(fù)這一過程直到標準測度函數(shù)開始收斂為止。一般都采用均方差作為標準測度函數(shù)。k個聚類具有以下特點:各聚類本身盡可能的緊湊,而各聚類之間盡可能的分開。KMeans算法流程如圖2所示。

具體算法過程如下:

①從N個數(shù)值中隨機選取k個數(shù)據(jù)作為質(zhì)心;

②對剩余的每個數(shù)據(jù)測量其到每個質(zhì)心的距離,并把它歸到最近的質(zhì)心的類;

③重新計算已經(jīng)得到的各個類的質(zhì)心(該類中所有對象的均值);

④迭代第②、第③步直至新的質(zhì)心與原質(zhì)心相等或小于指定閥值,算法結(jié)束。

對要進行連續(xù)數(shù)據(jù)離散化的屬性(評估指標),首先從所選對象數(shù)據(jù)中隨機的選取k(分類數(shù))個對象作為初始聚類的中心,然后就依據(jù)算法流程開始計算分類,最終將連續(xù)數(shù)據(jù)對象成功的離散化為需要的k個類別。

圖2 K-Means算法流程

3 應(yīng)急預(yù)案評估的實現(xiàn)

以預(yù)案都涉及的共性的評估指標為例介紹決策樹算法在應(yīng)急預(yù)案評估中的應(yīng)用并進行分析。

首先,進行評估指標的篩選。評估指標的數(shù)值分2種類型:枚舉類型和數(shù)值類型。對于枚舉類型要求類別不能太多,4～6個最為合適,取太多容易使生成的樹過于胖,形成的規(guī)則過于“精確”,無法實現(xiàn)對新樣本的合理分析;取太少,形成的規(guī)則又過于粗略,不能正確的分類,因此枚舉類型的類別太多太少都不合適。而數(shù)值類型的屬性,需要對這些數(shù)據(jù)做處理才能應(yīng)用到?jīng)Q策樹算法中,這里就選擇聚類算法中的K-Means算法來實現(xiàn)對數(shù)據(jù)的分類,同樣分類也要適中。

其次,獲取樣本數(shù)據(jù)。表1為地震評估指標的一些模擬樣本數(shù)據(jù),用于生成決策樹。

表1 地震評估樣本指標表

每次突發(fā)事件最后都要進行總結(jié),統(tǒng)計人員傷亡、經(jīng)濟損失和資源消耗等,并且針對本次突發(fā)事件進行評估,最終給出一個總的評估結(jié)果。這里的樣本數(shù)據(jù)就是每次突發(fā)事件的評估指標項數(shù)據(jù)及最后的評估結(jié)果。由于全國各個地方的地質(zhì)結(jié)構(gòu)不一樣,所以在獲取這些樣本的時候要按地區(qū)進行,這樣有利于最終生成決策樹并且用于對新樣本的評估,這是因為地質(zhì)結(jié)構(gòu)較為接近的地區(qū)樣本評估指標項也可以認為是一樣的,并且這樣的樣本越多越有利于決策樹的生成。

再次,生成決策樹。每個項目的內(nèi)容不一樣,評估指標也不一樣,因此對決策樹的要求也就不一樣。例如應(yīng)急預(yù)案的評估,評估項中的大部分都是數(shù)值類型的,需要對這些數(shù)據(jù)離散化處理才能滿足決策樹分類的需要。這里采用的就是K-Means算法實現(xiàn)的。按照上述的建樹流程構(gòu)造決策樹,程序通過循環(huán)方式,先計算各屬性的熵,然后比較各屬性熵的大小,選擇值最大的屬性進行分類,遞歸直到生成一顆完整的決策樹。

某次演練的評估結(jié)果及建議如表2所示。

表2 某次演練的評估結(jié)果及建議

最后,實現(xiàn)對新樣本的評估。新樣本的數(shù)據(jù)結(jié)構(gòu)必須與生成決策樹的這些樣本結(jié)構(gòu)一致。表2是對一次演練數(shù)據(jù)的評估,并且針對預(yù)案要求,該算法能夠?qū)崿F(xiàn)給出一些評估指標參考取值。

4 結(jié)束語

在項目中的應(yīng)用與測試結(jié)果表明:K-Means算法將連續(xù)數(shù)據(jù)型指標離散化處理分為2類。通過遞歸遍歷生成的決策樹,能夠?qū)崿F(xiàn)對當前數(shù)據(jù)進行分析,得到評估建議。該預(yù)案評估算法準確性很高,同時能夠大大減少了專家評估中人為因素的影響,并且針對預(yù)案中出現(xiàn)的問題能夠給出參考性的建議,使評估更加的客觀,預(yù)案實施更加科學(xué)有效。

評估指標之間有很大的關(guān)聯(lián),并且關(guān)聯(lián)程度不一樣。單個指標的重要性在評估中不能很好地體現(xiàn)出來,因此需要對算法和評估指標做進一步的研究,使這種算法在應(yīng)急預(yù)案評估中得到更好的應(yīng)用。

[1]NAKANISHIY.Assessing Emergency Preparedness of Transit Agencies:A fouctm on Performance Indicators[C].The 82ndAnnual Meeting of the Transportation Research Board,2003(4):24-32.

[2]劉功智,劉鐵民.重大事故應(yīng)急預(yù)案編制指南[J].勞動保護,2004,2(4):11-18.

[3]孫 穎,池宏等.基于改進的多屬性群決策方法的突發(fā)事件應(yīng)急預(yù)案評估[J].中國管理科學(xué),2005,13(10):153-156.

[4]張 勇,賈傳亮,王建軍.基于模糊綜合評價方法的突發(fā)事件應(yīng)急預(yù)案評估[J].中國管理科學(xué),2004,12(10):153-156.