分布式WEB信息检索技术研究.ppt

1、分布式分布式WEB信息检索技术研究信息检索技术研究Research on Distributed WEB Information Retrieval 博士生：张刚导师：李国杰院士2005年12月Outlinel研究背景l学位论文研究情况和已完成的研究内容l已取得的阶段性成果l下一步的工作计划l科研项目的完成情况l学术论文发表情况l课程完成情况研究背景研究背景l海量信息检索的挑战WEB信息的增长：6个月翻一番表层页面（surface WEB）80亿-100亿Hobbes Internet Timeline统计，截止到2005年8月，互联网上WEB服务主机数已达到70,392,567台 l矛盾与问

2、题80亿 VS.Top10问题！是否80亿个页面都需要查询？如何减少查询量？研究背景研究背景l分布式信息检索是海量信息检索的有效方案团队作战分而治之l分布式信息检索的主要过程文档集合划分集合选择单文档集合检索结果合并分布式信息检索的体系结构分布式信息检索的体系结构分布式信息检索的过程分布式信息检索的过程集合选择查询学位论文研究情况和已完成的研究内容学位论文研究情况和已完成的研究内容l分布式WEB信息检索的集合划分问题分布式信息检索检索的划分问题建模 基于内容的文档划分技术基于链接的文档划分算法分布式信息检索文档集合划分算法评价l分布式信息检索的集合选择问题研究 tf.idf系列模型CORI集合

3、选择算法语言模型检索 OKAP模型分布式信息检索检索的划分问题建模分布式信息检索检索的划分问题建模l文档集合划分的问题描述 l文档集合的划分模型l模型的解空间分析l文档划分问题最优解的快速解法l算法复杂度分析文档集合划分的问题描述文档集合划分的问题描述l文档集合划分问题问题1：文档分布问题。即：每个子集合中应包含哪些文档问题2：文档集划分个数问题。即：一个给定的文档集合应该被划分成几个子集合l直观的划分原则同一个查询的相关文档，尽可能集中在少数的子集合各个子集合的规模相差尽可能小l影响文档划分的三个主要因素文档集D、查询集Q、查询的相关文档集R文档集合划分的问题描述（文档集合划分的问题描述（）

4、l文档集合划分的核心难题文档与查询的相关关系是一种多对多的关系一个查有多个相关文档、一个文档是多个查询的相关文档DocQuery多对多DocQuery多对一问题文档文档集合的划分模型文档集合的划分模型l文档集划分问题1（文档分布问题）建模描述：如果给定一个文档集合D，查询集合Q及其相关文档集R，要将文档集D划分成K个子集合，那么D中的文档如何在各个子集合中分布是最合理的方式什么是最合理的方式？l模型优化原则：求解一种文档集合的划分，使得处理Q中的查询，所需要检索的平均文档数最少l分布式检索的过程第一步：找出含有相关文档的子集合第二步：对于每个子集合，找出其中的相关文档文档集合的划分模型文档集合

5、的划分模型l文档集合划分模型1子集合查询集合相关文档集l模型物理意义查询平均文档数文档的划分结果就是当avgdoc1取最小值时对应的一组Si举例举例l集合D=1,5,6,7,8,9,12共7元素，另外知道四个查询的相关文档集合R1=1，5，9，12R2=1，5，7，8R3=5，6，7，9R4=7，8，9，12l7个数被划分成三个子集合S1=1，5，6，S2=7,8，S3=9,12l模型代价为(|S1|+|S3|)+(|S1|+|S2|)+(|S1|+|S2|+|S3|)+(|S2|+|S3|)/4文档集合的划分模型文档集合的划分模型l文档划分问题2（文档集划分个数问题）建模问题描述：如果给定一

6、个文档集合D，查询集合Q及其相关文档集R，在不考虑机器等资源限制条件下，应该划分成多少个子集合是最合理的l重温分布式信息检索过程第一步：找出含有相关文档的子集合第二步：对于每个子集合，找出其中的相关文档文档集合的划分模型文档集合的划分模型l文档集合划分模型2考虑文档集合划分个数情况下的，平均查询文档数查询集子集合相关文档集子集合个数文档的划分结果就是当avgdoc2取最小值时,对应的 一组Si和K文档集合的划分模型文档集合的划分模型l模型2的两种极端情况传统集中式检索，无文档划分每个文档作为一个文档集合两种情况按照模型是一致的，实际上也没有差别可行解空间分析可行解空间分析l模型1可行解空间分析

7、有m个小球放入n个盒子中(m=n)，小球有差别，盒子没有差别，不准有空盒，所有的可能性中寻求一个最佳的放法（组合个数为第二类Stirling数）l模型2可行解空间分析有m个小球放入n个盒子中（m=n），小球有差别，盒子没有差别，允许有空盒，所有的可能性中寻求一个最佳的放法文档划分问题最优解的快速解法文档划分问题最优解的快速解法l模型1与模型2的关系l关键问题：求解模型1的最优解类哈夫曼编码的最优解求解算法文档划分问题最优解的快速解法文档划分问题最优解的快速解法l模型1最优解求解过程随子集合个数减少，模型1的最优解分为两个阶段解法第一阶段：模型1的最优解是一个常数第二阶段：模型1最优解的构造采用

8、类哈夫曼编码算法文档划分问题最优解的快速解法文档划分问题最优解的快速解法l第一阶段模型1的最优解为常数首先考虑每个文档是一个子集合的情况，此时模型1的最优解为如果将子集合个数减少，需要将部分子集合合并，合并原则是：合并后新的子集合中的文档都是同一个查询的相关文档，这种过程不断进行，直到无法进行为止当合并无法进行时，是模型的一个分界点，在此之前模型1的最优解保持不变文档划分问题最优解的快速解法文档划分问题最优解的快速解法l第二阶段模型1的最优解算法当过了上述临界点，再进行合并时，就会出现一个子集合中包含多个查询的相关文档的情况此时该子集合在计算模型1的最优值是就会被多次使用，使用的次数为不同查询

9、的个数因此决定哪两个子集合合并时，需要找出一种合并以后代价最小的方案求解最小代价的方法，类似于哈夫曼编码的过程文档划分问题最优解的快速解法文档划分问题最优解的快速解法l类哈夫曼编码算法模型1与哈夫曼编码的类比l子集合Si为待编码的字符l子集合的模|Si|为该字符的编码长度 l子集合在计算模型1被使用的次数，为字符的出现频率由此模型1的求解过程就是完成对子集合Si的一个编码过程，也就是构建一个哈夫曼编码树文档划分问题最优解的快速解法文档划分问题最优解的快速解法l演示代价8代价6代价6代价4模型求解临界点算法复杂度分析算法复杂度分析l第一次比较合并需要两两比较代价计算次数为l此后采用动态规划算法，

10、利用前次计算的结果1 2 3 4 51 2 3 4 51 2 34 51 2 34 5算法复杂度分析算法复杂度分析l模型1算法时间复杂度l模型2算法时间复杂度l空间开销文档集合划分模型试验分析文档集合划分模型试验分析l文档集描述TREC2002、2003、2004年的查询集合，共324个 相关集合中文档个数为3853个不同文档个数为3778篇69篇文档同时是2个查询的相关文档3篇文档同时是3个查询的相关文档 文档集合划分模型试验分析文档集合划分模型试验分析l模型最优值随子集合个数变化曲线横轴：子集合个数纵轴：最优值对数l最优划分方案子集合个数为52划分方案为模型1对应的模型参数Si文档集合划分

11、模型实验分析文档集合划分模型实验分析l最优划分方法与其他划分方法比较模型2最优划分基于内容相关聚类划分随机划分最优划分 内容聚类 随机划分 avgdoc150.04 273.59 653.15avgdoc2102.04 325.59 601.15 文档集合划分模型实验深入分析文档集合划分模型实验深入分析l划分模型的假设及实践应用中的方法知道全部查询和查询相关文档为前提实践中，可以利用查询日志，得到查询以及查询的相关文档，甚至可以利用查询出现的次数进行优化l模型综合考虑了直观划分的两个指标相关文档集中分布子集合规模差距尽量小文档集合划分模型小结文档集合划分模型小结l给出了一个可以量化的最优划分模

12、型给出了一种划分的最优化标准回答了集合划分的两个问题可行的模型最优化解法l对其他研究领域的意义数据流管理平台l扫描关键词类似文档l关键词的分布类似文档集合的划分数据库管理系统l数据的分布问题学位论文研究情况和已完成的研究内容学位论文研究情况和已完成的研究内容l分布式WEB信息检索的集合划分问题分布式信息检索检索的划分问题建模 基于内容的文档划分技术基于链接的文档划分算法分布式信息检索文档集合划分算法评价l分布式信息检索的集合选择问题研究 tf.idf系列模型CORI集合选择算法语言模型检索 OKAP模型基于内容的文档划分技术基于内容的文档划分技术l基于内容相关的文档划分思想考虑一个查询的相关文

13、档之间的关系假设：一个查询的相关文档他们在内容上也是相关的l基于内容的文档划分算法策略文档内容相关度的度量基于内容相关度的聚类技术采用快速的聚类算法基于内容的文档划分技术基于内容的文档划分技术l内容相关度度量方法向量空间模型VSM余弦相似度计算l快速聚类方法K-Means聚类技术基于内容的文档划分实验基于内容的文档划分实验l测试集为TREC标注测试集55万文档内容聚类随机平均正确率 0.1161 0.0830 相关的文档数 1172 773 基于内容的文档划分局限基于内容的文档划分局限l效率问题55万文档划分用时大于7天，2颗P4CPU、4GMem125万文档，几乎无法计算出结果l效率问题成因

14、聚类中心向量维度爆炸，导致计算代价巨大l解决办法及困难向量降维聚类难以进行有指导的学习学位论文研究情况和已完成的研究内容学位论文研究情况和已完成的研究内容l分布式WEB信息检索的集合划分问题分布式信息检索检索的划分问题建模 基于内容的文档划分技术基于链接的文档划分算法分布式信息检索文档集合划分算法评价l分布式信息检索的集合选择问题研究 tf.idf系列模型CORI集合选择算法语言模型检索 OKAP模型基于链接的文档划分算法基于链接的文档划分算法l基于链接的文档划分思想假设：一个查询的相关文档间，在网页的链接关系上具有某些特点，使得能够通过这些特点，可以刻划他们之间的相关性l基于内容的文档划分算

15、法策略网页文档之间的链接关系挖掘利用链接关系刻划网页的相关度利用网页的相关度对网页进行聚类，实现文档集合的划分链接分析算法回顾链接分析算法回顾l通过链接评价网页质量的算法PageRank HITS链接分析算法回顾（链接分析算法回顾（）l网页间的相关度计算Co-Citation Bibliographic Coupling Amsler ABCCA sim.BABCCA sim.B链接相似度计算方法的扩展链接相似度计算方法的扩展l网页与网页集合的相似度计算网页集合被视为虚拟网页虚拟网页的入链接虚拟网页的出链接基于链接的网页划分方法基于链接的网页划分方法l类k-means聚类方法不确定0.30.2

16、0.80.50000K类sim实验及结果分析实验及结果分析l数据集TREC WEB track Gov数据集：124万文档划分的子集合个数：100个查询集：WEB track2002、2003、2004l划分方法基于链接的划分算法co-cite、co-ref、co-cite-ref 随机划分方法实验及结果分析（实验及结果分析（）l不同划分方法比较WEB track2002查询集坐标轴l横坐标查询编号l纵坐标为子集合个数实验及结果分析（实验及结果分析（）l不同叠带次数比较WEB track2002坐标轴l横坐标查询编号l纵坐标为子集合个数结论算法能够比较快速稳定实验及结果分析（实验及结果分析（）

17、l相关文档分布比较WEB track2002坐标轴l子集合编号l相关文档数结论相关文档集中在较少的子集合中实验及结果分析（实验及结果分析（）lTop10子集合含相关文档比例Top10子集合含有80-90%相关文档rand（%）co-ref（%）co-cite（%）co-cite-ref（%）TREC200242.2579.2277.3878.71TREC200373.6484.1186.8289.53TREC200457.6374.3178.7379.69实验及结果分析（实验及结果分析（）l基于链接的分布式检索结果比较2002、2003、2004查询三种链接相似度、随机划分、集中式划分对比p5

18、 p10 相关文档数 CC 0.1447 0.1106 334 BC 0.09790.1043344 AM 0.13190.1191390RA0.09790.0809125CE 0.12340.1106634p5 p10 相关文档数 CC 0.0410.041149BC 0.050.0325148AM 0.030.0325158RA0.040.02539CE 0.0650.0475268p5 p10 相关文档数 CC 0.0680.0535512BC 0.05050.0406469AM 0.05250.0411540RA0.03270.0238167CE 0.06140.046869TREC

19、WEB Track2002TREC WEB Track2003TREC WEB Track2004基于链接划分算法特点基于链接划分算法特点l算法复杂度方面并没有比基于内容的算法复杂度低l计算难度网页相关度计算简单、效率高相对词语来说，链接数量较少集合增加较慢对于特征的选择简单l比较适合处理大规模文档集合划分问题计算简单、处理速度快125万网页，处理时间在6-7小时学位论文研究情况和已完成的研究内容学位论文研究情况和已完成的研究内容l分布式WEB信息检索的集合划分问题分布式信息检索检索的划分问题建模 基于内容的文档划分技术基于链接的文档划分算法分布式信息检索文档集合划分算法评价l分布式信息检索的

20、集合选择问题研究 tf.idf系列模型CORI集合选择算法语言模型检索 OKAP模型分布式信息检索文档集合划分算法评价分布式信息检索文档集合划分算法评价l文档集合划分问题可以作为聚类问题图划分问题l聚类问题评价本身是一个困难的问题l文档集合划分算法平价的难点不同划分算法，划分的子集合个数不尽相同子集合个数相同也难以比较，例如：算法1：Rq=10，2，1，1，算法2：Rq=8，7分布式信息检索文档集合划分算法评价分布式信息检索文档集合划分算法评价l直观的评价的困惑同一个查询的相关文档，尽可能集中在少数的子集合避免各个子集合的规模相差过于悬殊标准难以量化l分布式检索结果作为评价标准的问题受到集合选

21、择、单数据集合检索、结果合并的影响较大l文档划分模型1和模型2作为划分算法评价标准模型1评价划分子集合个数相同的算法模型2评价划分子集合个数不同的算法分布式信息检索文档集合划分小结分布式信息检索文档集合划分小结l分布式检索文档划分问题建模两个划分模型：模型1、模型2模型求解算法：类哈夫曼编码算法l基于内容的划分算法效率问题严重l基于网页链接关系的划分算法运算简单，效率较高l划分算法的评价问题优化模型作为评价指标学位论文研究情况和已完成的研究内容学位论文研究情况和已完成的研究内容l分布式WEB信息检索的集合划分问题分布式信息检索检索的划分问题建模 基于内容的文档划分技术基于链接的文档划分算法分布

22、式信息检索文档集合划分算法评价l分布式信息检索的集合选择问题研究 tf.idf系列模型CORI集合选择算法语言模型检索 OKAP模型分布式信息检索的集合选择问题研究分布式信息检索的集合选择问题研究l问题描述通过检索的方法找出那些含有相关文档的集合l通行的策略文档集合作为一个虚拟的文档建立索引采用类似文本检索的方法检索到相关文档集合l著名的算法CORI算法gGlOSS算法分布式信息检索的集合选择问题研究分布式信息检索的集合选择问题研究l文档检索与集合选择问题的比较文档检索与集合选择问题的比较 相同点：集合选择可以看作是一种文档检索不同点：l文档长度的不同 l文档内容的蕴涵不同 l词语的分布特征不

23、同 l文档的数量不同l将集合选择作为文档检索问题经典的检索方法可用是否能取得和文档检索相当的效果？分布式信息检索的集合选择问题研究分布式信息检索的集合选择问题研究l经典的检索方法tf.idf系列检索方法概率模型算法OKAPIINQUERY算法语言模型检索方法l在集合选择中已经用的INQUERY就是CORI算法语言模型有应用，但讨论的不够全面分布式信息检索的集合选择问题研究分布式信息检索的集合选择问题研究ltf.idf系列多种权重规格化方法llog(tf)lcosin权重规格化 分布式信息检索的集合选择问题研究分布式信息检索的集合选择问题研究l概率模型算法OKAPI分布式信息检索的集合选择问题研

24、究分布式信息检索的集合选择问题研究lINQUERY算法分布式信息检索的集合选择问题研究分布式信息检索的集合选择问题研究l语言模型检索方法l平滑算法JMAbsDir分布式信息检索的集合选择问题研究分布式信息检索的集合选择问题研究l理想的集合选择算法按照子集合中相关文档的个数进行排序可以作为集合算法性能的参照分布式信息检索的集合选择问题实验分布式信息检索的集合选择问题实验l实验数据WEB TREC Gov数据基于链接划分算法，划分成100个数据子集合相关文档总数为1275篇检索方法检索方法文档检索文档检索集合选择集合选择(篇篇)tf.idfraw(tf)0.0176794log(tf)0.0176

25、810cosine0.0539756OKAPI(BM25)0.0807441INQUERY(CORI)0.0848863 语言语言模型模型JM0.0683860Dir0.0647840Abs0.0808876理想集合选择算法理想集合选择算法1155分布式信息检索的集合选择问题实验分布式信息检索的集合选择问题实验l语言模型在集合选择中的平滑分析平滑技术是影响检索性能的重要因素以往在对文档检索中，平滑因素影响很大实验验证对于集合选择平滑因素的影响l以往的实验结果分布式信息检索的集合选择问题实验分布式信息检索的集合选择问题实验l语言模型在集合选择中的平滑实验集合选择结果对平滑参数不敏感已取得的阶段性

26、成果已取得的阶段性成果l分布式信息检索文档划分问题建模分布式信息检索文档划分问题建模l分布式信息检索文档划分模型的最优解求解算法分布式信息检索文档划分模型的最优解求解算法 l基于链接的分布式信息检索文档划分算法基于链接的分布式信息检索文档划分算法 l多种文档检索算法在分布式信息检索中集合选择多种文档检索算法在分布式信息检索中集合选择问题的应用分析问题的应用分析 下一步的工作计划下一步的工作计划l在文档集合划分方面特征选择方面进行一些探索降低基于内容文档划分方法的计算难度l考虑划分、集合选择、单数据集合检索、结果合并集合过程因素相融合的统一分布式文档权重计算模型打破现在的各部分相对孤立的方式，争取构建一种综合多方面因素的文档权重计算模型谢谢！谢谢！