在进行文本相似度评分时如何矢量化和加速 pandas 数据帧的双 for 循环

Question

我有以下数据框：

d_test = {
    'name' : ['South Beach', 'Dog', 'Bird', 'Ant', 'Big Dog', 'Beach', 'Dear', 'Cat'],
    'cluster_number' : [1, 2, 3, 3, 2, 1, 4, 2]
}
df_test = pd.DataFrame(d_test)

我想识别name列中相似的名称（如果这些名称属于一个簇编号）并为它们创建唯一的 ID。例如South Beach和Beach属于簇号1，它们的相似度得分相当高。所以我们将它与唯一的 id 关联起来，比如说1。下一个簇是数字2，列中的三个实体name属于该簇：Dog、Big Dog和Cat。Dog并且Big Dog具有很高的相似度分数，并且他们的唯一 ID 将是，比如说2。对于Cat唯一的 id 来说，是3。等等。

我为上面的逻辑创建了一个代码：

# pip install thefuzz
from thefuzz import fuzz

d_test = {
    'name' : ['South Beach', 'Dog', 'Bird', 'Ant', 'Big Dog', 'Beach', 'Dear', 'Cat'],
    'cluster_number' : [1, 2, 3, 3, 2, 1, 4, 2]
}

df_test = pd.DataFrame(d_test)

df_test['id'] = 0

i = 1
for index, row in df_test.iterrows():
    for index_, row_ in df_test.iterrows():
        if row['cluster_number'] == row_['cluster_number'] and row_['id'] == 0:
            if fuzz.ratio(row['name'], row_['name']) > 50:
                df_test.loc[index_,'id'] = int(i)
                is_i_used = True
    if is_i_used == True:
        i += 1
        is_i_used = False
                           

代码生成预期结果：

    name        cluster_number id
0   South Beach 1              1
1   Dog         2              2
2   Bird        3              3
3   Ant         3              4
4   Big Dog     2              2
5   Beach       1              1
6   Dear        4              5
7   Cat         2              6

请注意，因为Cat我们得到了idas6但没关系，因为无论如何它都是唯一的。

虽然上面的算法适用于测试数据，但我无法将其用于我拥有的真实数据（大约 100 万行），并且我试图了解如何矢量化代码并摆脱两个 for 循环。

thefuzz模块还具有process功能，它允许立即处理数据：

from thefuzz import process
out = process.extract("Beach", df_test['name'], limit=len(df_test))

但我不知道它是否有助于加快代码速度。

Answer 1

tl;dr：如果 N 很大，请避免 O(N^2) 运行时间。

\n

\n

帮助加快代码速度。

\n

\n

人们贬低它.iterrows()，称之为“慢”。

\n

从.iterrows矢量化方法切换到\n可能会在某种程度上“加快速度”，但这是一个相对的衡量标准。\n让我们谈谈复杂性。

\n

时间复杂度

\n

您当前的算法是二次的；\nit 具有一对嵌套.iterrows循环。\n但是我们立即过滤

\n

\n

        if different_cluster and not_yet_assigned:\n

\n

\n

现在，这对于“小”N 是可行的。\n但是 400K 的 N 很快就变得不可行：

\n

>>> 419_776 ** 2 / 1e9\n176.211890176\n

\n

一千七百六十亿次迭代（带有“B”）\n没什么值得你小瞧的，\n即使每个过滤步骤的成本微不足道（但非零）。

\n

冒着背诵之前\n已经重复过很多次的乏味事实的风险，

\n

\n
• 排序成本 O(N log N)，以及
\n
• N log N 远小于 N^2
\n

\n

我不相信你想要的是“走得快”。\n相反，我怀疑你真正想要的是“少做”。\n首先对你的行进行排序，然后\n大致线性地传递该行数据集。

\n

您没有指定典型的簇组大小 G。\n但是由于有许多不同的簇编号，\n我们肯定知道 G << N。\n我们可以将复杂性从 O(N^2) 降低到 O (N \xc3\x97 G^2)。

\n\n

df = df_test.sort_values([\'cluster_number\', \'name\'])\n

\n

你写了

\n

for index, row in df_test.iterrows():\n    for index_, row_ in df_test.iterrows():\n

\n

把它变成

\n

for index, row in df.iterrows():\n    while ...\n

\n

并使用.iloc()检查相关行。

\n

这while一旦看到新的簇号，循环就会终止，而不是每次都必须艰难地遍历数十万行，直到看到数据帧末尾

\n

为什么可以提前退出？\n由于排序顺序。

\n\n

构建此结构的更方便的方法可能是编写一个集群助手。

\n

def get_clusters(df):\n    cur_num = -1\n    cluster = []\n    for _, row in df.iterrows():\n        if row.cluster_number != cur_num and cluster:\n            yield cluster\n            cluster = []\n        cur_num = row.cluster_number\n        cluster.append(row)\n

\n

现在，您的顶级代码可以迭代一堆\n簇，对每个簇执行成本 O(G^2)\n 的模糊匹配。

\n

每个生成的簇的不变量是簇内的所有行都应具有相同的 cluster_number。

\n

并且，由于排序，我们保证给定的 cluster_number 最多生成一次。

\n\n

https://stackoverflow.com/help/self-answer

\n

请测量当前的运行时间，\n实施这些建议，\n再次测量，\n并发布代码+计时。

\n