基于關聯規則的自然災害預測系統①

李漢巨, 梁浩波

(廣東電網有限責任公司東莞供電局, 東莞 523008)

基于關聯規則的自然災害預測系統①

李漢巨, 梁浩波

(廣東電網有限責任公司東莞供電局, 東莞 523008)

建立自然災害預測模型, 對自然災害進行預測和分析, 有利于提升防災減災的技術水平. 基于關聯規則和Web文本挖掘技術提出自然災害預測系統的設計方案及實現方法. 該系統利用成熟開源的爬蟲框架從權威的災害信息發布平臺中定向抓取非結構化的自然災害信息, 通過中文分詞技術進行數據清理將其整理成結構化的自然災害數據庫, 并利用改進的關聯規則算法從中挖掘出自然災害事件的關聯規則, 進而可通過實時監控關聯規則的前端信息, 實現對自然災害事件的預測. 試運行結果表明該系統能有效挖掘出自然災害信息的關聯規則, 并具有較高置信度.

Web文本; 自然災害; 災害預測; 關聯規則; 文本挖掘

1 引言

Web文本中蘊含豐富的以自然語言描述的非結構化自然災害信息[1-4]. 通過Web文本挖掘技術為災害數據源, 自動抽取并整理包含災害事件類型、時間、空間位置以及影響范圍等結構化的自然災害信息, 是對傳統結構化災害數據庫的重要補充[5,6]. 而基于Web文本自動提取和構造結構化、綜合性災害信息, 是災害信息領域研究的前沿問題[7], 目前國內外利用Web文本挖掘技術在災時與災后的應急響應與救援, 災害的早期預警和風險分析等方面開展應用研究.

從自然災害發生機理研究發現, 同一地區不同類型自然災害的發生、不同地區同一類型自然災害的發生以及不同地區不同類型自然災害的發生之間存在著聯系[8]. 一方面, 通過對區域范圍內大量積累的、文本語言記錄的歷史災害信息進行分析和挖掘, 有利于發現災害事件存在的聯系, 進而對災害發生的類型、時空分布特征進行分析, 為不同地域空間的自然災害事件發生的關聯性提供決策支持. 另一方面, 在突發災害事件下, 需要針對事件可能發生的前兆和演化過程的數據進行快速收集獲取、整理, 以實現對自然災害的預警、預測, 提升自然災害的應急處理能力.

基于上述背景, 本文設計并研發了自然災害預測系統, 該系統利用成熟開源爬蟲框架(WebMagic)從權威的災害信息發布平臺中定向抓取非結構化的自然災害信息, 并利用中文分詞技術進行數據清理將其轉換成結構化的自然災害數據庫. 接著通過關聯分析算法從中挖掘出不同區域災害事件發生的關聯規則, 最后通過實時監控某災害事件發生的前兆, 結合關聯規則,進而實現自然災害事件的預測.

2 自然災害預測系統設計

2.1 系統功能及設計

自然災害預測系統實現如下功能:

(1) 定向抓取自然災害Web文本信息, 通過數據清理, 形成結構化數據, 并存儲在MySQL數據庫.

(2) 利用改進關聯規則算法對MySQL數據庫的數據進行挖掘, 產生關聯規則庫.

(3) 利用關聯規則庫和實時抓取的自然災害Web文本信息監測關聯規則的前端信息, 實現對關聯規則的后端信息的預測.

系統設計如圖1所示.

圖1 系統設計

用戶界面設計如圖2所示.

2.2 Web技術架構

采取如圖3所示的Web技術架構.

2.3 自然災害預測技術原理

關聯規則采取形如X→Y(時間間隔)的蘊涵式,X和Y分別稱為關聯規則的前端和后端, 該關聯規則表示X發生, 經過時間間隔后, Y將發生. 比如關聯規則:

表示桂林發生暴雨15天后東莞將發生臺風. 因此假設上述關聯規則成立, 那么只要監測到桂林發生暴雨, 那么就可以預測15天后東莞發生臺風.

圖2 用戶界面設計

圖3 Web技術架構

因此自然災害預測系統實現的關鍵點是:

(1) 自然災害Web文本信息抓取, 并通過數據清洗,形成結構化的數據;

(2) 如何從結構化數據中挖掘關聯規則;

(3) 實時抓取關聯規則的前端信息.

3 自然災害預測系統實現

3.1 Web文本數據收集

3.1.1 數據收集的難點

目前國內還沒有統一的結構化自然災害數據信息庫, 因此存在災害數據標準不同、數據來源的可靠性與廣泛性難以界定、缺乏統一的收錄數據標準界定和數據管理范式(包括災害特征類、字段名稱、對應數據類型等規范的確定)等種種數據質量問題, 很難實現災害信息的應用層面共享. 此外, 由于災害信息發布來源在區域尺度、時間尺度、信息的精度、信息的時效性、信息條目的全面性等方面往往存在較大的偏差,因此如何得到統一標準的、規范的、可統計分析的結構化數據成為本系統實現的技術難點.

3.1.2 數據源選取

為確保災害數據來源的可靠性以及能夠覆蓋地震、洪澇等十余種主要災害類型, 經過調查分析研究,最終選擇下面國家權威機構的災害信息數據發布平臺作為本系統的災害歷史數據來源. 具體網站信息如下:

(1) 中國農業部種植業管理司歷史災害查詢網站(www.zzys.moa.gov.cn);

(2) 中國森林防火網(www.slfh.gov.cn);

(3) 國家減災網(www.jianzai.gov.cn);

(4) 中國地震信息網(www.csi.ac.cn).

3.1.3 數據收集方式

由于系統的數據源來自不同資料平臺, Web文本數據形式以及內容均不一樣, 因此系統使用第三方爬蟲軟件進行歷史數據收集, 根據不同的數據源定制化采集網頁中指定的文本信息. 最終完成原始數據的采集.

3.2 數據清洗

3.2.1 數據清洗目標

災害信息的原始數據均是Web文本中非結構化的自然語言, 如何從大段的Web文本中提取結構化的滿足需求的有用災害信息成為本系統實現的難點. 對文本災害信息的語義理解和抽取, 重點是解決文本語言信息的形式化問題, 建立模糊的、定性的語言與定量化的計算機模型之間的聯系, 實現從大段敘述性的Web文本中整理抽取成形如“時間+地點+災害類型”的結構化數據. 因此需要按照一定的規則從文本中抽取匹配有關災害事件的命名實體, 如災害類型、時間、地點, 確定實體之間的關系, 進而實現非結構化災害信息向結構化災害信息的轉換.

3.2.2 基于中文分詞的數據清洗方法

根據數據來源復雜、數據內容雜亂無序等特點,采用了機械匹配法(又稱為字符串匹配法)的自然語言分詞方法, 實現從文本數據中提取有效災害關鍵信息(災害類型、時間、地點).

機械分詞方法又叫基于字符串匹配的分詞方法,它是按照一定的策略將待分析的字符串與一個“充分大的”機器詞典中的詞條進行匹配, 若在詞典中找到某個字符串, 則匹配成功(識別出一個詞). 該方法是目前Web文本數據提取的主流實現方法之一, 具有易實現、可維護、可擴展等優點. 但該方法也存在難以處理未登錄詞, 無法有效克服歧義切分的缺點. 由于本系統中Web文本不涉及語義分析, 同時“時間”、“地點”、“災害類型”的匹配詞庫量較小, 因此綜合考慮最終使用機械匹配法來實現數據提取清洗.

3.2.3 數據清洗規則

目前收集的Web文本數據存在如下數據質量問題:

(1) 原始數據針對時間要素相關的描述存在多種格式, 沒有統一的規范格式. 以1990年1月1日為例,Web文本數據中存在“1990年1月1日”、“1990-01-01”、“19900101”等多種形式.

(2) 原始數據針對地點要素相關的描述存在描述地域粒度不同, 缺乏統一的唯一標示. 在Web文本中存在類似“廣東省”、“東莞市”、“珠江三角洲流域”、“華南地區”等不同級別不同粒度的地域描述說明, 無法形成統一的結構化要素.

(3) 原始數據針對災害類型要素相關的描述存在縮略語或者同義詞, 缺乏統一的定義. 例如Web文本中“雪災”災害類型可能存在被描述成“暴雪”、“大雪”等同義詞.

(4) 原始數據針對時間要素相關的描述存在模糊缺省的情況, 例如“1990年1月, ....”.

(5) 原始數據來源復雜, 數據排列無序.

(6) 數據中存在由于錄入錯誤等行為導致的違背常識錯誤無效數據, 例如(1月56日)等.

根據對以上原始數據質量問題進行歸納整理, 得出如下數據清洗規則:

(1) 將時間要素提取成格式統一的結構化要素, 為方便后續關聯分析算法使用, 時間要素格式定位為4位數字表示年份、2位數字表示月份、2位數字表示日期的格式, 即“19900101”的形式.

(2) 將地點要素提取成格式統一的結構化要素, 將地區性的地點描述、省級的地點描述轉換成相應城市的地點描述, 將地點要素統一成以行政市為單位的數據.

(3) 將災害類型要素統一定義, 最終形成地震、洪災、干旱等十類災害.

(4) 針對時間要素缺省日期的情況, 在當月時間內實現隨機日期補全, 針對時間要素缺省月份的情況則視該條數據為無效數據.

(5) 將各條原始數據提取信息后按照時間順序進行排序, 形成結構化、有序的數據集.

(6) 針對清洗后的結構化數據進行常識性容錯檢查, 發現錯誤后將該條無效數據剔除.

按照以上規則進行數據清洗, 最終獲取33717條結構化數據(表1所示), 并存入MySQL數據庫中.

表1 MySQL數據庫數據集示例

3.3 自然災害Web文本信息實時抓取

3.3.1 實現思路

針對成熟開源爬蟲框架(WebMagic)進行二次開發, 定制化實現“標題+發布時間+災害類型”的原災害Web文本信息采集. 對采集到的非結構化文本信息數據按照上節方法進行數據清洗, 檢索其文本內容, 解析生成“時間+地點+災害類型”的結構化前端信息.

3.3.2 WebMagic框架介紹

WebMagic框架介紹內容來源于網絡參考文獻《WebMagic爬蟲框架學習》, 本文摘取和修改其中重要內容方便讀者閱讀. WebMagic的框架由四大組件Downloader、PageProcessor、Scheduler和Pipeline組成,而Spider負責將它們組織起來. 這四大組件對應爬蟲生命周期中的下載、處理、管理和持久化等功能. Spider是WebMagic內部流程的核心. 四大組件都是Spider的一個屬性, 可以自由設置這些屬性, 從而實現不同的功能. Spider也是WebMagic操作的入口, 它封裝了爬蟲的創建、啟動、停止、多線程等功能. WebMagic總體架構圖如下:

(1) Downloader負責下載頁面, 供后續處理.WebMagic默認以Apache HttpClient作為下載工具.

(2) PageProcessor負責解析頁面, 抽取有用信息, 以及發現新的鏈接. WebMagic使用Jsoup作為HTML解析工具, 并基于其開發了解析XPath的工具Xsoup. Page-Processor對于每個站點每個頁面都不一樣, 是需要使用者定制的部分.

圖4 WebMagic總體架構圖

(3) Scheduler負責管理待抓取的URL和去重工作.WebMagic默認提供了JDK的內存隊列來管理URL, 并用集合來進行去重. 也支持使用Redis進行分布式管理.除非有一些特殊的分布式需求, 否則無需自己定制Scheduler.

(4) Pipeline負責抽取結果, 包括計算、持久化到文件、數據庫等. WebMagic默認提供了“輸出到控制臺”和“保存到文件”兩種結果處理方案. Pipeline定義了結果保存的方式, 如果你要保存到指定數據庫, 則需要編寫對應的Pipeline. 對于一類需求一般只需編寫一個Pipeline.

3.4 關聯規則算法介紹及改進

3.4.1 算法介紹及選擇

R.Agrawal等[9]于1993年提出了關聯規則的概念,用于挖掘顧客交易數據的頻繁模式. 關聯規則挖掘算法最常用的就是Apriori和FP-Growth算法. 嚴格地說Apriori和FP-Growth都是尋找頻繁項集的算法. 其中最經典的算法是Apriori[10], 但是其致命的缺點是需要多次掃描事務數據庫. FP-Growth算法是韓家煒等人在2000年提出的關聯分析算法[11,12], 它采取如下分治策略: 將提供頻繁項集的數據庫壓縮到一棵頻繁模式樹(FP-tree), 但仍保留項集關聯信息. 該算法和Apriori算法最主要不同點有: 第一, 不產生候選集; 第二, 只需要兩次遍歷數據庫, 大大提高了效率. 因此我們選擇FPGrowth算法挖掘關聯規則.

FP的全稱是Frequent Pattern, 在算法中使用了一種稱為頻繁模式樹(Frequent Pattern Tree)的數據結構. FP-tree是一種特殊的前綴樹, 由頻繁項頭表和項前綴樹構成. 所謂前綴樹, 是一種存儲候選項集的數據結構, 樹的分支用項名標識, 樹的節點存儲后綴項, 路徑表示項集.

FP_growth算法描述如下[13](偽代碼):

輸入: 事務數據庫D; 最小支持度閾值min_sup;

輸出: 頻繁模式的完全集;

方法:

(1) 按以下步驟構造FP樹:

(a) 掃描事務數據庫D一次. 收集頻繁項的集合F和它們的支持度計數. 對F按支持度計數降序排序, 結果為頻繁項列表L;

(b) 創建FP樹的根結點, 以“null”標記它. 對于D中每個事務Trans, 執行: 選擇Trans中的頻繁項, 并按L中的次序排序. 設Trans排序后的頻繁項列表[p|P], 其中p是第一個元素, 而P是剩余元素的列表. 調用insert_tree([p|P], T). 該過程執行情況如下. 如果T有子女N使得N.item-name=p.item-name, 則N的計數增加1; 否則,創建一個新結點N, 將其計數設置為1, 鏈接到它的父結點T, 并且通過結點鏈結構將其鏈接到具有相同itemname的結點. 如果P非空, 則遞歸地調用insert_tree(P, N).

(2) FP樹的挖掘通過調用FP_growth(FP_tree,null)實現. 該過程procedure FP_growth(Tree, α)實現如下:

(a) if Tree包含單個路徑P then;

(b) for路徑P中結點的每個組合(記作β);

(c) 產生模式β∪α, 其支持度計數support_count等于β中結點的最小支持度計數;

(d) else for Tree的頭表中每個ai;

(e) 產生一個模式β=ai∪α, 其支持度計數support_count=ai. Support_count;

(f) 構造β的條件模式基, 然后構造β的條件FP樹Treeβ;

(h) 調用FP_growth(Treeβ, β).

3.4.2 算法輔助改進

系統使用Hadoop平臺mahout庫中自帶的FPGrowth算法進行頻繁模式的挖掘. 由于算法的特性, 根據本系統涉及問題進行算法輔助改進.

問題1. 關聯分析的輸入數據類型為標稱型數據,而從數據采集結果得到的是具有時間、地點、災害類型三個屬性的數據.

輔助改進: 編寫shell腳本將數據采集結果整理成算法需要的標稱型數據, 首先把地點與災害類型合并,再將同一時間發生的災害作為一個事務進行處理.

問題2. FP-Growth算法的結果得到的是關于災害預測的頻繁項集, 而本系統需要的是帶有特定結構的關聯規則.

輔助改進: 編寫python腳本, 將頻繁項集整理輸出為本系統需要的關聯規則.

問題3. 本系統需要分析出具有時間間隔的關聯規則.

輔助改進: 首先編寫python腳本將數據采集結果整理為具有時間間隔的標稱型數據, 再利用大平臺環境進行后續的頻繁模式挖掘, 最后利用對解決問題2而編寫的python腳本整理輸出為具有時間間隔的關聯規則.

3.4.3 關聯規則庫設計及示例

關聯規則作為重要的發現知識, 被單獨存在MySQL數據庫, 與圖1中的災害信息數據庫是分開的.關聯規則庫(或關聯規則數據庫)的數據集結構設計為“前端+時間間隔(天)+后端+置信度”, 其中字段“前端”和“后端”由地點和災害類型合并而成, 比如前端“貴港_洪澇”是指關聯規則的前端信息, 表示貴港發生洪澇災害. 置信度是指前端發生的條件下, 后端發生的概率.

對表1所示的數據集用改進后的FP-Growth算法進行挖掘, 并按照閾值(置信度為60%)對關聯規則進行篩選, 得到137620條有效關聯規則(見表2).

3.5 自然災害預測實現

預測任務由系統的預測程序負責, 操作接口如圖5所示.

表2 關聯規則庫數據集示例

圖5 自然災害預測

對預測效果的評估存在一些困難, 因為預測準確性受到很多因素影響, 一是災害信息報道不及時, 導致抓取實時災害信息延期, 影響最后預測結果; 二是預測結果的驗證存在困難, 如預測結果確實發生了, 但在指定的網絡上不存在相關的報道(或許在別的網站上有相關報道), 導致無法抓取到真實信息. 目前在系統上設計自動驗證程序存在技術難點, 因此預測效果的評估靠人工核實.

4 結論

自然災害嚴重威脅著人民生命和國家財產的安全,隨著國家經濟發展和人口增長, 自然災害所造成的巨大損失正在日益加重. 本文基于關聯規則和Web文本挖掘技術提出了一種自然災害預測系統設計方案及設計方法, 該系統可定向抓取自然災害的Web文本信息,通過中文分詞技術將非結構化的Web文本信息轉化為結構化數據, 并利用改進的關聯規則算法從結構化數據中挖掘出自然災害關聯規則庫, 最后通過實時抓取自然災害Web文本信息監測關聯規則的前端信息, 即某特定自然災害事件發生的前兆, 結合關聯規則庫以實現該自然災害事件的預測. 試運行結果表明該系統能挖掘出有效的關聯規則, 有效提升自然災害的防災減災能力. 該系統還存在一些不足, 比如缺少有效的預測效果評估程序, 這也是本研究后期努力改進的方向.

1Brunt J. Using the world wide web to advance data management in LTER. LTER Network News, 1998, 11(1):18–19.

2周寧. 信息資源數據庫. 2版. 武漢: 武漢大學出版社, 2006.233–235.

3韋方強, 崔鵬, 胡凱衡, 等. 泥石流災害信息共享的方法與實現. 災害學, 2002, 17(3): 60–64.

4林孝松, 趙純勇. GIS在重慶市地質災害信息管理系統中的應用. 災害學, 2003, 18(1): 71–76.

5Dunbar PK. Increasing public awareness of natural hazards via the Internet. Natural Hazards, 2007, 42(3): 529–536. [doi:10.1007/s11069-006-9072-3]

6Peduzzi P, Dao H, Herold C. Mapping disastrous natural hazards using global datasets. Natural Hazards, 2005, 35(2):265–289. [doi: 10.1007/s11069-004-5703-8]

7李衛江, 溫家洪. 基于Web文本的災害信息挖掘研究進展.災害學, 2010, 25(2): 119–123, 128.

8任振球. 關于加強特大自然災害預測新途徑新方法研究的討論. 地球信息科學, 2000, 2(2): 76–77.

9Agrawal R, Imieliński T, Swami A. Mining association rules between sets of items in large databases. Proc. 1993 ACM SIGMOD International Conference on Management of Data.Washington DC, USA. 1993. 207–216.

10Agrawal R, Srikant R. Fast algorithms for mining association rules. Proc. 20th International Conference on Very Large Data Bases. Santiago, Chile. 1994. 487–499.

11Han JW, Pei J, Yin YW. Mining frequent patterns without candidate generation. Proc. 2000 ACM SIGMOD International Conference on Management of Data. Dallas, Texas,USA. 2000. 1–12.

12楊勇, 王偉. 一種基于MapReduce的并行FP-growth算法. 重慶郵電大學學報(自然科學版), 2013, 25(5): 651–657, 670.[doi: 10.3979/j.issn.1673-825X.2013.05.016]

13Han JW, Kamber M, Pei J, 等. 數據挖掘: 概念與技術.范明,孟小峰, 譯. 北京: 機械工業出版社, 2012.

Natural Disaster Forecasting System Based Association Rules

LI Han-Ju, LIANG Hao-Bo
(Guangdong Power Grid Co. Ltd., Dongguan Power Supply Bureau, Dongguan 523008, China)

The establishment of natural disaster prediction model to predict and analyze the occurrence of natural disasters is conducive to enhance the technical level of disaster prevention and mitigation. We present a design and implementation of natural disaster forecasting system based on association rules and the Web text mining technology. The system uses a mature open source crawler framework to capture the unstructured natural disaster information from the authoritative disaster information release platforms. By using the Chinese word segmentation technique the data are cleaned up and organized into a structured natural disaster database, and mining association rules of natural disaster events are worked out from improved association rule algorithm. And then by monitoring the front-end information of association rules in real time, the prediction of natural disasters can be achieved. Experimental results show that the system can effectively mine the association rules of natural disaster information with high confidence.

Web text; natural disaster; disaster prediction; association rules; text mining

李漢巨,梁浩波.基于關聯規則的自然災害預測系統.計算機系統應用,2017,26(7):50–55. http://www.c-s-a.org.cn/1003-3254/5877.html

廣東電網有限責任公司職工創新項目(GDZC-031920160256)

2016-11-18; 收到修改稿時間: 2017-01-04