Google搜索引擎的數(shù)學(xué)模型及其應(yīng)用.pdf

西南民族大學(xué)學(xué)報 自然科學(xué)版 第 36 卷第 3 期 Journal of Southwest University for Nationalities Natural Science Edition May 2010 收稿日期 2010 03 13 作者簡介 趙國 1979 男 碩士 西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院講師 主要研究方向?yàn)榻鹑跀?shù)學(xué) 數(shù)學(xué)模型 基金項(xiàng)目 西南民族大學(xué)青年項(xiàng)目 文章編號 1003 2843 2010 03 0480 07 Google 搜索引擎的數(shù)學(xué)模型及其應(yīng)用 趙國 宋建成 西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 四川成都 610041 摘 要 該文在闡明 Google 搜索引擎中關(guān)鍵的頁面等級算法 PageRank 原理的基礎(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)鍵詞 搜索引擎 Google PageRank 算法 隨機(jī)沖浪模型 足球隊(duì)排名問題 中圖分類號 O141 4 文獻(xiàn)標(biāo)識碼 A 1 引言 據(jù)統(tǒng)計(jì) 在短短 20 多年的時間里 Internet 中產(chǎn)生的信息量相當(dāng)于人類過去 100 年產(chǎn)生的信息總量 而且 Internet 上的信息量正以幾何級數(shù)遞增 搜索引擎已經(jīng)成為人們進(jìn)行 Internet 信息資源搜索必不可少的工具 在 眾多的搜索引擎中 Google 搜索引擎以其雄厚的技術(shù)為支撐 憑借其強(qiáng)大的檢索功能和高質(zhì)量的檢索服務(wù) 逐 漸脫穎而出 Google 搜索引擎是由斯坦福大學(xué) Sergey Brin 和 Lawrence Page 共同設(shè)計(jì)的 1 它是目前功能最強(qiáng)的 搜索引擎 通過對 80 億網(wǎng)頁進(jìn)行整理 Google 可為世界各地的用戶提供所需的搜索結(jié)果 而且搜索速度極快 通常不到半秒 每天可提供約 3 億次查詢服務(wù) 圖 1 Google 搜索引擎的工作原理示意圖 圖 2 Internet 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu) Google 的優(yōu)勢在于掌握的信息量以及檢索模型和檢索速度 傳統(tǒng)的搜索引擎在很大程度上取決于文字在 網(wǎng)頁上出現(xiàn)的頻率 Google 使用 PageRank 技術(shù)檢查整個網(wǎng)絡(luò)鏈接結(jié)構(gòu) 并確定哪些網(wǎng)頁重要性最高 然后進(jìn) 行超文本匹配分析 Hypertext Matching Analysis 以確定哪些網(wǎng)頁與正在執(zhí)行的特定搜索相關(guān) 在綜合考慮整體 481 第 3 期 趙國等 Google 搜索引擎的數(shù)學(xué)模型及其應(yīng)用 重要性以及與特定查詢的相關(guān)性之后 Google 可以將最相關(guān)最可靠的搜索結(jié)果放在最前面 2 Google 搜索引擎的數(shù)學(xué)模型 Google 擁有多項(xiàng)專利技術(shù) 其中 PageRank 算法是關(guān)鍵技術(shù)之一 它奠定了 Google 強(qiáng)大的檢索功能及提供 各種特色功能的基礎(chǔ) 雖然Google每天有很多工程師負(fù)責(zé)全面改進(jìn)Google 系統(tǒng) 但是仍把PageRank 算法作為 所有網(wǎng)絡(luò)搜索工具的基礎(chǔ)結(jié)構(gòu) 2 2 1 PageRank 原理 PageRank 算法是 Google 搜索引擎對檢索結(jié)果的一種排序算法 它的基本思想主要是來自傳統(tǒng)文獻(xiàn)計(jì)量學(xué) 中的文獻(xiàn)引文分析 即一篇文獻(xiàn)的質(zhì)量和重要性可以通過其它文獻(xiàn)對其引用的數(shù)量和引文質(zhì)量來衡量 也就是 說 一篇文獻(xiàn)被其它文獻(xiàn)引用越多 并且引用它的文獻(xiàn)的質(zhì)量越高 則該文獻(xiàn)本身就越重要 Google 在給出頁面 排序時也有兩條標(biāo)準(zhǔn) 一是看有多少超級鏈接指向它 二是要看超級鏈接指向它的那個頁面重要不重要 這兩 條直觀的想法就是 PageRank 算法的數(shù)學(xué)基礎(chǔ) 也是 Google 搜索引擎最基本的工作原理 PageRank 算法利用了互聯(lián)網(wǎng)獨(dú)特的超鏈接結(jié)構(gòu) 在龐大的超鏈接資源中 Google 提取出上億個超級鏈接頁 面進(jìn)行分析 制作出一個巨大的網(wǎng)絡(luò)地圖 具體的講 就是把所有的網(wǎng)頁看作圖里面相應(yīng)的頂點(diǎn) 如果網(wǎng)頁A有 一個指向網(wǎng)頁 B 的鏈接 則認(rèn)為一條從頂點(diǎn) A 到頂點(diǎn) B 的有向邊 這樣就可以利用圖論來研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu) PageRank 算法正是利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來判斷網(wǎng)頁的重要性 具體來說 假如網(wǎng)頁 A 有一個指向網(wǎng)頁 B 的 超鏈接 Google 就認(rèn)為網(wǎng)頁 A 投了網(wǎng)頁 B 一票 說明網(wǎng)頁 A 認(rèn)為網(wǎng)頁 B 有鏈接價值 因而 B 可能是一個重要的 網(wǎng)頁 Google 根據(jù)指向網(wǎng)頁 B 的超鏈接數(shù)及其重要性來判斷頁面 B 的重要性 并賦予相應(yīng)的頁面等級值 PageRank 網(wǎng)頁 A 的頁面等級值被平均分配給網(wǎng)頁 A 所鏈接指向的網(wǎng)頁 從而當(dāng)網(wǎng)頁 A 的頁面等級值比較高 時 則網(wǎng)頁 B 可從網(wǎng)頁 A 到它的超鏈接分得一定的重要性 根據(jù)這樣的分析 得到了高評價的重要頁面會被賦 予較高的網(wǎng)頁等級 在檢索結(jié)果內(nèi)的排名也會較高 頁面等級值 PageRank 是 Google 表示網(wǎng)頁重要性的綜合 性指標(biāo) 而且不會受到不同搜索引擎的影響 當(dāng)然 重要性高的頁面如果和檢索關(guān)鍵詞無關(guān)同樣也沒有任何意義 為此 Google 使用了完善的超文本匹 配分析技術(shù) 使得能夠檢索出重要而且正確的網(wǎng)頁 2 2 PageRank 算法 PageRank 算法的具體實(shí)現(xiàn)可以利用網(wǎng)頁所對應(yīng)的圖的鄰接矩陣來表達(dá)超鏈接關(guān)系 為此 首先寫出所對應(yīng) 圖的鄰接矩陣A 為了能將網(wǎng)頁的頁面等級值平均分配給該網(wǎng)頁所鏈接指向的網(wǎng)頁 對各個行向量進(jìn)行歸一化 處理 得矩陣A PageRank 算法的矩陣是將歸一化矩陣A轉(zhuǎn)置所得矩陣 T AW 這樣形成的矩陣W被稱為轉(zhuǎn) 移概率矩陣 它的各個列向量之和為全概率 1 各個行矢量表示狀態(tài)之間的轉(zhuǎn)移概率 轉(zhuǎn)移概率矩陣與 Markoff 過程有著密切的聯(lián)系 3 轉(zhuǎn)置的理由是 PageRank 算法并非重視鏈接到多少頁面 而是重視被多少頁面鏈接 各 個網(wǎng)頁的頁面等級值 PageRank 的計(jì)算 就是求這個轉(zhuǎn)移概率矩陣 W 的最大特征值所屬的特征向量 現(xiàn)在以前面給出的三個頁面之間的超鏈接關(guān)系為例 說明 PageRank 算法如何計(jì)算給定網(wǎng)頁的頁面等級值 PageRank 從而定量地知道哪些網(wǎng)頁是最重要的 為利用網(wǎng)頁所對應(yīng)的圖的鄰接矩陣來表達(dá)鏈接關(guān)系 首先寫 出所對應(yīng)圖的鄰接矩陣 001 100 110 A 為了能將網(wǎng)頁的頁面等級值平均分配給該網(wǎng)頁所鏈接指向的網(wǎng)頁 對各個行向量進(jìn)行歸一化處理 得 第 36 卷 482 西南民族大學(xué)學(xué)報 自然科學(xué)版 001 100 2 1 2 1 0 A 將歸一化所得的矩陣A轉(zhuǎn)置 所得到的轉(zhuǎn)移概率矩陣 ij wW 為 012 1 002 1 100 T AW 現(xiàn)給每個頁面 i P一個 PageRank 值 i x 這些 PageRank 值應(yīng)該由鏈接到該頁面的那些頁面的 PageRank 值確 定 即指向 i P的那些頁面的頁面等級值之和應(yīng)該與 i P的頁面等級值 i x成正比 設(shè)共同的比例系數(shù)為 則有下 面的線性方程組 i j jij xxw 3 1 3 2 1 i 1 令 T xxxx 321 為頁面等級值組成的列向量 則由矩陣乘法 等式 1 可以寫成 xWx 由此求出轉(zhuǎn)移概率矩陣的最大正特征值1 相應(yīng)非負(fù)特征向量 T x 1 2 1 1 由此可以確定網(wǎng)頁的排 序?yàn)?C A B 其中頁面 A C 的排序無顯著差別 之所以將 C 排在前面是因?yàn)橹赶?C 的超鏈接數(shù)更多一些 2 3 隨機(jī)沖浪模型 Random Surfer Model PageRank 算法原理中有一個重要的假設(shè) 所有的網(wǎng)頁形成一個閉合的鏈接圖 除了這些文檔以外沒有其他 任何鏈接的出入 并且每個網(wǎng)頁能從其他網(wǎng)頁通過超鏈接達(dá)到 但是在現(xiàn)實(shí)的網(wǎng)絡(luò)中 并不完全是這樣的情況 當(dāng)一個頁面沒有出鏈的時候 它的 PageRank 值就不能被分配給其它的頁面 同樣道理 只有出鏈接而沒有入鏈 接的頁面也是存在的 但 PageRank 并不考慮這樣的頁面 因?yàn)闆]有流入的 PageRank 而只流出的 PageRank 從 對稱性角度來考慮是很奇怪的 同時 有時候也有鏈接只在一個集合內(nèi)部旋轉(zhuǎn)而不向外界鏈接的現(xiàn)象 在現(xiàn)實(shí) 中的頁面 無論怎樣順著鏈接前進(jìn) 僅僅順著鏈接是絕對不能進(jìn)入的頁面群總歸是存在的 PageRank 技術(shù)為了解決這樣的問題 提出用戶的隨機(jī)沖浪模型 用戶雖然在大多數(shù)場合都順著當(dāng)前頁面中 的鏈接前進(jìn) 但有時會突然重新打開瀏覽器隨機(jī)進(jìn)入到完全無關(guān)的頁面 Google 認(rèn)為 用戶在 85 的情況下沿著 鏈接前進(jìn) 但在 15 的情況下會跳躍到無關(guān)的頁面中 用公式表示相應(yīng)的轉(zhuǎn)移概率矩陣為 T ee n d dWW 1 其中 e為分量全為 1 的n維列向量 從而 T ee為全 1 矩陣 1 0 d為權(quán)重因子 damping factor 在實(shí)際中 Google 取85 0 d 也就是說 在隨機(jī)沖浪模型中 求各個頁面等級值 PageRank 的問題變成了求正矩陣W的 最大特征值所屬的特征向量問題 還是考慮前面給出的三個網(wǎng)頁 A B C 之間的超鏈接關(guān)系 在隨機(jī)沖浪模型下為方便計(jì)算令5 0 d 相 應(yīng)的轉(zhuǎn)移概率矩陣為 0 16670 66670 4167 0 16670 16670 4167 0 66670 16670 1667 3 5 01 5 0 T eeWW 根據(jù)著名的 Perron Frobenius 定理 3 轉(zhuǎn)移概率矩陣W的最大正特征值是 1 相應(yīng)的特征向量為 T 13 15 13 14 13 10 由此可以確定網(wǎng)頁的排序?yàn)?C A B 可見隨機(jī)沖浪模型下的排序結(jié)果更合理一些 483 第 3 期 趙國等 Google 搜索引擎的數(shù)學(xué)模型及其應(yīng)用 3 頁面等級算法 PageRank 的應(yīng)用 首先我們從圖論的角度解釋 PageRank 算法的原理 一是看這個頁面對應(yīng)頂點(diǎn)的入度 二是要給指向該頂 點(diǎn)的邊賦予權(quán)重 表明這個超級鏈接的重要性 具體的講 就是把所有的頁面看作圖里面的點(diǎn) 然后給每一個頁 面一個數(shù)量 用這個數(shù)量來刻畫頁面的重要性 這樣網(wǎng)頁的重要性就脫離了它的具體內(nèi)容 我們只需從網(wǎng)絡(luò)拓 撲結(jié)構(gòu)出發(fā)研究網(wǎng)頁的重要性 這樣就可以用圖論來研究向互聯(lián)網(wǎng)這樣的隨機(jī)復(fù)雜網(wǎng)絡(luò) 而且按照這個原理對 網(wǎng)頁排序具有三個優(yōu)點(diǎn) 第一 排序與特定搜索關(guān)鍵詞無關(guān) 第二 網(wǎng)頁排序與網(wǎng)頁的具體內(nèi)容無關(guān) 第三 只 需要知道網(wǎng)頁所對應(yīng)的圖的結(jié)構(gòu) PageRank 算法的這個特點(diǎn)使得它可以被應(yīng)用于社會領(lǐng)域的其他問題 例如體育比賽的排名問題 下面針對 1993 年全國大學(xué)生數(shù)學(xué)建模競賽 B 題 4 利用 PageRank 算法討論足球隊(duì)排名次問題 我們發(fā)現(xiàn)隨機(jī)沖浪模型可 以有效克服數(shù)據(jù)缺損等方面的困難 足球隊(duì)排名次問題要求我們建立一個客觀的評估方法 只依據(jù)過去一段時間 幾個賽季或幾年 內(nèi)每個球隊(duì) 的戰(zhàn)績給出各個球隊(duì)的名次 具有很強(qiáng)的實(shí)際背景 5 通過分析題中 12 支足球隊(duì)在聯(lián)賽中的成績 不難發(fā)現(xiàn)表 中的數(shù)據(jù)殘缺不全 隊(duì)與隊(duì)之間的比賽場數(shù)相差很大 直接根據(jù)比賽成績來排名次比較困難 下面我們利用 PageRank 算法的隨機(jī)沖浪模型來求解 類比 PageRank 算法 我們可以綜合考慮各隊(duì)的比賽成績?yōu)槊恐蜿?duì)計(jì)算相應(yīng)的等級分 Rank 然后根據(jù)各 隊(duì)的等級分高低來確定名次 直觀上看 給定球隊(duì)的等級分應(yīng)該由它所戰(zhàn)勝和戰(zhàn)平的球隊(duì)的數(shù)量以及被戰(zhàn)勝或 戰(zhàn)平的球隊(duì)的實(shí)力共同決定 具體來說 確定球隊(duì) i T的等級分的依據(jù)應(yīng)為 一是看它戰(zhàn)勝和戰(zhàn)平了多少支球隊(duì) 二要看它所戰(zhàn)勝或戰(zhàn)平球隊(duì)的等級分的高低 這兩條就是我們確定排名的基本原理 在實(shí)際中 若出現(xiàn)等級分 相同的情況 可以進(jìn)一步根據(jù)凈勝球的多少來確定排名 由于表中包含的數(shù)據(jù)量龐大 我們先在不計(jì)平局 只考慮獲勝局的情形下計(jì)算出各隊(duì)的等級分 以說明算 法原理 然后我們綜合考慮獲勝局和平局 加權(quán)后得到各隊(duì)的等級分 并據(jù)此進(jìn)行排名 考慮到競技比賽的結(jié)果 的不確定性 我們最后建立了等級分的隨機(jī)沖浪模型 分析表明等級分排名結(jié)果具有良好的參數(shù)穩(wěn)定性 3 1 獲勝局的等級分 首先利用有向賦權(quán)圖的權(quán)重矩陣來表達(dá)出各隊(duì)之間的勝負(fù)關(guān)系 用圖的頂點(diǎn)表示相應(yīng)球隊(duì) 用連接兩個頂 點(diǎn) i T與 j T的有向邊表示兩隊(duì)的比賽結(jié)果 同時給該邊賦予相應(yīng)的權(quán)重 表明 i T戰(zhàn)勝 j T的次數(shù) 由此 可以寫出 表中 12 支球隊(duì)所對應(yīng)的有向賦權(quán)圖的權(quán)重矩陣 S 0 1 1 3 1 1 0 1 2 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 2 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 2 0 1 2 0 0 0 2 3 2 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 2 0 2 1 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 例如 表中 3 T與 8 T比賽了兩場 各勝一場 故1 38 T 1 83 T 同理 3 14 T表明 1 T曾 3 次戰(zhàn)勝 4 T 注意到被戰(zhàn)勝球隊(duì)的等級分應(yīng)該平均分配給各個獲勝球隊(duì) 將權(quán)重矩陣的各個列向量向量進(jìn)行歸一化 得 轉(zhuǎn)移概率矩陣 ij sS 為 第 36 卷 484 西南民族大學(xué)學(xué)報 自然科學(xué)版 S 0 0 1667 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 3333 0 1667 0 0 0 125 0 0 0 0 0833 0 1667 0 25 0 0 3333 0 1667 0 3333 0 0 25 0 0 0 0 0833 0 1667 0 0 0 0 1667 0 1667 0 125 0 0 0 0 0 0833 0 1667 0 0 2 0 3333 0 1667 0 3333 0 375 0 25 0 0 0 0 1667 0 1667 0 0 4 0 0 0 0 0 0 0 0 2 0 0833 0 0 0 0 0 1667 0 0 0 0 0 0 0 0833 0 0 0 0 0 0 0 0 125 0 0 0 0 0 0 0 0 0 0 1667 0 125 0 125 1 0 3333 0 2 0 0833 0 0 5 0 2 0 0 0 0 125 0 0 0 3333 0 0 0833 0 1667 0 0 2 0 0 0 0 25 0 125 0 0 3333 0 2 0 25 0 1667 0 25 0 現(xiàn)設(shè)每個隊(duì) i T的等級分 i x 這些等級分應(yīng)由被 i T戰(zhàn)勝的那些隊(duì)的等級分確定 即 i j jij xxs 12 1 12 2 1 i 3 其中 為比例系數(shù) 令 T xxx 121 則由矩陣乘法 等式 3 可以寫成 xxS 即各個隊(duì)的等級分的計(jì)算 轉(zhuǎn)化求這個轉(zhuǎn)移概率矩陣S的最大正特征值 所屬的正特征向量 直接利用 Matlab軟 件 計(jì) 算 得1 相 應(yīng) 等 級 分 為 0 2731 0 2085 0 7144 0 0302 0 0026 0 003 0 456 0 2416 0 2503 0 2042 0 0005 0 0006 由此可以確定只算獲勝局的情況下各隊(duì)的排名為 1112564102 89 173 T T T T T T T T T T T T 3 2 加權(quán)等級分 在實(shí)際中 平局也會隊(duì)雙方的排名產(chǎn)生影響 因此也有必要考慮平局對等級分的貢獻(xiàn) 因?yàn)槠骄质窍嗷サ?所以可以利用無向賦權(quán)圖的權(quán)重矩陣來表達(dá)出各隊(duì)之間的平局關(guān)系 即 P 0 2 0 0 1 0 0 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 2 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 2 0 0 0 1 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 2 2 0 1 2 0 0 1 0 0 2 0 0 0 0 0 0 1 1 0 注意平局的權(quán)重矩陣P是對稱的 同時注意到被戰(zhàn)平球隊(duì)的等級分也應(yīng)該平均分配給各個與之戰(zhàn)平的球隊(duì) 故將權(quán)重矩陣的各個列向量向量進(jìn)行歸一化處理 得轉(zhuǎn)移概率矩陣 485 第 3 期 趙國等 Google 搜索引擎的數(shù)學(xué)模型及其應(yīng)用 P 0 1 0 0 0 2 0 0 0 6667 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3333 0 2 0 25 0 0 0 2 0 0 1 0 5 0 0 0 1429 0 0 0 0 0 0 2 0 0 1 0 0 2 0 0 1429 0 0 0 25 0 0 0 0 0 2 0 0 0 0 1429 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1429 0 3333 0 0 0 0 0 0 5 0 2 0 0 0 0 0 0 0 0 0 0 2 0 0 0 25 0 0 0 1429 0 3333 0 4 0 5 0 0 3333 0 4 0 0 0 25 0 0 0 2857 0 0 0 0 0 0 0 5 0 1 0 根據(jù)常識 在一場比賽中平局出現(xiàn)的概率為 3 1 同時 考慮到通常平局與獲勝局的得分比為3 1 我們可以 對平局和獲勝局的轉(zhuǎn)移概率矩陣進(jìn)行加權(quán)處理 得到下面的加權(quán)權(quán)重矩陣 SPW3 3 2 1 3 1 0 0 6667 0 0 0 0667 0 0 0 6222 0 0 0 0 0 1333 0 0 0 0 0 0 0 4 0 0 0 0 0 6667 0 3333 0 0 1111 0 3167 0 0833 0 0 0 2333 0 3333 0 5333 0 1667 0 6667 0 3333 0 7143 0 0 5 0 0 0 0 2333 0 3333 0 0333 0 0 0667 0 3333 0 3810 0 25 0 0 0833 0 0 0 1667 0 3333 0 0667 0 4 0 6667 0 3333 0 7143 0 75 0 5667 0 0 0 0 3333 0 3333 0 0667 0 8 0 0 0 0 0 0 0 0 4 0 1667 0 0 0 0 1333 0 3333 0 0 0 0 0 0 0 1667 0 0 0333 0 0 0 0 0476 0 1111 0 25 0 0 0 0 0 1667 0 0667 0 0 0 0 3333 0 25 0 25 2 0 6667 0 4 0 2333 0 1 0 4833 0 0 0 0476 0 3611 0 1333 0 1667 0 6667 0 1111 0 3 0 3333 0 0 4833 0 0 0 0952 0 5 0 25 0 0 6667 0 4 0 5 0 5 0 5333 0 同樣 被戰(zhàn)勝或或戰(zhàn)平球隊(duì)的等級分也應(yīng)該平均分配給各個獲勝隊(duì)或與之戰(zhàn)平的球隊(duì) 故將加權(quán)權(quán)重矩陣的各個 列向量向量進(jìn)行歸一化 得轉(zhuǎn)移概率矩陣 ij wW 為 W 0 0 2857 0 0 0 0286 0 0 0 2667 0 0 0 0 0 0571 0 0 0 0 0 0 0 1714 0 0 0 0 0 2857 0 1429 0 0 0476 0 1357 0 0357 0 0 0 1 0 1429 0 2286 0 0714 0 2857 0 1429 0 3061 0 0 2143 0 0 0 0 1 0 1429 0 0143 0 0 0286 0 1429 0 1633 0 1071 0 0 0357 0 0 0 0714 0 1429 0 0286 0 1714 0 2857 0 1429 0 3061 0 3214 0 2429 0 0 0 0 1429 0 1429 0 0286 0 3429 0 0 0 0 0 0 0 0 1714 0 0714 0 0 0 0 0571 0 1429 0 0 0 0 0 0 0 0714 0 0 0143 0 0 0 0 0204 0 0476 0 1071 0 0 0 0 0 0714 0 0286 0 0 0 0 1429 0 1071 0 1071 0 8571 0 3333 0 1714 0 1 0 0 4286 0 2071 0 0 0 0204 0 1548 0 0571 0 0714 0 3333 0 0476 0 1286 0 1429 0 0 2071 0 0 0 0408 0 2143 0 1071 0 0 3333 0 1714 0 2143 0 2143 0 2286 0 現(xiàn)設(shè)每個隊(duì) i T的等級分為 i x 這些等級分應(yīng)由 i T所戰(zhàn)勝或戰(zhàn)平的那些隊(duì)的等級分確定 即 i j jij xxw 12 1 12 2 1 i 4 第 36 卷 486 西南民族大學(xué)學(xué)報 自然科學(xué)版 其中 為比例系數(shù) 令 T xxx 121 則由矩陣乘法 等式 4 可以寫成 xxW 即各個隊(duì)的等級分的計(jì)算 轉(zhuǎn)化求平局的轉(zhuǎn)移概率矩陣矩陣W的最大正特征值 所屬的非負(fù)特征向量 直 接利用 Matlab 軟件計(jì)算得1 相應(yīng)等級分為 0110 0 0026 0 419 0 25210 2473 0 2 0 4435 118 0 009 0 0981 0 0 27 0 265 0 66 0 3173 由此可以確定在綜合考慮獲勝局和平局的情況下各隊(duì)的排名為 116125498 102 173 T T T T T T T T T T T T 3 3 等級分的隨機(jī)沖浪模型 在大多數(shù)時候 競技比賽的結(jié)果都是兩隊(duì)之間實(shí)力的客觀反映 但是 競技比賽的結(jié)果有時具有一定的不 確定性 它很容易受到某些偶然或人為因素的影響 為了消除這些不確定因素的影響 我們需要建立等級分的 隨機(jī)沖浪模型 設(shè)球隊(duì)的實(shí)力能確定比賽的結(jié)果的概率為d 即強(qiáng)隊(duì)因?yàn)椴淮_定因素輸?shù)艚o任意一支球隊(duì)的概率為d 1 則可得下面的轉(zhuǎn)移概率矩陣 T ee n d WdW 1 其中 e為分量全為 1 的n維列向量 從而 T ee為全 1 矩陣 1 0 d為權(quán)重因子 在實(shí)際中可以根據(jù)歷史數(shù)據(jù) 確定 同樣 各個隊(duì)的等級分的計(jì)算 轉(zhuǎn)化求轉(zhuǎn)移概率矩陣W最大正特征值所屬的正特征向量 下面著重分析權(quán)重因子 1 0 d的變化對排名的影響 為此 我們利用 Matlab 軟件計(jì)算出權(quán)重因子d取不 同的值時的排名情況如表 1 表 1 權(quán)重因子d取不同的值時的排名情況 d取值范圍 球隊(duì)排名 1 d 116125498 102 173 T T T T T T T T T T T T 95 09 0 d 116512498 102 173 T T T T T T T T T T T T 85 045 0 d 116512489 102 173 T T T T T T T T T T T T 4 0 d 6115124109 82 173 T T T T T T T T T T T T 從表中可以看出 根據(jù)等級分的排名結(jié)果具有良好的穩(wěn)定性 并且 權(quán)重因子的變化