非指定時間約束的社會安全事件關聯規則挖掘

郭 文 月,劉 海 硯,余 岸 竹,馬 紹 龍,馮 培 義

(1.信息工程大學地理空間信息學院，河南 鄭州 450001;2.地理信息工程國家重點實驗室，陜西 西安 710000;3.陸軍指揮學院，江蘇 南京 210045)

非指定時間約束的社會安全事件關聯規則挖掘

郭 文 月1,2,劉 海 硯1,余 岸 竹1,2,馬 紹 龍3,馮 培 義1

(1.信息工程大學地理空間信息學院，河南 鄭州 450001;2.地理信息工程國家重點實驗室，陜西 西安 710000;3.陸軍指揮學院，江蘇 南京 210045)

關聯規則挖掘是社會安全事件分析的重要方法之一，用于發現事件屬性項及事件間的潛在關聯。該文分析了社會安全事件的時空特性，利用時空關聯規則挖掘方法分析事件屬性項間的時空關聯。為解決現有時空關聯規則挖掘方法需要事先指定挖掘時間區間的問題，提出一種非指定時間約束的時空關聯規則挖掘方法，根據事件時間屬性值和時間劃分粒度為事件空間和專題屬性項增加時間標識，用時間標識代替時間屬性值，得到全時間域內帶有時間指向性的關聯規則挖掘結果。以全球恐怖主義事件數據庫為數據源，對該方法進行驗證，結果表明其具有一定的可靠性與實用性，能夠為社會安全事件的分析與預測、快速響應與防范提供決策依據。

社會安全事件；關聯規則挖掘；時空關聯規則；FP-Growth算法；GTD

0 引言

突發公共事件分為自然災害、事故災害、公共衛生事件和社會安全事件，其中社會安全事件主要包括恐怖襲擊事件、經濟安全事件和涉外突發事件等[1]。近年來，各種突發事件頻繁發生，突發事件的應對已成為考驗政府執政能力的一個重要方面[2]。在已有數據庫支持下，綜合利用數據挖掘、統計分析與知識發現等技術快速、高效地提取和挖掘出有價值的信息，為事件的分析與預測、快速響應與防范提供可靠參考依據，是提高社會安全事件應對能力的重要方法之一。

社會安全事件是帶有時間屬性、空間位置屬性和專題屬性的地理現象，事件的發生與發展通常具有潛在時空關聯，時空關聯規則挖掘是社會安全事件關聯分析的有效手段。傳統的關聯規則挖掘算法有Apriori[3]算法和PF-Growth[4]算法等，主要針對“購物籃”類型的交易數據庫，為解決傳統關聯規則挖掘算法無法表現時間與空間關聯的問題，各領域研究人員通過增加空間約束[5]和時間約束的方法對傳統算法進行拓展。Peuquet等[6]提出了一種基于事件的時空數據模型(ESTDM)，用于地理數據的時間分析；Verhein等[7]針對交通高峰區域屬性約減問題，提出一種時空關聯規則算法(Spatio-Temporal Association Rules,STAR)；沙宗堯[8]提出時序空間關聯規則挖掘方法，用于土地類型變化的時空關聯分析中；岳慧穎[9]提出時空數據挖掘(Shi Kong Data Mining,SKDM)算法，考慮空間約束和時間因素，并將兩者的相關有效時間進行推廣和歸并，得到相應的帶時空約束的關聯規則；李光強等[10]利用事件影響域挖掘時空關聯規則并劃分時空域，利用時空關系謂詞建立事件與影響域中目標間的時空關系；夏英[11]、張俊[12]等對空間語義和時間語義進行了擴充，提出了同時考慮時空約束的時空關聯規則挖掘(Spatio-Temporal Apriori，STApriori)算法，并將其應用于智能交通領域。

如何在已有關聯規則挖掘算法基礎上合理添加時間約束和空間約束，尤其是時間約束，是當前時空關聯規則挖掘研究所面臨的主要問題之一。已有的時空關聯規則挖掘方法需要事先指定時間約束，在指定區間內運行關聯規則挖掘算法，進而得到指定時間區間內的關聯規則結果(圖1)。然而當用戶對數據不了解或無法明確指出能夠挖掘出有效關聯規則的時間區間時，利用這種基于指定時間約束的時空關聯規則挖掘方法可能無法得到有效關聯規則，算法的實用性大大降低。

圖1 指定時間約束的關聯規則挖掘方法Fig.1 Association rule mining method with specified time constraint

針對上述問題，提出一種利用時間標識代替時間屬性值的方法，改進FP-Growth算法，設計并實現了非指定時間約束的時空關聯規則挖掘方法，以全球恐怖主義事件數據庫為數據源進行驗證，為社會安全事件預警和快速響應提供決策依據。

1 社會安全事件時空關聯規則挖掘

1.1 非指定時間約束的關聯規則挖掘方法

為解決已有的時空關聯規則挖掘算法在用戶無法指定有效運行時間區間時可能得不到有效關聯規則的問題，提出一種為事件屬性項增加時間標識的方法，在運行關聯規則挖掘算法前，為事件空間和專題屬性值賦予時間標識，形成帶有時間標識的事件數據集，之后在整個數據集內運行關聯規則挖掘算法(圖2)。這種方式保證了得到的結果仍具有明確的時間指向性，且無須用戶指定時間區間而只需設定時間細化程度即可。

圖2 帶時間標識的關聯規則挖掘方法Fig.2 Association rule mining method with temporal stamps

時間標識是事件時間屬性值在時間軸上所屬的非固定時間區間。在不同的時間細化程度(時間粒度)標準下，時間區劃界限值不同，例如：若時間粒度為“月”，則時間屬性值為“2010-1-1”和“2010-1-11”的事件所對應的時間標識均為“1月”； 若時間細化程度為“日”，則上述事件所對應的時間標識分別為“1日”和“11日”。根據事件時間屬性值及時間粒度標準，為事件空間屬性項和專題屬性項賦時間標識，使之時間特性得到直接體現。這種方法通過增加時間標識解決了需要用戶事先指定挖掘區間的問題，只需確定時間約束的粒度，如“日”、“周”、“月”、“季度”等時間單位，而無需確定具體的時間區間如“1-3月”、“2010-2013年”等，實現了時間粒度可變的全時間范圍關聯規則挖掘，能夠有效避免因時間約束不當導致的挖掘失敗。

1.2 帶時間標識的事件時空關聯規則

事件時空關聯規則是指從給定的事件數據集中發現頻繁出現的屬性項模式知識。設I={t,i1,i2,…,im}是事件記錄，t記錄事件發生時間，i1,i2,…,im記錄事件的空間特征和專題特征；事件數據集D={I1,I2,…,Im}，其中Im是I的非空子集，Im∈I，Im表示某一事件，具有唯一標識編碼。帶時間標識的事件屬性項時空關聯規則可表示為X[Ti]?Y[Tj]，其中X，Y∈I且X∩Y=?，Ti、Tj分別是X和Y的時間標識，由事件時間屬性值t和時間粒度大小確定，X[Ti]和Y[Tj]分別為關聯規則X[Ti]?Y[Tj]的先導和后繼。帶時間標識的事件時空關聯規則相關定義如下：

定義1 支持度是數據集D中X[Ti]和Y[Tj]同時發生的次數與所有事件總數的比值，表達為：

S(X[Ti]?Y[Tj])=P(X[Ti]Y[Tj])

定義2 置信度是數據集D中X[Ti]和Y[Tj]同時發生的次數與X[Ti]發生次數的比值，表達為：

設最小支持度閾值為minS，最小置信度閾值為minC，當滿足大于最小支持度和置信度閾值的條件時，即S≥minS且C≥minC時，帶有時間標識的關聯規則成立，可表示為：

X[Ti]?Y[Tj](S,C)

一個數據項的集合稱為項集，滿足最小支持度閾值和最小置信度的項集稱為頻繁項集，關聯規則挖掘實際上是依據特定算法找出數據集中的頻繁項集，最終通過頻繁項集形成關聯規則的過程。

1.3 帶時間標識的FP-Growth算法

改進傳統FP-Growth算法,形成帶時間標識的FP-Growth算法，對帶有時間標識的事件數據集進行關聯規則挖掘。帶時間標識的FP-Growth算法在構建頻繁模式樹時，每個節點除了存儲屬性項值、子節點、父節點及出現次數等信息外，還需存儲事件的時間標識，使得相同屬性值因其帶有不同時間標識而存在于不同節點中。挖掘頻繁項集的具體過程描述如下：輸入數據：事件數據集D，時間粒度TL，最小支持度閾值minS；輸出數據：頻繁模式的完全集。

算法基本過程如下：1)掃描事件數據集D={I1,I2,…,Im}，根據時間粒度TL和事件時間屬性值，為事件空間屬性項和專題屬性值賦予該記錄對應的時間后綴，形成帶時間標識的事件數據集DT={I1[t1],I2[t2],…,Ik[tk],…,Im[tm]}，其中，Ik[tk]={i1[tk],i2[tk],…,in[tk]}；2)掃描帶時間標識的事件數據集DT一次，除去支持度小于最小支持度閾值的項，獲得頻繁項和各頻繁項支持度F∶S，對F∶S中每條記錄中的項按支持度大小降序排序，結果為頻繁項表L；3)創建FP-tree根節點，以“NULL”標記,對每個事件Ik[tk]中的頻繁項按照L中的次序重新排序，對帶時間標識的事件數據庫DT遞歸調用InsertTree()函數，構建頻繁模式樹；4)FP-tree的挖掘通過調用procedure FP_Growth(Tree,a)實現，構建節點的條件模式基和條件模式樹，最終獲得頻繁模式完全集。

2 實驗與結果分析

2.1 實驗過程

以美國全球恐怖主義事件數據庫(GlobalTerrorismDatabase,GTD)[13]為數據源，首先對數據進行清洗和整合，刪除了缺乏關鍵屬性項的事件記錄，規范了相同屬性值的不同表述形式；篩選并確定事件集屬性項，構建合理的、適用于關聯規則挖掘的社會安全事件數據表結構，得到用于屬性項時空關聯規則挖掘的事件數據集；為提高解算效率，對屬性值編碼，構建國家、省份(州)、事件實施組織、事件類型、目標類型等多個字典表，用屬性值編碼代替屬性值進行運算，部分字典表如表1、表2所示。

表1 事件類型字典表Table 1 Dictionary table of event types

實驗針對2012年發生在伊拉克的1 438起有記錄的社會安全事件。以該地區的政治經濟中心巴格達為地理參考點，用Close to、Far from、In作為空間謂詞表示事件發生地與巴格達在空間距離上的關系，用Northwest、Northeast等空間謂詞表示事件發生地與巴格達在空間方位上的相對關系。以事件類型、事件目標類型、事件實施組織為事務項，根據事件的時間信息，以“月”作為時間粒度，為各事務項添加時間標識，構建事件事務表(表3);再采用帶有時間標識的FP-Growth關聯規則挖掘算法挖掘事件屬性項之間的時空關聯關系，并對結果進行解譯。根據數據特征，實驗中設定最小支持度閾值=15.6%，最小置信度閾值=50%。

表3 事件事務Table 3 Event services

2.2 實驗結果與分析

采用帶時間標識的FP-Growth算法，指定以“月”作為時間粒度，以“事件類型”、“事件目標類型”、“事件實施組織”及時空屬性作為挖掘對象，當最小支持度閾值=15.6%、最小置信度閾值=50%時，得到頻繁項完全集94項。由于數據挖掘的目的在于發現潛在的有意義的知識[14]，因而需對挖掘結果進行邏輯判斷和語義判斷，篩選符合邏輯并且有意義的結果，最終整理得到帶有月份標識的有效關聯規則18條，其中1月份的關聯規則如表4所示。

表4 關聯規則(1月份)Table 4 Association rules (January)

對照制定的字典表，對得到的關聯規則進行解譯，以R1、R2、R3為例分析如下：R1表示在1月份巴格達發生爆炸襲擊的可能性為20.8%，如果巴格達發生社會安全事件，則有90.9%的概率為爆炸襲擊事件；R2表示在1月份距巴格達較遠地區發生爆炸襲擊事件的可能性為17.7%，如果在該地區發生社會安全事件，則事件類型為爆炸襲擊的可能性為72.3%；R3表示在1月份巴格達周邊地區發生爆炸襲擊社會安全事件的可能性為41.1%，如果在該區域發生社會安全事件，則事件類型為爆炸襲擊的可能性為78.2%。綜合考慮R1、R2、R3可得分析結果：1月份，爆炸襲擊事件是伊拉克面臨的主要安全威脅之一，且多發生在巴格達內部及鄰近周邊地區，因而在該區域應重點加強對爆炸襲擊事件的防范措施和應急預案的制定。

為驗證實驗得到關聯規則的有效性，利用傳統統計分析的方法對2012年1月發生在伊拉克的社會安全事件的類型及其空間分布特征進行分析，統計結果(圖3)證明，爆炸襲擊事件對巴格達及其附近區域威脅較大，證明利用本文方法得到的結果具有一定的可靠性。

圖3 不同類型事件在各區域范圍內發生頻次Fig.3 Statistical of different types of events occur in different region

傳統統計分析側重展現事件各屬性的數值與比重差異，適用于對事件時空熱點及主要威脅類型等既有特征進行分析，但不能直接揭示屬性項間的潛在關聯，進而實現更深層次的規則發現。同時，根據分析類型的不同，傳統統計分析需要多次計算統計指標的值及比重，在多屬性項關聯分析中運算量較大、效率不高。本文提出的非指定時間約束關聯規則挖掘方法，能夠在僅遍歷一次事件數據集的條件下揭示事件屬性項之間的時空關聯關系，同時有效解決已有時空關聯規則挖掘算法中用戶無法事先指定時間約束的問題，得到全時間域內帶有時間特征的時空關聯規則結果。非指定時間約束的關聯規則挖掘方法與現有時空關聯規則挖掘方法及傳統統計分析方法在驅動模式、算法特性、結果特征及適用性等方面的對比如表5所示。

表5 不同事件時空挖掘與分析方法的特性對比Table 5 Feature comparison of different methods of spatio-temporal data mining and analysis

3 結論

本文分析了面向社會安全事件的時空關聯規則挖掘基本原理，為解決已有方法存在的無法事先指定有效時間約束問題，提出了為事件屬性項增加時間標識、用時間標識代替時間屬性值的方法，在傳統關聯規則挖掘算法基礎上，設計了非指定時間約束的FP-Growth算法，并利用全球恐怖主義事件數據庫數據得到了有效、可靠的結果。以下問題需深入研究：1) 帶有時間標識的關聯規則算法通過結構優化可進一步提高運行效率；2) 提高數據預處理效率，融合多源事件數據，構建面向我國的大型事件數據庫，將進一步增強本文方法的應用廣度與深度；3) 本文提出的關聯規則挖掘方法只能對時間片內事件屬性項及相互之間的關聯關系進行分析，如何挖掘時間片之間的時空關聯關系，以便對社會安全事件進行更加完備的分析與預測，是下一步的工作重點。

[1] 國務院.國家突發公共事件總體應急預案[Z].中國防汛抗旱,2006.

[2] 劉曉東,朱翊,孫立堅,等.面向突發事件的地理信息服務研究[J].測繪科學,2010,35(6):219-221.

[3] AGRAWAL R,SRIKANT R.Fast algorithms for mining association rules[A].Proc.20th int.conf.Very Large Data Bases,VLDB.1994,1215:487-499.

[4] HAN J,PEI J,YIN Y,et al.Mining frequent patterns without candidate generation:A frequent-pattern tree approach[J].Data Mining and Knowledge Discovery,2004,8(1):53-87.

[5] 陳虎,李麗,李宏偉,等.本體輔助的約束空間關聯規則挖掘方法[J].測繪科學技術學報,2011,28(6):458-462.

[6] PEUQUET D J,DUAN N.An event-based spatiotemporal data model (ESTDM) for temporal analysis of geographical data[J].International Journal of Geographical Information Systems,1995,9(1):7-24.

[7] VERHEIN F,CHAWLA S.Mining spatio-temporal patterns in object mobility databases[J].Data Mining and Knowledge Discovery,2008,16(1):5-38.

[8] 沙宗堯.時序空間關聯規則挖掘及其應用研究[J].地理空間信息,2008,6(5):18-21.

[9] 岳慧穎.含有時空約束的關聯規則挖掘方法研究[D].哈爾濱:哈爾濱工程大學,2004.

[10] LI G Q,DENG M,ZHANG W L.Events-coverage based spatio-temporal association rules mining method[J].Journal of Remote Sensing,2010,14(3):468-481.

[11] 夏英,張俊,王國胤.時空關聯規則挖掘算法及其在 ITS 中的應用[J].計算機科學,2011,38(9):173-176.

[12] 張俊.時空關聯性分析方法研究與應用[D].重慶:重慶郵電大學,2011.

[13] Global Terrorism Database[DB/OL].http://www.start.umd.edu/gtd/.2015-10-31.

[14] WATTENBERG M.Baby names,visualization,and social data analysis[A].Information Visualization,2005[C].IEEE Symposium on.IEEE,2005.1-7.

Association Rules Mining on Social Security Events with Non-specified Time Constraints

GUO Wen-yue1,2,LIU Hai-yan1,YU An-zhu1,2,MA Shao-long3,FENG Pei-yi1

(1.InstituteofSurveyingandMapping,Zhengzhou450001;2.StateKeyLaboratoryofGeo-informationEngineering,Xi′an710000;3.ArmyCommandCollege,Nanjing210045,China)

Association rules mining is one of the most important methods in analyzing social security events for discovering potential relevance between events and event′s properties.The spatial and temporal characteristics of social security events have been analyzed,and spatio-temporal association rule mining has been used to analyze the spatio-temporal association relationships between event′s properties.In order to solve the problem of existing spatio-temporal association rules mining algorithms that specified time interval has to be pre-required,a spatio-temporal association rules mining method without specified time constraint has been put forward.Event′s temporal property values are replaced by temporal stamps which are made according to the event′s temporal property and time partitioning granularity.Temporal stamps are marked to the spatial and thematic attribute items,so that the event spatial and thematic attribute items with temporal stamps could reflect its intrinsic temporal characteristic.Through this method,mining algorithms could run in full time domain and time-directional association rules between event′s location,the performing organization,event type and target type supported by probability could be obtained.Global Terrorism Database has been used to validate the usefulness of this method,the result proves that the method is reliable and practical,and could provide a reliable basis for decision making on analysis and prediction,rapid response and prevention of social security events.

social security events;association rule mining;spatio-temporal association rule;FP-Growth algorithm;GTD

2015-12-15；

2016-01-21

國家自然科學基金項目(41501446)；地理信息工程國家重點實驗室開放基金課題(SKLGIE2015-M-4-3、SKLGIE2015-M-3-1)

郭文月(1990-)，女，博士研究生，主要從事數字地圖制圖和時空數據分析方面研究。E-mail:GuoWYer@163.com

10.3969/j.issn.1672-0504.2016.03.003

P208

A

1672-0504(2016)03-0014-05