對Google搜索引擎PageRank算法研究

模式識別論文題目：對Google搜索引擎PageRank算法研究姓名：學(xué)號：學(xué)院：國際軟件學(xué)院指導(dǎo)老師：教授2023年12月摘要隨著網(wǎng)絡(luò)技術(shù)的迅猛開展,WWW已成為信息發(fā)布、交互及獲取的主要工具,它涉及新聞、廣告、消費(fèi)、金融、教育、電子商務(wù)等許多領(lǐng)域。Web具有四個特點(diǎn):龐大性、動態(tài)性、異構(gòu)性、半結(jié)構(gòu)化的數(shù)據(jù)結(jié)構(gòu)環(huán)境。此外,Web還包含豐富和動態(tài)的超鏈接資源。面對Web這些固有特點(diǎn),人們要從這些海量的數(shù)據(jù)中查找數(shù)據(jù)和信息,使用最多的就是搜索引擎技術(shù)。搜索引擎技術(shù)的開展是隨著電子技術(shù)不斷進(jìn)步的信息數(shù)字化和數(shù)據(jù)網(wǎng)絡(luò)化的必然產(chǎn)物，網(wǎng)頁排序算法一直是搜索引擎的核心技術(shù)之一。Google搜索引擎依靠其PageRank機(jī)制及收斂算法一直處于該領(lǐng)域的領(lǐng)先地位。本文首先說明了國內(nèi)外搜索引擎排名算法的研究背景、開展現(xiàn)狀，然后分析了搜索引擎的工作原理和關(guān)鍵技術(shù)。然后，剖析了傳統(tǒng)PageRaak算法和已改進(jìn)的PageRank算法，分析了它們存在的優(yōu)、缺點(diǎn)，為我們進(jìn)一步改進(jìn)PageRank算法提供了可能性。關(guān)鍵詞Google搜索引擎PageRank算法目錄第1章緒論41.1引言41.2研究背景51.3國內(nèi)外研究現(xiàn)狀6第2章搜索引擎的相關(guān)知識72.1搜索引擎開展歷史72.2搜索引擎工作原理8第3章經(jīng)典搜索引擎PageRank算法研究102.1PageRank的根本概念102.2PagPank算法的分析112.1PagPank算法的原理142.2PagPank算法的評價及現(xiàn)有改進(jìn)方法16第4章展望和總結(jié)162.1展望162.2總結(jié)17緒論引言當(dāng)前因特網(wǎng)上有大量站點(diǎn)正在不斷地從廣闊用戶當(dāng)中搜索數(shù)據(jù)，并利用機(jī)器學(xué)習(xí)和統(tǒng)計方法從中獲得需要的信息。Google搜索引擎作為其中的佼佼者，它不僅可以利用網(wǎng)絡(luò)鏈接對網(wǎng)頁進(jìn)行排名，而且當(dāng)其廣告被不同的用戶選定時，它會持續(xù)搜集信息，這使得Google能夠更加有效地進(jìn)行廣告定位。它目前被公認(rèn)為是全球規(guī)模最大的搜索引擎，它提供了簡便人性化的各種免費(fèi)效勞，用戶可以在很短的時間內(nèi)得到相關(guān)的搜索結(jié)果。一個優(yōu)秀的搜索引擎應(yīng)該及時向用戶提供所需要的最重要最有價值的網(wǎng)頁信息并將其排在前面，然而這種及時，高效，高質(zhì)量的顯示結(jié)果必然需要一個強(qiáng)大的搜索算法給予支持。大家普遍相信，Google從一個研究型工程迅速崛起為世界范圍內(nèi)最受歡送的搜索引擎，這在很大程度上歸功于它的RageRank網(wǎng)頁排名機(jī)制及其收斂加速算法的進(jìn)一步開展。這種基于鏈的網(wǎng)頁排名的巧妙之處在于它把整個互聯(lián)網(wǎng)當(dāng)作了一個整體的結(jié)構(gòu)來看待，這無意識的符合了系統(tǒng)論和整體的觀點(diǎn)。Google搜索引擎在信息采集上處于領(lǐng)先地位，其得到的龐大索引數(shù)據(jù)庫不單純追求網(wǎng)頁鏈接的數(shù)量，同時采取了一些很有力的篩選和過濾措施。這也使得基于鏈分析的網(wǎng)頁排序(PageRank)受人為控制因素大為減少或者說是微缺乏道的，并且響應(yīng)速度快同時也不影響網(wǎng)頁排名的質(zhì)量。在學(xué)術(shù)界,這個網(wǎng)頁排序算法被公認(rèn)為是文獻(xiàn)檢索中最大的奉獻(xiàn)之一，并且被很多大學(xué)引入了信息檢索課程的教程。因此，對網(wǎng)頁排序算法(PageRank算法)的分析、探索、研究和應(yīng)用具有重大的現(xiàn)實意義。研究背景隨著信息技術(shù)的快速開展，互聯(lián)網(wǎng)已成為人們工作、學(xué)習(xí)最重要的知識來源和信息來源。根據(jù)中國互聯(lián)網(wǎng)絡(luò)信息中心2023年1月發(fā)布的《第25次中國互聯(lián)網(wǎng)絡(luò)開展?fàn)顩r統(tǒng)計報告》，截止到2023年12月，我國上網(wǎng)用戶規(guī)模到達(dá)3．84億人，互聯(lián)網(wǎng)普及率到達(dá)28．996?；ヂ?lián)網(wǎng)之所以有如此多的網(wǎng)民，主要在于互聯(lián)網(wǎng)上的信息幾乎包容人類開展過程中的所有知識，并且還在以幾何級的速度在增長?；ヂ?lián)網(wǎng)在給人們帶來大量信息的同時，也出現(xiàn)了一些問題，比方，在眾多雜亂的信息中如何迅速檢索到有效信息，以及搜索結(jié)果不能到達(dá)用戶需要等問題。因此，搜索引擎已成為互聯(lián)網(wǎng)的重要組成局部，對互聯(lián)網(wǎng)的進(jìn)一步普及產(chǎn)生著巨大的影響。由于互聯(lián)網(wǎng)的迅速開展，互聯(lián)網(wǎng)上的信息呈現(xiàn)著信息量大且分散，自治性強(qiáng)，資源多樣的特點(diǎn)。因此，現(xiàn)有搜索引擎搜索出來的結(jié)果有時存在不一致和不完整，出現(xiàn)這種問題的原因，可以總結(jié)為以下幾個方面：1．互聯(lián)網(wǎng)上存在一些信息量很少、價值很一般的網(wǎng)頁。2．互聯(lián)網(wǎng)還存在著一詞多義，同一個詞在不同主題，不同領(lǐng)域，有其特殊的含義。當(dāng)用戶在查詢時，搜索引擎就會將各種情況都糅合在一起提交給用戶。3．重復(fù)頁面多。由于常用文檔的廣泛傳播和著名網(wǎng)頁被其它站點(diǎn)的引用，互聯(lián)網(wǎng)上有許多的重復(fù)頁面。研究說明，互聯(lián)網(wǎng)上有60％的頁面是重復(fù)頁面。4．大多數(shù)搜索引擎采用基于關(guān)鍵詞的檢索算法。因此，有一些人或公司就專門針對這方面進(jìn)行研究，為了提高自己網(wǎng)頁的檢索排名，采用一些不正當(dāng)?shù)氖侄巍＿@樣搜索引擎在搜索時就會優(yōu)先搜索出質(zhì)量一般的網(wǎng)頁提交給用戶。面對互聯(lián)網(wǎng)的種種問題，如何快速、準(zhǔn)確地從互聯(lián)網(wǎng)上獲取有價值的信息，就成為評價搜索引擎的重要指標(biāo)，搜索引擎的排序算法也就成為了人們關(guān)注的主題。國內(nèi)外研究現(xiàn)狀PageRank算法是1998年由SergeyBrin和LawrencePage[31提出的基于鏈接分析的網(wǎng)頁排序算法。同年，J．Kleinberg提出了HITS算法，接著相繼出現(xiàn)了，如ARC、SALSA、PHITS等基于鏈接分析的頁面分級算法。這些算法在實際的應(yīng)用和使用中，取得了很好的效果。Google是目前世界上很受歡送的搜索引擎之一，它提供了較高的準(zhǔn)確率和快速搜索速度，這主要因為是Google使用了復(fù)雜的文本匹配算法和PageRank算法相結(jié)合的技術(shù)。在PageRank算法的根底上，很多學(xué)者相繼提出了改進(jìn)后的一些PageRank算法。比方華盛頓大學(xué)計算機(jī)科學(xué)與工程系的MatthewRichardson和PedroDominggos提出的結(jié)合鏈接和內(nèi)容信息的PageRank算法。還有，斯坦福大學(xué)TaherHaveliwalat等人提出的主題敏感的PageRank算法。在國內(nèi)，也有一些學(xué)者提出了基于PageRank算法的改進(jìn)算法，比方，上海交通大學(xué)宋聚平博士提出的結(jié)合網(wǎng)頁HTML語言的PageRank算法，以及北京大學(xué)計算機(jī)系提出的利用HTTP協(xié)議，記錄網(wǎng)頁最近一次被修改時間，作為控制參數(shù)，計算網(wǎng)頁的排名。PageRank算法中對于網(wǎng)頁鏈出是同等對待，對于不同鏈接是不考慮其重要性的，然而，在實際的Web鏈接中，不同鏈接其重要性是不同的。因此，J．Kleinberg就提出了HITS算法嘲，該算法引入了中心頁(Hub)和權(quán)威頁(Authority)，讓其互相加強(qiáng)，從而找到Authority網(wǎng)頁，實現(xiàn)Web結(jié)構(gòu)及資源的自動發(fā)現(xiàn)。搜索引擎的相關(guān)知識2.1、搜索引擎開展歷史1994年至今，搜索引擎的開展無論是在數(shù)量還是質(zhì)量上都發(fā)生了很大的變化。第一代搜索引擎的索引網(wǎng)頁的數(shù)量少于100萬個j很少重新搜集網(wǎng)頁和更新索引，而且這一時期的搜索引擎檢索速度非常慢，一般都需要等待很長的時間。在實現(xiàn)技術(shù)上，根本上是沿用較為成熟的信息檢索技術(shù)，網(wǎng)絡(luò)技術(shù)和數(shù)據(jù)庫等技術(shù)。實際上，第一代搜索引擎是利用一些現(xiàn)有技術(shù)，實現(xiàn)一個互聯(lián)網(wǎng)上的應(yīng)用。在當(dāng)時，網(wǎng)絡(luò)搜索程序每天承受大約1500次的查詢。第二代以A1tavista為代表的搜索引擎，大多采用分布式方式來提高數(shù)據(jù)的規(guī)模、響應(yīng)速度和用戶數(shù)量等關(guān)鍵技術(shù)，這一時期的搜索引擎一般都保持大約一個5000萬網(wǎng)頁的索引數(shù)據(jù)庫，每天能夠滿足1000萬次的用戶檢索請求。第三代搜索引擎是指1998年開始開展起來的搜索引擎，這一時期的搜索引擎不僅索引數(shù)據(jù)庫規(guī)模空前的大，而且還出現(xiàn)了主題搜索和地域搜索，搜索數(shù)量和搜索質(zhì)量也明顯提高，出現(xiàn)了搜索引擎的鼎盛時代。2.2、搜索引擎的工作原理根據(jù)搜索引擎的分類，我們可以給搜索引擎下個定義，搜索引擎就是指從互聯(lián)網(wǎng)上搜集大量的網(wǎng)頁，這些網(wǎng)頁數(shù)量可以是幾千萬到幾十億，將搜集的網(wǎng)頁中的關(guān)鍵字進(jìn)行檢索，建立索引數(shù)據(jù)庫的全文搜索引擎。當(dāng)用戶需要查找某個關(guān)鍵詞，并將該關(guān)鍵詞輸入，進(jìn)行查詢的時候，包含該關(guān)鍵詞的所有網(wǎng)頁都將作為檢索到的結(jié)果被檢索出來，再經(jīng)過排序算法計算之后，檢索出的頁面就將按照與該關(guān)鍵詞相關(guān)度上下的順序排列起來?，F(xiàn)有搜索引擎中普遍采用的技術(shù)是超鏈接分析技術(shù)，這種技術(shù)在分析網(wǎng)頁時，不僅要分析索引頁中的文字，還要分析索引指向該網(wǎng)頁的錨文檔，甚至還要分析鏈接到網(wǎng)頁周圍的文字。因此，這種技術(shù)的運(yùn)用為提高查詢結(jié)果的準(zhǔn)確率提供了可能。一般來說，搜索引擎系統(tǒng)的搜索過程是由三個階段來完成，即抓取網(wǎng)頁、加工處理、查詢效勞這三個階段。在組成上，搜索引擎一般是由蜘蛛程序(也叫網(wǎng)頁爬行器)、切詞器、索引器、查詢器幾局部組成。蜘蛛程序其實是一個搜索程序，主要負(fù)責(zé)網(wǎng)頁信息的獲取工作，一般是同切詞器和索引器一起使用，它們共同負(fù)責(zé)將抓取到的網(wǎng)頁內(nèi)容進(jìn)行分詞處理，并自動加注標(biāo)引，建立索引數(shù)據(jù)庫。查詢器是根據(jù)用戶提出的查詢條件檢索索引數(shù)據(jù)庫，并對檢索出的結(jié)果進(jìn)行集合運(yùn)算和排序，再提取出網(wǎng)頁中的簡單摘要信息提供應(yīng)需要查詢的用戶。根據(jù)搜索引擎處理信息的過程，可以將搜索引擎的工作原理分為三個步驟。從互聯(lián)網(wǎng)上抓取網(wǎng)頁利用Spider程序或者Robot機(jī)器人程序，從互聯(lián)網(wǎng)上自動抓取網(wǎng)頁，并沿著任何網(wǎng)頁中的所有的URL地址反復(fù)搜索其他網(wǎng)頁，并將這些網(wǎng)頁進(jìn)行收集、整理。建立索引數(shù)據(jù)庫由分析索引系統(tǒng)程序?qū)κ占貋淼木W(wǎng)頁進(jìn)行分析，根據(jù)一定的算法進(jìn)行大量復(fù)雜的相關(guān)度計算處理，根據(jù)這些算法，利用網(wǎng)頁中的網(wǎng)頁文字和鏈接的每一個關(guān)鍵詞的相關(guān)度，建立網(wǎng)頁索引數(shù)據(jù)庫。搜索排序當(dāng)用戶輸入關(guān)鍵詞要求搜索后，由搜索系統(tǒng)程序從網(wǎng)頁索引數(shù)據(jù)庫中找到和該關(guān)鍵詞相符合的所有關(guān)聯(lián)的網(wǎng)頁，然后根據(jù)已有的相關(guān)度算法，對搜集到的網(wǎng)頁進(jìn)行相關(guān)度數(shù)值的排序，相關(guān)度越高的網(wǎng)頁，排名就越靠前。最后，系統(tǒng)將搜索結(jié)果返回給用戶，返回的頁面中包括搜索結(jié)果的鏈接地址和頁面內(nèi)容摘要等信息。經(jīng)典搜索引擎PageRank算法研究搜索引擎排序算法就是將搜索引擎查詢結(jié)果按照一定規(guī)那么排序，提供應(yīng)用戶的一種方法?，F(xiàn)有的大多數(shù)搜索引擎是以PageRank算法、HITS算法為根底，通過鏈接關(guān)系找到相比照擬重要的網(wǎng)頁，在此根底上，進(jìn)行改進(jìn)，形成綜合的排序算法。3．1、PageRank的根本概念PageRank(網(wǎng)頁級別)，2001年9月被授予美國專利，專利人是Google創(chuàng)始人之一拉里·佩奇〔LarryPage〕。因此，PageRank里的page不是指網(wǎng)頁，而是指佩奇，即這個等級方法是以佩奇來命名的。它是Google排名運(yùn)算法那么〔排名公式〕的一局部，是Google用于用來標(biāo)識網(wǎng)頁的等級/重要性的一種方法，是Google用來衡量一個網(wǎng)站的好壞的重要標(biāo)準(zhǔn)之一。在揉合了諸如Title標(biāo)識和Keywords標(biāo)識等所有其它因素之后，Google通過PageRank來調(diào)整結(jié)果，使那些更具“等級/重要性〞的網(wǎng)頁在搜索結(jié)果中令網(wǎng)站排名獲得提升，從而提高搜索結(jié)果的相關(guān)性和質(zhì)量。其級別從1到10級，10級為總分值。PR值越高說明該網(wǎng)頁越受歡送〔越重要〕。例如：一個PR值為1的網(wǎng)站說明這個網(wǎng)站不太具有流行度，而PR值為7到10那么說明這個網(wǎng)站非常受歡送〔或者說極其重要〕。一般PR值到達(dá)4，就算是一個不錯的網(wǎng)站了。Google把自己的網(wǎng)站的PR值定到10，這說明Google這個網(wǎng)站是非常受歡送的，也可以說這個網(wǎng)站非常重要。3.2、PagPank算法的分析網(wǎng)頁級別算法作為網(wǎng)頁的組織管理工具，充分利用了互聯(lián)網(wǎng)的巨大鏈接結(jié)構(gòu)，即一個網(wǎng)頁被其他網(wǎng)頁鏈接的數(shù)量就決定了該網(wǎng)頁的重要性。網(wǎng)頁分級算法可以保證系統(tǒng)對用戶的需求給出快速響應(yīng)，把最重要的網(wǎng)頁優(yōu)先顯示給用戶。研究者分析發(fā)現(xiàn)在網(wǎng)絡(luò)上超級鏈接的結(jié)構(gòu)是非常豐富、重要的資源。如果能夠充分利用超鏈接的結(jié)構(gòu)，就可以很方便的實現(xiàn)網(wǎng)頁的分級?；谶@種超鏈接的思想，SergryBrin和LawrencePage在1998年提出了PageRaak算法，基于Google的復(fù)雜文本匹配算法和搜索程序所使用的就是PageRank算法相結(jié)合的技術(shù)。通過PageRank算法在Google中的使用，可以證明，該技術(shù)運(yùn)用在搜索引擎中是非常有效的，特別是在網(wǎng)絡(luò)資源膨脹的情況下。網(wǎng)絡(luò)資源的膨脹必然會產(chǎn)生很多的鏈接，這些鏈接的產(chǎn)生就為評價文件的重要性提供了更多的依據(jù)。在網(wǎng)頁分級算法中，除了考慮網(wǎng)頁鏈接的數(shù)量之外，還要考慮分析被鏈接的網(wǎng)頁。對于重要的、高質(zhì)量的網(wǎng)頁在搜索結(jié)果中可以得到較高的網(wǎng)頁級別，從而獲得較靠前的排名。所以，網(wǎng)頁級別就成為網(wǎng)頁重要性綜合指標(biāo)，代表了網(wǎng)頁本身的特性，是網(wǎng)頁數(shù)據(jù)采用評定鏈接結(jié)構(gòu)的綜合運(yùn)算方法進(jìn)行分析的結(jié)果。經(jīng)過分析，得到高評價的重要頁面就會給予較高的網(wǎng)頁等級，那么它在搜索結(jié)果內(nèi)的排名也就會相應(yīng)提高。網(wǎng)頁的等級一般是由該頁面的鏈入數(shù)量和該頁面的鏈入網(wǎng)頁的PR值，以及該頁面的鏈入網(wǎng)頁的鏈出數(shù)量決定的。因此，假設(shè)要計算網(wǎng)頁A的等級，那么它的PR值就是鏈入網(wǎng)頁A的頁面除以該頁面的鏈入頁面本身的鏈出數(shù)量的和，因此，其算法就可以定義如下：其中，PR(A)是頁面A的級別，PR(Ti)是頁面T。的級別，頁面Ti鏈向頁面A,C(Ti)是頁面T。鏈出的鏈接數(shù)量，d是阻尼系數(shù)，它的取值在01之間，根據(jù)LawrencePage和SergeyBrin給出的實際值，一般將d在應(yīng)用中設(shè)為O．85。PR(Tn)／(Tn)表示為每一個指向A頁面的頁面，重復(fù)相同的操作步驟。該算法不以站點(diǎn)排序，頁面的級別是由一個個獨(dú)立的頁面決定，每個鏈入頁面的奉獻(xiàn)值都是不同的。如果T頁面中鏈出越多，它對當(dāng)前頁面的A的奉獻(xiàn)就越小。A的鏈入頁面越多，其網(wǎng)頁級別也越高。因此，決定頁面級別的因素，主要是其頁面的鏈入頁面數(shù)量。阻尼系數(shù)的使用，可以減少其他頁面對當(dāng)前頁面A的排序奉獻(xiàn)。LawrencePage和SergeyBrin在解釋該算法時提出了用戶行為的隨機(jī)沖浪模型(TheRandomSurferModel)，他們把用戶點(diǎn)擊鏈接的行為視為一種不關(guān)心內(nèi)容的隨機(jī)行為。用戶單擊頁面內(nèi)的鏈接概率，完全由頁面上的鏈接數(shù)量決定。一個頁面通過隨機(jī)沖浪到達(dá)的概率就是鏈入它的別的頁面上鏈接的被單擊概率的和。阻尼系數(shù)的引入，是因為用戶不可能無限地單擊鏈接，常常會因為勞累而隨機(jī)跳入另一個頁面。d可以看作用戶無限單擊下去的概率，卜d就是頁面本身所具有的網(wǎng)頁級別。對于公式3．1的PageRank算法，可以進(jìn)行修訂，得到公式3．2。其中，N是互聯(lián)網(wǎng)上所有網(wǎng)頁的數(shù)量。在公式3．1中，隨機(jī)沖浪訪問某個頁面的概率由互聯(lián)網(wǎng)的總數(shù)決定，而在公式3．2中，網(wǎng)頁級別是一個頁面被隨機(jī)訪問的期望值(為了計算簡單，計算中是不考慮N的值的)。3.3、PagPank算法的原理對于PageRank算法的原理，可以用圖表來闡述。假設(shè)有五個網(wǎng)頁A，B，C，D和E，他們相互鏈接。為了計算簡單，可以將阻尼系數(shù)d設(shè)為O．5。那么下面我們計算一下鏈接后這五個網(wǎng)頁各自的PageRank的情況。PR(A)=0．5+0．5PR(D)PR(B)=0．5+0．5(PR(A)／2)PR(C)=O．5+0．5(PR(B)／2)PR(D)=0．5+0．5(PR(A)／2+PR(C)+PR(E))PR(E)=0．5+0．5(PR(B)／2)解得：PR(A)=I．25925926PR(B)=O．81481482PR(C)=0．70370370PR(D)=1．51851852PR(E)=0．70370370有：PR(A)+PR(B)+PR(C)+PR(D)+PR(E)=5在計算過程中，先給每個網(wǎng)頁一個初始值。在迭代過程中，每個網(wǎng)頁的網(wǎng)頁級別的和是收斂于整個網(wǎng)絡(luò)頁面數(shù)的。所以，每個頁面的平均網(wǎng)頁級數(shù)是l，實際上的值在(1-d)和(州l-d))之間。它們的迭代過程如表3所示。表3迭代過程表通過迭代計算，直到每個頁面的數(shù)值逼近一個定值，最后發(fā)現(xiàn)，D的PageRaak最高。分析后，可以對外部鏈接和最終的PagePank值做出如下的對照。對照發(fā)現(xiàn)，鏈入頁面越多的網(wǎng)頁，其排名也就越靠前。3.4、PagPank算法的評價及現(xiàn)有改