（计算机应用技术专业论文）基于粗糙集的属性约简算法研究(2).pdf

西南交通大学硕士研究生学位论文第1 页 摘要 粗糙集是数据挖掘的方法之一，它是处理不精确、不一致、不完整信息 的有效工具。属性约简是粗糙集理论中的一个研究重点。属性约简要求在保 持信息系统的分类和决策能力不变的条件下，删除不相关或不重要的属性， 形成精简的规则库以帮助人们做出正确且简洁的决策。目前寻找一个信息系 统的最小约简具有指数级复杂度，因此，寻求快速高效的属性约简算法仍然 是粗糙集理论的主要研究内容，在信息系统分析与数据挖掘等领域具有重要 的应用意义。 本文深入系统地研究了基于粗糙集的属性约简算法，提出了一种改进的 基于属性频率的约简算法和一种新的基于简化差别矩阵的属性约简算法。 研究了h o r a f a 和h o r a f a a 算法，针对胡或所提h o r a f a a 算法存在 的不足，提出了下列改进：采用简化差别矩阵来设计算法，大大减少了生成 矩阵的时间和矩阵元素占用的存储空间；设计了一个权值公式来度量属性的 分辨能力，当有多个属性同时具有最大的加权频率时，选择权值最大的一个 属性并入约简集，以保证获得的规则最简，覆盖面最大。证明了该改进算法 是完备的，能得到最小约简且适用于相容与不相容信息系统。实验结果表明 该算法优于h o r a f a a 算法，是有效的。 在现有基于差别矩阵的属性约简算法中，通常要先求出差别矩阵，由此 设计出的算法，其时间和空间复杂度较高。为了降低该类算法的复杂度，设 计了一个求简化差别矩阵中条件属性频率的函数，并给出了该函数的快速计 算算法，该算法不用求出差别矩阵，就能直接计算出属性的频率值，在此基 础上，以属性频率为启发式信息，设计了属性约简算法。证明了该算法是完 备算法，能得到最小约简且适用于相容与不相容信息系统。实验结果表明该 算法约简速度快，空间耗费小，适用于大型数据集的属性约简，明显优于 h o r a f a a 算法。 关键词：粗糙集；属性约简；决策表；差别矩阵 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t r o u g h s e ti so n eo ft h em e t h o d so fd a t am i n i n g i ti sa ne f f e c t i v et o o lt od e a l w i t hi n a c c u r a t e ，i n c o n s i s t e n t ，i n c o m p l e t ei n f o r m a t i o n a t t r i b u t er e d u c t i o ni sa r e s e a r c hf o c u si nr o u g hs e tt h e o r y u n d e rt h ec o n d i t i o no fm a i n t a i n i n gt h e c l a s s i f i c a t i o na n dd e c i s i o nm a k i n ga b i l i t yo fi n f o r m a t i o ns y s t e m s c o n s t a n t ， d e l e t i n gi r r e l e v a n to ru n i m p o r t a n ta t t r i b u t e sa n df o r m i n gt i d yr u l eb a s et oh e l p p e o p l em a k i n gt h er i g h ta n dc o n c i s ed e c i s i o n s c u r r e n t l yl o o k i n gf o rt h e m i n i m u mr e d u c t i o no fa ni n f o r m a t i o ns y s t e mi se x p o n e n t i a lc o m p l e x i t y ，s oi ti s s t i l lt h em a i nr e s e a r c ht os e a r c hf o rf a s ta n de f f i c i e n ta l g o r i t h m sf o ra t t r i b u t e r e d u c t i o no fr o u g hs e tt h e o r y i th a si m p o r t a n ta p p l i c a t i o ns i g n i f i c a n c ei nt h e i n f o r m a t i o ns y s t e ma n a l y s i sa n dd a t am i n i n g t h i sp a p e rs y s t e m a t i c a l l ys t u d i e dt h ea t t r i b u t er e d u c t i o na l g o r i t h m sb a s e do n r o u g hs e ta n dp r o p o s e da ni m p r o v e dr e d u c t i o na l g o r i t h mb a s e do na t t r i b u t e f r e q u e n c y a n dan e wa t t r i b u t er e d u c t i o n a l g o r i t h m b a s e do n s i m p l i f i e d d i s c e r n i b i l i t ym a t r i x t h i sp a p e rs t u d i e dh o r a f aa n dh o r a f a aa l g o r i t h ma n dm a d et h e f o l l o w i n gi m p r o v e m e n t sa sf o rt h ed i s a d v a n t a g e so fh o r a f a aa l g o r i t h m p r o p o s e db yh u y u i td e s i g n e da l g o r i t h mw i t hs i m p l i f i e dd i s c e r n i b i l i t ym a t r i x ， w h i c hg r e a t l yr e d u c e dt h et i m ef o rg e n e r a t i n gt h em a t r i xa n dt h es t o r a g es p a c e w h i c hm a t r i xe l e m e n t so c c u p i e d ；i td e s i g n e daw e i g h t i n gf o r m u l at om e a s u r et h e a t t r i b u t ed i s c e r n i b i l i t y ，w h e nt h e r ea r em o r et h a no n ea t t r i b u t eh a v i n gt h eg r e a t e s t f r e q u e n c ya to n et i m e ，c h o o s i n gt h ea t t r i b u t ew h i c h h a st h el a r g e s tw e i g h t e dv a l u e i n t or e d u c t i o ns e t st oe n s u r eo b t a i n i n gt h es i m p l e s ta n dl a r g e s tc o v e r a g eo fr u l e s i tp r o v e dt h a tt h ei m p r o v e da l g o r i t h mi sc o m p l e t e ，a n dc a no b t a i nt h em i n i m u m r e d u c t i o nf o r c o m p a t i b l e a n d i n c o m p a t i b l e i n f o r m a t i o n s y s t e m s t h e e x p e r i m e n t a lr e s u l t s s h o wt h a tt h e a l g o r i t h m s i sb e t t e rt h a nh o r a f a a a l g o r i t h ma n de f f e c t i v e i nt h ee x i s t i n ga t t r i b u t er e d u c t i o na l g o r i t h m sb a s e do nd i s c e r n i b i l i t ym a t r i x ， t h ed i s c e r n i b i l i t ym a t r i xi su s u a l l yo b t a i n e df i r s t ，t h e s ea l g o r i t h m sh a v eh i g h e r t i m ea n ds p a c ec o m p l e x i t y i no r d e rt or e d u c et h ec o m p l e x i t yo fs u c ha l g o r i t h m s ， 一 西南交通大学硕士研究生学位论文第1 if 页 。一一 ： t h i s p a p e rd e s i g n e d af u n c t i o nt oc a l c u l a t e t h e a t t r i b u t e f r e q u e n c yi nt h e s i m p l i f i e dd i s c e m i b i l i t ym a t r i x ，a n dg a v et h er a p i dc a l c u l a t i o na l g o r i t h mo ft h e f u n c t i o nw h i c hd o e sn o tc a l c u l a t et h e d i s c e r n i b i l i t ym a t r i xa n dc a nd i r e c t l y c a l c u l a t et h ef r e q u e n c yv a l u eo fa t t r i b u t e s o nt h i sb a s i s ，a na t t r i b u t er e d u c t i o n a l g o r i t h mw i t hh e u r i s t i ci n f o r m a t i o no fa t t r i b u t e f r e q u e n c yw a sd e s i g n e d i t p r o v e dt h a tt h ea l g o r i t h mi sc o m p l e t e ，a n dc a no b t a i nt h em i n i m u mr e d u c t i o nf o r c o m p a t i b l eo ri n c o m p a t i b l ei n f o r m a t i o ns y s t e m s t h ee x p e r i m e n t a lr e s u l t ss h o w t h a tt h ea l g o r i t h mh a sr a p i dr e d u c t i o ns p e e da n ds m a l ls p a c ec o s t ，i ti sa p p l i c a b l e t ol a r g ed a t as e t so fa t t r i b u t er e d u c t i o n ，a n di s o b v i o u s l yb e t t e rt h a nh o r a f a a a l g o r i t h m k e yw o r d s ：r o u g hs e t ；a t t r i b u t er e d u c t i o n ；d e c i s i o nt a b l e ；d i s c e m i b i l i t ym a t r i x 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位 论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密矿使用本授权书。 ( 请在以上方框内打“”) 蔬牟? 多畿 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作 所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 针对胡或h o r a f a a 算法存在的不足提出了两点改进：通过实验分 析采用简化差别矩阵来改进h o r a f a a 算法中的h u 差别矩阵；设计了一 个权值公式来度量属性的分辨能力，当有多个属性同时具有最大的加权频率 时，选择权值最大的一个属性并入约简集。进而提出了一种改进的基于属性 频率的约简算法。证明了该算法是完备的，能得到最小约简，适用于相容与 不相容信息系统。最后通过实验验证了该改进算法优于h o r a f a a 算法， 是有效的。 2 设计了一个求简化差别矩阵中条件属性频率的函数，给出了该函数的 快速计算算法，该算法不用计算差别矩阵元素。在此基础上提出了一种新的 基于简化差别矩阵的属性约简算法。证明了该算法是完备算法，能得到最小 约简且适用于相容与不相容信息系统。最后通过实验验证了该算法适用于大 数据集，明显优于h o r a f a a 算法，是有效的。 a - 一p 邓 d 一7 6 ，7 l 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 论文的研究目的与意义 近年来，随着计算机、网络和通信等信息技术的高速发展，商务贸易的 电子化，政府和企事业事务自动化的迅速普及，产生了大规模的数据；同时 日益增长的科学计算和大规模的工业生产过程也提供了海量数据。数据丰富、 信息贫乏是当今数字化社会面临的一个巨大挑战。在海量数据背后隐藏着许 多重要的信息，因此人们希望对其进行更高层次的分析，以便能更好地利用 这些数据。目前的数据库系统和数据库管理系统为海量数据的存储和管理提 供了技术保证，但是无法发现数据中存在的关系和规则，缺乏挖掘数据背后 隐藏的知识的手段和方法。知识发现( k n o w l e d g ed i s c o v e r y ，k d d ) 便应运而 生并得到迅速发展。由于蕴涵知识的信息大多存储于数据库中，数据库知识 发现即数据挖掘( d a t am i n i n g ，d m ) 成为当前知识发现的主要研究课题。 粗糙集( r o u g hs e t ) 是数据挖掘的方法之一，它是处理不精确、不一致、 不完整信息的有效工具。属性约简( a t t r i b u t er e d u c t i o n ) 是粗糙集理论中的一 个研究重点。一般说来，数据库中的数据属性并不是同等重要的，而且还存 在冗余，这不利于做出正确而简洁的决策。属性约简要求在保持数据库的分 类和决策能力不变的条件下，删除不相关或不重要的属性。人们总期望找到 最少约简，但这已被证明是个n p 完全问题【l 】。由于在粗糙集的属性约简中约 简属性集必须满足2 个条件，即保持原分类质量不变和属性集中不含冗余属 性，故粗糙集的属性约简是一个多约束、多目标的搜索优化过程。尽管粗糙 集理论与其它处理不确定的理论相比具有不可替代的优越性，但是仍然存在 某些片面性与不足之处。例如：在研究属性约简的问题时，考虑数据的规模 是比较少的情形：对于海量数据的情形，时间和空间复杂度较大。所以寻找 快速、有效的约简算法是研究粗糙集理论的一个有意义的课题。 西南交通大学硕士研究生学位论文第2 页 1 2 国内外研究现状 1 2 1 粗糙集理论研究现状 粗糙集理论是波兰学者z p a w l a k 于1 9 8 2 年提出的【甜。由于最初关于粗糙 集理论的研究大部分是用波兰语发表的，因此当时没有引起国际计算机学界 和数学界的重视，研究区域也局限在东欧一些国家。直到1 9 9 0 年前后，由于 该理论在数据的决策与分析，模式识别，机器学习与知识发现等方面的成功 应用，才逐渐引起了世界各国学者的广泛关注。1 9 9 1 年z p a w l a k 的专著粗 糙集一关于数据推理的理论1 3 1 系统全面的阐述了粗糙集理论，奠定了严密 的数学基础。1 9 9 2 年r s l o w i n s k i 主编的关于“粗糙集应用及其相关方法比 较研究”的论文集较好地总结了这一时期该理论的研究成果，推动了国际上 对粗糙集理论与应用的深入研究。1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗 糙集研讨会，这次会议着重讨论了集合近似的基本思想及其应用。自此，每 年都召开以粗糙集为主题的国际会议。1 9 9 4 年，国际粗糙集研究学会成立。 1 9 9 6 年在日本东京召开的第五届国际粗糙集研讨会，极大的推动了亚洲地区 对粗糙集理论与应用的研究。1 9 9 8 年在波兰召开了第一届以“粗糙集和计算 的当前趋势 为主题的学术会议。2 0 0 4 年，国际粗糙集协会出版发行第一本 粗糙集国际期刊 ( a d v a n c e si nr o u g hs e t ) ) ，为推动粗糙集在全世界的发展作 出了巨大贡献。 粗糙集研究在我国虽然起步晚，但发展较快。1 9 9 6 年王珏、苗夺谦等在 模式识别与人工智能发表了关于粗糙集理论与应用的论述，开始了国内 粗糙集理论的研究和应用；1 9 9 8 年曾黄麟编写的粗集理论与应用是国内 第一本关于粗糙集理论的专著。王国胤、刘清、张文修、史开泉、苗夺谦、 梁吉业和胡寿松等先后出版了关于粗糙集理论的专著。2 0 0 1 年在重庆邮电学 院举办了首届中国粗糙集与软计算学术研讨会，以后每年都召开一次，促进 了粗糙集理论在国内的发展。 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。它不需要 关于数据任何先验的或附加的信息，仅仅以数据的分类能力为基础，通过知 识约简，导出问题的决策或分类规则。粗糙集理论的基本框架可归纳为：以 不可分辨关系划分论域的知识，形成知识表达系统，引入上、下近似逼近所 西南交通大学硕士研究生学位论文 。 第3 页 描述对象，并考察属性的重要性，从而删除冗余属性，简化知识表达空间， 挖掘规则。粗糙集理论与其它处理不确定性方法的理论研究，主要集中在它 与概率统计、模糊数学【4 】、证据理论1 5 j 和信息论的相互渗透与补充方面。 在面对有噪音，有缺失值的数据以及海量数据时，p a w l a k 粗糙集模型的 使用效果不够理想，因此人们提出了多种粗糙集扩展模型，其中较主要的是 z i a r k oa 提出的可变精度模型【s 1 ，相似模型1 7 1 等。随着研究工作的不断深入， 粗糙集理论已广泛应用于知识发现、机器学习、决策支持、模式识别、专家 系统、归纳推理等领域。 1 2 2 属性约简算法研究现状 基于决策表的属性约简是粗糙集理论中的核一t l , 内容之一，也是粗糙集理 论研究较多的分支之一。国内外许多学者在粗糙集属性约简算法上作了大量 的研究，目前基于粗糙集的常用属性约简算法有： ( 1 ) 差别矩阵法 差别矩阵法【s 1 是a s k o w r o n 于1 9 9 2 年提出的，该方法利用差别矩阵导出差 别函数，然后求解其析取范式。该范式中的每一个析取项即为系统的一个约 简，这种算法直观，利于理解，能够计算出决策表的核属性及所有属性约简， 但由于差别矩阵中会出现大量的重复元素，且需要完成从合取式到析取式之 间的转化，降低了算法的效率【，】。 针对以上缺陷文献【州对该方法进行改进，主要是不用生成差别矩阵。它 直接从信息系统中提取关于属性分辨信息，并构造成分辨合取范式，同时做 逻辑公式的等价变换直接得到最小析取范式。因运算过程中不用生成差别矩 阵的中间环节，节省了空间和时间，提高了约简的效率。还有一些不用生成 差别矩阵 1 1 , 1 2 1 ，用等价代换求得差别矩阵核与属性重要度的方法。文献 1 3 1 提出 了拓广差别矩阵方法，按决策划分论域，不同类的对象分别构造差别矩阵， 空间复杂度有明显降低。 ( 2 ) 代数观与启发式属性约简算法 z p a w l a k 提出属性约简的代数观定义，约简前后只需保证正域元素不变， 无需考虑边界域元素。目前代数约简的算法一般采用启发式思想，可分为两 种。一种是先计算信息系统的核属性，再在核的基础上依次添加最重要的属 性求得约简；另一种不求核，在空集的基础上依次添加最重要的属性直到得 西南交通大学硕士研究生学位论文第4 页 到约简。属性重要度的度量主要有：属性依赖度 t 4 1 5 】、属性频度函豺托圳，等。 此类算法的时间性能较好，但在某些情况下求取的属性约简是不完备的，不 一定能得到最小约简。 ( 3 ) 信息熵的属性约简 基于信息熵的属性约简 2 2 习也分两种：先求信息熵的核再用信息熵重要 度启发式构造约简；或根据信息熵属性重要度进行排序，从初始条件属性集 开始，逐步删除不影响信息表条件熵的属性来达到约简的目的。 ( 4 ) 其它属性约简算法 除了以上方法外，学者们通过几种观点的综合或引入新的知识概念产生 了许多不同的约简方法，文献【拍】提出归并的约简分析方法，文献f 2 7 】通过与遗 传算法相结合，并采用加权平均的属性重要度和知识量作为启发式信息指导 约简，提出了一种改进的基于核子集的约简算法。文献 2 8 j 综合信息观与代数 观的优缺点提出了两种观点的综合方法。文献1 2 9 分析两种属性重要度定义的 不完备性，提出一种加权平均属性重要度定义来构造相关算法。文献m ，提出 平均决策强度和决策熵的概念建立两种新的知识约简定义，使之对不相容决 策表约简的结果也是一致的。此外还有概念格c ，l 3 2 、滤除性质t ，创，、模糊粗糙 f 3 ”7 】、遗传 3 8 4 1 、蚁群【4 2 1 、集值【4 3 】等。 对于不协调信息系统，文献给出了不协调信息系统属性约简的两种定 义，即分布约简与分配约简，讨论了它们的等价形式。文献【4 5 】提出一种不协 调信息系统最大分布约简的属性约简概念，它弱于分布约简，克服了对信息 系统过于苛刻的要求。同时，它又克服了分配约简可能产生与原系统不相容 命题规则的缺陷。文献给出两种变精度粗糙集模型上的属性约简概念，即 上、下分布约简。讨论各种约简之间的关系。证明了分布协调集既是上分 布协调集，也是下分布协调集。同时给出了最大分布约简与下分布约简、 分配约简与上分布约简等价的条件。文献m 】用严凸函数定义决策表的属性 约简，证明用严凸函数定义的属性约简同分布约简是等价的，并给出严凸函 数定义的相对约简的一个判定定理。 属性约简的目标就是求得最优约简，但目前约简算法寻找一个信息系统 的最小约简具有指数级复杂度。对启发式算法的改进只是对属性重要度的度 量方式的修改，并不能改变贪心算法易落入局部最优的趋向；基于遗传算法 的属性约简虽然做到了并行搜索，同时缩小了搜索空间，但其收敛性还是个 待研究的问题，且该算法也并不能保证搜索方向不落入局部最优。因此，寻 西南交通大学硕士研究生学位论文第5 页 求快速高效的属性约简算法仍然是粗糙集理论的主要研究内容。 1 3 论文的组织 本论文的组织结构如下： 第1 章绪论 首先分析本文的研究目的及意义，然后介绍国内外研究现状及论文的组 织安排。 第2 章常见的粗糙集属性约简算法 简要介绍粗糙集属性约简的相关概念及常见约简算法。 第3 章基于属性频率的约简算法 本章首先研究分析h o r a f a 算法和h o r a f a a 算法，然后针对胡或 h o r a f a a 算法存在的不足提出一种改进的基于属性频率的约简算法，最后 通过实验仿真证明该算法的有效性。 第4 章基于简化差别矩阵的属性约简算法 为了降低生成差别矩阵的时间和空间复杂度，本章提出一种新的基于简 化差别矩阵的属性约简算法，并通过实验仿真证明该算法的有效性。 总结 总结本文的主要研究内容，并指出今后要做的研究工作。 西南交通大学硕士研究生学位论文第6 页 第2 章常见的粗糙集属性约简算法 粗糙集方法己被成功的应用于分类问题和决策分析。对于粗糙集的应用 而言，设计有效的算法是非常重要的。在粗糙集理论中，属性约简是粗糙集 理论的核心内容之一。所谓属性约简，就是在保持知识库分类能力不变的情 况下，删除其中不相关或不重要的知识。换句话说，约简是满足能区别由整 个属性集区别的，所有对象的属性极小子集，使原有的系统得到简化。 属性约简算法总结起来主要有两大类研究方法：由j a 等1 4 8 1 提出了基于 属性重要性程度逐步扩展的算法，此算法几乎是从空集开始搜索，计算量较 大。目前主要流行p a w l a k z 等人【4 9 】提出的算法，从求核开始，然后逐步扩展 求出一个相对属性约简，即求解约简时一般都使用核作为计算约简的出发点， 然后按照启发式信息“属性重要性的大小”把属性逐个加入到被选择的属性 子集中，直到该集合是一个约简为止。根据属性重要性定义的不同，可分为 基于依赖度，基于信息熵，基于属性频率的相对属性约简方法。国内外很多 学者投入到这方面的研究，并提出了大量有效的约简算法属性。 2 1 粗糙集属性约简相关概念 本节基本概念参考文献 5 0 。 定义2 1 ：称四元组s = ( 【，a ，v ，f ) 为信息系统，其中u 为所考虑对象的 非空有限集合，称为论域；a 为属性的非空有限集合；v = ug o ，g o 为属性 口一 a 的值域；fu x a 专矿是一个信息函数，v x u ，a a ，f ( x ，a ) v o ，对于给 定对象x ，f ( x ，口) 赋予对象x 在属性a 下的属性值。信息系统又可简记为 s = ( u ，a ) 。 信息系统可以用数据表格来表示，表格的行对应论域中的对象，列对应 描述对象的属性，一个对象的全部信息由表中一行属性的值来反映。 定义2 2 ：给定信息系统s = ( u ，a ，v ，厂) ，若a = cud ，d 0 ，c nd = g ， c 称为条件属性集，d 称为决策属性集，则称信息系统为决策表( d e c i s i o n t a b l e ) 。 西南交通大学硕士研究生学位论文第7 页 般来说，信息系统分为有决策与无决策两种类型。对于无决策的信息 系统我们简称为信息表，带决策属性的信息系统称为决策信息系统，即决策 表。 定义2 3 ：在信息系统s 中，对于每个属性子集b a ，可以定义一个不 可区分关系i n d ( b ) ： n d ( b ) = ( x ，y ) u u ：v b b ，b ( x ) = 6 ( y ) ) 显然i n d ( b ) 是一个等价关系，对象x 在属性集b 上的等价类 工 肋定 义为 叫肋( 口) = d ：y u ，y l n d ( b ) x 为简便起见，在不产生混淆的情况下用b 代替i n d ( b ) 。 定义2 4 ：假设给定知识库l o ( u ，r ) ，对于每个子集x 【，和一个等价关 系r 1 n d ( k ) ，定义两个子集： 足( x ) = u y 【厂rl 】，x ) ( 2 - 1 ) r 一( x ) = u r u 尺i 】，n x o )( 2 - 2 ) 分别称它们为x 的r 下近似集和上近似集。 下近似、上近似也可用下面的等式表达： 尺( x ) = x ui 【x 】r x ) ( 2 - 3 ) r 一( z ) = x ui x 】尺nx o )( 2 - 4 ) 集合锄尺( x ) = r 一( x ) 一足( x ) 称为x 的r 边界域；n e g 足( x ) = u - r 一( x ) 称 为x 的r 负域。足( x ) 是由那些根据知识r 判断肯定属于x 的u 中元素组成的集 合；r 一( x ) 是由那些根据知识r $ 1 j 断可能属于x 的u 中元素组成的集合； 6 ，l 。( x ) 是由那些根据知识r 既不能判断肯定属于x 又不能判断肯定属于 x ( 甚p u x ) 的u 中元素的集合；n e g 尺( x ) 是由那些根据知识r 判断肯定不属于 x 的u 中元素组成的集合。 定义2 5 t 5 1 】：在决策表s = ( u ，c ud ，v ，f ) 中，设u d = d 。，d 2 ，d k ) 表示由 决策属性集d 对论域u 的划分，u c = q ，g ，巴) 表示由条件属性集c 对论域 u 的划分，其中c ( 1 ，2 ，m ) 称为基本块，称p o s c ( d ) = ue ( 口) 为c 关于d 凸【，i d 的正区域。 西南交通大学硕士研究生学位论文第8 页 定义2 6 1 s * ：在决策表s = ( u ，c ud ，矿，) 中，对v a p c ，若 p o s p ( d ) = p o s p _ ( a ( d ) ，则称a 为p r o 相对于d 是可省的( 不必要的) ；否则称a 为p 中相对于d 是不可省的( 必要的) 。若v a p 相对于d 都是必要的，则称p 相对于d 是独立的。 定义2 7 【5 2 】：在决策表s = ( u ，c ud ，v ，f ) 中，v a c ，若p o s c _ t ) ( d ) p o s c ( d ) ，则称属性a 在c 中是不可缺少的；c 的所有不可缺少的属性的集合 称为c 的核，记为c o r e ( c ) 。 定义2 8 t 5 i 】：在决策表s = ( u ，cud ，v ，f ) 中，若v p c ， p o s p ( d ) = p o s c ( d ) 且p 相对于d 是独立的，则称p 是c 相对于d 的属性约简。 2 2 基于差别矩阵的所有属性约简算法 差别矩阵是s k o w r o na 于1 9 9 2 年提出的【8 】，该方法的提出，开启了粗糙 集理论基于差别矩阵进行属性约简的先河。 该方法首先构造差别矩阵，得到差别函数a ，然后利用吸收率对函数 a 进行简化，完成从合取范式到最小析取范式的转化，析取范式的每项即 为决策表的一个属性约简。该算法的具体步骤如下： 输入：决策表s = ，a ，v ，厂) ，其中u 是论域，a = c u d ，c 为条件属性 集，d 为决策属性集。 输出：s 的属性约简。 s t e p l 根据决策表构造差别矩阵m ； s t e p 2 根据已构造的差别矩阵m 构造差别函数a ； s t e p 3 运用吸收率对差别函数a 进行化简； s t e p 4函数a 的极小析取范式中每项则为c 的d 约简。 该算法简单、直观，可以求出决策表的所有属性约简，能直接提取出规 则，已成为小规模数据库进行属性约简的首选方法。但该方法的缺点是计算 的时间复杂度高，为仪2 m i 木木i u 卜l g l u ) 嘲( 其中a 表示差别函数中矩阵元 素的个数) ，对于较大规模的数据集难以适用，因此，只能处理较小的数据集。 西南交通大学硕士研究生学位论文第9 页 2 3 基于重要度的属性约简算法 基于属性重要性的约简算法0 4 舢】是胡小华于1 9 9 5 年提出的。目前，己有 学者提出了基于属性重要性的改进算法 5 3 1 。首先阐述关于属性依赖度和重要 性的定义，具体如下： 设属性集合d 对b 的依赖度定义为：r ( b ，d ) = i p o s s ( d ) l u i ，其中 p o s s ( d ) 为根据属性集合b 划分的正区域。若d 为决策属性集，贝j j r ( b ，d ) 表示 用b 对u 划分后，任一x u 能被正确划分到决策类的概率；同时刻画了条件 属性b 描述决策属性d 的能力。 定义2 9 t s o j ：基于条件属性集b 与决策属性集d 之间的依赖度，定义属 性的重要性如下： s i g ( a ，b ，d ) = r ( b + a ) ，d ) 一r ( b ，d )( 2 - 5 ) s i g ( a ，b ，d ) 表示当目前选择的属性集为b 时，属性a 的重要性。属性重要度越 大，属性对决策划分的影响越大，相对于决策属性来说，也就越重要。 基于属性重要性算法具体步骤如下： 输入：决策表s = ( u ，a ，v ，) ，其中a = cud ，且c ，d 分别为条件属性 集和决策属性集。 输出：决策表s 的一个属性约简r 。 s t e p l令初始约简属性集r = c o r e ( c ，d ) ，b = c r ； s t e p 2 计算r ( c ，d ) ，作为停止条件： s t e p 3若r 满足r ( r ，d ) = r ( c ，d ) ，则算法终止，输出r 即为一个约简。 否则，转s t e p 4 ； s t e p 4 按式( 2 5 ) 分别计算b 中每个属性的重要度，选择使属性重要度取 得最大值的属性a ；若存在多个属性其属性重要度取相同的最大值，则选择 一个与r 组合数最小的属性a ； s t e p 5r = r o a ) ，b = b - a ) ，转s t e p 3 继续执行； 这种算法得到的是代数观下的属性约简，但由于此算法要进行属性依赖 度、重要度的计算，算法的时间复杂度依然不理想，在处理大数据集时速度 较慢。 西南交通大学硕士研究生学位论文第1 0 页 2 4 基于信息熵的属性约简算法 信息是用来消除随机不确定性的度量，信息量的大小由所消除的不确定 性的大小来计量。条件属性与决策属性之间的互信息和条件熵便反映了信息 量的大小。在决策表属性约简中，条件属性相对决策属性的重要度可以通过 添加某个条件属性后所引起的信息熵的变化大小来衡量。 下面给出信息论中的相关概念： 、 设u 为论域，p 、q 是u 上的两个等价关系，认为u 上的任意等价关系 ( 即对论域的划分) 可以看作是定义在u 上的子集组成的一个随机变量，其概 率分布通过如下的方法来确定。 定义2 1 0e 5 4 l ：设c 、d 在u 上导出的划分分别为u c = 五，五，以) ， u d = 踊，k ，匕) ，则c 、d 在u 上的分类子集的概率分布分别为： 姒) = 斜户l ，2 ，棚洲驴斜小1 2 ，棚 定义2 1 1 【】：知识( 属性集合) p 的熵h ( p ) 为： h ( p ) = 一p ( x , ) l o g p ( x , ) ( 2 6 ) 信息熵h ( p ) 是信源提供的平均不确定性大小。 定义2 1 2 【5 4 】：知识( 属性集合) q 相对于知识p 的条件熵n ( e l p ) 为： h ( op ) = 一p ( 置) p ( 艺i 置) l o gp ( 弓i 置)( 2 7 ) i = 1 = l 其中p ( r , x , ) = r , nx , l i x , i ，i = l ，2 ，刀，j = l ，2 ，l 。条件熵h ( q i p ) 表示在己知知识p 的情况下，知识o 仍然存在的平均不确定度。 定义2 1 3 【5 4 】：知识q 与p 的互信息为： ，( 尸；q ) = h ( q ) - h ( q i p ) ( 2 8 ) 互信息度量了一个信源从另一个信源获得的信息量的大小，i ( p ；q ) 也称 o 和p 之间的平均信息量。 定义2 1 4 【：4 】：给定决策表s = ( u ，c u d ，v ，f ) ，其中c ，d 分别表示条件 属性集和决策属性集，对v a c ，a 是c 相对于d 不必要的充分必要条件是： 西南交通大学硕士研究生学位论文第11 页 h ( dc ) = h ( d i c 一 口) )( 2 - 9 ) 反之则a 是c 相对于d 必要的，属于信息观下c 的d 核c o r e c ( d ) 。 定义2 1 5 【2 4 1 ：给定决策表s = ( u ，c u d ，y ，) ，其中c ，d 分别表示条件 属性集和决策属性集，c 相对于d 独立的充分必要条件是，对v a c 满足： h ( dc ) h ( dc 一 以) )( 2 一l o ) 定义2 1 6 【2 4 】：给定决策表s = ( u ，c ud ，v ，厂) ，其中c ，d 分别表示条件 属性集和决策属性集，召c ，任意属性a c b 关于属性集b 的重要性定 义为： s i g ( a ，b ，d ) = h ( d l b ) 一h ( d i b u ( 口) ) ( 2 11 ) 定义2 1 7 【2 4 】：给定决策表s = ( u ，c u d ，v ，f ) ，其中c ，d 分别表示条件 属性集和决策属性集，则p 是c 相对于决策属性d 的一个约简的充分必要条 件为：日( d i 尸) = h ( dc ) ，且p 相对于决策属性d 是独立的。 王国胤等人提出了基于条件熵的知识约简算法c e b a r k c c t 2 3 j ，该算法以 决策表核属性集为起点，逐次选择使日( d i b u o ) ) 最小的非核条件属性a 添加 到核属性集中，直到满足终止条件日( d l b ) = h ( dc ) ，得到约简结果。 c e b a r k c c 具体算法步骤如下： 输入：一个决策表s = ( u ，a ，v ，f ) ，其中a = c u d ，c ，d 分别为条件属 性集和决策属性集。 输出：该决策表的一个相对约简b 。 s t e p l计算决策表t 中决策属性集d 相对条件属性集c 的条件熵 日( d l c ) 。 s t e p 2 计算核属性集c o r e ，并令a t t = c c o r e 。 s t e p 3 令b = c o r e ， s t e p 3 1 如果例! = o ，则计算条件熵h ( db ) ，转s t e p 3 4 ； s t e p 3 2 对每个属性a i a t t ，计算h ( db u 口啪； s t e p 3 3 选择使h ( d i b u a f ) ) 最小的属性a j ( 若同时有多个属性达到最 小值，则从中选取一个与b 的属性值组合数最少的属性) ，a t t = a t t a j ， b = b u a j ) ； s t e p 3 4 若h ( db ) = 日( d i c ) 则终止，否则转s t e p 3 2 。 基于信息熵的属性约简是可行的，而且在许多情况下能得到最小属性约 西南交通大学硕士研究生学位论文第12 页 简。但该方法性能与决策表核属性集的大小有关，如核集较大，则具有较好 的时间性能，否则，时间舯i 1 - 厶匕i v , 较差。该方法在最坏的情况下，时间复杂度为 o ( 彳l v l 2 ) + o ( i v l 3 ) 。 上面介绍的属性约简方法各有特点和不足，后续两章将分别介绍改进的 基于属性频率的约简算法和一种新的基于简化差别矩阵的约简算法。 2 5 本章小结 本章首先介绍了粗糙集属性约简的相关概念，如等价类、正域、相对核、 相对约简等，为后续算法的研究打下理论基础。接着介绍了基于差别矩阵、 基于重要度、基于信息熵的属性约简算法。 西南交通大学硕士研究生学位论文第13 页 第3 章基于属性频率的约简算法 3 1 h o r a f a 算法及不足 胡可云【1 6 】提出了基于属性频率的约简算法h o r a f a ，他认为，在差别矩 阵中一个属性的重要性由它出现的频率决定，一个属性出现越频繁，它的潜 在辨识能力就越大；同时，差别矩阵元素项的长短也是一个影响属性分辨能 力的因素。由此他提出了一个属性的加权频率函数： f ( a i ) = f ( a i ) + l c l m l ，( a i c )( 3 一1 ) 等式右的f ( a i ) 表示属性口f 在差别矩阵中出现的次数。l c l 是信息系统中 总的条件属性个数，i m l 是差别矩阵中非空元素项包含的属性个数。例如， 设f ( a 1 ) = 4 ，f ( a 2 ) = 5 ，系统总共有l o 个属性，新的差别矩阵元素项是 a l ，a 2 ) ， 则处理这项后，属性的频率被更新为：f ( a 1 ) = 4 + 1 0 2 = 9 ；f ( a 2 ) = 5 + 1 0 2 = 1 0 。 该式主要基于两个重要准则：( 1 ) 差别矩阵中属性出现越频繁，该属性越重 要；( 2 ) 差别矩阵中元素项长度越短，该项中属性越重要。 h o r a f