魏新蕾，顏金堯，陳征，石拓

(1.中國傳媒大學(xué)信息工程學(xué)院，北京 100024；2.中國傳媒大學(xué)媒介音視頻重點(diǎn)實(shí)驗(yàn)室，北京 100024；3.中國傳媒大學(xué)網(wǎng)絡(luò)中心，北京 100024)

基于TPML-WMA算法的犯罪率分布模型分析

魏新蕾1，顏金堯2，陳征3，石拓1

(1.中國傳媒大學(xué)信息工程學(xué)院，北京 100024；2.中國傳媒大學(xué)媒介音視頻重點(diǎn)實(shí)驗(yàn)室，北京 100024；3.中國傳媒大學(xué)網(wǎng)絡(luò)中心，北京 100024)

犯罪分布預(yù)測問題對社會穩(wěn)定有積極影響，在學(xué)術(shù)界引起了廣泛關(guān)注?，F(xiàn)有的研究方法并不能很好的適用于本文所用的數(shù)據(jù)集。因此，本文構(gòu)建了矢量運(yùn)動(dòng)模型，并提出了一種名為TPML-WMA(Transition Probability Matrix Learning and Weighted Moving Average)的新算法，利用此算法去學(xué)習(xí)轉(zhuǎn)移概率矩陣，然后對得到的矩陣做加權(quán)移動(dòng)處理，進(jìn)而來預(yù)測未來的犯罪率分布。本文所用數(shù)據(jù)集是中國某市2001年到2011年共11年間盜竊案發(fā)生的數(shù)據(jù)集，在此之上本文建立了VM(Vector Motion)模型，提出了TPML-WMA算法對犯罪率進(jìn)行預(yù)測，并討論了不同初始條件下算法的性能。本文還將所提出的算法與基于最小二乘法的經(jīng)典線性回歸方法進(jìn)行比較。擬合的結(jié)果表明TPML-WMA模型的預(yù)測性能較線性回歸模型有了很大提升。

TPML-WMA算法；轉(zhuǎn)移概率矩陣；加權(quán)移動(dòng)平均；犯罪率分布

1 引言

21世紀(jì)是計(jì)算機(jī)科技迅猛發(fā)展的時(shí)代，公共安全領(lǐng)域的電子數(shù)據(jù)信息量也隨之膨脹，相關(guān)犯罪數(shù)據(jù)的研究也發(fā)展起來。犯罪的發(fā)生和地理環(huán)境因素是分不開的，所以很多基于GIS系統(tǒng)的犯罪分析應(yīng)運(yùn)而生[1]。基于地理位置的犯罪分布問題中的經(jīng)典解決方案就是建立馬爾可夫模型，利用轉(zhuǎn)移概率矩陣來預(yù)測分布狀態(tài)。不過大多數(shù)轉(zhuǎn)移概率矩陣都是先驗(yàn)的，利用數(shù)學(xué)統(tǒng)計(jì)方法事先算出來[2]。在國外還有研究團(tuán)隊(duì)引入機(jī)器學(xué)習(xí)算法，建立時(shí)空模型對犯罪問題進(jìn)行了一系列的研究工作。在這些文章里，作者是建立網(wǎng)格來劃分地理位置，并對每個(gè)單元網(wǎng)格貼標(biāo)簽，然后用不同的機(jī)器學(xué)習(xí)算法來計(jì)算各個(gè)網(wǎng)格的犯罪度，再根據(jù)給定閾值進(jìn)行熱點(diǎn)劃分[3][4]。也有文章引入自回歸積分滑動(dòng)平均模型(ARIMA)對一個(gè)城市連續(xù)若干周的案件發(fā)生數(shù)做預(yù)測[5]。陳鵬所在的科研團(tuán)隊(duì)曾研究過不同犯罪行為在一天內(nèi)各自具有何種時(shí)間選擇特征，何種犯罪類型更具有集中性，然后用聚類方法來比較作案頻數(shù)曲線來判斷哪幾種犯罪行為的時(shí)間選擇特征比較接近[6]。并根據(jù)地理位置做加權(quán)回歸模型來分析犯罪空間分布與地理因素之間的關(guān)聯(lián)，提高影響因素參數(shù)估計(jì)的準(zhǔn)確性[7]。2011年陳鵬等建立時(shí)空犯罪熱點(diǎn)預(yù)測模型，通過描述犯罪主體特征來對下次犯罪地點(diǎn)進(jìn)行預(yù)測，這是從微觀犯罪個(gè)體角度出發(fā)進(jìn)行的預(yù)測[8]。還有一些文章引入?yún)^(qū)域覆蓋加權(quán)模型[9]、混合模型時(shí)間序列[10]、移動(dòng)加權(quán)平均[11]和支持向量機(jī)[12]來預(yù)測犯罪。

研究犯罪問題的模型和方法多種多樣，但是并不是都能很好的適應(yīng)本文數(shù)據(jù)集的特點(diǎn)和研究目的，所以本文提出了基于TPML-WMA算法的模型來解決問題。創(chuàng)新之處在于：

第一，本文對數(shù)據(jù)集的地理位置按行政區(qū)域劃分，從整體上關(guān)注罪案發(fā)生率的分布變化，并考慮了各個(gè)區(qū)域間的內(nèi)在影響。

第二，很多成熟的算法并不適用本文的數(shù)據(jù)集和研究問題，所以本文采用矩陣和向量建立模型，并且將區(qū)域間的影響抽象成轉(zhuǎn)移概率矩陣模型，之后本文設(shè)計(jì)算法代入數(shù)據(jù)去學(xué)習(xí)這個(gè)矩陣。

我們的研究是以馬爾可夫模型為著手點(diǎn)，根據(jù)歷年的數(shù)據(jù)通過改進(jìn)算法來迭代求解轉(zhuǎn)移概率矩陣，然后結(jié)合加權(quán)移動(dòng)平均，對學(xué)到的九個(gè)轉(zhuǎn)移概率矩陣做三項(xiàng)加權(quán)移動(dòng)平均，然后用得到的矩陣做頻率分布的預(yù)測分析，并且和經(jīng)典的回歸分析做比較。

2 算法分析

2.1 理論模型

在實(shí)現(xiàn)TPML-WMA算法之前，本文對數(shù)據(jù)集建立數(shù)學(xué)模型。首先本文把研究區(qū)域按行政區(qū)域劃分，記為行政區(qū)域1、行政區(qū)域2、……、行政區(qū)域n。

利用統(tǒng)計(jì)分析軟件計(jì)算出各行政區(qū)域?qū)?yīng)的盜竊數(shù)據(jù)案發(fā)頻率，記為x1、x2、……、xn，如表1所示。

表1 各行政區(qū)及其對應(yīng)的盜竊案發(fā)頻率

(1)

(2)

對于矩陣Ai，有公式：

(3)

即Aixi=xi+1，i=1，……，m-1

(4)

相鄰兩年的數(shù)據(jù)組成一對，m年數(shù)據(jù)組成m-1對n維的向量，然后代入算法1去學(xué)習(xí)這個(gè)轉(zhuǎn)移矩陣。接下來對學(xué)到的m-1個(gè)矩陣做三項(xiàng)加權(quán)移動(dòng)平均，加權(quán)系數(shù)取0.2，0.3和0.5，對矩陣加權(quán)移動(dòng)平均就是對三個(gè)矩陣的對應(yīng)每一個(gè)元素做加權(quán)移動(dòng)平均(詳見算法2)。最后用得到的矩陣來預(yù)測下一年的盜竊案發(fā)頻率分布。

本文的模型基于兩點(diǎn)基本假設(shè)：

第一，各個(gè)行政區(qū)域相互之間不獨(dú)立，即相互之間的盜竊案發(fā)生對其他區(qū)域皆有影響。

第二，把某市看成一個(gè)封閉系統(tǒng)，市外的盜竊案不會轉(zhuǎn)移到市內(nèi)；同理，市內(nèi)的盜竊案也不會轉(zhuǎn)移到市外。簡言之，本市內(nèi)的盜竊案只會在各個(gè)行政區(qū)域內(nèi)相互影響和轉(zhuǎn)移。

2.2 TPML-WMA算法

為了對某市各個(gè)行政區(qū)域的犯罪率分布的相互聯(lián)系和變化趨勢進(jìn)行量化分析，本文提出TPML-WMA算法。它包括轉(zhuǎn)移概率矩陣學(xué)習(xí)(TPML)和加權(quán)移動(dòng)平均(WMA)兩個(gè)主要算法，流程如圖1所示：

圖1 TPML-WMA算法流程圖

其策略如下：

1、清洗數(shù)據(jù)，統(tǒng)計(jì)每一年各區(qū)域的罪案發(fā)生頻率。

2、建立數(shù)學(xué)模型，每一年各區(qū)域罪案發(fā)生頻率抽象成一個(gè)n維向量。

3、上一年和下一年的頻率向量之間的轉(zhuǎn)移關(guān)系用矩陣表示，滿足公式(3)。分別m-1次代入相鄰兩個(gè)頻率向量數(shù)據(jù)，根據(jù)TPML算法(算法1)反復(fù)迭代得到Ai，i=1，……，m-1。

4、對得到的m-1個(gè)Ai，用三項(xiàng)加權(quán)移動(dòng)平均WMA(算法2)來得到最終的轉(zhuǎn)移概率矩陣，用最終的轉(zhuǎn)移概率矩陣作用在最后一年的頻率向量上，即得下一年各行政區(qū)域的罪案發(fā)生頻率向量。

5、與經(jīng)典線性回歸算法的預(yù)測結(jié)果做對比。此處的線性回歸是基于最小二乘法的，對每一年的頻率向量數(shù)據(jù)的每一個(gè)分量分別做線性回歸。

算法 1. TPML

輸入：向量對(xi，xi+1)，i=1，…，m-1.

輸出：Ai，i=1，…，m-1.

過程：

1：對Ai隨機(jī)設(shè)置初值.

2：xi+1～=Aixi

4：repeat

5： for i=1… m-1 do

6： for k=1…n do

7： for j=1…n do

8： if j=k then

10： else

12： end if

13： end for

14： end for

15： end for

16：until 達(dá)到停止條件

算法 2. WMA

Output：A1

Process：

1：repeat

2： for i=1… m-1 do

3： for k=1…n do

4： for j=1…n do

6： end for

7： end for

8： end for

9：until 達(dá)到停止條件

經(jīng)簡單計(jì)算可知本文的TPML-WMA算法復(fù)雜度為O(n3)。

3 案例研究

3.1 數(shù)據(jù)集

本文使用的數(shù)據(jù)集是中國某市2001年到2011年共11年間盜竊案數(shù)據(jù)，屬于封閉數(shù)據(jù)集。本文把前十年的數(shù)據(jù)作為訓(xùn)練集，第十一年的數(shù)據(jù)作為測試集，同時(shí)，本文為還將TPML-WMA算法的預(yù)測結(jié)果與線性回歸的預(yù)測結(jié)果做對比。

表2 2001年某市各行政區(qū)盜竊案發(fā)頻率

續(xù)表

對于矩陣Ai，仍有Aixi=xi+1，此時(shí)i=1，……，9。

3.2 評價(jià)標(biāo)準(zhǔn)

本實(shí)驗(yàn)采用平均絕對值誤差MAE來評價(jià)結(jié)果，其定義如下：

(5)

3.3 實(shí)驗(yàn)及結(jié)果分析

我們基于python進(jìn)行了算法的仿真實(shí)驗(yàn)，并與線性回歸預(yù)測結(jié)果進(jìn)行了對比分析。

實(shí)驗(yàn)1：半隨機(jī)取初始值和初始值固定時(shí)對結(jié)果的影響

表3 分別半隨機(jī)取初值和固定初始值后算法得出的各區(qū)域頻率值對比

實(shí)驗(yàn)2：TPML-WMA算法與線性回歸的預(yù)測結(jié)果做對比

由圖2可以看出，TPML-WMA算法(紅線)和真值(藍(lán)線)整體來說擬合的較好，而線性回歸LR算法(綠線)相對擬合的較差，尤其是在區(qū)域5、8、10和13。

圖2 TPML-WMA與LR預(yù)測結(jié)果比較

表4給出在平均絕對值誤差MAE的評價(jià)標(biāo)準(zhǔn)下，TPML-WMA算法的準(zhǔn)確性比線性回歸算法要高。并且通過對預(yù)測結(jié)果的求和，TPML-WMA的和基本上仍是1(0.999)，而線性回歸的和偏離1的程度就大的多，大約偏離了11%(1.109)。另外，TPML-WMA預(yù)測值的加和0.999與1的那一點(diǎn)誤差是數(shù)值計(jì)算中對數(shù)的取舍造成的，是不可避免的，這與算法設(shè)計(jì)無關(guān)。所以說TPML-WMA算法的性能比線性回歸算法要優(yōu)越的多。

表4 MAE & SUM結(jié)果對比

4 結(jié)論

本文中給出的TPML-WMA算法能夠很好的描述一個(gè)封閉系統(tǒng)內(nèi)部各部分的頻率分布與轉(zhuǎn)移狀態(tài)。相對線性回歸算法而言，用概率轉(zhuǎn)移矩陣來描述各部分狀態(tài)轉(zhuǎn)移更為貼切，并且由于借鑒了機(jī)器學(xué)習(xí)思路去讓矩陣自我學(xué)習(xí)，這也提高了矩陣的擬合度。

當(dāng)然目前的研究工作仍然面臨很多問題，未來會繼續(xù)沿著以下幾個(gè)方向改進(jìn)：

1、目前的研究成果是基于很多理想的假設(shè)條件下得出的結(jié)論，真實(shí)數(shù)據(jù)受政治，突發(fā)環(huán)境影響巨大，不可控的因素很多，如何用數(shù)學(xué)符號抽象這些不可控因素是研究的難點(diǎn)。

2、本文是針對一個(gè)封閉集提出的算法，是否能夠在其他公開數(shù)據(jù)集上很好的應(yīng)用，還需要繼續(xù)做實(shí)驗(yàn)。

3、對模型的優(yōu)化工作，比如用矩陣加擾動(dòng)來抽象不可控因素，或建立開放系統(tǒng)的數(shù)學(xué)模型等，也需要繼續(xù)研究。

[1]Yufei Zhang，Huifeng Ji. Using GIS to analyze and forecast the Chinese Crime rate[C].The 2nd International Conference on Information Science and Engineering(ICISE)，2010：3352-3354.

[2]吳紹兵，王昌梅.基于馬爾科夫鏈的民族地區(qū)毒品犯罪預(yù)測研究[J].計(jì)算機(jī)與數(shù)字工程，2015，43(7).

[3]Chung-Hsien Yu，Max W Ward，Melissa Morabito，Wei Ding. Crime Forecasting Using Data Mining Techniques[C]. 2011 IEEE 11th International Conference on Data Mining Workshops(ICDMW)，2011：779-786.

[4]Chung-Hsien Yu，Wei Ding，Peng Chen，Melissa Morabito. Crime Forecasting Using Spatio-Temporal Pattern with Ensemble Learning[C]. The 20th Pacific Asia Conference on Knowledge Discovery and Data Mining(PAKDD)，2014：174-185.

[5]Peng Chen，Hongyong Yuan，Xueming Shu. Forecasting Crime Using the ARIMA Model[C].The 5th International Conference on Fuzzy Systems and Knowledge Discovery(FSKD)，2008，5：627-630.

[6]陳鵬，疏學(xué)明，顏峻，等.犯罪活動(dòng)在一天內(nèi)的發(fā)生時(shí)間規(guī)律[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，49(12)：2032-2035.

[7]顏峻，疏學(xué)明，袁宏永.盜竊犯罪空間分布與地理因素的關(guān)聯(lián)[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010，50(2)：174-186.

[8]陳鵬，疏學(xué)明，袁宏永,等.時(shí)空犯罪熱點(diǎn)預(yù)測模型研究[J].系統(tǒng)仿真學(xué)報(bào)，2011，23(9).

[9]薛鐘，喬良，王峰等.連續(xù)犯罪預(yù)測的區(qū)域覆蓋加權(quán)模型(AOWM)[J].數(shù)學(xué)實(shí)踐與認(rèn)識，2010，40(15)：212-217.

[10]涂小萌，陳強(qiáng)國.基于ARIMA_LSSVM混合模型的犯罪時(shí)間序列預(yù)測[J].計(jì)算機(jī)技術(shù)與應(yīng)用，2015，41(2).

[11]王璟瑤，秦靜，劉軍.犯罪案件移動(dòng)平均預(yù)測模型改進(jìn)研究[J].中國人民公安大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，(1).

[12]陳鵬，胡嘯峰，陳建國.基于模糊信息?；闹С窒蛄繖C(jī)在犯罪時(shí)序預(yù)測中的應(yīng)用[J].科學(xué)技術(shù)與工程，2015，15(35).

(責(zé)任編輯：王 謙)

AnalysisofCrimeRateDistributionBasedonTPML-WMA

WEI Xin-lei1，YAN Jin-yao2，CHEN Zheng3，SHI Tuo1

( 1． Information Engineering School，Communication University of China，Beijing 100024，China; 2． Key Laboratory of Media Audio & Video，Communication University of China，Beijing 100024，China; 3． Computer NIC Center，Communication University of China，Beijing 100024，China)

Crime distribution forecasting has a positive impact on social stability and has drew much attention in academia. Existing research methods are not applicable for specific data sets very well，such as the data in this paper. So we build the Vector Motion Model and propose a new algorithm named as TPML-WMA(Transition Probability Matrix Learning and Weighted Moving Average algorithm)to predict a future robbery distribution and figure out how it transfers. We let the transition probability matrix to learn by itself，and do the weighted moving processing on the matrices. Using crime data from 2001 to 2011 from some city in China，we set up the model，propose TPML-WMA algorithm to predict the crime distribution，then discuss the performance of algorithms under different initial conditions. At the same time，we compare the proposed algorithm with the classical linear regression method based on the least square method. The results illustrate that the prediction performance of TPML-WMA is greatly improved compared with the linear regression method.

TPML-WMA algorithm；transition probability matrix；weighted moving average；crime rate distribution

TP399

A

1673-4793(2017)05-0021-06

2017-07-05

魏新蕾(1981-)，女(漢族)，吉林梅河口人，中國傳媒大學(xué)博士研究生.E-mail：weixinlei@cuc.edu.cn