（计算机应用技术专业论文）粒计算在私有数据保护中的应用研究.pdf

摘要 摘要 随着互联网上收集和使用个人信息变得越来越容易，个人信息的公开对未 授权的用户来说，即使不是故意地，也可能会导致个人隐私权的问题。当然， 如果使用的恰当，这些数据对于科学家们、分析师们以及决策者们来说是非常 宝贵的资源。所以，假如没有有效的防御措施的话，隐私信息被侵犯的可能性 则很大。因此，寻求对隐私信息的公开发布与关键内容的隐含化之间的平衡， 就显得尤其重要。 粒计算( g r a n u l a rc o m p u t i n g ，g r c ) 是信息处理的一种新的概念和计算模 式，其基本思想是在不同的粒度层次上进行问题求解。本文在深入研究粒计算 的基础上，将其应用到隐私保护这一新的领域中，旨在探索出一种基于粒计算 的隐私保护方法。 本文针对不完备信息系统采用基于粗糙集粒计算模型来进行隐私保护的研 究。首先，在研究粒计算理论及粒计算相关模型的基础上，提出了基于约简属 性来构建层次相容粒度空间的方法，并设计了相应算法。该方法根据约简属性 的幂集来构建各层次粒度知识，为后续的算法做好准备。其次，提出基于粒计 算的信息隐含化方法和相应的算法。所提出的方法以对决策信息的近似分类质 量作为一个衡量是否需要进行信息隐含的度量，通过以下几个步骤来实现。第 一，对原始信息系统进行约筒，并计算约简属性下对决策信息的近似分类质量。 第二，对近似分类质量不满足给定的信息隐含要求原始信息系统，则构建它的 层次相容粒度空间；第三，在所构建的原始信息系统的层次相容粒度空问基础 上进行遍历和对相应属性值进行粒度粗化：从第一层开始对该粒度层次上的在 约简属性子集中的所有属性的属性值进行粒度粗化，直到粗化后的信息系统在 该层约简属性集合下的近似分类质量小于原始信息系统在约简属性集合下的近 似分类质量为止。最后，为了验证基于粒计算的信息隐含化相关算法的有效性， 精选3 组测试数据集从多个角度进行实验测试，并对实验结果进行分析。测试 结果表明本文提出的基于粒计算的信息隐含化方法是有效的。 论文最后部分对所做的工作进行了总结，并分析了多个有待改进的地方， 同时展望了粗糙集粒计算模型在保护隐私数据领域的进一步研究方向。 关键字：粒计算；相容粒：层次相容粒度空间；隐私数据保护；信息隐含化 a b s t r a c t a b s t r a c t i th a sb e c o m em u c he a s i e rt oc o l l e c ta n du s ei n f o r m a t i o na b o u ti n d i v i d u a l sv i a i n t e m e t i nt e r mo fu n a u t h o r i z e du s e r s ，t h ep u b l i c i t yo fi n d i v i d u a li n f o r m a t i o nw i l l c a u s et h ep r i v a c yp r o b l e m ，e v e ni fn o ti n t e n t i o n a l l y o fc o u r s e ，i fu s e da p p r o p r i a t e l y , t h e s ed a t am a yb ev e r yv a l u a b l es o u r c e sf o rs c i e n t i s t s ，a n a l y s t s ，a n dp o l i c y - m a k e r s s o ，i ft h e r ei sn oe f f e c t i v em e a s u r e ，t h e r em a yb eag r e a td a n g e ro fp r i v a c yi n v a s i o n t h e r e f o r e ，h o wc a nw eb a l a n c i n gd a t au t i l i t ya n dp r i v a c yp r o t e c t i o ne f f e c t i v e l yi st h e c o r ep r o b l e mf o rt h ep r o c e s so fi m p l i c a t i o n g r a n u l a rc o m p u t i n g ( “g r c ”f o rs h o r t ) i st h en e wc o n c e p ta n dc o m p u t i n gm o d e l t oi n f o r m a t i o np r o c e e d i n g ，a n dt h e nt h em a i ni d e ai sp r o b l e ms o l v i n go nd i f f e r e n t g r a n u l a rh i e r a r c h i e s i nt h ep a p e r , g r a n u l a rc o m p u t i n gi sa p p l i e dt ot h ef i e l do f p r i v a c yp r o t e c t i n gb a s e do ns t u d y i n gt h ec o n c e p to fg r a n u l a rc o m p u t i n gd e e p l y , s o t h a ti ti sa i m e da ts e e k i n gf o rap r i v a c yp r o t e c t i n gm e t h o db a s e do ng r a n u l a r c o m p u t i n g i nt h ep a p e r , t h ei m p o r t a n tr e s e a r c hi s s t u d ya n da p p l i c a t i o no fp r i v a c y p r o t e c t i n gb a s e do nr o u g hs e t sa n dg r a n u l a rc o m p u t i n gm o d e li nc o n n e c t i o n 、析廿l i n c o m p l e t ei n f o r m a t i o ns y s t e m f i r s t l y , b a s e do nt h es t u d yo fg r cc o n c e p t sa n d m o d e l s ，am e t h o do fh o wt oc o n s t r u c th i e r a r c h i c a lr o l e r a n c eg r a n u l a r i t ys p a c eb a s e d o nr e d u c ta t t r i b u t e si sp r o p o s e d ，a n dd e s i g nt h ec o r r e s p o n da l g o r i t h m a c c o r d i n gt o t h ep o w e rs e t so fr e d u c ta t t r i b u t e s ，g r a n u l a rk n o w l e d g eo fe a c hh i e r a r c h yi s c o n s t r u c t e d , a n di sr e a d yf o rf o l l o wa l g o r i t h m s s e c o n d l y , am e t h o db a s e do ng r c a n da l g o r i t h m so fi n f o r m a t i o na n o n y m i s a t i o ni sp r o p o s e d t h em e t h o di sv i e w e da sa m e a s u r e m e n to fa p p r o x i m a t i o nc l a s s i f i e dq u a l i t yo v e rd e c i s i o ni n f o r m a t i o n , w h i c h t e s ti n f o r m a t i o na n o n y m i s a t i o nw h e t h e ro rn o t t h e nt h i sm e t h o di sa c h i e v e df r o m f o l l o ws t e p s ：f i r s t , t h er e d u c t i o no ft h eo r i g i n a li n f o r m a t i o na n da p p r o x i m a t i o n c l a s s i f i e dq u a l i t yo ft h er e d u c ta t t r i b u t e so v e rd e c i s i o ni n f o r m a t i o ni so b t a i n e d s e c o n d ，i fc l a s s i f i e dq u a l i t yo ft h eo r i g i n a li n f o r m a t i o ns y s t e mt h ea p p r o x i m a t i o ni s n o ts a t i s f i e d ，h i e r a r c h i c a lc o m p a t i b l eg r a n u l a r i t ys p a c eo fi n c o m p l e t ei n f o r m a t i o n s y s t e mi sc o n s t r u c t e d t h i r d ，t h eh i e r a r c h i c a lt o l e r a n c eg r a n u l a r i t ys p a c eo fo r i g i n a l n a b si k a c l i n f o r m a t i o ns y s t e mi st r a v e r s e da n dm a d et h ec o r r e s p o n da t t r i b u t ev a l u e sc o a r s e r ： f r o mf i r s th i e r a r c h y , a t t r i b u t ev a l u e so fa l lt h ea t t r i b u t e s ，t h a ti st h es e to fr e d u c t i o n a t t r i b u t e s ，a r ec o a r s e n e d0 1 1t h i sh i e r a r c h y , u n t i lt h ea p p r o x i m a t i o nc l a s s i f i e dq u a l i t y o ft h ec o a r s e n e di n f o r m a t i o ns y s t e mo v e rt h es e to fr e d u c t i o na t t r i b u t e s o nt h i s h i e r a r c h yi ss m a l l e rt h a nt h a to ft h eo r i g i n a li n f o r m a t i o ns y s t e mo v e rt h es e to f r e d u c t i o na t t r i b u t e s f i n a l l y , i no r d e rt op r o v et h ee f f i c i e n c yo ft h em e t h o do f i n f o r m a t i o na n o n y m i s a t i o na n dt h ec o r r e s p o n da l g o r i t h m ，t h r e eg r o u p so ft e s t i n g d a t a s e t sa g ec h o s et ot e s tf r o mv a r i o u sa s p e c t s ，a n da n a l y s i st h et e s t i n gr e s u l t s t h e n t h et e s t i n gr e s u l t ss h o wt h a tt h em e t h o do fi n f o r m a t i o na n o n y m i s a t i o nb a s e do ng r c i se f f e c t i v e i nl a s tp a r to ft h ep a p e r , a l lo fr e s e a r c h e sa n d w o r ki nt h ep a p e ra l es u m m a r i z e d , a n dm a n ya s p e c t so fi m p r o v e m e n t sa r ea n a l y z e d ，a n dt h ef u r t h e rr e s e a r c hd i r e c t i o n s 洫n l ef i e l do fp r i v a c yp r o t e c t i n gb a s e do nr o u g hs e ta n dg r a n u l a rc o m p u t i n ga r e p r o s p e c t e d k e y w o r d s ：g r a n u l a rc o m p u t i n g ；c o m p a t i b l eg r a n u l a r ；h i e r a r c h i c a l t o l e r a n c e g r a n u l a r i t ys p a c e ；p r i v a c yp r o t e c t i n g ；i n f o r m a t i o na n o n y m i s a t i o n i l l 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：监艏沲签字日期： 矽矽年1 月乡e l 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：丝村滔 导师签名：币7 彳w 巧夺， l 签字目期：硼9 年1 月弓日签字日期：知，口年t 月多日 第1 童绪论 第l 章绪论 1 1 课题来源与研究意义 过去，大部分人都没有资源也没有时间侵犯他人隐私，也没有方法散播已 暴露的隐私信息。所以，那是的主要工作是限制政府机构以及出版社等不侵犯 隐私i l j 。但是，互联网技术的发展从根本上改变了这个状况，而由于这种变化发 展了数据挖掘技术。现在，知识的发现和数据的挖掘在许多应用中发挥了积极 作用，这种积极作用也使得收集和使用个人信息变得越来越容易。若使用得当， 这些信息对科学家、分析师及决策者而言都是相当宝贵的资源，因为正确的信 息有利于得出合理而准确的结果。个人信息被公开对未授权的用户来说，即便 他们获取信息不是出于故意，但也可能会导致个人隐私权被侵犯的问题。众所 周知，在公开信息被侵犯得最严重的就是个人隐私权，即对个人数据信息的非 法收集、利用或篡改、窃取，例如现今正流行的人肉搜索从某种角度来说就是 侵犯个人隐私权的行为。目前国际社会已经提出了一系列保护信息隐私权的措 施，阐述了若干关于保护信息隐私权的核心原则。著名的公平信息实施( f a i r i n f o r m a t i o np r a c t i c e ) 原则就是研究数据隐私保护，这一原则阐述了在数据挖掘 时收集到的信息必须考虑如何对进行隐私保护。这是数据挖掘中的隐私保护问 题，即如何在保证个人隐私的前提下进行数据挖掘 2 1 。 随着p a w l a k 提出粗糙集理论【3 6 j 与越来越多的学科联合并将其成果应用到 全新的领域，使得用粗糙集相关理论来研究本课题成为可能。将粒计算 7 - 1 2 j 理论 ( g r a n u l a rc o m p u t i n g ，简记为g r c ) 这种融合了粗糙集、模糊集及人工智能等 多种理论研究成果应用到隐私保护这个全新领域亦是一种新的尝试。粒计算理 论从更高层次对复杂问题进行综合分析，强调对现实世界问题多视角、多层次 的理解和描述，从而得到对问题的粒表示。它的研究对人工智能、问题求解及 智能信息系统的设计与实现有着非常重要的指导意义。 在现实生活和工作中，由于对数据的不适当地理解或获取以及获取信息时 的代价太大等原因，使得数据的不确定性甚至缺损现象普遍存在。在各种实用 数据库中，属性值缺失的情况经常发生甚至不可避免。因此，在绝大多数情况 下，信息系统是不完备的，或者说存在某种程度的不完备。所以，本课题研究 第l 章绪论 的是在基于粗糙集粒计算的模型下针对不完备信息系统来进行信息隐含化的隐 私保护技术。该研究一方面从新的角度和方法提供了隐私保护技术，另一方面 拓展了基于粗糙集粒计算模型的应用领域。 本课题来源于导师的研究项目。 1 2 国内外研究现状 1 2 1 粒计算的起源及发展 1 9 9 7 年，t k l i n 教授首次介绍了“粒计算 【1 3 】这一概念，它被认为是涉及 多种科学研究的一个全新领域。从那时起，许多研究者开始密切关注这个发展 迅速且快速成长的课题，如参考文献 1 4 1 2 0 】。所以，由于众多粒计算的方法、 模型被提出和研究，也就增强了学者们对粒计算理论的理解。随着粒计算理论 研究不断深入地广泛应用于在相关各个领域，国际上已形成了专门的粒计算研 究群体。1 9 9 8 年1 0 月第六届粗糙集、数据挖掘及粒度计算国际研讨会“ms i x t h i n t e r n a t i o n a lw o r k s h o po nr o u g hs e t s ，d a t am i n i n ga n dg r a n u l a rc o m p u t i n g ， r s d m c j r c 9 8 ”在美国北卡罗那州召开，这次会议是首次以粒计算为主题的国际 会议。2 0 0 3 年在中国重庆召开的第九届粗糙集、模糊集、数据挖掘和粒度计算 国际研讨会( r s t f d g r c 2 0 0 3 ) ，以及2 0 0 5 年在加拿大r e g i n a 召开的第十届粗 糙集、模糊集、数据挖掘和粒度计算国际研讨会( i 峪1 f d 2 0 0 5 ) 中粒计算 都得到了广泛认可。 粒计算是研究基于多层次粒结构的思维方式、问题求解方法、信息处理模 式及其相关理论、技术和工具的学科。我国学者在粒计算方面的研究一直处于 世界领先地位。第一、四和五届i e e e 国际粒计算大会“i n t e r n a t i o n a lc o n f e r e n c e o ng r a n u l a rc o m p u t i n g ”分别于2 0 0 5 年、2 0 0 8 年和2 0 0 9 年在北京、杭州和南昌 召开，就什么是粒度计算、粒度计算需要解决的问题、粒度计算的发展和应用 等问题展开了讨论与研究。第二、三届“i n t e m a t i o n a lc o n f e r e n c eo ng r a n u l a r c o m p u t i n g 于2 0 0 6 年和2 0 0 7 年在美国亚特兰大和硅谷召开。从这些会议的文 献来看，其成果涉及粒计算的哲学、理论、方法和应用等多个方面。 1 2 2 粒计算的研究现状 随着粒计算理论被应用到众多相关研究领域，有部分研究者们研究基于智 2 第1 章绪论 能计算理论和模型的粒计算理论，并将其公式化后的相关应用有1 1 4 h 1 6 1 1 8 h 2 0 l 。首 先，l i n i l 3 1 建议把粒计算理论作为一个全新的研究领域来发展。而后，l i n 2 1 2 2 1 又提出用邻域系统来公式化粒计算，即作为基于粗糙集理论的划分的一个扩展。 y a o 2 3 2 4 】贝0 在基于来自计算机科学其他领域的规则和想法的大背景下来解释粒 计算。另外，其他研究者们在基于粒度和抽象的概念上，研究粒计算理论在人 工智能领域的应用，例如，知识表示f 2 5 2 6 】、定理证明【2 5 1 、信息检索 2 6 , - - 2 7 ，规划 2 8 , - , 2 9 ，智能控制系统 3 0 1 ，模式识别【3 ，本体【3 2 1 ，和数据挖掘【3 3 】等。其中，h o b b s 2 5 提出了基于观察的粒度概念，“我们将世界定义在各种大小不同的粒度下来观 察，并且从中抽取出我们当前感兴趣的部分，它是一种在公式化方面类似于粗 糙集理论的理论。g i u n e h i g a l i aa n dw a l s h 2 6 】则提出抽象化理论，抽象化被看作是 “一个过程：它允许人们考虑那些相关的和忽略那些不相关的。它们是在抽取 信息和泛化领域上最前沿的成果。而k n o b l o c k 2 9 1 提出分层规划理论，考虑在不 同粒度上的规划方法。 近年来，随着粒计算研究成为热点，国内也有很多学者进行了粒计算的研 究。商空间理论就是被人们广泛认识和推广的一种粒计算理论，张钹和张铃提 出了一个基于层次描述和表示来解决问题的方法，即商空间理论【蚓。该理论将 粒计算理论看作是一种解决问题的结构化方法，并在此基础上研究基于商空间 理论的粒计算模型【2 7 1 和模糊商空间及粒计算的商闭包空间模型理论伫引，为粒计 算提供了新的数学工具和模型，该理论已成功应用于数据挖掘等领域；为了探 讨粗糙集理论在各种环境下的应用，刘清【1 8 ”j 基于粗糙逻辑概念提出粒逻辑及 其归结原理，构造了基于粗糙逻辑的近似推理系统，并将该系统应用于医疗诊 断系统中；王国胤1 3 7 】提出基于相容关系的粒计算模型，并利用属性值上的相 容关系给出了不完备信息系统的粒表示、粒运算规则及粒分解算法，同时在深 入研讨粗糙集中的属性约简问题的前提下，提出了基于不完备信息系统的粒表 示下的属性判定条件，同时对基于粒计算的规则提取方法进行深入研究。 1 2 3 隐私保护技术的研究现状 伴随数据共享、隐私保护、知识发现等多重需求而产生的基于隐私保护的 数据挖掘( d a t am i n i n gb a s e do np r i v a c yp r e s e r v i n g ，简称p p d m ) ，受到国内外著 名高校、科研机构和工业界的广泛关注，并成为数据挖掘和信息安全领域近几 年来新的研究方向和研究热点【2 j 。 3 第1 章绪论 基于隐私保护的数据挖掘主要是关注两个方面的问题【3 8 1 ：一是像姓名、身 份证号、地址和爱好等敏感原始数据的处理，避免个人隐私信息的泄露。二是 能通过数据挖掘工具得到的敏感知识也应该避免其被恶意挖掘。基于隐私保护 的数据挖掘的主要目标是使用某种方法对原始数据进行处理，使得私有数据和 知识在挖掘之后仍然是私有的。 目前，根据数据的分布情况，数据挖掘中的隐私保护方法分为集中式数据 挖掘的隐私保护技术和分布式数据挖掘的隐私保护技术。 其中，集中式数据挖掘的隐私保护技术【2 】包括： ( 1 ) 数据变换法。o l i v e r i r a 3 9 】等人研究基于数据清洗思想的基础上，提出 了一系列关联规则挖掘算法。 ( 2 ) 数据阻塞技术。s a y g i n l 4 0 】提出三个具体的关联规则隐藏算法。 ( 3 ) 数据扰乱技术。a g r a w a l l 4 1 】提出一种基于随机扰动的决策树构造算法。 黜z v i 【4 2 】提出典型的基于随机扰乱技术的隐私保护关联规则算法m a s k 算 法，该算法须对项目集的支持度进行重构，估算项目实际支持度，从而发现频 繁项目集。针对m a s k 算法的不足，王锐【4 3 】等人提出将随机响应技术与关联规 则挖掘算法相结合，一个多参数随机扰动算法- m r d 算法。 ( 4 ) k 匿名技术。l o u k i d e s 和s h a 0 1 4 4 1 提出k a n o n y m i s a t i o n 技术( 基于贪 婪聚类算法) ，通过将相似属性的属性值替换为更一般的值，使得在隐含化后的 表格中，每个元组的一般化后的相似属性的属性值被统一为与其他至少k 1 个元 组一样。随着近年来国内开始流行研究k 匿名技术，研究各种k 匿名模型【4 5 枷j ， 并对该技术进行改进和扩展1 4 7 。 ( 5 ) 反向构造数据集方法。郭宇红等人郴j 提出给予f p t r e e 的反向频繁项 集挖掘方法。 分布式数据挖掘的隐私保护技术【2 j 根据数据分片情况，可将分布式隐私保护 数据挖掘技术分为：数据垂直分片的隐私保护技术，如v a i d y a 和c l i t t o n l 4 9 等人 提出的无需透露双方数据信息的安全点积协议和数据水平分片的隐私保护技 术，及k a n t a r c i o g l u 5 0 1 等人提出的水平分布隐私保护关联规则挖掘算法。分布式 数据挖掘的隐私保护技术根据参与方数目可分为：基于安全两方的隐私保护技 术和基于安全多方的隐私保护技术。目前，分布式数据挖掘的隐私保护技术主 要采用基于密码学方法来进行数据加密。其中比较有代表性的是基于安全多方 计算【5 l 】( s e c u r em u l t i p a r t yc o m p u t a t i o n ，简称s m c ) 的隐私保护数据挖掘技术。 4 第1 章绪论 当前，基于粒计算模型的隐私保护研究还比较少。其中较有代表性的是w a n g d w 【5 2 】等人提出的基于粒计算的隐私保护c e l l s e c u 系统，发表了关于此系统的数 篇文章，对系统进行了多番改进并结合实际将其应用到医疗数据库系统中。随 着粒计算和粗糙集理论受到众多学者更广泛的关注，相应的隐私问题和隐私保 护技术必将会逐渐成为近几年的研究热点。 1 4 本文的主要研究内容 ( 1 ) 深入理解和掌握隐私保护技术的相关理论基础和目前的研究新进展； ( 2 ) 分析研究粗糙集理论相关原理及知识获取方法，并掌握针对不完备信 息系统的粗糙集处理方法和相关原理； ( 3 ) 理解粒计算理论及方法，深入分析基于相容关系的层次粒度空间构 建方法；在此基础上，研究并提出基于约筒属性来构建层次相容粒度空间的方 法，并提出相应算法； ( 4 ) 分析理解由领域背景知识提供的属性泛化字典，研究如何根据构建的 层次相容粒度空问和属性泛化字典对约简属性的属性值进行粒度粗化，并提出 相应的属性值粒度粗化算法； ( 5 ) 分析基于粗糙集粒计算模型的隐私保护框架，着重研究本课题的关键 方法一基于粒计算的信息隐含化方法，提出相应的信息隐含化算法； ( 6 ) 基于提出的信息隐含化算法，对3 组u c ! 数据集进行测试，并对实验 结果进行分析。 1 5 本文的组织结构 具体章节如下： 第1 章：绪论 介绍本课题的研究背景、研究意义等，介绍了粒计算概念和私有数据保护 的研究现状，最后介绍了本文的主要研究内容以及论文的组织结构。 第2 章：粒计算理论 本章首先在浅析粒计算的基本知识的背景上，介绍粒计算理论的基本组成 以及基本问题；其次，着重论述了粒计算的主要模型和理论方法，并深入研究 各种粒计算模型之间的差异和相互关系；最后，简介了粒计算理论广泛的应用 5 第1 章绪论 领域。 第3 章：隐私保护技术分析 本章介绍基于隐私保护的数据挖掘技术，重点论述了基于启发式的隐私保 护技术，并简介了隐私保护技术的性能评价标准。 第4 章：基于粗糙集粒计算模型的隐私保护 本章提出基于粗糙集粒计算模型来处理隐私保护问题。首先，主要定义了 在不完备信息系统下的相容信息粒及信息粒度；其次，提出采用基于约简属性 来构建不完备信息系统的层次相容粒度空间的算法；然后，提出基于粒计算的 信息隐含化算法，即根据层次相容粒度空间的粒度层次的顺序来对不完备信息 系统进行信息隐含化的；最后，给出了一个简单实例进行说明。 第5 章：信息隐含化算法的测试 介绍了测试信息隐含化的测试平台，开发语言和测试数据。对3 组数据集 进行有关信息隐含化的测试和测试结果的分析。通过对不同情况的测试结果表 明了所提出的基于粒计算的信息隐含化算法是有效的。 第6 章：结束语 包括总结与展望。 论文最后包括“致谢”、“参考文献和“攻读学位期间的研究成果 三个 部分。 6 第2 章粒计算理论 第2 章粒计算理论 2 1 引言 众所周知，人们针对同一个问题可以从多个角度、多个层次分别予以分析， 之后选择一个相对简单的角度和层面去解决这个问题。并且在总体解决过程中 能非常自如地从一个角度转换到另外一个角度，或者从一个层面切换到另外一 个层面。粒计算就是研究基于多层次粒结构的思维方式、问题求解方法、信息 处理模式及其相关理论、技术和工具的学科。它集哲学思想、方法论、计算模 型及应用研究为一体，是将人类智能上的哲学思维基本原理应用于实际问题解 决的成功尝试。其主要研究目的就是找到一种能够模拟人类这种从不同角度和 层面观察、分析问题的能力的理论方法，从而能够圆满地解决问题。 2 2 粒计算的基本组成 粒计算的基本组成1 7 l 主要包括3 个部分：粒、层次和粒结构。 粒 构成粒计算模型的最基本元素是粒子。粒子具有双重身份，它可以是某个 整体中相对独立的一个部分，也可以是一些粒子共同组成的一个粒。所有的粒 子都具有内在属性、外在属性和环境属性。当粒作为整体时，我们所要考虑的 是粒的内在属性，内在属性由粒所拥有的元素决定。当粒作为部分时，我们所 要考虑的是粒的外在属性，由于具有外在属性，粒就能够被人们直接认识。粒 的环境属性是指粒对外部环境变化的应对情况，即对外部环境的影响和回应以 及对其内在属性、外在属性的保持与调整。 粒的内在属性通常需要强调它所包含的各个细小个体的不同特性，是对它 内部各个基本组成成分性质的描述：而粒的外在属性则是强调，把它考虑为一 个整体时所体现出的综合特性。s i m o n 7 】曾经用一个例子解释了粒的双重身份及 粒的内在属性、外在属性之间的关系。这个例子是这样的：假设有这样一座办 公大楼，这座大楼是由许多楼层组成的，每个楼层又包含了许多房间，每个房 间又被分成许多小的办公区域。相对于整个社区环境来说，这座大楼就是一个 整体，也即是一个粒，它的外墙及外形设计就是它所表现出来的外在属性。而 7 第2 章粒计算理论 相对于更细小的组成时，这座大楼则是复杂的分层结构，它的内部组成和划分 就是它的内在属性。再从大楼的各个局部看，每个办公区域的温度、湿度、人 员密度都不尽相同，因而体现了粒的内在属性的多样性。最后从总体看，整个 办公楼就形成一个相对稳定、相对封闭的内环境，从而区别于其他外环境。 一层次 粒均存在于特定的层次中以是不相交的关系，也可以是相交的关系。层次 中每一个粒都表示一个特定的粒化观点，处于相同层次的粒形成了这个层次的 覆盖。层次中粒的粒化观点相互补充、对照，完整地表达了在该层次上的某种 问题。每个层次都具有内在属性、外在属性、环境属性，同一层次的粒属性共 同体现本层次特性。 在问题求解中，选择在最合适的粒度层次上产生对一个问题的描述，能帮 助更好更快地解决问题。在不同的粒层上求解同一问题的复杂度往往不尽相同。 较高层次包含较低层次，或者由较低层次组成，较高层次一般由聚合粒组成。 所有层次都存在一定的独立性，任意两层次之间的关系是通过偏序关系的传递 性和桥接原理来表示和体现的。粒计算模型的主要作用是能够在不同粒度层次 上进行问题求解，使不同粒度层次上的解能够进行相互转化。 _ 粒结构 。在粒计算研究中强调的是全面、整体的观点，而不是局部、离散的观点。 若要达到该目标，不仅要考虑一个分层结构中的多个层次，还需要将多个分层 结构综合考虑。 分层结构由若干层次组成，层次间的递进关系反映了粒由表及里、由抽象 到具体的变化。若干低层次的粒可以组合成一个高层次的粒。反之，一个高层 次的粒可以分解为若干个低层次的粒。低层次的粒为高层次的粒提供了精确的 描述和详细的信息。高层次的粒则将与本层不相关的细节忽略，并为低层次的 粒提供更粗糙或者更粗粒度的描述。 粒结构的形式包括：直线型、树型和网络型，如图1 1 所示。图中的圆形表 示粒，同一高度的粒表示在同一粒度层次。需要说明的是，分层结构即是对一 个问题近似的描述。 8 第2 章粒计算理论 图2 1 粒结构形式 2 3 粒计算的基本问题 粒计算的基本问题【1 1 】包括两个主要的方面：一个是信息粒度如何构建，一 个是如何利用粒度进行计算。前者主要处理粒度的表示和语义解释，而后者主 要解决怎样利用粒度去进行问题求解。信息粒子的大小；信息粒度的的表示和 语义解释；信息粒度粗细与求解有效性的关系；信息粒度的运算法则；信息粒 度之间及其与外部环境的关系等内容共同构成一个粒度世界。粒度世界的构造 影响问题求解，合理的构造能提高问题求解的效率。 问题空间的粒化指的是将问题空间分解为多个子空间，或基于确定的信息 和知识将问题空间中的个体聚集成不同的类( 即粒) 。粒计算和概念生成、知识 发现和数据挖掘都是有联系的，概念生成的目的之一是表示、特征化、描述和 解释具有某些概念的粒，知识发现和数据挖掘都是在粒之间建立联系。 粒化 粒化是构造一个问题求解空间的过程，它可以简单理解为在给定粒化准则 下构建粒层的过程，这个过程构建粒计算的粒、粒视图、粒网以及层次结构等 基础单元。根据不同的粒化准则得到多个粒层，进一步得出粒层的网络结构。 粒化方法有自顶而下通过分解粗粒子得到细粒子和自底向上合并细粒子得到粗 粒子。粒化问题空间的过程主要是解决粒化准则、粒化算法、粒和粒结构的表 示及粒和粒结构的定性描述等问题。粒化准则主要针对语义方面解决两个对象 能放进同个粒子内的问题，根据实际问题的具体需求和具体精度求解得到准 则，它的一个最主要的要求就是忽略冗余细节，进而降低问题求解复杂度。粒 化方法属于算法问题，它回答对实际问题空间如何进行粒化，采用何种算法和 工具实现粒层的构造。 9 第2 章粒计算理论 粒结构描述的是如何用形式化的语言表述粒化方法得到的粒，粒结构描述 能方便后续的说明和计算。例如粗糙集理论模型中，粒的表示是一个子集，而 概念格理论中，粒的表示就是一个概念。粒结构包括概念的外延和内涵，它的 描述形式往往多种多样：在商空间理论模型中，粒结构是分层递阶结构；在概 念格模型中，粒结构是种h a s s e 图。成功的粒化方法的原理大都以解空间形成 的划分为目标，解空间形成的划分有利于将子空间上的解更方便地合成为原问 题空间的解，我们所知道的商空间理论就是基于这一原理实现的。但是，如果 用某种粒化方法形成的解空间不是划分将增加合成问题空间解的复杂度。 一粒的计算 从狭义上理解的粒计算是以粒为运算对象进行问题的推理或求解。用粒计 算解决问题可以通过系统访问粒结构的方法实现，这种访问包括在粒在层次结 构中向上和向下两个方向的互动，及粒在在同一层次内的转移，即不同粒度层 次粒之间和同一粒度层次上粒的相互转换。由映射来表示不同粒度层次之间的 联系，以不同的粒度、不同的细节来表示在不同粒度层次上同一问题，粒度层 次之间的映射建立了同一问题的不同粒度描述以及它们之问的联系。商空间理 论模型就是通过自然投影建立了分层递阶的商空间链式结构。 粒计算的主要特点是同一问题的解可以在不同粒度层次之间自由转化。这 一点就决定了人们能用粒计算方法高效地实现复杂问题的求解。通过模糊等价 关系的截关系可以建立模糊商空间上的分层递阶结构的相应的转化联系：可以 通过属性的增加或删减来控制粗糙集理论中的划分粒度；可以通过改变概念的 内涵来实现概念格理论模型中概念粒子的相互转化。这些转化虽然方式不同， 但一个共同的特点是在转化的过程中，必须能在不同粒度层次上表现出问题求 解的重要性质，重要性质的表现好坏是评价粒化方法好坏的重要依据。在粒层 相互转变过程中某些重要属性体现不了，不但不利于问题空间的求解，而且会 导致问题求解过程中产生发散现象，从而增加问题求解的复杂度。 粒计算的两个基本问题中，粒化方法是关键，它决定着粒计算成功与否。 正因为粒化方法的关键性，粒化方法就成为了人们研究的热点问题。已经被研 究出来的粒化方法很多，有基于等价关系的划分产生粒，有基于模糊集产生模 糊信息粒，有基于模糊等价关系截集产生分层递阶粒空间，有基于概念格产生 概念信息粒和概念知识粒等等。 总而言之，粒计算是一个多准则学科，粒计算从众多科学领域中获得它的 1 0 第2 章粒计算理论 基本思想、基本准则和基本方法，是一种基于不同层次粒度和细节的一般性问 题求解理论。用粒计算进行研究，能够探知到不同学科之间原理的关联性。同 时粒计算与相关具体的学科研究又是相互独立的。我们如果掌握了粒计算问题 求解中的结构化思维和抽象思想，对我们在任何领域中运用粒计算都是有帮助 的。 2 4 粒计算的主要模型与理论方法 2 4 1 三种主要的粒计算模型 _ 基于模糊集合论的词计算模型1 9 1 1 j 在某些科学领域广泛应用的是普通的精确方法，然而，在现实中我们常常 会遇到有些情况是不能精确定义的，比如人文学科。因此，在这些无法用精确 的数学方法来描述的情况下，基于庞杂的入文学科系统，科学家们就开始尝试 用表示不精确程度的词来描述。此时，z a d e h 就提出基于模糊概念的模糊粒计算 方法，方法中提出的概念的模糊性是源自于基本粒的模糊相似性及相近性等。 其提出基于模糊信息粒化原理，能在不同的环境下，根据不同的情况得出问题 求解的合理结果。 人类主要是运用语言来思考、判断和推理的，然而要利用一个很粗粒度的 语言来推理判断思考的话，那就必须进行“词计算 ，即z a d e h 【5 列提出的基于模 糊概念的词计算( c o m p u t i n gw i t hw o r d s ) 理论，它是用“词来进行计算及推 理的方法。而对于粒计算问题中的一个基本问题粒化问题，为了弥补在现 实问题中碰到的问题求解空间并非都是精确，大部分都是模糊的问题，学者们 提出了模糊信息粒化方法，是对基本信息粒化方法的一种扩展。从狭义上来看， 模糊词计算理论是指运用通常意义下的数学运算加、减、乘、除等来构造带具 有不精确或模糊的数值的词计算数学体系，并借助模糊逻辑概念，利用群、环、 域等代数结构，构造出以“词为定义的类似结构，像模糊概念及其运算【5 6 】就 属于这种结构。从广义上来看，模糊词计算理论则是指用“词进行推理、构 建原型系统以及编程。 从应用方面来看，国外的z a d e h t 5 卅提出基于模糊概念的模糊信息粒化理论【5 4 1 ( t h e o r yo ff u z z yi n f o r m a t i o ng r a n u l a t i o n , t f i g ) ，实质是数学方法，它启发自人 类利用模糊概念来处理问题的方式，并建立在一种能在模糊信息粒化过程中起 第2 章粒计算理论 主导作用，并能提供概念框架及相关技术的模糊逻辑和信息粒化方法 ( i n f o r m a t i o ng r a n u l a t i o n ) 的基础上；相对于国外来说，国内对广义词计算理论 的研究工作才刚刚起步，因此理路研究成果还不够成熟。作为研究热点之一的 模糊控制系统，它作为基于信息粒化和词计算( i g c w ) 的系统，具有很强的信 息推理判断和处理能力，能从更高程度更好地模拟人类智能。然而，李征1 5 7 】 等人认为模糊控制事实上只是应用了很少一部分的基于模糊概念的信息粒化技 术和词计算技术。王飞跃1 5 8 】则是在自然语言的基础上，提出建立以词计算为基 础的语言动力学系统( 1 i n g u i s t i cd y n a m i cs y s t e m s ，l d s ) ，并通过融合几个不同领 域的概念和方法建立了相关的词计算理论框架。无论是国外还是国内学者们的 这些研究，目的都是为了建立起人类的语言知识表示与计算机的数字知识表示 问的联系，已成为实现下一代智能化人机交互的理论基础之一。 总而言之，基于模糊概念的词计算理论是以贴近人类的思维模式来求解问 题的，并能高效快速地处理复杂系统的信息，因而有着广阔的应用前景。虽然 这种基于模糊概念的词计算理论体系在模糊控制、图像识别、语言处理、信息 检索、人工智能等领域已得到了一些较好的研究成果，但是由于理论本身的问 题导致其应用范围受到一定的限制。所反映出的存在于模糊信息粒化的基本准 则的两个核心问题，一是模糊约束的表述问题，另一个是模糊约束的继承问题。 因此，词计算理论必须和其他理论体系相结合，才能更加有效地处理复