Cálculo de la similitud de dos listas

Tengo dos listas:Cálculo de la similitud de dos listas

por ejemplo. a = [1,8,3,9,4,9,3,8,1,2,3] y b = [1,8,1,3,9,4,9,3,8, 1,2,3]

Ambos contienen enteros. No hay ningún significado detrás de las entradas (por ejemplo, 1 no está 'más cerca' de 3 que 8).

Estoy tratando de diseñar un algoritmo para calcular la similitud entre dos listas ORDERED. Ordenada es la palabra clave aquí (así que no puedo tomar el conjunto de ambas listas y calcular su porcentaje de diferencia de set_). A veces los números se repiten (por ejemplo 3, 8 y 9 arriba, y no puedo ignorar las repeticiones).

En el ejemplo anterior, la función a la que llamaría me diría que a y b son ~ 90% similares, por ejemplo. ¿Cómo puedo hacer eso? Editar distancia fue algo que vino a la mente. Sé cómo usarlo con cadenas, pero no estoy seguro de cómo usarlo con una lista de entradas. ¡Gracias!

Fuente

2011-07-15 aerain

Teniendo en cuenta una cadena a ser simplemente una lista de caracteres, no parece estar una asignación bastante simple entre calcular la distancia de edición en cadenas y calcular la distancia de edición en listas de enteros. – Chowlett

tal vez está buscando la [distancia de Hamming] (http://en.wikipedia.org/wiki/Hamming_distance)? –

@Pat B: la distancia de Hamming requiere que las secuencias tengan la misma longitud y no puede tratar con eliminaciones/inserciones. Eche un vistazo al ejemplo de OP ('a' y' b'). – NPE

Usted puede utilizar el módulo difflib relación

()
Return una medida de similitud de las secuencias como un flotador en el rango [0, 1].

cual da:

>>> s1=[1,8,3,9,4,9,3,8,1,2,3] 
>>> s2=[1,8,1,3,9,4,9,3,8,1,2,3] 
>>> sm=difflib.SequenceMatcher(None,s1,s2) 
>>> sm.ratio() 
0.9565217391304348

Fuente

2011-07-15 16:04:51 kraymer

único problema aquí sería que los espacios también terminan contando en la diferencia porcentual – aerain

Más razón por la que no desea utilizar este enfoque: esto castiga enteros de dos dígitos más que los de un solo dígito y algunas veces confundir números de dígitos simples y dobles (o más). – aerain

de hecho no (sobre los espacios) porque el SequenceMatcher es lo suficientemente inteligente como para detectar espacios como basura. – kraymer

Simplemente use el mismo algoritmo para calcular la distancia de edición en cadenas si los valores no tienen ningún significado particular.

Fuente

2011-07-15 15:49:30 jason

Parece que la distancia de edición (o Levenshtein) es precisamente la herramienta adecuada para el trabajo.

Aquí es una implementación de Python que se puede utilizar en las listas de números enteros: http://hetland.org/coding/python/levenshtein.py

El uso de ese código, levenshtein([1,8,3,9,4,9,3,8,1,2,3], [1,8,1,3,9,4,9,3,8,1,2,3]) vuelve 1, que es la distancia de edición.

Dada la distancia de edición y las longitudes de las dos matrices, calcular una métrica de "porcentaje de similitud" debería ser bastante trivial.

Fuente

2011-07-15 15:52:12 NPE

Yup funciona muy bien. ¡Gracias! ¿Para qué dividirías la distancia de edición para obtener el porcentaje? No estoy seguro de cuál de las listas para usar – aerain

en realidad recomendaría el enfoque del módulo difflib. No sabía que podría usarse para comparar la similitud de secuencia. – aerain

A menos que me falta el punto.

from __future__ import division 

def similar(x,y): 
    si = 0 
    for a,b in zip(x, y): 
     if a == b: 
      si += 1 
    return (si/len(x)) * 100 


if __name__ in '__main__': 
    a = [1,8,3,9,4,9,3,8,1,2,3] 
    b = [1,8,1,3,9,4,9,3,8,1,2,3] 
    result = similar(a,b) 
    if result is not None: 
     print "%s%s Similar!" % (result,'%')

Fuente

2011-07-15 16:04:45

Creo que el problema principal es que no puede tratar con eliminaciones/inserciones (considera que las dos secuencias en este ejemplo de PO son similares en un 18% mientras que espera ~ 90%). – NPE

@aix está aquí – aerain

Una forma de abordar este es utilizar histogram. A modo de ejemplo (manifestación con numpy):

In []: a= array([1,8,3,9,4,9,3,8,1,2,3]) 
In []: b= array([1,8,1,3,9,4,9,3,8,1,2,3]) 

In []: a_c, _= histogram(a, arange(9)+ 1) 
In []: a_c 
Out[]: array([2, 1, 3, 1, 0, 0, 0, 4]) 

In []: b_c, _= histogram(b, arange(9)+ 1) 
In []: b_c 
Out[]: array([3, 1, 3, 1, 0, 0, 0, 4]) 

In []: (a_c- b_c).sum() 
Out[]: -1

Existen ahora plétora de formas de aprovechar a_c y b_c.

Cuando la (aparentemente) más simple medida de similitud es:

In []: 1- abs(-1/ 9.) 
Out[]: 0.8888888888888888

seguido de:

In []: norm(a_c)/ norm(b_c) 
Out[]: 0.92796072713833688

In []: a_n= (a_c/ norm(a_c))[:, None] 
In []: 1- norm(b_c- dot(dot(a_n, a_n.T), b_c))/ norm(b_c) 
Out[]: 0.84445724579043624

Por lo tanto, tiene que ser mucho más específico a encuentre la medida de similitud más adecuada para sus propósitos.

Fuente

2011-07-15 16:25:54 eat

He implementado algo para una tarea similar hace mucho tiempo. Ahora, solo tengo a blog entry for that. Era simple: tenía que calcular el pdf de ambas secuencias y luego encontraría el área común cubierta por la representación gráfica de pdf.

Disculpe las imágenes rotas en el enlace, el servidor externo que he usado en ese momento está muerto.

En este momento, para su problema el código se traduce en

def overlap(pdf1, pdf2): 
    s = 0 
    for k in pdf1: 
     if pdf2.has_key(k): 
      s += min(pdf1[k], pdf2[k]) 
    return s 

def pdf(l): 
    d = {} 
    s = 0.0 
    for i in l: 
     s += i 
     if d.has_key(i): 
      d[i] += 1 
     else: 
      d[i] = 1 
    for k in d: 
     d[k] /= s 
    return d 

def solve(): 
    a = [1, 8, 3, 9, 4, 9, 3, 8, 1, 2, 3] 
    b = [1, 8, 1, 3, 9, 4, 9, 3, 8, 1, 2, 3] 
    pdf_a = pdf(a) 
    pdf_b = pdf(b) 
    print pdf_a 
    print pdf_b 
    print overlap(pdf_a, pdf_b) 
    print overlap(pdf_b, pdf_a) 

if __name__ == '__main__': 
    solve()

Por desgracia, da una respuesta inesperada, sólo se 0.212292609351

Fuente

2011-07-15 17:06:45

Cálculo de la similitud de dos listas

Respuesta

Cuestiones relacionadas