改进型Apriori算法在犯罪关联分析中的应用[精品资料]

改进型 Apriori 算法在犯罪关联分析中的应用 -精品资料 本文档格式为 WORD,感谢你的阅读。 最新最全的 学术论文 期刊文献 年终总结 年终报告 工作总结 个人总结 述职报告 实习报告 单位总结 摘要：介绍了关联规则数据挖掘技术，特别是Apriori 核心算法，并对 Apriori 算法进行了 Hash优化。以某市的犯罪信息数据库为实例，将改进后的关联分析技术应用其中，以便发现犯罪行为特点及犯罪嫌疑人特性等潜在的联系，为公安部门的战略部署、决策指挥、侦查破 案、治安管理等提供依据。 关键词关键词：犯罪特征；关联规则；数据挖掘；Apriori TP312A16727800（ 2013） 011006802 0 引言 信息技术的飞速发展，给公安机关的信息化应用提供了强有力的保障，较大程度上提高了整个公安队伍的战斗力，在防范打击违法犯罪、维护国家安全稳定等方面起到了重要作用。 “ 金盾工程 ” 的推进，促使各类业务应用平台逐步建成和完善，但情报导向的信息应用仍处于初探阶段。信息的关键价值不在于存储，而在于对所拥有的大量警务信息进行二次挖掘 ，获取更有价值的情报信息 1 。近年来，公安部门积累了海量的基础数据和犯罪数据信息，但对于这些数据的高效利用和深度应用未有明显成绩。因此，如何利用先进的信息技术在这些海量数据中进行深度挖掘，得出一些新知识，使之有益于公安部门的战略部署、决策指挥、侦查破案、治安管理等，具有一定的时代意义。 1 关联规则挖掘 关联规则挖掘，有时也叫关联分析，是数据挖掘的一个重要研究领域。它是指从事务数据库、关系数据库和其它信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性，即所谓的关联 规则。其形式为： “X=Y” ，即在设定的高置信度的规则下， X 事件发生了， Y 事件必然发生。 关联规则挖掘核心算法为著名的 Apriori算法。当然，此后出现了一些相关算法，诸如 DIC算法 2 、 DLG算法 3 和 DHP算法 4 等，都是基于 Apriori 算法做了改进或优化而成的。 1.1Apriori 算法 Apriori 算法，是一种挖掘布尔关联规则频繁项集的算法，是 Agrawal.R 、 Imieliski.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 tD （ 5） Ct=subset（ Ck， t）； （ 6） for each candidate c Ct ； （ 7） c.count+； （ 8） （ 9） Lk= cCk |c.countmi n_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 所示。 阅读相关文档 :实施过程管理在网络集成项目中的运用 微课开发与应用研究 基于 C#的多机远程桌面 监控系统设计与实现 基于 Multigen Creator的三维虚拟校园应用研究 基于 CDIO 理念的模拟电路课程教学改革与实践 基于粒子群优化算法和 Wiki 的数字化教材开发研究 Flash 在深度和广度优先遍历算法教学中的应用 高效运动目标检测算法研究 基于 VC+的虚拟示波器软件设计 振镜式激光打标系统及工艺参数分析 一种基于多因素的潜在好友推荐算法 基于 .NE