基于浓缩差别矩阵的不完备信息系统的规则获取算法研究

《基于浓缩差别矩阵的不完备信息系统的规则获取算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单位代码１０６０２学号２０１３０１１５４２分类号ＴＰ３０１级公开＾ＧＵＡＮＧＸＩＮＯＰＭＡＬＵＮＩＶＥＰＳＩＴＹ硕壬学位冷文基于浓缩差别矩阵的不完备信息系统的规则获取算法研究ＲｅｓｅａｒｃｈｏｎＡｌｇｏｒｉｔｈｍｆｏｒＲｕｌｅＡｃｑｕｉｓｉｔｉｏｎＢａｓｅｄｏｎＥｎｒｉｃｈｉｎｇＤｉｓｃｅｒｎ化ｉｌｉｔＭａｔｒｉｘｉｎＩｎｃｏｍｐｌｅｔｅＩｎｆｏｒｍａｔｉｏｎＳｓｔｅｍｓｙｙ学院：计算机科学与信息工程学院专业：软件工程研究方向：数据挖捆年级：２０１３级研究生；

2、朱金虎指导教师；ＷｍＷ陈元淡教授完成日期：２０１６年４月基于浓缩差别矩阵的不完备信息系统的规则获取算法研究工专业名称：软件程申请人：朱金虎指导教师：峰章艳Ｉ陈元玻教授论文答辩委员会＾主席：和讀ｉｓ＾委员：令术＇－４１４－基于浓缩差别矩阵的不完备信息系统的规则获取算法研究研究生姓名：朱金虎导师姓名：除章艳元谈Ｉ陈：２０１３专业：软件王程研究方向数据挖掘年级：级摘要随着科学技术的发展，，人们想要快速的搜索到、网络的普及大量的信息都得Ｗ保存一白ｄ需要的信息变得更加困难，。粗趟集理论作为种较新的软

3、计算方法目前在国际上仍一然是人工智能理论及其应用领域中的研究热点之，由于它是在模糊集、概率论及证据理一论之后出现的又个处理不确定性的数学工具，肝其能够有效的巧许多科学与工程领域中，，越来越受到人们的重视得Ｗ应用所Ｗ。粗糖集理论起初主要研究对象是针对完备信息系统的，然而现实生活中的数据可能是一遗漏型或缺省型的，传统的粗趟集理论就不能够再像原来样处理这类信息系统了。怎样利用粗趟集理论来处理这类信息系统成为了国内外学者和专家的研巧热点，他们最先想到一巧种如法来解决这类问题，种是将完备信息系统中的等价关系理论延伸到不完备信息系？统中去，

4、因而产生了容差关系和相似关系等扩展模型：另种则是通过将不完备信息系统，，然后再来处理的空缺值补充起来使它成为完备的信息系统。一规则获取是粗糖集理论的项重要研究内容，它主要包含属性约简及属性值约简。属性约简的目的是为Ｔ尽量化简原始数据，且不会改变原始数据背后的隐藏规则及数据之间，达到规则获取的目的的关系。且属性约简的结果也是为了能够更好的进行属性值约简。因而，研究粗糖集理论的多种扩展模型和知识获取方法在不完备信息系统中有着极其重要的理论与现实意义。本文在前人研究的基础么上对粗趟集理论中的属性约简Ｗ及规则获取方面进行了研究学习，主要

5、进行了下面Ｓ个方面的研究：，１）差别矩阵方法因简单方便，被许多学者使用。然而，对于现实中所面对的海量数据（传统的差别矩阵方法不仅费时且占用空间大而使得效率不高。有学者使用元素么间相冗比４较的方法来构造浓缩差别矩阵的算法，其算法时间复杂度达到０ＣＵ，因此，巧不适（１）ＩＩＩ合用来处理大数据，减少ｒ存储的宅间，。也巧研究者将差别元素压缩存储到ＦＰ树上但一却并没能够去掉那峰无用的元素，为此，我们设计种改进算法，引入二义树的思想，循环采用規差别元素建立二义树，长差别元素化次查找比较的方法，然／ｒ；在此基础之上，引入了扩展的二进制差别矩阵，

6、并肯接从矩阵中提取规则，使得新算法的时间复杂度降到了２２ｗａｘ〇Ｃｔ／），〇Ｃｔ／。，设计的浓缩差别矩阵的规则获取算法是高（｜实验证明｛｜｜｜｜（｜｜ｗＪＷ）｝■效ｎｊ行的。２由十大型决策表求解差别矩阵时费时且需要用到大量的存储空间－使得属性约简算（），法的效率不高．化能运用到差别矩阵的思想引入。为了不仪能降低差别矩阵的存储空间了区分对象对集的思想，Ｗ知识粒度为启发信息，引入分布计数排净法求容差类，并结合Ｉ冲突域的思想，使得算法时空复杂度分别降到了Ｃ１／Ｃ／／ｆｌａＧＣ）及１１化０（１Ｃ１１ｆ｝（２一／？０ｔ／０

7、＾＾／口口ｅＣ。。的，）最后实验证明该算法是种高效可行的属性约简算法（｜Ｉ）（１｜｝（一３为了降低属性约简算法的复杂度，在布尔冲突矩阵的基础上，定义了个肩发函数，（）该函数能求出决策表中条件属性导致的冲突个数，同时给出了计算该启发函数的快速算法一个有效的关于不完备决策表的改进的布尔冲突矩阵的高效。然后用该启发函数设计了０ＣＫ＝：２．Ｃ／。属性约简算法，该算法将时间复杂度降到了ＫＵ／ｍｃｃｊｃｅ最后Ｉ〇ＩＩＩ｜）（｜｜｛｜；〇，）｜｜，。实验结果说明了新算法的有效性。关键词：属性约简；规则获取！浓缩差别矩阵；二叉树

8、；布尔冲突矩阵打Ｒｅｓｅａｒｃ