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

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

Análise de dados de Tênis utilizando WEKA – Rivalidade Roger Federer x Rafael Nadal

O tênis é um dos esportes que exigem um alto grau de precisão, e tecnicamente é um dos mais difíceis, no qual a execução de um golpe errado pode definir os rumos de uma partida como um todo. Uma das verdades universais é que o tênis é um jogo no qual ganha que erra menos, e isso é uma verdade quase que absoluta.

Dentro desse pequeno cenário, há atualmente no circuito da ATP dois gênios do esporte, que são atores de uma das maiores rivalidades da história do esporte. De um lado o maior jogador de todos os tempos Roger Federer, possuidor de nada menos do que 16 Majors e é recordista absoluto em títulos dessa natureza. Dotado de um estilo de jogo clássico, como poucos consegue unir agressividade e técnica refinada em seus jogos. Do outro lado Rafael Nadal vencedor de 10 Majors, e medalhista olímpico, rei absoluto da superfície de saibro. Tem como principal característica a extrema regularidade em seus golpes, e também por unir atributos físicos dignos de maratonistas, além de ter golpes que altíssimo volume de efeito.

Esses jogadores até hoje disputaram 26 partidas em torneios oficiais onde Nadal leva vantagem de 17-9 sobre Federer. O cenário dessa análise foi realizado através de dados de jogos da ATP entre esses dois jogadores desde 2004 até o último encontro (Londres, 2011) onde foram discretizados diversos atributos de acordo com stats da ATP como número de erros não forçados, aces, break points convertidos, entre outros.

A base de dados foi gerada consolidada em Excel, e tratada para o software de Mineração de Dados WEKA, no qual foi utilizada a técnica de Agrupamento (Clustering) no qual foi formado alguns centroides que são padrões de características nas quais tem atributos com um determinado grau de correlação.

Vamos para a prática.

Base de Dados: A base de dados foi retirada do site da ATP através dos stats de confrontos entre os dois jogadores. Os atributos foram discretizados de acordo com o seu quantitativo, ou seja não foram usadas as informações de porcentagem devido ao fato de manter maior fidelidade aos dados de cada partida, bem como não haver mistura na base do quantitativo real de aproveitamento em cada um dos jogos.

Atributos como TeveTieBreak, TimePlay e Winner foram colocados, por permitir uma melhor análise relacionada a ocorrência desses acontecimentos dentro de um jogo e elaborar um padrão não supervisionado com os dados.

Tratamento no WEKA: Após a discretização dos atributos no arquivo, realizei uma conversão para o Arff (formato padrão do WEKA), e fiz o load. Como havia dados numéricos e string, a melhor alternativa para esse dataset, bem como o objetivo era mais de uma abordagem exploratória; foi utilizado a técnica de Agrupamento (Clustering) pois trata-se de um aprendizado não supervisionado.

O algoritmo utilizado foi o SimpleKMeans que tem como característica realizar o agrupamento de acordo com um número de centroides. Neste caso, foi escolhido 10 centroides para representação, haja vista que mesmo com uma quantidade baixíssima de registros há muitas nuances entre os atributos, os quais alguns poucos são determinantes para a análise.

A medida de dissimilaridade (distância) escolhida foi a Euclidiana, devido ao fato de se obter um melhor processamento pelo Engine do WEKA, bem como se buscar a distância direta entre as métricas. Dentro de 26 ocorrências entre os dois jogadores, foi escolhido que se formasse 10 centroides, os quais apresentariam características em aproximadamente todos os eventos (Tournament) os quais já houveram confrontos.

O StringSet utilizado foi o seguinte: weka.clusterers.SimpleKMeans -N 10 -A “weka.core.EuclideanDistance -R first-last” -I 500 -S 10

Resultados: Através da análise dos resultados apresentados pelo algoritmo, chegamos algumas conclusões bem razoáveis.

1 – Nadal praticamente tem ampla superioridade ao rival no confronto direto em superfícies de Saibro, no qual em todos os clusters com ocorrência de jogos no saibro o espanhol leva ampla vantagem.

2 – Em todos os agrupamentos quem ganhou o primeiro set, geralmente foi o vencedor do confronto; fator esse que pode ser determinante pensando em termos de análise dos jogos.

3 – Uma regra bem interessante é que os jogadores tem uma maior probabilidade de conseguir aces no piso de grama, já que é este no qual os mesmos obtém a maior média de acertos; em seguida.

4 – Os torneios em que os jogadores apresentam maiores dificuldades em defesa de break points são para Roger Federer o aberto da França, e para Rafael Nadal o aberto da Inglaterra.

5 – Em apenas um cluster o padrão de confronto entre os dois não foram a final dos torneios em que disputaram.

6 – No cluster que indica uma maior frequência de confrontos (Miami) os dois tenistas apresentam as maiores médias de duplas faltas, o que pode ser explicado pelo fato do torneio de Miami ocorrer no início da temporada.

É até obvio que o modelo criado não é perfeito, e há muitas imperfeições na base; como por exemplo dois clusters outliers (Hamburgo e Roma) os quais apresentam dados muito discrepantes para qualquer tipo de análise; mas é nesse momento em que entra a figura do analista de data mining que avalia de acordo com as regras de negócio; bem como realiza modificações (transformando em dados puros, para porcentagem para equilíbrio de pesos) necessárias para uma melhor análise.

PS: Esse post foi inicialmente escrito antes do jogo da data de hoje (26 Jan 11), porém foi finalizado após a vitória do Rafael Nadal por 3 x 1; no qual quem ganhou o primeiro set foi o Roger Federer, e foi na superfície dura. O Australian Open não entrou na análise devido ao algoritmo não ter considerado o número de ocorrências do mesmo (1 até o jogo de hoje). Isso mostra que os dados puros não significam muita coisa sem o analista.

PARA LER:

ATP Head to Head – http://www.atpworldtour.com/Players/Head-To-Head.aspx?pId=F324&oId=N409

DE HOON, Michiel. Similarity Measures – http://bonsai.hgc.jp/~mdehoon/software/cluster/manual/Distance.html

IOS. Euclidean and Encludean Squared Distance

HANNEMAN, Robert. Measures of similarity and structural equivalence. – http://faculty.ucr.edu/~hanneman/nettext/C13_%20Structural_Equivalence.html

WIKIPEDIA. Federer and Nadal Rivalry – http://en.wikipedia.org/wiki/Federer%E2%80%93Nadal_rivalry

DATASET e demais arquivos: http://dl.dropbox.com/u/8266208/Tennis%20WEKA%20Project.rar

Análise de dados de Tênis utilizando WEKA – Rivalidade Roger Federer x Rafael Nadal