Re: [問題] 有人寫過PageRank嘛?(Google搜尋引擎技術)
先跟版主還有板友們說聲抱歉啊
這不是學校作業啦(囧),只是想研究看看啊
我大致上了解PageRank的演算法啦:
PR(pi) = (1-d)/N + Σ( PR(pj)/L(pj) )
PR(pi)為目標網頁i的PR值
PR(pj)為具有指向網頁i連結的網頁j的PR值
L(pj)為網頁j中超連結的數目
N為網頁總數
d為隨機瀏覽的機率,一般設定為0.85
不過在實作上就碰到了滿多困難,例如如何parse之前所講到的紀錄所有連結資訊的txt檔
然後把對所一網頁的inLink outLink資訊作儲存,才有辦法算PageRank
因為八月才開始學java的關係,在寫比較長的程式碼時會碰到很多問題
於是之後找到了一個Package-WebLA
http://webla.sourceforge.net/ 首頁
http://webla.sourceforge.net/javadocs/ API documentation
其中包含了許多Link Analysis的演算法如PageRank'HITS和SimRank等等
比較重要的是WebGraph這個Class,可以parse文件檔然後儲存連結資訊
雖然裡面寫的輸入格式跟我現有的資料格式不同,不過在修改和測試後也可以使用了
目前的問題就卡在另一個Class-PageRank上面了
其中的方法PageRank:
public Double pageRank(String link)
輸入參數為目標網址,會傳回該網只在計算過後的PR值
計算了手邊紀錄了數十萬筆連結資訊的txt檔後(記憶體加到1G才有辦法算)
出現了以下問題(連結資訊格式為url1 -> url2):
1.出現在右邊的連結(如上一行的url2),傳回值全都會是Infinity
2.出現在左邊的連結(如上一行的url1),傳回值幾乎全部一樣(PR值完全相同,
小部分不相同)
想說應該是計算PR值的方法出了問題吧,但是又一直找不出來問題在哪
因此想麻煩各位大大幫我看看是哪邊寫錯了 謝謝
public void computePagerank(int iter) //iter為重複計算次數
{
int n=graph.numNodes(); //WebGraph的方法 numNodes(),傳回總節點(網頁)數
double aux = (1-dampening)/n; //dampening即為d,隨機瀏覽機率(0.85)
while((iter--)>0)
{
Map newScore = new HashMap();
for (int j=0;j<n;j++)
{
Map inlinks = graph.inLinks(new Integer(j));
//inLinks方法傳回參數型態為map,紀錄所有具有連向網頁pj超連結的網頁url
Iterator it = inlinks.keySet().iterator();
Double weight2 = new Double(0);
while (it.hasNext())
{
Integer link = (Integer)(it.next());
Double weight = (Double)(inlinks.get(link));
if(weight!=null && weight.doubleValue()>0)
{
int numLinks = 0;
Map outlinks = graph.outLinks(link);
Iterator it2 = inlinks.keySet().iterator();
while (it.hasNext())
{
Integer l = (Integer)(it.next());
Double w = (Double)(outlinks.get(l));
if(w!=null && w.doubleValue()>0) numLinks++;
}
weight2 = new Double(weight2.doubleValue() +
(((Double)(scores.get(link))).doubleValue()/numLinks));
}
}
weight2 = new Double(aux + dampening*weight2.doubleValue());
newScore.put(new Integer(j),weight2);
}
for (int j=0;j<n;j++)
{
scores.put(new Integer(j),(Double)(newScore.get(new Integer(j))));
}
}
}
整個程式碼太長了所以貼我覺得有問題的部分
如果有需要再把其他部分也貼出來,或是上面網頁也有程式碼可以下載
先謝謝大家了
※ 引述《willieliao (Willie Liao)》之銘言：
: ※ 引述《kians (臨兵鬥者皆陣列在前)》之銘言：
: : 如題,Google利用頁面分析+PageRank技術達成了搜尋引擎霸主的地位
: : PageRank就是給予每一個網頁一個value啦,用google自己發展的PageRank演算法
: : 用在搜尋後的網頁排序,越重要的網頁會放在越前面
: : 最近對PageRank滿有興趣的,要如何讓電腦對數以億計的網頁進行運算
: : 一般的電腦根本不可能達成吧,有點想知道演算法是怎麼寫的
: : 還是說關鍵在硬體? 用multiprocess的方式達成?
: GOOG是用分散式運算
: : 有人用java寫過PageRank的演算法嘛?
: 單純回答你的問題，有（舉手）
: 這是我在CARNEGIE MELLON CS大二資料結構的第三還是第四個作業，兩周要寫出來，
: 而且包括CRAWLER（讀取網頁並TOKENIZE），INDEXER﹛讓USER搜尋關鍵字），和PAGE
: RANKING。我是用JAVA寫的，據說GOOGLE是用RUBY寫的，不過還請板上強者補充。
: 這裡是我的作業的CLASS DIAGRAM，看看是不是你想要的
: http://www.willieliao.com/ooad/src/default.dfPackage.wmf
: : 希望能找到範例來參考一下,想對手邊有的幾十萬筆的連結資訊算出所有url的PageRank值
: : (格式(txt): url1->url2
: : url1->url3
: : url2->url3
: : .
: : .
: : . )
: : 不知道有沒有辦法辦到,先謝謝各位囉
: 既然你只要算PAGERANK，那左邊都不用管，建一個HASHMAP，對每一個右邊的
: URL先去看看MAP裡面有沒有，沒有的話用URL當KEY（假設你是STRING），用一個
: INTEGER HOLDER當DATA丟進去，KEY存在的話就把DATA的VALUE 加一
: 話說我怎麼聞到作業文的味道...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.201.125
推
11/02 23:56, , 1F
11/02 23:56, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 6 篇)：