基于K-prototype聚類算法恐怖分子嫌疑度的劃分

閆普虹 黃潤才 姜川 孫園園 孫劉成 王從澳

摘要：當(dāng)今，恐怖分子作案的多樣性和復(fù)雜性給相關(guān)機(jī)構(gòu)的破案大大增加了難度，如何迅速簡便地發(fā)現(xiàn)隱藏的恐怖分子，是安全機(jī)構(gòu)最為關(guān)心的問題。本文基于K-prototype聚類算法，依據(jù)恐怖事件發(fā)生的數(shù)據(jù)特征，運用SPSS軟件對此數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，得出恐怖分子典型事件的嫌疑度樣例的特征向量，通過Python進(jìn)行聚類分析，得到五類別聚類中心分布圖。實驗結(jié)果驗證了方法的可行性與有效性，為安全機(jī)構(gòu)對恐怖分子嫌疑度的劃分提供了一種分析方法。

關(guān)鍵詞： k-mean++; 嫌疑度; Python; K-prototype聚類

【Abstract】 Currently， the diversity and complexity of terrorist crimes have greatly increased the difficulty of solving relevant cases. How to quickly and easily discover hidden terrorists is the most concerned issue of security agencies. Based on the K-prototype clustering algorithm， this paper uses SPSS software to standardize the data according to the data characteristics of terrorist events， and obtains the feature vector of the suspected terrorist sample. The clustering analysis is performed by Python. Five categories of cluster center distribution map are given out. The experimental results verify the feasibility and effectiveness of the method， and provide an analysis method for the security agencies to divide the terrorists' suspect degree.

【Key words】 ?k-mean++; ?suspicion; Python; K-prototype cluster analysis

0 引 言

自美國“911”恐怖襲擊以來，恐怖主義的危害性，以及恐怖襲擊形式的多樣化和復(fù)雜化的演變，引起了全社會的關(guān)注與重視。研究中發(fā)現(xiàn)因恐怖襲擊者的由精心策劃到“獨狼式”隨機(jī)游走暴動襲擊，再加上網(wǎng)絡(luò)化、全球化的發(fā)展，以及沒有先驗知識分類的影響恐怖襲擊發(fā)生因素[1]，使許多恐怖案件的偵破變得更加棘手和困難，針對于這些沒有事先的經(jīng)驗或一些國際、國內(nèi)、行業(yè)標(biāo)準(zhǔn)的恐怖襲擊案件，要對嫌疑程度進(jìn)行劃分和判別，如果直接分類便會顯得隨意和主觀，不能得到科學(xué)合理的判斷結(jié)果，對于海量數(shù)據(jù)上的處理也不現(xiàn)實。鑒于以上原因，研究可知聚類分析可以根據(jù)對象的內(nèi)在屬性，將其聚集成為不同的簇，每一個簇內(nèi)部相似度高，簇之間差異度大。利用聚類分析的這種特點，可以對海量涉恐情報數(shù)據(jù)進(jìn)行自動化、智能化的處理。通過引入以K-means改進(jìn)的K-prototype聚類分析算法對標(biāo)準(zhǔn)化后的樣本數(shù)據(jù)進(jìn)行分析，發(fā)現(xiàn)內(nèi)部高度相似的恐怖團(tuán)伙，并在此基礎(chǔ)上提煉恐怖團(tuán)伙之間的關(guān)系，提升政府、公安機(jī)關(guān)分析反恐情報的能力和水平，進(jìn)而提升打擊恐怖主義的工作效能[2]，對于政府及公安機(jī)關(guān)盡早發(fā)現(xiàn)新生或隱藏的恐怖分子有著重要的意義與價值。

1 引入多層聚類算法劃分恐怖分子嫌疑程度的背景

對于恐怖襲擊者嫌疑程度的劃分這一問題，現(xiàn)有的成果存在一定問題，缺乏科學(xué)方法對樣本分類的預(yù)處理，只是單獨地分析某一地區(qū)的情況，或在整體上缺乏對其中重點國家的關(guān)注，在新態(tài)勢上，泛泛而談?wù)呔佣?，沒有對襲擊者主題數(shù)據(jù)進(jìn)行預(yù)處理，或以偏概全，未區(qū)分具體國家恐怖襲擊事件的發(fā)生頻度;在原因分析上，單項分析居多，缺乏整體性和完整性，恐怖襲擊者嫌疑程度的區(qū)分是多種因素相互影響的一個結(jié)果，在分析中應(yīng)該規(guī)避單一化或絕對化，以免得到錯誤的結(jié)論。劃分聚類可用在對于一個包含n個多維對象的集合D，劃分出k（k≤n）個子集合，每個子集合就是一個簇。對于本文研究的主題而言，利用劃分聚類可以有效地發(fā)現(xiàn)潛在的涉恐人員群體。集合D是公安機(jī)關(guān)掌握的人員的總體，集合中的每一個對象就是一個人員的信息。研究時要識別一個人是否是恐怖分子或者潛在的恐怖分子，僅僅根據(jù)單一的指標(biāo)是無法做到的，必須要根據(jù)恐怖分子的歷史數(shù)據(jù)，建立一個基于人員個人信息、活動軌跡、社會交往等多個方面多個指標(biāo)構(gòu)成的一個評價體系，因此文中要分析的每一個對象都是多維度的。

2 基于劃分的聚類分析恐怖分子嫌疑程度模型建立與算法實現(xiàn)2.1 [ZK（]基于K-means聚類恐怖襲擊者嫌疑程度劃分算法實現(xiàn)

基于劃分的聚類算法可以說是一種基于原型的聚類方法，首先將恐怖襲擊事件數(shù)據(jù)集的對象初始劃分為K組，每一組表示一個簇，然后反復(fù)利用迭代重定位技術(shù)將反恐案件在各個簇中重新劃分。其中，初始劃分原則是：每個簇中至少有一個案件，每個案件只能屬于一個簇。好的劃分結(jié)果標(biāo)準(zhǔn)是：簇內(nèi)案件特征盡量接近，簇間案件特征互相遠(yuǎn)離[3-4]。聚類分析法是一種探索性分析方法，能夠分析事物的內(nèi)在特點和規(guī)律，并根據(jù)相似性原則對事物進(jìn)行分組，是數(shù)據(jù)挖掘中常用的一種技術(shù)。K-means基本思想是：在數(shù)據(jù)集中隨機(jī)選擇一個樣本點作為第一個初始化的聚類中心。選擇出其余的聚類中心： 計算樣本中的每一個樣本點與已經(jīng)初始化的聚類中心之間的距離，并選擇其中最短的距離，記為d-i以概率選擇距離最大的樣本作為新的聚類中心，重復(fù)上述過程，直到k個聚類中心都被確定對k個初始化的聚類中心，利用K-Means算法計算最終的聚類中心[5]。綜上可得，算法的整體描述見如下。

至此，研究得到的算法步驟詳述如下。

輸入：聚類簇的個數(shù)k， 權(quán)重因子

輸出：產(chǎn)生好的聚類

Step 1 從數(shù)據(jù)集中隨機(jī)選取k個對象作為初始的k個簇的原型。

Step 2 遍歷數(shù)據(jù)集中的每一個數(shù)據(jù)，計算數(shù)據(jù)與k個簇的相異度。再將該數(shù)據(jù)分配到相異度最小的對應(yīng)的簇中，每次分配結(jié)束后，更新簇的原型，并計算目標(biāo)函數(shù)。

Step 3 對比目標(biāo)函數(shù)值是否改變，循環(huán)直到目標(biāo)函數(shù)值不再變化為止。

3 實驗與仿真分析

根據(jù)模式之間的相似性對模式進(jìn)行分類，K-prototype算法是一種非監(jiān)督分類方法。相似性的含義為：有n個特征值則組成n維向量X=[x1，x2，…，xn]，X稱為該樣本的特征向量。這相當(dāng)于特征空間中的一個點，以特征空間中，點間的距離函數(shù)作為模式相似性的測量，以“距離”作為模式分類的依據(jù)，距離越小，越“相似”[6]。

首先在樣本數(shù)據(jù)中篩選出任務(wù)二給出的恐怖分子關(guān)于典型事件的10個樣例所對應(yīng)的數(shù)據(jù)，運用SPSS軟件對此數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，然后進(jìn)行聚類分析，最后得出各個事件相對應(yīng)的特征向量。恐怖分子關(guān)于典型事件10個樣例的特征向量如圖1所示，嫌疑程度判斷框圖如圖2所示。

在此基礎(chǔ)上，篩選出近兩年發(fā)生的、尚未有組織或個人宣稱負(fù)責(zé)的恐怖襲擊事件后，要選取影響恐怖分子關(guān)于嫌疑度的影響因素，這里選取的影響因素有：country，extended，crit1，crit2，crit3，doubtterr，success，suicide，attacktype1，targtype1，weaptype1。針對近兩年發(fā)生的、尚未有組織或個人宣稱負(fù)責(zé)的恐怖襲擊事件在選取影響因素下的數(shù)據(jù)，將其在SPSS軟件中進(jìn)行標(biāo)準(zhǔn)化處理;而后將標(biāo)準(zhǔn)化數(shù)據(jù)導(dǎo)入Excel表格;基于K-prototype算法，用Python對Excel表格中數(shù)據(jù)進(jìn)行聚類分析;k=n時，可將其聚為n類，但根據(jù)程序結(jié)果圖形可知，將其聚為5類時效果最佳[7]。仿真生成的聚類圖如圖3所示。

4 結(jié)束語

實驗證明，K-prototype聚類克服了對初始化非常敏感和只能對單一數(shù)值屬性聚類的缺點，對處理海量的影響恐怖襲擊事件發(fā)生的樣本數(shù)據(jù)可以進(jìn)行快速有效的聚類分析，最終得到恐怖襲擊者嫌疑劃分的等級依據(jù)，即簇內(nèi)案件特征盡量接近，簇間案件特征互相遠(yuǎn)離的標(biāo)準(zhǔn)，通過Python進(jìn)行聚類分析，得到5類聚類中心圖[8-9]，又繪制出恐怖分子關(guān)于典型事件嫌疑度的直觀描述圖形，并按個人的危害性從大到小選出其中的前5個進(jìn)行嫌疑程度排序，給相關(guān)安全機(jī)構(gòu)統(tǒng)一組織偵查和提高破案率提供了一種技術(shù)支持。

參考文獻(xiàn)

[1] ? 陳安，陳寧，周龍驤. ?數(shù)據(jù)挖掘技術(shù)與應(yīng)用[M]. ?北京：科學(xué)出版社，2006.

[2]夏穎，王哲，程琳. ?聚類分析在犯罪數(shù)據(jù)分析中的應(yīng)用[J]. 合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2009，32 （12） ：1924.

[3]馬立平. 聚類分析法[J]. 北京統(tǒng)計，2000（5）：36.

[4]王千，王成，馮振元，等. K-means聚類算法研究綜述 [J]. 電子設(shè)計工程 ，2012，20（7）：21.

[5]楊文雅. 聚類分析算法理論研究綜述[J]. 華章，2012（23）： 305.

[6]OLUKANMI P O， TWALA B. K-means-sharp： Modified centroid update for outlier-robust k-means clustering[C]// 2017 Pattern Recognition Association of South Africa and Robotics and Mechatronics（PRASA-Rob Mech），Bloemfontein：IEEE，2017：14.

[7]沈艷，余冬華，王昊雷. 粒子群 K-means聚類算法的改進(jìn) [J]. 計算機(jī)工程與應(yīng)用 ，2014，50（21）：125.

[8] 陳磊磊. 不同距離測度的 K-Means 文本聚類研究 [J]. 軟件 ，2015，36（1）：56.

[9]陳小雪，尉永清，任敏，等. 基于螢火蟲優(yōu)化的加權(quán)K-means算法[J]. 計算機(jī)應(yīng)用研究 ，2018，35（2）：466.

[10]向培素. 聚類算法綜述[J]. 西南民族大學(xué)學(xué)報（自然科學(xué)版），2011（S1） ： 112.

[11]賈瑞玉，李玉功. 類簇數(shù)目和初始中心點自確定的 K-means 算法 [J]. 計算機(jī)工程與應(yīng)用 ，2018，54（7）：152.

[12]RODRIGUEZ A，LAIO A. Clustering by fast search and find of density peaks[J]. Science，2014，344（6191）：1492.

[13]GU Lei. A novel locality sensitive k-means clustering algorithm based on subtractive clustering[C]// 2016 7th IEEE ?International Conference on Software Engineering and Service Science（ICSESS）. Beijing， China：IEEE，2017：836.

[14]XUE Wei， YANG Rongli，HONG Xiaoyu，et al. A novel k-means based on spatial density similarity measurement[C]//2017 29th Chinese Control and Decision Conference（CCDC）. Chongqing， China：IEEE，2017：7782.

[15]GANESH S H， PREMKUMAR M S. A median based external initial centroid selection method for K-Means clustering[C]//World Congress on Computing and Communication Technologies（WCCCT）. Tamil Nadu， India ：IEEE Computer Society， 2017：143.

[16]SINGH J P， BOUGUILA N. Proportional data clustering using K - means algorithm： A comparison of different distances[C]//2017 IEEE International Conference on Industrial Technology（ICIT）.Toronto， ON， Canada：IEEE，2017：1048.