java - Page Rank算法计算错误的页面排名

Question

我正在尝试实现一个页面排名算法。

我总共有 5 个网页(见下图)。下图表示一个图表并显示哪个网页包含指向哪个页面的链接。

我已将此网页链接存储在 HashMap 中，每个网页的唯一链接都存储为 key 和 HashSet 包含给定网页指向的网页的所有链接被存储为该键的值。 (见下图)

每个网页都由其唯一链接表示。上面提到的HashMap在代码中表示为

HashMap<URI, HashSet<URI>> graph = new HashMap<>();

我选择了等于 0.85 的 decay 值和等于 0.00001 的 epsilon

问题

在生成上面提到的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 除外.

我已经在这个page rank 算法中尝试了不同的输入，无论我尝试什么，我总是有一个或两个网页 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);
    }
}

下面是简单的WebPage类

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); 
}

Answer 1

总结: 您正在测试错误的值。您必须减少代码的 epsilon 值，以使网页排名在所需值的 0.00001 以内。 0.00001 以内的两次连续猜测并不意味着该结果。

除了我在评论中指出的问题外，我相信我也看到了您的问题。这是收敛中的一个概念问题。看来单元测试的要求是收敛到预定值的 epsilon 以内。您还没有为此编写算法。你的测试

if (oldPageRanks.get(uri) - newPageRanks.get(uri) >= epsilon)

检查两个连续的近似值是否在该值内。这不保证新页面排名在最终值的 epsilon 范围内。 “近”邻域的微积分/拓扑定义如下所示，用于猜测 x 和引用(正确)点 z。

abs(x - z) < delta  ==>  abs(f(x) - f(z)) < epsilon

您可能混淆了 delta 和 epsilon。

如果你的近似函数的梯度在 [-1, +1] 范围之外，那么你很可能会犯这个错误。您需要找到它所对应的 delta 值，然后使用 that 量代替当前的 epsilon。这是您提供给函数的 epsilon 值的简单更改。