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

閆普虹 黃潤(rùn)才 姜川 孫園園 孫劉成 王從澳

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

關(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 引 言

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與仿真分析

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)

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

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

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

[4]王千，王成，馮振元，等. K-means聚類算法研究綜述 [J]. 電子設(shè)計(jì)工程 ，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ì)算機(jī)工程與應(yīng)用 ，2014，50（21）：125.

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

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

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

[11]賈瑞玉，李玉功. 類簇?cái)?shù)目和初始中心點(diǎn)自確定的 K-means 算法 [J]. 計(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.