Modelo de espacio vectorial coseno tf-idf para encontrar documentos similares

Tener un corpus de más de un millón de documentos.

Para un documento dado, desea encontrar documentos similares usando coseno como en el modelo de espacio vectorial

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

Todos los tf se han normalizado usando frecuencia aumentada, para evitar un sesgo hacia documentos más largos como en este tf-idf :

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

Han precalculado todos Haga que los valores para el denominador se calculen previamente. Por lo tanto, para un determinado debe obtener una puntuación superior a 1 millón de Tener un umbral de 0,6 coseno para similitud $||d||$

$d1$ $d2$

Puedo observar eso para un determinadohay un rango bastante estrecho depara coseno 0.6 Por ejemplo, en una búsqueda de similar para un coseno de 0.6 y ade 7.7631 luegorango de 7.0867 a 8.8339 Donde fuera del umbral del coseno 0.6rango de 0.7223 a 89.3395 Esto fue con normalización de documentos tf estándar. Está mirando MUCHOque no tienen la posibilidad de ser un coseno 0.6 partido $||d_1||$ $||d_2||$ $\ge$
$\ge$ $||d_1||$ $||d_2||$
$||d_2||$

$||d_2||$

Finalmente la pregunta:
para dary coseno de> = 0.6 ¿cómo puede determinar el rango deque tiene una oportunidad? Quepuedo eliminar de forma segura? $||d_1||$ $||d_2||$
$||d_2||$

También sé el número de términos en y si hay un rango de conteo de términos. $d_1$ $d_2$

A través de la experimentacióny parece ser seguro, pero es de esperar que haya un rango que sea seguro
$||d2|| > .8 ||d1||$ $||d2|| < ||d1|| / .8$

Creé algunos casos de prueba con algunos términos únicos, algunos no tan únicos y otros comunes. Efectivamente, puede tomar el término más exclusivo y aumentar esa frecuencia en la comparación. El numerador (producto de puntos) subirá y también lo hará || comparar || y obtendrá un coseno muy cerca de 1.

Tipo de relacionado y NO la pregunta.
También estoy usando el tf-idf para agrupar documentos en grupos. La base de clientes a la que estoy vendiendo está acostumbrada a cerca de grupos dup. Ahí estoy tomando un enfoque relacionado en el que considero el recuento de términos más pequeño y lo evalúo contra el recuento de términos hasta 3 veces. Por lo tanto, un conteo a término de 10 mira de 10 a 30 (4-9 ya tenían su oportunidad en 10). Aquí puedo darme el lujo de perder uno y recogerlo en otro. He terminado el 10% y la proporción más grande es 1.8.

Identifique las fallas en este análisis.
Como lo señaló AN6U5, hay una falla en este análisis.
Ya no es un coseno si el documento está normalizado en ponderado
Y como señaló Mathew tampoco puede concluir d1⋅d2≤d1⋅d1
Estoy todavía con la esperanza de algo que me diera una tapa dura, pero la gente que parece saber estas cosas no me están diciendo
que no quieren cambiar la pregunta por lo que sólo ignorar este
voy a hacer algunos análisis y tal vez enviar una pregunta separada sobre el documento de normalización
para el propósito de esta pregunta asume que el documento está normalizado en bruto tf
Lo siento, pero no soy bueno con el marcado que se usa para hacer las ecuaciones.
Así que en mi notación
|| d1 || = sqrt (suma (w1 x w1))
d1 punto d2 = suma (w1 X w2)
Suponga que d1 es el documento más corto
El mejor d1 punto d2 que se puede lograr es d1 punto d1
Si d1 se casa con 100 paul 20
Y d2 se casa con 100 paul 20 peter 1
Normalizado
d1 se casa 1 paul 1/5
d2 se casa 1 paul 1/5 peter 1/100
Claramente casarse y paul tienen el mismo idf en ambos documentos
El mejor punto d1 posible d2 es d1 punto d1
La coincidencia máxima posible con d1 es d1
cos = d1 punto d1 / || d1 || || d2 ||
cuadrado ambos lados
cos X cos = (d1 punto d1) X (d1 punto d1) / ((d1 punto d1) X (d2 punto d2)) cos X cos = (d1 punto d1) / (d2 punto d2)
toma el cuadrado raíz de ambos lados
cos = || d1 || / || d2 ||
es || d2 || no limitado por el cos?
Si solo uso || d2 || > = cos || d1 || y || d2 || <= || d1 || / cos obtengo la velocidad computacional que necesito

text-mining similarity paparazzo
fuente

Su argumento que concluye con un límite determinado por no funciona porque "El mejor d1 dot d2 que se puede lograr es d1 dot d1 "es incorrecto. Mientras , no es el caso de que . Para esta clase particular de vectores, puede funcionar en casos suficientes como para que sea una aproximación decente, pero sería considerablemente más difícil establecer que siempre es así.

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

@MatthewGraves Creo que estoy de acuerdo contigo. No es mi experiencia, pero todavía la estoy pirateando.

paparazzo

Respuestas:

Desafortunadamente, las matemáticas se simplifican para mostrar que no se puede justificar rigurosamente restringir la comparación de similitud de coseno de los vectores en función de su longitud.

El punto clave es que la métrica de similitud de coseno se normaliza en función de la longitud, de modo que solo se consideran los vectores unitarios. Sé que esta no es necesariamente la respuesta que quería, pero las matemáticas muestran claramente que las métricas de similitud de coseno son independientes de la longitud del vector.

Veamos las matemáticas con más detalle:

Está aplicando una métrica de similitud de coseno y requiere que esa métrica sea mayor que 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$

Pero las longitudes escalares en la parte inferior se pueden distribuir en los productos cruzados anteriores (propiedad distributiva):

\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}}$

$\hat{\mathbf{A}}$ $\hat{\mathbf{B}}$ $\mathbf{A}$ $\mathbf{B}$

Por lo tanto:

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$

depende solo de la orientación de los vectores y no de su magnitud (es decir, longitud).

Conciliar esto con lo que estás haciendo:

$\geq0.6$ $||d2|| > .8 ||d1||$ $||d2|| < ||d1|| / .8$

Quizás pueda conciliar lo que ha estado haciendo con las métricas de distancia al considerar también la distancia euclidiana. Mientras que la similitud del coseno solo devuelve un valor entre -1 y 1 basado en el ángulo entre los dos vectores, las distancias euclidianas devolverán valores que dependen de las longitudes de los dos vectores. En cierto sentido, estás combinando aspectos de la distancia euclidiana con similitud de coseno.

Tiene bastante sentido exigir que las longitudes relativas estén dentro del 25% una de la otra en el sentido de que esto combina un aspecto de la distancia euclidiana para crear coberturas grupales, lo que reduce el tiempo de cálculo, luego se puede usar la similitud de coseno agnóstico de la longitud como El determinante final.

Tenga en cuenta que 1 / .8 = 1.25, entonces d2> =. 8d1 es una restricción más estricta que d2 <= d1 / .8. Sugiero usar d2> =. 75d1 y d2 <= 1.25d1 ya que esto es simétrico.

¡Espero que esto ayude!

AN6U5
fuente

Creo que esto no está haciendo uso del hecho de que las longitudes de los vectores provienen principalmente de los pesos idf compartidos, debido al esquema de normalización tf que está utilizando. Si un documento tiene una norma muy baja, eso implica que no contiene palabras raras (o las contiene con una frecuencia fraccional muy baja), lo que significa que puede descartarse como similar a un documento que solo contiene palabras raras. Pero cuán apretada es esta restricción en general no me parece clara. Es probable que los límites teóricos sean muy amplios en comparación con los límites empíricos observados.

Matthew Graves

@ Matthew Graves, todo lo que digo es que la similitud del coseno es independiente de la longitud del vector. Se pregunta cómo las diferencias en la longitud del vector pueden afectar la similitud del coseno resultante y la respuesta es: no pueden.

AN6U5

La correlación empírica no puede ser ignorada. Debe haber una forma de correlacionar la aleatoriedad del corpus para que abunde, aunque solo sea estadístico. No tengo suficiente representante en este sitio para registrar un voto positivo.

paparazzo

Aquí es donde no estoy de acuerdo. No se normaliza en función de la longitud. Se normaliza en el término más común. Un documento más largo solo puede diluirse. Estoy dispuesto a ajustar cómo se realiza la normalización para obtener un límite que pueda soportar.

paparazzo

Gracias por modificar tu pregunta. Aclara mejor lo que está tratando de lograr. Tenga en cuenta que su normalización modificada hace que esto no sea realmente una similitud de coseno, ya que está estrictamente definido. Sugeriría algunas ediciones adicionales para explicar esto. Tenga cuidado y buena suerte.

AN6U5

$||d_i||$ $||d_i||$ $||d_i||$

Para trabajar con un poco de álgebra, permítanme presentarles algunos términos más (y renombrar algunos por otros más cortos):

$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||$

$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)$

$0.5\le t_i+x_i \le 1$

$x$ $x_i=0\ \forall i$ $d_i+x_i=1$

$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)$

$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$

$P$ $d_1$ $X$

$X$ $w$ $x$ $X$

Matthew Graves
fuente

No estoy de acuerdo con || d || Parece que sirve como una medida de rareza. Esta normalizado. "Mary tenía un corderito" tendrá un || que "Casarse tenía un corderito blanco". Y "oddxxA oddxxB oddxxC" tendrá un || que "oddxxA oddxxB oddxxC oddxxD" en aproximadamente la misma proporción. Y esas dos comparaciones tendrán cos similares.

paparazzo

@Frisbee, ¿estás seguro de esa comparación? Suponiendo que los idfs son 0 para 'a', 0.5 para 'had' y 'Mary', 1 para 'little' y 'white', y 2 para 'lamb', calculo 2.4 para "Mary tenía un corderito" y 2.55 para "Mary tenía un corderito blanco", pero 1.83 para "A Mary tenía un corderito". Es decir, la única forma de disminuir la norma es aumentando la frecuencia del término más frecuente, no agregando nuevas palabras. ¿O no estamos usando la misma fórmula?

Matthew Graves el

Estaba pensando que normalizó el documento en la ponderada (con IDF), no en la frecuencia bruta. Eso cambiaría las cosas. Tiene más sentido para mí normalizar en ponderado. Cambio significativo de un documento || haciendo que 'a' el término más común se ensucie con cosas.

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$

Publico una respuesta pero claramente otorgaré el bono a otra persona

Creo que hay un numerador máximo si el documento tf está normalizado

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

Suponga que d1 tiene los mismos o menos términos (o simplemente tome la d con menos términos)
El máximo posible tf normalizado es 1
Entonces, la suma máxima posible del numerador (tf1, i * idf, i * 1 * idf, i)

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

En cuanto a un mínimo, estoy trabajando en eso, pero claramente hay un mínimo.
Si vas a igualar vas a tener || d ||

paparazzo
fuente