一、算法的前置知識
算法：計算每一個網頁的值，然后根據這個值的大小對網頁的重要性進行排序。
從用戶角度來看，一個網站就是若干頁面組成的集合。然而，對于網站的設計者來說，這些頁面是經過精心組織的，是通過頁面的鏈接串聯起來的一個整體。因此，Web的結構挖掘主要是對網站中頁面鏈接結構的發現。例如：在設計搜索引擎等服務時，對Web頁面的鏈接結構進行挖掘可以得出有用的知識來提高檢索效率和質量。
一般來說，Web頁面的鏈接類似學術上的引用，因此，一個重要的頁面可能會有很多頁面的鏈接指向它。也就是說java數據結構與算法免費下載，如果有很多鏈接指向一個頁面，那么它一定是重要的頁面。同樣地，假如一個頁面能鏈接到很多頁面，它也有其重要的價值。
設u為一個Web頁，Bu為所有指向u的頁面的集合，Fu為所有u指向的頁面的集合，c（在將一個頁面的等級值傳遞時，采用平均分配方法傳遞到所有它所指向的頁面，即每個從它鏈接處的頁面等分它的等級值。
算法的核心部分可以從一個有向圖開始。最典型的方法是根據有向圖構造一個鄰接矩陣來進行處理。鄰接矩陣A=(ai,j)中的元素ai,j(∈[0,1])表示從頁面j指向頁面i的概率。
二、算法的基本思想
基本的算法在計算等級值時，每個頁面都將自己的等級值平均地分配給其引用的頁面節點。假設一個頁面的等級值為1，該頁面上共有n個超鏈接，其分配給每個超鏈接頁面的等級值就是1/n，那么就可以理解為該頁面以1/n的概率跳轉到任意一個其所引用的頁面上。
一般地，把鄰接矩陣A轉換成所謂的轉移概率矩陣M來實現算法：M=(1-d)Q+dA，其中，Q是一個常量矩陣，最常用的是Q=(qi,j)，qi,j=1/n，轉移概率矩陣M可以作為一個向量變換矩陣來幫助完成頁面等級值向量R的迭代計算：Ri+1=M*R
三、算法的例子
算法例子
四、算法的實現過程
實驗內容
互聯網中的網頁的鏈接可以看作是有向圖，如A、B、C、D四個網頁，請采用算法對網頁進行分級排序
實驗思路
（1）定義Score分數類，在Score分數類中包含分子son和分母mom屬性，還包含靜態方法()用于對分子分母進行約分，靜態方法()用于分數相加并化簡結果，靜態方法()用于分數相乘并調用()對結果進行化簡。
（2）定義初始數據集，定義轉移矩陣的每一項Score分數類對象，調用()方法對數據集進行初始化。
（3）定義Score類對象并對其實例化，對象表示分數值1/4，表示最初人們對點擊A，B，C，D四個網頁的概率都是相同的1/4。定義一維數組V0存放4個，初始的也賦值成V0。
（4）進入while循環，調用()方法獲取矩陣。在()方法體內部定義集合存放最終的值，遍歷數據集中每一項數據，使用for循環遍歷，使得和Vk完成矩陣乘法，并將矩陣乘法后每一項的結果保存在當中，當遍歷結束后，將添加到集合當中，在遍歷數據集集合結束后，將轉換成數組后返回。
（5）調用()方法判斷新得到的矩陣值是否和上次得到的矩陣值相同，若不相同則繼續迭代，若相同則不再迭代。()方法主要是判斷形參V1和形參V2的矩陣內的值是否相等，返回類型的值，方法體內部對數組V1進行遍歷，比較V1中每一項的分子和V2中每一項的分子是否相同，若有不相同的則返回false，若遍歷結束后沒有不同的則返回true。
（6）若新得到的矩陣值不與上次得到的矩陣值相同，則將新得到的矩陣值賦值給最終要輸出的變量，輸出每一次得到的值。
實現源碼
Score類
package com.data.mining.entity;
import lombok.Data;
@Data
public class Score {
private int son;
private int mom;
public Score(){}
public Score(int s, int m){
son = s;
mom = m;
}
/**
* 分數相加并調用simplify方法進行約分
* @param s1
* @param s2
* @return
*/
public static Score getAdd(Score s1, Score s2){
if (s1.getMom() == 0 || s2.getMom() == 0) return s1.getMom() == 0 ? s2 : s1;
int commonMom = s1.getMom() * s2.getMom();
int commonSon = s1.getSon() * s2.getMom() + s2.getSon() * s1.getMom();
Score addResult = simplify(commonSon, commonMom);
return addResult;
}
/**
* 分數相乘并調用simplify方法進行約分
* @param s1
* @param s2
* @return
*/
public static Score getMultiply(Score s1, Score s2){
int tempMom = s1.getMom() * s2.getMom();
int tempSon = s1.getSon() * s2.getSon();
Score simplifyResult = simplify(tempSon, tempMom);
return simplifyResult;
}
/**
* 對分子分母進行約分
* @param s
* @param m
* @return
*/
private static Score simplify(int s, int m){
int common = getCommon(s, m);
s = s / common;
m = m / common;
Score result = new Score(s, m);
return result;
}
/**
* 找分子分母的最大公約數
* @param s
* @param m
* @return
*/
private static int getCommon(int s, int m){
for (int i = s; i >= 1; i--) {
if (m%i==0 && s%i==0){
return i;
}
}
return 1;
}
}
PageRank算法實現代碼
package com.data.mining.main;
import com.data.mining.entity.Score;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PageRank {
//定義轉移矩陣
public static List<Score[]> dataList = new ArrayList<>();
//定義轉移矩陣中的每一項
public static Score s00,s01,s02,s03,s10,s11,s12,s13,s20,s21,s22,s23,s30,s31,s32,s33;
public static void main(String[] args) {
initData();
Score voScore = new Score(1, 4);
Score[] V0 = {voScore, voScore, voScore, voScore};
Score[] pageRank = V0;
while (true){
Score[] tmpVk = getPageRank(pageRank);
if (isRankEqual(pageRank, tmpVk)) break; //新得到的PageRank矩陣和上次得到的PageRank矩陣不相同，則繼續迭代，相同則不再迭代
pageRank = tmpVk;
System.out.println(Arrays.toString(pageRank));
}
System.out.println(Arrays.toString(pageRank));
}
/**
* 判斷V1和V2的PageRank矩陣內的值是否相等
* @param V1
* @param V2
* @return
*/
public static boolean isRankEqual(Score[] V1, Score[] V2){
for (int i = 0; i < V1.length; i++) {
int subSon = V1[i].getSon() - V2[i].getSon();
int subMom = V1[i].getMom() - V2[i].getMom();
if (subSon != 0 || subMom != 0) return false;
}
return true;
}
/**
* 獲取PageRank矩陣
* @param Vk
* @return
*/
public static Score[] getPageRank(Score[] Vk){
List<Score> pageRankList = new ArrayList<>();
for (Score[] dataItem : dataList) {
Score itemSum = new Score(0,0); //itemSum中存放PageRank矩陣的每一項
//通過遍歷數據集的每一行和Vk的每一列實現矩陣乘法
for (int i = 0; i < dataItem.length; i++) {
Score multiply = Score.getMultiply(dataItem[i], Vk[i]);
itemSum = Score.getAdd(multiply, itemSum); //將對應項相乘的結果累加到itemSum中
}
pageRankList.add(itemSum);
}
return pageRankList.toArray(new Score[pageRankList.size()]);
}
/**
* 初始化數據集
*/
public static void initData(){
s00 = new Score(0, 0);
s01 = new Score(1, 2);
s02 = new Score(1, 1);
s03 = new Score(0, 0);
s10 = new Score(1, 3);
s11 = new Score(0, 0);
s12 = new Score(0, 0);
s13 = new Score(1, 2);
s20 = new Score(1, 3);
s21 = new Score(0, 0);
s22 = new Score(0, 0);
s23 = new Score(1, 2);
s30 = new Score(1, 3);
s31 = new Score(1, 2);
s32 = new Score(0, 0);
s33 = new Score(0, 0);
Score[] s0 = {s00, s01, s02, s03};
Score[] s1 = {s10, s11, s12, s13};
Score[] s2 = {s20, s21, s22, s23};
Score[] s3 = {s30, s31, s32, s33};
dataList.add(s0);
dataList.add(s1);
dataList.add(s2);
dataList.add(s3);
}
}
實驗結果
面對這個迭代結果，筆者還是有些許疑問的，書上最后的迭代結果說是趨于穩定了最后結果是[3/9，2/9java數據結構與算法免費下載，2/9，2/9]，可是本次實驗最終并沒有得到滿意的結果，而是因為數據溢出直接終止了程序，但可以看到最后一次輸出的結果已經很趨近于正確答案了，包括每次的迭代結果筆者也進行了筆算，也沒發現什么問題。這圖片不知道為啥字這么小，反正我是看不清，所以用表格盛一下：
五、實驗總結
本實驗結果筆者并不保證一定是正確的，筆者僅僅是提供一種使用Java語言實現算法的思路。因為實驗并沒有給答案，筆者已將書上有答案的實驗數據輸入程序后，程序輸出的結果和答案一致，所以問題應該不大。若有寫的不到位的地方，還請各位多多指點！
筆者主頁還有其他數據挖掘算法的總結，歡迎各位光顧！