前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每周学点大数据 | No.39单词共现矩阵计

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

作者头像
灯塔大数据
发布2018-04-04 17:16:47
2.3K0
发布2018-04-04 17:16:47
举报
文章被收录于专栏:灯塔大数据

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 的条带数组进行聚合,从而得出所需要的结果。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2017-05-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 灯塔大数据 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
NLP 服务
NLP 服务(Natural Language Process,NLP)深度整合了腾讯内部的 NLP 技术,提供多项智能文本处理和文本生成能力,包括词法分析、相似词召回、词相似度、句子相似度、文本润色、句子纠错、文本补全、句子生成等。满足各行业的文本智能需求。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档