基于K-means算法的突發(fā)事件地理信息空間化研究

楊 波，王繼周，毛 曦，馬維軍

(1. 遼寧工程技術大學，遼寧 阜新 123000； 2. 中國測繪科學研究院，北京 100830)

突發(fā)事件，是指突然發(fā)生，造成或者可能造成嚴重社會危害，需要采取應急處置措施予以應對的自然災害、事故災難、公共衛(wèi)生事件和社會安全事件[1-3]。伴隨著國家經(jīng)濟和人口的不斷增長，各地的突發(fā)事件也與日俱增。像某地發(fā)生的跳樓事件、聚眾打架斗毆事件、野外求救等類似惡性事件屢見不鮮，這類應急事件伴隨著發(fā)展周期短、影響惡劣以及即時性等特點，其結果嚴重影響國家的人民安全和社會秩序。面對這類災害性事件，應急預案處理過程中并沒有相關的基礎地理信息的空間化數(shù)據(jù)，而且由于報案人員語言描述的地理屬性信息并不規(guī)范。這給應急處置帶來了巨大的工作壓力，同時也增加了應急救援的難度和困難。本文針對以上問題提出了面向突發(fā)事件的地理信息空間化方法，其中基于應急災害事件的地名地址標準化方法請參考相關文獻[4—5]，本文主要研究那些在基礎地理信息庫中沒有空間化信息的突發(fā)事件的地理信息空間化。

地理信息的空間化方法主要包括應急地理信息匹配技術和應急地理格網(wǎng)的空間化[6-9]?；谕暾刂纷R別的方法是將突發(fā)事件對應的地址數(shù)據(jù)通過調(diào)用地圖服務來獲取空間化信息，由于數(shù)據(jù)處理簡單，也比較容易和其他統(tǒng)計數(shù)據(jù)結合，應用比較廣泛，但是單純的獲取空間化信息卻忽略了地理實體之間的空間關系[10]；基于格網(wǎng)的空間化方式雖然更加注重地理實體的空間關系，是現(xiàn)在地理信息科學研究的方向之一，但是其中涉及多個領域的知識，推理過程復雜，現(xiàn)在仍處于探索階段[11-12]。現(xiàn)有的地理信息空間化技術為常見的地名命名實體識別技術提供了扎實的基礎。但是，面對眾源應急事件，人們既需要分析地理信息的空間關系又需要及時、快速地獲取空間信息，尤其是獲取那些無法采用常用方法獲取的空間化信息。這類研究普遍有如下缺點：

(1) 只是獲取常見地址的空間信息，沒有獲取不常見地址的空間信息。

(2) 只是單一的分析空間關系，沒有結合地名與空間信息來綜合分析空間關系。

(3) 對獲取的空間化信息，沒有構建基于空間信息獲取的精度評估方法。

因此，本文通過分析科學的應急地理信息空間化方法，提出了基于K-means算法的眾源應急地理信息空間化研究。主要是通過應急地理屬性和空間信息來分析突發(fā)事件的空間關系[13]，包括眾源應急地理信息在空間中的拓撲關系、方位關系及度量關系。研究目標是解決通用地理信息空間化方法的不足，更重要的是為了解決應急事件的精確定位的問題。當相關應急災害發(fā)生時，該研究能夠為決策者快速準確地獲取到應急災害發(fā)生的場所，提高決策者的決策可行性與科學性，從而減少國家的人員與財產(chǎn)損失。

1 相關工作

為了實現(xiàn)上述研究目標，本文提出了基于眾源應急事件的地理信息空間化方法，其總體思路如圖1所示。

該技術框架有3個模塊：一是坐標擬合模塊，主要是將那些無法使用常用工具及方法來空間化的應急地理信息使用基于K-means算法進行空間坐標的擬合，從而補充普通方法空間化的不足；二是空間化模塊主要是將原有的應急地理信息轉化為應急空間信息，同時結合數(shù)據(jù)源中的應急地址信息分析其空間關系，這里的數(shù)據(jù)源是經(jīng)過基于事件框架的信息提取和突發(fā)事件應急處置的完整地址獲取之后的數(shù)據(jù)，具體請參考相關文獻；三是精度分析模塊，針對前兩個模塊進行試驗結果分析。這3個模塊相互關聯(lián)，前一個模塊的運行結果是后一個模塊的數(shù)據(jù)源，前一個模塊的結果也同時影響著后一個模塊的精度，對于各模塊的具體流程現(xiàn)分述如下。

圖1 總體技術流程

2 K-means算法

常見的地理信息的空間化方法有軌跡模擬空間化和統(tǒng)一坐標均值空間化。軌跡模擬即通過規(guī)則圖形的路徑軌跡來預測未知地理位置的坐標，該方法使用與具有線狀軌跡關系的坐標預測，但是當遇到離散地理位置時，此方法則無用武之地；坐標均值的方法是將已知的坐標通過取其均值來獲取未知地理位置坐標，這種方法雖然可以簡單地獲取未知地理位置的坐標，但是該方法是對所有坐標進行均值求坐標，求取結果的誤差不可估量；在數(shù)據(jù)挖掘中，K-means是在圖形圖像處理中廣泛應用的聚類算法[14-16]，其核心是計算數(shù)據(jù)的聚集程度，通過不斷地取離中心點最近的均值坐標來獲取最優(yōu)聚類解的算法[17]。K-means算法解決的問題如圖2所示，左側有離散應急信息點，可以很容易地判斷這是3個地址點群，但是如何通過計算機程序找到這3個地址點群，這是K-means能夠解決的問題。

圖2 K-means聚類分析

K聚類中心的準則函數(shù)為

(1)

式中，Gj為第j個聚類；Nj為第j個聚類中心的樣本數(shù)；Zj為第j個樣本的聚類中心。

算法步驟如下：

(1) 任選k個初始聚類中心Z1(l),Z2(l),…,Zk(l)。

(2) 計算每個樣本到k個聚類中心的距離，并按最近規(guī)則歸類；

(3) 從步驟(2)的計算結果計算新的聚類中心

(2)

式中，j=1,2,…,k，該聚類中心可以使準則函數(shù)的Jj值達到最小。

(4) 若新的聚類中心與前一個聚類中心相等，即

Zj(k+1)=Zj(k)

(3)

式中，j=1,2,…,k。當滿足式(3)的條件時，算法收斂，聚類結束；否則轉入步驟(2)。

該算法的執(zhí)行結果受所選的聚類中心的個數(shù)、初始位置、樣本的幾何性質(zhì)以及數(shù)據(jù)讀入的次序的影響。在對應急地理信息空間化的應用中可以結合實例只選擇一個聚類中心進行聚類擬合。如果測試樣本為N個孤立的區(qū)域分布，則很容易得到算法的收斂結果。

3 試驗與分析

本文以123 804個非空原始網(wǎng)頁為測試源樣本，精度評估參考的是信息檢索領域的經(jīng)典方法[18-19]，即查準率和查全率，詳細內(nèi)容請參考相關文獻。基于多維度地理空間認知模型的測試結果見表1。

表1 應急地理信息空間化的試驗分析

由試驗可知，影響應急地理信息空間化精度的主要誤差如下：

(1) 應急災害數(shù)據(jù)源存在一些噪聲，如應急災害的預防和災害常識的科普性文章，這些文章中并不包含突發(fā)事件信息。

(2) 某些應急災害的描述文件中并不包含地名信息，而且本文的主要測試對象是中文地址，但數(shù)據(jù)庫中并未構建國外地名數(shù)據(jù)庫信息，這是造成查準率低的主要原因。

(3) 本文的測試對象構建的是國內(nèi)三層行政區(qū)地名庫，包括省、市、縣地名結構，對于那些超出數(shù)據(jù)庫之外未能識別的應急地址信息，本不在誤差的考慮范圍之內(nèi)，但是考慮數(shù)據(jù)的真實可靠性，在計算時并沒有將其去除。如果去除這部分的噪聲樣本，綜合識別地址識別精度會更高。

(4) 在應急地理信息的空間化過程中，由于地圖服務的超時鏈接所產(chǎn)生的噪聲，這也是本文誤差來源之一。

當然，通過試驗分析發(fā)現(xiàn)，本文方法還不夠優(yōu)越，以后的應急信息提取研究之路任重道遠。本文的測試對象是中文地址，中文地址的命名規(guī)則是按照從大范圍到小范圍逐級遞減的結構命名[20]，這可能與非中文為母語的國家的地址命名存在差別。但是，本文的算法具有通用的參考價值，如以英語為母語的國家而言，他們國家的地址命名是從小到大的范圍逐漸擴大的規(guī)則，此時只要調(diào)用相應的地圖服務即可獲取應急空間信息。通過應急空間信息的精度評估，其綜合精度為81.94%，測試結果可靠，符合實際應急相關部分的精度需要。

4 結 語

本文通過對國內(nèi)外常見的空間化方法進行了對比總結，在此基礎上指出了常見空間化方法的不足之處。在應急測繪領域中，基于K-means算法的空間化是一種實際應用中較為少見獲取應急空間信息的方法。由于傳統(tǒng)的基礎地理信息并不直接等同于空間的位置信息，因此應急地理信息的空間化正是解決這一問題的關鍵。通過以上研究實現(xiàn)了眾源應急信息的空間化。將應急屬性信息同空間位置信息進行關聯(lián)，提高了眾源應急數(shù)據(jù)的空間化效率。當然，本文的空間化方法仍有不足之處，還有待進一步研究。