定义
随机游走是一种数学统计模型,由连续的随机轨迹构成,常被用于网页搜索、图像分割、证券涨跌的预测等领域。随机游走的前提假设是任何无规则行走者所带的守恒量都各自对应着一个扩散运输定律[1]。随机游走的形式有三种:1)马尔科夫链或马尔科夫过程;2)醉汉走路;3)莱维飞行等过程。若随机游走是一维固定步长的无漂移随机游走,则我们假设每个粒子只能沿着一条直线运行,每次只能向左或向右随机走一步,每移动一步的概率是相等的如图1所示。因此我们取足够多的次数,则可以找到相对稳定的每步出现的概率。
图 1 一维随机游走
若随机游走用于二维图像[2],则其基本思想是将图像看成由固定的顶点和边组成的连通带权无向图,随机游走从未标记顶点开始随机漫步,首次到达各类标记顶点的概率代表了未标记点归属于标记类的可能性,把最大的概率所在类的标签赋给未标记顶点,完成分割。
参考文献
[1] Fama, Eugene F. "Random walks in stock market prices." Financial analysts journal 51.1 (1995): 75-80.
[2] Grady, Leo. "Random walks for image segmentation." IEEE transactions on pattern analysis and machine intelligence 28.11 (2006): 1768-1783.