（计算机软件与理论专业论文）粒度计算与粗集、泛系和商空间理论的研究.pdf

要 粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的 理论、方法、技术和工具的研究。它是词计算理论、粗糙集理论、商空间理论、 区间计算等的超集，也是软计算科学的一个分支。论文以粒度计算为主线，对商 空间理论与粒度计算、泛系算子与粒度计算、粗集与粒度计算进行了较为深入的 研究，提出格粒度计算模型。论文取得了以下研究成果： 论文将商空间理论引入到粒度计算中，并将概念用子集表示，将不同粒度 的概念表示为空间的一个划分商空间。基于商空间，粒度计算可以在给定知 识基上的各种子集之间进行转换，对同一问题取不同层次粒度上的论域、结构和 属性加以合成，通过两种分层递阶求解方法，利用商空间中细粒度空间对粗粒度 空间的“保真性”定理以及粗空间对细空间的“保假性”定理不断将不同层次的 结果加以推理综合，最后得到结果，这种通过分层求解的商空间问题求解模式大 大简化了问题求解的难度。在此基础上，论文将模糊商空间中的理论和方法应用 到模糊粒度计算中，讨论模糊商空间中粒度的转化问题。 利用泛系理论中系统和转化的思想，论文介绍并采用等价算子将一般二元 关系转化为等价关系，从而可以将普通关系通过不同的泛系等价算子转化为知识 库的集合。在此基础上首次提出泛系粗集、泛粗等价、泛粗包含的概念，推导出 泛系粗集中泛粗等价、泛粗包含与粗集中等价、包含之间的内在联系。推导并计 算出在不同泛系算子的作用下粒的大小、最大粒子、最小粒子以及精度的变化规 律。 论文从传统粗集理论出发，讨论在粗集理论中粒度、分辨度与熵的关系。 针对信息系统提出重要度的概念，推导出信息系统中重要度与粒度之间的内在联 系和规律。在决策系统中，根据重要度与粒度之间的关系，提出了最小约简算法， 推出决策系统中重要度与协调度之间的联系。 论文首次提出了格粒度计算模型，讨论了在此模型上所进行的上卷、下钻 等基本操作，研究数值属性离散化的各种方案，并将一个信息表的各种可能离散 化方案组织成一个格空间离散格。证明离散格是一个布尔代数，构造了离散 格到划分格的映射，研究了离散格及划分格中的信息粒度变化规律、条件属性对 决策属性的正区域和条件信息熵的变化规律。 关键词：商空间；粗集；模糊集；泛系算子；粒度计算；格粒度计算模型：属性 约简 a b s t r a c t g r a n u l a rc o m p u t i n gi sak i n do fn e wc o n c e p to fi n f o r m a t i o np r o c e s s i n ga n d c o m p u t a t i o n a ln o r m a lf o r m ，o v e r l a ya l lr e l e v a n tr e s e a r c h e so ft h eg r a n u l a r st h e o r i e s ， m e t h o d s ，t e c h n i q u e sa n dt o o l s i ti ss u p e r s e to ft h ew o r dc o m p u t a t i o n a lt h e o r y , r o u g h _ s e t st h e o r y ，q u o t i e n ts p a c et h e o r ya n di n t e r v a lc o m p u t i n g i ti sa l s oab r a n c ho fs o f t c o m p p u t i n gs c i e n c e t h et h e s i sf o c u s e so ng r a n u l a rc o m p u t i n g ，w h a t a r ei n v e s t i g a t e d c o n c e r nw i t hq u o t i e n ts p a c et h e o r y , o p e r a t o r so fp a n s y s t e m s ，r o u g hs e t st h e o r ya n d g r a n u l a rc o m p u t i n g t h em a i nr e s e a r c hr e s u l t sa r ec l a r i f i e da sb e l o w b a s e do nt h eq u o t i e n tt h e o r y , t h eg r a n u l a rc o m p u t i n ge x p r e s s e st h ec o n c e p ta sa s u b s e t ad i v i s i o ni sc o m p o s e do fas e to fc o n c e p t s ，i ti saq u o t i e n tt h e o r y g r a n u l a r c o m p u t i n gi sas t u d yw h i c hr e s e a r c ht h es u b s e t sr e l a t i o na n dc o n v e r s i o n ，g e ta n d s y n t h e s i z et h ed o m a i n ，s t r u c t u r ea n da t t r i b u t eo fg r a n u l a r i t yi nd i f f e r e n tl a y e r s t h e r e a r et w oi m p o r t a n tt h e o r e m s ：f i d e l i t yt h e o r e mi nf i n eg r a n u l a t i o nt oc o a r s eg r a n u l a t i o n a n dp r o t e c tf a l s et h e o r e mi nc o a r s eg r a n u l a t i o nt of i n eg r a n u l a t i o n u s et h e s et w o t h e o r e m ，w ec a ni n f e ra n ds y n t h e s i z et h ed i f f e r e n tl a y e r sr e s u l t ，g e tt h el a s tr e s u l t ， t h u sd e c r e a s et h ec o m p l e x i t yo fp r o b l e ms o l v i n g o nt h i sf o u n d a t i o n ，t h i st e x ta p p l y t h ef u z z yq u o t i e n ts p a c e st h e o r ya n dm e t h o di nf u z z yg r a n u l a rc o m p u t i n g ，d i s c u s st h e g r a n u l ac o n v e r s i o np r o b l e mi nf u z z yq u o t i e n ts p a c e u s i n gt h et h o u g h t so fs y s t e ma n dc o n v e r s i o ni np a n s y s t e mt h e o r y , t h i st e x t i n t r o d u c ea n du s ee q u i v a l e n c eo p e r a t o rt oc o n v e r tt h eo r g i n a lb i n a r yr e l a t i o n si n t o e q u i v a l e n tr e l a t i o n s ，g e td i f f e r e n tk n o w l e d g eb a s e st h r o u g hd i f f e r e n te q u i v a l e n c e o p e r a t o r s t h e t e x t p r e s e n tt h en e wc o n c e p t s o ft h eg e n e r n i z e dr o u g hs e t s g e n e r a l i z e dr o u g he q u i v a l e n c ea n dg e n e r a l i z e dr o u g hi n c l u s i o n ，d e d u c et h ei n h e r e n t r e l a t i o n sb e t w e e n g e n e r a l i z e dr o u g he q u i v a l e n c ea n do r d i n a r ye q u i v a l e n c e ，t h e g e n e r a l i z e dr o u g hi n c l u s i o na n do r d i n a r yi n c l u s i o ni nr o u g hs e t st h e o r y i td e d u c ea n d f i g u r eo u tt h er u l e so ft r a n s f o r m a t i o no ft h eg r a n u l e ss i z e ，t h em a x i m i z eg r a n u l e ，t h e m i n i m i z eg r a n u l e ，t h ep r e c i s i o n t h r o u g ht h ed i f f e r e n to p e r a t o ro f p a n s y s t e m f r o mt h er o u g hs e t st h e o r y , t h i st e x td i s c u s s e st h er e l a t i o n sb e t w e e nt h e g r a n u l a r i t y , r e s o l u t i o na n de n t r o p y i ni n f o r m a t i o ns y s t e m ，t h et e x tg i v ei nt h ec o n c e p t o fi m p o r t a n c ed e g r e e ，d e d u c et h ei n h e r e n tr e l a t i o na n dr u l e sb e t w e e nt h ei m p o r t a n c e d e g r e ea n dg r a n u l a r i t yi nd e c i s i o n m a k i n gs y s t e m ，b a s e do nt h er e l a t i o nb e t w e e n i m p o r t a n c ed e g r e ea n dg r a n u l a r i t y ，a d v a n c et h em i n i m a lr e d u c t i o na l g o r i t h m s ，d e d u c e t h er e l a t i o nb e t w e e ni m p o r t a n c ed e g r e ea n dc o o r d i n a t i o nd e g r e e t h et e x tp o s e st h em o d e lf o rl a t t i c eg r a n u l a rc o m p u t i n g ，d i s c u s s e st h es c r o l l a n dg o i n gd o w no p e r a t i o ni nd a t aw a r e h o u s ed a t ad i s c r e t i z a t i o ni sat a s ki nm a c h i n e l e a r n i n ga n dd a t am i n i n g ，t h et e x td i s c o v e rt h er e l m i o no fv a r yd a t ad i s c r e t i z a t i o n s a l t e r n a t i v e s ，o r g a n i z ea l lk i n do fd a t ad i s c r e t i z a t i o n sa l t e r n a t i v ei n t ol a t t i c es p a c e ，i s e n t i t l e dd i s c r e t el a t t i c e i tp r o v e st h ed i s c r e t el a t t i c ei sab o o l e a na l g e r a ，g i v et h e t h e o r e m si nd i s c r e t el a t t i c e ，s t r u c m r et h em a p p i n gf r o md i s c r e t el a t t i c et od i v i s i o n l a t t i c e ，r e s e a r c h e st h er u l e so ft h ei n f o r m a t i o ng r a n u l e st r a n s f o r m a t i o n ，p o s i t i v e r e g i o nw i t hc o n d i t i o na t t r i b u t e st od i c i s i o na t t r i b u t e sa n de n t r o p y k e y w o r d s ：q u o t i e n ts p a c e ，r o u 曲s e t s ，f u z z ys e t s ，o p e r m o r so fp a n s y s t e m s ，g r a n u l a r c o m p u t i n g ，m o d e lf o rl a t t i c eg r a n u l a rc o m p u t i n g ，a t t r i b u t er e d u c t i o n v 原，创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名：兰叠盈 日期： ：2 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：墨塑查导师签名：窆杰丝日 期：虹，j 绪 论 1 绪论 1 1 研究现状 粒度计算是信息处理的一种新的概念和计算范式，现己成为人工智能领域 研究的热点之一。2 0 世纪6 0 年代，美国著名数学家z a d e h 提出模糊集合论。在 此基础上，于1 9 7 9 年首次提出并讨论了模糊信息粒度化问题，推动了模糊逻辑 理论及其应用的发展，但在当时未引起足够的重视。接着，z a d e h 在1 9 9 6 年提 出“词计算理论，i ”，标志着模糊粒度化理论的诞生，其旨在解决利用自然语言， 进行模糊推理和判断以实现模糊智能控制。基于z a d e h 的模糊集论，进行粒度计 算理论和方法的研究，已成为“粒度计算”的重要研究方向之一。随后，美国多 特蒙德大学的h e l m u t t h i e l e 教授于1 9 9 8 年发表了“词计算理论的语义模型”，促 进了词计算理论的发展。词计算理论对i n t e r n e t 上海量信息资源的高效利用有着 深远的影响。波兰学者p a w l a k 于1 9 8 2 年提出了粗糙集理论 2 】。由于粗糙集理论 具有很强的定性分析能力，能够有效地表达不确定的或不精确的知识，善于从数 据中获取知识，并能利用不确定、不完整的经验知识进行推理，因此在知识获取、 机器学习、规则生成、决策分析、智能控制等领域获得了广泛应用，特别是在数 据挖掘领域获得了巨大成功，业已成为粒度计算研究领域的主要方向之一。加拿 大r e g i n a 大学教授y y y a o 在研究粗糙集理论的基础上，提出了基于邻域系统的 粒度计算模型i l 引，并成功应用于知识发现领域。粒度计算作为专门的术语，首次 出现在z a d e h 的文献中。后来，t y l i n 、y y y a o 和z a d e h 又在文献中着重描述 了粒度计算的重要性，这激发了人们对它的研究兴趣。随后，大量的关于粒度计 算研究的文献相继发表。而且在国际上形成了专门的研究群体，定期召开关于粒 度计算的国际研讨会。 在国内，张钹院士和张铃教授提出了基于商空间的粒度计算模型 1 9 1 3 5 】。 其利用子集来表示概念，不同粒度的概念就体现为不同粒度的子集，一簇概念就 构成空间的一个划分商空间( 知识基) ，不同的概念簇就构成不同的商空 间。而粒度计算问题，也就等价于研究在给定知识基上的各种子集合之间的关系 和转换。对同一问题，可以采取不同的粒度，通过对不同的粒度的分析，综合获 釉斌萼 硕士学位论文 取对原问题的求解。在此基础上，张铃、张钹于2 0 0 3 年提出模糊商空间理论18 1 。 总的来看，粒度计算的研究在国内属于起步阶段，尚未引起广泛关注。但我们相 信，不久的将来会有越来越多的学者加入到该领域的研究中来。 1 2 论文组织 本文共六章，第一章介绍粒度计算的研究现状与背景，第二章到第五章， 分别从商空间、泛系算子、粗集与模糊集、离散格与划分格四个方面出发，讨论 了基于商空间的粒度计算、基于泛系算子的粒度计算、基于粗集与模糊集的粒度 计算和格粒度计算模型，具体组织如下： 第二章分析了商空间理论与粒度计算之间的关系。商空间理论用三元组( x ， f ，t ) 描述一个问题，通过对x 的粒度进行简化，产生一个新的较大粒度的论域 x 】，把原问题( x ，f t ) 变成新的层次上的( x 】， f ，【t 】) ，此时可以从较 粗粒度 x 】上去观察和解决问题。在此基础上构造了两种分层递阶结构，用以实 现同层粒的合成与分解以及不同层粒之间的转化。结合处理不确定信息的模糊集 理论，提出模糊商空间理论的概念，推导出模糊商空间理论的性质，举例说明商 空间理论在数据仓库中的应用。 第三章在基于泛系理论的基础上，提出了泛系粗集的概念。通过泛系算子， 将普通关系转换为各种不同的等价类的集合，构成各个不同的知识库。在此基础 上，运用等价算子和相容算予，通过推导提出泛粗等价和泛粗包含的概念，并讨 论了在不同泛系算子的作用下，粒子基数、最大粒子、最小粒子和精度的变化情 况。 第四章从粗集理论的基础出发，讨论了在粗集理论中粒度、分辨度与熵的 关系。在信息系统中，根据信息系统重要度的概念，推导出信息系统中重要度与 粒度之间的内在联系和规律。在决策系统中，根据重要度与粒度之间的关系，提 出了晟小约简算法，推出决策系统中重要度与协调度之间的关系。 第五章提出了离散格的概念，证明离散格是一个布尔代数。构造了离散格 到划分格的映射，研究了离散格及划分格中的信息粒度变化规律、条件属性对决 策属性的区域和条件信息粒的变化规律。在离散格中随着离散化方案等价类的加 粗，条件属性对决策属性的正区域下降，条件信息熵上升。 绪论 1 3 论文的创新点 本文的创新之处在于将商空间理论引入粒度计算，通过两种分层递阶结构， 可以实现同一层各个不同粒与不同层粒之间的合成、分解与转换。在泛系理论的 基础上，本文首次提出了泛粗等价和泛粗包含的概念，通过不同的泛系算子将普 通关系转换为各种不同等价类的集合，构造不同的知识库，讨论在不同泛系算子 的作用下，不同知识库所对应的粒子基数、最大粒子、最小粒子和精度的变化情 况。从传统粗集的角度出发，本文了讨论分辨度、熵与粒度之间的关系，以期在 问题求解时从适当的层次出发去分析和解决问题，降低求解问题的复杂度。根据 数据立方体的特点，本文提出了基于格的粒度计算模型，构造了离散格和划分格， 提示了两者在粒度方面的内在联系，对于数值离散化有一定的意义。 萄耐文萼 硕士学位论文 2 商空间理论与粒度计算 在问题求解中，一个问题用三元组( x ，f ，t ) 来描述，其中x 表示所研 究对象的全体，称为论域：f 是从x y 的映射：y 是实数集合或一般的空间， 对比x ，有一个相应的厂( x ) 表示元素x 的某些属性；t 是论域的结构，反映 x 中各元素的相互关系。分析或求解问题( x ，f ，t ) ，是指对论域x 及其有关 的结构、属性进行分析和研究。人类从不同的粒度来处理问题，设x 是论域中 最细的粒度，从一个较粗的角度来看问题，就是将x 按某种方式简化，把性质 相近的对象看成是等价的，把它们看成整体作为一个元素构成粒度较大的新论域 【x ，这样就把原来问题的( x ，f ，t ) 转化为问题( 【x ，嘲， t 】) 。这一简化 过程与数学中商集的概念相同，故以商集作为不同粒度世界的数学模型i 。面对 复杂对象，如何描述对象往往成为解决问题的基础，为此，提出了一种不同粒度 世界的描述方法商空间法【1 8 l 。在商空间法中用一个三元组( x ，f t ) 描述 个问题，在其论域上引入等价关系r ，对应于r 的商集【x 】，然后将 x 】作为新 的论域，对它进行分析、研究，从而将问题表述成不同的粒度世界，进而达到简 化问题、解决问题的目的。与粗糙集、决策树等方法相比较，商空间法具有更强 的表达能力，它不仅可以定义多种不同的属性函数，而且可以描述论域中的元素、 元素之间的相互关系( 即结构) 、运算等。 2 1 信息粒化 粒度计算的基本问题包括两个主要的方面，一个是如何构建信息粒度，另 一个是如何利用粒度去计算。前者处理粒度的形成、粗细、表示和语义解释，而 后者处理怎样利用粒度去求解问题。信息粒度的形成、表示、粗细、语义解释， 信息粒子的大小；信息粒度粗细与求解有效度的关系：信息粒度的运算法则；信 息粒度之间及其与外部环境的关系等，这些内容构成一个粒度世界【3 。粒度世界 是否构造得合理极大地影响着问题求解的效率。 定义2 1 粒度设给定论域u 和u 上的一个关系r ：u 斗p ( c z ) ， 商空间理论与粒度计算 u = u g ，则称每一个g ，为一个信息粒子， g ，i f ) 是论域的一种粒度。其 中，p ( u ) 表示论域u 的幂集：r 代表等价关系、不可区分关系、功能相近关系、 相似关系、相等关系、约束、相容关系、复合关系、模糊关系、属性、投影、结 构关系和一般的函数等【5 】口 1 ) 当f f ，i ，g ，n g j = o ，则称 g ，) ，i r 是论域的无重叠粒度划 分，简记为 g ，) 。= u ： 2 ) 当i ，j f ，i j ，g 。n g ，g ，则称 g i r 是论域的一种覆盖，简记 为 g ，) 。= 。 定义2 2 粒子的大小设u 是给定的一个论域，粒度划分u = u g ，n g , ，e r 粒子g 的大小为d ( g ，) = c a r d ( g ，) = i g 卜f 叔。 当论域为离散情形时，积分表示信息粒子g 所含个体的总个数，也可能是 可列个：当论域为连续状态时，积分表示信息粒子g 。长度的度量值，也可能是 无穷大或不可数；当g ，为模糊信息粒子时，公式中的g 表示集合 x i 2 g ( x ) o ，x u ) 。 定义2 3 信息粒度粗细设r 是论域上关系的全体，j ；i r 。、r ：r ，若对 x ，y u 、x r l y jx r 2 y ，则称r 】比r 2 细，简记为r 2 r l 。一个关系代表一种分 类，因此，也可表示粒度粗细。设r 。 r ， r ： r 。，表示一个嵌套关系簇， 其中r 。代表论域本身是一个等价类，即最粗的划分：r 。代表 v x ，y u ，x r 。y x = y ，即最细的划分；其他的表示中间层次的划分。同一论 域的粒度之间存在不能比较粗细的情形。 我们知道，信息粒度的粗细影响着计算复杂度和问题的求解效度【1 6 】【3 5 】。在 问题求解过程中，同一个粒度世界或不同粒度世界所要求描述的信息含量和相互 变换决定了信息粒度的粗细优化。粒度计算的目的就是在误差允许的范围内，尽 量找到计算复杂度最小的足够满意的可行近似解。因此，可以认为粒度计算是降 萄耐虫孽 项士学位论文 低计算复杂度的有效工具。总之，如何在问题求解时选择恰当的粒度层次，以使 求解效度达到最佳，这是粒度计算的一个关键内容之一。 2 2 商空间的性质 设( x ，t ) 是拓扑空间，其中t 是x 的拓扑。设r 是x 上的一个等价关 系，对x 可以得到对应的商集，记为 x 】。现在，在【x 上定义由t 诱导出的拓扑， 记为 t ，称 t 】为商拓扑，( 【x ， t 】) 为商拓扑空间。由拓扑学的原理知，从商 空间的结构可以了解原拓扑空间的某些性质，并有如下命题 2 8 】 2 9 1 。 命题2 1p ：( x ，t ) _ ( 瞵 ， ， ) 是自然投影，所以p 是连续的。若a 亡且 a 是x 中的连通集，则p ( x ) 是 x 中的连通集。 命题2 1 表明，若一个问题在原论域x 中有解( 是连通的) ，在适当的粗粒 度论域 x 】上也有解。反之，若粗粒度论域上无解，则原问题必无解( 不连通) 。 这个性质说明，商空间变换的保假的特点。 命题2 2 设r 是相容的，若x ，y ( x ，t ) 且x m i n ( r ( x , ，x 2 ) ，r ( x 2 ，y ) ) = m i n ( 1 ，r ( x 2 ，y ) ) = r ( x 2 ， y ) 。 同理可以得到r ( x 2 ，y ) r ( x 】，y ) 。故有r ( x l ，y ) = r ( x 2 ，y ) 。由此得到v x i ， x 2 a ，y l ，y 2 b ，有r ( x i ，y 1 ) = r ( x 2 ，y 2 ) 。故得到公式( 1 ) 对v a ，b x l ，惟一 确定一个非负数d ( a ，b ) 。 下面证明d 是 x 】上的一个距离函数。 因为若d ( a ，b ) = 0 ，得到d ( a ，b ) = 1 一r ( x ，y ) = 0 ，v x a ，y b 。故得到r ( x ， y ) = 1j x y ，即a = b 。 9 胡，i 土萼 硕士学位论文 其次，由r ( x ，y ) 的对称性，可得到d ( a ，b ) 的对称性。 最后，v a ，b ，c x 】，取x a ，y e b ，z e c ，由r ( x ，z ) 一m i n ( r ( x ，y ) ， r ( y ，z ) ) j1 - r ( x ，z ) 1 - m i n ( r ( x ，y ) ，r ( y ，z ) ) jd ( a ，c ) ( 1 一r ( x ，y ) ) + ( 1 - r ( y ， z ) ) 2 d ( a ，b ) + d ( b ，c ) ，即d 满足三角不等式，故d 是 x 上的距离函数，得到( x 】， d 1 是一个距离空间。 定义2 6 商结构空间设r 是x 上的一个模糊等价关系，称由定理2 1 定 义的距离空p j ( x ，d ) 为r 对应的商结构空间。 命题2 4 设r 是x 上的一个模糊等价关系，令r 产 ( x ，y ) l r ( x ，y ) 五) ，0 五1 ，则r 。是x 上的一个普通等价关系，称r 。为r 的截关系。 令等价关系r 。对应的商空间为x ( o 由定义容易得到如下性质： 若o 2 l 1 曹r r 铮( 兄1 ) 是x ( 如) 的商集。于是，商空间 族 x ( 旯) i o 五 l 按照商集的包含关系构成一个有序链，称 x ( ) 1 0 五1 ) 为x 上的一个分层递阶结构。 命题2 5 给定x 上一个模糊等价关系，则对应一个x 上的分层递阶结 构。 下面讨论归化的距离在什么情况下可以产生对应的模糊等价关系 定义2 7 等腰距离设归一化距离空间( x ，d ) ( 所谓归一化，即v a ，b x ， 有d ( a ，b ) s 1 ) ，若x 中任取3 点构成的三角形均为等腰三角形，且腰是大 边，则称其为等腰距离。 命题2 6 设d 是某模糊等价关系对应的归一化距离，则d 是等腰的。 证明：反证之。假设不是等腰的，设存在x ，y ，z e x ，不妨设d ( x ，z ) m a x ( d ( x ，y ) ，d ( y ，z ) ) ，于是得至0r ( x ，z ) = 1 - d ( x ，z ) 1 - m a x ( d ( x ， y ) ，d ( y ，z ) ) 2 m i n ( 1 - d ( x ，y ) ，1 - d ( y ，z ) ) = m i n ( r ( x ，y ) ，r ( y ，z ) ) ， 得到r 不满足模糊等价关系条件( 3 ) 。 定理2 2 设 x 】是x 的商空间，在i x 上给定一个归一化等腰距离函数d ， 令v x ，y e x ，r ( x ，y ) - i d ( x ，y ) ，则r ( x ，y ) 是x 上的一个模糊等价 关系。 证明：显然，r ( x ，y ) 满足模糊等价关系的条件( 1 ) 和条件( 2 ) 。以下证明 条件( 3 ) 也满足。v x ，y ，z e x ，由于d 是等腰距离，故有 商空问理论与粒度计算 d ( x ，z ) 一 m a x ( d ( x ，y ) ，d ( y ， 所以得到1 - d ( x ，z ) 1 m a x ( d x ( 1 - d ( y ，z ) ) ) ，即 z ) ) ， y ) ，d ( y ，z ) ) 2 r n i n ( ( 1 - d ( x ，y ) ) r ( x ，zj m i n ( r ( x ，y ) ，r ( y ，z ) ) 。 上式右边对y 取s u p ，得到r ( x ，y ) 满足模糊等价关系条件( 3 ) 。 由定理2 1 和定理2 2 可知，x 上的一个模糊等价关系与x 的某一个商空 间上的归一化等腰距离函数是一一对应的。这个等价关系使我们可以用距离空间 为工具来研究模糊等价关系，即可将模糊等价关系放在( x ，f ，t ) 的商空间理 论中进行研究，其中t 是由某模糊等价关系给出的拓扑。 上面已经证明，给定一个x 上的模糊等价关系对应一个惟一的x 的分层递 阶结构。下面证明反之亦然。 定理2 3 设 x ( 丑) l o 丑l 是x 上的一个分层递阶结构，则存在x 上 的一个模糊等价关系r ，其截关系为r ，月。对应的商空间为z ( a ) ， 0 ，1 】。 我们将上述结论归结成下面的定理： 下面的断言是等价的： ( 1 ) 在x 上给定一个模糊等价关系： ( 2 ) 在x 的商空间上给定一个归一化的等腰距离； ( 3 ) 给定x 的一个分层递阶结构。 通过这个定理，我们可以将模糊粒度计算化为一个在结构( 【x 】，d ) 上进行的 计算，于是，可以用我们提出的商空间理论进行研究。 2 4 2 模糊商空间的结构 下面来说明用模糊等价关系所描述的模糊商空间的结构和性质。 定义2 8 模糊商空间 设r 是x 上的一个模糊等价关系，可得到一个与它 等价的x 的商空间 x 上的归一化等腰距离d 。对va e x ，定义z 。( 6 ) = 1 d ( a ， b ) ，v b e x 。于是，每个1 。就定义了 x 上的一个模糊集。由这些模糊集构成 的空间就是对应于模糊等价关系r 的模糊商空间 卢。ld ) ，或称其为x 上 的一个模糊知识基【1 5 。 麓耐z 荨 硕士学位论文 定义2 9 设r i ，r 2 是x 上的两个模糊等价关系，若对v ( x ，y ) ( x x x ) ，有r 2 ( x ，y ) r 1 ( x ，y ) ，则称r 2 比r l 细，记为r i r 2 。 定理2 4 在上述定义的关系“ ”下，所有x 上的模糊商空间全体构成 个完备半序格r 。 这样，我们就能把在精确粒度下的商空间的理论和方法推广到模糊粒度计算 中。 2 4 3 结论 作为模糊粒度计算的起步，本文讨论模糊商空间理论1 8 】。所得到的主要结果 有：证明了利用模糊等价关系可以将原来的商空间理论推广成模糊商空间理论， 并给出了几个基本的定理。 第一，下面的叙述是等价的： ( 1 ) 在x 上给定一模糊等价关系r ； ( 2 ) x 的商空间【x 上给定一个归化的等腰距离d ； ( 3 ) 给定x 的一个分层递阶结构 x ( 五) ) ； f 4 ) 给定一个x 的模糊知识基。 第二，x 上所有模糊等价关系构成一个完备半序格。 这两个结论为粒度计算提供了强有力的数学模型和工具。下一步的研究工作 是把这些理论和方法应用于数据挖掘等领域。 2 5 商空间理论在数据仓库中的应用 数据仓库是当今在数据挖掘和数据处理应用中经常出现的概念。通常数据仓 库是用多维数据为结构建模，是数据挖掘的重要预处理步骤。数据仓库引入了概 念分层。将低层的概念映射到更一般的高层概念层上( 上卷) 或沿维的概念分层 向下实现( 下钻) 。而概念分层正好和商空间多粒度求解问题的理论一致，且商 空间粒度理论不限于对不同层次粒度问题分析，对同层次粒度也可以进行分析， 因而在数据仓库中具有应用前景。 数据仓库提供了联机分析处理( 0 l a p ) 工具，用于各种粒度多维数据分析， 有利于数据挖掘效率，是数据挖掘的重要预处理步骤。通常数据仓库是用多维数 商空间王! i ! 论与粒度计算 据库结构建模。其中，每一维对应于模式的一个或一组属性，每个单元存放某个 聚积度量值。数据仓库的实际物理结构可咀是关系数据存储或多维数据立方体 “”，最流行的数据仓库数据模型是多维数掘模型，这种模型可以是星形模式、雪 花模式。各模式之间主要是结构上变化，其基本数据仓库包含一个大的大批数据 和不含冗余的中心表( 事实表) 和一小组附属表( 维表) 。这样的结构，也很适 合应用商空f 刚理论。 下面给出星状数据仓库实例进行说明。如图2 1 所示。 销售事实表 项目维表 时间维表 m o n t h l o c a t i o nk e y c i t y p r o v i n c e c o u n t r y t i m ek e y i t e mk e y l o c a t i o nk e y d 0 1 l a r ss o l d i t e ms o l d 位鼍维表 b r a n d t y p e 图2 1 销售数据仓库星型模式图 假设想对某一公司的销售创建一个数据立方体，包含时间( t i m e ) 、位置 ( l o c a t i o n ) 、项目( i t e m ) 维表和销售情况事实表，从数据立方体计算的方体 和分类有： 基本立方体：由( c i t y ，i t e m ，y e a r ) 组成。 2 一d 方体：( c i t y ，i t e m ) ，( c i t y ，y e a r ) ，( i t e m ，y e a r ) 组成。 卜d 方体：c i t y ，i t e m ，y e a r 组成。 0 一d 方体：a ll 全体。 对于n 维方体所有可能产生的方体总数： ，= 丌( 厶+ 1 ) ，其中上，维i 的层数。 萄埘未萼 硕士学位论文 可见，这立方体将是十分庞大，如果不进行预先处理，将会出现海量的多维 数据聚集和消耗大量的存储空间，且速度很慢。下面用商空间粒度理论对问题以 求解方式进行知识预处理。在对处理能够得到的结果做到“心中有数”的情况下 在进行实际运算，可以大大提高效率。 2 5 1 不同层次粒度问题求解 从图2 1 的销售数据仓库星型状模式图可知各维表存在以下层次： 时间维表：m o n t h ( q u a r t e r y e a r 项目维表：i t e m b r a n d t y p e 位置维表：c i t y p r o v i n c e c o u n t r y 先考虑1 一d 方体中的位置维表： 考虑位置维表和销售事实表的拓扑关系( x ，t ) ，如果粒度从最小的粒度城 市开始：x = ( 爿。) i ， 4 。1 ， 4 2 ，) ， 4 ：。：) ， 4 。) ， 4 。) ) ，其中爿。表示m 省 的第n 。座城市。 令拓扑关系中t 的拓扑基b 为x ，根据拓扑基定义，由b 中的元素经过任意的 并得到的所有可能集合的全体就形成了x 的拓? b t 。 t = ( ( 彳l i ， 一。) ， a l l ，a i 2 ) 4 川，彳 ， 爿i 。，a 1 2 ，爿。 ) 也就是在现有粒度下能得到t 结构，陔结构反映了在目前粒度下销售事实表 中能够得到的城市货物销售量及销售货款的信息为，t ，即城市和各城市之间 任意组合的货物销售量及销售货款的信息。假设有n 座城市，共有 c ：+ 口+ q + + c 2 = 2 “一l 项。这是一个十分庞大的数据项。 现改变粒度，考察省的销售情况。从位置维表可知： p l = a f ，p 2 = a 2 ，p 。= f a 。) ； 其中p i = 爿a 1 2 ，a i n l ) ，p 。= 爿州，a 。2 ，a 删。) 【x 】= p ，p ：，p 。) ，p 。表示第m 省。 现在构造 x 的商拓扑 ，r ，有： 4 商空间理论与粒度计算 p 】= a a m ，a h ) t ， p i ) t p 2 = a 2 l ，a 2 2 ，“，a 2 ) t ， p 2 阳t p 。= 爿，a 。2 ，a 。) t ， p 。，) i t ( p 】，p 2 ) t p 1 ，p 2 ) t ( p l ，p 2 ，p ，) t ， p l ，p ，p 。) “t 最终得： t 】- “p 。) ， p ：) j ， 且，p ：，p 。) ) 即改变粒度后，能够得到只能是在商拓扑 t 中的货物销售量及销售货款的 信息，是各省之间的货物销售量及销售货款的信息，由于省只有m 项，所以商拓 扑 t 中共有：c ：+ c ：+ + c ：= 2 ”一1 项。而m n ，所以改变粒度后需要处 理的数据大大减少。如果实际中关心该层次的销售，只需在本层粒度下处理。会 极大提高效率。 如果考察全国的销售情况，n = ( n ，p ：，p 。) z 】_ n ) 。 再构造 x 的商拓扑 t ，只有 ) t 。在此粒度上只能得到全国总货物销售 量及销售货款的信息，即商拓扑 t 中只有一项。 同理考虑时间维表和销售事实表的