每周学点大数据 | No.39单词共现矩阵计

No.39期

单词共现矩阵计算

Mr. 王：这里还有一个很典型的例子——单词共现矩阵计算。

这个例子是计算文本集合中词的共现矩阵。我们设 M 是一个 N×N 的矩阵，其中 N 为词数，矩阵中的 Mij 表示 i 和 j 在同一个上下文中的次数。

小可：这个上下文是什么呢？

Mr. 王：上下文可以是一个句子，也可以是一个段落，这要视实际情况而定。

小可：那么单词共现矩阵计算有什么用呢？

Mr. 王：这是一种用来测量语义距离的方法。两个词出现在同一个句子中的次数越多，说明它们之间的语义距离就越近，它们之间的关联性也就越大。“语义距离”这个量，在很多的自然语言处理任务中发挥着很重要的作用。

这是一个典型的大规模计数问题，它具有大规模计数问题的几个主要特征。首先，它有一个大的事件空间（单词数目）；其次，它会产生大量的观测值（单词集合）。而我们的目标是记录有趣的关于事件的统计数据。

小可：具体应该怎么做呢？

Mr. 王：解决这类问题的一个基本方法，就是让 Mapper 来生成对多个文档的部分计数，Reducer 对部分计数进行聚合。

小可：这和前面我们使用的方法也是十分类似的。

Mr. 王：没错，但是现在我们面对的核心问题就是，如何高效地对部分计数进行聚合。我们首先可以想到的基本方法就是词对法。当 Mapper 处理一个句子时，生成这个句子里面的共现词对。

对于所有的词对， Mapper 会发出一个 (a,b) 为 key、计数为 value 的键值对， Reducer将这些来自 Mapper 的词对 + 计数键值对进行聚合，得出最终结果。下面是算法的伪代码。

不难看出，在 Mapper 中，对于任何一个词 w，将它所有的邻居 u 与之组成一个 pair(u,w)，于是每一个 (u,w) 都拥有计数 1，我们将 ((w,u),1) 这样的键值对发送出去。

在 Reducer 中，对于每一个 pair p 和来自 Mapper 的各种计数累和，最后返回 (p,count) 这样的键值对，就成功地实现了单子贡献矩阵计算。 小可：不过这样做的通信复杂度就会很大吧。

Mr. 王：没错，这种做法虽然易于实现，但其洗牌和排序的复杂度会非常大，效率真的很差。你想它的 key 都是一些词对，这意味着 key 的取值空间是非常大的。

小可：那么我们在 Mapper 后面加上一个 combiner 会不会好一些呢？

Mr. 王：增加 combiner 确实是一个比较常用的方法，但是在这个问题中， combiner 却很难发挥它的作用，原因还是 key 的空间过大。

key 用 (a,b) 这样的形式来表示，就意味着 (a,b)、 (a,c)等都不是相同的 key，本身在一个 Mapper 中，相同的键值对就非常少，可以进行聚集的键值对就不多。所以用 combiner 这种策略对于改进这个算法的效果不够好。

小可：那还有什么更有效的策略吗？

Mr. 王：这里介绍一种方法，叫作条带法。前面引起很大困难的原因是键值设计过于复杂，其空间太大导致了排序和洗牌的混乱。这次我们把 key 就设为单词。

原来，我们设定的词对是这样的：

(a,b) → 1 (a,b) → 2 (a,b) → 5 (a,b) → 3 (a,b) → 2

现在调整为： a → { b: 1, c:2, d: 5, e: 3, f: 2 }

我们记录与 a 共现的单词分别有哪些，它们出现的次数是多少，而不是记录共现对出现的次数。

小可：这样做， key 的取值空间就会大大减小。

Mr. 王：此时，当 Mapper 需要处理一个句子时，我们发出的键值对的形式就是：

word

a → {wordb:countb,wordc:countc, ...}

到了 Reducer 之中，我们再将上述的键值对进行合并：

但是这个问题的关键点在于，如何设计一个好的数据结构，让后面的 value 部分能够更容 易聚合。

我们可以设计这样一个数组，该数组将每一个词映射成一个数组下标，然后当某个词 u 出现在词 w 的上下文中时，我们将其对应的下标在 w 申领的数组中的位置中的计数值加 1。最后发出的是 (Term w,Array H) 这样的键值对。

接下来在 Reducer 中，我们将关于 term w 的条带数组进行聚合，从而得出所需要的结果。