基于属性重要度约简算法在数据挖掘中的应用研究论文.docx

基于属性重要度约简算法在数据挖掘中的应用研究论文

摘要：属性约简是粗糙集理论研究的核心内容之一，本文通过对属性重要度的计算，以核为基础计算条件属性集中除核以外其他属性的重要性来确定最小的约简，最后通过实例分析验证了算法的有效性与可行性。关键词：数据挖掘属性约简重要度数据挖掘是从海量的且不断动态变化的数据中，借助有效的方法挖掘出潜在、有价值的知识过程。而粗糙集理论它是一种刻画不完整性和不确定性的数学工具，能在保持分类能力不变的前提下，通过知识约简从中发现隐含的知识，揭示潜在的规律，是由波兰科学家Pawlak在1982年提出的。而属性约简是粗糙集理论研究的核心内容之一，它能保证在分类能力不变的情况下，消除重复、冗余的属性和属性值，减少数据挖掘要处理的信息量，提高数据挖掘的效率。本文提出了通过计算单个属性的重要性，以重要性大于零的属性为核，来选取其它属性加入核中形成新的集合RED，直至剩下的所有属性的重要性为零，得到的集合REDn即为属性约简。1粗糙集的基本理论[1-2]定义1设是一个信息系统，其中是对象的非空有限集合，即;是属性的非空有限集合;，是属性的值域;是一个信息函数，即每个对象在每个属性上对应的`信息值。若，其中为非空有限条件属性集合，为非空有限决策属性集合，且，则称信息系统为决策表。定义2对决策表，，，考虑单决策属性的情况，即，则的分辨矩阵是一个矩阵，其中的元素定义如下：定义3对分辨矩阵中每个，用布尔函数来表示，若，则决策表的分辨函数可定义为：。2基于粗糙集的数据挖掘的属性约简算法[3-4]2.1算法分析第一步：求核。通过求条件属性C中的每个属性a对在整个条件属性集C的重要性SigC(x)来确定属性核CORE(x)，重要性SigC(x)>0的属性为核属性。第二步：通过向属性核CORE(x)中依次加入重要性大的属性来确定属性集x的最小约简，详细步骤如下：(1)把a加入到属性集R中，计算重要性，选择重要性最大的属性;(2)如果两个属性有相同的重要性，取离散值小的属性。2.2算法复杂度通过算法的分析，在对决策表进行划分的时间复杂度为O(n2)。而计算条件属性的重要性也是满足划分的线性关系，因此所求属性核的时间复杂度为O(n2)，依次添加次重要度的属性也没有增加额外的开销，因此整个时间复杂度还是O(n2)。2.3实例及分析为了进一步验证算法的可行性，下面以表1中的决策表为例进行分析说明，其中对象集，条件属性集，决策属性。以上对计算出的实验数据的重要性进行统计得出信息系统的两个约简为{c1,c4}和{c2,c4}。3结语本文针对属性约简算法中的属性重要度的计算来确定核，适合对海量数据的挖掘，不仅节省了存储空间，而且在时间复杂度开销少，通过实验分析验证了算法的可行性与有效性，为决策表的属性约简提供了一条高效的途径。参考文献：[1]张文修,吴伟志.粗糙集理论与方法[M].北京:科学出版社,2001:18-19[2]周献中,黄兵，李华雄,等.不完备信息系统知识获取的粗糙集理论与方法[M].南京:南京大学出版社,2010:10-11[3]饶泓,夏叶娟,李娒竹.基于分辨矩阵和属性重要度的规则提取算法[J].计算机工程与应用，2008,44(3):163-165[4]黄国顺,刘云生.一种改进的决策表属性重要性及其快速约简算法[J].计算机工程与应用,2007,43(28):173-176