《P2P与复杂网络在多媒体信息检索中的应用》由会员分享，可在线阅读，更多相关《P2P与复杂网络在多媒体信息检索中的应用（9页珍藏版）》请在金锄头文库上搜索。
1、P2P 与复杂网络在多媒体信息检索中的应用通过对P2P、复杂网络以及多媒体信息检索(以文献检索为主) 三块内容进行调研，我初步对各个方向有了大致了解，对它们的交叉 应用做了一定的学习研究，并产生了一些自己的想法。下面我将分四个部分阐述。前三个部分分别总结对P2P、复杂网 络以及多媒体信息检索的调研结果，第四部分阐述三者的交叉应用并 做出总结。一、P2P调研结果P2P(Peer-to-Peer)又称对等网络，作为一种全新的网络构架， 它表示“通过在系统之间直接交换信息来共享计算机资源和服务”的 系统。P2P打破了传统的客户/服务器模式，对等网中各节点的地位都 是相同的，每个节点既充当服务器，为其
2、他节点提供服务，同时也充 当客户机，享用其他节点提供的服务。P2P可以被广泛应用于互联网 和局域网中，极大地提高网络信息、带宽和计算资源的利用率，有效 均衡负载。P2P相对于其他网络模型有很多优势。P2P架构不需要性能超强 的服务器，而是将过高的成本在网络节点中分摊开来，充分聚集和利 用网络中其他节点的空闲资源。也正是由于P2P网络的每个节点既可 作服务器又是客户端，它还有高扩展性、稳定性和很强的容错性，在 网络拓扑构造、安全与可靠性、分布式数据存储、大规模并行计算等 方面都有很强的应用性，这里就不多介绍了。现有的 P2P 文件共享系统按照结构特征通常被分为四类，即基于 集中索引的 P2P 网
3、络、非结构化 P2P 网络、基于分布式哈希表的结 构化 P2P 网络和混合式 P2P 网络。集中索引 P2P 结构是最早出现的 对等网络应用模式，因为仍然具有中心化的特点也被称为非纯粹的 P2P结构，典型系统是Napster。非结构化的P2P网络是在网络中采 用随机图的节点拓扑组织方式，克服了单点故障的问题，可扩展性更 强，典型系统是Gnutella。结构化的P2P搜索机制中，P2P网络的拓 扑结构是受到严格控制的，文件不是被随机摆放，而必须放置在P2P 网络的特定节点上以利于搜索的进行，多采用分布式哈希表（DHT） 算法。混合式P2P网络中，节点会把它上面的资源信息发布到超节点 上，为查找一
4、个文件，节点会首先把查询发到超节点上，查询也可以 被进一步转发到其它的超节点上。超节点一般会具有较大的带宽和较 强的处理能力。信息检索是从大量文档信息集合中找到与给定查询请求相关的 文档子集。 P2P 信息检索分为集中式信息检索、泛洪式信息检索和 DHT式信息检索。集中式信息检索（如Napster）需要一个中央服务 器保存所有注册过的文件，查询工作由服务器完成，然后各节点采用 点对点方式直接通讯。缺点是单点失效，可扩展性不佳。泛洪式信息 检索（如Gnutella、FreeNet） 中,每个节点仅仅维护本身的内容索引， 一个节点要进行检索，就像他的邻居节点广播消息（泛洪），邻居节 点可满足就返回
5、结果集，否则向该点的邻居节点转发。缺点是不能保 证可靠性。 DHT 式信息检索利用分布式哈希表，每个节点不仅维护 本身的内容缩引，而且维护其他节点上部分特定内容的索引，维护该 内容的索引节点 ID 可通过 Hash 得到。缺点是不支持模糊查找。二、复杂网络理论调研结果社会心理学家 Milgram 曾做过一个实验，实验要求参与者把 一封信通过熟人传送给指定的某人，借此探明熟人关系网络中路径长 度的分布。虽然实验中大多数信被丢弃，但仍有四分之一的信被送达 目标人。统计显示平均依次经过6 个熟人就可传达到，这就是著名的 “六度分隔”理论。“六度分隔”现象的普遍存在一定程度上揭示了 复杂网络的内在共性
6、看似复杂的自然与社会网络中各元素之间 的距离其实很“近”，专业术语称为“小世界效应”：即网络中任意两 点间的平均距离 L 随网络节点数 N 的增加呈对数增长，网络规模的 变化并不对L的值产生很大影响，网络局部呈现明显的集团化特性。两个定义。簇系数：对于某个节点，它的簇系数被定义为它所有 相邻节点之间连得数目占可能的最大连边数目的比例，专门用来衡量 网络节点聚类的情况。 平均距离：在网络中，两点间的距离被定义 为连接两点的最短路径所包含的边的数目，对所有节点对的距离求平 均，就得到了网络的平均距离。规则网络具有很大的簇系数和大的平均距离，随机网络具有小的 簇系数和小的平均距离。1998年，Wat
7、ts和Strogatz通过以某个很小 的概率切断规则网络中原始的边，并随机选择新的端点重新连接，构 造出了介于规则网络和随机网络的“小世界网络”，它同时具有大的 簇系数和小的平均距离。也就是说，网络呈现一种以密集的局部连接 为主，以稀少的长程连接为辅的体系结构。举个例子，在社会网中， 人们通常有一些与其兴趣相似的朋友，同时也可能有少数与其兴趣不 一定相似但有众多社会联系的朋友，从而人们可以通过很短的“朋友 的朋友”社会关系链相互联系。研究表明，现实世界的许多复杂网络具有幂律特性，即具有某个 特定“度” K的节点数目与这个特定的度之间的关系可以用一个幕函 数近似表示：，这使得度很大的节点可以在网
8、络中存 在，即网络中仅有少数一些节点具有大量与其他节点的连接，绝大多 数节点与其他节点的连接度较低，这种网络又被称为“无标度网络”。 这种现象产生的原因是，新的节点加入网络时会以更大的概率连接到 网络中度较大的老节点上。大规模非结构化自组织网络均具有小世界特性。2000 年 5 月至 12 月， MihajloA.Jovanovic 和 S.Annexstein 等人对 Gnutella 网络的拓 扑结构进行了研究，发现其拓扑结构显示出小世界特性；2001 年， 他们又发现，Gnutella网络拓扑节点的分布具有幕律特性：网络中有 少数节点有较高的度，多数节点度较低。于是可以预见，在这样的网
9、络中，不需要在随机网络中必须做“洪泛”才能实现高效了路径选择， 只需选择从一个节点到达另一个节点的路径算法就有较高的效率和 较小的开销。由于小世界网络的高聚集度和低网络直径，最终对较短 路径的实现起了关键作用的是那些高聚集度节点和密集的捷径连接。三、文献信息检索技术调研结果宏观地看，主要有两类信息检索技术：语义方面的和统计学方面 的，其中统计学方法用的最多。统计学方法又包括布尔方法、扩展布 尔方法、向量空间方法和概率论方法等。目前 P2P 中多数使用的是布 尔模型。布尔模型是基于集合论的一种简单匹配模型，其查询项 （Query Term）定义为包含该Term的文档集合，Query为一个布尔 表
10、达式，查询项用布尔代数的运算符号来连接，其运算结果的文档集 合作为检索结果。在向量空间模型中，文档用加权的关键词向量来表 示，相似度用两个向量夹角余弦来计算，通常权值计算使用的是基于 统计分析、直觉和试验的基础上的经验公式，典型的是TF/IDF的线 性组合。为提高检索的健壮性，引入自然语言处理和机器学习的方法。支 持向量机（SVM）是一种基于统计的机器学习方法，其核心思想就 是学习机器要与有限的训练样本相适应。支持向量机根据结构风险最 小化准则，在使训练样本分类误差极小化的前提下，尽量提高分类器 的泛化推广能力。为在尽量保持文档信息特征的情况下减少信息存储量，使用潜在 语义索引提取文档特征向量
11、作为支持向量机的文档特征向量。潜在语 义索引（LSI）又称潜在语义分析，是为了改善向量空间模型的效果 而提出的。在用词来表示文本的时候，由于大量存在的同义词、近义 词和多义词，使得特征之间相互独立的假设不能成立。LSI通过统计 大量文本中这些词的共现信息，来发掘它们的内部联系，称为文本的 语义。LSI认为每篇文章都包含几种语义，他们之间是相互独立的， 如果可以用这些语义来表示文档，并拿它们来进行计算，则在降低计 算复杂度的同时，还可以保持良好的效果。如何对文献进行准确的分类呢？有一种方法是，首先利用潜在语 义索引提取文档特征向量，在降维的文档特征向量基础上，使用支持 向量机对训练文档进行有指导
12、的学习，获取支持向量模型，从而能对 其他文档进行准确的分类。四、三者的交叉应用前面提到过，Gnutella网络是非结构化的P2P网络，同时也是小 世界网络。在Gnutella网络中使用“洪泛”机制进行节点定位和查询 的路由机制缺乏可扩展性的原因：Gnutella是小世界网络，网络中节 点具有较高的聚集度，因此“洪泛”机制会产生大量冗余的流量，很 容易导致网络中弱计算节点过载失效，使得网络被分片，最终导致网 络规模不易扩展。为解决此问题，利用前三块讲述的内容，可构建P2P网络文献检 索小世界模型。设定模型是一个具有n个节点的非结构化的P2P文件共享系统， 根据小世界现象中的短连接要求，每个节点在
13、两跳范围内选择文档类 别兴趣比例相似的节点（选择 2 跳原因是考虑效率和维护的开销）， 选择的标准是相似度超过预定的相似度阈值；再根据小世界现象中的 长链接要求，如果网络中个别节点在某一种文档类别的兴趣比例非常 高，超过预定的阈值，则该节点设置成最有可能被其他节点直接连接 的超级节点；最后所有节点在超过两跳的范围外，按照非常小的概率 与超级节点直接链接。类比到社会网络关系中，人们一般希望与自己 兴趣相近似的人交朋友，这与短链接节点相类似；同时人们也希望与 有着广泛社会联系的人交朋友，这些人也许与自己的兴趣不一定相 同，长链接节点则与此类似。本模型基本思路是使 P2P 网络中的所有节点都具有直接
14、相连的 较少的与其兴趣相似的短链接节点和极少的与其兴趣不一定相似但 一定在某一种文档类别的兴趣比例非常高的长链接，从而形成具有小 世界特征的网络拓扑。这一段将讲述如何在文献检索中应用P2P网络小世界模型。检索 的主要目标是将查询语句路由到最有可能回答该请求的节点，而不是 传统的盲目路由，从而提高查询效率；同时，充分利用小世界中的长 链接，使查询语句也能被很快的路由到网络中的其他部分，而不是陷 在小的网络范围内，从而提高信息检索的重要指标查全率。节点分类 的方法是首先利用潜在语义索引提取文档特征向量，然后在降维的文 档特征向量的基础上，使用支持向量机对训练文档进行有指导的学 习，获取支持向量模型
15、，从而能对其他文档进行准确的分类；最后 P2P网络中的节点在获得以上向量模型后，对本节点的所有共享文档 进行分类，形成分类信息，该分类信息标志该节点对文档类别的兴趣 比例。在完成对节点的分类后，即可按照小世界模型的参数要求，构 建具有小世界特征的对等网络拓扑。P2P 网络文献检索小世界模型构建流程图：呈否计舞思編如星jK绑应尉須过嘲111+设黄燼 节点为対簸廿点在2牛毗范阐丙鬲 們戌徘粪仍思 L I计相鰹崔粗过険個蜕藍 対胞节点为is乍点的艇琏枝神点收到俄广播怙息的节点按煦槪率验宣密牡 点为氐琏疲节点判川支持向址模亞琢对防燉的址忙（分 宾.形曲节点的丈档佶JW 5= W 丹训绰玄持向址机.砂:得妾拎向童権醜曲广插SS级节点怕駄在该模型中的文献检索流程图：幵始否谆肚殆蛊A JKF发布讳査海语旬 的FAWffi比ffl捋分散布柱询晤旬= K,时. 其中JT表:示关徒字山裁示文档类别柠Q菲发蜡芳曲芳点的折附枝睦接节点將J?转发蛤巧谨节血直挨相 童的哪居节点执荷帛地fiffl-井逆回査询轴舉將0转发绪所有短捱接节点
