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 科學采樣（對網絡數據而言，比較

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

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

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

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

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

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

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

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

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

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

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

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