搜索引擎在查找時主要考慮兩方面因素：網(wǎng)頁和查詢的相關(guān)性、網(wǎng)頁的重要性
鏈接分析解決網(wǎng)頁重要性的問題
網(wǎng)頁中最重要的三個要素，出鏈（Out Link），入鏈（In Links），錨文字
鏈接分析算法
1、隨機(jī)游走模型：對直接跳轉(zhuǎn)和遠(yuǎn)程跳轉(zhuǎn)兩種用戶瀏覽行為進(jìn)行抽象的概念模型，用戶從當(dāng)前網(wǎng)頁到達(dá)某網(wǎng)頁的概率
2、子集傳播模型：把網(wǎng)頁劃分為若干子集，給予子集內(nèi)網(wǎng)頁初始權(quán)值，根據(jù)鏈接關(guān)系，按照一定方式將權(quán)值傳遞到其他網(wǎng)頁
不同子集傳播模型在如下方面存在差異：
1）如何定義特殊子集合
2）在確定了特殊子集合所具有的性質(zhì)后，如果對子集內(nèi)的網(wǎng)頁賦初始值
3）從特殊子集合將其分值傳播到其他網(wǎng)頁時，采取何種傳播方式
PageRank算法
除了考慮到入鏈數(shù)量的影響，還參考了網(wǎng)頁質(zhì)量因素
數(shù)量假設(shè)：在Web圖模型中，如果一個頁面節(jié)點接收到的其他網(wǎng)頁指向的入鏈數(shù)量越多，那么這個頁面越重要
質(zhì)量假設(shè)：質(zhì)量高的頁面會通過鏈接向其他頁面?zhèn)鬟f更多的權(quán)重
算法開始賦予每個網(wǎng)頁相同的重要性得分，通過迭代遞歸計算來更新每個頁面節(jié)點的PageRank得分，直到穩(wěn)定為止
遠(yuǎn)程跳轉(zhuǎn)：解決鏈接陷阱的通用方式，在網(wǎng)頁向外傳遞分值時，不限于向出鏈所指網(wǎng)頁傳遞，也可以以一定的概率向任意其他網(wǎng)頁跳轉(zhuǎn)（虛擬邊，權(quán)值通過虛擬邊向外傳遞）
HITS(Hypertext Induced Topic Selection)算法
Authority頁面：某個領(lǐng)域或者某個話題相關(guān)的高質(zhì)量網(wǎng)頁
Hub頁面：指向很多Authority頁面
基本假設(shè)1：一個好的Authority頁面會被很多好的Hub頁面指向
基本假設(shè)2：一個好的Hub頁面會向向很好的Authority頁面
算法步驟：
1、將查詢提交給某個現(xiàn)有的搜索引擎，或檢索系統(tǒng)，提取排名靠前的結(jié)果（根集）
2、在根集的基礎(chǔ)上，對其擴(kuò)充（凡是與根集內(nèi)網(wǎng)頁有直接鏈接指向關(guān)系的網(wǎng)頁都被擴(kuò)充進(jìn)來）
3、在根集+擴(kuò)充網(wǎng)頁，尋找好的Hub頁面與好的Authority頁面
4、初始情況下，在沒有更多可利用信息前，把所有頁面兩個權(quán)值都設(shè)置為1
5、以相互增強(qiáng)的關(guān)系等原則進(jìn)行多輪迭代計算，每輪迭代計算更新每個頁面的兩個權(quán)值，直到權(quán)值穩(wěn)定為止
HITS算法不僅在搜索引擎領(lǐng)域應(yīng)用，在自然語言處理，社交分析也有較好的效果
HITS算法的不足：計算效率較低、主題漂移，易被作弊者操縱結(jié)果，結(jié)果不穩(wěn)定（添加刪除個別網(wǎng)頁或者改變少數(shù)鏈接關(guān)系，對排名影響會很大）
HITS算法與PageRank算法比較
1、HITS與用戶輸入查詢相關(guān)，PageRank與查詢無關(guān)
2、HITS計算效率低，PageRank離線計算，在線直接使用計算結(jié)果，計算效率高
3、HITS為局部計算，適合在客戶端，PageRank為全局計算，適合步驟在服務(wù)器端
4、HITS適合處理具體用戶查詢，PageRank處理適合處理寬泛的用戶查詢
5、HITS算法在計算時，為每個頁面計算兩個分值，PageRank只需計算一個分值，在搜索引擎領(lǐng)域，更重要Authority權(quán)值，其他應(yīng)用領(lǐng)域Hub分值也很重要
6、從反作弊角度說，PageRank從機(jī)制上優(yōu)于HITS
7、PageRank比HITS計算過程更穩(wěn)定，原因是PageRank計算時的遠(yuǎn)程跳轉(zhuǎn)
SALSA算法
很多實驗數(shù)據(jù)表明，SALSA是目前最好的鏈接分析算法之一
計算流程分兩個階段：
1、確定計算對象集合，與HITS類似
1）擴(kuò)展網(wǎng)頁集合，在收到用戶查詢后，利用現(xiàn)有搜索引擎或檢索系統(tǒng)獲取根集，并擴(kuò)展
2）轉(zhuǎn)換為無向二分圖，一個子集合Hub集合，Authority集合
2、鏈接關(guān)系傳播過程，在這一階段采納了隨機(jī)游走模型
在權(quán)值傳播過程中，權(quán)值是被所有鏈接平均分配的
HITS模型關(guān)注的是Hub和Authority之間的節(jié)點相互增強(qiáng)關(guān)系
SALSA實際上關(guān)注的是Hub-Hub及Authority-Authority之間的節(jié)點關(guān)系
Authority集合內(nèi)從某個節(jié)點i轉(zhuǎn)移到另一個節(jié)點j的概率，i與j之間概率是不同的，非對稱
在二分圖中，對于Authority集合內(nèi)的某個節(jié)點來說，一定可以通過Hub子集合的節(jié)點中轉(zhuǎn)后再次返回本身
建立好Authority節(jié)點關(guān)系圖后，即可利用隨機(jī)游走模型來計算每個節(jié)點的Authority權(quán)值
SALSA將搜索結(jié)合排序問題進(jìn)一步轉(zhuǎn)換為求Authority節(jié)點矩陣的主秩問題，無需迭代，計算速度快
決定Authority權(quán)值的4個因子：
1）Authority子集合中包含的節(jié)點總數(shù)
2）網(wǎng)頁i所在連通圖中的節(jié)點個數(shù)
3）網(wǎng)頁i所在連通圖中包含的入鏈總數(shù)
4）網(wǎng)頁i的入鏈個數(shù)
SALSA算法的特點：
1、SALSA算法無需像HITS算法一樣迭代計算，計算速度快
2、解決了HITS主題漂移的問題，搜索質(zhì)量優(yōu)于HITS
主題敏感PageRank
該算法被Google使用在個性化搜索服務(wù)中，非常適合作為個性化搜索的技術(shù)方案
用戶會對某些領(lǐng)域感興趣，同時當(dāng)瀏覽某個頁面時，這個頁面也是與某個主題相關(guān)，跳轉(zhuǎn)時，更傾向于點擊和當(dāng)前頁面主題類似的鏈接
主題敏感PageRank是將用戶興趣，頁面主題及鏈接所指向網(wǎng)頁與當(dāng)前網(wǎng)頁主題的相似程度綜合考慮而建立模型
該算法引入16種主題類型，對于某個網(wǎng)頁來說，對應(yīng)某個主題類型都有相應(yīng)的PageRank分值
主題敏感的PageRank與主題相關(guān)，在接收到用戶查詢后，主題敏感PageRank還需要利用分類器，計算該查詢隸屬于事先定義好的16個主題的相似度，并在排序時利用此相似度信息
計算流程：
1、離線的分類主題PageRank數(shù)值計算，計算網(wǎng)頁對于16個分類的相似度
將網(wǎng)頁劃分為兩個集合，一個ODP對應(yīng)分類主題對應(yīng)的所有網(wǎng)頁S，剩下的網(wǎng)頁為另一個集合T
通過鏈接關(guān)系，從S向T傳遞權(quán)重，即計算網(wǎng)頁所屬類別的概率
2、在線利用算好的PageRank分值，來評估網(wǎng)頁和用戶查詢的相似度
通過計算查詢詞所屬類別的概率*網(wǎng)頁所屬類別的概率，得出兩者相關(guān)性的分值，進(jìn)行排序
HillTop算法
1、從海量的互聯(lián)網(wǎng)網(wǎng)頁中通過一定的規(guī)則選出專家頁面子集合，并單獨為其建立索引
2、接收用戶發(fā)出的查詢請求時，根據(jù)用戶查詢的主題，從專家頁面子集合中找出部分相關(guān)性最強(qiáng)的專家頁面，對每個專家頁面計算相關(guān)性得分
3、根據(jù)目標(biāo)頁面（從索引系統(tǒng)中中取到的頁面）和這些專家頁面的鏈接關(guān)系 對目標(biāo)頁面進(jìn)行排序
4、整合相關(guān)專家頁面和得分較高的目標(biāo)頁面作為搜索結(jié)果，返回給用戶
從屬組織頁面：主機(jī)IP地址的前3個網(wǎng)段相同，網(wǎng)站域名中的主域名相同
專家頁面
1、與某個主題相關(guān)的高質(zhì)量頁面
2、這些頁面的鏈接所指向的頁面相互之間是非從屬組織頁面
3、這些被指向的頁面大多數(shù)是與專家頁面主題相近
HillTop可以與某個排序算法相結(jié)合，不適合作為一個獨立的網(wǎng)頁排序算法來使用，因為當(dāng)無法得到一個足夠大的專家頁面時，會返回空結(jié)果。
步驟1：專家頁面搜索
從1億4千萬網(wǎng)頁中，篩選出250萬作為專家頁面，專家頁面特征:
1、頁面中至少包含K個出鏈，K可以人為指定
2、K個出鏈指向的所有頁面相互之間的關(guān)系，都符合非從屬組織頁面
對專家頁面單獨建索引，且只對關(guān)鍵字段(Key Phrase)進(jìn)行索引，關(guān)鍵字段包含3類信息：網(wǎng)頁標(biāo)題，H1標(biāo)簽內(nèi)文字和URL錨文字
關(guān)鍵字段有影響范圍（可以支配Qualify的鏈接），依次為，標(biāo)題->H1標(biāo)簽->URL錨文字
在計算網(wǎng)頁排序時，對查詢字段在不同的關(guān)鍵字段中，會使用不同的權(quán)值
系統(tǒng)接收到用戶查詢Q，將對專家頁面進(jìn)行打分，主要考慮以下3類信息：
1、關(guān)鍵字段包含了多少詞
2、關(guān)鍵片段本身的類型，即關(guān)鍵字段的類型
3、用戶查詢和關(guān)鍵詞的失配率，即關(guān)鍵字段中不屬于查詢的單詞個數(shù)占關(guān)鍵片段總單詞個數(shù)的比率
步驟2：目標(biāo)頁面排序
Hilltop算法包含的基本假設(shè)：一個目標(biāo)頁面如果是滿足用戶查詢的高質(zhì)量搜索結(jié)果，其充分必要條件是該目標(biāo)頁面有高質(zhì)量專家頁面鏈接指向
為保證上述假設(shè)的成立，Hilltop算法在這個階段需要對專家頁面的出鏈仔細(xì)進(jìn)行甄別，以保證查詢時，選出那些和查詢密切相關(guān)的目標(biāo)頁面。
在進(jìn)行傳遞分值之前，首先需要對鏈接關(guān)系進(jìn)行整理，能夠獲得專家頁面分值的目標(biāo)頁面需要滿足以下兩點要求：
條件1、至少需要兩個專家頁面有鏈接指向目標(biāo)頁面，且兩個專家頁面不能是從屬組織頁面
能夠獲得傳遞分值的目標(biāo)頁面一定有多個專家頁面鏈接指向，目標(biāo)頁面所獲得的總傳播分值是每個有鏈接指向的專家頁面所傳遞的分值之和
條件2、專家頁面和所指向的目標(biāo)頁面不能是從屬組織頁面
目標(biāo)頁面權(quán)值計算步驟：
1、找到專家頁面中那些能夠支配頁面的關(guān)鍵片段集合S
2、統(tǒng)計S中包含用戶查詢詞的關(guān)鍵片段個數(shù)T，T越大權(quán)值越大
3、專家頁面給目標(biāo)頁面?zhèn)鬟f分值：E*T,E為專家頁面本身在第一階段計算得到的相關(guān)得分，T為b步驟計算分值
對于包含多個查詢詞的用戶請求，則每個查詢詞單獨計算，將多個查詢詞的傳遞分值累加
Hilltop算法存在與HITS算法類似的計算效率問題，隨著專家頁面集合的增大
其他改進(jìn)算法
1、智能游走模型(Intelligent Surfer Model)
判斷網(wǎng)頁包含的鏈接所指向的網(wǎng)頁內(nèi)容和用戶查詢的相關(guān)性，以此來改善鏈接分析效果
2、偏置游走模型(Biased Sufer Model)
智能游走模型考慮的是網(wǎng)頁內(nèi)容和用戶查詢的相關(guān)性，而偏游走模型考慮的是鏈接指向的網(wǎng)頁內(nèi)容和當(dāng)前瀏覽網(wǎng)頁內(nèi)容之間的相似性
3、PHITS算法(Probability Analogy of HITS)
PHITS是對HITS算法的直接改進(jìn)。PHITS算法認(rèn)為不同鏈接其傳遞權(quán)值的能力應(yīng)該是不同的，PHITS需要計算兩個頁面S和T之間鏈接的連接強(qiáng)度
鏈接的強(qiáng)度依據(jù)頁面S和T之間相似度確定
4、BFS算法(Backward Forward Step)
對SALSA算法的擴(kuò)展，對HITS算法的限制
解除了SALSA算法只允許直接相鄰網(wǎng)頁才能有影響的限制，只要網(wǎng)頁S和T可通達(dá)，即可對網(wǎng)頁T施加影響，如果網(wǎng)頁S距離網(wǎng)頁T距離越遠(yuǎn)，那么網(wǎng)頁S的影響就隨著距離增大而呈現(xiàn)衰減
posted on 2013-11-12 14:06
胡滿超 閱讀(646)
評論(0) 編輯 收藏 引用 所屬分類:
搜索引擎