基于圖模式的犯罪情報數(shù)據(jù)集挖掘算法

唐德權(quán)， 史偉奇， 劉緒崇

(湖南警察學(xué)院信息技術(shù)系， 湖南長沙 410138)

0 引言

圖是表示復(fù)雜數(shù)據(jù)的常用方法，挖掘重復(fù)子圖有許多應(yīng)用，如在化學(xué)信息、生物信息、高效存儲半結(jié)構(gòu)化數(shù)據(jù)庫、高效索引和web信息管理領(lǐng)域模式發(fā)現(xiàn)[1]。在圖數(shù)據(jù)庫中如何高效挖掘處理大量重復(fù)出現(xiàn)的模式，基于不同的需求和期望找出頻繁子圖是目前圖模式挖掘研究的一個重要問題。例如，為了應(yīng)對挖掘大型網(wǎng)絡(luò)中的集團的挑戰(zhàn)，Shahrivari等人[2]提出了基于狀態(tài)空間搜索的完全適合MapReduce框架的解決方案KCminer。大多數(shù)現(xiàn)有的帶標(biāo)記網(wǎng)絡(luò)社團檢測算法都是為了給網(wǎng)絡(luò)提供一個固定分區(qū)，其中任何節(jié)點都應(yīng)該屬于一個社團。為了改進已有的聚類算法，Qi等人[3]提出了一種新的有符號網(wǎng)絡(luò)聚類方法，即有符號真子團合并算法SQCM，該算法對網(wǎng)絡(luò)中的重疊社區(qū)推斷出某個節(jié)點屬于哪些社區(qū)，并隨機得到一個聚類，但聚類數(shù)量不能確定，因此SQCM不能精確計算子團結(jié)構(gòu)，但是面臨頻繁子模式的總數(shù)量以指數(shù)形式增長，這些方法通常不能高效應(yīng)對圖數(shù)據(jù)集挖掘。

由于圖能表示犯罪情報數(shù)據(jù)復(fù)雜結(jié)構(gòu)，如何在圖數(shù)據(jù)集中挖掘頻率較高“公共子結(jié)構(gòu)”已經(jīng)成為警務(wù)數(shù)據(jù)挖掘研究領(lǐng)域重要問題之一[4]。針對犯罪情報數(shù)據(jù)集的特點和頻繁子模式挖掘所面臨的挑戰(zhàn)[5]，本文提出了一種基于k個頂點類的頻繁模式挖掘算法，簡稱為k-頻繁模式挖掘算法。該算法有效挖掘k-頻繁模式，首先將圖數(shù)據(jù)集預(yù)處理找出k個頂點的頻繁子圖類，然后找出其所有生成子圖，最后挖掘頻繁模式，算法的總時間復(fù)雜度為O(2nT4logTk2)，其中n為圖的頂點數(shù)，T為圖數(shù)據(jù)集大小，k為頻繁子結(jié)構(gòu)圖頂點個數(shù)(2≤k≤n)。通過真實平臺數(shù)據(jù)集實驗表明，該算法能根據(jù)嫌疑人員的特點高效的挖掘關(guān)聯(lián)模式和規(guī)律，為靶向推進個案、類案精準(zhǔn)偵辦和處置提供決策依據(jù)。

1 定義、記號與問題描述

標(biāo)簽圖G是一個無向連通圖，定義為4元組G=(V,E,Σ,l)，其中V是圖G的頂點集，E?V×V是圖G的邊集，Σ是由數(shù)字或字母組成的具有偏序關(guān)系的標(biāo)號集，l是頂點和邊到標(biāo)號集的映射函數(shù)，即l：V∪E→Σ。具有T個標(biāo)簽圖組成的數(shù)據(jù)集稱為標(biāo)簽圖數(shù)據(jù)集，記為GD={G1,G2,…,GT}，數(shù)據(jù)集GD的大小為T，記為|GD|=T。

如果一個標(biāo)簽圖G=(V,E,L,l)與另一個圖G′=(V′,E′,L′,l′)同構(gòu)，則f:V(G)→V(G′)，且同時滿足：

(1)?u∈V,l(u)=l′(f(u))；

(2)?u,v∈V,(u,v)∈E≡(f(u),f(v))∈E′；

(3)?(u,v)∈E,l(u,v)=l′(f(u),f(v))。

給定任意兩個圖G′和G，如果圖G′到圖G的某個子圖存在同構(gòu)映射函數(shù)f，那么稱G′與G子圖同構(gòu)。

對于圖數(shù)據(jù)集GD，其中與圖G同構(gòu)子圖的個數(shù)與圖數(shù)據(jù)集GD中所有圖的數(shù)量的比值稱為圖G的支持度，記為σG。

設(shè)定最小支持度閾值為Min_σ，如果圖G的支持度大于或等于最小支持度(σG≥Min_σ)，那么圖G稱為頻繁圖或頻繁子圖[6]。

在圖數(shù)據(jù)集GD中，含有k個頂點的生成子圖且是連通子圖，稱為k-子圖。一個k-子圖或者去掉若干邊后的連通子圖是GD的頻繁子圖，則稱為k-頻繁子圖。含有k個頂點的所有子圖的集合記為Gk，定義為：

Gk={g=〈Vk,Ek〉∈GD,Vk={v1,v2,…,vk}?V,Ek={(vi,vj)/vi,vj∈Vk}是Vk中頂點形成的邊}

在犯罪情報圖數(shù)據(jù)集中，k個頂點的子圖，表示k個犯罪實體或人員的關(guān)聯(lián)關(guān)系。本文研究犯罪情報圖數(shù)據(jù)集中所有k-頻繁子結(jié)構(gòu)的獲取問題，即為k-頻繁子圖挖掘。具體描述如下：

輸入：一個大小為T的圖數(shù)據(jù)集GD={G1,G2,…,GT}，最小支持度為Min_σ，給定子結(jié)構(gòu)頂點數(shù)為k。

輸出：圖數(shù)據(jù)集中的所有k-頻繁子圖。

2 k-頻繁子圖挖掘算法

2.1 圖數(shù)據(jù)集預(yù)處理

本文的犯罪情報關(guān)聯(lián)圖集中頂點表示嫌疑人員，邊表示兩個嫌疑人員之間的聯(lián)系，邊的標(biāo)簽表示聯(lián)系類型，聯(lián)系類型根據(jù)嫌疑人之間的通話(x)、同住宿(y)、同上網(wǎng)(z)等聯(lián)系途徑設(shè)定，由若干頂點和連接頂點的邊構(gòu)成的圖數(shù)據(jù)結(jié)構(gòu)，用圖模式表示嫌疑人員關(guān)聯(lián)是一種直觀的表示方法。k-子圖包含k個頂點的子圖，表示k個嫌疑人員的關(guān)聯(lián)，圖模式不僅表示人員拓?fù)湫畔ⅲ瑘D上的每條邊標(biāo)簽表示人員聯(lián)系方式類型[7]。在進行k-頻繁子圖模式挖掘前，首先對原始圖數(shù)據(jù)集進行預(yù)處理得到圖數(shù)據(jù)集，犯罪情報數(shù)據(jù)集的數(shù)據(jù)來源如圖1所示。

圖1 圖模式數(shù)據(jù)集來源

傳統(tǒng)的人際關(guān)系應(yīng)用模型中社會關(guān)系網(wǎng)絡(luò)由多個節(jié)點和關(guān)系構(gòu)成的人際圈子，其中的人際關(guān)系構(gòu)成了一個簡單的無向網(wǎng)絡(luò)圖。與現(xiàn)實世界社會關(guān)系網(wǎng)絡(luò)比較而言，傳統(tǒng)的模型過于簡單，不能真實地反映現(xiàn)實世界的復(fù)雜關(guān)系情況，同時，傳統(tǒng)的應(yīng)用模型在節(jié)點關(guān)系親疏度管理機制上存在不足，無法拓展犯罪情報數(shù)據(jù)平臺的創(chuàng)新應(yīng)用。本文提出的圖模型基于現(xiàn)實世界人際關(guān)系，體現(xiàn)雙向關(guān)系的圖模型，如圖2所示。

圖2 圖模型

2.2 求Gk類的k-子圖算法

對犯罪情報數(shù)據(jù)集建立了圖模型以后，本文的主要任務(wù)是基于圖模式情報數(shù)據(jù)集挖掘重點人員或核心組織，這也是實現(xiàn)智慧警務(wù)風(fēng)險排查管控功能中的重點人員管控功能的關(guān)鍵技術(shù)。風(fēng)險排查管控主要是以人的管控為核心，只要管住了人，也就管住了重點場所、重點車輛、重點企業(yè)、重點組織、重點案事件。下面主要介紹挖掘重點k類人員的算法。

算法1. 求Gk類的k-子圖

輸入：圖數(shù)據(jù)集GD，|GD|=T。

輸出：所有k-子圖。

(1)從k=2～n，找出具有k個頂點子圖類Gk；

(2)從G2～Gn，對每一類圖Gk找出所有k-頂點生成子圖g；

(3)按所有生成子圖的邊數(shù)從小到大進行排序Gk={g1,g2,…,gT}；

(4)GD′={Gk}+GD′;

(5)輸出GD′={G2,G3,…,Gn};

(6)結(jié)束

表1 Gk與g的數(shù)量關(guān)系

2.3 有效得到k-頻繁子圖

求出所有生成k-子圖以后，根據(jù)k-頻繁子圖定義，下面求出一個k-子圖或者去掉若干邊后的連通子圖是否為頻繁子圖。

算法2. 挖掘k-頻繁子圖

輸入：圖數(shù)據(jù)集GD′，最小支持度閾值Min_σ。

輸出：k-頻繁子圖

(1)k=2 ton, 對GD′中的每個Gk：

(2)Gk={g1,g2,…,gT}

(3)i=1 toT

(4)以gi為模式圖，從gi+1到gT進行子圖同構(gòu)測試；

(5)如果gi的支持度大于或等于Min_σ，則gi為k-頻繁子圖；

(6)Fk=gi∪Fk；

(7)重復(fù)第1步和第6步，直到輸出所有Gk的頻繁子圖F={F2,F3,…Fn};

(8)輸出F，算法結(jié)束。

重點人員動態(tài)管控以支撐情報部門動態(tài)研判和民警動態(tài)管控為出發(fā)點，以“一人一檔”的方式，整合資源建立反映重點人員動態(tài)管控全過程的“電子檔案庫”，集中展現(xiàn)重點人員的基礎(chǔ)信息、動態(tài)信息、管控信息、現(xiàn)實表現(xiàn)信息、積分信息、關(guān)系人信息、關(guān)聯(lián)信息、文本情報信息、人工研判信息、流程控制等信息，清楚地體現(xiàn)研判過程，直觀、準(zhǔn)確地展現(xiàn)出重點人員在不同時間節(jié)點、不同地域范圍的行為軌跡、活動規(guī)律和可能異常動向，有效篩選違法犯罪嫌疑度高和對社會穩(wěn)定危害性大的重點人員，以便采取針對性的分類管控措施，提高重點人員積分預(yù)警的科學(xué)性、高效性，滿足重點人員積分升降、顏色變化的要求。圖3表示挖掘結(jié)果有4個重點人員電話聯(lián)系子圖，上面的實體人員有姓名和證號信息，下面有電話號碼信息，圖中的權(quán)重數(shù)字表示重點人員聯(lián)系的頻率。

圖3 電話聯(lián)系類4-子圖

為了減少重復(fù)的子圖，盡快使算法收斂，提高算法效率，提出了下面定理。

定理1算法2中計算Gk中k-子圖的支持度具有向下閉合性質(zhì)。

證明：由算法1的第5步可知，將所有生成子圖按邊數(shù)從小到大進行排序|g1|≤|g2|≤…≤|gT|。 又知所有生成子圖的頂點數(shù)相同為k，g1～gT，小的模式是大的模式的子模式；gT～g1，大的模式是小模式的超集。 若子圖g與某一大的模式?jīng)]有同構(gòu)子圖，則與小的頻繁模式中肯定沒有同構(gòu)子圖，定理得證。

根據(jù)定理1，可以對算法2的第4步子圖同構(gòu)測試進行優(yōu)化，在計算Gk每個子圖g支持度的過程中不斷對搜索空間進行有效的剪枝。

3 實驗分析

本文采用的實驗環(huán)境為單機Intel(R) Core(TM) i7-5600 2.6 GHz CPU， G內(nèi)存，500 GB硬盤，Windows 10 Professional操作系統(tǒng)，所有算法使用C++語言實現(xiàn)，G++編譯器編譯通過。由于未見挖掘k-頻繁模式的相關(guān)算法，主要是通過不同頂點規(guī)模及不同參數(shù)條件下驗證理論分析的結(jié)果及算法執(zhí)行的效率。

本文數(shù)據(jù)來源“神鷹”平臺數(shù)據(jù)集，該平臺以公安大數(shù)據(jù)中心為基座，融合公安經(jīng)濟偵查信息庫、公安內(nèi)部信息庫、社會行業(yè)信息庫、互聯(lián)網(wǎng)信息庫等資源庫，匯集公安內(nèi)網(wǎng)數(shù)據(jù)1 008類1 104億條、公安外網(wǎng)數(shù)據(jù)37類5億余條，建設(shè)了與稅務(wù)、市場監(jiān)管、公共資源交易等部門的數(shù)據(jù)專線。本文算法實驗數(shù)據(jù)集從中提取了與公安業(yè)務(wù)相關(guān)的9大類犯罪模型，共53個頂點數(shù)據(jù)標(biāo)簽，按數(shù)據(jù)集來源將其分為內(nèi)網(wǎng)數(shù)據(jù)集(Intranet datasets)和外網(wǎng)數(shù)據(jù)集(Extranet datasets)，分別包含320和410個圖的數(shù)據(jù)集。

算法結(jié)合了“云”計算技術(shù)，對大數(shù)據(jù)進行高性能處理，對資源檢索目標(biāo)達到秒級。通過“云”計算技術(shù)，內(nèi)置圖模式數(shù)據(jù)挖掘算法、統(tǒng)計分析工具，實現(xiàn)對海量的信息服務(wù)資源的橫向關(guān)聯(lián)、毫秒查詢、批量比對，滿足于各專業(yè)警種的應(yīng)用。

先驗證在最小支持度閾值Min_σ從10～100變化的情況下，本文算法在兩個數(shù)據(jù)集上的運行時間。從圖4中可以看出，當(dāng)最小支持度閾值由小增大其運行時間效率顯著提升，這是因為隨著支持度的增大，算法輸出的k-頻繁模式數(shù)量急劇減少，圖數(shù)據(jù)集預(yù)處理的時間減少了。圖5是顯示k值與算法運行運行時間關(guān)系，從圖中可以看出，在兩個數(shù)據(jù)集上k的大小對算法運行時間的影響，最小支持度閾值Min_σ=50%的條件下，隨著k的不斷增大，算法運行時間速度會有很大提升，這是因為隨著k值增大，輸出的k個頂點的頻繁模式數(shù)量會減少。

圖4 運行時間與支持度閾值關(guān)系

圖5 運行時間與k的關(guān)系

為了進一步驗證提出的CGMA算法的有效性，在實際數(shù)據(jù)集上取p=10，與本文挖掘目標(biāo)相近的PageRank算法[8]進行了比較，圖6顯示在不同k值下CGMA算法和PageRank算法的性能比較，結(jié)果可以看出在幾乎所有情況下本文算法都比PageRank算法運算速度快。

圖6 算法比較

最后根據(jù)情報關(guān)聯(lián)性，從實驗結(jié)果的k-頻繁模式中總共輸出2 360條關(guān)聯(lián)規(guī)則，其中滿足用戶閾值的有337條，為監(jiān)測預(yù)警、犯罪形勢分析報告、行業(yè)風(fēng)險評估報告、維穩(wěn)形勢分析報告等提供依據(jù)，為制定防范化解金融風(fēng)險對策、打擊經(jīng)濟犯罪提供參考。

4 結(jié)語

本文研究了如何在圖模式情報數(shù)據(jù)集找出k-頻繁模式問題，提出了一種高效挖掘k頂點頻繁子模式挖掘算法，通過確定k個頂點的生成子模式快速得到k-頻繁模式，解決了犯罪情報數(shù)據(jù)集包含子模式空間大且難于挖掘的問題。通過在犯罪情報兩個數(shù)據(jù)集上實驗研究，結(jié)果表明本文提出的算法能夠高效地從圖模式犯罪情報數(shù)據(jù)集中找出k-頻繁模式，可為今后如何利用圖模式挖掘研究犯罪嫌疑人員的關(guān)聯(lián)規(guī)律提供有力支持。