基于支持度矩陣的關(guān)聯(lián)規(guī)則挖掘算法在公安情報分析中的應(yīng)用*

李為 王池 重慶市公安局巴南分局

基于支持度矩陣的關(guān)聯(lián)規(guī)則挖掘算法在公安情報分析中的應(yīng)用*

李為 王池 重慶市公安局巴南分局

將關(guān)聯(lián)規(guī)則算法引入公安情報的數(shù)據(jù)挖掘中，以求發(fā)現(xiàn)情報信息中的相關(guān)規(guī)律，提高執(zhí)法效率與快速反應(yīng)能力，并及時預(yù)防和打擊犯罪行為。由于關(guān)聯(lián)規(guī)則Apriori算法存在多次掃描數(shù)據(jù)庫并且時間性能較低的缺陷，提出了一種基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法。該算法通過對矩陣操作，只需掃描數(shù)據(jù)庫一次，就能一次產(chǎn)生所有頻繁項集，大大減少了計算項集的工作，有效提高了挖掘效率。

數(shù)據(jù)挖掘 頻繁項集 支持度矩陣 Apriori算法

一、引言

隨著現(xiàn)代科學(xué)技術(shù)的發(fā)展、科技強警的不斷推進，全國公安機關(guān)依托“金盾工程”進行了一場公安信息化的現(xiàn)代警務(wù)新變革，公安信息化系統(tǒng)建設(shè)已成為打擊違法犯罪活動的有力工具，但在實際工作中收集和積累的海量社會信息和數(shù)據(jù)信息越來越多、數(shù)據(jù)規(guī)模日益增大、復(fù)雜程度不斷增加已成為公安信息系統(tǒng)處理的難題[1]。為了適應(yīng)信息動態(tài)管理，如何從這些蘊涵大量有用情報的信息數(shù)據(jù)中及時發(fā)現(xiàn)、總結(jié)各種犯罪的規(guī)律性、最新規(guī)則以及社會治安的變化特點，以制定有利于社會穩(wěn)定和發(fā)展的決策，提高執(zhí)法效率與快速反應(yīng)能力，及時預(yù)防和打擊犯罪行為，并采取相應(yīng)的措施顯得越來越重要。將數(shù)據(jù)挖掘技術(shù)應(yīng)用于公安情報分析，能夠為公安部門提供各種決策信息以及解決方案，大大提高決策的質(zhì)量和效率，已成為當(dāng)前公安工作中亟需進一步研究解決的問題，也是公安信息化建設(shè)進一步發(fā)展的方向。

在絕大多數(shù)犯罪活動中，犯罪活動之間或內(nèi)部擁有錯綜復(fù)雜的聯(lián)系，犯罪數(shù)據(jù)挖掘得到了很大關(guān)注，各種數(shù)據(jù)挖掘技術(shù)的研究為社會安全提供了幫助[2]?，F(xiàn)有關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法[3]已不太適應(yīng)當(dāng)前公安信息系統(tǒng)的發(fā)展。針對在關(guān)聯(lián)規(guī)則挖掘中如何高效挖掘頻繁項集，本文提出了生成支持度矩陣并利用矩陣?yán)碚摰念l繁項集挖掘算法。該算法通過對矩陣操作，只需掃描數(shù)據(jù)庫一次，就能一次產(chǎn)生所有頻繁項集，大大減少了計算項集的工作，有效提高了挖掘效率。

二、基于矩陣的關(guān)聯(lián)規(guī)則信息挖掘高效算法

（一）關(guān)聯(lián)規(guī)則的基本概念及定義

關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中數(shù)據(jù)項之間存在的潛在關(guān)系的規(guī)則，即反映一個事物與其它事物之間的相互依存性和關(guān)聯(lián)性。問題可以描述如下[4]：I={i1,i2,...,im}由m個不同項組成，是所有項的集合；D={T1,T2,...,Tn}由一系列具有唯一標(biāo)識TID的事物組成，是所有事物的集合。每個事物T由I中的若干項組成，是I的子集，記為T={t1,t2,...tn}，t1I。若X、Y是數(shù)據(jù)項集，X中含有的項數(shù)目為k，則稱為k-項集。事物集D中的關(guān)聯(lián)規(guī)則表示為蘊涵式X Y，且X I，Y I，X∩Y=φ，X為規(guī)則的前提，Y是結(jié)果。

給定一個事物集D，挖掘關(guān)聯(lián)規(guī)則就是產(chǎn)生支持度和置信度分別大于用戶給定的最小支持度（min_supp）和最小置信度（min_conf）的關(guān)聯(lián)規(guī)則。當(dāng)規(guī)則的置信度和支持度分別大于min_supp、min_conf時，我們認(rèn)為規(guī)則是有效的，稱為強關(guān)聯(lián)規(guī)則。當(dāng)數(shù)據(jù)項集X的支持度大于min_supp時，稱X為高頻數(shù)據(jù)項集。

定義1項的向量表示：

Ii則項Ii相應(yīng)的支持度表示為

cup_count[Ii]=（Ii表示項，j表示事物標(biāo)號）。

定義2項集I的矩陣記為：

定義3k-項集的支持度計數(shù)：

定義4關(guān)聯(lián)規(guī)則的置信度：

性質(zhì)1一個頻繁項集的任一子集必定是頻繁項集。

性質(zhì)2一個非頻繁項集的任一超集也是非頻繁項集。

（二）基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法

算法的具體實現(xiàn)過程描述如下：

1. 把事物數(shù)據(jù)庫構(gòu)造成矩陣，求頻繁1-項集

對給定的事務(wù)數(shù)據(jù)庫D，根據(jù)定義2構(gòu)造矩陣M1。以事物表示成行向量，項表示成列向量，若第i個事物中包含了第j個項，則矩陣的第i行第j列的值為1，否則值為0。該矩陣中的每一個位置在內(nèi)存中僅占一位。

對該矩陣各列向量掃描，根據(jù)定義1，由矩陣的各列數(shù)字和就可以得到支持度計數(shù)。當(dāng)支持度計數(shù)sup_count[Ii]>min_supp，則Ii為頻繁項，將該項加入頻繁1-項集L1中。否則Ii非頻繁項集，將其從事務(wù)矩陣中刪除。

2. 構(gòu)造二項集的支持度矩陣，快速找出頻繁2-項集

由頻繁1-項集構(gòu)造|L1|階2-項集支持度矩陣M2，此矩陣為對稱矩陣。根據(jù)定義3，依次求出矩陣中各元素對應(yīng)的2-項集支持度計數(shù)。當(dāng)M2[i,j]=mis_supp(imin_supp，則M2[i,j]為頻繁項，將該項加入頻繁2-項集L2中。否則M2[i,j]為非頻繁項集，不加入頻繁項集中。

3. 利用支持度矩陣，尋找所有頻繁項目集

對于每個候選k（k≥3）項集X，從X在Ck之后的位置中查找以X后k-1個項開始的其它候選k項集，若找到這樣一個候選k項集Y，則把X的第一個項Ir和Y的最后一個項Is的標(biāo)號連接形成矩陣坐標(biāo)[r,s]，到矩陣M2中查找這個坐標(biāo)上的值是否大于最小支持度計數(shù)min_supp，如果大于或等于，則生成候選k+1項集；如果不大于，則不予連接，繼續(xù)查找下一個，直到Ck中的最后一個k項集。至此候選k+1項集表構(gòu)造結(jié)束。

4. 由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則

從事物數(shù)據(jù)庫D中挖掘出所有的頻繁項集后，就可以產(chǎn)生關(guān)聯(lián)規(guī)則，即產(chǎn)生滿足最小支持度和最小置信度的強關(guān)聯(lián)規(guī)則。根據(jù)定義4中的公式，具體產(chǎn)生關(guān)聯(lián)規(guī)則的操作如下：

（1）對于找出的每個頻繁項集l，產(chǎn)生l的所有非空子集s；

（2）對于每個非空子集s，如果包含l的事務(wù)數(shù)與包含s的事務(wù)數(shù)的比值大于最小置信度，即support(l) /support(s)≥min_conf，則輸出規(guī)則“s l-s”，其中min_conf是最小置信度。

由于關(guān)聯(lián)規(guī)則是通過頻繁項集直接產(chǎn)生的，因此關(guān)聯(lián)規(guī)則所涉及的所有項集均滿足最小支持度。

（三）算法在公安情報分析中的應(yīng)用

選取少量登記在案的犯罪嫌疑人員數(shù)據(jù)，由此算法進行數(shù)據(jù)挖掘。假定T1～T10為案件編號，a～f分別為案件相關(guān)信息，則案件與事件信息之間的關(guān)系如表1所示，假設(shè)最小支持度計數(shù)為4。

?

（1）掃描數(shù)據(jù)庫，得到事物矩陣M1。

（2）構(gòu)造支持度矩陣M2。

根據(jù)定義3，依次求出M2[i,j](i

?

把M2中元素與最小支持度min_supp=4比較，得到頻繁2-項集L2={{a，b}，{b，c}，{a，c}，{c，e}，{b，e}，{e，f}，{c，f}，{b，f}，{a，f}}。

（3）對a行的二項集進行掃描，發(fā)現(xiàn)二項集{a，b}大于最小支持度，于是轉(zhuǎn)到b行，搜索b行中大于最小支持度計數(shù)的二項集，得到{b，c}，{b，e}，{b，f}。然后定位到矩陣[a，c][a，e][a，f]，發(fā)現(xiàn)M2[a,e]k，則{a，b，f}一定不是頻繁3-項集。然后繼續(xù)對a行后面的頻繁二項集進行查找工作，當(dāng)a行搜索完畢后，對后面的行進行掃描。用此方法依次搜索，可求出頻繁3-項集L3={{b，c，e}，{b，e，f}，{c，e，f}，{a，c，f}，{b，c，f}，{a，b，f}}。

（4）發(fā)現(xiàn)候選4-項集以及更高維的k項集，對于三項集{b，c，e}，從它的位置之后在C3中查找以{c，e} 開頭的其它三項集，發(fā)現(xiàn)符合條件的三項集{c，e，f}，于是定位到矩陣坐標(biāo)[b，f]中，發(fā)現(xiàn){b，f} 是頻繁2-項集。于是生成候選四項集{b，c，e，f}，此時已不能再生成其它候選四項集以及更高維的k項集，生成k項集表的連接剪枝過程至此結(jié)束。L4為{{b，c，e，f}}。

三、實驗結(jié)果分析

（一）與Apriori算法的比較

1. 時間復(fù)雜性

Apriori算法是逐層搜索的迭代算法，通過頻繁（k-1） -項集搜索頻繁k-項集。其時間復(fù)雜度為其中xx為交易事務(wù)數(shù)據(jù)庫中包含的交易數(shù)量，k為頻繁項集大小。Apriori算法在挖掘每一層中所包含的頻繁項目集時都需要進行一次數(shù)據(jù)庫掃描，來獲得候選項集的支持度。而且在發(fā)現(xiàn)頻繁項目集的過程中，產(chǎn)生了大量的候選項目集。當(dāng)遇到海量數(shù)據(jù)庫時，耗時太長，難以滿足實際應(yīng)用的需求。同時Apriori算法的效率不高，利用頻繁（k-1）-項集連接產(chǎn)生候選k-項集，判斷連接條件時重復(fù)次數(shù)太多[5]。

而本文算法中只需要一次掃描數(shù)據(jù)庫得出事務(wù)矩陣，并求出支持度，構(gòu)造二項集的支持度矩陣。根據(jù)支持度矩陣的性質(zhì)產(chǎn)生頻繁k-項集。利用矩陣可以更方便地處理數(shù)據(jù)，減少候選項集的生成，大大地提高了挖掘關(guān)聯(lián)規(guī)則的效率，并且基于矩陣的算法也便于在實際應(yīng)用中被實現(xiàn)和理解。

2. 空間復(fù)雜性

Apriori算法會產(chǎn)生大量的候選項集，并且所有具有相同長度的候選項集必須被存儲在內(nèi)存中，這將會占用大量的內(nèi)存空間，導(dǎo)致內(nèi)存不停地?fù)Q進換出操作。而本文算法采用矩陣進行存儲，大量減少所需的I/O次數(shù)，減小了存儲空間，不需要在內(nèi)存中存儲所有的候選項集，具有良好的空間特性。

（二）實驗結(jié)果分析

為了對算法的優(yōu)勢進行驗證，將其進行實驗驗證。在Inter(R) Core(TM) i3 CPU 2.27GHz，4.00GB內(nèi)存，Windows 7 64Bit操作系統(tǒng)的實驗環(huán)境下，算法采用Java語言實現(xiàn)。實驗數(shù)據(jù)采用T40I10D100K，將本文所述的優(yōu)化算法與Apriori算法進行比較。圖1是在最小支持度不同時，挖掘所有頻繁項集執(zhí)行時間的區(qū)別。由圖1可知，Apriori算法當(dāng)支持度減少時，耗費的時間會增大，而本文算法受最小支持度的影響較小；并且當(dāng)最小支持度越小時，優(yōu)化后算法的執(zhí)行時間比Apriori算法的執(zhí)行時間少得越多，這說明優(yōu)化后的算法在給出支持度較小時具有較高的執(zhí)行效率。

圖2給出了當(dāng)數(shù)據(jù)庫中事務(wù)記錄數(shù)不同時兩種算法執(zhí)行時間的區(qū)別。由圖2可知，兩種算法執(zhí)行時間都會呈上升趨勢，但當(dāng)事物記錄適當(dāng)大時，優(yōu)化后算法的效率比Apriori算法的效率要高一些，這說明優(yōu)化后的算法在所給數(shù)據(jù)庫中記錄較大時具有較高的執(zhí)行效率。

四、結(jié)束語

關(guān)聯(lián)分析是數(shù)據(jù)挖掘技術(shù)的一個重要的應(yīng)用?；诮?jīng)典的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法Apriori算法的研究，提出了改進的基于支持度矩陣的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法：該算法僅掃描數(shù)據(jù)庫一次，把結(jié)果存儲到矩陣中，節(jié)省了大量的內(nèi)存空間，并通過矩陣運算來計算項的支持度計數(shù)，并生產(chǎn)支持度矩陣來產(chǎn)生頻繁項集。將該算法應(yīng)用到公安情報分析領(lǐng)域的規(guī)則發(fā)現(xiàn)中，通過對案件信息的一些強關(guān)聯(lián)規(guī)則的挖掘，為公安偵破工作提供依據(jù)，提高了決策的質(zhì)量和效率。

[1] 趙偉.數(shù)據(jù)挖掘技術(shù)在公安預(yù)測預(yù)警中的應(yīng)用[J].警察技術(shù),2009,9:56-58.

[2] Chen H,Chung W,Jie J,et al.Crime Data Mining:A General Framework and Some Examples[J].The IEEE Computer Society,2004.

[3] Patel Nimisha R,Sheetal Mehta.A Survey on Mining Algorithms[J].International Journal of Soft Computering and Engineering(IJSCE),2013.

[4] Jiawei Han, Micheline Kamber. 數(shù)據(jù)挖掘概念與技術(shù)[M].機械工業(yè)出版社,2001.

[5] 倪堅.對Apriori算法的一個改進[J].大連交通大學(xué)學(xué)

公安理論及軟科學(xué)研究計劃（編號：20125000000000871）