Groove som struktur

De posse de uma representação da coleção de documentos – seja o modelo vetorial ou um modelo de tópicos – é possível utilizar medidas de dissimilaridade para quantificar a semelhança semântica entre dois documentos. A escolha da métrica deve levar em consideração o tipo de representação adotada.

Para o modelo vetorial, indica-se métricas com motivação geométrica como a distância

Euclidiana. O cálculo da distância Euclidiana entre dois documentos, representados pelos

vetores d1 e d2, é dado pela seguinte equação:

disseuclid(d1, d2) = v u u tXM k=1 (freq1k− freq2k)2 (2.6)

onde M é o número de termos da representação e freqij refere-se à medida de influência do

termo tj no documento di. A distância Euclidiana é uma medida de dissimilaridade, ou seja,

quanto mais próximo de 0 for o valor de disseuclid(d1, d2), mais similares são os documentos

d1 e d2.

No entanto, mesmo após a redução de dimensionalidade (eliminação de stopwords, etc.) da representação vetorial, os vetores que representam os documentos continuam tipicamente esparsos (muitos atributos, e poucos deles com valores não nulos). A similaridade entre dois documentos deve depender do número de características (termos) que eles compartilham, ao invés do número de características que eles não compartilham (Tan et al., 2005). Se comparações do tipo 0 — 0 forem consideradas e a representação for esparsa, alguns documentos serão indicados como sendo similares pelo número de termos que ambos não possuem. Dessa forma, a distância Euclidiana não é muito indicada para determinar a similaridade entre dois documentos, pois considera as comparações 0 — 0. A similaridade

do cosseno é uma das medidas mais utilizadas para definir a similaridade entre dois

documentos representados pelo modelo vetorial, pois não favorece comparações do tipo 0 — 0, sendo uma medida indicada justamente para espaços de alta dimensionalidade e esparsos.

Se −→v (d1) e −→v (d2) são dois documentos representados por dois vetores de tamanho M, a

similaridade do cosseno é calculada pela seguinte equação:

simcos(d1, d2) = − →_v(d 1) · −→v (d2) k−→v(d1)k k−→v (d2)k (2.7) onde o operador · indica o produto escalar entre dois vetores, −→v(d1) · −→v (d2) = PMk=1f req1k·

f req2k, e k−→v(d1)k é a norma do vetor −→v(d1), k−→v (d1)k =qPMk=1f req21k =

q

−

→_{v(d1) · −}→_v(d1).

O denominador na Equação (2.7) tem a função de normalizar os vetores −→v(d1) e −→v (d2) para

vetores unitários, caso eles ainda não estejam normalizados. Dessa forma, a Equação (2.7) pode ser vista como o produto escalar das versões normalizadas dos vetores, i.e., o cosseno

do ângulo entre eles.

A similaridade do cosseno retorna valores no intervalo [0, 1], i.e., se o valor é igual a 1, os vetores tem representações idênticas. Já se a similaridade do cosseno é igual a 0, os documentos não compartilham nenhum termo, e não são similares. Para transformar essa

medida de similaridade em uma medida de dissimilaridade basta utilizar disscos(d1, d2) =

1 − simcos(d1, d2).

Já na representação LDA, os documentos são representados por distribuições probabi- lísticas. Métricas com motivação geométrica como a distância Euclidiana e similaridade do cosseno também funcionam nesse tipo de representação. No entanto, também existem métricas de similaridade para medir a diferença entre duas distribuições probabilísticas (Lin, 1991), sendo que uma medida padrão para medir a diferença entre duas distribuições p e q é a divergência de Kullback Leibler (KL):

KL(p, q) = T X k=1 pklog2 pk qk (2.8)

Esta função é igual a zero quando para todos os valores de pk = qk, com k = [1..T ]. Essa

medida permite somente distribuições probabilísticas não-nulas, pois o contrário implicaria numa divisão por zero. A divergência de KL também é assimétrica (KL(p, q) 6= KL(q, p)), e em muitas aplicações é conveniente aplicar uma métrica simétrica baseada na divergência de KL:

dissKL(p, q) =

1

2[KL(p, q) + KL(q, p)] (2.9)

Outra opção para obter uma métrica simétrica a partir da divergência de KL é a

divergência de Jensen-Shannon (JS):

dissJ S(p, q) =

1

2[KL(p, (p + q)/2) + KL(q, (p + q)/2)] (2.10)

que determina que duas distribuições p e q são similares somente se elas são similares à sua média (p + q)/2.

Outra opção também muito utilizada e indicada em Blei e Lafferty (2007) é a

distância de Hellinger, que é simétrica e também obedece a desigualdade triangular

(H(p, q) ≤ H(p, x) + H(x, q)): dissH(p, q) = 1 √ 2 v u u tXT k=1 (√pk−√qk)2 (2.11)

quanto menor o valor de dissH(p, q), mais próximas são as distribuições probabilísticas p e q.

As métricas de Kullback Leibler (KL), de Jensen-Shannon (JS) e de Hellinger são muito utilizadas no contexto de buscas para recuperação de informação. No entanto, essas métricas

consideram que probabilidades baixas para um mesmo atributo é um indicativo de similaridade. O que pode não ser desejável em alguns cenários, quando, por exemplo, estamos calculando a similaridade par a par para um conjunto de distribuições e o número de probabilidades baixas que as distribuições compartilham é maior que o número de probabilidades altas compartilhadas. Nesse tipo de cenário, as distribuições do conjunto tornariam-se todas similares umas as outras, o que pode tornar a similaridade do cosseno mais indicada nesses casos.

Outra abordagem para o cálculo da dissimilaridade entre documentos é baseada na

complexidade de Kolmogorov (Kolmogorov, 1965), que busca quantificar a complexidade

(quantidade de informação) de strings e outros objetos de forma objetiva e absoluta. Medidas baseadas na complexidade de Kolmogorov não requerem representações intermediárias para a coleção de documentos, como o modelo vetorial, o que pode ser uma grande vantagem. No entanto, a complexidade de Kolmogorov não é uma função computável. Apesar disso, uma aproximação para a verdadeira complexidade é possível usando algoritmos de compressão.

Seguindo essa abordagem, Li et al. (2003) propuseram uma medida denominada

Normalized Compression Distance (NCD) que dadas duas strings x e y calcula uma

aproximação para a complexidade de Kolmogorov:

N CD(x, y) = C(xy) − min {C(x), C(y)}

max {C(x), C(y)} (2.12)

onde xy é a concatenação das strings x e y, e C(x) é o tamanho em bytes da compressão da

string x por um compressor. O valor de N CD(x, y) é um número entre 0 e 1 + δ, onde δ é

uma função de limitação do compressor. Quanto menor o valor de NCD(x, y), mais similares são x e y. Algoritmos de compressão como o LZW , zip e PPMZ podem ser utilizados para comprimir as strings.

Baseando-se na medida NCD, Telles et al. (2007) criaram uma medida modificada chamada

Scaled NCD (NCDs) que visa superar problemas relacionados à precisão do compressor:

N CDs(x, y) = NCD(x, y) +

N CD(x, x) + NCD(y, y)

2 (2.13)

A medida NCDs possui a vantagem de retornar 0 quando aplicada sobre dois documentos idênticos, o que é intuitivo. No entanto, o cálculo de medidas baseadas na complexidade de Kolmogorov tem um alto custo computacional.

Existem muitas outras medidas para quantificar a similaridade semântica entre dois documentos. Em particular, existe toda uma classe de medidas de similaridade baseadas na comparação direta entre strings (Salazar et al., 2013), que também não requerem representações intermediárias. Por exemplo, a distância Levenshtein ou distância de edição entre duas strings (duas sequências de caracteres) é dada pelo número mínimo de operações necessárias para transformar uma string em outra. Onde entende-se por “operações” a

inserção, deleção ou substituição de um caractere.

Como mencionado anteriormente medidas baseadas na complexidade de Kolmogorov ou medidas baseadas na comparação entre strings não requerem representações intermediárias. Dessa forma, a etapa de pré-processamento não é necessária, evitando o custo computacional envolvido nessa etapa e a definição de parâmetros, como os limiares superior e inferior da Curva de Zipf. Além disso, em coleções que sofrem adição ou remoção de novos documentos, a representação vetorial deve ser gerada novamente a cada alteração da coleção. A medida NCDs e as medidas baseadas na comparação entre strings não sofrem com este problema, pois nenhuma representação é utilizada e a adição de novos documentos à coleção não altera as relações de similaridade entre os documentos que já estavam presentes, o que possibilita a paralelização do algoritmo.