搜索引擎的數(shù)學(xué)模型及其應(yīng)用_第1頁
已閱讀1頁,還剩7頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、第36卷第3期JoumaIofSouthw西est南Un民iv族e(cuò)rs大ity學(xué)fo學(xué)rN報(bào)ati。on自al然itie苧sN學(xué)at版uralScienceEditionMay201oI1‘一。文章編號(hào):10032843(2010)03048007Google搜索引擎的數(shù)學(xué)模型及其應(yīng)用趙國,宋建成(西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,四川成都610041)摘要:該文在闡明Google搜索引擎中關(guān)鍵的頁面等級算法(PageRallk)原理的

2、基礎(chǔ)上,分析了PageRank算法的隨機(jī)沖浪模型,并著重討論相應(yīng)的數(shù)學(xué)模型在足球隊(duì)排名問題(1993年全國大學(xué)生數(shù)學(xué)建模競賽B題)中的應(yīng)用具體做法是綜合考慮各隊(duì)的比賽成績,為每支球隊(duì)計(jì)算相應(yīng)的等級分(Rank),然后根據(jù)各隊(duì)的等級分高低來確定名次考慮到競技比賽結(jié)果的不確定性,最后建立了等級分的隨機(jī)沖浪模型分析表明等級分排名結(jié)果具有良好的參數(shù)穩(wěn)定性,并且可以成功地處理數(shù)據(jù)缺損方面的困難關(guān)鍵詞:搜索引擎;GooglePageRank算法;隨

3、機(jī)沖浪模型;足球隊(duì)排名問題中圖分類號(hào):01414文獻(xiàn)標(biāo)識(shí)碼:A1引言據(jù)統(tǒng)計(jì),在短短20多年的時(shí)間里,Intemet中產(chǎn)生的信息量相當(dāng)于人類過去100年產(chǎn)生的信息總量,而且Internet上的信息量正以幾何級數(shù)遞增搜索引擎已經(jīng)成為人們進(jìn)行Internet信息資源搜索必不可少的工具在眾多的搜索引擎中,Google搜索引擎以其雄厚的技術(shù)為支撐,憑借其強(qiáng)大的檢索功能和高質(zhì)量的檢索服務(wù),逐漸脫穎而出Google搜索引擎是由斯坦福大學(xué)SergeyB

4、rin和LawrencePage共同設(shè)計(jì)的,它是目前功能最強(qiáng)的搜索引擎通過對80億網(wǎng)頁進(jìn)行整理,Google可為世界各地的用戶提供所需的搜索結(jié)果,而且搜索速度極快,通常不到半秒,每天可提供約3億次查詢服務(wù)圖1Google搜索引擎的工作原理示意圖圖2Intemet網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)Google的優(yōu)勢在于掌握的信息量以及檢索模型和檢索速度傳統(tǒng)的搜索引擎在很大程度上取決于文字在網(wǎng)頁上出現(xiàn)的頻率Google使用PageRank技術(shù)檢查整個(gè)網(wǎng)絡(luò)鏈接結(jié)

5、構(gòu),并確定哪些網(wǎng)頁重要性最高然后進(jìn)行超文本匹配分析(HypeneXtMatchingAnalysis),以確定哪些網(wǎng)頁與正在執(zhí)行的特定搜索相關(guān)在綜合考慮整體收稿日期:20100313作者簡介:趙國(1979),男,碩士,西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院講師,主要研究方向?yàn)榻鹑跀?shù)學(xué)、數(shù)學(xué)模型基金項(xiàng)目:西南民族大學(xué)青年項(xiàng)目萬方數(shù)據(jù)482西南民族大學(xué)學(xué)報(bào)自然科學(xué)版第36卷彳=o12O0l0將歸一化所得的矩陣彳轉(zhuǎn)置,所得到的轉(zhuǎn)移概率矩陣∥=(w

6、口)為現(xiàn)給每個(gè)頁面尸一個(gè)PageRank值x,,這些PageRank值應(yīng)該由鏈接到該頁面的那些頁面的PageRank值確定,即指向P的那些頁面的頁面等級值之和應(yīng)該與尸的頁面等級值x。成正比設(shè)共同的比例系數(shù)為A,則有下面的線性方程組土≥:W,,x,=2x,,f_12,3(1)。J=l令x=(而,x2,X3)7為頁面等級值組成的列向量,則由矩陣乘法,等式(1)可以寫成Wx=觸由此求出轉(zhuǎn)移概率矩陣的最大正特征值五=1,相應(yīng)非負(fù)特征向量x=(1

7、,1/2,1)1,由此可以確定網(wǎng)頁的排序?yàn)镃,A,B,其中頁面A,C的排序無顯著差別,之所以將c排在前面是因?yàn)橹赶駽的超鏈接數(shù)更多一些23隨機(jī)沖浪模型(RandomSurferModel)PageRank算法原理中有—個(gè)重要的假設(shè):所有的網(wǎng)頁形成一個(gè)閉合的鏈接圖,除了這些文檔以外沒有其他任何鏈接的出入,并且每個(gè)網(wǎng)頁能從其他網(wǎng)頁通過超鏈接達(dá)到但是在現(xiàn)實(shí)的網(wǎng)絡(luò)中,并不完全是這樣的情況當(dāng)一個(gè)頁面沒有出鏈的時(shí)候,它的PageRank值就不能被分

8、配給其它的頁面同樣道理,只有出鏈接而沒有入鏈接的頁面也是存在的但PageRank并不考慮這樣的頁面,因?yàn)闆]有流入的PageRank而只流出的PageRank,從對稱性角度來考慮是很奇怪的吲時(shí),有時(shí)候也有鏈接只在一個(gè)集合內(nèi)部旋轉(zhuǎn)而不向外界鏈接的現(xiàn)象在現(xiàn)實(shí)中的頁面,無論怎樣順著鏈接前進(jìn),僅僅順著鏈接是絕對不能進(jìn)入的頁面群總歸是存在的PageRank技術(shù)為了解決這樣的問題,提出用戶的隨機(jī)沖浪模型:用戶雖然在大多數(shù)場合都順著當(dāng)前頁面中的鏈接前進(jìn)

9、,但有時(shí)會(huì)突然重新打開瀏覽器隨機(jī)進(jìn)入到完全無關(guān)的頁面Google認(rèn)為:用戶在85%的情況下沿著鏈接前進(jìn),但在15%的情況下會(huì)跳躍到無關(guān)的頁面中用公式表示相應(yīng)的轉(zhuǎn)移概率矩陣為一W:dWo!型PP7’。門其中,e為分量全為l的胛維列向量,從而eel為全1矩陣,d∈(0,1)為權(quán)重因子(dampingfactor),在實(shí)際中Google取d=O85也就是說,在隨機(jī)沖浪模型中,求各個(gè)頁面等級值PageRank的問題變成了求正矩陣形的最大特征值所

10、屬的特征向量問題還是考慮前面給出的三個(gè)網(wǎng)頁A、B、c之間的超鏈接關(guān)系,在隨機(jī)沖浪模型下為方便計(jì)算令d=05,相應(yīng)的轉(zhuǎn)移概率矩陣為,,o1667o1667o6667)一W:o5W4螋PP7104167o1667o1667I3Io4167o6667o1667j根據(jù)著名的Perron—Frobenius定理【3】,轉(zhuǎn)移概率矩陣∥的最大正特征值是1,相應(yīng)的特征向量為(14/13,10/13,15/13)T由此可以確定網(wǎng)頁的排序?yàn)閏,A,B可見隨

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論