Page Rank算法计算错误的页面排名
Page Rank algorithm computing wrong page ranks
我正在尝试实施 page rank
算法。
我共有 5 个网页(见下图)。下图表示一个图表,显示哪个网页包含 link 到哪个页面。
我已将此 link 网页年龄存储在 HashMap
中,这样每个网页的唯一 link 存储为 key
和 HashSet
包含给定网页指向的网页的所有 link 存储为该键的值。 (见下图)
每个网页都由其唯一的 link 表示。上面提到的HashMap
在代码中表示为
HashMap<URI, HashSet<URI>> graph = new HashMap<>();
我选择了 decay
值等于 0.85
和 epsilon
等于 0.00001
问题
生成上述 Hashmap
后,我正在计算每个网页的 page rank
。
最终聚合页面排名应该是
但我的实际网页排名是
Page A = 0.3170604814815385
Page B = 0.18719407056490575
Page C = 0.13199010955519944
Page D = 0.31131469834360015
Page E = 0.05244064005475638
每个页面的实际值都可以,因为每个页面的实际值和预期值之间的差异小于所选的 epsilon
值 Page D
[=91 除外=].
我已经尝试过对这个 page rank
算法的不同输入,无论我尝试什么,我总是有一个或两个网页 页面排名值不正确。算法在所有页面收敛页面排名之前返回,即每个页面的旧排名和新排名之间的差异小于 epsilon
值。
问题
我做错了什么?为什么我的网页排名算法会在所有网页排名收敛之前返回网页排名?
代码
以下函数生成上图中显示的 HashMap
。
private static HashMap<URI, HashSet<URI>> makeGraph(HashSet<WebPage> webpages) {
HashMap<URI, HashSet<URI>> webPagesGraph = new HashMap<>();
HashSet<URI> singleWebPageLinks;
HashSet<URI> availableWebPages = new HashSet<>();
// add all the web pages available in data set in a collection
for (WebPage doc : webpages) {
availableWebPages.add(doc.getUri());
}
for (WebPage doc : webpages) {
singleWebPageLinks = new HashSet<>();
for (URI link : doc.getLinks()) {
// if link is not pointing to the web page itself and is available in data set
if (!link.equals(doc.getUri()) && availableWebPages.contains(link)) {
singleWebPageLinks.add(link);
}
}
webPagesGraph.put(doc.getUri(), singleWebPageLinks);
}
return webPagesGraph;
}
以下函数计算网页排名
private static HashMap<URI, Double> makePageRanks(HashMap<URI, HashSet<URI>> graph,
double decay,
int limit,
double epsilon) {
// Step 1: The initialize step should go here
HashMap<URI, Double> oldPageRanks = new HashMap<>();
HashMap<URI, Double> newPageRanks = new HashMap<>();
double singleWebPageNewRank;
int numLinkedPagesBySinglePage;
double singleWebPageOldRank;
boolean haveConverged = true;
double rank;
// provide ranks to each web page
// initially the rank given to each page is 1/(total no. of web pages).
// also give new page rank to each page equal to zero
for (URI key : graph.keySet()) {
oldPageRanks.put(key, (double) 1 / graph.size());
newPageRanks.put(key, 0.0);
}
for (int i = 0; i < limit; i++) {
// Step 2: The update step should go here
for (URI uri : graph.keySet()) {
singleWebPageOldRank = oldPageRanks.get(uri);
numLinkedPagesBySinglePage = graph.get(uri).size();
// if any web page doesn't have any outgoing links to any other
// web page, increase the new page rank for every web page
if (numLinkedPagesBySinglePage == 0) {
for (URI u : newPageRanks.keySet()) {
singleWebPageNewRank = decay * (singleWebPageOldRank / graph.size());
saveNewRank(newPageRanks, u, singleWebPageNewRank);
}
} // increase the new page rank of every web page that is pointed to
// by current web page
else {
for (URI linkedWebPageURI : graph.get(uri)) {
singleWebPageNewRank = decay * (singleWebPageOldRank / numLinkedPagesBySinglePage);
saveNewRank(newPageRanks, linkedWebPageURI, singleWebPageNewRank);
}
}
}
// account for random user/surfer by adding (1 - decay) / (total no. of web pages)
// to each web page's new rank
for (URI uri : newPageRanks.keySet()) {
rank = newPageRanks.get(uri);
rank = rank + ((1 - decay) / graph.size());
newPageRanks.put(uri, rank);
// check for convergence
// check if difference b/w old rand and new rank for each web page
// is less than epsilon or not
// if difference between old and new ranks is greater than or
// equal to epsilon even for one web page, ranks haven't converged
if (oldPageRanks.get(uri) - newPageRanks.get(uri) >= epsilon) {
haveConverged = false;
}
}
if (haveConverged) {
return oldPageRanks;
} else {
haveConverged = true;
overWriteOldRanksWithNewRanks(oldPageRanks, newPageRanks);
}
}
return oldPageRanks;
}
以下两个函数是从 makePageRanks
函数中调用的实用函数
// save the new page rank for a given web page by adding the passed new page rank to
// its previously saved page rank and then saving the new rank
private static void saveNewRank(HashMap<URI, Double> newPageRanks, URI pageURI, double pageNewRank) {
pageNewRank += newPageRanks.get(pageURI);
newPageRanks.put(pageURI, pageNewRank);
}
// overwrite old page ranks for next iteration
private static void overWriteOldRanksWithNewRanks(HashMap<URI, Double> oldRanks, HashMap<URI, Double> newRanks) {
for (URI key : newRanks.keySet()) {
oldRanks.put(key, newRanks.get(key));
// make new rank for each web page equal to zero before next iteration
newRanks.put(key, 0.0);
}
}
以下为简单网页class
public class WebPage {
private ArrayList<String> words;
private URI uri;
private ArrayList<URI> links;
WebPage(URI uri, ArrayList<String> words, ArrayList<URI> links) {
this.words = words;
this.uri = uri;
this.links = links;
}
public ArrayList<String> getWords() {
return words;
}
public URI getUri() {
return uri;
}
public ArrayList<URI> getLinks() {
return links;
}
}
最后 main
方法,供任何想查看我为网页排名算法提供的输入的人使用
public static void main(String[] args) {
ArrayList<URI> pageALinks = new ArrayList<>();
pageALinks.add(createURI("www.b.com"));
pageALinks.add(createURI("www.d.com"));
URI pageAURI = createURI("www.a.com");
WebPage pageA = new WebPage(pageAURI, new ArrayList<>(), pageALinks);
ArrayList<URI> pageBLinks = new ArrayList<>();
pageBLinks.add(createURI("www.c.com"));
pageBLinks.add(createURI("www.d.com"));
URI pageBURI = createURI("www.b.com");
WebPage pageB = new WebPage(pageBURI, new ArrayList<>(), pageBLinks);
ArrayList<URI> pageCLinks = new ArrayList<>();
URI pageCURI = createURI("www.c.com");
WebPage pageC = new WebPage(pageCURI, new ArrayList<>(), pageCLinks);
ArrayList<URI> pageDLinks = new ArrayList<>();
pageDLinks.add(createURI("www.a.com"));
URI pageDURI = createURI("www.d.com");
WebPage pageD = new WebPage(pageDURI, new ArrayList<>(), pageDLinks);
ArrayList<URI> pageELinks = new ArrayList<>();
pageELinks.add(createURI("www.d.com"));
URI pageEURI = createURI("www.e.com");
WebPage pageE = new WebPage(pageEURI, new ArrayList<>(), pageELinks);
HashSet<WebPage> pages = new HashSet<>();
pages.add(pageA);
pages.add(pageB);
pages.add(pageC);
pages.add(pageD);
pages.add(pageE);
HashMap<URI, HashSet<URI>> graph = makeGraph(pages);
HashMap<URI, Double> map = makePageRanks(graph, 0.85, 100, 0.00001);
}
总结:
您正在测试错误的值。您必须减少代码的 epsilon
值才能使网页排名在所需值的 0.00001 范围内。 0.00001 以内的两次连续猜测并不意味着该结果。
除了我在评论中指出的问题外,我相信我也看到了您的问题。这是收敛中的一个概念问题。看来单元测试的要求是收敛到预定值的epsilon
以内。您还没有为此编写算法。你的测试
if (oldPageRanks.get(uri) - newPageRanks.get(uri) >= epsilon)
检查两个连续的近似值是否在该值内。这确实 不 保证新页面排名在最终值的 epsilon
范围内。 "close" 邻域的微积分/拓扑定义如下所示,用于猜测 x
和参考(正确)点 z
.
abs(x - z) < delta ==> abs(f(x) - f(z)) < epsilon
您可能混淆了 delta
和 epsilon
。
如果你的近似函数的梯度在[-1,+1]范围之外,那么你很可能会被这个错误绊倒。您需要找到它所对应的 delta
值,然后使用 that 数量代替您当前的 epsilon
。这是您提供给函数的 epsilon
值的简单更改。
我正在尝试实施 page rank
算法。
我共有 5 个网页(见下图)。下图表示一个图表,显示哪个网页包含 link 到哪个页面。
我已将此 link 网页年龄存储在 HashMap
中,这样每个网页的唯一 link 存储为 key
和 HashSet
包含给定网页指向的网页的所有 link 存储为该键的值。 (见下图)
每个网页都由其唯一的 link 表示。上面提到的HashMap
在代码中表示为
HashMap<URI, HashSet<URI>> graph = new HashMap<>();
我选择了 decay
值等于 0.85
和 epsilon
等于 0.00001
问题
生成上述 Hashmap
后,我正在计算每个网页的 page rank
。
最终聚合页面排名应该是
但我的实际网页排名是
Page A = 0.3170604814815385
Page B = 0.18719407056490575
Page C = 0.13199010955519944
Page D = 0.31131469834360015
Page E = 0.05244064005475638
每个页面的实际值都可以,因为每个页面的实际值和预期值之间的差异小于所选的 epsilon
值 Page D
[=91 除外=].
我已经尝试过对这个 page rank
算法的不同输入,无论我尝试什么,我总是有一个或两个网页 页面排名值不正确。算法在所有页面收敛页面排名之前返回,即每个页面的旧排名和新排名之间的差异小于 epsilon
值。
问题
我做错了什么?为什么我的网页排名算法会在所有网页排名收敛之前返回网页排名?
代码
以下函数生成上图中显示的 HashMap
。
private static HashMap<URI, HashSet<URI>> makeGraph(HashSet<WebPage> webpages) {
HashMap<URI, HashSet<URI>> webPagesGraph = new HashMap<>();
HashSet<URI> singleWebPageLinks;
HashSet<URI> availableWebPages = new HashSet<>();
// add all the web pages available in data set in a collection
for (WebPage doc : webpages) {
availableWebPages.add(doc.getUri());
}
for (WebPage doc : webpages) {
singleWebPageLinks = new HashSet<>();
for (URI link : doc.getLinks()) {
// if link is not pointing to the web page itself and is available in data set
if (!link.equals(doc.getUri()) && availableWebPages.contains(link)) {
singleWebPageLinks.add(link);
}
}
webPagesGraph.put(doc.getUri(), singleWebPageLinks);
}
return webPagesGraph;
}
以下函数计算网页排名
private static HashMap<URI, Double> makePageRanks(HashMap<URI, HashSet<URI>> graph,
double decay,
int limit,
double epsilon) {
// Step 1: The initialize step should go here
HashMap<URI, Double> oldPageRanks = new HashMap<>();
HashMap<URI, Double> newPageRanks = new HashMap<>();
double singleWebPageNewRank;
int numLinkedPagesBySinglePage;
double singleWebPageOldRank;
boolean haveConverged = true;
double rank;
// provide ranks to each web page
// initially the rank given to each page is 1/(total no. of web pages).
// also give new page rank to each page equal to zero
for (URI key : graph.keySet()) {
oldPageRanks.put(key, (double) 1 / graph.size());
newPageRanks.put(key, 0.0);
}
for (int i = 0; i < limit; i++) {
// Step 2: The update step should go here
for (URI uri : graph.keySet()) {
singleWebPageOldRank = oldPageRanks.get(uri);
numLinkedPagesBySinglePage = graph.get(uri).size();
// if any web page doesn't have any outgoing links to any other
// web page, increase the new page rank for every web page
if (numLinkedPagesBySinglePage == 0) {
for (URI u : newPageRanks.keySet()) {
singleWebPageNewRank = decay * (singleWebPageOldRank / graph.size());
saveNewRank(newPageRanks, u, singleWebPageNewRank);
}
} // increase the new page rank of every web page that is pointed to
// by current web page
else {
for (URI linkedWebPageURI : graph.get(uri)) {
singleWebPageNewRank = decay * (singleWebPageOldRank / numLinkedPagesBySinglePage);
saveNewRank(newPageRanks, linkedWebPageURI, singleWebPageNewRank);
}
}
}
// account for random user/surfer by adding (1 - decay) / (total no. of web pages)
// to each web page's new rank
for (URI uri : newPageRanks.keySet()) {
rank = newPageRanks.get(uri);
rank = rank + ((1 - decay) / graph.size());
newPageRanks.put(uri, rank);
// check for convergence
// check if difference b/w old rand and new rank for each web page
// is less than epsilon or not
// if difference between old and new ranks is greater than or
// equal to epsilon even for one web page, ranks haven't converged
if (oldPageRanks.get(uri) - newPageRanks.get(uri) >= epsilon) {
haveConverged = false;
}
}
if (haveConverged) {
return oldPageRanks;
} else {
haveConverged = true;
overWriteOldRanksWithNewRanks(oldPageRanks, newPageRanks);
}
}
return oldPageRanks;
}
以下两个函数是从 makePageRanks
函数中调用的实用函数
// save the new page rank for a given web page by adding the passed new page rank to
// its previously saved page rank and then saving the new rank
private static void saveNewRank(HashMap<URI, Double> newPageRanks, URI pageURI, double pageNewRank) {
pageNewRank += newPageRanks.get(pageURI);
newPageRanks.put(pageURI, pageNewRank);
}
// overwrite old page ranks for next iteration
private static void overWriteOldRanksWithNewRanks(HashMap<URI, Double> oldRanks, HashMap<URI, Double> newRanks) {
for (URI key : newRanks.keySet()) {
oldRanks.put(key, newRanks.get(key));
// make new rank for each web page equal to zero before next iteration
newRanks.put(key, 0.0);
}
}
以下为简单网页class
public class WebPage {
private ArrayList<String> words;
private URI uri;
private ArrayList<URI> links;
WebPage(URI uri, ArrayList<String> words, ArrayList<URI> links) {
this.words = words;
this.uri = uri;
this.links = links;
}
public ArrayList<String> getWords() {
return words;
}
public URI getUri() {
return uri;
}
public ArrayList<URI> getLinks() {
return links;
}
}
最后 main
方法,供任何想查看我为网页排名算法提供的输入的人使用
public static void main(String[] args) {
ArrayList<URI> pageALinks = new ArrayList<>();
pageALinks.add(createURI("www.b.com"));
pageALinks.add(createURI("www.d.com"));
URI pageAURI = createURI("www.a.com");
WebPage pageA = new WebPage(pageAURI, new ArrayList<>(), pageALinks);
ArrayList<URI> pageBLinks = new ArrayList<>();
pageBLinks.add(createURI("www.c.com"));
pageBLinks.add(createURI("www.d.com"));
URI pageBURI = createURI("www.b.com");
WebPage pageB = new WebPage(pageBURI, new ArrayList<>(), pageBLinks);
ArrayList<URI> pageCLinks = new ArrayList<>();
URI pageCURI = createURI("www.c.com");
WebPage pageC = new WebPage(pageCURI, new ArrayList<>(), pageCLinks);
ArrayList<URI> pageDLinks = new ArrayList<>();
pageDLinks.add(createURI("www.a.com"));
URI pageDURI = createURI("www.d.com");
WebPage pageD = new WebPage(pageDURI, new ArrayList<>(), pageDLinks);
ArrayList<URI> pageELinks = new ArrayList<>();
pageELinks.add(createURI("www.d.com"));
URI pageEURI = createURI("www.e.com");
WebPage pageE = new WebPage(pageEURI, new ArrayList<>(), pageELinks);
HashSet<WebPage> pages = new HashSet<>();
pages.add(pageA);
pages.add(pageB);
pages.add(pageC);
pages.add(pageD);
pages.add(pageE);
HashMap<URI, HashSet<URI>> graph = makeGraph(pages);
HashMap<URI, Double> map = makePageRanks(graph, 0.85, 100, 0.00001);
}
总结:
您正在测试错误的值。您必须减少代码的 epsilon
值才能使网页排名在所需值的 0.00001 范围内。 0.00001 以内的两次连续猜测并不意味着该结果。
除了我在评论中指出的问题外,我相信我也看到了您的问题。这是收敛中的一个概念问题。看来单元测试的要求是收敛到预定值的epsilon
以内。您还没有为此编写算法。你的测试
if (oldPageRanks.get(uri) - newPageRanks.get(uri) >= epsilon)
检查两个连续的近似值是否在该值内。这确实 不 保证新页面排名在最终值的 epsilon
范围内。 "close" 邻域的微积分/拓扑定义如下所示,用于猜测 x
和参考(正确)点 z
.
abs(x - z) < delta ==> abs(f(x) - f(z)) < epsilon
您可能混淆了 delta
和 epsilon
。
如果你的近似函数的梯度在[-1,+1]范围之外,那么你很可能会被这个错误绊倒。您需要找到它所对应的 delta
值,然后使用 that 数量代替您当前的 epsilon
。这是您提供给函数的 epsilon
值的简单更改。