coseno similitud de vectores, con <O (n^2) la complejidad

Question

Tras mirar alrededor de este sitio para problemas similares, encontré esto: http://math.nist.gov/javanumerics/jama/ y esto: http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html

Sin embargo, parece que estos se ejecutan en O (n^2). He estado haciendo algunos clústeres de documentos y me di cuenta de que este nivel de complejidad no era factible cuando se trataba incluso de conjuntos de documentos pequeños. Dado que, para el producto escalar, solo necesitamos los términos vectoriales contenidos en ambos vectores, debería ser posible poner los vectores en un árbol y así calcular el producto escalar con n log n complejidad, donde n es el número más bajo de términos únicos en 1 de los 2 documentos.

¿Echo de menos algo? ¿Hay una biblioteca de Java que hace esto?

gracias

Answer 1

Si almacena los elementos del vector en una tabla hash, búsqueda sólo se log n de todos modos, ¿no? Pasa el cursor por todas las teclas del documento más pequeño y observa si existen en el documento más grande ...

Answer 2

Hashmap es bueno, pero puede llevar mucha memoria.

Si sus vectores están almacenados como pares clave-valor ordenados por clave, la multiplicación vectorial se puede hacer en O (n): solo tiene que iterar en paralelo sobre ambos vectores (la misma iteración se usa, por ejemplo, en algoritmo de ordenación de fusión) El pseudocódigo para la multiplicación:

i = 0 
j = 0 
result = 0 
while i < length(vec1) && j < length(vec2): 
    if vec1[i].key == vec2[j].key: 
    result = result + vec1[i].value * vec2[j].value 
    else if vec1[i].key < vec2[j].key: 
    i = i + 1 
    else 
    j = j + 1 

Answer 3

Si sólo desea recomendar objetos limitados, para los artículos ejemplo, m, a cada elemento de un conjunto con el tamaño de n, la complejidad no tiene por qué ser n^2, pero m * norte. Como m es una constante, la complejidad es lineal.

Puede consultar con la base de datos del proyecto https://github.com/guokr/simbase, es una base de datos de semejanza vectorial nosql.

Simbase utilizar por debajo de conceptos:

• Conjunto de vectores: un conjunto de vectores
• Base: la base de vectores, los vectores en un conjunto de vectores tienen la misma base
• Recomendación: a una sola dirección binaria relación entre dos conjuntos de vectores que tienen la misma base

Answer 4

Si está planeando utilizar la similitud del coseno como una forma de encontrar grupos de documentos similares, puede convencer Mirando hacia el locality-sensitive hashing, un enfoque basado en hash que fue diseñado específicamente con esto en mente. Intuitivamente, LSH clasifica los vectores de forma tal que con alta probabilidad coloca elementos similares en el mismo cubo y elementos distantes en diferentes segmentos. Existen esquemas LSH que usan la similitud de coseno como su distancia subyacente, por lo que para buscar clústeres, use LSH para colocar cosas en cubos y luego solo calcule las distancias por pares de elementos en el mismo cubo. En el peor de los casos, esto será cuadrático (si todo cae en el mismo cubo), pero es mucho más probable que tenga una disminución significativa en el trabajo.

Espero que esto ayude!