基于本体的P2P复杂搜索
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于本体的P2P复杂搜索范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：传统的DHT―P2P系统有一定的局限性，如基于单特征词搜索，计算机不理解用户搜索请求的含义等。对基于本体的p2p复杂搜索进行了研究。应用向量空间模型理论去描述文档，同时对P2P标识符空间进行分割，使相似文档在邻近的节点范围内聚集，不但解决了多特征词复杂搜索的问题，而且提高了搜索的速度。利用本体知识的帮助去理解用户的搜索请求，合理扩大搜索范围，避免搜索结果出现遗漏。实验结果表明，依据该理论构建的仿真系统实现了复杂搜索，搜索速度较快，提高了查全率，且节点达到了较好的负载平衡。
关键词：
对等网；复杂搜索；向量空间模型；本体；负载平衡
中图分类号： TP393文献标识码：A
文章编号：1001-9081(2007)04-0780-04
0 引言
P2P技术由于其固有的优点，如非集中结构、自治性、容错性和良好的可伸缩性等，已经被广泛用于网络环境下的文件共享系统中，成为Internet上有效的资源共享模型。一般来说，P2P系统被分为结构化P2P和无结构化P2P两类。Chord[1]、CAN和Pastry等是典型的结构化P2P。Gnutella[2]、Kazza等是典型的无结构化P2P。在无结构化P2P中，覆盖网络采用松散的方式连接，节点的加入和退出比较简单，覆盖网络的维护成本比较低。但是无结构化P2P的查询多采用泛洪的方式，在系统中产生了大量的消息，网络负担较重。在结构化P2P中，覆盖网络严格按照一定的结构组织在一起，查询请求在节点间转发的过程中有很强的方向性，查询性能较好。当节点加入和退出结构化P2P系统时，需要对覆盖网络的局部结构进行调整，所以覆盖网络有一定的维护成本。
在结构化P2P系统中，基于DHT（Distributed Hash Table）的结构化P2P技术（如Chord）具有很好的可扩展性和良好的性能，一直是人们研究的热点。然而，DHT―P2P系统是基于单特征词搜索的。通常，给定一个搜索特征词，系统首先通过哈希技术将该特征词转换成空间标识，然后通过DHT路由算法进行定位和搜索。
在实际的查询搜索过程中，人们经常会碰到这样的情况：不能准确描述所要搜索的目标，只能从几个侧面对搜索目标的特征进行大致的描述。为了很好地完成上述查询搜索，DHT―P2P系统需要完善和解决两个问题:1）如何支持多特征描述的复杂搜索，而不仅仅是单特征的准确匹配;2）用户从多个侧面对搜索目标进行了描述，如何准确理解这些特征词，避免搜索过程漏掉符合要求的结果。
本文以文档搜索为背景，尝试运用向量空间模型（Vector Space Model，VSM）[3]和本体（Ontology）[4]来解决DHT―P2P系统所遇到的上述两个问题。利用向量空间模型来支持多特征的复杂搜索；利用本体知识的帮助去理解关于搜索目标特征的描述。本文第2节介绍了基于本体的P2P 复杂搜索所涉及到的关键技术及关键问题；第3节介绍了仿真实验，给出了实验结果，并对结果进行了分析；第4节是本文的结论和下一步工作的展望。
1 基于本体的P2P复杂搜索关键技术
1.1 向量空间模型
向量空间模型是信息获取领域经典的统计算法，它将描述文档的多个特征词以向量的形式来表示，向量中的每个分量对应了文档的不同特征。用户进行文档搜索时，将提交的描述文档的多个特征词也用类似的向量表示，通过比较两个向量的相似程度来进行文档的匹配。
TFIDF（Term Frequency Inverse Document Frequency）技术[5]可以很好地解决上述问题。TFIDF考虑特征词在当前文档及整个文档集的频率而计算权重。TF表示在某文档中某特征词出现的数量，DF表示该文档集中拥有该特征词的文档数量，TF值除以DF值就是该特征词对应的TFIDF值。定性的来看，在很多文档中都会出现的特征词的权值肯定没有只在极少数文档中出现的特征词的权值大。文档di的第j个特征词的权重vi,j
定量计算如式(1)所示：
给定任何一个文档向量，根据式(4)就能够得到其相似角。相似角是通过与标准单位向量比较而得到的。对任何两个文档，如果其相似角的值接近，则说明两文档相似。
1.2 相似文档的聚集
利用向量空间模型可以将描述一个文档的多个特征词向量化，按照DHT的原理，下面就可以利用该向量得到该文档对应的空间标识符（Space Identifiers）。由于DHT哈希的随机性，即使是两个很接近的值经过哈希后的数据相差也可能非常大。这样使得分布在各个节点的文档没有相关性，不利于搜索的展开。
如果相似的文档向量经过DHT哈希后得到的值仍然是很接近的，就能够保证相似文档被分配到同一节点或者是邻近的节点上。为此，可以将整个标识符空间进行分割，将式(4)计算出的θ值接近的文档分配在同一个区域。θ值接近也就意味着对应文档的相似度比较高，相似文档聚集可以提高搜索的效率。
1.3 本体的应用
本体（Ontology）[4]的概念来源于哲学领域。本体是概念模型明确的规范说明，概念包括四个方面：概念化、明确、形式化和共享。提出本体概念的目的是通过捕获相关领域的知识，提供对该领域知识的共同理解，确定该领域内共同认可的概念，并从不同层次的形式化模式上给出这些概念和概念间相互关系的明确定义。通俗地说，本体就是对某个特定领域内的知识进行规范定义，涉及的方面有：该领域都有哪些概念（Conceptions）；通过哪些属性（Attributes或者Properties）可以刻画这些概念；这些概念间都有什么样的关系（Relationships）等。现在，不少领域内已经有了普遍认同的本体，例如学术科研领域的SWRC本体（Semantic Web Research Community Ontology）[7]。
SWRC本体专门用于描述科研机构、出版物、科研项目等概念以及它们之间关系。目前主要包括六个顶层概念：Person、Publication、Event、Organization、Topic和Project。SWRC本体的部分结构如图1所示。Publication、Person和Topic是类，Article和Proceedings是Publication的子类，subTopic是Topic的子类。方框中的内容是属性，每个属性有定义域和值域。如属性Author的定义域是Publication，值域是Person；属性isAbout的定义域是Publication，值域是Topic。
通过本体可以了解某一特定领域都有什么概念，概念与概念间有什么样的关系等。比如，通过equivalentClass可以知道两个概念是等价的，比如“计算机”和“电脑”；同样，通过differentFrom可以知道两个看似相同的概念是不同的，比如“doctor”（医生）和“doctor”（博士）。
最初人们是使用RDF（S）来描述和构建本体，由于RDF（S）的表达能力非常有限，目前W3C推荐的本体描述语言是OWL。现在已经有了不少工具可以帮助人们构建本体，如Stanford大学的Protégé[8]等。
可以借助于本体知识很好地理解用户所提交的搜索目标的多个特征词汇，合理扩大搜索的范围，从而有效地提高查全率。扩大的范围主要包含两个方面：一方面是具有相同语义的特征词。如搜索“计算机”的同时也搜索“电脑”；另一方面是具有相似语义的特征词。只要两个特征词的语义相似度达到了事先设定的阈值，就认为二者的语义是相似的。
1.4 文档和搜索过程
（5）这些搜索请求在n跳内进行广播，到达相应的节点后，提取出与搜索目标相似的文档。相似的标准是比较两个文档的相似角θ，如果两者的差值在事先设定的阈值范围之内，则认为两文档相似，该文档为搜索结果之一。
1.5 负载平衡问题
由于文档空间标识符不是通过DHT哈希函数得到，而是利用式(5)获取，从而破坏了整个系统中文档均匀分布的特性，可能会导致节点负载不平衡。极端情况下一些相似文档可能高度聚集，导致某些节点过载现象比较突出。
如果P2P系统中的每个节点记录有自己所负责的文档的数量以及判断是否负载过重的阈值，那么当新的文档时，就可以通过下面的方法解决负载平衡问题。
由上述过程可知，相似文档被分配到了邻近的节点上。由于相似文档搜索是在n跳范围内进行广播，这个范围刚好是相似文档聚集的区域，所以这样做既能保证负载平衡，又能提高搜索的效率。
2 仿真实验
仿真实验使用BRITE[10]网络结构生成器。BRITE生成的网络结构与实际网络结构相似。与P2P的真实环境相类似，仿真利用两层拓扑结构。拓扑结构生成的方法是自底向上。路由结构使用Waxman模式，设标识符空间为216
大小，节点的数量为4096个。文档采用了TREC[11]的Web Track测试中所使用的数据集，该数据集是检索领域的标准数据集。实验从TREC中随机选择了20000篇文档，这些文档分别来自报纸，杂志等，包含了不同的主题。
仿真实验主要回答下面三个问题：
（1）向量空间模型和本体的运用能否实现多特征词复杂搜索，且提高查全率？
（2）将标识空间进行分割能否缩短搜索过程，加快收敛速度？
（3）各节点能否达到负载平衡？
为了回答第一个问题，在构造的环境中发起了5000次文档搜索请求，发起搜索请求的节点从4096个节点中随机选取。文档搜索征词数量的分布如图2所示。从图2可以看到，包含1个，2个和3个特征词的搜索占了全部搜索请求总数的90%以上，这和实际中人们发出搜索请求时使用的特征词数目的分布基本相符。
为方便起见，依据本文理论仿真实现的系统命名为SSP2P（Semantic Supporting Peer to Peer），下同。为了检验多特征词复杂检索的效果，将SSP2P与Chord作了对比。Chord系统不支持多特征词复杂搜索，对单个特征词展开独立搜索，这样每个特征词都会对应一个搜索结果集，实验中取这些结果集的交集作为Chord搜索的结果。图3显示了SSP2P与Chord的查全率随模拟次数的变化情况。
从图3的仿真结果可以看出，Chord的平均查全率在85%左右，而SSP2P的查全率则在90%以上。产生这种结果的原因有两个方面：1）SSP2P利用本体知识，扩大了搜索的范围，所以能提高查全率；2）相似的文档在小范围内聚集，而搜索时刚好在这个小范围内采用广播方式进行，进一步提高了查全率。并且大量（百分比为44%）存在的单特征词并没有影响到搜索的性能，说明SSP2P对单特征词搜索仍有很好的支持。
为了回答第二个问题，统计了上述仿真实验中节点发起的5000次文档搜索请求找到结果所需的平均逻辑跳数，计算出了逻辑跳数的概率密度函数（Probability Density Function），得出的结果如图4所示。
从图4可以看到,Chord大部分请求的平均逻辑跳数在6―7之间，这和Chord文献中给出的平均逻辑跳数为1/2log (N)的实验结果是一致的。从图3中还可以看到，在SSP2P中小逻辑跳数所占的概率比在Chord中小逻辑跳数所占的概率大，而大逻辑跳数所占的概率前者又比后者小。所以,总体上来说，SSP2P的平均逻辑跳数小于Chord的平均逻辑跳数。产生这种效果的主要原因是将标识符空间进行了分割，导致相似文档在小范围内聚集，在一定程度上加快了收敛的速度。
对于第三个问题，可以将采用负载平衡技术的运行效果和不采用负载平衡技术的运行效果进行对比。取4096个节点中的500个节点作为测试对象。如果负载均衡，每个节点所负责的文档的数量应该在5上下浮动，在此取每个节点负责文档数量的阈值为5的2倍，即为10。采用负载平衡技术进行文档后节点的负载情况与不采用负载平衡技术节点负载情况的对比效果如图5所示。从图5可以看出，当不采用负载平衡技术时，负载是不均匀的，相似文档大量地聚集在某些节点上。采用负载平衡技术后，每个节点的负载变得相对比较均匀。
3 结语
本文对基于本体的P2P复杂搜索进行了研究。向量空间模型VSM技术的应用实现了P2P系统中多特征词复杂搜索问题；将DHT―P2P标识符空间进行分割，使相似文档在邻近的节点范围内聚集，缩短了搜索所需的逻辑跳数，在一定程度上提高了搜索的速度；本体的使用，使P2P系统能够更好地理解搜索请求，扩大搜索的范围，提高搜索的查全率。
向量空间模型通过特征向量来描述文档，描述所有文档的特征向量就构成了一个高维矩阵。高维矩阵的运算量是非常大的。下一步考虑是不是能将高维矩阵降维，从而减小运算量。矩阵论中的奇异值分解（Singular Value Decomposition,SVD）[12]可以将高维矩阵转化为低维矩阵，但是如何选择降维后的矩阵维数，保证既能降低运算复杂度，又不丢失搜索请求中的语义信息是一个有待解决的问题。
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。