將搜索結果進行排序是搜尋引擎的一個重要課題，相關的研究也比較多
索引系統中權值計算模組就是為了實現Web文檔的排序功能
排序的方法主要是利用文檔之間的超文字連結關係、描述連結的文本及文本自身內容
一個網頁在一組網頁中的重要程度應該由這組網頁之間的相互作用關係來決定，而不是由自身來決定
在此，還存在一個重要概念，如果一個連結從網頁P指向網頁Q，那麼這個連結所得到的資訊不僅屬於網頁P，更屬於網頁Q，由此得到的資訊定向也更為準確
如果將每個網頁認為是一個節點，每一條超文字鏈認為是結點P和Q之間的有向邊(從P指向Q)，那麼整個Web就構成了一個龐大的有向圖
基於對此有向圖的理解，出現了兩大關於連結結構在搜索演算法上的表示和應用，Page Rank技術和HITS技術(Hyperlink－Induced Topic Search)
Page Rank由Stanford大學的google研究小組提出，並應用于其開發的Google系統
HITS技術是由Cornell大學的J.M.Kleinberg教授等人首先提出，並應用於IBM的Clever系統開發中
Google系統的page Rank技術 Google系統的Page Rank技術實現建立在一個“隨機衝浪”模型的假設上，這個“隨機衝浪”模型是用來描述網路使用者對網頁的訪問行為
模型假設如下： ①用戶隨機地選擇一個網頁作為上網的起始網頁； ②看完這個網頁後，從該網頁內所含的超鏈內隨機地選擇一個頁面繼續進行流覽； ③沿著超鏈前進了一定數目的網頁後，使用者對這個主題感到厭倦，重新隨機選擇一個網頁進行流覽，並重複2和3
按照以上的使用者行為模型，每個網頁可能被訪問到的次數就是該網頁的連結權值
假設網頁P存在T1，T2……Tn的連結網頁；參數d代表“隨機飆網者”沿著連結訪問網頁的衰減因素，取值範圍在0～1之間，根據經驗值我們一般取為0.85；C(Ti)代表網頁Ti鏈向其他網頁的連結數量；PR(P)定義為網頁P的連結權值
Page Rank採用以下公式計算這個權值： 應用以上遞推公式可以算出每一個網頁的連結權值(Page Rank)，並且與網路規則連結矩陣所構成的有向圖的特徵向量相符合
Google研究小組計算了26，000，000個網頁的Page Rank，在一個中型工作站只用幾個小時即得所有結果
對Google系統測試結果也表明，Page Rank技術能夠大幅度地提高簡單檢索返回結果的品質，同時能夠有效地防止網頁編寫者對搜尋引擎的欺騙，因為如果某網頁沒有任何連結，其Page Rank值[PR(P)]則為0
目前，Google的Page Rank技術在網頁排序中被認為是比較成熟而有效的技術
由於Page Rank技術建立在“隨機衝浪”使用者行為模型假設上，所以對於“隨機衝浪”用戶的簡單查詢來說，這種方法比較適合，並且可實現快速排序
但Google系統的排序是在網頁搜集完成後離線計算每個網頁的Page Rank值
檢索時，檢索器只從資料庫中取出資料而不做額外運算，所以它的回應速度比較快，同時也缺乏用戶查詢的靈活性，從某種程度上說，其檢索結果還不夠精確
HITS反覆運算演算法 首先，網頁按其作用分為兩類：Authority網頁和Hub網頁
Authority網頁指那些真正的使用者查詢所需資訊的源所在地，即對於一個特定的用戶查詢，該網頁提供最好的相關信息；Hub網頁指那些資訊內容集中所在地，對Hub提供很多指向高品質Authority網頁的超鏈
HITS演算法的出發點就是一個Hub指向多個Authority，而一個Authority被多個Hub指向，兩者之間是一種相互增強的關係
如果要得到某一網頁具體的Hub權值和Authority權值，則須打破這種相互增強關係的影響
Kleinberg在原文中給出了完整的數學證明來說明這種關係是可以被打破的並最終趨於一個穩態值
Kleinberg使用的是反覆運算演算法來表徵每一網頁的Hub權值和Authority權值
在一個網頁集合中，每一個網頁都有Hub權值[H(P)]和Authority權值[A(P)]，在每一次反覆運算中分兩步：1用所有指向P的網頁的H(P)值來替代A(P)；2用所有被P指向的網頁的A(P)值來替代H(P)
把(p,q)抽象為集合中的任一對超鏈，在所有的(p,q)的相互評價中，轉化為向量的運算，經過E次反覆運算運算後，向量A和H趨於相應的穩態值
反覆運算公式如下： HITS反覆運算演算法在搜尋引擎中的具體應用是，當用戶提交一個查詢，Robot利用關鍵字得到一個網頁根集合，再根據超鏈並結合一定的搜索策略來擴展根集合，將被連結的網頁加入根集合而形成新集合，重複至得到一個較大的網頁集合
然後對集合中網頁採用HITS反覆運算計算出集合中每一網頁的Hub權值和Authority權值，分別取出前n個結果返回給用戶
由以上簡單描述可以推論HITS演算法適用於使用者一次查詢結果中精選出Hub和Authority網頁
值得一提的是，某一網頁的Hub權值和Authority權值是互斥的，也就是說，Hub值越高，其Authority權值越低，反之亦然
所以，在結果頁的提供上應該讓用戶更多地參與選擇排序方法
在HITS演算法的基礎上，Soumen Chakrabarti做了進一步改進，提出結合文本相關性HITS演算法，利用描述連結的文本內容(anchor text)更加精化了結果，這種演算法比較適用於主題檢索
HITS反覆運算靈活性強，結果較為精確，但由於都是基於反覆運算，速度較慢，回應使用者查詢要進行大量的運算，比較耗費伺服器資源
資料來源: 關鍵字SEO網路行銷
留言列表
