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

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

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

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

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

(800million)A.Gulliand

A.Signorini,

“TheIndexableWebisMorethan11.5billionpages”,

WWW

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

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

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

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

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

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

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

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

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