资源描述：
《刑事案件的属性约简聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、刑事案件的属性约简聚类算法研宄卢睿辽宁羿察学院公安信息系，辽宁省大连市116036摘要：为发现刑事案件的发案规律与特点，从而及时预防和打击犯罪，本文提出了刑事案件的属性约简K-means聚类算法。该算法首先通过属性约简去除冗余属性，以属性重要度大小设置权重，然后将K-means算法作以改进以实现聚类分析。采用某地区刑事案件相关的样本数据对算法可行性和有效性进行仿真测试，结果证明该算法的优势在于降低了数据规模,并可获得较高且稳定的准确率。关键词：籼糙集；属性约简；属性重要度；聚类；刑事案件分析一、引言公安机关积累了大量犯罪数据，为避免出现“数据丰富，知识贫乏”的现象，如何利用这些犯罪
2、数据是公安机关迫切需要研宂的课题。利用数据挖掘方法对公安机关积累的海量犯罪数裾进行深入研究，可以发现刑事案件屮相似案件的发展趋势，探寻犯罪的规律与特点,对及时预防和打击犯罪具有重要的理论和现实意义。贝叶斯网络、粗糙集方法、决策树和祌经网络等数据挖掘方法在零售业、保险业、制造业、电信、医学等领域得到了较好的应用，但在公安情报工作的研究中尚处于起步阶段，尤其是对公安系统刑事案件的侦查决策方面的深入应用还较少见"’2]。传统K-means算法处理离散的数伉型数据时速度快、效率商，但对符号型和连续型数裾的处理能力较弱,特别是在处理孤立点和噪声数据时，算法效率较低;对于高维数据，K-mean
3、s算法的正确性较低，运算吋间较长。并且，因其对每个属性赋以相同权重，容易瞄入“维数陷阱”[31。另外，K-means算法得到的不是全局最优解，而是局部最优解。针对传统算法的以上不足，本文提出属性约简的刑事案件聚类算法，其核心思想是利用籼糙集屮的属性约简理论去除冗余属性，依据每个属性的重要程度对其赋以不同权重，对K-means算法进行改进，并采用刑事案件数据实施聚类分析。二、相关理论属性约简是粗糙集知识发现的核心A容之一，它描述了信息系统属性集屮每个属性是否是必要的，以及如何删除不必要的知识。高效的属性约简算法是知识发现的基础，但研宄表明求解属性的最小约简是NP-hardfu）题，因
4、此要在有限的时间内获得约简，通常采川基于启发式知识的约简方法。作为一种信息呈判断的手段，属性重要度度量了属性对信息系统的分类能力。基于属性重要度的约简算法以属性重要度作为启发信息,从而找到信息系统的某-个约简，此约简是最优解或次优解。2.1粗糙集理论定义1[4’51信息系统可用四元组S=（（7，A，V，/）表示，其中：（/二｛xa，…，x,,｝表示研究对象的集合，即论域；A=CUD,A是属性的集合，C表示条件属性集，£＞表示决策属性集；V=Uv,,Vf/EA,表示属性的值域；/=/是信息函数，对xef/，4有/（X，6Z）GVa。定义2[“]等价关系/7V£>(B)={(x，y)e
5、t/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=UX.:/=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)和知识
6、库中的一个等价关系族尸eS,对任意的GoP,若G满足以下两条：(1)G是独立的；(2)/^(^//^(/^，则称^是户的一个约简，记为GeRED(P)，其屮/?££>(尸)表示尸的全体约简的集合。定义［4'5］6设给定信息系统S=(t/，A，V，/)，Vfi［C以及VtzeC—B,属性u对属性集g的重要度为珣(。，坎c)=card(u，1卿U⑷))-card{U!扁⑽，其中azr6f(f/)表示集合(7的基数。2.2K-means聚类算法K-meems聚类算法又称群分析算法，聚类是对数据库中物理的或抽象的对象集合进行分组的过程，其结果是使同一簇中的数据具有较高的相似度，不同簇中的数
7、据对象具有较高的相异性。K-means算法的主要思想是试图对n个对象给出k个划分，其中每个划分代表一个簇。首先，随机地选择k个对象，每个对象初始地代表一个簇的平均值或中心。对剩余对象，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值，对数据库屮的每个对象与每个簇的平均值相比较，把对象赋给最相似的某个簇。这个过程不断重复，直到簇巾的对象都是相似的，而不同簇中的对象都是相异•的，即准则函数收敛使平A误差函数值最小。其准则函数定义为d=xf其中，6/是
