【文章內(nèi)容簡(jiǎn)介】 重要性的算法首先假設(shè)有N個(gè)訪問(wèn)者每個(gè)訪問(wèn)者本身有一個(gè)PR值1/ N。有的網(wǎng)站允許訪問(wèn)者對(duì)網(wǎng)頁(yè)內(nèi)容評(píng)價(jià)，這時(shí)多數(shù)的訪問(wèn)者表態(tài)代表了正確的評(píng)價(jià)，即訪問(wèn)者的評(píng)價(jià)對(duì)網(wǎng)頁(yè)的評(píng)價(jià)得到越多的人的贊同則訪問(wèn)者的PR值越高，否則就越低，通過(guò)大量的訪問(wèn)記錄，則統(tǒng)計(jì)結(jié)果表明訪問(wèn)者本身的PR值，同時(shí)由于訪問(wèn)者在不同領(lǐng)域的知識(shí)水平不同，應(yīng)該在不同的領(lǐng)域有不同的PR值，假設(shè)網(wǎng)頁(yè)根據(jù)內(nèi)容可以劃分為i類，即分為i個(gè)領(lǐng)域，則訪問(wèn)者在i領(lǐng)域的PageRank值為PR(i)，網(wǎng)絡(luò)網(wǎng)站總量為T(mén)，i領(lǐng)域的網(wǎng)站的總量是T(i)。將所有網(wǎng)站分為兩類：一種是訪問(wèn)者可以投票的網(wǎng)站，第二種是訪問(wèn)者不可以投票。投票網(wǎng)站一般給出 好、中、差 或者是贊成、反對(duì)、中立等幾個(gè)選項(xiàng)給訪問(wèn)者直接選擇，訪問(wèn)者只可以選擇其中一個(gè)對(duì)網(wǎng)頁(yè)進(jìn)行評(píng)價(jià)。投票又可以分為登錄投票和匿名投票，都沒(méi)有問(wèn)題，因?yàn)橄旅鏁?huì)講到本文是由物理地址標(biāo)志訪問(wèn)者的。同時(shí)現(xiàn)在的網(wǎng)站大部分都是分主題的，一個(gè)網(wǎng)站就是講一個(gè)領(lǐng)域的知識(shí)，按照現(xiàn)在的比例百分之九十八的網(wǎng)站都是講一個(gè)領(lǐng)域或者說(shuō)是主題的內(nèi)容(分類網(wǎng)頁(yè))，例如體育、軍事、健康、新聞、娛樂(lè)……等等，大概有百分之二的網(wǎng)站是同時(shí)具有幾個(gè)主題的(非分類網(wǎng)頁(yè))，根據(jù)這個(gè)情況，我們可以抓主要的先，先將網(wǎng)頁(yè)分為i個(gè)主題，每個(gè)主題的網(wǎng)頁(yè)是j個(gè)，最后才考慮多個(gè)主題的少數(shù)網(wǎng)頁(yè)，這些非分類網(wǎng)頁(yè)的PR值可以通過(guò)由分類網(wǎng)頁(yè)計(jì)算出來(lái)的訪問(wèn)者PR值計(jì)算，因?yàn)榉诸惥W(wǎng)頁(yè)的算法是根據(jù)絕大部分網(wǎng)頁(yè)(約98%)來(lái)計(jì)算訪問(wèn)者PR值的，非分類網(wǎng)頁(yè)(約2%)對(duì)訪問(wèn)者PR值的計(jì)算的影響微乎其微[10]。因此由分類網(wǎng)頁(yè)計(jì)算出來(lái)的訪問(wèn)者PR值來(lái)計(jì)算網(wǎng)頁(yè)的PR值具有統(tǒng)計(jì)特性，可以準(zhǔn)確反映每個(gè)訪問(wèn)者的實(shí)際情況，這樣計(jì)算出來(lái)的PR值是可靠的，反映了網(wǎng)頁(yè)的真實(shí)重要性(也就是網(wǎng)頁(yè)的權(quán)威性和正確性)，所以計(jì)算訪問(wèn)者的PR值只需要根據(jù)分類網(wǎng)頁(yè)來(lái)計(jì)算即可，根據(jù)計(jì)算出來(lái)的每個(gè)訪問(wèn)者在不同領(lǐng)域的不同PR值，結(jié)合某個(gè)網(wǎng)頁(yè)被每一個(gè)訪問(wèn)者的訪問(wèn)次數(shù)和投票情況決定了網(wǎng)頁(yè)的PR值，因?yàn)樗阉髡卟坏业氖侨藲飧叩?、重要的網(wǎng)站，而且要求網(wǎng)站的內(nèi)容是權(quán)威的準(zhǔn)確的，所以訪問(wèn)者每次訪問(wèn)這個(gè)網(wǎng)站的投票情況，將影響網(wǎng)頁(yè)的排名。為了表示投票情況，先設(shè)置一個(gè)參數(shù)Kijn，表示訪問(wèn)者對(duì)網(wǎng)頁(yè)P(yáng)ij的投票評(píng)價(jià)的被認(rèn)同度。由于本論文研究的改進(jìn)搜索引擎排序算法是由訪問(wèn)者的知識(shí)水平及其投票情況決定網(wǎng)頁(yè)的排名，因此在計(jì)算網(wǎng)頁(yè)的PR值之前首先就要求出訪問(wèn)者本身的PR值，第二步才是求網(wǎng)頁(yè)的PR值，下面將改進(jìn)方法分兩步詳細(xì)說(shuō)明。 計(jì)算每個(gè)訪問(wèn)者的PageRank值 計(jì)算訪問(wèn)者PR值的數(shù)學(xué)表達(dá)式為了下面的運(yùn)算現(xiàn)在設(shè)置好運(yùn)算的變量，假設(shè)總共N個(gè)訪問(wèn)者，整個(gè)網(wǎng)絡(luò)的網(wǎng)頁(yè)有b=98%的網(wǎng)頁(yè)是單一主題的，另外的2%網(wǎng)頁(yè)具有多個(gè)主題，單一主題的網(wǎng)頁(yè)可以分為i個(gè)領(lǐng)域，每個(gè)領(lǐng)域有j個(gè)網(wǎng)頁(yè)，因此Pij就指向具體的任何一個(gè)網(wǎng)頁(yè)。首先計(jì)算某個(gè)訪問(wèn)者n在i領(lǐng)域的PR值PRin，設(shè)Zijn表示訪問(wèn)者n對(duì)網(wǎng)頁(yè)P(yáng)ij的訪問(wèn)次數(shù)，Kijn為訪問(wèn)者n對(duì)網(wǎng)頁(yè)P(yáng)ij的投票評(píng)價(jià)的被認(rèn)同度 (例如：10個(gè)訪問(wèn)者訪問(wèn)網(wǎng)頁(yè)P(yáng)ij，其中8人投贊成票，2人投反對(duì)票。則投了贊成票的8個(gè)人的Kijn為80%，投反對(duì)票的2人的Kijn為20%)。訪問(wèn)者在i領(lǐng)域的PR值PRin可以用下式表示PRin= (Kijn ZijnPRinKijn) () 上式兩邊都有PRin，不是說(shuō)上式存在錯(cuò)誤，上式只是表達(dá)出了一種計(jì)算思路，遇到由自身求自身的數(shù)學(xué)問(wèn)題，類似先有蛋還是先有雞的問(wèn)題，在這里和Google PageRank傳統(tǒng)算法計(jì)算網(wǎng)頁(yè)P(yáng)R的情況類似了，式()也是由網(wǎng)頁(yè)自身PR值求網(wǎng)頁(yè)自身PR值，因此我們可以完全借鑒Google PageRank傳統(tǒng)的計(jì)算思路，利用循環(huán)計(jì)算收斂值的方法解決這個(gè)問(wèn)題。下面詳細(xì)分析一下上式()的思路：ZijnPRinKijn ()式()整體可以看做網(wǎng)頁(yè)j權(quán)重，這個(gè)權(quán)重乘以Kijn得出網(wǎng)頁(yè)j對(duì)訪問(wèn)者n的PR值的貢獻(xiàn)，將i領(lǐng)域所有網(wǎng)頁(yè)的貢獻(xiàn)疊加就得到訪問(wèn)者n在i領(lǐng)域的PR值表示為PRin。籠統(tǒng)來(lái)說(shuō)訪問(wèn)者在每一個(gè)網(wǎng)頁(yè)的被認(rèn)同度越高，訪問(wèn)者的PR值就越高，但是每個(gè)網(wǎng)頁(yè)對(duì)訪問(wèn)者的PR值計(jì)算中貢獻(xiàn)的份量是不一樣的，也就是權(quán)重不同，舉個(gè)例子，像中國(guó)期刊網(wǎng)的權(quán)重是非常大的，比一般的空間要大幾個(gè)數(shù)量級(jí)，當(dāng)訪問(wèn)者在中國(guó)期刊網(wǎng)得到認(rèn)同，和訪問(wèn)者在自己的空間被別人認(rèn)同對(duì)訪問(wèn)者的PR計(jì)算的貢獻(xiàn)是差異極大的，相差好幾個(gè)數(shù)量級(jí)。所以計(jì)算PRin時(shí)首先要算出網(wǎng)頁(yè)的權(quán)重。ZijnPRinKijn 式()中的ZijnPRin也是一個(gè)權(quán)重，表示訪問(wèn)者n在計(jì)算網(wǎng)頁(yè)j權(quán)重中的份量，乘以Zijn的原因是，訪問(wèn)者訪問(wèn)的次數(shù)越多，說(shuō)明這個(gè)網(wǎng)頁(yè)越受訪問(wèn)者n關(guān)注，稱為關(guān)注度，當(dāng)然一個(gè)網(wǎng)頁(yè)受訪問(wèn)者n關(guān)注越多，并不表示網(wǎng)頁(yè)j的權(quán)重()越大，還要看訪問(wèn)者的被認(rèn)同度Kijn，ZijnPRin只是作為一個(gè)權(quán)重 ，還要看他的意見(jiàn)是否得到大家的贊同，所以乘以Kijn，簡(jiǎn)單舉個(gè)例子，一個(gè)資深的學(xué)者訪問(wèn)一個(gè)本專業(yè)的網(wǎng)頁(yè)，并不是訪問(wèn)次數(shù)越多對(duì)網(wǎng)頁(yè)權(quán)重的貢獻(xiàn)就越大，還要乘以一個(gè)系數(shù)Kijn，當(dāng)沒(méi)有人同意這位資深學(xué)者的評(píng)價(jià)時(shí)，這位資深學(xué)者本身在這個(gè)領(lǐng)域很高的PR值當(dāng)然不可以貢獻(xiàn)在網(wǎng)頁(yè)j的權(quán)重上，相反如果很多人贊同這位資深學(xué)者的評(píng)價(jià)，即Kijn很大，這位資深學(xué)者本身的PR就會(huì)很大比例地對(duì)網(wǎng)頁(yè)j的權(quán)重做出貢獻(xiàn)。Kijn表示在投票網(wǎng)頁(yè)P(yáng)ij的所有訪問(wèn)者之中，與訪問(wèn)者n有相同投票的人占得比例?？紤]到不是每個(gè)網(wǎng)站都設(shè)置有投票欄，也不是每個(gè)領(lǐng)域所有的網(wǎng)站，訪問(wèn)者n都會(huì)去訪問(wèn)，有的訪問(wèn)者訪問(wèn)了網(wǎng)站卻不一定會(huì)投票，因此上式中的Kijn分四種情況，具體如下：與訪問(wèn)者n相同的評(píng)價(jià)(投票)占所有評(píng)價(jià)的比例Kijn= 50% ，網(wǎng)頁(yè)沒(méi)有投票欄 表達(dá)式一50%，訪問(wèn)者沒(méi)有投票0 ，訪問(wèn)者n沒(méi)有訪問(wèn)網(wǎng)頁(yè)P(yáng)ij表達(dá)式一的表示其實(shí)不嚴(yán)密，有少數(shù)訪問(wèn)者會(huì)多次訪問(wèn)同一個(gè)網(wǎng)頁(yè)但是在這部分人之中又會(huì)有極少數(shù)的人會(huì)對(duì)網(wǎng)站的評(píng)價(jià)進(jìn)行多次不同的投票也就是給出不同的評(píng)價(jià)，這并不奇怪，因?yàn)槿说乃枷胧请S著認(rèn)知水平和社會(huì)情況而變化的，因此越后面的投票越具有權(quán)威性，因此最后面投票基本反映了最近的社會(huì)情況，越后的投票時(shí)訪問(wèn)者經(jīng)過(guò)更加縝密結(jié)合了最新的事實(shí)綜合考慮的結(jié)果，因此我們只需要考慮訪問(wèn)者最好一次的投票，為了使計(jì)算更加精確所以有必要對(duì)Kijn進(jìn)行修正：與訪問(wèn)者最后一次的評(píng)價(jià)(投票)相同的評(píng)價(jià)占所有評(píng)價(jià)的比例Kijn= 50 %，網(wǎng)頁(yè)沒(méi)有投票欄 表達(dá)式二50%，訪問(wèn)者沒(méi)有投票0 ，訪問(wèn)者n沒(méi)有訪問(wèn)網(wǎng)頁(yè)P(yáng)ij這時(shí)有人可能會(huì)問(wèn)，既然上面已經(jīng)對(duì)Kijn進(jìn)行了修正，Kijn其實(shí)是考慮最后一次投票的，再乘以訪問(wèn)次數(shù)，顯得不合理，這樣的說(shuō)法其實(shí)不對(duì)因?yàn)樵L問(wèn)者訪問(wèn)這個(gè)網(wǎng)站越多就說(shuō)明對(duì)這個(gè)網(wǎng)站關(guān)注越多，說(shuō)明這個(gè)網(wǎng)站比較重要，再乘以訪問(wèn)者對(duì)網(wǎng)站的最終評(píng)價(jià)，正好反映了網(wǎng)站的權(quán)威性重要性。一個(gè)本身PR值越高的人訪問(wèn)某網(wǎng)頁(yè)的次數(shù)越多則網(wǎng)頁(yè)越重要。對(duì)網(wǎng)頁(yè)內(nèi)容的評(píng)價(jià)越高則網(wǎng)頁(yè)越權(quán)威相應(yīng)的PR值越高，因此以上表達(dá)式是合理的可行的。 訪問(wèn)者PR值的循環(huán)收斂計(jì)算方法類似Google PageRank計(jì)算方法，首先賦予每個(gè)訪問(wèn)者相同的PageRank值簡(jiǎn)稱PR值，首先假設(shè)每個(gè)訪問(wèn)者的PR值為常數(shù)。PRin(i+1)= (Kijn ZijnPRin(i)Kijn) ()這里是根據(jù)上一次的PRin計(jì)算下一次的PRin，設(shè)L=ZijnPRin(i)Kijn則上式可以表達(dá)為PRin(i+1)= (KijnL)。上式表示對(duì)i領(lǐng)域的所有網(wǎng)頁(yè)中訪問(wèn)者n被認(rèn)同度的疊加得到PRin，但是相同的認(rèn)同度對(duì)于不同的網(wǎng)頁(yè)所對(duì)訪問(wèn)者的PR值貢獻(xiàn)是不同的，所以對(duì)于不同的網(wǎng)頁(yè)有不同的權(quán)重，乘以這個(gè)權(quán)重就比較準(zhǔn)確反映了 j網(wǎng)頁(yè)對(duì)訪問(wèn)者n的PR值的貢獻(xiàn)。L的具體算法是ZijnPRin(i)Kijn L權(quán)重是由訪問(wèn)者本身的權(quán)重乘以訪問(wèn)次數(shù)(訪問(wèn)次數(shù)越多說(shuō)明網(wǎng)頁(yè)越受關(guān)注)。訪問(wèn)者本身有PR值但是只有訪問(wèn)者被認(rèn)同越高，他本身的PR值才會(huì)對(duì)網(wǎng)頁(yè)的權(quán)重做出越多貢獻(xiàn)(只有訪問(wèn)者被認(rèn)同越高，本身的PR值才會(huì)對(duì)網(wǎng)頁(yè)的PR做出相應(yīng)的貢獻(xiàn)，所以乘以Kijn)。考慮到還有2的網(wǎng)站是非分類網(wǎng)頁(yè)，非分類網(wǎng)頁(yè)的PR值需要根據(jù)每個(gè)訪問(wèn)者在相關(guān)領(lǐng)域的PR值來(lái)計(jì)算，與兩個(gè)以上的領(lǐng)域有關(guān)的非分類網(wǎng)頁(yè)的PR值，是將本網(wǎng)頁(yè)有關(guān)的領(lǐng)域的PR值的疊加再除以涉及到的領(lǐng)域數(shù)，而不是在單獨(dú)的領(lǐng)域計(jì)算總的PR值，如果不將不同領(lǐng)域的所有訪問(wèn)者的PR值進(jìn)行歸一化將出現(xiàn)以下的情況，一個(gè)訪問(wèn)者在兩個(gè)不同的領(lǐng)域的知識(shí)水平一樣但是他在這兩個(gè)領(lǐng)域的PR值相差很大，如果一個(gè)非分類網(wǎng)頁(yè)包含這兩個(gè)領(lǐng)域，將各個(gè)領(lǐng)域的網(wǎng)頁(yè)P(yáng)R相加得到總的PR的方法計(jì)算的結(jié)果將會(huì)出現(xiàn)偏差，因?yàn)槭?)中，不同領(lǐng)域的PRin是獨(dú)立運(yùn)算的，計(jì)算分類網(wǎng)頁(yè)時(shí)只需要結(jié)果分出相對(duì)大小就行，對(duì)計(jì)算出來(lái)的PRin本身的大小則不要求，式()僅僅限于單領(lǐng)域網(wǎng)頁(yè)即分類網(wǎng)頁(yè)的PR計(jì)算，因此在不同領(lǐng)域它們的基數(shù)不一樣，為了使計(jì)算結(jié)果更加準(zhǔn)確，所以必須要對(duì)PRin進(jìn)行歸一化以方便跨領(lǐng)域的PR值疊加運(yùn)算。為了避免出現(xiàn)不同領(lǐng)域總的PR值不同給下面計(jì)算非分類網(wǎng)頁(yè)總的PR值帶來(lái)偏差的情況，下面對(duì)計(jì)算所有訪問(wèn)者對(duì)各個(gè)領(lǐng)域的總的PR值的和。PRi= 設(shè)置歸一化常數(shù)Ci=因此最后得出某個(gè)訪問(wèn)者n在i領(lǐng)域的PR值PRin(i+1)=Ci (Kijn ZijnPRin(i)Kijn) () 上式就是結(jié)合訪問(wèn)者的自身情況得出的改進(jìn)算法算法描述如下：PRin(0) = //初始化每個(gè)訪問(wèn)者的PageRankwhile (|PRin(i) PRin(i1)|ε)　//PageRank收斂前的循環(huán)計(jì)算判斷{ε=i=1for each n∈N PRin(i)= (Kijn ZijnPRin(i1)Kijn)PRi= Ci= //設(shè)置歸一化常數(shù),規(guī)范因子的計(jì)算，以保證計(jì)算結(jié)果的正確性PRin(i)= Ci PRin(i) //進(jìn)行規(guī)范化得出的結(jié)果i=i+1}隨著循環(huán)次數(shù)的增加，計(jì)算結(jié)果越來(lái)越收斂，越來(lái)越接近真實(shí)的PR值，只要循環(huán)次數(shù)足夠多可以得到任何精度的網(wǎng)頁(yè)P(yáng)R值。據(jù)統(tǒng)計(jì)，Web已經(jīng)擁有100億左右的靜態(tài)網(wǎng)頁(yè)和550億左右的動(dòng)態(tài)網(wǎng)頁(yè)，因此，PageRank要處理的矩陣是“世界上最大的矩陣”，為了便于討論驗(yàn)證算法的正確性同時(shí)也是為了讓讀者更加容易理解算法的結(jié)構(gòu)邏輯，下面建立簡(jiǎn)單的模型，驗(yàn)證程序是否可行。PRin(i)= (Kijn ZijnPRin(i1)Kijn) ()以上圖示為了方便驗(yàn)證下面的結(jié)果是否正確，如圖，圓圈表示訪問(wèn)者，方框表示網(wǎng)頁(yè)，直線表示訪問(wèn)相應(yīng)的網(wǎng)頁(yè)。 3，其他的依次類推。,訪問(wèn)者1的被認(rèn)同度明顯是高于其他三人，訪問(wèn)者4的被認(rèn)同度明顯低于其他三人，而訪問(wèn)者2的被認(rèn)同度又高于訪問(wèn)者3，讀者可以明顯看出4個(gè)訪問(wèn)者的PR是PRi(1) PRi(2) PRi(3) PRi(4)。如果下面的計(jì)算結(jié)果同上，則說(shuō)明我所改進(jìn)的算法，不存在邏輯的錯(cuò)誤，計(jì)算結(jié)果沒(méi)有錯(cuò)誤。Visual Basic作為非計(jì)算機(jī)專業(yè)科學(xué)工作者的常用編程軟件深得使用者的好評(píng)，用來(lái)實(shí)現(xiàn)數(shù)學(xué)運(yùn)算簡(jiǎn)單方便，可以將公式的()的運(yùn)算關(guān)系表達(dá)的很清楚，但是存在的缺點(diǎn)是對(duì)于多重循環(huán)運(yùn)算，對(duì)編程者的編程水平要求較高。Matlab是矩陣實(shí)驗(yàn)室（Matrix Laboratory）的簡(jiǎn)稱，作為數(shù)學(xué)矩陣的專用軟件，由美國(guó)新墨西哥大學(xué)教授設(shè)計(jì)，自誕生以來(lái)，一直受到數(shù)學(xué)工作者的喜愛(ài)，對(duì)于數(shù)學(xué)矩陣運(yùn)算編程方法簡(jiǎn)單，是數(shù)學(xué)運(yùn)算的常用工具。本文改進(jìn)算法可以表示為矩陣的運(yùn)算，采用matlab計(jì)算比較合適，而且Google 搜索引擎就是用矩陣運(yùn)算得出網(wǎng)頁(yè)P(yáng)R值的，但是缺點(diǎn)是不能夠清楚表達(dá)原來(lái)的運(yùn)算關(guān)系。比較兩者的優(yōu)缺點(diǎn)，采用兩種方法同時(shí)編程運(yùn)算，發(fā)揮兩者的優(yōu)點(diǎn)，使讀者比較容易理解本文改進(jìn)算法的設(shè)計(jì)思路。同時(shí)也是檢驗(yàn)運(yùn)算結(jié)果是否正確的雙保險(xiǎn)。[11] Visual Basic編程驗(yàn)證算法收斂將上面的算法結(jié)合上圖編寫(xiě)相應(yīng)的VB程序，運(yùn)行循環(huán)結(jié)構(gòu)后得出收斂后的結(jié)果驗(yàn)證算法的正確性：private Sub Command1_Click()Dim m, n, l, i, j, k, oDim PRi(1 To 4)Dim Zi(1 To 4, 1 To 4)Dim Ki(0 To 4, 1 To 4)Dim C(0 To 4)Dim T(0 To 4)Dim PR(1 To 4, 1 To 9999)Dim P(1 To 4)Dim G(1 To 4)Zi(1, 1) = 3: Zi(1, 2) = 0: Zi(1, 3) = 1: Zi(1, 4) = 2: Zi(2, 1) = 1: Zi(2, 2) = 4: Zi(2, 3) = 0: Zi(2, 4) = 3Zi(3, 1) = 0: Zi(3, 2) = 2: Zi(3, 3) = 2: Zi(3, 4) = 0: Zi(4, 1) = 2: Zi(4, 2) = 0: Zi(4, 3) = 0: Zi(4, 4) = 1PRi(1) = 1 / 4: PRi(2) = 1 / 4: PRi(3) = 1 / 4: PRi(4) = 1 / 4Ki(1, 1) = : Ki(1, 2) = : Ki(1, 3) = : Ki(1, 4) = : Ki(2, 1) = : Ki(2, 2) = : Ki(2, 3) = : Ki(2, 4) = Ki(3, 1) = : Ki(3, 2) = : Ki(3, 3) = : Ki(3, 4) = : Ki(4, 1) = : Ki(4, 2) = :