如何檢測重複數據？

Question

我有一個簡單的聯繫人數據庫，但我遇到了用戶輸入重複數據的問題。我已經實現了一個簡單的數據比較，但不幸的是，輸入的重複數據並不完全相同。例如，名字拼寫錯誤，或者一個人放入'Bill Smith'，另一個人放入'William Smith'替換同一個人。

那麼是否有某種算法可以給出一個條目與另一條條目類似的百分比？

Answer 1

雖然我沒有算法給你，但我的第一步是看看進入新聯繫人的過程。也許用戶沒有簡單的方法找到他們正在尋找的聯繫人。就像Stack Overflow的新問題表單一樣，您可以建議新聯繫人屏幕上已存在的聯繫人。

Answer 2

我想，這個問題很容易理解，但什麼發生，我一讀就是：

• 比較領域單獨
• 算那些匹配（用於匹配的可能是寬泛的定義是，並可能重領域不同）
• 目前人類干預，通過一些門檻

使用現有的數據庫，以獲得良好的第一猜測任何情況下，門檻，正確的積累經驗。

您可能更喜歡對誤報有相當強烈的偏見，至少在第一時間。

Answer 3

您可以將名稱與Levenshtein distance進行比較。如果名稱相同，則距離爲0，否則由將一個字符串轉換爲另一個字符串所需的最小操作數給出。

Answer 4

這可能是也可能不是相關的，但是一個Soundex search可能會檢測到較小的拼寫錯誤，例如，這可以讓您將Britney Spears，Britanny Spares和Britny Spears視爲重複項。

但是，暱稱收縮很難被認爲是重複的，我懷疑它是否明智。肯定會有多個人叫Bill Smith和William Smith，你必須用Charles-> Chuck，Robert-> Bob等來反覆說明。問題變得更加困難（例如，穆罕默德/穆罕默德被稱爲穆斯林太多）。

Answer 5

如果您有權訪問SSIS，請查看模糊分組和Fuzzy查找轉換。

http://www.sqlteam.com/article/using-fuzzy-lookup-transformations-in-sql-server-integration-services

http://msdn.microsoft.com/en-us/library/ms137786.aspx

Answer 6

我不知道它會爲名稱VS暱稱問題工作得很好，但在這類地區最常見的算法將是edit distance/Levenshtein distance算法。它基本上是將一個項目轉換爲另一個項目所需的字符更改，添加和刪除的數量。

對於名字，我不確定你是否會用純算法取得好成績 - 你真正需要的是大量的數據。舉例來說，Google拼寫建議比普通桌面應用程序的建議好得多。這是因爲Google可以處理數十億個網頁查詢，並查看導致彼此的查詢，你的意思是什麼「鏈接」實際上被點擊了。

有幾家公司專門研究名稱匹配問題國家安全和欺詐應用）。我記得的，搜索軟件美國似乎已被這些傢伙http://www.informatica.com/products_services/identity_resolution/Pages/index.aspx收買，但我懷疑這些解決方案對於聯繫人應用程序來說都是非常昂貴的。

Answer 7

如果您擁有一個包含字符串字段的大型數據庫，則可以使用simhash算法快速找到大量重複項。

Answer 8

那麼，有沒有某種算法 的，可以給一個條目如何 相似的是另一百分比？

算法作爲Soundex和編輯距離（如前一篇文章中所建議的）可以解決您的一些問題。但是，如果您認真清理數據，這還不夠。正如其他人所說的「比爾」聽起來不像「威廉」。

我發現的最佳解決方案是使用簡化算法和表來將名稱縮減爲根名。

到你的正常地址表，添加名字，e.g 人（名字，RootFirstName，姓氏，Rootsurname ....）的根版本

現在，創建一個映射表。 FirstNameMappings（主鍵名字，ROOTNAME）

通過填充你的映射表： 插入忽略（選擇名字，「未定義」從Person）到FirstNameMappings

這將增加你都firstnames在你的人表以及「UNDEFINED」的根名稱

現在，很遺憾，您將不得不查看所有獨特的名字並將它們映射到RootName。例如，「Bill」，「Billl」和「Will」應該全部翻譯成「William」 這非常耗時，但如果數據質量真的對你很重要，我認爲這是最好的方法之一。

現在使用新創建的映射表來更新Person表中的「Rootfirstname」字段。重複姓名和地址。完成此操作後，您應該能夠檢測重複內容而不會遭受拼寫錯誤。

Answer 9

你可能也想看看概率匹配。

Answer 10

FullContact.com有API可以幫你解決這個問題，請看他們的文檔：http://www.fullcontact.com/developer/docs/?category=name。

它們具有用於名稱標準化（Bill into William），名稱Deducer（用於原始文本）和名稱相似性（比較兩個名稱）的API。

目前所有的API都是免費的，它可能是一個很好的開始。