Calcular la similitud entre dos listas.

Me gustaría calcular la similitud entre dos listas de varias longitudes.

p.ej:

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

Como puede ver, un solo elemento puede aparecer varias veces en una lista, y las longitudes son de diferentes tamaños.

Ya he pensado en comparar las frecuencias de cada elemento, pero eso no abarca el tamaño de cada lista (una lista que es simplemente el doble de otra lista debería ser similar, pero no perfectamente similar)

eg2:

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

Así que básicamente quiero abarcar el tamaño de las listas y la distribución de los elementos en la lista.

¿Algunas ideas?

Use collections.Counter() tal vez; esos son conjuntos múltiples, o bolsas, en lenguaje de datos:

 from collections import Counter counterA = Counter(listA) counterB = Counter(listB) 

Ahora puedes compararlos por entradas o frecuencias:

 >>> 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}) 

Puedes calcular su similitud de coseno usando:

 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) 

Lo que da:

 >>> counter_cosine_similarity(counterA, counterB) 0.8728715609439696 

Cuanto más cercano a 1 sea ese valor, más similares serán las dos listas.

La similitud del coseno es una puntuación que puedes calcular. Si te importa la longitud de la lista, puedes calcular otra; Si mantiene esa puntuación entre 0.0 y 1.0, también puede multiplicar los dos valores para obtener una puntuación final entre -1.0 y 1.0.

Por ejemplo, para tener en cuenta las longitudes relativas, podría usar:

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

y luego combinar en una función que toma las listas como entradas:

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

Para sus dos listas de ejemplo, eso resulta en:

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

Puede mezclar en otras métricas según sea necesario.

Desde un punto de vista teórico: te recomiendo que busques una similitud de coseno http://en.wikipedia.org/wiki/Cosine_similarity

Puede que tenga que modificar para que se ajuste a su esquema, pero la idea de la similitud de coseno es genial.

Creo que lo que está buscando es contar el número de inversiones en una matriz. La pregunta tiene su respuesta: contar inversiones en una matriz