Modèle d'espace vectoriel cosinus tf-idf pour trouver des documents similaires

Avoir un corpus de plus d'un million de documents

Pour un document donné, vous voulez trouver des documents similaires en utilisant le cosinus comme dans le modèle d'espace vectoriel

$d_1 \cdot d_2 / ( ||d_1|| ||d_2|| )$

Tous les tf ont été normalisés en utilisant une fréquence augmentée, pour éviter un biais vers des documents plus longs comme dans ce tf-idf :

$tf(t,d)=0.5+0.5\frac{f(t,d)}{\mathrm{max}\{f(t,d): t\in d\}}$

Avoir pré-calculé tout Avoir les valeurs du dénominateur pré-calculées Donc, pour un donné, il faut marquer plus de 1 million de Avoir un seuil de 0,6 cosinus pour la similitude $||d||$

$d1$ $d2$

Je peux observer que pour unil existe une plage assez étroite depour cosinus 0.6 Par exemple dans une recherche similaire pour un cosinus de 0.6 et unde 7,7631 alorsplage de 7,0867 à 8,8339 En dehors du seuil de cosinus 0,6plage de 0,7223 à 89,3395 C'était avec la normalisation standard des documents tf. Il examine BEAUCOUP dequi n'ont aucune chance d'être un match cosinus 0.6 $||d_1||$ $||d_2||$ $\ge$
$\ge$ $||d_1||$ $||d_2||$
$||d_2||$

$||d_2||$

Enfin la question:
Pour un donneret cosinus de> = 0,6 comment déterminer la plage dequi ont une chance? Quipuis-je éliminer en toute sécurité? $||d_1||$ $||d_2||$
$||d_2||$

Je connais également le nombre de termes en et s'il y a une plage de nombre de termes . $d_1$ $d_2$

Via l'expérimentationet semble être sûr, mais j'espère qu'il y a une portée qui s'est avérée sûre
$||d2|| > .8 ||d1||$ $||d2|| < ||d1|| / .8$

Créé des cas de test avec des termes très uniques, certains pas si uniques et certains courants. Effectivement, vous pouvez prendre le terme le plus unique et augmenter cette fréquence dans la comparaison. Le numérateur augmentera (produit scalaire) et il en sera de même pour || comparer || et obtiendra un cosinus très proche de 1.

Type de relation et PAS la question.
J'utilise également le tf-idf pour regrouper des documents en groupes. La clientèle dans laquelle je vends est habituée à se rapprocher des groupes de dup. Là, je prends une approche connexe dans je regarde comme le plus petit nombre de termes et je l'évalue par rapport au nombre de termes jusqu'à 3x. Ainsi, un nombre de termes de 10 ressemble à 10 à 30 (4-9 avait déjà son tir à 10). Ici, je peux me permettre d'en manquer un, de le récupérer dans un autre. J'ai terminé 10% et le plus grand ratio est de 1,8.

Veuillez identifier les défauts de cette analyse
Comme le souligne AN6U5 il y a un défaut dans cette analyse
Ce n'est plus un cosinus si le document est normalisé sur pondéré
Et comme le souligne Mathew ne peut pas non plus conclure d1⋅d2≤d1⋅d1
Je suis en espérant toujours quelque chose pour me donner un lien solide, mais les gens qui semblent connaître ce genre de choses me disent non,
je ne veux pas changer la question, alors ignorez cela,
je ferai une analyse et peut-être publier une question distincte sur la normalisation des documents
Pour le but de cette question suppose que le document est normalisé sur tf brut
Désolé mais je ne suis pas bon avec ce que le balisage est utilisé pour faire les équations
Donc dans ma notation
|| d1 || = sqrt (somme (w1 x w1))
d1 point d2 = somme (w1 X w2)
Supposons que d1 est le document le plus court
Le meilleur d1 point d2 qui peut être atteint est d1 point d1
Si d1 est marié 100 paul 20
Et d2 est marié 100 paul 20 peter 1
Normalisé
d1 est marié 1 paul 1/5
d2 est marié 1 paul 1/5 peter 1/100
Clairement marier et paul ont le même idf dans les deux documents
Le meilleur point d1 possible d2 est d1 point d1
La correspondance maximale possible avec d1 est d1
cos = d1 point d1 / || d1 || || d2 ||
carré des deux côtés
cos X cos = (d1 point d1) X (d1 point d1) / ((d1 point d1) X (d2 point d2)) cos X cos = (d1 point d1) / (d2 point d2)
prendre le carré racine des deux côtés
cos = || d1 || / || d2 ||
est || d2 || pas limité par le cos?
Si j'utilise juste || d2 || > = cos || d1 || et || d2 || <= || d1 || / cos j'obtiens la vitesse de calcul dont j'ai besoin

text-mining similarity paparazzo
la source

Votre argument qui se termine par une limite déterminée par ne fonctionne pas car "le meilleur point d1 d2 qui peut être atteint est d1 point d1 "est incorrect. Alors que , ce n'est pas le cas que . Pour cette classe particulière de vecteurs, cela peut fonctionner dans suffisamment de cas pour que ce soit une approximation décente, mais il serait beaucoup plus difficile d'établir que c'est toujours le cas.

c o s = \frac{| | d_{1} | |}{| | d_{2} | |}

$\mathrm{cos}=\frac{||d_1||}{||d_2||}$

\frac{d_{1} \cdot d_{2}}{| | d_{1} | | | | d_{2} | |} \leq \frac{d_{1} \cdot d_{1}}{| | d_{1} | | | | d_{1} | |}

$\frac{d_1\cdot d_2}{||d_1||\ ||d_2||}\le\frac{d_1\cdot d_1}{||d_1||\ ||d_1||}$

d_{1} \cdot d_{2} \leq d_{1} \cdot d_{1}

$d_1\cdot d_2\le d_1\cdot d_1$

Matthew Graves du

@MatthewGraves Je pense que je suis d'accord avec vous. Ce n'est pas mon expertise, mais je continue de la pirater.

paparazzo

Réponses:

Malheureusement, les calculs se simplifient pour montrer que vous ne pouvez pas justifier rigoureusement de restreindre la comparaison de similitude cosinus des vecteurs en fonction de leurs longueurs.

Le point clé est que la métrique de similitude cosinus se normalise en fonction de la longueur, de sorte que seuls les vecteurs unitaires sont pris en compte. Je sais que ce n'est pas nécessairement la réponse que vous vouliez, mais les calculs montrent clairement que les métriques de similitude cosinus sont agnostiques à la longueur du vecteur.

Regardons les mathématiques plus en détail:

Vous appliquez une métrique de similitude cosinus et exigez que cette métrique soit supérieure à 0,6:

s i m i l a r i t y = \cos (θ) = \frac{A \cdot B}{| | A | | | | B | |} \geq 0.6

$similarity=\cos{(\theta)}=\frac{\mathbf{A}\cdot\mathbf{B}}{||A|| ||B||}\geq0.6$ .

Mais les longueurs scalaires sur le fond peuvent être réparties dans les produits croisés ci-dessus (propriété distributive):

\frac{A \cdot B}{| | A | | | | B | |} = \frac{A}{| | A | |} \cdot \frac{B}{| | B | |} = \hat{A} \cdot \hat{B}

$\frac{\mathbf{A}\cdot\mathbf{B}}{||A|| ||B||} = \frac{\mathbf{A}}{||A||}\cdot\frac{\mathbf{B}}{||B||}=\hat{\mathbf{A}}\cdot\hat{\mathbf{B}}$ .

Maintenant et sont des vecteurs qui pointent dans la même direction que et mais ils ont été normalisés à la longueur un. Ainsi, la définition de la métrique de similitude cosinus est la prise des vecteurs d'origine, leur normalisation à la longueur un, puis la mesure du produit scalaire des vecteurs unitaires. $\hat{\mathbf{A}}$ $\hat{\mathbf{B}}$ $\mathbf{A}$ $\mathbf{B}$

À cet effet:

s i m i l a r i t y = \cos (θ) = \frac{d 1 \cdot d 2}{| | d 1 | | | | d 2 | |} = \hat{d 1} \cdot \hat{d 2} \geq 0.6

$similarity=\cos{(\theta)}=\frac{\mathbf{d1}\cdot\mathbf{d2}}{||d1|| ||d2||}=\hat{\mathbf{d1}}\cdot\hat{\mathbf{d2}}\geq0.6$

ne dépend que de l'orientation des vecteurs et non de leur ampleur (c'est-à-dire de la longueur).

Concilier cela avec ce que vous faites:

Malgré ce que montrent les résultats de l'algèbre linéaire, vous pouvez toujours voir un résultat statistiquement significatif. En pratique, vous constaterez peut-être que les statistiques montrent que les restrictions de longueur sont valides pour vos données. Par exemple, vous pourriez constater que les tweets ne partagent jamais une similitude cosinus par rapport à "War and Peace" de Tolstoï. Si vos statistiques semblent bonnes pour l'utilisation deet alors je vous suggère de l'accompagner car ce type de restrictions de canopée est très utile pour gagner du temps de calcul. $\geq0.6$ $||d2|| > .8 ||d1||$ $||d2|| < ||d1|| / .8$

Vous pouvez peut-être concilier ce que vous avez fait avec les métriques de distance en considérant également la distance euclidienne. Alors que la similitude en cosinus ne renvoie qu'une valeur comprise entre -1 et 1 en fonction de l'angle entre les deux vecteurs, les distances euclidiennes renvoient des valeurs qui dépendent des longueurs des deux vecteurs. Dans un certain sens, vous combinez des aspects de la distance euclidienne avec une similitude en cosinus.

Il est assez logique d'exiger que les longueurs relatives soient à moins de 25% les unes des autres dans le sens où cela combine un aspect de la distance euclidienne pour créer des auvents groupés, ce qui réduit le temps de calcul, puis la similitude cosinus agnostique de la longueur peut être utilisée comme le déterminant final.

Notez que 1 / .8 = 1,25, donc d2> =. 8d1 est une restriction plus stricte que d2 <= d1 / .8. Je suggère d'utiliser d2> =. 75d1 et d2 <= 1.25d1 car c'est symétrique.

J'espère que cela t'aides!

AN6U5
la source

Je pense que cela ne fait pas usage du fait que les longueurs de vecteur proviennent principalement des poids idf partagés, en raison du schéma de normalisation tf qu'il utilise. Si un document a une norme très basse, cela implique qu'il ne contient pas de mots rares (ou les contient à une fréquence fractionnaire très faible), ce qui signifie qu'il peut être exclu comme similaire à un document qui ne contient que des mots rares. Mais la rigueur de cette contrainte me semble en général peu claire. Il est probable que les limites théoriques soient très larges par rapport aux limites empiriques observées.

Matthew Graves

@Matthew Graves, tout ce que je dis, c'est que la similitude du cosinus est agnostique à la longueur du vecteur. Il demande comment les différences de longueur de vecteur peuvent affecter la similitude cosinus résultante et la réponse est: elles ne le peuvent pas.

AN6U5

La corrélation empirique ne peut être ignorée. Il existe un moyen de corréler le caractère aléatoire du corpus à abonder, ne serait-ce que statistique. Je n'ai pas assez de représentants sur ce site pour pouvoir voter.

paparazzo

Voici où je ne suis pas d'accord. Il ne se normalise pas en fonction de la longueur. Il se normalise sur le terme le plus courant. Un document plus long ne peut que se diluer. Je suis prêt à ajuster la façon dont la normalisation est effectuée pour obtenir une limite que je peux soutenir.

paparazzo

Merci d'avoir modifié votre question. Il clarifie mieux ce que vous essayez d'accomplir. Notez que votre normalisation modifiée ne fait en fait pas une similitude cosinus, car elle est strictement définie. Je suggérerais quelques modifications supplémentaires pour le préciser. Prends soin de toi et bonne chance.

AN6U5

Tout d'abord, essayons de comprendre pourquoi cela fonctionnerait. semble servir de mesure de rareté des mots, ce qui semble plausible comme quelque chose à filtrer. Si les documents utilisent un nombre différent de mots rares, il leur sera difficile de s'aligner sur la mesure de similitude cosinus. Mais il me semble peu probable que cette coupure ne dépende que de, plutôt que sur la structure des poids tf ou idf qui entrent dans. $||d_i||$ $||d_i||$ $||d_i||$

Pour travailler sur une algèbre, permettez-moi d'introduire quelques termes supplémentaires (et renommer certains en plus courts):

Soit un vecteur de poids tf élément multiplié par un vecteur de poids idf pour obtenir les poids finaux . Nous savons que et (en raison de la taille du corpus et en supposant que nous utilisons la base 10, peu importe si nous ne le sommes pas). Soit. $d_1$ $[t_1, t_2, ...]$ $[w_1, w_2, ...]$ $[d_1, d_2, ...]$ $0.5\le t_i\le 1$ $0\le w_i\le 6$ $D_1=||d_1||$

Connaissant , nous voulons construire un vecteur delta , tel que ait le minimal (ou maximal) soumis aux contraintes qui: $d_1$ $x$ $d_1+x$ $X$

$X=\sqrt{\sum_i w_i^2 (t_i+x_i)^2}$

$0.6D_1X\le \sum_i w_i^2t_i(t_i+x_i)$ (1)

$0.5\le t_i+x_i \le 1$

Parce que nous n'avons pas utilisé le poids tf brut pour , est dans l'espace de la solution. également la contrainte plus compliquée d'au moins un , car nous ne pouvons pas l'exprimer de manière linéaire. Nous allons le laisser tel quel et espérons que l'optimiseur finira par mettre l'un d'entre eux à 1. $x$ $x_i=0\ \forall i$ $d_i+x_i=1$

Intuitivement, il semble que l'ensemble des possibles devrait être convexe, mais même si c'est le cas, nous sommes déjà dans le domaine de la programmation quadratique contrainte . Notez que nous pouvons résoudre pour minimal au lieu de minimal , car , mais nous ne pouvons probablement pas utiliser cette méthodologie pour maximiser (c'est-à-dire minimiser ). Mais heureusement, cela sera facilement résoluble si est semi-défini positif . Alors, qu'est-ce que ? Nous devons réécrire (1) sous la forme correcte, ce qui commence par la quadrature des deux côtés: $x$ $X^2$ $X$ $X>0$ $X$ $-X$ $P$ $P$

$0\ge 0.36D_1^2\sum_i w_i^2 (t_i+x_i)^2-\sum_{i,j}w_i^4t_it_j(t_i+x_i)(t_j+x_j)$

Nous pouvons réécrire ceci comme où si et sinon. $0\ge x^TPx+q^Tx+r$ $P_{i,j}=0.36D_1^2-w_i^2t_it_j$ $i=j$ $-w_i^2t_it_j$

Il n'est pas évident pour moi que doit être semi-défini positif, mais ce sera facile à vérifier pour tout individu . Si oui, pop cela dans un solveur QP et vous obtiendrez une borne inférieure sur . Sinon, nous avons des ennuis. $P$ $d_1$ $X$

Pouvons-nous également obtenir une limite supérieure pratique? Je ne suis pas sûr. Évidemment, il existe une limite supérieure finie, car nous pouvons facilement calculer le maximum possible à partir du vecteur idf . Mais le fait que le poids minimum de tf soit de 0,5 au lieu de 0 jette mes intuitions sur la façon de créer un contradictoire avec un maximum de , et donc la meilleure approche que je propose est la descente en gradient, qui peut ou non trouver le maximum global réel mais sera probablement proche. $X$ $w$ $x$ $X$

Matthew Graves
la source

Je ne suis pas d'accord avec || d || avec semble servir de mesure de rareté. C'est normalisé. "Mary avait un petit agneau" aura un plus petit || que "Marry avait un petit agneau blanc". Et "oddxxA oddxxB oddxxC" aura un plus petit || que "oddxxA oddxxB oddxxC oddxxD" dans à peu près le même rapport. Et ces deux comparaisons auront un cos similaire.

paparazzo

@Frisbee, êtes-vous sûr de cette comparaison? En supposant que les idfs sont 0 pour 'a', 0,5 pour 'had' et 'Mary', 1 pour 'little' et 'white', et 2 pour 'lamb', je calcule 2,4 pour "Mary had a little lamb" et 2,55 pour "Mary avait un petit agneau blanc", mais 1,83 pour "A Mary avait un petit agneau". C'est-à-dire que la seule façon de diminuer la norme est d'augmenter la fréquence du terme le plus fréquent, et non d'ajouter de nouveaux mots. Ou n'utilisons-nous pas la même formule?

Matthew Graves

Je pensais que vous avez normalisé le document sur la fréquence pondérée (avec IDF) et non sur la fréquence brute. Cela changerait les choses. Il est plus logique pour moi de normaliser la pondération. Modification significative d'un document || en faisant de 'a' le terme le plus courant avec tout.

paparazzo

d_{t} = w_{t} (0.5 + 0.5 \frac{w_{t} f (t, d)}{m a x {w_{t} f (t, d) : t \in d}})

$d_t=w_t(0.5+0.5\frac{w_tf(t,d)}{\mathrm{max}\{w_tf(t,d): t\in d\}})$

w_{t} = l o g \frac{N}{| {d \in D : t \in d} |}

$w_t=\mathrm{log}\frac{N}{|\{d\in D: t\in d\}|}$

d

$d$

d_{i}

$d_i$

d

$d$

Je poste une réponse mais je vais clairement attribuer le bonus à quelqu'un d'autre

Je pense qu'il y a un numérateur maximum si le document tf est normalisé

d1⋅d2 / (|| d1 |||| d2 ||)

Supposons que d1 a les mêmes termes ou moins (ou prenez simplement le d avec moins de termes)
Le maximum possible normalisé tf est 1
Donc la somme maximale possible du numérateur (tf1, i * idf, i * 1 * idf, i)

|| d2 || = somme (tf1, i * idf, i * 1 * idf, i) / || d1 || / .6

En ce qui concerne un minimum, je travaille là-dessus, mais il y a clairement un minimum.
Si vous allez correspondre, vous allez avoir || d ||

paparazzo
la source