（农业机械化工程专业论文）基于粗糙集的数据挖掘约简算法的研究与应用.pdf

摘要 基于粗糙集的数据挖掘约简算法的研究与应用 农业机械化专业硕士研究生阎桦 指导教师余建桥教授 ( 摘要) 随着信息技术的高速发展，数据库应用的规模不断扩大，原有的数据库处理方法己经远 远不能满足现实需要，数据挖掘正是为迎合这种需要而产生并迅速发展起来的一种新的数据 处理技术。它能够在没有明确假设的前提下，自动地从数据中抽取隐含的、具有潜在应用价 值的信息，经过检验和验证，然后返回对用户最有用的结果。目前数据挖掘已经被越来越多 的领域所采用，具有广泛的应用前景。 在数据挖掘的过程中，存在大量冗余数据影响我们的决策，粗糙集理论在得到的决策规 则和推理过程方面是最有利的工具。它不但可以在不影响数据表达信息的前提下使原来的数 据量大为减少( 数据浓缩) ，而且还可以产生决策规则，从而挖掘出数据中的有效模式。粗 糙集理论不同于其他处理不确定性问题的理论，如概率方法、模糊集方法和证据理论方法等， 它无需提供任何所需处理数据集合之外的先验信息。 本文首先对基于粗糙集的数据挖掘过程数据预处理、约简及规则获取进行研究。其 次，对挖掘过程中的核心问题约简，进行了深入的探讨，对目前的约简算法展开分析， 指出了其中存在的问题。 其次，针对目前较多的启发式算法为了减少时间代价，无法得到决策表最小约简，且时 间复杂度与空间复杂度仍然在i u i2 ( i u i 为决策表中记录数) 的问题，提出一种既可以降低 时间复杂度和空间复杂度，又可以求得最小约简的算法一基于d h i ( 区分矩阵属性约简改 进算法) 的改进算法。主要内容如下： 1 对d m i 算法进行了分析，举例说明了该算法对于不相容决策表的不正确性：然后给出 了一种对相容决策表与不相容决策表都适合的改进约简算法。 2 针对目前的约简算法必须反复遍历决策表各个数据项，使时间复杂度、空间复杂度 较高的现状进行了改进，改进后的算法不用遍历完一次决策表就可以实现约简，大大减少了 算法的时间和空间复杂度。 3 突出了属性值约简对数据约简的重要性，真正实现了决策表的最简化。并提出改进 的值约简算法，时间复杂度在原有基础上大大减少。 4 将3 个对约简的改进思想融合在一个算法当中，成为真正意义上的约简算法，实现了 属性约简和属性值约简的一体化。同目前普遍存在的用不同算法独立处理属性约简和属性值 约简的方法相比，本算法的空间复杂度大大减少。因此，本算法具有很强的实践意义和应用 前最。 5 算法的整个约简过程都是针对所有对象同时进行，真正考虑到了齄个决策类对约简 的意义，避免了发生求得局部最优的错误。 西南大学硕士论文 经对u c i 中数据集的实验，结果证明了改进算法的有效性与高效性。 最后，将本文提出的约简改进算法用于农业水价改革与农民承受能力研究课题的研 究。首次提出将数据挖掘用于农业水资源管理领域，并成功建立模型，得到的规则和一线专 家的经验相吻合，证实了该算法的先进性和实用性。 关键词：数据挖掘，粗糙集，约简，区分矩阵 l l a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , t h ea p p l i c a t i o no fd a t ab a s eb e c o m e m o r ea n dm o r ew i d e l yi nd i f f e r e n ta r e a s ，a n dt h ep r e v i o u sp r o c e s s i n gm e t h o d so fd a t ab a s ec a n t m e e tt h en e e d sa n ym o r e ，d a t am i n i n gi san e wt e c h n o l o g yo f d a t ap r o c e s s i n gt om e e tt h en e e d s i t c a nt a k eo u tt h ep o t e n t i a lu s e f u lo n e sa m o n yag r e a td e a lo fi n f o r m a t i o na u t o m a t i c a l l y , a n dt e s t a n dv e r i f yt h e m ，r e t u r n i n gt h em o s tu s e f u lr e s u l t st ot h eu s e r sw i t h o u ta n ye x p l i c i th y p o t h e s e s t h i st e c h n o l o g yi sw i d e l yu s e di nm o r ea n dm o r ea r e a s ；i th a sab r i g h tf u t u r ei na p p l i c a t i o n t h er o u g hs e tt h e o r ys o l v e st h ep r o b l e mo fag r e a td e a lo fr e d u n d a n td a mt h a ti n f l u e n c eo u r d e c i s i o nb yt h er u l eo fd e c i s i o na n dt h ep r o g r e s so fr e a s o n i n g i tc a l ln o to n l yd e c r e a s et h ed a t a a m o u n t ( d a t ac o n c e n t r a t i o n ) ，b u ta l s op r o d u c ed e c i s i o nr o l e st ot a k eo u tt h ee f f l c i e n tm o d e l s a m o n gd a t au n d e rt h ec o n d i t i o no fn o tc h a n g i n gt h ed a t ai n f o r m a t i o n u n l i k eo t h e rt h e o r i e st o s o l v i n gi n e x p l i c i tp r o b l e m s ，r o u g hs e tt h e o r yd o e s n tn e e dt h ep r e v i o u sv e r l f yi n f o r m a t i o ne x c e p t t h ed e m a n d i n gd a t as e tt op r o c e s s i n g i nt h i sp a p e gf i r s t l y , t h es m d yo nt h ep r o g r e s so fd a t am i n i n g ( t h ed a t ap r o c e s s i n gi n a d v a n c e ，r e d u c t i o na n dt h er u l e s ) b a s e do nr o u g hs e tw a sc o n d u c t e d a n dt h ek e yt o p i ci sa t t r i b u t e r e d u c t i o nw i t hw h i c haf u r t h e rs t u d yw a sc o n d u c e d ，a n a l y z i n gt h ea l g o r i t h mo f a t t r i b u t er e d u c t i o n 也a t i s p o p u l a r n o w a d a y s a n d p o i n t i n go u t t h ee x i s t i n g p r o b l e m s s e c o n d l y , a l la l g o r i t h mb a s e do nd m lw a sp u tf o r w a r d e dt h a tc a nn o to n l yd e c r e a s et h e c o m p l e x i t yo f t i m ea n ds p a c e ，b u ta l s og e tt h em i n i m i z ea t t r i b u t er e d u c t i o n t h em a i nc o n t e n t sa r e t h ef o l l o w i n g ： 1 t h ea n a l y s i so nd i s c e m i b i l i t ym a t r i x ：s h o w i n gt h i sa l g o r i t h mi si n c o r r e c tt oi n c o m p a t i b l e r e s o l u t i o nl i s t sw i t he x a m p l e s ，a n dp u t t i n gf o r w a r d i n ga ni m p r o v i n ga l g o r i t h mo fa t t r i b u t e r e d u c t i o ns u i t i n gf o rc o m p a t i b l er e s o l u t i o nl i s t sa n di n c o m p a t i b l eo n e s 2 a i m i n ga tt h ew e a k n e s so fc u r r e n ta 越r i b u t er e d u c t i o nt h a th a v et or e a da l ld a t ai t a m so f r e s o l u t i o nl i s t s ，c o m p l e x i n gt h et i m ea n ds p a c e ，a ni m p r o v i n ga l g o r i t h mw a sp u tf o r w a r d e dt o s i m p l i f yt h et i m ea n ds p a c eb yo n l yr e a d i n gr e s o l u t i o nl i s t so n c e 3 s h o w i n gt h ei m p o r t a n c eo fa t t r i b u t ev a l u er e d u c t i o nt o d a t ar e d u c t i o n ，p r a c t i c a l l y r e a l i z i n gt h es i m p l i c i t yo f r e s o l u t i o nl i s t s a n dp u t t i n gf o r w a r d e dt h ei m p r o v e da l g o r i t h mo f v a l u e a t t r i b u t er e d u c t i o nt h a td e c r e a s e st h ec o m p l e x i t yo f t i m eg r e a t l y 4 r e a l i z i n gt h eu n i f yo f 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 nb yf u s i n gt h et h r e e i m p r o v e dt h o u g h t so fr e d u c t i o nt o g e t h e r , a n dt h a ti st h er e a la l g o r i t h mo fr e d u c t i o ni n d e e d c o n s i d e r i n gt h es i g n i f i c a n to ft h ew h o l e r e s o l u t i o nt y p e ，t h ew h o l er e d u c t i o np r o g r e s so f a l g o r i t h mw a sc o n d u c t e da i m i n ga ta l lt a r g e t s c o m p a r i n gw i t ht h ec u r r e n tm e t h o d st h a tp r o c e s s s e p a r a t e l ya t t r i b u t e sr e d u c t i o na n d a t t r i b u t ev a l u er e d u c t i o nw i t hd i f f e r e n t a l g o r i t h m ，t h i s a l g o r i t h md e c r e a s e dt h es p a c ec o m p l e x i t yg r e a t l y t h e r e f o r e ，t h i sa l g o r i t h mh a sg r e a tp r a c t i c e s i g n i f i c a n ta n db r i f g h tf u t u r eo f a p p l i c a t i o n 5 w j 也t h er e a lc o n s i d e r a t i o no f t h em e a n i n go f t h ew h o l ec l a s so f d e c i s i o nt ot h er e d u c t i o n t h ew h o l ep r o c e s so fa l g o r i t h mf o c u s e so f fa l lt h eo b j e c t sa tt h es a n et i m ew h i c ha v o i dt h e m i s t a k e si ng a i n i n gp a r t i a ld a t a t h ee x p e r i e n c e sf o r w a r d st h eu c id a t a b a s eh a st e s t i f i e dt h e i m p r o v e da l g o r i t h m sa d v a n c e da n dp r a c t i c a b l e a n dl a s t l y , t h ei m p r o v e dr e d u c t i o na l g o r i t h mw a sa p p l i e dt ot h ep r o j e c ts t u d y i n go nt h e i n n o v a t i o no f a g r i c u l t u r a lw a t e rp r i c ea n df a r m e r sa b i l i t yt oo f f e r i ti st h ef i r s tt i m et op u tf o r w a r d i i i 西南大学硕士论文 t h a ta p p l y i n gd a t at a k i n go u ti nt h ea r e ao fa g r i c u l t u r ew a t e rr e s o u r c em a n a g e m e n t , a n ds e tt h e m o d e ls u c c e s s f u l l y , t h er u l e sa c h i e v i n gf r o mw h i c ha g r e e dw i t ht h ef r o n t i e re x p e r t s e x p e r i e n c e s t h i sp r o v e dt h ea l g o r i t h mi sa d v a n c e da n dp r a c t i c a b l e k e yw o r d s ：d a t am i n i n g 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 i s c e r n i b i l i t ym a t r i x 独创性声明 学位论文题目：基王塑蹩篡曲数握控握约笾簋法的盟窒生廑翅 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西南大学或其他教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者： ( 园碑 签字日期：20 0 6 年5 月1 7 日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：回不保密， 口保密期限至年月止) 。 学位论文作者签名：( 刍乃娣 导师签名： 签字日期：2 0 0 6 年5 月f 7 日签字日期：2 0 0 6 学位论文作者毕业后去向： 17 日 工作单位；亟直态堂让箕拯生焦皇盘堂堂睦电话：( q ! ! ! 2 ! q 塑 通讯地址：重庭吏d 硅匡酉直盘堂i 土篡狃量焦! 垦登堂堂睦 邮编：! q q 21 第1 章文献综述 随着信息技术的高速发展，数据库应用的规模不断扩太，原有的数据库处理方法己经远 远不能满足现实需要，数据挖掘正是为迎合这种需要而产生并迅速发展起来的一种新的数据 处理技术数据挖掘( d a t am i n i n g ，d m ) 是从存放在数据库、数据仓库或其它信息库中的大 量数据中挖掘有趣知识的过程。许多数据挖掘技术仅仅适用于精确集，不适用于粗糙集，而 现实中粗糙集是普遍存在的现象，因此基于粗糙集的数据挖掘的研究在信息系统的研究领域 具有重要意义。 1 1 数据挖掘 1 1 1 数据挖掘的定义 数据挖掘最早是在1 9 9 5 年，美国计算机年会( a c m ) 上提出的概念，数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、 人们事先不知道的、但又是潜在有用的信息和知识的过程。 另一种比较公认的定义是w j f r a w l e y ，g p i a t e t s k y ，s h a p i r o 等人提出的：数据挖掘就 是从大型数据库中的数据中提取人们感兴趣的知识。这些知识是隐含的、事先未知的潜在的 有用的信息，提取的知识表示为概念( c o n c e p t s ) 、规则( r u l e ) 、规律( r e g u l a t i o n s ) 、模式 ( p a t t e r n s ) 等形式。 数据库中知识发现是从数据( 集) 中识别出有效的、新颖的、潜在有用的，以及最终可理 解的模式的高级( 非平凡) 的过程。数据挖掘是数据库的知识发现( k d d ，k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 的关键步骤和核心技术，在实际应用中对数据挖掘和k d d 这两个术语 的应用往往不加区别。 1 1 2 国内外研究现状 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，已经从点( 单台 机器) 发展到面( 网络) ，甚至l j i n t e m e t 全球信息系统，使得无论是商业企业、科研机构或是 政府部门，在很短的时间里都积累了海量的、以不同形式存储的数据资料如超级市场上的p o s 系统每天都要存储上万笔的顾客购买数据：各种同步卫星每小时传回地球的遥感i 酮像数据就 达5 0 9 i g a ( 千兆) 字节由于这些资料十分繁杂，仅仅依靠数据库的查询检索机制和统计学方 法己经远远不能满足现实需要了，它迫切要求自动地和智能地将待处理的数据转化为有用的 信息和知识，从而达到为决策服务的目的数据挖掘正是为迎合这种需要而产生并迅速发展 起来的用于开发信息资源的一种新的数据处理技术 数据挖掘出现于2 0 世纪8 0 年代后期，9 0 年代有了突飞猛进的发展，目前，数据挖掘不仅 被许多研究人员看作是数据库系统和机器学习方面的一个重要的研究课题，而且被许多工商 界人士看作是一个能带来巨大回报的重要领域从数据库中发现出来的知识可以用在信息管 理、查询响应、决策支持、过程控制等许多方面”。1 ，数据挖掘是融合了人工智能、数据库技 术的一个新兴的跨学科的研究领域，它被越来越多的领域所采用，并取得了较好的效果，为 人们的正确决策提供了很大的帮助，具有较为广泛的应用前景。 11 3 数据挖掘的主要任务 西南大学硕士研究生学位论文 1 数据总结 数据总结的目的是对数据进行浓缩，给出它的紧凑描述数据挖掘主要关心从数据泛化 的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的 过程。数据泛化目前主要有两种技术：多维数据分析方法和面向属性的归纳方法 2 概念描述 概念描述是对数据库的整体信息进行全面概括，从数据库中归纳抽象的信息。概念描述 有两种典型的描述：特征描述和判别描述。 3 分类 分类是数据挖掘中一项非常重要的任务，目前在商业上应用最多。分类的目的是提出一 个分类函数或分类模型( 也常常称作分类器) ，该模型能把数据库中数据项映射到给定类别中 的某一个。分类和回归都可用于预测。预测的目的是从历史数据记录中自动推导出给定数据 的推广描述，从而能对未来数据进行预测。和回归方法不同的是，分类的输出是离散的类别 值，而回归的输出则是连续数值。 分类器的典型构造方法有决策树法、贝叶斯法，神经网络方法、近邻学习或基于事例的 学习等方法。不同的分类器有不同的特点。 4 聚类 聚类是根据数据的不同特征，将其划分为不同的数据类。它的目的是使得属于同一类别 的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的大。聚类方法包括： 统计方法、机器学习方法和神经网络方法。 5 相关性分析 相关性分析的目的是发现特征之间或数据之间的相互依赖性。数据相关性关系代表类 重要的可发现的知识。若两个或多个数据项的取值重复出现且概率很高时，它就存在着某种 关联。可以建立起这些数据项的关联规则。最著名、最重要的关联规则发现算法是r a g r a w a l 等人提出的a p d o r i 算法。 6 偏差分析 偏差分析包括分类中的反常实例、例外模式、观测结果对期望值的偏离以及量值随时间 的变化等，其基本思想是寻找观察结果与参照量之间的有意义的差别。数据库中的数据能反 映许多异常情况，从数据分析中发现这些异常情况是很重要的，能引起人们对它更多的注意。 7 预测 预测是预测新事物的特征，它不拥现有的数据找出变化规律，即建立模型，井用此模型 来预测未来数据的种类、特征等。 1 1 4 数据挖掘过程 数据挖掘的基本过程和主要步骤“。”3 如图1 1 所示。 1 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最后结构 是不可预测的，但要探索的问题应是有预见的，数据挖掘时带有盲目性是不会成功的。 2 数据准备 2 第1 章文献综述 图1 1 数据挖掘过程示意图 1 ) 数据的选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数据挖掘应用的 数据。对于同一数据源来说，不同的数据挖掘目标，可能只对某一些数据子集和数据划分感 兴趣，因此在数据挖掘过程中，只对这样的数据进行处理，不仅可以排除不必要的数据干扰， 而且还可以极大地提高数据挖掘的效率。 2 ) 数据的预处理 数据预处理为进一步的分析作准备，并确定将要进行的挖掘操作的类型。这一工作有时 主要涉及到数据的集成和不完整数据及噪声的处理。 3 ) 数据的转换 将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的。建立一个真正适合 挖掘算法的分析模型是数据挖掘成功的关键。 4 ) 数据集成 这一工作主要是对不同来源的、异类数据集进行集成，使之成为一个统一形式的数据源， 便于数据挖掘。这一处理过程在不同的应用中可能有不同的处理方法，如，有的应用可以在 建立数据仓库时对异类数据源的数据进行集成，并咀统一的形式将数据存储于数据仓库之 中，然后在数据仓库的基础上进行数据挖掘因此从软件工程的角度出发，利用分布式处理 的方法，在不同数据源间建立数据动态交换的公共规范，并在此基础上进行数据挖掘过程将 是个很好的解决数据集成的途径。 3 模式发现 对经过转换的数据进行挖掘，从而得到用户感兴趣的模式的过程，它是数据挖掘的主要 处理过程，在一个数据挖掘系统中除了选择合适的挖掘算法外，其余一切工作都能自动地完 成。 4 结果分析 解释并评估结果使用的分析方法一般由所采用的数据挖掘方法而定，通常基于以适当 的形式展现评估结果的可视化技术。在实际应用中，得到的知识并不完全是我们所感兴趣的 模式。通过对所得到的知识进行进一步的评估，得到真正感兴趣的知识。在有些情况下，这 一过程可以与上一过程同步进行，也可以将两者合并。无论如何，这种评估作用一般是不可 少的，它是用来衡量挖掘出的知识是否有效的必要手段。 5 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去，通过可视化技术以及其它的 一些知识表示技术提供给最终用户。由于数据挖掘的目的是给用户提供一种可参考的知识信 息，而往往用户对于由某种或某几种挖掘算法挖掘出的知识形式难以理解，因此以一种直观 西南大学硕士研究生学位论文 的、易于理解和解释的形式将知识提供给用户，是数据挖掘系统应该具备的良好功能之一。 1 1 5 数据挖褫技术莳主要方法 从不同的角度看，数据挖掘技术有多种分类方法，如根据发现的知识种类分类，根据挖 掘的数据库类型分类，根据挖掘方法分类，根据挖掘的选径分类，根据所使用的技术分类阔 等等目前常用的数据挖掘技术内容包括如下： 1 决策树方法 利用信息论中的互信息寻找数据库中具有最大信息量的字段，建立决策树的一个节点 再根据字段的不同取值建立树的分支，在每个分支子集中重复建立树的下层节点和分支的过 程。即可建立决策树国际上最有影响积最早的决策树算法是r q u i n l a n 研制的i 鹏方法，数 据库越大它的效果越好此后又发展了各种决策树方法，如i b l e 方法使识别率提高了1 0 。 2 神经网络方法 它模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础，用神经网络连接的权值 表示知识，其学习体现在神经网络权值的逐步计算上目前主要有3 大类辛率经弼络模型：1 ) 前馈式网络，它以感知机、反向传播模型、函数型网络为代表，可用于预测、模式识别等方 面：2 ) 反馈式网络，它以h o p f i e l d 的离散模型和连续模型为代表，分别用于联想记忆和优 化计算；3 ) 自组织网络，它以a r t 模型、k o h o l o n 模型为代表，用于聚类。 3 粗糙集方法 它将知识理解为对数据的划分，每一被划分的集合称为概念主要思想是利用己知的知识 库，将不精确或不确定的知识用已知的知识库中的知识来近似刻划处理。 4 概念树方法 对数据库中记录的属性字段按归类方式进行抽象，建立起来的层次结构称之为概念树 利用概念树提升的方法可以大大浓缩数据库中的记录，对多个属性字段的概念树进行提升， 将得到高度概括的知识基表，然后再将它转换成规则。 5 遗传算法 这是模拟生物进化过程的算法，由3 个基本算子组成：1 ) 繁殖( 选择) ，是从1 个旧种群( 父 代) 选出生命力强的个体，产生新种群( 后代) 的过程：2 ) 交叉( 重组) ，选择2 个不同个体( 染 色俐的部分( 基因) 进行交换，形成新个体；3 ) 变异( 突变) 对某些个体的某些基因进行变 异( 1 变0 ，0 变i ) 。这神遗传算法可以起到产生优良后代的作用这些后代需满足适应度值， 经过若干代的遗传，将得到满足要求的后代( 问题的解) 。遗传算法已在优化计算和分类机器 学习方面显示了明显的优势。 6 公式发现 在工程和科学数据库( 虫实验数据组成) 中。对若干数据项( 变量) 进行一定的数学运算， 求得相应的数学公式比较典型的b a c o n 发现系统完成了对物理学中大量定律的重新发现， 其基本思想是：对数据项进行初等数学运算( 加、减、乘、除等) ，形成组合数据项，若它的 值为常数项，就得到了组合数据项等于常数的公式。 7 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性关系) 和相关 4 第1 章文献综述 关系( 不能用函数公式表示，但仍是相关确定关系) 。对它们的分析采用如下方法：回归分析、 相关分析、主成分分析。 8 模糊集方法 利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式识别、模糊聚类分析和 模糊控制。”1 模糊性是客观存在的。系统的复杂性越高，精确化能力就越低，即模糊性就越 强，这是z a d e h 总结出的互克性原理。 9 。可视化技术 可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清楚，例如，把数 据库中的多维数据变成多种图形，这对提示数据的状况、内在本质及规律性起了很大作用。 在这诸多方法中，粗糙集理论与方法对于处理复杂系统是一种较为有效的方法。 116 数据挖掘的的主要应用及展望 数据挖掘处理的对象是规模庞大的数据，目的是从中发现大量有益的信息基于数据量 巨大这一特性，如何从数据库中高效地提取数据。是目前数据挖掘的难点也是热点，已有许 多研究工作与成果”。” 目前，数据挖掘技术主要应用在市场营销业、金融业，其它领域也有所应用 1 市场营销业市场营销业利用数据挖掘技术进行市场定位和消费分析，辅助制定市场策略 在直销行销方面，数据挖掘被广泛地应用在邮寄活动中，对数据库中所有记载的人员进行邮 寄相比较，预测出哪些人最有可能回复邮寄活动和购买产品，找到潜在客户，同时最能节省 时间和成本费用在客户关系管理( c u s t o m e rr e l a t i o nm a n a g e m e n t ) 方面，c r m 已成为世界 各企业正在关注的一个重要概念，目前企业己从“以产品为中心”转变为“以客户为中心”。 在这种经营观念的影响下，对现有客户和潜在客户的培养和挖掘，成为企业获得成功的关键， 资料显示：发展一个新客户要比保留一个老客户多出5 倍的投入，投资于现有客户，保持住 好的客户是会影响到企业的是终效益的因此往往采用数据挖掘的各种工具来确定各种客 户的特点，据此为客户提供针对性的服务在消费分析上，数据挖掘主要用于帮助企业了解 客户的消费行为，利用简单相关分析，发现哪些产品客户倾向同时购买：利用序列相关分析 发现客户在买了某一产品后，在多长时间之内可能购买另一产品在获取各种消费信息的基 础上，采用关联性产品销售和连贯性销售方法，来提高客户的终身价值。 2 金融业，数据挖掘在金融领域应用广泛，包括金融市场分析和预测、客户分类、银行担保 和信用评估等这些金融业务都需要处理大量数据，很难通过人工或使用一两个小型软件就能 进行分析预测，而数据挖掘则可以通过对已有数据的处理，找到数据对象的特征及彼此之间 的关系利用聚类分析法对客户进行分类，阻止产生坏账，防范金融欺诈，挖掘优质客户， 让金融业更了解客户，为各种客户量身定做，设计更好的金融品种来满足客户需要。运用估 计及预测的方法进行市场动向分析，可以从历史数据中分析市场走向，并预测观察到金融市 场的变化趋势。 3 其他领域数据挖掘技术以其强大的智能性和自动性，在工程和科学研究中得到广泛应 用。天文学中利用决策树方法对上百万天体进行分类进而发现新的天体，靠4 造业应用数据挖 掘技术进行零部件故障论断、资源优化、生产过程分析等司法领域将数据挖掘用于案件调查， 诈骗监测、洗钱认证、犯罪组织等分析医疗卫生行业利用数据挖掘预测外科手术、医疗试 验和药物治疗的效果，制药业通过挖掘巨大的化学物质和基因对疾病的影响和数据库来判断 哪些物质可能对治疗某种疾病产生疗效通讯行业利用数据挖掘技术，从通话记录资料中预 替盗打电话的可能性广告公司利用数据挖掘分析人们购买模式，估计他们的收八和孩子数 目，作为潜在的市场信息，旅游调查局利用数据挖掘分析不同团体的旅游模式，决定不同团 体之间的关联。 总之，数据挖掘可广泛应用于金融、零售与批发、制造、保险、公共设施、政府、教育、 远程通讯、软件开发、运输等各个企事业单位及国防科研上 1 2 粗糙集 12 1 粗糙集理论的产生与发展 长期以来，许多的科学家就致力于研究含糊概念。1 9 6 5 年，l a z a d e h 提出了模糊集概 念，以说明现实中的含糊现象。许多的科学家试图通过这个理论解释含糊概念。但是，模糊 集无法对含糊的多少进行计算。模糊集中的隶属函数是无法用数学公式计算的。1 9 8 2 年。 p a w l a k 教授提出了粗糙集理论，把那些无法确认的个体都归属于边界线区域。由于它有确切 的数学公司进行描述，所以含糊度是可以计算的。从此之后，粗糙集理论开始迅速发展起来。 1 9 9 2 年，p a w l a k 教授出版了第一本关于粗糙集的专著。同年，r s l o w i n s k i 主编的关于粗糙集 应用与相关方法比较研究的论文集的出版，推动了对粗糙集理论的深入研究。同时，在波兰 k i e k r z 召开了第一届国际粗糙集学术讨论会，主要讨论了集合近似定义的基本思想及其应 用。第2 年，在加拿大b a f f 召开了第二届粗糙集和知识发现研讨会。这次会议的主题是租糙 集、模糊集与知识发现。1 9 9 4 年，在美国s a n j o s e 召开了第三届国际粗糙集与软计算研讨会， 这次会议主要探讨了粗糙集与模糊逻辑、神经网络、进化理论等的融合问题。第2 年，召开 的第四届模糊理论与技术国际研讨会主要针对粗糙集与模糊集之间的关系进行了讨论，促进 了粗糙集的发展。1 9 9 9 年，在日本召开第七届粗糙集、模糊集、数据挖掘和粒度一软计算国 际会议，主要阐述了当前粗糙集、模糊集的研究现状和发展趋势。第2 年在加拿大召开了第 二届粗糙集和计算的当前趋势学术会议。当前许多重要的国际学术会议都把粗糙集理论的研 究列入主要内容之一。2 0 0 3 年l o 月1 7 日至2 2 日，“9 t h i n t e r n a t i o n a l c o n f e r e n c eo n r o u g h s e t s ， f u z z ys e t s d a t am i n i n g , a n dg r a n u l a rc o m p u t i n g ( r s f d g r c 2 0 0 3 ) ”和“第三届中i n r o u g h 集与 软计算学术研讨会( c r s s c 2 0 0 3 ) ”在重庆邮电学院成功召开。同年1 1 月，在中国广卅i 举行的 全国人工智能学会的年会上，正式成立了粗糙集与软计算专业委员会。 1 2 2 粗糙集理论的基本观点和特点 1 基本观点 粗糙集理论具有一些独特的观点，这些观点使得粗糙集理论特别适合于数据分析。 1 ) 知识与分类粗糙集理论认为知识就是将现实的或抽象的对象进行分类的能力假设我们事 先对论域中的元素具有必要的信息或知识，通过这些知识能够将元素划分到不同的类别，如 果某些元素具有相同的信息，它们就是不可分辨的，即根据已有的信息不能区分它们。不可 分辨关系满足自反性、对称性和传递性，因此是等价关系。 6 如果给定一个有限的非空集合u ，称为论域，r 为u 上的族等价关系，则知识可以定义 为：等价关系族r 对论域u 的划分，记为u r ，假设我们根据关于论域u 的某种知识，使用属性及 其值来描述u 中的元素，属性或属一陛集合就构成了u 上的一族等价关系r 任意一个等价关系r r 可以对u 划分，形成等价类，称为r 的基本集如果两个元素同属于一个等价类，则它们之 间是不可分辨的不可分拼关系提示出论域知识的粒状结构，是定义其它概念的基础。 2 ) 概念的模糊性和边界设论域为u 炼u 为u 上的一个概念。知识的粒度性是造成使用已有知 识不能精确表示某些概念的原因。粗糙集理论中，模糊性就是一种基于边界的概念，即一个 模糊概念具有一个没有明确界线的边界。为了描迷这种模糊性，利用等价类，每个不精确的 概念x 由一对精确概念，即下近似与上近似来表示。x 的下近似包含了可确切分类到x 中的元 素，上近似包含了所有那些可能属于x 的元素上近似与下近似的差就是概念的边界域，即利 用可用信息不能确定地分类到概念中的所有元素。显然，如果边界域非空，n x 是一个模糊 概念。 3 ) 不确定性和隶属函数模糊概念具有边界元素，即不能确定地分类到概念中的论域元素， 不确定性是关于元素对集合的隶属关系而言的。在粗糙集理论中定义了粗糙隶属函数来描述 这种不确定性的程度，粗糙隶属函数是客观计算的，只与已知数据有关，从而避免了主观因 素的影响，这与模糊隶属函数是不同的。 因此，模糊性是关于集合而言的，指集合具有边界域，集合可以用上、下近似来逼近 不确定性是关于集合中的元素而言的，指某元素是否属于某集合是不确定的，不确定性的程 度用粗糙隶属函数来描述利用粗糙隶属函数又可以定义集合x 的近似及其边界域，因此，模 糊性和不确定性之间存在着确定的联系 2 主要特点 粗糙集理论的特点主要有： 1 ) 无需附加信息根据g i g e r e n z e r 提的数据分析的一般模型1 ，粗糙数据分析是建立在经验 系统的层次上的因此，粗糙集理论的一个重要特点是它不需要预先给出关于数据的任何附加 信息，如统计学中的概率分布、模糊集理论中的隶属度或隶属匾数、证据理论的基本概率分 配。 2 ) 数据分析工具粗糙集理论是一个强大的数据分析工具，它能表达和处理不完备的数据以 及拥有众多变量的数据、能在保留关键信息的前提下对数据进行化简并求得知识的最小表 达、能识别并评估数据之间的依赖关系、能从经验数据中获取最小规则。 3 ) 软计算粗糙集是一种软计算方法软计算的概念是由模糊集创始人z a d e h 提的传统的计 算方法即所谓硬计算，使用精确、固定和不变的算法来表达和解决问题，而软计算的指导原 则是利用所允许的不精确性、不确定性和部分真实性以得到易于处理、鲁棒性强和成本较低 的解决方案，以便更好地与现实系统相协调软计算的主要工具包括粗糙集、模糊逻辑、神经 网络、概率推理、信度网络、遗传算法与其他进化优化算法、混沌理论等。 1 2 3 粗糙集理论的研究领域及发展前景 1 主要研究领域 粗糙集理论从诞生到现在只有二十年左右的时间，但在很多方面已经取得了比较大的 7 西南大学硕士研究生学位论文 成功。已经应用于机器学习、模式识别、知识发现、决策分析和过程控制等方面的领域。目 前对粗糙集的研究主要在以下两个方面： 1 ) 粗糙集理论的理论方面的研究： 粗糙集的数学性质方面的研究【2 1 】：主要是粗糙集的代数结构( s t o n e 代数等) 和拓扑结 构等方面的研究。 粗糙逻辑与推理口l j ：近似真的概念很早就引起哲学家和逻辑学家的注意，而近年来主要 是被从事人工智能的研究者所关注。粗糙逻辑有五个逻辑植，即真、假、粗糙真、粗糙假和 粗糙不相容。 粗糙集的扩展模型方面的研究口1 l ：主要有变精度粗糙集模型、概率粗糙集模型、模糊粗 糙集模型和基于随机集的粗糙集模型； 高效率的约简算法的研究 2 2 - x s 】：找出信息系统所有的约简或最优约简是一个n p 问题， 于是目前主要集中在约简的启发式算法、并行算法、导出规则的增量式算法等方面； 粗糙集理论和其他方法的结合：粗糙集与模糊集理论的结合 2 9 】；还有与神经网络的结合。 ( 2 ) 粗糙集理论的应用方面的研究： 数据挖掘口1 】：粗糙集理论是一种比较有效的数据挖掘方法。粗糙集方法现已成为数据挖 掘的一种重要方法。 模式识别；粗糙集理论可用在模式识别的特征选取中，以选择那些确实能表征该模式 的特征项。 医疗诊断”，】：粗糙集方法根据以往的病例归纳出是否得病的决策规则，井用这些决策规 则来诊断新的病例。 决策分析0 1 1 ：利用信息系统( 决策表) ，粗糙集理论可以获得决策规则。 除此之外，还有故障诊断，图象处理等等。 2 今后的发展 在今后几年内，粗糙集知识发现将有以下几个可能的研究方向1 3 6 ： ( 1 ) 基于粗糙集理论的粗糙逻辑以及不精确推理的研究。该项研究不仅对于知识的挖掘 和表示，而且对于人工智能中的不确定性推理将发挥重要作用。 ( 2 ) 快速、高效的约简算法。约简算法是粗糙集知识发现的基础，目前还没有一种十分有 效的约简算法。 ( 3 ) 粗糙集w e b 知识发现问题。随着i n t e r n e t 的迅速扩展，w e b 页面的增加，利用粗糙集进 行w e b 知识发现将是今后最重要的课题之一。 f 4 ) 与模糊集方法等其他方法的结合问题。目前有很多知识发现方法，粗糙集如何与其他 方法结合，可能是提高知识发现效率的一种途径。 1 3 数据挖掘与粗糙集 j 3 1 数据挖掘与粗糙集 粗糙集理论在以上各领域的应用大都可以归入两类任务：无决策