改進型Apriori算法在犯罪關(guān)聯(lián)分析中的應(yīng)用

張亞洲

摘 要：文章針對公安機關(guān)已為犯罪行為建立了海量的業(yè)務(wù)信息數(shù)據(jù)庫，提出基于Apriori算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)，并將該技術(shù)應(yīng)用于犯罪行為分析，以便發(fā)現(xiàn)犯罪行為特點及犯罪嫌疑人特性等潛在的聯(lián)系，為公安部門的戰(zhàn)略部署，決策指揮，偵查破案，治安管理等提供依據(jù)。

關(guān)鍵詞：犯罪分析；Apriori算法；關(guān)聯(lián)規(guī)則

近年來，公安部門積累了海量的基礎(chǔ)數(shù)據(jù)和犯罪數(shù)據(jù)信息，但對于這么多數(shù)據(jù)的高效利用和深度應(yīng)用未有明顯成績。因此如何利用先進的信息技術(shù)在這些海量數(shù)據(jù)中進行深度挖掘，得出一些新知識，使之有益于公安部門的戰(zhàn)略部署，決策指揮，偵查破案，治安管理等，自然具有一定的時代意義。

1 關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘，有時也叫關(guān)聯(lián)分析，是數(shù)據(jù)挖掘的一個重要研究領(lǐng)域。它是指從事務(wù)數(shù)據(jù)庫，關(guān)系數(shù)據(jù)庫和其他信息存儲中的大量數(shù)據(jù)的項集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性，即所謂的關(guān)聯(lián)規(guī)則。其形式為：“X=>Y”，即在設(shè)定的高置信度的規(guī)則下，X事件發(fā)生了，Y事件必然發(fā)生。

關(guān)聯(lián)規(guī)則挖掘核心算法為著名的Apriori算法。當(dāng)然，此后出現(xiàn)了一些相關(guān)算法，諸如DIC算法[1]、DLG算法[2]和DHP算法[3]等，都是基于Apriori算法做了改進或優(yōu)化而成的。

1.1 Apriori算法

Apriori算法，是Agrawal.R、Imieliński.T等人在1993數(shù)據(jù)管理國際會議上提出的，它是一種最具影響挖掘關(guān)聯(lián)規(guī)則頻繁項集的算法[4]。算法實質(zhì)是一個逐層迭代搜索的方法，利用K項集探索K+1項集。第一次，找出頻繁1項集的集合，記為L1；第二次，利用L1探索L2，找出頻繁2項集，記為L2；如此進行探索，直至頻繁項集K為空，停止。

算法描述如下：

Input： Database D， of transactions； minimum support threshold；

Output： L， frequent itemsets in D

Method：

（1） L1=find_frequent_1-itemsets（D）；

（2） For（k=2； Lk-1≠Φ； k++）{

（3） Ck=apriori_gen（Lk-1， min_sup）；

（4） for each transaction t∈D{

（5） Ct=subset（Ck，t）；

（6） for each candidate c ∈Ct；

（7） c.count++；

（8） }

（9） Lk={ c∈Ck |c.count≥min_sup}；

（10） }

（11） return L=∪kLk；

Procedure apriori_gen（Lk-1：frequent（k-1）-itemsets； min_sup： support）

（1） for each itemset l1∈ Lk-1

（2） for each itemset l2∈ Lk-1

（3） if（l1 [1]= l2 [1]）∧ （l1 [2]= l2 [2]） ∧…∧（l1 [k-2]= l2 [k-2]）∧ （l1 [k-1]= l2 [k-1]） then {

（4） c=l1∪ l2；

（5） if has_infrequent_subset（c， L k-1） then

（6） delete c；

（7） else add c to Ck；

（8） }

（9） return Ck；

Procedure has_infrequent_subset（c： candidate k-itemset； Lk-1：

frequent（k-1）-itemsets）

（1） for each（k-1）-subset s of c

（2） if s ！∈L k-1 then

（3） return true；

（4） return false；

1.2 關(guān)聯(lián)規(guī)則的產(chǎn)生

事實上，當(dāng)從數(shù)據(jù)庫D中的事務(wù)找出頻繁項集時，由他們產(chǎn)生的關(guān)聯(lián)規(guī)則是顯而易見的。然而，這些規(guī)則的置信度是不一樣的。因此，和支持度一樣，置信度得設(shè)置一個閥值。在設(shè)定的置信度閥值和支持度閥值條件下，同時滿足這兩個條件的規(guī)則叫強規(guī)則，這些規(guī)則通常有趣，是關(guān)聯(lián)規(guī)則挖據(jù)的目的。

對于置信度，可以用下式，其中條件概率用項集支持度計數(shù)表示

Conference（A=>B）=P（B|A）=support-count（A+B）/support-count（A）

其中，support-count（A+B）是包含項集A+B的事務(wù)數(shù)，support-count（A）包含項集的A的事務(wù)數(shù)[5]。

1.3 Apriori算法優(yōu)化

從算法描述可看出，當(dāng)數(shù)據(jù)庫D的事務(wù)達到一定規(guī)模時，算法的空間復(fù)雜度和時間復(fù)雜度相當(dāng)高。因此，優(yōu)化是必要的，旨在提高原算法的效率。常用方法有：散列技術(shù)計數(shù)、事務(wù)壓縮、劃分、選樣。還有一些通過變形實現(xiàn)有效性，如動態(tài)項集計數(shù)、多層和多維等關(guān)聯(lián)規(guī)則挖掘。

2 實例分析

2.1 挖據(jù)過程

將Apriori算法應(yīng)用于犯罪行為分析，主要目的在找出案件的各個特征及犯罪嫌疑人各個特征之前可能存在的相互關(guān)系，以便找出有用的關(guān)聯(lián)規(guī)則。其挖掘過程如下所示。

第一步，數(shù)據(jù)選擇。從犯罪行為數(shù)據(jù)庫中檢索選擇與分析任務(wù)相關(guān)的數(shù)據(jù)并消除噪聲信息。

第二步，數(shù)據(jù)梳理。運用減低維數(shù)、連續(xù)數(shù)據(jù)的離散分類等將數(shù)據(jù)梳理成標準統(tǒng)一的適合于挖據(jù)的形式。

第三步，關(guān)聯(lián)規(guī)則挖掘。主要步驟，使用Apriori算法對已梳理過的事務(wù)進行關(guān)聯(lián)分析。

第四步，實效評估。通過調(diào)整支持度閥值及置信度閥值，按照既定的業(yè)務(wù)興趣度量，結(jié)合實戰(zhàn)檢驗，使得過程挖掘所獲得知識結(jié)果更容易接受，更有價值。

第五步，知識表示與存儲。使用可視化和知識表示技術(shù)，形成知識庫，為決策提供依據(jù)。

其中，Apriori算法是關(guān)鍵。過程將發(fā)現(xiàn)事務(wù)數(shù)據(jù)庫中隱藏的形式為“A=>B”的規(guī)則，即在一定的支持度和一定置信度下，假如A發(fā)生則B一定發(fā)生。

2.2 模型建立

優(yōu)秀的技術(shù)應(yīng)用于具體行業(yè)，要想達到實戰(zhàn)的成果，模型的建立尤為重要。而對于關(guān)聯(lián)數(shù)據(jù)挖掘而言，這個模型的關(guān)鍵點在于合適事務(wù)數(shù)據(jù)庫的建立。公安業(yè)務(wù)數(shù)據(jù)庫巨大無比，如何梳理，直接影響挖掘的成果。

在實際工作中，犯罪兩個重要的組成是犯罪行為和行為者。因此，從事和人出發(fā)，考慮其特點。以已破的刑事犯罪案件信息數(shù)據(jù)的主導(dǎo)，進行梳理，如下：

（1）案件信息：編號、類別、時間、地點、特點、危害程度、簡情；

（2）涉案人員：姓名、外號、性別、民族、出生日期、居民身份證號碼、籍貫、戶籍地、居住地、文化程度、收入狀況、家庭背景、違法犯罪經(jīng)歷

在本文中，挑選其中主要的八項事務(wù)建立模型：作案形式、選擇時機、選擇處所、選擇對象、案件類別、嫌疑人籍貫、嫌疑人年齡、嫌疑人文化。

2.3 數(shù)據(jù)抽樣

樣本來源于某地市2012年搶劫案連續(xù)抽取的12個樣本，并按照模型格式進行梳理，其結(jié)果如表1所示。

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

實驗環(huán)境：平臺windows，語言java，算法基于Hash技術(shù)改進的Apriori。

取值支持度閥值=3，置信度=8時，從結(jié)果中抽一條規(guī)則：

from 下半夜；單獨作案；小學(xué)；少年；貴州??；calc下半夜；單獨作案；少年；->小學(xué)；貴州省；：1.0

//規(guī)則說明：from L（支持度大于已設(shè)定支持度閥值）；calc S->L-S（關(guān)聯(lián)規(guī)則）；：Num（置信度）

該規(guī)則的預(yù)示：

下半夜發(fā)生的搶劫案，若實施犯罪者為單人且為少年，可以鎖定該犯罪嫌疑人是貴州籍，且文化程度為小學(xué)。

取值支持度閥值=4，置信度=9時，從結(jié)果中抽一條規(guī)則：

from上半夜；共同作案；少年；calc上半夜；少年；->共同作案；：1.0

//規(guī)則說明：from L（支持度大于已設(shè)定支持度閥值）；calc S->L-S（關(guān)聯(lián)規(guī)則）；：Num（置信度）

該規(guī)則的預(yù)示：

發(fā)生在上半夜的搶劫案，如實施犯罪者為少年，一定還有同伙。

對比，提高支持度閥值和置信度閥值，可提高挖掘結(jié)果的可靠性，但發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則也大大減少。因此，根據(jù)用戶的興趣程度和實效評估，及時調(diào)整相關(guān)參數(shù)，對于關(guān)聯(lián)規(guī)則挖掘在某一領(lǐng)域的應(yīng)用至關(guān)重要。

3 結(jié)語

本文僅僅是作為關(guān)聯(lián)規(guī)則在犯罪分析中應(yīng)用的一個引子，對其可行性做了探究，其工程運用需要更多更廣的梳理和評估。隨政治、經(jīng)濟、科技等的發(fā)展，犯罪行為也悄然發(fā)展，其新特點也層出不窮，因此借助于數(shù)據(jù)挖掘技術(shù)，更快更準的掌握犯罪動態(tài)尤為重要。這對提高公安機關(guān)打、防、控等整體作戰(zhàn)水平和能力具有積極重大意義。

[參考文獻]

[1]Brin S，Motwani R，Ullman J D and Tsur S.Dynamic itemset counting and implication rules for market basket data[C].Proc.of the ACM SIGMOD Intl Conf.on Management of Data，1997.

[2]Yen S J and Chen A L P.An Efficient Approach to Discovering Knowledge from Large Databases[C].Proc.IEEE/ACM International Conference on Parallel and Distributed Information Systems（PDIS），1996.

[3]Park J S，Chen M S and Yu P S.An Effective Hash Based Algorithm for Mining AssociationRules[C].Proc.of ACM SIGMOD，May 23-25，1995：175.186.

[4]Agrawal， R.；Imieliński， T.； Swami， A.（1993）."Mining association rules between sets of items in large databases". Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. pp.207. doi：10.1145/170035.170072.ISBN 0897915925.

[5]Jiawei Han，Micheline Kamber，Data Mining：Concepts adn Technigues，The Second Edition，Morgan Kaufmann Publishers，2006，138.