1、網(wǎng)絡(luò)檢索,李 柯 2010-12,搜索引擎的發(fā)展,第一代搜索引擎基于關(guān)鍵詞的檢索 第二代搜索引擎基于超鏈接的檢索 第三代搜索引擎基于概念的檢索,第一代搜索引擎,基于關(guān)鍵詞的檢索是利用關(guān)鍵詞索引來獲取文檔，即整個(gè)文檔的內(nèi)容通過這些關(guān)鍵詞進(jìn)行表示，同樣，用戶的檢索提問式也用一組關(guān)鍵詞來表示。然后利用關(guān)鍵詞將文檔與提問式進(jìn)行匹配，計(jì)算文檔與提問式的相關(guān)程度。 布爾模型 向量空間模型 概率模型,第二代搜索引擎,基于超鏈接的檢索也稱鏈接分析，是搜索引擎面對網(wǎng)絡(luò)這一動態(tài)環(huán)境，所采用的一種新的檢索排序方法。 基本思想 PageRank算法 HITs算法,超鏈接分析的基本思想,主要是來自傳統(tǒng)的文獻(xiàn)計(jì)量學(xué)中的文

2、獻(xiàn)引文分析。傳統(tǒng)的文獻(xiàn)引文分析認(rèn)為，一篇學(xué)術(shù)論文的價(jià)值很大程度上體現(xiàn)在它被其他學(xué)術(shù)論文作為參考文獻(xiàn)飲用的次數(shù)，即被其他學(xué)術(shù)論文引用得越多，這篇論文的價(jià)值就越高。 超鏈接分析充分利用了網(wǎng)絡(luò)自身的超鏈接結(jié)構(gòu)，提出了一個(gè)假設(shè)，即網(wǎng)頁的重要性可用其他網(wǎng)頁對其超鏈接的數(shù)量來衡量。,超鏈接分析的基本思想,一般地，我們把一個(gè)由網(wǎng)頁A指向網(wǎng)頁B的超鏈接理解為網(wǎng)頁A中包含對網(wǎng)頁B的引用，則超鏈接分析最簡單直接的應(yīng)用是：指向一個(gè)網(wǎng)頁的超鏈接數(shù)目越多，則這個(gè)網(wǎng)頁的重要性就越高。 也可以這樣理解： 網(wǎng)頁A指向網(wǎng)頁B的鏈接 由網(wǎng)頁A對網(wǎng)頁B投了一票。,PageRank概念,PageRank(網(wǎng)頁級別)，2001年9月被

3、授予美國專利，專利人是Google創(chuàng)始人之一拉里佩奇（Larry Page）。 它是Google排名運(yùn)算法則（排名公式）的一部分，是Google用于用來標(biāo)識網(wǎng)頁的等級/重要性的一種方法，是Google用來衡量一個(gè)網(wǎng)站的好壞的唯一標(biāo)準(zhǔn)。,PageRank概念,Google的PageRank根據(jù)網(wǎng)站的外部鏈接和內(nèi)部鏈接的數(shù)量和質(zhì)量來衡量網(wǎng)站的價(jià)值。PageRank背后的概念是，每個(gè)到頁面的鏈接都是對該頁面的一次投票，被鏈接的越多，就意味著被其他網(wǎng)站投票越多。這個(gè)就是所謂的“鏈接流行度”衡量多少人愿意將他們的網(wǎng)站和你的網(wǎng)站掛鉤。 PageRank分值從0到10，PR值越高說明該網(wǎng)頁越受歡迎。,Pag

4、eRank定義,基本思想：如果網(wǎng)頁T存在一個(gè)指向網(wǎng)頁A的連接，則表明T的所有者認(rèn)為A比較重要，從而把T的一部分重要性得分賦予A。這個(gè)重要性得分值為： PR（T）/C(T)。 其中PR（T）為T的PageRank值，C(T)為T的出鏈數(shù)，則A的PageRank值為一系列類似于T的頁面重要性得分值的累加。,PageRank定義,L.Page等人對PageRank的定義：,PR(A)：表示網(wǎng)頁A的PageRank值； C：為規(guī)范化因子，是保證所有網(wǎng)頁的PR值總和為一常量； T1,T2,Tn ：鏈接到網(wǎng)頁A的其他網(wǎng)頁； PR(Ti)：網(wǎng)頁Ti的PageRank值； C(Ti)：網(wǎng)頁Ti指向其他網(wǎng)頁的超

5、鏈接數(shù)目。,PageRank定義,假設(shè)前提：即認(rèn)為所有的網(wǎng)頁形成一個(gè)牢固的鏈接圖，每個(gè)網(wǎng)頁都能從其他網(wǎng)頁通過超鏈接到達(dá)。定義中給出的PR值都可以根據(jù)所有鏈接到它的網(wǎng)頁的PR值除以各自向外的超鏈接數(shù)的商再進(jìn)行求和。 假如一個(gè)人對網(wǎng)頁上的超鏈接的點(diǎn)擊是隨機(jī)的，在牢固鏈接圖的假設(shè)前提下，可以到達(dá)任一網(wǎng)頁，只是到大的可能性大小不同。 顯然，網(wǎng)頁鏈入的超鏈接數(shù)越多，到達(dá)的可能性就越大，相應(yīng)的PR值就越高。對于PR值高的網(wǎng)頁鏈接到的網(wǎng)頁，到達(dá)的可能性也就越大，其PR值也相應(yīng)越高。,PageRank計(jì)算（一）,利用PageRank的公式定義可以計(jì)算網(wǎng)頁集合中所有網(wǎng)頁的PR值。假設(shè)S為整個(gè)網(wǎng)頁的總和，由于所有

6、網(wǎng)頁的PR值開始都是未知的，我們進(jìn)行平均分配，給每個(gè)網(wǎng)頁的PR值都賦予1/S，再根據(jù)公式定義進(jìn)行計(jì)算，然后對得到的值再次利用公式定義，這樣循環(huán)反復(fù)，直到計(jì)算所得的PR值收斂于一個(gè)相對固定的值。 算法如下：,PageRank計(jì)算（一）,任意 While for each ; ; ; for each ; ; ,PageRank計(jì)算（一）,算法中PR(P)i表示進(jìn)行i次循環(huán)計(jì)算后的PR值，C的計(jì)算是保證總PR值為1 L.Page等人通過實(shí)驗(yàn)，認(rèn)為循環(huán)次數(shù)和鏈接數(shù)目是對數(shù)增長的。,PageRank計(jì)算（二）,作為最基本的考慮方法，就是用行列式的形式來表達(dá)鏈接關(guān)系。從頁面 i 鏈接到另一張頁面 j 的

7、時(shí)，將其成分定義為1，反之則定義為 0 。即，行列陣 A 的成分 aij 可以用aij 1 (從頁面 i 向頁面 j 有 鏈接的情況) 0 (從頁面 i 向頁面 j 沒有鏈接的情況) 來表示。,PageRank計(jì)算（二）,文件數(shù)用 N 來表示的話，這個(gè)行列陣就成為 NN 的方陣。這個(gè)相當(dāng)于在圖論中的“鄰接矩陣”。也就是說，Web 的鏈接關(guān)系可以看做是采用了鄰接關(guān)系有向圖 S?？偠灾?，只要建立了鏈接，就應(yīng)該有鄰接關(guān)系。,PageRank計(jì)算（二）,PageRank 的行列陣是把這個(gè)鄰接行列倒置后(行和列互換)，為了將各列(column)矢量的總和變成 1 (全概率), 把各個(gè)列矢量除以各自的鏈

8、接數(shù)(非零要素?cái)?shù))。這樣作成的行列被稱為推移概率行列，含有 N 個(gè)概率變量，各個(gè)行矢量表示狀態(tài)之間的推移概率。倒置的理由是，PageRank 并非重視鏈接到多少地方而是重視被多少地方鏈接。,PageRank計(jì)算（二）,一個(gè)典型化的例子,PageRank計(jì)算（二）,歸一化(全概率) A= 轉(zhuǎn)置矩陣A= AT=,PageRank計(jì)算（二）,計(jì)算過程,PageRank計(jì)算（二）,將 PageRank 的評價(jià)按順序排列 名次 PageRank 文件ID 發(fā)出鏈接ID 被鏈接ID 1 0.304 1 2,3,4,5,7 2,3,5,6 2 0.179 5 1,3,4,6 1,4,6,7 3 0.166

9、2 1 1,3,4 4 0.141 3 1,2 1,4,5 5 0.105 4 2,3,5 1,5 6 0.061 7 5 1 7 0.045 6 1,5 5,PageRank計(jì)算（二）,PageRank計(jì)算（二）,ID=1的流入量(ID=2發(fā)出的Rank)+(ID=3發(fā)出的Rank)+(ID=5發(fā)出的Rank)+(ID=6發(fā)出的Rank) = 0.166+0.141/2+0.179/4+0.045/2 = 0.304 ID=2的流入量(ID=1發(fā)出的Rank)+(ID=3發(fā)出的Rank)+(ID=4發(fā)出的Rank= 0.304/5+0.141/2+0.105/3= 0.167 ID=3的流入

10、量(ID=1發(fā)出的Rank)+(ID=4發(fā)出的Rank)+(ID=5發(fā)出的Rank)= 0.304/5+0.105/3+0.179/4 = 0.141 ID=4的流入量(ID=1發(fā)出的Rank)+(ID=5發(fā)出的Rank= 0.304/5+0.179/4 = 0.106 ID=5的流入量(ID=1發(fā)出的Rank)+(ID=4發(fā)出的Rank)+(ID=6發(fā)出的Rank)+(ID=7發(fā)出的Rank) = 0.304/5+0.105/3+0.045/2+0.061 = 0.180 ID=6的流入量(ID=5發(fā)出的Rank= 0.179/4= 0.045 ID=7的流入量(ID=1發(fā)出的Rank= 0

11、.304/5 = 0.061,HITS算法,如果網(wǎng)頁A指向大量的重要網(wǎng)頁，那么A的建議就會變得有價(jià)值，如果A指向B，則說明B也是一個(gè)重要網(wǎng)頁。 HITS算法是由康奈爾大學(xué)的Kleiberg博士于1998年首次提出， HITs的全稱Hyperlink-Induced Topic Search，是基于鏈接分析的網(wǎng)頁排名算法。,HITs算法,HITS算法描述兩種類型的網(wǎng)頁： 1） 權(quán)威型（Authority）網(wǎng)頁，對于一個(gè)特定的檢索，該網(wǎng)頁提供最好的相關(guān)信息。 2）目錄型（Hub）網(wǎng)頁，該網(wǎng)頁提高很多指向其他高質(zhì)量權(quán)威型網(wǎng)頁的超鏈接 。 由此，我們可以在每個(gè)網(wǎng)頁上定義 “權(quán)威型權(quán)值”和 “目錄型權(quán)值

12、”兩個(gè)參數(shù)。,HITs算法,如果一個(gè)網(wǎng)頁有大量的鏈接指向其他網(wǎng)頁，則這個(gè)網(wǎng)也就可能是一個(gè)好的Hub；一個(gè)網(wǎng)頁如果被大量的鏈接所指，那么它就可能是一個(gè)好的Authority。 HITS算法的基本思想 1）好的Hub型網(wǎng)頁指向好的Authority網(wǎng)頁 2）好的Authority網(wǎng)頁是由好的Hub型網(wǎng)頁所指向的網(wǎng)頁,HITS算法,1）HITS通過搜索引擎查詢主題詞，生成初始網(wǎng)頁集合，稱為根集合。由于根集合中有些網(wǎng)頁包含指向權(quán)威網(wǎng)頁的鏈接，因此，對根集合進(jìn)行網(wǎng)頁擴(kuò)展生成基集合，其中包括根集合指向的網(wǎng)頁以及鏈接到根集合中的網(wǎng)頁。 2）給基集合中的每個(gè)網(wǎng)頁賦予一個(gè)Hub權(quán)值hp和一個(gè)權(quán)威權(quán)值ap，初始值

13、為同一個(gè)非負(fù)常數(shù)，然后對hp和ap進(jìn)行運(yùn)算。 ，其中網(wǎng)頁q指向網(wǎng)頁p ，其中網(wǎng)頁q由網(wǎng)頁p指向,HITS算法,通過迭代遞歸計(jì)算網(wǎng)頁的Hub權(quán)值和權(quán)威權(quán)值 3）HITS輸出與給定主題對應(yīng)的一些具有較大Hub權(quán)值的網(wǎng)頁和具有較大權(quán)威權(quán)值的網(wǎng)頁，即重要的網(wǎng)頁。,PageRank與HITS的比較,共同特點(diǎn)：PageRank和HITS的迭代算法都利用了特征向量作為理論基礎(chǔ)和收斂性依據(jù)。 區(qū)別： 1）權(quán)值傳播模型 2） 處理對象 3） 具體應(yīng)用,PageRank與HITS的比較,從兩者的權(quán)值傳播模型來看： PageRank基于隨機(jī)沖浪模型將網(wǎng)頁權(quán)值直接從Authority網(wǎng)頁傳遞到Authority網(wǎng)頁。

14、 HITS將Authority網(wǎng)頁的權(quán)值經(jīng)過hub網(wǎng)頁的傳遞進(jìn)行傳播。,PageRank與HITS的比較,從兩者的處理對象來看： 都是針對整個(gè)Web上的網(wǎng)頁的一個(gè)自集進(jìn)行排序、篩選，沒有一個(gè)搜索引擎能夠?qū)⒄麄€(gè)Interent上的網(wǎng)頁全部搜索下來。但是 PageRank的處理對象是一個(gè)搜索引擎當(dāng)前搜索下來的所有網(wǎng)頁，一般在幾千萬個(gè)頁面以上。 HITS的處理對象是搜索引擎針對具體查詢主題所返回的結(jié)果，從幾百個(gè)頁面擴(kuò)展到幾千幾萬個(gè)頁面。,PageRank與HITS的比較,從兩者的具體應(yīng)用來看： PageRank應(yīng)用于搜索引擎服務(wù)端，可以直接用于關(guān)鍵字查詢并獲得較好的結(jié)果；若要用于全文查詢，需要與其他

15、相似度判定標(biāo)準(zhǔn)（向量模型等）進(jìn)行復(fù)合，以針對具體查詢形成最終排名。 HITS一般用于全文搜索引擎客戶端，對寬主題的搜索相當(dāng)有效，可以用于自動編撰Web分類目錄，通過找到指向某網(wǎng)頁的Hub網(wǎng)頁并以此為根集，可以查到該網(wǎng)頁的相關(guān)網(wǎng)頁；對于較窄主題的檢索，HITS的能力還較弱，因?yàn)楦?，篩選的效果將不會很好。,PageRank與HITS的比較,總之， PageRank算法和HITS算法是具有代表性的兩個(gè)網(wǎng)頁排序算法，前者更適合于搜索引擎的服務(wù)器端，后者更適合于搜索引擎的客戶端。 PageRank算法和HITS算法為發(fā)現(xiàn)核心網(wǎng)頁與網(wǎng)頁之間的關(guān)系提供了基本的思路和方法。,第三代搜索引擎,目前搜索引擎

16、基本上都采用基于關(guān)鍵詞匹配的全文檢索技術(shù)，使得檢索效果未能實(shí)現(xiàn)質(zhì)的飛躍，發(fā)展知識化、智能化的搜索引擎成為必然趨勢，概念檢索是關(guān)鍵技術(shù)之一。,第三代搜索引擎,概念是關(guān)于具有共同屬性的一組對象、事件或符號的知識，是客觀事物在頭腦中的反映，要通過字、詞、詞組等概念描述元素表達(dá)出來。 同一個(gè)概念可以由多個(gè)描述元素來表達(dá)，這些描述元素在此概念的約束下構(gòu)成了同義關(guān)系。 概念并不是獨(dú)立存在的，一個(gè)概念總是與其他概念之間存在著關(guān)系，根據(jù)概念之間的相互聯(lián)系，形成的是語義的關(guān)系網(wǎng)。,第三代搜索引擎,同義詞擴(kuò)展：自行車腳踏車單車 語義蘊(yùn)涵擴(kuò)展：操作系統(tǒng)計(jì)算機(jī)軟件應(yīng)用軟件 語義相關(guān)擴(kuò)展：微軟微軟視窗Window NT

17、,第三代搜索引擎,概念檢索是通過對文檔原文信息進(jìn)行語義上的自然語言處理，析取出各種概念信息，形成一個(gè)知識庫，從概念意義層次上來處理用戶的檢索提問式，不僅能檢索出包含提問式中的關(guān)鍵詞的結(jié)果，還能檢索出包含那些與該詞同屬一類概念的詞匯的結(jié)果。,第三代搜索引擎,概念檢索是能夠利用信息的語義知識，“理解”用戶的檢索需求，通過知識學(xué)習(xí)，分析理解和推理歸納來實(shí)現(xiàn)檢索的“智能化”，突破關(guān)鍵詞匹配局限于表面形式的缺陷。,第三代搜索引擎,構(gòu)建概念語義網(wǎng)絡(luò) 概念語義網(wǎng)絡(luò)可以看做一個(gè)帶標(biāo)識的分類樹。節(jié)點(diǎn)表示概念，節(jié)點(diǎn)之間的連線表示概念之間的關(guān)系：其中實(shí)線表示概念之間的內(nèi)涵和外延上的豎向?qū)哟侮P(guān)系，虛線表示相關(guān)概念之間

18、的橫向聯(lián)系。 A 計(jì)算機(jī)軟件 計(jì)算機(jī)廠商 應(yīng)用軟件 操作系統(tǒng) 國外廠商 國內(nèi)廠商 微軟視窗 微軟 ,第三代搜索引擎,概念檢索的具體實(shí)現(xiàn)： 概念節(jié)點(diǎn)是語義網(wǎng)絡(luò)的基本元素，屬性描述如下：,第三代搜索引擎,struct Concept char number; /概念意義分類代碼 char name; /概念意義描述 int fathnum; /父概念個(gè)數(shù) int bronum; /兄弟概念個(gè)數(shù) int sonnum; /下層概念個(gè)數(shù) int relnum; /相關(guān)概念個(gè)數(shù) char * synonym; /指向該概念的集合的指針 struct Concept *father; /指向父概念的指針 struct Concept *brother; /指向所有兄弟概念的指針 struct Concept *son; /指向所有子概念的指針 struct Concept *relation; /指向所有相關(guān)概念的指針 ,第三代搜索引擎,其中概念意義分類代碼（num