刑事案件信息數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則分析

摘要:利用數(shù)據(jù)挖掘中的有關(guān)方法和技術(shù)，對(duì)刑事案件信息數(shù)據(jù)進(jìn)行分析研判，得出各類犯罪之間的關(guān)聯(lián)規(guī)則，為公安機(jī)關(guān)對(duì)相似案件的偵破提供分析依據(jù)，并對(duì)犯罪案件的發(fā)展趨勢(shì)進(jìn)行預(yù)測(cè)，提前采取相關(guān)措施，減少違法案件的發(fā)生。

關(guān)鍵詞:數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;序列分析;刑事案件信息

中圖分類號(hào):TP399文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)35-9909-03

Association Rules Analysis in Criminal Case Database

XIA Ying1， WANG Zhe2， WANG Sheng-he1， CHENG Lin1

(1. AnHui Vocation College of Public Security， Hefei 230088， China; 2. Hefei Public Security Bureau， Hefei 230001， China)

Abstract: The use of data mining methods and Technology to the analysis of criminal cases，to draw between various types of criminal association rules， the public security organs for the detection of similar cases to provide an analysis of the basis for the development of criminal cases and trends predicted in advance to take relevant measures to reduce the occurrence of cases of violations.

Key words: Data mining; association rules; sequence analysis; Criminal case Database

1 背景

隨著公安信息化建設(shè)的發(fā)展，公安機(jī)關(guān)積累的大量刑事案件犯罪數(shù)據(jù)。利用數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則和序列分析等方法對(duì)犯罪信息數(shù)據(jù)進(jìn)行研判，揭示各類案件的相互關(guān)系及案件的發(fā)展趨勢(shì)，為案件的偵破以及案件的預(yù)測(cè)提供有益幫助。

2 關(guān)聯(lián)分析

關(guān)聯(lián)分析(association analysis)就是從大量的數(shù)據(jù)中發(fā)現(xiàn)項(xiàng)集之間有意義的關(guān)聯(lián)、相關(guān)關(guān)系或因果結(jié)構(gòu)以及項(xiàng)集的頻繁模式[1]。利用關(guān)聯(lián)分析對(duì)現(xiàn)有刑事案件信息數(shù)據(jù)庫中提供案件特征進(jìn)行統(tǒng)計(jì)與預(yù)測(cè)指導(dǎo)，并通過對(duì)犯罪人員特征和犯罪內(nèi)容、情節(jié)進(jìn)行挖掘以發(fā)現(xiàn)在各種犯罪活動(dòng)中存在的某些聯(lián)系，如那些類人群易于從事不法活動(dòng)，當(dāng)他們?cè)谄溽尫藕?，再犯或另外犯新的犯罪活?dòng)可能性有多大;某些犯罪分子其犯罪活動(dòng)具有哪些規(guī)律性。利用關(guān)聯(lián)挖掘方式可以了解犯罪活動(dòng)的關(guān)聯(lián)性和可能性等。

2.1 關(guān)聯(lián)算法及其改進(jìn)Apriori算法

1993年，Agrawal.R提出一種逐層搜索的迭代方法——Apriori算法[1]。它利用k-項(xiàng)集Lk來探索(k+1)-項(xiàng)集T，但該方法的存在諸多缺陷。所以，針對(duì)公安犯罪情報(bào)數(shù)據(jù)這種大信息量的情況，原Apriori算法并不適用，有必要使用其改進(jìn)方法，S.Park等人利用Hash表的方法對(duì)其加以了改進(jìn)，它作為一種AprioriTid算法的變形[3]。它的改進(jìn)之處在于[4]:

1)利用Lk，Ck中的結(jié)果對(duì)數(shù)據(jù)庫進(jìn)行篩選，減少候選集在數(shù)據(jù)庫中查找的次數(shù);

2)項(xiàng)集存儲(chǔ)使用Hash鏈表法，并將主表[5]長(zhǎng)度設(shè)置得足夠長(zhǎng)，這樣做有兩點(diǎn)好處:a)使用Hash表使得以后在新定義生成頻繁項(xiàng)集Fk無需像Aprioiri算法一樣重新掃描事務(wù)集T，以減少CPU工作量;b)主表足夠長(zhǎng)使得在訪問Ck鏈表時(shí)，不會(huì)因沖突需要繼續(xù)作沖突訪問，既減少了工作量，還使在存有頻繁項(xiàng)集itemset的Ck的Hash表中防止假頻繁項(xiàng)集False positive，簡(jiǎn)化了在對(duì)hash表中項(xiàng)集Ck支持度計(jì)數(shù)的計(jì)算過程;

3)將

4)將加入散列表的候選k-項(xiàng)集整體加入Dk的相應(yīng)事務(wù)，即事務(wù)T中包含的單位是項(xiàng)集。這樣，不僅在以后對(duì)事務(wù)中的k-項(xiàng)集進(jìn)行剪枝前無需重新組合k-項(xiàng)集，并且將剪枝前所含的k-項(xiàng)集數(shù)量盡可能的減少;程序在掃描D中，由Ck候選項(xiàng)集產(chǎn)生Lk時(shí)，對(duì)每個(gè)事務(wù)t產(chǎn)生各自所有的Tk+1，以減少Ck+1的項(xiàng)集數(shù)目;

5)改進(jìn)prune步，在Dk-1產(chǎn)生C時(shí)，先去除Lk-1中非freq_itemset，新生成頻繁項(xiàng)集Fk-1，利用Fk-1再生成Ck，以減少子迭代。

3 PHP(Phase Hashing Program)算法關(guān)聯(lián)過程

從刑事案件信息數(shù)據(jù)庫中抽取所有罪犯的犯罪項(xiàng)目，將每個(gè)罪犯的每次犯罪事實(shí)定義某個(gè)事務(wù)項(xiàng)TID計(jì)錄該次的所有犯罪事實(shí)構(gòu)成項(xiàng)目ID，以編制數(shù)組鏈表，即事務(wù)數(shù)據(jù)庫[3]，以案件事務(wù)數(shù)據(jù)庫鏈表(表1)為例。

設(shè)最小支持度min_sup=2，由D1和F2產(chǎn)生D3時(shí)T800的情況作說明。通過查詢F2，D2中T800的2-項(xiàng)集{I3，I5}被剪去，其余2-項(xiàng)集連接可得到3-項(xiàng)集{I1，I2，I3}，{I1，I2，I5}，{I1，I3，I5}，{I2，I3，I5}，而因{I3，I5}不在F2中，故{I1，I3，I5}， {I2，I3，I5}必不頻繁，不予考慮，而將{I1，I2，I3}和{I1，I2，I5}兩個(gè)項(xiàng)集整個(gè)放入D3，此即改進(jìn)算法的關(guān)鍵所在。得到D3和F3后，由T800連接可產(chǎn)生4-項(xiàng)集{I1，I2，I3，15}，但其子集{I2，I3，I5}不頻繁，故不考慮{I1，I2，I3，I5}，算法結(jié)束。如關(guān)聯(lián)挖掘過程圖(圖1)。

4 關(guān)聯(lián)挖掘用于案件研判分析

以公安機(jī)關(guān)登記的案件信息數(shù)據(jù)經(jīng)過數(shù)據(jù)映射變換處理后再進(jìn)行挖掘:在得到強(qiáng)關(guān)聯(lián)規(guī)則數(shù)據(jù)表后，便可根據(jù)關(guān)聯(lián)序號(hào)將相關(guān)屢犯的犯罪分子進(jìn)行犯罪預(yù)測(cè)，分析其在出獄后指定時(shí)間內(nèi)重行進(jìn)行犯罪活動(dòng)的可能性有多大，以便為預(yù)防犯罪分子重行犯罪提供幫助。通過該方法我們不僅可以發(fā)現(xiàn)新的犯罪聯(lián)系，而且發(fā)現(xiàn)關(guān)聯(lián)挖掘還可糾正一些人為認(rèn)識(shí)誤區(qū)，如通過關(guān)聯(lián)分析軟件發(fā)現(xiàn)，在特定條件下，犯較輕罪行的罪犯，再犯同一罪行的幾率很小，而再犯其它罪行的可能往往較大。

犯罪關(guān)聯(lián)分析的工作流程分別用關(guān)聯(lián)罪犯參數(shù)界面(圖2、圖3)和關(guān)聯(lián)分析結(jié)果界面圖(圖4)演示出來。

圖2 關(guān)聯(lián)罪犯參數(shù)界面1

圖3 關(guān)聯(lián)罪犯參數(shù)界面2

5 利用序列分析實(shí)施累犯案件分析

在利用以上算法實(shí)現(xiàn)的案件數(shù)據(jù)關(guān)聯(lián)分析時(shí)，由于受案件類型劃分類的合理性、劃分準(zhǔn)確性影響以及統(tǒng)計(jì)數(shù)據(jù)確定過程等實(shí)際情況的約束，從目前的測(cè)試結(jié)果來看，還無法達(dá)到較高的預(yù)測(cè)精度，經(jīng)常表現(xiàn)為歸類過大，甚至是歸類失當(dāng)，影響DSS人員判斷。另一方面，關(guān)聯(lián)挖掘時(shí)建立在相關(guān)項(xiàng)集具有關(guān)聯(lián)的概率運(yùn)算基礎(chǔ)上，初步給定的最小支持度的初始值具有很大的主觀性，勢(shì)必造成分析結(jié)果的模糊性。以上分析結(jié)果構(gòu)成的關(guān)聯(lián)項(xiàng)集會(huì)導(dǎo)致交叉犯罪分析內(nèi)容過大，甚至出現(xiàn)混亂，造成DSS分析軟件的低效性。目前，為提高預(yù)測(cè)準(zhǔn)確性，很多采用神經(jīng)網(wǎng)絡(luò)的算法，但它需要借助大量的反饋權(quán)值，以實(shí)現(xiàn)預(yù)測(cè)結(jié)果的輸出，而在預(yù)測(cè)分析中，面對(duì)大量的犯罪數(shù)據(jù)，需要決定大量有效的權(quán)值[6]，同時(shí)，權(quán)值的使用還有一定的實(shí)時(shí)性，作為實(shí)用的DSS分析軟件，要求盡量減少人工參與，因此，為提高預(yù)測(cè)準(zhǔn)確性，還有必要引入序列分析的方法，利用序列模式挖掘?qū)υ紨?shù)據(jù)進(jìn)行過濾來加強(qiáng)關(guān)聯(lián)預(yù)測(cè)效能，從而提高了預(yù)測(cè)正確率，更有效地實(shí)施犯罪案件的研判分析。

5.1 序列分析說明

以最簡(jiǎn)單的序列分析為例:假設(shè)某罪犯(criminal_id)在某時(shí)間(犯罪時(shí)間:guilty_time)進(jìn)行犯罪活動(dòng)項(xiàng)A(items)，后來又在其釋放后重行犯罪(犯罪時(shí)間:guilty_time)從事犯罪活動(dòng)項(xiàng)B(items)，則刑事案件信息記錄表(表2)。

將案件信息數(shù)據(jù)構(gòu)成序列，有以下定義[7]:

給定一個(gè)案件事務(wù)的數(shù)據(jù)庫D，每個(gè)事務(wù)都包含:customer_id、事務(wù)發(fā)生時(shí)guilty_time以及在事務(wù)中的犯罪犯罪criminal_id。在同一時(shí)間不存在一個(gè)罪犯多于兩個(gè)以上的事務(wù)發(fā)生 ，目前只考慮犯罪項(xiàng)目。一個(gè)項(xiàng)目集itemset是一個(gè)非空的犯罪項(xiàng)目的集合。一個(gè)序列Sequence是有序的 若干個(gè)項(xiàng)目集組成的隊(duì)列，可以將項(xiàng)目集映射到一個(gè)連續(xù)的整數(shù)集。將項(xiàng)目集i定義:i=(i1，i2，…，im)，ij表示為某個(gè)項(xiàng)是一個(gè)產(chǎn)品。定義一個(gè)序列s=，其中sj是一個(gè)項(xiàng)目集。一個(gè)序列a屬于另一個(gè)序列b，如果存在整數(shù)i1。

如果一個(gè)序列s被包含于一個(gè)罪犯的罪犯序列criminal_seq中，則稱該罪犯支持序列s。一個(gè)序列的支持度定義為支持該序列的罪犯數(shù)與總罪犯數(shù)之比。序列的長(zhǎng)度是序列中項(xiàng)目集的個(gè)數(shù)，一個(gè)長(zhǎng)度為k的序列稱為k-sequence。給定一個(gè)案件事務(wù)的數(shù)據(jù)庫D，序列模式的數(shù)據(jù)挖掘問題就是在所有由一個(gè)用戶指定的最小支持度的序列中發(fā)現(xiàn)最大的序列，每個(gè)這種最大的序列代表一個(gè)序列模式(Sequence Pattern)。我們稱滿足最小支持度限制的一個(gè)序列是一個(gè)大序列(large Sequence)。

5.2 序列分析實(shí)現(xiàn)

下面介紹支持長(zhǎng)度為2的序列模式的挖掘過程[8]:

5.2.1排序階段(Ordering Phase)

數(shù)據(jù)庫以罪犯號(hào)(criminal_id)為主鍵(primary key)，犯罪時(shí)間(guilty_time)為次鍵(secondary key)進(jìn)行排序。實(shí)際上這個(gè)階段將原來的犯罪數(shù)據(jù)庫(crime.db)轉(zhuǎn)換成由罪犯序列組成的數(shù)據(jù)庫。上述數(shù)據(jù)庫的罪犯序列視圖如表3所示。

5.2.2 大項(xiàng)集階段(Large_itemset Phase)

這個(gè)階段找出所有大項(xiàng)集組成的集合。同時(shí)也得到所有大L-序列組成的集合，然后將大項(xiàng)集映射成連續(xù)的整數(shù)(Mapping Integer)。在表3給出的數(shù)據(jù)庫中，對(duì)最小支持2個(gè)罪犯的情況下，大項(xiàng)集分別是(a0003)，(b0007)，(e0001)，(a0001，b0007)。再由表4給出了一個(gè)映射對(duì)應(yīng)數(shù)據(jù)表。

5.2.3 轉(zhuǎn)換階段(Alteration Phase)

用每次犯罪所包含的所有大項(xiàng)集取代該犯罪記錄。如果一個(gè)犯罪不包含任何大項(xiàng)集，在轉(zhuǎn)換完成的序列中它將不被保留。而如果一個(gè)罪犯序列不包含任何大項(xiàng)集，在轉(zhuǎn)換好的數(shù)據(jù)庫中這個(gè)序列也將不復(fù)存在。之后，將原來的罪犯序列轉(zhuǎn)換為若干長(zhǎng)度為2的序列模式，其中，取序列時(shí)間之間的間隔n=date interval≤6(年)，時(shí)間間隔n>6(年)的大項(xiàng)集不出現(xiàn)在序列中。設(shè)一個(gè)最小序列支持長(zhǎng)度為2，則形成一個(gè)轉(zhuǎn)換好的數(shù)據(jù)庫。

5.2.4 序列挖掘階段(Sequential Mining Phase)

利用AprioriAll算法找出所有已知序列內(nèi)的所有最高項(xiàng)集:

以表3為例，長(zhǎng)度為2的序列模式:L2={large 2-sequuence}={<1，2>，，<1，4>，<2，3>，<2，4>，<3，4>}，最小支持度:min_support=0.25，則可生成下表5所得支持計(jì)數(shù)。

序列模式挖掘得到序列模式后，可將滿足某一序列模式的部分或全部罪犯作為犯罪項(xiàng)A后又實(shí)施犯罪項(xiàng)的訓(xùn)練測(cè)試樣本，將罪犯實(shí)施犯罪項(xiàng)A后5年內(nèi)未重新犯罪項(xiàng)B的部分或全部罪犯作為另一部分訓(xùn)練測(cè)試樣本，于是將其它具有犯罪項(xiàng)A尚不到5年的罪犯作為待預(yù)測(cè)樣本，并進(jìn)行犯罪項(xiàng)B的產(chǎn)生可能預(yù)測(cè)，從而得到犯罪數(shù)據(jù)之間的規(guī)則，為以后的犯罪分析提供有益幫助。

6 小結(jié)

為提高刑事案件的破案率和偵破的過程中提供有效手段，首先使用關(guān)聯(lián)挖掘算法進(jìn)行案件分析，可以在通常情況下發(fā)現(xiàn)關(guān)聯(lián)犯罪項(xiàng)目的內(nèi)在聯(lián)系，及時(shí)為分析決策人員找到案件數(shù)據(jù)的統(tǒng)計(jì)依據(jù)。本文通過改進(jìn)的Apriori算法，有效地提高了傳統(tǒng)的關(guān)聯(lián)算法的算法效率，縮短了頻繁項(xiàng)集的計(jì)算周期，加快了規(guī)則庫的的生成速度，為解決在大型數(shù)據(jù)庫中實(shí)現(xiàn)項(xiàng)集快速歸類開辟了新的道路。

但是，在實(shí)施過程中發(fā)現(xiàn)，其關(guān)聯(lián)挖掘在交叉案件分析過程中受概率因素，劃分項(xiàng)集等一系列因素影響，還無法取得令人足夠滿意的分析精度，更重要的是案件分析系統(tǒng)還需要能夠有為分析人員提供罪犯在一定時(shí)間周期內(nèi)，實(shí)現(xiàn)有關(guān)犯罪案件可能性預(yù)測(cè)的能力，從而，為分析決策人員進(jìn)行偵查分析和案情研判提供幫助，而不是簡(jiǎn)單的業(yè)務(wù)總結(jié)，因此，又引入序列挖掘的方式為交叉分析提供預(yù)測(cè)訓(xùn)練樣本進(jìn)行過濾和排序，尋找罪犯可能在實(shí)施犯罪的趨勢(shì)，真正實(shí)現(xiàn)為公安偵查管理分析進(jìn)行預(yù)測(cè)的功能。本文只是選取部分刑事案件信息數(shù)據(jù)利用關(guān)聯(lián)規(guī)則和序列分析等方法進(jìn)行分析研究，研究的深度不夠，得出的規(guī)則也很有限，但為公安機(jī)關(guān)大量刑事案件信息數(shù)據(jù)的研判提出了有益地探索。

參考文獻(xiàn):

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

[2] 梁世紅.數(shù)據(jù)挖掘在CRM中的應(yīng)用[J].科技情報(bào)開發(fā)與經(jīng)濟(jì)，2003，13(1).

[3] Mannila H，Toivonen H，Verkamo A.Efficient algorithm for discovering association rules[C].AAAI Workshop on Knowledge Discovery in Databases，1994:181-192.

[4] Toivonen H.Sampling large databases for association rules[C].Bombay，India:Proceedings of the 22nd International Conference on Very Large Database，1996.

[5] Park S，Chen M S，Yu P S.An effective hash-based algorithm for mining association rules[C].San Jose，CA:Proceedings of ACM SIGMOD International Conference on Management of Data，1995:175-186.

[6] 聞新.Matlab 神經(jīng)網(wǎng)絡(luò)技術(shù)應(yīng)用技巧集[M].北京:科學(xué)出版社，2001.

[7] 序列模式挖掘[EB/OL].Shemy5204，http://www.dmresearch.net/bbs/viewthread.php? tid=3437extra=page%3D5.

[8] Agrawal R，Srikant R.Mining Sequential Paterns[M].IBM Research Center，1995.

[9] 錢江波，陳珺，等.犯罪分析決策樹的構(gòu)造方法[J].警察技術(shù)，2004(2):8-11.