python - 计算 Pandas 数据框列组合之间距离的有效方法

Question

任务

我有一个 pandas 数据框，其中:

• 列是文档名称
• 行是那些文档中的单词
• 框架单元格内的数字是衡量单词相关性的指标(如果您想保持简单，则为单词计数)

我需要计算一个新的 doc1-doc 相似性矩阵，其中:

• 行和列是文档名称
• 框架内的单元格是两个文档之间的相似性度量(1 - 余弦距离)

余弦距离由 script.spatial.distance.cosine 方便地提供.

我目前正在这样做:

1. 使用 itertools 创建文档名称(数据框列名称)的所有 2 种组合的列表
2. 遍历这些并创建一个更新字典 {doc1: {doc2: similarity}}
3. 循环后，使用 pandas.DataFrame(dict) 创建一个新框架

问题

但这需要非常非常长的时间。以下显示了运行最新 anaconda python 3.5 的 MacBook Pro 13 的当前速度，配备 16GB 内存和 2.9GHz i5cpu ... 绘制针对文档组合所花费的时间。

您可以看到 100,000 个组合需要 1200 秒。将其外推到我的 7944 文档语料库，它创建了 31,549,596 组合，需要 5 天 来计算这个相似度矩阵!

有什么想法吗？

• 我 previously正在动态创建数据框 df.ix[doc1,doc2]= 相似性 .. 这非常非常慢。
• 我考虑过 numba @git 但它在 pandas 数据结构上失败了。
• 我找不到可以在内部(用 C 语言？)完成所有工作的内置函数
• 在战术上我必须做的是对文档进行随机抽样以创建一个更小的集合来处理......目前 0.02 的一小部分导致大约 20 分钟的计算!

这是代码(github)

docs_combinations = itertools.combinations(docs_sample, 2)
for doc1, doc2 in docs_combinations:
    # scipy cosine similarity function includes normalising the vectors but is a distance .. so we need to take it from 1.0
    doc_similarity_dict[doc2].update({doc1: 1.0 - scipy.spatial.distance.cosine(relevance_index[doc1],relevance_index[doc2])})
    pass

#convert dict to pandas dataframe
doc_similarity_matrix = pandas.DataFrame(doc_similarity_dict)

简单示例

@MaxU 要求提供一个说明性示例。

相关矩阵(这里是字数，只是为了简单起见):

...     doc1 doc2 doc3
wheel   2.   3.   0.
seat    2.   2.   0.
lights  0.   1.   1.
cake    0.   0.   5.

基于 2 种组合 (doc1, doc2), (doc2, doc3), (doc1, doc3) 计算的相似度矩阵

...     doc2 doc3
doc1    0.9449  0.
doc2    -       0.052

取左上角的值 0.889 .. 那是点积 (2*3 + 2*2 + 0 + 0) = 10 但由向量的长度归一化 ... 所以除以 sqrt(8) 和 sqrt (14) 给出 0.9449。您可以看到 doc1 和 doc3 之间没有相似性..点积为零。

将其从包含 4 个单词的 3 个文档扩展到 7944 个文档，这将创建 3 个1,549,596 组合...

Answer 1

这与我在不进入多处理 (bleh) 的情况下制作算法的效率差不多。该函数使用 numpy 数组进行所有计算。

def cos_sim(data_frame):
    # create a numpy array from the data frame
    a = data_frame.values
    # get the number of documents
    n = a.shape[-1]
    # create an array of size docs x docs to populate
    out = np.ravel(np.zeros(shape=(n, n)))

    for i in range(n):
        # roll the array one step at a time, calculating the cosine similarity each time
        r = np.roll(a, -i, axis=1)
        cs = np.sum(a[:,:n-i]*r[:,:n-i], axis=0) / (
                np.sqrt(np.sum(a[:,:n-i]*a[:,:n-i], axis=0))
                *np.sqrt(np.sum(r[:,:n-i]*r[:,:n-i], axis=0)))

        # push the cosine similarity to the output array's i-th off-diagonal
        out[i:n*n-i*n:n+1] = cs

    return out.reshape((n,n))