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