P2P与复杂网络在多媒体信息检索中的应用

P2P与复杂网络在多媒体信息检索中的应用通过对P2P、复杂网络以及多媒体信息检索（以文献检索为主）三块内容进行调研，我初步对各个方向有了大致了解，对它们的交叉应用做了一定的学习研究，并产生了一些自己的想法。下面我将分四个部分阐述。前三个部分分别总结对P2P、复杂网络以及多媒体信息检索的调研结果，第四部分阐述三者的交叉应用并做出总结。一、P2P调研结果P2P（Peer-to-Peer）又称对等网络，作为一种全新的网络构架，它表示“通过在系统之间直接交换信息来共享计算机资源和服务”的系统。P2P打破了传统的客户/服务器模式，对等网中各节点的地位都是相同的，每个节点既充当服务器，为其他节点提供服务，同时也充当客户机，享用其他节点提供的服务。P2P可以被广泛应用于互联网和局域网中，极大地提高网络信息、带宽和计算资源的利用率，有效均衡负载。P2P相对于其他网络模型有很多优势。P2P架构不需要性能超强的服务器，而是将过高的成本在网络节点中分摊开来，充分聚集和利用网络中其他节点的空闲资源。也正是由于P2P网络的每个节点既可作服务器又是客户端，它还有高扩展性、稳定性和很强的容错性，在网络拓扑构造、安全与可靠性、分布式数据存储、大规模并行计算等方面都有很强的应用性，这里就不多介绍了。现有的P2P文件共享系统按照结构特征通常被分为四类，即基于集中索引的P2P网络、非结构化P2P网络、基于分布式哈希表的结构化P2P网络和混合式P2P网络。集中索引P2P结构是最早出现的对等网络应用模式，因为仍然具有中心化的特点也被称为非纯粹的P2P结构，典型系统是Napster。非结构化的P2P网络是在网络中采用随机图的节点拓扑组织方式，克服了单点故障的问题，可扩展性更强，典型系统是Gnutella。结构化的P2P搜索机制中，P2P网络的拓扑结构是受到严格控制的，文件不是被随机摆放，而必须放置在P2P网络的特定节点上以利于搜索的进行，多采用分布式哈希表（DHT）算法。混合式P2P网络中，节点会把它上面的资源信息发布到超节点上，为查找一个文件，节点会首先把查询发到超节点上，查询也可以被进一步转发到其它的超节点上。超节点一般会具有较大的带宽和较强的处理能力。信息检索是从大量文档信息集合中找到与给定查询请求相关的文档子集。P2P信息检索分为集中式信息检索、泛洪式信息检索和DHT式信息检索。集中式信息检索（如Napster）需要一个中央服务器保存所有注册过的文件，查询工作由服务器完成，然后各节点采用点对点方式直接通讯。缺点是单点失效，可扩展性不佳。泛洪式信息检索（如Gnutella、FreeNet）中，每个节点仅仅维护本身的内容索引，一个节点要进行检索，就像他的邻居节点广播消息（泛洪），邻居节点可满足就返回结果集，否则向该点的邻居节点转发。缺点是不能保证可靠性。DHT式信息检索利用分布式哈希表，每个节点不仅维护本身的内容缩引，而且维护其他节点上部分特定内容的索引，维护该内容的索引节点ID可通过Hash得到。缺点是不支持模糊查找。二、复杂网络理论调研结果社会心理学家Milgram曾做过一个实验，实验要求参与者把一封信通过熟人传送给指定的某人，借此探明熟人关系网络中路径长度的分布。虽然实验中大多数信被丢弃，但仍有四分之一的信被送达目标人。统计显示平均依次经过6个熟人就可传达到，这就是著名的“六度分隔”理论。“六度分隔”现象的普遍存在一定程度上揭示了复杂网络的内在共性——看似复杂的自然与社会网络中各元素之间的距离其实很“近”，专业术语称为“小世界效应”：即网络中任意两点间的平均距离L随网络节点数N的增加呈对数增长，网络规模的变化并不对L的值产生很大影响，网络局部呈现明显的集团化特性。两个定义。簇系数：对于某个节点，它的簇系数被定义为它所有相邻节点之间连得数目占可能的最大连边数目的比例，专门用来衡量网络节点聚类的情况。平均距离：在网络中，两点间的距离被定义为连接两点的最短路径所包含的边的数目，对所有节点对的距离求平均，就得到了网络的平均距离。规则网络具有很大的簇系数和大的平均距离，随机网络具有小的簇系数和小的平均距离。1998年，Watts和Strogatz通过以某个很小的概率切断规则网络中原始的边，并随机选择新的端点重新连接，构造出了介于规则网络和随机网络的“小世界网络”，它同时具有大的簇系数和小的平均距离。也就是说，网络呈现一种以密集的局部连接为主，以稀少的长程连接为辅的体系结构。举个例子，在社会网中，人们通常有一些与其兴趣相似的朋友，同时也可能有少数与其兴趣不一定相似但有众多社会联系的朋友，从而人们可以通过很短的“朋友的朋友”社会关系链相互联系。研究表明，现实世界的许多复杂网络具有幂律特性，即具有某个特定“度”K的节点数目与这个特定的度之间的关系可以用一个幂函数近似表示：，这使得度很大的节点可以在网络中存在，即网络中仅有少数一些节点具有大量与其他节点的连接，绝大多数节点与其他节点的连接度较低，这种网络又被称为“无标度网络”。这种现象产生的原因是，新的节点加入网络时会以更大的概率连接到网络中度较大的老节点上。大规模非结构化自组织网络均具有小世界特性。2000年5月至12月，MihajloA.Jovanovic和S.Annexstein等人对Gnutella网络的拓扑结构进行了研究，发现其拓扑结构显示出小世界特性；2001年，他们又发现，Gnutella网络拓扑节点的分布具有幂律特性：网络中有少数节点有较高的度，多数节点度较低。于是可以预见，在这样的网络中，不需要在随机网络中必须做“洪泛”才能实现高效了路径选择，只需选择从一个节点到达另一个节点的路径算法就有较高的效率和较小的开销。由于小世界网络的高聚集度和低网络直径，最终对较短路径的实现起了关键作用的是那些高聚集度节点和密集的捷径连接。三、文献信息检索技术调研结果宏观地看，主要有两类信息检索技术：语义方面的和统计学方面的，其中统计学方法用的最多。统计学方法又包括布尔方法、扩展布尔方法、向量空间方法和概率论方法等。目前P2P中多数使用的是布尔模型。布尔模型是基于集合论的一种简单匹配模型，其查询项（QueryTerm）定义为包含该Term的文档集合，Query为一个布尔表达式，查询项用布尔代数的运算符号来连接，其运算结果的文档集合作为检索结果。在向量空间模型中，文档用加权的关键词向量来表示，相似度用两个向量夹角余弦来计算，通常权值计算使用的是基于统计分析、直觉和试验的基础上的经验公式，典型的是TF/IDF的线性组合。为提高检索的健壮性，引入自然语言处理和机器学习的方法。支持向量机（SVM）是一种基于统计的机器学习方法，其核心思想就是学习机器要与有限的训练样本相适应。支持向量机根据结构风险最小化准则，在使训练样本分类误差极小化的前提下，尽量提高分类器的泛化推广能力。为在尽量保持文档信息特征的情况下减少信息存储量，使用潜在语义索引提取文档特征向量作为支持向量机的文档特征向量。潜在语义索引（LSI）又称潜在语义分析，是为了改善向量空间模型的效果而提出的。在用词来表示文本的时候，由于大量存在的同义词、近义词和多义词，使得特征之间相互独立的假设不能成立。LSI通过统计大量文本中这些词的共现信息，来发掘它们的内部联系，称为文本的语义。LSI认为每篇文章都包含几种语义，他们之间是相互独立的，如果可以用这些语义来表示文档，并拿它们来进行计算，则在降低计算复杂度的同时，还可以保持良好的效果。如何对文献进行准确的分类呢？有一种方法是，首先利用潜在语义索引提取文档特征向量，在降维的文档特征向量基础上，使用支持向量机对训练文档进行有指导的学习，获取支持向量模型，从而能对其他文档进行准确的分类。四、三者的交叉应用前面提到过，Gnutella网络是非结构化的P2P网络，同时也是小世界网络。在Gnutella网络中使用“洪泛”机制进行节点定位和查询的路由机制缺乏可扩展性的原因：Gnutella是小世界网络，网络中节点具有较高的聚集度，因此“洪泛”机制会产生大量冗余的流量，很容易导致网络中弱计算节点过载失效，使得网络被分片，最终导致网络规模不易扩展。为解决此问题，利用前三块讲述的内容，可构建P2P网络文献检索小世界模型。设定模型是一个具有n个节点的非结构化的P2P文件共享系统，根据小世界现象中的短连接要求，每个节点在两跳范围内选择文档类别兴趣比例相似的节点（选择2跳原因是考虑效率和维护的开销），选择的标准是相似度超过预定的相似度阈值；再根据小世界现象中的长链接要求，如果网络中个别节点在某一种文档类别的兴趣比例非常高，超过预定的阈值，则该节点设置成最有可能被其他节点直接连接的超级节点；最后所有节点在超过两跳的范围外，按照非常小的概率与超级节点直接链接。类比到社会网络关系中，人们一般希望与自己兴趣相近似的人交朋友，这与短链接节点相类似；同时人们也希望与有着广泛社会联系的人交朋友，这些人也许与自己的兴趣不一定相同，长链接节点则与此类似。本模型基本思路是使P2P网络中的所有节点都具有直接相连的较少的与其兴趣相似的短链接节点和极少的与其兴趣不一定相似但一定在某一种文档类别的兴趣比例非常高的长链接，从而形成具有小世界特征的网络拓扑。这一段将讲述如何在文献检索中应用P2P网络小世界模型。检索的主要目标是将查询语句路由到最有可能回答该请求的节点，而不是传统的盲目路由，从而提高查询效率；同时，充分利用小世界中的长链接，使查询语句也能被很快的路由到网络中的其他部分，而不是陷在小的网络范围内，从而提高信息检索的重要指标查全率。节点分类的方法是首先利用潜在语义索引提取文档特征向量，然后在降维的文档特征向量的基础上，使用支持向量机对训练文档进行有指导的学习，获取支持向量模型，从而能对其他文档进行准确的分类；最后P2P网络中的节点在获得以上向量模型后，对本节点的所有共享文档进行分类，形成分类信息，该分类信息标志该节点对文档类别的兴趣比例。在完成对节点的分类后，即可按照小世界模型的参数要求，构建具有小世界特征的对等网络拓扑。P2P网络文献检索小世界模型构建流程图：在该模型中的文献检索流程图：