Redes Neurais Auto-Organizáveis - SOM

Nest post, irei discutir um pouco sobre as redes neurais auto-organizáveis (Self-Organized-Maps -SOM), também conhecidas como Mapas de Kohonen ou mapas topográficos.

Até agora, meus artigos sobre redes neurais focaram no campo de aprendizado supervisionado, isto é, o aprendizado pelo qual apresentamos um conjunto de padrões a uma rede neural em conjunto com as saídas desejadas. A rede então ajusta os pesos visando obter as saídas corretas em função das entradas. Entretanto, vamos supor que não temos de antemão o conjunto de saídas desejadas. E agora ? Como podemos fazer com que a rede neural nos traga alguma informação útil ? Isto se chama o aprendizado não supervisionado. A tarefa agora é explorar as semelhanças entre os exemplos de entrada e agrupar padrões parecidos sem conhecer as classes de antemão. Algumas razões pelo qual escolhemos este método são:

• Agrupamento de padrões (Clusters)
• Redução de dimensionalidade
• Descoberta de correlações escondidas entre os dados (mineração de dados)
• Compressão de dados (Extração de características)
• Classificação
  
  

A rede SOM é uma rede neural de 2 camadas que aceita padrões de N-dimensões como entrada e os mapeia para um conjunto de neurônios de saída, o qual representa o espaço dos dados a serem agrupados. O mapa (camada) de saída, que é tipicamente bi-dimensional, representa as posições dos neurônios em relação aos seus vizinhos. A idéia é que neurônios topologicamente próximos respondam de maneira semelhante a entradas semelhantes. Para isso todos neurônios da camada de entrada são todos conectados aos neurônios de saída.

Modelo de uma rede SOM

Os passos do algoritmo de treinamento do SOM é simples:

1. Inicialize os pesos com valores aleatórios.
2. Apresente o padrão de entrada à rede.
3. Escolha o neurônio de saída com maior estado de ativação (Neurôno "vencedor").
   
4. Atualize os pesos dos neurônios vizinhos ao neurônio vencedor, usando um fator de aprendizado (Geralmente baseado no raio de vizinhança e taxa de aprendizado).
5. Reduza o fator de aprendizado monotonicamente (linearmente).
6. Reduza o raio de vizinhaça monotonicamente (linearmente).
7. Repita os passos a partir do passo 2 até que a atualização dos pesos sejam bem poucas.
   
   
   

O tamanho de vizinhaça irá inicialmente incluir todos neurônios da camada, e sendo reduzindo progressivamente durante a execução do treinamento, até incluir apenas o próprio neurônio vencedor.

Para descrever o treinamento acima, apresentarei um exemplo de uma solução de um problema com a rede SOM. O exemplo consiste de um conjunto de 25 alimentos, onde a rede SOM irá tentar agrupá-los em regiões de similaridade, baseado em três parâmetros, que são as informações nutricionais do alimento: Proteínas, carboidratos e gordura.

Logo, o desafio para esta rede SOM é reduzir os dados contendo três dimensões para apenas 2 dimensões, sem perda de informação. As redes SOM fazem isso automaticamente identificando as características diferenciais que terão maior efeito no resultado final do treinamento da rede.

O conjunto de exemplos de entrada segue abaixo:

Após executada a rede SOM com este conjunto de dados, os alimentos são posicionados em um plano de 10 x 10 agrupados em regiões de acordo com suas semelhanças. Uma representação gráfica do resultado é apresentado abaixo:

Agrupamento de regiões

Como o mapa de características agrupou os itens, reduzindo as três dimensões para apenas 2 dimensões ? Bem, um número de regiões foram geradas. Por exemplo, água, que não contém nenhuma proteína, carboidratos ou gordura foi empurrado para o canto direito superior. Seguindo para o canto superior esquerdo, o açúcar que é formado praticamente de carboidratos, foi posicionado. No canto inferior direito, manteiga reina soberana, sendo composta inteiramente por gordura. Finalmente, o canto esquerdo inferior é ocupado por filé de atum e frango assado, que contêm a maior concentração de proteína em relação aos alimentos apresentados. Os alimentos restantes são distribuídos entre esses extremos, onde os alimentos "fast food" ocupam a zona do centro.

Podemos observar que a rede SOM conseguiu agrupar em regiões os alimentos de acordo com as informações nutricionais. Podemos inferir 4 tipos de grupos: O grupo formado pelos padrões onde a proteína foi a característica determinante, outro pela gordura como característica predominante, e carboidratos como determinante. Por fim o último grupo seriam os alimentos na região central formados por alimentos formados por quantidades balanceadas dos 3 componentes acimas demonstrados. Isso que acabamos de fazer foi uma análise de dados e extração de informações úteis de um conjunto de dados brutos: Mineração de dados.

Abaixo disponibilizo o código em Python da rede SOM, o qual você poderá modificar ou alterar o conjunto de entradas. Tente adicionar mais dimensões no conjunto de entradas (novas infomações nutricionais) e observe os resultados. É claro que não é sempre óbvio ver o que está acontecendo, especialmente com um grande número de dimensões. Entretanto, eventualmente você poderá concluir, e até as vezes inesperadamente, alguma correlação entre os dados. Isso é a magia da mineração de dados!

Não irei exibir o código aqui no site, pois é um pouco grande, mas deixarei o link para download. Espero que usufruam bem e ajudem no seu aprendizado de redes neurais!

Até a próxima,

Marcel Pinheiro Caraciolo

Introdução à Inteligência de Enxame - Otimização por Enxame de Partículas (PSO)

Olá pessoal,

Neste novo tutorial abordarei um novo ramo na área de inteligência artificial, e de certo modo, com grande motivação. Não que os outros artigos não tenham sido motivantes, mas é justificado pelo fato que este tutorial é baseado na área de conhecimento que preparei minha tese de conclusão de curso de graduação: Multi-Ring: Uma nova topologia para o algoritmo de otimização por enxame de partículas (PSO).

Mas antes de entrarmos em detalhes sobre o que é PSO ou enxame de partículas, é necessário entendermos o conceito de inteligência de enxame (swarm intelligence).

Enxame de formigas colaborando para criar uma ponte viva.

O que é Inteligência de enxame ?

Swarm Intelligence (Inteligência de enxame) é o termo utilizado para designar sistemas de inteligência artificial onde o comportamento coletivo dos indivíduos em uma população causa simples soluções coerentes ou padrões a surgir.

O termo "enxame" (ou população) é utilizado de forma genérica para se referir a qualquer coleção estruturada de agentes capazes de interagir. O exemplo clássico de um enxame é um enxame de abelhas. Entretanto, de maneira similar podemos considerar também que outros sistemas, como por exemplo uma colônia de formigas, podem ser vistas como um enxame, onde os agentes são as formigas; uma revoada de pássaros que é um enxame, onde os agentes são os pássaros e até um engarrafamento, onde os agentes são os carros. A noção de enxame sugere um aspecto de movimento coletivo no espaço, todavia, como em um enxame de pássaros, estamos interessados em todos os tipos de comportamentos coletivos, não somente espacial.

Logo, podemos dizer que as interações coletivas de todos os agentes dentro do sistema muitas vezes leva a algum tipo de comportamento ou inteligência coletiva. Este tipo de inteligência artificial inclui qualquer tentativa de projetar algoritmos ou dispositivos distribuídos de solução de problemas sem ter um controle centralizado, inspirado no comportamento coletivo de agentes sociais e outras sociedades animais.

A inteligência coletiva é uma propriedade de sistemas compostos por agentes não (ou pouco) inteligentes com capacidade individual limitada, capazes de apresentar comportamentos coletivos inteligentes. Tais comportamentos seguem as seguintes propriedades:

• Proximidade: Os agentes devem ser capazes de interagir .

• Qualidade: Os agentes devem ser capazes de avaliar seus comportamentos.

• Diversidade: Permite ao sistema reagir a situações inesperadas.

• Estabilidade: Nem todas as variações ambientais devem afetar o comportamento de um agente.

• Adaptabilidade: Capacidade de se adequar a variações ambientais.
  

Exemplos de sistemas de inteligência de enxame

Otimização por Colônia de Formigas (ANT Colony Optimization - ACO)

O comportamento da colônia de formigas tem sido um dos mais populares modelos de comportamento de enxame. Formigas por si só podem parecer agir de forma aleatória e sem qualquer efeito discernível, mas quando a interação entre as formigas são tomadas em conjunto, emerge uma inteligência coletiva e de comportamento que tem a capacidade de resolver uma série de problemas. A idéia por trás deste algoritmo é a busca de um melhor caminho em um conjunto de rotas baseado no comportamento das formigas procurando um caminho entre o seu formigueiro (colônia) e o local do alimento. Uma técnica probabilística muito poderosa para resolver problemas computacionais de otimização.

O algoritmo de otimização por colônia de formigas já foi aplicada na solução de diversos problemas de otimização combinatória nos últimos anos, como roteamento de otimização de redes de comunicação, programação de fábricas e roteamento de veículos. Não entraremos em detalhe agora sobre o ACO (Ant Colony Optimization) já que não é o foco deste artigo, mas fiquem à vontade para descobrir mais sobre o algoritmo e sua implementação. Em outras oportunidades poderemos detalhar mais este algoritmo. Mais informações sobre o mesmo podem ser encontradas neste link.

Este artigo irá tratar de outro algoritmo popular na área de inteligência de enxame , o algoritmo de otimização por enxame de partículas (PSO).

Otimização por enxame de partículas (Particle Swarm Optimization - PSO)

O algoritmo de otimização por enxame de partículas, por outro lado, é um tipo de inteligência de enxame inspirado no comportamento de bandos de pássaros. A busca por alimentos e a interação entre aves ao longo do vôo são modeladas como um mecanismo de otimização. No caso, a área sobrevoada é equivalente ao espaço de busca e encontrar o local com comida corresponde a encontrar a solução ótima. O algoritmo é modelado por pássaros (doravante chamados de partículas) que fazem uso de sua experiência e da experiência do próprio bando para encontrar a melhor região do espaço de busca.

Aves voando "alinhadas" em busca de alimento

Há anos vem sendo estudado o comportamento social de alguns grupos de animais como a organização de abelhas, formigas e pássaros na busca de alimentos ou novos locais para estabelecer sua nova moradia. Este último grupo, em especial despertou um grande interesse de alguns pesquisadores, na década de 80, onde se destaca dentre eles o biológo Frank Heppner. Após diversas observações sobre o comportamento de bando de pássaros em revoada, Heppner decidiu modelar aquela inteligência coletiva para usá-la em métodos de busca para solução de problemas. Os estudos de Heppner consideravam que o comportamento de várias espécies de pássaros, em bando ao longo do vôo, fazia o uso de alguma lógica e de alguma forma de comunicação. Após vários estudos e observações, Heppner descreveu o raciocínio por trás daquele comportamento, qualificando-o como comportamento social.

James Kennedy e Russel Eberhart, inspirados no comportamento social dos pássaros estudados por Heppner, desenvolveram uma técnica de otimização que veio a ser conhecida como enxame de partículas. Essa denominação se deu, pois se notou que o modelo escrito por Heppner demonstrava características de um enxame inteligente, onde seus membros que apresentavam tal comportamento foram generalizados para o termo partículas.

Não só o nome do algoritmo, como os demais aspectos do modelo estudado por Heppner ganharam uma nova conotação. Fazendo uma analogia, o termo partícula foi adotado para simbolizar os pássaros e representar as possíveis soluções do problema a ser resolvido. A área sobrevoada pelos pássaros é equivalente ao espaço de busca e encontrar o local com comida, ou o ninho, corresponde a encontrar a solução ótima.

Para que o bando de pássaros sempre se aproxime do objetivo, ao invés de se perder ou nunca alcançar o alvo focado, utiliza-se o indicador denominado fitness, função que irá avaliar o desempenho das partículas. Para alcançar o alvo focado, sejam os alimentos ou os ninhos, os pássaros fazem uso de suas experiências e da experiência do próprio brando.

O termo indicador da experiência ou conhecimento individual de cada partícula, isto é, seu histórico de vida, é o pbest. Em uma abordagem mais simples, o responsável por representar o conhecimento do enxame como um todo é o gbest. A Tabela 1 apresenta de forma resumida as nomenclaturas descritas acima:

O algoritmo de técnica de otimização por enxame de partículas é um algoritmo que possui uma população de partículas, onde cada partícula representa uma possível solução para o problema de otimização. Cada partícula do exame pode ser representada por um objeto que possui associado a ele um vetor posição, isto é, a posição da partícula no espaço de busca, e um vetor velocidade, responsável por guiar as mudanças da posição das partículas durante a execução do processo.

A idéia é que as partículas voem pelo espaço de busca (mudanças de posição) tendo suas velocidades atualizadas dinamicamente de acordo com o histórico das experiências individuais e coletiva de todo o enxame. Logo, a evolução do algoritmo do PSO está associada à trajetória percorrida pelo enxame e ao tempo gasto para encontrar a melhor solução do problema.

O algoritmo básico de otimização por enxame de partículas pode ser descrito brevemente utilizando os seguintes passos: dada uma população inicial de partículas, atualiza-se o vetor posição a partir do vetor velocidade de cada partícula até que se atinja o critério de parada pré-definido. A figura abaixo ilustra essa lógica:

Fluxograma-Algoritmo PSO

O enxame é inicializado com os valores dos vetores de velocidade e posição gerados aleatoriamente. A primeira iteração do algoritmo inicia com a atribuição de valores aos parâmetros da equação de velocidade. Definem-se então os valores referentes ao enxame, constantes e o critério de parada. Tendo já definido os valores para posição das partículas e suas respectivas velocidades, aplica-se o cálculo do fitness a cada partícula desta população. Conforme explicado anteriormente, o fitness avalia o desempenho da partícula. Com as partículas do enxame avaliadas, extraem-se os pbest e o gbest, isto é, a melhor posição encontrada pela partícula e pelo enxame. Depois as velocidades e as posições de cada partícula do enxame são atualizadas. Diante das novas posições, caso o critério de parada tenha sido atingido, a solução do problema encontrada é apresentada. Caso contrário, aplica-se novamente o fitness a este enxame, atualizam-se os valores de pbest e gbest, caso seja apresentada uma solução melhor, seguido da velocidade e posição de cada partícula do enxame. O laço prossegue até o critério de parada ter sido atingido.

Existem duas variantes bastante utilizadas na literatura para a escolha do critério de parada do algoritmo PSO. Uma é pelo número de iterações, ou seja, quando o algoritmo chega ao fim por que atingiu a última iteração. A outra é pela função de avaliação (Fitness), ou seja, quando o algoritmo chegou ao fim por que alcançou um valor pré-definido para a função.

Outro componente importante que influencia no desempenho do algoritimo PSO é a estrutura ou topologia da comunicação das partículas. Ela rege como as partículas do enxame trocam informações e se comunicam. Logo, a escolha da topologia influencia na avaliação da velocidade das partículas. A depender de como as partículas se comunicam entre si e do problema a ser tratado, a busca pela solução ótima pode priorizar tanto a velocidade de convergência, a qualidade da solução ou ambas. As principais topologias utilizadas como mecanismos de comunicação entre as partículas são: a topologia global e a topologia local. A figura abaixo apresenta a estrutura de tais topologias.

a) Topologia local b) Topologia Global

Na topologia local, conforme ilustrado na figura a), o enxame está organizado em formato de anel e cada partícula deste possui dois vizinhos. Logo, a partícula troca informações apenas com seus vizinhos diretos. Embora a troca de informação entre as partículas seja mais lenta, esta estrutura provê uma melhor qualidade de soluções para problemas multimodais em comparação ao mesmo provido pela topologia global, visto a seguir.

Na topologia global, conforme ilustrado na figura b) acima, o enxame está organizado em formato estrela e todas as partículas estão conectadas entre si. Esta topologia utiliza o mecanismo de vizinhança global, também denominado de gbest para a troca de informação. Ao contrário da topologia anteriormente descrita, esta topologia permite uma convergência mais acelerada, visto que a informação da melhor posição é disseminada rapidamente entre todas as partículas do enxame,porém não garante a qualidade da solução obtida. Nestes casos o algoritmo pode atingir um mínimo local, devido a sua convergência precoce.

Depois dessa breve introdução sobre o algoritmo PSO, vamos agora vê-lo em execução. Iremos utilizar o PSO implementado em Python para solucionar um problema matemático de otimização: a minimização da função esfera (sphere). O objetivo é encontrar a solução ótima, que para esta função seria o seu mínimo global localizado pelo ponto (x,y) através das coordenadas (0,0).

Gráfico em Três dimensões da função esfera

Como podemos observar acima no gráfico plotado da função sphere, que o mínimo desta função encontra-se na região mais baixa (vértice inferior) da função esfera, e é a solução desejada a ser obtida pelo algoritmo de otimização por enxame de partículas.

Para este problema, padronizamos as fronteiras do espaço de busca, a região de inicialização das posições das partículas e o número de dimensões. Utilizamos também uma variação do PSO, com o fator de enxugamento (constriction factor - CONSTRICTED) no cálculo do vetor velocidade, o qual tem obtido um grande desempenho para solução de problemas multi-modais difíceis. A topologia utilizada para a solução deste problema foi a topologia global (todas as partículas conectadas entre si), o qual é bastante utilizada na literatura.

Todo o enxame é inicializado aleatoriamente na sub-região do espaço de busca disponível longe da solução ótima em todas as dimensões de acordo com a função a ser minimizada, neste caso, longe da posição (0,0).

Ao iniciar a execução do PSO, podemos observar o estado das partículas distribuídas aleatoriamente na região do espaço de busca com um alto valor de fitness ( O objetivo é minimizar a função, ou seja foca na redução do fitness). Vejam o histograma/gráfico abaixo:

Histograma -Distribuição Fitness x Partículas- (Iteração: 0)

Distribuição das partículas no espaço de busca (Iteração: 0)

Podemos inferir que há uma dispersão na distribuição das partículas com altos valores de fitness, o que significa que as partículas são inicializadas aleatoriamente em regiões distantes da solução ótima.
A simulação do algoritmo PSO é executada por 10.000 iterações, o qual no fim da mesma, obtemos os seguintes resultados:

Simulação do PyPSO para a solução do problema Sphere

Podemos observar pela figura acima, que após 9000 iterações, o melhor fitness encontrado é o valor 4.46.. e-164 e a melhor posição com o valor 3.03...e-83, ou seja, aproximadamente 0.00. Isto prova que o algoritmo convergiu até a solução ótima, isto é, as partículas se moveram pelo espaço de busca em direção à região que contém a solução ótima, o mínimo global da função matemática o qual estamos tentando minimizar. Claro, que o algoritmo consegue convergir bem antes que 9000 iterações, mas a fim de ilustrar o desempenho do PSO, decidimos executar com 10.000 iterações.

Plotando o histograma de distribuição de fitness e o gráfico da posição das partículas no fim da execução do algoritmo PSO, podemos concluir que os fitness de cada partículas estão com valores na ordem de grandeza e -160, bem próximo ao valor 0.0, o que significa que as partículas convergiram para a solução ótima, pela trajetória no espaço de busca. Observer também o gráfico de distribuição das posições das partículas na iteração 10.000, o qual ilustra as partículas concentradas numa região ao redor do ponto ótimo localizado nas coordenadas (0,0). Embora este seja um estudo de caso, demonstramos o poder do algoritmo PSO que se mostra eficiente na solução de problemas de busca e otimização de alta dimensionalidade.

Histograma - Distribuição de Fitness das partículas (Iteração: 10000)


Distribuição das posições das partículas na região de busca (Iteração: 10000)

Segue abaixo, o código principal utilizado para este experimento:

#Pso Demo

from pypso import Pso
from pypso import Consts
from pypso import GlobalTopology

#This is the Sphere Function
def sphere(position):
    n = len(position)
    total = 0.0
    for i in xrange(n):
        total += (position[i] ** 2.0)
    return total

#Parameters
dimensions = 30
swarm_size = 30
timeSteps = 10000

# PSO Instance

pso = Pso.PSO()
pso.setPsoType(Consts.psoType["CONSTRICTED"])
pso.setTimeSteps(timeSteps)
pso.setTopology(GlobalTopology.GlobalTopology(swarm_size,dimensions))

# The evaluator function (objective function)
pso.setFunction(sphere)
pso.initializeBounds(dimensions)
pso.definePositionBounds(0, dimensions, (-100.0, 100.0))
pso.defineInitialPositionBounds(0,dimensions, (50.0,100.0))
pso.defineVelocityBounds(0,dimensions,100.0)

#Do the swarm movement, with stats
#dump frequency of 10 timeSteps
#import psyco

#psyco.full()

pso.execute(freq_stats=20)

(Código PSODemo.py)

Na época da execução desta simulação, tomei a iniciativa de construir um framework (ainda em desenvolvimento - versão 0.1) denominado PyPsoBox -Python PSO Toolbox- para execução de testes e avaliação de desempenho de algoritmos de otimização por enxame de partículas (PSO) e suas variações. O framework está sendo construído em Python e com suporte apenas para plataformas Windows. Em breve, novas funcionalidades serão adicionadas ao projeto que é gratuito e open-source. Todos estes gráficos acima foram gerados através do framework, que tem suporte para plotagem de gráficos de análise de simulação. Em um próximo post, disponibilizarei um tutorial de como usar o framework para simulações.

O projeto está hospedado no Google Code Hosting e o código está acessível através deste link.

Quero agradecer especialmente ao colega Christian S. Perone, criador do projeto PyEvolve (Um Framework similar implementado em Python para algoritmos genéticos). O trabalho dele serviu-me como forte inspiração para o meu trabalho.

Quaisquer dúvidas, dicas, sugestões para este artigo, framework, fiquem à vontade.

Até a próxima,

Marcel P. Caraciolo

[Artigo] Introdução a Árvores de decisão para classificação e mineração de dados

Um dos maiores dilemas enfrentados por quaisquer sistemas de tomada de decisão é determinar um meio eficiente para produzir classificadores a partir de base de dados em relação ao tempo de processamento e à forma de representação simbólica simples e compreensível que facilite a análise do problema em questão.

Este artigo introduz uma ferramenta bastante popular no processo de descoberta de conhecimento em um banco de dados e consequentemente no auxílio na tomada de decisões : as Árvores de decisão.

Os classificadores baseados na árvore de decisão são um dos ramos na área de inteligência artificial. Mais especificamente, eles pertencem ao sub-campo de aprendizagem de máquina. Isto se deve à sua habilidade de aprender através de exemplos com o objetivo de classificar registros em uma base de dados.

Irei abordar os conceitos iniciais sobre árvores de decisão e como elas podem auxiliar no processo de tomada de decisões através de um exemplo prático. Para isso, usarei uma das heurísticas mais conhecidas durante o processo de aprendizagem para construção da árvore de decisão mais eficiente. E para o desfecho deste artigo, demonstrarei através de implementação em Python uma simples árvore de decisão.

"O seu sucesso depende de fazer escolhas de forma inteligente."

O que são Árvores de decisão ?

Amplamente utilizadas em algoritmos de classificação, as árvores de decisão são representações simples do conhecimento, e um meio eficiente de construir classificadores que predizem ou revelam classes ou informações úteis baseadas nos valores de atributos de um conjunto de dados. Eles são muito úteis em atividades de mineração de dados, isto é, o processo de extração de informações previamente desconhecida, a partir de grandes bases de dados. Aplicações desta técnica podem ser vista em diversas áreas, desde cenários de negócios até sistemas de piloto automático de aeronaves e diagnósticos médicos.

Uma árvore de decisão é essencialmente uma série de declarações if-elses, que quando aplicados a um registro de uma base de dados , resultam na classificação daquele registro. O mais interessante sobre o programa de árvores de decisão não é a sua construção a partir de classificação de um conjunto de treinamento, e sim a sua habilidade de aprendizado. Quando o treinamento é finalizado, é possível alimentar sua árvore de decisão construída a partir de exemplos com novos casos a fim de classífica-los.

É uma das estruturas de dados mais fácies de entender com uma boa representação gráfica. A figura 1 abaixo ilustra um exemplo de árvore de decisão.

Figura 1. Exemplo de árvore de decisão

Observe que a estrutura realmente é na forma de árvore. Dessa maneira, é possível utilizar técnicas recursivas para criar e percorrer a árvore de decisão. Você poderá utilizar quaisquer conceitos de representação de árvores aprendidos durante o seu curso de estrutura de dados para representar sua árvore. Neste artigo, para deixar as coisas bem simples, construirei a minha árvore de decisão apenas com objetos do tipo dicionário em Python.

Entendendo o problema...

Neste exemplo, são trabalhados objetos que relatam as condições propícias de uma ação de marketing baseado em uma análise demográfica do comportamento de clientes, onde se analisa se os mesmos compram ou não compra seus produtos. Para isto, é considerado um conjunto de exemplos para treinar a árvore de decisão. Considere que, os dados vieram de uma pesquisa por e-mail anônima e que existem alguns positivos (os que compram) e outros negativos (os que não compram). Depois de organizar toda essa massa de dados, chegamos a seguinte tabela:

A partir de uma árvore de decisão é possível derivar regras. As regras são escritas considerando o trajeto do nó raiz até uma folha da árvore. Estas regras determinam como as árvores classificam os registros de uma base de dados. Com basen a árvore de decisão apresentada na figura 1, pode-se exemplificar a derivação de regras. Dois exemplos de regras obtidas a partir desta árvore são mostradas a seguir: Iniciando do nó-pai (Age), verifica que o valor do atributo do primeiro exemplo casa com o valor 36-55, o qual desce para o próximo nó da árvore (Marital Status) e repete o processo até finalmente chegar a um nó-folha (um nó sem filhos). Este nós abriga a resposta para a questão de se o cliente irá ou não comprar o produto (Neste exemplo, o cliente irá comprar, porque seu estado civil ("marital status") é solteiro.

Se Age = 36-55 e Marital Status= single então Class= will buy .

É interessante também observar que este tipo de operação de derivação de regras é feita sobre um processo recursivo (não necessariamente a mais eficiente para o programa, mas é de forma elegante).

A árvore de decisão apresentada acima é uma de várias árvores que poderiam ser construídas para solucionar o problema acima apresentado. A tarefa de achar a melhor árvore de decisão é um problema NP-completo, isto é, que o tempo de processamento necessário para achar a "melhor" árvore de decisão pode ser exponencial a medida que o número de de dados usados no treinamento da rede. Embora, pareça ser impossível encontrar a menor árvore de decisão em um tempo considerável, é possível encontrar uma que seja "pequena suficiente", satisfatória a partir do uso de heurísticas especiais. A tarefa da heurística é realizar esta tarefa escolhendo o "melhor próximo" atributo que divida o conjunto de dados baseado em um critério pré-definido.

Há vários algoritmos de construção de árvore de decisão (C4.5,CART,CHAID, entre outros). Entretanto, para este artigo escolhemos o mais popular deles: a heurística ID3, para a escolha dos "melhores próximos" atributos baseados em conceitos encontrados em teoria da informação.

O algoritmo ID3 usa o conceito de entropia para calcular qual o melhor atributo será utilizado para dividir os dados em sub-grupos. Após a construção de uma árvores de decisão é importante avaliá-la. Esta avaliação é realizada através da utilização de dados que não tenham sido usados no treinamento. Esta estratégia permite estimar como a árvore generaliza os dados e se adapta a novas situações, podendo, também, se estimar a proporção de erros e acertos ocorridos na construção da árvore .

A próxima seção fala um pouco sobre como esta heurística funciona. E posteriormente, entraremos em detalhes em como criarmos a árvore de decisão e classificar clientes existentes em seu conjunto de dados em "will buy" ou "won't buy", tornando sua companhia mais lucrativa.

A heurística ID3

A física usa o termo entropia para descrever a quantidade de desordem associada a um sistema. Na teoria da informação, este termo tem uma significado semelhante, -- ele mede o grau de desordem de um conjunto de dados. A heurística ID3 usa este conceito para encontrar o próximo melhor atributo de um dado para ser utilizado como nó de uma árvore de decisão. Logo , a idéia por trás do algoritmo ID3 é achar um atributo que reduza em maior valor a entropia de um conjunto de dados, assim reduzindo a aleatoriedade - dificuldade de previsão - da variável que define classes. Seguindo esta heurística, você estará essencialmente encontrando o melhor atributo para classificar os registros (de acordo com a redução da quantia de informação necessária para descrever a partição dos dados que foram divididos ) a fim de que os mesmos tenham utilidade máxima (exemplos são da mesma classe).

O algoritmo ID3 segue os seguintes passos:

1. Começar com todos os exemplos do treinamento
2. Escolher o atributo que melhor divide os exemplos, ou seja agrupar os exemplos da mesma classe ou exemplos semelhantes
3. Para o atributo escolhido, criar um nó filho para cada valor possível do atributo
4. Transportar os exemplos para cada filho tendo em conta o valor do filho
5. Repetir o procedimento para cada filho não "puro". Um filho é puro quando cada atributo X tem o mesmo valor para todos os exemplos.

Na etapa 2 do algoritmo, para achar o melhor atributo é necessário encontrar a entropia para cada atributo possível naquele nó. Para isto usamos a fórmula da entropia:

Onde calculamos a proporção do número de exemplos positivos e o mesmo para o número de exemplos negativos para aquele atributo em questão multiplicado pelo logaritmo destas proporções. Um exemplo prático: Considere S uma coleção de 14 exemplos, incluindo 9 positivos ("will buy") e 5 negativos ("won't buy"). Logo a entropia para esta coleção S seria :

Notação: [+9,-5]

O próximo passo na heurística ID3 é calcular o ganho de informação para cada atributo que pode ser selecionado como nó na árvore. Essencialmente é apenas calcular a entropia de todo o conjunto de dados e diminuir este da entropia do sub-conjunto particionado para tal atributo. Este processo é feito para cada atributo do conjunto de dados, e o atributo com o maior ganhor de informação será o selecionado para o próximo nó da árvore.

O raciocínio por trás do ganho de informação é semelhante ao cálculo de entropia demonstrado acima. Agora considerando os sub-conjuntos particionados de acordo com o valor do atributo em questão. Considere o atributo "Vento" que pode ter os valores "Fraco" ou "Forte". Calcula-se então a entropia para cada um desses valores e depois a diferença entre a entropia do atributo vento e a soma das entropias de cada um dos valores associados ao atributo, multiplicado pela proporção de exemplos particionados de acordo com o valor (separados de um lado os exemplos com Vento = "Weak" e do outro lado Vento = "Strong").

Depois dessa breve explicação sobre a heurística ID3, vamos ao código-fonte.

Código-Fonte
O código-fonte a seguir ilustra a função principal do programa usada na construção da árvore de decisão:

##Returns the new decision tree based on the examples given
#@param data: Copy of the data list.
#@param attributes: List of all attributes 
#@param target_attr: The targer attribute that will be the evaluated
#@param fitness_func: The target function
def create_decision_tree(data,attributes,target_attr,fitness_func):
    
    data = data[:]
    vals = [record[target_attr] for record in data]
    default = majority_value(data, target_attr)
    
    #if the dataset is empty or the attributes list is empty, return the
    #the default value. When checking the attributes list for emptiness,
    #we need to subtract 1 to account for the target attribute.
    if not data or (len(attributes)-1) <= 0:
        return default
    #if all the records in the dataset have the same classification,
    #return the classification.
    elif vals.count(vals[0]) == len(vals):
        return vals[0]
    
    else:
        #Choose the next best attribute to best classify our data
        best = choose_attribute(data,attributes,target_attr,fitness_func)
        
        #Create a new decision tree/node with the best attribute.
        tree = {best:{}}
        
        #Create a new decision tree/sub-node for each of the values in the
        #best attribute field
        for val in get_values(data,best):
            #create a subtree for the current value under the "best" field
            subtree = create_decision_tree(get_examples(data,best,val),
                [attr for attr in attributes if attr != best],
                target_attr,
                fitness_func)
        
            # Add the new subtree to the empty dictionary object in our new
            # tree/node we just created.
            tree[best][val] = subtree
        
    return tree

A heurística ID3 usa o conceito de entropia para formular o ganho de informação na escolha de um atributo particular para ser o próximo nó na árvore de decisão. Aqui segue o código da função de entropia e do ganho de informação:

##Calculates the entropy of the given data set for the target attribute.
#@param data: the data list
#@param target_attr = the target attribute
def entropy(data,target_attr):
    val_freq = {}
    data_entropy = 0.0
    
    #Calculates the frequency of each of the values in the target attribute.
    for record in data:
        if val_freq.has_key(record[target_attr]):
            val_freq[record[target_attr]] += 1.0
        else:
            val_freq[record[target_attr]] = 1.0
    
    #Calculate the entropy of the data for the target attribute
    for freq in val_freq.values():
            data_entropy += (-freq/len(data)) * math.log(freq/len(data),2)
    

    return data_entropy

##Calculates the information gain (reduction in entropy) that
##would result by splitting the data on the chosen attribute (attr).
def gain(data, attr, target_attr):
    val_freq = {}
    subset_entropy = 0.0
    
    #Calculate the frequency of each of the value in the target attribute
    for record in data:
        if val_freq.has_key(record[attr]):
            val_freq[record[attr]] += 1.0
        else:
            val_freq[record[attr]] = 1.0
    
    #Calculate the sum of the entropy for each subset of records weighted
    #by their probability of ocurring in the training set.
    for val in val_freq.keys():
        val_prob = val_freq[val] / sum(val_freq.values())
        data_subset = [record for record in data if record[attr]==val]
        subset_entropy += val_prob * entropy(data_subset,target_attr)
 
    #subtract the entropy of the chosen attribute from the entropy of the
    #whole data set with respect to the target attribute (and return it)
    return (entropy(data,target_attr) - subset_entropy)

Mineração de dados com Árvores de decisão
Além de classificação de dados, árvores de decisão são úteis para inferir padrões a partir dos dados, também referenciado como mineração de dados. Apenas dando uma observada na árvore de decisão representada pela figura 1 no início deste artigo, você pode já inferir algumas tendências a partir do conjunto de dados. A mais óbvia tendência no dados é que jovens (idades entre 18 e 35) e idosos (> 55) não compram seus produtos. Isto poderia direcionar seu foco em outro público mais jovem (<>

O ponto mais importante é que olhando por cima o conjunto de dados, mesmo com apenas 20 registros, nenhum dessas tendências ou padrões são fáceis de encontrar a olho nu. Quando esse número aumenta para centenas, milhares ou até milhões de registros, achar essas tendências pode ser impossível. Usando árvores de decisão, você não apenas pode prever os gostos do seu cliente na hora de compra do seu produto, mas como também você pode apontar tendências importantes no seu conjunto de dados de teste a fim de auxiliar na melhora de práticas de marketing, e consequentemente atingir uma nova classe de clientes.

Conclusão

Os códigos acima apresentados são os componentes principais do programa. O resto das funções auxiliares para a construção da árvore de decisão podem ser encontradas no código-fonte disponível para download. Não tentei entrar muito em detalhes no código, pois acredito que o código é auto-explicatório, já que está bem comentado.
Quando executado o programa, uma árvore de decisão é construída e os dados são classificados de acordo com a árvore moldada.
Espero ter ajudado nesse pequeno tutorial sobre árvores de decisão, quaisquer dúvidas estou à disposição.

Até a próxima e boa programação!

Marcel Pinheiro Caraciolo

Referências

Arvores de Decisão - Prof. PHD Teresa Ludermir CIN/UFPE