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

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

(1.中國傳媒大學信息工程學院，北京 100024；2.中國傳媒大學媒介音視頻重點實驗室，北京 100024；3.中國傳媒大學網(wǎng)絡中心，北京 100024)

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

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

(1.中國傳媒大學信息工程學院，北京 100024；2.中國傳媒大學媒介音視頻重點實驗室，北京 100024；3.中國傳媒大學網(wǎng)絡中心，北京 100024)

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

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

1 引言

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

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

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

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

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

2 算法分析

2.1 理論模型

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

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

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

(1)

(2)

對于矩陣Ai，有公式：

(3)

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

(4)

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

本文的模型基于兩點基本假設：

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

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

2.2 TPML-WMA算法

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

圖1 TPML-WMA算法流程圖

其策略如下：

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

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

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

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

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

算法 1. TPML

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

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

過程：

1：對Ai隨機設置初值.

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 達到停止條件

算法 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 達到停止條件

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

3 案例研究

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

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

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

續(xù)表

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

3.2 評價標準

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

(5)

3.3 實驗及結(jié)果分析

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

實驗1：半隨機取初始值和初始值固定時對結(jié)果的影響

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

3、對模型的優(yōu)化工作，比如用矩陣加擾動來抽象不可控因素，或建立開放系統(tǒng)的數(shù)學模型等，也需要繼續(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ū)毒品犯罪預測研究[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]陳鵬，疏學明，顏峻，等.犯罪活動在一天內(nèi)的發(fā)生時間規(guī)律[J].清華大學學報(自然科學版)，2009，49(12)：2032-2035.

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

[8]陳鵬，疏學明，袁宏永,等.時空犯罪熱點預測模型研究[J].系統(tǒng)仿真學報，2011，23(9).

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

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

[11]王璟瑤，秦靜，劉軍.犯罪案件移動平均預測模型改進研究[J].中國人民公安大學學報(自然科學版)，2015，(1).

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

(責任編輯：王 謙)

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-)，女(漢族)，吉林梅河口人，中國傳媒大學博士研究生.E-mail：weixinlei@cuc.edu.cn