（计算机软件与理论专业论文）基于粗糙集理论的数据挖掘应用研究.pdf

大连理工大学硕士学位论文 摘要 租糙集理论是一种新的处理模糊和不精确问题的重要数学工具，由荷兰学者p a w l a k z 于1 9 8 2 年提出的。它不依赖于数据集之外的附加信息，是处理含有噪声、不精确、 不完整数据的有力工具，是一种新的数据挖掘技术。 基于粗糙集理论的数据挖掘过程主要分为数据预处理、属性约简、规则生成和决策 支持四个步骤。本文研究了属佳约简的相关算法，并探讨了数据预处理过程中的连续属 性离散化问题。属性约简是利用粗糙集理论进行数据挖掘中最重要的一个环节，它分为 前向选择法和后向删除法两大类，其中前者主要基于属性核的结果，因此本文着重研究 了求核算法。当决策表中存在大量冗余或不相容数据时，以往的求核算法，虽然既可以 处理相容数据，又可以有效得到不相容数据的求核结果，但它们采用或者保留冲突数据 的方法计算，或者直接删除冗余与冲突数据进行处理，而忽略了其内在隐含的信息。本 文给出了一种加权求核算法，能够根据冗余或不相容的程度体现出数据的参考价值和结 果的可靠性，并己通过实验证实，所得结果更接近于实际情况，弥补了仅仅从算法角度 求核的不足。连续属性离散化是数据挖掘过程中的前期工作，本文介绍了几种离散化思 想，并讨论了传统的基于属性重要性离散化方法和结合微粒群理论进行离散化处理的过 程，为本文的国民经济动员潜力分析系统连续属性离散化处理提供理论指导。 最后，以蘑菇数据库为例进行实验，得到影响蘑菇毒性的属性及规则，证实了粗糙 集理论在数据挖掘过程中的有效性。由于蘑菇数据库与本文的国民经济动员潜力分析系 统的数据相似性，从而，尝试性应用于后者，达到国民经济动员的目的。 关键词：粗糙集；数据挖掘；属性约简；高散化 大连理工大学硕士学位论文 r e s e a r c ha n da p p l i c a t i o no f d a t am i n m gb a s e do nr o u g hs e t a b s t r a c t r o u g hs c t ( i 塔) i san e wa n di m p o r t a n tm a t h e m a t i c a lt o o lt od e a lw i t hv a g u e n e s sa n d i m p r e c i s ep r o b l e m s w h i c hw a sm 删u c e db yp a w l a kzi n1 9 8 2 r sd o e s n td e p e n do n a d d i t i o n a li n f o r m a t i o nb e y o n dt h ed a t as e t , s oi t sap o t e n tt o o lf o rd e a l i n gw i t hv a g l 坞， i m p r e c i s e ，i n c o m p l e t ea n d u n c e r t a i nd a t a , a n di snl l c wt e c h n o l o g yi nd a t am i n i n g 1 1 地p r o c e s so fd a t am j n i n gb a s e do nr sc o n s i s t so fd a t ap r e p a r a t i o n , a t t r i b u t er e d u c t i o n , t h er u l e so ff o r m a t i o na n dd e c i s i o ns u p p o r t t h i sp a p e ri sf o c u s e do na t t r i b u t er e d u c t i o na n d i n t t o d u c e st h ed i s c r e t i z a t i o no fc o n s i s t a n ta t t r i b u t e s a t t r i b u t er e d u c t i o ni so n eo ft h em o s t i m p o r t a n tl i n k sd u r i n gd a t am i n i n gb a s e do nr s 1 1 尬c o r r e l a t i v em e t h o d sa r ed i v i d e di n t ot w o k i n d s s e l e c t i o nb e f o r ea n dd e l e t i o n 如r ，n 硷f o r m e ro f t 印s t a r t sw i t ht h ec o m p u t a t i o no f c o r e ， s ot h i sp a p e rm a k e sa s t u d yf o rt h ea l g o r i t h m so fc o r e w h e nt h e r ee x i t sl o t so fr e d u n d a n c y a n dc o n f l i c t s ，a l t h o u g ht h o s ea l g o r i t h m sb e f o r ec a nd e a lw i t hb o t ht h ec o n s i s t e n ta n d i n c o n s i s t e n td a t aa n dg e tt h er i g h tr e s u l t s ，t h e ye i t h e rd e l e t et h ec o n f l i c t sd i r e c t l yo rr e s e r v e t h ec o n f l i c t sc o m p l e t e l yi n s t e a do fs t u d y i n gt h ei n f o r m a t i o ni n s i d et h ed a t as e l f t i f f sp a p e r p r o p o s e saw e i g h t e dm e t h o dt oc o m p u t e rt h ec o r e ，w h i c ha c c o r d i n gt o t h ed e g r e eo f r e d u n d a n c ya n dc o n f l i c t e x p r e s s e st h er e f e r e n c e sa n dr e l i a b i l i t yo ft h er e s u l t s 1 n b e e x p e r i m e n th a ss h o w nt h eb e t t e rr e s u l t sw h i c ha r em o r en e a rt ot h ef a c ta n di m p r o v e dt h e m o d ec o m p u t i n go n l yf r o mt h ea l g o r i t h m s d i s c r e t i z a t i o ni st h ee a r l yw o r ki nd a t am i n i n g ，t h e p a p e ri n t r o d u c e st h em e t h o d so fd i s c r e t i z a t i o na n dd i s c u s s e ss o m er e l a t e dm o t h o d ss u c ha s t h eo n eb a s e do n 山ei m p o r t a n c eo fe a c ha m i h n t ea n dt h eo n eb a s e do np s 0 w h i c hg i v et h e t h e o r yg u i d a n c et ot h ea p p l i c a t i o n f i n a l l y 。b a s e do nt h ee x p e r i m e n ti nt h em u s h r o o md a t a b a s e ，i tp r o v e st h ee f f e c t i v e n e s so f r si na p p l i c a t i o n s b e c a u s eo ft h ec o m p a r a b i l i t yb e t v d e f f f lt h em u s h r o o md a t aa n dt h o s ed a t a i nt h en a t i o n a le c o n o m ym o b i l i z a t i o np o t e n t i a la n a l y z a t i o ns y s t e m s ，t h ep a p e rt r i e st oa p p l y t h ep r o c e s st ot h eh a e ra n da c h i e v et h ep u r p o s eo f n a t i o n a le c o n o m i cm o b i l i z a t i o n k e yw o r d s ：r o u g hs e t ；d a t am i n i n g ；a t t r i b u t er e d u c t i o n ；d i s c r e d z a t i o n i i i - r 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：撕 吼弯叫 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 导师签名 爸导守 皇。琴掣 珥址月乒日 大连理工大学硕士学位论文 1 绪论 1 1 粗糙集和数据挖掘 数据挖掘就是对观测到的数据集( 经常是很庞大的) 进行分析，目的是发现未知的关 系和以数据拥有者可以理解并对其有价值的新颖方式来总结数据。数据挖掘是一门跨学 科的技术。统计学、数据库技术、机器学习、模式识别、人工智能、可视化技术都在数 据挖掘中起着作用【l l 。 粗糙集理论( r s ) 作为集合论的扩展，主要研究在信息不完全和不完整情况下的数据 挖掘技术。而许多传统的数据挖掘技术仅仅适用于精确集，不适用于粗糙集，但在现实 中粗糙集是普遍存在的现象。因此，基于粗糙集的数据挖掘技术在信息系统的研究领域 具有重要的意义。 现实世界中数据的不完整、有噪声和不一致是很普遍的现象。在不完全信息下的数 据挖掘是一个困难的问题，但它在数据决策中是不可避免的。因为传统的数据挖掘技术 对数据的质量要求较高，只能在精确集下进行数据挖掘，例如决策树方法。对一些含有 模糊信息的数据需要进行改变或摒弃之后才可以挖掘，这样很容易造成信息的丢失，而 粗糙集却可以对这一类信息进行挖掘。 数据挖掘是从大量数据中提取或“挖掘”知识，而这也是粗糙集中约简所要达到的 目的。知识约简，就是在保持知识库分类能力不变的条件下，删除其中不相关的或不重 要的知识【2 】。所以利用粗糙集理论进行数据挖掘，得到知识规则，最重要的一点就是基 于粗糙集的属性约简( 知识约简) 。 1 2 研究背景 本文的选题来自于国家国防动员委员会国民经济动员办公室的一个实际项目 国民经济动员潜力分析系统。 在当今世界上，任何国家都存在着应付战争和其他人类灾难的可能。从上世纪末到 本世纪初，除了人们熟知的战争状态外，灾难性紧急状态的多发性和多元性日益凸显出 来，如重大自然灾害、重大环境灾难、大规模恐怖活动、大范围瘟疫、大范围动乱、全 球性或地区性金融危机等。无论是战争、局部冲突而导致的战时状态，还是多种原因造 成的紧急状态，都会打破正常的社会运行规律。这时候需要一种机制去发挥作用，首先 保证社会继续运转，同时积极组织力量服务于其时国家的核心任务。从正常机制到特殊 机制是一个过渡和转化的过程，这个过程就叫做“动员”。动员包括许多方面，而国民 经济动员是其中的核心部分，它围绕国民经济基础而展开，是所有动员的前提条件。古 基于租糙集理论的数据挖掘应用研究 往今来无数事实证明，经济实力是赢得战争胜利或战胜重大灾难最终的决定性因素。 国民经济动员潜力分析是国民经济动员工作的最基本需要，它通过统计调查方法将 所需要的信息收集上来，进行加工处理变成有序信息，保障国民经济动员工作的一切信 息使用需要。最后，为达到国民经济动员的最终目的，本文选用基于粗糙集理论进行数 据挖掘应用。 1 3 国内外研究现状 粗糙集理论已经被证实在实践中是非常有用的，从大量的现实生活中应用的记录来 看已经非常明显。这一理论对于a j 和认知科学尤为重要，在决策支持、专家系统、归 纳推理、开关电路等方面有了重要的应用。在数据库领域知识发现( k d d ) 中的应用取得 了较大的进展，基于粗糙集理论的方法逐渐成为k d d 主流方法之一。 在过去几年中，建立了不少基于粗糙集的知识发现系统，其中最有代表性的，主要 有以下几种。 ( 1 ) l e r s l e r s ( l e a r nf r o me x a m p l e sb a s e do nr o u g hs e t ) 系统是美国k a n s a s 大学开发的基于 粗糙集的实例学习系统，它是用c o m m o nl i s p 在v a x 9 0 0 0 上实现的。l e r s 已经为 n a s a 的j o h n s o n 空间中心应用了多年。另外，l e r s 还被广泛的用于环境保护，气象 研究和医疗研究。 ( 2 ) r o s e r o s e ( r o u g h s e t d a t a e x p l o r e r ) 是由波兰p o z n a n 科技大学开发的，用于决策分析。 r o s e 是运行在p c 兼容机w i n d o w s n t 上的交互式软件系统。 ( 3 ) k d d r k d d r 由加拿大的r e g i n a 大学开发的基于可变精度粗糙集模型的知识发现系统， 这个系统被用于对医学数据分析，以产生症状与疾病之间的新联系，另外它还支持电信 业的市场研究，该系统由四部分组成：数据预处理，基于v p r s 模型的属性依赖分析和 清除冗余属性，规则提取，决策。 ( 4 ) d a t al o g i c r d a t al o g i c r 由加拿大的r e d u e ts y s t e mi n c 公司开发的用于数据库知识发现的软 件，它是用c 语言开发的，可安装在个人计算机上，为科研和工业界服务。 ( 5 ) k n i g h t s k n i g h t s 是南京大学计算机学院开发的一个知识挖掘系统，是一个通用的数据挖掘 工具，可适应不同领域的不同要求。 2 一 大连理工大学硕士学位论文 1 4 本文研究工作 ( 1 ) 介绍租糙集的概念以及基于粗糙集理论进行数据挖掘的过程，获得有用的关联 规则。 ( 2 ) 讨论了各种属性约简的算法和思想，为实际项目的应用提供广泛的思路。 ( 3 ) 着重介绍了求核方法，并在此基础上，提出了一种加权求核算法，用于处理存 在大量冗余或不相容数据，实验证明，使用该算法所得结果比较接近实际。 ( 4 ) 探讨了利用粗糙集进行数据离散化的方法，为实际应用提供理论准备。 ( 5 ) 将基于粗糙集理论的数据挖掘过程用于蘑菇数据库，得到了期望的效果，从而， 为运用于实际项目奠定了实验基础。 本文利用粗糙集理论进行数据挖掘，基于蘑菇数据库的实验结果，针对国民经济潜 力动员分析系统中数据的关联性，想要得到有用的关联规则，为国民经济动员奠定了理 论及实验基础。 1 5 论文组织结构 第一章介绍了数据挖掘的原理。本文从数据挖掘和知识分类的角度出发，探讨了数 据挖掘的相关概念及应用现状，并介绍了当前一些的基于粗糙集的数据挖掘系统。 第二章是粗糙集基础理论。详细介绍了粗糙集相关知识，包括信息系统与信息表、 不可分辨关系、上下近似集、知识的依赖性、重要性以及知识约简中的约简和核等。 第三章是基于粗糙集理论的数据挖掘。介绍了基于粗糙集的数据挖掘过程，以及各 种属性约简算法。由于在此过程中，核的重要性，重点研究了求核的相关算法，并针对 决策表中存在冗余和不相容数据时，给出了一种求核算法，使结果更接近实际。 第四章是连续属性离散化。是数据挖掘过程中的预处理部分，介绍了其相关概念， 并结合粗糙集理论进行处理，为国民经济动员的数据准备提供理论指导。 第五章是租糙集理论在国民经济动员潜力分析系统中的尝试性应用。介绍了作者实 际开发的一个系统及相关技术，并将以上介绍的理论运用于蘑菇数据库中，得到满意的 结果，由于蘑菇数据库与本系统的数据相似性，为后者的应用奠定了理论及实验基础。 基于粗糙集理论的数据挖掘应用研究 2 粗糙集理论概述 粗糙集( r o u g hs e t ) 理论是由波兰华沙理工大学p a w l a k l 3 1 教授于1 9 8 2 年提出的一种 数据分析理论，主要研究不完整、不确定知识和数据的表达、学习和归纳的方法，近年 来受到国际上的众多学者的重视。其主要思想是在保持分类能力不变的前提下，提出知 识约简，导出问题的决策和分类规则。目前，粗糙集理论己被充分地应用于机器学习、 决策分析、过程控制、模式识别和数据挖掘等领域。本章主要介绍粗糙集理论的相关概 念，其中包括信息系统与信息表1 4 l 、不可分辨关系【5 6 1 、上下近似集【7 1 、知识的依赖性8 l 以及知识约简中的约简1 4 1 和核【9 l 等。 2 1 粗糙集中的知识表示方法 任何一个物种都是由一些知识来描述的，利用不同的知识描述，对物种可以产生不 同的分类。数据挖掘的关键步骤就是知识获取，就是从大量的原始数据信息中分析发现 有用的规律性信息，即将知识从一种原来的表达形式( 原始数据表达形式) 转换为一种新 的目标表达形式( 人类或计算机便于处理的形式) 。而要实现上述的转换过程，就必须对 知识有种合适的表达方式以便处理和解释。 粗糙集假定知识是一种基于对对象进行分类的能力，通常借助于决策表这样一种有 效的知识表达方式进行处理。对象指任何可以想到的任何事物，例如实际物体、状态、 抽象概念、过程、时刻等。知识必须与真实或抽象世界有关的不同分类模式联系在一起， 称之为论域( u n i v e r s e ) 嗍。由于经典的粗糙集理论是基于集合论的，所以下面的定义都 是从集合论的角度给出的。 定义2 1 信息系统( i n f o r m a t i o ns y s t e m ) 与信息表( i n f o r m a t i o nt a b l e ) 粗糙集把客观世界或对象世界抽象为一个信息系统，也称知识库。一个信息系统s 是一个四元组：s = ( u ，a ，v ，) 。 其中，u 是对象( 或实例) 的有限集合，u = “，x 2 焉) ；一是属性的有限集合， 一= q ，0 2 巩，；v 是属性的值域集，v = 叶，屹) ，其中v 是属性a s 的值域。厂信 息函数( i n f o r m a t i o n f u n c t i o n ) ，f ：u a 斗v ，( 而，a j ) v ，。 定义2 2 不可分辨关系( i n d i s c e m i b i l i t yr e l a t i o n ) 不可分辨关系( 也称为等价关系) 是粗糙集理论的基础概念，它在信息系统中的定义 为：r ( 曰) = ( k ，五) i 厂( 而，b ) = f ( x 2 ，6 ) ，b 占) 。 其中b 是彳的子集，即对任意的而，屯e 五，有瓴，x 2 ) e 震；对任意的气蜀，x 2 e 乃， 4 一 大连理工大学硕士学位论文 f j ，有( 而，x j ) 叠r 。 r ( b ) 把u 划分为k 个等价类，记为r + ( 动= x l ，x 2 。 。若无特别指明，后文 中的r ( 曰) 将简记为r ，胄( 回简称为胄。对于等价类五而言，f 表示集合x 的基数。 由定义可以看出论域中的对象组成了一些等价类，这些等价类由不能分辨的对象组成。 定义2 3 上近似和下近似 设x u 是一组对象，对于一个等价关系r ，即月c 是一组条件属性，则x 相对 于盖的下近似可表示为：_ r x = x e u r i k x ；x 相对于盂的上近似可表示为： r x = x u r i 【硼。n x o ) 。通过以上概念可知，下近似是指由那些根据知识r 判 断肯定属于x 的u 中的元素组成的集合；上近似是指那些根据知识矗判断可能属于j 的u 中的元素组成的集合。粗糙集中有时也将下近似成为x 的震正域，记为p o s 。( ； u - r _ ( x ) 称为x 的足负域，记为n e g 。( x ) 。 由以上定义，可以看出来集合的不精确性正是由于边界域的存在而引起的。集合的 边界域越大，其精确度越低。为了更精确的表达这一点，引入精度来描述。由等价关系 且定义的集合的近似精度为口。爿鱼l i r x i 其中x a ，i x i 表示集合的基数。 定义2 4 决策系统与决策表 上述信息系统中，如果属性集合中含有决策属性，s 又可称为决策系统。决策系统 是一类特殊而重要的信息系统，指当满足某些条件时，决策( 行为) 应当怎样进行。 相应于信息系统可以用信息表来表达，决策系统也可以，记为t = ( u ，c u d ) ，此时 属性集彳常常划分为两个集合c 和d ，其中c 表示条件属性集合( 条件维集) ，d 表示决 羡属性集合( 决策维集) 。并且a = c u d ，c n d = a 。 表2 1 决策表 t a b 2 1d e c i s i o nt a b l e 例2 1 决策表例子，如表2 1 所示。列是属性，行是对象。论域为u = “，而，黾) ， 一5 一 基于粗糙集理论的数据挖掘应用研究 属性集合( 维集) 为a = a , b ，c ，d ，其中条件属性集合为c = a s b ，c ，决策属性集合为 d = d ) 。 定义2 5 属性依赖度 集合属性d 对占的依赖度定义，如公式( 2 1 ) 所示。 r ( b ，d ) 爿p o s 口( d ) i l u ( 2 1 ) 其中p o s e ( d ) 为根据属性集合口划分的正区域。如果d 是全部决策属性集合，口是 条件属性，则r ( b ，d ) 表示用口对u 划分后，任意x u 能被正确划分到决策类的概率； 同时刻画了条件属性b 描述决策属性d 的能力。该定义在有些文献中也称为近似质量或 分类质量l lo j 。 定义2 6 属性重要度 在属性依赖度的基础上，可以定义每一个属性的重要程度。属性a 相对于口对于d 的依赖程度的属性重要度，如公式( 2 2 ) 所示。 s i g ( 口，b ，d ) ；r ( 丑+ 【口】，d ) - r ( b ，d )( 2 2 ) 由此可以理解为，为了求得某些属性或属性集的重要性，可以从表中去掉一些属性， 再来考察之后分类会怎样变化。若去掉该属性会相应的改变分类，则说明该属性的强度 大，即重要性高；反之，若去掉该属性后并不改变分类，则说明该属性的强度小，即重 要性低。也就是说，属性重要度越大，属性a 对决策划分的影响越大，相对于决策属性 来说也就越重要。在以后的章节中，很多算法是基于属性重要度计算的。 2 2 知识约简 知识约简是粗糙集理论的核心内容之一。知识约简是研究信息系统中每个等价关系 是否都是必要的，以及如何删除不必要的知识。其中两个重要概念是约简和核。 定义2 7 设尸c ，若= r c ，且不存在胄p ，使得n = r c ，则称p 为c 的一个 ( 相对于决策属性d 的) 属性约简。所有c 的属性约简的交集，称为c 的核( 简称核) ，记 为c o r e ( c ) 。 定义2 8 如果属性a c 满足，c 一陋i ， 8 ) ， 9 ) ， 1 0 ， 1 1 ) ， 1 2 ， 1 3 ， u 1 n d ( 4 ，4 ，4 ) = 1 ) ，( 2 ) ，( 3 ，1 3 ， 4 ，1 0 ， 5 ) ， 6 ， 7 ， 8 ) ， 9 1 ， 1 0 ， 1 1 ， 1 2 ) ， 1 3 ) ) 所以，4 的属性重要度s g ( 4 ，e d ) = 1 - c a r d ( 2 59 1 0 ，1 l ，1 3 ) j ，c a r d ( u ) = 4 7 。 同样的道理可以依次求出4 ，4 ，4 的属性重要度分别是0 ，o 和2 7 。由以上方法 可以得到4 、4 为核属性以及4 、4 属性重要性为0 的属性，可知它们对于所有属性是 可以省略的，但是能不能同时省略需要进一步考察。构造集合a = 4 ，4 ，彳是由所 有属性重要性为0 的属性构成的集合，求出彳的各阶幂子集，从高阶开始计算各阶幂集 元素的属性重要性，如t r a ) 为一的最高阶幂子集，乏( 彳) = 4 ，4 ，其中只有一个元素， 则计算 4 ，4 ) 重要度：u i n 硪4 ，4 ) = “l ，8 ，9 ， 2 ，1 1 ， 4 ，5 ，1 0 ， 6 ，1 4 ， 3 ，1 3 ， 7 ，1 2 。 又求得属性集 4 ，4 ) 的属性重要性为5 1 4 ，所以属性集 4 ，4 ) 是不可省略的。于是 进一步求五( 4 ) 的各个元素的重要性，五( 爿) = “4 ) ， 坞， ，前面已经得到属性4 和4 的 重要性为0 ，所以省略其中任意一个，余下的就是属性约简的结果。于是，约简的结果 是“码4 或 4 厶以。 采用传统的约简算法得到的结果也是 4 4 或 4 以4 ，说明此方法在计算的 正确性上和传统方法一致。由于它和传统方法都不可避免地要用到求集合幂子集，对属 性进行全部的搜索计算，所以在效率上没有太大的提高，但是采用的方法提供了求属性 约简的另一种思维方法，并与之前的决策表离散化( 详细内容见第四章) 采用同样的方 法，使约简的过程更加统一和一致化。 3 2 4 基于遗传算法求属性约简 遗传算法( g e n e t i ca l g o r i t h m ，简称g 舢八十年代发展起来的一种随机全局优化算法， 它是基于达尔文生物进化论的自然选择学说和群体遗传学原理而建立的，主要由选择、 交叉和变异三个算子组成，分别模仿达尔文进化过程中的自然选择过程和群体遗传过程 中发生的交配和基因突变等现象。遗传算法应用于实际问题时，需对优化问题进行编码， 基于粗糙集理论的数据挖掘应用研究 称为个体，个体的集合称为群体，每个个体都表示问题的一个潜在解。算法通过使用遗 传算子对初始群体进行操作，使初始群体一代一代向最优解进化。 遗传算法主要运算过程如下： ( 1 ) 编码方法 由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传 空间的基因型串结构数据。在此，使用固定长度的二进制符号串来表示群体中的个体， 其等位基因是由二值符号集 o ，1 所组成的。初始群体中各个个体的基因值可用均匀分布 的随机数来生成。如1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 就可表示一个个体，该个体的染色体长度是 n = 1 8 ，其中每一位对应一个条件属性，若某位取值为1 则表示选择其对应的条件属性， 若某位取值为0 ，则表示不选择其对应的条件属性。 ( 2 ) 个体适应度评价 定义适应值函数，如公式( 3 1 ) 所示。 f ( 工) = ( 1 - c a r d ( x ) 甩) + k( 3 1 ) 其中c a r d ( x ) 为染色体中1 的个数，即染色体所含条件属性的个数：”为染色体的长 度，即条件属性的个数；k 为决策属性对该染色体所含的条件属性的依赖度。该函数可 以控制染色体朝着最小约简的方向进化：k 越大，说明决策属性d 依赖条件属性c 越强， 当k = l 对，决策信息完全由条件信息确定：通过c a r d ( x ) 来控制染色体所含条件属性的 长度。通过这两方面，构造的适应值函数可以在保持决策属性对整体条件属性依赖度不 变的情况下找到所含条件属性最少的约简。 ( 3 ) 选择操作 本文采用适应度比例选择方法，从当前群体中选出优良的个体，将其复制到下一代 群体中，该方法也称为赌盘选择。 其具体执行过程是： 先计算出群体中所有个体的适应度总和。 其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代群 体中的概率：c f ( x j ) = f ( x j ) 7 e f ( x j ) ，_ ，= 1 ，2 ，m 。 l 最后使用模拟赌盘操作( 即0 到1 之间的随机数) 来确定各个个体被选中的次数。 ( 4 ) 交叉操作 本文采用单点交叉算子，其具体执行过程为：对群体中的个体进行两两随机配对； 对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点：对每一对相互配 大连理工大学硕士学位论文 对的个体，依设定的交叉概率弘在其交叉点出相互交换两个个体的部分染色体，从而 产生出两个新的个体。 ( 5 ) 变异操作 本文采用基本位变异算子，其具体执行过程为：对个体的每一个基因座，依变异概 率聊l 指定其为变异点；对每一个指定的变异点，核中属性对应的基因位不发生变异， 其它则对其基因值做取反运算，从而产生出一个新的个体。 ( 6 ) 最优保存策略 在得到新一代个体之后，如果其中最坏个体( 适应值最小) 的适应值小于上一代最好 个体( 适应值最大) 的适应值，则用上一代最好的个体代替新一代最坏的个体，该方法确 保算法收敛。 基于遗传算法求属性约简。 输入：一个决策表s = ( u ，a ，v ，厂) ，a = c u d ，c 是条件属性，d 是决策属性。 输出：此决策表的一个属性约简胄。 由( 1 ) 式计算出决策属性d 对条件属性c 的依赖度，。( d ) 。 求核c o r e ( c ) ；若y ( d ) = 7 c ( d ) ，则c o r e 即为最小相对约简，否则执行。 随机产生m 个长度为疗( 条件属性的个数) 的二进制串组成初始群体；对于核中的 属性，其对应位取1 ；其它则对应位随机取0 或1 。 计算出决策属性对每个个体所含条件属性的依赖度；计算出每个个体的适应值； 计算出每个个体被选择的概率；最后使用模拟赌盘操作( 即0 到l 之间的随机数) 来选择 个体。 根据交叉概率筇进行交叉操作，采用单点交叉方式。 根据变异概率p m 进行变异，采用基本位变异方式，其中核属性的对应位不变。 采用最优保存策略，将最优个体复制到下一代群体中。 如果连续k e e p 代的最优个体的适应值不再提高，则终止计算，否则转。 为了进一步验证本算法的约简效果，从u c i 机器学习数据库中选择了z o od a t a b a s e ， 条件属性集为c = a n i m a ln a m e , h a i r , f e a t h e r s ，e g g s ，m i l k ，a i r b o r n e , a q u a t i c , p r e d a t o r , t o o t h e db a c k b o n e , b r e a t h e s ，v e n o m o u s , 归琏l e g s , t a i l ，d o m e s t i c , s i z e ) ；决策属性集 d = t y p e 。 文【2 5 】给出了利用该遗传算法求解最小约简的结果。其中m = 1 0 ，p c = o 6 ，p m = o 0 2 。 在本例中，第1 6 代出现了最优个体，并连续1 0 代均不变，即求得属性约简后的结果为 a n i m a ln a r l l 。 基于粗糙集理论的数据挖掘应用研究 表3 3 对z o o 数据的约简结果 t 曲3 3r e s u l t so f r e d u c t i o nf o rz o od a t a 3 3 求核 3 3 1 已有的求核方法 在粗糙集理论中，属性约简是最重要的研究内容之一，也是知识获取的关键步骤， 因此属性约简的研究倍受粗糙集研究者的关注，也取得了很大的进展。然而很多属性约 简都是从核开始的，因此求核成了属性约简求解的关键步骤，而探索求核的有效方法具 有重要的实用价值 2 6 1 。 由差别矩阵的定义可知，差别矩阵的元素实际上是若干属性集合，这些属性集合表 示了某两个对象在这些属性上有差异。因此当考察一个差别矩阵时不难发现，如果矩阵 中存在只包含单个属性的元素，则该属性就是区分这个矩阵元素所对应的两个对象所必 须的属性，也是唯一能区分这两个对象的属性。差别矩阵中所有这样的元素组成的属性 集合其实就是该决策表的核集合。 定义3 3 胡晓华等学者1 1 7 1 提出了更简洁的利用改进差别矩阵来确定核的方法，其 中改进的差别矩阵，如公式( 3 2 ) 所示。 一 i 口c ：f ( x j ，口) f ( x j ，口) 当地，研f ( x j ，d ) 时 阳们 j 珐。= 、o ， ”i o ( 空集) ，其他情况时 在上述定义中，与通常意义下的矩阵元素不同的是，差别矩阵的元素，是条件属 性c 的某个子集。但胡等人中未加证明地给出如下结论：当且仅当某个嘲，为单个属性 时，该属性属于核c o r e ( c ) 。需要指出的是，该方法存在着缺陷。在一些情况下，它求 得的结果是错误的。叶东毅等人给出了反例，并予以证明。从而提出新的定义。 定义3 4 对给定的信息系统腰( 决策表) ，定义差别矩阵s m = 嘭 ，见公式( 3 3 ) 。 大连理工大学硕士学位论文 巾 三：篓嬲卜1 江s ， 其中， 的定义同式( 3 2 ) ；对而u ，d ) = f o ，d ) ：y k 】c i 。 由以上的定义可以得出：若决策表中不存在不一致数据，那么胡的结论可以直接使 用；否则，需要判断d ( ) 的值，产生的具体原因可以参考文献 2 7 。但判断d ( 而) 需要 很大计算量，于是杨明等人脚l 又对算法做了相应的改进。 定理3 1 渊对属性a c ，a 是不可缺少的当且仅当存在x c ，帆( f 【l ，j 】) 使得下 列条件之一成立： ( 1 ) 存在【l ，七】且j f ，使得【乩一i 。 n y ，g ； i ( 2 ) 【扎- 口 n 一c 讥) o 。 ，l 定义3 5 伫羽对给定的信息系统俗，定义差别矩阵m i = ) ，如公式( 3 4 ) 所示。 2 钮c ：f b 。，由芋，bj ，烈，b l ，聊，q p 聊l u t ，x | u 、 a e c ：f ( x , ，a ) f ( x j ，力) ，薯u ，t 呸 ( 3 4 ) 须揲) ，其它 其中，酝= c 矿，= u - u 1 。 月1 。定理3 2 2 6 i 对于信息系统嚣，若记皿m ( c ) = i m 且为单个属性 ， 则有i d m ( c ，m ) = c o r e ( c ) ，即当且仅当某个为单个属性时，该属性属于核c o r e ( c ) 。 引理3 1 对c 饥，呸= u u l ，且o ，若_ u 2 ，一巩。对任意口c 满足 i = l f ( x y ，口) = 厂( ，口) ，且f ( x j ，d ) f ( x t ，三 ) ，则对任意而u i ，啊，= 巩。 定义3 6 对给定的信息系统嚣，定义差别矩阵彤：= ，如公式( 3 5 ) 所示。 f p c ：，口) f ( x i ，口) ) ，( _ ，d ) 厂吒，d ) 且u ，工，u 1 = 口c ：厂( 五，口) 厂( ，口) ，薯u ， ( 3 5 ) 【a ( 空集) 其他 其中，u = c 妒，u 2 = u - u 。，q = d e2 ：r e p ( u , ) ，这里的函数出岫( ) 实际上就 j ；t 是将不一致数据进行处理，处理的结果使每组不一致数据集合仅保留一个元素。 基于租糙集理论的数据挖掘应用研究 例3 3 如表3 4 所示。 表3 4 决策表 t 曲3 4d e c i s i o nt a b l e 利用上述定义求出：q = 而，) ，f f i x ：，而) ，e = 。依据建立的差别矩阵 而毛屯 为五fo c 2 c 1 ) 1 。 x 4 l ( c 2 ) o c l ，c 2 ) j 3 3 2 一种带权重的求核算法 不一致数据的存在，从逻辑上讲，就可以理解为，决策表本身存在矛盾：同样的条 件属性，可能得到不同的决策属性。在海量数据信息中，这种情况是难免的。既然决策 表本身存在矛盾，那么这些数据在决策过程中，所占有地位的重要性也就有所不同。所 以，在计算的过程中，对对象进行权重设置，从而结合实际情况求核。 对于不存在不一致数据的对象而言，在决策过程中，具有很重要的参考价值，所以 应将此类对象的权重设置较大；对于存在不一致数据的对象，应考虑其冲突的程度，冲 突的程度越大，该对象的权重设置则越小。因此，在数据挖掘的准备数据之后，不要立 刻删除重复数据，而要做以下工作： 算法3 1 ： i 输入：u i = u c 西= u u 。差别矩阵为j i f 2 ，( 其中u l 中可能包含重复数据) 。 t f f i l 输出：对象的权重数组w r l 。 算法描述： b e g i n f o r 任意& u d o i = 1 w x 】= c o u n t ( x ) 对象x 重复出现的个数 大连理工大学硕士学位论文 e n a f o r o r z d o t = c = ，t 2 ，岛，f 。 贝啦( o 后s 肼) s = d = 焉，8 2 ，岛，) 建k t ( 0 s f s 玎) 计算出集合s 中元素基数最大的值c a r d ( s j ) 。 所有元素基数的和s c 目m 以f l ( w x = ( c a r d ( s j ) - s k ) s u m 。 l l 矿研明0t h e n w x 】赋予一个非常小的正值 e 稚移 e n a f o r r e t u r n 形口 e n d 这样完成了每个对象的权值分配。利用文献 2 8 】的方法，将u 2 简化为明，并且u 2 中 的对象的权值赋予职中的对象根据以上定义，形口中的数值代表了每个属性的重要性。 在不存在冲突数据的情况下，只需要计算m = c o u n t ( x ) ，与以前计算属性重要性的结 果完全一致。 所以，对给定的信息系统四，定义差别矩阵m 2 = 嘞) 。 扣c ：，i 矗，a ) f ( x j ，口) ，“，d ) f ( x j ，d ) 且弓e u , ，_ q 若潮个数为1 ，则一定是核属性( 3 6 ) = 口c ：八耳，a ) , f ( x ，口) ，墨q ，e u z 研空集) ，其它 若幽个致为l ，需给舔加权重哪】 ( 3 7 ) 其中，u = 钆，= 【，一u ，矾= d e l r e p ( u 2 ) ( 可参考引理3 1 ) ，这样可以粗略理 t = l 解： 公式( 3 6 ) 中的核属性是必需的；公式( 3 7 ) 中求出的而不在公式( 3 6 ) 中核属性，需 要将它的权值进行累加，则可以根据具体需要进行选择。这里，可以设定一个阀值h ( 根 据具体的应用而定，范围一般在1 之间) ： ( 1 ) 当属性对应的列对象的权值累加和大于该阀值，则保留为核属性； ( 2 ) 否则可以舍弃。 说明：当所有对象的权重都设为1 的时候，就是传统的求核算法。也就是说，传统 基于粗糙集理论的数据挖掘应用研究 算法是该算法的一个特例，该算法是传统算法的一种拓展形式，更具有通用性。 3 3 3 实例及实验结果 例3 a 如表3 。5 所示，由此计算出核属性为c l ，c 2 。当引入1 个错误记录毛( o 1 ，1 ，0 ) 以 后：由完全冲突算法计算出的结果为：空；由杨等人的算法计算出的结果为：c l ，c 2 ； 用算法3 1 ，设置属性为1 ，2 ，计算出的结果为c 1 ，c 2 。 表3 5 决策表 t a b 3 5d e c i s i o nc a b l e 当引a , 1 个错误记录而( 1 ，l ，0 ，1 ) 以后：由完全冲突算法计算出的结果为：c l ，c 2 ；由 杨等人的算法计算出的结果为：q ，q ，g ，用算法3 1 ，设置属性为1 2 ，计算出结果为： c 1 ，c 2 。 图3 3 比较结果 f i g 3 3 r e s u l t so f c