海量網(wǎng)頁(yè)集合的分析與處理：機(jī)遇、挑戰(zhàn)與實(shí)例 李曉明

海量網(wǎng)頁(yè)集合的分析與處理2009年8月30日第三屆中國(guó)語(yǔ)義萬(wàn)維網(wǎng)研討會(huì)—

機(jī)遇、挑戰(zhàn)與實(shí)例1提綱引子一則廣告關(guān)于“基于真實(shí)數(shù)據(jù)的研究”的一點(diǎn)認(rèn)識(shí)網(wǎng)絡(luò)信息（網(wǎng)頁(yè)）量面向網(wǎng)絡(luò)文本信息處理的計(jì)算機(jī)技術(shù)基本能力及其利用兩個(gè)例子中國(guó)萬(wàn)維網(wǎng)的形狀（）大規(guī)模網(wǎng)頁(yè)集合的消重（CIKM2008）結(jié)束一則廣告—最近譯的一本小書(shū)基于數(shù)據(jù)分析，描述了萬(wàn)維網(wǎng)上若干重要的規(guī)律性模式(powerlaw,congestion,etc.)；通過(guò)對(duì)人們?cè)L問(wèn)網(wǎng)絡(luò)信息（分布式）行為的建模，形成l了對(duì)上述模式的理解（即為什么會(huì)形成那樣的模式）；基于上述，提出了幾點(diǎn)可能改善網(wǎng)絡(luò)信息訪問(wèn)效率的建議。

大量數(shù)據(jù)的收集與分析是本書(shū)成果的基礎(chǔ)現(xiàn)象道理應(yīng)用對(duì)“基于真實(shí)數(shù)據(jù)的研究”的認(rèn)識(shí)什么是“真實(shí)的數(shù)據(jù)”？?jī)H“源于實(shí)際”還不夠，還要有“代表性”在數(shù)據(jù)上能夠開(kāi)展的兩類研究工作方法與技術(shù)（例如分類、聚類、信息提?。?shù)據(jù)集=訓(xùn)練集+測(cè)試集數(shù)據(jù)集需不需要有“代表性”？（過(guò)程+參數(shù)）關(guān)于數(shù)據(jù)所反映事物的性質(zhì)（結(jié)論、規(guī)律）要求數(shù)據(jù)集具有代表性更是顯然的對(duì)數(shù)據(jù)代表性的追求科學(xué)采樣（對(duì)網(wǎng)絡(luò)數(shù)據(jù)而言，比較難；也有量的要求）盡量完整（普遍的實(shí)踐）有效的網(wǎng)絡(luò)信息處理研究需要在大規(guī)模數(shù)據(jù)上開(kāi)展才有意義一個(gè)碰巧“比較準(zhǔn)確”的例子有意思，但并沒(méi)有科學(xué)依據(jù)在科學(xué)的意義上，我們有理由懷疑任何adhoc型的“網(wǎng)絡(luò)民意”調(diào)查結(jié)果關(guān)于網(wǎng)絡(luò)信息（網(wǎng)頁(yè)）的數(shù)量世界上不少人關(guān)心專門的網(wǎng)站，隔幾年會(huì)有一篇論文發(fā)表，介紹一次新的估計(jì)S.LawrenceandC.L.Giles,“Accessibilityofinformationon

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

(800million)A.Gulliand

A.Signorini,

“TheIndexableWebisMorethan11.5billionpages”,

WWW

2005CNNIC從2002開(kāi)始每年發(fā)布一次中國(guó)網(wǎng)頁(yè)數(shù)量Crawl和調(diào)查相結(jié)合我在2002年做了一個(gè)中國(guó)靜態(tài)網(wǎng)頁(yè)數(shù)量增長(zhǎng)模型李曉明，“對(duì)中國(guó)曾有過(guò)靜態(tài)網(wǎng)頁(yè)數(shù)的一種估計(jì)”，《北京大學(xué)學(xué)報(bào)》，2003年5月中國(guó)（靜態(tài)）Web的成長(zhǎng)1995

–

50萬(wàn)1996

–

200萬(wàn)1997

–

230萬(wàn)1998

–

410萬(wàn)1999

–

820萬(wàn)2000

–

2640萬(wàn)2001–5000萬(wàn)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億網(wǎng)頁(yè)在一定時(shí)間t內(nèi)被刪除的概率：左邊結(jié)果對(duì)應(yīng)u=0.77對(duì)我們的啟示網(wǎng)絡(luò)信息量已經(jīng)十分巨大，若要對(duì)它形成某種一般性結(jié)論，或者一般性的服務(wù)，也必須基于足夠大的一個(gè)信息集合“天網(wǎng)搜索”在2002年前后的變化，以及“天網(wǎng)收藏”（中國(guó)網(wǎng)絡(luò)信息博物館）與時(shí)俱進(jìn)地誕生，然后又有“天網(wǎng)薈萃”的嘗試（2008）網(wǎng)絡(luò)信息處理的基礎(chǔ)價(jià)效分析（1）Cost-effectiveness？計(jì)算機(jī)技術(shù)與產(chǎn)業(yè)的發(fā)展，對(duì)處理大規(guī)模網(wǎng)頁(yè)信息給我們帶來(lái)了哪些基本的能力2009年，若我們有30,000元，能做到的配置10GB內(nèi)存1TB硬盤1000Mbps網(wǎng)絡(luò)連接能干什么？每天能從網(wǎng)上搜集1000萬(wàn)篇網(wǎng)頁(yè)能存放5000萬(wàn)篇網(wǎng)頁(yè)天網(wǎng)收藏：中國(guó)網(wǎng)絡(luò)信息博物館北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室，基于天網(wǎng)搜索的技術(shù)，從2001年開(kāi)始，系統(tǒng)地搜集并長(zhǎng)期存儲(chǔ)中國(guó)互聯(lián)網(wǎng)上的網(wǎng)頁(yè)迄今，已經(jīng)搜藏有近40億網(wǎng)頁(yè)，涉及上千萬(wàn)個(gè)網(wǎng)站，超過(guò)40TB存儲(chǔ)量而且，其信息量仍然在以每天1~2百萬(wàn)網(wǎng)頁(yè)的速度增長(zhǎng)提供歷史網(wǎng)頁(yè)瀏覽服務(wù)10示例：InfoMall界面11示例：輸入12示例：2002.1.18新浪13鏈接保持14繼續(xù)保持鏈接15中國(guó)網(wǎng)絡(luò)信息博物館（天網(wǎng)收藏）的存在形式在線服務(wù)近線備份離線備份16構(gòu)建天網(wǎng)收藏的體會(huì)網(wǎng)絡(luò)信息搜集可達(dá)到非常高的“rawpower”輕易地，每天上千萬(wàn)網(wǎng)頁(yè)隨意大量地搜集容易，指定目標(biāo)地覆蓋難區(qū)域（中國(guó)，教育網(wǎng)，…），主題天網(wǎng)收藏：典型的長(zhǎng)尾現(xiàn)象（價(jià)值分布）大量“垃圾”，不乏“珍品”（與Web一樣）挑戰(zhàn)：如何科學(xué)的評(píng)價(jià)搜得的信息集合？網(wǎng)絡(luò)信息處理的基礎(chǔ)價(jià)效分析（2）還是那樣一臺(tái)3萬(wàn)元的計(jì)算機(jī)鏈接提取–

每分鐘10,000篇網(wǎng)頁(yè)基于關(guān)鍵詞的網(wǎng)頁(yè)過(guò)濾–

每分鐘10,000篇網(wǎng)頁(yè)噪音消除–

每分鐘1000篇網(wǎng)實(shí)體提取–

每分鐘1000篇網(wǎng)頁(yè)人物名，機(jī)構(gòu)名，時(shí)間，地點(diǎn)，等等實(shí)體關(guān)系發(fā)現(xiàn)–

每分鐘4000篇網(wǎng)頁(yè)消重–

每分鐘1000篇網(wǎng)頁(yè)我們可能問(wèn)如何能達(dá)到這樣的能力？以“消重”為例有了那些基本能力可以做些什么？以計(jì)算中國(guó)Web的形狀為例而高效的消重技術(shù)又可以成為一種新型的搜索服務(wù)的基礎(chǔ)我們可以認(rèn)識(shí)到Google的GFS/MapReduce/BigTable是對(duì)大規(guī)模網(wǎng)絡(luò)文本處理共性模式的支持提煉出共性基本操作，予以高效實(shí)現(xiàn)也具有重要意義大規(guī)模網(wǎng)頁(yè)消重：轉(zhuǎn)載版本的發(fā)現(xiàn)與聚類問(wèn)題：給你一個(gè)4億文章型網(wǎng)頁(yè)的集合，10臺(tái)計(jì)算機(jī)。要花多少時(shí)間能將它劃分成相似網(wǎng)頁(yè)的子集，達(dá)到可以接受的召回率和精度？“相似文檔的檢測(cè)”是一個(gè)“古老的”話題，人們已經(jīng)而且還在不斷設(shè)計(jì)算法。但注意到我們定義這個(gè)問(wèn)題的時(shí)候并不是“微觀地看”給定兩篇網(wǎng)頁(yè)，如何又好又快地判斷它們是否相似而是考慮一個(gè)整體的任務(wù)，是一個(gè)宏觀的目標(biāo)，就可能在對(duì)微觀算法問(wèn)題的處理上有不同的選擇考慮。20目前在相似文檔檢測(cè)方面的基本方法基于詞語(yǔ)向量空間的cosine文檔的相似性由詞語(yǔ)頻率向量的cosine度量基于概率的shingling，simhash文檔的相似性由基于指紋（fingerprint）的“可能相似的概率”度量它們的基本優(yōu)點(diǎn)：速度快給定文檔A和B，算法的復(fù)雜性=O(|A|+|B|)缺點(diǎn)：判別準(zhǔn)則不夠直接，因而召回率和精度還有很大改進(jìn)空間21什么是“更直接的”判別準(zhǔn)則？最長(zhǎng)公共子串（longestcommonsubsequence,LCS）A=abcabbaB=cbabacLCS=caba基于LCS的相似性度量準(zhǔn)則：22主要挑戰(zhàn)是什么？求LCS的效率給定文字串A和B，直接了當(dāng)（“蠻干”）的LCS算法復(fù)雜性很高而且理論上我們需要對(duì)4億個(gè)網(wǎng)頁(yè)兩兩相比較，時(shí)間會(huì)很長(zhǎng)很長(zhǎng)很長(zhǎng)！如果比較兩篇網(wǎng)頁(yè)需要1秒鐘，4億篇兩兩比較需要8*1016秒，約1012天！23兩種自然的解困思路尋找一種比“蠻干”更好的計(jì)算LCS的算法分治—

采用一種兩階段判別法解決組合爆炸問(wèn)題第一階段：將原始集合預(yù)先（快速）劃分成具有某種性質(zhì)（很可能相似）的一些子集第二階段：讓相似性的兩兩比較只在子集中進(jìn)行（不進(jìn)行跨子集的比較）（這樣，最初的劃分質(zhì)量很重要）24針對(duì)這兩方面考慮的基本決定利用Myer的計(jì)算文檔差別的算法（Linuxdiff）來(lái)求LCS(A,B)。D:A和B之間的最短編輯距離。A和B越相似，D就越小。將原始集合預(yù)劃分成“可能相似”的子集。這樣，D可能就比較小，從而有利于減少M(fèi)yer算法的執(zhí)行時(shí)間。25實(shí)驗(yàn)數(shù)據(jù)集天網(wǎng)收藏中的4.3億文章型網(wǎng)頁(yè)評(píng)測(cè)指標(biāo)精度召回率效率，在6臺(tái)計(jì)算機(jī)群上實(shí)際執(zhí)行的結(jié)果比較對(duì)象simhash（Charikar,2002）cosine第一階段后，得到4600萬(wàn)可能相似網(wǎng)頁(yè)子集。第二階段將它們進(jìn)一步分成了6800萬(wàn)個(gè)相似子集。26評(píng)測(cè)從6800萬(wàn)相似網(wǎng)頁(yè)集合中隨機(jī)抽樣1000個(gè)集合進(jìn)行人工評(píng)測(cè)對(duì)于每一個(gè)抽樣集合，我們確定一個(gè)代表元素（在集合中有最多真相似（即人工判定為相似）的元素）RP精度和召回率的定義：27結(jié)果召回率以simhash為相對(duì)基準(zhǔn)計(jì)算LCS，實(shí)驗(yàn)發(fā)現(xiàn)取r=0.28較好（顯然，這與數(shù)據(jù)集有關(guān)）28于是用6臺(tái)機(jī)器，花120小時(shí)，我們將4.3億網(wǎng)頁(yè)集合劃分成了6800萬(wàn)個(gè)相似網(wǎng)頁(yè)子集，其精度和召回率均好于公認(rèn)較好算法的結(jié)果（性能相當(dāng)）為什么精度會(huì)高？我們采用了LCS作為判據(jù)，直覺(jué)上，它就是反映兩個(gè)文檔相似情況的其他算法（simhash,shingling）本質(zhì)上都是用“相似的概率”作為判據(jù)，是間接的為什么性能也不錯(cuò)？Myer算法和分治方法，加上在實(shí)現(xiàn)中的細(xì)節(jié)處理29計(jì)算中國(guó)萬(wàn)維網(wǎng)的“形狀”網(wǎng)絡(luò)信息“形狀”是它的基本特點(diǎn)之一，也是每隔幾年就有人發(fā)表新的研究成果的。30計(jì)算Web結(jié)構(gòu)的一個(gè)例子2006年1-2月間執(zhí)行了一次比較徹底的搜集，得到8.3億網(wǎng)頁(yè)（在同樣的時(shí)間段，在百度的協(xié)助下，CNNIC報(bào)告的是9.47億）搜集能力的體現(xiàn)基于該網(wǎng)頁(yè)集合，構(gòu)造了一個(gè)巨大的有向圖（8.3億節(jié)點(diǎn)），對(duì)應(yīng)超過(guò)400GB數(shù)據(jù)量鏈接提取能力的體現(xiàn)在16節(jié)點(diǎn)的機(jī)群上運(yùn)行一個(gè)結(jié)構(gòu)發(fā)現(xiàn)算法，得到了相應(yīng)的成分?jǐn)?shù)據(jù)變隨機(jī)訪問(wèn)為多次順序訪問(wèn)（磁盤）SCC44.10%IN25.50%OUT14.60%TENDRILS15.80%31算法流程用鄰接表(adjacencylist)表達(dá)8.3億節(jié)點(diǎn)的圖，對(duì)應(yīng)順序磁盤文件選幾個(gè)肯定在SCC中的網(wǎng)頁(yè)作為種子，例如新浪首頁(yè)寬度優(yōu)先向前搜索（BFSforward）直到收斂，得到節(jié)點(diǎn)集合FS還是從種子開(kāi)始，寬度優(yōu)先向后搜索（BFSbackward）直到收斂，得到節(jié)點(diǎn)集合BSFS和BS的交集就是

SCCFS–SCCisOUT；BS–SCCisIN從FSandBS的并集開(kāi)始做無(wú)向BFS，得WCCTotal–WCCistheDISKsWCC–SCCistheTENDRILs32天網(wǎng)收藏+網(wǎng)頁(yè)消重（聚類）歷史信息搜索想象我們到了2050年問(wèn)題一：關(guān)于三峽大壩，自醞釀到建成，歷經(jīng)數(shù)年，一定有各種觀點(diǎn)和爭(zhēng)論，我想研究一下其中的沿革。哪里找得到有關(guān)材料？國(guó)圖，翻舊報(bào)紙，查有關(guān)文獻(xiàn)資料；（需要一個(gè)月吧）。問(wèn)題二：“超女現(xiàn)象”曾經(jīng)在中國(guó)風(fēng)靡一時(shí)，據(jù)說(shuō)有個(gè)叫李宇春的最后脫穎而出，當(dāng)時(shí)關(guān)于她有哪些報(bào)道呢？33基于天網(wǎng)收藏的事件報(bào)道歷史搜索引擎與普通搜索引擎的比較34事件報(bào)道歷史搜索引擎這背后是2001年以來(lái)，中國(guó)網(wǎng)上曾經(jīng)出現(xiàn)過(guò)的4.3億篇文章型網(wǎng)頁(yè)，分成了6300萬(wàn)個(gè)轉(zhuǎn)載組（相當(dāng)于這么多篇不相同的文章。目前Wikipedia有多少文章—300萬(wàn)）35事件報(bào)道歷史36這樣一個(gè)搜索引擎的建立過(guò)程Step1:取天網(wǎng)大全中25億網(wǎng)頁(yè)Step2:從中挑出“文章型網(wǎng)頁(yè)”，大約4.3億Step3:將這4.3億篇文章型網(wǎng)頁(yè)劃分成了6800萬(wàn)轉(zhuǎn)載網(wǎng)頁(yè)集Step4:在每一個(gè)集合中確定最早的發(fā)表時(shí)間Step5:建立索引，提供查詢服務(wù)37重要事件信息的綜合展示應(yīng)用天網(wǎng)薈萃—2008北京奧運(yùn)會(huì)（WebDigest–BeijingOlympics）關(guān)注100個(gè)重要的網(wǎng)站（不同的省份）每天的信息（搜集并留下來(lái)）多層面的展示時(shí)間上的積累實(shí)體關(guān)系的分析信息強(qiáng)度的變化（實(shí)體及其關(guān)系的提取與分析能力的體現(xiàn)）38WebDigest–BeijingOlympics39Informationaboutanathlete40關(guān)于一個(gè)運(yùn)動(dòng)員的輿論的變化August8August10August14August18August22August2641天網(wǎng)薈萃–2008北京奧運(yùn)會(huì)的運(yùn)行4pm–12pm,網(wǎng)頁(yè)爬取1~2百萬(wàn)12pm–2am,過(guò)濾出奧運(yùn)網(wǎng)頁(yè)2am–8am,網(wǎng)頁(yè)中的噪音消除8am–10am,實(shí)體提取10am–12am,實(shí)