hits演算法

㈠ Hits的演算法

HITS,網頁分析，演算法，搜索引擎
HITS 演算法是由康奈爾大學( Cornell University ) 的JonKleinberg 博士於1998 年首先提出的,HITS 的英文全稱為Hyperlink - Inced Topic Search,為IBM公司阿爾馬登研究中心( IBM Almaden Research Center) 的名為「CLEVER」的研究項目中的一部分。
具體解釋：
一個網頁重要性的分析的演算法，根據一個網頁的入度（指向此網頁的超鏈接）和出度（從此網頁指向別的網頁）來衡量網頁的重要性。其最直觀的意義是如果一個網頁的重要性很高，則他所指向的網頁的重要性也高。一個重要的網頁被另一個網頁所指，則表明指向它的網頁重要性也會高。指向別的網頁定義為Hub值,被指向定義為Authority值。
通常HITS演算法是作用在一定范圍的，比如一個以程序開發為主題的網頁，指向另一個以程序開發為主題的網頁，則另一個網頁的重要性就可能比較高，但是指向另一個購物類的網頁則不一定。
在限定范圍之後根據網頁的出度和入度建立一個矩陣，通過矩陣的迭代運算和定義收斂的閾值不斷對兩個向量Authority和Hub值進行更新直至收斂。
理解HITS演算法是Web結構挖掘中最具有權威性和使用最廣泛的演算法。HITS演算法通過兩個評價權值——內容權威度（Authority）和鏈接權威度（Hub）來對網頁質量進行評估。其基本思想是利用頁面之間的引用鏈來挖掘隱含在其中的有用信息（如權威性），具有計算簡單且效率高的特點。HITS演算法認為對每一個網頁應該將其內容權威度和鏈接權威度分開來考慮，在對網頁內容權威度做出評價的基礎上再對頁面的鏈接權威度進行評價，然後給出該頁面的綜合評價。內容權威度與網頁自身直接提供內容信息的質量相關，被越多網頁所引用的網頁，其內容權威度越高；鏈接權威度與網頁提供的超鏈接頁面的質量相關，引用越多高質量頁面的網頁，其鏈接權威度越高。
首先，它完全將網頁的內容或文本排除在外，僅考慮網頁之間的鏈接結構來分析頁面的權威性，這與現實網路中的權威頁面相比，其不科學性顯而易見。然而HITS演算法也有其明顯的不足。
因為權威頁面必須針對某一主題或關鍵詞而言。某一頁面對一確定主題的具有較大權威性的頁面並不意味在其他與其無關的主題方面同樣具有權威性。其次一個頁面對另一頁面的引用有多種情況，其中包含了一頁面對另一頁面的認可，但除此之外也有其他目的鏈接，如為了導航或為了付費廣告。就HITS演算法的思想與實現過程做了細致的研究與概括。而HITS演算法在實現過程中均沒有考慮以上情況．導致了結果與目標的差距。
對HITS演算法的第二個不足，即非正常目的的引用．在HITS演算法看來，也誤認為是正常引用，導致實際結果與目標的出入。針對前面第一種不足，就有相關的學者提出了一種利用超鏈文字及其周圍文字與關鍵字相匹配而計算超鏈權值的方法，並引入系數對周圍文字和超鏈文字進行權值的相對控制，很好地將頁面文本信息引入到HITS演算法，提高了演算法的可靠性，並在現實中取得了很好的效果。
後來，經過不斷的改進。HITS演算法又引入了時間參數，即利用對一鏈接引用的時間長短來評價是否為正常引用。因為非正常鏈接其引用時間肯定不會很長（如交換鏈接、廣告鏈接），相反，如果一頁面對另一頁面的鏈接時間較長，則必然反映此頁面就是用戶的尋找頁面。即目標頁面或至少是正常引用。
如設定訪問時間少於1分鍾者為非正常引用。如果設定時間閥值，則可以將非正常引用的鏈接在HITS演算法的實現過程中篩選出來。另外可構造時間訪問函數，控制權威頁面的相對大小。如隨訪問時間的增大而其權威性也逐漸非線性增大．這樣可為HITS演算法的權威頁面提供更合理、更科學的解釋。

㈡ HITS演算法的Hits演算法

HITS (Hyperlink – Inced Topic Search) 演算法是利用HubPAuthority的搜索方法,
具體演算法如下:
將查詢q提交給基於關鍵字查詢的檢索系統，從返回結果頁面的集合中取前n個網頁(如n=200)，作為根集合(root set)，記為S，則S滿足：
1.S中的網頁數量較少
2.S中的網頁是與查詢q相關的網頁
3.S中的網頁包含較多的權威(Authority)網頁
通過向S 中加入被S 引用的網頁和引用S 的網頁,將S 擴展成一個更大的集合T. 以T 中的Hub 網頁為頂點集V1 ,以權威網頁為頂點集V2 。
V1 中的網頁到V2 中的網頁的超鏈接為邊集E ,形成一個二分有向圖. 對V1 中的任一個頂點v ,用h ( v) 表示網頁v 的Hub 值,且h ( v)收斂;對V2 中的頂點u ,用a ( u) 表示網頁的Authority 值。
開始時h ( v) = a ( u) = 1 ,對u 執行I 操作,修改它的a ( u) ,對v執行O操作,修改它的h ( v) ,然後規范化a ( u),h ( v) ,如此不斷的重復計算下面的I操作和O操作,直到a ( u),h(v)收斂 。
其中I操作:a ( u) = Σh ( v) ;O 操作: h ( v) = Σa ( u) 。每次迭代對a ( u) 、h ( v) 進行規范化處理: a ( u) = a ( u)/Σ[ a ( q) ]2 ; h ( v) = h ( v)/Σ[ h ( q) ]2 。 HITS演算法偽代碼 如下：
1G:= set of pages
2for eachpagepinGdo
3p.auth = 1 //p.auth is the authority score of the pagep
4p.hub = 1 //p.hub is the hub score of the pagep
5functionHubsAndAuthorities(G)
6forstepfrom1tokdo// run the algorithm for k steps
7 norm = 0
8for eachpagepinGdo// update all authority values first
9p.auth = 0
10for eachpageqinp.incomingNeighborsdo//p.incomingNeighborsis the set of pages that link top
11p.auth +=q.hub
12 norm += square(p.auth) // calculate the sum of the squared auth values to normalise
13 norm = sqrt(norm)
14for eachpagepinGdo// update the auth scores
15p.auth =p.auth / norm // normalise the auth values
16 norm = 0
17for eachpagepinGdo// then update all hub values
18p.hub =
019for eachpagerinp.outgoingNeighborsdo//p.outgoingNeighborsis the set of pages thatplinks to
20p.hub +=r.auth
21 norm += square(p.hub) // calculate the sum of the squared hub values to normalise
22 norm = sqrt(norm)
23for eachpagepinGdo// then update all hub values
24p.hub =p.hub / norm // normalise the hub values

㈢ hits演算法：在網上找了幾個關於hits的java實現演算法，演算法的輸入都是一個方陣，請問不是方陣的如何實現

k相當於你用來記錄每次運算的進度的，k不斷的增長的過程，就是假設你用手算一個一個運算的過程。你寫兩個矩陣A是3*3的，B是3*3的，兩個矩陣相乘，你看看是不是你手算的過程和這個程序的步驟是一致的。如果不是方陣假設A是2*3.B是3*2那麼k還是原來的東西。只不過，2用i來循環，3用j來循環，for (int i = 0; i < len; i++)中的len=2. for (int j = 0; j < len; j++)中的len=3而已了。k=2因為C=A*B是2*2的。不明白你再問O(∩_∩)O

㈣ HITS演算法的英文全稱

Hypertext-Inced Topic Search

㈤ HITS演算法的具體解釋

按照HITS演算法，用戶輸入關鍵詞後，演算法對返回的匹配頁面計算兩種值，一種是樞紐值（Hub Scores），另一種是權威值(Authority Scores),這兩種值是互相依存、互相影響的。所謂樞紐值，指的是頁面上所有導出鏈接指向頁面的權威值之和。權威值是指所有導入鏈接所在的頁面中樞紐之和。
一個網頁重要性的分析的演算法。
通常HITS演算法是作用在一定范圍的，比如一個以程序開發為主題網頁，指向另一個以程序開發為主題的網頁，則另一個網頁的重要性就可能比較高，但是指向另一個購物類的網頁則不一定。
在限定范圍之後根據網頁的出度和入度建立一個矩陣，通過矩陣的迭代運算和定義收斂的閾值不斷對兩個向量Authority和Hub值進行更新直至收斂。

㈥ hits演算法為什麼歸一化

您好，為了空間的考慮，我們在存儲Web圖的時候，一般都是用的鄰接矩陣表示。
經過分析發現，一個頁面的權威值，其實是指向它的頁面的中心值之和；一個頁面的中心值，是它指向的頁面的權威值的過程。這是一個相互加強的過程。
為什麼要歸一化。主要原因是消除不同維度數據之間的差異，還以加快訓練演算法的收斂速度。包括去除量綱不一致的缺陷，時間序列不平穩。

㈦ 為什麼hits演算法是與用戶輸入的查詢請求密切相關的

Hub頁面（樞紐頁面）和Authority頁面（權威頁面）是HITS演算法最基本的兩個定義。
所謂「Authority」頁面，是指與某個領域或者某個話題相關的高質量網頁，比如搜索引擎領域，Google和網路首頁即該領域的高質量網頁，比如視頻領域，優酷和土豆首頁即該領域的高質量網頁。
所謂「Hub」頁面，指的是包含了很多指向高質量「Authority」頁面鏈接的網頁，比如hao123首頁可以認為是一個典型的高質量「Hub」網頁。
圖1給出了一個「Hub」頁面實例，這個網頁是斯坦福大學計算語言學研究組維護的頁面，這個網頁收集了與統計自然語言處理相關的高質量資源，包括一些著名的開源軟體包及語料庫等，並通過鏈接的方式指向這些資源頁面。這個頁面可以認為是「自然語言處理」這個領域的「Hub」頁面，相應的，被這個頁面指向的資源頁面，大部分是高質量的「Authority」頁面。

㈧ HITS演算法的演算法由來

HITS的演算法由來

HITS 演算法是由康奈爾大學( Cornell University ) 的Jon Kleinberg 博士於1997 年首先提出的,為IBM
公司阿爾馬登研究中心( IBM Almaden Research Center) 的名為「CLEVER」的研究項目中的一部分。

HITS
(Hyperlink – Inced Topic Search) 演算法是利用HubPAuthority的搜索方法,

具體演算法如下:

將查詢q提交給基於關鍵字查詢的檢索系統，從返回結果頁面的集合中取前n個網頁(如n=200)，作為根集合(root set)，記為S，則S滿足：

1. S中的網頁數量較少

2. S中的網頁是與查詢q相關的網頁

3. S中的網頁包含較多的權威(Authority)網頁

通過向S 中加入被S 引用的網頁和引用S 的網頁,將S 擴展成一個更大的集合T. 以T 中的Hub 網頁為頂點集V1 ,以權威網頁為頂點集V2 。

V1 中的網頁到V2 中的網頁的超鏈接為邊集E ,形成一個二分有向圖. 對V1 中的任一個頂點v ,用h ( v) 表示網頁v 的Hub 值,且h ( v)收斂;對V2 中的頂點u ,用a ( u) 表示網頁的Authority 值。

開始時h ( v) = a ( u) = 1 ,對u 執行I 操作,修改它的a ( u) ,對v執行O操作,修改它的h ( v) ,然後規范化a ( u),h ( v) ,如此不斷的重復計算下面的I操作和O操作,直到a ( u),h(v)收斂 。

其中I操作:a ( u) = Σh ( v) ;O 操作: h ( v) = Σa ( u) 。每次迭代對a ( u) 、h ( v) 進行規范化處理: a ( u) = a ( u)/Σ[ a ( q) ]2 ;h ( v) = h ( v)/Σ[ h ( q) ]2 。

㈨ 求問：HITS演算法的實現代碼！！C語言，或者JAVA都可以！

隨著網路的迅速發展，萬維網成為大量信息的載體，如何有效地提取並利用這些信息成為一個巨大的挑戰。搜索引擎(Search Engine)，例如傳統的通用搜索引擎AltaVista，Yahoo!和Google等，作為一個輔助人們檢索信息的工具成為用戶訪問萬維網的入口和指南。但是，這些通用性搜索引擎也存在著一定的局限性，如：�

(1) 不同領域、不同背景的用戶往往具有不同的檢索目的和需求，通用搜索引擎所返回的結果包含大量用戶不關心的網頁。�
(2) 通用搜索引擎的目標是盡可能大的網路覆蓋率，有限的搜索引擎伺服器資源與無限的網路數據資源之間的矛盾將進一步加深。�
(3) 萬維網數據形式的豐富和網路技術的不斷發展，圖片、資料庫、音頻/視頻多媒體等不同數據大量出現，通用搜索引擎往往對這些信息含量密集且具有一定結構的數據無能為力，不能很好地發現和獲取。�
(4) 通用搜索引擎大多提供基於關鍵字的檢索，難以支持根據語義信息提出的查詢。�
為了解決上述問題，定向抓取相關網頁資源的聚焦爬蟲應運而生。聚焦爬蟲是一個自動下載網頁的程序，它根據既定的抓取目標，有選擇的訪問萬維網上的網頁與相關的鏈接，獲取所需要的信息。與通用爬蟲(general�purpose web crawler)不同，聚焦爬蟲並不追求大的覆蓋，而將目標定為抓取與某一特定主題內容相關的網頁，為面向主題的用戶查詢准備數據資源。�

1 聚焦爬蟲工作原理及關鍵技術概述�
網路爬蟲是一個自動提取網頁的程序，它為搜索引擎從萬維網上下載網頁，是搜索引擎的重要組成。傳統爬蟲從一個或若干初始網頁的URL開始，獲得初始網頁上的URL，在抓取網頁的過程中，不斷從當前頁面上抽取新的URL放入隊列,直到滿足系統的一定停止條件，如圖1(a)流程圖所示。聚焦爬蟲的工作流程較為復雜，需要根據一定的網頁分析演算法過濾與主題無關的鏈接，保留有用的鏈接並將其放入等待抓取的URL隊列。然後，它將根據一定的搜索策略從隊列中選擇下一步要抓取的網頁URL，並重復上述過程，直到達到系統的某一條件時停止，如圖1(b)所示。另外，所有被爬蟲抓取的網頁將會被系統存貯，進行一定的分析、過濾，並建立索引，以便之後的查詢和檢索；對於聚焦爬蟲來說，這一過程所得到的分析結果還可能對以後的抓取過程給出反饋和指導。�

相對於通用網路爬蟲，聚焦爬蟲還需要解決三個主要問題：�
(1) 對抓取目標的描述或定義；�
(2) 對網頁或數據的分析與過濾；�
(3) 對URL的搜索策略。�
抓取目標的描述和定義是決定網頁分析演算法與URL搜索策略如何制訂的基礎。而網頁分析演算法和候選URL排序演算法是決定搜索引擎所提供的服務形式和爬蟲網頁抓取行為的關鍵所在。這兩個部分的演算法又是緊密相關的。�

2 抓取目標描述�
現有聚焦爬蟲對抓取目標的描述可分為基於目標網頁特徵、基於目標數據模式和基於領域概念3種。�
基於目標網頁特徵的爬蟲所抓取、存儲並索引的對象一般為網站或網頁。根據種子樣本獲取方式可分為：�
（1） 預先給定的初始抓取種子樣本；�
（2） 預先給定的網頁分類目錄和與分類目錄對應的種子樣本，如Yahoo!分類結構等；�
（3） 通過用戶行為確定的抓取目標樣例，分為：�
a) 用戶瀏覽過程中顯示標注的抓取樣本；�
b) 通過用戶日誌挖掘得到訪問模式及相關樣本。�
其中，網頁特徵可以是網頁的內容特徵，也可以是網頁的鏈接結構特徵，等等。�
現有的聚焦爬蟲對抓取目標的描述或定義可以分為基於目標網頁特徵，基於目標數據模式和基於領域概念三種。�
基於目標網頁特徵的爬蟲所抓取、存儲並索引的對象一般為網站或網頁。具體的方法根據種子樣本的獲取方式可以分為：（1）預先給定的初始抓取種子樣本；（2）預先給定的網頁分類目錄和與分類目錄對應的種子樣本，如Yahoo!分類結構等；（3）通過用戶行為確定的抓取目標樣例。其中，網頁特徵可以是網頁的內容特徵，也可以是網頁的鏈接結構特徵，等等。�

-----------------------------------------------------------

2 爬蟲技術研究綜述
基於目標數據模式的爬蟲針對的是網頁上的數據，所抓取的數據一般要符合一定的模式，或者可以轉化或映射為目標數據模式。�

另一種描述方式是建立目標領域的本體或詞典，用於從語義角度分析不同特徵在某一主題中的重要程度。�

3 網頁搜索策略�
網頁的抓取策略可以分為深度優先、廣度優先和最佳優先三種。深度優先在很多情況下會導致爬蟲的陷入(trapped)問題，目前常見的是廣度優先和最佳優先方法。�
3.1 廣度優先搜索策略�
廣度優先搜索策略是指在抓取過程中，在完成當前層次的搜索後，才進行下一層次的搜索。該演算法的設計和實現相對簡單。在目前為覆蓋盡可能多的網頁，一般使用廣度優先搜索方法。也有很多研究將廣度優先搜索策略應用於聚焦爬蟲中。其基本思想是認為與初始URL在一定鏈接距離內的網頁具有主題相關性的概率很大。另外一種方法是將廣度優先搜索與網頁過濾技術結合使用，先用廣度優先策略抓取網頁，再將其中無關的網頁過濾掉。這些方法的缺點在於，隨著抓取網頁的增多，大量的無關網頁將被下載並過濾，演算法的效率將變低。�

3.2 最佳優先搜索策略�
最佳優先搜索策略按照一定的網頁分析演算法，預測候選URL與目標網頁的相似度，或與主題的相關性，並選取評價最好的一個或幾個URL進行抓取。它只訪問經過網頁分析演算法預測為「有用」的網頁。存在的一個問題是，在爬蟲抓取路徑上的很多相關網頁可能被忽略，因為最佳優先策略是一種局部最優搜索演算法。因此需要將最佳優先結合具體的應用進行改進，以跳出局部最優點。將在第4節中結合網頁分析演算法作具體的討論。研究表明，這樣的閉環調整可以將無關網頁數量降低30%~90%。�

4 網頁分析演算法�

網頁分析演算法可以歸納為基於網路拓撲、基於網頁內容和基於用戶訪問行為三種類型。�
4.1 基於網路拓撲的分析演算法�
基於網頁之間的鏈接，通過已知的網頁或數據，來對與其有直接或間接鏈接關系的對象（可以是網頁或網站等）作出評價的演算法。又分為網頁粒度、網站粒度和網頁塊粒度這三種。�
4.1.1 網頁(Webpage)粒度的分析演算法�
PageRank和HITS演算法是最常見的鏈接分析演算法，兩者都是通過對網頁間鏈接度的遞歸和規范化計算，得到每個網頁的重要度評價。PageRank演算法雖然考慮了用戶訪問行為的隨機性和Sink網頁的存在，但忽略了絕大多數用戶訪問時帶有目的性，即網頁和鏈接與查詢主題的相關性。針對這個問題，HITS演算法提出了兩個關鍵的概念：權威型網頁（authority）和中心型網頁（hub）。�

基於鏈接的抓取的問題是相關頁面主題團之間的隧道現象，即很多在抓取路徑上偏離主題的網頁也指向目標網頁，局部評價策略中斷了在當前路徑上的抓取行為。文獻[21]提出了一種基於反向鏈接（BackLink）的分層式上下文模型（Context Model），用於描述指向目標網頁一定物理跳數半徑內的網頁拓撲圖的中心Layer0為目標網頁，將網頁依據指向目標網頁的物理跳數進行層次劃分，從外層網頁指向內層網頁的鏈接稱為反向鏈接。�

4.1.2 網站粒度的分析演算法�
網站粒度的資源發現和管理策略也比網頁粒度的更簡單有效。網站粒度的爬蟲抓取的關鍵之處在於站點的劃分和站點等級(SiteRank)的計算。SiteRank的計算方法與PageRank類似，但是需要對網站之間的鏈接作一定程度抽象，並在一定的模型下計算鏈接的權重。�
網站劃分情況分為按域名劃分和按IP地址劃分兩種。文獻[18]討論了在分布式情況下，通過對同一個域名下不同主機、伺服器的IP地址進行站點劃分，構造站點圖，利用類似PageRank的方法評價SiteRank。同時，根據不同文件在各個站點上的分布情況，構造文檔圖，結合SiteRank分布式計算得到DocRank。文獻[18]證明，利用分布式的SiteRank計算，不僅大大降低了單機站點的演算法代價，而且克服了單獨站點對整個網路覆蓋率有限的缺點。附帶的一個優點是，常見PageRank 造假難以對SiteRank進行欺騙。�
4.1.3 網頁塊粒度的分析演算法�
在一個頁面中，往往含有多個指向其他頁面的鏈接，這些鏈接中只有一部分是指向主題相關網頁的，或根據網頁的鏈接錨文本表明其具有較高重要性。但是，在PageRank和HITS演算法中，沒有對這些鏈接作區分，因此常常給網頁分析帶來廣告等雜訊鏈接的干擾。在網頁塊級別(Block�level)進行鏈接分析的演算法的基本思想是通過VIPS網頁分割演算法將網頁分為不同的網頁塊(page block)，然後對這些網頁塊建立page�to�block和block�to�page的鏈接矩陣，�分別記為Z和X。於是，在page�to�page圖上的網頁塊級別的PageRank為�W�p=X×Z；�在block�to�block圖上的BlockRank為�W�b=Z×X。�已經有人實現了塊級別的PageRank和HITS演算法，並通過實驗證明，效率和准確率都比傳統的對應演算法要好。�
4.2 基於網頁內容的網頁分析演算法�
基於網頁內容的分析演算法指的是利用網頁內容（文本、數據等資源）特徵進行的網頁評價。網頁的內容從原來的以超文本為主，發展到後來動態頁面（或稱為Hidden Web）數據為主，後者的數據量約為直接可見頁面數據（PIW，Publicly Indexable Web）的400~500倍。另一方面，多媒體數據、Web Service等各種網路資源形式也日益豐富。因此，基於網頁內容的分析演算法也從原來的較為單純的文本檢索方法，發展為涵蓋網頁數據抽取、機器學習、數據挖掘、語義理解等多種方法的綜合應用。本節根據網頁數據形式的不同，將基於網頁內容的分析演算法，歸納以下三類：第一種針對以文本和超鏈接為主的無結構或結構很簡單的網頁；第二種針對從結構化的數據源（如RDBMS）動態生成的頁面，其數據不能直接批量訪問；第三種針對的數據界於第一和第二類數據之間，具有較好的結構，顯示遵循一定模式或風格，且可以直接訪問

base set
基本集
基礎集合

base基數

在HITS 演算法中,對每個文檔都要計算兩個值:權威值(authority)與中心值(hub)。開始時,由用戶發出查詢,HITS 演算法使用一個基於文本的搜索引擎,得到許多被返回的頁面,構成根集合(root set)R。把根集合中的頁面所指向的頁面都包括進來,再把指向根集合中的頁面的頁面也包括進來,這樣就擴充成了基礎集合(base set)T.