數據集內的評分一致性

Question

假設我得到了一組結構化數據。數據已知是有問題的，我需要以某種方式「一致」地評分它們。例如，我有數據，如下圖所示：

fieldA | fieldB | fieldC 
-------+--------+------- 
foo | bar | baz 
fooo | bar | baz 
foo | bar | lorem 
..  | ..  | .. 
lorem | ipsum | dolor 
lorem | upsum | dolor 
lorem | ipsum | baz 

所以假設，因爲有在該組合相對更多的數據相比，第二排和第三排的記錄的第一行被認爲是正確的條目。在第二行中，fieldA的值應爲foo（由於拼寫錯誤而不一致）。然後在第三行中，fieldC的值應爲baz，因爲數據集中的其他條目具有fieldA（foo）和fieldB（bar）的相似值。

此外，在數據集的其他部分，還有另一種相對更常見的組合（lorem,ipsum,dolor）。因此，以下記錄中的問題與前面提到的相同，只是數值組合不同。

我最初將所有內容都轉儲到SQL數據庫，並使用GROUP BY的語句來檢查字段值的一致性。因此，對於每個我想檢查一致性以及每條記錄的字段，都會有一個查詢。

SELECT fieldA, count(fieldA) 
FROM  cache 
WHERE  fieldB = 'bar' and fieldC = 'baz' 
GROUP BY fieldA 

然後，我可以檢查的記錄fieldA值是參照記錄以下（以前的SQL查詢的處理結果）的對象，其餘是一致的。

{'foo': {'consistency': 0.99, 'count': 99, 'total': 100} 
'fooo': {'consistency': 0.01, 'count': 1, 'total': 100}} 

不過它非常慢（數據集有220萬左右的記錄，而我檢查4個領域，所以作出有關9mil查詢），並會採取半天才能完成。然後我將SQL存儲換成了elasticsearch，處理時間縮短到5個小時左右，能否以某種方式更快？

也只是出於好奇，我在這裏重新發明了一個輪子？有沒有現成的工具？目前它是用Python3和elasticsearch實現的。

Answer 1

我剛剛閱讀你的問題，發現它很有趣。我使用ntlk（python Natural Language Toolkit）做了類似的事情。 無論如何，在這種情況下，我認爲你不需要複雜的string comparison algorithms。

所以我嘗試了一種使用python difflib的方法。標題聽起來前途：difflib - 助手計算增量¶

的difflib.SequenceMatcher類說：

這是比較對任何類型的序列的靈活類，只要序列元素是可散列的。

順便說一句，我認爲，如果你想節省時間，你可以容易地在內存中容納和處理2.000.000三元組（相對較短）的字符串。 （請參見下面的testruns和Mem Usage）

所以我寫了一個demo App，它產生了2.000.000（可以改變這種情況）隨機輕微混洗字符串的三元組。混洗後的字符串是基於並與您的默認模式進行比較：['foofoo'，'bar'，'lorem']。然後使用difflib.SequenceMatcher比較它們。全部在內存中。

下面是比較代碼：

def compare(intuple, pattern_list): 
    """ 
    compare two strings with difflib 
    intuple: in this case a n-tuple of strings 
    pattern_list: a given pattern list. 
    n-tuple and list must be of the same lenght. 

    return a dict (Ordered) with the tuple and the score 
    """ 
    d = collections.OrderedDict() 
    d["tuple"] = intuple 
    #d["pattern"] = pattern_list 
    scorelist = [] 
    for counter in range(0,len(pattern_list)): 
     score = difflib.SequenceMatcher(None,intuple[counter].lower(),pattern_list[counter].lower()).ratio() 
     scorelist.append(score) 
    d["score"] = scorelist 
    return d 

以下是運行時間和內存使用的結果：

2000 3元組： - 比較時間：417毫秒= 0417秒 - Mem使用：594 KiB

200.000三元組： - 比較時間：5360 ms = 5.3秒 - 內存使用：58 MIB

2.000.000 3元組： - 比較時間：462241毫秒= 462秒 - 內存使用：580 MIB

所以它縮放在時間和內存使用線性。它（僅）需要462秒，用於比較2.000.000個三元組字符串。

結果如下：（例如對於200.000行）

[ TIMIMG ] 
build    function took 53304.028034 ms 
[ TIMIMG ] 
compare_all   function took 462241.254807 ms 
[ INFO ] 

num rows: 2000000 
pattern: ['foofoo', 'bar', 'lorem'] 
[ SHOWING 10 random results ] 
0: {"tuple": ["foofoo", "bar", "ewrem"], "score": [1.0, 1.0, 0.6]} 
1: {"tuple": ["hoofoo", "kar", "lorem"], "score": [0.8333333333333334, 0.6666666666666666, 1.0]} 
2: {"tuple": ["imofoo", "bar", "lorem"], "score": [0.6666666666666666, 1.0, 1.0]} 
3: {"tuple": ["foofoo", "bar", "lorem"], "score": [1.0, 1.0, 1.0]} 
.... 

正如你可以看到你得到基於比較模式字符串的相似性的得分。 1.0表示平等，下面的所有數據越差，得分越低。

difflib被稱爲不是最快的算法，但我認爲7分鐘相當於半天或5小時的改善。

我希望這可以幫助你（而不是完全的誤解），但昨天編程這很有趣。我學到了很多。 ;） 例如使用tracemalloc來跟蹤內存使用情況。從來沒有這樣做過。

我將代碼丟棄到github (as a one file gist)。