使用numpy计算文本文档之间的Kullback-Leibler (KL)距离

Question

我的目标是计算以下文本文档之间的KL距离：

1)The boy is having a lad relationship
2)The boy is having a boy relationship
3)It is a lovely day in NY

我首先对文件进行了向量化处理，以便更轻松地应用numpy。

1)[1,1,1,1,1,1,1]
2)[1,2,1,1,1,2,1]
3)[1,1,1,1,1,1,1]

我接着应用了以下代码来计算文本之间的KL距离：

import numpy as np
import math
from math import log

v=[[1,1,1,1,1,1,1],[1,2,1,1,1,2,1],[1,1,1,1,1,1,1]]
c=v[0]
def kl(p, q):
    p = np.asarray(p, dtype=np.float)
    q = np.asarray(q, dtype=np.float)
    return np.sum(np.where(p != 0,(p-q) * np.log10(p / q), 0))
for x in v:
    KL=kl(x,c)
    print KL

以下是上面代码的结果：[0.0, 0.602059991328, 0.0]。 第一段文本和第三段文本完全不同，但它们之间的距离为0，而高度相关的第一段文本和第二段文本却有一个距离为0.602059991328。这不准确。

有人知道我在KL方面做错了什么吗？感谢您的建议。

- Tiger1

---

好的，由于v[0]==v[2]，因此在kl函数中p-q为0，那么总和就是0。你所说的“向量化文档”是什么意思？你的向量1和3是相等的。 - J. Martinot-Lagarde

@J.Martinot_Lagarde 感谢您的观察。在这里向量化意味着对文档中每个单词进行频率计数，并使用这些值来表示文档。问题在于如何以这样的方式表示每个文档，以便可以使用KL准确地计算两个文档之间的距离。 - Tiger1

Answer 1

尽管我不太想再添加另一个答案，但这里有两个要点。首先，正如Jaime在评论中指出的那样，KL散度（或距离-根据以下文档，它们是相同的）旨在衡量概率分布之间的差异。这基本上意味着您传递给函数的应该是两个类似数组，每个数组的元素总和为1。

其次，scipy显然实现了这一点，并采用更与信息理论领域相关的命名方案。该函数名为“entropy”：

scipy.stats.entropy(pk, qk=None, base=None)

http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.stats.entropy.html

文档中指出：

若 qk 不为 None，则计算相对熵（也称为 Kullback-Leibler 差异或 Kullback-Leibler 距离） S = sum(pk * log(pk / qk), axis=0)。

此函数的额外好处是，如果传入的向量未归一化（即和不为1），它也会将其归一化（但这意味着您需要小心您从数据中构造的数组）。

希望这可以帮助您，并且至少有一个库提供它，因此您不必编写自己的代码。

- dpb

Answer 2

经过一番搜索了解KL概念后，我认为你的问题是由于向量化造成的：你正在比较不同单词出现次数。你应该将列索引链接到一个单词，或使用字典。

#  The boy is having a lad relationship It lovely day in NY
1)[1   1   1  1      1 1   1            0  0      0   0  0]
2)[1   2   1  1      1 0   1            0  0      0   0  0]
3)[0   0   1  0      1 0   0            1  1      1   1  1]

然后您可以使用kl函数。为了自动向字典矢量化，请参见如何计算列表中元素的频率？（collections.Counter正是您所需的）。然后，您可以循环遍历字典键的并集来计算KL距离。

- J. Martinot-Lagarde

---

那样行不通...根据wikipedia的说法："只有在P和Q都加起来等于1且如果Q(i)=0，则P(i)=0时，K-L散度才有定义。" 不过我不确定该怎么做。 - Jaime

没错。我发现最有用的文章是http://staff.science.uva.nl/~tsagias/?p=185。他们计算的是词汇交集而不是并集，并在词汇差异太大时添加了一个“解决方法”。最后还有代码。无论如何，问题在于这里的“向量化”部分。 - J. Martinot-Lagarde

谢谢@J.Martinot-Lagarde，我会看一下这篇文章。 - Tiger1

处理文档词汇差异的另一种方法是为每个单词添加一个小概率/频率，以便没有单词的概率为零。这在机器学习中相当标准，可能比忽略它们更好的想法（例如：如果两个文档有一个共同单词，但许多不同单词，则在考虑词汇交集时将它们视为相同！） - drevicko

@J.Martinot-Lagarde 实际上，如果您继续阅读链接的论文，您会发现他们没有使用交集，而是执行了我刚刚描述的操作。 - drevicko

链接已失效，现在我找到了一个缓存版本：https://web.archive.org/web/20130508191111/http://staff.science.uva.nl/~tsagias/?p=185 - Sadegh

Answer 3

你的KL问题可能在NP定义中存在。阅读维基百科页面以获取公式：http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence

请注意，你应该仅将(p-q)乘以对数结果，这符合KL公式。

 return np.sum(np.where(p != 0,(p) * np.log10(p / q), 0))

可能会有帮助...

- dpb

---

你那里的公式是非对称KL散度的。看一下对称KL散度，你会更好地理解我的意思。 - Tiger1

我理解对称KL的必要性，但我认为你所做的不会给你它。如果需要一个版本，请查看Jensen-Shannon分歧：http://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence - dpb

我已经准备好了Jensen-Shannon散度。我甚至在Stack Overflow上回答了一个关于JS散度的问题。除了JS散度之外，还有其他对称化版本的KL散度。 - Tiger1