关于本节代码中tmp_rank[root]与alpha的问题

来源:3-4 代码实战personal rank算法的基础版本

综合奖

2019-08-27

老师好,我对本节中的代码有一些疑问

    for iter_index in range(iter_num):
        tmp_rank = {point: 0 for point in graph}
        for out_point, out_dict in graph.items():
            for inner_point, value in out_dict.items():
                tmp_rank[inner_point] += round(alpha * rank[out_point] / len(out_dict), 4)
                if inner_point == root:
                    tmp_rank[inner_point] += round(1 - alpha, 4)
        print('iter ', iter_index, ' tmp_rank', tmp_rank)
        if tmp_rank == rank:
            break
        rank = tmp_rank

本节代码中的核心部分,对于root结点,在计算pr值时,不止要计算其他结点依照图中的边一步转移到root结点时的概率,也要加上其他节点直接回到root结点的概率

我觉得在outer_point和inner_point这两层for循环中有可能多次计算其他结点直接回到root结点的概率
例如对于记录(a,A) (b,A),在root=A并且游走到a和游走到b时,即out_point=a或b,inner_point=A的时候,都会令tmp_rank[A]+=1-alpha
那么这个时候tmp_rank[A]的pr值就重复加上了1-alpha
根据公式里的内容,在计算A的pr值时应该只加一次1-alpha

所以我觉得代码应该写成如下形式,即去掉if判断,改为在外层直接tmp_rank[root]+=round(1-alpha,4)

    for iter_index in range(iter_num):
        tmp_rank = {point: 0 for point in graph}
        for out_point, out_dict in graph.items():
            for inner_point, value in out_dict.items():
                tmp_rank[inner_point] += round(alpha * rank[out_point] / len(out_dict), 4)
        tmp_rank[root] += round(1 - alpha, 4)
        print('iter ', iter_index, ' tmp_rank', tmp_rank)
        if tmp_rank == rank:
            break
        rank = tmp_rank

这是我第二份代码在rank达到收敛时的运行结果
tmp_rank {‘A’: 0.5014000000000001, ‘item_a’: 0.1127, ‘item_b’: 0.1127, ‘item_d’: 0.1127, ‘B’: 0.0412, ‘item_c’: 0.0248, ‘C’: 0.0412, ‘item_e’: 0.0124, ‘D’: 0.0412}
其中所有的pr_score相加的结果约为1,我想应该符合算法的定义,大约描述了从A出发,向各个结点转移的概率

写回答

1回答

David

2019-08-27

你所说的 a,A b,A 本来就构成了 A-》a , A-》b 两条路径, 我们在随机游走的时候, 游走到a, a可能会回到A, 游走的b,b依然可能会回到A。两次没问题。

0
1
综合奖
老师好,确实a可能回到A,b也可能回到A,但是我们之前实现的graph,里面的形式像这样 {'A':{'a':1,'b':1},'a':{'A':1},'b':{'B':1}} 不仅包含A->a,也包含a->A这样的记录 依照代码逻辑,当循环进行到out_point=a或out_point=b,以及inner_point=A的时候,此时计算pr score,tmp_rank[A]会加上1-alpha,这样的话就是加了两次。 但我们上节课的公式是PR(A)=1-alpha+alpha*所有(与A相邻点的pr值/与A相邻点的出度),PR(A)里只加过一次1-alpha,这样的话在代码里是不是重复加了1-alpha?
2019-08-29
共1条回复

个性化推荐算法实战(可用于毕设) BAT大牛亲授

让你掌握一套完整的,能落地的个性化推荐算法体系。可用于毕设。

839 学习 · 253 问题

查看课程