（计算机软件与理论专业论文）基于模糊概念格的社会导航研究.pdf

西华大学硕士学位论文 基于模糊概念格的社会导航研究 计算机软件与理论 研究生谢春芝指导教师伊良忠 在i n t e m e t 这样一个海量的信息世界中，用户可能迷失，也可能在一个未曾 涉足的信息中不知所措。尽管当前的搜索引擎能够通过用户查询词来帮助人们 获取一些信息，但要从庞大的搜索结果找到有用信息，有时显得非常困难。怎 样帮助人们快速有效地找到自己感兴趣且价值更高的信息，是本文所要研究和 解决的主要问题。 所幸的是，人类社会中存在的一种普遍现象社会导航被引入到本领域， 其主要目标是直接地或间接地利用他人的信息来帮助人们做出决策。将社会导 航与搜索引擎相结合是引导人们在搜索引擎返回的大量结果中做出决策的有效 方法。概念格是规则获取与知识表达的重要工具，但其所基于的形式背景大多 是二值形式背景。而在实际中，大量的形式背景都是模糊的。因此，模糊概念 格( f c l ) 是在模糊形式背景下进行数据分析与知识发现的一种有效的工具。 本文取得的主要研究成果如下： 1 提出了基于模糊概念格的社会导航模型。该模型主要通过获取用户需要 导航的目标和社会经验来向用户提供导航。用户需要的导航目标是通过 n a v f c a 插件与用户交互过程中获得的用户查询词，社会经验是通过从日志文 件中抽取用户踪迹而构造出的模糊形式背景。通过将社会经验表示成模糊概念 格这种有效的知识结构，社会导航的网页的g r g s 及其摘要由n a v f c a 插件显 示给用户。同时，为实现本社会导航模型，设计并实现了如何获取用户踪迹、 模糊形式背景生成、在模糊概念格上进行社会导航并显示给用户等一系列技术 与算法。 2 提出并实现了模糊概念格构造算法( f c l b ) 。该算法从给定的模糊形式 背景与模糊集集合中，生成模糊形式概念，自动建立并图形化显示模糊概念格。 第1 页 西华大学硕士学位论文 3 设计并实现了基于模糊概念格的社会导航系统，并通过实验表明本系统 能将用户踪迹处理成有用的知识结构，这种结构有助于智能搜索。 关键词：社会导航，模糊概念格，模糊形式背景，形式概念分析 第u 页 r e s e a r c ho fs o c i a ln a v i g a t i o nb a s e d0 1 1 f u z z yf o r m a lc o n c e p t l a t t i c e c o m p u t e rs o f t w a r ea n dt h e o r y m a s t e rd e g r e ec a n d i d a t e ：x i ec h u n z h i s u p e r v i s o r ：y il i a n g z h o n g i nt h ei n f o r m a t i o nw o r l ds u c ha si n t e m e t ，p e o p l ew i l lb el o s to rw i l lb ea tal o s s t oa c ti na l lu n k n o w ne n v i r o n m e n t a sw ek n o w , s e a r c he n g i n ec a nh e l pp e o p l et o f i n ds o m ei n f o r m a t i o n h o w e v e r ，t of i n du s e f u li n f o r m a t i o ni nt h eh u g er e s u l t so f s e a r c he n g i n ei ss o m e t i m e sv e r yd i f f i c u l t s oh o wt oh e l pp e o p l et of i n di n t e r e s t i n g a n dm o r ee f f e c t i v ei n f o r m a t i o ni st h em a i ni s s u eo ft h i sp a p e r f o r t u n a t e l y , s o c i a ln a v i g a t i o nt h eu n i v e r s a lp h e n o m e n o ni nh u m a ns o c i e t yi s i n t r o d u c e di nt h i sd o m a i n ；t h em a i na i mo fs o c i a ln a v i g a t i o ni st oh e l pp e o p l et o t a k ed e c i s i o n su s i n gd i r e c t l yo ri n d i r e c t l yi n f o r m a t i o nf r o mo t h e rp e o p l e s o ， i n t e g r a t i n gs o c i a ln a v i g a t i o nw i t hs e a r c he n g i n e si s a ne f f i c i e n tw a yt op r o v i d e a s s i s t a n c e ss u p p o r t i n gm a k i n gp r o g r e s sa f t e rs e a r c he n g i n e sr e t u r nl o t so fr e s u l t s 。 c o n c e p tl a t t i c ei sa ni m p o r t a n tt o o lf o rr u l e sa c q u i r i n ga n dk n o w l e d g ee x p r e s s i n g b u tt h ef o r m a lc o n t e x to fi tb a s e di su s u a l l yab i n a r yc o n t e x t h o w e v e r i nf a c t ，m o s t o ff o r m a lc o n t e x ta r ei n d e f i n i t ea n df u z z ys of u z z yc o n c e p tl a t t i c e ( f c l ) i sa n e f f e c t i v et o o lf o rd a t aa n a l y z i n ga n dk n o w l e d g ed i s c o v e r i n g t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r el i s t e db e l o w ： 1 an e wm o d e lo fs o c i a ln a v i g a t i o nb a s e do nf u z z yc o n c e p tl a t t i c ei sp u t f o r w a r d a sw ek n o w , t h ea i mo fn a v i g a t i o nt h eu s e rn e e d e da n dt h es o c i a l e x p e r i e n c ea r et h et w ok e yf a c t o r sf o rs o c i a ln a v i g a t i o n i no u rs o c i a ln a v i g a t i o n m o d e l ，t h ea i mc a nb ea t t a i n e db yt h eq u e r yw o r d sw h i c hi si n p u t t e db yt h eu s e r s t h e m s e l v e sv o l u n t a r i l yi nt h ep r o c e s so ft h ep l u g - i ni n t e r f a c en a v f c ad e v i s e db y 第1 i i 页 西华大学硕士学位论文 o u r s e l v e si n t e r a c t i n gw i t hu s e r s ；t h es o c i a le x p e r i e n c ec a nb ea t t a i n e db yt h ef u z z y f o r m a lc o n t e x tc o n s t r u c t e db yt h er e l a t e di n f o r m a t i o ne x t r a c t e df r o ml o gf i l e s t h r o u g hp r o c e s s i n gt h i ss o c i a le x p e r i e n c ei n t of u z z yc o n c e p tl a t t i c et h ee f f e c t i v e k n o w l e d g es t r u c t u r e ，t h eu r l sa n dt h e i ra b s t r a c t so ft h en a v i g a t e dw e bp a g e sc a nb e s h o w e dt ou s e r sb yn a v f c a b e s i d e st h i s ，a l g o r i t h m sa n dr e l a t i v et e c h n o l o g i e so f s o c i a ln a v i g a t i o nb a s e do nf u z z yc o n c e p tl a t t i c ea r ep r o p o s e ds u c ha sa c q u i r i n gu s e r t r a i l s ，g e n e r a t i n gf u z z yf o r m a lc o n c e p t s ，s o c i a ln a v i g a t i n go nf c l e t c 2 af a s ta n da u t o m a t i ca l g o r i t h mf o rf c lb u i l d i n gi sp r o p o s e d ，c a l l e df c l b a l g o r i t h m ，f o rg e n e r a t i n gf u z z yc o n c e p t sf r o mag i v e nf u z z yf o r m a lc o n t e x ta n da s e t o ff u z z ys e t s ，a u t o m a t i c a l l yb u i l d i n gaf u z z yc o n c e p tl a t t i c ea n dr e p r e s e n t i n gi t 伊a p l u c a l l y 3 t h es o c i a ln a v i g a t i o ns y s t e mb a s e do nf u z z yc o n c e p tl a t t i c ei sd e s i g n e da n d i m p l e m e n t e d e x p e r i m e n t si n d i c a t et h a t i tc a t lp r o c e s ss u r f i n gt r a i l si n t ou s e f u l k n o w l e d g es t r u c t u r e sw h i c hc a i lb el a t e ru s e di ni n t e l l i g e n ts e a r c h i n g k e y w o r d s ：s o c i a ln a v i g a t i o n ，f u z z yc o n c e p tl a t t i c e ，f u z z yf o r m a lc o n t e x t ， f o r m a lc o n c e p ta n a l y s i s 第页 西华大学硕士学位论文 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 作者签名：弓射乔兰 聊躲纺 坼上月2 , 0 日 未衙5 - 月加日 第5 8 页 西华大学硕士学位论文 1 绪论 社会导航本是一种普遍的社会现象，9 0 年代中期陆续有学者开始将其应用 到信息空间的导航中。信息空间是指信息被存储、检索和可能被转化的空f f l t l l ， 其可以是物理的也可是虚拟的。物理的空间包括我们所居住的现实世界，而虚 拟的空间则是当今海量的信息世界。i n t e m e t 在给我们带来海量信息的同时，也 给我们寻找有用信息带来了令人望而生畏的困难。所以，在这个漫无边际的信 息空间中需要信息导航。信息导航是一种在信息空间中进行“定位 的活动， 其分为空间导航、语义导航和社会导航【2 1 。其中，空间导航是依靠空间自身结 构向用户导航；语义导航依靠空间的语义结构进行导航：而社会导航则是依靠 用户之间的交互影响和作用的基础上的。 用户可能在信息空间中迷失，也可能在一个未曾涉足的环境中不知所措， 而社会导航的主要目标是直接地或间接地利用他人的信息来帮助人们做出决 策。例如，到图书馆借阅受读者欢迎的书籍，到商场购买大众喜爱的商品等， 这些行为不仅受内在目标和认知过程的驱使，同时受到社会、其他用户行为的 影响。人们可通过社会导航来使经验知识共享、传承与传播。随着i n t e m e t 的迅 猛发展，通过搜索引擎找到精确表达出用户兴趣的信息越来越困难，因而将社 会导航这种现实世界中的行为引入到搜索引擎返回的大量结果中，可帮助人们 更有效地获取信息。 1 1 研究动态 1 1 1 社会导航 社会导航是一个较新的术语，最早关于社会导航的定义可能由d o u r i s h 2 】 提出，其认为社会导航是面向其他人群，选择他们已经确定的对象。e f i c k s o n 3 】 认为，w w w 中的结点可以表示用户，并且当用户从一个结点导航到另一个结 第1 页 西华大学硕士学位论文 点上时，可被认作是一种社会导航。d i e b e r g e r 4 】认为社会导航是基于用户间相 互交流和作用的i n t e r n e t 上的导航行为。而m a r t i ns v e n s s o n 5 】则认为，社会导航 是直接或间接的与其他人交互。他又将社会导航分为间接社会导航与直接社会 导航【6 】，并指出按用户踪迹进行的社会导航是间接社会导航。文献 7 认为可将 暗示性文化作为社会导航工具，暗示性文化是一种新方法，这种方法鼓励或诱 导人们按照群体惯例行为来做，利用暗示性文化可帮助新用户获得其它用户行 为信息。因此，在本文中我们定义社会导航是一种行为方式，其不仅受内在目 标和认知过程的驱使，同时受到社会、其他用户行为的影响。 尽管社会导航没有统一的概念，但自1 9 9 7 年d i e b e r g e r 提出在w w w 上进行 社会导航以来，社会导航思想被广泛应用于信息空间设计及信息空间设计应用 系统中。常见的社会导航系统形式有：推荐系统、居住空间系统、h i s t o r y - e n r i c h e d 系统三种【8 】。 i 推荐系统( r e c o m m e n d a t i o ns y s t e m s ) 推荐系统旨在通过调查其它具有相似兴趣的人们的行为来帮助人们做出决 策。例如，在亚马逊网站中，“购买这本书的顾客也购买了”便是最明显的例 子p j 。推荐系统主要包括基于内容的过滤推荐与协同过滤推荐两种。其中，基 于内容的过滤推荐需要分析资源内容信息并根据用户兴趣建立用户个人特征框 架，然后根据资源与用户特征之间的相似性向用户提供推荐。但这种推荐对音 乐、图像、视频等多媒体信息具有一定局限性。协同过滤推荐技术又称为社会 过滤，其主要运用其他用户的评价来向某一用户进行推荐。获得评价的方法可 以是隐式也可以是显示的。其中，显示获得用户评价的方法要求用户给所浏览 的信息进行评价，如打分。例如，作为s t a n f o r d 大学数字图书馆项目的一部分的 f a b 系统是一个基于内容的过滤和协同过滤结合的混合推荐系统【l0 1 。其设计思想 是，从用户已经评价的文档中抽取一定特征组成用户概况表( u s e rp r o f i l e ) ，一个 用户具有一个用户概况表，使用t f i d f 向量表示。同样地，也使用t f i d f 向量来 描述文档，计算用户概况信息与文档间的相似度，并把与用户概况表内容相似 程度高的文档向用户推荐。再如m i l l l l e s o t a 大学的j k o n s t a n 和他的同事共同研 发的g r o u p l e n s 系统，其是一个向用户推荐新闻消息的社会导航系统【l 。这个系 第2 页 西华大学硕士学位论文 统首先对读者个人资料进行详细分组，系统中的网络新闻阅读器可使读者按照 个人喜好对新闻进行评价，然后该系统根据读者群的相关性对文章进行分类、 分级排列。这种排列帮助后来读者在众多的文章群中找到自己感兴趣的部分。 从g r o u p l e n s 系统中可以看出，运用社会导航系统同其他一般的评价系统比较起 来，能够显示出较深入的预示性优势。而隐式的评价方法则根据用户在i n t e r n e t 上浏览网页的行为来得到用户评价，如监视用户浏览网页时间、对网页的访问 频率、用户是否采用保存操作等。在协同过滤中使用暗示性文化得其更适 合做社会导航的工具，暗示性文化【眩】思想被成功应用到推荐系统中，用于w e b 搜索和帮助用户查找其相关的感兴趣的主题等。例如，s i c s ( s y s t e mf o ri m p l i c i t c u l t u r es u p p o r t ) 系统通过将用户行为信息存入数据库，然后分析存储资料并应 用到数据挖掘技术中以发现在某种环境中哪种行为是最普遍的，最后使用观察 器搜集当前用户信息以建议该用户在给定环境中应采取的行为。 2 居住空间系统( p o p u l a t e ds p a c e s ) 一些社会导航工具使用居住空间思想，即在此居住空间中可碰到其它人们。 也就是用户接收的推荐并不是来自系统，而是来自群体中其它具有相似兴趣的 成员发出的信息。居住空间系统就是使用该思想来建立用于w e b 搜索的推荐系 统。例如e f o l ( e u r o p e a nf o o do n l i n e ) t 1 3 1 系统，该系统是由k r i s l 及其同事共同 开发的网上食品商店。其通过经过厨师选择的菜谱和一些必要的成分组成了顾 客的购物图表，以及一个顾客可以与其他顾客交流的居住空间( p o p u l a t e d s p a c e ) ，充分展示了其社会导航思想。e f o l 还利用了社会导航器丰富了社会导 航的功能。首先，菜谱本身就是由推荐系统( 协同过滤) 产生的；其次，除了单 个菜谱外，它们还被聚合为一个菜谱社区，如蔬菜类食品等。顾客可以在这些 社区间切换并获取评论性的信息。 3 h i s t o r ye n r i c h e d 系统 这种类型的系统使用的是以前活动的信息( 交互历史) 来指导用户。交互 历史不是改变行为的对象本身而且影响是我们的观念，是过去行为怎样改变当 前对象的观念。例如：石头阶梯磨损程度表明了此地交通状况，而古老的铜却 第3 页 西华大学硕士学位论文 可以代表人类辛酸的历史。我们利用这些踪迹来指导我们的行为，来暗示可能 性、并感知当前的资源。如f o o t p r i n t s 系统 1 4 】，它是在一个2 d 的空间中绘制用户 的浏览历史并面向所有的用户提供网站图的系统。h i s t o r ye n r i c h e d 系统是近年 研究热点之一。自1 9 9 9 年，w e x e l b l a t 1 5 】等提出可以使用追踪用户踪迹和交互历 史来进行信息导航的社会导航系统后，社会导航系统被得到了广泛应用 1 3 , 1 5 - 1 9 】。 2 0 0 5 年，b r u s i l o v s k y _ 【2 0 1 等提出在教育数字图书馆中的综合个性化信息访问。2 0 0 6 年，m e y e r 提出h i s t o r y - e n r i c h e d 安全文本交换技术【2 。2 0 0 7 年，g h a s s a n b e y d o u n t 2 2 】等提出引进f c a ( f o r m a lc o n c e p ta n a l y s i s ) 来推理用户踪迹以进行社 会导航，并实现社会导航系统k a p u s t 。该社会导航系统是为大学电子教学而 设计，并通过实验验证了使用f c a 算法进行推理用户踪迹以实现社会导航的适 宜性。 本文研究怎样利用用户踪迹，在模糊概念格上使用模糊推理技术来实现具 有暗示性文化的社会导航。 1 1 2 模糊概念格 形式概念分析【2 3 j 由w i l l e 于1 9 8 2 年提出，是规则获取与知识表达的重要工 具。形式概念分析理论中的核心数据结构是概念格模型。f c a 已被成功应用到 诸如软件工程、信息检索、知识发现、知识工程、决策系统、数据挖掘等领域 中 2 4 - 2 6 1 。例如，在软件工程领域，可以从类库的规范说明上构造概念格，从而 对类库结构的可视化以及类库的重构和优化提供支持；在信息检索方面，概念 格可以实现对信息的有机组织；在知识发现领域，可以从关系数据中构造出概 念格，然后在概念格上提取各种类型的知识，如蕴含规则、关联规则与分类规 则等；在知识工程领域，概念格可以用于知识库的重新结构化等。但f c a 所基 于的形式背景大多是二值形式背景，它表示了对象与属性之间精确的关系，而 在实际中，大量的形式背景都是模糊的。形式背景中引入模糊集【2 7 】可反映对象 与属性之间的这种模糊性，模糊概念格由此应运而生。 1 9 9 4 年，b u r u s c o 首次将z a d e h 的模糊集理论应用于概念格，并集合l 模 糊形式背景，提出了一种l 。模糊概念格模型【2 吼，并且指出w i l l e 的形式概念是 第4 页 西华大学硕士学位论文 其一个特例。 自b u r u s c o 提出模糊概念格后，多位学者开始了对模糊概念格理论及其应 用的探索。1 9 9 8 年，b u r u s c o 给出了l 模糊概念格的构造算法( 2 9 】。2 0 0 0 年 b e l o h l a v e k 研究了模糊概念格中的相似性关系，定义了三个不同层次上的相似 性：对象相似性( 属性相似性) 、概念的相似性和概念格的相似性【3 们。此后， b e l o h l a v e k 3 t - 3 4 1 和g e o r g e s c u t 3 5 】等对模糊概念格进行了深入研究，提出y _ - 种模 糊概念格，此三种模糊概念格中的对应的概念分别称作模糊形式概念、模糊属 性概念、模糊对象概念。2 0 0 4 年b e l o h l a v e k t 3 4 】讨论了模糊概念格的层次结构。 2 0 0 5 年张文修等提出了第四种模糊概念格，对应的概念为对偶模糊形式概念 p 6 | ，并证明了此四种模糊概念具有经典意义下一致的相互关系，即同构性。2 0 0 7 年，强字( 37 l 采用阈值可以将偏小的隶属度值置o ，并使用参数e ( 外延中对象 的平均隶属度) 、6 ( 对象的隶属度值) ，构造了属性模糊的模糊概念格并应用 于聚类分析中。但这种模糊概念格仅是对模糊属性进行处理，因此可以看作是 概念格的一种推广形式。 从1 9 9 4 年到2 0 0 8 年，模糊概念格理论研究正经历着日新月异的发展而越 趋成熟，而模糊概念格应用研究也必将如火如荼。 1 1 3 模糊推理 模糊推理是模拟人的日常推理的一种近似推理，它研究如何根据已有的模 糊概念，建立推理规则推测未知概念问题。它是模糊控制技术的理论基础，也 是人工智能中的一个重要研究内容。 多年来，大量的学者从事这方面的研究并取得了丰硕的研究成果。在模糊 推理的理论研究中，最基本的模糊推理形式为f m p ( f u z z ym o d u sp o n e n s ) 。 z a d e h 首先针对f m p 模型提出了著名的c r i 方法，c r i 方法不久后被成功应用 到模糊控制和模糊专家系统中。但是c r i 不具有还原性这一学术界公认的 评判模糊推理好坏的重要指标。此后，许多学者人们进行了大量的研究并提出 了许多新模糊推理方法，如：真值推理法p 扪、证据推理法、基于相似度的类 比推理方法p ”、区间值推理法1 等。1 9 9 9 年王国俊“踟首先指出了c r i 方法的若 第5 页 西华大学硕士学位论文 干缺陷与不足，并基于逻辑语义蕴涵理论提出了模糊推理的全蕴涵三i 算法， 并在蕴涵算子r 。下给出了f m t ( f u z z ym o d u st o l l e n s ) 模型。王国俊提出三i 算法后，又有不少学者对这种推理方法进行了深入研究。文献4 4 借助蕴涵算子 的性质，针对满足一定条件的较一般蕴涵算子，建立了f m p 与f m t 模型的口一 三i 算法，宋士吉、吴澄h 瓢删又提出了模糊推理的反向三i 算法。2 0 0 6 年张文 修等提出了基于模糊概念格的上近似模糊推理与下近似模糊推理汹1 ，同时他指 出，使用从模糊关系等式h 7 1 衍生的模糊关系来代替下近似推理并与所提出的上 近似推理相结合，可使推理更准确。 模糊推理一个重要的应用是语言值模糊推理。早在1 9 9 7 年，z a d e t h 严叼就给 出了语言命题及产生式规则的标准型，并基于模糊集理论及模糊推理方法，研 究了语言值模糊推理。h e r r e r a 提出2 一元组模糊语言模型，并将其应用于模糊推 理和模糊决策等问题中f 4 9 o2 0 0 4 年裴峥跚1 等研究了简单的语言真值格蕴涵代数。 2 0 0 6 年，伊良忠等给出y 基于l u k a i s i e w i c z 代数的语言真值推理方法p ”。2 0 0 7 年，伊良忠啼2 1 给出了常用语气算子并抽象出常用语言的格蕴涵代数结构，并给 出了语言真值推理规则。 模糊形式概念分析与模糊推理奠定了基于模糊概念格的社会导航的理论基 础。 1 2 研究目的与意义 ( 1 ) 网络文本信息获取是非平凡的：网络文本信息量巨大( 海量信息) 且 信息结构和关系复杂( 复杂系统) ，完全超出了人们所能理解的范围。同时，由 于人类的参与使数据和信息中存在大量的模糊性，想在一定时间内从被存储的 信息中搜寻并提供与用户输入的导航词相匹配的文本信息是非平凡的，必需借 助已有的理论和方法，特别是人工智能领域知识表示及获取的研究成果。 ( 2 ) 利用模糊形式概念与模糊推理技术进行社会导航，是实现社会导航的 新途径。 社会导航三种基本形式为：推荐系统、居住空间系统、h i s t o r y e n r i c h e d 系 统。其中h i s t o r y - e n r i c h e d 系统是指用以前的活动信息来指导用户，因此可通过 第6 页 西华大学硕士学位论文 追踪用户踪迹和交互历史来进行社会导航。为推理用户踪迹，形式概念分析 ( f c a ) 被引进社会导航系统中。但f c a 所基于的形式背景大多是二值形式背 景，它表示对象与属性之间精确的关系，而在实际中，大量的形式背景都是模 糊的。利用用户日志，从中抽取相关信息以形成模糊形式背景便是其中一例。 同时模糊推理研究如何根据已有的模糊概念，建立推理规则推测未知概念问题。 本文从构建模糊形式背景出发，提出利用用户踪迹在模糊概念格上进行模糊推 理以实现社会导航的模型。 ( 3 ) 模糊形式概念分析与模糊推理技术为实现社会导航提供了坚实理论基 础和技术支持。本文所建立的社会导航模型及进行的研究工作为模糊形式概念 分析理论提供了良好实验验证。 1 3 论文结构 本文剩下的章节将组织如下： 第二章：介绍了模糊概念格与模糊推理基本理论。 第三章：详细介绍本文提出模糊概念格的构造算法。 第四章：详细介绍基于模糊概念格的社会导航算法，包括怎样追踪用户踪迹， 怎样完成数据清洗并形成社会导航模糊形式背景，怎样从给定模糊形式背景及 模糊集中生成模糊形式概念并构成模糊概念格，以及怎样在模糊概念格上利用 模糊推理技术实现社会导航。 第五章：设计并编程设计了基于模糊概念格的社会导航系统。 第六章：对全文进行总结，并展望下一步研究工作。 第7 页 西华大学硕士学位论文 2 模糊概念格与模糊推理基本理论 2 1 模糊概念格 形式概念分析理论是由德国的w i l l e 教授于1 9 8 2 年首先提出的，其中概念 格模型是形式概念分析理论的核心数据结构。在形式概念分析中，概念由外延 和内涵组成。其中，外延是属于概念的所有对象的集合，内涵是属于概念的所 有对象所共同具有的属性集合。概念格中的层次结构，表现了概念间的泛化与 例化关系，对应的h a s s e 图可以实现概念格的可视化形式概念分析【5 3 1 。 概念格反映了对象与属性之间的精确关系，而在实际中，大量的形式背景 都是模糊的。形式背景中引入模糊集【2 8 1 可反映对象与属性之间的这种模糊性， 模糊逻辑 ”】是在模糊环境下进行推理的优良工具，它的重大意义是它允许使用 介于0 与1 之间的值来刻画命题真值。将模糊逻辑引入该领域，用于处理对象 与属性之间模糊关系【3 钔。 定义2 1 55 】称( g 4 d 为模糊形式背景，若g = 怯，恐，x n ) ，4 = 溉，n ：) ， j 是定义在g 4 上的模糊关系，即j ：g xa - - - ) 0 ，1 】。 定义2 2 1 5 5 称l = ( l ， ，v ，p ，一，0 ，1 ) 为完备剩余格，若满足以下条件： ( 1 ) ， ，v ，0 ，1 ) 是一个具有最小元0 和最大元1 的完备格。 ( 2 ) 犯， ，1 ) 是具有交换律、结合律、单位元的幺半群。 ( 3 ) ( ，一) 是l 的一个剩余对。也就是满足对口，6 ，c l ， a o b i 似力) ( 2 1 0 ) z e “矧 若如= 豆伊= 只称( z 两为由“专”生成的模糊概念。其中曼g q 4 ，庄小_ f q 即贾为g 上的模糊集记为贾f ( g ) ，雪为a 上的模糊集记为雪f ( a ) 。 定义2 5 【5 5 1 称“专”： 0 ，1 】2 一 0 ，1 1 是蕴含算子，若0ja = 1 ( a 0 ，1 1 ) ， 且满足以下性质： ( 1 ) 当a l a 2 时，a 2 一b q b ( 2 ) 当6 1 1 x y石 y 2 0 x j y 1 ( 2 1 5 ) x y 。 ix + y 1 、一1 。7 第9 页 西华大学硕士学位论文 定义2 6 设( g ，a ，7 ) 为模糊形式背景，f ( g ) 、f ( 彳) 分别是g 、a 上的所 有模糊集，对于舅f ( g ) ，b f ( 彳) ，若j 事= 否，伊= 牙，称( 岩，否) 为模糊概念。 定理2 3 【5 5 1 设( g ，4 ，7 ) 为模糊形式背景，记 0 g ( x ) 兰01 g ( x ) 兰l ( x g ) 0 一( a ) 三01 a ( 口) 三1 ( a 彳) 则有如下性质： ( 1 ) 6 ；= i a ，6 ：= k ( 2 ) 对于置，丘f ( g ) ，当置丘时，爱置 ( 2 1 6 ) ( 2 1 7 ) ( 3 ) m g b 一, ，鼋f ( 么) ，当豆互b 2 时，鼋+ 耷 推论2 1 【5 5 】对于两个模糊概念 ，骞) 及暖，豆) ，若置亘记为 ( 暑，骞) ( 置，豆) ( 或等价于展毒) ，记婀4 乃= 两i 弦= 恿伊= 两则 三( ( g ，4 ，j ) ，) 是偏序集。 定理2 4 t 5 5 】设( g ，彳，7 ) 为模糊形式背景，“专”是蕴含算子，三( ( g ，a ，歹) ，) 为 由“一”生成的模糊概念的全体，则( ( g ，a ，j ) ， ) 为完备格。 定义2 7 t 3 1 】定义在集合u 与a 之间的一个l 模糊伽罗瓦连接是一个映射 对( 宰，木) 木：木：一，宰：啼，对每一个墨，丘，x 。产，毒，b 2 ，b 。满足： s ( 置，置) s ( 露置+ )( 2 1 8 ) s ( b 。t ，龟) s ( 瓦豆) ( 2 1 9 ) j 贾”( 2 2 0 ) 雪雪”( 2 2 1 ) 其中：s ( 2 。，贾：) = 会( 墨( z ) 专j ：( 工) ) ，表示了2 , 属92 ：真值程度。 定理2 5 t 3 司若l = ( l ，a ，v ，o ，专，0 ，1 ) 是一个完全剩余格，对一个l 模糊形式 背景( g ，4 7 ) ，戈，雪可定义下列的算子： x 木( 口) = 尘( x ( 工) 争i ( x ，口) )b 木( 工) = ( b ( 口) - i ( x ，口) ) ( 2 2 2 ) x ”( 口) = v f l r ( x ，口) x ( x ) ) b 。( 工) = 八( ，( x ，以) 争b ( 口) )( 2 2 3 ) x 。( 口) = a ( i ( x ，岔) 争x ( x ) )b 。( 石) = v ( j ( x ，口) p8 ( a ) )( 2 2 4 ) 第1 0 页 西华大学硕士学位论文 x 4 ( 口) = ( j 。( x ，口) x 。( x ) )b 4 ( x ) = v ( ，。( x ，口) 0 b 。( 口) ) ( 2 2 5 ) 乞uq t ，l 定义2 8 如1 设( g ，以a 为l 模糊形式背景，对足l ( g ) 百l ( a ) ，若 贾：伊，雪：贾宰，则称( 牙，雪) 是一个模糊形式概念，若j = 伊雪= 牙。则称( j ，雪) 为模糊属性概念，若贾= 伊，秀= 贾口，则称( 贾，西) 称为模糊对象概念，若 贾= 雪4 ，雪= 戈4 则( j ，雪) 称为对偶模糊形式概念。 以上所有的四种概念统称为模糊概念。 2 2 模糊推理 1 模糊推理的基本形式 模糊推理研究如何根据已有的模糊概念，建立推理规则推测未知概念问题， 模糊推理分为模糊向前推理f m p 和模糊拒式推理f m t ，其f m p 基本形式为 已知：x 专b 且给定影， 求 而f m t 的基本形式为： 已知：x 专b 目给定： 丑! 求 碧t ( 2 z 6 ) ( 2 z 7 ) 其中：宕一雪是一条模糊规则，其j 和雪、牙、雪分别是模糊集。 2 还原性定义 1 9 7 3 年z a d e h 提出了第一个模糊推理方法，即著名的c r i 方法，并成功应 用于模糊控制中，但是c r i 算法不满足还原性这学术界公认的评判模糊 推理好坏的重要指标。同时，还原性也是对模糊推理算法的最基本要求。 定义2 9 【5 q 对于单一规则情形下的f m p 问题，若能由贾。= j 推理出雪_ 后 第1 l 页 西华大学硕士学位论文 则称这种算法具有单一规则的f m p 问题的还原性。 对于单一规则情形下的f m t 问题，若能由雪= 雪推理出2 - 贾则称这种算 法具有单一规则的f m t 问题的还原性。 3 常见的模糊推理算法 常见的模糊推理算法有：c r i 法、真值推理法、证据推理法、基于相似度 的类比推理方法、区间值推理法、全蕴涵三i 算法，基于模糊概念格的模糊推 理等。下面将简单介绍c r i 方法，全蕴涵三工方法及本文所涉及的模糊概念格 上的模糊推理方法。 1 ) c r i 方法 c r i 算法是由z a d e h 提出，适用于f m p 问题，c r i 算法不具有还原性。其 算法基本思想是【5 7 】： ( 1 ) 利用蕴涵算子r 把已知条件贾专豆转化为x _ y 上的模糊关系 r ( x ，y ) ，即转化成映射r ：x x y 专 o ，1 ： r ( x ，y ) = r ( x ( z ) ，b ( y ) ) ( 2 2 8 ) ( 2 ) 把给定的碧与模糊关系r 作合成得雪 曰- ( y ) = x or ( x ( x ) ，曰( y ) )( 2 2 9 ) 2 ) 三i 算法 三i 算法的基本思想是：已知2 f ( x ) ，后f ( 】，) 且给定2 f ( x ) ( 或 豆f ( r ) ) ，寻求豆f ( y ) ( 或贾，( x ) ) ，使得贾_ 雪最大程度了支持 x 专b 即对一切x x ，y y ， ( x ( x ) _ 曰( y ) ) 一( x ( 石) 一b ( y ) )( 2 3 0 ) 具有最大的可能值。 由三i 原则解叫做该问题的关于蕴涵算子r 的三i 解。常见的蕴涵算子r 有： r ：( 口，b ) = a v ( a 人6 ) ( 2 3 1 ) ( 口，b ) = ( 口+ 易) 1 ( 2 3 2 ) 第1 2 页 西华大学硕士学位论文 r c 4 ，6 ，= ：，v 6 兰三： ( 2 3 3 ) 其中口= 1 一a 。 口三i 原则f m p ：设x ，】，是非空集，4 ，a 。f ( x ) ，b f ( y ) 则f m p 中的丑+ 是f ( y ) 中对于任意工x ，y y ， ( y ( 力- - + b ( y ) ) - - + ( x ( x ) 一b ( y ) ) 口( 2 3 4 ) 总成立的最小模糊集。 口三i 原则f m t ：设x ，y 是非空集，a ，( x ) ，艿，b f ( y ) 则f m p 中的a 是f ( x ) 中对于任意1 c x ，y y ， ( x ( 工) 争b ( y ) ) - - + ( x ( 工) 专b ( y ) ) 口( 2 3 5 ) 总成立的最大模糊集。 特别的当口= 1 时称为模糊推理的三i 算法。 3 ) 基于模糊概念格的模糊推理 定义2 1 0 e 3 q 设l = ( 厶 ，v ，o ，_ ，0 ，1 ) 为完备剩余格，( 贾，毒) o = 1 ，聆) 是由 在l 为完备对合条件下得到的模糊形式概念和对偶模糊形式概念，给定露，定 义台的模糊推理规则为： _ 冉 一 一 一 b ( 口) = v ( b i ( a ) ps ( x ，置) ) ( 2 3 6 ) 给定否，定义求贾的模糊推理规则为： _ 一 - 一 - x ( x ) = y ( 五( 口) 0 s ( b ，忍) ) ( 2 3 7 ) 若( 置，毒) ( f _ 1 ，珂) 是模糊属性概念或模糊对象概念，给定牙，定义雪的模糊 推理规则为： 一 一 _ 一一 男( 口) = y ( 点( 口) 0 j ( 五，x ) )( 2 3 8 ) 给定雪，定义求牙t 的模糊推理规则为： 一 n _ 一 x ( x ) = y ( z ( 口) s ( b i ，b ) )( 2 3 9 ) 其中s ( l ，丘) 表示置属于忌的真值，且s ( 置，忌) = 人 ( 冠( x ) 。置o ) ) 第1 3 页 西华大学硕士学位论文 3 模糊概念格构建算法 由于大量信息存在着客观性或模糊性，模糊概念格作为在模糊形式背景下 进行数据分析与知识发现的一种有效的工具而提出，有些算法被提出用于产 生模糊概念。然而数据挖掘需要建立在模糊概念格上，本文提出了一种新的模 糊概念格构造算法称为f c l b 。该算法从给定的模糊形式背景与模糊集集合中 生成模糊形式概念，自动建立并图形化显示模糊概念格。最后本算法被应用到 用于旨在帮助人们有效发现信息的社会导航系统中。 3 1 模糊概念格构造算法 模糊概念格的构建要实现从给定的模糊形式背景( g ，4 ，) 和有限模糊集 三= j ( x ) ix g ) 中生成模糊概念格，并图形化显示的过程。在此过程中需解 决的问题主要有4 个：( 1 ) 产生所有模糊概念；( 2 ) 去除冗余模糊概念：( 3 ) 寻找所有偏序集；( 4 ) 确定模糊概念在