随机行走（random walk）

第4章基于图的特征选择

我们研究的目的是寻找更高效、更能帮助分类器、能更好理解数据集的特征选择技术。我们提出一种新的基于图的过滤型特征选择算法：基于图的多类别特征结合算法（GMS, Graph-based Multi-category Score Combination）。

这一算法对数据集上的每个类构建一个词在这个图上通过马尔可夫链给每个词项算出一个评分，然后综合各个词项在各个类别的评分，得到每个词项的一个总的评分，从而得到一个词项的排序，选取评分最大的若干个词项，作为这一数据集的特征集合。

 

4.1图模型与符号表示

本节介绍算法的图模型，及算法中使用的符号表示。

 

4.1.1符号表示

设数据集可以表示为一个 的矩阵 ，其中 是总的特征数， 是数据集中的文档数。这是一个向量空间模型表示。 中的每一个列向量表一篇文档 , 的第 个元素由 表示， 。 表示 的转置。假设有 个类别， 。这里假设训练集中的每篇文档属于且仅属于一个类。

维度约简问题可以被定义为求解函数 ，其中 是原特征总数，p是约简后的特征数（ ），约简后的结果向量表示为 。从特征抽取的角度来看，特征约简问题目的在于找到一个优化的转换矩阵 ，使得 是原数据的遵循某种优化准则的 维数据表示。在特征抽取问题里， 是连续的解空间。然而，特征选择任务是为了找到原特征集的某个子集，使得 ,其中 是离散的解空间。 的元素或者是0、或者是1，而且 的每列只有一个非0元素。

在文本分类任务中，特征等价于词项，每个词项是一个特征。一个数据集的全特征集空间，既是除去stop words和stemming后的所有词项构成的词项空间。

特征约简的目的是除去不相关的数据并且提高学习的精确度。文本分类题中特征约简的优化准则是与全特征集空间的对比分类正确率。约简后的特征空间中进行的文本分类工作的分类能力应该和全空间特征集的差距不大，甚至超过全空间特征集的分类能力。

这里，定义特征选择问题为：

给定一组训练文档，特征选择任务是在原特征空间中选择一组特征子集，使得约简后的特征空间在某个优化标准上几乎与原特征空间是可比的。

在文本分类问题中，这一优化标准即是分类能力，具体表现为分类正确率、精准率、召回率、错误率、F1量测等一系列评价指标。

 

4.1.2图模型

算法对每个类别 构建两个图，一个是文档-词项图 ,一个是表示词项之间互相关联的词项图 。

令 表示一个类别 的无向二分图，其中 表示 的节点集合， 表示 的边集合。图4.1是一个 的示意图。小圆圈代表文档，小方框代表词项。一篇文档和一个词项有边，当且仅当此文档包含这个词。文档 和词项 之间的边权是t在文档里中的TF-IDF值：

 

 

 

其中 表示词项， 表示文档； 是词项 在文档 中出现的频率； 是数据集中所有文档的数目； 是词项 出现的文档数目。

 

 

 

图4.1: 是 的文档-词项图，图4.1是一个有4篇文档和5个词项的 的例子；其中小圆代表文档，小方框代表词项。

 

 

 

图4.2: 是由图4.1的 转换生成的词项图。其中小方框代表词项。

 

文档-词项矩阵W∈Rd×n既是图 的邻接矩阵，其中的元素是词项在文档中的TF-IDF值，也即是边权。

从文档-词项图 ，可以得到另一个图 ,其结点都是词项，如图4.2所示。令 表示类别 的一个无向图， 表示 的节点集合， 表示 的边集合。词项 和 有边，当且仅当 和 同时出现于至少一篇文档里。 和 的边权定义为：

 

 

 

其中 是0若文档 不包含词项 。 是所有 和 同时出现的文档的 和 权值之积的总和。则称词项 和 有关系， 和 在图 中有边相联，边权等于 。

    的邻接矩阵 可由如下公式得到：

 

 

 

是无向图 的邻接矩阵，且 是对称矩阵。

 

4.2马尔可夫链模型

在本算法中，马尔可夫链模型对寻找最重要的词项起到了很重要的作用。本节介绍马尔可夫链模型的基本思想和原理。

 

4.2.1中心性（Centrality）

表示的是类别 的词项图，而希望找到的是哪些词项更重要，也即是寻找哪些词项更重要。这里对类别 的词项图 进行分析。

见图4.2，显而易见，有较大的度的词项，例如词项4，它和比较多的词项相连接，所以，它看起来比其他度小的词项在这个图中更有意义，也既是更重要。然而，只考虑度的大小是不够的。度的大小反映了结点的在小范围内的相对重要性，而即使度相同，不同重要程度的边也会使不同的结点不一样重要。这里希望得到的是整个图上，每个结点的重要程度。称整个图上的结点重要性为中心性（Centrality）。

举个例子，考虑一个社交网络。社交网络里的每个结点是人，每个人认识一些朋友，有的人认识的朋友多，和他/她相联的边就比较多，有的人认识的朋友少，和他/她相联的边就少。中心性可以认为对应于人在这一社交网络中的名声/重要程度。很容易可以想到，一个人认识越多的人，他的名声就越大，这个人就越重要。然而，有时候，一个人虽然认识的人多，但这些人都是些不重要的人，那么这个人也未必有名气；若一个人认识的人少，但是这些人都是有名气、很重要的人物，那么这个人必然也是一个很重要的人。抽象来说，一个结点相联的多少固然重要，然而与之相联的结点是否重要也是中心性的一个有意义的考虑因素。

还有一个方面。仍然以社交网络为例。假若一个人认识了一个有名气的大人物，这会一定程度上给他/她的重要度加分，然而，加多少分，还要取决于他/她和这个大人物之间的关系如何，越是亲密的关系，加分就越多。若是很弱的关系，那恐怕加分就很小了。抽象来说，还需要考虑结点和结点之间的边权对中心性的作用。

小结一下，若想在一个图中寻找结点的重要程度，即中心性，则需要考虑三个因素：结点度，与此结点相连接的结点，结点之间的边权。结点度越高，结点就越重要；与此结点相连接的结点越重要，此结点就越重要；结点之间的边权越高，则相邻结点的重要程度对此结点的影响就越大。使用马尔可夫链模型来对 建模。4.2.2，4.2.3，4.2.4将介绍马尔可夫链模型，并说明马尔可夫链模型是如何满足上述的三点要求的。

 

4.2.2马尔可夫链模型（Markov Chain Model）

令stochastic矩阵X表示一个马尔可夫链的转移矩阵。所有stochastic矩阵的行的和必须等于1。 表示在这马尔可夫链中从状态 转移到状态 的转移概率。 表示从状态 经过n步转移到状态 的概率。对应于stochastic矩阵X的马尔可夫链收敛于一个固定分布：

 

 

 

其中I=(1,1,...,1)，称向量r为马尔可夫链的固定分布。

固定分布的一个直观解释是随机行走。假设有随机行走者在马尔可夫链图上沿着链接随机的走。在每个结点上，他可能随机的沿着不同的路走，不同的路有不同的概率。一直一直地在图上跳转。若这个图的转移矩阵满足马尔可夫链要求的话，则可以证明无论这个人从哪里开始，他最后停留在每个结点上的概率是恒定的。直观上来看，随机行走的收敛性说明了各个结点的overall centrality是由图本身的结构决定的，而与初始点无关。

向量 的每一个元素可以被认为是，随机行走最后会停在这个结点上的极限概率，不管初始状态是什么。

这里讨论马尔可夫链的收敛性。如果马尔可夫链中的任何结点都可以从其他结点转移到，则称此马尔可夫链是irreducible的，即对任意 ， ，存在 ，使得 。此外，如果马尔可夫链中的任意结点都可以转移至它子集，则称此马尔可夫链是aperiodic的，即对任意结点 ,存在 ，使得 。根据Perron-Frobenius定理（Seneta,1981），一个irreducible和aperiodic的马尔可夫链一定会收敛于一个唯一的固定分布。

直观地想，如果一个马尔可夫链有某部分是reducible或者periodic的话，则随机行走者可能会困在某个子图里，永远也无法访问图的其他的部分。所以irreducible和aperiodic是随机行走可以成行的必要条件。

下面给出收敛马尔可夫链的数学模型。

假设有一个图 ， 是结点集， 是边集。设 是图 的一个马尔可夫链的stochastic矩阵，且X满足irreducible和aperiodic。 表示图中结点总数。设 是随机行走在结点 的分布概率。 表示从 转移至 的转移概率。则有

 

 

 

其中 表示 的邻接结点集合。这个公式表明每个结点的分布概率是其邻接结点的分布概率与邻接边乘积之和。当随机行走收敛时，每个结点都将满足这个公式。

随机行走计算的矩阵表示是：

 

 

 

其中 是 维向量， 表示结点 的分布概率。这个公式意为固定分布再转移一次，固定分布不变，说明已收敛至稳定状态。

 

4.2.3类别建模

在这一节中，将结合马尔可夫链模型，对每个类别 的图 构造马尔可夫链。

令 表示 的转移矩阵，其 表示词项 和词项 的相关度如公式（2）所示。 可由文档-词项图矩阵 直接求得。希望经过对 进行变换，得到图 上的一个马尔可夫链的stochastic矩阵。

为了满足stochastic矩阵的要求，对 矩阵的每行进行归一化。令 表示 的每行归一化后的矩阵，则有：

 

 

 

则 k的每一行之和等于1。则 是 上的一个stochastic矩阵。所以，可以将这个问题看成是马尔可夫链。

令p表示词项图 的所有结点的分布概率向量。 是 维向量， 表示结点 的分布概率。则结点的分布概率关系是：

 

 

 

其中 表示结点 的分布概率， 是 的邻接结点集， 是结点 和结点 在归一化的转移矩阵 中的边权。

等价地，可以得到矩阵形式为：

 

 

 

然而，除了满足stochastic要求以外，还需要 满足irreducible和aperiodic的。为了解决这个问题，Larry Page建议给每个结点加一个小的跳转概率。这样随机行走者总有可能从孤立子图跳出到其他地方去，这样就使得这个图变成irreducible和aperiodic的了。如果赋予每一个结点同样的一个小的跳转概率，则将结点分布计算公式修改为如下形式：

 

 

 

其中 是图中的结点总数， 是一个衰减因子（damping factor），一般的选择分为是[0.1,0.2]。

相应的矩阵表示形式为

 

 

 

其中 是一个所有元素都为 的方阵。对应马克尔夫链的转移核心, ，是两个方阵 和 的结合。在此马尔可夫链上的随机行走者以 的概率选择跳转当前状态的邻接状态的其中一个，或者以概率 跳去图上的任何一个状态，包括当前的状态。由于此跳转，任何结点都可能到达任何其他结点，由此满足了irreducible和aperiodic的条件。由此，每个图 可以认为是一个马尔可夫链来进行计算。

马尔可夫链的收敛性使其可以用一种简单的迭代法计算各结点的固定概率，称这一方法为Power Method。这一方法初始令每个结点的概率分布值相等。在每次迭代中，将分布向量与随机矩阵相乘。只要随机矩阵是irreducible和aperiodic的，这样的随机矩阵保证最后的分布向量将收敛到一个固定概率分布。

 

 

摘自：文本分类中特征选择的理论分析和算法研究

其中不可约矩阵和非周期矩阵的介绍可以参见wiki上马尔科夫链词条。

http://zh.wikipedia.org/wiki/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE