（计算机应用技术专业论文）基于二进制可辨矩阵的属性约简研究.pdf

基于二进制可辨矩阵的属性约简研究 摘要 数据挖掘( d m ) 是从数据中提取人们感兴趣的、潜在的、可用的知识，并表 示成用户可理解的形式。分类是数据挖掘的一个重要分支，粗糙集方法是数据 挖掘中的重要分类技术之一。粗糙集理论是一种处理模糊和不精确知识的数学 工具，它具有很强的知识获取能力。粗糙集理论在数据挖掘中的应用是一个较 新的研究领域。由于粗糙集理论提供了严格的处理数据分类问题的数学方法， 不需要任何数据的附加信息，能够搜索数据的最小集合，可以使用定性与定量的 数据，并从数据中产生决策规则集合等优点而得到广泛的应用。 对于分类来说，并非所有的条件属性都是必要的，有些是多余的，去除这 些属性不会影响原来的分类效果，反而会提高系统潜在知识的清晰度。决策表 的属性约简就是约简决策表中的条件属性，约简后的决策表具有约简前决策表 的功能，但是约简后的决策表具有更少的条件属性。 本文主要对粗糙集理论中的二进制可辨矩阵进行研究，研究了基于二进制 可辨矩阵的知识粒度的有关理论和计算公式。利用获得的公式可计算知识的分 辨度和粒度，以及属性的重要度。并利用得出的有关理论进行决策表的属性约 简和值约简，提出了两种约简算法：一种是基于二进制可辨矩阵的属性及属性 值约简算法，该算法只要扫描一次二进制可辨矩阵，就可求得核属性和去除核属 性后，所增加的不能被正确分类的对象，从而得出核值。同时将吸收律应用于 各析取式，可求得条件属性的约简集，从而得到具有约简属性的核值表。该算 法使得属性约简和属性值约简得以一致计算，大大缩短了约简时间。 另一种是基于二进制可辨矩阵的重要度的属性及属性值约简算法( b d m s r ) ： 该算法利用二进制可辨矩阵的属性重要度作为属性选择标准，以在获取核属性 的基础上，通过逐个增加属性构成决策表的最小约简。该算法也使得属性约简和 属性值约简得以一致计算。 此外，我们设计了基于b d m s r 算法和基于二进制可辨矩阵的属性约简算法 ( b d m r ) 的原型系统，在此统一的平台上，我们通过对u c i 提供的多个标准测 试数据集进行测试，对两种算法的性能进行比较。实验证明，b d m s r 算法确实 优于b d m r 算法。 关键词；数掘挖掘，粗糙集，二进制可辨矩阵，粒度，属性约简 r e s e a r c ho fa t t r i b u t er e d u c t i o nb a s e do n b i n a r yd i s c e r n a b l em a t r i x a b s t r a c t d a t am i n i n gi st h ep r o c e s so fm i n i n gt h ei n t e r e s t i n g ，p o t e n t i a l l yu s e f u l ，a n d u n d e r s t a n d a b l ek n o w l e d g ei nd a t a c l a s s i f i c a t i o ni s a ni m p o r t a n ts u b b r a n c ho f d a t am i n i n ga n dt h em e t h o do fr o u g hs e ti so n eo ft h ei m p o r t a n tt e c h n i q u e so f c l a s s i f i c a t i o n r o u g hs e t i san e wm a t h e m a t i c a lt o o lt od e a lw i t hf u z z ya n d u n c e r t a i nk n o w l e d g e i th a ss t r o n gk n o w l e d g eo b t a i n i n ga b i l i t y i ti st h en e w r e s e a r c hd o m a i nt h a tt h et h e o r i e so fr o u g hs e ta r ea p p l i e di nd a t am i n i n g b e c a u s e t h et h e o r i e so fr o u g hs e tp r o v i d et h es t r i c tm a t h e m a t i c sm e t h o do ft h ep r o b l e mo f d e a l i n gw i t hd a t a sc l a s s i f i c a t i o n ，w i t h o u tt h ea d d i t i o n a li n f o r m a t i o no fa n yd a t a s ， t h e yc a ns e a r c hf o rt h es m a l l e s ta s s e m b l yo ft h e d a t a s ， m a yu s ed a t a so f d e t e r m i n i n gt h en a t u r ea n df i x i n gq u a n t i t ya n d a l s oc a ng e n e r a t et h er u l e a s s e m b l yo fp o l i c yd e c i s i o nf r o mt h ed a t a s ，e t c r o u g hs e th a sg o tt h ee x t e n s i v e a p p l i c a t i o n n o ta l lt h ec o n d i t i o na t t r i b u t e sa r en e c e s s a r yf o rc l a s s i f i c a t i o n ，s o m ea r e u n n e c e s s a r y d o i n ga w a yw i t ht h e s ea t t r i b u t e sw o n ta f f e c to r i g i n a lc l a s s i f i c a t i o n e f f e c t ，o nt h ec o n t r a r y ，i tw i l li m p r o v et h ea r t i c u l a t i o no ft h el a t e n tk n o w l e d g ei n s y s t e m a t t r i b u t er e d u c t i o n i s r e d u c i n g c o n d i t i o na t t r i b u t e si nad e c i s i o n t a b l e t h ed e c i s i o nt a b l ea f t e r b e i n gr e d u c e dh a st h ef u n c t i o n o ft h eo n eb e f o r e b e i n g r e d u c e d ，b u tt h ef o r m e rh a s t h el e s sc o n d i t i o na t t r i b u t e s t h ed i s s e r t a t i o ni sm a i n l yr e s e a r c h i n go n b i n a r yd i s c e r n a b l em a t r i xi nt h e t h e o r i e so fr o u g hs e ta n dr e l a t e dt h e o r i e sa n dc a l c u l a t i o nf o r m u l a sb a s e do nt h e k n o w l e d g eg r a n u l a t i o n w ec a nc a l c u l a t et h ed i s c e r n m e n td e g r e e ，g r a n u l a t i o no f k n o w l e d g ea n da t t r i b u t es i g n i f i c a n c em a k i n gu s eo ff o r m u l a so b t a i n e d w ec a na l s o g oo na t t r i b u t er e d u c t i o na n dv a l u er e d u c t i o no ft h ed e c i s i o nt a b l eu t i l i z i n gr e l a t e d f o r m u l a so b t a i n e da n dp r e s e n tt w or e d u c t i o na l g o r i t h m s ：o n ei sa t t r i b u t ea n di t s v a l u er e d u c t i o na l g o r i t h mb a s e do nb i n a r yd i s c e r n a b l e m a t r i x o n l ys c a n n i n g b i n a r yd i s c e r n a b l em a t r i xo n c e ，t h ea l g o r i t h mc a ng e tc o r ea t t r i b u t e sa n do b j e c t s t h a tc a n tb ec l a s s i f i e dc o r r e c t l y ，s ow ec a no b t a i nc o r ev a l u e s r e d u c t i o n a s s e m b l i e so fc o n d i t i o na t t r i b u t e sc a nb ea c q u i r e difw ea p p l yt h er o l eo fa b s o r p t i v e t oe v e r yd i s j u n c tn o r m a lf o r m ，s ow ec a ng e tac o r ev a l u et a b l eh a v i n ga t t r i b u t e s w h i c ha r er e d u c e d t h ea l g o r i t h mm a k e st h a ta t t r i b u t er e d u c t i o na n di t sv a l u e r e d u c t i o na r ec a l c u l a t e di d e n t i c a l l y ，s oi ts h o r t e n st i m eo fr e d u c t i o ng r e a t l y t h eo t h e ri st h ea t t r i b u t ea n di t sv a l u er 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 s i g n i f i c a n c eo fb i n a r yd i s c e r n a b l em a t r i x ( b d m s r ) ：o nt h eb a s i co fg e t t i n gc o r e a t t r i b u t e s ，t h es m a l l e s tr e d u c t i o na s s e m b l yo fad e c i s i o n t a b l ei sf o r m e db y i n c r e a s i n gaa t t r i b u t eo n eb yo n eu t i l i z i n ga t t r i b u t e s i g n i f i c a n c eo ft h eb i n a r y d i s c e r n a b l em a t r i xa sac r i t e r i o no fa t t r i b u t es e l e c t i o n t h ea l g o r i t h mm a k e st h a t a t t r i b u t er e d u c t i o na n da t t r i b u t ev a l u er e d u c t i o na r ec a l c u l a t e di d e n t i c a l l y 。t o o i na d d i t i o n ，w ed e s i g n e dap r o t o t y p es y s t e mb a s e do nb d m s ra l g o r i t h m m o d e la n da t t r i b u t er e d u c t i o na l g o r i t h mm o d e lb a s e d0 1 1 _ b i n a r yd i s c e r n a b l e m a t r i x ( b d m r ) o nt h i su n i f o r mf l a t f o r m ，w ec o m p a r e dt h e b d m s ra l g o r i t h m a n db d m ra l g o r i t h mb yu s i n gt h es t a n d a r du c ld a t as e t s f r o mt h ee x p e r i m e n t ，w e c a ns e et h eb d m s ra l g o r i t h mi ss u p e r i o rt ob d m ra l g o r i t h mi n d e e d k e y w o r d s ：d a t a m i n i n g ，r o u g hs e t ，b i n a r y d i s c e r n a b l e m a t r i x ， g r a n u l a t i o n ，a t t r i b u t e r e d u c t i o n 插图清单 图l ，l 知识发现过程示意图3 图5 1 原型系统组成图3 5 图5 2 原型系统主界面3 6 图5 3 数据一致性检验结果3 6 图5 4 求得了核属性和其核值以及一个约简了的属性集3 7 图5 ，5 删去的属性列3 7 幽5 6 经预处理后的数据表3 8 插表清单 表2 1 决策表1 1 4 表2 2 消去属性b ，c 后的决策表。1 5 表2 3决策表2 1 6 表2 4 表2 ，3 的分辨矩阵1 7 表2 5 将包含核属性的元素项修改为0 后的分辨矩阵1 7 表3 1 信息系统1 2 l 表3 2 表3 1 的分辩矩阵2 1 表3 3 表3 1 的二进制可辨矩阵2 4 表3 4决策表的二进制可辨矩阵2 4 表4 1 决策表3 ，2 6 表4 2 表4 ，l 的二进制可辨矩阵2 7 表4 3 决策表的核值表2 9 表4 4 信息系统2 ，。3 l 表4 5 表4 4 的二进制可辨矩阵3 2 表4 6 决策表4 4 的二迸制可辨矩阵3 2 表5 1 两种算法运行的响应时间一4 0 表5 2两种算法获得的属性约简集中的属性个数4 0 独创性声明 本人声则所旱交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所l f 除了文巾特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果也不包含为获得 盒鳇王些态堂或其他教育机构的学位或证书而使用过的 材料。与我一同t 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：之乏j ) 一乏 签字日期：厶一年办 学位论文版权使用授权书 本学位沦文作者完全了解佥罂王些友坐有关保留、使用学位论文的规定有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金魍王 些去堂可以将学位论文的全部或部分内容编入有关数据摩进行检索。可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：注0 ) 兹 签字日期：撕f 角2 - 日 学位论文作者毕业后去向： 工作单位：安徽丁业大学计算机学院 通讯地址：安徽t 业大学计算机学院 导师签名 乏t 签字日期：彩年9 1 乙日 电话；0 5 5 5 - 3 2 7 3 9 7 6 邮编：2 4 3 0 0 2 致谢 衷心感谢我的导师王浩教授在整个论文阶段给予的悉心指导和帮助。王老 师严谨治学、丌拓创新的学术作风，平易近人的高尚品德，勤勉踏实的工作态 度，对我在做人、治学、工作等多方面产生了极大影响，将使我终身受益。正 是由于受导师的影响，我对科学研究产生了浓厚的兴趣，导师渊博的学识、对 新事物敏锐的洞察力以及勇于拓新的精神永远值得我学习。在此，再一次向导 师致以诚挚的谢意。 另外，在研究生期间，我还得到了许多老师和同学的热心帮助和指导，在 此一并表示感谢! 最后，感谢所有对论文提出宝贵意见的老师和同学，感谢在百忙之中评阅 论文和参加论文答辩的各位专家。 作者：汪小燕 2 0 0 6 年5 月1 8 日 1 i 数据挖掘简述 第一章数据挖掘 l - l _ l 数据挖掘的发展与现状 数据库中发现知识( k d d ) 一词首次出现在1 9 8 9 年举行的第十一届国际联 合人工智能学术会议上。到目前为止，由美国人工智能协会主办的k d d 国际研 讨会已经召开了8 次，规模由原来的专题讨论会发展到国际学术大会，研究重 点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多 种学科之间的相互渗透。1 9 9 9 年，亚太地区在北京召开的第三届p a k d d 会议收 到1 5 8 篇论文，空前热烈。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率 先在1 9 9 3 年出版了k d d 技术专刊。并行计算、计算机网络和信息工程等其他领 域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论，甚至到了 脍炙人口的程度。 目前，在i j c a i 、a a a i 、v l d b 、a c m s i g m o d 等代表人工智能与数据库技术 研究最高水平的国际学术会议上，对k d d 的研究都占有较大的比例，k d d 已经 成为当今计算机科学与技术研究、应用的热点领域之一。在数据挖掘方面还有 更多的国际会议，如p a k d d 、p k d d 、s i a m d a t am i n i n g 、( i e e e ) i c d m 、d a w a k 、 s p i e - d m 等等。 在国外有许多研究机构、公司和院校从事数据挖掘工具的研究与开发，此 外，在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g e d is c o v e r yn u g g e t s 最为权威( h t t p ：w w w k d n u g g e t s c o m s u b s c r i b e h t m l ) 。 在网上还有许多自出论坛，如d me m a i lc 1u b 等。目前，世界上比较有影响的 典型数据挖掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n t m i n e r 、s g i 公司的s e t m i n e t 、s p s s 公司的c i e m e n t i d e 、s y b a s e 公司的w a r e h o u s e s t u d i o 、r u le q u e s tr e s e a r c h 公司的s e e 5 、还有c o v e r s t o r y 、e x p l o r a 、 k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d b m i n e r 、q u e s t 等。 随着k d d 在国际上的兴起，我国也积极地开展了相应的研究和应用。1 9 9 3 年国家自然科学基金首次支持对该领域的研究项目。目前，国内的许多科研单 位和高等院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华 大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中， 北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北 京大学也在丌展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大 学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开 采算法的优化和改造；合肥工业大学开展了基于粗糙集合理论的概念格模型研 究，南京大学、四川大学和上海交通大学等单位探讨、研究了非结构化数据的 知识发现以及w e b 数据挖掘，等等。最近，g a r t n e rg r o u p 的一次高级技术调 查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大 关键技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点 的十大新兴技术前两位。根据最近g a r t n e r 的h p c 研究表明，“随着数据捕获、 传输和存储技术的快速发展，大型系统用户将更多地需要采用新技术来挖掘市 场以外的价值，采用更为广阔的并彳亍处理系统来创建新的商业增长点。” 1 1 2 数据挖掘的基本概念 自2 0 世纪6 0 年代以来，数据库和信息技术已经从原始的文件处理演化到 复杂的、功能强大的数据库系统。数据库系统已由7 0 年代的关系数据库发展 到如今的数据仓库，同时数据管理信息检索及数据分析工具也由原来的联机事 务处理o l t p 发展到现在的联机分析处理o l a p 。随着数据库技术的迅速发展以 及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的数据背后隐 藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利 用这些数据。目前的数据库系统可阻高效地实现数据的录入、查询、统计等功 能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发 展趋势。缺乏挖掘数据背后隐藏知识的手段，导致了“数据爆炸但知识贫乏” 的现象。 对于这些海量的、不断增长的数据来说，如何通过对数据对象之间关系的 分析，提取出隐含在数据对象中的模式( 即知识) ，已是迫在眉睫。正是由于 实际工作的需要和相关技术的发展，丰富的数据带来了对强有力的数据分析工 具的需求，这样数据挖掘技术( d a t am i n i n g d m )便应运而生了”1 。数据 挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在 其中的，人们事先不知道的，但又是潜在有用的信息和知识的过程。它是一门 涉及面很广的交叉学科，包括机器学习、数理统计、神经网络、数据库、模式 识别、粗糙集、模糊数学等相关技术。 由于数据挖掘是一门受到来自各种不同领域的研究者关注的交叉性学科， 因此导致了很多不同的术语和名称。其中，最常用的术语是”知识发现”和”数据 挖掘”。相对来讲，数据挖掘主要流行于统计( 最早出现于统计文献中) 、数据 分析、数据库和管理信息系统等领域；而知识发现则主要流行于人工智能和机 器学习界。 1 ，1 3 数据挖掘与k d d 的比较 一般认为数据挖掘是数据库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 过程的核心部分，即将k d d 中进行知识发现的阶段称为数据挖掘( 如图1 1 所示) ， 2 数据挖掘是k d d 最关键的步骤，也是技术难点所在。所以某些应用领域对数据挖掘与 k d d 不加区分地使用，某种意义上二者可看作同一个概念。 图1 1 知识发现过程示意图 1 1 4 数据挖掘与联机分析处理( o l a p ) 的比较 联机分析处理o 。“( o n 一1 i n ea n a l y t ic a lp r o c e s s i n g 一0 l a p ) 也是近几年发 展起来的一个热门技术，由多维数据库( m u l t i d i m e n s i o n a ld a t ab a s e ) ” 和数据立方体( d a t ac u b e ) ”。”支持。数据立方体以多维方式对数据建模和观 察，每个维表示某一个属性满足不同条件的值，它是现有的数据库管理系统的 检索、查询、报表功能和多维分析、统计分析方法的综合的工具。 o l a p 是决策支持领域的一部分。传统的查询和报表工具是告诉我们数据库 中都有什么( w h a th a p p e n e d ) ，o l a p 则更进一步告诉我们下一步会怎么样( w h a t n e x t ) 、和如果我采取这样的措施又会怎么样( w h a ti f ) 。用户首先建立一个 假设，然后用o l a p 检索数据库来验证这个假设是否正确。比如，一个分析师想 找到什么原因导致了贷款拖欠，他可能先做一个初始的假定，认为低收入的人 信用度也低，然后用o l a p 来验证他这个假设。如果这个假设没有被证实，他可 能去察看那些高负债的账户，如果还不行，他也许要把收入和负债一起考虑， 一直进行下去，直到找到他想要的结果或放弃。而且在知识发现的早期阶段， o l a p 工具还有其他一些用途，可以帮人们探索数据，找到哪些是对一个问题比 较重要的变量，发现异常数据和互相影响的变量。这都能帮我们更好的理解数 据，加快知识发现的过程。 数据挖掘与o l h p 不同的地方“1 是，数据挖掘不是用于验证某个假定的模式 ( 模型) 的丁f 确性，而是在数据库中自己寻找模型。它在本质上是一个归纳的 过程。比如，一个用数据挖掘工具的分析师想找到引起贷款拖欠的风险因素。 数据挖掘工具可能帮他找到高负债和低收入是引起这个问题的因素，甚至还可 能发现一些分析师从来没有想过或试过的其他因素，比如年龄。 总之，o l a p 是一种验证型工具，数据挖掘则是一种挖掘型工具，它能自动 地发现隐藏在数据中的模式，是现有的人工智能、统计学等成熟技术在数据库 领域的应用。从数掘分析的角度来看，o l a p 位于较浅的层次，而数据挖掘则处 于较深的位置。如果按照e f c o d d 的数据分析模型来区分“1 ，则应该说o l a p 实现了解释模型和思考模型，数据挖掘实现了公式模型，两者是相辅相成的。 1 1 5 数据挖掘与专家系统的比较 有时，使用数据挖掘的方法来解决问题是不可行的。一个明显的情况是缺 乏优质的数据，在数据挖掘不可行时，找到一个或多个能为所感兴趣问题给出 解决方案的人是可能的。有能力解决一个或多个困难问题的人通常称为该领域 的专家。如：能够快速诊断疾病的医生，能够及时做出决策的执行官。专家通 过教育和经验获取技能。多年的经验有助于专家发展技能，使他们能够快速并 有效地解决问题。 专家系统”2 。是一组程序软件。它处理的问题是本领域的专家才能处理的 复杂问题。它收集该领域专家的知识，以推理计算模型模拟人类专家分析处理 问题，得出和人类专家一样的结论。显然，专家系统要有一个知识库“记住” 人类专家的知识。还要有一个推理机，可根据输入的要求解问题，按知识库中 的知识( 事实和规则) 推导出结论。机器是不认识任何数和知识的，怎么能推 导呢? 基本原理是它能作基于谓词逻辑的符号演算，即它认识符号以及符号出 现的次序，会到库中查寻匹配并作相应置换，以及简单的逻辑运算。 专家系统是一种智能的计算机程序，它能够运用知识进行推理，解决只有 专家彳能解决的复杂问题。也就是说，专家系统是种模拟专家决策能力的计 算机系统。专家系统是以逻辑推理为手段，以知识为中心解决问题的。专家 系统的架构”为：知识库( k n o w l e g eb a s e ) 储存专家用以解决问题的知识。推理 机( i n f e r e n c em e c h a n i s m ) 用以控制推理过程。用户接口( u s e ri n t e r f a c e ) 提供 用户与专家系统的接口。解释机( e x p l a n a t i o nm e c h a n i s m ) 提供用户友善的解释 说明及咨询功能。 顾名思义，数据挖掘就是从大量的数耀中挖掘出有用的信息。它是根据人 们的特定要求，从浩如烟海的数据中找出所需的信息来，供人们的特定需求使 用。一句话，数据挖掘与专家系统的区别在于，前者为面向事实，后者为面向 经验。 1 2 数据挖掘的主要步骤 数据挖掘可粗略地理解为三部曲：数据准备( d a t ap r e p a r a t i o n ) 、数据 挖掘，以及结果的解释评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 。 数掘挖掘一般分为以下几个主要步骤“” ( 1 ) 数据收集 大量丰富的数据是数据挖掘的前提，没有数据，数据挖掘也就无从做起。因 此数据收集是数据挖掘的首要步骤。数据可以来自于现有事务处理系统，也可 以从数据仓库中得到。 ( 2 ) 数据整理 数据整理是数据挖掘的必要环节，由数据收集阶段得到的数据可能有一定 的污染，表现在数据可能存在自身的不一致性或者有缺失数据的存在，等等。因 此，数据的整理是必须的，同时，通过数据整理，可以对数据做简单的泛化处 理，从而在原始数据的基础之上得到更为丰富的数据信息，进而便于下一步数 据挖掘的顺利进行， ( 3 ) 数据挖掘 利用各种数据挖掘方法对数据进行分析。 ( 4 ) 数据挖掘结果的评估 数据挖掘的结果有些具有实际意义，面另一些没有实际意义，或是与实际 情况相违背，这就需要进行评估。评估可以根据用户多年的经验，也可以直接 用实际数据来验证模型的正确性，进而调整挖掘模型，不断重复进行数据挖掘。 ( 5 ) 分析决策 数据挖掘的最终目的是辅助决策，决策者可以根据数据挖掘的结果，结合 实际情况调整竞争策略等。 总之，数据挖掘过程需要多次的循环反复，才有可能达到预期的效果。 1 3 数据挖掘的方法 数据挖掘的方法可孝日分为：统计方法“】、机器学习方法】、神经网络方 法和数据库方法儿“。统计方法中，可细分为：回归分析( 多元回归、自回归 等) 、判别分析( 贝叶斯判别、费歇尔判别、非参数判别等) 、聚类分析( 系 统聚类、动态聚类等) 、探索性分析( 主元分析法、相关分析法等) 、以及模 糊集、粗糙集、支持向量机等。机器学习中，可细分为：归纳学习方法( 决策 树、规则归纳等) 、基于范例的推理c b r 、遗传算法、贝叶斯信念网络等。神 经网络方法，可绍分为：前向神经两络( b p 算法等) 、自组织神经网络( 自组 织特征映射、竞争学习等) 等。数据库方法主要是基于可视化的多维数据分析 或o l a p 方法，另外还有面向属性的归纳方法。 现介绍以下几种主要的数据挖掘方法： ( 1 ) 决策树方法 数据挖掘中决策树【19 , 2 0 1 是一种经常要用到的、可以用于分析数据的技术， 同样也可以用来做预测。利用信息论中的互信息( 信息增益) 寻找出数据集中具 有最大信息的字段，建立决策树中的每一个结点，再根据字段的不同取值建立 捌的分支的过程，即建立决策树。决策树提供了种展示类似在什么条件下会 得到什么值这类规则的方法，决策树很擅长处理非数值型数据，这与神经网络 只能处理数值型数据比起来，就免去了很多数据预处理工作。国际上最有影响 的决策树方法是q u i n l a n 研究的i d 3 方法。 ( 2 ) 神经网络方法 神经网络2 1 , 2 2 1 近年来越来越受到人们的关注，因为它为解决大复杂度问 题提供了一种相对来说比较有效的简单方法。神经网络可以很容易解决具有上 百个参数的问题( 当然实际生物体中存在的神经网络要比我们这里程序模拟的 神经网络要复杂的多) 。神经网络常用于两类问题：分类和回归。 在结构上，可以把一个神经网络划分为输入层、输出层和隐含层。输入层 的每个节点对应一个预测变量。输出层的节点对应目标变量，可有多个。在输 入层和输出层之间是隐含层( 对神经网络使用者来说不可见) ，隐含层的层数 和每层节点的个数决定了神经网络的复杂度。 神经网络模拟人脑神经元结构，以m p 模型和h e b b 学习规贝i j 为基础，建立 了三大类神经网络模型。 前馈式网络，以反向传播模型、函数型网络为代表，用于预测、模式识 别等方面。 反馈式网络，以h o p f ie l d 离散模型和连续模型为代表，分别用于联想记 忆和优化计算。 自组织网络，以a p t 模型，k o h o o i l 模型为代表，用于聚类。 ( 3 ) 模糊论方法 利用模糊集合理论”对实际问题进行模糊评判、模糊决策、模糊模式识别 和模糊聚类分析。模糊性是客观存在韵，系统的复杂性越高，模糊性越强，这 是z a d e h 总结出的互克性原理。 ( 4 ) 遗传算法 遗传算法“1 是一种抽象于生物进化过程的基于自然选择和生物遗传机制 的优化技术。它可被看作寻优和优化的过程。它首先将问题参数按某种形式进 行编码，编码后的位串称作个体。随机生成n 个染色体构成初始种群，再根据 预定的函数对每个染色体分配，使得性能较好的染色体具有较高的适应值。之 后，选择出适应值高的染色体进行复制，通过遗传算子( 选择，交叉，变异) ， 产生一群新的更适应环境的染色体，形成新的种群。这样一代一代不断繁殖、 进化，最后收敛到一群最适应环境的个体，求得问题的最优解。 遗传算法由三个基本算子组成： 选择，是指从一个旧种群( 父代) 中选出生命力强的个体，产生新种群( 后 代) 的过程。 交叉，是选择两个不同的个体部分进行交换，形成新韵个体 变异，对某些个体的某些基因进行变异。 遗传算法已在优化计算和分类机器学习等方面发挥了显著的作用。 ( 5 ) 粗糙集方法 粗糙集理论”“是八十年代初z ，p a w l a k 针对g f i r e g e 的边界域思想提出 的，基于给定训练数掘内部的等价类的建立，用对上下近似集台来逼近数据 库中的不精确概念。用于分类，可以发现不准确数据或噪声数据内在的结构联 系：用于特征归约，可以识别和删除无助于给定训练数据分类的属性：用于相关 分析，可以根据分类任务评估每个属性的贡献或意义。其主要思想是将数据库 中的属性分为条件属性和决策属性，对数据库中的实例根据各个属性不同的属 性值分成相应的子集。在保持分类能力不变的前提下，通过知识约简，导出问 题的决策或分类规则。 粗糙集理论和模糊集理论都是针对不确定性问题的，且它们既相互独立又 相互补充用理论来处理不确定性问题的最大优点在于它不需要关于数据的预 先或咐加的信息，且粗糙集方法容易掌握和使用，它最早被用于医学和工业知识 库中。 ( 6 ) 可视化技术 可视化技术“”采用直观的图形方式将信息模式、数据的关联成趋势呈现给 用户( 决策者) 以便用户交互地分析数据关系。例如，把数据库中的多维数据变 成多种图形，这对揭示数据的状况、内在本质及规律性起了很大作用。 数据挖掘是数据领域中一个高速发展的分支，它应用于许多不同的领域， 其它领域的知识和理论也广泛地应用到数据挖掘的研究中。结合实际需要，往 往能开发出更高效的算法。 1 4 数据挖掘的分类 从数据挖掘的不同角度可以得到不同的分类标准，常见的有以下几种分类 标准：挖掘任务，挖掘对象，挖掘方法。根据数据挖掘的对象分，有如下若 干种数据源：关系数据库、面向对象数据库、空间数据库、时态数据库、文本 数据源、多媒体数据、异质数据库、遗产( 1 e g a c y ) 数据库，以及w e b 数据 源。根据挖掘方法可粗略的分为：机器学习法、统计方法、神经网络方法、数 据库方法等。下面我们介绍目前用的最广泛的根据挖掘任务分类”的情况。 ( 1 ) 分类和预测 分类是一个找出描述并区分数据类或概念的模型( 或函数) ，以便能够使用 模型预测类标记未知的对象类。导出模型是基于对训练数据集( 即其类标记已知 的数据对象) 的分析。 ( z ) 聚类分析 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类是在事先 不规定分组规则的情况下，将数据按照其自身特征划分成不同的群组。要求是 在不同群组的数据之间要有明显差别，而每个群组内部的数据之间尽量相似。 聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类 技术主要包括传统的模式识别方法和数学分类学。 ( 3 ) 关联分析 所谓关联分析就是发现事物之间有意义的联系和规则。数据关联是数据库 中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种 规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析 的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数， 即使知道也是不确定的，因此关联分析生成的规则带有可信度。 ( 4 ) 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者 描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有 对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等， ( 5 ) 序列模式 序列模式”“1 数掘挖掘是与关联规则数据挖掘相类似的一个重要问题，但是 它更侧重于分析事物之间的前后( 因果) 关系。正如哲学中的“联系”包含各 种联系：相似性、因果性等等。现在已经广泛应用于股市波动、生产流程动态 追踪、科学实验、医学疗程分析等方面。它强调的是数据之间在时间上的连贯 性。 ( 6 ) 偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。 偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结 果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找 观测结果与参照值之间有意义的差别。 1 5 基于粗糙集的数据挖掘 利用粗糙集理论来处理数据挖掘有着较传统挖掘工具不具有的优点。粗糙 集理论处理数据不需要对数据的了解，即不再需要对数据的先验信息：比如说统 计学中的概率分布、d e m p s t e r s h a f e r 理论中的概率赋值、或者模糊集理论中 的隶属度或概率值；基于粗糙集的数学模型更易于被理解，针对一个特定的大型 数据库，利用粗糙集理论比其它理论更容易建立数学模型。许多实验表明，对于 同一个数据集，在粗糙集理论工具下进行处理，最终得到的信息更简单、更准确、 更易于被决策者接受和理解。 基于粗糙集的数据挖掘算法实际是对决策表进行约简的过程，这个处理过 程具体如下： ( 1 )删除决策表中重复的实例； ( 2 )删除多余的属性； ( 3 )删除每个实例中多余的属性值： ( 4 )求出最小约简： ( 5 )由最小约简求出逻辑规则。 粗糙集理论是一种处理不确定和不精确问题的新型数学工具，为数据挖掘 提供了一条崭新的途径。粗糙集理论在数据挖掘中的应用研究目前已成为信息 科学中的一个研究热点，其发展空间广阔。 1 6 本文的组织 本文主要对粗糙集理论中的二进制可辨矩阵进行研究，研究了基于二进制 可辨矩阵的知识粒度的有关理论和计算公式。利用获得的公式可计算知识的分 辨度和粒度，以及属性的重要度。并利用得出的有关理论进行决策表的属性约 简和值约徜，提出了两种约简算法：一种是基于二进制可辨矩阵的属性及属性 值约简算法，另一种是基于二进制可辨矩阵的重要度的属性及属性值约简算法 ( b d m s r ) 。 本文的内容安排如下： 第一章系统地介绍了数据挖掘的有关理论，包括数据挖掘的发展与现状、 数据挖掘的基本概念、数据挖掘与k d d ，o l a p 等的比较、数据挖掘的主要步骤及 其方法、分类以及基于粗糙集的数据挖掘。 第二章介绍粗糙集理论。重点介绍了决策表属性约简中的一般约简算法和 基于分辨矩阵和逻辑运算的属性约简算法。 第三章主要介绍基于分辨矩阵的知识粒度与计算，并利用二进制可辨矩阵 讨论知识的粒度的计算及其应用。 第四章主要提出了两种约简算法：一种是基于二迸制可辨矩阵的属性及属 性值约简算法，另一种是基于二进制可辨矩阵的重要度的属性及属性值约简算 法( b d m s r ) 。介绍了算法的基本思想。算法描述以及应用。 第