Log Book – Guia de Abordagens de Medição de Distância para K-Cleansing

Neste guia, tentei cobrir os diferentes tipos e características de distâncias que podem ser usadas no K-Means Clustering

Dip Ranjan Chatterjee em Em direção a Data Science Follow Jul 13 · 9 min ler

L et começar com uma breve introdução de clustering. O agrupamento é a tarefa de dividir os pontos de dados em vários grupos, de modo que os pontos de dados nos mesmos grupos sejam mais semelhantes a outros pontos de dados no mesmo grupo do que aqueles em outros grupos. Em palavras simples, o objetivo é segregar grupos com características semelhantes e atribuí-los a clusters .

O K-Means Clustering é um dos muitos algoritmos de clustering. A ideia por trás disso é definir clusters para que a variação total dentro do cluster (conhecida como variação total dentro do cluster) seja minimizada. O algoritmo K-means pode ser resumido da seguinte forma:

 1. Especifique o número de clusters (k) a serem criados. 2. Selecione aleatoriamente k objetos do conjunto de dados como os centros ou meios iniciais do cluster. 3. Atribua cada observação ao seu centróide mais próximo, baseado na distância especificada [o tipo de distância é o que iremos explorar neste artigo, no caso acima é Euclidiano] entre o objeto e o centróide. 4. Para cada um dos k clusters, atualize o centróide do cluster calculando os novos valores médios de todos os pontos de dados no cluster. O centróide de um K-ésimo cluster é um vetor de comprimento p contendo as médias de todas as variáveis para as observações no K-ésimo cluster; p é o número de variáveis. 5. Iterativamente, minimize o total dentro da soma do quadrado. Ou seja, iterar as etapas 3 e 4 até que as atribuições do cluster parem de mudar ou o número máximo de iterações seja atingido. 

K – significa visualização de clusters [ fonte ]

Em R calculamos o cluster K-Means por:

 Kmeans(x, centers, iter.max = 10, nstart = 1, method = "euclidean") onde 
x> frame de dados
Centros> Número de clusters
iter.max> O número máximo de iterações permitido
nstart> Quantos conjuntos aleatórios de centro devem ser escolhidos
method> A medida de distância a ser usada
Há outras opções também para calcular o agrupamento de kmeans, mas esse é o padrão usual.

Existem diferentes métodos de cálculo de distância, como euclidean, maximum (Distância Chebychev), manhattan, hamming, canberra, pearson, abspearson, abscorrelação, spearman ou kendall . Então, como você escolhe qual deles usar?

Medições de distância entre pontos de dados

Os métodos são definidos em 2 grupos, um é baseado na captura da separação geométrica e outro é dependente da correlação. Vamos dar uma olhada em cada um.

G Separação eometrical

Distância Euclidiana, Manhattan & Máxima ( Chebychev )

Para estar com muito deste material nesta seção foi referido a partir da página agora off-line de divingintodatascience , o site tinha sido de grande ajuda. A distância de Minkowski é uma métrica que nos diz a distância entre 2 pontos no espaço. Agora a distância Minkowski vem de ordens diferentes e logo veremos o que isso significa e também veremos porque estou falando sobre isso em vez de distâncias euclidianas e outras.

A fórmula genérica para Minkowski distância de 2 pontos P e Q:

É dado por:

Distância Minkowski

A distância de Minkowski é tipicamente usada com r sendo 1 ou 2, que correspondem à distância de Manhattan e a distância euclidiana, respectivamente. No caso limitante de r alcançar o infinito , obtemos a distância de Chebychev.

Distância euclidiana Manhattan distância Distância máxima (Chebychev)

Uma maneira mais fácil de entender é com a imagem abaixo

Euclidiano (verde) vs Manhattan (vermelho)

A distância de Manhattan captura a distância entre dois pontos, agregando a diferença absoluta entre cada variável, enquanto a distância euclidiana captura a mesma, agregando a diferença quadrática em cada variável. Portanto, se dois pontos estão próximos na maioria das variáveis, mas mais discrepantes em um deles, a distância euclideana exagerará essa discrepância, enquanto a distância de Manhattan diminuirá, sendo mais influenciada pela proximidade das outras variáveis . A distância Chebychev calcula o máximo das diferenças absolutas entre os recursos de um par de pontos de dados.

A distância de Manhattan deve dar resultados mais robustos, enquanto a distância euclidiana provavelmente será influenciada por outliers. O mesmo se aplica aos valores mais altos de “p” na fórmula de distância de Minkowski. À medida que aumentamos o valor de p, a medida de distância se torna mais suscetível a perder a robustez e os outliers em poucas dimensões começam a dominar o valor da distância.

Uma observação interessante pode ser feita sobre a diferença entre eles se desenharmos um 'Círculo' usando essas diferentes medidas de distância ao invés de uma euclidiana padrão. Como sabemos, um Círculo é o local de um ponto equidistante de um determinado ponto, o centro do círculo. Agora, se usarmos medidas de distância de Manhattan ou Chebychev para medir a distância dos pontos do centro, obteremos “quadrados” em vez dos círculos “redondos” usuais.

Camberra Distância

É uma versão ponderada da distância de Manhattan. Ele mede a soma das diferenças fracionais absolutas entre as características de um par de pontos de dados e é muito sensível a uma pequena alteração quando ambas as coordenadas estão mais próximas de zero.

Canberra distância

Distância Hamming

Para variáveis categóricas (masculino / feminino ou pequeno / médio / grande), podemos definir a distância como 0 se dois pontos estiverem na mesma categoria e 1 caso contrário. Se todas as variáveis forem categóricas, você poderá usar a distância de Hamming, que conta o número de incompatibilidades.
Você também pode expandir variáveis categóricas para variáveis indicadoras, uma para cada nível da variável.
Se as categorias forem ordenadas (como pequena / média / grande), de modo que algumas categorias estejam “mais próximas” umas das outras do que outras, você poderá convertê-las em uma sequência numérica. Por exemplo, (pequeno / médio / grande) pode ser mapeado para (1/2/3). Então você pode usar a distância euclidiana ou outras distâncias para dados quantitativos.

Distância Mahalanobis

Podemos pensar na distância de Mahalanobis de um ponto ao seu centro de cluster respectivo como sua distância euclidiana dividida pela raiz quadrada da variância na direção do ponto. A métrica de distância de Mahalanobis é preferível à métrica de distância euclidiana, pois permite alguma flexibilidade na estrutura dos clusters e leva em consideração variações e covariâncias entre as variáveis.

Quando você usa distância euclidiana, você assume que os clusters têm covariâncias de identidade. Em 2D, isso significa que seus clusters têm formas circulares. Obviamente, se as covariâncias dos agrupamentos naturais em seus dados não são matrizes de identidade, por exemplo, em 2D, os clusters têm covariâncias de formato elíptico, então usar Mahalanobis sobre Euclidean será uma modelagem muito melhor.

Distância de Mahalanobis para um vetor bidimensional sem covariância

Distâncias baseadas em correlação

A distância baseada na correlação considera dois objetos semelhantes se suas características são altamente correlacionadas, mesmo que os valores observados possam estar distantes em termos de distância geométrica. A distância entre dois objetos é 0 quando eles estão perfeitamente correlacionados. Se você quiser identificar grupos de observações com os mesmos perfis gerais, independentemente de suas magnitudes, então você deve ir com a distância baseada em correlação como uma medida de dissimilaridade.

Se a distância euclidiana for escolhida, as observações com altos valores de feições serão agrupadas. O mesmo vale para observações com baixos valores de recursos.

Distância de correlação de Pearson

A correlação de Pearson mede o grau de uma relação linear entre dois perfis. A análise de correlação de Pearson é o método mais comumente usado . Também é conhecido como uma correlação paramétrica que depende da distribuição dos dados. Essa distância é baseada no coeficiente de correlação de Pearson que é calculado a partir dos valores da amostra e seus desvios-padrão. O coeficiente de correlação ' r ' toma valores de –1 (correlação negativa grande) para +1 (correlação grande e positiva).

Distância de correlação de Pearson

Existem algumas outras variantes dessa distância:

  1. Distância de Correlação Absoluta de Pearson: Nesta distância, o valor absoluto do coeficiente de correlação de Pearson é usado; daí a distância correspondente fica entre 0 e 1.
  2. Distância de correlação não centralizada: é igual à correlação de Pearson, exceto que as médias da amostra são definidas como zero na expressão para correlação não centralizada. O coeficiente de correlação não centrado situa-se entre –1 e +1 ; daí a distância fica entre 0 e 2 .
  3. Distância de correlação absoluta, não centralizada: é igual à correlação de Pearson absoluta, exceto que as médias de amostra são definidas como zero na expressão para correlação não centralizada. O coeficiente de correlação não centrado está entre 0 e +1 ; daí a distância fica entre 0 e 1.

Distância de correlação de cosseno de Eisen

É um caso especial de correlação de Pearson com x e y ambos substituídos por zero:

Distância de correlação de Spearman e Kendall

A correlação de Spearman entre duas variáveis é igual à correlação de Pearson entre os valores de classificação dessas duas variáveis; enquanto a correlação de Pearson avalia relações lineares, a correlação de Spearman avalia relações monotônicas (lineares ou não). Se não houver valores de dados repetidos, uma correlação de Spearman perfeita de +1 ou -1 ocorre quando cada uma das variáveis é uma função monótona perfeita da outra.

Intuitivamente, a correlação de Spearman entre duas variáveis será elevada quando observações têm uma semelhante (ou idêntico para uma correlação de 1) posto (ou seja etiqueta posição relativa das observações dentro da variável: 1a, 2a, 3a, etc.) entre os dois variáveis, e baixo quando as observações têm um rank dissimilar (ou totalmente oposto para uma correlação de -1) entre as duas variáveis.

A distância de classificação tau de Kendall é uma métrica que conta o número de discordâncias entre duas listas de classificação. Quanto maior a distância, mais dissimilares são as duas listas. A distância tau de Kendall também é chamada de distância de bolha de classificação, pois é equivalente ao número de trocas que o algoritmo de classificação de bolhas levaria para colocar uma lista na mesma ordem que a outra lista.

O coeficiente de Spearman é apropriado para variáveis ordinais contínuas e discretas. Tanto o ? de Spearman quanto o ? de Kendall podem ser formulados como casos especiais de um coeficiente de correlação mais geral .

Poucos ponteiros no agrupamento k-means

  1. O valor das medidas de distância está intimamente relacionado à escala na qual as medições são feitas. Portanto, as variáveis são frequentemente escalonadas antes de medir as diferenças entre observações. Isto é particularmente recomendado quando as variáveis são medidas em diferentes escalas (por exemplo: quilogramas, quilômetros, centímetros, …); caso contrário, as medidas de dissimilaridade obtidas serão severamente afetadas. A padronização faz com que os quatro métodos de medição de distâncias – Euclidean, Manhattan, Correlation e Eisen – sejam mais semelhantes do que seriam com dados não transformados. Note que, quando os dados são padronizados, existe uma relação funcional entre o coeficiente de correlação de Pearson e a distância euclidiana.
  2. k-means trabalha com variáveis contínuas. Não deve ser feito com dados de tipos mistos. Quando seus dados consistem em variáveis de tipos mistos, você pode tentar usar a distância de Gower. Há uma visão geral da distância de Gower aqui .

Não há melhor medida de distância.

Existe apenas uma melhor medida de distância para um dado conjunto de dados. A escolha da medida de distância irá influenciar o seu agrupamento, mas isso depende do conjunto de dados e no objectivo, que medem a distância é mais adequada para a sua aplicação particular.

Medidas de similaridade para dados contínuos

Referências

  1. https://pdfs.semanticscholar.org/b3b4/445cb9a2a55fa5d30a47099335b3f4d85dfb.pdf
  2. https://www.datanovia.com/en/lessons/clustering-distance-measures/
  3. https://stats.stackexchange.com/questions/81481/why-does-k-means-clustering-algorithm-use-only-euclidean-distance-metric
  4. https://arxiv.org/ftp/arxiv/papers/1405/1405.7471.pdf
  5. https://stats.stackexchange.com/questions/130974/how-to-use-both-binary-and-continuous-variables-together-in-clustering
  6. Wikipedia
  7. http://www.divingintodatascience.com/