（系统工程专业论文）基于粗糙集与神经网络的数据分类研究及应用.pdf

大连理工大学硕士学位论文 摘要 在信息技术和数据库技术高速发展的今天，数据成了人们工作和生活中必不可少的 一部分，然而要从海量数据中提取出有用信息却很困难。数据分类作为一种重要的数据 分析技术，可以用于提取描述重要数据类的模型和预测未来的数据趋势，帮助人们总结 出数据中隐含的规律，为业务决策和战略发展服务。 论文首先介绍了粗糙集理论，并引入了一种基于属性重要度的粗糙集属性约简算 法，它能有效地消除冗余信息，达到为输入变量降维的目的。其次，针对多分类问题设 计了一个基于动态阈值的神经网络分类器，此分类模型采用了与传统模型不同的动态阈 值函数，可以有效提高分类器的泛化能力。另外，还结合理论指导和实际的试验仿真对 神经网络的隐层数及其节点数进行了优化设计，采用具有双隐层的b p 神经网络作为分 类器模型的核心。最后，通过分析粗糙集和神经网络的特点，取长补短，把二者有机地 结合在了一起，使用粗糙集作为分类器模型的前端处理器，约简输入变量，达到了科学 选择变量的目的，提高了模型的分类性能。 电影票房预测是一个典型的非线性问题，通过将其转化成一个分类问题，可以使问 题简化，即把影片根据其票房收入的高低划分成了6 个档次，预测的目的就是把影片分 到相应的类别里面。在成功建模的基础上，确定了影响影片票房高低的因素作为输入变 量，然后通过统计的方法确定了其初始值。最后运用所设计的分类器模型解决了该票房 预测问题。通过与决策树、支持向量机、r b f 网络等方法的比较结果表明，基于动态阈 值的神经网络分类器具有更好的预测精度、稳定性以及泛化能力。基于粗糙集的属性约 简对分类器的输入变量进行了科学合理的降维，其与神经网络分类器的有机结合取得了 良好的效果，预测性能明显优于其它分类模型。 关键词：数据分类；粗糙集；神经网络；动态阈值；票房预测 基于粗糙集与神经网络的数据分类研究及应用 r e s e a r c ha n d a p p l i c a t i o no f d a t ac l a s s i f i c a t i o nm e t h o db a s e do nr o u g h s e ta n dn e u r a ln e t w o r k a b s t r a c t n o wd a y s ，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 ya n dd a t a b a s e t e c h n o l o g y ，d a t ah a sb e e na l la b s o l u t e l yn e c e s s a r yp a r ti np e o p l e sw o r ka n dl i f e ，b u ti ti sa v e r yd i f f i c u l tt a s kt oe x t r a c tt h eu s e f u li n f o r m a t i o nf r o mm a s s i v ed a t a d a t ac l a s s i f i c a t i o ni s a ni m p o r t a n td a t aa n a l y s i st e c h n o l o g y a n di tc a nb eu s e dt oe x t r a c tt h em o d e lt h a td e s c r i b e s i m p o r t a n td a t ac a t e g o r ya n dp r e d i c tt h ef u t u r ed a t at r e n d 也e nd i s c o v e rt h eh i d d e nr u l e st o s u p p l ys e r v i c ef o rb u s i n e s sd e c i s i o na n ds t r a t e g i cd e v e l o p m e n t i nt h i sp a p e r ，t h er o u g hs e tt h e o r yi si n t r o d u c e df i r s t l y ，a n da l lr e d u c t i o na l g o r i t h mb a s e d o nt h ei m p o r t a n td e g r e eo fa t t r i b u t ei s i m p o r t e d w h i c h c a r lr e m o v et h er e d u n d a n c y i n f o r m a t i o ne f f e c t i v e l ya n dr e d u c et h ed i m e n s i o no fi n p u t s e c o n d l y ，an e u r a ln e t w o r k c l a s s i f i e rb a s e do nd y n a m i ct h r e s h o l di sp r o p o s e da i ma tm u l t i c l a s sp r o b l e m ，a n dt h i s c l a s s i f i c a t i o nm o d e lad i f f e r e n tt h r e s h o l df u n c t i o nf r o mt r a d i t i o n a lo n e s w h i c hi m p r o v e st h e c l a s s i f i e r sg e n e r a l i z a t i o na b i l i t ye f f e c t i v e l y i na d d i t i o n ，t h eo p t i m i z a t i o nd e s i g no ft h e s t r u c t u r ep a r a m e t e r ss u c ha st h en u m b e ro fh i d d e nl a y e r sa n d 也e i ro w nn o d e si so p e r a t e db y c o m b i n i n gt h e o r yg u i d a n c ea n de x p e r i m e n t ，a n dt h e nt h eb pn e u r a ln e t w o r kw i t ht w oh i d d e n l a y e r si se m p l o y e da st h ek e r n e lo ft h ec l a s s i f i e rm o d e l f i n a l l y t h er o u g hs e ta n dn e u r a l n e t w o r ka r ec o m b i n e db ym a k i n gu pf o re a c ho t h e r sd e f i c i e n c i e s ，a n dt h er o u g hi su s e da st h e f r o n tp r o c e s s o ro ft h en e u r a ln e t w o r km o d e lt or e d u c et h ei n p u tv e c t o rf o rt h ep u r p o s eo f s e l e c tv a r i a b l es c i e n t i f i c a l l ya n di m p r o v et h ep e r f o r m a n c eo ft h em o d e l b o x o f f i c ep r e d i c t i o ni sat y p i c a ln o n l i n e a rp r o b l e m ，a n dc a na l s ob et r a n s l a t e dt oa c l a s s i f i c a t i o np r o b l e m a i lt h em o v i e sa r ed i v i d e di n t os i xc a t e g o r i e sa c c o r d i n gt ot h e i r b o x o f f i c ei n c o m e s a n dt h ep u r p o s ei st op r e d i c taf i l mi n t ot h er i g h tc l a s s o nt h eb a s i co f s u c c e s s f u lm o d e l i n g f a c t o r st h a te f f e c tt h eb o x o f - 矗c er e v e n u ea r es e l e c t e da st h ei n p u t v a r i a b l e s a n dt h e i ri n i t i a lv a l u e sa r ed e t e r m i n e db yu s i n gs t a t i s t i c a lm e t h o d t h e nt h e p r o p o s e dc l a s s i f i e rm o d e li su s e dt os o l v et h i sp r o b l e m a c c o r d i n gt oc o m p a r et h er e s u l t sw i t l l d e c i s i o nt r e e ，s u p p o r tv e c t o rm a c h i n e ，a n di 氇fn e u r a ln e t w o r k ，t h en e u r a ln e t w o r kc l a s s i f i e r w i t hd y n a m i ct h r e s h o l dh a sb e t t e rf o r e c a s t i n ga c c u r a c y ，s t a b i l i t ya n dg e n e r a l i z a t i o na b i l i t y t h ec o m b i n eo fr o u g hs e ta n dn e u r a ln e t w o r kc a no b t a i nf a v o r a b l ee f f e c tt oi m p r o v et h e c l a s s i f i c a t i o np e r f o f i n a n c e a n dd i s t i n c t l yb e t t e rt h a i lo t h e rm o d e l s k e yw o r d s - d a t ac l a s s i f i c a t i o n ；r o u g hs e t ；n e u r a ln e t w o r k ；d y n a m i ct h r e s h o l d ； b o x - o f l 6 c ef o r e c a s t i n g i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 学位论文题目：整墨塑：毽建壶谴丝因蕴堑查遗盗参蟹墨! 蕴i 蛰 作者签名：! 骂蕴簦 日期：皇2 型正年圭- 月三三日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本入完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文 作者签名 导师签名 大连理工大学硕士学位论文 1绪论 1 1 课题的研究背景 近十几年来，随着信息技术的迅猛发展，产生和收集数据的能力大幅度提高，千千 万万的数据库被用于商业管理、政府办公、科学研究和工程开发等等。为了充分利用这 些数据为其业务决策和战略发展服务，数据挖掘和知识发现技术应运而生，并蓬勃发展， 越来越显示出其强大的生命力。数据挖掘是一种决策支持过程，技术基础是人工智能。 人工智能是通过使用计算机来模拟人的某些思维过程和智能行为，从而高效率地解决现 实世界存在的问题。目前数据挖掘主要利用人工智能中的一些算法和技术，包括人工神 经网络技术来进行未来趋势的分析预测、模式识别、分类和聚类等。数据挖掘的两个基 本目标往往是预测和描述。预测涉及到使用数据集中的一些变量或域来预测其它我们所 关心的未知或未来的值【1 捌。 预测是决策的前提，任何成功的决策都离不开科学的预测。而预测作为决策的前提 和基础，对最终决策选择方案起着至关重要的作用，因而也是人类生存和发展的一项重 要活动p j 。预测是一门研究未来的科学，是根据一定事物的运动和变化规律，用科学的 方法和手段对该事物的发展趋势和未来状态进行估量，作出定性或定量的评价。它从过 去和现在己知的情况出发，研究某一事物当前已知因素与未来某些可确定因素之间的关 系、寻求事物的发展规律，利用一定的方法或技术去探索或模拟不可知的、未出现的或 复杂的中间过程，推知其未来发展的趋势( 包括水平、方向、途径、时限、速度及其可 能性等) ，为当前制定规划、进行决策提供依据。简言之，预测是根据某一事物过去的 发展现律研究其未来的发展趋势，以调节当前行动的一种理论和方法【4 】。 分类是数据挖掘的一种非常重要的方法。分类的概念是在已有数据的基础上学会一 个分类函数或构造出一个分类模型( 即分类器c l a s s i f i e r ) 。该函数或模型能够把数据 库中的数据纪录映射到给定类别中的某一个，从而可以应用于数据预测。要构造分类器， 需要有一个训练样本数据集作为输入。训练集( t r a i n i n gs e t ) 由一组数据库纪录或元组构 成，每个纪录是一个由有关字段值组成的特征向量，我们把这些字段称做属性 ( a t t r i b u t e ) ，把用于分类的属性叫做标签( l a b e l ) ，标签属性也就是训练集的类别标记【5 】。 如何选择那些对分类贡献较大的属性成为了数据挖掘的又一个重要的研究内容，即如何 从数据中提取出有价值的信息，而摒弃那些对分类没有贡献甚至起干扰作用的信息。 基于粗糙集的知识挖掘研究如何从大量的数据中智能地、自动地提取出有价值的知 识和信息，是当前相当活跃的知识领域。作为一种较新的软计算方法，粗糙集理论以其 基于粗糙集与神经网络的数据分类研究及应用 独特的优势正赢得越来越多的关注，在理论研究方面日趋成熟，并在很多领域取得了较 为成功的应用。国外已产生许多粗糙集知识挖掘系统以及相应的软件系统，在各个领域 中得到了广泛的应用。目前，粗糙集理论已经被应用在数据挖掘、信息系统分析、人工 智能、决策支持系统和机器学习等各种领域【6 】。， 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 是模仿大脑神经元功能而形成的智能仿生 模型。它是由大量简单元件神经元，广泛相互连接而成的非线性、非局域性、非定 常性和非凸线性的复杂网络系统，具有并行分布的信息处理结构和自适应的信息处理能 力，它可以通过“自学习”或“训练”掌握大量的知识，完成特定的工作。神经网络的 学习算法有多种，而误差反向传播( b p ) 算法是目前广泛采用的神经网络权值的修正算法 一】。实践证明，人工神经网络对建立预测模型十分有效，它能从数据样本中自动学习以 前的经验而无需复杂的查询和表述过程，并自动地逼近那些最佳的数据中蕴涵的规律， 它在分类预测方面尤其是高复杂度的非线性分类方面明显优于传统的分类方法【8 。 任何一种理论或方法都不是完美的，粗糙集理论和神经网络用于数据分类也有各自 的优缺点。粗糙集理论提供了一系列的有效算法用于数据预处理、属性约简和规则抽取 等方面，但是容错能力和泛化能力相对较弱，噪声环境下往往精度不高。神经网络用于 分类问题具有分类精度高和鲁棒性强的优点，但是存在知识解释性能差、训练时间长及 网络结构不确定等问题。很显然，两种技术具有很强的互补性，它们相互结合有助于克 服各自的缺点，产生性能更优的分类算法。 1 2 数据分类技术研究现状 分类( c l a s s i f i c a t i o n ) 是一个从现有的带有类别的数据集中寻找同一类别数据的共同 特征，并以这些特征为依据对新数据进行区分的过程。分类技术发展至今己取得了很大 的成就，各种分类技术和理论不断涌现，基本上可以分为三大类。一种是基于统计的方 法，如贝叶斯网络、k n n 、支持向量机、回归模型、最大嫡模型等方法；另一种是基于 连接的方法，如人工神经网络；还有一种是基于规则的方法，如决策树、关联规则和粗 糙集理论掣1 0 l 。下面简要地介绍常见的数据分类技术。 1 2 1 常见的数据分类技术 目前，用于数据分类的理论和技术有很多，下面对决策树、支持向量机、贝叶斯网 络、神经网络四种常用的分类方法先作简要介绍。 ( 1 ) 决策树分类 决策树归纳是经典的分类算法。它采用自顶向下递归的各个击破方式构造决策树。 树的每一个结点上使用信息增益度量选择测试属性。可以从生成的决策树中提取规则。 一2 一 大连理工大学硕士学位论文 基于决策树的分类方法是一种监督学习的方法，树的数量决定于分类的精度和树的 大小决策树的算法有很多，1 9 8 6 年j r o s sq u i n l a r l 给出i d 3 算法，它是国际上最早、 最有影响力的决策树算法，i d 3 算法是基于信息嫡的决策树分类算法，根据属性集的取 值选择实例的类别。1 9 9 6 年，j r o s sq u i n l a n 对i d 3 算法进行了补充和改进，给出了后 来非常流行的c 4 5 算法，该算法是一种归纳学习算法，但是这两种决策树算法对于相 对小的数据集是很有效的，但面对海量数据时，算法的有效性和可扩展性就成了关注的 问题f l l 】。 ( 2 ) 支持向量机分类 s v m 法即支持向量机( s u p p o r tv e c t o rm a c h i n e ) 法，由v a p m k 等人于1 9 9 5 年提出， 具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习方法。通过 学习算法，s v m 可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出 的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分准率。该方法只 需要由各类域的边界样本的类别来决定最后的分类结果。支持向量机算法的目的在于寻 找一个超平面h ( d ) ，该超平面可以将训练集中的数据分开，且与类域边界的沿垂直于该 超平面方向的距离最大。待分样本集中的大部分样本不是支持向量，移去或者减少这些 样本对分类结果没有影响，s v m 法对小样本情况下的自动分类有着较好的分类结果i l 2 | 。 ( 3 ) 贝叶斯网络分类 贝叶斯分类是统计学分类方法，它基于贝叶斯定理，可以预测类成员关系的可能性， 给定样本属于某个特定类的概率。贝叶斯网络的研究在国外十分广泛，它可以对不确定 性知识进行推理。例如：医生看病，根据病人的症状，判断病人是否得了某种疾病，往 往是一种不确定的推理( 带概率的推理) ，多数情况下没有百分之百的把握。运用贝叶斯 网络进行推理，可以达到较好的效果。朴素贝叶斯分类算法能运用到大型数据库中，且 方法简单、分类准确率高、速度快。但是，贝叶斯定理假设一个属性值对给定类的影响 独立于其它属性的值，而此假设在实际情况中经常是不成立的，因此其分类准确率可能 会下降【1 3 】。 ( 4 ) 神经网铬分类 神经网络分类算法的重点是构造阈值逻辑单元，一个值逻辑单元是一个对象，它可 以输入一组加权系数的量，对它们进行求和，如果这个和达到或者超过了某个阈值，输 出一个量。神经网络是基于经验风险最小化原则的学习算法，有一些固有的缺陷，比如 层数和神经元个数难以确定，容易陷入局部极小，还有过学习现象，这些本身的缺陷在 s v m 算法中可以得到很好的解决【1 4 】。神经网络数据分类技术将在第三章进行详细地介 绍。 基于粗糙集与神经网络的数据分类研究及应用 1 2 2 数据分类技术存在的问题及未来的发展方向 尽管分类技术继承了大量在人工智能、机器学习以及模式识别等领域已发展出的论 与技术，但是它仍然面临大量问题的挑战。主要有以下几个方面的问题，有新的题就促 使学者进行相应的研究，所以，数据分类技术未来的研究也主要围绕这些方面。 ( 1 ) 分类算法的有效性和可扩展性。现在的数据库包含的数据量往往达到g b 级， 甚至t b 级。从海量的数据中有效抽取分类信息要求所用的分类算法的运行时间必须是 可预测和可接受的，而且是可扩的，即对于小型数据具有很高分类精度而对于大海数据 也应该具有较高的分类精度【1 5 , 1 6 j 。 ( 2 ) 有效的特征降维技术。目前，海量数据不仅是数据量大同时数据维数也非常高， 如表示文本的向量空间型通常高达几千维甚至几万维。如果直接在输入空间上进行分类 器训练，就可能带来两个棘手的问题。如何在无损失或少损失的前提下有效的降低数据 的维数成为一个研究热点，在特征降维和特征选择方面也取得了一定的成就，但是很多 己有的特征选择方法是针对具体的应用问题的【1 7 以9 1 。所以，更多具有通用性和高效的特 征降维方法需要进一步研究。 ( 3 ) 噪声数据和丢失数据的处理。这个问题在商业领域中尤其突出。可以想象，如 果某数据库在建立时不是面向数据挖掘的，其某些重要数据或属性可能丢失，某些数据 的记录很可能产生模糊甚至错误。这将干扰分类挖掘过程，降低挖掘知识的精确性。目 前主要是使用统计和不确定性理论来确定隐含变量及其依赖关系。所以，如何有效的去 除噪声数据，合理的补全丢失的数据，以提高算法的鲁棒性必将成为数据分类技术未来 的研究热点之一。 ( 4 ) 时序数据和知识更新问题。在各种应用领域中的数据库大多是随时间变化的， 这使得早期挖掘到的知识即分类规则不适用于后期的情况或者有许多新的类型的数据。 这就要求数据挖掘系统能够保存已有知识的同时随时增加新知识或更新己无用的旧知 识的功能，并且通常采用增量学习等手段来处理时序数据。 ( 5 ) 模式易懂性。分类结果能否为人所理解是该分类算法能否为人所用的前提条 件。简单明了的表达方式能够提高挖掘结果的可理解性。目前的表达方式主要有：决策 树、规则、图表、自然语言表示，以及数据与知识的可视化等。如何将分类结构表示得 直观易懂，表示海量数据的分类结果，对于多类分类都能够很直观表示等问题将是分类 领域的又一关注点。 一4 一 大连理工大学硕士学位论文 1 3 课题的主要研究内容 1 3 1 研究的目的及意义 现实中有很多问题实质上就是数据分类，也有很多问题可以转换为数据分类来解 决，因此数据分类存在着广泛的潜在应用。从政府管理决策、商业经营、科学研究和工 业企业决策支持等各个领域都可以找到分类技术的用武之地。例如，可以建立一个分类 模型，对银行的贷款客户进行分类，以降低贷款的风险：也可以通过建立分类模型，对 工厂的机器运转情况进行分类，用来预测机器故障的发生；类似的也能进行网络故障的 诊断与预测。因此，数据分类技术的进一步研究具有重要的理论意义和实际应用价值。 电影综合艺术、经济、科技等于一身，是艺术中的商品，商品中的艺术。随着人们 的生活的日益提高，越来越多的人开始走进电影院，选择看电影作为周末或节假日休闲 放松方式，从而带来了电影行业的蓬勃发展。目前，国内3 0 0 0 家左右的电影院加盟在 3 0 家左右的电影院线公司，院线公司的一项重要任务就是选择要上映的影片，这对于年 票房的多少起着至关重要的作用。于是，影片选择前的票房预测就成了院线公司的一项 重要任务。只有正确估算一部影片可能的产出才能决定上映影片的影院数量、对影片的 宣传成本投入数量以及投入市场的档期，从而获得更多的利润。 对于一部影片，。很难预测其精确的票房收入。目前普遍采用的是头脑风暴法来粗略 估计一部影片的票房的高低，更多的是由负责发行的几个工作人员简单的猜测，而缺乏 正确的理论指导和成熟的运作模式，这严重影响了票房的产出。根据影片的票房收入高 低，可以把影片分为许多档次，即不同的类别，从而把票房预测问题转化成为一个分类 问题，把数据分类技术引入进来对问题加以解决，使票房预测的科学性和可靠性得到了 显著的提高。 1 3 2 作者的主要工作 在已有数据分类理论成果的基本上，作者针对目前数据分类技术存在的问题进行了 深入的分析和研究，并把研究重点放在了特征降维和分类算法的有效性上，通过粗糙集 和神经网络这两种智能方法的有效结合，提出了一个新的数据分类模型。首先应用粗糙 集这一新兴的理论方法作为神经网络分类器的前端处理器，进行条件属性的约简，即对 输入变量进行降维处理，去除那些对分类贡献较小甚至没有贡献的属性，而保留那些能 有效区分各个类别的属性，从而达到了用更少的输入变量来取得更好的分类性能的目 的。在有效约简输入变量的基础上，采用了目前应用最广泛的b p 神经网络作为分类器 的核心算法，并根据已有的理论和方法对b p 神经网络的结构进行了优化，从而取得了 基于粗糙集与神经网络的数据分类研究及应用 较优的分类性能。在分类器模型的输出部分，采用了不同于传统方法的动态阈值函数对 神经网络的输出进行规范化处理，从而提高了模型的鲁棒性和输出的直观性。 在论文的最后，所提出的分类器模型成功解决了电影票房预测问题。在输入变量的 初始值的确定过程中，使用了统计学方法，并根据b p 神经网络的特点进行了归一化处 理，从而使变量的取值更具科学性。最后通过票房预测结果的比较分析，有效说明了提 出的分类器模型具有更优的分类性能。 论文的主要内容如下： 第一章：绪论，阐述了课题的研究背景，并介绍了数据分类技术及其研究现状，最 后说明了本课题的研究意义和论文的结构。 第二章：基于属性重要度的粗糙集属性约简方法，系统地阐述了粗糙集及其用于条 件属性约简的方法步骤。 第三章：介绍了神经网络尤其是b p 网络的相关概念以及神经网络分类器的基本原 理，最后提出了基于动态阈值的神经网络分类器。最后，详细说明了粗糙集和神经网络 的特点，以及它们的结合方式，并提出了一种基于粗糙集和神经网络的分类器。 第四章：把以上的理论成果运用到了实际问题当中，解决了未上映影片的票房预测 问题。系统全面地介绍了问题的解决流程，并对分类器模型的性能进行了全面的测试和 比较分析。 一6 一 大连理工大学硕士学位论文 2 基于属性重要度的粗糙集属性约简方法 对于分类数据挖掘而言，重要条件属性的缺少或冗余条件属性的存在同样是有害无 益的，提高系统知识清晰度的一个重要方法就是对数据库中的数据进行约简。因此，属 性约简成为获取分类规则的必经途径。属性约简不仅可以减少要处理的数据量，降低决 策表中冗余属性对挖掘质量的破坏，简化分类器，而且可以在某种程度上降低分类数据 挖掘中数据噪声的影响，提高分类器的泛化性能。 属性约简，就是在所有条件属性构成的集合中，选择一个可以尽量多地保留属性全 集的分类信息的属性子集的过程。在粗糙集理论中，决策表的属性约简是一个非常重要 的研究课题，国内外有很多学者对这一问题进行了大量的研究，给出了多种不同的属性 约简方法。由于属性约简问题已被证明是n p - h a r d 问题，所以用穷举法找出属性集合的 最佳子集是不可能的，通常采用启发式搜索策略，做局部最优选择，并由此逼近全局最 优解，这是处理此类问题的一种有效策略。本文采用了一种改进的粗糙集属性约简的启 发式方法。 2 1常见的属性约简算法 如何得到一种最佳的求取属性约简的方法，是至今为止许多科学家正在研究探讨的 关键问题。现在已经有很多属性约简方面的理论成果，形成了很多行之有效的属性约简 方法，下面对已有的属性约简算法进行一下简要的总结和概括。j ( 1 ) 删除法 在约简算法中，最常见的方法就是删除法。此方法为依次从数据表中删除属性，将 删除属性后的信息表与原信息表的决策类的不可分辨关系进行比较，如果不可分辨关系 没有变化，那么可以继续从新生成的信息表中删除属性，继续比较；如果不可分辨关系 发生了改变，则恢复到前一个信息表，删除另一属性。 ( 2 ) 基于差别矩阵的约简算法 利用差别矩阵( d i s c e r n i b i l i t ym a t r i x ) 来表达知识有很多的优点，特别是它可以容易 地计算约简和核。差别矩阵由两种值组成，当两条记录之间条件属性值不完全相同且决 策属性值也不相同时，该元素为属性值不相同的条件属性的组合；当两条记录之间的条 件属性值相同或决策属性值相同时，该元素为o 。差别矩阵的对角元素均为0 ，且沿主 对角线对称。通过引入一个差别函数( 布尔函数) ，应用布尔代数中的分配定律和吸收定 律对其进行化简，从而得到这个差别函数的析取范式。由差别函数的性质可以得到，这 基于粗糙集与神经网络的数据分类研究及应用 个差别函数的极小析取范式中的所有合取式就是属性集的所有约简，换句话说，约简是 满足能区分由整个属性集区别所有对象的属性极小子集。 ( 3 ) 基于近似质量的属性约简算法 属性约简应该为不含多余属性并能保证分类正确的最小条件属性集合，约简前的分 类近似质量与约简后的分类近似质量应该是相同的。该算法以所有的条件属性作为初始 约简集合，以集合的近似质量不变为前提，逐步缩减求取约简，可以在很短的时间内找 出属性约简。 ( 4 ) 基于属性重要度的启发式约简算法 针对某一具体问题，各属性的重要性是不同的。利用属性的依赖度可以定义属性的 重要度，即去除某个条件属性后所引起的分类误差，这个误差越大，说明该属性越重要。 2 2 粗糙集理论概述 粗糙集理论是一种处理不完整和不确定知识的数学工具，1 9 8 2 年z 。p a w l a k 发表了 经典论文r o u g hs e t s ，宣告了粗糙集理论的诞生【2 0 1 。它能有效地分析和处理不精确和不 完整等各种不完备信息：并从中发现隐含的规律，同时也是一个强大的数据分析工具， 它能表达和处理工程技术领域中普遍存在的不完备甚至不一致的信息，能在保留关键信 息的前提下对数据进行化简，求出知识的最小表达，能够从经验数据中获取易于证实的 规则知识，为基于粗糙集的分类方法提供了理论基础。 2 2 1 粗糙集的基本概念 “知识”这个概念在不同的范畴内有多种不同的含义。在粗糙集理论中，“知识 被认为是一种分类能力。人们的行为是分辨现实的或抽象的对象的能力，如在远古时代， 人们为了生存必须能分辨出什么可以食用，什么不可以食用；医生给病人诊断，必须辨 别出患者得的是哪一种病。这些根据事物的特征差别将其分门别类的能力均可以看作是 某种“知识”。 知识是关于对象分类的能力，对象指任意客观事物，知识与真实或抽象世界的不同 分类模式联系在一起，称之为论述的论域。设u 9 是我们感兴趣的对象组成的有限集 合，称为论域。任何子集x u ，称为u 中的个概念或范畴。空集也是一个概念，u 中的任何概念族称为关于u 的抽象知识，简称知识。u 上的一族划分称为关于【，的一 个知识库。设置是u 上的一个等价关系，u r 表示r 的所有等价类构成的集合，i x i 。 表示包含元素x e u 的r 等价类【2 1 1 。一个知识库就是一个关系系统k = ( u , r ) ，其中【厂 为非空有限集，称为论域，只是【厂上的一族等价关系。 大连理工大学硕士学位论文 分类过程中，相差不大的个体被归于同一类，它们的关系就是不可分辨关系，也称 为等价关系。假定只用两种黑白颜色把空间中的物体分割成两类， 黑色物体) ， 白色 物体) ，那么同为黑色的两个物体就是不可分辨的，因为描述它们特征属性的信息相同， 都是黑色。如果再引入方和圆两种属性，又可以将物体进一步分割为四类：f 黑色方物 体) ， 黑色圆物体) ， 白色方物体) ， 白色圆物体) 。这时，如果两个同为黑色方物体， 则它们还是不可分辨的。不可分辨关系也称为一个等价关系，两个白色圆物体间的不可 分辨关系可以理解为它们在白和圆两种属性下存在等效关系。 若p 欠，且p 西，则n 尸俨中所有等价关系的交集) 也是一个等价关系，称为p 上的不可区分关系，记为i n d ( p ) 。属性集p 的不可区分关系定义为 i n d ( p ) = ( x ，y ) u uv a p ，f ( x ，口) = f ( y ，口) 。女果( x ，y ) i n d ( p ) ，贝0 称x 和y 是p 不可区分的。 令x u ，足为u 上的一个等价关系，当x 能表达成某些足基本范畴的并集时， 称x 是月可定义的；否则称x 为盈不可定义的。矗可定义集是论域的子集，它可以在 知识库中精确地定义，而r 不可定义集不能在这个知识库中定义，r 可定义集也称作足 精确集，而r 不可定义集也称为足非精确集或r 粗糙集。粗糙集理论拓展了经典的集 合论，把用于分类的知识引入集合内，作为集合组成的一部分，对于粗糙集可以近似地 定义，使用两个精确集，即粗糙集的上近似和下近似来描述。 包含在x 中的最大可定义集称为x 的r 下近似，即噩( x ) = x uix l 。x ， 噩( x ) 表示在知识r 下u 中一定能归入x 的元素的集合，集合p o s 且( x ) = 噩( x ) 称为x 的r 正域。x 的足上近似，即r 一( x ) = x ulxl pnx a ，足( x ) 表示根据知识欠 判断u 中可能属于x 的元素组成的集合。n e g 詹( x ) = u - g 一( x ) 称为x 的r 负域，是那 些根据知识r 判断肯定不属于x 的u 中元素组成的集合。集合b n 詹( x ) = r 一( x ) 一冠( x ) 称为x 的r 边界域，是那些根据知识月既不能判断肯定属于x 又不能判断肯定属于u - x 的u 中元素组成的集合【2 。 2 2 2 基于粗糙集的知识表达系统 知识表达在智能数据处理中占有十分重要的地位。一个知识表达系统是一个四元组 s = ( u ，a ，v ，) ，其中u 为对象的非空有限集合，称为论域；彳为属性的非空有限集合； y 是属性值的集合；f ：u x aov 是一个信息函数，它为每个对象的每个属性赋予一个 信息值，即对于任意的“u ，口a ，有f ( u ，口) = v 。知识表达系统也称为信息系统，通 常用s = ( u ，么) 代替s = ( u ，a ，v ，厂) 。知识表达系统的数据以关系表的形式表示，关系表 基于粗糙集与神经网络的数据分类研究及应用 的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来 表达【2 2 1 。容易看出，一个属性对应一个等价关系，一个表可以看作是定义的一簇等价关 系，即知识库。 决策表是一类特殊而重要的知识表达系统，多数决策问题都可以用决策表形式来表 达，这一工具在决策应用中起着重要的作用。具有条件属性和决策属性的知识表达系统 s = 够4 ，v ，f ) 称为决策表。其中a = c u l 9 ，c n d = 彩，c 称为条件属性集，d 称为决 策属性集，例如表2 1 是一个决策表。该决策表的对象是e ，巨，最，条件属性为国产、 明星阵容和类型，决策属性为票房。 表2 。1 决策表 t a b 2 1d e c i s i o nt a b l e 知识约简是粗糙集理论的核心内容之一，知识库中的知识( 属性) 并不是同等重要 的，甚至其中某些属性是冗余的。所谓知识约简，就是在保持知识库分类能力不变的前 提下，删除其中不相关或不重要的知识。知识约简中有两个基本概念：约简和核。给定 知识表达系统s ，其中，条件属性集合c 的约简是c 的一个非空子集p 。它满足： ( 1 ) v a p ，a 都是d 不可省略的；( 2 ) p o s e ( d ) = p o s c ( d ) 。则称p 是c 的一个约简， c 中所有约简的集合记作r e d ( c ) 。c 中所有不可省略属性的集合称为c 的核，记为 c o r e ( c ) ，则c o r e ( c ) = n r e d ( c ) 。若p o s c ( d ) = u ，则称该决策表为相容决策表， 否则称其为不相容决策表。对于决策表的属性约简，有如下性质：一般来说，一个决策 表的相对约简不是唯一的，即对同一个决策表可能存在多个相对约简，因此人们期望找 到具有最小条件属性的约简，即相对最小约简1 2 引。 大连理工大学硕士学位论文 2 3 基于属性重要度的粗糙集属性约简算法 2 3 1 属性重要度的计算 设有决策系统s = ( u , c u d ，k 力，其中c ，d 分别表示条件属性和决策属性，则决 策属性在条件属性下的正区域可定义为 p o s c ( d ) 2 删u 。( 石) ( 2 1 ) 五e u i d p o s c ) 表明根据c 的知识所进行的划分u c ，能够确切地划入u c 类的对象集合。 决策属性d 对条件属性c 的依赖度定义为 k = y c ( d ) ： p o 矿s c ( d ) ( 2 2 ) l ui 依赖度r c ( d ) 表示在条件属性c 下能够确切划入决策在u d 的对象占论域中总对象 数的比率，表达了决策属性对条件属性的依赖程度。 针对一个具体问题，各属性的重要度是不同的。利用属性的依赖度可以定义属性的 重要程度。通常的做法是将某一属性口从c 中除去，看看它对由c 所产生的正区域的 影响程度。由式2 2 可知，比( d ) 表示决策属性d 和条件属性c 之间的依赖程度，因此 可通过当a 从c 中除去时，r c ( j o ) 的改变来衡量属性a 的重要度。即在上述决策系统s 中，a c 的属性重要必定义为 吲加警斗锗 亿3 ， 可以将q c d ) ( 口) 理解为当属性a 被除去时，所发生的分类错误率，q c ，d ) ( 口) 越大， 属性a 就越重要【2 引。 2 3 2 连续属性值的离散化 粗糙集理论研究的一个关键问题是连续属性的离散化问题。许多学习算法要求输入 的属性值是离散的，离散化可以有效地减少信息系统的大小，提高数据分析的质量。粗 糙集理论为处理离散属性提供了一种有效工具，但它不能直接处理连续属性，现实数据 库中常包含离散和连续两种属性，粗糙集要从这样的数据库中发现知识，推理决策规则， 就要对连续属性进行离散化。离散化的任务是把连续属性的取值范围或取值区间划分为 若干个数目尽可能少的小区间，其中每个小区间分别对应一个离散符号。离散化可以由 领域专家根据经验给出相应的区间，也可以根据某种原则对输入空间进行划分，给出离 散点进行离散化。 基于粗糙集与神经网络的数据分类研究及应用 目前已有很多种离散化方法，有的不考虑粗糙集理论的特殊性，将其他学科中的离 散化方法应用于粗糙集理论中；有的考虑到粗糙集理论的特殊性，即该类方法是否改变 原决策表的不可分辨关系，是否在原决策表中引入冲突。本文采用了s h n g u y e n ， h s n g u y e n 改进的贪心算法，些算法有效减少离散化算法的时间复杂度和空间复杂度 【2 4 】 o 定义一个能够被给定的断点区分开的实例对的个数为爿( q ) ，其中。为属性口 上的第k 个断点，l 薹七兰，n a 为属性a 的断点总数；x 矽，矽为实例全集。 设j ( j = l ，2 ，力为决策的种类，定义： 属于集合z 同时在属性a 上的值小于断点值的实例的个数为 垆( ) = l x xi a ( x ) 】 【万= 栅f ( 2 5 ) 所以有 ( 2 6 ) ( 2 7 ) 从而可以得到 w x ( c ；) = z x ，x ( ) 一矿( ) ，( ) ( 2 8 ) f # l w x ( ) 值越大，则断点的重要性越高，在选取断点时先被选取的可能性也就越 大。 假设x l ，恐，是信息系统的实例已经被所选取的断点集合p 划分的等价类，那 么能够被断点c ( c 仨尸) 区分而不能被尸区分的实例对的个数为 阿，p ( c ) = w x - ( c ) + 形疋( c ) + + 形孔( c ) ( 2 9 ) 由此得到下面的离散化算法： p 为选取的断点的集合，工为实例被选取的断点所划分的等价类，g 为候选断点的 集合，步骤如下： ( 1 ) p = g ，工= 砚； ( 2 ) 对每一个c g ，计算砑馓c ) ； 川川 、，、， 口 0 x x x x ”rk j j j j 、，、， 等 h ， ，芦，州 | | l | 口七 口 雠 雠 p j时 大连理工大学硕士学位论文 ( 3 ) 选择r e e ( c m 戤) 最大的断点c 一加到p 中，p = - p u c m 默) ，g _ 矾 c m a x ； ( 4 ) 对x l ，如果c m 酞把等价类x 划分为x ，憋，那么从工中去掉x ，把等价类 x ，弼加到互中； ( 5 ) 如果工中所有的等价类都对应一种决策，则停止，否则转到( 2 ) 。 s h 。n g u y e n ，h s n g u y e n 提出的改进的贪心算法选择断点的本质和贪心算法是一 样的，因此得到的断点集和贪心