Levenshteinリストの距離

Question

Levenshtein Distanceを使用して単語リストをいくつかのクラスターに分割したいと考えています。

data = pd.read_csv("data.csv") 
Target_Column = data["words"] 
Target = Target_Column.tolist() 
clusters = defaultdict(list) 
threshold =5 
numb = range(len(Target)) 

for i in numb: 
    for j in range(i+1, len(numb)): 
     if distance(Target[i],Target[j]) <= threshold: 
      clusters[i].append(Target[j]) 
      clusters[j].append(Target[i]) 

しかし、ループオーバーリストを実行しているうちに、いくつかのクラスタが繰り返されます。この問題をソートするのを手伝ってください

Answer 1

文字列しかない場合は、セットを使用しないでください。

clusters = defaultdict(set) 

しかし、これはあなたのループでset.addにlist.appendを変更する必要があります：あなたは、あなたのマッピングの設定のデフォルト値を使用することができます

Target = set(Target_Column.tolist()) 

---

。

---

ただし、あなたのコードの代わりにpythonicの代替があります。

私はおそらく言葉からその接続のセットへのマッピングをその場で生成します。ここで

はwordsを想定した例であるすべての単語のset次のとおりです。

clusters = {w1: set(w2 for w2 in words if distance(w1, w2) <= threshold) for w1 in words} 

ライブ例：

：

>>> distance = lambda x, y: abs(len(x) - len(y)) 
>>> words = set("abc def abcd abcdefghijk abcdefghijklmnopqrstuv".split()) 
>>> threshold = 3 
>>> for cluster, values in clusters.items(): 
...  print cluster, ": ", ", ".join(values) 
... 
abcd : abcd, abc, def 
abc : abcd, abc, def 
abcdefghijk : abcdefghijk 
abcdefghijklmnopqrstuv : abcdefghijklmnopqrstuv 
def : abcd, abc, def 

がしきい値を増やすと、我々はすべての単語のための一つの大きな "クラスタ" を取得

>>> threshold = 100 
>>> clusters = {w1: set(w2 for w2 in words if distance(w1, w2) <= threshold) for w1 in words} 
>>> for cluster, values in clusters.items(): 
...  print cluster, ": ", ", ".join(values) 
... 
abcd : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def 
abc : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def 
abcdefghijk : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def 
abcdefghijklmnopqrstuv : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def 
def : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def