detección similitud rápido

Question

Tengo una gran colección de objetos y necesito averiguar las similitudes entre ellos.

Para ser exactos: dados dos objetos que pueden calcular su diferencia como un número, un métricas - valores superiores significan menos similitud y 0 significa que los objetos tienen contenidos idénticos. El coste de calcular este número es proporcional al tamaño del objeto más pequeño (cada objeto tiene un tamaño dado).

Necesito la capacidad de encontrar rápidamente, dado un objeto, el conjunto de objetos similares a él.

Para ser exactos: Necesito para producir una estructura de datos que mapea cualquier objeto o para el conjunto de objetos no más disímiles a O que d, para un cierto valor de disimilitud d, de tal manera que una lista de los objetos en el conjunto no toma más tiempo que si estuvieran en una matriz o lista enlazada (y tal vez lo que realmente son). Por lo general, el conjunto será mucho menor que el número total de objetos, por lo que es realmente vale la pena realizar este cálculo. Es lo suficientemente bueno si la estructura de datos asume una d fijo, pero si funciona para un d arbitraria, incluso mejor.

¿Usted ha visto este problema antes, o algo similar a ella? ¿Qué es una buena solución?

Para ser exactos: una solución sencilla consiste en el cálculo de las diferencias entre todos los pares de objetos, pero esto es lento - O (n ² ) donde n es el número de objetos. ¿Hay una solución general con menor complejidad?

Answer 1

Sin conocer más detalles de la métrica, es difícil de decir. No tengo ninguna idea para la eliminación de la O (n ^ 2) aspecto, pero puede haber una manera de reducir algunas de las constantes involucradas. Por ejemplo, si has tenido una euclidiana métrica d (p, q) = sqrt ((p_1-q_1) ^ 2 + .. + (p_n-q_n) ^ 2), se puede cuadrar su distancia d y compararlo con el parcial sumas de (p_i-q_i) ^ 2 y se detendrá cuando se excede d ^ 2.

si en realidad esto le ahorrará tiempo depende de lo caro que la comparación es simplemente el cálculo de los sumandos y cómo muchos cálculos sumando las que cabe esperar de evitar al hacer esto (obviamente, cuanto más pequeño es d, mejor).

Answer 2

  

necesito para producir una estructura de datos   que los mapas de cualquier objeto o para el conjunto de   objetos no hay más disímiles a O de   d, para algún valor de disimilitud d.

Puede ser que sea más rápido para simplemente abandonar el cálculo similitud cuando el subtotal se vuelve mayor que d. Por ejemplo, si sus similitudes se basan en coseno o Distancia de Hausdorff esto puede hacerse fácilmente.

PS: si esto no se puede hacer, el problema podría estar relacionado con el k-vecinos más cercana problema (o más preciso un problema vecino más cercano con un barrio umbral). Debe buscar algoritmos que se encuentran cerca de los miembros sin calcular todas las distancias (tal vez algo usando la desigualdad del triángulo). Wikipedia debería ayudar a explorar los algoritmos adecuados.

Answer 3

Si su medida de similitud es transitivo, que no tienen que calcular la similitud de todos los pares de objetos ya que para objetos a, b, c:

similarity(a,c) = similarity(a,b) op similarity(b,c)

donde op es un operador binario, por ejemplo, multiplicación o adición.

Answer 4

Creo que la solución depende de muchos más detalles sobre la naturaleza de su problema.

1. ¿Es necesario encontrar los objetos similares para el mismo objeto varias veces, o sólo una vez? Si es muchas veces, y luego la creación de una estructura de datos en la que calcular la diferencia una vez para cada par y luego conectar objetos a objetos similares para que pueda recuperar la lista de forma rápida y sin recálculo podría ser una mejora de rendimiento de gran utilidad.

2. ¿Cuál es la naturaleza del cálculo? En un extremo, si la naturaleza de la diferencia es que se trata, por ejemplo, la diferencia de altura entre dos personas, a continuación, mantener la lista ordenada por la altura dejaría a encontrar los objetos similares con gran rapidez. Estoy asumiendo que el verdadero problema es más complicado que eso, pero siguiendo en esa lógica, si la diferencia es la suma de varias cantidades lineales, se puede crear una matriz multi-dimenstional, y entonces se puede imaginar conceptualmente el conjunto de objetos similares a las dentro de una esfera n-dimensional (es decir, círculo, esfera, hiperesfera, etc) centrada alrededor del objeto de referencia, y de nuevo encontrar directamente. En realidad, se me ocurre que si los cálculos de radio son demasiado complicados o toma demasiado tiempo de ejecución, una buena aproximación sería la creación de un cubo de n dimensiones (es decir, cuadrado, cubo, Tesseract, etc) alrededor del objeto de referencia, recuperar todos objetos que se encuentran dentro de ese cubo como "candidatos", y luego acaba de hacer el cálculo real de los candidatos.

Por ejemplo, supongamos que la "diferencia" es la suma de los valores absolutos de las diferencias de tres atributos, por ejemplo A1, A2 y A3. Se puede crear una matriz de 3 dimensiones y establecer el valor de cada nodo de la matriz en el objeto con esos valores, si los hay. Entonces, si usted quiere encontrar todos los objetos con una diferencia menor que d de objeto O, usted podría escribir:

for (x1=o.a1-d;x1<o.a1+d;++x1)
{
  for (x2=o.a2-d;x1<o.a2+d;++x2)
  {
    for (x3=o.a3-d;x1<o.a3+d;++x3)
    {
      if (array[x1][x2][x3]!=null
        && (abs(x1-o.a1)+abs(x2-o.a2)+abs(x3-o.a3)<=d)
        {
          ... found a match ...
        }
    }
  }
}

Sospecho que las reglas de diferencia son más complicado que eso, pero está bien, sólo tiene que añadir sofisticación a la alrorithm para que coincida con la complejidad de las reglas. El punto es utilizar la matriz para limitar el conjunto de objetos que hay que examinar.

3. Una vez más sobre la naturaleza del cálculo: Si uno de los elementos que componen la diferencia, o algún subconjunto pequeño, tiende a ser más importantes que otros, a continuación, crear una estructura de datos que le permite comparar rápidamente para esta dentro del alcance. Si está en rango, hacer el pleno comparar. Si no es así, que ni siquiera se mire.

Answer 5

¿No es posible utilizar un k D-árbol?

Puede ser necesario (si es posible) para normalizar las dimensiones. A continuación, sólo tiene que rellenar el árbol, y el uso de una búsqueda "más cercanos N vecinos", y tratar de encontrar cualquier objeto dentro de un rango.

Answer 6

Ejemplo de objetos: Imágenes, documentos. Por supuesto, el trabajo con la representación cruda de estos objetos no es sobre todo útil. por lo general uno pre-proceso de la forma cruda y convertirla en una forma normalizada (para los documentos, por ejemplo un vector para la cual cada entrada representa el número / porcentaje de veces que apareció una determinada palabra, para las imágenes que podría ser una representación de características visuales encontrado en la imagen).

si d es fijo y un n ^ 2 pre-cálculo es factible, sólo podría utilizar una representación gráfica utilizando una lista vinculada para cada objeto, por ejemplo. Puede tener soluciones más eficientes en la costa de la precisión utilizando algoritmos aproximados vecinos más próximos.

Answer 7

¿Podemos asumir que la similitud es transitiva, es decir. diff(a,c) == diff(a,b) + diff(b,c)? Si es así, puede intentar lo siguiente:

1. Ordenar la colección de objetos. Si la métrica de similitud objeto no tiene un valor absoluto decente, se puede seleccionar arbitrariamente un objeto como "cero" y ordenar todos los demás objetos por su similitud con ese objeto.
2. Para encontrar los objetos con s similitud con o, encontrar o en la lista ordenada, y la búsqueda hacia la izquierda y hacia la derecha hasta el diff crece más grande que s.

La ventaja de esto es que la clasificación puede hacerse una vez, y la posterior construcción de conjunto es proporcional al número de miembros que estarán en el conjunto.

Answer 8

Suena como BK-árbol. href="https://nullwords.wordpress.com/2013/03/13/the-bk-tree-a-data-structure-for-spell-checking/" He aquí una pequeña ejemplo . Es, básicamente, crea árbol y comprobar qué rama se debe utilizar para la búsqueda de un objeto similar y cuáles no, por lo que se evita O(n2)