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

1、海量網(wǎng)頁集合的分析與處理海量網(wǎng)頁集合的分析與處理李曉明北京大學網(wǎng)絡與信息系統(tǒng)研究所2009年8月30日第三屆中國語義萬維網(wǎng)研討會機遇、挑戰(zhàn)與實例機遇、挑戰(zhàn)與實例 機遇、挑戰(zhàn)與實例提綱o 引子n 一則廣告n 關于“基于真實數(shù)據(jù)的研究”的一點認識o 網(wǎng)絡信息（網(wǎng)頁）量o 面向網(wǎng)絡文本信息處理的計算機技術基本能力及其利用o 兩個例子n 中國萬維網(wǎng)的形狀（WWW 2008）n 大規(guī)模網(wǎng)頁集合的消重（CIKM 2008）o 結束 機遇、挑戰(zhàn)與實例一則廣告 最近譯的一本小書o 基于數(shù)據(jù)分析，描述了萬維網(wǎng)上若干重要的規(guī)律性模式(power law, congestion, etc.)；o 通過對人們訪問網(wǎng)絡

2、信息（分布式）行為的建模，形成l了對上述模式的理解（即為什么會形成那樣的模式）；o 基于上述，提出了幾點可能改善網(wǎng)絡信息訪問效率的建議。o - 大量數(shù)據(jù)的收集與分析是本書成果的基礎現(xiàn)象道理應用 機遇、挑戰(zhàn)與實例對“基于真實數(shù)據(jù)的研究”的認識o 什么是“真實的數(shù)據(jù)”？n 僅“ 源于實際”還不夠，還要有“ 代表性”o 在數(shù)據(jù)上能夠開展的兩類研究工作n 方法與技術（例如分類、聚類、信息提?。﹐ 數(shù)據(jù)集 = 訓練集 + 測試集o 數(shù)據(jù)集需不需要有“代表性”？（過程+參數(shù)）n 關于數(shù)據(jù)所反映事物的性質（結論、規(guī)律）o 要求數(shù)據(jù)集具有代表性更是顯然的o 對數(shù)據(jù)代表性的追求n 科學采樣（對網(wǎng)絡數(shù)據(jù)而言，比較

3、難；也有量的要求）n 盡量完整（普遍的實踐）有效的網(wǎng)絡信息處理研究需要在大規(guī)模數(shù)據(jù)上開展才有意義 機遇、挑戰(zhàn)與實例一個碰巧“比較準確”的例子o 有意思，但并沒有科學依據(jù)o 在科學的意義上，我們有理由懷疑任何ad hoc型的“網(wǎng)絡民意”調(diào)查結果 機遇、挑戰(zhàn)與實例關于網(wǎng)絡信息（網(wǎng)頁）的數(shù)量o 世界上不少人關心n 專門的網(wǎng)站http:/，n 隔幾年會有一篇論文發(fā)表，介紹一次新的估計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開始每年發(fā)布一次中國網(wǎng)頁數(shù)量n Crawl和調(diào)查相結合o 我在2002年做了一個中國靜態(tài)網(wǎng)頁數(shù)量增長模型n 李曉明，“對中國曾有過靜態(tài)網(wǎng)頁數(shù)的一種估計”，北京大學學報，2003年5月 機遇、挑戰(zhàn)與實例中國（靜態(tài)）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)(網(wǎng)頁在一定時間 t內(nèi)被刪除的概率：左邊結果對應u = 0.7 機遇、挑戰(zhàn)與實例對我們的啟示o 網(wǎng)絡信息量已經(jīng)十分巨大，若要對它形成某種一般性結論，或者一般性的服務，也必須基于足夠大的一個信息集合n “天網(wǎng)搜索”在2002年前后的變化，以及“天網(wǎng)收藏”（中國網(wǎng)絡信息博物館）與時俱進地誕生，然后又有“天網(wǎng)薈萃”的嘗試（2008） 機遇、挑戰(zhàn)與實例網(wǎng)絡信息處理的基礎價效分析（1）o Cost-effecti

6、veness？計算機技術與產(chǎn)業(yè)的發(fā)展，對處理大規(guī)模網(wǎng)頁信息給我們帶來了哪些基本的能力o 2009年，若我們有30,000元，能做到的配置n10GB內(nèi)存n1TB硬盤n1000Mbps網(wǎng)絡連接o 能干什么？n 每天能從網(wǎng)上搜集1000萬篇網(wǎng)頁n 能存放5000萬篇網(wǎng)頁 機遇、挑戰(zhàn)與實例天網(wǎng)收藏：中國網(wǎng)絡信息博物館o 北京大學網(wǎng)絡實驗室，基于天網(wǎng)搜索的技術，從2001年開始，系統(tǒng)地搜集并長期存儲中國互聯(lián)網(wǎng)上的網(wǎng)頁o 迄今，已經(jīng)搜藏有近40億網(wǎng)頁，涉及上千萬個網(wǎng)站，超過40TB存儲量o 而且，其信息量仍然在以每天12百萬網(wǎng)頁的速度增長o 提供歷史網(wǎng)頁瀏覽服務 機遇、挑戰(zhàn)與實例示例：InfoMall界面

7、 機遇、挑戰(zhàn)與實例示例：輸入 機遇、挑戰(zhàn)與實例示例：2002.1.18新浪 機遇、挑戰(zhàn)與實例鏈接保持 機遇、挑戰(zhàn)與實例繼續(xù)保持鏈接 機遇、挑戰(zhàn)與實例中國網(wǎng)絡信息博物館（天網(wǎng)收藏）的存在形式中國網(wǎng)絡信息博物館（天網(wǎng)收藏）的存在形式 在線服務 近線備份 離線備份 機遇、挑戰(zhàn)與實例構建天網(wǎng)收藏的體會o 網(wǎng)絡信息搜集可達到非常高的“raw power”n 輕易地，每天上千萬網(wǎng)頁o 隨意大量地搜集容易，指定目標地覆蓋難n 區(qū)域（中國，教育網(wǎng)，），主題o 天網(wǎng)收藏：典型的長尾現(xiàn)象（價值分布）n 大量“垃圾”，不乏“珍品”n （與Web一樣）o 挑戰(zhàn)：如何科學的評價搜得的信息集合？ 機遇、挑戰(zhàn)與實例網(wǎng)絡信息

8、處理的基礎價效分析（2）o 還是那樣一臺3萬元的計算機n 鏈接提取 每分鐘10,000篇網(wǎng)頁n 基于關鍵詞的網(wǎng)頁過濾 每分鐘10,000篇網(wǎng)頁n 噪音消除 每分鐘1000篇網(wǎng)n 實體提取 每分鐘1000篇網(wǎng)頁o 人物名，機構名，時間，地點，等等n 實體關系發(fā)現(xiàn) 每分鐘4000篇網(wǎng)頁n 消重 每分鐘1000篇網(wǎng)頁 機遇、挑戰(zhàn)與實例- 我們可能問 -o 如何能達到這樣的能力？n 以“消重”為例o 有了那些基本能力可以做些什么？n 以計算中國Web的形狀為例n 而高效的消重技術又可以成為一種新型的搜索服務的基礎o 我們可以認識到n Google的GFS/MapReduce/BigTable是對大規(guī)模

9、網(wǎng)絡文本處理共性模式的支持n 提煉出共性基本操作，予以高效實現(xiàn)也具有重要意義 機遇、挑戰(zhàn)與實例大規(guī)模網(wǎng)頁消重：轉載版本的發(fā)現(xiàn)與聚類o 問題：給你一個4億文章型網(wǎng)頁的集合，10臺計算機。要花多少時間能將它劃分成相似網(wǎng)頁的子集，達到可以接受的召回率和精度？o “相似文檔的檢測”是一個“古老的”話題，人們已經(jīng)而且還在不斷設計算法。但注意到我們定義這個問題的時候并不是“微觀地看”n 給定兩篇網(wǎng)頁，如何又好又快地判斷它們是否相似o 而是考慮一個整體的任務，是一個宏觀的目標，就可能在對微觀算法問題的處理上有不同的選擇考慮。 機遇、挑戰(zhàn)與實例目前在相似文檔檢測方面的基本方法o 基于詞語向量空間的ncosin

10、en文檔的相似性由詞語頻率向量的cosine度量o 基于概率的nshingling，simhashn文檔的相似性由基于指紋（fingerprint）的“可能相似的概率”度量o 它們的基本優(yōu)點：速度快n給定文檔A和B，算法的復雜性=O(|A|+|B|)o 缺點：判別準則不夠直接，因而召回率和精度還有很大改進空間 機遇、挑戰(zhàn)與實例什么是“更直接的”判別準則？o 最長公共子串（longest common subsequence, LCS）A = abcabba B = cbabacLCS = caba基于LCS的相似性度量準則：主要挑戰(zhàn)是什么？ 求LCS的效率o 給定文字串A和B，直接了當（“蠻干

11、”）的LCS算法復雜性很高o 而且理論上我們需要對4億個網(wǎng)頁兩兩相比較，時間會很長很長很長！n 如果比較兩篇網(wǎng)頁需要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算法的執(zhí)行時間。OABD 機遇、挑戰(zhàn)與實例實驗o 數(shù)據(jù)集n 天網(wǎng)收藏中的4.3億文章型網(wǎng)頁o 評測指標n 精度n 召回率n 效率，在6臺計算機群上實際執(zhí)行的結果o 比較對象n simhash（Charikar, 2002）n cosine第一階段后，得到4600萬可能相似網(wǎng)頁子集。第二階段將它們進一步分成了6800萬個相似子集。評測o 從6800萬相似網(wǎng)頁集合中隨機抽樣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 機遇、挑戰(zhàn)與實例結果召回率以simhash為相對基準計算LC

14、S，實驗發(fā)現(xiàn)取r=0.28較好（顯然，這與數(shù)據(jù)集有關） 機遇、挑戰(zhàn)與實例于是o 用6臺機器，花120小時，我們將4.3億網(wǎng)頁集合劃分成了6800萬個相似網(wǎng)頁子集，其精度和召回率均好于公認較好算法的結果（性能相當）o 為什么精度會高？n 我們采用了LCS作為判據(jù)，直覺上，它就是反映兩個文檔相似情況的n 其他算法（simhash,shingling）本質上都是用“相似的概率”作為判據(jù)，是間接的o 為什么性能也不錯？n Myer算法和分治方法，加上在實現(xiàn)中的細節(jié)處理 機遇、挑戰(zhàn)與實例計算中國萬維網(wǎng)的“形狀”o 網(wǎng)絡信息“形狀”是它的基本特點之一，也是每隔幾年就有人發(fā)表新的研究成果的。計算Web結構的

15、一個例子o 2006年1-2月間執(zhí)行了一次比較徹底的搜集，得到8.3億網(wǎng)頁（在同樣的時間段，在百度的協(xié)助下，CNNIC報告的是9.47億）n搜集能力的體現(xiàn)o 基于該網(wǎng)頁集合，構造了一個巨大的有向圖（ 8.3億節(jié)點），對應超過400GB數(shù)據(jù)量n鏈接提取能力的體現(xiàn)o 在16節(jié)點的機群上運行一個結構發(fā)現(xiàn)算法，得到了相應的成分數(shù)據(jù)n變隨機訪問為多次順序訪問（磁盤）SCC44.10%IN25.50%OUT14.60%TENDRILS15.80% 機遇、挑戰(zhàn)與實例算法流程o 用鄰接表(adjacency list )表達8.3億節(jié)點的圖，對應順序磁盤文件o 選幾個肯定在SCC中的網(wǎng)頁作為種子，例如新浪首頁

16、o 寬度優(yōu)先向前搜索（BFS forward）直到收斂，得到節(jié)點集合FSo 還是從種子開始，寬度優(yōu)先向后搜索（BFS backward）直到收斂，得到節(jié)點集合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 機遇、挑戰(zhàn)與實例天網(wǎng)收藏+網(wǎng)頁消重（聚類）歷史信息搜索o 想象我們到了2050年n 問題一：關于三峽大壩，自醞釀到建成，歷經(jīng)數(shù)年，一定有各種觀點和爭論，我想研究一下其中的沿革。哪里找得到

17、有關材料？o 國圖，翻舊報紙，查有關文獻資料；（需要一個月吧）。n 問題二：“超女現(xiàn)象”曾經(jīng)在中國風靡一時，據(jù)說有個叫李宇春的最后脫穎而出，當時關于她有哪些報道呢？基于天網(wǎng)收藏的事件報道歷史搜索引擎http:/索引的數(shù)據(jù)輸出排序用戶普通搜索 引擎各種網(wǎng)頁在爬取時得到的 網(wǎng)頁清單 按相關性普通百姓基于天網(wǎng) 收藏的搜索引擎文章型網(wǎng)頁歷史網(wǎng)頁清單按照時間社會科學研究人員o 與普通搜索引擎的比較 機遇、挑戰(zhàn)與實例事件報道歷史搜索引擎這背后是2001年以來，中國網(wǎng)上曾經(jīng)出現(xiàn)過的4.3億篇文章型網(wǎng)頁，分成了6300萬個轉載組（相當于這么多篇不相同的文章。目前Wikipedia有多少文章300萬） 機遇、挑

18、戰(zhàn)與實例事件報道歷史 機遇、挑戰(zhàn)與實例這樣一個搜索引擎的建立過程o Step 1: 取天網(wǎng)大全中25億網(wǎng)頁o Step 2: 從中挑出“文章型網(wǎng)頁”，大約4.3億o Step 3: 將這4.3億篇文章型網(wǎng)頁劃分成了6800萬轉載網(wǎng)頁集o Step 4: 在每一個集合中確定最早的發(fā)表時間o Step 5: 建立索引，提供查詢服務 機遇、挑戰(zhàn)與實例重要事件信息的綜合展示應用o 天網(wǎng)薈萃2008北京奧運會（WebDigest Beijing Olympics）o 關注100個重要的網(wǎng)站（不同的省份）o 每天的信息（搜集并留下來）o 多層面的展示n 時間上的積累n 實體關系的分析n 信息強度的變化o （實體及其關系的提取與分析能力的體現(xiàn)） 機遇、挑戰(zhàn)與實例WebDigest Beijing Olympics 機遇、挑戰(zhàn)與實例Information abou