二进制在集合运算与数据挖掘中与应用研究

1、硕士学位论 文李天志硕士二制在集合运算与数据挖掘中的应用研究2006二进制在集合运算与数据挖掘中的应用研究李天志二0 0六年 六 月分类号 TP18 密级 UDC 硕士学位论文二进制在集合运算与数据挖掘中的应用研究 李 天 志 学科专业 计算机应用技术 指导教师 梁家荣 教授 论文答辩日期 2006年6月 日 学位授予日期 答辩委员会主席 论文评阅人 .二进制在集合运算与数据挖掘中的应用研究摘 要集合论的提出及发展大大促进了计算机应用技术的创新，尤其，近些年来迅速发展起来的Rough集理论，对于处理不确定、不精确、模糊信息提供了良好的解决方法，加快了人工智能技术的发展。但是，集合运算计算机实现

2、技术的落后严重阻碍了集合的进一步应用。二进制与集合存在着密切的内在联系，二进制位运算是计算机中处理速度最快的运算，而且二进制数据运用方便，变化灵活。本文将二进制引入到集合运算中，并不断加深研究。首先，探讨了集合运算的基本概念，通过分析二进制与集合之间的内在联系，将二进制位运算引入到集合基本运算中，并给出了各种基本运算的具体实现算法。接着，通过对粗糙集理论的研究，阐明了粗糙集理论是一种尤为适用于不确定、不完备系统的数据挖掘的数学工具，其中，重点探讨了属性约简以及数据挖掘的相关内容。在此基础上，提出了基于二进制的粗糙集运算理论，将二进制位运算运用到粗糙集的基本运算、属性求核中，并且提出了相关的一些

3、定理。 然后，通过分析知识表以及决策表求核过程，找到新的求核方法，提出新的定理及规则，并将求核运算转化为二进制数据的比较运算，进一步提高了求核效率。最后，通过分析二进制与关联规则项集的关系，提出了基于二进制的关联规则挖掘算法，并分析比较了相对于传统算法的优势。关键词：集合论；粗糙集；二进制；属性约简；核；知识表；决策表；关联规则；数据挖掘Research of Rough Set Operations and Data Mining Based on BinaryABSTRACT The innovation of the computer operation technique is acc

4、elerated with the development of set theory. Especially,rough set theory- a mathematical tool for dealing with inexact, uncertain or vague knowledge- has greatly promoted the developing of artificial intelligence. However, the algorithms for set application was inefficient which has blocked the furt

5、her application of set theory. Theres an internal relation between binary system and set. Bit operation is the fastest way as to computers process speed. Moreover, its data is quite convenient and changeable for applying.This paper applies Binary system into set operation and gives a further researc

6、h.To begin with,the basic-concept of set operation is discussed. Binary system is introduced into set operation through analyzing the internal relation between binary and set. Also the author gives us the detailed process of various basic operation. Next, with the study of rough set theory, the auth

7、or holds that rough set theory is a mathematical tool especially for dealing with the data mining of inexact or incomplete system, focusing on attribute reduction and data mining. Based on the above research,rough set operation theory based on binary is presented. Bit operation is applied to rough s

8、et basic operation and attribute core algorithm . Then new core algorithms, theorems and rules are presented by analyzing the process of core operation of decision table and knowledge table . The algorithms transform the way to get the core into the comparison of numbers. It is more efficient and ef

9、fective than the traditional algorithms. Finally, through analyzing the relation between binary system and association rules, binary-based association rules mining algorithm is presented which is more efficient and effective than the traditional algorithms .KEY WORDS: set theory;rough set;binary；att

10、ribute reduction；core；decision table；knowledge table;association rules;data mining .目 录 TOC o 1-3 h z HYPERLINK l _Toc133143640 第一章 绪 论 PAGEREF _Toc133143640 h 1 HYPERLINK l _Toc133143641 1.1国内外研究现状 PAGEREF _Toc133143641 h 1 HYPERLINK l _Toc133143642 1.2论文的选题背景及意义 PAGEREF _Toc133143642 h 1 HYPERLINK

11、 l _Toc133143643 1.3 论文的主要工作 PAGEREF _Toc133143643 h 2 HYPERLINK l _Toc133143644 1.4 论文的组织结构 PAGEREF _Toc133143644 h 3 HYPERLINK l _Toc133143645 第二章 基于二进制的集合运算研究 PAGEREF _Toc133143645 h 5 HYPERLINK l _Toc133143646 2.1集合的概念 PAGEREF _Toc133143646 h 5 HYPERLINK l _Toc133143647 集合基本定义 PAGEREF _Toc133143

12、647 h 5 HYPERLINK l _Toc133143648 集合的基本运算 PAGEREF _Toc133143648 h 6 HYPERLINK l _Toc133143649 2.2集合与二进制的关系 PAGEREF _Toc133143649 h 6 HYPERLINK l _Toc133143650 2.3 基于二进制的集合运算 PAGEREF _Toc133143650 h 7 HYPERLINK l _Toc133143651 用二进制求集合的幂集 PAGEREF _Toc133143651 h 7 HYPERLINK l _Toc133143652 用二进制求集合的交集

13、PAGEREF _Toc133143652 h 9 HYPERLINK l _Toc133143653 用二进制求集合的并集 PAGEREF _Toc133143653 h 9 HYPERLINK l _Toc133143654 用二进制求集合的补集 PAGEREF _Toc133143654 h 10 HYPERLINK l _Toc133143655 用二进制求集合的相对补 PAGEREF _Toc133143655 h 10 HYPERLINK l _Toc133143656 判断一个集合是否是另一个集合的子集 PAGEREF _Toc133143656 h 10 HYPERLINK l

14、 _Toc133143657 2.4本章小结 PAGEREF _Toc133143657 h 11 HYPERLINK l _Toc133143658 第三章 粗糙集理论概述 PAGEREF _Toc133143658 h 12 HYPERLINK l _Toc133143659 3.1 粗糙集理论的基本概念 PAGEREF _Toc133143659 h 12 HYPERLINK l _Toc133143660 3.2 属性约简 PAGEREF _Toc133143660 h 15 HYPERLINK l _Toc133143661 属性约简 PAGEREF _Toc133143661 h

15、15 HYPERLINK l _Toc133143662 值约简与规则提取 PAGEREF _Toc133143662 h 17 HYPERLINK l _Toc133143663 3.3 粗糙集的理论研究 PAGEREF _Toc133143663 h 18 HYPERLINK l _Toc133143664 3.4数据挖掘的粗糙集方法 PAGEREF _Toc133143664 h 18 HYPERLINK l _Toc133143665 粗糙集应用于数据挖掘的优势 PAGEREF _Toc133143665 h 18 HYPERLINK l _Toc133143666 基于粗糙集理论的数

16、据挖掘过程 PAGEREF _Toc133143666 h 19 HYPERLINK l _Toc133143667 3.5 本章小结 PAGEREF _Toc133143667 h 20 HYPERLINK l _Toc133143668 第四章 基于二进制的粗糙集基本运算研究 PAGEREF _Toc133143668 h 21 HYPERLINK l _Toc133143669 4.1 二进制与粗糙集的内在联系 PAGEREF _Toc133143669 h 21 HYPERLINK l _Toc133143670 4.2 基于二进制的粗糙集基本运算 PAGEREF _Toc133143

17、670 h 21 HYPERLINK l _Toc133143671 粗糙集的上近似集 PAGEREF _Toc133143671 h 22 HYPERLINK l _Toc133143672 粗糙集的下近似集 PAGEREF _Toc133143672 h 22 HYPERLINK l _Toc133143673 等价类的交 PAGEREF _Toc133143673 h 23 HYPERLINK l _Toc133143674 集合的基数 PAGEREF _Toc133143674 h 24 HYPERLINK l _Toc133143675 粗糙集运算举例 PAGEREF _Toc133

18、143675 h 24 HYPERLINK l _Toc133143676 4.3本章小结 PAGEREF _Toc133143676 h 24 HYPERLINK l _Toc133143677 第五章 基于位运算的属性核约简 PAGEREF _Toc133143677 h 26 HYPERLINK l _Toc133143678 5.1算法基本思想 PAGEREF _Toc133143678 h 26 HYPERLINK l _Toc133143679 5.2算法的实现 PAGEREF _Toc133143679 h 27 HYPERLINK l _Toc133143680 算法IsInd

19、sp PAGEREF _Toc133143680 h 27 HYPERLINK l _Toc133143681 求解核算法core PAGEREF _Toc133143681 h 30 HYPERLINK l _Toc133143682 5.3算法分析 PAGEREF _Toc133143682 h 30 HYPERLINK l _Toc133143683 5.4 事例分析 PAGEREF _Toc133143683 h 30 HYPERLINK l _Toc133143684 5.5本章小结 PAGEREF _Toc133143684 h 31 HYPERLINK l _Toc1331436

20、85 第六章 基于二进制的知识表求核算法 PAGEREF _Toc133143685 h 32 HYPERLINK l _Toc133143686 6.1属性值二进制化 PAGEREF _Toc133143686 h 32 HYPERLINK l _Toc133143687 6.2求核算法 PAGEREF _Toc133143687 h 33 HYPERLINK l _Toc133143688 6.3求核算法复杂度分析 PAGEREF _Toc133143688 h 35 HYPERLINK l _Toc133143689 6.4结束语 PAGEREF _Toc133143689 h 35 H

21、YPERLINK l _Toc133143690 第七章 基于二进制的决策表求核算法 PAGEREF _Toc133143690 h 36 HYPERLINK l _Toc133143691 7.1属性值二进制化 PAGEREF _Toc133143691 h 36 HYPERLINK l _Toc133143692 7.2求核算法 PAGEREF _Toc133143692 h 37 HYPERLINK l _Toc133143693 7.3算法复杂度分析 PAGEREF _Toc133143693 h 40 HYPERLINK l _Toc133143694 7.4本章小结 PAGEREF

22、 _Toc133143694 h 40 HYPERLINK l _Toc133143695 第八章 基于二进制的关联规则挖掘算法 PAGEREF _Toc133143695 h 42 HYPERLINK l _Toc133143696 8.1关联规则挖掘基本知识 PAGEREF _Toc133143696 h 42 HYPERLINK l _Toc133143697 8.2二进制的引入 PAGEREF _Toc133143697 h 43 HYPERLINK l _Toc133143698 8.3基于二进制的关联规则挖掘算法 PAGEREF _Toc133143698 h 44 HYPERLI

23、NK l _Toc133143699 算法结构体设计 PAGEREF _Toc133143699 h 44 HYPERLINK l _Toc133143700 事务项集真子集求解 PAGEREF _Toc133143700 h 44 HYPERLINK l _Toc133143701 算法实现 PAGEREF _Toc133143701 h 45 HYPERLINK l _Toc133143702 8.4本章小结 PAGEREF _Toc133143702 h 47 HYPERLINK l _Toc133143703 第九章 总结 PAGEREF _Toc133143703 h 48 HYPE

24、RLINK l _Toc133143704 9.1 工作小结 PAGEREF _Toc133143704 h 48 HYPERLINK l _Toc133143705 9.2 存在的问题 PAGEREF _Toc133143705 h 48 HYPERLINK l _Toc133143706 9.3 进一步的工作 PAGEREF _Toc133143706 h 49 HYPERLINK l _Toc133143707 参考文献 PAGEREF _Toc133143707 h 50 HYPERLINK l _Toc133143708 致 谢 PAGEREF _Toc133143708 h 55

25、HYPERLINK l _Toc133143709 攻读硕士学位期间完成的学术论文 PAGEREF _Toc133143709 h 56 HYPERLINK l _Toc133143710 攻读硕士学位期间参加的科研项目 PAGEREF _Toc133143710 h 57.第一章 绪 论1.1国内外研究现状集合论在计算机科学、人工智能领域、逻辑学及语言学等方面的理论研究成果已经很多，但在理论研究中人们主要是利用传统数学方式对集合进行描述，对于集合的计算机实现算法研究很少，主要局限文5-9所提到的一些方法，这些方法由于自身操作的复杂性导致集合运算的效率很低。二进制位运算是计算机中最基本的运算，

26、具有易于实现，运算速度快等特点，被广泛应用与计算机的各个领域中，如密码学10，遗传算法11，可变矩阵约简12，编码13-14等，其主要思想是利用二进制的位操作来实现各种技术。随着人们对二进制认识的不断加深，其应用领域也在不断扩大，运用技巧方法也不断被改进更新。在求集合幂集、组合方面有学者曾尝试使用二进制来实现15，但是由于所用技巧方法不当，时间复杂度仍然很高。随着数据挖掘技术和粗集理论的不断发展，人们将二者有效结合了起来，即出现了对基于粗集理论的数据挖掘技术的研究。基于粗集理论的数据挖掘思想是：将数据库中的属性分为条件属性和决策属性，对数据库中的元组根据各个属性不同的属性值分成相应的子集，然后

27、根据条件属性划分的子集和决策属性划分的子集之间的上下近似关系生成决策规则。将以粗集为代表的集合论方法应用到数据挖掘(DM)领域已经取得了一定的成果16-29，一些学者曾尝试将二进制融于数据挖掘中30-31，并且取得了良好的效果。因此，将二进制应用于集合以及粗糙集运算中，完成数据挖掘，无论在理论上还是应用上都有待深入研究和发展，这为本课题的研究提供了契机。1.2论文的选题背景及意义集合论是在19世纪70年代由德国数学家康托（G. Cantor）在无穷序列和分析的有关课题的理论研究中创立的1，康托对具有任意特性的无穷集合进行了深入的探讨，提出了关于基数、序数、超穷数和良序集等理论，奠定了集合论的深

28、厚基础，以后逐步发展形成一门独立学科，一般称此时期的集合理论为经典集合论。经典集合论是以二值逻辑为基础的，从集合和特征函数定义看, 某个事物只能属于或不属于某集合, 不可能有第三种可能，这就是经典集合的二值性。但是随着集合论的发展，以及它与数学哲学密切联系所作的讨论，出现了许多似是而非、自相矛盾的悖论，如著名的罗素（BAWRussell）悖论，有力的冲击了或者说动摇了集合论的发展，由此，激发许多数学家、哲学家为克服这些矛盾而建立了各种公理化集合论体系。出于解决处理一些问题的需要，20世纪60年代Zadeh提出了Fuzzy集理论2， 20世纪80年代波兰教授Z.Pawlak等提出了Rough集理

29、论3，这两种理论不同于经典集合理论，它们是一种新的模糊集合理论，自问世以来，一直受到学术界的重视和青睐，并取得了喜人成果。经典集合论曾为半个多世纪的计算机技术大发展立下不朽的功勋，并且当前仍然广泛应用于各种计算机领域。但是，人脑是这个世界上最复杂、智能最高的系统。它的精妙之处就在于能够处理信息的不确定性、不精确性、不完全性、模糊性、随机性和非单调性，从而得到正确或满意的结论，为人们作出决策提供强有力的支持。在现实世界中，人们对某个事物或事件进行判断、推理、预测、决策时，所面对的信息常常是不精确、不完全或模糊的，这就要求我们在计算机中模拟人的智能行为时，计算机能够处理这类信息。Rough集理论作

30、为经典集合论的扩展，是一种新的处理模糊和不确定知识的软计算工具，它把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于上近似集和下近似集都可以通过等价关系给出确定的数学公式描述，所以含糊元素数目可以被计算出来，即在真假二值之间的含糊程度可以计算。粗糙集自问世以来，无论是在理论还是应用上都是一种新的、最重要的并且发展非常迅速的一门研究领域，它在理论上的深远意义和应用中的巨大潜力正吸引着世界各国许多专家学者的注意，尤其在人工智能的各个研究领域中发展尤其显著4。 给定一个集合，对其进行计算机运算并不是一件容易事，传统的操作主要是将集合元素存入数组或者字符串中

31、，通过字符串的查找、比较、插入等操作完成集合的各种运算，传统的这些操作算法空间、时间复杂度都很高，有的还牵扯到数据的移动，因此，运算速度慢、效率低，大大制约了集合论在现实中的应用。如何快速有效的利用计算机对集合以及粗糙集运算进行处理，一直是学术界关心的课题。本课题将通过讨论二进制与集合之间的内在联系，提出基于二进制的集合运算理论，充分发挥二进制数据在计算机中运算速度快、节约空间的优势，并对二进制在数据挖掘中的应用进行探索，以提高数据挖掘效率。因此，基于二进制的集合运算及在数据挖掘中的应用研究是一项很有学术价值和实际意义的工作。 1.3 论文的主要工作本文从二进制在经典集合计算中的应用研究入手，

32、将二进制与集合联系在一起，进而将二进制应用到粗糙集运算中，并对其在数据挖掘中的应用进行了探讨。论文主要完成了以下几个方面的工作：1、研究了经典集合运算与二进制位运算的关系，指出了传统经典集合运算计算机实现方法的缺点，实现了二进制与集合基本运算的结合，并给出了相关算法。2、研究了粗糙集的基本理论和方法，讨论了粗糙集基本运算与集合的联系，重点研究了二进制位运算在粗糙集基本运算中以及属性核约简中的应用，并结合实例分析了基于二进制位运算的粗糙集运算的优点，得出了有意义的结论。3、通过分析属性约简过程，得出相关定理，提出了基于二进制的知识表核约简以及基于二进制的决策表核约简思想，将求核过程转化为数值的比

33、较，并通过理论分析和实例说明了算法的有效性。4、通过分析二进制与关联规则项集的关系，提出了基于二进制的关联规则挖掘算法，并分析比较了相对于传统算法的优势。1.4 论文的组织结构本文针对传统集合运算计算机算法运算效率低的问题，将二进制引入到集合以及数据挖掘中，围绕二进制在集合以及粗糙集运算中的应用，逐步展开全面而深入的研究。本文各章节的安排如下：第一章 绪论 介绍了论文的选题背景，阐述了论文选题的意义，并对本课题的国内外研究现状进行了介绍。第二章 基于二进制的集合运算研究首先介绍了集合的基本概念，然后分析比较二进制与集合之间的内在联系，最后，通过二进制位运算实现了集合的各种基本运算，并且对相关算

34、法给出了C语言源代码。第三章 粗糙集理论概述本章首先介绍粗糙集理论的基本概念，然后分析了该理论的研究状况，最后对粗糙集理论在数据挖掘中的应用进行了研究。第四章 基于二进制的粗糙集基本运算研究本章在第二章基于二进制的集合运算研究的基础上，通过讨论二进制与粗糙集之间的内在联系，提出了基于二进制的粗糙集运算理论。借助位操作对粗糙集进行运算，充分发挥其运算速度快、节约空间的优势，并且给出了相关算法的C语言源程序。第五章 基于位运算的属性核约简本章是二进制位运算在粗糙集中的进一步应用，通过将二进制位运算运用到知识表属性的核约简中，提高求核效率。第六章 基于二进制的知识表求核算法本章首先分析知识表求核过程

35、，得出了一个重要分类定理，然后，将二进制引入求核算法中，利用此定理将属性核的求解变为数值的比较问题，充分利用了二进制数据处理灵活，运算速度快的优势，可以将时间复杂度降到O(|U|*|R|)。第七章 基于二进制的决策表求核算法本章首先分析了决策表求核过程，提出了相关定理和规则，在此基础上，将二进制运用到求核算法中，将决策表属性核的求解变为数值的查找、比较问题，从而将算法时间复杂度大大降低。第八章 基于二进制的关联规则挖掘算法本章通过分析二进制与关联规则项集的关系，将二进制引入到关联规则挖掘过程中，减少了事务子集的求解次数，从而减少了时间复杂度，提高了挖掘效率。第九章 总结对论文工作进行了总结，对

36、后续研究进行了展望。第二章 基于二进制的集合运算研究集合论是在十九世纪末由德国数学家康托创立的，以后逐步发展形成一门独立学科，由于广泛的使用了数理逻辑的工具，集合论逐渐成为数理逻辑的一个分支，并从60年代以来获得迅速的发展，现已渗透到数学的许多分支中，并在计算机的人工智能等领域得到了广泛应用，如粗糙集，模糊集等数据挖掘方法中都大量使用了集合的各种运算。但是，目前关于集合运算计算机实现算法的相关研究文献不多，而传统的对集合操作主要是利用字符串匹配、查询等来实现5，效率低，而且对空间要求很高，大大制约了集合理论向实际应用的转化，如何快速有效的利用计算机对集合运算进行处理一直是学术界关心的课题。本章

37、首先介绍了集合的基本概念，然后分析比较二进制与集合之间的内在联系，最后，通过二进制位运算实现了集合的各种基本运算，并且对相关算法给出了C语言源代码。2.1集合的概念 集合基本定义定义2.1集合是一些确定的对象的全体，对象称为元素，若a是集合A的元素，则记为a A。定义2.2不含任何元素的集合叫做空集，记做 或。定义2.3设A,B为集合，若任意一定有，则称A是B的子集，也称A被B包含，或B包含A，记为。定义2.4 设A,B为集合，若且，则称A与B相等，记为A=B。定义2.5 若，但是，则称A是B的真子集，记为。定义2.6 幂集：由A的所有子集组成的集合称为A的幂集，记为P（A）或。定义2.7 基

38、数：集合A中元素的个数称为A的基数，记为 |A|。定义2.8 交集：集合A与B的交集AB=x|xA并且xB。定义2.9 并集：集合A与B的并集AB= x|xA或xB。定义2.10 A, B是分离的，若AB=定义2.11 相对补：集合A对B的相对补A-B= x|xA并且xB 。定义2.12 补集：集合A的补集为全集E与A的差，记为A。定义2.13 对称差：集合A与B的对称差AB=（A-B）（B-A）。2.2集合与二进制的关系二进制自问世以来，在计算机的研究和应用领域起着重要的作用，它的值域只有“0”，“1”两个值，但是通过对这两个值的有效组合和简单运算，却能表达出客观真实世界的千变万化，下面通过

39、分析二进制和集合之间强大的内在联系，说明二进制在集合运算中的巨大作用。若集合A具有n个元素，则A的所有子集(幂集)的个数| P(A)|=，例如，Aa,b,c,则A的幂集为,a,b,a,b,c,a,c,b,c,a,b,c，A的幂集的基数为8 。 长度为n的二进制位所能表达的数据个数为，例如长度为3的二进制位，所能生成的数据为 000,001,010,011,100,101,110,111，共8个数据。 通过比较发现，长度为n的二进制位所能表达的数据个数和具有相同元素个数的集合的所有子集(幂集)的数目相同，由此可以猜想二进制和集合之间应该具有某些联系,现在做以下规定：规定2.1 对于集合I=0,1

40、,2,n,，规定个n位的二进制数P=。与之对应，其中二进制数的第0位对应集合的第0个元素0 ，第1位对应第1个元素1 ，第k位对应第k个元素。例2.1规定一个3位的二进制数，用此二进制数的第0位代表上面所提到的集合A的a元素，第1位代表集合A的b元素，第2位代表集合A的c元素，然后比较集合A的幂集和二进制数据的关系，如下表所示：表2.1序号子集二进制数00001a0012b0103a,b0114c1005a,c1016b,c1107a,b,c111通过比较发现，如果我们按照上表中的对应关系对子集进行编号，则集合第i个子集和二进制所产生的第i个数据之间存在着非常微妙的对照关系：如果在子集中某个元

41、素存在，则此子集对应的二进制数中该元素所对应的二进制位为1，否则为0。例如,子集a,b,因为a对应二进制第0位，b对应二进制第1位，c对应二进制的第三位，而c元素没有在此子集中出现，所以，其对应的二进制数为011。定义2.14子集的下标：集合A的子集所对应的二进制数的十进制数值称为此子集的下标。有了集合与二进制之间的这种内在联系，以后在对集合操作时，我们没有必要对子集中的实际元素进行处理，只要知道子集的下标，就可以很容易的利用位运算来实现对集合进行各种操作的目的。2.3 基于二进制的集合运算已知集合A，求A的幂集。由于集合子集中的元素与子集下标中二进制位的“1”相对应，因此求子集中元素的运算可

42、以转化为寻找子集下标二进制位中“1”所在位置的运算，此运算可以利用移位操作来实现。例如，求101所对应的A的子集，我们可以通过3次移位，每次先将当前的数值与数值1相与，如果结果等于1，则本次第0位上的值为1，否则为0，由移位的次数可以知道当前第0位的1在原数据中的位置，从而找到对应的实际元素。运算如下： = 1 * GB3 第0次与：101&0011 ，a对应二进制位的第0位，而且本次相与的结果为1，所以 a属于此子集；101右移一位，现在的数值为010 = 2 * GB3 第1次与：010&001=0，b对应二进制位的第1位，而且本次相与的结果为0，所以 b不属于此子集。010右移一位，现在

43、的数值为001 = 3 * GB3 第1次与：001&001=1，c对应二进制位的第2位，而且本次相与的结果为1，所以 c属于此子集。001右移一位，现在的数值为000。计算完毕。求出101对应的A的子集为a,c。求子集元素的c语言算法程序如下：/* findelement找出集合A中子集下标b所对应的子集中的所有元素*/void findelement(char A,unsigned b ) int f,j0; /*f标志当前输出是否为子集的第一个元素，j记录移位次数*/ f=0; printf(n); while(b0) if(b&1)0 ) if(f=0) f=1; printf(%c,

44、Aj); else printf(,%c ,Aj); b=b1; j=j+1; printf(); 若求A的所有子集,只要从子集下标0依次求各对应子集的元素即可，本算法可用一个循环完成，代码如下：void findchildsets(char A,unsigned n) /n=为A的子集个数， unsigned i; for (i=0;in;i+) findelement(A,i); 设集合B,C均为集合A的子集，求B C。由交集的定义知,集合的交集概念和二进制中位的 与运算是相似的，所以求交集的运算转变为求两个二进制数的位与运算，通过两个集合下标的位与运算我们可以得到两个集合交集下标的值，从

45、而很快得到两个集合中的公共元素。例如，B=a,c，对应的二进制数为101，C=a,b,对应的二进制数为011，因为101&011=001，所以B C=a。本运算对应算法的C语言代码如下：unsigned intersection(unsigned set1,unsigned set2) /返回值为交集下标return (set1&set2);对返回值调用findelement子程序，求出交集中的所有元素。设集合B,C均为集合A的子集，求B C。由并集的定义知,集合的并集概念和二进制中位的或运算是相似的, 所以可以将求并集的运算转变为求两个集合下标的位或运算，从而得到两个集合并集的下标值，根据下

46、标值调用findelement子程序得到并集的所有元素。例如B=a,c，对应的二进制数为101，C=a,b,对应的二进制数为011，因为101|011=111，所以BC=a,b,c。对应算法的C语言代码如下：unsigned unionset(unsigned set1,unsigned set2) /返回值为并集下标 return(set1|set2); 对返回的值调用findelement子程序，求出并集中的所有元素。设集合B为全集A的子集，求B。由补集的定义知，集合的补集与二进制数据的按位求反是一致的，因此可以将此运算转换为求集合B下标值的按位求反操作，例如B=a,c，对应的二进制数为1

47、01，则101=111101=010，所以B=b。本运算对应算法的C语言代码如下：unsigned complement(unsigned set,unsigned n) / n=-1，返回值为补集下标return(setn); 设集合B,C均为集合A的子集，求B-C。由相对补定义知，此运算可以转换为B(C)，所以相对补运算相当于交集和补集的复合运算。因此求B-C，可以先求C的补集对应的二进制数,然后，将所求结果与B下标进行与运算，从而得出B-C对应的下标值。例如B=a,c，对应的二进制数为101，C=a,b,对应的二进制数为011，因为011=111011=100，101&100=100,故

48、B-C=c。 本运算对应算法的c语言代码如下：unsigned difference(unsigned set1,unsigned set2,unsigned n) / n=-1,返回值为相对补集下标 return(set1&complement(set2,n);设集合B,C均为集合A的子集，判断B是否是C的子集。由子集定义知，若任意xB一定有xC，即集合B中的所有元素都存在于集合C中，故，所以判断B是否是C的子集可以转换为判断B的下标和C的下标相或后是否等于C的下标的问题，如等于C的下标则。本运算对应算法的c语言代码如下：int issubset(unsigned set1,unsigned

49、 set2) /判断是否return(set1|set2)=set2);2.4本章小结本章通过比较二进制与集合间的内在联系，将二进制运用在集合的各种基本运算中，用二进制进行集合运算主要进行的是位运算,所以速度快,空间要求低,在对大量数据集合的运算中优势尤为明显。本章只是简单列举了常用的集合基本运算算法的实现，集合的其它各种运算可以通过这些基本运算的复合运算得到。集合理论在现代数学领域和计算机领域都起到了举足轻重的作用，尤其人工智能的发展更加快了集合理论与实际应用的联系，本章所提出的集合操作算法将有利于集合理论在计算机领域的进一步应用，并促进集合其他分支与计算机的联系，下一章将将二进制引入粗糙集

50、运算中，着重讨论二进制在粗糙集基本运算中的运用。第三章 粗糙集理论概述Rough Set理论是由波兰华沙理工大学Pawlak教授于20世纪80年代初提出的一种研究不完整、不确定知识和数据的表示、学习、归纳的理论方法，是一种有别于模糊集的新型的数据分析技术。该理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。它将分类与知识联系在一起，把知识理解为对数据的划分，每一被划分的集合称为概念。其主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来(近似)刻画。它以等价关系、上近似、下近似等作为基本概念。Rough理论为发现不精确和

51、不确定知识中的重要数据结构以及复杂对象的分类提供了强有力的理论基础，已广泛应用于数据挖掘32,33、人工智能34和分类35等领域。本章首先介绍粗糙集理论的基本概念，然后分析了该理论的研究状况，最后对粗糙集理论在数据挖掘中的应用进行了研究。3.1 粗糙集理论的基本概念36-39粗糙集把客观世界或对象世界抽象为一个信息系统（Information System），也称属性值系统。信息系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来表达。定义3.1 一个信息系统是一个四元组，其中，是对象的非空有限集合，称为论域（n表示对象个数）；是属性

52、的非空有限集合，C和D分别称为条件属性集和决策属性集；是属性值的集合，是属性a的值域；是一个信息函数，它为每个对象的每个属性赋予一个信息值，即。S也可以简记为：。如果一个信息系统的决策属性为空集，我们称此信息表为知识表，否则称此信息表为决策表。信息表中的一个属性集对应一个等价关系，一个信息表可以看成是定义的一族等价关系，即知识库。定义3.2 在一个信息系统中，对任一属性集合，不可分辨关系（indiscernibility relation）以表示，其定义如下：。若，则称x和y是B不可区分的，或相对于B是不可分辨的。容易证明，是U上的等价关系。二元组构成了一个近似空间。等价关系把U划分为K个不相

53、交的等价类，这些等价类称为B基本集（B-elementary concept）或B原子集。表示关系在U上的等价类族，简记为。符号表示包含的B等价类。为方便起见，空集一般也认为是基本集。若将U中的集合称为概念或知识，则A称为知识库，原子集表示基本概念或知识模块。任意有限的基本集的并和空集均称为可定义集，否则称为不可定义集。可定义集也称为精确集，可以在知识库中被精确地定义或描述，可表示已有的知识。不可定义集也称为非精确集或粗糙集。对于粗糙集可以近似地定义，使用两个精确集，即粗糙集的上近似（upper approximation）和下近似(lower approximation)来描述：定义3.3

54、令为一个信息系统，对任何一个对象子集和属性子集, X关于B的下近似和上近似分别定义为：，。在此基础上，分别定义X关于B的正域、负域和边界域如下：正域：；负域：；边界域：。或是由那些根据B判断肯定属于X的U中元素组成的集合；是那些根据B判断可能属于X的U中元素组成的集合；是那些根据B既不能判断肯定属于X又不能判断肯定属于（U-X）的U中元素组成的集合；是那些根据B判断肯定不属于X的U中元素组成的集合。如果，则X是B可定义集，否则X是B粗糙集。图3.1是对上述几个基本概念的一个直观表示：图3.1 用X的上、下近似集对实例集X的近似逼近（矩形区域表示等价类）Fig.3-1 A rough set a

55、pproximation of the set of samples of the class X using lower and upper approximation sets of X. The rectangular regions represent equivalence classes.定义3.4 由等价关系定义的集合X的近似精度（accuracy of approximation）为：，其中表示集合X的基数。该比值反映我们对于了解集合X的知识的安全程度。显然，对于每个B和有。定义3.5 粗糙隶属函数（rough membership function）可以定义为.该函数表示了x

56、属于X的确定程度。显然，。定义3.6 属性集合D对C的属性依赖程度（degree of dependency）记为k.其中，为正区域，它包含了U中所有利用条件属性C可以分类到决策属性D的对象。如果D是全部决策属性，C是条件属性，则表示用C对U划分后，任意能被正确划分到决策类的概率，同时刻划了条件属性C描述决策属性D的能力。定义3.7 在属性依赖程度的基础上，属性a相对于B对于D的依赖程度的属性重要度（significance of an attribute a）为：.可见，属性独立性改变越大，属性a对决策划分的影响越大，相对于决策属性来说，也就越重要。3.2 属性约简属性约简是粗糙集理论的核心

57、内容之一。知识库中的属性并不是同等重要的，甚至某些知识是冗余的。冗余知识的存在，一方面是对资源的浪费，另一方面则干扰人们做出正确而简洁的决策。所谓知识约简，就是在保持知识库分类或决策能力不变的条件下，删除其中不相关或不重要的知识。我们可以使用约简后的属性集合代替原来的整个属性集合而不降低分类效果。粗糙集中的知识约简包括两方面的内容，即属性约简和值约简。3.2.1 属性约简定义3.8 信息系统，其中，令BC为条件属性的非空子集。如果存在一子集有，则称B为属性依赖集，否则，称B为独立集。如果BC为独立集，且IND(C)=IND(B)，则B称为C的约简。C的所有约简族记为RED(C)。定义3.9 对

58、于任意属性，如果IND(C)IND(C-a)，则称a为C中必要的；否则，a为C中不必要的。C中所有必要关系的集合称为C的核，记为CORE(C)，且有CORE(C)=RED(C)。一般，属性的约简不唯一，而核唯一。定义3.10若POSC（D）= POS(Cr)（IND(D)）,则称r为C中D不必要的，否则称r为C中D必要的。对于BC,如果存在一子集，有，则B称为相对于D的依赖集，否则，称为相对于D的独立集。定义3.11 若BC是相对于D的独立集，且，则称B为C相对于D的约简。C的所有D约简族记为REDD(C)。定义3.12 C中所有D必要关系的集合称为C的D核，记为CORED(C),且有CORE

59、D(C)=REDD(C)。核即在属性约简过程中不能消去的必要属性的集合。核可以作为所有约简的计算基础，因为核包含在所有的约简之中，并且计算可以直接进行。从决策表的角度看，属性约简就是去除那些对决策没有贡献的属性。因此属性约简又可定义为条件属性C的子集B，满足。属性约简是粗糙集理论研究的一个核心内容。人们希望找到最佳属性约简，最佳约简是可以区分所有对象的最小属性子集。如果去掉最佳约简中的任何一个属性，都将使得该属性集对应的规则发生变化，即导致规则与例子的不一致。然而和Ziarko W己经证明这是一个NP-hard问题39。导致NP-hard问题的主要原因是属性的组合爆炸问题。因而目前还没有公认的

60、高效的最佳属性约简算法。但是在实际应用中，只要得到相对最小属性约简就可以了。常用的方法是利用属性重要性作为启发式信息，从信息系统或决策表中找出属性的约简。为了计算约简，波兰华沙大学数学家Skowron提出了区分矩阵的概念，其定义如下：定义3.13 设是一个信息系统，a(x)是对象x在属性a上的取值，则区分矩阵(Discernibility Matrix)的任一元素为： .因此cij是可以区分两个对象xi和xj的所有属性的集合。由定义可知，区分矩阵是对称矩阵。有的文献也称其为分明矩阵、可辨识矩阵、差异矩阵或差别矩阵。当考虑决策属性时，决策属性相同的对象之间我们认为没有区别，在区分矩阵中不予区分，