改进型apriori算法在犯罪关联研究中应用

《改进型apriori算法在犯罪关联研究中应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、改进型Apriori算法在犯罪关联研究中应用　　摘要：介绍了关联规则数据挖掘技术，特别是Apriori核心算法，并对Apriori算法进行了Hash优化。以某市的犯罪信息数据库为实例，将改进后的关联分析技术应用其中，以便发现犯罪行为特点及犯罪嫌疑人特性等潜在的联系，为公安部门的战略部署、决策指挥、侦查破案、治安管理等提供依据。关键词关键词：犯罪特征；关联规则；数据挖掘；Apriori中图分类号：TP312文献标识码：A文章编号文章编号：16727800（2013）0110068020引言7信息技术的飞速发展，给公安机关的信息化应用提供了强有力的保障，较大程度上提

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

3、叫关联分析，是数据挖掘的一个重要研究领域。它是指从事务数据库、关系数据库和其它信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性，即所谓的关联规则。其形式为：“X=>Y”，即在设定的高置信度的规则下，X事件发生了，Y事件必然发生。关联规则挖掘核心算法为著名的Apriori算法。当然，此后出现了一些相关算法，诸如DIC算法＼[2＼]、DLG算法＼[3＼]和DHP算法＼[4＼]等，都是基于Apriori算法做了改进或优化而成的。1.1Apriori算法Apriori算法，是一种挖掘布尔关联规则频繁项集的算法，是Agrawal.R、Imielińs

4、ki.T等人在1994第20届大型数据库国际会议上提出的＼[5＼]，于当时最具影响力。此算法实质是一个逐层迭代搜索的方法，利用K项集探索K+1项集。第一次，找出频繁1项集的集合，记为L1；第二次，利用L1探索L2，找出频繁2项集，记为L2；如此进行探索，直至频繁项集K为空，停止。7算法描述如下：Input：DatabaseD，oftransactions；minimumsupportthreshold；Output：L，frequentitemsetsinDMethod：（1）L1=find_frequent_1-itemsets（D）；（2）For（k=2；L

5、k-1≠Φ；k++）{（3）Ck=apriori_gen（Lk-1，min_sup）；（4）foreachtransactiont∈D{（5）Ct=subset（Ck，t）；（6）foreachcandidatec∈Ct；（7）c.count++；（8）}（9）Lk={c∈Ck

6、c.count≥min_sup}；（10）}（11）returnL=∪kLk；Procedureapriori_gen（Lk-1：frequent（k-1）-itemsets；min_sup：support）（1）foreachitemsetl1∈Lk-1（2）foreachitemse

7、tl2∈Lk-1（3）if（l1＼[1＼]=l2＼[1＼]）∧（l1＼[2＼]=l2＼[2＼]）∧…∧（l1＼[k-2＼]=l2＼[k-2＼]）∧（l17＼[k-1＼]=l2＼[k-1＼]）then{（4）c=l1∪l2；（5）ifhas_infrequent_subset（c，Lk-1）then（6）deletec；（7）elseaddctoCk；（8）}（9）returnCk；Procedurehas_infrequent_subset（c：candidatek-itemset；Lk-1：frequent（k-1）-itemsets）（1）foreach（k

8、-1）-subsetsofc（2）ifs！∈Lk-1then（3）returntrue；（4）returnfalse；1.2关联规则的产生事实上，当从数据库D中的事务找出频繁项集时，它们产生的关联规则是显而易见的，然而，这些规则的置信度是不一样的。因此，和支持度一样，置信度得设置一个阈值。在设定的置信度阈值和支持度阈值条件下，同时满足这两个条件的规则叫强规则，这些规则通常颇为有趣，是关联规则挖据的目的。7对于置信度，可以用下式表示，其中条件概率用项集支持度计数表示。Conference（A=>B）=P（B

9、A）=support-count（A+B）/suppor

10、t-count（A）其中