Python批次模糊匹配的3種方法範例

2022-03-01 10:00:37

前言

當然，基於排序的模糊匹配（類似於Excel的VLOOKUP函數的模糊匹配模式）也屬於模糊匹配的範疇，但那種過於簡單，不是本文討論的範疇。

本文主要討論的是以公司名稱或地址為主的字串的模糊匹配。

使用編輯距離演演算法進行模糊匹配

進行模糊匹配的基本思路就是，計算每個字串與目標字串的相似度，取相似度最高的字串作為與目標字串的模糊匹配結果。

對於計算字串之間的相似度，最常見的思路便是使用編輯距離演演算法。

下面我們有28條名稱需要從資料庫（390條資料）中找出最相似的名稱：

import pandas as pd

excel = pd.ExcelFile("所有客戶.xlsx")
data = excel.parse(0)
find = excel.parse(1)
display(data.head())
print(data.shape)
display(find.head())
print(find.shape)

編輯距離演演算法，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。允許的編輯操作包括將一個字元替換成另一個字元，插入一個字元，刪除一個字元。
一般來說，編輯距離越小，表示操作次數越少，兩個字串的相似度越大。

建立計算編輯距離的函數：

def minDistance(word1: str, word2: str):
    '編輯距離的計算函數'
    n = len(word1)
    m = len(word2)
    # 有一個字串為空串
    if n * m == 0:
        return n + m
    # DP 陣列
    D = [[0] * (m + 1) for _ in range(n + 1)]
    # 邊界狀態初始化
    for i in range(n + 1):
        D[i][0] = i
    for j in range(m + 1):
        D[0][j] = j
    # 計算所有 DP 值
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            left = D[i - 1][j] + 1
            down = D[i][j - 1] + 1
            left_down = D[i - 1][j - 1]
            if word1[i - 1] != word2[j - 1]:
                left_down += 1
            D[i][j] = min(left, down, left_down)
    return D[n][m]

關於上述程式碼的解析可參考力扣題解：https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/

遍歷每個被查詢的名稱，計算它與資料庫所有客戶名稱的編輯距離，並取編輯距離最小的客戶名稱：

result = []
for name in find.name.values:
    a = data.user.apply(lambda user: minDistance(user, name))
    user = data.user[a.argmin()]
    result.append(user)
find["result"] = result
find

測試後發現部分地址的效果不佳。

我們任取2個結果為信陽息縣淮河路店地址看看編輯距離最小的前10個地址和編輯距離：

a = data.user.apply(lambda user: minDistance(user, '河南美銳信陽息縣淮河路分店'))
a = a.nsmallest(10).reset_index()
a.columns = ["名稱", "編輯距離"]
a.名稱 = data.user[a.名稱].values
a

a = data.user.apply(lambda user: minDistance(user, '河南美銳信陽潢川四中分店'))
a = a.nsmallest(10).reset_index()
a.columns = ["名稱", "編輯距離"]
a.名稱 = data.user[a.名稱].values
a

可以看到，在前十個編輯距離最小的名稱中還是存在我們想要的結果。

使用fuzzywuzzy進行批次模糊匹配

通過上面的程式碼，我們已經基本瞭解了通過編輯距離演演算法進行批次模糊匹配的基本原理。不過自己編寫編輯距離演演算法的程式碼較為複雜，轉換為相似度進行分析也比較麻煩，如果已經有現成的輪子就不用自己寫了。

而fuzzywuzzy庫就是基於編輯距離演演算法開發的庫，而且將數值量化為相似度評分，會比我們寫的沒有針對性優化的演演算法效果要好很多，可以通過pip install FuzzyWuzzy來安裝。

對於fuzzywuzzy庫，主要包含fuzz模組和process模組，fuzz模組用於計算兩個字串之間的相似度，相當於對上面的程式碼的封裝和優化。而process模組則可以直接提取需要的結果。

fuzz模組

from fuzzywuzzy import fuzz

簡單匹配（Ratio）:

a = data.user.apply(lambda user: fuzz.ratio(user, '河南美銳信陽潢川四中分店'))
a = a.nlargest(10).reset_index()
a.columns = ["名稱", "相似度"]
a.名稱 = data.user[a.名稱].values
a

非完全匹配（Partial Ratio）:

a = data.user.apply(lambda user: fuzz.partial_ratio(user, '河南美銳信陽潢川四中分店'))
a = a.nlargest(10).reset_index()
a.columns = ["名稱", "相似度"]
a.名稱 = data.user[a.名稱].values
a

顯然fuzzywuzzy庫的 ratio()函數比前面自己寫的編輯距離演演算法，準確度高了很多。

process模組

process模組則是進一步的封裝，可以直接獲取相似度最高的值和相似度：

from fuzzywuzzy import process

extract提取多條資料：

users = data.user.to_list()
a = process.extract('河南美銳信陽潢川四中分店', users, limit=10)
a = pd.DataFrame(a, columns=["名稱", "相似度"])
a

從結果看，process模組似乎同時綜合了fuzz模組簡單匹配（Ratio）和非完全匹配（Partial Ratio）的結果。

當我們只需要返回一條資料時，使用extractOne會更加方便：

users = data.user.to_list()
find["result"] = find.name.apply(lambda x: process.extractOne(x, users)[0])
find

可以看到準確率相對前面自寫的編輯距離演演算法有了大幅度提升，但個別名稱匹配結果依然不佳。

檢視這兩個匹配不準確的地址：

process.extract('許灣鄉許灣村焦豔芳衛生室', users)

[('小寨溝村衛生室', 51),
('周口城鄉一體化焦豔芳一體化衛生室', 50),
('西華縣皮營鄉樓陳村衛生室', 42),
('葉縣鄧李鄉杜楊村第二衛生室', 40),
('湯陰縣瓦崗鄉龍虎村東衛生室', 40)]

process.extract('河南美銳信陽息縣淮河路分店', users)

[('信陽息縣淮河路店', 79),
('河南美銳大藥房連鎖有限公司息縣淮河路分店', 67),
('河南美銳大藥房連鎖有限公司息縣大河文錦分店', 53),
('河南美銳大藥房連鎖有限公司息縣千佛庵東路分店', 51),
('河南美銳大藥房連鎖有限公司息縣包信分店', 50)]

對於這樣的問題，個人並沒有一個很完美的解決方案，個人建議是將相似度最高的n個名稱都加入結果列表中，後期再人工篩選：

result = find.name.apply(lambda x: next(zip(*process.extract(x, users, limit=3)))).apply(pd.Series)
result.rename(columns=lambda i: f"匹配{i+1}", inplace=True)
result = pd.concat([find.drop(columns="result"), result], axis=1)
result

雖然可能有個別正確結果這5個都不是，但整體來說為人工篩查節省了大量時間。

整體程式碼

from fuzzywuzzy import process
import pandas as pd

excel = pd.ExcelFile("所有客戶.xlsx")
data = excel.parse(0)
find = excel.parse(1)
users = data.user.to_list()
result = find.name.apply(lambda x: next(
    zip(*process.extract(x, users, limit=3)))).apply(pd.Series)
result.rename(columns=lambda i: f"匹配{i+1}", inplace=True)
result = pd.concat([find, result], axis=1)
result

使用Gensim進行批次模糊匹配

Gensim簡介

Gensim支援包括TF-IDF，LSA，LDA，和word2vec在內的多種主題模型演演算法，支援流式訓練，並提供了諸如相似度計算，資訊檢索等一些常用任務的API介面。

基本概念：

語料（Corpus）：一組原始文字的集合，用於無監督地訓練文字主題的隱層結構。語料中不需要人工標註的附加資訊。在Gensim中，Corpus通常是一個可迭代的物件（比如列表）。每一次迭代返回一個可用於表達文字物件的稀疏向量。
向量（Vector）：由一組文字特徵構成的列表。是一段文字在Gensim中的內部表達。
稀疏向量（SparseVector）：可以略去向量中多餘的0元素。此時，向量中的每一個元素是一個(key, value)的元組
模型（Model）：是一個抽象的術語。定義了兩個向量空間的變換（即從文字的一種向量表達變換為另一種向量表達）。

安裝：pip install gensim

官網：https://radimrehurek.com/gensim/

什麼情況下需要使用NLP來進行批次模糊匹配呢？那就是資料庫資料過於龐大時，例如達到幾萬級別：

import pandas as pd

data = pd.read_csv("所有客戶.csv", encoding="gbk")
find = pd.read_csv("被查詢的客戶.csv", encoding="gbk")
display(data.head())
print(data.shape)
display(find.head())
print(find.shape)

此時如果依然用編輯距離或fuzzywuzzy暴力遍歷計算，預計1小時也無法計算出結果，但使用NLP神器Gensim僅需幾秒鐘，即可計算出結果。

使用詞袋模型直接進行批次相似度匹配

首先，我們需要先對原始的文字進行分詞，得到每一篇名稱的特徵列表：

import jieba

data_split_word = data.user.apply(jieba.lcut)
data_split_word.head(10)

0 [珠海, 廣藥, 康鳴, 醫藥, 有限公司]
1 [深圳市, 寶安區, 中心醫院]
2 [中山, 火炬, 開發區, 伴康, 藥店]
3 [中山市, 同方, 醫藥, 有限公司]
4 [廣州市, 天河區, 元崗金, 健民, 醫藥, 店]
5 [廣州市, 天河區, 元崗居, 健堂, 藥房]
6 [廣州市, 天河區, 元崗潤佰, 藥店]
7 [廣州市, 天河區, 元崗, 協心, 藥房]
8 [廣州市, 天河區, 元崗, 心怡, 藥店]
9 [廣州市, 天河區, 元崗永亨堂, 藥店]
Name: user, dtype: object

接下來，建立語料特徵的索引字典，並將文字特徵的原始表達轉化成詞袋模型對應的稀疏向量的表達：

from gensim import corpora

dictionary = corpora.Dictionary(data_split_word.values)
data_corpus = data_split_word.apply(dictionary.doc2bow)
data_corpus.head()

0 [(0, 1), (1, 1), (2, 1), (3, 1), (4, 1)]
1 [(5, 1), (6, 1), (7, 1)]
2 [(8, 1), (9, 1), (10, 1), (11, 1), (12, 1)]
3 [(0, 1), (3, 1), (13, 1), (14, 1)]
4 [(0, 1), (15, 1), (16, 1), (17, 1), (18, 1), (...
Name: user, dtype: object

這樣得到了每一個名稱對應的稀疏向量（這裡是bow向量），向量的每一個元素代表了一個詞在這個名稱中出現的次數。

至此我們就可以構建相似度矩陣：

from gensim import similarities

index = similarities.SparseMatrixSimilarity(data_corpus.values, num_features=len(dictionary))

再對被查詢的名稱作相同的處理，即可進行相似度批次匹配：

find_corpus = find.name.apply(jieba.lcut).apply(dictionary.doc2bow)
sim = index[find_corpus]
find["result"] = data.user[sim.argmax(axis=1)].values
find.head(30)

可以看到該模型計算速度非常快，準確率似乎整體上比fuzzywuzzy更高，但fuzzywuzzy對河南美銳大藥房連鎖有限公司308廠分店的匹配結果是正確的。

使用TF-IDF主題向量變換後進行批次相似度匹配

之前我們使用的Corpus都是詞頻向量的稀疏矩陣，現在將其轉換為TF-IDF模型後再構建相似度矩陣：

from gensim import models

tfidf = models.TfidfModel(data_corpus.to_list())
index = similarities.SparseMatrixSimilarity(
    tfidf[data_corpus], num_features=len(dictionary))

被查詢的名稱也作相同的處理：

sim = index[tfidf[find_corpus]]
find["result"] = data.user[sim.argmax(axis=1)].values
find.head(30)

可以看到許灣鄉許灣村焦豔芳衛生室匹配正確了，但河南美銳信陽息縣淮河路分店又匹配錯誤了，這是因為在TF-IDF模型中，由於美銳在很多條資料中都出現被降權。

假如只對資料庫做TF-IDF轉換，被查詢的名稱只使用詞頻向量，匹配效果又如何呢？

from gensim import models

tfidf = models.TfidfModel(data_corpus.to_list())
index = similarities.SparseMatrixSimilarity(
    tfidf[data_corpus], num_features=len(dictionary))
sim = index[find_corpus]
find["result"] = data.user[sim.argmax(axis=1)].values
find.head(30)

可以看到除了資料庫本來不包含正確名稱的愛聯寶之林大藥房外還剩下河南美銳大藥房連鎖有限公司308廠分店匹配不正確。這是因為不能識別出308的語意等於三零八。如果這類資料較多，我們可以先將被查詢的資料統一由小寫數位轉換為大寫數位（保持與資料庫一致）後，再分詞處理：

trantab = str.maketrans("0123456789", "零一二三四五六七八九")
find_corpus = find.name.apply(lambda x: dictionary.doc2bow(jieba.lcut(x.translate(trantab))))

sim = index[find_corpus]
find["result"] = data.user[sim.argmax(axis=1)].values
find.head(30)

經過這樣處理後，308廠分店也被正確匹配上了，其他類似的問題都可以使用該思路進行轉換。

雖然經過上面的處理，匹配準確率幾乎達到100%，但不代表其他型別的資料也會有如此高的準確率，還需根據資料的情況具體去分析轉換。並沒有一個很完美的批次模糊匹配的處理辦法，對於這類問題，我們不能完全信任程式匹配的結果，都需要人工的二次檢查，除非能夠接受一定的錯誤率。

為了我們人工篩選的方便，我們可以將前N個相似度最高的資料都儲存到結果中，這裡我們以三個為例：

同時獲取最大的3個結果

下面我們將相似度最高的3個值都新增到結果中：

result = []
for corpus in find_corpus.values:
    sim = pd.Series(index[corpus])
    result.append(data.user[sim.nlargest(3).index].values)
result = pd.DataFrame(result)
result.rename(columns=lambda i: f"匹配{i+1}", inplace=True)
result = pd.concat([find.drop(columns="result"), result], axis=1)
result.head(30)

完整程式碼

from gensim import corpora, similarities, models
import jieba
import pandas as pd

data = pd.read_csv("所有客戶.csv", encoding="gbk")
find = pd.read_csv("被查詢的客戶.csv", encoding="gbk")

data_split_word = data.user.apply(jieba.lcut)
dictionary = corpora.Dictionary(data_split_word.values)
data_corpus = data_split_word.apply(dictionary.doc2bow)
trantab = str.maketrans("0123456789", "零一二三四五六七八九")
find_corpus = find.name.apply(
    lambda x: dictionary.doc2bow(jieba.lcut(x.translate(trantab))))

tfidf = models.TfidfModel(data_corpus.to_list())
index = similarities.SparseMatrixSimilarity(
    tfidf[data_corpus], num_features=len(dictionary))

result = []
for corpus in find_corpus.values:
    sim = pd.Series(index[corpus])
    result.append(data.user[sim.nlargest(3).index].values)
result = pd.DataFrame(result)
result.rename(columns=lambda i: f"匹配{i+1}", inplace=True)
result = pd.concat([find, result], axis=1)
result.head(30)

總結

本文首先分享了編輯距離的概念，以及如何使用編輯距離進行相似度模糊匹配。然後介紹了基於該演演算法的輪子fuzzwuzzy，封裝的較好，使用起來也很方便，但是當資料庫量級達到萬條以上時，效率極度下降，特別是資料量達到10萬級別以上時，跑一整天也出不了結果。於是通過Gensim計算分詞後對應的tf-idf向量來計算相似度，計算時間由幾小時降低到幾秒，而且準確率也有了較大提升，能應對大部分批次相似度模糊匹配問題。

到此這篇關於Python批次模糊匹配的3種方法的文章就介紹到這了,更多相關Python批次模糊匹配內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！