Supongamos que tengo 2 vectores. ¿Qué algoritmos puedo usar para compararlos?

Question

La compañía 1 tiene este vector:

['books','video','photography','food','toothpaste','burgers'] ... ...

La empresa 2 tiene este vector:

['video','processor','photography','LCD','power supply', 'books'] ... ...

Supongamos que se trata de una distribución de frecuencia (podría convertirla en una tupla pero demasiado para escribir).
Como puedes ver ... estos vectores tienen cosas que se superponen. " video " y " fotografía " parece ser " similar " entre dos vectores debido al hecho de que están en posiciones similares. Y ... " libros " Obviamente es un punto fuerte para la empresa 1. El orden y el posicionamiento son importantes, ya que esta es una distribución de frecuencia.

¿Qué algoritmos podrías usar para jugar con esto? ¿Qué algoritmos podría usar que podrían proporcionar datos valiosos para estas compañías, utilizando estos vectores?

Soy nuevo en minería de texto y recuperación de información. ¿Alguien podría guiarme sobre esos temas en relación con esta pregunta?

Answer 1

La posición es muy importante, como usted enfatiza, entonces la métrica crucial se basará en la diferencia de posiciones entre los mismos elementos en los diferentes vectores (puede, por ejemplo, sumar los valores absolutos de las diferencias, o sus valores). cuadrícula). El gran problema que debe resolverse es cuánto pesa un elemento que está presente (digamos que es el N-ésimo) en un vector y completamente ausente en el otro. ¿Es un problema relativamente menor, como si el elemento faltante estuviera realmente presente justo después de los reales, por ejemplo, o un problema realmente muy importante? Eso es imposible de decir sin una mayor comprensión del área de aplicación real. ¡Puede probar varias formas de resolver este problema y ver qué resultados dan en casos de ejemplo que le interesan!

Por ejemplo, supongamos que " un elemento faltante es más o menos el mismo que si estuviera presente, justo después de los reales " ;. Luego, puede preprocesar cada vector de entrada en un elemento de asignación de dictado a posición (¡optimización crucial si tiene que comparar muchos pares de vectores de entrada!):

def makedict(avector):
  return dict((item, i) for i, item in enumerate(avector))

y luego, para comparar dos de estos dictados:

def comparedicts(d1, d2):
  allitems = set(d1) | set(d2)      
  distances = [d1.get(x, len(d1)) - d2.get(x, len(d2)) for x in allitems]
  return sum(d * d for d in distances)

(o, abs (d) en lugar de la cuadratura en la última declaración). Para hacer que los artículos que faltan pesen más (hacer que los dados, es decir, los vectores, se consideren más lejos), puede usar el doble de longitud en lugar de solo la longitud, o alguna constante grande como 100, en un programa estructurado de otra manera similar.

Answer 2

Le sugeriría un libro llamado Programming Collective Intelligence .
Es un libro muy bonito. sobre cómo puede recuperar información de datos simples como este. Hay ejemplos de código incluidos (en Python :)

Editar: Solo respondiendo a gbjbaanb: ¡Esto es Python!

a = ['books','video','photography','food','toothpaste','burgers']
b = ['video','processor','photography','LCD','power supply', 'books']
a = set(a)
b = set(b)

a.intersection(b)
    set(['photography', 'books', 'video'])

b.intersection(a)
    set(['photography', 'books', 'video'])

b.difference(a)
    set(['LCD', 'power supply', 'processor'])

a.difference(b)
    set(['food', 'toothpaste', 'burgers'])

Answer 3

Echa un vistazo a Distancia de Hamming

Answer 4

Como mencionó mbg, la distancia de Hamming es un buen comienzo. Básicamente, se está asignando una máscara de bits para cada elemento posible si está contenido en el valor de las empresas.

Por ej. la pasta dental es 1 para la compañía A, pero 0 para la compañía B. Luego cuenta los bits que difieren entre las compañías. El coeficiente de Jaccard está relacionado con esto.

La distancia de Hamming en realidad no podrá capturar similitud entre cosas como " video " y " fotografía " ;. Obviamente, una compañía que vende una vende la otra también con mayor probabilidad que una compañía que vende pasta dental.

Para esto, puedes usar cosas como LSI (también se usa para la reducción de dimensionalidad) o códigos factoriales (por ejemplo, cosas de redes neuronales como Máquinas de Boltzman Restringidas, Autoencodificadores o Minimización de Predictablidad) para obtener representaciones más compactas que luego puedes comparar usando Distancia euclidiana.

Answer 5

seleccione el rango de cada entrada (un rango más alto es mejor) y haga una suma de medias geométricas entre coincidencias

para dos vectores

sum(sqrt(vector_multiply(x,y)))  //multiply matches

La suma de rangos para cada valor sobre vector debe ser igual para cada vector (preferiblemente 1) De esa manera puedes hacer comparaciones entre más de 2 vectores.

Si aplicas el método de ikkebr puedes encontrar que a es similar a b

en ese caso solo usa

sum( b( b.intersection(a) ))

Answer 6

Puede utilizar el algoritmo set_intersection . Los 2 vectores deben ordenarse primero (usar orden de llamada), luego pasar 4 iteradores y obtendrá una colección con los elementos comunes insertados en ella. Hay algunos otros que operan de manera similar.