【NLP】基于TF-IDF和KNN的模糊字符串匹配優(yōu)化

編譯 | VK
來源 | Towards Data Science

研究表明，94%的企業(yè)承認(rèn)有重復(fù)的數(shù)據(jù)，而且這些重復(fù)的數(shù)據(jù)大部分是不完全匹配的，因此通常不會被發(fā)現(xiàn)

隨著數(shù)據(jù)的增長，對速度的需求也在增長。

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']

讓我們來練習(xí)一下

# 導(dǎo)入數(shù)據(jù)操作模塊
import pandas as pd
# 導(dǎo)入線性代數(shù)模塊
import numpy as np
# 導(dǎo)入模糊字符串匹配模塊
from fuzzywuzzy import fuzz, process
# 導(dǎo)入正則表達(dá)式模塊
import re
# 導(dǎo)入迭代模塊
import itertools
# 導(dǎo)入函數(shù)開發(fā)模塊
from typing import Union, List, Tuple
# 導(dǎo)入TF-IDF模塊
from sklearn.feature_extraction.text import TfidfVectorizer
# 導(dǎo)入余弦相似度模塊
from sklearn.metrics.pairwise import cosine_similarity
# 導(dǎo)入KNN模塊
from sklearn.neighbors import NearestNeighbors

# 字符串預(yù)處理
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:
    # 創(chuàng)建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
    ):
    # 擬合干凈的數(shù)據(jù)和轉(zhuǎn)換凌亂的數(shù)據(jù)
    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:
    # 創(chuàng)建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

# 導(dǎo)入計(jì)時(shí)模塊
import time

# 加載數(shù)據(jù)
df = pd.read_csv('room_type.csv')

# 檢查數(shù)據(jù)的維度
print('Dimension of data: {} rows and {} columns'.format(len(df), len(df.columns)))

# 打印前5行
df.head()

# 運(yùn)行模糊字符串匹配算法
start = time.time()
df_result = (df.pipe(fuzzy_tf_idf, # 函數(shù)和混亂的數(shù)據(jù)
                     column = 'Expedia', # 混亂數(shù)據(jù)列
                     clean = df['Booking.com'], # 主數(shù)據(jù)(列表)
                     mapping_df = df, # 主數(shù)據(jù)
                     col = 'Result') # 可以自定義
            )
end = time.time()

# 打印計(jì)算時(shí)間
print('Fuzzy string matching in {} seconds'.format(end - start))

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

# 導(dǎo)入數(shù)據(jù)操作模塊
import pandas as pd
# 導(dǎo)入線性代數(shù)模塊
import numpy as np
# 導(dǎo)入模糊字符串匹配模塊
from fuzzywuzzy import fuzz, process
# 導(dǎo)入二分搜索模塊

def stringMatching(
    df: pd.DataFrame,
    column: str,
    clean: pd.Series,
    mapping_df: pd.DataFrame,
    col: str
    ):
    # 創(chuàng)建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]}
        # 保存結(jié)果
        categoryFuzzy.update(catFuzzy)
        #保存比率
        ratioFuzzy.update(ratFuzzy)

    # 創(chuàng)建列名
    catCol = col
    ratCol = 'Ratio'
    # 合并結(jié)果
    df[catCol] = df[column]
    df[ratCol] = df[column]
    # 映射結(jié)果
    df[catCol] = df[catCol].map(categoryFuzzy)
    df[ratCol] = df[ratCol].map(ratioFuzzy)
    return df

# 運(yùn)行模糊字符串匹配算法
start = time.time()
df_result = (df.pipe(stringMatching, # 函數(shù)和混亂的數(shù)據(jù)
                     column = 'Expedia', # 混亂數(shù)據(jù)列
                     clean = df['Booking.com'], # 主數(shù)據(jù)
                     mapping_df = df, # 主數(shù)據(jù)
                     col = 'Result') # 可以自定義
            )
end = time.time()

# 打印計(jì)算時(shí)間
print('Fuzzy string matching in {} seconds'.format(end - start))

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