王雨晨,過仲陽,王媛媛

(華東師范大學地理科學學院,上海200241)

基于隨機森林的犯罪風險預測模型研究

王雨晨,過仲陽,王媛媛

(華東師范大學地理科學學院,上海200241)

犯罪預測是犯罪預防的前提,也是公安部門亟待解決的問題.隨機森林作為一種組合分類方法,具有準確率高、速度快、性能穩(wěn)定的特性,且能夠給出指標重要性評價,本文將其應用于犯罪風險預測中.實驗證明,隨機森林方法選出的指標集可以顯著地提高預測準確率,基于該方法構建的預測模型相較于神經網(wǎng)絡與支持向量機具有更高的準確性和穩(wěn)定性,能夠滿足犯罪風險預測的需求.

隨機森林;犯罪風險預測;指標集選擇

0 引言

犯罪預測是實現(xiàn)精準、快速打擊犯罪行為的前提,對于犯罪風險的準確預測可以為預防犯罪提供有效的決策信息,實現(xiàn)警力跟著警情走,提高警務工作效率.隨著大數(shù)據(jù)與數(shù)據(jù)挖掘技術的發(fā)展,公安部門的警務大數(shù)據(jù)平臺已經進入了實際應用階段,犯罪相關數(shù)據(jù)的數(shù)量與質量也在大幅度提升,使得數(shù)據(jù)挖掘技術支撐下的犯罪預測成為可能.

目前,我國對于犯罪預測的研究多數(shù)停留在定性預測階段,定量預測的缺少造成了犯罪預測精度較低,從而使得預測結果缺少實用價值[1].在犯罪行為的定量預測方面,通過建立數(shù)學模型進行預測的相關學習算法有:利用決策樹算法對涉嫌違法犯罪人員數(shù)據(jù)進行挖掘,預測其犯罪風險[2-3];利用自回歸移動平均模型、支持向量機和向量自回歸模型的動態(tài)優(yōu)化組合,預測立案總數(shù)的年際變化[4];利用模糊BP(Back Propagation)神經網(wǎng)絡預測各年份公安破案的案件數(shù)量和檢察院受理的案件數(shù)量[5];利用基于模糊信息?；闹С窒蛄繖C擬合犯罪時序信息[6]等.

在進行犯罪風險預測的過程中,構建模型所使用的訓練數(shù)據(jù)的質量直接決定了最終預測結果的準確性,如何選擇與預測結果相關的有效指標信息成為建立模型的關鍵.犯罪信息屬性繁雜,構建模型時過多的指標容易造成預測模型的過度擬合,反而會降低實際預測時的準確性.同時,犯罪數(shù)據(jù)數(shù)量大、有噪聲、不完全、模糊和隨機等特點,也使得犯罪風險預測中指標集合的選擇顯得尤為重要.

本文介紹了一種對于數(shù)據(jù)噪聲魯棒、預測結果準確且穩(wěn)定的組合分類算法——隨機森林(Random Forest),應用于犯罪信息指標集合的選取與犯罪風險的預測.實驗結果證明,該算法選出的指標集合具有明顯的合理性,改善了指標選擇缺乏客觀標準的現(xiàn)狀.同時基于該算法建立的風險預測模型在預測的準確性和穩(wěn)定性方面,相較于其他模型均有一定的提升,得到了較為理想的結果.

1 基本原理

1.1 隨機森林原理

隨機森林是組合分類方法的一種,它由大量CART(Classifi cation And Regression Tree)決策樹的集合構成,所以稱之為“森林”.其中生成單棵樹的訓練數(shù)據(jù)由獨立抽樣產生,單棵樹中每個內部節(jié)點的候選分裂屬性從全部的候選屬性中隨機抽取.隨機森林的最終分類結果由每棵決策樹投票決定[7-8].隨機森林具備以下特點:

①對于包含d個元組的原始數(shù)據(jù)集D,產生n棵決策樹,迭代i(i=1,2,···,n)次利用自助法(Bootstrap)每次從數(shù)據(jù)集D中有放回地抽取d個元組作為訓練集Di,每個Di都是一個自助樣本.由于是有放回地隨機抽樣,D中的某些元組會被多次抽取,而另一些元組則不會出現(xiàn)在Di中.因此,未被抽取的元組可以作為檢驗集.

可以證明,D中每個元組被抽中的概率為1/d,因此,該元組未被抽中的概率為(1?1/d),抽取N次后某個元組未被抽中的概率為(1?1/d)N.當N足夠大時, (1?1/d)N收斂于e?1=0.368.所以一般情況下,自助法產生的訓練集和檢驗集分別占63.2%和36.8%.

②隨機屬性選擇,對于全部F個分類屬性,每個內部節(jié)點隨機選擇f個屬性形成候選分類屬性集,其中f?F,且f的值固定.

③單棵樹生成過程中完全生長,不進行剪枝操作,有助于消除樹的偏移.

④分類結果由n棵決策樹投票決定,每棵樹Ti返回一個分類結果且有相同的投票權重,票數(shù)最多的類成為最終的分類結果.

1.2 泛化誤差收斂性[9-11]

對于組合分類模型{h1(X),h2(X),···,hk(X)},其中h(X)表示一個分類器對于輸入X產生相應的類標號輸出,該分類器的訓練樣本由自助法得到.定義組合分類模型的間隔函數(shù)(Margin Function),公式為

間隔函數(shù)可以衡量分類模型的正確性與確信度,該函數(shù)表示平均正確分類數(shù)與平均錯誤分類數(shù)的間隔程度,正確分類的數(shù)量超過錯誤分類的數(shù)量越多,說明分類模型的性能越好.因此,分類模型的泛化誤差定義為

該泛化誤差推廣到隨機森林,hk(X)=h(X,Θ),其中Θ表示單棵決策樹的參數(shù)向量.隨著森林中分類樹數(shù)目的增加,根據(jù)大數(shù)定律,泛化誤差幾乎處處收斂,公式為

這說明,隨機森林對于噪聲和離群點是魯棒的,也不會產生過度擬合問題.

1.3 OOB估計

裝袋(Bagging),也叫自助聚集(Bootstrap Aggregation),屬于組合分類方法.其一般過程是,通過自助法(Bootstrap)從訓練集中有放回地抽取k個自助樣本集,分別學習得到k個分類模型,最終聚集(Aggregate)所有模型得到裝袋分類器.根據(jù)第1.1節(jié)中證明可知,每次抽取自助樣本時,約36.8%的數(shù)據(jù)未被抽中,未被抽中的數(shù)據(jù)稱為袋外(Out-Of-Bag,OOB)數(shù)據(jù),構成檢驗集.這種使用袋外數(shù)據(jù)估計模型準確率的方法稱為OOB估計[12].OOB估計可以得到分類模型的泛化誤差,并且不同于交叉驗證的是,此方法不需要額外的計算.實驗證明, OOB誤差屬于無偏估計.

1.4 基于OOB估計的屬性選擇

隨機森林衡量屬性重要性的理論基礎是,通過在每次迭代過程中隨機置換第j個分裂屬性Xj,打破其與類標號屬性y的聯(lián)系.當屬性Xj被置換后,剩余的屬性用于觀測隨機森林OOB估計的變化,如果屬性置換后的分類準確率大幅降低,說明屬性Xj與相應類標號屬性y的相關性較強.平均所有樹在屬性Xj被置換前后分類準確率的差值作為衡量變量重要性的度量[13-15].屬性Xj在第k棵數(shù)的變量重要性(Variable Importance,VI)計算公式為

根據(jù)OOB誤差最小化準則,在擬合所有森林后,依據(jù)屬性重要性選取其子集并檢查OOB誤差,選擇擁有最小屬性數(shù)量的方案.并且被選屬性的誤差率不超過所有森林最低誤差的標準誤差,標準誤差利用二項計數(shù)誤差sqrt(p(1?p)×1/N)計算得到.該方法對于高維小樣本數(shù)據(jù)較為適用[16],通過此方法可以選取候選屬性集的最優(yōu)子集.

2 模型構建

2.1 實驗數(shù)據(jù)的準備

本文的實驗數(shù)據(jù)來源于某公安分局數(shù)據(jù)庫中犯罪人員信息的部分記錄,所有分析操作均在公安平臺上進行,數(shù)據(jù)使用前已進行脫敏處理.利用犯罪人員信息挖掘得到犯罪風險預測模型,該模型的主要目的是通過犯罪人員信息分析出可能引發(fā)不同犯罪風險的各因素之間的關系,最終協(xié)助有關部門制定相應的政策,預防嚴重危害公共安全案件的發(fā)生.模型最終的分類結果是“犯罪程度”,包含{嚴重,一般}兩類.

為了提高數(shù)據(jù)質量,需要對數(shù)據(jù)做預處理.首先,數(shù)據(jù)庫中存在著與預測結果無關的冗余指標,如“案件編號”等,這些指標對于本文的研究沒有意義,故將其刪除;其次,某些指標包含了有窮多個且無序的不同值,應將其泛化到較高的概念層次,使該指標的不同值數(shù)量減少,如將信息表中的“現(xiàn)住址全稱”泛化成“是否本區(qū)居住人口”;最后,處理信息表中的缺失值,原則是盡可能地填補缺失值,如“年齡”指標的缺失值可通過“出生日期”和“案發(fā)時間”填充,無法填充缺失值的記錄做刪除處理.經過數(shù)據(jù)預處理后,最終提取有效記錄4 053條,其中“嚴重”類別1 969條,“一般”類別2 084條.提取的指標名稱及編號參見表1.

表1 指標名稱及編號Tab.1 ID of the variables

2.2 相關指標的確定

利用用第1.4節(jié)所介紹的方法對樣本數(shù)據(jù)進行計算,得到各指標被排除后的平均OOB準確率降低值,其結果參見表2.以準確率降低程度為標準對指標進行排序,獲得各指標的重要性排名,準確率降低值越大,說明該指標越重要,指標重要性降序序列為114、105、102、107、113、108、115、104、103、101、111、112、106、110、109,其結果參見圖1(a).

按照圖1(a)的排序結果,選擇誤差率滿足1?S E規(guī)則的前6個指標作為候選指標集S1= {114,105,102,107,113,108}.同時,根據(jù)圖1(a)的重要性排序,向候選指標集S1中逐一增加指標,使得S2=S1∪{115},S3=S2∪(104),S4=S3∪{103},得到3個新的指標集,用于對比得出OOB估計標準下的最優(yōu)指標集.分別計算以上4個指標集的OOB誤差率,結果為24.38%, 24.18%,23.91%和24.53%.因此選擇OOB誤差率最小的S3作為候選指標集.

為了進一步驗證S3指標集的合理性,利用基尼指數(shù)方法再次選擇指標集[17],計算各指標的平均基尼指數(shù)降低值,其結果參見表2,排序結果參見圖1(b).根據(jù)圖1(b)中各指標平均基尼指數(shù)降低值降序排序結果,選擇基尼指數(shù)降低值較高的前8個指標形成對比指標集S5={105,110,102,114,103,104,108,107}.同時,將全部指標作為對比指標集S6.計算S5與S6兩個指標集的OOB誤差率分別為33.36%和41.92%.

表2 指標重要性度量Tab.2 Importance of the variables using diff erent measures

圖1 不同標準下的指標重要性排序Fig.1 Importance order of the variables using diff erent measure

圖2 不同指標集的OOB誤差率Fig.2 OOB error rates of diff erent variables sets

S3、S5與S6三個指標集的OOB誤差對比結果參見圖2,圖中體現(xiàn)了隨著隨機森林中樹的棵數(shù)的增加,OOB誤差率的變化趨勢,其中黑色曲線表示總體的OOB誤差率,紅色曲線表示“嚴重”類別的OOB誤差率,綠色曲線表示“一般”類別的OOB誤差率.通過對比得出,S5與S6指標集的OOB誤差率均大于S3,因此選擇S3作為最終的指標集參與模型構建.

2.3 預測模型的實現(xiàn)

根據(jù)最終確定的S3指標集中的元素,剔除原數(shù)據(jù)中不屬于S3指標集的指標列,余下的數(shù)據(jù)作為構建預測模型的數(shù)據(jù)集.分別使用神經網(wǎng)絡、支持向量機和隨機森林建立預測模型,并進行10-折交叉驗證.

神經網(wǎng)絡由相互聯(lián)系的計算單元構成,每個計算單元執(zhí)行兩次連續(xù)的計算:輸入的線性組合;對輸入結果的非線性計算得到的輸出值作為神經網(wǎng)絡的下一個計算單元的輸入.每個計算單元的連接都有一個相關聯(lián)的權重.

支持向量機使用一種非線性映射,將原始數(shù)據(jù)映射到一個新的高維空間中,在這個新的高維空間中,有可能應用線性模型來獲得一個超平面將原數(shù)據(jù)分離.原輸入數(shù)據(jù)到較高維空間的非線性變換是在核函數(shù)的幫助下進行的.

為確定各模型的參數(shù),采用控制變量法,調節(jié)3個模型的參數(shù)并觀察模型行為,選擇最優(yōu)參數(shù),使其預測結果達到相對較好的準確率,參數(shù)優(yōu)化結果見表3.對于神經網(wǎng)絡模型,最終確定其參數(shù):隱藏層中的節(jié)點個數(shù)設為8,收斂過程中所允許使用的最大迭代次數(shù)設為300,反向傳播算法權重的更新率設為0.01;對于支持向量機,最終確定其參數(shù):使用高斯徑向基核函數(shù)K(x,y)=exp(?∥x?y∥2×gamma),gamma值設為0.1,違反邊際所引入的損失設為50;對于隨機森林,最終確定其參數(shù):森林中樹的棵數(shù)設為200,每次分裂隨機選擇的候選變量個數(shù)設為2.

表3 各模型參數(shù)設置及相應結果Tab.3 Prediction accuracy for each model using diff erent parameters

按照優(yōu)化后的參數(shù),分別構建神經網(wǎng)絡、支持向量機和隨機森林模型,在每次迭代交叉驗證完成后,計算各模型的準確率、精度與召回率.其中,準確率(Accuracy)指被正確分類的正元組和負元組占總元組的比例,衡量了預測模型的總體識別率,計算參見公式(6);精度(Precision)指被預測為正元組的元組中實際為正元組的比例,衡量了預測模型的精確性,計算參見公式(7);召回率(Recall)指實際為正元組的元組中被預測為正元組的比例,衡量了預測模型的完全性,計算參見公式(8).

其中,P(Positive)指正元組的數(shù)量;N(Negative)指負元組的數(shù)量;TP(True Positive)指實際為正元組而被分類為正元組的數(shù)量;TN(True Negative)指實際為負元組而被分類為負元組的數(shù)量; FP(False Positive)指實際為負元組而被分類為正元組的數(shù)量;FN(False Negative)指實際為正元組而被分類為負元組的數(shù)量.本文中把“嚴重”類別當做正元組,因為該類擁有更大的錯誤代價.

綜合考慮精度和召回率,可以使用F分數(shù)度量,其含義是精度和召回率的調和均值,計算公式為

為了比較各模型的有效性,另加入基準模型作為標準,一般認為只有準確率高于基準模型,該模型的建立才是有意義的.基準模型的準確率是指不使用任何指標進行預測所能達到的最大準確率,即數(shù)量占多數(shù)的類的比例.由于本文使用的數(shù)據(jù)幾乎不存在類的不平衡問題,所以基準模型的準確率約為50%.此次實驗的最終計算結果參見表4.

表4 各模型預測準確率Tab.4 Prediction accuracy for each data

3 結果分析

通過表4可以看出,在準確率方面,三個預測模型的準確率均高于基準模型的0.527 6,說明預測模型的建立是有意義的.其中隨機森林的預測準確率最高,達到0.769 9,支持向量機次之,而神經網(wǎng)絡的準確率最低,為0.729.對于樣本的總體識別率,隨機森林的表現(xiàn)最好.

精度方面,隨機森林的預測精度最高,達到0.7886,高于支持向量機的0.754以及神經網(wǎng)絡的0.7366.說明在對犯罪風險作出預測時,隨機森林的預測結果相比于神經網(wǎng)絡和支持向量機要更精確,其結果的含金量更高.

召回率方面,隨機森林的預測召回率也是最高,達到0.7192,高于支持向量機的0.7131以及神經網(wǎng)絡的0.6897.說明對于所有的有嚴重犯罪傾向的犯罪嫌疑人,隨機森林作出的預測結果相比于神經網(wǎng)絡和支持向量機覆蓋率更高.

一般而言,預測的精度與召回率之間趨向于呈現(xiàn)逆關系,提高一個的代價往往是降低另外一個,然而,隨機森林在兩方面相較于其他模型都表現(xiàn)良好,體現(xiàn)在F分數(shù)上就是,隨機森林的F分數(shù)取得0.752 3,高于神經網(wǎng)絡的0.712 4以及支持向量機的0.733.

穩(wěn)定性方面,隨機森林0.018 4的總體準確率標準差也是最穩(wěn)定的一個,預測結果的波動性最小,好于神經網(wǎng)絡的0.022 4與支持向量機的0.020 8.

綜合各方面結果可以得出,隨機森林模型對于犯罪風險的預測更為出色.

4 結論

隨機森林作為一種組合分類模型,克服了單個決策樹分類時的局限性,同時對于數(shù)據(jù)的噪聲有更強的魯棒性,能夠有效地避免過度擬合的問題,并且隨著森林中樹的棵數(shù)的增加,泛化誤差趨于一個上界.實驗結果表明,針對犯罪信息噪聲多、屬性復雜的特點,隨機森林模型在風險預測中的應用相較于神經網(wǎng)絡與支持向量機模型表現(xiàn)出更好的適應性與準確性.本文運用隨機森林方法選擇的預測指標,避免了以往預測模型中指標選擇的主觀性與盲目性,也證明了指標集的選擇存在一個最優(yōu)子集,并非以往觀念中的指標越豐富越好.作為數(shù)據(jù)挖掘在犯罪領域的應用,本文提出的隨機森林犯罪風險預測模型為實際的犯罪風險預測工作提供了一定的參考.

[1]趙軍.我國犯罪預測及其研究的現(xiàn)狀、問題與發(fā)展趨勢[J].湖南大學學報(社會科學版),2011,25(3):155-160.

[2]金光,錢家麒,錢江波,等.基于數(shù)據(jù)挖掘決策樹的犯罪風險預測模型[J].計算機工程,2003,29(9):183-185.

[3]王慧,王京.屬性約簡的決策樹分類算法對未成年人犯罪行為的分析[J].中國人民公安大學學報(自然科學版),2011(4):29-32.

[4]李明,薛安榮,王富強,等.犯罪量動態(tài)優(yōu)化組合預測方法[J].計算機工程,2011,37(17):274-278.

[5]于紅志,劉鳳鑫,鄒開其.改進的模糊BP神經網(wǎng)絡及在犯罪預測中的應用[J].遼寧工程技術大學學報(自然科學版),2012, 31(2):244-247.

[6]陳鵬,胡嘯峰,陳建國.基于模糊信息粒化的支持向量機在犯罪時序預測中的應用[J].科學技術與工程,2015,15(35):54-57.

[7]HAN J W,MICHELINE K,PEI J.數(shù)據(jù)挖掘:概念與技術[M].北京:機械工業(yè)出版社,2015:245-249.

[8]BREIMAN L.Random forests[J].Machine Learning,2001,45(1):5-32.

[9]方匡南,吳見彬,朱建平,等.隨機森林研究方法綜述[J].統(tǒng)計與信息論壇,2011,26(3):32-38.

[10]林成德,彭國蘭.隨機森林在企業(yè)信用評估指標體系確定中的應用[J].廈門大學學報(自然科學版),2007,46(2):199-203.

[11]張華偉,王明文,甘麗新.基于隨機森林的文本分類模型研究[J].山東大學學報(理學版),2006,41(3):139-143.

[12]ANANTHA M P,LOUIS R I,ANDY L.Newer classifi cation and regression tree techniques:Bagging and random forests for ecological Prediction[J].Ecosystems,2006,9:181-199.

[13]CAROLIN S,ANNE L B,THOMAS K,et al.Conditional variable importance for random forests[J].BMC Bioinformatics,2008,9:307-317.

[14]VERIKAS A,GELZINIS A,BACAUSKIENE M.Mining data with random forests:A survey and results of new tests[J].Pattern Recognition,2011,44:330-349.

[15]RAMON D U,SARA A.Gene selection and classifi cation of microarray data using random forest[J].BMC Bioinformatics,2006,7:3-15.

[16]姚登舉,楊靜,詹曉娟.基于隨機森林的特征選擇算法[J].吉林大學學報(工學版),2014,44(1):137-141.

[17]CAROLIN S,ANNE L B,ACHIN Z,et al.Bias in random forest variable importance measures:Illustrations, sources and a solution[J].BMC Bioinformatics,2007,8:25-45.

(責任編輯：李藝)

A forecasting model of crime risk based on random forest

WANG Yu-chen,GUO Zhong-yang,WANG Yuan-yuan
(School of Geographic Sciences,East China Normal University,Shanghai 200241,China)

Crime prediction has always been an outstanding issue for public security department.Random forest is a combined classification method with high accuracy,high speed,and stable performance,which is suitable for solving the problem of predicting crime risk.In the meantime,this method can choose the index group for predicting crime risk more objectively.As proved by studies,the index group chosen by random forest method can signifi cantly improve the accuracy of prediction,and the predictive model based of this method is more accurate and stable,so it can meet the demand of crime risk prediction.

random forest;crime risk prediction;index group selection

TP18

A

10.3969/j.issn.1000-5641.2017.04.008

1000-5641(2017)04-0089-08

2016-06-28

國家自然科學基金人才培養(yǎng)項目(J1310028)

王雨晨,男,碩士研究生,研究方向為數(shù)據(jù)挖掘.E-mail：wangyc ecnu@qq.com.

過仲陽,男,教授,博士生導師,研究方向為數(shù)據(jù)挖掘和遙感圖像處理. E-mail：zyguo@geo.ecnu.edu.cn.