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

Preparando Arquivos para o WEKA

Um dos maiores problemas (ainda) no WEKA sem sombra de dúvidas é a criação dos arquivos para o minerador.

Em geral os datasets em ARFF não possuem nenhum tipo de relacionamento referencial, ou mesmo relacionamento entre suas instâncias; porém, isso não é impeditivo para realização de determinadas análises no minerador. A Microsoft com o SQL Server Analysis Services em sua suíte de mineração de dados contém uma feature que comtempla esse tipo de situação chamado “Nested” que é utilizado no momento de construção do modelo de mineração. Ademais, ainda é pendente de contextos de atualização esse tipo de feature.

O WEKA utiliza como arquivo padrão para as tarefas de mineração o formato ARFF, porém o minerador pode aceitar também arquivos CSV para realização das tarefas; porém, é preciso inserir os atributos de cada instância.

Com a utilização de algumas ferramentas como ExcelToARFF ou mesmo com o próprio Excel através da conversão para ARFF e após isso inserção dos atributos.

O ARFF aceita basicamente dois tipos de datatypes que são String (Nominal) e Numeric. Geralmente o minerador trabalha com Nominal Values em tarefas de associação e classificação; e com atributos numéricos em tarefas de agrupamento; contudo isso não é obrigatório.

% Arquivo ARFF utilizado com template para o blog mineracaodedados.wordpress.com %
@relation Escola
@attribute StatusAluno { Passou, Recuperacao, Reprovado }
@attribute NotaGeral numeric
@attribute Aproveitamento numeric
@attribute BomComportamento { true, false }
@attribute ReuniaoPais { yes, no }
@data
%
% 14 Instancias
%

Passou, 85, 85, false, no
Passou, 80, 90, true, no
Recuperacao, 83, 86, false, yes
Reprovado, 70, 96, false, yes
Reprovado, 68, 80, false, yes
Reprovado, 65, 70, true, no
Recuperacao, 64, 65, true, yes
Passou, 72, 95, false, no
Passou, 69, 70, false, yes
Reprovado, 75, 80, false, yes
Passou, 75, 70, true, yes
Recuperacao, 72, 90, true, yes
Recuperacao, 81, 75, false, yes
Reprovado, 71, 91, true, no

Adaptado de Witten,I.H.(Ian H.), Data mining : practical machine learning tools and techniques – 2nd ed. Pg. 54

Para criar arquivos no excel.

Digamos que iremos criar um dataset chamado CreditRating com 6 atributos para avaliar uma carteira de crédito para mapeamento de futuros empréstimos.

Tempo no Emprego (Numérico), Ocupação (String), Tempo de Residencia(Numérico), Status de Residencia(String), Saldo Devedor(Numérico) e Informacao se o devedor pagou ou não (String)

Foi criado um dataset simples com 20 instâncias, com a seguinte distribuição:

TempoEmprego Ocupacao TempoResidencia StatusResidencia SaldoDevedor Pagou
1 ProfissionalLiberal 3 Propria 1000 Yes
2 Vendas 4 Propria 3234 No
3 Autonomo 2 Propria 233 No
12 ProfissionalLiberal 5 Financiada 9283 Yes
23 Autonomo 8 Financiada 342 No
12 Vendas 7 Propria 367 Yes
2 FuncionarioPublico 8 Propria 2109 No
6 ProfissionalLiberal 4 Financiada 245 Yes
7 Profissional 5 Aluguel 5687 Yes
9 Profissional 9 Financiada 871 Yes
8 Autonomo 10 Financiada 906 Yes
12 ProfissionalLiberal 12 Aluguel 9842 No
16 Vendas 15 Aluguel 1209 Yes
12 FuncionarioPublico 2 Financiada 934 Yes
10 FuncionarioPublico 4 Financiada 213 Yes
2 Vendas 1 Financiada 4519 No
7 ProfissionalLiberal 1 Aluguel 7239 Yes
22 FuncionarioPublico 18 Propria 1010 No
21 Vendas 15 Propria 8214 No
6 FuncionarioPublico 14 Propria 6321 No

Com essa distribuição realizada, salve o arquivo em CSV separado por vírgulas com a opção salvar como…, e após isso abra o arquivo no bloco de notas que o mesmo será aberto com o seguinte formato:

TempoEmprego ;Ocupacao ;TempoResidencia;StatusResidencia;SaldoDevedor;Pagou
1;ProfissionalLiberal;3;Propria;1000;Yes
2;Vendas;4;Propria;3234;No
3;Autonomo;2;Propria;233;No
12;ProfissionalLiberal;5;Financiada;9283;Yes
23;Autonomo;8;Financiada;342;No
12;Vendas;7;Propria;367;Yes
2;FuncionarioPublico;8;Propria;2109;No
6;ProfissionalLiberal;4;Financiada;245;Yes
7;Profissional;5;Aluguel;5687;Yes
9;Profissional;9;Financiada;871;Yes
8;Autonomo;10;Financiada;906;Yes
12;ProfissionalLiberal;12;Aluguel;9842;No
16;Vendas;15;Aluguel;1209;Yes
12;FuncionarioPublico;2;Financiada;934;Yes
10;FuncionarioPublico;4;Financiada;213;Yes
2;Vendas;1;Financiada;4519;No
7;ProfissionalLiberal;1;Aluguel;7239;Yes
22;FuncionarioPublico;18;Propria;1010;No
21;Vendas;15;Propria;8214;No
6;FuncionarioPublico;14;Propria;6321;No

Após isso, no próprio bloco de notas, substitua o ponto e virgula por somente virgula para o delimitador do preprocessador conseguir enxergar os dados.

Com isso basta inserir os atributos com as seguintes descrições, e abaixo inserir a base de dados já inserida tendo o seguinte resultado.

@relation CreditRating.symbolic
@attribute TempoEmprego numeric
@attribute Ocupacao {Autonomo, FuncionarioPublico, ProfissionalLiberal, Vendas, Profissional}
@attribute TempoResidencia numeric
@attribute StatusResidencia {Financiada, Alugada, Propria}
@attribute SaldoDevedor numeric
@attribute Pagou {yes, no}
@data

1,ProfissionalLiberal,3,Propria,1000,Yes
2,Vendas,4,Propria,3234,No
3,Autonomo,2,Propria,233,No
12,ProfissionalLiberal,5,Financiada,9283,Yes
23,Autonomo,8,Financiada,342,No
12,Vendas,7,Propria,367,Yes
2,FuncionarioPublico,8,Propria,2109,No
6,ProfissionalLiberal,4,Financiada,245,Yes
7,Profissional,5,Aluguel,5687,Yes
9,Profissional,9,Financiada,871,Yes
8,Autonomo,10,Financiada,906,Yes
12,ProfissionalLiberal,12,Aluguel,9842,No
16,Vendas,15,Aluguel,1209,Yes
12,FuncionarioPublico,2,Financiada,934,Yes
10,FuncionarioPublico,4,Financiada,213,Yes
2,Vendas,1,Financiada,4519,No
7,ProfissionalLiberal,1,Aluguel,7239,Yes
22,FuncionarioPublico,18,Propria,1010,No
21,Vendas,15,Propria,8214,No
6,FuncionarioPublico,14,Propria,6321,No

That’s all folks!

Preparando Arquivos para o WEKA

Sobre os livros e especialistas de produto em Mineração de Dados

Olá a todos!

No começo de algumas pesquisas sobre Mineração de Dados, um dos maiores percalços sem sombra de dúvidas foi (é) encontrar literatura suficientemente boa para iniciação dos estudos. Os problemas mais comuns eram (é):

  • Livros sem nenhum tipo de aplicação prática: Não adianta ter uma técnica multidisciplinar que pode revolucionar diversas formas de como nos relacionamos com os dados, se o pesquisador não tem nenhum tipo de compromisso de mostrar como essa técnica pode ser aplicada. Diferentemente da matemática pura, a Mineração de Dados não trabalha em base de axiomas e teoremas; e ela é parte de uma ciência (inteligência artificial) que detêm parte da sua segmentação na ciência humana (análise e tomada de decisão). Dessa forma é mais do que necessário além de buscar o aprimoramento teórico, buscar sim a representação da técnica através da sua aplicação prática (Há outro segmento que é da Mineração de Dados no aspecto puro, mas isso é tema para outro post);
  • Autores despreocupados com outros métodos e não vão além da tríade popular de técnicas (Associação, Classificação e Agrupamento): Esse é um problema que eu considero gravíssimo. Muitos autores não vão além do arroz com feijão quando se fala das técnicas de Mineração de Dados, seja por meio de se arriscarem a dizer algo que não tem completo domínio, e/ou não assustar os leitores menos avisados. Dessa forma, ao longo de uma revisão de literatura sempre há um sentimento de ‘Deja Vu’ na qual os autores vêm se parafraseando ao longo de páginas e mais páginas;
  • Base estatística altíssima: Na verdade isso não chega a ser um problema, e penso que isso é o que difere autores como honestidade intelectual dos aproveitadores que querem estar na ‘crista da onda’ para explorar um assunto tão complexo com ferramentas. Nesse caso, o único ponto contra é que os livros de Mineração de Dados (em geral os estrangeiros) partem de uma elipse muito grande o que pode dificultar a curva de aprendizado, levando o estudante a recorrer a literaturas mais provincianas e menos técnicas;
  • Poucas explicações de como a base matemática serve de base para a Mineração de Dados: Esse é um erro gravíssimo que eu vejo mais na literatura nacional sobre Mineração de Dados. Há livros no mercado de gente que tem PhD e que escreve um livro de Mineração de Dados sem nenhum tipo de fórmula matemática. Isso é ideal se fosse um livro para executivos ou tomadores de decisão; contudo, indicar um livro dessa natureza como de utilização acadêmica é um ato de no mínimo desonestidade intelectual;
  • Dispersão de amplo material bom que está pegando poeira em alguma editora ou sobra de congressos de mineração: Mais do que bases de dados, os estudantes de Mineração de Dados precisam de disciplinas investigativas avançadas para achar pesquisadores sérios interessados no tema, bem como materiais de altíssima qualidade, até mesmo na internet. Grande parte dos congressos de Mineração de Dados ocorre em lugares específicos o qual há um publico muito seleto (para não dizer exclusivo) o qual há uma troca de ideias que somente com muito esforço se tem acesso, principalmente aqui no Brasil.

E o que eu considero mais grave…

  • Especialistas de ‘produtos de mercado’(sic.) falando a respeito de algo seríssimo como se a Mineração de Dados fosse apenas mais uma ferramenta trivial de análise de dados: Em determinados momentos ao escutar alguns especialistas de produtos (Principalmente da Microsoft com seus MVP’s (sic.)) falando de Mineração de Dados dá a impressão que estamos falando de mais um produto como o office ou mesmo como se a mineração fosse resumida ao Addin do Excel. Entretanto, a Mineração de Dados como técnica de análise vem se consolidando cada vez mais, em especial com o fenômeno de Big Data que vem chamando a atenção das corporações que não querem perder nenhum tipo de dado, por mais trivial que seja. Esses especialistas de produto fazem uma série de webnars, webcasts, palestras falando de Clustering (Agrupamento, mas eles adoram colocar outras línguas no meio das frases para ter algum grau de sofisticação) sendo que se você falar de Distância Euclidiana o especialista de produto passa vergonha no meio do webnar só para ficar em um exemplo simples. Existe muita gente no mercado que conhece os seus produtos, bem como as técnicas; e cada a cada um ter o filtro necessário para saber o que é propaganda e o que é método matemático aplicado de forma séria, como a Mineração de Dados deve ser.

Para finalizar, é preciso ter cuidado com os recursos disponíveis que alegam serem sobre Mineração de Dados, mas na verdade são exclusivamente propaganda de ferramentas.

Sobre os livros e especialistas de produto em Mineração de Dados

A utilização do WEKA como Minerador de Dados

O WEKA (Acrônimo para Waikato Environment for Knowledge Analysis) é um software livre com licença General Public License desenvolvido pela Universidade de Waikato na Nova Zelândia para utilização em tarefas de Mineração de Dados.

Há muito escrito sobre o WEKA na web, e o objetivo desse post não é realizar uma comparação com algumas ferramentas de mercado, mas sim ressaltar algumas das boas características do WEKA.

O WEKA contém uma série de algoritmos que são desenvolvidos pela comunidade que contribuí com a ampliação do Software, já que o mesmo é desenvolvido em Java e o projeto é código aberto, o que significa que dia após dia o projeto aumenta cada vez mais já que não há restrições de bibliotecas, bem como não há nenhum tipo de corporação por trás de uma iniciativa exclusivamente acadêmica.

O WEKA conta também com uma grande flexibilidade na utilização de suas técnicas de mineração, nas quais há uma ampla variedade de algoritmos os quais contém a sua respectiva descrição, bem como de acordo com o conhecimento do analista pode representar um diferencial de acordo com a escolha do algoritmo para a base que será analisada, na qual uma representação de um algoritmo pode ter um resultado distinto de acordo com a técnica escolhida.

Dois grandes diferenciais do WEKA em relação a outras ferramentas, é que há um amplo material de referẽncia através da internet, no qual em poucos minutos já é possível utilizar o software sem nenhum tipo de problema em relação a base de conhecimento e/ou documentação. No site http://www.cs.waikato.ac.nz/ml/weka/ há toda a documentação do projeto e a descrição dos componentes que formam a Engine, e também há dois excelentes livros de referência como Data Mining: Practical Machine Learning Tools and Techniques de Hall, Witten e Frank e o Data Mining Methods and Models do Daniel Larose que são livros técnicos com exemplos práticos em WEKA.

Como pode ser visto o WEKA além de ser uma importante ferramenta de análise de dados e descoberta de conhecimento em bases de dados; possuí muitos recursos que o tornam um minerador de dados robusto, flexível e com um corpo de conhecimento muito grande; o qual pode ser muito útil em aplicações com maior grau de especificação e complexidade.

A utilização do WEKA como Minerador de Dados