Расстояние Левенштейна для списка

Question

Я хочу разделить свой список слов на некоторое количество кластеров, используя расстояние Левенштейна.

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

Если у вас есть только строки, почему бы не использовать набор?

Target = set(Target_Column.tolist())

---

Вы также можете использовать значение по умолчанию набора для вашего отображения:

clusters = defaultdict(set)

Но это требует изменения list.append в set.add в вашей петле.

---

Существует, однако, более питонная альтернатива вашему коду.

Я бы, вероятно, сгенерировал бы сопоставление слов со множеством их связей на лету.

Вот пример, предполагая, 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