《海量网页集合的分析与处理：机遇、挑战与实例.ppt》由会员分享，可在线阅读，更多相关《海量网页集合的分析与处理：机遇、挑战与实例.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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科学采样（对网络数据而言，比较难；也有量的要求）n尽量完整（普
3、遍的实践）海量网页集合的分析与处理 机遇、挑战与实例有效的网络信息处理研究需要在大规模数据上开展才有意义一个碰巧“比较准确”的例子o有意思，但并没有科学依据o在科学的意义上，我们有理由怀疑任何ad hoc型的“网络民意”调查结果海量网页集合的分析与处理 机遇、挑战与实例关于网络信息（网页）的数量o世界上不少人关心n专门的网站，n隔几年会有一篇论文发表，介绍一次新的估计oS.Lawrence and C.L.Giles,“Accessibility of information on the web”.Nature,400:107109,1999.(800 million)oA.Gulli an
4、d A.Signorini,“The Indexable Web is More than 11.5 billion pages”,WWW 2005oCNNIC从2002开始每年发布一次中国网页数量nCrawl和调查相结合o我在2002年做了一个中国静态网页数量增长模型n李晓明，“对中国曾有过静态网页数的一种估计”，北京大学学报，2003年5月海量网页集合的分析与处理 机遇、挑战与实例中国（静态）Web的成长o1995 50万o1996 200万o1997 230万o1998 410万o1999 820万o2000 2640万o2001 5000万万o2002 1.03亿（1.05亿）o200
5、3 2.11亿（2.26亿）o2004 4.35亿（4.66亿）o2005 8.94亿（9.47亿）o2006 18.4亿o2007 37.8亿o2008 77.7亿网页在一定时间 t内被删除的概率：左边结果对应u=0.7对我们的启示o网络信息量已经十分巨大，若要对它形成某种一般性结论，或者一般性的服务，也必须基于足够大的一个信息集合n“天网搜索”在2002年前后的变化，以及“天网收藏”（中国网络信息博物馆）与时俱进地诞生，然后又有“天网荟萃”的尝试（2008）海量网页集合的分析与处理 机遇、挑战与实例网络信息处理的基础价效分析（1）oCost-effectiveness？计算机技术与产业的发
6、展，对处理大规模网页信息给我们带来了哪些基本的能力o2009年，若我们有30,000元，能做到的配置n10GB内存n1TB硬盘n1000Mbps网络连接o能干什么？n每天能从网上搜集1000万篇网页n能存放5000万篇网页海量网页集合的分析与处理 机遇、挑战与实例天网收藏：中国网络信息博物馆o北京大学网络实验室，基于天网搜索的技术，从2001年开始，系统地搜集并长期存储中国互联网上的网页o迄今，已经搜藏有近40亿网页，涉及上千万个网站，超过40TB存储量o而且，其信息量仍然在以每天12百万网页的速度增长o提供历史网页浏览服务示例：InfoMall界面示例：输入示例：新浪链接保持继续保持链接中国
7、网络信息博物馆（天网收藏）的存在形式中国网络信息博物馆（天网收藏）的存在形式 在线服务 近线备份 离线备份海量网页集合的分析与处理 机遇、挑战与实例构建天网收藏的体会o网络信息搜集可达到非常高的“raw power”n轻易地，每天上千万网页o随意大量地搜集容易，指定目标地覆盖难n区域（中国，教育网，），主题o天网收藏：典型的长尾现象（价值分布）n大量“垃圾”，不乏“珍品”n（与Web一样）o挑战：如何科学的评价搜得的信息集合？网络信息处理的基础价效分析（2）o还是那样一台3万元的计算机n链接提取 每分钟10,000篇网页n基于关键词的网页过滤 每分钟10,000篇网页n噪音消除 每分钟1000
8、篇网n实体提取 每分钟1000篇网页o人物名，机构名，时间，地点，等等n实体关系发现 每分钟4000篇网页n消重 每分钟1000篇网页海量网页集合的分析与处理 机遇、挑战与实例-我们可能问-o如何能达到这样的能力？n以“消重”为例o有了那些基本能力可以做些什么？n以计算中国Web的形状为例n而高效的消重技术又可以成为一种新型的搜索服务的基础o我们可以认识到nGoogle的GFS/MapReduce/BigTable是对大规模网络文本处理共性模式的支持n提炼出共性基本操作，予以高效实现也具有重要意义海量网页集合的分析与处理 机遇、挑战与实例大规模网页消重：转载版本的发现与聚类o问题：给你一个4亿
9、文章型网页的集合，10台计算机。要花多少时间能将它划分成相似网页的子集，达到可以接受的召回率和精度？o“相似文档的检测”是一个“古老的”话题，人们已经而且还在不断设计算法。但注意到我们定义这个问题的时候并不是“微观地看”n给定两篇网页，如何又好又快地判断它们是否相似o而是考虑一个整体的任务，是一个宏观的目标，就可能在对微观算法问题的处理上有不同的选择考虑。目前在相似文档检测方面的基本方法o基于词语向量空间的ncosinen文档的相似性由词语频率向量的cosine度量o基于概率的nshingling，simhashn文档的相似性由基于指纹（fingerprint）的“可能相似的概率”度量o它们的
10、基本优点：速度快n给定文档A和B，算法的复杂性=O(|A|+|B|)o缺点：判别准则不够直接，因而召回率和精度还有很大改进空间什么是“更直接的”判别准则？o最长公共子串（longest common subsequence,LCS）A=abcabba B=cbabacLCS=caba基于LCS的相似性度量准则：主要挑战是什么？求LCS的效率o给定文字串A和B，直接了当（“蛮干”）的LCS算法复杂性很高o而且理论上我们需要对4亿个网页两两相比较，时间会很长很长很长！n如果比较两篇网页需要1秒钟，4亿篇两两比较需要8*1016秒，约1012天！两种自然的解困思路o寻找一种比“蛮干”更好的计算LCS
11、的算法o分治 采用一种两阶段判别法解决组合爆炸问题n第一阶段：将原始集合预先（快速）划分成具有某种性质（很可能相似）的一些子集n第二阶段：让相似性的两两比较只在子集中进行（不进行跨子集的比较）n（这样，最初的划分质量很重要）针对这两方面考虑的基本决定o利用Myer的计算文档差别的算法（Linux diff）来求 LCS(A,B)。nD:A和B之间的最短编辑距离。A和B越相似，D就越小。o将原始集合预划分成“可能相似”的子集。n这样，D可能就比较小，从而有利于减少Myer算法的执行时间。实验o数据集n天网收藏中的4.3亿文章型网页o评测指标n精度n召回率n效率，在6台计算机群上实际执行的结果o比
12、较对象nsimhash（Charikar,2002）ncosine第一阶段后，得到4600万可能相似网页子集。第二阶段将它们进一步分成了6800万个相似子集。评测o从6800万相似网页集合中随机抽样1000个集合进行人工评测o对于每一个抽样集合，我们确定一个代表元素（在集合中有最多真相似（即人工判定为相似）的元素）RP o精度和召回率的定义：结果召回率以simhash为相对基准计算LCS，实验发现取r=0.28较好（显然，这与数据集有关）于是o用6台机器，花120小时，我们将4.3亿网页集合划分成了6800万个相似网页子集，其精度和召回率均好于公认较好算法的结果（性能相当）o为什么精度会高？n
13、我们采用了LCS作为判据，直觉上，它就是反映两个文档相似情况的n其他算法（simhash,shingling）本质上都是用“相似的概率”作为判据，是间接的o为什么性能也不错？nMyer算法和分治方法，加上在实现中的细节处理计算中国万维网的“形状”o网络信息“形状”是它的基本特点之一，也是每隔几年就有人发表新的研究成果的。计算Web结构的一个例子o2006年1-2月间执行了一次比较彻底的搜集，得到8.3亿网页（在同样的时间段，在百度的协助下，CNNIC报告的是9.47亿）n搜集能力的体现o基于该网页集合，构造了一个巨大的有向图（8.3亿节点），对应超过400GB数据量n链接提取能力的体现o在16
14、节点的机群上运行一个结构发现算法，得到了相应的成分数据n变随机访问为多次顺序访问（磁盘）SCC44.10%IN25.50%OUT14.60%TENDRILS15.80%算法流程o用邻接表(adjacency list)表达8.3亿节点的图，对应顺序磁盘文件o选几个肯定在SCC中的网页作为种子，例如新浪首页o宽度优先向前搜索（BFS forward）直到收敛，得到节点集合FSo还是从种子开始，宽度优先向后搜索（BFS backward）直到收敛，得到节点集合BSoFS 和 BS 的交集就是 SCCoFS SCC is OUT；BS SCC is INo从FS and BS的并集开始做无向BFS，
15、得WCC oTotal WCC is the DISKsoWCC SCC is the TENDRILs天网收藏+网页消重（聚类）历史信息搜索o想象我们到了2050年n问题一：关于三峡大坝，自酝酿到建成，历经数年，一定有各种观点和争论，我想研究一下其中的沿革。哪里找得到有关材料？o国图，翻旧报纸，查有关文献资料；（需要一个月吧）。n问题二：“超女现象”曾经在中国风靡一时，据说有个叫李宇春的最后脱颖而出，当时关于她有哪些报道呢？基于天网收藏的事件报道历史搜索引擎索引的数据输出排序用户普通搜索 引擎各种网页在爬取时得到的 网页清单 按相关性普通百姓基于天网 收藏的搜索引擎文章型网页历史网页清单按照
16、时间社会科学研究人员o与普通搜索引擎的比较事件报道历史搜索引擎这背后是2001年以来，中国网上曾经出现过的4.3亿篇文章型网页，分成了6300万个转载组（相当于这么多篇不相同的文章。目前Wikipedia有多少文章300万）事件报道历史这样一个搜索引擎的建立过程oStep 1:取天网大全中25亿网页oStep 2:从中挑出“文章型网页”，大约4.3亿oStep 3:将这4.3亿篇文章型网页划分成了6800万转载网页集oStep 4:在每一个集合中确定最早的发表时间oStep 5:建立索引，提供查询服务重要事件信息的综合展示应用o天网荟萃2008北京奥运会（WebDigest Beijing O
17、lympics）o关注100个重要的网站（不同的省份）o每天的信息（搜集并留下来）o多层面的展示n时间上的积累n实体关系的分析n信息强度的变化o（实体及其关系的提取与分析能力的体现）WebDigest Beijing OlympicsInformation about an athlete关于一个运动员的舆论的变化August 8 August 10 August 14August 18 August 22 August 26天网荟萃 2008北京奥运会的运行o4pm 12pm,网页爬取 12百万o12pm 2am,过滤出奥运网页o2am 8am,网页中的噪音消除o8am 10am,实体提取o
18、10am 12am,实体关系发现o12am 2pm,建索引，数据融合o2pm:提供服务o（显然，这样的服务有趣，但信息不一定可靠）结束语（summary）o基于实际数据的评测和验证，是网络信息处理方法和技术研究的基本方法（论）o数据的代表性是一个基本挑战n网络难以实现科学抽样尽量接近全体（不要与全体相比太少）海量网络信息处理（效率很重要）o计算机技术与产品的发展带来了高价效（cost-effectiveness）处理海量网络信息的基本能力o对于特定的研究或应用目标，提高方法与技术的实施效率不仅十分必要，而且也有很大的空间n这也就是我们研究工作的另一个可能的维度所在海量网页集合的分析与处理 机遇、挑战与实例