非指定时间约束的社会安全事件关联规则挖掘

郭 文 月,刘 海 砚,余 岸 竹,马 绍 龙,冯 培 义

(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