作者 | Audhi Aprilliant

編譯 | VK
來源 | Towards Data Science

在處理真實數據時，最大的問題主要是數據預處理。

匹配可能是許多分析師面臨的最大挑戰之一。例如，當我們談論喬治·華盛頓和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:#?創建vectorizervectorizer?=?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:#?創建vectorizerclean?=?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):#?創建vectorizercategoryClean?=?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?=?colratCol?=?'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是其他的一些算法，可以用來提高尋找最近鄰居的性能。

參考文獻

[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). https://bergvca.github.io/2017/10/14/super-fast-string-matching.html.

[3] E. Elahi. Fuzzy Matching 101: Cleaning and Linking Messy Data Across the Enterprise(2019). https://dataladder.com/fuzzy-matching-101/.

[4] A. Pearl. Fuzzy String Matching with TF-IDF (2019). https://adrianpearl.github.io/fuzzystring.html.

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載機器學習的數學基礎專輯溫州大學《機器學習課程》視頻 本站qq群851320808，加入微信群請掃碼：

總結

以上是生活随笔為你收集整理的【NLP】基于TF-IDF和KNN的模糊字符串匹配优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。