Medidas de similaridade

Em estatística e campos relacionados, uma medida de similaridade ou função de similaridade ou métrica de similaridade é uma função de valoreal que quantifica a similaridade entre dois objetos. Embora não exista uma definição única de similaridade, geralmente tais medidas são, em certo sentido, o inverso das métricas de distância: elas assumem maiores valores para objetos semelhantes e zero ou um valor negativo para objetos muito diferentes. Embora, em termos mais amplos, uma função de similaridade também possa satisfazer axiomas métricos.

A similaridade por cosseno é uma medida de similaridade comumente usada para vetores de valor real, usada (entre outros campos) na recuperação de informações para pontuar a similaridade de documentos no modelo de espaço vetorial . No aprendizado de máquina, as funções comum do Kernel, como o Kernel RBF, podem ser vistas como métricas de similaridade.

Existem diferentes tipos de medidas de similaridade para vários tipos de objetos, dependendo dos objetos que estão sendo comparados. Para cada tipo de objeto existem várias fórmulas para métricas de similaridade.

Similaridade entre dois pontos de dados

• Distância euclidiana
• Distância de Manhattan (Geometria do táxi)
• Distância de Minkowski
• Distância de Chebyshev

Semelhança entre strings

• Distância de edição
• Distância de Levenshtein
• Distância de Lee
• Distância de Hamming
• Distância de Jaro-Winkler

Semelhança entre duas distribuições de probabilidade

• Distância de Mahalanobis
• Distância de Bhattacharyya
• Distância de Hellinger

Semelhança entre dois conjuntos

• Índice Jacard
• Coeficiente de Sørensen

Uso em análise de agrupamentos

Clustering ou análise de agrupamentos é uma técnica de mineiração de dados usada para descobrir padrões em dados agrupando objetos semelhantes. A técnica envolve o particionamento de um conjunto de pontos de dados em grupos ou clusters com base em suas semelhanças. Um dos aspectos fundamentais do clustering é como medir a similaridade entre os pontos de dados.

As medidas de similaridade desempenham um papel crucial em muitas técnicas de agrupamento, pois são usadas para determinar o quão intimamente relacionados dois pontos de dados estão e se eles devem ser agrupados no mesmo cluster. A medida de similaridade pode assumir muitas formas diferentes, dependendo do tipo de dados que está sendo agrupado e do problema específico que está sendo resolvido.

Uma das medidas de similaridade mais comumente usadas é a distância euclidiana, que é usada em muitas técnicas de agrupamento, incluindo K-means e agrupamento hierárquico. A distância euclidiana é uma medida da distância em linha reta entre dois pontos em um espaço de alta dimensão. É calculado como a raiz quadrada da soma das diferenças quadradas entre as coordenadas correspondentes dos dois pontos. Por exemplo, se tivermos dois pontos de dados $(x1,y1)$ e $(x2,y2)$, a distância euclidiana entre eles é $d=\surd [(x2-x1)^{2}+(y2-y1)^{2}]$

Fig: Mapa de calor da região HIST1, localizada no cromossomo 13 do camundongo nas seguintes coordenadas: [21,7 Mb, 24,1 Mb].

Outra medida de similaridade comumente usada é o Índice de Jaccard ou similaridade de Jaccard, que é usado em técnicas de agrupamento que trabalham com dados binários, como dados de presença/ausência ou dados booleanos; A similaridade Jaccard é particularmente útil para técnicas de agrupamento que trabalham com dados de texto, onde pode ser usada para identificar agrupamentos de documentos semelhantes com base em seus recursos compartilhados ou palavras-chave . É calculado como o tamanho da interseção de dois conjuntos dividido pelo tamanho da união dos dois conjuntos. $J(A,B)={A\bigcap B \over A\bigcup B}$

As semelhanças entre 162 perfis nucleares relevantes são testadas usando o índice de Jaccard (veja a figura com o mapa de calor). A similaridade de Jaccard do perfil nuclear varia de 0 a 1, com 0 indicando nenhuma similaridade entre os dois conjuntos e 1 indicando similaridade perfeita com o objetivo de agrupar o perfil nuclear mais similar.

A distância de Manhattan, também conhecida como geometria do táxi, é uma medida de similaridade comumente usada em técnicas de agrupamento que trabalham com dados contínuos. É uma medida da distância entre dois pontos em um espaço de alta dimensão, calculada como a soma das diferenças absolutas entre as coordenadas correspondentes dos dois pontos $\left\vert x1-x2\right\vert +\left\vert y1-y2\right\vert$.

Em agrupamento espectral, uma medida de similaridade ou afinidade é usada para transformar dados para superar dificuldades relacionadas à falta de convexidade na forma da distribuição de dados. A medida dá origem a uma matriz de similaridade de tamanho $(n,n)$ para um conjunto de n pontos, onde a entrada $(i,j)$ na matriz pode ser simplesmente a (recíproca da) distância euclidiana entre $i$ e $j$, ou pode ser uma medida de distância mais complexa, como a similaridade Gaussiana $e^{-\|s_{1}-s_{2}\|^{2}/2\sigma ^{2}}$ . Modificar ainda mais esse resultado com técnicas de análise de rede também é comum.

A escolha da medida de similaridade depende do tipo de dados que está sendo agrupado e do problema específico que está sendo resolvido. Por exemplo, trabalhando com dados contínuos, como dados de expressão gênomica, a distância euclidiana ou a similaridade de cosseno podem ser apropriadas. Já com dados binários como a presença de um loci genômico em um perfil nuclear, o índice de Jaccard pode ser mais apropriado. Por fim, trabalhando com dados organizados em uma estrutura de grade, como dados de processamento de imagem ou sinal, a distância de Manhattan é particularmente útil para o agrupamento.

Uso em sistemas de recomendação

Medidas de similaridade também são ferramentas para desenvolver sistemas de recomendação, observando a percepção do usuário e gosto em relação a vários itens. Em sistemas de recomendação, o método usa um cálculo de distância como Distância Euclidiana ou Similaridade por Cosseno para gerar um Matriz de Similaridade com valores que representam a similaridade de qualquer par de alvos. Então, analisando e comparando os valores na matriz, é possível combinar dois alvos com a preferência de um usuário ou vincular usuários com base em suas notas. Nesse sistema, é relevante observar o próprio valor e a distância absoluta entre dois valores. A coleta desses dados pode indicar a probabilidade de uma marca para um usuário, bem como o quão próximas duas marcas são rejeitadas ou aceitas. É possível então recomendar a um usuário alvos com alta similaridade aos seus gostos.

Os sistemas de recomendação são observados em múltiplas plataformas de entretenimento online, em redes sociais e sites de streaming. A lógica para a construção desses sistemas é baseada em medidas de similaridade.

Uso em alinhamento de sequências

As matrizes de similaridade são usadas no alinhamento de sequências . Pontuações mais altas são dadas para características mais semelhantes e pontuações mais baixas ou negativas para características diferentes.

As matrizes de similaridade de nucleotídeos são usadas para alinhar sequências de ácidos nucleicos. Como existem apenas quatro nucleotídeos comumente encontrados no DNA (Adenina (A), Citosina (C), Guanina (G) e Timina (T)), as matrizes de similaridade de nucleotídeos são muito mais simples do que as matrizes de similaridade de proteínas. Por exemplo, uma matriz simples atribuirá a bases idênticas uma pontuação de +1 e bases não idênticas uma pontuação de -1. Uma matriz mais complicada daria uma pontuação mais alta para transições (mudanças de uma pirimidina como C ou T para outra pirimidina, ou de uma purina como A ou G para outra purina) do que para transversões (de uma pirimidina para uma purina ou vice-versa). A proporção de correspondência/incompatibilidade da matriz define a distância evolutiva alvo. A matriz de DNA +1/-3 usada pelo BLASTN é mais adequada para encontrar correspondências entre sequências que são 99% idênticas; uma matriz +1/−1 (ou +4/−4) é muito mais adequada para sequências com cerca de 70% de similaridade. Matrizes para sequências de menor similaridade requerem alinhamentos de sequência mais longos.

As matrizes de semelhança de aminoácidos são mais complicadas, porque existem 20 aminoácidos codificados pelo código genético e, portanto, um número maior de substituições possíveis. Portanto, a matriz de similaridade para aminoácidos contém 400 entradas (embora geralmente seja simétrica). A primeira abordagem marcou todas as mudanças de aminoácidos igualmente. Um refinamento posterior foi determinar as semelhanças de aminoácidos com base em quantas mudanças de base foram necessárias para alterar um códon para codificar aquele aminoácido. Este modelo é melhor, mas não leva em conta a pressão seletiva das mudanças de aminoácidos. Modelos melhores levaram em consideração as propriedades químicas dos aminoácidos.

Uma abordagem possível é gerar empiricamente as matrizes de similaridade. O método Dayhoff usou árvores filogenéticas e sequências retiradas de espécies da árvore. Esta abordagem deu origem à série de matrizes PAM. As matrizes PAM são rotuladas com base em quantas alterações de nucleotídeos ocorreram, por 100 aminoácidos. Embora as matrizes PAM se beneficiem de ter um modelo evolutivo bem compreendido, elas são mais úteis em distâncias evolutivas curtas (PAM10–PAM120). Em longas distâncias evolutivas, por exemplo PAM250 ou 20% de identidade, foi demonstrado que as matrizes BLOSUM são muito mais eficazes.

As séries BLOSUM foram geradas comparando um número de sequências divergentes. A série BLOSUM é rotulada com base em quanta entropia permanece inalterada entre todas as sequências, portanto, um número BLOSUM mais baixo corresponde a um número PAM mais alto.