郭 文 月,劉 海 硯,余 岸 竹,馬 紹 龍,馮 培 義
(1.信息工程大學(xué)地理空間信息學(xué)院,河南 鄭州 450001;2.地理信息工程國家重點實驗室,陜西 西安 710000;3.陸軍指揮學(xué)院,江蘇 南京 210045)
非指定時間約束的社會安全事件關(guān)聯(lián)規(guī)則挖掘
郭 文 月1,2,劉 海 硯1,余 岸 竹1,2,馬 紹 龍3,馮 培 義1
(1.信息工程大學(xué)地理空間信息學(xué)院,河南 鄭州 450001;2.地理信息工程國家重點實驗室,陜西 西安 710000;3.陸軍指揮學(xué)院,江蘇 南京 210045)
關(guān)聯(lián)規(guī)則挖掘是社會安全事件分析的重要方法之一,用于發(fā)現(xiàn)事件屬性項及事件間的潛在關(guān)聯(lián)。該文分析了社會安全事件的時空特性,利用時空關(guān)聯(lián)規(guī)則挖掘方法分析事件屬性項間的時空關(guān)聯(lián)。為解決現(xiàn)有時空關(guān)聯(lián)規(guī)則挖掘方法需要事先指定挖掘時間區(qū)間的問題,提出一種非指定時間約束的時空關(guān)聯(lián)規(guī)則挖掘方法,根據(jù)事件時間屬性值和時間劃分粒度為事件空間和專題屬性項增加時間標(biāo)識,用時間標(biāo)識代替時間屬性值,得到全時間域內(nèi)帶有時間指向性的關(guān)聯(lián)規(guī)則挖掘結(jié)果。以全球恐怖主義事件數(shù)據(jù)庫為數(shù)據(jù)源,對該方法進行驗證,結(jié)果表明其具有一定的可靠性與實用性,能夠為社會安全事件的分析與預(yù)測、快速響應(yīng)與防范提供決策依據(jù)。
社會安全事件;關(guān)聯(lián)規(guī)則挖掘;時空關(guān)聯(lián)規(guī)則;FP-Growth算法;GTD
突發(fā)公共事件分為自然災(zāi)害、事故災(zāi)害、公共衛(wèi)生事件和社會安全事件,其中社會安全事件主要包括恐怖襲擊事件、經(jīng)濟安全事件和涉外突發(fā)事件等[1]。近年來,各種突發(fā)事件頻繁發(fā)生,突發(fā)事件的應(yīng)對已成為考驗政府執(zhí)政能力的一個重要方面[2]。在已有數(shù)據(jù)庫支持下,綜合利用數(shù)據(jù)挖掘、統(tǒng)計分析與知識發(fā)現(xiàn)等技術(shù)快速、高效地提取和挖掘出有價值的信息,為事件的分析與預(yù)測、快速響應(yīng)與防范提供可靠參考依據(jù),是提高社會安全事件應(yīng)對能力的重要方法之一。
社會安全事件是帶有時間屬性、空間位置屬性和專題屬性的地理現(xiàn)象,事件的發(fā)生與發(fā)展通常具有潛在時空關(guān)聯(lián),時空關(guān)聯(lián)規(guī)則挖掘是社會安全事件關(guān)聯(lián)分析的有效手段。傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法有Apriori[3]算法和PF-Growth[4]算法等,主要針對“購物籃”類型的交易數(shù)據(jù)庫,為解決傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法無法表現(xiàn)時間與空間關(guān)聯(lián)的問題,各領(lǐng)域研究人員通過增加空間約束[5]和時間約束的方法對傳統(tǒng)算法進行拓展。Peuquet等[6]提出了一種基于事件的時空數(shù)據(jù)模型(ESTDM),用于地理數(shù)據(jù)的時間分析;Verhein等[7]針對交通高峰區(qū)域?qū)傩约s減問題,提出一種時空關(guān)聯(lián)規(guī)則算法(Spatio-Temporal Association Rules,STAR);沙宗堯[8]提出時序空間關(guān)聯(lián)規(guī)則挖掘方法,用于土地類型變化的時空關(guān)聯(lián)分析中;岳慧穎[9]提出時空數(shù)據(jù)挖掘(Shi Kong Data Mining,SKDM)算法,考慮空間約束和時間因素,并將兩者的相關(guān)有效時間進行推廣和歸并,得到相應(yīng)的帶時空約束的關(guān)聯(lián)規(guī)則;李光強等[10]利用事件影響域挖掘時空關(guān)聯(lián)規(guī)則并劃分時空域,利用時空關(guān)系謂詞建立事件與影響域中目標(biāo)間的時空關(guān)系;夏英[11]、張俊[12]等對空間語義和時間語義進行了擴充,提出了同時考慮時空約束的時空關(guān)聯(lián)規(guī)則挖掘(Spatio-Temporal Apriori,STApriori)算法,并將其應(yīng)用于智能交通領(lǐng)域。
如何在已有關(guān)聯(lián)規(guī)則挖掘算法基礎(chǔ)上合理添加時間約束和空間約束,尤其是時間約束,是當(dāng)前時空關(guān)聯(lián)規(guī)則挖掘研究所面臨的主要問題之一。已有的時空關(guān)聯(lián)規(guī)則挖掘方法需要事先指定時間約束,在指定區(qū)間內(nèi)運行關(guān)聯(lián)規(guī)則挖掘算法,進而得到指定時間區(qū)間內(nèi)的關(guān)聯(lián)規(guī)則結(jié)果(圖1)。然而當(dāng)用戶對數(shù)據(jù)不了解或無法明確指出能夠挖掘出有效關(guān)聯(lián)規(guī)則的時間區(qū)間時,利用這種基于指定時間約束的時空關(guān)聯(lián)規(guī)則挖掘方法可能無法得到有效關(guān)聯(lián)規(guī)則,算法的實用性大大降低。
圖1 指定時間約束的關(guān)聯(lián)規(guī)則挖掘方法Fig.1 Association rule mining method with specified time constraint
針對上述問題,提出一種利用時間標(biāo)識代替時間屬性值的方法,改進FP-Growth算法,設(shè)計并實現(xiàn)了非指定時間約束的時空關(guān)聯(lián)規(guī)則挖掘方法,以全球恐怖主義事件數(shù)據(jù)庫為數(shù)據(jù)源進行驗證,為社會安全事件預(yù)警和快速響應(yīng)提供決策依據(jù)。
1.1 非指定時間約束的關(guān)聯(lián)規(guī)則挖掘方法
為解決已有的時空關(guān)聯(lián)規(guī)則挖掘算法在用戶無法指定有效運行時間區(qū)間時可能得不到有效關(guān)聯(lián)規(guī)則的問題,提出一種為事件屬性項增加時間標(biāo)識的方法,在運行關(guān)聯(lián)規(guī)則挖掘算法前,為事件空間和專題屬性值賦予時間標(biāo)識,形成帶有時間標(biāo)識的事件數(shù)據(jù)集,之后在整個數(shù)據(jù)集內(nèi)運行關(guān)聯(lián)規(guī)則挖掘算法(圖2)。這種方式保證了得到的結(jié)果仍具有明確的時間指向性,且無須用戶指定時間區(qū)間而只需設(shè)定時間細化程度即可。
圖2 帶時間標(biāo)識的關(guān)聯(lián)規(guī)則挖掘方法Fig.2 Association rule mining method with temporal stamps
時間標(biāo)識是事件時間屬性值在時間軸上所屬的非固定時間區(qū)間。在不同的時間細化程度(時間粒度)標(biāo)準(zhǔn)下,時間區(qū)劃界限值不同,例如:若時間粒度為“月”,則時間屬性值為“2010-1-1”和“2010-1-11”的事件所對應(yīng)的時間標(biāo)識均為“1月”; 若時間細化程度為“日”,則上述事件所對應(yīng)的時間標(biāo)識分別為“1日”和“11日”。根據(jù)事件時間屬性值及時間粒度標(biāo)準(zhǔn),為事件空間屬性項和專題屬性項賦時間標(biāo)識,使之時間特性得到直接體現(xiàn)。這種方法通過增加時間標(biāo)識解決了需要用戶事先指定挖掘區(qū)間的問題,只需確定時間約束的粒度,如“日”、“周”、“月”、“季度”等時間單位,而無需確定具體的時間區(qū)間如“1-3月”、“2010-2013年”等,實現(xiàn)了時間粒度可變的全時間范圍關(guān)聯(lián)規(guī)則挖掘,能夠有效避免因時間約束不當(dāng)導(dǎo)致的挖掘失敗。
1.2 帶時間標(biāo)識的事件時空關(guān)聯(lián)規(guī)則
事件時空關(guān)聯(lián)規(guī)則是指從給定的事件數(shù)據(jù)集中發(fā)現(xiàn)頻繁出現(xiàn)的屬性項模式知識。設(shè)I={t,i1,i2,…,im}是事件記錄,t記錄事件發(fā)生時間,i1,i2,…,im記錄事件的空間特征和專題特征;事件數(shù)據(jù)集D={I1,I2,…,Im},其中Im是I的非空子集,Im∈I,Im表示某一事件,具有唯一標(biāo)識編碼。帶時間標(biāo)識的事件屬性項時空關(guān)聯(lián)規(guī)則可表示為X[Ti]?Y[Tj],其中X,Y∈I且X∩Y=?,Ti、Tj分別是X和Y的時間標(biāo)識,由事件時間屬性值t和時間粒度大小確定,X[Ti]和Y[Tj]分別為關(guān)聯(lián)規(guī)則X[Ti]?Y[Tj]的先導(dǎo)和后繼。帶時間標(biāo)識的事件時空關(guān)聯(lián)規(guī)則相關(guān)定義如下:
定義1 支持度是數(shù)據(jù)集D中X[Ti]和Y[Tj]同時發(fā)生的次數(shù)與所有事件總數(shù)的比值,表達為:
S(X[Ti]?Y[Tj])=P(X[Ti]Y[Tj])
定義2 置信度是數(shù)據(jù)集D中X[Ti]和Y[Tj]同時發(fā)生的次數(shù)與X[Ti]發(fā)生次數(shù)的比值,表達為:
設(shè)最小支持度閾值為minS,最小置信度閾值為minC,當(dāng)滿足大于最小支持度和置信度閾值的條件時,即S≥minS且C≥minC時,帶有時間標(biāo)識的關(guān)聯(lián)規(guī)則成立,可表示為:
X[Ti]?Y[Tj](S,C)
一個數(shù)據(jù)項的集合稱為項集,滿足最小支持度閾值和最小置信度的項集稱為頻繁項集,關(guān)聯(lián)規(guī)則挖掘?qū)嶋H上是依據(jù)特定算法找出數(shù)據(jù)集中的頻繁項集,最終通過頻繁項集形成關(guān)聯(lián)規(guī)則的過程。
1.3 帶時間標(biāo)識的FP-Growth算法
改進傳統(tǒng)FP-Growth算法,形成帶時間標(biāo)識的FP-Growth算法,對帶有時間標(biāo)識的事件數(shù)據(jù)集進行關(guān)聯(lián)規(guī)則挖掘。帶時間標(biāo)識的FP-Growth算法在構(gòu)建頻繁模式樹時,每個節(jié)點除了存儲屬性項值、子節(jié)點、父節(jié)點及出現(xiàn)次數(shù)等信息外,還需存儲事件的時間標(biāo)識,使得相同屬性值因其帶有不同時間標(biāo)識而存在于不同節(jié)點中。挖掘頻繁項集的具體過程描述如下:輸入數(shù)據(jù):事件數(shù)據(jù)集D,時間粒度TL,最小支持度閾值minS;輸出數(shù)據(jù):頻繁模式的完全集。
算法基本過程如下:1)掃描事件數(shù)據(jù)集D={I1,I2,…,Im},根據(jù)時間粒度TL和事件時間屬性值,為事件空間屬性項和專題屬性值賦予該記錄對應(yīng)的時間后綴,形成帶時間標(biāo)識的事件數(shù)據(jù)集DT={I1[t1],I2[t2],…,Ik[tk],…,Im[tm]},其中,Ik[tk]={i1[tk],i2[tk],…,in[tk]};2)掃描帶時間標(biāo)識的事件數(shù)據(jù)集DT一次,除去支持度小于最小支持度閾值的項,獲得頻繁項和各頻繁項支持度F∶S,對F∶S中每條記錄中的項按支持度大小降序排序,結(jié)果為頻繁項表L;3)創(chuàng)建FP-tree根節(jié)點,以“NULL”標(biāo)記,對每個事件Ik[tk]中的頻繁項按照L中的次序重新排序,對帶時間標(biāo)識的事件數(shù)據(jù)庫DT遞歸調(diào)用InsertTree()函數(shù),構(gòu)建頻繁模式樹;4)FP-tree的挖掘通過調(diào)用procedure FP_Growth(Tree,a)實現(xiàn),構(gòu)建節(jié)點的條件模式基和條件模式樹,最終獲得頻繁模式完全集。
2.1 實驗過程
以美國全球恐怖主義事件數(shù)據(jù)庫(GlobalTerrorismDatabase,GTD)[13]為數(shù)據(jù)源,首先對數(shù)據(jù)進行清洗和整合,刪除了缺乏關(guān)鍵屬性項的事件記錄,規(guī)范了相同屬性值的不同表述形式;篩選并確定事件集屬性項,構(gòu)建合理的、適用于關(guān)聯(lián)規(guī)則挖掘的社會安全事件數(shù)據(jù)表結(jié)構(gòu),得到用于屬性項時空關(guān)聯(lián)規(guī)則挖掘的事件數(shù)據(jù)集;為提高解算效率,對屬性值編碼,構(gòu)建國家、省份(州)、事件實施組織、事件類型、目標(biāo)類型等多個字典表,用屬性值編碼代替屬性值進行運算,部分字典表如表1、表2所示。
表1 事件類型字典表Table 1 Dictionary table of event types
實驗針對2012年發(fā)生在伊拉克的1 438起有記錄的社會安全事件。以該地區(qū)的政治經(jīng)濟中心巴格達為地理參考點,用Close to、Far from、In作為空間謂詞表示事件發(fā)生地與巴格達在空間距離上的關(guān)系,用Northwest、Northeast等空間謂詞表示事件發(fā)生地與巴格達在空間方位上的相對關(guān)系。以事件類型、事件目標(biāo)類型、事件實施組織為事務(wù)項,根據(jù)事件的時間信息,以“月”作為時間粒度,為各事務(wù)項添加時間標(biāo)識,構(gòu)建事件事務(wù)表(表3);再采用帶有時間標(biāo)識的FP-Growth關(guān)聯(lián)規(guī)則挖掘算法挖掘事件屬性項之間的時空關(guān)聯(lián)關(guān)系,并對結(jié)果進行解譯。根據(jù)數(shù)據(jù)特征,實驗中設(shè)定最小支持度閾值=15.6%,最小置信度閾值=50%。
表3 事件事務(wù)Table 3 Event services
2.2 實驗結(jié)果與分析
采用帶時間標(biāo)識的FP-Growth算法,指定以“月”作為時間粒度,以“事件類型”、“事件目標(biāo)類型”、“事件實施組織”及時空屬性作為挖掘?qū)ο?,?dāng)最小支持度閾值=15.6%、最小置信度閾值=50%時,得到頻繁項完全集94項。由于數(shù)據(jù)挖掘的目的在于發(fā)現(xiàn)潛在的有意義的知識[14],因而需對挖掘結(jié)果進行邏輯判斷和語義判斷,篩選符合邏輯并且有意義的結(jié)果,最終整理得到帶有月份標(biāo)識的有效關(guān)聯(lián)規(guī)則18條,其中1月份的關(guān)聯(lián)規(guī)則如表4所示。
表4 關(guān)聯(lián)規(guī)則(1月份)Table 4 Association rules (January)
對照制定的字典表,對得到的關(guān)聯(lián)規(guī)則進行解譯,以R1、R2、R3為例分析如下:R1表示在1月份巴格達發(fā)生爆炸襲擊的可能性為20.8%,如果巴格達發(fā)生社會安全事件,則有90.9%的概率為爆炸襲擊事件;R2表示在1月份距巴格達較遠地區(qū)發(fā)生爆炸襲擊事件的可能性為17.7%,如果在該地區(qū)發(fā)生社會安全事件,則事件類型為爆炸襲擊的可能性為72.3%;R3表示在1月份巴格達周邊地區(qū)發(fā)生爆炸襲擊社會安全事件的可能性為41.1%,如果在該區(qū)域發(fā)生社會安全事件,則事件類型為爆炸襲擊的可能性為78.2%。綜合考慮R1、R2、R3可得分析結(jié)果:1月份,爆炸襲擊事件是伊拉克面臨的主要安全威脅之一,且多發(fā)生在巴格達內(nèi)部及鄰近周邊地區(qū),因而在該區(qū)域應(yīng)重點加強對爆炸襲擊事件的防范措施和應(yīng)急預(yù)案的制定。
為驗證實驗得到關(guān)聯(lián)規(guī)則的有效性,利用傳統(tǒng)統(tǒng)計分析的方法對2012年1月發(fā)生在伊拉克的社會安全事件的類型及其空間分布特征進行分析,統(tǒng)計結(jié)果(圖3)證明,爆炸襲擊事件對巴格達及其附近區(qū)域威脅較大,證明利用本文方法得到的結(jié)果具有一定的可靠性。
圖3 不同類型事件在各區(qū)域范圍內(nèi)發(fā)生頻次Fig.3 Statistical of different types of events occur in different region
傳統(tǒng)統(tǒng)計分析側(cè)重展現(xiàn)事件各屬性的數(shù)值與比重差異,適用于對事件時空熱點及主要威脅類型等既有特征進行分析,但不能直接揭示屬性項間的潛在關(guān)聯(lián),進而實現(xiàn)更深層次的規(guī)則發(fā)現(xiàn)。同時,根據(jù)分析類型的不同,傳統(tǒng)統(tǒng)計分析需要多次計算統(tǒng)計指標(biāo)的值及比重,在多屬性項關(guān)聯(lián)分析中運算量較大、效率不高。本文提出的非指定時間約束關(guān)聯(lián)規(guī)則挖掘方法,能夠在僅遍歷一次事件數(shù)據(jù)集的條件下揭示事件屬性項之間的時空關(guān)聯(lián)關(guān)系,同時有效解決已有時空關(guān)聯(lián)規(guī)則挖掘算法中用戶無法事先指定時間約束的問題,得到全時間域內(nèi)帶有時間特征的時空關(guān)聯(lián)規(guī)則結(jié)果。非指定時間約束的關(guān)聯(lián)規(guī)則挖掘方法與現(xiàn)有時空關(guān)聯(lián)規(guī)則挖掘方法及傳統(tǒng)統(tǒng)計分析方法在驅(qū)動模式、算法特性、結(jié)果特征及適用性等方面的對比如表5所示。
表5 不同事件時空挖掘與分析方法的特性對比Table 5 Feature comparison of different methods of spatio-temporal data mining and analysis
本文分析了面向社會安全事件的時空關(guān)聯(lián)規(guī)則挖掘基本原理,為解決已有方法存在的無法事先指定有效時間約束問題,提出了為事件屬性項增加時間標(biāo)識、用時間標(biāo)識代替時間屬性值的方法,在傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法基礎(chǔ)上,設(shè)計了非指定時間約束的FP-Growth算法,并利用全球恐怖主義事件數(shù)據(jù)庫數(shù)據(jù)得到了有效、可靠的結(jié)果。以下問題需深入研究:1) 帶有時間標(biāo)識的關(guān)聯(lián)規(guī)則算法通過結(jié)構(gòu)優(yōu)化可進一步提高運行效率;2) 提高數(shù)據(jù)預(yù)處理效率,融合多源事件數(shù)據(jù),構(gòu)建面向我國的大型事件數(shù)據(jù)庫,將進一步增強本文方法的應(yīng)用廣度與深度;3) 本文提出的關(guān)聯(lián)規(guī)則挖掘方法只能對時間片內(nèi)事件屬性項及相互之間的關(guān)聯(lián)關(guān)系進行分析,如何挖掘時間片之間的時空關(guān)聯(lián)關(guān)系,以便對社會安全事件進行更加完備的分析與預(yù)測,是下一步的工作重點。
[1] 國務(wù)院.國家突發(fā)公共事件總體應(yīng)急預(yù)案[Z].中國防汛抗旱,2006.
[2] 劉曉東,朱翊,孫立堅,等.面向突發(fā)事件的地理信息服務(wù)研究[J].測繪科學(xué),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] 陳虎,李麗,李宏偉,等.本體輔助的約束空間關(guān)聯(lián)規(guī)則挖掘方法[J].測繪科學(xué)技術(shù)學(xué)報,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] 沙宗堯.時序空間關(guān)聯(lián)規(guī)則挖掘及其應(yīng)用研究[J].地理空間信息,2008,6(5):18-21.
[9] 岳慧穎.含有時空約束的關(guān)聯(lián)規(guī)則挖掘方法研究[D].哈爾濱:哈爾濱工程大學(xué),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] 夏英,張俊,王國胤.時空關(guān)聯(lián)規(guī)則挖掘算法及其在 ITS 中的應(yīng)用[J].計算機科學(xué),2011,38(9):173-176.
[12] 張俊.時空關(guān)聯(lián)性分析方法研究與應(yīng)用[D].重慶:重慶郵電大學(xué),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
國家自然科學(xué)基金項目(41501446);地理信息工程國家重點實驗室開放基金課題(SKLGIE2015-M-4-3、SKLGIE2015-M-3-1)
郭文月(1990-),女,博士研究生,主要從事數(shù)字地圖制圖和時空數(shù)據(jù)分析方面研究。E-mail:GuoWYer@163.com
10.3969/j.issn.1672-0504.2016.03.003
P208
A
1672-0504(2016)03-0014-05