南昌網站建設

個性化網頁權重PageRank算法研究

發布日期:2017-03-29 作者: 點擊:

       目前關于個性化PageRank,其他的常見方法還有模型化PageRank(modular PageRank)和BlockRank等。這些方法在具體的計算方法上,主要的特點體現在從效率的角度上對算法進行了必要的優化。


       關于加速PageRank算法的先前研究內容主要使用稀疏性圖結構技術,比如Arasu等提出的觀點,他們不僅僅單純使用上次迭代循環產生值來計算本輪循環值,也使用本輪循環已經產生的值來加速本輪循環的計算。甚至提出了Web網絡的蝴蝶結結構,并將其用于PageRank值的有效計算中。然而這些方法并不具有很大的實用性,主要原因在于算法要求對Web網絡矩陣進行排序,這個操作需要按照深度搜索優先的原則進行網絡遍歷,這顯然是一種代價極大的運算。最近Kamvar等也提出一些算法,使用連續中間循環來推斷真實PageRank更好的估計值,但是仍然存在受PageRank算法初始參數影響的不足之處。


       目前對于Web網絡圖結構的分析主要關注于研究圖的屬性,如節點的分布、網頁鏈接的情況和Web網頁圖結構的建模等。然而,對于這些研究并沒有強調如何有效利用這些屬性來加快超鏈分析。


       不少學者提出了一些改進做法,如Raghavan和Garcia-Molina等利用主機名稱或者URL隱含的Web結構來代表Web圖更為成功的做法也有很多,如Jeh和Widom通過有限修改網頁的權值來表達的個性化網頁權重,這個重要性權值可以反映用戶指定的初始興趣網頁。由于對個性化視圖的計算需要反復遍歷整個Web圖結構中的網頁,這只有在運行期間才能實現,所以事先計算和存儲所有的個性化視圖并不現實。他們利用新的圖論結果和技術構建出表達個性化視圖的“偏好向量”(partial vector),它可以在不同用戶的個性化視圖中共享,同時關于它的計算和存儲花費與視圖數量的多少呈現出合理的比例。在計算中,還可以采用遞增式計算,這就使得在查詢期間利用偏好向量去構建個性化視圖是可行的。這個偏好向量即為個性化PageRank向量(personalized PageRank vector,PPV),通俗地說,PPV是種Web網頁的個性化視圖。按照這個PPV來對網頁結果進行排序可以有效地表達用戶的偏好。


       簡單地看,每個PPV的長度都為咒,即Web的網頁數量。但是由于從一個固定的角度循環計算PPV需要多次遍歷Web網頁圖,這顯然是不可能作為一種在線響應用戶查詢的方式。從另一個角度來看,所有PPV向量的總數量會達到2n(n為網頁總數),這顯然又過于巨大而無法實現離線存儲。所以,必須將p集合中出現的網頁限制為hub網頁集合H的子集。H集合通常包含一些用戶最為感興趣的網頁。在實踐中,H集合可以是具有較高PageRank值的網頁集合(重要網頁)、在人工分類目錄中的網頁(如Yahoo和Open Directory)、特定企業或程序的重要網頁等。H集合可以看成是計算個性化的基礎。這種基于PPV的計算方式,不像傳統的方式,能夠和H集合大小成良好的比例縮放關系,并且這種技術也可以在更大的PPV集合上取得近似的效果,滿足一些對于任意偏好網頁集合的個性化計算要求。


       除此以外,還有一些在計算效果上進行改進的算法。


       如一種較為成功的做法是BlockRank方法,它主要是充分利用Web網頁間鏈接結構呈現一種塊狀結構的特征來改進算法效率。關于Web網絡塊狀結構的特征,已有很多學者進行了論證。例如,據Bharat等的分析,通過對比分析Web網絡的鏈接結構,可以發現近80%左右的網頁超鏈都是同一站點主機內部不同網頁間形成的,而不同主機站點間網頁的超鏈比重僅為20%左右。如果去除無用的死鏈接,這一比重表現得更加不平衡,近似于9:l。進一步將考察范圍限定在域名級別后,上述的兩個比重都有明顯的增加,一為84:16,二為95:5,不平衡性明顯加劇。一般在一個主機站點內,大部分的超鏈由于導航和站點安排,往往會在幾個關鍵的網頁上具有較多的內部鏈接。例如,高校站點內一般會對諸如圖書館、教務處和學生處等網頁產生很高的鏈接比重。其實這種內部鏈接較高、外部鏈接較低的情況在不同級別的Web網頁圖結構中廣泛存在,產生了明顯的塊化現象,而且大部分的塊結構都遠遠小于整個Web的圖結構。


       這種Web網絡所具有的塊化結構有助于快速計算PageRank,同時為表達個性化PageRank提供了良好的基礎。這個算法的思路大體描述如下:先對每個主機的網頁計算本地化的PageRank值,得到在主機內部的相對重要權值。這些本地化的PageRank向量可以進一步按照不同Web網頁塊的相對重要程度加權形成全局PageRank值的近似值,然后將此PageRank向量作為標準PageRank算法的起始向量。不可否認,個性化PageRank雖然是個非常吸引人的主意,但是它需要對大規模的PageRank向量進行有效的迭代計算,而使用BlockRank算法和對沖浪者的隨機沖浪行為做簡單的限制就可以有效地減少個性化PageRank值的計算復雜度。這個限制就是當他厭倦時,他并不是從諸多網頁中選擇,而是從主機站點中進行選擇。也就是說,此時無需考察沖浪者跳轉的網頁,而只考慮跳轉的站點。這時構造的個性化向量具有的維度就是Web網絡中主機的個數K,并且向量的元素值也反映沖浪者對不同主機的偏好程度。有了這個限制,本地化PageRank向量就無需針對不同的個性化用戶而改變。事實上,本地化的PageRank向量也不會因為矩陣B結構的改變而改變,只有BlockRank向量6才會因為不同的個性化特征而改變,因此只需對每個基于塊結構的個性化PageRank向量進行重新計算。


       應該說,不論從理論上看,還是從實踐上看,利用個性化PageRank來實現搜索引擎的個性化服務是個非??尚械倪x擇,適應Web網絡資源對信息檢索提出的特點要求。它不僅在推薦結果內容上綜合考慮網頁客觀性權重這個重要指標,而且該方法性能較高,主要計算工作都在離線階段完成。然而,這些現有的個性化PageRank技術都需要用戶登錄并主動提交個性化信息,卻忽略了用戶對Web網頁的理解,沒有挖掘用戶使用行為,收集用戶個性化信息的方式不自然,這顯然加重了用戶的使用負擔。所以,雖然說節省了用戶挑選相關網頁的時間,但是用戶卻需要花更多的時間去實現搜索個性化。由此可以看出,探討獲取用戶個性化信息的其他有效形式將是提高此方法效果的關鍵所在,本書也主要對此進行研究,探尋更好的個性化信息收集和表達方法以適用于個性化PageRank算法中,該方法較為客觀和全面。


相關標簽:南昌網站制作

最近瀏覽:

在線客服
分享
歡迎給我們留言
請在此輸入留言內容,我們會盡快與您聯系。
姓名
聯系人
電話
座機/手機號碼
吉泽明步在办公室被强,国产激情电影综合在线看,国产国产乱老熟视频网站