Medidas de Distância

Um dos tópicos mais importantes no momento de se realizar uma análise de agrupamento sobre a base de dados é em relação à medida de distância adotada.

Diversos fatores são levados em consideração quando se faz uma análise como inferência estatística, métricas adotadas para composição do modelo, quantidade de dados a serem minerados; o que exige conhecimento por parte do analista de qual medida de distância escolher de acordo com o domínio do problema e o conjunto de dados, ou se não houver escolha ao menos ter consciência do tipo de resultado que  pode ser obtido de acordo com a medida de distância implantada.

As medidas de distância de uma maneira geral podem ser definidas como medidas de similaridade, e dissimilaridade; na qual a primeira é para definir o grau de semelhança entre as instâncias e realizam o agrupamento de acordo com a sua coesão, e a segunda de acordo com as diferenças dos atributos das instâncias. Como forma de reduzir o escopo de assuntos tratados, esse post irá adotar abordar somente as distâncias de similaridade mais comuns que são a Distância Euclidiana e a Distância Manhattan.

WITTEN e FRANK (2005) realizam uma consideração sobre a utilização das medidas de similaridade:

In instance-based learning, each new instance is compared with existing ones using a distance metric, and the closest existing instance is used to assign the class to the new one. This is called the nearest-neighbor classi__fi__cation method. (WITTEN e FRANK, 2005 p.78)

A Distância Euclidiana é definida como a soma da raiz quadrada da diferença entre x e y em suas respectivas dimensões.

Já a Distância Manhattan tem uma definição mais simples na qual é apenas a soma das diferenças **entre x e y em cada dimensão**.

Abaixo segue a representação matemática dessas duas medidas:

Distância Euclideana: √((x1 - x2)² + (y1 - y2)²).

Realizando uma analogia entre a diferença entre essas duas distâncias, vamos imaginar uma a rota de GPS para dois veículos, uma para um carro e outra para um helicóptero. A Distância Euclidiana seria o segmento de uma reta na qual indicaria uma possível rota de helicóptero (na qual não haveria preocupação com as ruas já que é um veículo aéreo, e geometricamente seria a hipotenusa de um triângulo) e a Distância Manhattan seria um segmento de retas na vertical quanto na horizontal semelhante a uma rota de carro (já que esse obedece o sentido das ruas, e devido à esse comportamento essa medida de distância é também conhecida como City Block, e  geometricamente seriam a soma dos catetos).

Um dos problemas para a utilização de técnicas de agrupamento é a utilização de dados nominais em seus atributos, os quais por não ter uma métrica implícita dificultam o trabalho dos algoritmos em termos de atribuição de pesos e valores para formação dos clusters. WITTEN e FRANK (2005) realizam uma observação sobre essa ocorrência de dados nominais em bases de dados para agrupamento.

When nominal attributes are present, it is necessary to come up with a “distance” between different values of that attribute. What are the distances between, say, the values red, green, and blue? Usually a distance of zero is assigned if the values are identical; otherwise, the distance is one. Thus the distance between red and red is zero but that between red and green is one. However, it may be desirable to use a more sophisticated representation of the attributes. For example, with more colors one could use a numeric measure of hue in color space, making yellow closer to orange than it is to green and ocher closer still. Some attributes will be more important than others, and this is usually reflected in the distance metric by some kind of attribute weighting. Deriving suitable attribute weights from the training set is a key problem in instance based learning. (WITTEN e FRANK, 2005 p.78)

Um dos trabalhos futuros para melhorias das medidas de distância são pesquisas na área atribuição dinâmica de pesos para distribuição dos clusters, no qual ao invés dos atributos deterem pesos fixos, de acordo com a sua distribuição e incidência seriam atualizados de forma incremental, WITTEN e FRANK afirmam abaixo:

The next improvement in instance-based learning is to learn the relevance of each attribute incrementally by dynamically updating feature weights. (WITTEN e FRANK, 2005 p.238)

Em termos relativos a utilização da distância euclideana se aplica melhor a dados não padronizados (ou seja dados que não tem nenhum tipo de tratamento de adaptação de escala); e devido a isso o resultado final é insensível a outliers (exceções, ou dados com uma diferença muito grande em relação à média do dataset). Uma desvantagem sobre essa medida de distância pode acontecer se houver diferença de escala entre as dimensões; por exemplo, se no eixo X houver a distância em kilometros, e no eixo Y a distância estiver em centímetros pensando em termos cartográficos. No momento em que houver a transformação de escala (ou seja a conversão de Cm para Km) os resultados euclideanos (que se baseiam nos quadrados e na raiz) sofrem uma influência muito grande das dimensões que possuem os maiores valores. (Adaptado de STATISTICA)

Já para a Distância Manhattan, além do fato que os outliers são igualmente desconsiderados; entretanto, não há influência de escala (dentro do conjunto de dados) sobre o resultado já que não há elevação ao quadrado dos valores de X e Y.

Concluíndo, na análise de agrupamento é importante saber qual o tipo de medida de distância utilizar de acordo não só com os resultados esperados, mas também analisando todo o tipo de dado que será minerado; pois, como vimos este também exerce influência no resultado final e se não levado em consideração pode tornar a análise de dados enviesada e consequentemente levando a decisões erradas.

REFERÊNCIAS

WITTEN, Ian H., FRANK, Eibe. Data Mining : practical machine learning tools and techniques. 2ª Edição – (2005). Morgan Kaufmann series in data management systems. ISBN: 0-12-088407-0

JAIN, A.K.; MURTY, M.N.; FLYNN, P.J. Data Clustering: A Review. ACM Computing Surveys, Vol. 31, No. 3, September 1999

STANFORD University. Curso CS345 — Lecture Notes - 11 - Clustering, Part I. 2004

OLIVEIRA, Luiz Eduardo S. Inteligência Computacional: Tipos de Aprendizagem. Disponível em « http://www.ppgia.pucpr.br/~soares » Acessado em 10 Jun 10

Paul E. Black, “Manhattan distance”, in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 31 May 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/manhattanDistance.html

Paul E. Black, “Euclidean distance”, in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/euclidndstnc.html

Stanford University. Heuristics Program. Disponível em «http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html » Acessado em 10 Mar 12.

STATISTICA. Cluster Analysis. Disponível em «http://www.statsoft.com/textbook/cluster-analysis/#d » Acessado em 10 Mar 12.