楊 靜，王 靖

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

0 引言

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

1 問題的提出

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

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

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

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

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

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

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

圖1 迭代拓展集合

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

證明:

(1)假如CaseX是集合中元素，那么和CaseX有關(guān)聯(lián)關(guān)系案件肯定在集合中。因為拓展集合中每一個案件，肯定也包括拓展案件CaseX，那么和CaseX有關(guān)聯(lián)關(guān)系案件肯定被拓展進入到集合中了。

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

4 算法處理過程

整個算法可以分成3個步驟來處理:

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

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

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

圖2 算法流程圖

4.1 案件預(yù)處理

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

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

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

4.2 分類迭代拓展集合

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

4.3 查找團伙多起犯罪案件

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

5 結(jié)束語

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

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

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

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

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

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

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

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

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

[9]溫粉蓮，唐常杰，喬少杰，等.基于社會網(wǎng)絡(luò)最短路徑挖掘犯罪集團核心[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é)報，2009，32(12):1924-1925.

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

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

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