（计算机系统结构专业论文）基于粗糙集的图书销售信息离群数据检测.pdf

摘要 摘要 本文把目前流行的粗糙集属性约简算法运用到销售数据的离群检测与分 析。离群数据挖掘是数据挖掘的一个分支，目前在很多领域得到运用，挖掘出 来的数据不再是当作噪声数据去掉，具有一定的价值和实用性。本文设计了一 种基于相异度的离群数据挖掘算法，其基本思想是：首先运用正区域约简算法 来求取图书数据集的相对约简，消除冗余属性，再运用相异度公式进行离群数 据的检测，加快了离群检测的速度。本文主要的研究工作包括： 对目前流行的粗糙集理论进行了介绍，并分析了三种主要粗糙集约简算法， 即基于区分矩阵的属性约简算法、基于信息熵的属性约简算法和基于代数形式 的属性约简算法。本文采用了正区域的属性约简算法，此算法更贴近粗糙集的 约简本质，算法简单，且容易理解。 深入研究各种离群数据的挖掘模型的优劣，设计了一种基于相异度的离群 数据挖掘算法，此算法的基本思想是：运用粗糙集的正区域属性约简算法将高 维数据集降为低维数据集，再利用改进后的相异度公式对此约简后的数据集进 行离群数据的检测。同时通过分析涂丽红，杨丽萍等提出的基于相异度的孤立 点挖掘研究的种种缺点证明了本文的相异度离群数据挖掘算法的优势。 为了更好的实现本系统的灵活性，用户可以自定阈值，限定取值范围，输 入的阈值越小，得到的离群记录就越精确，反之，得到的离群记录就越粗糙。 本系统用在图书销售数据集中具有一定的灵活性和实效性。 关键词：粗糙集；相异度；离群数据挖掘；属性约简；销售数据 a b s t r a c t a b s t r a c t i nt h i sp a p e r , t h ec u r r e n t l yp r e v a i l 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 mb a s e do nt h e r o u g hs e ti sa p p l i e dt ot h ed e t e c t i o na n da n a l y s i so fo u t l i e rc o n c e r t is e l l i n g s i n c et h e o u t l i e rm i n i n gi sas u b b r a n c ho fd a t am i n i n g ，t h ef o r m e rh a sb e e na p p l i e dt oag r e a t m u l t i t u d eo ff i e l d s ，w h e r et h em i n e dd a t a , i n s t e a do fb e i n gr e g a r d e da sn o i s yo n e sa n d t h e nd i s c a r d e d ，a r eo fc e r t a i nv a l u ea n da p p l i c a b i l i t y a na l g o r i t h mo fo u t l i e rm i n i n g b a s e do nd i s s i m i l a r i t yi sd e s i g n e d ，w i t ht h eb a s i ci d e a sa sf o l l o w s ：i nt h ef i r s tp l a c e ， t h ep o s i t i v er e g i o nr e d u c t i o na l g o r i t h mi su t i l i z e dt oe x t r a c tt h er e l a t i v er e d u c t i o no f t h ed a t as e tc o n c e m i n gb o o k sa n de l i m i n a t er e d u n d a n ta t t r i b u t e s ；i nt h es e c o n dp l a c e ， t h ef o r m u l ao fd i s s i m i l a r i t y , a na c c e l e r a t i n gm e t h o do fd e t e c t i o n ，i st h e nu s e dt o d e t e c tt h eo u t l i e r t h em a i nr e s e a r c ht a r g e to ft h i sp a p e rc o v e r st h ei n t r o d u c t i o nt ot h ep r e v a i l i n g r o u g hs e tt h e o r ya n dt h ea n a l y s i so ft h r e em a j o rr e d u c t i o na l g o r i t h mb a s e do nt h e r o u g hs e t ：t h a ti s ，t 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 mb a s e do nt h ed i s c e r n i b i l i t ym a t r i x , t 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 mb a s e do ni n f o r m a t i o ne n t r o p y , a n dt h ea t t r i b u t e r e d u c t i o na l g o r i t h mb a s e do nt h ea l g e b r a i cf o r m i nt h i sp a p e r , t h ep o s i t i v er e g i o n a t t r i b u t er e d u c t i o na l g o r i t h mi sa d o p t e db e c a u s ei ti si nc l o s e rp r o x i m i t yw i t ht h e e s s e n c eo fr o u g hs e tr e d u c t i o na n di t i sa l g o r i t h m i c a l l ys i m p l ea n du n d e r s t a n d a b l e t h ep r o sa n dc o n so fv a r i o u sm o d e l sf o ro u t l i e rm i n i n ga r ei n t e n s i v e l ys t u d i e d ， a n da l la l g o r i t h mf o ro u t l i e rm i n i n gb a s e do nd i s s i m i l a r i t yi sd e s i g n e d ，t h eb a s i ci d e a o fw h i c hl i e si nt h a tt h ea l g o r i t h mo fp o s i t i v er e g i o na t t r i b u t er e d u c t i o no ft h er o u g h s e ti su s e dt oa l t e rt h eh i g h - d i m e n s i o n a ld a t as e tt ot h el o w - d i m e n s i o n a lo n e m e a n w h i l e ，t h ea d v a n t a g eo ft h ed a t am i n i n ga l g o r i t h mb a s e do nt h ed i s s i m i l a r i t yi s d e m o n s t r a t e dt h r o u g ha n a l y z i n gt h es h o r t c o m i n g sr e f l e c t e di nt h es t u d yp r o p o s e db y t ul i h o n ga n d y a n gl i p i n gc o n c e r n i n gi s o l a t e dv e r t e x e sb a s e do nd i s s i m i l a r i t y i no r d e rt oa c h i e v eh i g h e rf l e x i b i l i t yo ft h i ss y s t e m ，u s e r sc a l lc u s t o m i z et h e t h r e s h o l d 。r e s t r i c tt h er a n g eo fv a l u ei nt h a tt h es m a l l e rt h et h r e s h o l di s ，t h em o r e a c c u r a t er e c o r do fo u t l i e rt h e yc a no b t a i n ，a n dv i c ev e r s a t h i ss y s t e me x h i b i t sc e r t a i n f l e x i b i l i t ya n dp r a c t i c a l i t yw h e na p p l i e dt ot h ed a t as e tc o n c e r n i n gb o o ks e l l i n g a b s t r a c t k e yw o r d s ：r o u g hs e t ；d i s s i m i l a r i t y ；o u t l i e rm i n i n g ；a t t r i b u t er e d u c t i o n ；d a t a c o n c e r n i n gs e l l i n g 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得直昌太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名( 手写) ：r 蹴 签字日期： z 。年1 月多日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权直昌太堂可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。同时授 权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名( 手写) ：陈雪缭 签字日期：b f 口年 1 月了日 导师签名( 手写) ：径荡 签字日期：z 。f 。年1 月了日 第1 章引言 第1 章引言 本文采用粗糙集的正区域属性约简算法对图书销售数据进行约简，提出了 基于粗糙集的图书销售信息离群数据检测o m b s i r s ( o u t l i e rm i n i n go fb o o k s e l l i n gi n f o r m a t i o nb a s e do nr o u g hs e t ) 开发模型，实现了对图书销售离群数据 的挖掘。 离群数据挖掘属于数据挖掘的一个分支，目前在很多方面得到应用，尤其 是在销售领域。如何在竞争激烈的市场中胜出，关键在于抓住市场销售这个环 节。如何在浩瀚的信息中获取有用的信息以便于决策的制定。以前销售信息挖 掘都是针对主要的消费群体，如：李铭的基于关联规则的多支持度挖掘在销售 数据中的应用f l 】、李春宏提出的数据挖掘在销售管理中的应用【2 】和姜云苹等提出 的基于粗糙集的关联规则挖掘在餐饮信息化中的应用【3 】，都是针对大部分数据的 关联规则的挖掘，而对于一些弱势消费群体却常常忽略，其实销售行业既要留 住主要的消费群体又要挖掘出新的潜在用户，例如，在我们的图书销售数据库 中，就动漫书这个种类，因为色彩艳丽简洁易懂，深受孩子们的喜爱，通过图 书销售信息的离群数据挖掘可以知道老人对动漫书的需求最少，是动漫书不适 合老年群体吗? 其实不然，随着年数的增长及身体等各方面的原因，部分老人 和孩子一样，同样需要简洁易懂的读物，如何针对老人的读书需求中，推出一 些老人喜爱的动漫书籍和种类，挖掘新的购书群体，是现在图书出版及销售行 业不可忽视的一个部分。 为了实现图书销售信息离群数据的挖掘，本文从粗糙集的正区域属性约简 与基于相异度的离群数据挖掘两方面着手。粗糙集是上个世纪8 0 年代初由 z p a w l a k 就g f r e g e 的边界线区域问题提出来的。对于不能确认的个体给出了新 的归类，即属于边界线区域，并且把上近似集刀( x ) 与下近似集p ( x ) 的差集等 同为这种新归类的边界线区域。众所周知，上近似集与下近似集我们是可以利 用等价关系来进行描述的，而且所得出的是确切的数学公式，这样含糊元素数 目就很容易被计算出来，从而真假二值之间的含糊程度就不难得出。人们在处 理不确切问题时具有定的常规性。粗糙集理论反映出了这点，通过对不完 全信息或知识的处理，达到解决一些不确切现象的功能。 粗糙集理论在处理含糊与不精确问题方面是一种新型的数学理论，近年来， 第l 章引言 运用的越来越广泛，在认知科学、人工智能和软计算领域、机器学习和决策分 析等方面，特别地，在医学、商业、银行、金融、市场研究、决策分析、并发 系统分析等都有重要的应用。数据库中的数据相关性的发现、数据约简、数据 意义的评估等问题一般是利用粗糙集理论来处理。 离群数据挖掘( o u t l i e rm i n i n g ) 来自于数据挖掘，是数据挖掘( d a t am i n i n g ) 的一 项重要技术，其目的是发现数据集当中一些行为异常的数据对象，这在金融欺 诈、网络监控、数据清洗等许多方面都有非常强的应用需求。到目前为止，离 群数据的各种定义还没有一个为人们所普遍接受，只是大家普遍认为h a w k i n s 的定义对离群点的本质进行了一定的揭示：“离群数据的表现与其他点如此不 同，不禁让人怀疑它是由完全不同的机制产生的。 【4 j 大部分的数据挖掘算法都试图做到离群数据的影响达到最低程度甚至排除 它们。然而要做到这点可能性是不大的，因为这些数据的噪声往往是其他数据 的信号，这就很容易引起重要的一些隐藏信息被丢失，也就是说离群数据本身 有可能是十分重要的，离群数据探测和分析是一个非常有价值的数据挖掘任务， 被称为离群数据发现。离群数据发现有着广泛的应用，例如在欺诈探测中，它 可以用于欺诈监测，探测异常的信用卡使用或电信服务。除此之外，在市场分 析中也可用于监测极低和极高收入群体的消费行为，或用于医疗分析中发现对 多种治疗手段的异常反应。 研究者们近年来在离群数据的发现问题上进行了广泛深入的研究基于距 离( d i s t a n c e b a s e d ) 的离群数据概念最先由k n o t t 等提出，也就是说如果一个点和 数据集中的大部分点之间的距离都大于某个阈值，那么这个点就是离群数据p j 。 这一概念的局限性被b r e n u i n g 等进行了仔细的研究，在此基础上还引入了另一 个概念即基于密度( d e n s i t y - b a s e d ) i y j 局部离群点的概念，它的基本思想是对一个 点和附近点的密度进行比较来考察离群程度【6 】。但是高维数据的稀疏分布使得数 据之间的距离尺度和以此为基础的区域密度失去了直观意义，因此出现了一些 新的研究，他们先将高维空间的数据投影到子空间，然后再来检测离群数据。 其中，i b m 公司的研究员a g g a r w a l 就利用演化计算的方法寻找所有投影到子空 间稀疏的小方格，把处于稀疏小方格中的数据作为离群数据 7 1 。我国复旦大学教 授魏薄提出了一些基于估计的高效子空间局部离群数据发现s l o t ( s u b s p a c e l o c a lo u t l i e rt e s t ) ，数据集在某些维上的投影的特殊的点我们就称之为子空间离 群数据，这是对数据集的纵向分割。这个算法的最大优点就是能够在预先去除 2 第1 章引言 大量完全不可能成为离群数据的对象的前提下，所有子空间中的所有局部离群 数据都能够被找到，这样就大大的减少了计算量碍1 。问题是以上提出的所有方法 都不能对其含义进行解释，只能发现离群数据。魏薄他们又在离群数据研究方 面进行了大量的研究，终于一种基于超图模型的离群数据定义提了出来，给出 了h o t ( h y p e r g r a p ho u t l i e rt e s t ) 算法，也就是通过计算每个数据的隶属度、支持 度和规模偏差来监测离群数据，并且依据窗i s l 的定义来解释离群数据含义【9 】。 目前离群数据挖掘的应用大多都只注重离群数据的挖掘，而忽略了对挖掘 出的离群数据进行分析。本文提出了一种基于相异度的离群数据挖掘算法，采 用粗糙集的正区域属性约简算法对数据进行预处理，消除一些不必要的属性， 适当减少了空间维数，再对约简后的数据集通过相异度的计算方法进行离群数 据挖掘。这样挖掘出来的离群数据剔除了一些冗余属性，简化了决策规则，使 用户使用起来更简洁与清晰。本系统的基于相异度进行离群数据挖掘的算法是 一种新的思路，既结合了基于聚类的离群数据挖掘方法，又克服了此方法的缺 点，对其进行了相应的改进，用户可根据自己的需求挖掘出自己想要的数据， 算法简单，易于理解，大大提高了算法的运行效率。 3 第2 章粗糙集原理 第2 章粗糙集原理 随着i n t c r n c t 技术的迅速发展，基于w e b 的信息数据通过积累不断膨胀， 如何解决信息量的膨胀问题就成了信息系统的重要研究课题，当然也是i n t c r n c t 必须解决的重要问题。要解决这一难题首先必须做到在不影响其原有功能的基 础上竞可能地减少信息量，把多余或者无关的信息剔除，我们称之为信息系统 约简。我们把约简后的信息重新组合，得出新的决策规则，新的决策规则有可 能和约简前的任何一条决策规则都不同，但它们却都能推理得到相似甚至相同 的结论，达到异曲同工的效果。由此可见粗糙集( r o u g hs e t ) 对数据库挖掘以 及进一步应用将产生新的影响。目前，粗糙集数据约简主要采用三种算法来实 现：基于正区域的约简算法【1 m ，基于信息熵的约简算法】和基于差别矩阵的属 性约简算法【12 。 2 1 粗糙集当前的发展情况 2 1 1 租糙集理论及其发展 人们为了解决不完整性和不确定性问题，提出了概率论、模糊集和证据理 论，粗糙集理论就是继此之后被人们提出的一个新的强大的数据分析工具。粗 糙集理论和传统的其他理论相比具有更加强大的数据分析能力，主要表现在三 个方面；一是能表达和处理残缺的信息；二是在不改变关键信息的前提条件下， 能实现对数据进行化简且求得知识的最小表达式；三是能对数据之间的依赖关 系进行准确的识别并做出评估，得出概念简单的模式；四是易于证实的规则知 识能够从经验数据中获取，例如智能控制方面就能得到广泛的应用。粗糙集的 概念自从提出以来，在理论以及应用上都是一种新的研究领域，近年来粗糙集 得到了迅速的发展。模糊集这个概念的创始人z a d e h 提出了硬计算的方法，即 通过精确的、固定以及不变的算法从而解决与表达问题。粗糙集这个软计算方 法( s o f tc o m p u t i n g ) 腰j u 好与硬计算方法相对，是一种容易处理的、鲁棒性强以及 成本较低的解决问题的方案，从而更好地与现实系统相协调。软计算方法的工 具主要有粗糙集、神经网络、模糊逻辑、信度网络、概率推理、遗传算法与其 他进化优化算法以及混沌理论等1 1 3 1 4 第2 章粗糙集原理 粗糙集这个理论与所有软计算理论之间或多或少地存在一些相似之处，如： 模糊逻辑、神经网络、概率推理、信度网络、遗传算法等，尤其是证据理论 d s ( d e m p s t e r - s h a f e r ) ，当然两者也有区别，主要表现在d s 理论通过置信和似然 函数作为主要方法，而粗糙集这个理论通过上下近似集。当然粗糙集与模糊集 这两个概念之间并不是冲突的，而是起到相互补充的作用，只是在处理问题上 采用了不同的方法而己。 粗糙集理论自提出后取得了巨大的发展，这归结于许多研究家们对该理论 以及应用进行的坚持不懈的研究。早在2 0 世纪9 0 年代初，z p a w l a k 发表了第 一本相关于粗糙集理论的专著【1 引，并且因此决定粗糙集这个理论的基础；相隔一 年，rs l o w i n s k i 又发表了相关的粗糙集应用方面的论文集【15 1 ，在国际上推动了 粗糙集这个理论及应用的发展。同年，第一届国际粗糙集学术讨论会k i e k r z 在波 兰召开，使得集合近似定义的基本思想及其应用得到了进一步的发展。1 9 9 5 年， z p a w l a k 初步的给出了粗糙集理论的概念，并概括性地阐述了其具体的研究进 展。上世纪末，第七届关于粗糙集、模糊集、数据挖掘和粒度的软计算国际会 议在日本顺利召开，对当前粗糙集、模糊集的研究现状以及发展趋势进行了全 面具体地阐述。2 0 0 0 年，第二届粗糙集和软计算的当前趋势学术会议在加拿大 成功召开。 2 1 2 粗糙集理论的研究现状 粗糙集理论的提出至今，也就二十多年的时间，却取得了巨大的发展，如 今，已经发展为人工智能领域的一个学术热点，在理论方面得到了不段的完善， 在实际应用上更是取得了惊人的成果。目前，人们对粗糙集继续进行深入的研 究，主要从以下几个方面开展 1 6 , u t l ： ( 1 ) 粗糙集理论方面的研究 对粗糙集理论的研究开展的时间不长，主要体现在以下五个方面： 粗糙集模型的推广研究 主要采取构造性方法和公理化方法来进行，粗糙集模型的推广研究一直是 粗糙集理论研究的主流方向。 粗糙集数学性质方面的研究 数学性质方面的研究也是研究的热点，主要集中在对粗糙集的代数系统、 粗糙拓扑结构等方面的研究。 5 第2 章粗糙集原理 与其他相关理论的对比研究 概率统计、模糊数学、神经网络【讳】、d s 证据理论和信息论都是处理不确定 性方法的理论，这些理论和粗糙集存在不同程度的相互渗透和互补。对它们之 间关系的研究可以促进粗糙集理论的研究 粗糙集高效算法的研究 要找出信息系统所有的约简或者最优约简是一个多项式不能确定的问题n p ( n o n d e t e r m i n i s t i cp o l y n o m i a l ) ，如今，主要对约简的启发式算法1 1 9 1 、导出规则 的增量式算法、并行算法、遗传算法以及与粗糙集有关的神经网络等领域进行 研究。 粗糙逻辑与粗糙推理研究 粗糙逻辑例的五个逻辑值是研究的重点，也就是真、假、粗糙真、粗糙假 和粗糙不相容，以及建立在其上的粗糙推理。 以上研究大部分是受应用而推动产生的，当然也有少部门是纯理论的研究 和发展。 ( 2 ) 粗糙集理论应用方面的研究 这是该理论研究的关键，前面讲到，粗糙集方法具有很强大的功能，如可 以指导数据约简、数据依赖的发现、数据的近似分类、数据重要性的评估、决 策产生算法、数据异同的发现、数据中模式的发现以及因果关系的发现等，因 此具有很广泛的应用： 数据挖掘：粗糙集方法在获取知识方面十分有效，目前已经成为数据挖掘中 的重要的一个数学工具。 医疗诊断：粗糙集方法在诊断新的病例上也有广泛运用，主要是通过对以往 的病例进行归纳，从而得出是否得病的决策规则。 模式识别：粗糙集方法还可以进行特征提取，将表征该模式的特征项提取出 来，达到模式识别的作用。 决策分析：粗糙集方法利用信息系统，即决策表来获得决策规则，实现决策 分析。 粗糙集w e b 知识发现：粗糙集方法在w e b 知识发现方面也取得了巨大的应 用。 与其它软计算方法结合：要使粗糙集发挥更大的运用，与其他处理不确定性 方法的理论的结合，也将是提高粗糙集方法应用的一种重要途径 6 第2 章粗糙集原理 2 2 粗糙集的基本概念 粗糙集的定义被很多学者所提出过，但至今一直没有那种是被人们所普遍 认同的，其工作原理主要是在保证不改变分类能力的基础上，采取知识约简， 导出问题的决策或分类规则来实现的。概括的说是一种新的处理模糊与不确定 性知识的数学工具。粗糙集理论首先是通过分类这个机制的基础来建立的，然 后将分类定义为一定空间范围上的等价关系，等价的这个关系又形成了对这个 空间的划分。其主要原理是利用被人们所知晓的信息库，将不明确或不确定性 的信息用己知的信息库中的信息来描述。粗糙集理论与其它处理该问题的理论 的最主要的区别是无需提供任何先验信息，而且与概率论、模糊数学、证据理 论等有很强的相互渗透性和互补性。 2 2 1 知识的分类 设论域u 为非空集合，r 要为论域u 的不可分辨关系，必须是u 上的二元 等价关系，那么知识库k = ( u ，r ) 就是一个关系系统。对于任意的( x ，y ) 属于u u ，如果( x ，y ) 属于不可分辨关系r ，则称对象x 与y 在知识库k 中是不可分辨的。 u 瓜构成了u 上的一个划分，它是u 上由r 生成的等价类的全体。由此可以得 出，u 上的划分与u 上的二元等价关系之间是一一对应的关系。基本集或原子 集为u 瓜中的集合。对于任意有限的基本集可定义集为它们的并和交空间。反 之为不可定义集。对于可定义集，换种说法叫做精确集，已知知识可用此表示， 可以通过知识库中进行精确的描述或定义，构成u 上的一个拓扑的所有可定义 集全体也可以得以验证。 定义2 1 设r 是u 上的一个等价关系，u r 表示r 的所有等价类构成的集 合，【x l r 表示包含元素x u 的r 等价类。知识库k = ( u ，r ) ，其中u 为非空有 限集合，称为论域，r 是u 上的一个等价关系族。 定义2 2 设r 是u 上的一族等价关系，若p 三r ，且p o ，则f lp ( p 中 所有等价关系的交集) 也是一个等价关系，称为p 上的不可分辨( i n d i s c e m i b i l i t y ) 关系，记为i n d ( p ) ，即 i n d ( p ) = ( x ，y ) e u ui f ( x ，a ) 2 f ，a ) ，va c _ p 且有 【x 】j n 妒) - n 【x r ， r p 例2 1 表2 1 所示的个体集合 咖，c ，d ，e ，0 称为论域，即所要考察的对象全体。 7 第2 章粗糙集原理 每个个体在四个属性( 流鼻涕、腰疼、体温和流感) 上对应四个取值，那么每个个 体与其对应属性取值就构成了一个元组。如果按照某个或多个属性来描述这些 个体，就可以得到不同的分类知识。 为方便起见，定义四个等价关系( 即属性) ：流鼻涕a 1 ，腰疼a 2 ，体温a 3 ，和流 感，通过这些等价关系，可以得到下面四个等价类： u a 1 = 钆b ，c ， d ，e ，f ) u a 2 = 啪，c ，d ) ， e ，f ) u a 3 = 钆d ) ， b ，e ) ， c ，0 ) u a 4 = a , d ，e ) ， b ，c ，d ) 也可以按照属性的组合来分类，例如： u a 1ua 2 = “a , b ，c ) ， d ) ， e ，d ) u a lu a 4 = a ) ， b ，c ) ， d ，e ) ， d ) 表2 i 信息表 编号流鼻涕腰疼 体温流感 a 是是 正常否 b 是是高是 c 是是很高是 d否是正常否 e 否 否高否 f 否 否很高是 通过例子得知，对论域进行分类往往可以用不同的标准，从而得出不同的概 念和抽象，有些概念是我们所需要的，而有些是没有意义的，数据挖掘就是要探寻 出对我们有用的概念，揭示出概念之间的内在联系。 2 2 2 不精确范畴，粗糙集与上、下近似集 对于我们所要讨论的论域u 上随意的一个子集x 有时x 不一定可以通过 知识库k 当中的知识去精确地得以描述，也就是说x 可能是不可以定义的集合， 这时就可以用x 关于知识库k 的一对下近似尺( ) ( ) 与上近似尺( x ) 得以近似描述。 其相关定义如下： 第2 章粗糙集原理 尺( x ) 2 u y u rl y n x 一 r ( x ) 。u y u ri y n x 中) 下近似尼( x ) 也叫做x 关于知识库k 的正区域，表示为p o s r ( ，它能解释 为那些通过已知知识来推断出确定属于子集x 的对象来组成的最大的集合，上 近似足( x ) 能解释为那些通过已知知识来推断出可能属于子集x 的对象来组成 的最小的集合。u r ( x ) 叫做x 的负域，表示为n e g r ( x ) ，它能解释为那些通过 已知知识来推断出确定不归属于x 的对象来组成的集合。尺( x ) r ( x ) 叫做边界 域，它能理解为那些通过己知知识来推断出可能归属于x 可又不能完全确定属 不属于集合x 的对象来组成的集合，表示为b nr ( ) ( ) 。同时下面的等式成立： r ( 均= p o s u ( x ) ub n r ( x ) = r x ub n r ( x ) 由定义，以下性质成立： o ) x 为r 可定义集当且仅当r i x ) = r ( x ) ( 2 ) x 为r 粗糙集当且仅当尺( x ) r ( 例2 2 在表2 2 所示的信息表中，若取属性集p = 流鼻涕，腰疼) ，x ： e 1 ，e 2 ， e 3 ) ，则有： 表2 2 信息表 病人流鼻涕腰疼体温 e l是是正常 e 2是是高 e 3 是是很高 e 4 否是正常 e 5 否否高 e 6 否是很高 u p = e 1 ，e 2 ，e 3 ， e 4 ，e 6 ， e 5 ) ) p ( 均。p o s , , ( x ) 2 c 4 ，e 6 ) p ( x ) 。 e l ，e 2 ，e 3 ，e 4 ，e d 9 第2 章粗糙集原理 n e g p ( x ) - u 。p ( ) ( ) 2 e 5 ) b n p ( x ) = p p 2 e l , l ：2 ，e 3 2 2 3 近似分类和近似分类质量 由等价关系r 定义的x 关于u 的近似精度为： r r ( x ) = lr ( x ) i | r ( x ) i 其中ir ( x ) i 干t a lr ( x ) l 表示集合x 的下近似和上近似基数，x 垂。近似精 度表明了知识x 当中确定在知识库k 当中的部分在已知知识当中的百分比。很 明显对于每一个等价关系r 与x k u 都有0 弋 r r ( l 。当近视精度r r ( x ) = l 时，知识x 的边界域是空集，也就是集合x 是r 可定义的；当近视精度r r ( x ) l 时，集合x 是不空的r 边界域，那么集合x 是r 不可定义的。 通过等价关系r 来表示的集合x 对于近似的空间u 粗糙性的测度公式为： pr ( x ) = 1 i r ( x ) i ir ( x ) i 显然，当0 pr ( x ) 1 时，x 为可定义的必须是pr ( x ) = 0 ，x 为粗糙的必 须是pr ( x ) 0 。粗糙性的测度表明了所谓知识不完全的程度。 粗糙集的理论当中也对集合类对于近似的空间描述了上近似与下近似。假 设f = x 1 ，x 2 ，x d 是通过u 的子集来构成的集合类，那么f 对于近似的空 间u 的下近似尺( f ) 与上近似尺( f ) 公式为： r ( f ) 2 尺( x 1 ) ，r ( x 2 ) ，r ( x n ) r ( f ) 2 尺( x 1 ) ，r ( x 2 ) ，r ( 墨) 通过r ，f 的近似的分类精度与近似的分类质量可分别描述为： r r ( f ) = ir ( x ，) i l 尺( 一) i f i r ( f ) = r ( x ，) l i u i 近似的分类精度表述的是当通过r 对对象进行分类时，可行的决策当中正 确的决策的一个百分比例；而近似的分类质量描述的是通过r 可以准确地划分 到f 类当中的对象的一个百分比例 1 0 第2 章粗糙集原理 2 3 基于粗糙集的属性约简 粗糙集理论的核心之：属性约简。毋庸质疑，信息系统中属性( 知识) 的重要性并不是相同的，甚至有些属性( 知识) 是冗余的。特别是当随机采集 信息系统的数据时，冗余性更高。冗余过高就会导致存储空间资源的浪费，而 且还会对正确决策制定的干扰。属性约简，能够达到丢掉知识库中的冗余属性 ( 知识) ，把知识中隐藏的关联和规则挖掘出来，使人们做出正确简洁的决策。 粗糙集理论能够在短短二十多年的时间里引起了人们的重视且得到了迅速的发 展，也正是它所提出的属性约简的思想。 就信息系统而言，人们总是追求完美，期望可以找到最小约简或全部约简。 然而这基本上是不可能完成的，因为计算约简的复杂度是和决策表的增大呈正 比的，w o n g s k m 和z i a r k o 已经证明了这一点，认为要找出一个决策表的最小 约简或全部约简是一个典型的n p 难题( n p h a r d ) 1 2 2 】，所以，我们必须努力研 究，找出更为有效的新的简化算法。 2 3 1 属性约简的概念 属性约简概括的说就是不改变信息库分类能力的前提下，剔除其中无关性 或不是很重要的信息。 知识约简中有两个极其重要的基本概念：约简( r e d u c t ) 与核( c o r e ) 。 定义2 3 设r 是一个等价关系族，r r ，如果i n d ( r ) = i n d ( r 一 r ) ，狈0 称r 在r 中是可被约去的知识；如果p - r - r ) 是独立的，则p 是r 中一个约简。 如果对任意re r 都不可约去，则等价关系族r 是独立的；否则r 是相关 的。 定义2 4r 中所有不可约去的关系称为核，由它构成的集合称为r 的核集， 记为c o r e ( r ) 。 定理2 1 2 3 1c o r e ( p ) = n r e d ( p ) ，其中r e d ( p ) 表示p 的所有约简。 定义2 5 设p 和q 都是等价关系族，如果 p o s m o ( p ) ( i n d ( q ) ) = p o s 刑, t x p r ) ( i n d ( q ) ) 则称r p 是p 上q 可约去的；否则r 是p 上q - 不可约去的。 如果p 上的每个等价关系r 都是q 不可约去的，则称p 是q 独立的或p 关 于o 独立的。 定义2 6 所有p 中q 不可约去的等价关系的集合被称为p 的q 核，记为 第2 章粗糙集原理 c o r c q ( p ) 。 定理2 21 1 9 等价关系族s e p 是p 的q 约简，当且仅当s 是p 的q 独立族， 并且有p o ss ( q ) = p o s “q ) 成立。 定理2 3 【2 3 】c o r e q ( p ) = n r e d q ( p ) ，其中r e d q ( p ) 是p 中的所有q 约简集。 2 3 2 属性约简的主要算法 2 3 2 1 基于区分矩阵的属性约简算法 1 9 9 1 年，a s h o w r o n 提出了基于区分矩阵的属性约简算法【2 4 1 ，它的主要思 路是：通过对矩阵的区分来完成对函数的区分，然后采用合取与吸取律对区分 函数进行化简。 定义2 7 令s - ( u ，八v ，f ) 是一个信息系统，i ui = n ，s 的区分矩阵m ( s ) 是 一个n x n 矩阵，其任意元素为 a ( x ，y ) = a ai f ( x ，a ) f o ，a ) ) a ( x ，y ) 是区分对象x 和y 所有属性的集合。 很明显，区分矩阵其实是一个对称的阵，因此我们在对区分矩阵的分析时 只取其下三角的部分。 首先通过区分矩阵构造出布尔函数，接着求出s 的全体约简，具体步骤如 下： ( 1 ) 计算出信息系统s 的区分矩阵m ( s ) ； ( 2 ) 通过区分矩阵m ( s ) 来构造出相关的区分函数f m ( s ) ； ( 3 ) 计算区分函数f k s ) 的最小析取范式，然后求出所有的约简。 区分矩阵的算法如下： 输入：一个目标决策系统s = ( u ，八v ，f ) ，其中u 是论域，a = cud ，c 是 条件属性集合，d 是决策属性集合。 输出：s 的属性约简及核属性。 ( 1 ) 计算u i n d ( c ) ，令c o r e = c p ，r c d u c t = ，n - l ui ，定义一个nx n 的矩阵 结构m ( n ，n ) ，并令其所有元素为m ： ( 2 ) 生成区分矩阵的伪代码如下： f o r ( i = 1 ；i = n ；i 什) f o r ( j = i + l j = n j h ) f 0 r 皿；l ；k ，- i c 玉+ + ) i f ( c k ( x 0 c k 隅) a n dd ( x i ) d ( x j ) ) 1 2 第2 章粗糙集原理 m ( ij ) 却呱i ，j ) u c k ( 3 ) 求约简及核值的伪代码如下： f o r ( i - - 1 ；i = n ；i h ) f o r ( i - - i + l j = n j + + ) i f ( m ( ij ) 1 ) c o r e = c o r e u m ( ij ) ) r e d u c t = r e d u c tf lm ( ij ) c o r e 为核值，r e d u c t 为约简。 例2 - 3 设信息系统s = ( uav ，f ) ，设u = a l ，a 2 ，a 5 ) ，a = f ，g ，h ，ij ) ，v = 0 ，1 ，2 ，如表2 3 所示。根据区分矩阵的定义，我们有如表2 4 所示的区分矩阵。 表2 3 信息系统 uf g h1 j a l 1o2l0 a 2o o 1 2l a 82o2 lo 籼oo222 a 5ll2lo 表2 4 对于表2 3 信息系统的区分矩阵 uf t 1a 2a aa 4a s a l 0 2 h ，幻 0 af f ，t l ，i j 0 4 f , i j蛐f , i j 舶 g f , g , h ，i jg g ，巧 利用逻辑中合取和析取运算，最小简化的析取范式计算如下： f u ( s ) = ( fv hv iv j ) a fa ( fv iv j ) a ga ( fv hv iv j ) a ( hv j ) a ( fv gv hv iv j ) a ( fv iv j ) a ( fv g ) a ( fv gv iv j ) _ - fa ga ( hv j ) - ( fa ga h ) v ( fa ga j ) 1 3 第2 章粗糙集原理 所以，其对应的两个约简为 r 1 = f ，g ，h ，r 2 = f ，gj 这个算法的主要优点是可以直接给出规则，但是该算法的计算复杂度为 ( o ( 2 j xl m n l g n ) ，i x l 一核、m - 条件属性个数、n - | u 1 ) ，只能处理非常小的数据，这样 区分矩阵的简化方法就得以提出。简化方法的最终目的就是要达到节省空间与 时间，使约简算法复杂度尽可能的最低，这就要从信息系统中提取关于属性值 是区分的属性并构成区分合取范式，同时，做逻辑公式的等价变化，直接得到 最小析取范式，省去区分矩阵的中间环节。除此之外，也存在其他一些改进了 的算法，都能够达到一定程度的降低算法复杂度。 除此之外，必须找出核值属性，也就是能够区分这两个样本所必须的属性， 当然也是唯一属性，通过对区分矩阵的观察，很容易发现，倘若某元素的取值 只有单个属性，那么该属性就是核值属性。因此，算法能够首先将这些属性取 出加入到约简集中，同时把修改其值为o ，然后利用区分函数计算出最小析取范 式，最后再把所有核属性加入到析取范式中的每个合取项，这样就得出了约简 结果。 2 3 2 2 基于属性重要性的约简算法 h u x 最先提出了基于属性重要性的启发式约简算法【2 5 ，2 6 1 。其主要思想是使 用核值作为初始约简，启发信息是属性重要性，并且按属性的重要性从大到小 的顺序逐个加入到约简集，直到集合是一个约简为止，该算法的优点是简单直 观，可以对较大的数据集合进行处理，可是复杂度仍然不低为( o ( m 2 n i g h ) ) ，这样 在处理大数据集合时速度相对来说比较慢。人们正在不段的研究，很多人已经 取得了些成就，提出了一些基于属性重要性的有效的改进算法。 基于信息熵的属性重要性 该方法引入了高等数学中随机变量的数学公式，从信息论的角度来考虑， 将粗糙集理论中的知识( 属性) 看作是定义在论域u 的子集组成的。代数上的随 机变量，从而引入了知识熵与互信息的概念，并给出了属性约简的新定义；从 而可以从信息熵的角度定义属性的重要性【”捌。 定义2 8 信息系统的属性集合p 的熵h ( p ) 定义为： 三l h (