喻 慧，張 明，喻 玨

（南京航空航天大學(xué)民航學(xué)院，南京 211106）

基于K-means范例推理的救援物資需求預(yù)測(cè)

喻 慧，張 明，喻 玨

（南京航空航天大學(xué)民航學(xué)院，南京 211106）

針對(duì)低空救援過程中物資需求的模糊性，提出基于K-means范例推理法的物資需求預(yù)測(cè)。首先，對(duì)范例屬性用粗糙集進(jìn)行簡(jiǎn)約，并計(jì)算各屬性的權(quán)重值；其次，將簡(jiǎn)約后的范例運(yùn)用基于DB Index準(zhǔn)則的K-means算法進(jìn)行聚類分析；然后，計(jì)算當(dāng)前范例與距離最小類中所有范例的相關(guān)系數(shù)，檢索出相似度最大的目標(biāo)范例，并根據(jù)目標(biāo)范例的消耗量線性求解當(dāng)前范例的需求量；最后，比較該方法與遺傳優(yōu)化BP算法的準(zhǔn)確性，結(jié)果表明基于K-means范例推理的預(yù)測(cè)算法具有更高精度。

K-means；范例推理；粗糙集；需求預(yù)測(cè)

應(yīng)急救援資源的需求預(yù)測(cè)受到諸多社會(huì)、環(huán)境等因素影響，具有很強(qiáng)的時(shí)效性和階段性，同時(shí)災(zāi)情和物資需求信息具有模糊性和不確定性，災(zāi)情發(fā)生短時(shí)間內(nèi)獲取的信息極為有限，需結(jié)合對(duì)災(zāi)區(qū)歷史統(tǒng)計(jì)數(shù)據(jù)挖掘基礎(chǔ)上進(jìn)行的資源需求分布預(yù)測(cè)，以保證預(yù)測(cè)的準(zhǔn)確性?？茖W(xué)合理的應(yīng)急救援物資需求預(yù)測(cè)不僅能給災(zāi)民提供充足的物資保障，而且能為應(yīng)急調(diào)度策略的實(shí)施提供基礎(chǔ)數(shù)據(jù)。因此，對(duì)應(yīng)急救援物資需求進(jìn)行合理預(yù)測(cè)是必不可少的救援環(huán)節(jié)。Guo等[1]針對(duì)應(yīng)急物流的突發(fā)性、不確定性和復(fù)雜性等特點(diǎn)，提出基于模糊馬爾可夫鏈的應(yīng)急物資需求預(yù)測(cè)模型；Sun等[2]采用了兩區(qū)域間模糊粗糙集方法來對(duì)應(yīng)急物資需求進(jìn)行預(yù)測(cè)；Hu[3]提出了一個(gè)保護(hù)災(zāi)害節(jié)點(diǎn)的基于公差模型的應(yīng)急需求預(yù)測(cè)方法；Mohammadi等[4]提出了一種新的基于混合進(jìn)化RBF神經(jīng)網(wǎng)絡(luò)的方法對(duì)緊急供應(yīng)需求量進(jìn)行預(yù)測(cè)研究。已有的相關(guān)研究并未考慮特征因素間的相關(guān)性，而且屬性權(quán)重的確定在一定程度上仍依賴人的主觀判斷，大多忽略了對(duì)歷史災(zāi)情數(shù)據(jù)的信息挖掘，缺乏將歷史物資需求數(shù)據(jù)挖掘規(guī)則結(jié)合到應(yīng)急物資需求預(yù)測(cè)中去，因而難以獲得準(zhǔn)確的應(yīng)急救援物資需求。為使預(yù)測(cè)結(jié)果更為準(zhǔn)確，本文提出一種基于K-means的范例推理法對(duì)低空應(yīng)急救援物資需求進(jìn)行預(yù)測(cè)。

一般來說，低空救援過程中首要解決的是效率和準(zhǔn)確率問題，而歷史災(zāi)情范例具有多屬性、數(shù)據(jù)多而雜的特點(diǎn)，傳統(tǒng)的范例推理法[5]在一定程度上會(huì)影響整個(gè)救災(zāi)效果，因此，提高范例檢索效率及準(zhǔn)確率是應(yīng)急物資預(yù)測(cè)中急需解決的問題。為提高大數(shù)據(jù)的檢索效率，首先對(duì)范例各屬性運(yùn)用粗糙集方法進(jìn)行屬性的簡(jiǎn)約，并計(jì)算各屬性的權(quán)重值，然后將簡(jiǎn)約后的范例運(yùn)用基于DB_Index準(zhǔn)則的K-means算法進(jìn)行聚類分析，再計(jì)算當(dāng)前范例與距離最小類中所有范例的相關(guān)系數(shù)，檢索出相似度最大的歷史目標(biāo)范例，并根據(jù)目標(biāo)范例的物資消耗量以及各屬性的權(quán)重值線性求解當(dāng)前范例的物資需求量。該方法在一定程度上提高了范例的檢索效率與需求預(yù)測(cè)精度。

1 基于DB Index準(zhǔn)則的K-means聚類算法

K-means算法采用歐式距離作為兩個(gè)樣本聚類評(píng)價(jià)指標(biāo)，其基本思想是：隨機(jī)選取歷史范例數(shù)據(jù)庫中的k個(gè)點(diǎn)作為初始聚類的中心，根據(jù)各范例到k個(gè)中心的距離將其歸類到距離最小的類中，然后計(jì)算各個(gè)類中范例距離的平均值，更新每個(gè)類的中心，直到聚類中心不再發(fā)生變化。其目標(biāo)是將范例數(shù)據(jù)庫中的范例分成若干個(gè)類，使得同一類范例間的相似度盡可能大，不同類范例間的相似度盡可能小。

本文使用DB Index準(zhǔn)則評(píng)估k的最優(yōu)取值，獲得數(shù)據(jù)的分類，為下文找出與當(dāng)前范例相似度最高的歷史范例提供數(shù)據(jù)支持，DB Index準(zhǔn)則評(píng)估步驟如下：

1）類內(nèi)平均離散度

其中：Zi是Ci類的類中心；表示Ci類樣本數(shù)；

DB Index準(zhǔn)則是DBk值越小，說明分類效果越好。

2 基于范例推理的物資需求預(yù)測(cè)

2.1 范例推理預(yù)測(cè)方法

2.1.1 基于粗糙集的范例屬性簡(jiǎn)約

針對(duì)災(zāi)情范例的模糊性與不確定性，首先需對(duì)范例屬性進(jìn)行規(guī)整，得到簡(jiǎn)化后范例特征以提高數(shù)據(jù)的處理效率。

粗糙集理論[6]是波蘭數(shù)學(xué)家Z·Pawlak于1982年提出的，其在處理不完整數(shù)據(jù)和不精確數(shù)據(jù)方面具有獨(dú)特優(yōu)勢(shì)。設(shè)信息系統(tǒng)S=（C，B），C={C1，C2，…，Cn}為范例數(shù)據(jù)庫，Cn為第n個(gè)范例，B為范例屬性所組成的集合，即B=F∪D。其中，F(xiàn)={f1，f2，…，fm}為條件屬性集，即和地震有關(guān)的情景特征因素（如總?cè)丝?、總面積、震級(jí)、震源深度、最高烈度、受災(zāi)人數(shù)、傷亡人數(shù)、磚混比例）信息集，fm為第m個(gè)屬性的信息；D={D1，D2，…，Di}為決策屬性集，即主要應(yīng)急物資需求集，Di為第i類物資的需求量，在本文中D0表示耐用品需求量，D1表示消耗品需求量。給定各條件屬性閾值，范例條件屬性值滿足閾值要求為1，否則為0，按此規(guī)則生成0-1信息表。如果C/ind（F）=C/ind（F-{fm}），則屬性fm可以約簡(jiǎn)，否則不可約簡(jiǎn)。

2.1.2 屬性權(quán)重值計(jì)算

在不同的決策環(huán)境下，各條件屬性對(duì)決策結(jié)果會(huì)有不同程度的影響，在此需計(jì)算出簡(jiǎn)約后范例的各條件屬性對(duì)物資預(yù)測(cè)結(jié)果的影響程度，用屬性權(quán)重值ωj表示。令條件屬性集F={f1，f2，…，fm}的影響權(quán)重集為{ω1，ω2，…，ωm}，且滿足

在不同的決策環(huán)境下，條件屬性對(duì)決策輸出會(huì)有不同影響。令n（f）表示范例在條件屬性為f時(shí)的取值。當(dāng)n（f）在范例庫C={C1，C2，…，Cn}中的分布差異較大時(shí)，說明該條件屬性對(duì)分類判別作用大，應(yīng)賦予較高權(quán)重值；反之，當(dāng)n（f）在分類中的分布差異較小時(shí)，說明該條件屬性對(duì)分類作用不大，應(yīng)取較小的權(quán)重值。范例Ci在條件屬性fj下的取值n（fj）為該案例在特征因素fj下的隸屬度函數(shù)，并有

均方差為

則可求得各特征因素的權(quán)重ωj為

2.1.3 范例相似度計(jì)算

根據(jù)K-means算法的分類，找出K個(gè)聚類中心點(diǎn)距離當(dāng)前范例最近的一類，再比較當(dāng)前范例與該類中的每一個(gè)范例的相似度，找出相似度最大歷史災(zāi)情范例，為當(dāng)前范例的物資需求預(yù)測(cè)提供數(shù)據(jù)基礎(chǔ)。

本文采用相關(guān)系數(shù)對(duì)范例間的相似度進(jìn)行計(jì)算，其中相關(guān)系數(shù)的定義如下

相關(guān)系數(shù)是衡量隨機(jī)向量X與Y相關(guān)程度的一種方法，取值范圍是[-1，1]。相關(guān)系數(shù)的絕對(duì)值越大，則表明X與Y相關(guān)度越高。

2.1.4 覆蓋度計(jì)算

規(guī)則覆蓋度的直觀意義就是符合某個(gè)決策規(guī)則的對(duì)象數(shù)占整個(gè)論域空間對(duì)象數(shù)的比例。

2.2 應(yīng)急救援物資需求預(yù)測(cè)

假設(shè)相似度最大的歷史目標(biāo)范例的總?cè)丝?、震?jí)、傷亡人數(shù)及磚混比例分別為P1、P2、P3和P4，耐用品和消耗品的供應(yīng)量分別為N1、N2，條件屬性f1、f3、f7、f8的權(quán)重值分別為ω1、ω3、ω7、ω8，當(dāng)前范例的總?cè)丝?、震?jí)、傷亡人數(shù)以及磚混比例分別為P1′、P2′、P3′和P4′，則當(dāng)前范例耐用品和消耗品的需求量N1′和N2′分別為

3 算例分析

3.1 范例屬性簡(jiǎn)約及權(quán)重值計(jì)算

選取2008—2012年22個(gè)災(zāi)情數(shù)據(jù)[7]作為訓(xùn)練樣本，如表1所示，其中，條件屬性為總?cè)丝冢ㄈ耍?、總面積（km2）、震級(jí)（級(jí)）、震源深度（級(jí)）、最高烈度（級(jí)）、受災(zāi)人數(shù)（人）、傷亡人數(shù)（人）、磚混比例，決策屬性為耐用品需求量D0（kg）、消耗品需求量D1（kg）。將樣本的條件屬性按表2的規(guī)則進(jìn)行離散化處理，超過閾值的屬性值設(shè)為1，否則設(shè)為0。

離散化后，屬性f1、f2對(duì)各范例的屬性值相同，故只保留屬性f1；同樣，屬性f3、f4、f5對(duì)各范例的屬性值相同，保留屬性f3；屬性f6、f7對(duì)各范例的屬性值相同，保留屬性f7。屬性簡(jiǎn)約后得到新的條件屬性集為F= {f1、f3、f7、f8}。再按式（4）計(jì)算出當(dāng)前條件屬性集中各屬性的權(quán)重值分別為ω1=0.13、ω3=0.36、ω7=0.31、ω8=0.20，權(quán)重值越大，說明該條件屬性對(duì)分類判別的作用越大，反之，權(quán)重值越小，說明該屬性對(duì)分類判別的作用越小。

表1 范例信息Tab.1 Case information

表2 離散化處理規(guī)則Tab.2 Discrete processing rule

利用粗糙集屬性簡(jiǎn)約方法，屬性的維數(shù)從8維降到了4維，可以有效降低災(zāi)害范例冗余屬性，提高運(yùn)行效率，在不損失有效信息的前提下降低了數(shù)據(jù)處理的規(guī)模和存儲(chǔ)空間；而簡(jiǎn)約后的范例各屬性對(duì)應(yīng)急救援物資需求預(yù)測(cè)結(jié)果的影響也不同，因而再利用粗糙集的屬性重要度，確定約簡(jiǎn)后的范例屬性權(quán)重值，以克服由專家決定關(guān)鍵屬性和權(quán)重的主觀性，提高了應(yīng)急資源需求預(yù)測(cè)的效率和精度。

3.2 物資需求決策規(guī)則覆蓋度計(jì)算

經(jīng)過粗糙集簡(jiǎn)約所得決策規(guī)則如表3所示。搜集400條歷史災(zāi)情數(shù)據(jù)構(gòu)建范例數(shù)據(jù)庫，統(tǒng)計(jì)各規(guī)則發(fā)生頻率如下。

表3 物資需求決策規(guī)則Tab.3 Decision rule of material demand

對(duì)表3中第一行可分析出，當(dāng)總?cè)丝谛∮?00000人、震級(jí)≥6級(jí)、傷亡人數(shù)＜3 000人、磚混比例≥0.6這4個(gè)條件都滿足時(shí)，對(duì)應(yīng)初級(jí)救援配送方案為：耐用品D0的物資配送量為300～600 kg，消耗品D1的物資配送量為600～900 kg，規(guī)則依此類推，可得出不同的低空應(yīng)急救援快速響應(yīng)預(yù)案。

覆蓋度等于各規(guī)則頻率之和，當(dāng)條件覆蓋度大于90%時(shí)，則該規(guī)則成立[8]。通過表3中各規(guī)則出現(xiàn)的頻率，計(jì)算得出滿足該決策樣本數(shù)占整體樣本數(shù)的92.3%，即規(guī)則覆蓋率為92.3%，說明該規(guī)則成立，可用于實(shí)際救援，也為后續(xù)范例物資需求量預(yù)測(cè)提供理論依據(jù)。

3.3 范例聚類分析及物資需求預(yù)測(cè)

運(yùn)用K-means算法將400條歷史災(zāi)情數(shù)據(jù)[9]的范例樣本進(jìn)行分類，其結(jié)果如圖1～圖3所示。

圖1 k=2時(shí)的范例聚類結(jié)果Fig.1 Case clustering result when k=2

圖2 k=3時(shí)的范例聚類結(jié)果Fig.2 Case clustering result when k=3

通過對(duì)比以上實(shí)驗(yàn)聚類結(jié)果，可明顯看出k=2時(shí)范例聚類效果太分散，k=4時(shí)的范例聚類結(jié)果中各分類重疊區(qū)域較大，當(dāng)k=3時(shí)范例聚類效果較好，分類清晰可見。故選取k=3作為分類數(shù)。

圖3 k=4時(shí)的范例聚類結(jié)果Fig.3 Case clustering result when k=4

令當(dāng)前范例X22=（129 320，6.3，4 967，0.833），從而計(jì)算出X22與上述4個(gè)中心點(diǎn)的歐式距離分別為155 114.910、31 896.365、104 617.455、376 667.762。通過分析可知，當(dāng)前范例X22與第二類中心點(diǎn)O2的距離最近，故將當(dāng)前范例視為第二類，然后運(yùn)用Matlab將屬于第二類的數(shù)據(jù)篩選出來，并將當(dāng)前范例X22與第二類中的每個(gè)范例運(yùn)用式（5）進(jìn)行相似度計(jì)算。計(jì)算結(jié)果中最大的相關(guān)系數(shù)為0.999 983 050 183 65，其對(duì)應(yīng)的歷史案例是X141=（136 455，8.4，4 418，0.783），通過查找范例數(shù)據(jù)庫數(shù)據(jù)可知，歷史范例X141對(duì)耐用品和消耗品的物資需求量分別為1 100 kg和700 kg，故結(jié)合式（4）求得各條件屬性權(quán)值ω1=0.13、ω3=0.36、ω7=0.31、ω8=0.20，利用線性相關(guān)算法對(duì)當(dāng)前范例的耐用品和消耗品的物資需求量進(jìn)行預(yù)測(cè)，結(jié)果分別為D0=1 049 kg，D1=668 kg。

3.4 范例推理預(yù)測(cè)法與遺傳優(yōu)化BP預(yù)測(cè)法的比較

從400條歷史范例中選出X22=（129320，6.3，4967，0.833）作為當(dāng)前范例，已知其對(duì)耐用品和消耗品的物資需求量分別為1 000 kg和600 kg，運(yùn)用基于K-means的范例推理預(yù)測(cè)法及遺傳優(yōu)化BP預(yù)測(cè)法[10]的相同權(quán)值（即ω1=ω3=ω7=ω8=0.25）和不同權(quán)值（即ω1=0.13、ω3=0.36、ω7=0.31、ω8=0.20）時(shí)的相對(duì)誤差，如表4所示。

表4 K-means范例推理預(yù)測(cè)法與遺傳優(yōu)化BP預(yù)測(cè)法的比較Tab.4 Comparison between K-means CBR method and genetic optimization BP algorithm

由表4可以看出，根據(jù)屬性重要度計(jì)算的權(quán)重值，預(yù)測(cè)相對(duì)誤差較平均權(quán)重值下的相對(duì)誤差明顯要小，且預(yù)測(cè)結(jié)果較為穩(wěn)定，運(yùn)用基于DB_Index準(zhǔn)則的K-means聚類方法對(duì)歷史災(zāi)情范例進(jìn)行先分類后處理，不僅提高了運(yùn)行效率，也使預(yù)測(cè)結(jié)果更具準(zhǔn)確性。

4 結(jié)語

本文將范例推理理論和基于DB_Index準(zhǔn)則的K-means聚類算法引入低空救援物資需求預(yù)測(cè)領(lǐng)域，在對(duì)歷史范例的特征屬性進(jìn)行有效約簡(jiǎn)的基礎(chǔ)上，再利用K-means聚類算法對(duì)大量歷史災(zāi)情數(shù)據(jù)進(jìn)行分類，檢索出相似度最高的歷史范例，根據(jù)歷史案例的物資消耗量及各屬性的權(quán)重值來線性推測(cè)當(dāng)前相似范例的物資需求量。范例推理理論和基于DB_Index準(zhǔn)則的K-means聚類算法的結(jié)合不僅提高了范例的檢索效率，同時(shí)也提高了預(yù)測(cè)精度，使其成為應(yīng)急救援物資需求預(yù)測(cè)的新方法。

[1]GUO Z,QI M.Research on the Demand Forecast of Emergency Material Based on Fuzzy Markov Chain[C]//E-Product E-Service and E-Entertainment(ICEEE),2010 International Conference on.IEEE,2010:1-4.

[2]SUN B,MA W,ZHAO H.A fuzzy rough set approach to emergency material demand prediction over two universes[J].Applied Mathematical Modelling,2013,37(10/11):7062-7070.

[3]HU Z H.Relief Demand Forecasting in Emergency Logistics Based on ToleranceModel[C]//InformationManagementandEngineering(ICIME), 2010 The 2nd IEEE International Conference on.IEEE,2010:451-455.

[4]MOHAMMADI R,GHOMI S M T F,ZEINALI F.A new hybrid evolutionary based RBF networks method for forecasting time series：A case study of forecasting emergency supply demand time series[J].Engineering Applications of Artificial Intelligence,2014,36：204-214.

[5]夏興生,朱秀芳,潘耀忠,等.基于歷史案例的自然災(zāi)害災(zāi)情評(píng)估方法研究[J].災(zāi)害學(xué),2016,31(1):219-225.

[6]張文修，吳偉志，梁吉玉.粗糙集理論與方法[M].北京：科學(xué)出版社，2003：2-10.

[7]鄭通彥,馮 蔚,鄭 毅.2014年中國(guó)大陸地震災(zāi)害損失述評(píng)[J].災(zāi)害學(xué),2015,25(2):88-97.

[8]夏葉娟.基于粗糙集和決策樹的規(guī)則提取方法研究[D].南昌：南昌大學(xué),2008.

[9]中國(guó)地震局監(jiān)測(cè)預(yù)報(bào)司.中國(guó)大陸地震災(zāi)害損失評(píng)估匯編[M].北京:地震出版社,2001.

[10]吳雪蓮.自然災(zāi)害應(yīng)急物資需求預(yù)測(cè)方法研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2012.

（責(zé)任編輯：楊媛媛）

Low altitude rescue demand forecasting based on K-means CBR

YU Hui,ZHANG Ming,YU Jue
（College of Civil Aviation,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China）

Aiming at the fuzziness of supplies demand in the process of low altitude rescue,a CBR（case based reasoning）prediction algorithm based on K-means is proposed.Firstly,the attributes of case are reduced through rough set, the weight values of attributes are calculated.Next,a cluster analysis is made on simplified case through DB Index K-means algorithm;then,correlation coefficient is calculated between the current case and each case in the nearest group,retrievaling the target case with maximum similarity.Finally,according to the supplies of target case,demand of the current case is obtained.A real seismic data is conducted to compare the accuracy of the current approach and genetic optimization BP algorithm.Result shows that the K-means CBR algorithm has higher precision.

K-means;CBR;rough set;demand forecasting

V355.2

A

1674－5590（2017）02－0055－05

2016-09-05；

2016-10-13

國(guó)家自然科學(xué)基金項(xiàng)目（U1233101，7127113）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)（NS2016062）

喻慧(1992—)，女，湖北孝感人，碩士研究生，研究方向?yàn)榈涂站仍⒖罩薪煌ㄖ悄芑?