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

海量网页集合的分析与处理2009年8月30日第三届中国语义万维网研讨会—

机遇、挑战与实例1提纲引子一则广告关于“基于真实数据的研究”的一点认识网络信息（网页）量面向网络文本信息处理的计算机技术基本能力及其利用两个例子中国万维网的形状（）大规模网页集合的消重（CIKM2008）结束一则广告—最近译的一本小书基于数据分析，描述了万维网上若干重要的规律性模式(powerlaw,congestion,etc.)；通过对人们访问网络信息（分布式）行为的建模，形成l了对上述模式的理解（即为什么会形成那样的模式）；基于上述，提出了几点可能改善网络信息访问效率的建议。

大量数据的收集与分析是本书成果的基础现象道理应用对“基于真实数据的研究”的认识什么是“真实的数据”？仅“源于实际”还不够，还要有“代表性”在数据上能够开展的两类研究工作方法与技术（例如分类、聚类、信息提取）数据集=训练集+测试集数据集需不需要有“代表性”？（过程+参数）关于数据所反映事物的性质（结论、规律）要求数据集具有代表性更是显然的对数据代表性的追求科学采样（对网络数据而言，比较难；也有量的要求）尽量完整（普遍的实践）有效的网络信息处理研究需要在大规模数据上开展才有意义一个碰巧“比较准确”的例子有意思，但并没有科学依据在科学的意义上，我们有理由怀疑任何adhoc型的“网络民意”调查结果关于网络信息（网页）的数量世界上不少人关心专门的网站，隔几年会有一篇论文发表，介绍一次新的估计S.LawrenceandC.L.Giles,“Accessibilityofinformationon

theweb”.Nature,400:107–109,1999.

(800million)A.Gulliand

A.Signorini,

“TheIndexableWebisMorethan11.5billionpages”,

WWW

2005CNNIC从2002开始每年发布一次中国网页数量Crawl和调查相结合我在2002年做了一个中国静态网页数量增长模型李晓明，“对中国曾有过静态网页数的一种估计”，《北京大学学报》，2003年5月中国（静态）Web的成长1995

–

50万1996

–

200万1997

–

230万1998

–

410万1999

–

820万2000

–

2640万2001–5000万2002

–

1.03亿（1.05亿）2003

–

2.11亿（2.26亿）2004

–

4.35亿（4.66亿）2005

–

8.94亿（9.47亿）2006

–

18.4亿2007

–

37.8亿2008

–

77.7亿网页在一定时间t内被删除的概率：左边结果对应u=0.77对我们的启示网络信息量已经十分巨大，若要对它形成某种一般性结论，或者一般性的服务，也必须基于足够大的一个信息集合“天网搜索”在2002年前后的变化，以及“天网收藏”（中国网络信息博物馆）与时俱进地诞生，然后又有“天网荟萃”的尝试（2008）网络信息处理的基础价效分析（1）Cost-effectiveness？计算机技术与产业的发展，对处理大规模网页信息给我们带来了哪些基本的能力2009年，若我们有30,000元，能做到的配置10GB内存1TB硬盘1000Mbps网络连接能干什么？每天能从网上搜集1000万篇网页能存放5000万篇网页天网收藏：中国网络信息博物馆北京大学网络实验室，基于天网搜索的技术，从2001年开始，系统地搜集并长期存储中国互联网上的网页迄今，已经搜藏有近40亿网页，涉及上千万个网站，超过40TB存储量而且，其信息量仍然在以每天1~2百万网页的速度增长提供历史网页浏览服务10示例：InfoMall界面11示例：输入12示例：2002.1.18新浪13链接保持14继续保持链接15中国网络信息博物馆（天网收藏）的存在形式在线服务近线备份离线备份16构建天网收藏的体会网络信息搜集可达到非常高的“rawpower”轻易地，每天上千万网页随意大量地搜集容易，指定目标地覆盖难区域（中国，教育网，…），主题天网收藏：典型的长尾现象（价值分布）大量“垃圾”，不乏“珍品”（与Web一样）挑战：如何科学的评价搜得的信息集合？网络信息处理的基础价效分析（2）还是那样一台3万元的计算机链接提取–

每分钟10,000篇网页基于关键词的网页过滤–

每分钟10,000篇网页噪音消除–

每分钟1000篇网实体提取–

每分钟1000篇网页人物名，机构名，时间，地点，等等实体关系发现–

每分钟4000篇网页消重–

每分钟1000篇网页我们可能问如何能达到这样的能力？以“消重”为例有了那些基本能力可以做些什么？以计算中国Web的形状为例而高效的消重技术又可以成为一种新型的搜索服务的基础我们可以认识到Google的GFS/MapReduce/BigTable是对大规模网络文本处理共性模式的支持提炼出共性基本操作，予以高效实现也具有重要意义大规模网页消重：转载版本的发现与聚类问题：给你一个4亿文章型网页的集合，10台计算机。要花多少时间能将它划分成相似网页的子集，达到可以接受的召回率和精度？“相似文档的检测”是一个“古老的”话题，人们已经而且还在不断设计算法。但注意到我们定义这个问题的时候并不是“微观地看”给定两篇网页，如何又好又快地判断它们是否相似而是考虑一个整体的任务，是一个宏观的目标，就可能在对微观算法问题的处理上有不同的选择考虑。20目前在相似文档检测方面的基本方法基于词语向量空间的cosine文档的相似性由词语频率向量的cosine度量基于概率的shingling，simhash文档的相似性由基于指纹（fingerprint）的“可能相似的概率”度量它们的基本优点：速度快给定文档A和B，算法的复杂性=O(|A|+|B|)缺点：判别准则不够直接，因而召回率和精度还有很大改进空间21什么是“更直接的”判别准则？最长公共子串（longestcommonsubsequence,LCS）A=abcabbaB=cbabacLCS=caba基于LCS的相似性度量准则：22主要挑战是什么？求LCS的效率给定文字串A和B，直接了当（“蛮干”）的LCS算法复杂性很高而且理论上我们需要对4亿个网页两两相比较，时间会很长很长很长！如果比较两篇网页需要1秒钟，4亿篇两两比较需要8*1016秒，约1012天！23两种自然的解困思路寻找一种比“蛮干”更好的计算LCS的算法分治—

采用一种两阶段判别法解决组合爆炸问题第一阶段：将原始集合预先（快速）划分成具有某种性质（很可能相似）的一些子集第二阶段：让相似性的两两比较只在子集中进行（不进行跨子集的比较）（这样，最初的划分质量很重要）24针对这两方面考虑的基本决定利用Myer的计算文档差别的算法（Linuxdiff）来求LCS(A,B)。D:A和B之间的最短编辑距离。A和B越相似，D就越小。将原始集合预划分成“可能相似”的子集。这样，D可能就比较小，从而有利于减少Myer算法的执行时间。25实验数据集天网收藏中的4.3亿文章型网页评测指标精度召回率效率，在6台计算机群上实际执行的结果比较对象simhash（Charikar,2002）cosine第一阶段后，得到4600万可能相似网页子集。第二阶段将它们进一步分成了6800万个相似子集。26评测从6800万相似网页集合中随机抽样1000个集合进行人工评测对于每一个抽样集合，我们确定一个代表元素（在集合中有最多真相似（即人工判定为相似）的元素）RP精度和召回率的定义：27结果召回率以simhash为相对基准计算LCS，实验发现取r=0.28较好（显然，这与数据集有关）28于是用6台机器，花120小时，我们将4.3亿网页集合划分成了6800万个相似网页子集，其精度和召回率均好于公认较好算法的结果（性能相当）为什么精度会高？我们采用了LCS作为判据，直觉上，它就是反映两个文档相似情况的其他算法（simhash,shingling）本质上都是用“相似的概率”作为判据，是间接的为什么性能也不错？Myer算法和分治方法，加上在实现中的细节处理29计算中国万维网的“形状”网络信息“形状”是它的基本特点之一，也是每隔几年就有人发表新的研究成果的。30计算Web结构的一个例子2006年1-2月间执行了一次比较彻底的搜集，得到8.3亿网页（在同样的时间段，在百度的协助下，CNNIC报告的是9.47亿）搜集能力的体现基于该网页集合，构造了一个巨大的有向图（8.3亿节点），对应超过400GB数据量链接提取能力的体现在16节点的机群上运行一个结构发现算法，得到了相应的成分数据变随机访问为多次顺序访问（磁盘）SCC44.10%IN25.50%OUT14.60%TENDRILS15.80%31算法流程用邻接表(adjacencylist)表达8.3亿节点的图，对应顺序磁盘文件选几个肯定在SCC中的网页作为种子，例如新浪首页宽度优先向前搜索（BFSforward）直到收敛，得到节点集合FS还是从种子开始，宽度优先向后搜索（BFSbackward）直到收敛，得到节点集合BSFS和BS的交集就是

SCCFS–SCCisOUT；BS–SCCisIN从FSandBS的并集开始做无向BFS，得WCCTotal–WCCistheDISKsWCC–SCCistheTENDRILs32天网收藏+网页消重（聚类）历史信息搜索想象我们到了2050年问题一：关于三峡大坝，自酝酿到建成，历经数年，一定有各种观点和争论，我想研究一下其中的沿革。哪里找得到有关材料？国图，翻旧报纸，查有关文献资料；（需要一个月吧）。问题二：“超女现象”曾经在中国风靡一时，据说有个叫李宇春的最后脱颖而出，当时关于她有哪些报道呢？33基于天网收藏的事件报道历史搜索引擎与普通搜索引擎的比较34事件报道历史搜索引擎这背后是2001年以来，中国网上曾经出现过的4.3亿篇文章型网页，分成了6300万个转载组（相当于这么多篇不相同的文章。目前Wikipedia有多少文章—300万）35事件报道历史36这样一个搜索引擎的建立过程Step1:取天网大全中25亿网页Step2:从中挑出“文章型网页”，大约4.3亿Step3:将这4.3亿篇文章型网页划分成了6800万转载网页集Step4:在每一个集合中确定最早的发表时间Step5:建立索引，提供查询服务37重要事件信息的综合展示应用天网荟萃—2008北京奥运会（WebDigest–BeijingOlympics）关注100个重要的网站（不同的省份）每天的信息（搜集并留下来）多层面的展示时间上的积累实体关系的分析信息强度的变化（实体及其关系的提取与分析能力的体现）38WebDigest–BeijingOlympics39Informationaboutanathlete40关于一个运动员的舆论的变化August8August10August14August18August22August2641天网荟萃–2008北京奥运会的运行4pm–12pm,网页爬取1~2百万12pm–2am,过滤出奥运网页2am–8am,网页中的噪音消除8am–10am,实体提取10am–12am,实