（管理科学与工程专业论文）基于粒计算理论的数据挖掘模型研究.pdf

abs t r act d a t a m i n i n g i s t h e p r o c e s s o f d i s c o v e r i n g i n t e r e s t i n g k n o w l e d g e f r o m l a r g e a m o u n t s o f d a t a s t o r e d e i t h e r i n d a t a b a s e s , d a t a w a r e h o u s e s , o r o t h e r i n f o r m a t i o n r e p o s i t o r i e s . i n t h e s e m a n y d a t a m i n i n g t o o l s , g r a n u l a r c o m p u t i n g i s a n e ff e c t iv e m e th o d . g r a n u l a r c o m p u t in g ( g r c ) i s a n u m b r e l l a t e r m t o c o v e r a n y t h e o r ie s , m e t h o d o l o g i e s , t e c h n i q u e s a n d t o o l s t h a t m a k e u s e o f g r a n u l e s i n p r o b l e m s o lv i n g . wh a t i s c a l l e d a g r a n u l e , i s a c l u m p o f o b j e c t s w h i c h a r e d r a w n t o g e t h e r 勿 i n d i s t in g w i s h a b i l i t y , s i m i l a r it y o r f u n c t i o n a li t y . g r a n u la r c o m p u t i n g m a y b e s t u d i e d b a s e d o n t w o re l a t e d i s s u e s , g r a n u l a t i o n a n d c o m p u t a t i o n . t h e f o r m e r d e a l s w i t h t h e c o n s t r u c t i o n , i n t e r p r e t a t i o n a n d r e p r e s e n t a t i o n o f g r a n u l e s , a n d t h e l a t t e r d e a l s w i也 比 。 c o m p u t in g a n d r e a s o n i n g w i 山g r a n u le s . n o w , i t h a s re c e i v e d m a n y a c h i e v e m e n t s f o r th e r e s e a r c h o f g r a n u l a r c o m p u t i n g , t h e re s e a r c h m e t h o d s i n c l u d i n g r o u g h喊 f u z z y s e t a n d q u o t ie n t s p a c e , e t c . t h e f o u n d a t i o n a n d d e v e l o p m e n t o f r o u g h s et i n fl u e n c e d a n d p r o m o t e d l a r g e l y f o r re s e a r c h a n d d e v e l o p m e n t o f g r a n u l a r c o m p u t i n g . a ft e r e m e r g e n c e o f r o u g h s e t , i t w a s i m m e d i a t e l y f o u n d t h a t i t s u c c e e d e d i n d a t a c l a s s i fi c a t i o n a n d k n o w l e d g e r e d u c t , a n d p r o m p t l y r e fl e c t e d t h a t i t w a s m o r e s u i t a b l e f o r re s e a r c h in g t h e s e c l a s s i fi c a t i o n a n d r e d u c t i n g r a n u l a r c o m p u t i n g t h e o ry . t h e re f o re , i t s o o n b e c o m e t h e h o t s p o t i n a c a d e m i c h o m e a n d a b r o a d . t h e a u th o r t a l k e d a b o u t g r a n u l a r c o m p u t i n g t h e o ry f ro m r o u g h s e t p e r s p e c t i v e . f i r s t, t h e a r t i c l e r e v i e w e d c l a s s i c a l r o u g h s e t 山 e e r y , a n d i n t h e l i g h t o f c u r r e n t i n c o m p l e t e i n f o r m a t i o n s y s t e m s , w e p r e s e n t e d a n e w ro u g h s e t m o d e l f o r i n c o m p l e t e i n f o r m a t i o n s y s t e m s . n e x t , t h e p a p e r e x p a t i a t e d p r o d u c t i o n o f g r a n u l a r c o m p u t i n g t h e o ry . f i n a ll y , w e 州 f o r w a r d a d a t a m i n i n g m o d e l b a s e d o n g r a n u l a r c o m p u t i n g , a n a l y z e d c e n t r a ll y d a t a p r e t r e a t m e n t m o d u l e , a t t r i b u t e s r e d u c t m o d u l e a n d r u l e m i n i n g m o d u l e , p r o p o s e d a n i n c o m p l e t i o n m e t h o d f o r i n c o m p l e t e d a t a , a t t r i b u t e s r e d u c t a r i t h m e t ic b a s e d o n g r a n u l a r i t y e n tr o p y , n o t i o n o f u s e r i d e n t i fi e d d a t a m i n i n g a n d it s i m p l e m e n t a r i t h m e t i c , a n i n s t a n c e w a s a p p e n d e d t o i ll u m i n a t e 山 e w h o l e d a t a 口 加 加9 油p s - k e y wo r d s : g r a n u l a r c o m p u t i n g ; d a t a m i n i n g ;g r a n u l e ; r o u g h s e t ; r u l e m 学位论文独创性声明 学位论文独创性声明 本人声明 所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。 据我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含 其 他 人已 经 发 表 或 撰 写 过 的 研 究 成 果 ， 也 不 包 含 为 获 得 之 彭 史声其 他 教 育 机构的学位或证书而使用过的材料. 与我一同工作的同志对本研究所做的任何 贡献均己 在论文中 作了 明确的说明并表示谢意。 学 位 论 文 作 者 签 名 (手 写 ): ) 司 辉签 字 日 期 : 2 p v 7 * 1 a !$ 日 学位论文版权使用授权书 本 学 位 论 文 作 者 完 全了 解 鱼s . a 匕有 关 保 留 、 使 用 学 位 论 文 的 规 定 ， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和 借 阅 本 人 授 权 鱼 鱼a 生可 以 将 学 位 论 文 的 全 部 或 部 分 内 容 编 入 有 关 数 据 库 进行检索， 可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文 在解密后适用本授权书) 学 位 论 文 作 者 签 名 。手 写 ) : 阁畔 签 字 日 期 : ,z 0 0 7 *扣 (s ei 导师签名 ( 手写) : ， 字 日 期 : 7 年 ” 学位论文作者毕业后去向: 工作单位: 通讯地址: 电话: 邮编: 第 1 章 引言 第1 章 引言 1 . 1引子 数 据挖掘( d a t a n e n i n g . d i v i ) 是 从存放在数据库、 数据仓库或其它信息库中 的大t数据中挖掘有用知识的过程。 它是一个多学科交叉研究领域，融合了数 据库技术、人工智能技术、机器学习、统计学、面向 对象方法学、信息检索、 高性能计算以 及数据可视化等最新技术的研究成果，经过十几年的研究，产生 了许多新概念和新方法。特别是最近几年，一些基本概念和方法趋于清晰，它 的研究正向 着更深入的方向发展，目 前已 成为国际上信息决策领域最前沿的研 究方向之一。 数据挖掘之所以成为未来信息处理的骨千技术之一，主要在于它以一种全 新的概念改变着人类利用数据的方式。 2 0 . 世纪，数据库技术取得了决定性的成 果，并且己经得到了广泛的应用。但是，数据库技术作为一种基本的信息存储 和管 理方式， 仍然以 联机事务处理( o l t p ) 为核心 应用，缺乏对决 策、 分析、预 测等高级功能的支持机制。众所周知，随着数据库容盘的膨胀，特别是数据仓 库以 及， e b等新型数据源的日 益普 及， 联机分析处理( o l a p ) 、决策支 持以 及 分类、聚类等复杂应用成为必然。面对这一挑战，数据挖掘和知识发现技术应 运而生，并且显示出强大的生命力。数据挖掘和知识发现使数据处理技术进入 了一个更高级的阶段。它不仅能对过去的数据进行查询，而且能够找出数据之 间的 潜在关系，进行更高层次的分析，以 便更好地做出决策，预测未来的发展 趋势等。通过数据挖掘， 有价值的知识、规则或更高层次的信息就能从数据库 的相关数据集合中 抽取出来，从而使大型数据库作为一个丰富可靠的资源为知 识 的 提 取 服 务 i ll 1 . 2数据挖掘的定义 数据挖掘最早是 在1 9 9 5 年美国 计算机年会( a c k上提出 的 概念， 数据挖掘 就是从大t的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其 第 1 章 引言 中的、人们事先不知道的但又是潜在有用的信息和知识的过程。另一种定义认 为，数据挖掘就是数据库中的知识发现( k n o w l e d g e d i s c o v e ry i n d a t a b a s e s . k d d ) ， 是指从数据库中识别有效的、新颖的、 潜在有 用的以 及最终 可理解的 模 式 的 非 平 凡 过 程 2 l. 其中“ 数 据” 是 一 组 事 实的 集 合 ( 如 关 系 数 据 库中 的 记 录 ) ; “ 模式” 是以某种语言来表示的一个表达式， 它可以 用来描述数据子集: “ 过程” 在数据挖掘中通常指多阶段的一个过程，包括数据准备、模式搜索、知识评估 以及反复的修改求精: “ 非平凡过程” 是指要有一定程度的智能性和自 动性，而 不像求平均值的那样的简单计算。 “ 新颖的”要求发现的模式应该是新的; “ 潜 在有用的”是指发现的模式将来有实际应用价值，如用于决策支持系统能够提 高经济效益: “ 最终可理解的”要求发现的模式能被用户理解。 1 . 3数据挖掘的过程 数据库中的知识发现， 应该是一个完整的过程， 该过程从大型数据库中挖掘 先前未知的、有效的和有实用价值的信息或模式，使用这些信息能够做出很好 的决策。数据库中的知识发现过程主要有以 下几个步骤组成: ( 1 ) 数据清理:为未知数据项赎值和消除噪音数据或不一致数据; ( 2 )数据集成:把多种数据源组合在一起; ( 3 ) 数据选择:从数据库中检索与分析感兴趣或与分析任务相关的数据; “) 数据转换:将数据变换或统一成适合挖掘的形式: ( 5 ) 数据挖掘:使用智能方法提取数据模式; ( 6 ) 模式评估:根据某种兴趣度度t，识别表示知识的真正有趣的模式; ( 7 )知识表示:使用可视化技术向用户展示挖掘出的知识。 从这里可以 看出，数据挖掘只是数据库中知识发现的一个步骤。然而，在 产业界、媒体和数据库研究领域，术语 “ 数据挖掘”比“ 数据库中的知识发现” 更为流行。因而，作者认为，应该从广义和狭义上去理解数据挖掘的概念。所 谓广义上的数据挖掘是指包含了一系列的非平凡过程的知识发现，数据源不仅 仅是数据库，还包括数据仓库、we b和其它信息库;所谓狭义上的数据挖掘就 是知 识发现的一 个具体步骤， 指的是 采用智能 挖掘方法， 比 如神经网 络、 r o u g h 集或遗传算法等，挖掘有趣模式的子过程，它是广义数据挖掘中的一部分。而 我们通常所谈论的数据挖掘指的是广义的数据挖掘，只有涉及到具体的挖掘算 第 t 章 引盲 法时才提及狭义的数据挖掘。 1 . 4致据挖掘的任务 数据挖掘的任务， 主要是从数据信息源中发现有用的并且用户能够理解的模 式. 棋式按功能 可以 分为预测型( p r e d i c ti v e ) 和描述型( d e s c r i p t i v e ) 模式， 按 实际作用可以 分为以下几种: ( 1 )分类模式 分类模式反映事物之间的共性以 及异类事物间的差异的特征知识。 它可以 提 取数据类的特征模型， 进而预测事物的发展趋势。 分类模式往往表现为一裸分类 树，从树根开始搜索， 沿着满足条件的分支走， 走到树叶就能确定类别。 这类方 法有决策树、统计分析、 r o u g h 集和粒计算等. ( 2 )关联模式 关联模式也称为关联规则， 是数据挖掘的一个重要课题。 它广泛用于购物篮 分析或者事务数据的分析当中。从大童超市购物事务记录中发现有趣的关联关 系，可以指导商家建立有利的市场经营策略，如商品的进货比率、摆放顺序以 及促销时机等。 对( x ) 0 当 且 仅当 x , n x; 核可作为计算所有约简的基础，因为核包含于每一个约简之中。 然而在实际生活中，上面定义的约简和核的概念作用有限，我们讨论的通 常是两个以上的知识系统，所以我们引入相对约简和相对核的概念。 2 . 2 . 2知识的相对约简和相对核 定义 2 . 6设p 和q是全域u上的等价关系族，则q的p正区域，记作 p o s , ( q ) ， 定 义 为 : p o s p ( q ) =u ? ( x ) x. u/ 口 等价 关系族q 的p 正区 域是全域u的 所有那些使用分 类u / p 所表达的知识， 能够正 确地分类于u / q的 等价类之中的 对象的 集合. 一 个 集合x相对于 一个等 价关系p 的正区 域就是这个集合的下近似p ( x ) ; 而一 个等价 关系q 相对于另一 个等 价关系p的正区 域的 概念是解决分类q的等价 类( 一 般视为决策类) 之中的 那些对象可由 分 类p的 等价 类( 一般视为条件类) 来分类的问 题 定义2 . 7设p 和q 是全域u上的等价关系族， 。 p 。 若 p o s , 幼 = p o s , _ j , ) 幼 ， 则称关系r 在p中 是q 可约去的， 否则称为q 不可约去的 ; 如果在p 中的 每个关 第2 章 r o u g b 集荃本理论 系r 都是q 不可约去的，则称p关于q 是独立的， 定义 2 . 8设p 和ra 是全域u上的等价关系族， 否则就称为是相关的。 所有p中仓 不可约去的等价 关系 的 集 合 被 称 为尸 的q 核， 记作c o r e q ( p ) 定义 2 . 9设p 和q 是全域u上的等价关系族，若 p的独立子集s r-p 有 p o s s 必 = p o s p ( q ) ， 则 称s是p的q约简。 p的 所 有 q约简的 集合 记成 r e d q 仍 。 定理2 . 2等价关系族p 的q 核等于等价关系族p 的所有q 约简的 交集. 即: c o r e g ( p ) 二 门 r e d q 仍 其中r e d q ( p ) 是 等 价 关 系 族p 的 所 有q 约简 的 集 合. 2 . 3信息系统与决策表 2 . 3 . 1信息系统 r o u g h 集理论中 的信息系统是一 个代数系统， 我们定义如下: 定 义2 . i o n s = ( u , a t , v , 力表 示 一 个 信 息 系 统， 其中u -_ xx z , . . . , x 是非空 有限 个体集 合， 称 为论 域，a t = 俩, a z , . . . . a . 是非空有限 属性的 集 合， 信 息 函 数 f , : u x a t 一啊， j = 1 么 ， m ， 对 于 每 一 个 个 体x , e u ， 每 一 个 属 性a , e a t 如 果 信 息 函 数f 在v 中 有 唯 一 的 一 个 值( 称为 确 定 属 性 值) ， 即 l a , ( x i ) i = 1 , 则 称 s 是 完 备 的 信 息 系 统 ， 否 则 称 s 是 不 完 备 信 息 系 统( v = t n 0 , ， l i表示 a r d , 指集合的基数， 下同) . 根据上述定义，当信息系统中每个对象对应的每个属性的属性值都是确定 时，这个信息系统是完备的，当信息系统某个对象的某个或某些属性的属性值 未知或存在多个属性值时，这个信息系统是不完备的。本论文中若无特殊说明， 讨论的都是完备信息系统。我们也往往把信息系统s = ( u , a t , v , 力也简记为 s = ( u , a t ) 。 给定一 个信息系统s 二 ( u , a t , v , n， 对于属性集a t 中的任意子集b， 我们 第2 章 r o u g h 集基本理论 总是可以 得到一个不分明 关系i n d ( b ) : i n d( b ) = ( u , u ) e u x v: va c - b, a ( u ) a a ( u ) ) . i n d ( b ) 是一个等价关系，且i 1 v d ( b ) 二f , i n d ( a ) .若 u i n d ( b ) u ，则表明 个 体“ 和u 关 于b中 的 属 性是 不 可 分明的 ， 即 我们不能 用b中的属性来区分u 和u 。一个信息表可以看成是全域u和其上定义的一族 等价关系，即知识库. 这样， 在r o u g h集中 对知识的 约 简就可以 转化为对信息 表中属性的约简。 2 . 3 . 2决策表 决策表是一类具有特殊形式的信息系统，它在决策系统中扮演着较为重要 的角色，其定义如下: 定 义2 . 1 1 p 71信息 系 统s = ( u , a 乃， 如 果c . d c a t 是 属 性 集 的 两 个 子 集， 并且有c ud二 a t ，c nd二 。， 则称s 是一个决策表， c , d分别称为a t 的条 件属性集和决策属性集， 一 般情况下决策属性只有一 个， 即d二 泌 。 设p - + s 为一条决策规则， 其中p = ( c , 二 c i ) a ( c 2 = c 2 ) 、二 a ( c二 c) ，s = ( d= d , ) . 闭为 满足p的 对象的等 价类， 阎为 满足s 的对象的等 价 类. 定义决策规则p - - s 的 支持度为“- p l n s l l / l ul ，确信度为r = 1 p n s i / i p 。 信息系统s = ( u , a t ) 如表2 . 1 , u - 1 , 2 ,3 ,4 , a 7 = g b , c , d ) , c = q b , c ) , d = ( d ) . 表2 . 1 信息 系统s = ( u , a t ) 3 1 0 1 0 4 0 1 1 1 表 2 . 1中不存在不确定的属性值，因此是完备信息系统。 a = l n b = 0 n c 二 1 - d = 1 的支持度和确信度的过程如下: a = 1 n b = 0 人 c = 1 = ( 1 ,3 ) , d = 1 = 1 , 4 ) . 因 此 。= ff p l n ( s l l 1 l u卜 1 ,3 ) n 1 1 , 4 ) 1 / 1 1 1 , 2 , 3 ,4 1 司.2 5 ; 计算决策规则 b = p n s l l 1 l 月= 1 1 , 3 r ) 1 , a 1 / i 1 , 3 1 = 0 . 5 . 第z 章r o u g h 集荃本理论 2 . 4决策逻辑语言 决策表作为一种特殊的数据表可以看作是关于现实和结果的命题的集合， 它可以 采用逻辑工具进行处理，我们把它看作一种特殊的逻辑模型， 这里称为 决策逻辑或r o u g h 逻辑。 2 . 4 . 1决策逻辑语言的语法 我们定义和讨论的决策逻辑语言由 原子公式组成。原子公式是一种属性. 属 性值对. 用命题连接词:与、或、非等通过规范化的方法构成复合公式，决策 逻辑语言可以形式地归纳定义如下: ( 1 )语言的符号集， 包括: 倒以 t - 属性常盘集。 ( b ) v = 品 v a 渭性 值 常 f 集 ( c ) 命题连接词集卜人 v ， 价.， 其中的 元素分别称为非、 合取、 析取、 蕴涵和等价。 ( d ) 括号 ( ， ) ( 2 )决策逻辑语言是满足下列两个条件: ( a ) 形如 ( .% v ) ， 或简写为的 表达 式称为原 子公 式， 对v a e a t , v e v a , ( 4 v ) 是决策逻辑语言的公式。 向如果0 , 9 是决策逻辑语言的公式，则一 护 ，o a 尹 ，4 v 尹 ，f 峥尹 和 沪 a v 也是公式。 2 . 4 . 2决策逻辑语言的语义 公式是论域中对象的描述工具，由 于论域中的对象可以 有相同的描述，故 公式同 样可以 描述子集。 特别地， 原 子公 式( q v ) 可以 被 解释为对那些在 属性a 下 取值为v 的对象的描述， 复合公式可以按照通常的方式给予解释。 为 了精确表达 这一思想，我们采用模型和可满足性的概念来定义决策逻辑的语义。 在决策逻 辑中， 一 个模型是指一个信息系统s = ( u , a t , v , f ) 。 在一个模型s 中， 我们通 过适当地解释公式，使得每一个公式变成表达某些对象性质的有意义的语句。 第2 章r a u 沙集基本理论 这个概念可以 通过一个公式被一个对象所满足的概念得到 精确的陈述。 一 个对象x e u 满足s 中的公 式9 ， 记作*s 9 或者简 记为xl-尹 面的条件被满足时: ， 当且仅当下 ( 1 ) x l= q v ) 当 且仅当a ( x ) = v ; ( 2 ) x 1= - 9 当 且仅当非x l= 9, ; ( 3 ) x l= / v p 当且仅当x l= q, 或x 1= 0 ( 4 ) x i= o a op 当 且仅当x l= .p 且x i = ! ; ( 5 ) x l= 0 -+ft 当 且 仅当x i= - o v g ; ( 6 ) x l= 9 =0 当且仅当x l= .p - 4 且x 1= 0 - ) , ? . 如 果ip 是 一 个 公 式， 定 义i -p i s = x e ul x l s g ) , i 叫 ， 称 为 公 式op 中 的 意 义 . 下面的定理解释了公式的含义。 定理2 . 3 ( 1 ) i( a , v ) 1 j = x e i l la ( x ) - ( 2 ) 卜f is = 一 ! v, i s ( 3 ) i p v o !， ， ! -p is u l o is ( 4 ) ! 9 a o ls = l g l$ 门 i o is ( 5 ) i -p - + 0 is = 一 l ol ls u i o l s ( 6 ) i 0 n o i. = a p i s n i o is ) u c - i op is 作l o ls ) 公式9 的 含义就是所有通过公式v 表达的 对象的 集合， 或者说公 式尹 是对象 集合l ol ls 在决策 逻辑语言中的描述。 在决 策 逻辑中， 我们也需要“ 真” 的 概念。 当 且仅当 i s is = u , 即 论域中的 所 有对象满 足该公式， 公式op 称为在信息系统s 中的 是真的。 当 且仅当 ! 叫 s 月 o is ， 我们称v 与0 在s 中 是等价的。 下面的定理给出了所介绍概念的简单性质。 定理2 . 4 ( 1 ) 1= s op 当 且仅当 冲is = u ( 2 )卜 ， 一 尹 当 且仅当 i v y = m ( 3 ) 1= s 9 - * 0 当 且 仅当 1 -p q 1 o ( 4 ) - - s p w 0 当 且仅当i q, 1s = 1 4 1s 这里我们强调，一个公式在一个信息系统中是真的， 但在另一个系统中却 可能是假的，但有些公式的真值却不依赖于出现在其中的 真实属性的 值，而是 第z 章 r o u g h 集基本理论 依赖于其本身的结构，这种公式在我们的讨论中具有特殊的作用。 2 . 5属性重要性 在病症诊断过程中，一些症状可能比 其它一些症状能为医生提供更多的信 息，也就是说识别症状时一些属性比 另一些属性更重要，怎样给各个属性确定 一个重要程度，便是属性重要性问 题。属性的重要性可以 通过一些辅助知识事 先假设， 或选择适合的 权数表达。 在r o u g h集中， 我们利用信息系统 或决策表 中属性的分类能力计算属性的重要性，完全从客观数据出发。 定义2 . 1 2在信息系统s = ( u , a t , y , f ) 中，a e a t ，o# b ca t , 属性a 在a t 中 的 相 对 重 要 性 定 义 为 y . 二 1 - i p o s ., - (. , ( a t ) 叻 u i ,属 性 集b 在a t 中 的 相对重要性定义为 y s = 1 - i p o s e t - b ( a t ) 功 u i 。其中 正区 域的 定 义如前面 的 定 义 : p o s , ( q ) = u p ( x ) . x. u/ q 单个属性或属性子集相对于整个属性集的重要性表达的是，当通过整个属 性集对对象分类时， 使用所有属性产生的 分类u / i n d ( a 力 的 正区域， 即a t 的a t 正区域u ， 相对于在使用去掉这个单个属性或属性子集后对对象分类产生的正区 域 p o s a t _ 1. 1 ( a t ) 或p o s a t - b ( a t ) 的 变 化 率 上述定义的是属性或属性子集相对于整个属性集中相对重要性， 我们还可 以计算属性或属性子集相对于其它属性子集的相对重要性。 定义2 . 1 3在信息系统s = 弘 a t , y , 力中， (d* b ca t , 4d* c c a t ，且 b r -) c= o , b 中的属性 b 相对 于属性集 c 的重要性定义为 : s g f b ( c ) = ! p o s b ( c ) ! 一 p o s e - 1 b ) ( 0 i ui 属性子集b 相对于属性集c的重要性 。 二，。， 。_ ! p o s e ( c ) i 一 i p o s e - b ( c ) .i 定 义为:s g f b .( c ) = 。 i ui 属性的相对重要性可以用于计算约简或相对约简， 当属性的相对重要性为幻 时，它是可约去的，否则是不可约去的，因此所有相对重要性不为 0的属性的 集合构成了核，在核的基础上求约简就降低了问题的难度。基于信息摘知识约 第2 章r o u g h 集荃本理论 简方法就是由此得来的。 2 . 6不完备信息系统 p a w l a k 的 经典r o u g h 集模型是以 等价关系为基 础的， 要求信息系统中的数 据具有很强的等价关系，但是人们在实践中所收集到的 表达知识信息的数据往 往是不完备的，某些对象的一些属性值是不确定的，这就产生了不完备信息系 统，因 此建立对象间的等价关系显得不太可能，在处理时p a w l a k 的 经典r o u g h 集模型似乎 无能为力。 这就需要对经典的r o u g h 集理论 进行扩展， 将等价关系 放宽，以满足实际的需要。 2 . 6 . 1基于容差关系的r o u g h 模型 m .k ry s z k i e w ie 2 提出 的 容 差 关 系 14 7 1 中 ， 把不 确 定 属 性 值 看 作 空 值， 用“ . ， 表示。这里我们把不确定属性值看作一个集合，完全不确定属性值取整个属性 值集，部分不确定属性值取值为值集的子集，在其他几个模型中我们也用集合 代替 “ ”，以便可以更好地处理部分不确定属性值， 扩大各模型的使用范围。 定义2 . 1 4在不完 备信息系统限制容差关系要求的条件为:两个对象必须在某些属性同时具有确 定属性值，并且存在属性值相同的属性;“ 相同度相似关系要求的条件为:两 个对象在某些属性下都有确定属性值，它们的确定属性值相同，并且具有相同 第z 章 rou g h 集荃本理论 属性值的属性个数与总属性个数之比不小于“。 第3 章 粗计算理论 第 3 章 粒计算理论 粒计算是一种描述空间或求解问 题的方法， 能够在不同粒度下描述空间或求 解问 题， 使得空间的描述或问题的求解更加可行。虽然粒计算理论的研究仍处 于探索阶段， 许多方面都不成熟，但是粒计算的荃本思想在软计算、 知识发现、 数据挖据、w e b 智能等领域都得到了 广泛的应用。 本章 我 们介绍当 前从r o u g h 集理论 工具上研究粒计算取得的 一系列 成果。 3 . 习信息粒与信息粒度 3 . t . 1信息粒与倍息较化 人类认知、推理和作决策都是在大t的信息中进行的，由于人类的能力有 限，把大a复杂信息按其各自 的特征和性能将其划分成若千较简单的 块，每个 块被看成一个信息粒，这种处理信息的过程称为信息粒化，粒化涉及到整体到 部分的划分。 例如， 停车场问 题的信息粒化，是指按车子的性能、型号和大小 而将停车场划分为若干块，其每一块将停放一种性能或一种型号或一种大小的 车子。这里所说的块就是信息粒。这就是一个通俗的停车场问题信息粒化的例 子 f1 o z q 就广泛的意义而言，粒化涉及整体到部分的划分。由于一个粒是一种个体 块， 它通过不分明 性、相似性、近似性或功能性被链接在一起。 粒可以是密集 的或稀疏的、清晰的 或模糊的，它完全依赖于粒的 边界是否被准确地定义。 设s - - ( u , a ) 是一个信息 系统， 其中u是 所讨论对象的全域， a是 属性集， ( q v ) 或是指定义在s 上的一种描述，其中a e a 是属性集a上的一个属性， v 是a 关于 个体集u 上的 个体x e u的 属性值， 也就是v = a ( x ) 。 于是( a , v ) 或被视 为r o u g h 逻 辑中 的 一个原 子公 式. 经典 逻辑 连接词 将诸多 ( 4 v ) 或组 合 起来， 则 可 得 到r o u g h 逻 辑 中 的 合 式 公 式o p . m ( 叻= x e u : x 卜 ， 讨被 称 作s 上 公式， 的 意 义 集， 其中 符 号 lo w ， 是 满 足 或 者 可 能 满 足符， 即 所 有 满 足尹 或 者 可 能 满 足p 的 u 上个体的 集合， 其中m是意义函 数符. 因 此二元对( 9 , m ( .p 刀 是s 上的 一个粒. 第3 章 粒计算理论 原子公 式a , 的 粒记成( a . , m ( a . ) ) ， 被称作基本粒， 属性( 关系) a 将u 划分成的 每 个 等 价 类 都 是 基 本 粒 显 然m ( f ) = 。 被 认 为v 在s 上 取 假 ， 城叻= u 被 认 大 f 在s 上取 真， 而。州4p ) q u， 则9 在s 上为可满足， 当qp 在u 的 任何子 集xqu 上不可求 其愈义集时，则- ( 叻在s上为不可观察， 于是可利用它的 下近似粒 ( ap, $ ( 二 ( ) ) ) 和上近似粒( t k , , b ( m ( .p ) ) ) 来 近似地表达 其愈义集_b ( m ( 4p ) ) 和 b ( m ( q ;刀， 其中b ca 是属性集上的一个子集. 3 . 1 . 2信息粒度 r o u g h逻辑中原子公式的 基本粒为( a . , m ( a . ) ) ， 合式公式4p 及其意义集 m ( 4 j) 组成的 信息 粒为( 9 , 二 ( 哟 ， 对于每个信息粒的大小， 我们用粒度 衡f. 信 息粒度是对信息粒大小的度t，是对信息和知识细化的不同 层次的度量。 定义 3 . 1设u 为 一个论域， r 为 属性 ( 集) ，帆m 印 刀 是对象在 r 上粒化形成 的 一个信 息粒，( 40 , m ( o ) 的 粒度为8 ( v ) = q m ( rp ) i / i ui 。 3 . 2较的二进制表示 3 . 2 . 1 位的二进制裹示 信 息 系 统s = 以a 乃中 ， 其中u = ( xx 2 , . . . , x . ) 是 个 体， a t = ( aa 2 , . . . , a) 是属性集。 任何子集b ga t 均可将u划分成互不相交的等价类， 等价类被定义 为粒， 显然是 r o u g h集理论的扩充，因为施行粒计算比 施行等价类计算要快得 多、 灵活的多。 然而， 对每个等价类表示的粒， 粒中的元素都可给出 它在全域u 上的 位2，用该元素的下标表示。如果以 下标对应于二进制数的位数，则该粒 可用一 个 二 进制 数定 义， 即x , e u， 对 应于 二进制 数的 相 应第1 位上 置1 。 显然 二进制数 长度恰好等于u的基数 1 0 .4 2 ) 表 3 . 1是个体斌予颜色特性的信息系统，按属性颜色分类，则可得到商集 u i i n d ( 司 r- - a i , a 2 , a 3 , a 4 , a s ， 其中a 1 = 【 红 卜 x j .x 3 .x 表3 . 3多属性关系列表 颜色( a )型号( b )价格( c ) 中贵贵中暄贵中贵贵中中贵 妇j叫便，月， b，re肠鲡肠b，co鲡肠肠肠扬鲡肠 红黄红蓝白蓝黄红红黄黑红 xl为x，为为勾勿翔匆xi0 xjixiz ( 3 ) u i md ( 价格卜( c j , c 2 , c s ) ，其中， c j = 便宜 】 x0 0 0 1 0 0 0 0 0 0 0 , c 2 = 【 中卜 1 0 0 1 0 0 1 0 0 1 1 0 , c 3 = 贵 = 0 1 1 0 0 1 0 1 1 0 0 1 0 如果粒化要求的是多个属性的组合，比如红色并且价格贵的产品为一个信 息粒， 则就要对信息粒a ， 和。进行组合， 新的信息粒为这两个粒意义集的交集， 即9 = a , a c 3 , m ( op ) = m 俩) r ) - ( c 3 ) . 两 个 意 义 集的 交 集 恰 好 可以 通 过 它 们 二 进 制数的按 位与 运算得到， 得到新的信息粒op = 1 0 1 0 0 0 0 1 1 0 0 1 所谓满足语句s ， 意思是程序被执行时， 对s 中 所播的 数 据 的 输 入 或 赋 值 使 得s 有 意 义 。 所 以 ， m ( g ) 二 u s . g m ( s ) 是 一 个 程 序 的 基 本 粒 ， 它表示程序的输入是符合程序的说明并且使得程序中的语句有意义。所以，一 个 程 序 的 基 本 粒 被 记 成 ( g m ( g ) ) = u s . c m ( s ) 10 ,19 7 . 3 . 3 . 1 . 4以局部粒定义整体拉 设v, 是形如a ， 描述或称原子的 逻辑组合， 所以9 是定 义 在信息系统s上的 通常的 r o u g h逻辑公式，vp中一切子公式的集合被记成: a p p ( q ) = ( a 1 9 2 , . . . . p t )，则用 - ( f , )来定义 m ( 01 ) ，也即 ( v , m ( f 二 ( p e ( 叻, ( n m ( , ) , 任 a p p e ( 州 ) 如果9 , e , b ( m ( ,p , ) ) ) a p 已 ( 叻， 但01 , 在给定xg. u上不可观察，则可将9 , 移到 和( b o b ( m ( q , ) ) ) 上去观察，也就是用( bg b ( m ( .p , ) ) ) 和 , b ( m ( v , ) ) ) 替换( b ,pm ( b q, , ) ) 所以 它 被写 成下 面 形 式: ( , m ( ) ) = ( p 8 t 4 , ( m j ) 画 ab p , ) ) ) , v , 。 a p p s ( ) ) o ,t . 3 . 3 . 2较语言 定义 3 . 3( 语法) 语法被递归定义如下: 让我 们用l s 表示信息系统s 上由 基 本粒组成的 语言， 它的 p 0 , 们】 ( 1 ) 取自 于属性子集b f_a t 上形如( ( a , v ) ， 二 ( a , v ) ) 或( a . , m ( a . ) ) 的 粒是l s 第3 章 粒计算理论 中的语句: ( 2 ) 形 如( , m ( 刀 和( 孙， 。 ( 孙) ) 的 粒 ， 其中 9 是 一 个 取自 于s 上 的 描 述 的 布尔 组合，当op 中 不含r o u g h逻辑连接词时， 它便是一个描述或原子， 则这 种形 式也 是l s 中 的 语 句; ( 3 ) 若9 和0 是l s 中的 语句， 则 ( v , 功 (朔 ， ( -p 八 o , m ( ,p 八 沪 ， ( 4p v 六 m ( op v ， ， ( b (奶, - ( b 卜叻) )， ( b ( - 4 ) , m ( b ( ) ) )， ( b ( qi n o ) , m ( b ( .p n 4 ) ) )， ( b ( lp n 0 ) , m ( b ( g p n 0 ) ) ) ( b ( .p v 0 ) , m ( b ( ,p v 4 ) ) ) ， ( b ( 97 v o ) , m ( b ( p v o ) ) ) 也 都 是 l s 中 的 语 句 。 ( 4 ) 经有限 次引 用( 1 ) 一( 3 ) 得到的 语 句都 被 看成是乌中 的 语句。 定 义3 . 4( 语 义) 被确定 在信息 系统s 二 价洲乃上的 语言几， 其语 句的 语 义被递归定义如下: 1 0 1 ( 1 ) m ( a , ) = 扛 u: a ( x ) = v e 玛， 其中v 是属性集值， m为 语义m 数符， a ( x ) 包括可能等于v 的x ，即 边界线上的 元素，以 下类推: ( 2 ) m 卜叻= u一 m 切 ; ( 3 ) m ( 4p n ) = m ( op ) n二 ( 4 ) ; ( 4 ) m ( p v 0 ) = m ( p ) vm ( o ) . 带峥和什连接词的语句都可用带、 人 v 连接词的语句替换。 我们可以注意到，任意的粒都是一个语句或称