每周学点大数据 | No.40单词共现矩阵应用

No.40期

单词共现矩阵应用

Mr. 王：这个算法的优势在于，它的 key 空间相比前面的词对要小得多，这意味着它能够更好地利用 combiner。

但是这种做法实现起来相对会困难一些，而且这个算法里面潜在的对象是非常大的。我们为每一个词申请的数组，是造成潜在对象非常大的首要原因。

下面我们看看如何进一步应用所求出来的单词共现矩阵。在自然语言处理中，我们经常需要通过共现矩阵求出两个单词间的相对频率。其表达式是这样的：

小可：这个 count(A,B) 就是词 A 和词 B 的共现计数吧？

Mr. 王：没错。现在需要思考的是，如何利用 MapReduce 来解决这个问题。首先来看看条带法。

对于条带法，我们只要使用共现矩阵关于 A 的那个数组就可以了。扫描一遍，就知道 A出现了多少次，在扫描第二遍时，就可以根据 count(A,B) 一一求出对于任意一个 B， f ( | B A)的值。

小可：那么对于词对法，又是怎么做的呢？

Mr. 王：对于词对法，要考虑的问题就比较多了。我们要对词 A 额外设计一个词对为（a,*）。

(a,*)这个量保存的是 a 出现的总频数，也就是 count(A)。为了完成上面的工作，我们在设计 MapReduce 时，要额外考虑以下几个方面。

Mapper 需要额外传递一个 (a,*) 用于求 count(a)，还要保证它必须先于其他所有的 (a,b) 先抵达 Reducer，这样计算才能有效地继续进行下去。

必须要保证所有的同一个词 a 都会传递给同一个 Reducer。

还要在涉及不同的 key-value 对的 Reducer 中保存相应的状态。

小可：各种方法在处理问题时还是各有利弊啊。

Mr. 王：在计算机科学中非常流行的一个词汇叫作 Trade-off。 Trade-off，简而言之，就是在有限的计算资源制约下，资源之间的互相置换和平衡。常见的例子有空间换时间和时间换空间等。

小可：都是怎么解释的呢？

Mr. 王：比如我们要解决一个问题，当希望利用较小的内存空间去解决时，就需要花费较多的时间；当希望节省时间时，可能就要占用较大的内存空间。我们要寻找一种时间和空间都能接受的方法，这个过程就是 Trade-off。

在 MapReduce 的设计中，也涉及很多 Trade-off 的问题。比如键值对的数量控制，创建对象的数量越多，开销就越大，同时也会对排序和洗牌的效率造成一些影响。

而如果减小键值对的数量，单个键值对的大小可能就会变得比较大，这意味着在传输过程中，同样会造成通信比较耗时的问题。

另外，对于本地聚合问题，也是很值得思考的。对于不同的问题， combiner的设计会产生很大的效率变化。当然，我们也可以尝试去设计 In-Mapper 和 combiner 共存的MapReduce 程序。

还有就是联系我们之前研究过的磁盘算法。

在算法执行过程中产生的大量中间结果，是存到内存中还是磁盘上，或者是在整个机架、机群的网络中传输，都会产生非常不同的效果，这是一个好的 MapReduce 使用者或者说程序员不得不深入考究的问题。

好了，今天听了这么多，你也很累了吧，我们的课就上到这里，下次再见。

小可：好的，王老师再见。