海量网页集合的分析与处理：机遇、挑战与实例-李晓明完整

1、海量网页集合的分析与处理海量网页集合的分析与处理李晓明北京大学网络与信息系统研究所2009年8月30日第三届中国语义万维网研讨会机遇、挑战与实例机遇、挑战与实例 机遇、挑战与实例提纲o 引子n 一则广告n 关于“基于真实数据的研究”的一点认识o 网络信息（网页）量o 面向网络文本信息处理的计算机技术基本能力及其利用o 两个例子n 中国万维网的形状（WWW 2008）n 大规模网页集合的消重（CIKM 2008）o 结束 机遇、挑战与实例一则广告 最近译的一本小书o 基于数据分析，描述了万维网上若干重要的规律性模式(power law, congestion, etc.)；o 通过对人们访问网络

2、信息（分布式）行为的建模，形成l了对上述模式的理解（即为什么会形成那样的模式）；o 基于上述，提出了几点可能改善网络信息访问效率的建议。o - 大量数据的收集与分析是本书成果的基础现象道理应用 机遇、挑战与实例对“基于真实数据的研究”的认识o 什么是“真实的数据”？n 仅“ 源于实际”还不够，还要有“ 代表性”o 在数据上能够开展的两类研究工作n 方法与技术（例如分类、聚类、信息提取）o 数据集 = 训练集 + 测试集o 数据集需不需要有“代表性”？（过程+参数）n 关于数据所反映事物的性质（结论、规律）o 要求数据集具有代表性更是显然的o 对数据代表性的追求n 科学采样（对网络数据而言，比较

3、难；也有量的要求）n 尽量完整（普遍的实践）有效的网络信息处理研究需要在大规模数据上开展才有意义 机遇、挑战与实例一个碰巧“比较准确”的例子o 有意思，但并没有科学依据o 在科学的意义上，我们有理由怀疑任何ad hoc型的“网络民意”调查结果 机遇、挑战与实例关于网络信息（网页）的数量o 世界上不少人关心n 专门的网站http:/，n 隔几年会有一篇论文发表，介绍一次新的估计oS. Lawrence and C. L. Giles, “Accessibility of information on the web”. Nature, 400:107109, 1999. (800 million

4、)oA. Gulli and A. Signorini, “The Indexable Web is More than 11.5 billion pages”, WWW 2005o CNNIC从2002开始每年发布一次中国网页数量n Crawl和调查相结合o 我在2002年做了一个中国静态网页数量增长模型n 李晓明，“对中国曾有过静态网页数的一种估计”，北京大学学报，2003年5月 机遇、挑战与实例中国（静态）Web的成长o1995 50万o1996 200万o1997 230万o1998 410万o1999 820万o2000 2640万o2001 5000万万o2002 1.03亿（1.

5、05亿）o2003 2.11亿（2.26亿）o2004 4.35亿（4.66亿）o2005 8.94亿（9.47亿）o2006 18.4亿o2007 37.8亿o2008 77.7亿tetD1)(网页在一定时间 t内被删除的概率：左边结果对应u = 0.7 机遇、挑战与实例对我们的启示o 网络信息量已经十分巨大，若要对它形成某种一般性结论，或者一般性的服务，也必须基于足够大的一个信息集合n “天网搜索”在2002年前后的变化，以及“天网收藏”（中国网络信息博物馆）与时俱进地诞生，然后又有“天网荟萃”的尝试（2008） 机遇、挑战与实例网络信息处理的基础价效分析（1）o Cost-effecti

6、veness？计算机技术与产业的发展，对处理大规模网页信息给我们带来了哪些基本的能力o 2009年，若我们有30,000元，能做到的配置n10GB内存n1TB硬盘n1000Mbps网络连接o 能干什么？n 每天能从网上搜集1000万篇网页n 能存放5000万篇网页 机遇、挑战与实例天网收藏：中国网络信息博物馆o 北京大学网络实验室，基于天网搜索的技术，从2001年开始，系统地搜集并长期存储中国互联网上的网页o 迄今，已经搜藏有近40亿网页，涉及上千万个网站，超过40TB存储量o 而且，其信息量仍然在以每天12百万网页的速度增长o 提供历史网页浏览服务 机遇、挑战与实例示例：InfoMall界面

7、 机遇、挑战与实例示例：输入 机遇、挑战与实例示例：2002.1.18新浪 机遇、挑战与实例链接保持 机遇、挑战与实例继续保持链接 机遇、挑战与实例中国网络信息博物馆（天网收藏）的存在形式中国网络信息博物馆（天网收藏）的存在形式 在线服务 近线备份 离线备份 机遇、挑战与实例构建天网收藏的体会o 网络信息搜集可达到非常高的“raw power”n 轻易地，每天上千万网页o 随意大量地搜集容易，指定目标地覆盖难n 区域（中国，教育网，），主题o 天网收藏：典型的长尾现象（价值分布）n 大量“垃圾”，不乏“珍品”n （与Web一样）o 挑战：如何科学的评价搜得的信息集合？ 机遇、挑战与实例网络信息

8、处理的基础价效分析（2）o 还是那样一台3万元的计算机n 链接提取 每分钟10,000篇网页n 基于关键词的网页过滤 每分钟10,000篇网页n 噪音消除 每分钟1000篇网n 实体提取 每分钟1000篇网页o 人物名，机构名，时间，地点，等等n 实体关系发现 每分钟4000篇网页n 消重 每分钟1000篇网页 机遇、挑战与实例- 我们可能问 -o 如何能达到这样的能力？n 以“消重”为例o 有了那些基本能力可以做些什么？n 以计算中国Web的形状为例n 而高效的消重技术又可以成为一种新型的搜索服务的基础o 我们可以认识到n Google的GFS/MapReduce/BigTable是对大规模

9、网络文本处理共性模式的支持n 提炼出共性基本操作，予以高效实现也具有重要意义 机遇、挑战与实例大规模网页消重：转载版本的发现与聚类o 问题：给你一个4亿文章型网页的集合，10台计算机。要花多少时间能将它划分成相似网页的子集，达到可以接受的召回率和精度？o “相似文档的检测”是一个“古老的”话题，人们已经而且还在不断设计算法。但注意到我们定义这个问题的时候并不是“微观地看”n 给定两篇网页，如何又好又快地判断它们是否相似o 而是考虑一个整体的任务，是一个宏观的目标，就可能在对微观算法问题的处理上有不同的选择考虑。 机遇、挑战与实例目前在相似文档检测方面的基本方法o 基于词语向量空间的ncosin

10、en文档的相似性由词语频率向量的cosine度量o 基于概率的nshingling，simhashn文档的相似性由基于指纹（fingerprint）的“可能相似的概率”度量o 它们的基本优点：速度快n给定文档A和B，算法的复杂性=O(|A|+|B|)o 缺点：判别准则不够直接，因而召回率和精度还有很大改进空间 机遇、挑战与实例什么是“更直接的”判别准则？o 最长公共子串（longest common subsequence, LCS）A = abcabba B = cbabacLCS = caba基于LCS的相似性度量准则：主要挑战是什么？ 求LCS的效率o 给定文字串A和B，直接了当（“蛮干

11、”）的LCS算法复杂性很高o 而且理论上我们需要对4亿个网页两两相比较，时间会很长很长很长！n 如果比较两篇网页需要1秒钟，4亿篇两两比较需要8*1016秒，约1012天！()O AB两种自然的解困思路o 寻找一种比“蛮干”更好的计算LCS的算法o 分治 采用一种两阶段判别法解决组合爆炸问题n 第一阶段：将原始集合预先（快速）划分成具有某种性质（很可能相似）的一些子集n 第二阶段：让相似性的两两比较只在子集中进行（不进行跨子集的比较）n （这样，最初的划分质量很重要）针对这两方面考虑的基本决定o 利用Myer的计算文档差别的算法（Linux diff）来求 LCS(A,B)。n D: A和B之

12、间的最短编辑距离。A和B越相似，D就越小。o 将原始集合预划分成“可能相似”的子集。n 这样，D可能就比较小，从而有利于减少Myer算法的执行时间。OABD 机遇、挑战与实例实验o 数据集n 天网收藏中的4.3亿文章型网页o 评测指标n 精度n 召回率n 效率，在6台计算机群上实际执行的结果o 比较对象n simhash（Charikar, 2002）n cosine第一阶段后，得到4600万可能相似网页子集。第二阶段将它们进一步分成了6800万个相似子集。评测o 从6800万相似网页集合中随机抽样1000个集合进行人工评测o 对于每一个抽样集合，我们确定一个代表元素（在集合中有最多真相似（即

13、人工判定为相似）的元素）RP o 精度和召回率的定义：the sampled sets# true similar pages of RP in this set# all pages in this set# the sampled setsprecision the sampled sets# true similar pages of RP detected by LCS (Cosine)# true similar pages of RP detected by Simhash# the sampled setsrecall 机遇、挑战与实例结果召回率以simhash为相对基准计算LC

14、S，实验发现取r=0.28较好（显然，这与数据集有关） 机遇、挑战与实例于是o 用6台机器，花120小时，我们将4.3亿网页集合划分成了6800万个相似网页子集，其精度和召回率均好于公认较好算法的结果（性能相当）o 为什么精度会高？n 我们采用了LCS作为判据，直觉上，它就是反映两个文档相似情况的n 其他算法（simhash,shingling）本质上都是用“相似的概率”作为判据，是间接的o 为什么性能也不错？n Myer算法和分治方法，加上在实现中的细节处理 机遇、挑战与实例计算中国万维网的“形状”o 网络信息“形状”是它的基本特点之一，也是每隔几年就有人发表新的研究成果的。计算Web结构的

15、一个例子o 2006年1-2月间执行了一次比较彻底的搜集，得到8.3亿网页（在同样的时间段，在百度的协助下，CNNIC报告的是9.47亿）n搜集能力的体现o 基于该网页集合，构造了一个巨大的有向图（ 8.3亿节点），对应超过400GB数据量n链接提取能力的体现o 在16节点的机群上运行一个结构发现算法，得到了相应的成分数据n变随机访问为多次顺序访问（磁盘）SCC44.10%IN25.50%OUT14.60%TENDRILS15.80% 机遇、挑战与实例算法流程o 用邻接表(adjacency list )表达8.3亿节点的图，对应顺序磁盘文件o 选几个肯定在SCC中的网页作为种子，例如新浪首页

16、o 宽度优先向前搜索（BFS forward）直到收敛，得到节点集合FSo 还是从种子开始，宽度优先向后搜索（BFS backward）直到收敛，得到节点集合BSo FS 和 BS 的交集就是 SCCo FS SCC is OUT；BS SCC is INo 从FS and BS的并集开始做无向BFS，得WCC o Total WCC is the DISKso WCC SCC is the TENDRILs 机遇、挑战与实例天网收藏+网页消重（聚类）历史信息搜索o 想象我们到了2050年n 问题一：关于三峡大坝，自酝酿到建成，历经数年，一定有各种观点和争论，我想研究一下其中的沿革。哪里找得到

17、有关材料？o 国图，翻旧报纸，查有关文献资料；（需要一个月吧）。n 问题二：“超女现象”曾经在中国风靡一时，据说有个叫李宇春的最后脱颖而出，当时关于她有哪些报道呢？基于天网收藏的事件报道历史搜索引擎http:/索引的数据输出排序用户普通搜索 引擎各种网页在爬取时得到的 网页清单 按相关性普通百姓基于天网 收藏的搜索引擎文章型网页历史网页清单按照时间社会科学研究人员o 与普通搜索引擎的比较 机遇、挑战与实例事件报道历史搜索引擎这背后是2001年以来，中国网上曾经出现过的4.3亿篇文章型网页，分成了6300万个转载组（相当于这么多篇不相同的文章。目前Wikipedia有多少文章300万） 机遇、挑

18、战与实例事件报道历史 机遇、挑战与实例这样一个搜索引擎的建立过程o Step 1: 取天网大全中25亿网页o Step 2: 从中挑出“文章型网页”，大约4.3亿o Step 3: 将这4.3亿篇文章型网页划分成了6800万转载网页集o Step 4: 在每一个集合中确定最早的发表时间o Step 5: 建立索引，提供查询服务 机遇、挑战与实例重要事件信息的综合展示应用o 天网荟萃2008北京奥运会（WebDigest Beijing Olympics）o 关注100个重要的网站（不同的省份）o 每天的信息（搜集并留下来）o 多层面的展示n 时间上的积累n 实体关系的分析n 信息强度的变化o （实体及其关系的提取与分析能力的体现） 机遇、挑战与实例WebDigest Beijing Olympics 机遇、挑战与实例Information abou