【毕业学位论文】（Word原稿）二进制在集合运算与数据挖掘中的应用研究-计算机应用技术

二进制在集合运算与 数据挖掘中的应用研究 李天志 二 0 0 六年 六 月 硕士学位 论 文 李天志 硕 士 二制 在 集 合运算与数据挖掘中的应用研究 2006 分类号 密级 硕士学位论文 二进制在集合运算与 数据挖掘中的应用研究 李 天 志 学科专业 计算机应用技术 指导教师 梁家荣 教授 论文答辩日期 2006 年 6 月 日 学位授予日期 答辩委员会主席 论文评阅人 i 二进制在集合运算与数据挖掘中的应用研究 摘 要 集合论的提出及发展大大促进了计算机应用技术的创新，尤其，近些年来迅速发展起来的 理论，对于处理不确定、不精确、模糊信息提供了良好的解决方法，加快了人工智能技术的发展。但是，集合运算计算机实现技术的落后严重阻碍了集合的进一步应用。二进制与集合存在着密切的内在联系，二进制位运算是计算机中处理速度最 快的运算，而且二进制数据运用方便，变化灵活。 本文将二进制引入到集合运算中，并不断加深研究。首先，探讨了集合运算的基本概念，通过分析二进制与集合之间的内在联系，将二进制位运算引入到集合基本运算中，并给出了各种基本运算的具体实现算法。接着，通过对粗糙集理论的研究，阐明了粗糙集理论是一种尤为适用于不确定、不完备系统的数据挖掘的数学工具，其中，重点探讨了属性约简以及数据挖掘的相关内容。在此基础上，提出了基于二进制的粗糙集运算理论，将二进制位运算运用到粗糙集的基本运算、属性求核中，并且提出了相关的一些定理。 然后， 通过分析知识表以及决策表求核过程，找到新的求核方法，提出新的定理及规则，并将求核运算转化为二进制数据的比较运算，进一步提高了求核效率。最后，通过分析二进制与关联规则项集的关系，提出了基于二进制的关联规则挖掘算法，并分析比较了相对于传统算法的优势。 关键词：集合论；粗糙集；二进制；属性约简；核；知识表；决策表；关联规则；数据挖掘 of is of a or of of s an is as to is a of is is us of of is a of or on on on is is to by of of to of It is is is 西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 目 录 第一章 绪 论 . 1 . 1 . 1 文的主要工作 . 2 文的组织结构 . 3 第二章 基于二进制的集合运算研究 . 5 . 5 合基本定义 . 5 . 6 . 6 于二进制的集合运算 . 7 二进 制求集合的幂集 . 7 二进制求集合的交集 . 9 二进制求集合的并集 . 9 二进制求集合的补集 . 10 二进制求集合的相对补 . 10 断一个集合是否是另一个集合的子集 . 10 . 11 第三章 粗糙集理论概述 . 12 糙集理论的基本概念 . 12 性约简 . 15 性约简 . 15 约简与规则提取 . 17 糙集的理论研究 . 18 . 18 . 18 . 19 章小结 . 20 第四章 基于二进制的粗糙集基本运算研究 . 21 进制与粗糙集的内在联系 . 21 于二进制的粗糙集基本运算 . 21 糙集的上近似集 . 22 糙集的下近似集 . 22 . 23 合的基数 . 24 糙集运算举例 . 24 . 24 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 第五章 基于位运算的属性核约简 . 26 . 26 . 27 . 27 . 30 . 30 例分析 . 30 . 31 第六章 基于二进制的知识表求核算法 . 32 . 32 . 33 . 35 . 35 第七章 基于二进制的决策表求核算法 . 36 . 36 . 37 . 40 . 40 第八章 基于二进制的关联规则挖掘算法 . 42 . 42 . 43 . 43 . 43 . 44 . 45 . 46 第九章 总结 . 48 作小结 . 48 在的问题 . 48 一步的工作 . 49 参考文献 . 50 致 谢 . 55 攻读硕士学位期间完成的学术论文 . 56 攻读硕士学位期间参加的科研项目 . 57 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 1 第一章 绪 论 内外研究现状 集合论在计算机科学、人工智能领域、逻辑学及语言学等方面的理论研究成果已经很多，但在理论研究中人们主要是利用传统数学方式对集合进行描述，对于集合的计算机实现算法研究很少， 主要局限文 5提到的一些方法，这些方法由于自身操作的复杂性导致集合运算的效率很低。 二进制位运算是计算机中最基本的运算，具有易于实现，运算速度快等特点，被广泛应用与计算机的各个领域中，如密码学 10，遗传算法 11，可变矩阵约简 12，编码 13，其主要思想是利用二进制的位操作来实现各种技术。随着人们对二进制认识的不断加深，其应用领域也在不断扩大，运用技巧方法也不断被改进更新。在求集合幂集、组合方面有学者曾尝试使用二进制来实现 15，但是由于所用技巧方法不当，时间复杂度仍然很高。 随着数据挖掘技术和粗集理论的不断发展，人们将二者有效结合了起来，即出现了对基于粗集理论的数据挖掘技术的研究。基于粗集理论的数据挖掘思想是：将数据库中的属性分为条件属性和决策属性，对数据库中的元组根据各个属性不同的属性值分成相应的子集，然后根据条件属性划分的子集和决策属性划分的子集之间的上下近似关系生成决策规则。将以粗集为代表的集合论方法应用到数据挖掘 (域已经取得了一定的成果 16一些学者曾尝试将二进制融于数据挖掘中 30并且取得了良好的效果。 因此，将二进制应用于集合以及粗糙集运 算中，完成数据挖掘，无论在理论上还是应用上都有待深入研究和发展，这为本课题的研究提供了契机。 文的选题背景及意义 集合论是在 19 世纪 70 年代由德国数学家康托（ G. 无穷序列和分析的有关课题的理论研究中创立的 1，康托对具有任意特性的无穷集合进行了深入的探讨，提出了关于基数、序数、超穷数和良序集等理论，奠定了集合论的深厚基础，以后逐步发展形成一门独立学科，一般称此时期的集合理论为经典集合论。经典集合论是以二值逻辑为基础的，从集合和特征函数定义看 , 某个事物只能属于或不属于某集合 , 不 可能有第三种可能，这就是经典集合的二值性。但是随着集合论的发展，以及它与数学哲学密广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 2 切联系所作的讨论，出现了许多似是而非、自相矛盾的悖论，如著名的罗素（ B A W 论，有力的冲击了或者说动摇了集合论的发展，由此，激发许多数学家、哲学家为克服这些矛盾而建立了各种公理化集合论体系。出于解决处理一些问题的需要， 20 世纪 60 年代 出了 理论 2， 20 世纪 80 提出了 理论 3，这两种理论不同于经典集合理论，它们是一种新的模糊集合理论，自 问世以来，一直受到学术界的重视和青睐，并取得了喜人成果。 经典集合论曾为半个多世纪的计算机技术大发展立下不朽的功勋 ，并且当前仍然广泛应用于各种计算机领域。但是，人脑是这个世界上最复杂、智能最高的系统。它的精妙之处就在于能够处理信息的不确定性、不精确性、不完全性、模糊性、随机性和非单调性，从而得到正确或满意的结论，为人们作出决策提供强有力的支持。在现实世界中，人们对某个事物或事件进行判断、推理、预测、决策时，所面对的信息常常是不精确、不完全或模糊的，这就要求我们在计算机中模拟人的智能行为时，计算机能够处理这类信息。 理论作为经典集合论的扩展，是一种新的处理模糊和不确定知识的软计算工具，它把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于上近似集和下近似集都可以通过等价关系给出确定的数学公式描述，所以含糊元素数目可以被计算出来，即在真假二值之间的含糊程度可以计算。粗糙集自问世以来，无论是在理论还是应用上都是一种新的、最重要的并且发展非常迅速的一门研究领域，它在理论上的深远意义和应用中的巨大潜力正吸引着世界各国许多专家学者的注意，尤其在人工智能的各个研究领域中发 展尤其显著 4。 给定一个集合，对其进行计算机运算并不是一件容易事，传统的操作主要是将集合元素存入数组或者字符串中，通过字符串的查找、比较、插入等操作完成集合的各种运算，传统的这些操作算法空间、时间复杂度都很高，有的还牵扯到数据的移动，因此，运算速度慢、效率低，大大制约了集合论在现实中的应用。如何快速有效的利用计算机对集合以及粗糙集运算进行处理，一直是学术界关心的课题。本课题将通过讨论二进制与集合之间的内在联系，提出基于二进制的集合运算理论，充分发挥二进制数据在计算机中运算速度快、节约空间的优势，并对二 进制在数据挖掘中的应用进行探索，以提高数据挖掘效率。因此，基于二进制的集合运算及在数据挖掘中的应用研究是一项很有学术价值和实际意义的工作。 文的主要工作 本文 从二进制在经典集合计算中的应用研究入手，将二进制与集合联系在一起，进而将二进制应用到粗糙集运算中 ，并对其在 数据挖掘中的应用进行了探讨 。论文 主要完成了以下几个方面的工作： 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 3 1、研究了经典集合运算与二进制位运算的关系， 指出了传统经典集合运算计算机实现方法的缺点，实现了二进制与集合基本运算的结合，并给出了相关算法。 2、研究了粗糙集的基本理论和方 法，讨论了粗糙集基本运算与集合的联系，重点研究了二进制位运算在粗糙集基本运算中以及属性核约简中的应用，并结合实例分析了基于二进制位运算的粗糙集运算的优点，得出了有意义的结论。 3、通过分析属性约简过程，得出相关定理， 提出了基于二进制的知识表核约简以及基于二进制的决策表核约简思想，将求核过程转化为数值的比较，并通过理论分析和实例说明了算法的有效性。 4、通过分析二进制与关联规则项集的关系，提出了基于二进制的关联规则挖掘算法，并分析比较了相对于传统算法的优势。 文的组织结构 本文针对传统集合运算计算机 算法运算效率低的问题，将二进制引入到集合以及数据挖掘中，围绕二进制在集合以及粗糙集运算中的应用，逐步展开全面而深入的研究。本文各章节的安排如下： 第一章 绪论 介绍了论文的选题背景，阐述了论文选题的意义，并对本课题的国内外研究现状进行了介绍。 第二章 基于二进制的集合运算研究 首先介绍了集合的基本概念，然后分析比较二进制与集合之间的内在联系，最后，通过二进制位运算实现了集合的各种基本运算，并且对相关算法给出了 C 语言源代码。 第三章 粗糙集理论概述 本章首先介绍粗糙集理论的基本概念，然后分析了该理论的研究 状况，最后对粗糙集理论在数据挖掘中的应用进行了研究。 第四章 基于二进制的粗糙集基本运算研究 本章在第二章基于二进制的集合运算研究的基础上，通过讨论二进制与粗糙集之间的内在联系，提出了 基于二进制的粗糙集运算理论。借助位操作对粗糙集进行运算，充分发挥其 运算速度快、节约空间的优势，并且 给出了相关算法的 第五章 基于位运算的属性核约简 本章是二进制位运算在粗糙集中的进一步应用，通过将二进制位运算运用到知识表属性的核约简中，提高求核效率。 第六章 基于二进制的知识表求核算法 本章首先分析知识表求核过程 ，得出了一个重要分类定理，然后，将二进制引入求广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 4 核算法中，利用此定理将属性核的求 解变为数值的比较问题，充分利用了二进制数据处理灵活，运算速度快的优势，可以将时间复杂度降到 O(|U|*|R|)。 第七章 基于二进制的决策表求核算法 本章首先分析了决策表求核过程，提出了相关定理和规则，在此基础上，将二进制运用到求核算法中，将决策表属性核的求解变为数值的查找、比较问题，从而将算法时间复杂度大大降低。 第八章 基于二进制的关联规则挖掘算法 本章通过分析二进制与关联规则项集的关系，将二进制引入到关联规则挖掘过程中，减少 了事务子集的求解次数，从而减少了时间复杂度，提高了挖掘效率。 第九章 总结 对论文工作进行了总结，对后续研究进行了展望。 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 5 第二章 基于二进制的集合运算研究 集合论是在十九世纪末由德国数学家康托创立的，以后逐步发展形成一门独立学科， 由于广泛的使用了数理逻辑的工具，集合论逐渐成为数理逻辑的一个分支，并从 60年代以来获得迅速的发展 ，现已渗透到数学的许多分支中，并在计算机的人工智能等领域得到了广泛应用，如粗糙集，模糊集等数据挖掘方法中都大量使用了集合的各种运算。但是，目前关于集合运算计算机实现算法的 相关研究文献不多，而传统的对集合操作主要是利用字符串匹配、查询等来实现 5，效率低，而且对空间要求很高，大大制约了集合理论向实际应用的转化，如何快速有效的利用计算机对集合运算进行处理一直是学术界关心的课题。 本章首先介绍了集合的基本概念，然后分析比较二进制与集合之间的内在联系，最后，通过二进制位运算实现了集合的各种基本运算，并且对相关算法给出了 C 语言源代码。 合的概念 合基本定义 定义 合是一些确定的对象的全体，对象称为元素，若 a 是集合 A 的元素，则记为 a A。 定义 含 任何元素的集合叫做空集，记做 或。 定义 A,B 为集合，若任意 一定有 ，则称 A 是 B 的子集，也称 包含，或 B 包含 A，记为 。 定义 A,B 为集合，若 且 ，则称 A 与 B 相等，记为 A=B。 定义 ，但是 ，则称 A 是 B 的真子集，记为 。 定义 集：由 A 的所有子集组成的集合称为 A 的幂集，记为 P（ A）或 定义 数：集合 A 中元素的个数称为 A 的基数，记为 |A|。 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 6 合的基本运算 定义 集：集合 A 与 B 的交集 A B=x|x A 并且 x B。 定义 集：集合 A 与 B 的并集 A B= x|x A 或 x B。 定义 , B 是分离的，若 A B= 定义 对补：集合 A 对 B 的相对补 x|x A 并且 x B 。 定义 集：集合 A 的补集为全集 E 与 A 的差，记为 A。 定义 称差：集合 A 与 B 的对称差 A B=（ （ 合与二进制的关系 二进制自问世以来，在计算机的研究和应用领域起着重要的作用，它的值域只有“ 0”，“ 1”两个值，但是通过对这两个值的有效组合和简单运算，却能表达出客观真实世界的千变万化，下面通过分析二进制和集合之间强大的内在联系，说明二进制在集合运算中的巨大作用。 若集合 A 具有 n 个元素，则 A 的所有 子集 (幂集 )的个数 | P(A)|= 例如， A a,b,c,则 A 的幂集为 ,a,b,a,b,c,a,c,b,c,a,b,c， A 的幂集的基数为 32 8 。 长度为 n 的二进制位所能表达的数据个数为 例如长度为 3 的二进制位，所能生成的数据为 000,001,010,011,100,101,110,111，共 32 8 个数据。 通过比较发现，长度为 n 的二进制位所能表达的数据个数和具有相同元素个数的集合的所有子集 (幂集 )的数目相同，由此可以猜想二进制和集合之间应该具有某些联系 ,现在做以下规定： 规定 于集合 I=0,1,2, ,n,，规定个 进制 数 P=。 与之对应，其中二进制数的第 0 位 对 应集合的第 0 个元素 0 ，第 1 位 对 应第 1 个元素 1 ，第 k 个元素 。 例 定一个 3 位的二进制数，用此二进制数的第 0 位代表上面所提到的集合 A的 a 元素，第 1 位代表集合 A 的 b 元素，第 2 位代表集合 A 的 c 元素，然后比较集合 下表所示： 序号 子集 二进制数 0 000 表 西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 7 1 a 001 2 b 010 3 a,b 011 4 c 100 5 a,c 101 6 b,c 110 7 a,b,c 111 通过比较发现，如果我们按照上表中的对应关系对子集进行编号，则集合第 i 个子集和二进制所产生的第 i 个数据之间存在着非常微妙的对照关系：如果在子集中某个元素存在，则此子集对应的二进制 数中该元素所对应的二进制位为 1，否则为 0。例如 ,子集 a,b,因为 a 对应二进制第 0 位， b 对应二进制第 1 位， c 对应二进制的第三位，而 以，其对应的二进制数为 011。 定义 集的下标：集合 A 的子集所对应的二进制数的十进制数值称为此子集的下标。 有了集合与二进制之间的这种内在联系，以后在对集合操作时，我们没有必要对子集中的实际元素进行处理，只要知道子集的下标，就可以很容易的利用位运算来实现对集合进行各种操作的目的。 于二进制的集合运算 二进制求集合的幂集 已知集合 A，求 A 的幂集。 由于集合子集中的元素与子集下标中二进制位的“ 1”相对应，因此求子集中元素的运算可以转化为寻找子集下标二进制位中“ 1”所在位置的运算，此运算可以利用移位操作来实现。例如，求 101所对应的 们可以通过 3次移位，每次先将当前的数值与数值 1相与，如果结果等于 1，则本次第 0位上的值为 1，否则为 0，由移位的次数可以知道当前第 0位的 1在原数据中的位置，从而找到对应的实际元素。运算如下： 第 0次与： 101&001 1 ， 位，而且本次 相与的结果为 1，所以 101右移一位，现在的数值为 010 第 1次与： 010&001=0， 位，而且本次相与的结果为 0，所广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 8 以 010右移一位，现在的数值为 001 第 1次与： 001&001=1， 位，而且本次相与的结果为 1，所以 001右移一位，现在的数值为 000。 计算完毕。求出 101 对应的 a,c。 求子集元素的 /* 中子集下标 b 所对应的子集中的所有元素 */ ,b ) f,j 0; /*; n); b0) b&1)0 ) if(f=0) f=1; %c,Aj); ,%c ,Aj); b=b1; j=j+1; ); 若求 只要从子集下标 0 次求各对应子集的元素即可，本算法可用一个循环完成，代码如下： ,n) /n= 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 9 i; i=0; i|i u; 糙集的下近似集 由粗糙集的 下 近似集公式 R X= Y U/R|Y X可知， R X 是 R 的所有等价类中包含于 X 的等价类的并。集合的包含关系可由其子集 下标 的或运算判断得到，即 AB 当且仅当 A B=B。求下近似集的具体算法如下： ， ， M) 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 23 /返回值为下近似集对应的 子集 下标 i; u; ; ; i=0;=t; ; 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 24 合的基数 在计算 近似精确度 R（ X）以及其它很多运算时，需要计算集合的基数，即元素个数。由集合对应的子集下标可以非常容易的计算其基数，即子集下标二进制表示中“ 1”的个数，该值可以利用移位运算来得 到。具体算法如下： ; ) )0) /当前值的最后一位为 1 ; 1; 关于粗糙集中其它运算的算法，可仿照上述算法给出，限于篇幅不再叙述。 糙集运算举例 例 例 X=按照前面的算法计算可得 : X=(10100111001)2=1337 R X=， X， M)=1467 R X=， X， M)=312 )=1467155 )=204780 R（ X） =|84 。 由此 ,可以看出，基于二进制的粗糙集基本运算方便，快捷。 章小结 本章在第二章研究的基础上，通过讨论 二进制与粗糙集之间的内在联系，提出了基于二进制的粗糙集运算理论。借助位运算操作，给出了几种基于二进制的粗糙集基本广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 25 运算算法，其 算法的时间复杂度主要与等价类的个数有关。由于算法中没有了等价类元素的比较且主要是位运算，所以，与传统的算法相比，其运算速度更快，效率更高。 本章提出的思想，也可以用于计算决策属性的支持度、依赖度等，为属性约简以及扩展粗糙集的应用提供了理论基础。该算 法思想可以应用在数据挖掘的分类、决策分析中。 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 26 第五章 基于位运算的属性核约简 粗糙集理论的核心内容之一就是知识约简，国内外很多专家对之进行了研究 43众所周知，求粗糙集的最小知识约简是一个 识约简方面的算法已经很多，如基于属性重要性、基于差别矩阵等，其中，很多算法都需要预先求出知识表中的属性核作为计算的初始条件，但是，到目前为止，还没有一个公认的、高效的求核算法。 本章是二进制位运算在粗糙集中的进一步应用，通过将二进制位运算运用到知识表属性的核约简中，提高求核效率。 本章二 进制与粗糙集的关系同第四章所述。 法基本思想 本算法主要是通过属性去除后，检测分类数目的变化来确定属性是否为必要的，下面给出算法所用到的一个定理。 定理 为某一等价关系簇，如果 ，且 r 为 R 必要的，则 U/ -r)所产生的分类数小于 U/ )产生的分类数。 证明：对 U/R 的任意等价类 x)，若 y x)，则 有 f(x,a)=f(y,a)，而R-r R，所以 y x-r), x) x-r) |U/R| |U/(R-r)| 又因为 r 为 R 必要的 |U/R| |U/(R-r)| 故 |U/R|0) /第 i 位元素还没有归类 (); /将当前等价类查找成功标志置 0 (*将第 i 位元素归入 */ (*表将要检测的下一元素对应位 */ 出：核属性集 知识库的属性值二进制化； 据二进制化的元素属性值，求 属性 (R)； U/) 的每个分类中选取一个元素形成新的集合 i=1 R| 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应用研究 35 /|R|为知识库中属性的个数 将 ； 遍历 是否有相同值的出现，有，则将 核算法复杂度分析 本算法中， 解 U/ )，需要遍历知识库中所有 元素，值相同的元素划分到同一类 ，这部分的时间复杂度与所使用的分类存储方式有关，可 以使用动态链表，或者静态链表，如果使用方法得当，可以将时间复杂度控制在 O(|U|)；对于 产生的分类数目有关。所以本算法的总的时间复杂度可以控制在 O(|U|*|R|)，而传统的求核算法中的时间复杂度为 O(|R|U|2)。 束语 知识约简是粗糙集理论中的核心内容之一，而求核运算又是知识约简的基础，求核算法的效率对于知识约简至关重要。本章提出了一个粗糙集分类定理，在这个定理基础上， 通过将属性值二进制化 ，给出了 基于二进制的知识表求核算法，充分利用了二进制数据处理 方便，变换灵活的优势。本 算法中主要运用的是数值的比较，与传统算法 61,62相比，其运算速度更快，效率更高。 广西大学硕士学位论文 二进制在集合运算与数据挖掘中的应