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

我有以下数据框：

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 and Beach属于簇号1而且他们的相似度得分相当高。所以我们将它与唯一的 id 关联起来，比如说1。下一个簇是数字2和三个实体来自name属于该簇的列：Dog, Big Dog and Cat. Dog and Big Dog具有很高的相似度分数，并且他们的唯一 ID 是，比如说2. For 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 we got id as 6但这很好，因为无论如何它都是独一无二的。

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

Also thefuzz模块有process函数，它允许立即处理数据：

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

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

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

帮助加快代码速度。

人们沮丧.iterrows()，称之为“慢”。

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

时间复杂度

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

        if different_cluster and not_yet_assigned:

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

>>> 419_776 ** 2 / 1e9
176.211890176

一千七百六十亿次迭代（带“B”） 没什么可打喷嚏的， 即使每个过滤步骤的成本微不足道（但非零）。

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

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

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

您没有指定典型的集群组大小 G。 但由于有许多不同的簇号， 我们肯定知道 G

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

你写了

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

把它变成

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

and use .iloc()检查相关行。

The while循环尽快终止 当看到新的簇号时， 每次都必须费力地通过数十万 行直到看到数据帧末尾。

为什么能够提前退出？ 由于排序顺序。

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

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

现在你的顶级代码可以迭代一堆 簇，执行成本 O(G^2) 的模糊匹配 在每个集群上。

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

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

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

请测量当前运行时间， 实施这些建议， 再次测量， 以及邮政编码+时间。