不乱于心,不困于情。
不畏将来,不念过往。如此,安好。

基于TF-IDF和KNN的模糊字符串匹配优化

在处理真实数据时,最大的问题主要是数据预处理。
匹配可能是许多分析师面临的最大挑战之一。例如,当我们谈论乔治·华盛顿和G·华盛顿时,当然,我们谈论的是一个人,即美国的第一任总统。幸运的是,研究人员已经开发出了概率数据匹配算法或众所周知的模糊匹配。
研究表明,94%的企业承认有重复的数据,而且这些重复的数据大部分是不完全匹配的,因此通常不会被发现

什么是模糊字符串匹配?

概率数据匹配,通常称为模糊字符串匹配,是一种算法或计算技术,用于寻找与模式近似(而不是精确)匹配的某些字符串。
概率数据匹配中的概率明确指示输出必须是概率(在0到1的范围内或相似度的百分比),而不是精确的数字。
有很多方法可以执行模糊字符串匹配,但是随着数据大小的增加,它们的性能会受到很大的影响,例如Levenshtein距离。原因是每个记录都要与数据中的所有其他记录进行比较。
随着数据大小的增加,执行模糊字符串匹配所花费的时间呈二次增长。这种现象被称为二次时间复杂度。二次时间复杂度表示一种算法,其性能与输入数据的平方大小成正比。
随着数据的增长,对速度的需求也在增长。

TF-IDF和KNN如何加速计算时间?

词频-逆文档频率(TF-IDF)是一种自然语言处理(NLP)技术,用于测量文档集合中一个单词对文档的重要性。
例如,从一个文档集合中,单词“flower”有多重要?TF-IDF值与单词出现的次数成比例增加(术语频率),但随着包含该单词的文档数量减少(与文档频率相反)。
IDF部分有助于解释这样一个事实,即某些词通常更常见(例如单词“The”没有任何信息)。
TF-IDF是使用n个字母组来实现的,这些字母组可能是由拼写错误或打字错误引起的。例如,independence这个词被分成以下形式,取决于n的个数。
1-gram
[‘independence’]
2-gram
[‘in’,’nd’,’de’,’ep’,’pe’,’en’,’nd’,’de’,’en’,’nc’,’ce’]
3-gram
[‘ind’,’nde’,’dep’,’epe’,’pen’,’end’,’nde’,’den’,’enc’,’nce’]
因此,n-gram是从用于字符串匹配的字符串列表中创建的。
TF-IDF背后的思想是,它将文档表示为数据,并且选择用k最近邻和余弦相似度,而不是Levenshtein距离(插入、删除或替换)匹配。
余弦相似度是一种相似性度量,可用于比较文档,或者根据给定的查询词向量给出文档的排序。x和y是两个比较的向量。用余弦度量作为相似函数,我们得到
之后,最匹配的候选数据将与主数据进行比较。它的目的是计算主数据中最匹配的候选字符串之间的相似度。

让我们来练习一下

对于本例,我将通过从Room Type Kaggle数据来演示TF-IDF模糊字符串匹配方法
https://www.kaggle.com/leandrodoze/room-type
老实说,我选择这个数据是因为:(1)数据非常小,只有103行,(2)列表示要比较的混乱字符串和主字符串。在实际情况中,这两种数据(杂乱的和干净的)可能来自不同的来源。
请先运行下面的命令,使用TF-IDF和KNN创建一个模糊字符串匹配函数。
# 导入数据操作模块
import pandas as pd
# 导入线性代数模块
import numpy as np
# 导入模糊字符串匹配模块
from fuzzywuzzy import fuzz, process
# 导入正则表达式模块
import re
# 导入迭代模块
import itertools
# 导入函数开发模块
from typing import Union, List, Tuple
# 导入TF-IDF模块
from sklearn.feature_extraction.text import TfidfVectorizer
# 导入余弦相似度模块
from sklearn.metrics.pairwise import cosine_similarity
# 导入KNN模块
from sklearn.neighbors import NearestNeighbors

# 字符串预处理
def preprocess_string(s):
# 去掉字符串之间的空格
s = re.sub(r'(?<=\b\w)\s*[ &]\s*(?=\w\b)’, ”, s)
return s

# 字符串匹配- TF-IDF
def build_vectorizer(
clean: pd.Series,
analyzer: str = ‘char’,
ngram_range: Tuple[int, int] = (1, 4),
n_neighbors: int = 1,
**kwargs
) -> Tuple:
# 创建vectorizer
vectorizer = TfidfVectorizer(analyzer = analyzer, ngram_range = ngram_range, **kwargs)
X = vectorizer.fit_transform(clean.values.astype(‘U’))

# 最近邻
nbrs = NearestNeighbors(n_neighbors = n_neighbors, metric = ‘cosine’).fit(X)
return vectorizer, nbrs

# 字符串匹配- KNN
def tfidf_nn(
messy,
clean,
n_neighbors = 1,
**kwargs
):
# 拟合干净的数据和转换凌乱的数据
vectorizer, nbrs = build_vectorizer(clean, n_neighbors = n_neighbors, **kwargs)
input_vec = vectorizer.transform(messy)

# 确定可能的最佳匹配
distances, indices = nbrs.kneighbors(input_vec, n_neighbors = n_neighbors)
nearest_values = np.array(clean)[indices]
return nearest_values, distances

# 字符串匹配-匹配模糊
def find_matches_fuzzy(
row,
match_candidates,
limit = 5
):
row_matches = process.extract(
row, dict(enumerate(match_candidates)),
scorer = fuzz.token_sort_ratio,
limit = limit
)
result = [(row, match[0], match[1]) for match in row_matches]
return result

# 字符串匹配- TF-IDF
def fuzzy_nn_match(
messy,
clean,
column,
col,
n_neighbors = 100,
limit = 5, **kwargs):
nearest_values, _ = tfidf_nn(messy, clean, n_neighbors, **kwargs)

results = [find_matches_fuzzy(row, nearest_values[i], limit) for i, row in enumerate(messy)]
df = pd.DataFrame(itertools.chain.from_iterable(results),
columns = [column, col, ‘Ratio’]
)
return df

# 字符串匹配-模糊
def fuzzy_tf_idf(
df: pd.DataFrame,
column: str,
clean: pd.Series,
mapping_df: pd.DataFrame,
col: str,
analyzer: str = ‘char’,
ngram_range: Tuple[int, int] = (1, 3)
) -> pd.Series:
# 创建vectorizer
clean = clean.drop_duplicates().reset_index(drop = True)
messy_prep = df[column].drop_duplicates().dropna().reset_index(drop = True).astype(str)
messy = messy_prep.apply(preprocess_string)
result = fuzzy_nn_match(messy = messy, clean = clean, column = column, col = col, n_neighbors = 1)
# 混乱到干净
return result

请将数据保存在特定的文件夹中,这样我们可以很容易的加载到jupyter上。
# 导入计时模块
import time

# 加载数据
df = pd.read_csv(‘room_type.csv’)

# 检查数据的维度
print(‘Dimension of data: {} rows and {} columns’.format(len(df), len(df.columns)))

# 打印前5行
df.head()图片

在这种情况下,Expedia将成为混乱的数据,而Booking.com将成为干净的主数据。为了清楚地理解,我将演示如何运行代码并显示结果。
# 运行模糊字符串匹配算法
start = time.time()
df_result = (df.pipe(fuzzy_tf_idf, # 函数和混乱的数据
column = ‘Expedia’, # 混乱数据列
clean = df[‘Booking.com’], # 主数据(列表)
mapping_df = df, # 主数据
col = ‘Result’) # 可以自定义
)
end = time.time()

# 打印计算时间
print(‘Fuzzy string matching in {} seconds’.format(end – start))

# 查看模糊字符串匹配的结果
df_result.head()

图片
该算法只需要0.050秒就可以将103行杂乱数据与103行主数据进行比较。
它可以在你自己的更大的数据上运行。但是当我们使用Levenshtein距离时,计算过程有多长?
我们必须进行比较,以确保TF-IDF和k -最近邻能够有效地提高计算时间。

与Levenshtein 距离的比较

对于本教程,我制作了一个与前一个函数具有类似输入和输出的函数(与TF-IDF和k近邻进行模糊字符串匹配)。
首先,运行以下代码来实现Levenshtein距离模糊字符串匹配。
# 导入数据操作模块
import pandas as pd
# 导入线性代数模块
import numpy as np
# 导入模糊字符串匹配模块
from fuzzywuzzy import fuzz, process
# 导入二分搜索模块

def stringMatching(
df: pd.DataFrame,
column: str,
clean: pd.Series,
mapping_df: pd.DataFrame,
col: str
):
# 创建vectorizer
categoryClean = clean.drop_duplicates().reset_index(drop = True)
categoryMessy = df[column].drop_duplicates().dropna().reset_index(drop = True).astype(str)

categoryFuzzy = {}
ratioFuzzy = {}
for i in range(len(categoryMessy)):
resultFuzzy = process.extractOne(categoryMessy[i].lower(), categoryClean)
# 映射
catFuzzy = {categoryMessy[i]:resultFuzzy[0]}
ratFuzzy = {categoryMessy[i]:resultFuzzy[1]}
# 保存结果
categoryFuzzy.update(catFuzzy)
#保存比率
ratioFuzzy.update(ratFuzzy)

# 创建列名
catCol = col
ratCol = ‘Ratio’
# 合并结果
df[catCol] = df[column]
df[ratCol] = df[column]
# 映射结果
df[catCol] = df[catCol].map(categoryFuzzy)
df[ratCol] = df[ratCol].map(ratioFuzzy)
return df

现在,是时候使用Levenshtein距离实现模糊字符串匹配算法了!
# 运行模糊字符串匹配算法
start = time.time()
df_result = (df.pipe(stringMatching, # 函数和混乱的数据
column = ‘Expedia’, # 混乱数据列
clean = df[‘Booking.com’], # 主数据
mapping_df = df, # 主数据
col = ‘Result’) # 可以自定义
)
end = time.time()

# 打印计算时间
print(‘Fuzzy string matching in {} seconds’.format(end – start))

# 查看模糊字符串匹配的结果
df_result.head()

与使用TF-IDF和KNN的模糊字符串匹配算法相比,Levenshtein距离需要1.216秒,长24.32倍。
需要注意的是,这个计算时间将随着数据的数量而增加。在这里了解更多关于TF-IDF和Levenshtein距离计算时间的比较。
https://medium.com/tim-black/fuzzy-string-matching-at-scale-41ae6ac452c2

结论

对于小数据,Levenshtein距离(fuzzy-wuzzy模块)是执行模糊字符串匹配的好选择。然而,随着数据大小的增长,计算时间也会增加。
另一种方法是使用TF-IDF结合k近邻和n-gram的NLP技术来查找匹配的字符串。FAISS和HSNW是其他的一些算法,可以用来提高寻找最近邻居的性能。
赞(0) 打赏
未经允许不得转载:seo优化_前端开发_渗透技术 » 基于TF-IDF和KNN的模糊字符串匹配优化

相关推荐

  • 暂无文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏