【文章內(nèi)容簡介】 ，則表示網(wǎng)頁越熱，越多人訪問。在改進(jìn)算法中，訪問者的PR值表示為PRin，PRin越大則表示訪問者的專業(yè)知識水平越高。網(wǎng)頁的PR值表示為Pij，Pij越大表示網(wǎng)頁的權(quán)威性、正確性越大。 從投票角度分析算法的本質(zhì)從投票的角度來分析兩種算法的本質(zhì)：Google PageRank傳統(tǒng)算法中，從網(wǎng)頁 A 指向網(wǎng)頁 B 的鏈接解釋為由網(wǎng)頁 A 對網(wǎng)頁 B 所投的一票，由其他網(wǎng)頁對網(wǎng)頁本身的投票來計(jì)算網(wǎng)頁的PR值。在改進(jìn)算法中，訪問者對網(wǎng)頁的投票的被認(rèn)同度就是其他訪問者對他的投票，由其他訪問者對他的投票來計(jì)算訪問者的PR值。在計(jì)算網(wǎng)頁P(yáng)R值時(shí)，網(wǎng)頁由訪問者對它的投票來決定網(wǎng)頁的PR值。不是每個(gè)訪問者和網(wǎng)頁的投票都是對訪問者或者網(wǎng)頁的PR值貢獻(xiàn)一樣的，因?yàn)槊總€(gè)訪問者和網(wǎng)頁的權(quán)重不一樣，兩者的權(quán)重分別與它們的知識水平和網(wǎng)頁權(quán)威性有關(guān)。因此計(jì)算兩者PR值之前要計(jì)算兩者的權(quán)重。權(quán)重是一個(gè)相對的概念，是針對某一指標(biāo)而言。某一指標(biāo)的權(quán)重是指該指標(biāo)在整體評價(jià)中的相對重要程度。 權(quán)重表示在評價(jià)過程中，是被評價(jià)對象的不同側(cè)面的重要程度的定量分配，對各評價(jià)因子在總體評價(jià)中的作用進(jìn)行區(qū)別對待。事實(shí)上，沒有重點(diǎn)的評價(jià)就不算是客觀的評價(jià)。 打個(gè)比方說, 一件事情, 你給它打100分, 你的老板給它打60分, 如果平均, 則是(100+60)/2=80分. 但因?yàn)槔习逭f的話分量比你重, 假如老板的權(quán)重是2, 你是1, 這時(shí)求平均值就是加權(quán)平均了, 結(jié)果是(100*1 + 60*2)/(1+2)=, 顯然向你的老板那里傾斜了。假如老板權(quán)重是3，你的權(quán)重是1，結(jié)果是(100*1+60*3)/(1+3)=70。這就是根據(jù)權(quán)重的不同進(jìn)行的平均數(shù)的計(jì)算，所以又叫加權(quán)平均數(shù)。同樣道理每個(gè)訪問者和每個(gè)網(wǎng)頁的權(quán)重都是不同的因?yàn)樗麄兊臋?quán)威性是不同的。例如：一個(gè)工程院院士關(guān)于PageRank網(wǎng)頁的投票的權(quán)重，比我對PageRank網(wǎng)頁的投票的權(quán)重大得多，因?yàn)樵菏康脑擃I(lǐng)域知識水平(PR值)遠(yuǎn)遠(yuǎn)高于我。接著是看投票情況，如果院士投了反對票，這個(gè)網(wǎng)頁的PR將大打折扣，如果我投了反對票，對網(wǎng)頁P(yáng)R的影響可能不大，因?yàn)槲业臋?quán)重比院士的權(quán)重小很多。網(wǎng)頁也有它的權(quán)重，因?yàn)樵L問者在不同權(quán)重的網(wǎng)頁被認(rèn)同，對訪問者的PR值貢獻(xiàn)是不同的。例如，我在中國期刊網(wǎng)的投票被別人贊同，和在自己空間被被人贊同，前者將大大增加我的PR值，后者影響較小，因?yàn)閮蓚€(gè)網(wǎng)頁的權(quán)重差幾個(gè)數(shù)量級。 權(quán)重就是反映影響力的一個(gè)值，訪問者的權(quán)重越大，則對網(wǎng)頁的PR值影響越大，至于是正面還是負(fù)面影響，還有看投票評價(jià)情況。在計(jì)算PRin時(shí)，網(wǎng)頁的權(quán)重越大，則對訪問者的PR影響越大，至于是正面還是負(fù)面影響，還有看投票評價(jià)被認(rèn)同情況。 算法改進(jìn)的詳細(xì)設(shè)計(jì)思路事實(shí)上，PageRank 值雖然在一定程度上表達(dá)了網(wǎng)頁與用戶查詢的相關(guān)度 ,但是存在的問題也是明顯的, 其中最明顯的在于 PageRank 的計(jì)算是獨(dú)立于用戶查詢而進(jìn)行的先期運(yùn)算，根本沒有考慮訪問者自身的情況和訪問者對網(wǎng)頁的評價(jià)，這樣，網(wǎng)頁的PageRank值只是一個(gè)基于全部網(wǎng)頁集合計(jì)算出來的一個(gè)獨(dú)立值。而網(wǎng)頁的排名不應(yīng)該單單看網(wǎng)頁的訪問量，還要看網(wǎng)頁內(nèi)容的權(quán)威性和正確性，因?yàn)槊總€(gè)用搜索引擎的訪問者希望自己搜索的結(jié)果是正確的具有一定的權(quán)威性的，當(dāng)然網(wǎng)絡(luò)多人訪問在一定程度上說明了它的正確性，但是也不能夠完全這樣來判斷網(wǎng)頁的正確性，還要結(jié)合訪問者對網(wǎng)頁的評價(jià)來決定網(wǎng)頁的權(quán)威性和正確性。但是PageRank算法僅僅根據(jù)訪問量來決定網(wǎng)站的重要性，這個(gè)有點(diǎn)不完善，搜索引擎不單只要返回多人關(guān)注的網(wǎng)站排位，而且還要考慮網(wǎng)站的內(nèi)容是否正確權(quán)威，這個(gè)可以從訪問者的知識水平來判斷網(wǎng)頁的權(quán)威性。我做的工作就是增加訪問者的具體情況影響PageRank值，首先就是訪問者的知識水平不同他對網(wǎng)站的PR值貢獻(xiàn)不同，在不同的領(lǐng)域不同的訪問者具有不同PR(PageRank，下同)值，這個(gè)PR值，首先計(jì)算每個(gè)訪問者的PR值，類似PageRank根據(jù)鏈接數(shù)量判斷網(wǎng)頁重要性的算法首先假設(shè)有N個(gè)訪問者每個(gè)訪問者本身有一個(gè)PR值1/ N。有的網(wǎng)站允許訪問者對網(wǎng)頁內(nèi)容評價(jià)，這時(shí)多數(shù)的訪問者表態(tài)代表了正確的評價(jià)，即訪問者的評價(jià)對網(wǎng)頁的評價(jià)得到越多的人的贊同則訪問者的PR值越高，否則就越低，通過大量的訪問記錄，則統(tǒng)計(jì)結(jié)果表明訪問者本身的PR值，同時(shí)由于訪問者在不同領(lǐng)域的知識水平不同，應(yīng)該在不同的領(lǐng)域有不同的PR值，假設(shè)網(wǎng)頁根據(jù)內(nèi)容可以劃分為i類，即分為i個(gè)領(lǐng)域，則訪問者在i領(lǐng)域的PageRank值為PR(i)，網(wǎng)絡(luò)網(wǎng)站總量為T，i領(lǐng)域的網(wǎng)站的總量是T(i)。將所有網(wǎng)站分為兩類：一種是訪問者可以投票的網(wǎng)站，第二種是訪問者不可以投票。投票網(wǎng)站一般給出 好、中、差 或者是贊成、反對、中立等幾個(gè)選項(xiàng)給訪問者直接選擇，訪問者只可以選擇其中一個(gè)對網(wǎng)頁進(jìn)行評價(jià)。投票又可以分為登錄投票和匿名投票，都沒有問題，因?yàn)橄旅鏁v到本文是由物理地址標(biāo)志訪問者的。同時(shí)現(xiàn)在的網(wǎng)站大部分都是分主題的，一個(gè)網(wǎng)站就是講一個(gè)領(lǐng)域的知識，按照現(xiàn)在的比例百分之九十八的網(wǎng)站都是講一個(gè)領(lǐng)域或者說是主題的內(nèi)容(分類網(wǎng)頁)，例如體育、軍事、健康、新聞、娛樂……等等，大概有百分之二的網(wǎng)站是同時(shí)具有幾個(gè)主題的(非分類網(wǎng)頁)，根據(jù)這個(gè)情況，我們可以抓主要的先，先將網(wǎng)頁分為i個(gè)主題，每個(gè)主題的網(wǎng)頁是j個(gè)，最后才考慮多個(gè)主題的少數(shù)網(wǎng)頁，這些非分類網(wǎng)頁的PR值可以通過由分類網(wǎng)頁計(jì)算出來的訪問者PR值計(jì)算，因?yàn)榉诸惥W(wǎng)頁的算法是根據(jù)絕大部分網(wǎng)頁(約98%)來計(jì)算訪問者PR值的，非分類網(wǎng)頁(約2%)對訪問者PR值的計(jì)算的影響微乎其微[10]。因此由分類網(wǎng)頁計(jì)算出來的訪問者PR值來計(jì)算網(wǎng)頁的PR值具有統(tǒng)計(jì)特性，可以準(zhǔn)確反映每個(gè)訪問者的實(shí)際情況，這樣計(jì)算出來的PR值是可靠的，反映了網(wǎng)頁的真實(shí)重要性(也就是網(wǎng)頁的權(quán)威性和正確性)，所以計(jì)算訪問者的PR值只需要根據(jù)分類網(wǎng)頁來計(jì)算即可，根據(jù)計(jì)算出來的每個(gè)訪問者在不同領(lǐng)域的不同PR值，結(jié)合某個(gè)網(wǎng)頁被每一個(gè)訪問者的訪問次數(shù)和投票情況決定了網(wǎng)頁的PR值，因?yàn)樗阉髡卟坏业氖侨藲飧叩摹⒅匾木W(wǎng)站，而且要求網(wǎng)站的內(nèi)容是權(quán)威的準(zhǔn)確的，所以訪問者每次訪問這個(gè)網(wǎng)站的投票情況，將影響網(wǎng)頁的排名。為了表示投票情況，先設(shè)置一個(gè)參數(shù)Kijn，表示訪問者對網(wǎng)頁P(yáng)ij的投票評價(jià)的被認(rèn)同度。由于本論文研究的改進(jìn)搜索引擎排序算法是由訪問者的知識水平及其投票情況決定網(wǎng)頁的排名，因此在計(jì)算網(wǎng)頁的PR值之前首先就要求出訪問者本身的PR值，第二步才是求網(wǎng)頁的PR值，下面將改進(jìn)方法分兩步詳細(xì)說明。 計(jì)算每個(gè)訪問者的PageRank值 計(jì)算訪問者PR值的數(shù)學(xué)表達(dá)式為了下面的運(yùn)算現(xiàn)在設(shè)置好運(yùn)算的變量，假設(shè)總共N個(gè)訪問者，整個(gè)網(wǎng)絡(luò)的網(wǎng)頁有b=98%的網(wǎng)頁是單一主題的，另外的2%網(wǎng)頁具有多個(gè)主題，單一主題的網(wǎng)頁可以分為i個(gè)領(lǐng)域，每個(gè)領(lǐng)域有j個(gè)網(wǎng)頁，因此Pij就指向具體的任何一個(gè)網(wǎng)頁。首先計(jì)算某個(gè)訪問者n在i領(lǐng)域的PR值PRin，設(shè)Zijn表示訪問者n對網(wǎng)頁P(yáng)ij的訪問次數(shù)，Kijn為訪問者n對網(wǎng)頁P(yáng)ij的投票評價(jià)的被認(rèn)同度 (例如：10個(gè)訪問者訪問網(wǎng)頁P(yáng)ij，其中8人投贊成票，2人投反對票。則投了贊成票的8個(gè)人的Kijn為80%，投反對票的2人的Kijn為20%)。訪問者在i領(lǐng)域的PR值PRin可以用下式表示PRin= (Kijn ZijnPRinKijn) () 上式兩邊都有PRin，不是說上式存在錯誤，上式只是表達(dá)出了一種計(jì)算思路，遇到由自身求自身的數(shù)學(xué)問題，類似先有蛋還是先有雞的問題，在這里和Google PageRank傳統(tǒng)算法計(jì)算網(wǎng)頁P(yáng)R的情況類似了，式()也是由網(wǎng)頁自身PR值求網(wǎng)頁自身PR值，因此我們可以完全借鑒Google PageRank傳統(tǒng)的計(jì)算思路，利用循環(huán)計(jì)算收斂值的方法解決這個(gè)問題。下面詳細(xì)分析一下上式()的思路：ZijnPRinKijn ()式()整體可以看做網(wǎng)頁j權(quán)重，這個(gè)權(quán)重乘以Kijn得出網(wǎng)頁j對訪問者n的PR值的貢獻(xiàn)，將i領(lǐng)域所有網(wǎng)頁的貢獻(xiàn)疊加就得到訪問者n在i領(lǐng)域的PR值表示為PRin。籠統(tǒng)來說訪問者在每一個(gè)網(wǎng)頁的被認(rèn)同度越高，訪問者的PR值就越高，但是每個(gè)網(wǎng)頁對訪問者的PR值計(jì)算中貢獻(xiàn)的份量是不一樣的，也就是權(quán)重不同，舉個(gè)例子，像中國期刊網(wǎng)的權(quán)重是非常大的，比一般的空間要大幾個(gè)數(shù)量級，當(dāng)訪問者在中國期刊網(wǎng)得到認(rèn)同，和訪問者在自己的空間被別人認(rèn)同對訪問者的PR計(jì)算的貢獻(xiàn)是差異極大的，相差好幾個(gè)數(shù)量級。所以計(jì)算PRin時(shí)首先要算出網(wǎng)頁的權(quán)重。ZijnPRinKijn 式()中的ZijnPRin也是一個(gè)權(quán)重，表示訪問者n在計(jì)算網(wǎng)頁j權(quán)重中的份量，乘以Zijn的原因是，訪問者訪問的次數(shù)越多，說明這個(gè)網(wǎng)頁越受訪問者n關(guān)注，稱為關(guān)注度，當(dāng)然一個(gè)網(wǎng)頁受訪問者n關(guān)注越多，并不表示網(wǎng)頁j的權(quán)重()越大，還要看訪問者的被認(rèn)同度Kijn，ZijnPRin只是作為一個(gè)權(quán)重 ，還要看他的意見是否得到大家的贊同，所以乘以Kijn，簡單舉個(gè)例子，一個(gè)資深的學(xué)者訪問一個(gè)本專業(yè)的網(wǎng)頁，并不是訪問次數(shù)越多對網(wǎng)頁權(quán)重的貢獻(xiàn)就越大，還要乘以一個(gè)系數(shù)Kijn，當(dāng)沒有人同意這位資深學(xué)者的評價(jià)時(shí)，這位資深學(xué)者本身在這個(gè)領(lǐng)域很高的PR值當(dāng)然不可以貢獻(xiàn)在網(wǎng)頁j的權(quán)重上，相反如果很多人贊同這位資深學(xué)者的評價(jià)，即Kijn很大，這位資深學(xué)者本身的PR就會很大比例地對網(wǎng)頁j的權(quán)重做出貢獻(xiàn)。Kijn表示在投票網(wǎng)頁P(yáng)ij的所有訪問者之中，與訪問者n有相同投票的人占得比例?？紤]到不是每個(gè)網(wǎng)站都設(shè)置有投票欄，也不是每個(gè)領(lǐng)域所有的網(wǎng)站，訪問者n都會去訪問，有的訪問者訪問了網(wǎng)站卻不一定會投票，因此上式中的Kijn分四種情況，具體如下：與訪問者n相同的評價(jià)(投票)占所有評價(jià)的比例Kijn= 50% ，網(wǎng)頁沒有投票欄 表達(dá)式一50%，訪問者沒有投票0 ，訪問者n沒有訪問網(wǎng)頁P(yáng)ij表達(dá)式一的表示其實(shí)不嚴(yán)密，有少數(shù)訪問者會多次訪問同一個(gè)網(wǎng)頁但是在這部分人之中又會有極少數(shù)的人會對網(wǎng)站的評價(jià)進(jìn)行多次不同的投票也就是給出不同的評價(jià)，這并不奇怪，因?yàn)槿说乃枷胧请S著認(rèn)知水平和社會情況而變化的，因此越后面的投票越具有權(quán)威性，因此最后面投票基本反映了最近的社會情況，越后的投票時(shí)訪問者經(jīng)過更加縝密結(jié)合了最新的事實(shí)綜合考慮的結(jié)果，因此我們只需要考慮訪問者最好一次的投票，為了使計(jì)算更加精確所以有必要對Kijn進(jìn)行修正：與訪問者最后一次的評價(jià)(投票)相同的評價(jià)占所有評價(jià)的比例Kijn= 50 %，網(wǎng)頁沒有投票欄 表達(dá)式二50%，訪問者沒有投票0 ，訪問者n沒有訪問網(wǎng)頁P(yáng)ij這時(shí)有人可能會問，既然上面已經(jīng)對Kijn進(jìn)行了修正，Kijn其實(shí)是考慮最后一次投票的，再乘以訪問次數(shù)，顯得不合理，這樣的說法其實(shí)不對因?yàn)樵L問者訪問這個(gè)網(wǎng)站越多就說明對這個(gè)網(wǎng)站關(guān)注越多，說明這個(gè)網(wǎng)站比較重要，再乘以訪問者對網(wǎng)站的最終評價(jià)，正好反映了網(wǎng)站的權(quán)威性重要性。一個(gè)本身PR值越高的人訪問某網(wǎng)頁的次數(shù)越多則網(wǎng)頁越重要。對網(wǎng)頁內(nèi)容的評價(jià)越高則網(wǎng)頁越權(quán)威相應(yīng)的PR值越高，因此以上表達(dá)式是合理的可行的。 訪問者PR值的循環(huán)收斂計(jì)算方法類似Google PageRank計(jì)算方法，首先賦予每個(gè)訪問者相同的PageRank值簡稱PR值，首先假設(shè)每個(gè)訪問者的PR值為常數(shù)。PRin(i+1)= (Kijn ZijnPRin(i)Kijn) ()這里是根據(jù)上一次的PRin計(jì)算下一次的PRin，設(shè)L=ZijnPRin(i)Kijn則上式可以表達(dá)為PRin(i+1)= (KijnL)。上式表示對i領(lǐng)域的所有網(wǎng)頁中訪問者n被認(rèn)同度的疊加得到PRin，但是相同的認(rèn)同度對于不同的網(wǎng)頁所對訪問者的PR值貢獻(xiàn)是不同的，所以對于不同的網(wǎng)頁有不同的權(quán)重，乘以這個(gè)權(quán)重就比較準(zhǔn)確反映了 j網(wǎng)頁對訪問者n的PR值的貢獻(xiàn)。L的具體算法是ZijnPRin(i)Kijn L權(quán)重是由訪問者本身的權(quán)重乘以訪問次數(shù)(訪問次數(shù)越多說明網(wǎng)頁越受關(guān)注)。訪問者本身有PR值但是只有訪問者被認(rèn)同越高，他本身的PR值才會對網(wǎng)頁的權(quán)重做出越多貢獻(xiàn)(只有訪問者被認(rèn)同越高，本身的PR值才會對網(wǎng)頁的PR做出相應(yīng)的貢獻(xiàn)，所以乘以Kijn)?？紤]到還有2的網(wǎng)站是非分類網(wǎng)頁，非分類網(wǎng)頁的PR值需要根據(jù)每個(gè)訪問者在相關(guān)領(lǐng)域的PR值來計(jì)算，與兩個(gè)以上的領(lǐng)域有關(guān)的非分類網(wǎng)頁的PR值，是將本網(wǎng)頁有關(guān)的領(lǐng)域的PR值的疊加再除以涉及到的領(lǐng)域數(shù)，而不是在單獨(dú)的領(lǐng)域計(jì)算總的PR值，如果不將不同領(lǐng)域的所有訪問者的PR值進(jìn)行歸一化將出現(xiàn)以下的情況，一個(gè)訪問者在兩個(gè)不同的領(lǐng)域的知識水平一樣但是他在這兩個(gè)領(lǐng)域的PR值相差很大，如果一個(gè)非分類網(wǎng)頁包含這兩個(gè)領(lǐng)域，將各個(gè)領(lǐng)域的網(wǎng)頁P(yáng)R相加得到總的PR的方法計(jì)算的結(jié)果將會出現(xiàn)偏差，因?yàn)槭?)中，不同領(lǐng)域的PRin是獨(dú)立運(yùn)算的，計(jì)算分類網(wǎng)頁時(shí)只需要結(jié)果分出相對大小就行，對計(jì)算出來的PRin本身的大小則不要求，式()僅僅限于單領(lǐng)域網(wǎng)頁即分類網(wǎng)頁的PR計(jì)算，因此在不同領(lǐng)域它們的基數(shù)不一樣，為了使計(jì)算結(jié)果更加準(zhǔn)確，所以必須要對PRin進(jìn)行歸一化以方便跨領(lǐng)域的PR值疊加運(yùn)算。為了避免出現(xiàn)不同領(lǐng)域總的PR值不同給下面計(jì)算非分類網(wǎng)頁總的PR值帶來偏差的情況，下面對計(jì)算所有訪問者對各個(gè)領(lǐng)域的總的PR值的和。PRi= 設(shè)置歸一化常數(shù)Ci=因此最后得出某個(gè)訪問者n在i領(lǐng)域的PR值PRin(i+1)=Ci (Kijn ZijnPRin(i)Kijn) () 上式就是結(jié)合訪問者的自身情況得出的改進(jìn)算法算法描述如下：PRin(0) = //初始化每個(gè)訪問者的PageRankwhile (|PRin(i) PRin(i1)|ε)　//PageRank收斂前的循環(huán)計(jì)算判斷{ε=i=1for each n∈N PRin(i)= (Kij