Enciclopédia das Distâncias (Michel Deza & Elena Deza)

Para quem está interessado em conhecer mais sobre as distâncias matemáticas (ex: Encludiana, Mahalanobis, ou a Minkowski) esse livro é essencial.

É um compêndio de inúmeras distâncias matemáticas, e além disso contém inúmeras informações de quais distâncias devem ser usadas de acordo com inúmeros contextos.

Enciclopédia das Distâncias (Michel Deza & Elena Deza)

Livro – Encyclopedia of Distances – Michel Marie Deza, Elena Deza

As técnicas de agrupamento (clustering) são provavelmente uma das disciplinas mais difíceis em relação ao aprendizado/aplicação prática tratando-se de mineração de dados. As técnicas de clustering tem diversas intersecções em relação ao conjunto de disciplinas em sua concepção: estatística, matemática, geometria, etc; e uma importante parte da construção dos clusters (indução gráfica) é bastante relacionado com as medidas de distâncias sejam elas de similaridade (relações entre os pontos da base de dados) e dissimilaridade (relações baseadas nas diferenças entre os pontos).

As medidas de distância são fundamentais em termos de clusters seja no seu custo computacional, complexidade e representação gráfica para análise; a qual dependendo da medida de distância utilizada pode apresentar mudanças significativas em termos de identificação de outliers,  formato dos clusters na camada de apresentação, e até mesmo na formação de vizinhanças entre os grupos de pontos de dados .

Esse livro tem tudo isso bem explicado, com pormenores que vão até o nível mais baixo em relação a aprendizado de máquina; na qual é explicado as importancias, detalhes matemáticos e características de cada uma das medidas de distâncias apresentadas.  

O livro é bem escrito e com as mais diversas medidas apresentadas oferece um leque bem vasto de possibilidades para análise de dados, tudo em linguagem bem acessível e com uma notação matemática bem simples.  É uma boa pedida para quem deseja sair do arroz e feijão das técnicas de cluster (Distância Euclideana, e Manhattan).

O livro não é recomendado para quem não tem familiaridade com análise de clusters, ou não tem endentimento básico de matemática; porém, não é impeditivo.

Encyclopedia of Distances – Michel Marie Deza, Elena Deza

Livro – Encyclopedia of Distances – Michel Marie Deza, Elena Deza

Taxi!

Essa coluna de Joe Malkevitch (York College (CUNY)) foi publicado na American Mathematical Society e aborda um tema bastante relevante em mineração de dados que é a geometria da medida de distância Taxicab (Manhattan). A coluna coloca em aspectos práticos a definição e aplicação dessa medida de distância apresentando exemplos de como funciona e as suas aplicações. O mais interessante sobre tudo, é que o entendimento dessa parte da matemática abre um grande leque de possibilidades em relação ao sair do lugar comum (leia-se, Distância Euclideana) no desenvolvimento de uma análise de agrupamento; ou mesmo em um projeto de mineração de dados no qual não  todos os dados não são discretizados, ou esses dados sofram uma variação de range muito alta devido a inúmeros outliers.

Feature Column from the AMS

Taxi!

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 classication 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)²).

Distância Manhattan: |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.

Medidas de Distância