wzhe06/SparrowRecSys

关于随机游走采样的方式

shexuan opened this issue · 2 comments

shexuan commented

王老师您好，对于代码中randomwalk随机采样方式，有一些疑问，代码如下：

    while i < sampleLength:
        if (curElement not in itemDistribution) or (curElement not in transitionMatrix):
            break
        probDistribution = transitionMatrix[curElement]
        randomDouble = random.random()
        accumulateProb = 0.0
        for item, prob in probDistribution.items():
            accumulateProb += prob
            if accumulateProb >= randomDouble:
                curElement = item
                break
        sample.append(curElement)
        i += 1

对于上面的代码我的理解是先随机一个概率randomDouble然后按某个顺序probDistribution.items()遍历当前结点的所有邻接点，每个邻接点概率与原始概率accumulateProb相加，当累计相加大于randomDouble时就选择这个结点放入路径中。

个人感觉这种方式没有利用到probDistribution.items()中的概率分布，即便是使用无权边也即所有邻接点的概率相同，用老师的这种方式也是可以做的。我的想法是是否能够充分利用到邻接点的概率分布，对于概率大的（也即原始pair出现次数多的）给与更大的采样概率？ 使用np.random.choice(adj_nodes, node_distributions)可以实现这种采样方式，而且效率可能比老师这种循环的方式来得更快。

而按老师的这种采样方式，如果将probDistribution.items()先按从大到小排序，然后再采样，应该也能达到充分利用邻接点概率分布的效果。

不知道我的理解对不对？

wzhe06 commented

不是非常理解你的思路。这段代码中probDistribution保存了点curElement所有邻接点的概率，这个概率是提前处理好的，总和为1的概率。
randomDouble选择了一个0-1之间的随机数。

然后剩下的过程类似于一个转盘的游戏，randomDouble是一个随机数指针，然后指到哪个邻接点的概率区间，就选择哪个邻接点，这个过程应该是充分利用了邻接点的概率分布，而且是完全随机的。

你说的方式np.random.choice(adj_nodes, node_distributions) 应该也是可行的，但二者的过程应该是完全等价的，效率问题要看np.random.choice函数的具体内部实现。

shexuan commented

应该是我理解错了，我试了下代码，老师的代码跟np.random.choice采样结果基本是一样的，而且速度要快40倍左右，相当意外了👍