頁面質(zhì)量評估及其在網(wǎng)絡(luò)信息檢索中的應(yīng)用
去偽存真 去粗取精 ——
清華大學(xué)計算機(jī)科學(xué)與技術(shù)系
智能技術(shù)與系統(tǒng)國家重點(diǎn)實驗室
2006年7月，山東，濟(jì)南
去偽存真 去粗取精
問題背景
頁面質(zhì)量評估的相關(guān)工作概述
高質(zhì)量頁面的查詢無關(guān)特征分析
基于學(xué)習(xí)的頁面質(zhì)量評估算法
應(yīng)用展望
去偽存真 去粗取精
問題背景
頁面質(zhì)量評估的相關(guān)工作概述
高質(zhì)量頁面的查詢無關(guān)特征分析
基于學(xué)習(xí)的頁面質(zhì)量評估算法
應(yīng)用展望
問題背景
World Wide Web的出現(xiàn)與發(fā)展
問題背景
Web蘊(yùn)含著多少信息？
How Much Info 工程
由Intel, Microsoft, HP, EMC等公司贊助，UC Berkeley大學(xué)完成
2002年世界上共產(chǎn)生了5Exabyte的數(shù)據(jù)，其中92%的信息存儲于電子介質(zhì)
相當(dāng)于人類歷史上所有說過的話語 所包含的信息量的總和
大部分存儲于Web中，構(gòu)成了Web 中超過150Billion的網(wǎng)絡(luò)頁面
問題背景
Web的發(fā)展帶來了什么？
信息數(shù)量的急劇膨脹
知識的獲取空前簡單與繁榮
Information is no longer a scarce resource - attention is.
(注意力，而不是信息，才是這個時代所稀缺的資源 )
(紐約時報，2005年10月16日)
在信息化時代，知識實際上已經(jīng)不是資源，智慧才是資源。（清華大學(xué)經(jīng)管學(xué)院魏杰教授）
從Web中有效的獲取知識正在成為人們生活與工作的必須技能
高科技企業(yè)員工1/3的時間用于查找資料
由于無法找到有效信息而浪費(fèi)的產(chǎn)值占企業(yè)收入1/5
問題背景
2005年搜索引擎市場的激烈競爭
Google市值的變化舉世關(guān)注
Baidu上市造就數(shù)以百計的百萬富翁
MSN推出新版搜索，MSRA建立搜索研究中心
Yahoo中國重組
主要門戶網(wǎng)站Sohu, Sina, Netease, 騰訊紛紛推出搜索引擎產(chǎn)品
問題背景
最早的網(wǎng)絡(luò)搜索引擎索引系統(tǒng)誕生：Stanford大學(xué), 1995
問題背景：搜索引擎用戶的需求
當(dāng)前面臨的存儲與運(yùn)算需求
每天處理超過2億用戶查詢
近80億頁面索引
問題背景：搜索引擎的索引能力
搜索引擎索引規(guī)模的競爭

問題背景：搜索引擎的索引能力
搜索引擎索引規(guī)模競爭的終結(jié)？
沒有任何一個搜索引擎可以覆蓋互聯(lián)網(wǎng)上的所有資源






2005年9月, Google從首頁去除了頁面索引數(shù)量的信息，并解釋說：“絕對的數(shù)量已經(jīng)不再重要”
問題背景：搜索引擎的索引能力
對中文搜索引擎而言
搜索引擎里每天有400多萬被檢索的關(guān)鍵詞
一般而言不重復(fù)的關(guān)鍵詞會占總數(shù)的30%以內(nèi)
（根據(jù)李彥宏報告的百度狀況）
對于每個關(guān)鍵詞，用戶平均點(diǎn)擊的頁面數(shù)在2頁以內(nèi)
則可以估算如下:
用戶每天使用到的被索引的頁面數(shù)為2400萬個左右
在百度的平均更新周期（1個月）內(nèi)，用戶共可能訪問到的頁面總數(shù)為7.2億個，
少于百度聲稱的索引量（8億）
更少于中文網(wǎng)頁總數(shù)（20億）
問題背景
搜索引擎應(yīng)當(dāng)處理 (存儲、評價、預(yù)處理與后處理)所有的Web頁面么?
數(shù)據(jù)數(shù)量已然非常龐大
網(wǎng)絡(luò)環(huán)境數(shù)據(jù)質(zhì)量堪憂：不可靠、Spam、過時，重復(fù)
不需要，也不可能!
利用頁面質(zhì)量評估定位高質(zhì)量頁面
在用戶查詢之前進(jìn)行  數(shù)據(jù)預(yù)處理階段
使用查詢無關(guān)特征進(jìn)行

問題背景
去偽存真 去粗取精
問題背景
頁面質(zhì)量評估的相關(guān)工作概述
高質(zhì)量頁面的查詢無關(guān)特征分析
基于學(xué)習(xí)的頁面質(zhì)量評估算法
應(yīng)用展望
頁面質(zhì)量評估相關(guān)工作概述
按照粒度不同
宏觀粒度的質(zhì)量評估
去除無用頁面 / 定位有用頁面
清理“全局垃圾”

微觀粒度的質(zhì)量評估
去除頁面中的無用部分 / 找出頁面中最有用的部分
清理“局部垃圾”
頁面質(zhì)量評估相關(guān)工作概述
宏觀粒度的頁面質(zhì)量評估
目的：找出對用戶檢索信息有用的頁面
當(dāng)前的研究重點(diǎn)：Web鏈接結(jié)構(gòu)分析
如果存在超鏈接L從頁面P(source)指向頁面P(destiny)，則P(source)與P(destiny)之間滿足：
假設(shè)1：（內(nèi)容推薦假設(shè)）頁面P(source)的作者推薦頁面P(destiny)的內(nèi)容，且利用L的鏈接文本內(nèi)容對P(destiny)進(jìn)行描述。
假設(shè)2：（主題相關(guān)假設(shè)）被超鏈接連接的兩個頁面P(source)與P(destiny)比隨機(jī)抽取的兩個頁面有更大的概率有內(nèi)容相關(guān)性。
PageRank（Google）, HITS（Kleinberg.）及眾多的改進(jìn)算法
頁面質(zhì)量評估相關(guān)工作概述
微觀粒度的頁面質(zhì)量評估
目的：找出對用戶檢索信息有用的頁面的某個部分
去除特定垃圾信息（利用機(jī)器學(xué)習(xí)方法和一定量的訓(xùn)練）
去除廣告條（Davison et. al.）
去除頁面中的無關(guān)鏈接與垃圾鏈接（Kushmerick et. al.）
頁面分塊模型
依據(jù)語料統(tǒng)計信息計算頁面塊的信息量（Lin et. al.）
基于模板頻度檢測構(gòu)建站點(diǎn)模板（Yossef et. al. Yi et. al.）
基于頁面塊的絕對位置和機(jī)器學(xué)習(xí)方法計算塊的重要性（VIsion Based Page Segmentation, VIPS, MSRA）
頁面質(zhì)量評估相關(guān)工作概述
微觀粒度的質(zhì)量評估示例（頁面分塊）

頁面質(zhì)量評估相關(guān)工作概述
頁面質(zhì)量評估的研究現(xiàn)狀
微觀粒度
具有數(shù)據(jù)挖掘方面研究的積累（數(shù)據(jù)預(yù)處理、數(shù)據(jù)清理等）
相對比較成熟完善
宏觀粒度
搜索引擎競價排名機(jī)制的引入，帶來了大量的鏈接垃圾
內(nèi)容推薦和主題相關(guān)假設(shè)受到挑戰(zhàn)
過多關(guān)注頁面自身的特性，忽略用戶的實際需求
只重視鏈接結(jié)構(gòu)特征，忽略頁面其他類型的查詢無關(guān)特征
頁面質(zhì)量評估的研究現(xiàn)狀
頁面質(zhì)量評估應(yīng)當(dāng)涉及到鏈接關(guān)系之外的特征信息
PageRank only uses the link structure of the web to estimate page quality. It seems to us that a better estimate of the quality of a page requires additional sources of information.
Monika R. Henzinger, Research Director of Google
我們的理解：
對于檢索系統(tǒng)而言，頁面質(zhì)量的最根本評價不是由諸如頁面在鏈接結(jié)構(gòu)圖中的重要程度這樣的特征來決定的。
能否滿足用戶獲取信息的需要是頁面質(zhì)量評價的根本出發(fā)點(diǎn)。
研究用戶需要什么，而非假設(shè)用戶需要什么
頁面質(zhì)量評估：我們的做法
有可能成為用戶檢索目標(biāo)的頁面才是高質(zhì)量的
用戶需要什么？
反映在用戶查詢的目標(biāo)頁面中
高質(zhì)量頁面：可能成為用戶檢索目標(biāo)的Web頁面
矛盾：
查詢目標(biāo)頁面是與查詢相關(guān)的
頁面質(zhì)量評估是查詢無關(guān)的過程必須使用查詢無關(guān)特征
宏觀上來講，與查詢相關(guān)的查詢目標(biāo)頁面是否存在與查詢無關(guān)的特征呢？
去偽存真 去粗取精
問題背景
頁面質(zhì)量評估的相關(guān)工作概述
高質(zhì)量頁面的查詢無關(guān)特征分析
基于學(xué)習(xí)的頁面質(zhì)量評估算法
應(yīng)用展望
高質(zhì)量頁面的查詢無關(guān)特征分析
基于真實網(wǎng)絡(luò)語料庫進(jìn)行查詢目標(biāo)頁面 的查詢無關(guān)特征分析
語料庫
2005.11月采集的超過3700萬中文網(wǎng)頁
占用空間超過0.5 Terabyte.
自Sogou.com獲得
高質(zhì)量頁面采樣
訓(xùn)練集: 1600頁面
測試集: 17000頁面
由Sogou工程師手工標(biāo)注
高質(zhì)量頁面的查詢無關(guān)特征分析
基于超鏈接結(jié)構(gòu)分析的特征
PageRank
入鏈接個數(shù)
入鏈接文本長度
其他特征
文檔長度/大小
完全鏡像個數(shù)
URL長度與類型
頁面編碼
高質(zhì)量頁面的查詢無關(guān)特征分析
PageRank
高質(zhì)量頁面的查詢無關(guān)特征分析
入鏈接個數(shù)
高質(zhì)量頁面的查詢無關(guān)特征分析
入鏈接文本長度
高質(zhì)量頁面的查詢無關(guān)特征分析
文檔長度
高質(zhì)量頁面的查詢無關(guān)特征分析
頁面鏡像個數(shù)
高質(zhì)量頁面的查詢無關(guān)特征分析
URL 長度/類型
高質(zhì)量頁面的查詢無關(guān)特征分析
其他部分特征




查詢無關(guān)特征能夠有效地區(qū)分目標(biāo)頁面與普通頁面，亦即查詢目標(biāo)頁面具有查詢無關(guān)特征
去偽存真 去粗取精
問題背景
頁面質(zhì)量評估的相關(guān)工作概述
高質(zhì)量頁面的查詢無關(guān)特征分析
基于學(xué)習(xí)的頁面質(zhì)量評估算法
應(yīng)用展望
基于學(xué)習(xí)的頁面質(zhì)量評估算法
根據(jù)查詢無關(guān)特征計算頁面成為查詢目標(biāo)頁面的可能性，用這種可能性表示頁面質(zhì)量的高低
形式化的表述為：
具有查詢無關(guān)特征A1, A2, A3, …, An的頁面P成為查詢目標(biāo)頁面的可能性
基于學(xué)習(xí)的頁面質(zhì)量評估算法
算法描述
[1] 單特征分析
基于學(xué)習(xí)的頁面質(zhì)量評估算法
算法描述
[2] 多特征分析
在合理選取的基礎(chǔ)上，可以發(fā)現(xiàn)特征之間的近似獨(dú)立性關(guān)系
基于學(xué)習(xí)的頁面質(zhì)量評估算法
算法描述
[2] 多特征分析（續(xù)）

基于學(xué)習(xí)的頁面質(zhì)量評估算法
比較 　　的相對大小


基于學(xué)習(xí)的頁面質(zhì)量評估算法
高質(zhì)量頁面的概率分布情況
基于學(xué)習(xí)的頁面質(zhì)量評估算法
測試效果
測試集合：17000多個查詢目標(biāo)頁面（訓(xùn)練集的10倍）






算法判定出的高質(zhì)量頁面僅占數(shù)據(jù)總量的5%，但能夠滿足超過92%以上的用戶查詢需求
基于學(xué)習(xí)的頁面質(zhì)量評估算法
質(zhì)量評估算法效果的評價指標(biāo)
高質(zhì)量頁面平均召回率（High Quality Page Average Recall, AR）
基于學(xué)習(xí)的頁面質(zhì)量評估算法
與直接應(yīng)用PageRank作為頁面質(zhì)量評估指標(biāo)的比較
基于學(xué)習(xí)的頁面質(zhì)量評估算法
算法分辨垃圾/低質(zhì)量頁面的能力








同時具有較好的篩選作弊頁面和低質(zhì)量頁面的作用
去偽存真 去粗取精
問題背景
頁面質(zhì)量評估的相關(guān)工作概述
高質(zhì)量頁面的查詢無關(guān)特征分析
基于學(xué)習(xí)的頁面質(zhì)量評估算法
應(yīng)用展望
應(yīng)用展望
利用頁面質(zhì)量評估算法作為搜索引擎層次索引機(jī)制的基礎(chǔ)
應(yīng)用展望
同PageRank一樣作為Ranking算法的依據(jù)
PageRank：用戶隨機(jī)訪問到某個頁面的可能性
頁面質(zhì)量：某個頁面成為用戶查詢目標(biāo)的普適可能性
具有明確的物理含義
利用類似方法進(jìn)行垃圾頁面清理工作
統(tǒng)計垃圾頁面的查詢無關(guān)特征
比較查詢目標(biāo)頁面而言，這種特征應(yīng)當(dāng)更加明顯
利用機(jī)器學(xué)習(xí)方法構(gòu)建分類器
計算某個頁面成為垃圾頁面的概率

應(yīng)用展望
其它的可能應(yīng)用方向
用于提高搜索引擎Spider的頁面抓取效率





提高個人化搜索（personalized search）質(zhì)量
更好的理解用戶使用搜索引擎的行為特點(diǎn)


頁面質(zhì)量評估及其在網(wǎng)絡(luò)信息檢索中的應(yīng)用