（管理科学与工程专业论文）基于语义关联的语义覆盖网构建方法研究.pdf

国防科学技术大学研究生院硕十学位论文 摘要 在大规模p 2 p 网络中节点数量庞大，节点上的信息呈现出海量、分布、动态、 异构的新特征，要建立集中的索引进行检索工作量太大，不容易实现，所以面对 这些缺乏组织与管理的网络节点，检索时往往采取洪泛的方法，效率很低，而且 有时检索已经达到指定跳数，检索停止了却还没有搜索到有用的信息。当前网络 中的检索都是基于关键字而进行的，常常搜索到大量关键字相同但无用的信息， 那些真正有用的信息又由于关键字不匹配而无法得到。可见用户需要的不只局限 于匹配关键字的那些信息，只依靠关键字进行检索远远不能满足用户的需求。所 以需要将节点按照所包含信息的语义关联进行有效的组织，建立基于语义关联的 语义覆盖网，使检索能够以需求为中心高效的搜索出大量语义关联的信息，为用 户提供信息资源关联聚焦服务。 本文以p 2 p 对等网络为研究背景，对实现信息资源关联聚焦服务的主要贡献 如下： 1 将节点按照存储资源的类型聚类。针对节点上存储资源类型的多样性，提 出先构建主题树将节点上的资源分类，基于资源的类别计算节点相似度，并进行 节点聚类。 2 将主题分解为多个属性，建立主题属性矩阵；利用关系数据库中实体之间 的关联，量化实体的主键属性之间的关联值，主键属性对应主题的属性，建立属 性矩阵来表示属性之间的语义关联。提出了根据某两个主题包含的属性之间的语 义关联值来计算主题之间语义关联值的算法，然后在有语义关联的聚类之间添加 关联链接。 3 基于聚类访问的偏好记录一个语义路由表，在经常访问的聚类之间添加朋 友聚类快捷链接。 经过上述步骤建立起一个基于语义关联的语义覆盖网，实验证明在这个语义 覆盖网的基础上进行资源检索可以大大提高检索效率，它还支持基于语义关联的 聚焦服务。为实现大规模、分布式p 2 p 网络环境下的信息高效共享提供了一个有 效途径。 主题词：对等网语义相似节点聚类关联关系朋友聚类语义覆盖网 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t i nt h ep 2 pn e t w o r k st h ea m o u n to fn o d e si sv e r yl a r g ea n dt h ei n f o r m a t i o no nt h e n o d e sm a k e st h en e wf e a t u r e so fl a r g e q u a n t i t i e s ，d i s t r i b u t i o n , d y n a m i c a n d h e t e r o g e n e o u s n e s s i ti sh e a v ya n du n p r a c t i c a lt ob u i l dac e n t r a l i z e di n d e xt os e a r c h i n f o r m a t i o ni nt h i sc o n d i t i o n n m s ，f a c i n gt h e s en o d e sf o rl a c ko fo r g a n i z i n ga n d m a n a g e m e n tw ea l w a y su s et h em e t h o do ff l o o d i n gt os e a r c h ，w h i c hi si nl o we f f i c i e n c y a n dc a nn o tg e ts o m eu s e f u li n f o r m a t i o nb e c a u s eo ft h el i m i to fh o p s i nt h ec u r r e n t n e t w o r k sm o s to ft h es e a r c h e sa r eb a s e do nk e y w o r d s ，s ot h es e a r c h e r sa l w a y sg e tal o t o fu s e l e s si n f o r m a t i o na n dc a n n o tf i n dt h er e a l l yu s e f u li n f o r m a t i o na sar e s u l to fn o m a t c h e dk e y w o r d s ；s o m e t i m e su s e r sn o to n l yn e e dt h ei n f o r m a t i o nm a t c h e dt h ek e y w o r d s ，w h i c hc a nn o tm e e tt h er e q u i r e m e n to fu s e r sa ta 1 1 1 1 1 e r e f o r e ，w en e e dt o o r g a n i z et h en o d e sa c c o r d i n gt ot h es e m a n t i ca s s o c i a t i o no fi n f o r m a t i o nc o n t a i n e di nt h e n o d e s ，b u i l dt h es e m a n t i co v e r l a yn e t w o r kb a s e do ns e m a n t i ca s s o c i a t i o n ，g e ta1 0 to f a s s o c i a t e di n f o r m a t i o nw i t ht h en e e d o r i e n t e ds e a r c h i n ga n dp r o v i d et h es e r v i c eo f f o c u s i n gi n f o r m a t i o nr e s o u r c ef o r t h eu s e r s i nt h eb a c k g r o u n do fp 2 pn e t w o r k , t h i sp a p e ra i m i n ga ta c h i e v i n gt h ei n f o r m a t i o n r e s o u r c ef o c u s i n gs e r v i c em a k e st h em a i nc o n t r i b u t i o n sa sf o l l o w s ： 1 o r g a n i z et h en o d e st oac l u s t e ra c c o r d i n gt ot h et y p eo fs t o r i n gr e s o u r c e i i l i n g a tt h ed i v e r s i t yo fi n f o r m a t i o ns t o r e di nan o d e ，w ep r o p o s et oc l a s s i f yt h ei n f o r m a t i o n o nan o d eb yt h et o p i ct r e ea n dc l u s t e rt h en o d e sb a s e do nt h es i m i l a r i t yo fn o d e st h a tw e h a v ec o m p u t e db yt h es o r to fi n f o r m a t i o n 2 w ed i v i d eo n et o p i ci n t os e v e r a lp r o p e r t i e s ，a n db u i l dat o p i c sa n dp r o p e r t i e s m a t r i x m a k i n gu s eo ft h ea s s o c i a t i o nb e t w e e ne n t i t i e si nr e l a t i o nd a t a b a s e ，w eg e tt h e a s s o c i a t e dv a l u eb e t w e e nk e yp r o p e r t i e sa n db u i l dp r o p e r t i e sm a t r i x w ep r o p o s et h e a l g o r i t h mt oc o m p u t et h es e m a n t i ca s s o c i a t e dv a l u eb e t w e e nt o p i c sa c c o r d i n gt ot h e p r o p e r t i e sm a t r i x ，a n dt h e na d dal i n kb e t w e e nt h ec l u s t e r so fs e m a n t i ca s s o c i a t i o n 3 w er e c o r das e m a n t i cr o u t i n gt a b l eb a s e do nt h ea c c e s sf r e q u e n c yo fac l u s t e r ， a n da d daf r i e n dc l u s t e rl i n kb e t w e e nt h ec l u s t e r sw h i c hc a l lb ea c c e s s e df r e q u e n t l y a c c o r d i n gt h es e m a n t i cr o u t i n gt a b l e b yt h ea b o v es t e p sw ec a ne s t a b l i s has e m a n t i co v e r l a yn e t w o r k sb a s e do n s e m a n t i ca s s o c i a t i o n o u re x p e r i m e n t sp r o v et h a ta l lo ft h es e a r c hp r o c e s si m p l e m e n to n t h i sk i n do fn e t w o r kc a ni m p r o v ee f f i c i e n c y ；m o r e o v e r ，i ta l s os u p p o r t s f o c u s i n g s e r v i c e sb a s e do ns e m a n t i ca s s o c i a t i o n t m sk i n do fn e t w o r kp r o v i d e sa ne f f e c t i v ew a y f o ri n f o r m a t i o ns h a r i n gi nl a r g e s c a l e ，d i s t r i b u t e dp 2 pn e t w o r k s k e yw o r d s ：p e e r - t o p e e rn e t w o r k , s e m a n t i cs i m i l a r i t y ，n o d ec l u s t e r i n g ， a s s o c i a t i o nr e l a t i o n s h i p ，f r i e n dc l u s t e r i n g ，s e m a n t i co v e r l a yn e t w o r k s 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表4 1 主题属性矩阵4 6 表4 2 属性矩阵4 6 表4 3 主题之间绝对相关度矩阵4 7 表4 4 主题之间标准化相关度矩阵4 8 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1v i r d 的三层结构：主干网，域和叶子5 图1 2 网格资源发现模型。6 图2 1p 2 p 模式与c s 模式。1 1 图2 2p 2 p 应用分类13 图2 3 混合式的p 2 p 系统。1 4 图2 4 非结构化的p 2 p 系统1 5 图2 5 结构化的p 2 p 系统1 6 图3 1 基于o m d 模型的描述组成2 4 图3 2 含有关联关系的语义覆盖网3 5 图3 3 发现朋友聚类后朋友列表的变化3 7 图3 4 添加了朋友链接的语义覆盖网3 7 图4 1 主题树4 3 图4 2 聚类时间随资源数目增长曲线4 4 图4 3 聚类时间随节点数目增长曲线4 5 图4 4 三种网络结构查询效率对比5 0 图4 5 三种网络结构查全率对比5 1 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 基王适幺羞送的适塞覆董圈抱建友洼堡窥 学位论文作者始址喘 夕哆年 ，月f日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 垄函函 作者指导教师签名：勺| j i h 日期：矽歹年，月r 日 嗍呷铀 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 研究背景 随着网络技术的飞速发展和信息时代的到来，社会结构框架重心开始从物理 空间向信息空间转移，信息技术的发展随着人们需求的增长日新月异，人们关注 的重点越来越投向信息空洲1 1 。 在广域网络环境下的信息资源具有动态性、分布性、多元性和无序性的特点， 信息共享机制尚未建立，各部门或组织之间的信息相对封闭，形成了一个个孤立 的“信息孤岛 ，造成了巨大的信息资源浪费。当前为了实现信息共享，网络节 点逐渐的都接入了网络，但是随着网络节点数量和节点上存储的信息量的急速增 大，信息的管理和检索面临极大的挑战，用户往往花费了大量的时间却得不到自 己真正想要的信息。 1 1 1 信息资源的组织与共享 要实现信息共享，使信息真正发挥它的优势为用户提供最高效的服务就要对 信息进行组织。无序的、杂乱无章的信息虽然数量大，但实际上却没有多大作用， 也就是说失去控制的、无组织的信息不再是一种资源，我们面临着“信息匮乏” 与“信息泛滥”的双重矛盾，解决这个矛盾的根本途径是在信息组织的基础上提 供面向用户需求的信息服务。 信息组织【2 】是利用一定规则、方法和技术对信息的外部特征和内容特征进行揭 示和描述，并按给定的参数和序列公式排列，使信息从无序集合转变为有序集合， 将信息转为信息资源或将潜在的信息资源转为显在信息资源的过程。从广义上说 这一过程包括信息选择、信息描述与揭示、信息加工、信息序化和信息存储。信 息组织是信息资源服务和信息资源开发、管理与利用的准备，是信息资源采集后 的首项工作，是对采集来的原始信息进行筛选和判别、分类和排序、计算和研究、 著录和标引、编目和组织而使之成为二次信息的活动p j 。 信息服务【3 】是联系用户与信息源之间的“桥梁 ，其目的是向用户提供他们所 需的各类信息资源。信息服务实际上依据特定用户在特定时间各条件下的信息需 求，运用一定技术、方法和工具，在信息组织的基础上从各种各样的信息资源中 形成用户所需信息资源集合的过程。信息服务是一种将信息作为“服务内容 提 供给用户的信息应用方式，将信息从封闭、分布和难以访问的环境中“解救”出 来，并将其转变成能实现特定业务功能的服务，使用户能以最便利的方式利用信 息。 第1 页 国防科学技术大学研究生院硕士学位论文 本文就是要通过合理方法，在广域、分布的条件下对信息进行组织，进而提 供高效的信息服务。特别是要针对用户的需求提供有针对性的、全面的信息服务。 1 1 2p 2 p 网络现状 随着信息量的增大，现今的网络结构开始向p 2 p 的组织方式发展。它提供了 一个开放、对等的资源贡献环境，在这种结构中，节点之间没有客户机服务器的 区别，节点都是对等的地位，信息资源的交换是采用点对点的形式，一个信息需 求直接找到相应可以提供信息的节点上，并将所需结果返回。 这种信息的组织方式不需要中央服务器进行集中的控制，不会因为服务器的 故障导致整个网络运行瘫痪，有效的解决了单点失效的问题。但是在这种分布、 自治的环境下，节点之间缺乏互相的了解，又没有一个集中的控制，信息检索和 处理都面临极大的困难。特别是在无结构的p 2 p 网络中，每当提出一个资源请求 都要进行洪泛的查询，不仅大大增加了查询时间，而且查全率和准确率都不能保 证。建立集中的索引来使查询直接指向适当的节点是一个解决办法，但是它只适 合应用在小型网络中，若是节点数量很大，首先建立集中的索引是不现实的；其 次就又要面临传统网络中的瓶颈和单点失效问题。所以现实迫切需要对p 2 p 网络 的结构进行组织，提高网络运行效率，为用户提供最优质的服务。 当前在网络中进行信息检索大多都是基于关键字进行的，这种简单的匹配已 经越来越不能满足用户的需求了，基于关键字的简单检索已经无法满足用户的需 求，因此语义网的概念应运而生，并已经越来越得到大家的认可。语义网在网络 的中加入语义信息，使搜索过程不是完全凭着关键字进行，在理解用户需求的基 础上可以将那些虽然不包含搜索的关键字但是实际上表示的是同一种内容的信息 都返回给用户。建立语义网的目的是实现异构数据的共享，提高网络的查全率， 但是对于提高网络运行效率的贡献不大，它没有从根本上解决p 2 p 网络洪泛查询 方法的弊端；语义网中所谓的语义也只是停留在统一异构信息的层面上，解决的 是同类资源的汇聚问题，网络中没有考虑到语义关联的存在。 1 2 问题的提出 基于p 2 p 网络的现状，要提供的高效的信息服务还面临很多问题，什么样的 网络结构才是最优的? 如何进行节点的组织才可以为用户提供最大的方便? 用户 需要的是什么样的信息服务? 用户真正需要的那些有语义关联的信息如何才能获 取到呢? 1 - 2 - 1 信息共享的现状与面临的难题 第2 页 国防科学技术大学研究生院硕士学位论文 虽然p 2 p 系统相对旧的网络系统有很多优点，它采用非集中控制的机制，避 免出现系统瓶颈及单点失效问题，它分布在广域空间中具有良好的自治性、负载 均衡性、自组织性和容错性。但正是由于它分布、自治，节点之间缺乏互联互通， 使得节点上的信息面临共享难题，不能快速的定位到所需的信息资源上，这就带 来了大规模、非集中网络环境下信息服务效率低的问题。而且在p 2 p 系统中节点 之间的相关性千差万别，如果不进行有效的组织与管理，信息共享的程度很低。 针对一个特定信息需求如何有效地选择节点提供服务是进行高效服务的关键，也 是现有p 2 p 系统进行深度信息共享所面临的首要挑斟4 ，5 】。 为了解决p 2 p 网络中的信息共享问题，当前做了很多研究，也有很多针对p 2 p 共享的网络结构。语义覆盖网的概念应运而生，建立语义覆盖网的根本目的是对 网络节点进行有效的组织，将包含同类信息的节点组织成聚类，在进行资源检索 的时候只要找到一个聚类就可以进行聚类内的检索，提高了资源检索的效率。 但当前建立的语义覆盖网都只是为了解决p 2 p 检索效率低下的问题，网络构 建的基础是资源的类别。有的算法随机的将相邻的几个节点组织成一个聚类：有 的算法统计节点内资源的数量，单纯的以最多的资源作为该节点的代表资源，将 含有同一类型的代表资源的节点组织成聚类，没有认识到节点上资源的多样性， 忽略了其它资源的存在。这些研究虽然在一定程度上避免了洪泛效率很低的问题， 可是查全率不高，而且不包含语义信息，检索过程大多都是基于资源的关键字展 开的，无法理解用户意图，更无法针对用户的需求将所有相关的信息都检索出来， 实现信息共享只是停留在最底层。 现实生活中，用户对信息的需求往往不是单一的，而是全面的，针对一个问 题会逐层追溯下去，或向四周扩展开来，需要了解大量相关的信息。有时在搜索 一个关键字的时候用户真正关心的并不是这个关键字本身的含义，而是与此关键 字相关的信息。在普通的网络中，如果一个指挥员要下达一个救援任务，他首先 要了解当前要救援地域的灾情，是否有可以调动的部队，如何走可以在最短的时 间内到达，其中的每一步都要进行至少一次的信息的检索，大量的时间都 浪费在了检索过程和信息筛选上，工作效率很低。于是我们想到，是否可以实现 每当指挥员下达一个任务的时候，网络可以按照语义信息一次性的将所有需要的 信息都检索出来呢? 也就是要实现针对用户用户的需求实现信息资源聚焦服务。 1 2 2 信息资源关联聚焦服务 现实存在的信息之间不仅具有相似的属性可以将同类信息归类管理，同时信息 之间还是有语义关联的，用户在进行资源搜索的时候往往对那些相关的信息也十 分关心。这就需要在构建网络的时候充分考虑实体的语义信息，并根据这些语义 第3 页 国防科学技术大学研究生院硕士学位论文 信息得出实体之间的语义关联关系。而在用户进行检索的时候可以充分利用网络 中的这种语义关联关系进行信息服务。 本文的目标就是使网络在检索的过程中可以处理语义关联信息，检索时可以 针对一个点展开资源的搜集，充分理解用户意图，迅速得到所有与这一点有语义 关联的信息，而不必一次一次的输入关键字进行多次查询，也就是实现信息资源 聚焦服务，这是当前任何一种网络结构都无法实现的。 针对上边的描述，给出信息资源聚焦服务的定义： 定义1 3 ( 信息资源聚焦服务) 【6 】：信息资源聚焦服务是以用户关注信息点为 焦点，以信息资源语义关系为信息导出关系形成信息资源聚焦集合，并以信息资 源聚焦集合为服务内容提供给出信息用户的有效信息应用方式。 信息资源聚焦服务在各自治信息源基础上形成信息资源统一理解，这是其基 础；在信息资源统一理解的基础上建立统一信息视图，完成信息资源的组织与索 引，这是信息资源聚焦服务的必要条件；然后充分利用信息资源与用户需求的语 义关系，形成以用户关注信息点为核心的信息资源集合，为满足用户需求提供有 效的信息服务。也就是说，信息资源聚焦服务是在信息资源统一理解的基础上， 通过有效的信息组织和索引，以用户信息需求和信息资源自身语义关系为导向， 以用户所关注的信息点为中心，快速汇聚形成一个相互关联的信息资源聚焦集合， 以满足用户的信息需求的过程。 针对信息之间存在的语义关联关系又可以将信息资源聚焦服务迸一步细化出 信息资源语义关联聚焦服务，也就是以用户所关注的信息点为中心，以信息之间 的语义关联为导向进行信息资源的汇聚，使用户可以快速准确的得到所有感兴趣 的相关信息。 那么怎样才可以实现这种语义关联聚焦服务呢? 这就需要合理的组织网络节 点，建立一种基于语义关联的语义覆盖网。 1 2 3 构建基于语义关联的语义覆盖网 通过前边的分析我们发现当前的信息共享存在两个问题：一是针对大规模的 p 2 p 网络没有一个合适的网络结构来进行快速的信息资源检索，检索的效率和查全 率都不高；二是缺乏语义支持，往往只是基于关键字进行检索，而且网络中没有 对语义关联的分析，无法针对用户的需求将可能需要的相关信息都提供出来，也 就是无法提供p 2 p 环境下的信息资源关联聚焦服务。 为了解决这两个问题，本文提出了一种基于语义关联的语义覆盖网( s e m a n t i c o v e r l a yn e t w o r kb a s e do ns e m a n t i ca s s o c i a t i o n ，简称s o ns a ) 构建方法，组织网络 节点，在这种网络中添加了语义信息，可以判断资源之间的语义关联，进而得出 第4 页 国防科学技术大学研究生院硕士学位论文 节点之间的语义关联，实现信息资源关联聚焦服务。 s o ns a 方法可以解决节点上资源多样性的问题，不再把一个聚类简单的看 成只包含一类资源，提高了网络的查全率。除此之外，利用s o ns a 方法建立的 语义覆盖网中包含了丰富的语义信息，可以理解用户的意图，不再是只进行关键 字的匹配，可以自动过滤掉那些无关的信息，减少了用户进行信息筛选的时间， 高效的提供更加准确的信息；在网络构建过程中，我们不只满足于将相似节点组 织起来，而是根据语义关联进行节点的组织，通过计算语义关联度可以将相关的 信息一次性检索出来，实现了语义关联聚焦服务。 网络建成之后，每当有用户提出资源的查询请求，这个请求便可以按照网络 的组织结构快速准确的定位到包含需求信息的节点上，根据资源之间的语义关联 度将所有与资源请求相关的资源都检索出来。所以利用本文提出的s o ns a 方法 构建网络可以针对一个问题向用户快速准确的提供所有语义相关的信息，省去了 用户逐步搜索的麻烦。以一个问题为中心，以用户的需求为导向，将所需信息都 搜索出来展现在用户眼前，实现信息资源聚焦服务。 1 3 研究现状 随着网络的应用，存储了信息的计算机都连接进网络，信息资源的空前增多 使得信息的获取使用变得更加繁琐。信息泡沫的现状使得组织信息资源从而实现 信息共享成为p 2 p 网络研究的重点课题。 针对p 2 p 网络资源共享问题，有人提出在网格的基础上进行资源的组织实现 高效的信息共享。龚奕利【_ 7 】提出了一种网格环境中的资源发现框架v i i m ，v e g a i n f r a s t r u c t u r ef o rr e s o u r c ed i s c o v e r y 。v i r d 采用了三层的体系结构，如图1 1 所示： s e r v i c ep r o v i d e r 用户 图1 1v i r d 的三层结构：主干网，域和叶子 由图可见v i r d 的顶层是由边界网格资源名字服务器( b o r d e rg r i dr e s o u r c e 第5 页 国防科学技术大学研究生院硕十学位论文 n a m es e r v e r ，b g r n s ) 组成的主干网；第二层包括若干个域，每个域都是由多个网 格资源名字服务器( g r i dr e s o u r c en a m e s e r v e r ，g r n s ) 组成的；而第三层是叶子， 包括客户端和资源提供者。其中边界网格资源服务器( b g r n s ) 连接着主干网和一 个或者多个域，在回答资源查询请求时，它们在域间转发请求，帮助查找满足条 件的资源；网格资源名字服务器( g g n s ) 动态地收集注册到它的资源的信息，并将 这些信息传播到域中其他的g r n s ，当g r n s 收到来自客户端的请求时，它会试 着根据它的本地资源信息或者通过b g r n s 束寻找合适的资源，并返回给用户一个 访问使用该资源的句柄，或者返回查找失败；当资源提供者启动时，它把自己注 册到一个g r n s ( 这个g r n s 称为该资源提供者的指定g r n s ( d e s i g n a t e dg r n s ) ) ， 并定期向它报告自己的状态，或者在状态发生改变时再报告，同时，资源提供者 还接收用户请求，并为之服务；客户端向g r n s 发送请求，并接收回答。一台主 机可以同时既是客户端又是资源提供者。 朱凌设计了一种的网格资源发现模型【8 l ，它在不破坏现有网络的链接结构，充 分考虑各种资源组织异构性和动态性特点的前提下，依据资源结点之间的资源属 性相似性通过网格资源结点动态自组织算法对网格系统内资源结点进行重组织。 该模型将网格上的各种资源都视为普通结点( c o m m e n tp e e r ，c p ) ，将具有相似 资源属性的c p 动态组织在一个或多个虚拟组织( v i r t u a lo r g a n i z a t i o n ，v 0 ) 内，形 成资源结点层。每个v o 通过一定的选择算法选出一个超级结点( s u p e fp e e r ) 作为 该v o 对外通信的结点，s p 之间采用p 2 p 方式相连，构成联系结点层。具有相似 资源属性的各个v o 由一个管理结点( m a n a g e rp e e r ，m p ) 来管理，构成一个资源社 区( r e s o u rs o c i e t y ，r s ) 。各m p 之间也采用p 2 p 方式链接，构成管理结点层。如 图1 2 所示，整个模型体系将网格划分为三层自组织覆盖架构。 图1 2 网格资源发现模型 第6 页 国防科学技术大学研究生院硕士学位论文 为了实现在p 2 p 网络中的资源共享，还存在一些基于用户兴趣和节点访问频 率来建立索引实现信息共享的方法。张永华给出了解决i n t e m e t 规模的w e b 搜索 的初步方案 9 1 。在这个方案中，p 2 p 网络中的每个节点都是一个w e bs e r v e r ，所有 这些w e bs e r v e r 组成了一个w e b 搜索联盟。每个节点由索引模块，兴趣学习模块 和p 2 p 路由模块三个模块组成。每个节点解析它的本地页面并创建本地索引，然 后根据索引内容学习自己的兴趣。节点的兴趣代表了创建这个w e bs e r v e r 的用户 的兴趣。利用结构化的p 2 p 路由机制，这个w e bs e r v e r 联盟可以提供索引发布服 务和个性化的内容检索服务。因此，当一个用户的查找请求被提交到这个w e b 查 找联盟中后，这个w e b 查找联盟将会返回一个确定性的查找结果给这个用户，并 且这个查找结果将会是基于这个用户兴趣的一个优化的结果。 上述提到的方法在一定程度上达到了信息共享目的，但他们在语义以及语义 关联方面的研究还不够深入。本文的目标是建立一种基于语义关联的语义覆盖网， 不仅要实现高效的信息共享，还要支持信息资源的语义关联聚焦服务，那么“如 何定义语义关联? 怎样才算是有关联? 是首先要解决的问题。 当前网络中的u r l 定位机制缺乏语义信息，所以很容易使用户迷失在网络的 信息海洋中，找不到自己需要的信息，所以有人提出了智能浏览【1 0 , 1 1 】。智能浏览 就是实现在用户进行浏览的时候可以分析用户的需求，自动帮助搜索用户可能需 要的关键字之外的信息。这个智能浏览的概念和语义关联原理相似，都要在信息 存储中加入语义信息，并可以发现这些信息之间语义的关联。 本文研究的重点是找出信息之间的关联。关联规则是数据挖掘领域最重要的 研究方向之一，用于发现大量数据中项集之间有趣的联系。关联规则的典型例子 就是购物篮分析，主要用于分析数据库中存在的大量数据，找出数据之间的关系， 从而进行快速准确分析，做出正确的判断。 a p r i o r i 算法【l2 j 是一种最有影响的挖掘布尔关联规则频繁项集的算法，它使用 频繁项集性质的先验知识，用一种称作逐层搜索的迭代方法，分为连接和剪切两 步。针对a p r i o r i 算法的固有缺陷，产生了候选挖掘频繁项集的方法_ f p g r o w t h 算法1 1 3 j 。f p g r o w t h 算法采用分而治之的策略，在经过第一遍扫描之后，把数据库 中的频繁项集压缩到一棵频繁模式树( f p t r e e ) ，同时依然保留其中的关联信息， 随后再将f p t r e e 分化成一些条件数据库，每个条件数据关联一个频繁项，然后再 分别对这些条件库进行挖掘。 梁凯强还提出提出利用本体与概念格进行关联规则的挖掘【1 4 1 ，概念格是由二 元关系导出的形式化工具，体现了概念内涵和外延的统一，非常适合于发现数据 中的潜在关系。 传统的关联规则很大程度上需要人力的干预才能获取语义信息，文献 1 5 1 提出 第7 页 国防科学技术大学研究生院硕士学位论文 一种新的关联规则，将其称为概念关联规则，这种规则中暗含了概念之问的关联， 相比传统的关联规则，它可以表达更多的语义信息。它并不是在全局范围内实施， 而是以聚类为基础在一定区域内进行挖掘概念关联规则。 但这些对于关联规则的研究都是针对数据库中的数据，本文研究的关联，不 是传统语义上的关联分析，而是探索信息资源中存在的语义关联；不是通过大量 的数据来分析是否存在关联，而是把重点放在确定什么算是关联，哪些信息之间 可以认为存在关联。 对于关联，有这样的描述：概念a 、b 满足属性p 描述的关系，记为p ( a ， b ) 。对于概念4 ，4 ，如果存在一个属性序列p s = p l ，p 2 9 oo ，以】，有概念 ( 4 ，4 ，4 一。) 满足b ( 4 书4 ) ( 0 f n ) ，则称4 ，4 之间存在一条属性序列，4 为 p s 的起点，4 为p s 的终点，只( 4 _ ，4 ) 为属性序列p s 的一个节点，记为 见( 4 中4 ) p s 。在本体知识库中，如果两个概念之间存在一条或多条属性序列， 称这两个概念存在语义关联【1 6 1 。语义关联描述了概念之间语义关系的紧密程度， 文献【1 7 】讨论了概念之间语义关联强度的计算方法。这种路径关联在许多领域有广 泛的应用前景，文献【1 8 】通过模板形式定义用户关注的对象关联关系，通过实体关 系和模板的相似性分析，解决诸如发现未知恐怖分子的国家安全问题。如何区分 有意义的关联和无意义的关联，是语义关联分析中一个重要的问题。目前进行关 联分析一般分为两步：首先根据相似程度将所有资源分为几个子集；然后分析子 集之间的关联程度。但是这种方法比较片面，因为它考虑这个子集中的所有资源 都是一类的，把它们作为一个整体来分析而忽略了子集内部存在的关联。针对这 种问题，出现了基于层次树的定量关联分析方法【1 9 1 ，文献 2 0 还提出了综合查询上 下文、概念层次位置、概念信息量、出度、入度、用户信任度和关联长度等多种 因素的语义关联计算方法。 通过综合分析，我们发现了当前研究存在的一些缺陷，而且没有将相关研究 成果应用到构建语义覆盖网中，针对这个现状，本文以p 2 p 网络为背景，提出构 建基于语义关联关系的语义覆盖网，重点解决信息资源共享以及语义关联聚焦服 务的问题，达到快速、准确、全面的汇聚信息，提供服务的目的。 1 4 研究内容与思路 本文以非结构化对等信息资源中心网络为背景，分析了当前p 2 p 网络的结构 特点、网络在运行效率以及提供的服务上存在的不足。提出了实现信息资源聚焦 服务的思路，根据用户的需求考虑建立一种基于语义关联关系的语义覆盖网。 研究的基本思路如下： 第8 页 国防科学技术大学研究生院硕士学位论文 1 对于p 2 p 网络的理论研究。 p 2 p 网络是本文研究的背景，所以从p 2 p 网络的特点入手，分析当前p 2 p 网 络的典型结构。针对无结构、半结构化以及结构化的p 2 p 网络在提供服务上存在 的问题展开了探讨。 2 分析了当前构建覆盖网的主要方法。 当前有很多建立语义覆盖网的方法，但是当前的方法只是停留在将包含同一 类信息的节点组织成一个聚类，即如果一个节点上含有某一类信息数量多，则将 该节点划入对应的聚类中。这类方法没有充分考虑节点上资源的多样性，会降低 查全率，而且没有考虑信息资源之间存在的语义关联，查询过程基本上都是基于 关键字进行的，无法提供语义关联查询，不支持信息资源聚焦服务。 3 提出了构建语义覆盖网来组织p 2 p 网络结构。 当前的网络缺乏语义信息，只是支持基于关键字匹配的查询，不能充分理解 用户意图，提供的服务质量不高。本文提出利用本体元数据理论在网络中加入语 义理解属性，更加有利于信息资源共享，并给用户提供了方便。 4 提出根据节点资源的相似进行聚类的节点分类算法。 通常在p 2 p 网络中，节点分布、自治、没有统一的理解与管理，节点之间缺 乏了解，彼此并不知道都存储了哪些资源。本文提出对节点分类然后进行相似节 点聚类的算法解决了这个问题，可以在节点之间缺乏了解的情况下进行，最终实 现将存储了相似信息的节点组织在一起形成聚类。实验与理论分析证明这种算法 是可行的，而且时间复杂度不高。 5 提出了判断主题之间关联的算法。 尽管现在已经有人提出通过构建覆盖网来解决p 2 p 环境下信息资源共享的问 题，但是现有的构建方法都是基于语义相似度来建立的，没有考虑信息资源之间 的语义关联关系。本文最终建立的语义覆盖网是一种基于关联关系的语义覆盖网， 要实现信息资源聚焦服务，可以针对一个信息点，将用户可能需要的所有信息都 汇聚出来提供给用户。要实现这些首先要明确什么是关联，哪些主题之间算是存 在关联关系。本文将主题分解出一些基本属性，提出利用关系数据库中实体之间 的关联，量化出属性之间的关联值，进而计算主题之间的关联值，详细给出了主 题之间关联关系的判断算法。在有关联的聚类之间添加关联链接，形成基于语义 关联的语义覆盖网，并用实验证明算法的可行性和高效性。 6 提出了基于访问频率在聚类之间添加朋友链接，形成朋友聚类。 用户的访问都是有访问偏好的，往往一个用户感兴趣的信息都是有限的，所 以考虑在经常访问的聚类之间添加朋友聚类快捷链接，可以大大加快搜索效率， 快速定位到用户感兴趣的信息。 第9 页 国防科学技术大学研究生院硕士学位论文 1 5 论文组织结构 本文研究的内容是在对等网环境下，如何组织网络节点，最终形成基于语义 关联的语义覆盖网，进而实现信息资源聚焦服务。全文共分五章，具体内容安排 如下： 第一章：绪论，简要介绍了论文研究的背景和意义，提出目前对等网环境下 信息共享无法解决的问题，阐述了相关研究现状，论文所做的主要工作，即文章 的主要内容，以及论文的组织结构。 第二章：介绍了p 2 p 系统的基本特点、具体应用以及拓扑结构，分析了当前 语义覆盖网研究的现状，并对这些构建方法进行了逐一剖析，指出他们存在的问 题，并得出结论：当前语义覆盖网的构建方法只是基于基本的语义相似进行聚类， 没有考虑加入语义关联因素，不支持信息资源的关联聚焦服务。 第三章：重点介绍了如何建立语义覆盖网，其中包含两个关键的算法。利用 本体元数据存在的语义信息进行信息资源的描述，并在其基础上提出了在节点之 间缺乏了解的情况下进行节点分类的算法。关键算法之一是进行节点聚类，首先 建立主题树对信息进行分类，给出了在对资源利用元数据进行统一描述之后衡量 节点之间相似度的算法，得出相似度之后就可以判断出资源归属于主题树上的哪 个主题，然后分析节点包含的资源类型，计算出节点之间的相似度k s i m ，根据k s i m 进行节点聚类；第二个算法是基于语义关联关系在聚类之间添加关联链接，提出 将主题划分为一些基本属性，通过关系数据库实体之间的联系量化得出属性之间 的关联矩阵，通过属性之间的关联度来计算主题之间的关联度。在计算出关联度 之后就可以在聚类之间添加关联链接。为了实现更加高效的服务，考虑到节点一 般都对某一类信息存在偏好，所以网络在运行的过程中记录访问频率，构造语义 路由表，基于访问频率在聚类之间添加朋友聚类快捷链接，从而更加快速的定位 到用户感兴趣的信息。 第四章：因为网络中的节点是随时变化的，有新的节点加入网络，也有节点 离开或因为某些问题突然失效。本章介绍了网络中节点加入以及离开网络时需要 做的一些动态调整。针对具体的抗震救灾这个任务，建立了主题树、主题属性矩 阵以及属性矩阵，并判断出主题之间是否含有关联，进而在聚类之间添加链接， 最终构成语义覆盖网。采用c # 编程将算法具体实现，并模拟语义覆盖网与其它主 流的网络结果的检索过程，实验结果表明文中提出的算法可行且效率很高。 第五章：总结与展望，总结了本文研究工作的成果，并对进一步工作进行了 展望。 第1 0 页 国防科学技术大学研究生院硕士学位论文 第二章语义覆盖网概述 p 2 p 网络，也称为对等网络( p e e r - t o - p e e rn e t w o r k s ) ，既是一种信息资源传递交 换的模式，也是一种网络结构的思想。它是建立语义覆盖网的基础，在这个网络 环境下对节点按照语义相似、语义关联等条件进行组织，达到为用户提供高效的 关联聚焦服务的目的。 2 1p 2 p 系统概述 要建立基于语义关联的语义覆盖网，首先要对构建网络的的基本环境_ p 2 p 网络有一个全面的了解。 2 1 1p 2 p 的基本概念 综合说来，p 2 p 计算是指“采用分散控制的方式，利用大量分布的动态自治资 源来完成特定功能的一种新型网络计算技术”【2 l 】。 随着p 2 p 计算技术的飞速发展和广泛应用，p 2 p 计算模式已成为一种重要的 网络计算模式。与传统的c l i e n t s e r v e r ( c s ) 计算模式相比，p 2 p 计算模式中的节点 一般在逻辑上是对等的，没有客户端和服务器之