（计算机应用技术专业论文）二进制在集合运算与数据挖掘中的应用研究.pdf

二进制在集合运算与数据挖据中的应用研究 摘要 集合论的提出及发展大大促进7 诗算机连嚣技术的剿瓤，尤其，近些 年来迅速发展起来的r o u g h 集理论，对于处理不确定、不精确、模糊信息 提供了良好的解决方法，加快了人工智畿技术的发展。但罴，集合运算计 算机实现技术的落磊严重骓碍7 集会的进一步应焉。二进嬲与集合存在蓑 密切的内在联系，二进制位运算是计算机中处理速度最快的运算，而且二 进制数据运用方便，变化灵活。 本文将二进制弓l 入翔集合运算中，并不蘸加深研究。酋先，探讨了集 合运算的基本概念，通过分析= 进制与集合之间的内在联系，在集合基本 运算中采用二进制位运算方式，并给出了各种基本运算的具体实现算法。 接着，遴过对糖糙集理论的研究，阐明了糖糙集理论是一种尤为遗用于不 确定、不完备系统的数据挖撼的数学工具，其中，重点探讨了属性约筒以 及数据挖掘的相关内容。在此基础上，提出了基于= 进制的粗糙集运算理 论，将= 迸制位运算运用舞粗糙集的基本运算、震性求核中，并丑提出了 相关的一些定理。然后，通过分析知识表以及决策表求核过程，找到新的 求核方法，提出新的定理及规则，并将求核运算转化为二进制数据的比较 运算，进一步提高了求核效率。最麝，通避分祈二避制与关联撬弼顼集的 关系，提出了基于二进制的关联规则挖掘算法，并分析比较了相对于传统 算法的优势。 关键词：集合论粗糙集二进制属性约简核知识表决策表 关联规则 r e s e a r c h0 fr o u g hs e to p e r 发r i o n sa n d d l 1 am 田啷gb a s e do nb 玳a r y a b s t r a c t t h ei n n o v a t i o no ft h ec o m p u t e ro p e r a t i o nt e c h n i q u ei sa c c e l e r a t e d 谢t ht h ed e v e l o p m e n to fs e t t h e o r y e s p e c h n y , r o u g h s e t t h e o r y - a m a t h e m a t i c a lt o o lf o rd e a l i n gw i t hi n e x a c t , u n c e r t a i no rv a g u e k n o w l e d g e - h a sg r e a t l yp r o m o t e dt h ed e v e l o p i n go fa r t i f i c i a li n t e l l i g e n c e h o w e v e r , t h e a l g o r i t h m sf o rs e ta p p l i c a t i o nw e r ei n e m c i e n tw h i c hh a sb l o c k e dt h ef u r t h e r a p p l i c a t i o no fs e tt h e o r y t h e r e sa ni n t e r n a lr e l a t i o nb e t w e e nb i n a r y s y s t e ma n ds e t b i to p e r a t i o ni st h ef a s t e s tw a ya st oc o m p u t e r s p r o c e s s s p e e d m o r e o v e r , i t sd a t ai sq u i t ec o n v e n i e n ta n dc h a n g e a b l ef o ra p p l y i n g t h i sp a p e ra p p l i e sb i n a r ys y s t e mi n t os e to p e r a t i o na n dg i v e saf u r t h e r r e s e a r c h t ob e o nw i t h ，t h eb a s i e - c o n c e p to fs e to p e r a t i o ni sd i s c u s s e d b i n a r ys y s t e mi si n t r o d u c e di n t os e to p e r a t i o nt h r o u g ha n a l y z i n gt h e i n t e r n a lr e l a t i o nb e t w e e nb i n a r ya n ds e t a l s ot h ea u t h o rg i v e sn st h e d e t a i l e dp r o c e s so fv a r i o u sb a s i co p e r a t i o n s n e x t , 埘t ht h es t u d yo fr o u g h s e tt h e o r y , t h ea u t h o rh o l d st h a tr o u g hs e tt h e o r yi sam a t h e m a t i c a lt o o l e s p e c i a l l yf o rd e a l i n gw i 值t h ed a t am i n i n go fi n e x a c to ri n c o m p l e t es y s t e m ， f o c u s i n go na t t r i b u t er e d u c t i o na n dd a t am i n i n g b a s e do nt h ea b o v e r e s e a r c h ，r o u g hs e to p e r a t i o nt h e o r yb a s e do rb i n a r yi sp r e s e n t e d b i t o p e r a t i o n i s a p p l i e d t o r o u g hs e t b a s i co p e r a t i o na n da t t r i b u t ec o r e a l g o r i t h m t h e nn e w c o l ea l g o r i t h m s ，t h e o r e m sa n dr u l e sa r ep r e s e n t e db y a n a l y z i n gt h ep r o c e s so fc o r eo p e r a t i o no fd e c i s i o nt a b l ea n dk n o w l e d g e t a b l e t h ea l g o r i t h m st r a n s f o r mt h e w a y t og e tt h ec o r ei n t ot h ec o m p a r i s o n o fn u m b e r s i ti sm o r ee m c i e n ta n de f f e c t i v et h a nt h et r a d i t i o n a la l g o r i t h m s f i n a l l y , t h r o u g ha n a l y z i n g t h er e l a t i o nb e t w e e n b i n a r ys y s t e ma n d a s s o c i a t i o n r a l e s , b i n a r y - b a s e da s s o c i a t i o nr u l e sm i n i n ga l g o r i t h mi s p r e s e n t e dw h i c hi sm o r ee f f i c i e n ta n de f f e c t i v et h a nt h et r a d i t i o n a l a l g o r i t h m s k e yw o r d s ：s e tt h e o r y ；r o u g hs e t ；b i n a r y ；a t t r i b u t er e d u c t i o n lc o l e ； d e c i s i o nt a b l e ；k n o w l e d g et a b l e ；a s s o c i a t i o nr u l e s 广西大学硕士掌位论文= 避制在，l 合避算与羲捆挖i 中的应月日兜 1 1 国内外研究现状 第一章绪论 集合论在计算机科学、人工智能领域、逻辑学及语言学等方面的理论研究成果已经 很多，但在理论研究中人们主要是利用传统数学方式对集合进行描述，对于集合的计算 机实现算法研究很少，主要局限文 5 - 9 】所提到的一些方法，这些方法由于自身操作的复 杂性导致集合运算的效率很低。 二进制位运算是计算机中最基本的运算，具有易于实现，运算速度快等特点，被广 泛应用与计算机的各个领域中，如密码学【l o l ，遗传算法【1 l 】，可变矩阵约简【1 2 1 ，编码 1 3 - 1 4 l 等，其主要思想是利用二进制的位操作来实现各种技术。随着人们对二进制认识的不断 加深，其应用领域也在不断扩大，运用技巧方法也不断被改进更新。在求集合幂集、组 合方面有学者曾尝试使用二进制来实现i ”】，但是由于所用技巧方法不当，时间复杂度仍 然很高。 随着数据挖掘技术和粗集理论的不断发展，人们将二者有效结合了起来，即出现了 对基于粗集理论的数据挖掘技术的研究。基于粗集理论的数据挖掘思想是：将数掘库中 的属性分为条件属性和决策属性，对数据库中的元组根据各个属性不同的属性值分成相 应的子集，然后根据条件属性划分的子集和决策属性划分的子集之间的上下近似关系生 成决策规则。将以粗集为代表的集合论方法应用到数据挖掘( d m ) 领域已经取得了一定的 成果1 1 6 - 2 9 】，一些学者曾尝试将二进制融于数据挖掘中 3 0 - 3 1 1 ，并且取得了良好的效果。 因此，将二进制应用于集合以及粗糙集运算中，完成数掘挖掘，无论在理论上还是 应用上都有待深入研究和发展，这为本课题的研究提供了契机。 1 2 论文的选题背景及意义 集合论是在1 9 世纪7 0 年代由德国数学家康托( gc a n t o r ) 在无穷序列和分析的有 关课题的理论研究中创立的”，康托对具有任意特性的无穷集合进行了深入的探讨，提 出了关于基数、序数、超穷数和良序集等理论，奠定了集合论的深厚基础，以后逐步发 展形成- - f 独立学科，一般称此时期的集合理论为经典集合论。经典集合论是以二值逻 辑为基础的，从集合和特征函数定义看，某个事物只能属于或不属于某集合，不可能有 广西大掌硕士掌位论文 ：遵口在，l 音葺i 算与羲冀挖掘中的应用研兜 第三种可能，这就是经典集合的二值性。但是随着集合论的发展，以及它与数学哲学密 切联系所作的讨论，出现了许多似是而非、自相矛盾的悖论，如著名的罗素 ( b a w r u s s e l l ) 悖论，有力的冲击了或者说动摇了集合论的发展，由此，激发许 多数学家、哲学家为克服这些矛盾而建立了各种公珊化集合论体系。出于二解决处理一些 问题的需要，2 0 世纪6 0 年代z a d e h 提出了f u z z y 集理论口1 ， 2 0 世纪8 0 年代波兰教授 z p a w l a k 等提出了r o u g h 集理论【3 】，这两种理论不同于经典集合理论，它们是一种新的 模糊集合理论，自问世以来，一直受到学术界的重视和青睐，并取得了喜人成果。 经典集合论曾为半个多世纪的计算机技术大发展立下不朽的功勋，并且当前仍然广 泛应用于各种计算机领域。但足，人脑是这个世界上最复杂、智能最高的系统，它的精 妙之处就在于能够处理信息的不确定性、不精确性、不完全性、模糊性、随机性和非单 调性，从而得到正确或满意的结论，为人们作出决策提供强有力的支持。在现实世界中， 人们对某个事物或事件进行判断、推理、预测、决策时，所面对的信息常常是不精确、 不完全或模糊的，这就要求我们在计算机中模拟人的智能行为时，计算机能够处理这类 信息。r o u g h 集理论作为经典集合论的扩展，是一种新的处理模糊和不确定知识的软计 算工具，它把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上 近似集和下近似集之差集。由于上近似集和下近似集都可以通过等价关系给出确定的数 学公式描述，所以含糊元素数目可以被计算出来，即在真假二值之间的含糊程度可以计 算。粗糙集自问世以来，无论是在理论还是应用上都是一种新的、最重要的并且发展非 常迅速的- - 1 7 研究领域，它在理论上的深远意义和应用中的巨大潜力正吸引着世界各国 许多专家学者的注意，尤其在人工智能的各个研究领域中发展尤其显著 4 】o 给定一个集合，对其进行计算机运算并不是一件容易事，传统的操作主要是将集合 元素存入数组或者字符串中，通过字符串的查找、比较、插入等操作完成集合的各种运 算，传统的这些操作算法空间、时问复杂度都很高，有的还牵扯到数据的移动，因此， 运算速度慢、效率低，大大制约了集合论在现实中的应用。如何快速有效的利用计算机 对集合以及粗糙集运算进行处理，一直是学术界关心的课题。本课题将通过讨论二进制 与集合之间的内在联系，提出基于二进制的集合运算理论，充分发挥二进制数据在计算 机中运算速度快、节约空问的优势，并对二进制在数据挖掘中的应用进行探索，以提高 数据挖掘效率。因此，基于二进制的集合运算及在数据挖掘中的应用研究是一项很有学 术价值和实防、意义的工作。 1 3 论文的主要工作 本文从二进制在经典集合计算中的应用研究入手，将二进制与集合联系在一起，进 而将二进制应用到粗糙集运算中，并对其在数据挖掘中的应用进行了探讨。论文主要完 2 广西大掌硕士掌位能- ，：= 苴制在薯1 短，算与羲据挖掘中的应用研究 成了以下几个方面的工作： 1 、研究了经典集合运算与二进制位运算的关系，指出了传统经典集合运算计算机 实现方法的缺点，实现了二进制与集合基本运算的结合，并给出了相关算法。 2 、研究了糊糙集的基本理论和方法，讨论了丰h 糙集基本运第与集合的联系，蕈点 研究了二进制位运算在粗糙集基本运算中以及属性核约简中的应用，并结合实例分析了 基于二进制位运算的粗糙集运算的优点，得出了有意义的结论。 3 、通过分析属性约简过程，得出相关定理，提出了基于二进制的知识表核约简以 及基于二进制的决策表核约简思想，将求核过程转化为数值的比较，并通过理论分析和 实例说明了算法的有效性。 4 、通过分析二进制与关联规则项集的关系，提出了基于二进制的关联规则挖掘算 法，并分析比较了相对于传统算法的优势。 1 4 论文的组织结构 本文针对传统集合运算计算机算法运算效率低的问题，将二进制引入到集合以及数 据挖掘中，围绕二进制在集合以及粗糙集运算中的应用，逐步展开全面而深入的研究。 本文各章节的安排如下：1 第一章绪论 介绍了论文的选题背景，阐述了论文选题的意义，并对本课题的国内外研究现状进 行了介绍。 第二章基于二迸制的集合运算研究 首先介绍了集合的基本概念，然后分析比较二进制与集合之间的内在联系，最后， 通过二进制位运算实现了集合的各种基本运算，并且对相关算法给出了c 语占源代码。 第三章粗糙集理论概述 本章首先介绍粗糙集理论的基本概念，然后分析了该理论的研究状况，最后对粗糙 集理论在数据挖掘中的应用进行了研究。 第四章基于二进制的粗糙集基本运算研究 本章在第一章基于二进制的集合运第研究的基础上，通过讨论二进制与租糙集之问 的内在联系，提出了基于二迸制的羊f 1 糙集运算理论。借l i 助位操作对租糙集进行运算，充 分发挥其运算速度快、节约空间的优势，并且给出了相关算法的c 语言源程序。 第五章基于位运算的属性核约简 本章是二进制位运算在粗糙集中的进一步应用，通过将二进制位运算运用到知识表 属性的核约简中，提高求核效率。 第六章基于二进制的知识表求核算法 二置制在j 冀e 算与羲捆挖掘中的应用研兜 本章首先分析知识表求核过程，得出了一个重要分类定理，然后，将二进制引入求 核算法中，利用此定理将属性核的求解变为数值的比较问题，充分利用t - - 进制数据处 理灵活，运算速度快的优势，可以将时间复杂度降n o ( i u r ! ) 。 第七章基于二进制的决策表求核算法 本章首先分析了决策表求核过程，提出了相关定理和规则，在此基础上，将二进制 运用到求核算法中，将决策表属性核的求解变为数值的查找、比较问题，从而将算法时 问复杂度大大降低。 第八章基于二进制的关联规则挖掘算法 本章通过分析二进制与关联规则项集的关系，将二进制引入到关联规则挖掘过程 中，减少了事务子集的求解次数，从而减少了时间复杂度，提高了挖掘效率。 第九章总结 对论文工作进行了总结，对后续研究进行了展望。 4 广西大掌硕士掌位论文 = 避徊在j l 舌r 葛| j 与羲据挖舅l 中的应用研竞 第二章基于二进制的集合运算研究 集合论是在十九世纪末由德国数学家康托创立的，以后逐步发展形成一门独立学 科，由于广泛的使用了数理逻辑的工具，集合论逐渐成为数理逻辑的一个分支，并从6 0 年代以来获得迅速的发展，现已渗透到数学的许多分支中，并在计算机的人工智能等领 域得到了广泛应用，如粗糙集，模糊集等数掘挖掘方法中都大量使用了集合的各种运算。 但是，目前关于集合运算计算机实现算法的相关研究文献不多，而传统的对集合操作主 要是利用字符串匹配、查询等来实现1 5 】，效率低，而且对空间要求很高，大大制约了集 合理论向实际应用的转化，如何快速有效的利用计算机对集合运算进行处理一直是学术 界关心的课题。 本章首先介绍了集合的基本概念，然后分析比较二进制与集合之间的内在联系，最 后，通过二进制位运算实现了集合的各种基本运算，并且对相关算法给出了c 语言源代 码。 2 1 集合的概念 2 1 1 集合基本定义 定义2 1 集合是一些确定的对象的全体，对象称为元素，若a 是集合a 的元素，则 记为a a 。 定义2 2 不含任何元素的集合叫做空集，记做 ) 或巾。 定义2 3 设a b 为集合，若任意d a 一定有口b ，则称a 是b 的子集，也称a 被b 包含，或b 包含a ，记为爿互b 。 定义2 4 设a ，b 为集合，若a b 且b 彳，则称a 与b 相等，记为a = b 。 定义2 5 若彳b ，但是a b ，则称a 是b 的真子集，记为a c b 。 定义2 6 幂集：由a 的所有子集组成的集合称为a 的幂集，记为p ( a ) 或2 4 。 定义2 7 基数：集合a 中元素的个数称为a 的基数，记为川。 广西大掌硕士掌位论文二置翻在鼻- 寺逞算与羲据挖掘中的矗l 用研究 2 1 2 集合的基本运算 定义2 8 交集：集合a 与b 的交集a n b = x l x a 并且x b ，。 定义2 9 并集：集合a 与b 的并集a u b = fxr x a 或x b 。 定义2 1 0 a ，b 是分离的，若a n b = 中 定义2 1 l 相对补：集合a 对b 的相对补a b = x x a 并且x 茌b 。 定义2 1 2 补集：集合a 的补集为全集e 与a 的差，记为a 。 定义2 1 3 对称差：集合a 与b 的对称差a o b = ( a b ) u ( b - a ) 。 2 2 集合与二进制的关系 二进制自问世以来，在计算机的研究和应用领域起着重要的作用，它的值域只有 “0 ”，“l ”两个值，但是通过对这两个值的有效组合和简单运算，却能表达出客观真实 世界的千变万化，下面通过分析二进制和集合之间强大的内在联系，说明二进制在集合 运算中的巨大作用。 若集合a 具有n 个元素，则a 的所有子集( 幂集) 的个数| p ( a ) p 2 ”，例如，a = 如，c ， 则a 的幂集为 中， a ) ， b ，( a b ， c ， a ，c ) ， b ，c ， a b ，c ) ) ，a 的幂集的基数为2 = 8 。 长度为n 的二进制位所能表达的数据个数为2 ”，例如长度为3 的二进制位，所能生 成的数据为0 0 0 ，0 0 1 ，0 1 0 ，0 1 1 ，1 0 0 ，1 0 1 ，l l o ，1 1 l ，共2 3 = 8 个数据。 通过比较发现，长度为n 的二进制位所能表达的数据个数和具有相同元素个数的集 合的所有子集( 幂集) 的数且相同，由此可以猜想二进制和集合之间应该具有某些联系，现 在做以下规定： 规定2 1 对于集合f f o ，f 。，f z ，一，f 。， ，规定一个n 位的二进制数卢 m p + 1 p l p o ) 与之对应，其中二进制数的第0 位p o 对应集合的第0 个元素i 。，第1 位p 7 对应第1 个元 素i 。，第k 位对应第k 个元素“。 例2 1 规定一个3 仿的二进制数，用此二进制数的笫0 位代表上面所提到的集合a 的a 元素，第l 位代表集合a 的b 元素，第2 位代表集合a 的c 元素，然后比较集合a 的幂集和二进制数据的关系，如表2 1 所示： 6 = 遵制在j 青置 算j ，羲蕾挖舅l 中的点l 研究 表2 - i 集合与二进制对应关系h = l a , b , c ) t a b l e2 - 1r e l a t i o nb e t w e e nb i n a r ya n dt h es u b s e t so f a = i n 占f ) 序号 子集 二进制数 n o s u b s e t s b i n a r y 0 o 0 0 0 1 a o o l 2 b ) 0 1 0 3 f a ，b 0 1 l 4 c 1 0 0 5 a ，c 1 0 1 6 b ，c 1 1 0 7 a ，b ，c 1 1 1 通过比较发现，如果我们按照表2 1 中的对应关系对子集进行编号，则集合第i 个 子集和二进制所产生的第i 个数据之间存在着非常微妙的对照关系：如果在子集中某个 元素存在，则此子集对应的二进制数中该元素所对应的二进制位为l ，否则为0 。例如， 子集 咖 ，因为a 对应二进制第0 位，b 对应二进制第l 位，c 对应二进制的第三位，而 c 元素没有在此子集中出现，所以，其对应的二进制数为0 1 1 。 定义2 1 4 子集的下标：集合a 的子集所对应的二进制数的十进制数值称为此子集 的下标。 有了集合与二进制之间的这种内在联系，以后在对集合操作时，我们没有必要对子 集中的实际元素进行处理，只要知道子集的下标，就可以很容易的利用位运算来实现对 集合进行各种操作的目的。 2 3 基于二进制的集合运算 2 3 1 用二进制求集合的幂集 已知集合a ，求a 的幂集。 由于集合子集中的元素与子集下标中二进制位的“l ”相对应，因此求子集中元素 的运算可以转化为寻找子集下标二进制位中“l ”所在位置的运算，此运算可以利用移 位操作来实现。例如，求1 0 1 所对应的a 的子集，我们可以通过3 次移位，每次先将当 前的数值与数值1 相与，如果结果等于1 ，则本次第0 位上的值为l ，否则为0 ，由移位 7 广西大掌硕士掌位论文 ：进翻在鼻r 膏q 0 算与铖据挖* 中的应用日完 的次数可以知道当前第0 位的l 在原数据中的位置，从而找到对应的实际元素。运算如 下： 第0 次与：l o l & 0 0 1 = 1，a 对应二进制位的第0 位，而且本次相与的结果为1 ， 所以a 属于此子集： 1 0 1 右移一位，现在的数值为0 1 0 第1 次与：0 1 0 & 0 0 1 = 0 ，b 对应二进制位的第l 位，而且本次相与的结果为0 ，所 以b 不属于此子集。 o l o 右移一位，现在的数值为0 0 1 第1 次与：0 0 1 & 0 0 1 = l ，c 对应二进制位的第2 位，而且本次相与的结果为1 ，所 以c 属f 此子集。 0 0 1 右移一位，现在的数值为0 0 0 。 计算完毕。求出1 0 1 对应的a 的子集为 a ，c l 。 求子集元素的c 语言算法程序如下： af i n d e l e m e n t 找出集合h 中子集下标b 所对应的子集中的所有元素 v o i df i n d e l e m e n t ( c h a ra ，u n s i g n e db ) i n tf ，j = o ： * f 标志当前输出是否为子集的第一个元素，j 记录移位次数木 f - - o ： p r i n t f ( ”n ”) ： w h i l e ( b o ) i f ( ( b & 1 ) 0 ) i f ( f = = o ) ff = l ： p r i n t f ( ”c ”，a j ) ： ) e l s e p r i n t f ( ”，c ”，a j ) ： b = b l ： j = j + l ： p r i n t f ( ) ： ；进在j l 寺4 算与致* 挖* 中的应用日完 若求a 的所有子集，只要从子集下标0 2 l 卅依次求各对应子集的元素即可，本算法 可用一个循环完成，代码如下： v o i dt l n d c h l 】d s e t s ( c h a ra ： 。u n s i g n e dn ) n = 2 1 4 为a 的子集个数， u n s i g n e di ： f o r ( i = o ：i n ：i + + ) f i n d e l e m e n t ( a ，1 ) ： 2 3 2 用二进制求集合的交集 设集合毋f 均为集合a 的子集，求口n ； 由交集的定义知，集合的交集概念和二进制中位的与运算是相似的，所以求交集的 运算转变为求两个二进制数的位与运算，通过两个集合下标的位与运算我们可以得到两 个集合交集下标的值，从而很快得到两个集合中的公共元素。例如，b = a ，c ，对应的 二进制数为1 0 1 ，c = a ，b ，对应的二进制数为0 1 1 ，因为l o l & 0 1 1 = 0 0 1 ，所以口n 庐 a 。 本运算对应算法的c 语言代码如下： u n s i g n e di n t e r s e c t i o n ( u n s i g n e ds e t l ，u n s i g n e ds e t 2 ) 返回值为交集下标 r e t u r n ( s e tl & s e t 2 ) ： 对返回值调用f i n d e l e m e n t 子程序，求出交集中的所有元素。 2 3 3 用二进制求集合的并集 设集合忍f 均为集合a 的子集，求占u 由并集的定义知，集合的并集概念和二进制中位的或运算是相似的，所以可以将求 并集的运算转变为求两个集合下标的位或运算，从而得到两个集合并集的下标值，根据 下标值调用f i n d e l e m e n t 子程序得到并集的所有元素。例如b = a ，c ，对应的- - i 挂q 数 为1 0 1 ，c _ a ，b ，对应的二进制数为0 1 1 ，因为1 0 1 1 0 1 1 = i i l ，所以b u 庐 a ，b ，c 。对 9 = m 在毒女4 囊坷敦l 把l 中的应用研究 应算法的c 语言代码如下 u n s i g n e du n i o n s e t ( u n s i g n e ds e t l ，u n s i g n e ds e t 2 )返回值为并集下标 r e t u r n ( s e t ls e t 2 ) ； 对返回的值调用f i n d e l e m e n t 子程序，求出并集中的所有元素。 2 3 4 用二进制求集合的补集 设集合口为全集a 的子集，求鼠 由补集的定义知，集合的补集与二进制数据的按位求反是一致的，因此可以将此运 算转换为求集合b 下标值的按位求反操作，例如b = a ，c ) ，对应的二进制数为1 0 1 ，则 1 0 1 = i i i 1 0 1 = 0 1 0 ，所以b = b 。本运算对应算法的c 语言代码如下： u n s i g n e dc o m p l e m e n t ( u n s i g n e ds e t ，u n s i g n e dn ) n = 2 1 4 1 ，返回值为补集下标 r e t u r n ( s e t n ) ； 2 3 5 用二进制求集合的相对补 设集合b ，c 均为集合a 的子集，求b c 。 由相对补定义知，此运算可以转换为b n ( c ) ，所以相对补运算相当于交集和补集 的复合运算。因此求b - c ，可以先求c 的补集对应的二进制数，然后，将所求结果与b 下标进行与运算，从而得出b c 对应的下标值。例如b = a ，c ，对应的二进制数为1 0 1 ， c = a ，b ，对应的二进制数为0 1 1 ，因为0 1 l = 1 1 l “0 1 1 = 1 0 0 ，1 0 】1 0 0 = 1 0 0 故b c = c 。 本运算对应算法的c 语言代码如下： u n s i g n e dd i f f e r e n c e ( u n s i g n e ds e t l ，u n s i g n e ds e t 2 ，u n s i g n e dn ) n = 2 1 4 1 ，返回值为相对补集下标 1 0 广西大掌司e 士掌位论，t ：遵制在，l 音葺i 算与羲l 挖掘中的应用研究 r e t u r n ( s e t l c o m p l e m e n t ( s e t 2 ，n ) ) 2 3 6 判断一个集合是否是另一个集合的子集 设集合b ，c 均为集合a 的子集，判断b 是否是c 的子集。 由子集定义知，若任意x b 一定有x c ，即集合b 中的所有元素都存在于集合c 中，故b u c = c ，所以判断b 是否是c 的子集可以转换为判断b 的下标和c 的下标相 或后是否等于c 的下标的问题，如等于c 的下标则b c 。本运算对应算法的c 语言代 码如f ： i n ti s s u b s e t ( u n s i g n e ds e t l ，u n s i g n e ds e t 2 ) 判断是否s e t l 互s e t 2 r e t u r n ( ( s e t1s e t 2 ) - - s e t 2 ) ： 2 4 本章小结 本章通过比较二进制与集合问的内在联系，将二进制运用在集合的各种基本运算 中，用二进制进行集合运算主要进行的是位运算，所以速度快，空间要求低，在对大量数 据集合的运算中优势尤为明显。本章只是简单列举了常用的集合基本运算算法的实现， 集合的其它各种运算可以通过这些基本运算的复合运算得到。 集合理论在现代数学领域和计算机领域都起到了举足轻重的作用，尤其人工智能的 发展更加快了集合理论与实际应用的联系，本章所提出的集合操作算法将有利于集合理 论在计算机领域的进一步应用，并促进集合其他分支与计算机的联系，第四章将将二进 制引入粗糙集运算中，着芎讨论二进制在粗糙集基本运算中的运用。 广西大攀硕士掌位论文= 避制在l 音目l 幕与& * 挖l 中的应用* 兜 第三章粗糙集理论概述 r o u g hs e t 理论是由波兰华沙理工大学p a w l a k 教授于2 0 世纪8 0 年代初提出的一种 研究不完整、不确定知识和数据的表示、学习、归纳的理论方法，是一种有别于模糊集 的新型的数掘分析技术。该理论是建立在分类机制的基础上的，它将分类理解为存特定 空间上的等价关系，而等价关系构成了对该空间的划分。它将分类与知识联系在一起， 把知识理解为对数据的划分，每一被划分的集合称为概念。其主要思想是利用已知的知 识库，将不精确或不确定的知识用已知的知识库中的知识来( 近似) 刻画。它以等价关系、 上近似、下近似等作为基本概念。r o u g h 理论为发现不精确和不确定知识中的重要数据 结构以及复杂对象的分类提供了强有力的理论基础，已广泛应用于数据挖掘【3 2 1 、人工 智能【3 4 1 和分类 3 5 1 等领域。 本章首先介绍粗糙集理论的基本概念，然后分析了该理论的研究状况，最后对粗糙 集理论在数据挖掘中的应用进行了研究。 3 1 粗糙集理论的基本概念口铂 粗糙集把客观世界或对象世界抽象为一个信息系统( i n f o r m a t i o ns y s t e m ) ，也称属 性一值系统。信息系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列 对应对象的属性，对象的信息是通过指定对象的各属性值来表达。 定义3 1 一个信息系统是一个四元组s = ( u ，a ，v ，力，其中， u = x 1x ：，x 。 是对象的非空有限集合，称为论域( h 表示对象个数) ； a 是属十牛的非窄有限集合，a = c u d ，c n d = o ，c 和d 分别称为条件属件集和 决策属性集； y = u 吒是属性值的集合，圪是属性口的值域； 瓶 ，：u x a 斗矿是一个信息函数，它为每个对象的每个属性赋予一个信息值，即 v a ，x u ，f ( x ，口) 圪。 1 2 广西大掌司e 士掌位论文 = 避制在，古遣算与藏据挖l 中的应用日完 s 也可以简记为：s = ( u ，a ) 。如果一个信息系统的决策属性为空集，我们称此信息 表为知识表，否则称此信息表为决策表。信息表中的一个属性集对应一个等价关系，一 个信息表可以看成是定义的一族等价关系，即知识库。 定义3 2 在一个信息系统s = ( u ，a ) 中，对任一属性集合b a ，不可分辨关系 ( i n d i s c e r n i b i l i t yr e l a t i o n ) 以1 n d ( b ) 表示，其定义如下： i n d ( b ) = ( 五y ) u x 硼v b b ，厂( 葺6 ) = 厂( ) 6 ) 。 若( 石，y ) i n d ( b ) ，则称工和y 是b 不可区分的，或相对于b 是不可分辨的。容易 证明，i n d ( b ) 是【，上的等价关系。二元组a = ( u ，i n d ( b ) ) 构成了一个近似空间。等价 关系1 n d ( b ) 把u 划分为k 个不相交的等价类，这些等价类称为b 基本集( b e l e m e n t a r y c o n c e p t ) 或曰原子集u 1 n d ( b ) = x ，x 。) 表示关系i n d ( b ) 在u 上的等价类族， 简记为u b 。符号【x b 表示包含x u 的曰等价类。为方便起见，空集一般也认为是基 本集。 若将u 中的集合称为概念或知识，则a 称为知识库，原子集表示基本概念或知识 模块。任意有限的基本集的并和空集均称为可定义集，否则称为不可定义集。可定义集 也称为精确集，可以在知识库中被精确地定义或描述，可表示已有的知识。不可定义集 也称为非精确集或粗糙集。对于粗糙集可以近似地定义，使用两个精确集，即粗糙集的 上近似( u p p e ra p p r o x i m a t i o n ) 和下近似( 1 0 w e ra p p r o x i m a t i o n ) 来描述： 定义3 3 令s = ( u ，a ) 为一个信息系统，对任何一个对象子集x u 和属性子集 b a ，x 关于b 的下近似和上近似分别定义为： 蹦= u ，r u i n d ( b ) l y x ， 戤= u y e u i n d ( b ) r f 7 x a l 。 在此基础上，分别定义x 关于口的正域、负域和边界域如下： 正域：p o s 口( x ) = 酗； 负域：n e g 口( z ) = u b x ； 1 3 广西大掌硕士学位论文 = 避匍在毒r 寺葺i 算与效蜘挖掘中的应用研究 边界域：b n b ( x ) = 戤一b _ x 。 8 _ x 或p o s 。( ) 是由那些根据b 判断肯定属于的u 中元素组成的集合：砑是那 些根据b 判断u r 能属fx 的ul 1 几亲组成的集合；b n 。( x ) 是那些根据b 既小能判断 肯定属于x 又不能判断肯定属于( u - x ) 的u 中元素组成的集合；n e g 。( x ) 是那些根 据b 判断肯定不属于z 的u 中元素组成的集合。如果b n 。( x ) = o ，则是b 可定义 集，否则x 是曰粗糙集。图3 1 是对上述几个基本概念的一个直观表示： i一一 ! 十，f ，一一 l 一 ；i l ：1l il ll i | l l；i 午瑶 l li f b n 3 b x - - b x 图3 1 用石的上，下近似集对实例集z 的近似逼近 ( 矩形区域表示等价类) f i g 3 1 a r o u g hs e ta p p r o x i m a t i o no f t h es e to f s a m p l e so f t h ec l a s s x u s i n gl o w e ra n d u p p e ra p p r o x i m a t i o ns e t so f x t h er e c t a n g u l a rr e g i o n sr e p r e s e n te q u i v a l e n c ec l a s s e s 定义3 4 由等价关系i n d ( b ) 定义的集合x 的近似精度( a c c u r a c yo f a p p r o x i m a t i o n ) 为： f b x l 卜耐 其中肖a ，i i 表示集合朋狗基数。该比值反映我们对于了解集合肼知识的安全程度。 显然，对于每个b 和x u 有0 ( x ) 1 。 定义3 5 粗糙隶属函数( r o u g h m e m b e r s h i p f u n c t i o n ) 可以定义为 娘加谢 该函数表示了x 属于珊q 确定程度。显然，：( 力【o ，1 】。 定义3 6 属性集合d 对c 的属性依赖程度( d e g r e eo f d e p e n d e n c y ) 记为七 1 4 广西大掌硕士掌位论文 二避制在毒- 奢遣算与i d 暑挖掘中的应用研完 后= y ( c ，。) = p o s 孑c 广( d ) 其中，p o s c ( d ) = u ( x ) 为正区域，它包含了u 中所有利用条件属性c 可以 分类到决策属性d 的对象。 如果d 是全部决策属性，c 是条件属性，则表示用c 对u 划分后，任意x u 能 被正确划分到决策类的概率，同时刻划了条件属性c 描述决策属性d 的能力。 定义3 7 在属性依赖程度的基础上，属性口相对于b 对于d 的依赖程度的属性重 要度( s i g m f i c a n c eo f a na t t r i b u t e 口) 为： s g f ( a ，b ，d ) = r ( b + 口 ，d ) - 7 ( b ，d ) 可见，属性独立性改变越大，属性口对决策划分的影响越大，相对于决策属性来说， 也就越重要。 3 2 属性约简 属性约简是粗糙集理论的核心内容之一。知识库中的属性并不是同等重要的，甚至 某些知识是冗余的。冗余知识的存在，一方面是对资源的浪费，另一方面则干扰人们做 出正确而简洁的决策。所谓知识约简，就是在保持知识库分类或决策能力不变的条件下， 删除其中不相关或不重要的知识。我们可以使用约简后的属性集合代替原来的整个属性 集合而不降低分类效果。粗糙集中的知识约简包括两方面的内容，即属性约简和值约简。 3 2 1 属性约简 定义3 8 信息系统s = ( u ，a ) ，其中a = c u d ，令b c c 为条件属性的非空子集。 如果存在一子集b cb 有i n d ( b ) = i n d ( b ) ，则称b 为属性依赖集，否则，称曰为独立 集。如果b c 为独立集，且i n d ( c ) = i n d ( b ) ，则b 称为c 的约简。c 的所有约简族记 为r e d ( o 。 定义3 9 对于任意属性口c ，如果i n d ( 6 3 ， r d ( g a ) ) ，则称a 为c 中必要的； 否则，口为c 中不必要的。c 中所有必要关系的集合称为c 的核，记为c o r e ( o ，且有 c o r e ( c ) = f l r e o ( c ) 。一般，属性的约简不唯一，而核唯一。 定义3 1 0 若p o s c ( d ) = p o s t c 一 r ) ( i n d ( d ) ) ，则称r 为c 中d 不必要的，否则称 广西大掌司e 士掌位论文：避口在j - 电r 遵算与囊据挖舅i 中的应用研究 r 为c 中d 必要的。对于b c 如果存在一子集b 。c 7 b ， 有 p o s ，( i n d ( d ) ) = p o s 。( i n d ( d ) ) ，则b 称为相对于d 的依赖集，否则，称为相对于d 的独立集。 定义3 1 l 若b c c 是相对于d 的独立集，j | p o s c ( i n d ( d ) ) = p o s b