刑事案件的属性约简聚类算法研究.doc

刑事案件的属性约简聚类算法研宄卢睿辽宁羿察学院公安信息系，辽宁省大连市116036摘要：为发现刑事案件的发案规律与特点，从而及时预防和打击犯罪，本文提出了刑事案 件的属性约简K-means聚类算法该算法首先通过属性约简去除冗余属性，以属性重要度大 小设置权重，然后将K-means算法作以改进以实现聚类分析采用某地区刑事案件相关的样 本数据对算法可行性和有效性进行仿真测试，结果证明该算法的优势在于降低了数据规模, 并可获得较高且稳定的准确率关键词：籼糙集；属性约简；属性重要度；聚类；刑事案件分析一、 引言公安机关积累了大量犯罪数据，为避免出现“数据丰富，知识贫乏”的现象，如何利用 这些犯罪数据是公安机关迫切需要研宂的课题利用数据挖掘方法对公安机关积累的海量犯 罪数裾进行深入研究，可以发现刑事案件中相似案件的发展趋势，探寻犯罪的规律与特点, 对及时预防和打击犯罪具有重要的理论和现实意义贝叶斯网络、粗糙集方法、决策树和祌 经网络等数据挖掘方法在零售业、保险业、制造业、电信、医学等领域得到了较好的应用， 但在公安情报工作的研究中尚处于起步阶段，尤其是对公安系统刑事案件的侦查决策方面的 深入应用还较少见"’2]。

传统K-means算法处理离散的数伉型数据时速度快、效率商，但对符号型和连续型数裾 的处理能力较弱,特别是在处理孤立点和噪声数据时，算法效率较低;对于高维数据，K-means 算法的正确性较低，运算吋间较长并且，因其对每个属性赋以相同权重，容易瞄入“维数 陷阱” [31另外，K-means算法得到的不是全局最优解，而是局部最优解针对传统算法的以上不足，本文提出属性约简的刑事案件聚类算法，其核心思想是利用 籼糙集中的属性约简理论去除冗余属性，依据每个属性的重要程度对其赋以不同权重，对 K-means算法进行改进，并采用刑事案件数据实施聚类分析二、 相关理论属性约简是粗糙集知识发现的核心A容之一，它描述了信息系统属性集中每个属性是否 是必要的，以及如何删除不必要的知识高效的属性约简算法是知识发现的基础，但研宄表 明求解属性的最小约简是NP-hardfu）题，因此要在有限的时间内获得约简，通常采川基于启 发式知识的约简方法作为一种信息呈判断的手段，属性重要度度量了属性对信息系统的分 类能力基于属性重要度的约简算法以属性重要度作为启发信息,从而找到信息系统的某- 个约简，此约简是最优解或次优解。

2.1粗糙集理论定义1[4’51信息系统可用四元组S = （（7，A，V，/）表示，其中：（/二｛xa，…，x,,｝表示研 究对象的集合，即论域；A = CUD, A是属性的集合，C表示条件属性集，＞表示决策 属性集；V = Uv,, Vf/E A, 表示属性的值域；/ = /是信息函数，对xef/，4 有 /（X，6Z）G Va定义 2[“]等价关系/7V>(B) = {(x，y)et/xC/:VZ^fi，&(x) = ^(y)},其中厶 eA,x^yeU ,称x和y关于B是不可分辨的定义3115］给定论域y上等价关系类P ,则P在论域t/上导出的划分为m兀=U ! IND(P) = {X，X2，…，XM}，且满足：(1) ； (2) X = U X.:/=1(3)X,•门；定义4［4’5］给定一个知识库A： = (t/，S)和知识库中的一个等价关系族尸eS, V/?gP,若IND(P) = IND(p - {R})成立，则称知识/?为尸中必要的，尸中所有必要的知识组成的集合称P的核，记为CORE(P)可以证明核是所有约简的交集，且核具有唯一性定义5［4’51给定一个知识库尺= ((7，S)和知识库中的一个等价关系族尸eS,对任意的GoP,若G满足以下两条：(1) G是独立的；(2) /^(^//^(/^，则称^是户的一个约简，记为GeRED(P)，其中/?>(尸)表示尸的全体约简的集合。

定义［45］6设给定信息系统S = (t/，A，V，/)，Vfi［C以及VtzeC —B,属性u对属 性集g的重要度为珣(坎c) = card(u，1 卿U⑷))-card{U!扁⑽，其中azr6f(f/)表示集合(7的基数2.2 K-means聚类算法K-meems聚类算法又称群分析算法，聚类是对数据库中物理的或抽象的对象集合进行分 组的过程，其结果是使同一簇中的数据具有较高的相似度，不同簇中的数据对象具有较高的 相异性K-means算法的主要思想是试图对n个对象给出k个划分，其中每个划分代表一个簇 首先，随机地选择k个对象，每个对象初始地代表一个簇的平均值或中心对剩余对象，根 据其与各个簇中心的距离，将它赋给最近的簇然后重新计算每个簇的平均值，对数据库中 的每个对象与每个簇的平均值相比较，把对象赋给最相似的某个簇这个过程不断重复，直 到簇巾的对象都是相似的，而不同簇中的对象都是相异•的，即准则函数收敛使平A误差函数 值最小其准则函数定义为d = xf 其中，6/是数据集中所有对象的平方误差•=1 xeQ9和，JC是空间中的点，是簇Cz的均值［5］利用K-means聚类算法对刑事案件信息作数据分析，其工作流程是把案件记录加以整理 归类形成样本数据，将案件信息内容、情节等进行数裾挖掘，将相似特征的案件从公安数椐 库中分拣出来，以形成专门的刑事案件特征数据库。

通过搜索案件中人部分犯罪具有的特征 信息，根据不同分类，将犯罪特征应用到该类其它案件的侦破中去，为犯罪案件的串并及破 案提供有益帮助16］三、刑事案件的属性约简聚类算法本算法的核心思想是利用属性约简去除冗余属性，依据每个属性的重要程度对其赋以不 同权重，利用改进K-means算法对刑事案件数据实施聚类分析描述如下：(1) 在改进的算法中，首先利用粗糙集对数据对象进行预处理在公安刑事案件源数 裾库中，很多记录不完整、不一致，还有一些错误的信息，因此在预处理阶段要清理所有聚 类分析的相关属性值对于空值和不一致数据，可以采取忽略元组、人工填写及填充均值等 方法进行处理在数据大致完整后，由于K-means算法应用条件要求离散数值型数据，因此 将案件属性值根据其类型定义为二值变量、整型变量和区间型变量[712) 刑事案件数据的某些冗余属性和干扰属性与犯罪倾向的关联性小，保留它们会增 加算法复杂度，降低准确率本算法中以约减算法删除冗余属性，从而减少运算时间；为使 不同属性在计算中发挥不同作用，对各属性赋以不同权重，因此聚类算法结果更具客观性, 更符合公安情报分析的实际需要3) 为破除“维数陷阱”现象，避免属性权重一致而影响聚类精度，令属性权重为权重—经确定，则去除传统算法中的欧氏距离，以加权距离式 7=1kd又 xk, = •(〜-〜))2来替代。

7=1根据以上分析，该算法的主要步骤描述如下：输入:信息系统5 = ([/，4,7，/)和簇数仑输出：簇集N = {N具…，Nk}Step 1:设 /? = 0 ;Step2： A,如果IND(4\{tz})弇 IND(4)，/?仁/?URz}，CORE(A)=/?；Step3：令 B = CORE(A)，如果/ND(B) = IND(A)，输出 BeRED(A),转 Step5， 否则转Step4；Step4： Vaz. g A\B,计算属性重要度sig(apB; A),求得 a* = arg max sig(“pB; A),其中arg表示取重要度达到最大的参数；如果满足sighAM)的属性有多个，则选取划分个数最小的属性即人•满足min|[/\/；VZ)(6f)|，转Step2;Step5:对于经过约简的样本数据集，…，计算*的权重并以随机9选取的々个样本作为初始聚类中心；Step6：对X中剩余的样本，汁算其与初始聚类中心的距离，并依此将其归类于与其S 为相似的中心；Step7：计算每个新类的聚类中心；Step8：不断重复Step6和Step7,直到所有样本点的分布不再改变或类中心不再改变，即6/（，C,.）不再变化。

四、实验分析表1刑事案件属性属性符号属性内容A,作案特点入室作案、单独作案、共同作案a2作案手段溜门、从门侵入、破坏窗栅、撬门a3作案地点镇、城区、郊区A4作案工具枪、刀、棍棒、其它a5案件交通工具摩托车、助动车、徒步A6涉案人员年龄少年、青年、中年、老年a7涉案人员性别男、女As入侵方式溜门、从门侵入、从窗侵入、橇门A9涉案人K职业务工农民、无业人员、其他A10选择对象钱财和其他从刑事案例库中抽取200例入室抢劫案件的样本数据，该数据包括10个属性，分别为 作案特点、作案手段、作案地点、作案工具、案件交通工具、涉案人员年龄、涉案人员性别、 入侵方式、涉案人员职业和选择对象，如表1所示利用本文算法对10个属性｛ Al，A2, A3, A4，A5，A6，A7，A8,A9，A10｝的重要性程度进行计算与约简，得出｛ Al，A2, A6, A8, A9, A10｝ 为重要属性将约简结果中的重要属性值分别除以其最大值处理后如图1所示1.00000.99000.98000.97000.96000.95000.94000.9300图1属性约简后重要性百分比所抽取的200例刑事案件样本数据集巾的60%作为训练集，其余40%作为测试集，训 练后，训练集中120条数据被分为5类，每类中聚合数量分别为22条、24条、45条、16 条和13条。

根据训练集所得模型，对测试集中80条数据进行聚类划分，得到前3类所占的 比重偏大，如表2所示表2刑事案件聚类结果类别案件数目所占百分比案件特征01620%作案特点=入室作案；作案手段=撬门；作案地点=镇；入 侵方式=撬门；涉案人员职业=务工农民；选择对象=钱财 作案特点=共同作案；作案手段=从门侵入；作案地点=城12025%区；入侵方式=从门侵入；涉案人员职业=务工农民；选择 对象=钱财22329%作案特点=入室作案；作案手段=从门侵入；作案地点=城 区；入侵方式=从门侵入；涉案人员职业=无业人员；选择3911%对象=其他作案特点=单独作案；作案手段=破坏窗栅；作案地点=郊 区；入侵方式=从窗侵入；涉案人员职业=其他；选择对象41215%=钱财作案特点=单独作案；作案手段=破坏窗栅；作案地点=郊 区；入侵方式=从窗侵入；涉案人员职业=无业人员；选择对象=钱财表2表明涉案人员职业与犯罪具有一定的相关关系，即在犯罪分子中，无业人员或务工 农民发生入室抢劫的概率较大，而这种现象与事实情况相符为验证本文法的性能，采用以上刑事案件数据，将文献［8］的k-means法与本文算 法的结果进行比较，均釆用运算10次后所得的平均残差平方和来判断聚类结果的准确程度， 所得的平均残差平方和数值越小，说明同一类中的距离越小，聚类的准确程度越高。

表3刑事案件数据的算法效果比较算法平均残差平方和k-means 算法[8]157.0本文提山改进算法125.0由表3可见，本文算法的平均残差平方相比文献［8j的算法具有较大优势，可以得到较 高且稳定的准确率，其原因是本文算法去除属性集中的冗余属性后聚类结果变得更为清晰, 而且数据经过预处理后数据结构得以精简，从而使数据规模降低，聚类质B:提高，并且使聚 类算法实现变得更为简单为了验证算法的准确性和一般性，从国际通用机器。