基于K-means范例推理的救援物資需求預測

喻 慧，張 明，喻 玨

（南京航空航天大學民航學院，南京 211106）

基于K-means范例推理的救援物資需求預測

喻 慧，張 明，喻 玨

（南京航空航天大學民航學院，南京 211106）

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

K-means；范例推理；粗糙集；需求預測

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

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

1 基于DB Index準則的K-means聚類算法

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

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

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

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

DB Index準則是DBk值越小，說明分類效果越好。

2 基于范例推理的物資需求預測

2.1 范例推理預測方法

2.1.1 基于粗糙集的范例屬性簡約

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

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

2.1.2 屬性權重值計算

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

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

均方差為

則可求得各特征因素的權重ωj為

2.1.3 范例相似度計算

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

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

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

2.1.4 覆蓋度計算

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

2.2 應急救援物資需求預測

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

3 算例分析

3.1 范例屬性簡約及權重值計算

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

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

表1 范例信息Tab.1 Case information

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

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

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

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

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

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

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

3.3 范例聚類分析及物資需求預測

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

圖1 k=2時的范例聚類結果Fig.1 Case clustering result when k=2

圖2 k=3時的范例聚類結果Fig.2 Case clustering result when k=3

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

圖3 k=4時的范例聚類結果Fig.3 Case clustering result when k=4

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

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

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

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

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

4 結語

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

[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]夏興生,朱秀芳,潘耀忠,等.基于歷史案例的自然災害災情評估方法研究[J].災害學,2016,31(1):219-225.

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

[7]鄭通彥,馮 蔚,鄭 毅.2014年中國大陸地震災害損失述評[J].災害學,2015,25(2):88-97.

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

[9]中國地震局監(jiān)測預報司.中國大陸地震災害損失評估匯編[M].北京:地震出版社,2001.

[10]吳雪蓮.自然災害應急物資需求預測方法研究[D].合肥:中國科學技術大學,2012.

（責任編輯：楊媛媛）

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

國家自然科學基金項目（U1233101，7127113）；中央高?；究蒲袠I(yè)務費專項（NS2016062）

喻慧(1992—)，女，湖北孝感人，碩士研究生，研究方向為低空救援、空中交通智能化.