改进型Apriori算法在犯罪关联分析中的应用

摘要：介绍了关联规则数据挖掘技术，特别是Apriori核心算法，并对Apriori算法进行了Hash优化。以某市的犯罪信息数据库为实例，将改进后的关联分析技术应用其中，以便发现犯罪行为特点及犯罪嫌疑人特性等潜在的联系，为公安部门的战略部署、决策指挥、侦查破案、治安管理等提供依据。

关键词关键词：犯罪特征；关联规则；数据挖掘；Apriori

中图分类号：TP312文献标识码：A文章编号文章编号：16727800（2013）011006802

0引言

信息技术的飞速发展，给公安机关的信息化应用提供了强有力的保障，较大程度上提高了整个公安队伍的战斗力，在防范打击违法犯罪、维护国家安全稳定等方面起到了重要作用。“金盾工程”的推进，促使各类业务应用平台逐步建成和完善，但情报导向的信息应用仍处于初探阶段。信息的关键价值不在于存储，而在于对所拥有的大量警务信息进行二次挖掘，获取更有价值的情报信息＼[1＼]。近年来，公安部门积累了海量的基础数据和犯罪数据信息，但对于这些数据的高效利用和深度应用未有明显成绩。因此，如何利用先进的信息技术在这些海量数据中进行深度挖掘，得出一些新知识，使之有益于公安部门的战略部署、决策指挥、侦查破案、治安管理等，具有一定的时代意义。

1关联规则挖掘

关联规则挖掘，有时也叫关联分析，是数据挖掘的一个重要研究领域。它是指从事务数据库、关系数据库和其它信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性，即所谓的关联规则。其形式为：“X=>Y”，即在设定的高置信度的规则下，X事件发生了，Y事件必然发生。

关联规则挖掘核心算法为著名的Apriori算法。当然，此后出现了一些相关算法，诸如DIC算法 ＼[2＼]、DLG算法＼[3＼]和 DHP算法＼[4＼]等，都是基于Apriori算法做了改进或优化而成的。

1.1Apriori算法

Apriori算法，是一种挖掘布尔关联规则频繁项集的算法，是Agrawal.R 、Imieliński.T等人在1994第20届大型数据库国际会议上提出的＼[5＼]，于当时最具影响力。此算法实质是一个逐层迭代搜索的方法，利用K项集探索K+1项集。第一次，找出频繁1项集的集合，记为L1；第二次，利用L1探索L2，找出频繁2项集，记为L2；如此进行探索，直至频繁项集K为空，停止。

算法描述如下：

Input： Database D， of transactions； minimum support threshold；

Output： L， frequent itemsets in D

Method：

（1） L1=find_frequent_1-itemsets（D）；

（2） For（k=2； Lk-1≠Φ； k++）{

（3） Ck=apriori_gen（Lk-1， min_sup）；

（4） for each transaction t∈D{

（5） Ct=subset（Ck，t）；

（6） for each candidate c ∈Ct；

（7） c.count++；

（8） }

（9） Lk={ c∈Ck |c.count≥min_sup}；

（10） }

（11） return L=∪kLk；

Procedure apriori_gen（Lk-1：frequent（k-1）-itemsets； min_sup： support）

（1） for each itemset l1∈ Lk-1

（2） for each itemset l2∈ Lk-1

（3） if（l1＼[1＼]= l2 ＼[1＼]）∧ （l1＼[2＼]= l2＼[2＼]） ∧…∧（l1＼[k-2＼]= l2＼[k-2＼]）∧ （l1 ＼[k-1＼]= l2 ＼[k-1＼]） then {

（4） c=l1∪ l2；

（5） if has_infrequent_subset（c， L k-1） then

（6） delete c；

（7） else add c to Ck；

（8） }

（9） return Ck；

Procedure has_infrequent_subset（c： candidate k-itemset； Lk-1：

frequent（k-1）-itemsets）

（1） for each（k-1）-subset s of c

（2） if s ！∈L k-1 then

（3） return true；

（4） return false；

1.2关联规则的产生

事实上，当从数据库D中的事务找出频繁项集时，它们产生的关联规则是显而易见的，然而，这些规则的置信度是不一样的。因此，和支持度一样，置信度得设置一个阈值。在设定的置信度阈值和支持度阈值条件下，同时满足这两个条件的规则叫强规则，这些规则通常颇为有趣，是关联规则挖据的目的。

对于置信度，可以用下式表示，其中条件概率用项集支持度计数表示。

Conference（A=>B）=P（B|A）=support-count（A+B）/support-count（A）

其中，support-count（A+B）是包含项集A+B的事务数，support-count（A）包含项集的A的事务数＼[6＼] 。

1.3Apriori算法优化

从算法描述可看出，当数据库D的事务达到一定规模时，算法的空间复杂度和时间复杂度相当高。因此，优化是必要的，旨在提高原算法的效率。常用方法有：散列技术计数、事务压缩、划分、选样。还有一些通过变形实现有效性，如动态项集计数、多层和多维等关联规则挖掘。

2实例分析

2.1挖据过程

将Apriori算法应用于犯罪行为分析，主要目的在于找出案件的各个特征及犯罪嫌疑人各个特征之前可能存在的相互关系，以便找出有用的关联规则。其挖掘过程如下：

（1）数据选择。从犯罪行为数据库中检索并选择与分析任务相关的数据并消除噪声信息。

（2）数据梳理。运用减低维数、连续数据的离散分类等将数据梳理成标准统一的适合于挖据的形式。

（3）关联规则挖掘。此步骤较为关键，使用Apriori算法对已梳理过的事务进行关联分析。

（4）实效评估。通过调整支持度阈值及置信度阈值，按照既定的业务兴趣度量，结合实战检验，使得过程挖掘所获得的知识结果更容易接受，且更有价值。

（5）知识表示与存储。使用可视化和知识表示技术，形成知识库，为决策提供依据。

其中，Apriori算法是关键。过程将发现事务数据库中隐藏的形式为“A=>B”的规则，即在一定的支持度和一定置信度下，假如A发生则B一定发生。图1犯罪行为关联规则挖掘过程2.2模型建立

优秀的技术应用于具体行业，要想达到实战的成果，模型的建立尤为重要。而对于关联数据挖掘而言，这个模型的关键点在于合适事务数据库的建立。公安业务数据库巨大无比，如何梳理，直接影响到挖掘的成果。

在实际工作中，犯罪两个重要的组成是犯罪行为和行为者。因此，从事和人出发，考虑其特点，以已破的刑事犯罪案件信息数据为主导进行梳理，①案件信息：编号、类别、时间、地点、特点、危害程度、简情；②涉案人员：姓名、外号、性别、民族、出生日期、居民身份证号码、籍贯、户籍地、居住地、文化程度、收入状况、家庭背景、违法犯罪经历。

本文中，挑选其中主要的八项事务建立模型：作案形式、选择时机、选择处所、选择对象、案件类别、嫌疑人籍贯、嫌疑人年龄、嫌疑人文化。

2.3数据抽样

样本来源于某地市2012年抢劫案连续抽取的12个样本，并按照模型格式进行梳理，其结果如表1所示。