（机械制造及其自动化专业论文）数据挖掘技术在产品概念设计中的应用研究.pdf

摘要 本文根据粗糙集理论中对知识分类的特点，将粗糙集理论应用到数据挖掘中 来指导产品概念设计，论述了粗糙集理论指导下的设计参数简化的方法。并且将 基于属性的概念爬升技术应用到设计知识数据库中，可以获得不同抽象层次、不 同角度描述的设计参数与设计方案之间的关系规则。并结合机械传动方案设计问 题，建立了一个支持产品概念设计的数据挖掘系统框架。针对从网络中搜集整理 的设计数据库，对设计参数进行了化简，得到了确定传动类型所需要的最重要的 参数集合，以便缩小设计的搜索范围、降低设计的复杂度，并对设计参数与传动 方案实现了多层次的挖掘，获得了两者之间不同抽象层次的关系规则信息。最后 为实现并验证上述各项工作，设计了一个基于粗糙集理论的数据挖掘技术指导机 械传动概念设计的系统。 关键词：粗糙集数据挖掘概念设计概念爬升 a b s t r a c t 1 1 1 ep a p e rb a s e do nt h ec h a r a c t e r i s t i co f r o u g h s e t sc l a s s i f i c a t i o na n da p p l yi tt o d a t am i l l i n gt og u i d i n gp r o d u c tc o n c e p t u a ld e s i g n m p a p e rd i s c u s s e st h em e t h o do f d e s i g np a r a m e t e r sp r e d i g e s t i o ng u i d e db yr o u g h s e t sa n da p p l yc o n c e p tc l i m bb a s e d o na t t r i b u t et o d e s i g nd a t a b a s e ，t h u sw ec a no b t a i nr e l a t i o nr u l e sb e t w e e nd e s i g n p a r a m e t e ra n dd e s i g ns c h e m ef r o ma l lk i n d so f a b s t r a c th i e r a r c h ya n dd i f f e r e n tp o i n to f v i e w c o m b i n e p r o b l e mo f m e c h a n i s mt r a n s m i s s i o ns c h e m e d e s i g n ，af r a m e w o r k t h a t s u s t a i np r o d u c tc o n c e p td e s i g ni se s t a b l i s h e d b a s e do nd e s i g nd a t a b a s es e a r c hf r o m i n t e r a c t d e s i g np a r a m e t e r sa r ep r e d i g e s t e d n 地m o s ti m p o r t a n tp a r a m e t e r st h a t m a k es u r et ot r a n s m i s s i o ns t y l ea r ea v a i l a b l e ，s ot h a tt h es e a r c hr a n g ei ss h r i n k e da n d t h ec o m p l e x i t yi sr e d u c e d n 圮m u l t i - p r e d i g e s tm i n i n gb e t w e e nd e s i g np a r a m e t e ra n d t r a n s m i s s i o ns c h e m ei sr e a l i z e da n dr e l a t i o nr u l e so fa l lk i n d so fa b s t r a c tl e v e l sa r e o b t a i n e d f i n a l l y ，as y s t e mo f m e c h a n i s mt r a n s m i s s i o nc o n c e p t u a ld e s i g ng u i d e db y d a t a m i n i n gb a s e do nr o u g h s e t si sd e v e l o p e di no r d e rt ov a l i d a t i n ga b o v ew o r k s k e y w o r d ：r o u g h s e t sd a t am i a m g c o n c e p t u a ln e s 垭nc o n c e p t c l i m b 声明 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：奎丝 本人承担一切相关责任。 日期竺! ! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：至塾 导师签名：至卫 日期兰! ! ! ：! 生 日期塑：垄：i 第一章绪论 1 1 数据挖掘在概念设计中应用的研究意义 随着企业生产自动化程度的日益提高，产品的功能与结构日趋复杂，产品设计 在整个生命周期内占有越来越重要的位置。作为只占5 产品成本的设计活动往往决 定占到7 0 - 8 0 的产品成本n 引。因此，深入研究产品设计过程的特点及其方法、规 律成为产品设计的主要研究课题。 近些年来，随着企业信息化程度的不断提高，c a d c a m c a p p 等先进设计、 生产方法的运用，同时企业事务电子化的迅速普及，企业积累了大量的设计、生产 数据资料；另一方面，企业需要在继承原有的设计信息的基础上，设计出具有新功 能、创新性的产品。因而如何更加充分的利用已有设计数据信息成为企业设计人员 关心的主要问题之一。 毫无疑问，这些庞大的数据库及其中的海量资料是极其丰富的信息源，传统的 信息检索机制和统计分析方法只能获得这些数据的表层信息，不能充分利用丰富的 数据资源，这远远满足不了人们对数据内部隐含的、有价值的信息和知识获得的需 求研州。如何将这些数据资源的利用提高到更高阶段，达到数据资源利用过程和人 的知识创新过程的有机结合，是信息社会发展到一定阶段的客观要求。 从人工智能应用来看，专家系统的研究虽然取得了一定的进展，但是知识获取 仍然是制约专家系统研究的瓶颈p 3 2 3 3 l 。实际上知识工程师从设计领域专家处获得 知识是非常复杂的个人到个人之间的交互过程，具有很强的个性，没有统一的办法。 这是一个长期而艰巨的任务，更何况要从庞大的数据库中获取知识，有必要研究从 数据库中自动挖掘新知识的方法。 因此，一门新兴的自动信息提取技术：数据挖掘( d a t a m i n i n g ，简称d m ) 也 称为数据库中知识发现( i g m w i e d g ed i s c o v e r yi nd a t a b a s e ，简称k d d ) 应运而生 并得到迅速的发展，它的出现为自动和智能地把海量的资料转化为有用的信息和知 识提供了手段 2 4 3 5 , 3 6 1 。 数据挖掘的一种公认的定义是在k d d 9 6 国际会议上1 2 0 1 ，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 s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形 式。更广义的说法是【l 2 6 1 ：数据挖掘意味着在一些事实或观察数据的集合中寻找 模式的决策支持过程。数据挖掘是一个交叉学科领域，受多个学科影响( 如图1 1 ) ， 包括数据库系统、统计学、机器学习、可视化和信息科学等学科【3 】。 2 数据挖掘技术在产品概念设计中的应j _ l ；j 研究 弋尸 图1 1 数据挖掘受多学科的影响示意图 作为一种独立于应用的技术，数据挖掘方法的提出，让人们有能力最终认识数 据资料的真正价值，即蕴藏在资料中隐含的、潜在有用的信息和知识。它不仅被产 品设计、数据库、人工智能和机器学习界的研究人员看作一个越来越重要的研究课 题，而且也被工商界视为能带来巨大回报的领域。 概念设计是产品设计的先导，又是产品构型设计的前提，概念设计搞好了，产 品设计才有可能达到高水平网。产品设计本身是创造性韵劳动，设计的本质是创新 l 删。在概念设计阶段，设计人员对产品的认识很多都是经验性知识，而这些经验性 知识的获得一方面是设计人员从大量的设计活动中积累的，另一方面是从前人的设 计方案中继承来的。而拥有大量的、丰富的经验知识是很少的设计领域专家才具备 的，并且设计专家的许多有价值的设计经验很难准确的表达出来。利用数据挖掘技 术，能够从积累的海量设计数据中挖掘出其中蕴含的丰富经验性知识，这些经验性 知识中有些是专家已经具备的、有些是专家未发现的，将它们提供给设计人员以便 设计时借鉴和参考，丰富设计人员的知识。 众所周知，产品的研制过程，往往是在一定的信息资源基础上的知识创新，从 原有的信息资源中挖掘的知识在一定程度上给设计人员以启发和借鉴j 。把成熟的 设计资源中蕴涵的知识应用到新产品的研制中，不仅可以缩短设计周期、降低成本， 而且可以确保产品的设计质量。能否充分合理地利用现有的丰富的设计资源，是影 响产品研制周期、产品设计质量以及产品的创新性的重要因素，也是衡量设计人员 水平的重要标准之一【2 5 1 。因此，将数据挖掘的研究从理论研究转向应用，从不同侧 面、不同应用层次最大限度地利用企业积累的丰富信息资源中蕴涵的知识，是数据 挖掘技术在工程实践领域的最终目标。 第一章绪论 鉴于以上论述，将数据挖掘应用到产品概念设计中具有很强的现实意义，同 时也可以加快概念设计的进展和应用。 i 2 国内外相关研究发展现状 1 2 1 国内外概念设计的研究动态 1 国外概念设计的研究动态 在概念设计方法学方面，s t u r g e s 通过定义功能之间的关系，使功能图的语义 更加完善【3 7 l ；h a n b u r g 提出了设计人员交互工作的问题和在不确定状态下的决策技 术；b r a c c w e l l 提出分层的信息结构，实现计算机辅助的功能载体映射。在知识表 达和建模方面，q i a n 通过对功能行为结构的表达，由交互方式在领域内产生创新 方案d s l ：u m e d a 将设计知识表达为功能行为散态的组合关系，以产生新方案【3 9 j ； c u l l e y 建立了一个产品装配模型，以快速找出所需部件。 在开发辅助工具方面，人们借助人工智能技术和数据库技术来推动概念设计 的智能化。a d z h i e v 提出面向代理的方法，有利于并行设计环境下使各种设计变量 保持高度一致性【柏l ；t a b e l - b e n d i a b 应用基于实例推理和机器学习的技术来学习设 计实例并存储起来；l i 利用定性启发式搜索方法，辅助机构的概念设计j 。 在基于计算机的设计环境方面，t w e n t e 建立了一个机电一体化产品的设计支 撑环境，支持多模型状态；t o m l y a n m 利用大型数据库建立了一个概念设计开发环 境；s h a r p e 主持开发的环境着重子集成，同时利用了超媒体和超文本技术。 2 国内概念设计的研究动态 上海交通大学邹慧君教授等人自1 9 8 9 年开始进行机械运动方案设计专家系统 的研究，结合机械产品概念设计开展了较为系统的研究【4 2 】。他们以机械运动系统 作为概念设计的对象，用组合分类法对机构分类，建立相应的存储和编码规则， 以二元逻辑推理和模糊综合评价相结合的方法建立推理机制，得出可行的方案解， 开发了“机构系统方案设计专家系统【4 3 、4 4 ”。孔凡国将方案创新设计过程划分为两 个主要阶段：基于实例功能推理的原始机械方案生成阶段和基于结构推理的方案 创新设计阶段，开发了机械方案创新设计智能支持系统( m c i d i s s ) t 4 。在这个基础 上，他们还提出了功能行为结构的概念设计模型和基于本样体知识表达和推理相 结合的方法，使领域知识和基础知识相互融合，以便产生多层次的创新解。采用 现代设计方法进行机械运动方案的构思、拟定和综合评价，同时按实现动作和功 用将机构分类，说明其特点和应用场合，供设计人员产品创新设计时应用。 4数据挖掘技术在产品概念设计中的应用研究 华中理工大学周济教授等人的研究主要集中在基于实例的基础上，将之应用于 工程中的再设计问题及实例检索与重用上【4 6 】，在相控雷达的方案设计支持系统中应 用了这一方法。这种方法可以在再设计中找出相近实例。 浙江大学潘云鹤教授等人，提出了基于原型的知识表示和推理方法【4 ”，并将其 应用于广告的方案设计和椅子的方案设计中，冯培恩教授提出了基于设计目录的方 案选择智能方法，并将其应用到了固液分离设备当中( 4 8 l ，得出适当的方案原理解。 同济大学王小同等将人工神经网络与传统人工智能相结合。提出智能设计系统 i d s 模型及其实现的关键技术。其侧重点在结构设计上，开发了机翼结构方案智能 设计系统 4 9 i 。 1 2 2 国内外数据挖掘的研究动态 数据挖掘是目前国际上数据库和信息决策领域的最前沿研究方向之一，引起了 学术界和工业界的广泛关注。一些国际上高级别的工业研究实验室，例如m m a l m a d e n 和g t e ，众多的学术单位，例如u cb e r k e l e y ，都在这个领域开展了各种 各样的研究计划f l 】。研究的主要目标是发展有关的方法论、理论和工具，以支持从 大量数据中提取有用的和让人感兴趣的知识和模式。 从八十年代开始，在世界各地逐渐形成了一批数据挖掘和l d 韵研究小组【2 5 l ， 1 9 8 9 年，召开了第届k d d 专题讨论会，并于1 9 9 1 年与1 9 9 3 年举行了第二、第 三届k d d 专题研讨会。由于这项研究广泛的应用背景和人们对信息资源应用的普 遍关注，终于在1 9 9 5 年。专题研讨会发展为首届国际数据挖掘和知识发现会议，以 后每年都举行一次。研究重点也逐渐从发展方法转向系统应用，并且注重多种发展 策略和技术的集成，以及多种学科之间的相互渗透。其他的专题会议1 6 “”j 如 i n t e r n a t i o n a lj o i n tc o n f e r e n c eo na r t i f i c i a l i n t e l l i g e n c e ( i j c a d 、i n t e r n a t i o n a l c o n f e r e n c eo n k n o w l e d g ed i s c o v e r y a n dd a t a m i n i n g ( k d d ) 、n a t i o n a l c o n f e r e n c eo n a r t i f i c i a li n t e l l i g e n c e ( a a a i ) 、i n t e r n a t i o n a lc o n f e r e n c eo i lv e r yl a r g ed a t a b a s e ( v l d b ) 等也把数据挖掘和知识发现列为议题之一，介绍数据挖掘和k d d 的最新进展和发 展动态、挖掘结果的评价指标以及各种挖掘算法等方面的研究，并逐渐成为计算机 科学界的一大热点。 目前，数据挖掘可以对多种数据库存储的信息进行处理，从关系数据库中挖掘 知识的关系数据挖掘，是使用最为广泛，也是最为成熟的一类数据挖掘技术。挖掘 的知识具有多种形式，如关联规则、分类规则、聚类规则、特征规则、时序规则i i 2 l 等。同时，这些知识也可以在不同的层面上表达，如：泛化知识、原始知识、多层 知识1 2 4 j 等。显然，即使是在同一个数据库中，隐含的知识也是多种多样的，所以， 一个优秀的挖掘技术应该能全面完整地挖掘出隐含在不同层面内的不同种类的知 第一章绪论 识。 数据挖掘经过十几年的发展，产生了许多挖掘知识的技术，包括：基于规则和 决策树的知识发现、基于神经网络的方法、模糊和粗糙集方法、统计方法、知识可 视化方法等【z 4 j 。在这众多技术中，现今的数据挖掘大都采用基于规则和决策树的知 识发现的方法。数据库中关联规则挖掘近几年研究较多，如今关联规则的挖掘已经 从单一概念层次关联规则的发现发展到多概念层次的关联规则的发现，并把研究的 重点放在提高算法的效率和规模可收缩性上。 数据挖掘技术的强大生命力还体现在一大批有关的原型系统的建立上，国外一 些著名的公司或研究机构纷纷推出自己数据挖掘商业产品。比较典型的系统有【1 l ： i b m 公司的q u e s t 、加拿大s i m o nf r a s e r 大学的d b m i n e r 、g t e 的k d w + 、g m d 的e x p l o r a 、日本k a y y a d 的s k i c a t 、 a t & t 的i m a c s 以及乔治梅森大学 m i c h a l s k i 的n l e n 。许多供应商将数据挖掘技术应用于电子商务，以提高i n t e m e t 站点和客户的关联性，如y a h o o z 使用数据挖掘工具，玛m 已经发布了一个以w e b 为中心的数据挖掘解决方案s u r f a i d 。 数据挖掘技术的潜在应用是十分广泛的，目前开展的比较活跃的数据挖掘应用 方向主要有【5 7 棚1 ：市场营销、银行业、生产销售和零售业、制造业、经纪业和安全 交易、保险业、医药、电信、资产评估、科学研究和政府决策等领域。 虽然数据挖掘得到蓬勃发展，但数据挖掘的研究还很不成熟，其应用还有很大 的局限性。数据挖掘的发展方向以及面临的技术挑战主要表现在以下几方面l l 2 4 j ： 挖掘方法和用户交互问题：这反映所挖掘的知识类型、在多粒度上挖掘知 识的能力、背景知识的使用、特定的挖掘和知识的表达和解释机制、噪声 和不完全数据的处理、挖掘模式评估一兴趣度问题。 性能问题：包括数据挖掘算法的有效性、可伸缩性和并行处理。 数据库类型多样性问题：包括关系的和复杂的数据类型的处理、有异种数 据库和全球信息系统挖掘信息。 私有性和安全性问题：数据挖掘能从不同角度、不同的抽象层上看待资料， 这将潜在的影响到资料的私有性和安全性。研究数据挖掘可能导致的非法 资料入侵，同样是实际应用过程中亟待解决的问题。 其它问题：包括知识的维护和更新、支持的局限、与其它系统的集成。 我国在数据挖掘和知识发现方面的研究起步较晚，目前许多科研院所已开始进 行数据挖掘技术的研究，取得了一些研究成果；但数据挖掘技术在我国成功应用的 案例还比较少。目前的研究重点正在从理论方面的研究转向应用方面的研究，特别 是将数据挖掘技术应用于支持产品概念设计的方面的研究还较少。因此，本文尝试 在这方面做一些探索性的研究工作。 6 数据挖掘技术在产品概念设计中的应用研究 1 3 本文的主要研究工作 本文主要的研究工作概括如下： 1 查阅了大量资料，研究了数据挖掘的理论，总结了数据挖掘研究目的、观点 和采用的方法。 2 由于粗糙集理论可支持知识发现的多个步骤，将粗糙集理论应用到数据挖掘 过程中，将获得的经验性知识用以指导概念设计的进行。 3 将面向属性的归纳和基于概念树的爬升技术结合，用领域的背景知识指导挖 掘不同层面知识的方法，并将这些知识添加到产品概念设计的知识库中，丰 富设计人员的设计素材。 4 。结合机械传动设计，以在网络中搜集和整理到的设计数据为基础，设计并实 现了将s q l 、j a 、a 语言和基于知识的推理系统相结合的原型系统，获得设 计参数与设计方案之间的相互关系，以此来给设计人员在概念设计时提供经 验性知识。 第二章粗糙集理论基础 第二章粗糙集理论基础5 0 、5 1 】 目前，知识发现方法的研究主要专注于知识发现过程的实施算法，这些算法 大多应用与发展了机器学习理论。就知识发现过程整体而言，尚缺乏坚实的理论 基础。以粗糙集理论为基本框架的知识发现过程的研究，越来越引起人们的关注， 特别是将粗糙集理论与机器学习、模式识别、数据库理论等相结合，并融合其它 有效的数学工具与方法的研究，显示出强大的优越性【2 1 。本章将对粗糙集理论的基 本思想做一介绍。 2 1 1 粗糙集简介 2 1 基本概念 粗糙集合( r o u g hs e t ，简称r s ) 理论1 5 3 - 5 6 是一种新型的处理模糊和不确定知 识的数学工具，自1 9 8 2 年由波兰数学家p a w l a kz 教授提出以来，经过近二十年的 研究和发展，已经在理论和实际应用上取得了长足的进展。特别是由于八十年代 末和九十年代初在知识发现等领域得到成功的应用而受到国际上广泛关注。目前， 它已经在人工智能、知识与数据发现、模式识别与分类、故障检测等方面得到了 较为成功的应用垆。 2 1 2 分类的基本概念 粗糙集理论的要点是将分类与知识联系在一起，认为知识源于人类以及其他 物种的分类能力，概念即是对象的集合，知识库即是分类方法的集合1 5 “”】。 定义2 1 假设给定一个对象的论域u ，对于任何子集x 尘1 j 称之为一个u 中的 概念( c o n c e p t ) 或范畴( c a t e g o r y ) ，并且u 中的任何概念簇称为u 中的抽象知 识，简称知识。一个u 上的分类簇，定义为一个u 上韵知识库( k n o w l e d g e b a s e ) 。 假设我们对论域里的个体( 对象) 具有必要的信息或知识，通过这些知识能 够将其划分到不同的类别。若我们对两个元素具有相同的信息，则他们是不可区 分的，即根据已有的信息不能够将其划分开，显然这是一种等价关系5 “1 。 定义2 2 当r 为u 上的等价关系，则u r 为r ( 或u 的分类) 的所有等价类簇， 用 x 。表示包含元素x 的r 的等价类，x u 。 定义2 3 若p c r ，且p 中，则n p ( p 中全部等价关系的交集) 也是一个等 价关系，称为p 上的不可分辨关系( i n d i s c e r n i b i l i t yr e l a t i o n ) ，且记为i n d ( p ) ： 数据挖掘技术在产品概念设计中的应用研究 x 。m 严n x 。 r e p 定义2 4u i n d ( p ) ( 等价关系i n d ( p ) 的所有等价类簇) 定义为与等价关系p 的簇 相关的知识。称为p 基本知识( pb a s i ck n o w l e d g e ) 。 为简便起见，将u i n d ( p ) 记为u p ，p 基本知识记为p ，h a d ( p ) 的等价类称为知 识p 的基本概念或基本范畴( b a s i cc a t e g o r y ) 。特别地，如果q r ，对于u 在k 中，则q 称为q 初等知识( qe l e m e n t a r yk n o w l e d g e ) ，且q 的等价类称为知识r 的q 初等范畴。例如：论域中的元素按年龄和身体状况分类，则“老”和“病”是 初等范畴，“老”且“病”是该知识库中的基本范畴。 实际上p 基本范畴是论域的基本特性，该论域可称为拥有知识p 。对于中p 量r 所有p 基本范畴的簇称为知识库k = ( u ，r ) 中的基本范畴簇。 定义2 5 当k = ( u ，r ) 为一知识库，i n d ( k ) 定义为k 中所定义的所有等价关 系的簇，记为i n d ( k ) = i n d ( p ) ：中p r ) 。i n d ( k ) 就是等价关系的最小集， 它包含了k 的全部初等关系，并且闭子等价关系的交集。 定义2 6 设k 寻( u ，p ) 和k l = ( u ，q ) 是两个知识库，如果i n d ( p ) 爿n d ( q ) ，则称k 和k i ( 或q 和p ) 是等价的，记作k 望k t ( 或p - - 。q ) 。 2 2 1 基本概念 2 2 近似和粗糙集 定义2 7 令x c _ u ，且r 为一等价关系。当对象子集x 能用属性子集r 确切地描 述( 即是属性子集r 所确定的不可分辨关系的并) 时，称x 是r 可定义的( r d e f i n a b l e ) ，否则x 是r 不可定义的( ru n d e f i n a b l e ) 。r 可定义集是论域的子集， 它可在知识库k 中被精确地定义，而r 不可定义集不能在这个知识库中被定义。r 可定义集也称作r 精确集( re x a c ts e t s ) ，而r 不可定义集也称为r 非精确集( r i n e x a c ts e t s ) 或粗糙集( rr o u g hs e t s ) 。 定义2 8 为了描述知识的近似程度，给定知识库k ( u ，r ) ，对于每个子集x _ c u 和一个等价关系r i n d ( k ) ，可用r 的基本集合的描述来划分集合x 。为了衡量r 的基本集合精确地说明x 中对象的隶属度情况，考虑两个子集： r ( x ) = u y e u r ：y c x ) r 一( x ) = u y e u r ：y n x o ) 分别称为x 的r 下近似( rl o w e ra p p m x i r n a f i o n ) 和r 上近似( ru p p e r a p p r o x i m a t i o n ) 。 上近似、下近似也可以用下面的等式表达： 第二章粗糙集理论基础9 一- _ _ - _ _ _ - _ _ _ - _ _ _ 一 r 一( x ) = x u ： x 一x r 一( x ) = ( x u ： x 。n x 中 下近似r ( x ) 表示根据知识r ( 属性子集r ) ，u 中所有一定能归入x 的元素的集 合：上近似r + ( x ) 表示根据知识r ，u 中所有可能归入x 的元素的集合。 定义2 9 集合b n 一( x ) ：r - ( x ) 一r 一( x ) ，称为x 的r 边晁域。 b n s ( x ) 是对于知识r 即不能归入x 也不能归入一x 的元素的集合。 定义2 1 0 集合p o s 。( x ) = r - ( x ) 称为x 的r 正域，n e g 。( x ) = u r 。( x ) 称为x 的r 负域。 正域p o s 一( x ) 是那些对于知识r 能完全确定地归入集合x 的对象的集合。负域 n e g 。( x ) 是那些对于知识r 毫无疑问不属于集合x 的元素的集合，它们是属于x 的补 集。 有了知识的上近似集、下近似集、正域、边界域的概念，它们之间的关系如下： r 一( x ) = p o s 。( x ) u b n r ( x ) = r ( x ) u b n 。( x ) = u r 一( 一) ( ) 2 2 2 近似的度量 由此可见，可以肯定地划分u 中的对象为x 或一x 两个不关联的子集，其对象的 总数等于除去x 的r 边界的对象韵数目，郢 l u b n 。( x ) = l u l 一 r - ( x ) 一i l ( x ) 这里ll 代表集合的基数，即u 中对象的数目。 由以上关于集合上、下近似的定义可有下列性质： 1 ) 当且仅当r ( x ) = r ( x ) 。x 为r 可定义集； 2 ) 当且仅当r ( x ) r i ( x ) ，对于r ，x 为租糙集。 我们可以将r ( x ) 描述为x 中的最大可定义集，将r - ( x ) 描述为含有x 的最小可 定义集。 定义2 1 1 集合的不确定性是由于边界域的存在而引起的。集合的边界域越大， 其精确性越低。为更准确地表达这一点，引入精度的概念，定义为： d r ( x ) = c a r d ( r - ( x ) ) c a r d ( r ( x ) ) 其中c a r d 0 表示该集合的基数，且x 中。 精度d r ( ，( ) 用来反映我们对于了解集合x 的知识的完全程度。显然，对于每一 个r 且x 5 u ，有0 d r ( 殉l ：当d s ( x 产l ，x 的r 边界域为空，集合x 为r 可 定义的；当d r ( ) ( ) 1 ，则集合x 有非空边界域，该集合为r 不可定义的。 图2 1 分别表示d r ( ) ( ) = l ，集合x 是全部r 可定义的；当o d r ( x ) i ，集合x 数据挖掘技术在产品概念设计中的应用研究 为部分r 可定义的；当d r ( x ) = 0 ，集合x 为全部r 不可定义的情况。 定义2 1 2r 的粗糙度( r r o u g h n e s s ) 来定义集合x 的不确定程度，即 p r ( x ) = i - d r ( ) ( ) x 的r 粗糙度与精度恰恰相反，表示集合x 的知识的不完全程度。 x ( a ) x i 饧溯绷铴 l x 勿锈彩钐例 彩砀笔么搦 ( c ) 图2 1 近似空间中集合x 可定义性的表示 ( a ) 集合x 是全部r 可定义的： ( b ) 集合x 是部分r 可定义的； ( c ) 集合x 是全部r 不可定义的 根据粗糙集x 的上近似集、下近似集的特征，我们对粗糙集x 的不确定程度作 如下定义： 定义2 1 3 假定集合x 是u 上的一个关于知识r 的租糙集， ( 1 ) 如果r ( x ) 中且r 一( x ) u ，则称x 为r 粗可定义的； ( 2 ) 如果艮( x ) = 中且r ( x ) u 则称x 为r 内不可定义的： ( 3 ) 如果r ( x ) 中且r _ ( x ) ：u ，则称x 为r 外不可定义的； ( 4 ) 如果r 一( x ) = 中且r - ( x ) = u ，则称x 为r 全不可定义的。 根据我们在集合中获得的知识，对知识f 的某些对象进行划分时，同样存在一 个近似分类的问题，分类的近似的定义如下： 定义2 1 4 当f - x l ，x 2 ，x n ) 为一集合簇，则r ( f ) = r - ( x 0 ，r ) ，& ( ) ( n ) ) 和r ( f ) = r ( x 1 ) r - ( x 2 ) ，r _ ( ) ( n ) 分别称为簇f 的r 下近似和r 上近似 定义2 。l s 近似分类的两个度量定义如下： 第一个度量为通过f 的r 的近似的精度： 第二章粗糙集理论基础 d r ( f ) - c a r d ( r ( x i ) ) c a r d ( r 一( x f ) ) 第二个度量为通过f 的r 近似质量： r r ( f ) 2 c a r d ( r ( x ) ) c a r d ( u ) 分类的精度描述的是当使用知识r 对对象分类时可能的决策中哪一个的百分比 最正确；分类的质量表示的是应用知识r 能确切地划入f 类的对象的百分比。 2 2 3 粗糙集的包含关系 定义2 1 6x 和y 是论域u 中的两个集合，r 为知识( 属性集合) ，定义 ( 1 ) 若r 一( x ) 量r 一( y ) ，则称集合x 为r 下包含于y ，或者y r 下包含x ，记 作x 三一y ： ( 2 ) 若r - ( x ) 冬矗一( y ) ，则称集合x 为r 上包含于y ，或者y r 上包含x ，记 作x 一y ； ( 3 ) 若z 一脚一y ，则称集合x 为r 包含于y ，或者y r 包含x ，记作x - y 。 集合x 为r 下包含于y 意味着x 的正例同样是y 的正例；集合x 为r 上包含于 y 意味着y 的负例同样是x 的负例。 定义2 。1 7x 和y 是论域u 中的两个集合，r 为知识( 属性集合) ，定义 ( 1 ) 若r ，( x ) = r 一( y ) ，则称集合x 为r 下等价于y ，记作x = 一y ； ( 2 ) 若r 一( x ) = r 一( y ) ，则称集合x 为r 上等价于y ，记作x - 一y ； ( 3 ) 若x = - y 且x = - y ，则称集合x 为r 粗等价于y ，记作x = - y 。 x - - y 说明集合x 和y 具有相同的正例集：x = - y 说明集合x 和y 具有相同的负例 集。 2 3 1 简化的概念 2 3 知识的简化 定义2 1 8 令r 为一等价关系簇，且r r ，当i n d ( r ) = i n d ( r - r ) ，称r 为r 中 可省略的( d i s p e n s a b l e ) ，否则r 为r 中不可省略的( i n d i s p e n s a b l e ) 。 定义2 1 9u 为一个论域，p 为定义在u 上的一个等价关系簇，p 中所有不可省 略关系的集合，称为p 的核，记作c o r e ( p ) 。 数据挖掘技术在产品概念设计中的应用研究 核与简化的关系如下：c o r e ( p ) = nr e d ( p ) ，其中r e d ( p ) 是p 的所有简化簇。 令p 和q 为u 中的等价关系，q 的p 正域( p p o s i t i v er e g i o n ) 记为p o s l , ( q ) ，即p o s p ( q ) = 1 2 只( x ) ( x t uj 0 ) 对于u p 的分类，u q 的正域是论域中所有通过用分类u p 表达的知识能够确 定地划入u q 类的对象的集合。 定义2 2 0p 和q 为u 中的等价关系簇，当p o s ；( i n d ( q ) ) = p o s 。( h ( i n d ( q ) ) 时，称r p 为p 中q 可省略的。否则，r 为p 中q 不可省略的。 定义2 2 l 当p 中每一个r 都为q 不可省略的，则称p 为q 独立的( 或p 是对于 q 独立的) 。当s 为p 的q 独立子簇，且p o s ；( q ) = p o s ，( q ) ，则簇s c p 称为p 的q 简 化。 定义2 2 2p 中所有q 不可省略原始关系簇称为p 的q 核，记为c o r e 。( p ) = n r e d 。( p ) ，其中r e d 。( p ) 是p 中q 简化簇。 集合p o s “q ) 是通过知识p 所有能够划入知识q 的初等范畴的对象的集合，当 必须把整个知识p 划分到q 的初等范畴时，则知识p 为q 独立的。 p 的q 核知识是p 中最基础的部分，它若没有划分对象到q 的初等范畴能力就 不能消去。知识p 的q 简化是p 的最小子集，它为知识q 的初等范畴提供了与全部 知识p 相同的对象分类，p 可以有不止一种简化。 只有一个q 简化的知识p ，从某种意义上说是一种确定性知识，即当划分对象 到q 的初等范畴时使用p 的初等范畴只能有一条途径：而在非确定性知识的情况下， 一般p 有多种q 简化，即可以有多种简化算法。 2 3 2 知识的依赖性 要进行知识的化箍，并从一给定籍识中导出另一知识，必须研究数据库中函数 之间的依赖关系。 定义2 2 3 当q 的所有初等范畴可以用p 中的某些初等范畴定义时，厦f j 知识q 是从知识p 中可导的。当q 从知识p 中可导时，称q 依赖于p ，记作p j q 。 依赖性可形式化地定义如下： 令k - - ( u ，r ) 为一知识库，令p ，q 三r ： 1 ) 当i n d ( p )i n d ( q ) ，知识q 依赖于知识p ； 2 ) 当p j q 且q ；p ，知识p 和q 时等价的，记作p ；q ： 3 ) 。当不存在p ；q ，且不存在q j p ，p 、q 为独立的。 显然，当且仅当i n d ( p ) = - i n d ( q ) ，有p q 。 为了度量知识的依赖性，形式化地定义知识的部分可导性。 第二章粗糙集理论基础 定义2 2 4 令k = ( u ，r ) 为知识库，且p ，q r ，当 k 2 r p ( q ) = c a r d ( p 0 5 p ( q ) ) c a r d ( u ) 时，称知识q 时k 度可导的( o k 1 ) ，记作p j 。q ，其中c a r d 表示集合的基 数。 当k = l ，则论域的全部元素都可以通过知识p 划入u 0 的初等范畴( q 是由p 全 可导的) ；当k 1 ，只有属于正域的元素可以通过p 划入知识q 的范畴( q 是粗可导 的) ：当k o ，论域中没有元素能通过p 划入q 的初等范畴( q 是全不可导的) 。 2 4 知识表达系统 知识表示就是要研究用机器表示知识的可行的、有效的、通用的原则和方法。 最前，常用的知识表示方法有逻辑模式、框架、语义网络、产生式规则、状态空间、 剧本等1 5 3 3 1 。基于信息表的知识表达形式，是p o u g h 集理论中对知识进行表达和处 理基本工具。 信息表知识表达系统的基本成分是研究对象的集合，关于这些对象的知识是通 过指定对象的属性( 特征) 和它们的属性值( 特征值) 来描述的。一般地，一个信 息表知识表达系统s 可以表示为 s = 这里，u 是对象的集合，也称为论域，r - - - c u d 是属性集合。子集c 和d 分别 称为条件属性和结果属性，v = 一是属性值的集合，v ，表示属性r r 的属性值范 而 围，即属性r 的值域，f u r v 是一个信息函数，它指定u 中每一个对象x 的 属性值。 为了直观方便，u 也可以写成一个表，纵轴表示实例标记，横轴表示实例属性， 实例标记与属性的交会点就是这个实例在这个属性的值。这个表称为信息表，是描 述知识的数据表格。 定义2 2 s 对于每个属性子集b 互r ，定义一个不可分辨二元关系玳d ( b ) ，即 i n d ( b ) = ( x ，y ) l ( x ，y ) u 2 ，vb b ( b ( x ) = b ( y ) ) 显然烈d ( b ) 是一个等价关系，且 r n d ( b ) = n 孙i d ( ( b ) ) 6 b 每个子集b c 2 r 也可称为一个属性，当b 是单元素集时，称b 为原始的，否则 称b 为复合的。属性b 可以认为是用等价关系( 在该属性上的取值相等) 表示的知 识的一个名称，称为标识属性【5 l 】。 实际上，信息表这种表格知识表达系统是对客观对象的描述和罗列，表达的知 数据挖掘技术在产品概念设计中的应用研究 识是属于说明性的知识。但信息表包含的数据足以反映论域的时候，通过属性所对 应的等价关系就可以体现论域中的过程知识，即概念之间的逻辑关系或规则知识。 事实上，从信息表所表达的说明性知识中发现过程性知识( 规则知识) 就是知识发 现的研究内容p “。 在知识表达系统数据表中，列表示属性，行表示对象( 如状态、过程等) ，并且 每行表示该对象的一条信息。一个属性对应一个等价关系，一个表可以看作是定义 的一簇等价关系，即知识库【5 0 】。知识表达系统的表格表达称为决策表。 从表面上看知识表达系统和关系数据库模型很相似，实际上这两个模型有一个 根本的区别。关系数据库模型对表中所存储信息的意义不感兴趣，它强调的是有效 数据的结构和操作，因此包含信息的对象在数据表中没有表示出来；在知识表达系 统中，所有的对象都明显地表达出来，并且属性值都与对象的特征和性质的显式意 义相联系。知识表达系统强调的不是数据的结构和操作，而是分析数据中存在的实 际依赖性和数据简化，它更接近于统计数据模型1 5 0 l 。 2 5 决策表及其简化 决策表是一类特殊而重要的知识表达系统，它指出满足某些条件时，决策( 行 为、操作、控制) 应当怎样进行。决策表可根据知识表达系统定义如下： 定义2 2 6k = ( u ，a ) 为一知识表达系统，且c ，d c a 是两个属性子集，分 别称为条件属性和决策属性。具有条件属性和决策属性的知识表达系统可表达为决 策表，记作t = ( u ，a ，c ，d ) 或简称c d 决策表( c d d e c i s i o nt a b l e ) 。关系i n d ( c ) 和关系i n d ( d ) 的等价类分别称为条件类和决策类。 对于每个x u ，对于每个a e c u d ，定义函数： d ，：a v ，d 。( a ) = a ( x ) 函数d 。称为表t 中决策规则，x 是决策规则d 。的标识，即决策表中集合u 的 元素不表示任何实际