基于粗糙集的缺失数据循环搜索重建算法

第２２卷第１２期　

２００７年１２月　乐ｌ１．Ｉ师范学院学报　

Ｊｏｕｒｎａｌ　ｏｆ　Ｌｅｓｈａｎ　Ｔｅａｃｈｅ￣Ｃｏｌｌｅｇｅ　Ｖｏ１．２２．Ｎｏ．１　２　

Ｄｅｃ．２００７　

基于粗糙集的数据挖掘的应用ｘｏｌ－究　

杨霞　

（乐山师范学院计算机科学与信息工程系，四川乐山６１４００４）　

摘要：粗糙集理论是一种处理不确定和模糊问题的数学工具，它的一系列优点使其特别适合于数据挖掘研究。本文　

阐述了粗糙集理论及其在数据挖掘中的应用。　

关键词：数据挖掘；粗糙集；属性约简　中图分类号：ＴＰ３１１．１３　文献标识码：Ａ　文章编号：１００９—８６６６（２００７）１２－００６７—０３　

０引言　

计算机技术和信息技术的发展把人们推人了信息社　

会，信息的增长呈超指数上升。信息量的急剧增长，使传统　

数据库的检索查询机制和统计分析方法已远远不能满足　

现实的需要，许多数据来不及分析就过时了，也有许多数　

据因其数据量极大而难以分析数据间的关系。在这样的背　

景下，新的数据处理技术——数据挖掘（Ｄａｔａ　Ｍｉｎｉｎｇ）便应　

运而生。ＤＭ就是从大量的、不完全的、有噪声的、模糊的、　随机的实际应用数据中，提取隐含在其中的、人们事先不　

知道的、但又是潜在有用的信息和知识的过程。　

粗糙集理论ＲＳ（Ｒｏｕｇｈ　ｓｅｔｓ）是由以波兰数学家Ｚ．　Ｐａｗｌａｋ为代表的研究者于１９８２年提出的一种分析数据的　

数学理论，该理论比较出色地处理了不精确、不一致、不完　整等各种不完备的信息，还可以对数据进行分析和推理，　

从中发现隐含的知识，揭示潜在的规律，其主要思想就是　

在保持分类能力不变的前提下，通过知识约简的决策或分　

类规则。［１１目前，粗糙集理论已成为数据挖掘研究中的有利　

工具，特别是将其与机器学习、模式识别、数据库等理论相　

结合，开发了多个原型系统，其中有代表性的有Ｒｏｓｅｔｔａ系　

统、ＬＥＲＳ系统、ＫＤＤ—Ｒ系统等。正是这些系统的成功开发　

与应用使得粗糙集理论与应用的研究在国际上日益受到　广泛的关注。∞１　

第２３巷第２期　

２００６年２月　计算机应用与软件　

Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｖｏ１．２３，Ｎｏ．２　

Ｆｅｂ．２００６　

一种基于粗糙集的集成算法及应用　

王小凤周明全郑建国　

（西北大学汁算：机科学系陕西西安７１００６９）　

摘要　粗糙集理论的主要思想是在保持信息系统分类能力不变的前提下，通过知识约简，导出问题的决策和分类规则：本文提　

出一种基于信息量的属性约简和规则提取的集成算法，并结合汽车里程试验数据进行验证，通过仿真实验，表明了该算法的有效性　

和可行性。　

关键词　粗糙集信息量　属性约简　值约筒　

ＡＮ　ＩＮＴＥＧＲＡＴＥＤ　ＡＬＧｏＲＩＴＨＭ　ＢＡＳＥＤ　ｏＮ　ＲｏＵＧＨ　ＳＥＴ　ＡＮＤ　ＩＴ’Ｓ　ＡＰＰＬＩＣＡＴＩｏＮ　

Ｗａｎｇ　Ｘｉａｏｆｅｎｇ　Ｚｈｏｕ　Ｍｉｎｇｑｕａｎ　Ｚｈｅｎｇ　Ｊｉａｎｇｕｏ　

（Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　Ｄｅｐａｒｔｍｅｎｔ．Ｎｏｒｔｈｗｅｓｔ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ＂ａｎ　Ｓｈａａｎｘｉ　７１００６９，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ　Ｔｈｅ　ｍａｉｎ　ｔａｒｇｅｔ　ｏｆ　Ｒｏｕｇｈ　Ｓｅｔ　ｔｈｅｏｒｙ　ｉｓ　ｒｅｄｕｃｉｎｇ　ｔｈｅ　ａｔｔｒｉｂｕｔｅ　ａｎｄ　ｇｅｔｔｉｎｇ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅ　ｒｕｌｅｓ　ｂａｓｅｄ　ｏｎ　ｋｅｅｐｉｎｇ　ｔｈｅ　ｃｌａｓｓｉｆｉａｂｌｅ　

ａｂｉｌｉｔｙ　ｏｆ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍ．Ａｃｃｏｒｄｉｎｇ　ｔＯ　ｔｉｌｅ　Ｒｏｕｇｈ　Ｓｅｔ　ｔｈｅｏｒｙ．ａｎ　ｉｎｔｅｇｒａｔｅｄ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｑｕａｎｔｉｔｙ　ａｎｄ　ｖａｌｕｅ　ｒｅｄｕｃｔｉｏｎ　ｉｓ　ｐｒｏｐｏｓｅｄ．ａｎｄ　ｔｈｅｎ　ｉｔ　ｉｓ　ｕｓｅｄ　ｔＯ　ａｎａｌｙｓｉｓ　ｃａｒ’ｓ　ｄａｔａ，ｏｂｔａｉｎｉｎｇ　ｔｂｅ　ｃｏｒｅ　ａｎｄ　ｅｆｆｅｃｔｉｖｅ　ｒｕｌｅｓ－Ｆｏｒ　ｔｈｅ　ｓａｍｅ　ｒｅａｓｏｎ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ａｌｓｏ　ｂｅ　

第９卷第ｌ２期　２０１０年１２月　软件导刊　ＳｏｆｔｗａｒｅＧｕｉｄｅ　Ｖ０１．９　ＮＯ．１２　Ｔｗｅ．２Ｏｌ０　

基于粗糙集和模糊聚类方法的属性约简算法　

耿德志　

（晋中学院，山西晋中０３０６００）　

摘要：在基于粗糙集的属性约简算法中引入模糊等价关系的一种新的度量方法，重新定义了高维数据中的属性重　要度．提出了一个结合粗糙集和模糊聚类方法的属性约简算法，并通过实验得到了用户满意的属性约简结果。　关键词：粗糙集；模糊聚类；属性约简算法　中图分类号：ＴＰ３１２　文献标识码：Ａ　文章编号：１６７２—７８００（２０１０）１２—００４９—０３　

０　引言　

本文在基于粗糙集的属性约简算法中引入模糊等价关系　的一种新的度量方法．重新定义了高维数据中的属性重要度，　提出了一个结合粗糙集和模糊聚类方法的属性约简算法，得到　了用户满意的属性约简结果，实验证明可以达到一个比较好的　效果。　

１粗糙集理论　

１．１信息系统　

信息系统Ｓ＝（叫，｛　。｝　是一个四元组，其中　是非空有　限集合，称为论域；Ａ是非空有限集合，称为属性集合；Ｖ　是属　

性口∈Ａ的值域　。为一单射，使论域ｕ中的任一元素取属　

性。在Ｖ　中的某一唯一值。Ａ由条件属性集合Ｃ和决策属性集合　

Ｄ组成，Ｃ和Ｄ满足ＣＬＪＤ＝Ａ，ＣＮＤ＝ｄ？，则称Ｓ为决策系统，用（　

ＣｕＤ）表示；当决策属性集合只有一个元素时，也常用（　ＣＵ　

｛ｄ））表示。若ＢＣ＿Ｃ，Ｙｘ，ＹＥ　Ｕ，　≠ｙ，称二元关系ＩＮＤ＝（Ｂ，｛ｄ｝）＝　｛（　，Ｙ）∈ＵｘＵ　Ｉ　ｄ（　）＝ｄ（ｙ）或者口∈Ｂ，口（　）＝Ⅱ（ｙ）｝为不可分辨　

关系。　

１．２粗糙集　对于信息系统Ｊｓ＝（　，｛　。｝　，ＢＣ＿Ａ，ＸＣ＿Ｕ，称Ｂｘ＝｛　∈Ｕ　ｌ　

［　］　（　ｃ＿ｘ｝，　＝｛　∈Ｕ　ｌ［　］，佃（　）ｎ　≠咖｝分别为　的日下近似　

４结束语　

本文结合粗糙集理论讨论了电子商务应用中的知识获取　过程。采用基于差别矩阵的属性约简方法直观，能求得系统的　核和所有约简．但生成一个差别矩阵的中间环节及计算差别函　数对应的最小简化的析取范式都会有一定的时间开销。此外，　差别矩阵中存储大量重复元素也较浪费空间。因此这类算法在　处理小型商务系统数据效率可行。若要运用于海量数据的处　理，其算法还有待进一步的研究。　

第２２卷第２期　２００６年４月　忻州师范学院学报　ＪＯＵＲＮＡＬＯＦＸＩＮＺＨＯＵＴＥＡＣＨＥＲＳＵＮＩＶＥＲＳＩＴＹ　Ｖ０Ｉ．２２　Ｎｏ．２　Ａｐｒ．２００６　

基于粗糙集的属性约简算法　

赵青杉，韩宝俊　

（忻州师范学院，山西忻州０３４０００）　

摘要：属性约简是粗糙集理论研究的关键问题之一，现已证明寻找一个决策表的最优约　

简是Ｎ　Ｐ—ｈａｒｄ问题。本文首先介绍可辨识矩阵属性约简的基本算法并对求核算法进行了改　

进。在此基础上给出决策表中属性重要性的两种度量，并以此为启发式信息，提出了一种属性　

约简的启发式算法。最后，实验结果表明，该算法在大多数情况下能有效地获得决策表的最优　

约简。　

关键词：粗糙集理论；可辨识矩阵；核；启发式算法　

中图分类号：ＴＰ３１１　文献标识码：Ａ　文章编号：１６７１—１４９１（２００６）０２—００４３—０４　

一、引言　

粗糙集理论是波兰数学家Ｚ．Ｐａｗｌａｋ在２０世纪８ｏ年代　

初首先提出的一种可以分析模糊和不确定问题的数学理　

论…。通过属性约简，可以成功地剔除知识库中的冗余知识　

（属性），发现知识库中隐含的关联和规则，帮助人们做出正　

确简捷的决策。约简通常不是唯一的，约简中属性个数的多　

少直接影响着属性值的约简过程和决策规则的繁简。遗憾　

的是Ｗｏｎｇ等已经从计算复杂性的角度证明了寻找决策表　

的最小约简是Ｎ　Ｐ—ｈａｒｄ问题。解决这类问题的方法一般　

是启发式搜索，进而获得最优解或近似最优解。　本文研究了可辨识矩阵的约简，从属性依赖度角度给出　

了两种属性重要性度量，在此基础上提出了一种属性约简的　

启发式算法。该算法利用两种属性重要性度量的乘积作为　

启发规则，来寻找最小约简。在大多数情况下，此算法可以　

找到最小约简。在没有找到最小约简的情况下，此算法可以　

找到次优约简。　

二、基本粗糙集理论　在粗糙集理论中，决策表Ｔ＝（ｕ，ｃＵＤ）被定义为其　

中ｕ为对象的非空有限集合，称为论域：其中Ｃ称为条件