Modelo de espaço vetorial cosseno tf-idf para encontrar documentos semelhantes

Possui corpus de mais de um milhão de documentos

Para um determinado documento, deseja encontrar documentos semelhantes usando cosseno como no modelo de espaço vetorial

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

Todos os tf foram normalizados usando frequência aumentada, para evitar um viés em direção a documentos mais longos, como neste tf-idf :

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

Pré-calculou tudo Os valores do denominador são pré-calculados. Portanto, para um dado necessário pontuar mais de 1 milhão Tenha um limite de 0,6 cosseno para semelhança $||d||$

$d1$ $d2$

Eu posso observar isso por um determinado existe uma gama bastante estreita de para cosseno 0,6 Por exemplo, em uma pesquisa semelhante para um cosseno de 0,6 e a de 7.7631 então intervalo de 7,0867 a 8,8339 Onde fora do limiar de cosseno 0,6 variam de 0,7223 a 89,3395 $||d_1||$ $||d_2||$ $\ge$
$\ge$ $||d_1||$ $||d_2||$
$||d_2||$
Isso ocorreu com a normalização padrão do documento tf.
Ele está olhando MUITO de que não têm chance de ser uma partida de cosseno 0,6 $||d_2||$

Finalmente a pergunta:
para dar e cosseno de> = 0,6 como pode determinar o intervalo de que tem uma chance? Qual posso eliminar com segurança? $||d_1||$ $||d_2||$
$||d_2||$

Eu também sei o número de termos em e se houver intervalo de contagem de termos. $d_1$ $d_2$

Via experimentação
e parece ser seguro, mas espero que haja um alcance comprovadamente seguro $||d2|| > .8 ||d1||$ $||d2|| < ||d1|| / .8$

Criamos alguns casos de teste com alguns termos únicos, alguns não tão únicos e outros comuns. Com certeza, você pode pegar o termo mais exclusivo e aumentar essa frequência na comparação. O numerador aumentará (produto escalar) e, portanto, || comparará || e obterá um cosseno muito próximo de 1.

Tipo de relacionado e NÃO a pergunta.
Também estou usando o tf-idf para agrupar documentos em grupos. A base de clientes em que estou vendendo está acostumada a aproximar-se de grupos dup. Lá, estou adotando uma abordagem relacionada, visto como a menor contagem de termos e a avalio em relação à contagem de termos até 3x. Portanto, uma contagem de 10 a 10 é de 10 a 30 (4-9 já teve sua chance de 10). Aqui, posso me dar ao luxo de perder um, caso ele seja capturado em outro. Estou 10% pronto e a maior proporção é de 1,8.

Por favor, identifique as falhas em esta análise
como fora apontado por AN6U5 há uma falha na análise
Não é mais um cosseno se o documento é normalizado em ponderada
E como fora apontado por Mathew também não se pode concluir d1⋅d2≤d1⋅d1
estou ainda esperando por algo para me dar uma dura ligado, mas as pessoas que parecem saber essas coisas estão me dizendo não
eu não quero mudar a pergunta então basta ignorar este
vou fazer algumas análises e talvez postar uma pergunta separada na normalização de documentos
para o objetivo desta pergunta assume que o documento está normalizado em bruto tf
Desculpe, mas não sou bom com o que a marcação é usada para fazer as equações
Então, na minha notação
|| d1 || = sqrt (soma (w1 x w1))
d1 ponto d2 = soma (w1 X w2)
Suponha que d1 seja o documento mais curto
O melhor d1 ponto d2 que pode ser alcançado é d1 ponto d1
Se d1 se casar com 100 paul 20
E d2 for se casar com 100 paul 20 pedro 1 D1
normalizado
é casado 1 paul 1/5
d2 se casa 1 paul 1/5 peter 1/100
claramente se casa e paul tem o mesmo idf nos dois documentos
O melhor ponto d1 possível d2 é d1 ponto d1
A correspondência máxima possível para d1 é d1
cos = d1 ponto d1 / || d1 || || d2 ||
quadrado ambos os lados
cos X cos = (d1 ponto d1) X (d1 ponto d1) / ((d1 ponto d1) X (d2 ponto d2)) cos X cos = (d1 ponto d1) / (d2 ponto d2)
pegue o quadrado raiz de ambos os lados
cos = || d1 || / || d2 ||
é || d2 || não limitado pelo cos?
Se eu apenas usar || d2 || > = cos || d1 || e || d2 || <= || d1 || / cos eu recebo a velocidade computacional necessária

text-mining similarity paparazzo
fonte

Seu argumento que termina com um limite determinado por

não funciona porque "O melhor d1 ponto d2 que pode ser alcançado é d1 ponto d1" está incorreto. Enquanto

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$

@MatthewGraves Acho que concordo com você. Não é meu conhecimento, mas ainda estou trabalhando nisso.

Paparazzo

Respostas:

Infelizmente, a matemática simplifica para mostrar que você não pode justificar rigorosamente restringir a comparação de similaridade de cosseno dos vetores com base em seus comprimentos.

O ponto principal é que a métrica de similaridade do cosseno normaliza com base no comprimento, de modo que apenas os vetores unitários são considerados. Eu sei que essa não é necessariamente a resposta que você queria, mas a matemática mostra claramente que as métricas de similaridade do cosseno são agnósticas ao comprimento do vetor.

Vamos analisar a matemática com mais detalhes:

Você está aplicando uma métrica de similaridade de cosseno e exigindo que essa métrica seja maior 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$

Mas os comprimentos escalares na parte inferior podem ser distribuídos nos produtos cruzados acima (propriedade 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}$

Para isso:

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 apenas da orientação dos vetores e não de sua magnitude (ou seja, comprimento).

Reconciliando isso com o que você está fazendo:

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

Talvez você possa reconciliar o que tem feito com as métricas de distância, considerando também a distância euclidiana. Onde como a similaridade do cosseno retorna apenas um valor entre -1 e 1 com base no ângulo entre os dois vetores, as distâncias euclidianas retornarão valores que dependem dos comprimentos dos dois vetores. Em certo sentido, você está combinando aspectos da distância euclidiana com semelhança de cosseno.

Faz bastante sentido exigir que os comprimentos relativos estejam dentro de 25% um do outro, no sentido de que isso combina um aspecto da distância euclidiana para criar copas agrupadas, o que reduz o tempo de computação e, em seguida, a similaridade agnóstica do cosseno pode ser usada como o determinante final.

Observe que 1 / .8 = 1,25; portanto, d2> =. 8d1 é uma restrição mais rígida que d2 <= d1 / .8. Sugiro usar d2> =. 75d1 e d2 <= 1.25d1, pois isso é simétrico.

Espero que isto ajude!

AN6U5
fonte

Eu acho que isso não está fazendo uso do fato de que os comprimentos de vetor vêm principalmente dos pesos idf compartilhados, devido ao esquema de normalização tf que ele está usando. Se um documento tem uma norma muito baixa, isso implica que ele não contém palavras raras (ou as contém em uma freqüência fracionária muito baixa), o que significa que pode ser descartado como semelhante a um documento que contém apenas palavras raras. Mas, em geral, o quão restrito é esse constrangimento não me parece claro. Provavelmente, os limites teóricos são muito amplos em comparação aos limites empíricos observados.

Matthew Graves

@ Matthew Graves, tudo o que estou dizendo é que a semelhança de cosseno é independente do comprimento do vetor. Ele está perguntando como as diferenças no comprimento do vetor podem afetar a similaridade resultante do cosseno e a resposta é: elas não podem.

AN6U5 13/10/2015

A correlação empírica não pode ser ignorada. Existe uma maneira de correlacionar a aleatoriedade do corpus a abundar, se apenas estatística. Eu não tenho representante suficiente neste site para que uma votação seja registrada.

Paparazzo

Aqui é onde eu não concordo. Não normaliza com base no comprimento. Normaliza no termo mais comum. Um documento mais longo pode apenas diluir. Estou disposto a ajustar como a normalização é executada para obter um limite que eu possa apoiar.

Paparazzo

Obrigado por modificar sua pergunta. Esclarece melhor o que você está tentando realizar. Observe que sua normalização modificada faz com que isso realmente não seja uma semelhança de cosseno, pois isso é estritamente definido. Eu sugeriria algumas edições adicionais para esclarecer isso. Cuide-se e boa sorte.

AN6U5

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

Para trabalhar com uma álgebra, deixe-me introduzir mais alguns termos (e renomear alguns para outros mais curtos):

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

Eu não concordo com || d || com parece servir como uma medida de raridade. Está normalizado. "Maria teve um cordeirinho" terá um menor || do que "Casar com um cordeirinho branco". E "oddxxA oddxxB oddxxC" terá um valor menor || que "oddxxA oddxxB oddxxC oddxxD" aproximadamente na mesma proporção. E essas duas comparações terão cos semelhantes.

Paparazzo

@Frisbee, você tem certeza sobre essa comparação? Supondo que os IDFs sejam 0 para 'a', 0,5 para 'had' e 'Mary', 1 para 'little' e 'white' e 2 para 'cordeiro', calculo 2,4 para 'Mary teve um cordeirinho' e 2,55 para "Maria teve um cordeirinho branco", mas 1,83 para "Uma Maria teve um cordeirinho". Ou seja, a única maneira de diminuir a norma é aumentando a frequência do termo mais frequente, não adicionando novas palavras. Ou não estamos usando a mesma fórmula?

Matthew Graves

Eu estava pensando que você normalizou o documento na frequência ponderada (com IDF) e não na frequência bruta. Isso mudaria as coisas. Faz mais sentido para mim normalizar o peso. Alteração significativa de um documento || tornando 'a' o termo mais comum mexe com as coisas.

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$

Eu posto uma resposta, mas claramente concederei o bônus a outra pessoa

Eu acho que existe um numerador máximo se o documento tf for normalizado

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

Suponha que d1 tenha os mesmos termos ou menos (ou apenas faça d com menos termos)
O máximo possível de tf normalizado é 1
Portanto, a soma máxima possível do numerador (tf1, i * idf, i * 1 * idf, i)

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

No mínimo, estou trabalhando nisso, mas claramente há um mínimo.
Se você vai combinar, você terá || d ||

paparazzo
fonte