基于聚類分析檢索團(tuán)伙多起犯罪的迭代算法

楊 靜，王 靖

(1.解放軍電子工程學(xué)院網(wǎng)絡(luò)系，安徽 合肥 230037;2.中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027)

0 引言

數(shù)據(jù)挖掘能從大量的數(shù)據(jù)中挖掘出隱含的、未知的、用戶可能感興趣的和對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則[1]。如今，數(shù)據(jù)挖掘技術(shù)也被有效地應(yīng)用到公安機(jī)關(guān)[2]，通過對(duì)犯罪數(shù)據(jù)的分析，查找犯罪的行為規(guī)律，幫助公安機(jī)關(guān)偵查辦案。面對(duì)物欲橫流的社會(huì)，刑事案件發(fā)生的頻率提升[3]，社會(huì)上有少數(shù)人形成黑社會(huì)勢(shì)力[4]，以團(tuán)伙形式協(xié)同多次作案，不斷地危害社會(huì)和人民的利益，現(xiàn)在公安機(jī)關(guān)開始重點(diǎn)打擊此類黑社會(huì)勢(shì)力，全力為社會(huì)營(yíng)造安定團(tuán)結(jié)的環(huán)境。如果能夠有效地在眾多案件中查找出團(tuán)伙多次犯案的案件，將有利于公安機(jī)關(guān)對(duì)此類案件進(jìn)行分析，找出規(guī)律，預(yù)防和偵查其它案件的發(fā)生，并進(jìn)一步打擊黑社會(huì)勢(shì)力，并將其一舉捕獲。對(duì)于此種情況，本文將社會(huì)網(wǎng)絡(luò)理論應(yīng)用到犯罪領(lǐng)域中[5]，通過犯罪案件的關(guān)聯(lián)關(guān)系，從層次聚類[6]中得到啟示，用迭代拓展集合的方法將案件分類為一個(gè)個(gè)小的犯罪關(guān)系網(wǎng)，從每個(gè)分類的關(guān)系網(wǎng)中找出團(tuán)伙多起犯罪案件。

1 問題的提出

團(tuán)伙多起犯罪案件，可以理解為超過兩起案件中有兩個(gè)或兩個(gè)以上相同的罪犯，而從龐大的數(shù)據(jù)庫(kù)中存放的案件數(shù)據(jù)中找出是團(tuán)伙多起犯案的案件，最基本的解決方案是找出一個(gè)案件的犯罪嫌疑人的集合，再和另一個(gè)案件犯罪嫌疑人的集合求交集，當(dāng)交集中的元素個(gè)數(shù)大于或等于2時(shí)，就表示這兩個(gè)案件有n(n≥2)個(gè)相同犯罪嫌疑人，即找到了n人2起團(tuán)伙案件集合。如果是找n人m(m≥2)起團(tuán)伙案件，就需要每m個(gè)案件的犯罪嫌疑人集合求交集。這樣一來，如果目前數(shù)據(jù)庫(kù)中存放有19萬條案件，那這19萬條案件兩兩組合，三三組合，依次類推，光是組合的可能性就有如公式(1)這么多:

這還不包括查詢數(shù)據(jù)庫(kù)和每種組合求交集的復(fù)雜度。對(duì)于現(xiàn)實(shí)應(yīng)用來說，這種解決方案的復(fù)雜度太高，不具備實(shí)際應(yīng)用性。因此，需要找出一種低復(fù)雜度，高效率地查找團(tuán)伙多起案件的算法，加大它的實(shí)際應(yīng)用性。

2 團(tuán)伙多起犯案構(gòu)成的犯罪網(wǎng)絡(luò)

目前有一種很流行的社交網(wǎng)站，如人人網(wǎng)、朋友網(wǎng)。這類網(wǎng)站根據(jù)注冊(cè)會(huì)員的信息，找到各個(gè)會(huì)員之間的某種聯(lián)系，形成一個(gè)龐大的關(guān)系網(wǎng)，你可以找到和你同一家鄉(xiāng)或同一學(xué)校畢業(yè)的朋友，甚至找到多年未見的朋友。其實(shí)這種社交網(wǎng)站是延續(xù)了英國(guó)人類學(xué)家布朗提出的“社會(huì)網(wǎng)絡(luò)”這一概念[7]?！吧鐣?huì)網(wǎng)絡(luò)”也被稱為人際網(wǎng)絡(luò)，是一個(gè)為了達(dá)到某些特定目的，人與人之間進(jìn)行信息交流和資源利用的關(guān)系網(wǎng)。是一個(gè)由某些個(gè)體間或組織間社會(huì)關(guān)系構(gòu)成的動(dòng)態(tài)系統(tǒng)[8]。那么對(duì)于團(tuán)伙性質(zhì)的犯罪，犯人之間是否其實(shí)也形成了一種類似“社會(huì)網(wǎng)絡(luò)”的關(guān)系網(wǎng)絡(luò)呢?如果將這種“社會(huì)網(wǎng)絡(luò)”的理論用在團(tuán)伙多起作案[9]的情況中，是否有助于降低查找時(shí)間，提高查找的準(zhǔn)確率呢?

從前面提到的最基本的查找方法中，得出其實(shí)大多數(shù)案件之間是無法形成團(tuán)伙多起作案的，因?yàn)檫@些案件之間沒有什么關(guān)聯(lián)，如果能從團(tuán)伙多起犯罪案件中找到這些案件之間的關(guān)聯(lián)關(guān)系，根據(jù)關(guān)聯(lián)關(guān)系將這些案件和犯人構(gòu)成一個(gè)犯罪關(guān)系網(wǎng)絡(luò)[10]，然后只在這個(gè)關(guān)系網(wǎng)絡(luò)中進(jìn)行匹配查找，那么復(fù)雜度就會(huì)急劇降低。假設(shè)已經(jīng)找出了n人m起(n，m均≥2)團(tuán)伙案件集合，會(huì)發(fā)現(xiàn)這樣一個(gè)關(guān)聯(lián)關(guān)系:m起案件中至少有2個(gè)相同的犯罪嫌疑人。如果對(duì)于所有的案件，放寬這個(gè)關(guān)聯(lián)關(guān)系，即案件中具有相同犯罪嫌疑人，那么在此關(guān)聯(lián)條件下形成的犯罪網(wǎng)絡(luò)必然包含最終需要的團(tuán)伙多起犯罪案件形成的一個(gè)子網(wǎng)。如果將網(wǎng)絡(luò)以集合的形式表示，也就是說結(jié)果集合是通過關(guān)聯(lián)關(guān)系形成集合的子集。接下來的工作就是如何將有關(guān)聯(lián)的案件形成一個(gè)個(gè)小的關(guān)系網(wǎng)絡(luò)。

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

為了能夠按照關(guān)聯(lián)關(guān)系把案件歸類形成一個(gè)個(gè)小的關(guān)系網(wǎng)，本文從數(shù)據(jù)挖掘的聚類分析方法中得到啟示，采用一種類似聚類的方法對(duì)案件進(jìn)行分類[11]。所謂聚類[12]就是數(shù)據(jù)對(duì)象分組成由類似對(duì)象組成的多個(gè)類或簇。聚類所生成的簇是一組數(shù)據(jù)對(duì)象的集合，這些對(duì)象與同一個(gè)簇中的對(duì)象具有較高的相似度，與其它簇中的對(duì)象差異較大[13]。因此聚類分析的目的就是根據(jù)事物自身的特性和關(guān)聯(lián)，將相似的事物歸為一類。聚類方法中有一種自底向上的層次聚類方法[14]，先將每個(gè)對(duì)象各自作為一個(gè)原子聚類，然后對(duì)這些原子聚類逐層進(jìn)行聚合，直至滿足一定的終止條件。本文是基于這種層次聚類方法，用一種迭代拓展集合的方法將案件按關(guān)聯(lián)關(guān)系分類成多個(gè)子集合，每個(gè)子集合之間交集為空，它們的并集是所有案件。這種迭代拓展集合的方法和層次聚類方法類似，不同的是迭代拓展集合是一個(gè)確定性的方法。假設(shè)開始集合中只有案件 Case1，根據(jù)關(guān)聯(lián)關(guān)系把和Case1有相同犯罪嫌疑人的案件 Case2、Case3、Cas4加入這個(gè)集合。接著就把分別和Case2、Case3、Cas4有相同犯罪嫌疑人的案件加入集合，這樣依次迭代拓展下去，直到集合中沒有合適關(guān)聯(lián)關(guān)系的新案件加入，如圖1所示。

圖1 迭代拓展集合

本身數(shù)據(jù)挖掘采集到的結(jié)果都是不確定的，基于聚類分析的基礎(chǔ)上改進(jìn)的這個(gè)方法，確保了算法的確定性。因?yàn)閷?duì)于這樣迭代拓展形成的集合，它是一個(gè)封閉的集合，集合中的某個(gè)案件如果屬于團(tuán)伙多起案件中的一個(gè)案件，那么同該案件一同形成團(tuán)伙多起案件的其它案件肯定都在集合中。這樣的話，只要匹配比較這個(gè)封閉集合中的元素，就可以確保找到全部能夠形成團(tuán)伙多起案件的案件。下面證明拓展形成的集合是一個(gè)封閉的集合。

證明:

(1)假如CaseX是集合中元素，那么和CaseX有關(guān)聯(lián)關(guān)系案件肯定在集合中。因?yàn)橥卣辜现忻恳粋€(gè)案件，肯定也包括拓展案件CaseX，那么和CaseX有關(guān)聯(lián)關(guān)系案件肯定被拓展進(jìn)入到集合中了。

(2)和集合中案件沒關(guān)系不在集合中。在迭代拓展過程中，加入到集合的新案件都是和上一級(jí)的案件有關(guān)聯(lián)關(guān)系的。沒有關(guān)聯(lián)關(guān)系肯定沒有加入，也就是說無關(guān)聯(lián)關(guān)系案件肯定不在集合中。在集合中的案件必然和某個(gè)案件有關(guān)聯(lián)關(guān)系。

4 算法處理過程

整個(gè)算法可以分成3個(gè)步驟來處理:

(1)案件預(yù)處理，先盡量去除不可能形成團(tuán)伙多起作案的案件。

(2)按照前面所描述的關(guān)聯(lián)規(guī)則分類方法對(duì)待處理案件進(jìn)行迭代分類，形成多個(gè)子集合。

(3)處理子集合中元素≥2的子集合，在這些集合中查找匹配多人多起團(tuán)伙作案的案件。算法流程如圖2，其中CaseSet集合表示經(jīng)過預(yù)處理留下的待處理案件集合，Case X表示CaseSet集合中一個(gè)元素，relatedCaseSet表示根據(jù)關(guān)聯(lián)規(guī)則迭代拓展形成的一個(gè)子集合。

圖2 算法流程圖

4.1 案件預(yù)處理

由于要查找的是團(tuán)伙多起犯罪案件，要滿足“多起”這個(gè)條件必須是犯罪嫌疑人犯案兩起以上，那么讓至少犯案兩起的犯罪嫌疑人所涉及的所有案件都保留下來，但是為了滿足“團(tuán)伙”這個(gè)條件，又必須剔除作案時(shí)只有一個(gè)犯罪嫌疑人的案件。因此經(jīng)過案件預(yù)處理這步可以留下來進(jìn)行下一步關(guān)聯(lián)規(guī)則分類的案件是:

待處理案件=至少犯案2起的人所涉及的所有案件－作案人員只有1個(gè)人案件

經(jīng)過數(shù)據(jù)庫(kù)查詢得到的待處理案件有4萬多條，比起所有案件19萬條，已經(jīng)大幅度減少，這大大降低了查找團(tuán)伙多起犯罪案件的運(yùn)行時(shí)間，也表明接下來的工作效率會(huì)大大提高。

4.2 分類迭代拓展集合

用CaseSet表示經(jīng)過案件預(yù)處理后所有待分類案件集合;extendedCase表示已經(jīng)被分類處理過案件集合;relatedCaseSet表示根據(jù)關(guān)聯(lián)規(guī)則迭代拓展形成的一個(gè)子集合;tempCase表示待擴(kuò)展的案件;processed-Case表示拓展案件時(shí)拋棄的案件集合，說明不符合這個(gè)子集合的關(guān)聯(lián)關(guān)系，但不排除符合其它子集合;caseID表示待擴(kuò)展第一條案件;members表示這個(gè)案件所有犯罪嫌疑人。下面是算法的描述:

4.3 查找團(tuán)伙多起犯罪案件

根據(jù)關(guān)聯(lián)規(guī)則分類后的子集合中，有些集合中只有一個(gè)元素，這表示該集合只有一個(gè)案件，無法滿足“多起”這個(gè)條件，剔除這類集合后，在剩下的集合元素≥2的子集合中查找團(tuán)伙多起犯罪案件。用relationCase表示一個(gè)分類的子集合。算法描述如下:

5 結(jié)束語

本文迭代算法是基于聚類分析的基礎(chǔ)上提出的，并利用了社會(huì)網(wǎng)絡(luò)這一理論，它能夠幫助公安機(jī)關(guān)更方便高效地處理團(tuán)伙多起犯案的問題，及時(shí)扼制同一團(tuán)伙再次犯案的情況出現(xiàn)。本文的算法是通過兩個(gè)案件有兩個(gè)共犯，加強(qiáng)規(guī)則來分類的。其實(shí)一個(gè)共犯也可以，這樣就不需要求案件所有犯罪嫌疑人集合，效率會(huì)提高。但是相應(yīng)集合元素就會(huì)變多，在后期處理時(shí)間對(duì)變長(zhǎng)。同時(shí)在算法中有個(gè)別子過程，如查找案件的犯罪嫌疑人的集合等比較低效。這些都是筆者在后面的研究和實(shí)施過程中要進(jìn)一步改進(jìn)的地方，從而達(dá)到算法效益的最大化。

[1]陳安，陳寧，周龍?bào)J.數(shù)據(jù)挖掘技術(shù)及應(yīng)用[M].北京:科學(xué)出版社，2006:1-50.

[2]莊海燕，王寶星.數(shù)據(jù)挖掘在犯罪防控中的運(yùn)用[J].鐵道警官高等?？茖W(xué)校學(xué)報(bào)，2008(5):118-119.

[3]陳巍.基于數(shù)據(jù)挖掘的刑事犯罪偵查系統(tǒng)研究[J].山西警官高等?？茖W(xué)校學(xué)報(bào)，2010，18(4):71-72.

[4]呂長(zhǎng)貴.涉黑涉惡犯罪問題初探[J].公安研究，2011(2):52-55.

[5]唐常杰，劉威，溫粉蓮，等.社會(huì)網(wǎng)絡(luò)分析和社團(tuán)信息挖掘的三項(xiàng)探索[J].計(jì)算機(jī)應(yīng)用，2006，26(9):2020-2021.

[6]向培素.聚類算法綜述[J].西南民族大學(xué)學(xué)報(bào)，2011(S1):112-114.

[7]趙蓉英，王靜.社會(huì)網(wǎng)絡(luò)分析(SNA)研究熱點(diǎn)與前沿的可視化分析[J].情報(bào)、信息與共享，2011(1):88-89.

[8]曹健.基于社會(huì)網(wǎng)絡(luò)分析的犯罪團(tuán)伙識(shí)別系統(tǒng)[D].上海:上海交通大學(xué)，2008.

[9]溫粉蓮，唐常杰，喬少杰，等.基于社會(huì)網(wǎng)絡(luò)最短路徑挖掘犯罪集團(tuán)核心[J].計(jì)算機(jī)科學(xué)，2006，33(11):266-267.

[10]李海波.基于通信行為挖掘的犯罪網(wǎng)絡(luò)分析技術(shù)研究與應(yīng)用[D].上海:上海交通大學(xué)，2007.

[11]夏穎，王哲，程琳.聚類分析在犯罪數(shù)據(jù)分析中的應(yīng)用[J].合肥工業(yè)大學(xué)學(xué)報(bào)，2009，32(12):1924-1925.

[12]Han Jiawei，Kamber M.數(shù)據(jù)挖掘:概念與技術(shù)[M].范明，孟小峰譯.北京:機(jī)械工業(yè)出版社，2008.

[13]楊文雅.聚類分析算法理論研究綜述[J].華章，2012(23):305.

[14]馬海云，黨建武.一種數(shù)據(jù)挖掘的方法研究[J].中央民族大學(xué)學(xué)報(bào)，2009，18(3):55-56.