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

张亚洲

摘 要：文章针对公安机关已为犯罪行为建立了海量的业务信息数据库，提出基于Apriori算法的关联规则数据挖掘技术，并将该技术应用于犯罪行为分析，以便发现犯罪行为特点及犯罪嫌疑人特性等潜在的联系，为公安部门的战略部署，决策指挥，侦查破案，治安管理等提供依据。

关键词：犯罪分析；Apriori算法；關联规则

近年来，公安部门积累了海量的基础数据和犯罪数据信息，但对于这么多数据的高效利用和深度应用未有明显成绩。因此如何利用先进的信息技术在这些海量数据中进行深度挖掘，得出一些新知识，使之有益于公安部门的战略部署，决策指挥，侦查破案，治安管理等，自然具有一定的时代意义。

1 关联规则挖掘

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

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

1.1 Apriori算法

Apriori算法，是Agrawal.R、Imieliński.T等人在1993数据管理国际会议上提出的，它是一种最具影响挖掘关联规则频繁项集的算法[4]。算法实质是一个逐层迭代搜索的方法，利用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的事务数[5]。

1.3 Apriori算法优化

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

2 实例分析

2.1 挖据过程

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

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

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

第三步，关联规则挖掘。主要步骤，使用Apriori算法对已梳理过的事务进行关联分析。

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

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

其中，Apriori算法是关键。过程将发现事务数据库中隐藏的形式为“A=>B”的规则，即在一定的支持度和一定置信度下，假如A发生则B一定发生。

2.2 模型建立

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

在实际工作中，犯罪两个重要的组成是犯罪行为和行为者。因此，从事和人出发，考虑其特点。以已破的刑事犯罪案件信息数据的主导，进行梳理，如下：

（1）案件信息：编号、类别、时间、地点、特点、危害程度、简情；

（2）涉案人员：姓名、外号、性别、民族、出生日期、居民身份证号码、籍贯、户籍地、居住地、文化程度、收入状况、家庭背景、违法犯罪经历

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

2.3 数据抽样

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

2.4 关联分析

实验环境：平台windows，语言java，算法基于Hash技术改进的Apriori。

取值支持度阀值=3，置信度=8时，从结果中抽一条规则：

from 下半夜；单独作案；小学；少年；贵州省；calc下半夜；单独作案；少年；->小学；贵州省；：1.0

//规则说明：from L（支持度大于已设定支持度阀值）；calc S->L-S（关联规则）；：Num（置信度）

该规则的预示：

下半夜发生的抢劫案，若实施犯罪者为单人且为少年，可以锁定该犯罪嫌疑人是贵州籍，且文化程度为小学。

取值支持度阀值=4，置信度=9时，从结果中抽一条规则：

from上半夜；共同作案；少年；calc上半夜；少年；->共同作案；：1.0

//规则说明：from L（支持度大于已设定支持度阀值）；calc S->L-S（关联规则）；：Num（置信度）

该规则的预示：

发生在上半夜的抢劫案，如实施犯罪者为少年，一定还有同伙。

对比，提高支持度阀值和置信度阀值，可提高挖掘结果的可靠性，但发现的关联规则也大大减少。因此，根据用户的兴趣程度和实效评估，及时调整相关参数，对于关联规则挖掘在某一领域的应用至关重要。

3 结语

本文仅仅是作为关联规则在犯罪分析中应用的一个引子，对其可行性做了探究，其工程运用需要更多更广的梳理和评估。随政治、经济、科技等的发展，犯罪行为也悄然发展，其新特点也层出不穷，因此借助于数据挖掘技术，更快更准的掌握犯罪动态尤为重要。这对提高公安机关打、防、控等整体作战水平和能力具有积极重大意义。

[参考文献]

[1]Brin S，Motwani R，Ullman J D and Tsur S.Dynamic itemset counting and implication rules for market basket data[C].Proc.of the ACM SIGMOD Intl Conf.on Management of Data，1997.

[2]Yen S J and Chen A L P.An Efficient Approach to Discovering Knowledge from Large Databases[C].Proc.IEEE/ACM International Conference on Parallel and Distributed Information Systems（PDIS），1996.

[3]Park J S，Chen M S and Yu P S.An Effective Hash Based Algorithm for Mining AssociationRules[C].Proc.of ACM SIGMOD，May 23-25，1995：175.186.

[4]Agrawal， R.；Imieliński， T.； Swami， A.（1993）."Mining association rules between sets of items in large databases". Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. pp.207. doi：10.1145/170035.170072.ISBN 0897915925.

[5]Jiawei Han，Micheline Kamber，Data Mining：Concepts adn Technigues，The Second Edition，Morgan Kaufmann Publishers，2006，138.