TFIDF and KNN 执行模糊字符串匹配

对于大批量的模糊字符串匹配最简单和高效的方法就是通过 TFIDF 和KNN 来实现。

计算 TF-IDF

假设我们有两个数据集:

source_data: 一个具有 1000 万容量的字符串
match_data: 相对小型的数据集，需要从 source_data 中找到 match_data 的最近似的值

首先我们需要将这两个数据集转换为向量形式，因为所有的机器学习都是基于向量计算的。而 TF-IDF 就是非常好的向量化处理字符串的方式:

Python

from sklearn.feature_extraction.text import TfidfVectorizer

# 初始化 TF-IDF 向量化器
# 如果想要其他特殊需求可以传入参数，主要就是分词和预处理
vectorizer = TfidfVectorizer()
# 对于数据集需要 fit -> fit_transform
X = vectorizer.fit_transform(source_data)

# 对于 match 就不要 fit 了，而是使用训练数据集中的 token
Y = vectorizer.transform(match_data)

这样我们就讲字符串向量化，之后就能够执行计算了。

使用 KNN 查找相似项

Python

from sklearn.neighbors import NearestNeighbors

# 初始化 KNN 模型
# n_neighbors 表示获取几个相似项目，如果只需要最相似 1 即可
# 对于字符串最好的距离算法就是 cosine 因为他只关注角度，不关注距离，这样字符串的长短就不会特别影响结果
knn = NearestNeighbors(n_neighbors=5, metric='cosine')
# 传入训练数据集，注意所有的机器学习传入的都是向量而不是原始的字符串
knn.fit(X)

# 开始执行模糊查找
# 真正执行机器学习的地方
distances, indices = knn.kneighbors(Y, n_neighbors=1)

kneighbors 方法真正的开始执行训练，他的返回值是距离以及相似项的索引(针对于训练数据集)，因此如果我们想要获取相似结果以及相似度可以:

Python

# match_data[0] 的相似结果
source_data[indices[0][0]]

# match_data[0] 和 source_data[indices[0]] 的相似度
1 - distances[0][0]

Tips

距离最近也意味着最相似，相似度也最高。其中距离是 [-1, 1] 范围的值，因此需要 1 去减。

通常我们需要根据输入来获取最优解，此时可以通过:

Python

def find_similar_companies(query, n_results=5):
    query_vector = vectorizer.transform([query])
    distances, indices = knn.kneighbors(query_vector, n_neighbors=n_results)

    results = df.iloc[indices[0]]
    return results

# 测试模糊查找
query = '公司'
similar_companies = find_similar_companies(query)
print(similar_companies)

annoy 实现

使用annoy来实现 TF-IDF 和 KNN，它最大的好处就是能够获取一个相当于训练好的模型，在构建 annoy 是只需要知道原始数据集就好了:

Python

from annoy import AnnoyIndex

# 传入特征值，vectorizer.get_feature_name_out()
# X.shape[1] 也可以
# 第二个是距离算法, angular 就是余弦，可以测试下结果
annoy_index = AnnoyIndex(X.shape[1], 'angular')

# 遍历矩阵，将每一个行数据都添加到 Annoy 索引中
for i in range(X.shape[0]):
    # 注意 TfidfVectorizer 返回的是稀疏矩阵
    # annoy 只能使用密集矩阵，因此这样是它非常耗费内存的原因
    annoy_index.add_item(i, X[i].toarray()[0])

# 创建索引树，树数量越多越精确但是也越慢
annoy_index.build(10)

# 之后就可以查找近邻了
# 查询
query = '需要查找的字符串'
# 注意需要具有同样特征根的 TfidfVectorizer 来 transform 并转换为密集矩阵
query_vector = vectorizer.transform([query]).toarray()[0]# 转换查询为 TF-IDF 向量
n_neighbors = 5
nearest_neighbors = annoy_index.get_nns_by_vector(query_vector, n_neighbors)

# 可以通过 source_data[nearest_neighbors] 来获取最近邻
print("最近邻的索引:", nearest_neighbors)


# 还可以保存索引在下次使用
annoy_index.save('annoy_index.ann')

# 加载索引
loaded_index = AnnoyIndex(n_features, 'euclidean')
loaded_index.load('annoy_index.ann')  # 记得指定相同的距离度量

# 但是需要注意 tf-idf 需要相同的特征根因此还需要保存 vectorizer 对象,这可以通过 pickle 来实现

总结

KNN 算法本身并不是真正的机器训练模型，他无法实现训练后得到一个训练好的模型来快速获取近似值。因此他每一次的 kneighbors 操作都需要一个计算过程，因此他的速度尤其是在大规模数据集上的速度堪忧。