在处理真实数据时，最大的问题主要是数据预处理。

匹配可能是许多分析师面临的最大挑战之一。例如，当我们谈论乔治·华盛顿和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模糊字符串匹配方法：

老实说，我选择这个数据是因为:

(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-IDFdef 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# 字符串匹配- KNNdef 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-IDFdef 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距离计算时间的比较。

结论

对于小数据，Levenshtein距离(fuzzy-wuzzy模块)是执行模糊字符串匹配的好选择。然而，随着数据大小的增长，计算时间也会增加。

另一种方法是使用TF-IDF结合k近邻和n-gram的NLP技术来查找匹配的字符串。FAISS和HSNW是其他的一些算法，可以用来提高寻找最近邻居的性能。

参考文献

[1] J. Han, M. Kamber, J. Pei. Data Mining: Concepts and Techniques (2012). Elsevier Inc.

[2] C. van den Berg. Super Fast String Matching in Python (2019). .

[3] E. Elahi. Fuzzy Matching 101: Cleaning and Linking Messy Data Across the Enterprise(2019). .

[4] A. Pearl. Fuzzy String Matching with TF-IDF (2019). .