Вычислить сходство между двумя списками

Я хотел бы вычислить сходство между двумя списками разной длины.

eg:

listA = ['apple', 'orange', 'apple', 'apple', 'banana', 'orange'] # (length = 6)
listB = ['apple', 'orange', 'grapefruit', 'apple'] # (length = 4)

как видите, один и тот же элемент может появляться в списке несколько раз, а длина может быть разной.

Я уже думал о сравнении частоты каждого элемента, но это не распространяется на размер каждого списка (список, который просто в два раза больше другого списка, должен быть похожим, но не полностью похожим)

eg2:

listA = ['apple', 'apple', 'orange', 'orange']
listB = ['apple', 'orange']
similarity(listA, listB) # should NOT equal 1

Поэтому я в основном хочу охватить размер списков и распределение элементов в списке.

Любые идеи?


python set algorithm similarity
person kmace    schedule 06.02.2013    source источник
comment
Это списки, а не наборы.   -  person Martijn Pieters    schedule 06.02.2013
comment
Под similarity вы подразумеваете создание третьего списка, содержащего элементы, которые появляются как в списке A, так и в списке B? чтобы результат в вашем случае был ['apple', 'orange']?   -  person Konsol Labapen    schedule 06.02.2013
comment
под сходством я подразумеваю некоторую меру того, насколько они похожи. таким образом, сравнение двух идентичных наборов (или списка) даст вам 1 балл, а два совершенно непохожих набора дадут вам ноль. эти наборы, однако, отличаются по размеру и могут содержать повторяющиеся элементы   -  person kmace    schedule 06.02.2013

Ответы (3)


arrow_upward
27
arrow_downward

Возможно, используйте collections.Counter(); это мультимножества или пакеты, на языке типов данных:

from collections import Counter

counterA = Counter(listA)
counterB = Counter(listB)

Теперь вы можете сравнить их по записям или частотам:

>>> counterA
Counter({'apple': 3, 'orange': 2, 'banana': 1})
>>> counterB
Counter({'apple': 2, 'orange': 1, 'grapefruit': 1})
>>> counterA - counterB
Counter({'orange': 1, 'apple': 1, 'banana': 1})
>>> counterB - counterA
Counter({'grapefruit': 1})

Вы можете вычислить их косинусное сходство, используя:

import math

def counter_cosine_similarity(c1, c2):
    terms = set(c1).union(c2)
    dotprod = sum(c1.get(k, 0) * c2.get(k, 0) for k in terms)
    magA = math.sqrt(sum(c1.get(k, 0)**2 for k in terms))
    magB = math.sqrt(sum(c2.get(k, 0)**2 for k in terms))
    return dotprod / (magA * magB)

Который дает:

>>> counter_cosine_similarity(counterA, counterB)
0.8728715609439696

Чем ближе к 1 это значение, тем больше похожи два списка.

Косинусное сходство — это одна оценка, которую вы можете рассчитать. Если вам важна длина списка, вы можете вычислить другой; если вы сохраните эту оценку между 0,0 и 1,0, вы можете перемножить два значения для окончательной оценки между -1,0 и 1,0.

Например, чтобы учесть относительную длину, вы можете использовать:

def length_similarity(c1, c2):
    lenc1 = sum(c1.itervalues())
    lenc2 = sum(c2.itervalues())
    return min(lenc1, lenc2) / float(max(lenc1, lenc2))

а затем объединить в функцию, которая принимает списки в качестве входных данных:

def similarity_score(l1, l2):
    c1, c2 = Counter(l1), Counter(l2)
    return length_similarity(c1, c2) * counter_cosine_similarity(c1, c2)

Для ваших двух примеров списков это приводит к:

>>> similarity_score(['apple', 'orange', 'apple', 'apple', 'banana', 'orange'], ['apple', 'orange', 'grapefruit', 'apple'])
0.5819143739626463
>>> similarity_score(['apple', 'apple', 'orange', 'orange'], ['apple', 'orange'])
0.4999999999999999

При необходимости вы можете смешивать другие показатели.

person Martijn Pieters    schedule 06.02.2013
comment
это работает, но если мы посмотрим на пример, где список c1 представляет собой просто двойной счет c2, то сходство по-прежнему равно 1. так что это не совсем то, что я ищу. хотя спасибо за код. - person kmace; 06.02.2013
comment
@kamula: это отправная точка; если сходство cos равно 1, посмотрите, имеет ли один верхний счет больше, чем другой (.most_common(1) на любом), который нужно настроить, и т. д. - person Martijn Pieters; 06.02.2013
comment
Если вам не нужна нормализованная по длине оценка, которую обеспечивает косинусное расстояние, вы можете рассчитать евклидово расстояние между двумя списками. - person duhaime; 17.12.2014

arrow_upward
1
arrow_downward

С теоретической точки зрения: я рекомендую вам искать косинусное сходство http://en.wikipedia.org/wiki/Cosine_similarity

Возможно, вам придется изменить схему, чтобы она соответствовала вашей схеме, но идея сходства косинусов великолепна.

person Vigneshwaren    schedule 06.02.2013

arrow_upward
0
arrow_downward

Я считаю, что вы ищете подсчет количества инверсий в массиве. На вопрос есть ваш ответ: Подсчет инверсий в массиве

person Computernerd    schedule 06.02.2013
comment
Извините, но я не уверен, что понимаю, что вы имеете в виду. Как сравнение двух наборов может быть преобразовано в подсчет количества инверсий в реализации сортировки слиянием? - person kmace; 06.02.2013