Ayant regardé autour de ce site pour des questions similaires, j'ai trouvé ceci: http: //math.nist. GOV / Javanumerics / Jama / et ceci: http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html
Cependant, il semble que ceci est exécuté dans O (n ^ 2). J'ai fait du clustering de documents et j'ai remarqué que ce niveau de complexité n'était pas réalisable lorsqu'il s'agissait de petits ensembles de documents. Donnée, pour le produit DOT, nous n'avons besoin que des termes vectoriels contenus dans les deux vecteurs qu'il devrait être possible de mettre les vecteurs dans un arbre et de calculer ainsi le produit DOT avec N log n complexité, où n est le nombre le plus bas de termes uniques dans 1 des 2 documents.
Est-ce que je manque quelque chose? Y a-t-il une bibliothèque Java qui fait cela?
merci
4 Réponses :
Si vous stockez les éléments vectoriels dans une haquetable, la recherche n'est que logée de toute façon, non? Boucle sur toutes les clés dans le petit document et voir s'ils existent dans le plus grand ..?
Toute classe que vous recommanderiez? Je pense que celui-ci est plutôt bon, si la mémoire est un problème: java2s.com/code/java/collections-Data-tructure/.../a>
Wow ne peut pas le juger si vite, mais vous pouvez toujours aller avec un java normal.Util.Hashmap pour commencer. BTW Etant donné que vous dites que c'est un effet de la taille de la 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 * journal 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?
Je coupe le cluster réglé pour obtenir la comparaison sur une constante, mais pour quelque chose comme Gahc, vous êtes tout à fait correct, vous avez un problème N ^ 2, où n est le nombre de grappes à comparer.
hashmap est bon, mais cela peut prendre beaucoup de mémoire.
Si vos vecteurs sont stockés sous forme de paires de clés triés par touche, la multiplication de vecteur peut être effectuée dans O (n): vous devez simplement faire itérer dans Parallèlement sur les deux vecteurs (la même itération est utilisée, par exemple dans la fusion d'algorithme de tri). Le pseudocode pour la multiplication: P>
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
J'aime cette idée, merci. Y a-t-il une bibliothèque Java qui utilise ce principe?
Je ne sais pas; Mais Lucene ( 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: Java.sun.com/j2se/1.4.2/docs/aPi/java/util/sortedmap.html
Si vous souhaitez uniquement recommander des éléments limités, par exemple M articles, à chaque élément d'un ensemble avec la taille de N, la complexité n'a pas besoin d'ê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 Utilisez ci-dessous Concepts:
Si vous envisagez d'utiliser la similitude cosinoise comme moyen de trouver des grappes de documents similaires, vous voudrez peut-être envisager de regarder dans J'espère que cela vous aide!
Vous n'allez pas avoir beaucoup de chance en attendant que les gens lisent ces deux pages. Peut-être que vous pourriez expliquer votre problème plus clairement - pourquoi multipliez-vous des vecteurs (et que voulez-vous dire, O (n ^ 2)? Calcul du produit de deux vecteurs n-dimensionnels est de trivialité O (n), je doute fortement Le paquet de vecteur pourrait bousiller ça mal)
Il est informatique produit de points pour chaque paire de documents. Cela le rend quadratique complexe.
Blueraja - Danny Pflughoeft, ce problème consiste à multiplier de très grands vecteurs dimensionnels mais très clairsemés; et n n'est pas une dimension mais le nombre d'éléments non nuls.