关于本节代码中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。两次没问题。
012019-08-29
相似问题