（计算机软件与理论专业论文）粒度计算模型及其应用.pdf

粒度计算模型及其应用 摘要 粒度计算理论作为目前的研究热点，受到越来越多的关注。目前模 糊集、粗糙集和商空间理论可以看作是三种不同形式的粒度计算理论。 这三者在思考问题的出发点和解决问题的任务方面各具特色，但三者有 一个共同的特点，就是在不同的粒度层次上观察问题，遵循了人类思维 的一般过程。本文论述了粒度计算模型的建立及其应用，主要研究内容 包括： ( 1 ) 、构造了基于o n t o l o g y 的粒度计算模型。首先给出了概念的形 式化表示，本体语言的应用实例，同时对o n t o l o g y 的研究热点问题以 及目前难以解决的问题进行了探讨。重点阐述了在新的粒度计算模型下 粒度的表示，粒度的大小、粒度的合成与分解等问题，最后构造了基于 此模型的文本搜索算法g r c - s e a r c h ，可在一定程度上降低时间复杂度。 ( 2 ) 、论述了在代数系统下的粒度计算模型。首先论述了商空间下论 域、拓扑空间、半序结构及属性函数的合成。重点阐述了代数系统下群 的上、下近似定义，粗糙群、粗糙子群、粗糙商群及其性质，给出了一 些定理的证明过程，构造了代数系统中的粒度计算体系。 ( 3 ) 、将o n t o l o g y 自动学习技术和粒度计算理论应用于网页搜索中。 论述了采用奇异值分解原理s v d 对词文档矩阵进行处理，形成概念特 征。重点论述了采用正态总体均值检验法的o c 函数对重要概念的选取。 然后对目前存在的各种分类方法进行了比较分析，并对推拉算法进行了 改进，形成多中心推拉分类算法m c c d p a 。构造了基于粒度计算原理的 分类算法c a g r c 。最后给出基于商空间的网页搜索算法 g r c w e b s e a r c h 。实验结果表明此算法提高了网页搜索的查准率，降低 了时间复杂度，取得了一定的效果。 ( 4 ) 、将粒度计算理论应用在网络入侵检测系统中。阐述了动态入侵 检测系统的国内外研究现状，主要论述了将基于粒度计算原理的入侵特 征选择应用于动态智能规则库的建立；最后给出了系统实验结果，在减 小误报率和漏报率上取得一定的效果。 关键词：粒度计算，o n t o l o g y ，代数系统，商空间，文本搜索，入侵检 测 i l g r a n u l a rc o m p u t i n gm o d e l a n di t sa p p l i c a t i o n a b s t r a c t a sar e s e a r c hp o p u l a rp o i n t , g r a n u l a r - c o m p u t i n gt h e o r ya t t r a c t i v e s m o r ea n dm o r ep e o p l eo v e l t h ew o r l d f u z z ys e t ，r o u g hs e ta n dq u o t i e n t s p a c ea r er e c o g n i z e da st h r e ed i f f e r e n tg r c t h e o r i e s t h e yh a v et h e i ro w n p e r s p e c t i v e s i n s o l v i n gp r o b l e m s ，b u ta l lo ft h e mh a v eac o m m o n c h a r a c t e r i s t i ct h a tc o n s i d e r sp r o b l e m si nd i f f e r e n tl e v e l sa n dh a st h es i m i l a r o ft h i n k i n gl i k eh u m a nb e i n g t h i st h e s i sd e a l sw i t hg r a n u l a r - c o m p u t i n g m o d e la n di t sa p p l i c a t i o n t h em a i nr e s e a r c hw o r k i n c l u d e s ： f i r s t l y , t h i st h e s i sp r e s e n t saf o r m a lr e p r e s e n t a t i o no fc o n c e p t , g i v e s a p p l i c a t i o ne x a m p l eo fo n t o l o g yl a n g u a g e ，a n dc o n s t r u c t san e wm o d e lf o r g r a n u l a rc o m p u t i n g s o m er e s e a r c hp o p u l a rp o i n t sa n dd i f f i c u l tp r o b l e m s a b o u to n t o l o g ya r ed i s c u s s e da tt h es a n l et i m e ，s e v e r a ld e f i n i t i o n s a r e p r o p o s e d ，s u c ha sp r e s e n t a t i o no fg r a n u l a r i t y , p a r t i t i o no fc l a s s e s ，s i z eo f g r a n u l a r i t y , s y n t h e s i sa n dd e c o m p o s i t i o nu n d e rt h ed e f i n e dm o d e l f i n a l l y , a na l g o r i t h mn a m e dg r c - s e a r c hf o rt h em o d e la p p l y i n gt ot h et e x tr e t r i e v a l i sd e s i g n e d ，a n de x p e r i e n t si l l u s t r a t et h a ti tc a nr e d u c eb o t ht i m ec o m p l e x i t y a n d s p a c ec o m p l e x i t y s e c o n d l y , t h i st h e s i sd i s c u s s e st h eg r a n u l a rc o m p u t i n gm o d e li na l g e b r a i i i s v s t e m t h es y n t h e s i so fd o m a i n ，t o p o l o g ys p a c e ，p a r t i a lo r d e r e dm u c t u l 怆 羽1 da t t r i b u i t en m c t i o nu n d e rq u o t i e n ts p a c ei sg i v e nf i r s t l y t h e n i tf o c u s e s 蚰峭ra p p r o x i m a t i o na n dl o w e ra p p r o x i m a t i o n o fg r o u pi na l g e b 。a s y s t e m r o u g hg r o u p ，r o u g hs u b g r o u p ，r o u g hi n v a r i a n t s u b g r o u p ，u g h q u o t i e n tg r o 叩a n dt h e r e l a t e dp r o p e r t a t i e s a l ed i s c u s s e d a l s o , 8 0 m e m e o r c m sa r ep r o v e dd e t a i l l yi nt h i sp a r t t h em o d e lo fg r a n u l a rc o m p u t m g i na l g e b r as y s t e mi sc o n s t r u c t e ds u c c e s s f u l l y 砥棚y 觚t h e s i sa p p l i e sa u t o m a t i co n t o l o g y l e a r n i n gt e c h n o l o g ya n d 掣蛐u l a rc o m p u t i n gp r i n c i p l e t oc h i n e s ew e bp a g er e l 帆e v a ls y s t 哪 t e r m d o c u m e n tm a 臼奴i sp r o c e s s e dw i t hs i n g u l a rv a l u ed e c o m p 0 8 i t i o na n d 州l r dc o n c 印t sa r ef o r m e d a d o p t i n go cf u n c t i o n i nn o r m a lp o p u l a n o n m e 趴t e s t i n gt os e l e c tt h ei m p o r t a n tc o n c e p t s i sd i s c u s s e d t h e ni tc o m p a r c s a n da l l a l y s e st h ec l a s s i f i c a t i o nm e t h o d st h a t a r cw i d e l yu s e dn o w a d a y 8 d r a g _ p u s l l i n gm e m o di s i m p r o v e da n dn e wm u a i _ c e n t r o i d 出a 窨棚h i n g a l g o r i t h i ni sf o r m e d c t a s s i f i c a t i o na l g o r i t h mb a s e d o np r i n c i p l eo fg r a n u l a r c o m p u t i n g i sd e s i g n e d f i n a l l y , i t g i v e s w e bp a g e s e 躺ha l g o r i t h m g r c 舷勰醐砌b 嚣e do nq u o t i e n ts p a c e e x p e r i m e n t a l r e s u l ts h o w si tc 锄 i m p r 0 v et h ep r e c i s i o n r a t eo f w e bs e a r c h i tg e t st h eb 眦r r e 刚t l a s t l y ,g r a n u l a r - c o m p u t i n gt h e o r y i s a p p l i e d t on e t w o r ki n t n l s l o n d e t e c t i o ns v s t e m i ts u m m a r i z e st h ec u r r ，e n t r e s e a r c hs t a r l so fm t m 8 1 0 n d e t e c t i o ns v s t e m ，m a i n l yd i s c u s s e st h ef o u n d a t i o no f r u l eb a s e ，s e l e c t i o n 砒l d c o n s t r u c t i o no fi n t r u s i o nf e a t u r e sb a s e d0 1 1g r a n u l a rc o m p u t i n g a tl a s t ，i t g i v e st h ee x p e d m e n t r e s u l tt h a ts h o w si m p r o v e m e n ti nd e c r e a s i n gm i s t a k e n r a t ea n df a i l a rr a t e k e yw o r d s ：g r a n u l a rc o m p u t i n g ，o n t o l o g y , a l g e b r as y s t e m , q u o t i e n t s p a c e ，t e x tr e t r i e v a l ，i n t r u s i o nd e t e c t i o n v 第一章绪论 本章主要介绍论文的研究目的与意义以及粒度计算的国内外研究现状，并简 要介绍论文的主要研究内容和创新点。 1 1 论文的研究目的与意义 所谓信息粒是指人类在解决和处理大量复杂信息问题时，总是按各自的特征 和性能将其分解为若干较简单的予问题或模块，每个如此分割成的块被看作一个 粒。丽这种处理信息的过程就叫做信息粒化。 粒度计算主要是指以下3 个方面； ( 1 ) 研究信息分类、被分成的块是两两分离的划分还是两两可能有交的模 糊分割。 ( 2 ) 研究分成的粒度大小、不同大小的粒度层之间的关系。 ( 3 ) 研究粒度分解与合并的方法。 波兰学者p a w l a k t l 】提出了一个假设：人的智能( 知识) 就是一种分类的能力。 这个假设可能不是很完备，但是却非常精练。 张钹、张铃在文献【2 】中提出了人类智能的一个公认特点，就是人们能从极 不相同的粒度上观察和分析同一个问题。人们不仅能在不同粒度的世界上进行问 题求解，而且能够很快从一个粒度世界跳到另一个粒度世界。往返自如，毫无困 难。这种处理不同世界的能力，就是人类问题求解的强有力的表现。 目前模糊集、粗糙集和商空间理论可以看作是三种不同的粒度计算理论。这 三者从思考问题的出发点和解决问题的任务各具特色。但三者有一个共同的特点 是在不同的粒度层次上观察问题。样本划分的商空间表示与粒度世界是目前在很 多领域( 如群论、分类、聚类，网页搜索等) 广为关注的问题求解的基本理论与 方法，也是近年来国内外人工智能界的一个主要研究热点，同样也是目前软计算 与粗糙集领域研究的主要热点。关于粒度计算的最新成果已经被应用于数据挖 掘、机器学习、信息检索、文本分类、图像处理、统计学等领域。 样本集合划分是模式识别中样本集合分类的基本问题，利用商空间上样本集 合的性质建立样本分类的新算法是传统模式识别方法所没有的，也是目前粒度计 算中还没有解决的问题。 关于样本集合等价划分和非等价划分的粒度构造方法，目的是在寻找不同粒 度上的样本集合等价划分和非等价划分的算法及其评价标准。这个问题也是目前 没有解决的问题。 另外，随着粒度计算的发展，一些n p 问题得到近似意义上的解，在一定程 浙江师范大学硕士学位论文 度上降低了时间复杂度和空间复杂度。 o n t o l o g y 作为语义w e b 实现的一大关键技术的出现引起了国内外广大科研 人员的关注，并且在很多领域得到了广泛的应用。如信息检索、信息推理和w e b 上异构信息的处理等。在粒度计算中，最重要的是如何构造各种不同的粒，要构 造粒就要按照一定的标准对论域进行分类，而不同的分类标准又对应不同的粒。 如何构造恰当的粒度是目前需要解决的问题之一。o n t o l o g y 作为描述概念与概念 之间的关系模型，它通过概念之间的关系来描述概念的语义，因此可以借鉴 o n t o l o g y 中的概念模型来表示不同的粒度。 代数系统的研究历史悠久，但是从2 0 世纪以来，代数学的研究对象和研究 方法发生了重大变革，形成了抽象代数学。在抽象代数系统中，对象是抽象的而 不是具体的，对象上的运算也是抽象的，其含义由一组给定公理规定。抽象代数 系统在计算机g t 学研究中始终占有重要的地位和作用，对计算机科学的产生和发 展具有决定性的作用。而代数系统中的半群理论在自动机和形式语言研究中发挥 了重要作用，群理论在信息安全与编码理论中得到了广泛的应用。而群中的商群 其实也是一种划分，从而可以将其看作一种粒度空间结构，因此在代数系统下研 究粒度计算模型是非常有意义的。 本文的研究目的主要是构建新的粒度计算模型：基于o n t o l o g y 的粒度计算 模型、代数系统下的粒度计算模型等，并将粒度计算理论应用于文本搜索及网络 入侵检测系统的规则库建立中。 1 2 粒度计算的国内外研究现状 人们在思考问题时，或者是先从总体进行观察，然后再逐步深入地研究各个 部分的情况；或先从各个方面对同一闷题进行不同侧面的了解，然后对它们进行 综合；或是上面两种方法的组合，即时而从各侧面对：事物进行了解，然后进行综 合观察，时而综合观察后，对不甚了解的部分再进行观察。总之，根据需要 从不同侧面、不同角度反复对事物进行了解、分析、综合、推理，最后得出事物 本质的性质和结论。 波兰学者p a w l a k 1 】提出了一个假设：人的智能( 知识) 就是一种分类的能力。 这个假设可能不是很完备，但是却非常精练。在此基础上，他提出概念可以用论 域中的子集来表示。于是，在论域中给定一个等价关系后，就为论域提供了一个 知识基陇r ) ，然后，讨论一个一般的概念x 如何用知识基中的知识来表示，即 用知识基中的集合的并来表示，对于那些无法用佤r ) 中的集合的并来表示的集 合，他借用拓扑中的内核和闭包的概念，通过艮下近似和r 上近似，从而引入 了粗糙集，创造了租糙集理论。 2 第一章绪论 t y l i n 教授于1 9 9 6 年在u c - b e r k e l e y 大学z a d e h 的重点实验室做客座教授 时，向z a d e h 提出作“g r a n u l a rc o m p u t i n g ”课题的研究当时z a d e h 称“g r a n u l a r m a t h e m a t i c s ”，l i n 改称“g - r a n u l a rc o m p u t i n g 后，立即得到z a d e h 的认可，并且缩 写成c n c 。以后“g r a n u l a rc o m p u t i n g 成为今天的一个热门研究领域。 目前z a d e h 提出的模糊集 3 1 、p a w l a k 创立的粗糙集【1 1 以及张钹，张铃提出的 商空间理论州可以看作是三种不同形式的粒度计算理论。 最近，z a d e h 在文献【5 7 】中讨论模糊信息粒度理论时，提出了人类认知的3 个主要概念，即粒度( g r a n u l a t i o n ，包括将全体分解为部分) 、组织( o r g a n i z a t i o n ， 包括从部分集成全体) 和因果( c a u s a t i o n ，包括因果的关联) ，并进一步提出了 粒度计算。他认为，粒度计算像一把大伞，它覆盏了所有有关粒度的理论、方法 论、技术和工具的研究。并指出，“粗略地说，粒度计算是模糊信息粒度理论的 超集，而粗糙集理论和区间计算是粒度数学的子集”。 目前粒度计算的研究主要有两种方法：代数学( 利用二元关系) 、逻辑学( 利 用谓词及其关于逻辑联结词的组合公式) 1 2 1 以模糊集理论、邻域观点研究信息粒度 z a d e h 于1 9 7 9 年在文献【3 】中提出了模糊粒度的概念，文中定义信息粒度为 一个命题：x 的值是以程度a 隶属于模糊子集g 厂，其中工是u 上的变量，x 的值是c ，上的一个实体，写成：g = x i s g i s a ，形式上被记成：g = “u ：x 的 值( v ( x ) = u ，v 是u 上的赋值符号) 是以程度五隶属于模糊子集g u 。很显然， 0 五1 。以模糊集的观点，此处的a 是模糊隶属函数u g ；而从逻辑的观点， 此处的五是所建立的命题的模糊真值或概率。因此在这篇文章中，除了定义模糊 粒度外，还讨论了模糊粒度的概率分布及其概率的计算方法。t y l i n 于1 9 9 8 年 在文献 8 1 以及在其以后的文献【9 - 1 4 中以邻域观点，通过二元关系定义了粒。设 s = ( u ，爿，n ，) 是信息系统，丑，矿一u 二元关系，其中u 是所讨论对象的全 集，4 是属性集，矿是属性值集，厂是信息函数。用曰定义粒是如下形式： g 。= 伽u ：u b p ，p e y ) 显然g 。是清晰还是模糊的完全取决于二元关系b 的特 性。设有两个二元关系b 和d ，如果b d ，则按召将全域划分的粒比按d 将 全域划分的粒更细，在这种情况下。也可将不同大小的粒度分成不同粒度层，并 在不同层上进行各自分别处理。 3 浙江师范大学硕士学位论文 1 2 2 以逻辑、代数格观点对不同大小的粒度进行分层 z a d c h 的工作激起了学术界对粒度计算研究的兴趣，y yy a o 及其合作者对 粒度计算进行了一系列的研究 t 5 - 18 1 ，并将其应用于数据挖掘领域。其工作要点是， 用决策逻辑语言( d l 语言) 来描述集合的粒度( 用满足公式厂元素的集合来定 义等价类m ) ，建立概念之间的i f t h e n 关系与粒度集合之间的包含关系的联 系，并提出利用由所有划分构成的格来求解一致分类问题。 1 9 8 5 年，在l o sa n g e l e s 举行的国际人工智能联合会议上，s t a n f o r d 大学教 授h o b b s 在文献 1 9 】中讨论了粒度的分解和合并，以及如何得到不同大小的粒度， 因此他提出了产生不同大小粒度的模型，这就是： ( v x ，y ) ( x y ) s ( v p 胄) ( p ( x ) s p ( j ，) ) ( 1 - 1 ) ( v x ，y ) ( x y ) 暑爿厂( x ) 一，( 力i p p o ) ( i - 6 ) 其中p g 。 s k o w r o n 研究各种近似空间上的r o u g h 下近似集和上近似集的意义在于他 探讨了r o u g h 集理论在各种环境下的引用，也就是建立了r o u g h 集理论在各个 专业领域中的应用前景。 p o l k o w s k i 在文献【2 4 】中以m e r e o l o g y 概念定义了r o u g h m e r e o l o g i c a l 粒。 m e r e o l o g y 实质上也是一种包含度概念。这个词出于经典集合论时期，当时认为 一个集合全部元素被包含在另一个集合中才称包含，否则称不包含。因此， l e s n i e w s k i 于1 9 1 6 年提出用这个词来研究关于部分元素被包含问题。设m 是全 集u 上的r o u g h 包含函数，其定义与上述s k o w r o n 定义的包含函数类似。，【0 ，l 】 是包含度，c l 。是类算子符，它被用于粒上，所以也称粒算子。设工u ，r o u g h m c r e o l o g i c a l 粒被定义如下： g ，( x ) = c l s ( y j ( 1 7 ) 其中y ，( y ) yu ，x ，表示y 以，程度包含于j ，这里的x ，y 应广义理解，不 应单纯看成一个元素。所以，这里的粒可以形式地定义成如下格式： g ，( x ) y u ：y 甜，x 0 r 1 ) ( 1 8 ) 设g z s = 渺。，a 。 是粒近似空间，u g 是粒的全域，以是粒集上派生的属性 集，【o ，l 】是近似度。 在国内，清华大学的张钹院士和安徽大学的张铃教授【2 棚进行了有关粒度计 算的研究，主要是从代数格方面研究如何产生不同大小的粒度空间，并讨论不同 空间上的粒度之间函数关系，从而提出了商空间理论。从给定的原始问题空间 仪f 7 ) ，其中x 是论域，f 是属性集，r 是x 上的拓扑关系，可找到它的对应的 s 浙江师范大学硕士学位论文 商空间( 【弼，【用，【刀) 。观察当前粒度空间决定是否进入更细粒度的更深一层粒度空 间，随后将不同大小粒度世界上的粒度解组合成整体粒度的解。 在商空间理论中，提出了“保假原理”和“保真原理”，这两个原理在商空 间模型的推理中起到了很重要的作用。当我们对一个问题进行求解时，如果问题 非常复杂，先对其进行初步分析，即取一个较粗粒度商空间，将问题转化为在该 空间上的对应的问题，然后再进行求解。利用这两个原理，可以近似解决一些 n p 问题，从而在一定程度上降低了时间复杂度和空间复杂度。 南昌大学的刘清教授在文献【2 5 】中对信息粒及粒计算展开了研究，特别是在 文献 2 6 3 2 中对粒度计算中的逻辑推理进行了详细地论述。 同济大学的苗夺谦教授在文献【3 3 】中介绍了知识的粒度、属性的重要度及协 调度等概念及其计算方法，并给出了属性的重要度在求属性集的最小约简、协调 度在构造决策树方面的具体步骤，同时在此文献中给出了几个具体实例。 中国科学院的王珏教授、西安交通大学的张文修教授、重庆邮电学院的王国 胤教授、浙江海洋学院的吴伟志教授以及山西大学的梁吉业教授等也对粒度计算 特别是r o u g h 集理论做了大量的研究，提出了一些熏要的理论。 在文献 3 4 】中结合粒计算的处理方法给出了不完备信息系统的粒表示、粒运 算规则的粒分解方法，同时结合粗集中的属性约简问题，提出了不完备信息系统 在粒表示下属性重要性的判定条件。 1 2 4 粒度计算理论的应用 目前粒度计算的应用主要有：聚类分类、数据库和数据仓库、纹理图象分 割等方面。 文献【3 5 】从信息粒度的角度剖析了聚类和分类技术。论述了这样一种观点： 从信息粒度的观点来看，聚类是在一个统一的粒度下计算，而分类却是在不同的 粒度下进行计算。 f i g u r e l - 1s a m p l ed i s t r i b u t i o n f i g u r e l - 2c l u s t e r i n gp e d i g r e e 图1 - 1 样本分布图阔图i - 2 聚类谱系图l a s l 文献 3 5 】中使用了聚类谱系图( 如图1 2 ) 对聚类和分类中的粒度原理进行 6 第一章绪论 了分析，同时设计了基于信息粒度原理的分类算法，将此算法应用于中文文本分 类中，取得了一定的效果，提高了泛化能力。 文献 3 6 1 中介绍了粒度世界的描写、划分法、粒度确定以及不同粒度世界的 关系，将其应用于互联网中的路由算法及称球游戏。 文献【3 7 】将商空间理论应用于纹理图像分割，通过对纹理的区域结构待征分 析研究，提出基于g 邻域周期排列的纹理区域特征，并对结构性多纹理图像进行 了分割实验。给出了图像分割算法( 如图l 一3 ) 。 文献1 3 8 对商空间中拓扑结构的合成进行了论述。并对不同层次粒度问题求 解以及同层任意粒度的问题求解给出了理论及实例应用，减小了计算复杂度。 满意 f i g u r e1 - 3i m a g ep a r t i t i o na l g o r i t h m 图l - 3 图像分割算法1 3 力 1 3 论文的创新点及组织结构 本文主要分为6 章： 第1 章介绍了粒度计算的国内外研究现状，论述了论文的研究目的及意义。 第2 章主要构造了基于o n t o l o g y 的粒度计算模型。o n t o l o g y 的概念层次结 构具有粒度层次的特点，给出了粒的定义、粒的大小、合成及分解等。 第3 章首先论述了商空间下论域、拓扑空间、半序结构、属性函数的合成 7 浙江师范大学硕士学位论文 等。接着构造了代数系统下群的粒度计算模型，论述了群的上、下近似定义， r o u g h 群、r o u g h 予群、r o u g h 商群等概念的定义及其主要性质，同时给出了一 些定理的证明过程。 第4 章将粒度计算模型应用于文本搜索中。文中对各种分类方法进行了比 较分析，并构造了基于粒度计算原理的分类算法。采用奇异值分解( s 叨i ) 对词 - 文档矩阵进行处理，形成概念特征；然后采用数理统计中的o ( 7 函数提取重要 特征。最后给出了文本搜索算法g r c - w e b s e a r c h ，同时给出了实验结果。 第5 章将粒度计算理论应用于网络入侵检测系统中规则库的建立，在一定 程度上增加了动态规则库的智能性，减小了误报率。 第6 章对论文进行总结并对下一步要进行的工作进行展望。 8 2 1 引言 第二章基于o n t o l o g y 的粒度计算模型 随着计算机科学特别是i n t e r a c t 技术的迅速发展，网络上的各种资源信息异 常丰富，但也伴随着这种发展出现了各种问题。主要表现在；知识表示、信息组 织、软件复用、信息检索等方面。面对网络上海量的信息，如何组织、管理和维 护这些信息并让这些信息为人类的生活提供各种服务成为一项重要的研究课题。 w 3 c 论坛主席b c r n c r s l c e t 3 9 在2 0 0 0 年提出的语义w e b 的体系结构改变了网络 的发展趋势，使得w e b 推理语言具有了一定的表达能力，而o n t o l o g y 作为语义 w e b 实现的一种关键技术的出现引起了国内外广大科研人员的关注，并且在很 多领域得到了广泛的应用。如信息检索、信息推理和w e b 上异构信息的处理等。 而粒度计算理论虽然处于初步阶段，但却是目前研究的另一大热点。大部分 学者将模糊集 6 1 、粗糙集【l 】和商空间1 4 1 看作是粒度计算中三种不同的理论。粗糙 集和模糊集理论和方法产生的时间相对较长，已经在数据挖掘、信息检索等很多 领域得到了广泛的应用，但商空间理论还没有引起人们的足够重视。目前有关粒 度计算模型的研究还不够成熟，在不同粒度上的样本集合等价划分与非等价划分 的方法及评价标准也没有进入实用阶段。本章试图通过利用o n t o l o g y 构造一种 新的粒度计算模型，希望能够对粒度计算的发展有所启发。 2 。2 o n t o l o g y o n t o l o g y 最早是一个哲学上的概念，从哲学的范畴来讲，o n t o l o g y 是客观存 在的一个系统的解释或说明，关心的是客观现实的抽象本质。而在人工智能界， 最早给出o n t o l o g y 定义的是n e c h e s 等人，他们将o n t o l o g y 定义为：“给出构成 相关领域词汇的基本术语和关系，以及利用这些术语和关系构成的规定这些词汇 外延的规则的定义”。目前对于o n t o l o g y 的定义使用最多的是：o n t o l o g y 是共享 概念模型的形式化规范说明。 对于“概念”的定义也没有统一的说法，但从它的使用中我们可以理解为： 表示同一含义的词语的集合。例如计算机、电脑、个人计算机、p c 等应该属于 同个概念，因为它们所描述的是同一种事物。概念模型( c o n c e p t u a l i z a t i o n ) 指 通过抽象出客观世界中一些现象的相关概念而得到的模型。 o n t o l o g y 中包含5 个基本的建模元语，分别为；类( c l a s s e s ) 、关系( r e l a t i o n s ) 、 函数( f u n c t i o n s ) 、公理( a x i o m s ) 和实例( i n s t a n c e s ) 。 关系代表了在领域中概念之间的相互作用。形式上定义为一维笛卡儿乘积的 9 浙江师范大学硕士学位论文 子集：r ：c l x c ：g ，如子类关系。函数则是一种特殊的关系，在这种关系 中，前n - 1 个元素可以唯一决定第拧个元素。对函数的定义为： f ：c 。c ：x c 。_ c 。，根据函数中的条件就可以找到所要寻找的唯一答案。 也就是找到了确定解，消除了二义性。例如a g e o f 关系，其中a g e o f ( x o o 表示y 代表x 的年龄，很显然地，x 可以唯一确定其年龄。 o n t o l o g y 中的公理代表永真断言( a s s e r t i o n s ) ，也可以将它看作为o n t o l o g y 中的约束。公理主要包含两个方面的公理：属性公理和关系公理【加】。 从语义上分析，o n t o l o g y 中的实例表示的就是对象，而概念表示的则是对象 的集合，关系对应于对象元素的组的集合。概念的定义一般采用框架结构，包含 概念的名称、与其它概念之间的关系的集合、以及用自然语言对概念的描述。 概念中的关系主要有4 种：p a r t - o f , k i n d - o f , i n s t a n c e - o f 以及a t t r i b u t e - o f 等。 p a r t - o f 表示的是概念中部分与整体的关系；k i n d o f 表示概念之间的继承关系， 相当于面向对象中的父类与子类的关系；i n s t a n c e o f 表示概念的实例与概念之间 的关系，类似于面向对象中的对象与类之间的关系：a t t d b u t c - o f 表示某个概念是 另一个概念的属性。例如概念“身高”可以作为概念“人”的一个属性。 2 2 1 概念表示方法 可以将概念作为一个具有固定长度的字符串来表示： t a b l e2 - 1 r e p r e s e n t a t i o no f c o n c e p t s 表2 1 概念的表示方法 在表2 1 中，表示概念的外延，其它的则表示概念的内涵。 采用内涵十外延来表示概念，内涵表示概念中明确的层次信息，外延表示 概念中非明确的层次信息。内涵越大，概念越明确；相反地，外延越大，概念越 不明确。 自信息量反映符号的不确定性，符号瑾，的自信息量记为i ( a 。) 。即 ，( 口，) = 一l o g p ( a , ) ，其中p ( a ，) 为符号口，出现的概率。概念c 的不确定度记为 日( c ) ，则有： 日( c ) = p ( a 1 ) j ( 口1 ) 4 - p ( a 2 ) ，( 口2 ) 十+ p ( 研) ，( 嘶) = 一p ( 口) l o g p ( a , ) ( 2 - 1 ) 1 0 第二章基于o n t o l o g y 的粒度计算模型 其中，表示概念中的符号数。不确定度越大，说明概念的外延越大。 假设存在两个概念石，j r ，它们所含的符号分别为a i ，b ，。p ( a , b ，) 表示当 l ，为b ，时x 为m 的条件概率。概念x ，】，的相关程度记为h ( x 功，则有： f _ h ( x ，】，) = p ( a ，6 ) l o g p ( a j b j ) ( 2 - 2 ) j 2 j j 。i 其中，m 分别为概念x ，j ，的字符数。 2 2 2 本体语言与本体研究热点 本体可以采用多种形式来表示，但一般都包含一个领域的词汇表和词汇意义 的某些说明，在最简单的情况下，本体可以只描述为由包含关系关联起来的概念 层次。近几年来，已经开发出多种本体语言，用于实现在异构环境中异构数据的 交换，其中，大多是基于x m l 语言的，具体可见图2 - 1 。同时，w 3 c 工作组也 相应制定了资源描述框架( r e s o u r s cd e s c r i p t i o nf r a m w o r k , r d f ) 和r d f 模式， 在此基础上又相继开发了本体推理层( o n t o l o g yi n f e r e n c el a y e r , o i l ) 和 d a m l + o i l 。其中d a m l + o i l 定义了多种方法实现对概念的分类。 f i g u r e2 - 1o n t o l o g yl a n g u a g e 图2 - 1 席体语言 人们看待事物的角度不同会导致对不同概念的不同表达方式，即使用不同的 词汇表达相同或相近的概念。主要考虑词与词之间的3 种语义关系。 ( 1 ) 同义关系( s y n o n y m ) 。词与词之间的意义相同或非常相近，往往可以互 相替代。如：计算机和电脑。d a m i 加i l 可以这样实现： d a m l ：c l a s sr d f ：i d = 计算机p ( 2 ) 上下位关系( h y p e r n y m ) - 又称为“i s a ”关系，下位词是上位词的特例。 如：植物与荷花之间的关系。在d m u - o i l 可以描述为： 浙江师范大学硕士学位论文 d a m l ：c l a s sr d f ：i d = 植物肛 ( 3 ) 包含关系( m e r o n y m ) ：又称为“h a s - a ”关系。如苹果由果皮、果肉、核 组成。在d a m i + o i l 可以描述为： r d f ：s u b c l a s s o i b r d f ：s u b c l a s s o f b r d f ：s u b c l a s s o 隆 r d f ：s u b c l a s s o t b 本体研究的数据源主要是非结构化数据( 如纯文本) 、半结构化数据( 如 x m l ，h t m l 文档) 、结构化数据( 主要是关系数据库或对象数据库中的数据) 。 目前o n t o l o g y 的研究热点主要有： ( 1 ) 概念的获取。主要有3 种方法：语言学方法；基于统计的方法；混合 方法： 第二章基于o n t o l o g y 的粒度计算模型 ( 2 ) 本体学习方法的改进。 虽然目前已经提出了很多本体学习方法，但大部分方法都不理想。就基于结 构化数据的本体学习来说，现有方法一般只考虑关系模式的语义，而没有进一步 去挖掘大量元组中包含的语义信息，所以获取的概念数量和关系种类都非常有 限：就基于非结构化数据的本体学习来说，它是目前研究较多的一大类阿题，但 是仍然没有一个成熟的领域概念获取方法，并且无法自动地为非分类关系赋予语 义；就基于半结构化数据的本体学习来讲，现有的方法往往是将其按照纯文本对 待，没有充分地利用其隐含的结构信息，从本体学习对象的层次来看，现有研究 主要集中在概念和关系的获取，公理的获取研究很少，然而，公理的定义和维护 也是本体构建中一项重要的i 作。总之。现有的方法仍然存在许多值得改进的地 方。另外，针对同一个学习目标，本体学习技术中的任意一种方法都有自己的适 用范围，无法保证在所有情况下都得到好的学习结果。因此，如何将各种方法进 行综合从而获得更好的学习结果，是未来的一个研究方向。而且，现有的本体学 习方法都需要人的参与，虽然完全自动的方法在短期内是不现实的，但由于w e b 资源的大量性，还需要进一步提高本体学习的自动化程度，尽量减少用户的参与。 ( 3 ) 概念间非分类关系的获取：不仅应判断两概念间是否存在层次关系， 而且应该为获耿的关系赋予相应的语义标签。概念间关系的获取主要方法是：基 于模板的方法( 模式匹配) ；基于概念聚类的方法；基于关联规则的方法；基于 词典的方法等。 ( 4 ) 公理的获取：此方面的研究成果很少，我们可以利用数据库定义良好 的结构来获取一些简单的定理。 。 ( 5 ) 本体学习工具的改进。 目前。本体研究工具主要有：a m i rk a b i ru n i v e r s i t yo ft e c h n o l o g y 开发的 h a s t i ；u n i v e r s i t yo fr o m e 开发的o n t o l e a m ：u n i v e r s i t yo fk a r l s u h e 开发的 t e x t - t o o n t o ；m i s s i s s i p p i s t a t eu n i v e r s i t y 开发的o n t o b u i l d e r ；u n i v e r s i t yo f k a r l s u h e 开发的o m o l i f t 以及s t a n f o r du n i v e r s i t y 开发的p r o t 6 酌2 0 0 0 等 ( 6 ) 对本体学习结果的评价标准。 ( 7 ) 本体的快速构建，即开发一种能够支持中文的本体学习工具。 2 3 信息粒度原理 粒度本来是一个物理学概念，它在计算机界则被用作“信息粗细的平均度 量”。信息粒度的提出，主要是因为很多专家和学者都认识到人工智能的一个特 点：在认知的处理现实世界的问题时，常常采用从不同层次观察问题的策略。 以三元组( x ，f ，d 来描述一个问题。其中x 是论域，厂( ) 表示论域上( 元素) 1 3 浙江师范大学硕士学位论文 的属性，f ：x 呻y ，y 可以是以维空间，也可以是一般的集合；t 是论域的结构， 它表示论域中各元素之间的关系。 对于一个问题，有时需要在不同的粒度层次上对问题进行求解，因此需要研 究不同粒度世界的关系。 设足表示由论域x 上一切等价关系组成的集合，可以定义如下等价关系， 也就是粒度的“粗”和“细”。 定义2 1 设兄i ，r 2 e r ，如果对于任意的x ，y e z ，都有x r i y j x r 2 y ，那 么就称庙