Cosinus similarité des vecteurs, avec <O (n^2) la complexité

Après avoir regardé autour de ce site pour des problèmes similaires, je trouve ceci: http://math.nist.gov/javanumerics/jama/ et ceci: http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html Cosinus similarité des vecteurs, avec <O (n^2) la complexité

, il semble toutefois ces exécutés dans O (n^2). J'ai fait quelques regroupements de documents et j'ai remarqué que ce niveau de complexité n'était pas réalisable lorsque l'on traitait même de petits ensembles de documents. Étant donné que pour le produit scalaire, nous avons seulement besoin des termes vectoriels contenus dans les deux vecteurs, il devrait être possible de placer les vecteurs dans un arbre et donc de calculer le produit scalaire avec n complexité n, où n est le plus petit nombre de termes uniques. 1 des 2 documents.

Ai-je raté quelque chose? Y a-t-il une bibliothèque Java qui fait cela?

grâce

Source

2010-07-27 Ash

Vous n'allez pas avoir beaucoup de chance d'attendre que les gens lisent ces deux pages. Peut-être pourriez-vous expliquer plus clairement votre problème - pourquoi multipliez-vous les vecteurs (et que voulez-vous dire, O (n^2)?) Le calcul du point-produit de deux vecteurs n-dimensionnels est trivialement O (n), le paquet de vecteur pourrait visser si mal) –

Il est le produit de point de calcul pour chaque * paire * de documents. Cela le rend quadratiquement complexe. – Rekin

BlueRaja - Danny Pflughoeft, ce problème concerne la multiplication de vecteurs de très grande dimension mais très clairsemés; et n n'est pas dimension mais compte des éléments non nuls. –

Si vous stockez les éléments vectoriels dans une table de hachage, la recherche est le journal ne n de toute façon, non? Boucle sur toutes les clés dans le document plus petit et voir si elles existent dans le plus grand ..?

Source

2010-07-27 18:13:05 Nicolas78

Toute classe que vous recommanderiez? Je pense que celui-ci est très bon, si la mémoire est un problème: http://www.java2s.com/Code/Java/Collections-Data-Structure/Amemoryefficienthashmap.htm – Ash

Wow ne peut pas juger cela si vite, mais vous pouvez toujours aller avec un java.util.HashMap normal pour commencer. Btw puisque vous dites que c'est un effet de la taille de collection de documents: Si vous comparez chaque document à chaque document, vous avez un autre terme quadratique (maintenant dans le nombre de documents) enroulé autour du terme (n * log n). Pour moi, cette partie a souvent été beaucoup plus problématique que le calcul de cosinus réel. Cela pourrait-il être le cas pour vous aussi? – Nicolas78

Je fais un découpage sur l'ensemble de grappes pour obtenir une comparaison à une constante, mais pour quelque chose comme GAHC vous avez complètement raison, vous avez un problème n^2, où n est le nombre de grappes à comparer. – Ash

Hashmap est bon, mais il peut prendre beaucoup de mémoire. Si vos vecteurs sont stockés sous forme de paires clé-valeur triées par clé, alors la multiplication vectorielle peut être effectuée en O (n): il suffit d'itérer en parallèle sur les deux vecteurs (la même itération est utilisée par exemple dans un algorithme de tri)). Le pseudo-code pour la multiplication:

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

Source

2010-07-27 19:22:05

J'aime cette idée, merci. Y at-il une bibliothèque Java qui utilise ce principe? – Ash

Je ne sais pas; mais lucene (http://lucene.apache.org/java/docs/index.html) pourrait contenir un tel algorithme. –

Merci dmitry-vk, il semble qu'une carte triée serait probablement la meilleure: http://java.sun.com/j2se/1.4.2/docs/api/java/util/SortedMap.html – Ash

Si vous ne souhaitez que recommander des articles limités, par exemple les articles m, à chaque élément dans un ensemble avec la taille de n, la complexité ne doit pas être n^2, mais m * n. Puisque m est une constante, la complexité est linéaire.

Vous pouvez vérifier avec le projet simbase https://github.com/guokr/simbase, il est une base de données nosql de similarité de vecteur.

Simbase ci-dessous utilisent les concepts:

Vector set: un ensemble de vecteurs
Base: la base de vecteurs, les vecteurs dans une série de vecteurs ont la même base
Recommandation: un binaire d'une direction relation entre deux ensembles de vecteurs qui ont la même base

Source

2014-06-12 15:14:53 Mountain

Si vous envisagez d'utiliser la similitude cosinus pour trouver des groupes de documents similaires, vous pouvez sider regardant dans locality-sensitive hashing, une approche basée sur le hachage qui a été conçu spécifiquement dans cet esprit. Intuitivement, LSH hache les vecteurs d'une manière qui, avec une probabilité élevée, place des éléments similaires dans le même compartiment et des éléments distants dans différents compartiments. Il existe des schémas LSH qui utilisent la similarité des cosinus comme distance sous-jacente. Ainsi, pour trouver des clusters, vous utilisez LSH pour déposer des objets dans des compartiments et calculer uniquement les distances par paires d'éléments dans le même compartiment. Dans le pire des cas, ce sera quadratique (si tout tombe dans le même panier), mais il est beaucoup plus probable que vous aurez une baisse significative du travail.

Espérons que cela aide!

Source

2014-06-12 17:21:41 templatetypedef

Cosinus similarité des vecteurs, avec <O (n^2) la complexité

Répondre

Questions connexes