盧　睿

(遼寧警察學院公安信息系, 遼寧大連　116036)

刑事案件的屬性約簡聚類算法研究

盧睿

(遼寧警察學院公安信息系, 遼寧大連116036)

摘要為發(fā)現(xiàn)刑事案件的發(fā)案規(guī)律與特點，從而及時預防和打擊犯罪,提出了刑事案件的屬性約簡K-means聚類算法。該算法應用粗糙集的屬性約簡算法消除冗余屬性，利用各屬性的重要度確定其權值，并在此基礎上以改進的K-means聚類算法進行聚類分析。最后應用某地區(qū)刑事案件相關數(shù)據(jù)對算法的正確性與有效性進行了驗證，實驗表明該方法的優(yōu)勢在于降低了數(shù)據(jù)規(guī)模，并獲得較高且穩(wěn)定的準確率。

關鍵詞粗糙集； 屬性約簡； 屬性重要度； 聚類； 刑事案件分析

0引言

公安機關積累了大量犯罪數(shù)據(jù)，為避免出現(xiàn)“數(shù)據(jù)豐富，知識貧乏”的現(xiàn)象，如何利用這些犯罪數(shù)據(jù)是公安機關迫切需要研究的課題。利用數(shù)據(jù)挖掘方法對公安機關積累的海量犯罪數(shù)據(jù)進行深入研究, 可以發(fā)現(xiàn)刑事案件中相似案件的發(fā)展趨勢,探尋犯罪的規(guī)律與特點,對及時預防與打擊犯罪行為具有重要的理論和現(xiàn)實意義。貝葉斯網(wǎng)絡、粗糙集方法、決策樹和神經(jīng)網(wǎng)絡等數(shù)據(jù)挖掘方法在零售業(yè)、保險業(yè)、制造業(yè)、電信、醫(yī)學等領域得到了較好的應用，但在公安情報工作的研究中尚處于起步階段，尤其是對公安系統(tǒng)刑事案件的偵查決策方面的深入應用還較少見[1-2]。

傳統(tǒng)的K-means算法因具有高效快速的聚類效果而被廣泛應用。但是傳統(tǒng)的K-means算法也存在局限性：只能處理離散的數(shù)值型數(shù)據(jù)，不能很好地處理符號型數(shù)據(jù)以及連續(xù)型數(shù)據(jù)，對孤立點、噪聲數(shù)據(jù)的處理效率較低，因而限制了K-means算法的應用范圍；對于高維數(shù)據(jù)，K-means算法的正確性較低，所需時間大大增加；同等重要地看待每個屬性，因此容易陷入“維數(shù)陷阱”[3]；K-means算法得到的不是全局最優(yōu)解，而是局部最優(yōu)解。

針對K-means算法的以上不足，本文提出屬性約簡的刑事案件聚類算法，其核心思想是利用粗糙集中的屬性約簡理論去除冗余屬性，并根據(jù)每個約簡屬性的重要度對屬性賦予不同的權值，然后利用改進的K-means算法對刑事案件數(shù)據(jù)進行聚類分析。

1相關理論

粗糙集理論最早是由波蘭的Z.Pawlak教授于20世紀80年代初提出，是一種研究不精確和不確定性知識的數(shù)學工具，在數(shù)據(jù)挖掘領域得到了成功應用。屬性約簡是粗糙集知識發(fā)現(xiàn)的核心內(nèi)容之一，它描述了信息系統(tǒng)屬性集中每個屬性是否是必要的，以及如何刪除不必要的知識。高效的屬性約簡算法是知識發(fā)現(xiàn)的基礎，但研究表明求解屬性的最小約簡是NP-hard問題，因此要在有限的時間內(nèi)獲得約簡，通常采用基于啟發(fā)式知識的約簡方法。作為一種信息量判斷的手段，屬性重要度度量了屬性對信息系統(tǒng)的分類能力?；趯傩灾匾鹊募s簡算法以屬性重要度作為啟發(fā)信息,從而找到信息系統(tǒng)的某一個約簡，此約簡是最優(yōu)解或次優(yōu)解。

1.1　粗糙集理論[4]

定義1信息系統(tǒng)可用四元組S=(U,A,V,f)表示，其中：U={x1,x2,…,xn}表示研究對象的集合，即論域；A=C∪D，A是屬性的集合，C表示條件屬性集，D表示決策屬性集；V=∪va，?a∈A，va表示屬性的值域；f=U×A→V是信息函數(shù)，對x∈U，a∈A有f(x,a)∈va。

定義2等價關系IND(B)={(x,y)∈U×U:?b∈B,b(x)=b(y)}，其中B?A，x,y∈U，稱x和y關于B是不可分辨的。

定義4給定一個知識庫K=(U,S)和知識庫中的一個等價關系族P?S，?R∈P，若IND(P)=IND(p-{R})成立，則稱知識R為P中必要的，P中所有必要的知識組成的集合稱P的核，記為CORE(P)。可以證明核是所有約簡的交集，且核具有唯一性。

定義5給定一個知識庫K=(U,S)和知識庫中的一個等價關系族P?S，對任意的G?P，若G滿足以下兩條：(1)G是獨立的；(2)IND(G)=IND(P),則稱G是P的一個約簡，記為G∈RED(P)，其中RED(P)表示P的全體約簡的集合。

屬性約簡是不含多余屬性并保證分類正確的最小條件屬性集，一般而言，屬性的約簡是不唯一的。

1.2　K-means聚類算法

利用K-means聚類算法對刑事案件數(shù)據(jù)進行分析研究，其主要工作是將詳細記錄加以整理歸類，對刑事案件的內(nèi)容、情節(jié)等進行挖掘, 把具有相似特征的案件從海量數(shù)據(jù)庫分中揀出來，單獨形成特征類型數(shù)據(jù)庫，即類案數(shù)據(jù)庫。找出每一類案件中大部分犯罪含有的特征信息，根據(jù)不同分類，將犯罪特征應用到該類其它案件的偵破中去，為犯罪案件的串并及破案提供有益幫助[5]。

2刑事案件的屬性約簡聚類算法

本算法的核心思想是利用粗糙集中的屬性約簡理論去除冗余屬性，并根據(jù)每個約簡屬性的重要度對賦予其不同的權值，再利用改進的K-means算法進行聚類分析，分析描述如下。

(1)在改進的算法中, 首先利用粗糙集對數(shù)據(jù)對象進行預處理。在公安刑事案件源數(shù)據(jù)庫中，很多記錄不完整、不一致，還有一些錯誤的信息，因此在預處理階段要清理所有聚類分析的相關屬性值。對于空值和不一致數(shù)據(jù)，可以采取忽略元組、人工填寫及填充均值等方法進行處理。在數(shù)據(jù)大致完整后，將案件屬性值根據(jù)其類型定義為二值變量、整型變量和區(qū)間型變量, 使其轉(zhuǎn)化為K-means算法應用條件中離散的數(shù)值型數(shù)據(jù),從而有利于算法的實現(xiàn)[6]。

(2)刑事案件數(shù)據(jù)的某些冗余屬性和干擾屬性與犯罪傾向的關聯(lián)性小，保留它們會增加聚類算法的復雜度，結果準確率也較低。本算法中利用粗糙集的屬性約簡算法刪除了冗余屬性，降低了運算時間，并賦予各屬性不同的權值，使不同的屬性發(fā)揮不同的作用，使聚類結果更具客觀性，更符合公安情報分析的實際需要。

根據(jù)以上分析，該算法的主要步驟描述如下：

輸入：信息系統(tǒng)S=(U,A,V,f)和簇數(shù)k

輸出：簇集N={N1,N2,…,Nk}

Step1：設R=?；

Step2：?a∈A，如果IND(A{a})≠IND(A)，R?R∪{a}，CORE(A)=R；

Step3：令B=CORE(A)，如果IND(B)=IND(A)，輸出B∈RED(A)，轉(zhuǎn)Step5，否則轉(zhuǎn)Step4；

Step5: 取約簡后的樣本數(shù)據(jù)集X={x1,x2,…,xm}，計算X中每個屬性對應的wi，隨機選擇k個樣本作為初始聚類中心；

Step6：數(shù)據(jù)集X中剩下的其他樣本點，根據(jù)樣本點與初始聚類中心的距離，分別將它們分配給與其最相似的中心所在的類別；

Step7：計算每個新類的聚類中心；

Step8：不斷重復Step6和Step7，直到所有樣本點的分布不再改變或類中心不再改變，即直到加權距離d(xk,ci)值不再變化為止。

圖1　屬性約簡后重要性百分比

對一個大小為n的數(shù)據(jù)集, 指定的聚類數(shù)為k，d是數(shù)據(jù)對象的屬性個數(shù)，則一次迭代的時間耗費由三部分組成: 將每一個數(shù)據(jù)對象歸到離它最近的聚類中心所在的類，需要時間O(ndk)；新類產(chǎn)生以后計算新的聚類中心所需的時間O(nd)；計算聚類準則函數(shù)值所需時間O(nd)。 而迭代次數(shù)則由數(shù)據(jù)集大小、聚類數(shù)以及數(shù)據(jù)分布情況決定，算法總的時間復雜度為O(ndk)。由于在決策分類能力不變的情況下對條件屬性進行了適當?shù)募s簡，因此算法具有較好的時間和空間特性。

3實驗分析

從刑事案例庫中抽取200例入室搶劫案件的數(shù)據(jù)，該數(shù)據(jù)包括10個屬性，分別為作案特點、作案手段、作案地點、作案工具、案件交通工具、涉案人員年齡、涉案人員性別、入侵方式、涉案人員職業(yè)和選擇對象，如表1所示。利用本文算法對10個屬性{A1, A2, A3, A4, A5, A6, A7, A8, A9, A10}的重要性程度進行計算與約簡，得出{A1, A2, A6, A8, A9, A10}為重要屬性。將約簡結果中的重要屬性值分別除以其最大值處理后如圖1所示。

表1　刑事案件屬性

所抽取的200例刑事案件數(shù)據(jù)集中的60%作為訓練集，其余40%作為測試集，訓練后，訓練集中120條數(shù)據(jù)被分為5類，每類中聚合數(shù)量分別為22條、24條、45條、16條和13條。根據(jù)訓練集所得模型，對測試集中80條數(shù)據(jù)進行聚類劃分，得到前3類所占的比重偏大，如表2所示。

表2　刑事案件聚類結果

表2表明涉案人員職業(yè)與犯罪具有一定的相關關系，即在犯罪分子中，無業(yè)人員或務工農(nóng)民發(fā)生入室搶劫的概率較大，而這種現(xiàn)象與事實情況相符。

為驗證本文算法的性能，采用以上刑事案件數(shù)據(jù)，將文獻[7]的k-means算法與本文算法的結果進行比較，均采用運算10次后所得的平均殘差平方和來判斷聚類結果的準確程度，所得的平均殘差平方和數(shù)值越小，說明同一類中的距離越小，聚類的準確程度越高。

表3　刑事案件數(shù)據(jù)的算法效果比較

由表3可見，本文算法的平均殘差平方相比文獻[7]的算法具有較大優(yōu)勢，可以得到較高且穩(wěn)定的準確率，其原因去除屬性集中的冗余屬性后聚類結果變得更為清晰，而且利用粗糙集對數(shù)據(jù)進行預處理，精簡了數(shù)據(jù)結構，降低了數(shù)據(jù)規(guī)模，便于聚類算法實現(xiàn)，有利于提高聚類質(zhì)量。

為了驗證算法的準確性和一般性，從國際通用機器學習數(shù)據(jù)庫UCI選取了Iris和Wine兩組樣本數(shù)據(jù)，仍然以表3的兩類算法進行比較，所求的結果為10次運算后的準確率均值。表4的比較結果說明本文提出的算法有效地提高了聚類性能，并得到了較高的準確率。

表4　通用數(shù)據(jù)庫數(shù)據(jù)的算法效果比較

4結語

本文把粗糙集中的屬性約簡和屬性重要度思想與K-means聚類算法相結合, 提出了一種有效的改進方法，經(jīng)實驗后證明該算法符合公安犯罪分析的實際情況。在算法應用中，公安機關可從大量不同犯罪特征中找出相似點，并對具有相同特征的案件進行串并，可為公安機關對相似案件的調(diào)查偵破提供一定幫助。

參考文獻

[1]王春雨，王雪華，張旭娟，等. 刑事案件的多層關聯(lián)分析模型研究[J]. 情報學報, 2011，30(1):44-50.

[2]盧睿，米佳.互聯(lián)網(wǎng)公安情報工作標準化流程研究[J].中國人民公安大學學報:自然科學版,2012,18(4):29-32

[3]徐麗，丁世飛，郭鋒鋒. 基于改進屬性約簡的粗核聚類算法[J]. 廣西師范大學學報，2011,29(3):105-109.

[4]Pang Ping Tan. 數(shù)據(jù)挖掘?qū)д揫M]. 北京：人民郵電出版社，2011.

[5]張揚，陳亮，張番棟. 一種基于聚類的情報分析程序的設計與實現(xiàn)[J]. 情報學報, 2013, 32(8):27-30.

[6]夏穎，王哲，程琳. 聚類分析在犯罪數(shù)據(jù)分析中的應用[J], 合肥工業(yè)大學學報，2009, 32(12):1924-1927.

[7]KRISHNAMUTHY R, KUMAR J S. Survey of data mining techniques on crime data analysis[J]. International Journal of Data Mining Techniques and Applications, 2012, 1(2):117-120.

(責任編輯陳小明)

作者簡介盧睿(1978—)，女，遼寧大連人，講師,博士。

基金項目本文為公安部軟科學項目(2011LLYJLNST049)和遼寧省高等學校優(yōu)秀人才支持計劃(LJQ2011132)的階段性研究成果。

中圖分類號D918.2