Hoje!

/Banco de dados

voltar
/Banco de dados

Data Mining na Prática: Árvores de Decisão

PorMauro Pichiliani em

Olá pessoal. Nesta coluna vamos continuar nosso estudo sobre algoritmos de Data Mining.

Desta vez, estudaremos o algoritmo de classificação supervisionada chamado Árvores de Decisão. Durante a apresentação do exemplo de funcionamento do algoritmo, um software será utilizado para a visualização da árvore.

O algoritmo

O algoritmo de Árvores de decisão é um pouco diferente dos algoritmos que foram apresentados em artigos anteriores. Isso porque ele gera uma estrutura de árvore que ajuda na classificação e predição das amostras desconhecidas. Com base nos registros do conjunto de treinamento, uma árvore é montada e, a partir desta árvore, pode-se classificar a amostra desconhecida sem necessariamente testar todos os valores dos seus atributos. O algoritmo de classificação por árvores de decisão é considerado um algoritmo supervisionado, pois é necessário saber quais são as classes de cada registro do conjunto de treinamento.

Como o algoritmo monta uma árvore, é necessário antes definir quais são os elementos desta árvore. Para simplificar a explicação do algoritmo, basta pensar em uma árvore como um conjunto de nós que são conectados por ramificações. Basicamente existem três tipos de nós: o nó raiz, que inicia a árvore, os nós comuns que dividem um determinado atributo e geram ramificações e os nós folha que contém as informações de classificação do algoritmo. Já as ramificações possuem todos os valores possíveis do atributo indicado no nó para facilitar a compreensão e interpretação.

A idéia do algoritmo é montar uma árvore onde cada nó indica o teste de um atributo. Os atributos escolhidos para os nós da árvore são chamados de atributos divisores ou atributos teste. A escolha de atributos é feita com base no maior ganho de informação, isto é, na qualidade de classificação do atributo. Deste modo, podemos dizer que o atributo que melhor classificar os dados deve ser escolhido como um nó da árvore. Para facilitar a compreensão, é comum colocar os valores das probabilidades de cada classe dentro do nó.

A classificação de uma nova amostra é feita percorrendo os ramos e nós da árvore de acordo com os valores dos atributos da amostra desconhecida. Este algoritmo permite uma análise mais detalhada levando em consideração cada valor de cada atributo. Contudo, dependendo de quão bom o atributo é para a classificação, nem sempre todos os atributos podem estar nos nós da árvore de decisão.

Outro fator importante a ser considerado é a análise da árvore. Apenas montar a estrutura da árvore e classificar novas amostras nem sempre é suficiente, pois a análise pode requerer um detalhamento melhor do que significa cada nó da árvore. Além de classificar uma amostra desconhecida, analisando a árvore gerada pode-se montar regras de decisão a partir da árvore de decisão montada com o objetivo de representação do conhecimento.

Sem entrar em detalhes muito técnicos de como o algoritmo funciona, basta pensar que os quatro passos abaixo devem ser seguidos:

PASSO 1: Geração do nó raiz.

Neste passo, cada classe do conjunto de treinamento possui sua probabilidade calculada. Como ainda não existe nenhum nó na árvore, basta criar um nó raiz contendo as probabilidades de cada classe. Nos próximo passo um atributo deve ser colocado para este nó raiz.

PASSO 2: Encontrar nós a serem divididos.

Neste passo é necessário encontrar os nós da árvore que ainda podem ser divididos para a geração de novos nós. Basta obter os nós que não são folhas, isto é, nós que ainda não possuem divisões e que cuja distribuição das probabilidades não classifique a amostra totalmente. Classificar a amostra totalmente quer dizer que o nó não deve possuir alguma classe que tenha 100% de probabilidade de classificar a amostra no seu nó. Se não houver mais nenhum nó que pode ser dividido o algoritmo termina.

PASSO 3: Divisão de nó.

Para cada nó do conjunto de nós que podem ser divididos deve-se escolher um atributo que melhor classifica os dados. Esta escolha deve excluir todos os atributos que inda não foram utilizados no caminho que começa deste o nó raiz até o nó a ser dividido. Além de considerar os atributos que já foram utilizados, também deve-se analisar a quantidade de nós folha que o atributo gera e a quantidade de nós não folhas escolhendo o atributo que mais gera nós folha e que menos gera nós que podem ser divididos. Em alguns casos, o nó não pode ser dividido devido às restrições, o que faz com que este nó não seja armazenado no conjunto de nós a serem divididos.

PASSO 4: Criação do nó.

Com o atributo escolhido, basta criar e desenhar o nó e as suas ramificações de acordo com todos os possíveis valores do atributo. A criação de ramificações gera novos nós que devem analisados em seguida. O algoritmo volta para o PASSO 2.

Do modo que o algoritmo foi apresentado, fica difícil imaginar uma implementação. A próxima sessão do artigo descreve passo a passo a geração de uma árvore exemplificando todo o algoritmo.

Mais informações sobre o algoritmo de Árvores de decisão podem ser obtidas nos links abaixo:

http://en.wikipedia.org/wiki/Decision_tree

Um bom artigo sobre como montar árvores de decisão no Weka:

http://www.devmedia.com.br/visualizaComponente.aspx?comp=3388&site=2

Exemplo de uso de algoritmo de Árvores de Decisão

Vamos considerar o seguinte cenário para a utilização do algoritmo. Um sistema de contas a receber de um clube esportivo envia para um banco no início de cada mês um boleto contendo da mensalidade do clube a ser paga pelos associados. O banco então envia pelo correio a fatura para os clientes e espera os recebimentos. No final do mês, o banco retorna para o sistema do clube quais clientes pagaram o boleto, quais não pagaram e quais clientes pagaram com atraso, dentre outras informações. Com o objetivo de diminuir a quantidade de clientes que pagam o boleto com atraso, foi feita uma mineração de dados na base de associados para identificar o perfil de quem paga com atraso o boleto.

Um pré-processamento dos dados separou as informações dos clientes em alguns atributos que podem ser visualizados na tabela da Figura 01. Para este exemplo, 14 registros foram utilizados para o conjunto de treinamento.


Figura 01. Dados dos associados de um clube esportivo

As colunas apresentadas na tabela da Figura 01 são descritas a seguir:

IDADE: Este atributo identifica a idade do associado. Foi dividido entre os valores <=30, 31..40 para indicar uma faixa de idade e >40 para os valores acima de 40 anos.

SALARIO: Este atributo identifica o salário do associado. Este atributo foi classificado de acordo com a freqüência dos salários, gerando os valores Alto, Médio e Baixo.

SUPERIOR_COMPLETO: Este atributo indica se a escolaridade do associado. Pode possuir os valores Sim e Não.

DEPENDENTES: Este atributo indica se o associado possui dependentes que utilizam o clube com a sua carterinha. Possui os valores Sim e Não.

ATRASOU: Esta é a coluna que apresenta a classificação das amostras. Neste exemplo, a classificação indica se o cliente atrasou no pagamento, isto é ATRASOU=SIM, ou se o cliente não atrasou no pagamento, isto é ATRASOU=NAO. Para facilitar a visualização os clientes do conjunto de treinamento que atrasaram o pagamento foram marcados em vermelho e os clientes que não atrasaram foram marcados em azul.

Vamos agora montar passo a passo a árvore de decisão. Para facilitar a explicação, o software Decision Tree Learning Applet foi utilizado. O link para download deste software se encontra no final do artigo. Como o algoritmo é bem extenso somente os cálculos do primeiro nível da árvore serão mostrados.

O primeiro passo é gerar o nó raiz da árvore. Devemos primeiro calcular a probabilidade para cada uma dos valores do atributo de classificação, que no exemplo é o atributo ATRASOU. As probabilidade do nó raiz são:

Probabilidade de ATRASOU=NÃO: 5/14 = 0,36
Probabilidade de ATRASOU=SIM: 9/14 = 0,64

O nó raiz da árvore fica assim:



Figura 02. Nó raiz da árvore de decisão

Notem na Figura 02 que os valores são seguidos da contagem para este nó e da sua probabilidade, que é apresentada numericamente e por uma barra. Este nó ainda não tem um atributo e por isso é um nó que pode ser dividido.

O próximo passo é escolher atributos para os nós que podem ser divididos. Como só temos um nó vamos analisar todos os atributos para verificar aquele que melhor classifica os dados.

Para o atributo IDADE temos:

Valor <=30
Probabilidade de ATRASOU=NÃO: 3/14
= 0,214
Probabilidade de ATRASOU=SIM: 2/14 = 0,143

Valor 31..40
Probabilidade de ATRASOU=NÃO: 0/14
= 0
Probabilidade de ATRASOU=SIM: 4/14 = 0,286

Este valor gera um nó folha, pois todos os registros que tem o  valor 31..40 são da classe ATRASOU=SIM

Valor > 40
Probabilidade de ATRASOU=NÃO: 2/14
= 0,143
Probabilidade de ATRASOU=SIM: 3/14 = 0,214

Para o atributo SALARIO temos:

Valor Alto
Probabilidade de ATRASOU=NÃO: 2/14
= 0,143
Probabilidade de ATRASOU=SIM: 2/14 = 0,143

Valor Médio
Probabilidade de ATRASOU=NÃO: 2/14
= 0,143
Probabilidade de ATRASOU=SIM: 4/14 = 0,286

Valor Baixo
Probabilidade de ATRASOU=NÃO: 1/14
= 0,071
Probabilidade de ATRASOU=SIM: 3/14 = 0,214

Para o atributo SUPERIOR_COMPLETO temos:

Valor Não
Probabilidade de ATRASOU=NÃO: 4/14
= 0,286
Probabilidade de ATRASOU=SIM: 3/14 = 0,214

Valor Sim
Probabilidade de ATRASOU=NÃO: 6/14
= 0,428
Probabilidade de ATRASOU=SIM: 1/14 = 0,071

Para o atributo DEPENDENTES temos:

Valor Não
Probabilidade de ATRASOU=NÃO: 2/14
= 0,143
Probabilidade de ATRASOU=SIM: 5/14 = 0,357

Valor Sim
Probabilidade de ATRASOU=NÃO: 3/14
= 0,214
Probabilidade de ATRASOU=SIM: 4/14 = 0,286

Conclusão: Somente o atributo IDADE gerou um nó folha e por isso ele deve ser escolhido como atributo de divisão do primeiro nó. Após escolher este atributo devemos calcular as probabilidades dos novos nós gerados pela ramificação deste nó. Deste modo o primeiro nível da árvore de decisão ficará como a Figura 03.

Figura 03. Primeiro nível da árvore de decisão

O algoritmo volta para o passo de escolha de nós a serem considerados para a divisão. Neste ponto, a árvore tem dois nós que podem ser divididos, que estão marcados em azul na Figura 03. O nó folha gerado pela divisão do valor 31..40 do atributo IDADE não pode mais ser divido. Seguindo o algoritmo, devemos calcular as probabilidades dos atributos SALARIO, SUPERIOR_COMPLETO e DEPENDENTES para cada um dos nós em azul e depois gerar nos nós e assim sucessivamente até não restar mais nós a serem divididos.  O resultado final do algoritmo de árvores de decisão aplicado aos dados do conjunto de teste é apresentado na Figura 04.

Figura 04. Árvore de decisão completa para o conjunto de testes de exemplo

A árvore de decisão mostrada na Figura 04 possui quatro nós folha (em verde) que classificam os valores das classes de acordo com seus atributos. Notem que o atributo SALARIO não foi utilizado, pois o algoritmo não considerou este atributo como relevante para a classificação. A árvore da Figura 04 também pode ser representada textualmente da maneira abaixo:

IDADE = <=30
|           SUPERIOR_COMPLETO = NÃO: NÃO
(3.0)
|           SUPERIOR_COMPLETO
= SIM: SIM (2.0)
IDADE = 30..40: SIM(4.0)
IDADE = >40
|           DEPENDENTES = NÃO:
SIM (3.0)
|           DEPENDENTES = SIM: NÃO
(2.0)

Desta maneira fica um pouco mais fácil para extrair as regras de classificação do tipo SE… ENTÃO da nossa árvore:

SE IDADE
= <=30 e             SUPERIOR_COMPLETO = NÃO ENTÃO
            A
amostra é classificada como ATRASA=NÃO
SE IDADE = <=30 e             SUPERIOR_COMPLETO
= SIM ENTÃO
            A
amostra é classificada como ATRASA=SIM
SE IDADE = 30..40 ENTÃO
            A
amostra é classificada como ATRASA=SIM
SE IDADE >=40 e DEPENDENTES = NÃO ENTÃO
            A
amostra é classificada como ATRASA=SIM
SE IDADE >=40 e DEPENDENTES = SIM ENTÃO
            A
amostra é classificada como ATRASA=NÃO

Contudo, devemos considerar alguns detalhes antes do uso do algoritmo de árvores de decisão. O algoritmo trabalha bem com valores discretos, pois caso contrário a árvore pode se tornar imensa e de difícil compreensão. Também é preciso dizer que em alguns casos os nós folhas são apresentam sempre um valor correto e nestes casos devemos classificar de acordo com a classe que apresenta maior probabilidade.

Outro detalhe é que para muitos atributos com muitos valores o algoritmo pode levar algum tempo para montar a árvore, pois é necessária uma grande quantidade de cálculos de probabilidade além de armazenamento temporário de valores.

Como dito anteriormente, além de permitir a classificação de uma amostra desconhecida, a árvore gerada pode permitir a classificação sem a necessidade da análise de todos os atributos. Por exemplo, na árvore da Figura 04 podemos classificar imediatamente como ATRASA=SIM uma amostra possuir o valor 30..40 para o atributo IDADE.

Outra vantagem do algoritmo que gera a árvore de decisão é permitir análises que filtram algum valor de um atributo. Por exemplo, podemos fazer as seguintes afirmações sobre a árvore da Figura 04:

“Mais da metade dos associados que possuem mais de quarenta anos têm dependentes”.

“Dos associados que tem idade igual ou menor que trinta anos menos da metade possui o superior completo”.

E como diria o rapaz de cabelo engraçado da Figura 05: “bada ban, bada bin, bada CIÊNCIA!”



Figura 5. “Você joga, eu rebato e a gente dança!"

O download do software Decision Tree Learning Applet pode ser feito no site abaixo:
http://www.cs.ubc.ca/labs/lci/CIspace/Version4/dTree/index.html

Um grande abraço e até a próxima coluna.

Deixe um comentário! 6

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Comentando como Anônimo

  1. Parabéns!! Fazia tempo que não via um guia tão simples, prático e explicativo!! Deu de pau na enorme maioria de ‘artigos’ dos grandes blogs de Computação.

    Parabéns!

leia mais
Este projeto é mantido e patrocinado pelas empresas: