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

来源:用户上传      作者:闫普虹 黄润才 姜川 孙园园 孙刘成 王从澳

　　摘要：当今，恐怖分子作案的多样性和复杂性给相关机构的破案大大增加了难度，如何迅速简便地发现隐藏的恐怖分子，是安全机构最为关心的问题。本文基于K-prototype聚类算法，依据恐怖事件发生的数据特征，运用SPSS软件对此数据进行标准化处理，得出恐怖分子典型事件的嫌疑度样例的特征向量，通过Python进行聚类分析，得到五类别聚类中心分布图。实验结果验证了方法的可行性与有效性，为安全机构对恐怖分子嫌疑度的划分提供了一种分析方法。
　　关键词： 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”恐怖袭击以来，恐怖主义的危害性，以及恐怖袭击形式的多样化和复杂化的演变，引起了全社会的关注与重视。研究中发现因恐怖袭击者的由精心策划到“独狼式”随机游走暴动袭击，再加上网络化、全球化的发展，以及没有先验知识分类的影响恐怖袭击发生因素[1]，使许多恐怖案件的侦破变得更加棘手和困难，针对于这些没有事先的经验或一些国际、国内、行业标准的恐怖袭击案件，要对嫌疑程度进行划分和判别，如果直接分类便会显得随意和主观，不能得到科学合理的判断结果，对于海量数据上的处理也不现实。鉴于以上原因，研究可知聚类分析可以根据对象的内在属性，将其聚集成为不同的簇，每一个簇内部相似度高，簇之间差异度大。利用聚类分析的这种特点，可以对海量涉恐情报数据进行自动化、智能化的处理。通过引入以K-means改进的K-prototype聚类分析算法对标准化后的样本数据进行分析，发现内部高度相似的恐怖团伙，并在此基础上提炼恐怖团伙之间的关系，提升政府、公安机关分析反恐情报的能力和水平，进而提升打击恐怖主义的工作效能[2]，对于政府及公安机关尽早发现新生或隐藏的恐怖分子有着重要的意义与价值。
　　1 引入多层聚类算法划分恐怖分子嫌疑程度的背景
　　对于恐怖袭击者嫌疑程度的划分这一问题，现有的成果存在一定问题，缺乏科学方法对样本分类的预处理，只是单独地分析某一地区的情况，或在整体上缺乏对其中重点国家的关注，在新态势上，泛泛而谈者居多，没有对袭击者主题数据进行预处理，或以偏概全，未区分具体国家恐怖袭击事件的发生频度;在原因分析上，单项分析居多，缺乏整体性和完整性，恐怖袭击者嫌疑程度的区分是多种因素相互影响的一个结果，在分析中应该规避单一化或绝对化，以免得到错误的结论。划分聚类可用在对于一个包含n个多维对象的集合D，划分出k（k≤n）个子集合，每个子集合就是一个簇。对于本文研究的主题而言，利用划分聚类可以有效地发现潜在的涉恐人员群体。集合D是公安机关掌握的人员的总体，集合中的每一个对象就是一个人员的信息。研究时要识别一个人是否是恐怖分子或者潜在的恐怖分子，仅仅根据单一的指标是无法做到的，必须要根据恐怖分子的历史数据，建立一个基于人员个人信息、活动轨迹、社会交往等多个方面多个指标构成的一个评价体系，因此文中要分析的每一个对象都是多维度的。
　　2 基于划分的聚类分析恐怖分子嫌疑程度模型建立与算法实现2.1 [ZK（]基于K-means聚类恐怖袭击者嫌疑程度划分算法实现
　　基于划分的聚类算法可以说是一种基于原型的聚类方法，首先将恐怖袭击事件数据集的对象初始划分为K组，每一组表示一个簇，然后反复利用迭代重定位技术将反恐案件在各个簇中重新划分。其中，初始划分原則是：每个簇中至少有一个案件，每个案件只能属于一个簇。好的划分结果标准是：簇内案件特征尽量接近，簇间案件特征互相远离[3-4]。聚类分析法是一种探索性分析方法，能够分析事物的内在特点和规律，并根据相似性原则对事物进行分组，是数据挖掘中常用的一种技术。K-means基本思想是：在数据集中随机选择一个样本点作为第一个初始化的聚类中心。选择出其余的聚类中心： 计算样本中的每一个样本点与已经初始化的聚类中心之间的距离，并选择其中最短的距离，记为d-i以概率选择距离最大的样本作为新的聚类中心，重复上述过程，直到k个聚类中心都被确定对k个初始化的聚类中心，利用K-Means算法计算最终的聚类中心[5]。综上可得，算法的整体描述见如下。 　　 至此，研究得到的算法步驟详述如下。
　　输入：聚类簇的个数k， 权重因子
　　输出：产生好的聚类
　　Step 1 从数据集中随机选取k个对象作为初始的k个簇的原型。
　　Step 2 遍历数据集中的每一个数据，计算数据与k个簇的相异度。再将该数据分配到相异度最小的对应的簇中，每次分配结束后，更新簇的原型，并计算目标函数。
　　Step 3 对比目标函数值是否改变，循环直到目标函数值不再变化为止。
　　3 实验与仿真分析
　　根据模式之间的相似性对模式进行分类，K-prototype算法是一种非监督分类方法。相似性的含义为：有n个特征值则组成n维向量X=[x1，x2，…，xn]，X称为该样本的特征向量。这相当于特征空间中的一个点，以特征空间中，点间的距离函数作为模式相似性的测量，以“距离”作为模式分类的依据，距离越小，越“相似”[6]。
　　首先在样本数据中筛选出任务二给出的恐怖分子关于典型事件的10个样例所对应的数据，运用SPSS软件对此数据进行标准化处理，然后进行聚类分析，最后得出各个事件相对应的特征向量。恐怖分子关于典型事件10个样例的特征向量如图1所示，嫌疑程度判断框图如图2所示。
　　 在此基础上，筛选出近两年发生的、尚未有组织或个人宣称负责的恐怖袭击事件后，要选取影响恐怖分子关于嫌疑度的影响因素，这里选取的影响因素有：country，extended，crit1，crit2，crit3，doubtterr，success，suicide，attacktype1，targtype1，weaptype1。针对近两年发生的、尚未有组织或个人宣称负责的恐怖袭击事件在选取影响因素下的数据，将其在SPSS软件中进行标准化处理;而后将标准化数据导入Excel表格;基于K-prototype算法，用Python对Excel表格中数据进行聚类分析;k=n时，可将其聚为n类，但根据程序结果图形可知，将其聚为5类时效果最佳[7]。仿真生成的聚类图如图3所示。
　　4 结束语
　　实验证明，K-prototype聚类克服了对初始化非常敏感和只能对单一数值属性聚类的缺点，对处理海量的影响恐怖袭击事件发生的样本数据可以进行快速有效的聚类分析，最终得到恐怖袭击者嫌疑划分的等级依据，即簇内案件特征尽量接近，簇间案件特征互相远离的标准，通过Python进行聚类分析，得到5类聚类中心图[8-9]，又绘制出恐怖分子关于典型事件嫌疑度的直观描述图形，并按个人的危害性从大到小选出其中的前5个进行嫌疑程度排序，给相关安全机构统一组织侦查和提高破案率提供了一种技术支持。
　　参考文献
　　[1]   陈安，陈宁，周龙骧.  数据挖掘技术与应用[M].  北京：科学出版社，2006.
　　[2]夏颖，王哲，程琳.  聚类分析在犯罪数据分析中的应用[J]. 合肥工业大学学报（自然科学版），2009，32 （12） ：1924.
　　[3]马立平. 聚类分析法[J]. 北京统计，2000（5）：36.
　　[4]王千，王成，冯振元，等. K-means聚类算法研究综述 [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]. 计算机工程与应用 ，2014，50（21）：125.
　　[8] 陈磊磊. 不同距离测度的 K-Means 文本聚类研究 [J]. 软件 ，2015，36（1）：56.
　　[9]陈小雪，尉永清，任敏，等. 基于萤火虫优化的加权K-means算法[J]. 计算机应用研究 ，2018，35（2）：466.
　　[10]向培素. 聚类算法综述[J]. 西南民族大学学报（自然科学版），2011（S1） ： 112.
　　[11]贾瑞玉，李玉功. 类簇数目和初始中心点自确定的 K-means 算法 [J]. 计算机工程与应用 ，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.
转载注明来源:https://www.xzbu.com/8/view-15265679.htm