データセット内の一貫性スコア付け

Question

構造化データのセットが与えられたとします。データには問題があることが知られており、何とか一貫性を保つためにそれらを「スコア付け」する必要があります。例えば、私は、以下に示すようなデータを持っている：だから組み合わせで比較的多くのデータが第3行目のレコードと比較してあるので、最初の行が正しいエントリであると考えられると仮定

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

。 2行目では、fieldAの値はfooである必要があります（スペルが間違っているため一致しません）。次に、3番目の行でfieldCの値は、（foo）とfieldB（bar）の同様の値を持つデータセット内の他の項目と同様に、bazになるはずです。

また、データセットの他の部分には、比較的一般的な別の組み合わせがあります（lorem,、dolor）。したがって、以下のレコードの問題は、前述のものと同じです。値の組み合わせが異なるだけです。

最初にすべてをSQLデータベースにダンプし、GROUP BYのステートメントを使用してフィールド値の一貫性をチェックしました。一貫性と各レコードのチェックを行うフィールドごとに1つのクエリがあります。レコードのfieldAの値が（以前のSQLクエリの処理結果）以下のオブジェクトにレコードを参照することにより、他の部分と一致している場合

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

それから私はチェックすることができます。それは非常に遅かったしかし

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

（データセットを約2.2millionレコードを持っている、と私はそう9milクエリについて作り、4つのフィールドをチェックしています）、および完了するまでに半日かかるだろう。その後、SQLストレージをelasticsearchに置き換え、処理時間を約5時間に短縮しました。

また好奇心の外に、私はここで車輪を発明していますか？これには既存のツールがありますか？現在は、elasticsearchを使用してPython3で実装されています。

Answer 1

私はちょうどあなたの質問を読んで、それはかなり興味深いとわかりました。私はntlk（python Natural Language Toolkit）を使って同様のことをしました。 とにかく、この場合、洗練されたstring comparison algorithmsは必要ありません。

私はPython difflibを使ってアプローチを試みました。タイトルは有望な音：difflib - コンピューティングデルタ¶

ためヘルパーdifflib.SequenceMatcherクラスは言う：

これは限りは、任意のタイプのシーケンスのペアを比較するための柔軟なクラスです。シーケンス要素はハッシュ可能です。

私は時間を節約したいと思うと、（比較的短い）文字列の2.000.000の3タプルをメモリに簡単に保持して処理できると思います。

私はdemo Appを書いて、ランダムに少しシャッフルされた文字列の3つのタプルを2.000.000（それを変えることができます）を作成しました。シャッフルされた文字列は、あなたのようなデフォルトパターン['foofoo'、 'bar'、 'lorem']と比較されます。次に、difflib.SequenceMatcherを使用してそれらを比較します。オールインメモリー。 - 時間比較：

2000年3タプル：ここ

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 

ランタイムとメモリ使用量の結果である：ここ

コンペアコードである417ミリ秒= 0417秒 - Mem Usage：594 KiB

200.000 3タプル： - 比較時間：5360 ms = 5,3秒 - メモリ使用量：58のMIB

2,000,000 3タプル： - 時間を比較：462241ミリ秒= 462秒 - メモリ使用量：580のMIB

だからそれは、時間とメモリ使用量に線形にスケーリングします。そしてそれは2.000.000の3タプルの文字列比較のために462秒必要です。あなたがパターンに比べて、文字列の類似性に基づいてスコアを得る見ることができるように（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)に変更しました。