基于聚类分析检索团伙多起犯罪的迭代算法

杨 静，王 靖

(1.解放军电子工程学院网络系，安徽 合肥 230037;2.中国科学技术大学计算机科学与技术学院，安徽 合肥 230027)

0 引言

数据挖掘能从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的和对决策有潜在价值的知识和规则[1]。如今，数据挖掘技术也被有效地应用到公安机关[2]，通过对犯罪数据的分析，查找犯罪的行为规律，帮助公安机关侦查办案。面对物欲横流的社会，刑事案件发生的频率提升[3]，社会上有少数人形成黑社会势力[4]，以团伙形式协同多次作案，不断地危害社会和人民的利益，现在公安机关开始重点打击此类黑社会势力，全力为社会营造安定团结的环境。如果能够有效地在众多案件中查找出团伙多次犯案的案件，将有利于公安机关对此类案件进行分析，找出规律，预防和侦查其它案件的发生，并进一步打击黑社会势力，并将其一举捕获。对于此种情况，本文将社会网络理论应用到犯罪领域中[5]，通过犯罪案件的关联关系，从层次聚类[6]中得到启示，用迭代拓展集合的方法将案件分类为一个个小的犯罪关系网，从每个分类的关系网中找出团伙多起犯罪案件。

1 问题的提出

团伙多起犯罪案件，可以理解为超过两起案件中有两个或两个以上相同的罪犯，而从庞大的数据库中存放的案件数据中找出是团伙多起犯案的案件，最基本的解决方案是找出一个案件的犯罪嫌疑人的集合，再和另一个案件犯罪嫌疑人的集合求交集，当交集中的元素个数大于或等于2时，就表示这两个案件有n(n≥2)个相同犯罪嫌疑人，即找到了n人2起团伙案件集合。如果是找n人m(m≥2)起团伙案件，就需要每m个案件的犯罪嫌疑人集合求交集。这样一来，如果目前数据库中存放有19万条案件，那这19万条案件两两组合，三三组合，依次类推，光是组合的可能性就有如公式(1)这么多:

这还不包括查询数据库和每种组合求交集的复杂度。对于现实应用来说，这种解决方案的复杂度太高，不具备实际应用性。因此，需要找出一种低复杂度，高效率地查找团伙多起案件的算法，加大它的实际应用性。

2 团伙多起犯案构成的犯罪网络

目前有一种很流行的社交网站，如人人网、朋友网。这类网站根据注册会员的信息，找到各个会员之间的某种联系，形成一个庞大的关系网，你可以找到和你同一家乡或同一学校毕业的朋友，甚至找到多年未见的朋友。其实这种社交网站是延续了英国人类学家布朗提出的“社会网络”这一概念[7]。“社会网络”也被称为人际网络，是一个为了达到某些特定目的，人与人之间进行信息交流和资源利用的关系网。是一个由某些个体间或组织间社会关系构成的动态系统[8]。那么对于团伙性质的犯罪，犯人之间是否其实也形成了一种类似“社会网络”的关系网络呢?如果将这种“社会网络”的理论用在团伙多起作案[9]的情况中，是否有助于降低查找时间，提高查找的准确率呢?

从前面提到的最基本的查找方法中，得出其实大多数案件之间是无法形成团伙多起作案的，因为这些案件之间没有什么关联，如果能从团伙多起犯罪案件中找到这些案件之间的关联关系，根据关联关系将这些案件和犯人构成一个犯罪关系网络[10]，然后只在这个关系网络中进行匹配查找，那么复杂度就会急剧降低。假设已经找出了n人m起(n，m均≥2)团伙案件集合，会发现这样一个关联关系:m起案件中至少有2个相同的犯罪嫌疑人。如果对于所有的案件，放宽这个关联关系，即案件中具有相同犯罪嫌疑人，那么在此关联条件下形成的犯罪网络必然包含最终需要的团伙多起犯罪案件形成的一个子网。如果将网络以集合的形式表示，也就是说结果集合是通过关联关系形成集合的子集。接下来的工作就是如何将有关联的案件形成一个个小的关系网络。

3 基于聚类分析方法分类案件

为了能够按照关联关系把案件归类形成一个个小的关系网，本文从数据挖掘的聚类分析方法中得到启示，采用一种类似聚类的方法对案件进行分类[11]。所谓聚类[12]就是数据对象分组成由类似对象组成的多个类或簇。聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象具有较高的相似度，与其它簇中的对象差异较大[13]。因此聚类分析的目的就是根据事物自身的特性和关联，将相似的事物归为一类。聚类方法中有一种自底向上的层次聚类方法[14]，先将每个对象各自作为一个原子聚类，然后对这些原子聚类逐层进行聚合，直至满足一定的终止条件。本文是基于这种层次聚类方法，用一种迭代拓展集合的方法将案件按关联关系分类成多个子集合，每个子集合之间交集为空，它们的并集是所有案件。这种迭代拓展集合的方法和层次聚类方法类似，不同的是迭代拓展集合是一个确定性的方法。假设开始集合中只有案件 Case1，根据关联关系把和Case1有相同犯罪嫌疑人的案件 Case2、Case3、Cas4加入这个集合。接着就把分别和Case2、Case3、Cas4有相同犯罪嫌疑人的案件加入集合，这样依次迭代拓展下去，直到集合中没有合适关联关系的新案件加入，如图1所示。

图1 迭代拓展集合

本身数据挖掘采集到的结果都是不确定的，基于聚类分析的基础上改进的这个方法，确保了算法的确定性。因为对于这样迭代拓展形成的集合，它是一个封闭的集合，集合中的某个案件如果属于团伙多起案件中的一个案件，那么同该案件一同形成团伙多起案件的其它案件肯定都在集合中。这样的话，只要匹配比较这个封闭集合中的元素，就可以确保找到全部能够形成团伙多起案件的案件。下面证明拓展形成的集合是一个封闭的集合。

证明:

(1)假如CaseX是集合中元素，那么和CaseX有关联关系案件肯定在集合中。因为拓展集合中每一个案件，肯定也包括拓展案件CaseX，那么和CaseX有关联关系案件肯定被拓展进入到集合中了。

(2)和集合中案件没关系不在集合中。在迭代拓展过程中，加入到集合的新案件都是和上一级的案件有关联关系的。没有关联关系肯定没有加入，也就是说无关联关系案件肯定不在集合中。在集合中的案件必然和某个案件有关联关系。

4 算法处理过程

整个算法可以分成3个步骤来处理:

(1)案件预处理，先尽量去除不可能形成团伙多起作案的案件。

(2)按照前面所描述的关联规则分类方法对待处理案件进行迭代分类，形成多个子集合。

(3)处理子集合中元素≥2的子集合，在这些集合中查找匹配多人多起团伙作案的案件。算法流程如图2，其中CaseSet集合表示经过预处理留下的待处理案件集合，Case X表示CaseSet集合中一个元素，relatedCaseSet表示根据关联规则迭代拓展形成的一个子集合。

图2 算法流程图

4.1 案件预处理

由于要查找的是团伙多起犯罪案件，要满足“多起”这个条件必须是犯罪嫌疑人犯案两起以上，那么让至少犯案两起的犯罪嫌疑人所涉及的所有案件都保留下来，但是为了满足“团伙”这个条件，又必须剔除作案时只有一个犯罪嫌疑人的案件。因此经过案件预处理这步可以留下来进行下一步关联规则分类的案件是:

待处理案件=至少犯案2起的人所涉及的所有案件－作案人员只有1个人案件

经过数据库查询得到的待处理案件有4万多条，比起所有案件19万条，已经大幅度减少，这大大降低了查找团伙多起犯罪案件的运行时间，也表明接下来的工作效率会大大提高。

4.2 分类迭代拓展集合

用CaseSet表示经过案件预处理后所有待分类案件集合;extendedCase表示已经被分类处理过案件集合;relatedCaseSet表示根据关联规则迭代拓展形成的一个子集合;tempCase表示待扩展的案件;processed-Case表示拓展案件时抛弃的案件集合，说明不符合这个子集合的关联关系，但不排除符合其它子集合;caseID表示待扩展第一条案件;members表示这个案件所有犯罪嫌疑人。下面是算法的描述:

4.3 查找团伙多起犯罪案件

根据关联规则分类后的子集合中，有些集合中只有一个元素，这表示该集合只有一个案件，无法满足“多起”这个条件，剔除这类集合后，在剩下的集合元素≥2的子集合中查找团伙多起犯罪案件。用relationCase表示一个分类的子集合。算法描述如下:

5 结束语

本文迭代算法是基于聚类分析的基础上提出的，并利用了社会网络这一理论，它能够帮助公安机关更方便高效地处理团伙多起犯案的问题，及时扼制同一团伙再次犯案的情况出现。本文的算法是通过两个案件有两个共犯，加强规则来分类的。其实一个共犯也可以，这样就不需要求案件所有犯罪嫌疑人集合，效率会提高。但是相应集合元素就会变多，在后期处理时间对变长。同时在算法中有个别子过程，如查找案件的犯罪嫌疑人的集合等比较低效。这些都是笔者在后面的研究和实施过程中要进一步改进的地方，从而达到算法效益的最大化。

[1]陈安，陈宁，周龙骧.数据挖掘技术及应用[M].北京:科学出版社，2006:1-50.

[2]庄海燕，王宝星.数据挖掘在犯罪防控中的运用[J].铁道警官高等专科学校学报，2008(5):118-119.

[3]陈巍.基于数据挖掘的刑事犯罪侦查系统研究[J].山西警官高等专科学校学报，2010，18(4):71-72.

[4]吕长贵.涉黑涉恶犯罪问题初探[J].公安研究，2011(2):52-55.

[5]唐常杰，刘威，温粉莲，等.社会网络分析和社团信息挖掘的三项探索[J].计算机应用，2006，26(9):2020-2021.

[6]向培素.聚类算法综述[J].西南民族大学学报，2011(S1):112-114.

[7]赵蓉英，王静.社会网络分析(SNA)研究热点与前沿的可视化分析[J].情报、信息与共享，2011(1):88-89.

[8]曹健.基于社会网络分析的犯罪团伙识别系统[D].上海:上海交通大学，2008.

[9]温粉莲，唐常杰，乔少杰，等.基于社会网络最短路径挖掘犯罪集团核心[J].计算机科学，2006，33(11):266-267.

[10]李海波.基于通信行为挖掘的犯罪网络分析技术研究与应用[D].上海:上海交通大学，2007.

[11]夏颖，王哲，程琳.聚类分析在犯罪数据分析中的应用[J].合肥工业大学学报，2009，32(12):1924-1925.

[12]Han Jiawei，Kamber M.数据挖掘:概念与技术[M].范明，孟小峰译.北京:机械工业出版社，2008.

[13]杨文雅.聚类分析算法理论研究综述[J].华章，2012(23):305.

[14]马海云，党建武.一种数据挖掘的方法研究[J].中央民族大学学报，2009，18(3):55-56.