Introdução a Aprendizagem de Máquina
através da Indução de Árvores de Decisão
Geber Ramalho
Jacques Robin
CIn-UFPE
Modelo do Agente Aprendiz (on-line)
Padrões de aceitação
Agente
t+1
sensores
ambiente
t
crítico
avaliação
trocas
elemento
ator
elemento de
conhecimento aprendizagem
objetivos de
aprendizagem
efetuadores
Depende da KRL
Gerador de
problemas
Experiências informativas
Aprendizagem para construção
do agente (off-line)
exemplos
Engenheiro de
conhecimento
parametriza
elemento
ator
elemento de
aprendizagem
Agente
Base de
conhecimento
Árvore de Decisão
A partir de um conjunto de propriedades, decide sim
ou não
 Exemplo Soparia (by Carlos Figueira)

• predicado-objetivo: vaiASoparia
• Atributos considerados:

Sono: Estou com sono?

Transporte: Tenho como ir de carro? Carona? etc.

CONIC: Devo estar amanhã cedo no CONIC?

Álcool: Estou precisando de álcool?

Sair: Quero sair de casa?

Fome: Estou com fome?
Árvore de Decisão “pensada”
valores
atributo
Sono?
Não.
Sim.
Meio de
transporte?
Carona
CONIC?
Precisa de
álcool?
Sim.
Não.
Não.
CONIC?
Sim.
Não.
Quer sair?
Sim.
Não.
ID3: exemplos da soparia

Atributos: (Sono, Transporte, CONIC, Álcool, Sair,
Fome)-> propriedade-objetivo
•
•
•
•
•
•
•
•
•
•
•
•
E01: (Pouco,Carro,Sim,Sim,Não,Sim) -> Sim!
E02: (Pouco,Carona,Não,Não,Sim,Sim) -> Sim!
E03: (Sim,Carro,Não,Sim,Sim,Sim) -> Não.
E04: (Pouco,Carona,Não,Não,Sim,Não) -> Sim!
E05: (Sim,Outros,Sim,Sim,Sim,Não) -> Não.
E06: (Pouco,Outros,Não,Sim,Não,Sim) -> Não.
E07: (Pouco,Carro,Sim,Não,Sim,Sim) -> Sim!
E08: (Pouco,Carona,Não,Não,Não,Sim) -> Não.
E09: (Sim,Carro,Não,Sim,Sim,Não) -> Não.
E10: (Não,Outros,Sim,Sim,Sim,Sim) -> Sim!
E11: (Não,Carro,Não,Sim,Sim,Não) -> Sim!
E12: (Não,Carona,Não,Sim,Sim,Sim) -> Sim!
ID3: conceitos

Classificação
• aplicação do predicado objetivo p a um exemplo

Exemplo positivo (ep) e exemplo negativo (en)
• p(ep) = verdadeiro, p(en) = falso

Conjunto de treinamento
• positivos + negativos

Objetivo da aprendizagem
• gerar a descrição d de p segundo os atributos dados
• d deve ser consistente (cobre todos positivos e exclui
todos negativos) e preditiva/geral (vai além da
memorização)
• d deve ser a mais simples possível (navalha de Ockahm)
ID3: construção da árvore

Escolha do melhor atributo
• O que discrimina o maior número de exemplos
• Maior ganho de informação (entropia)

Candidatos:
• Transporte: Não classifica imediatamente nenhum dos
exemplos
• Sono: Classifica de imediato 6 dos 12 exemplos
• ...
Exemplo: atributo transporte
+:E01,E02,E04,E07,E10,E11,E12
- :E03,E05,E06,E08,E09
Transporte?
carro
+: E01,E07,E11
-: E03,E09
carona
+: E02,E04,E12
-: E08
outros
+: E10
-: E05,E06
Exemplo: atributo sono
+:E01,E02,E04,E07,E10,E11,E12
- :E03,E05,E06,E08,E09
Sono?
sim
+: - - -: E3, E5, E9
pouco
+: E1,E2,E4, E7
-: E6,E8
não
+: E10,E11,E12
-: - - -
Cálculo do ganho de informação
Ganho(A) = I p/p+n, n/p+n -  vi=1(pi+ni)/(pi+ni) I pi/pi+ni, ni/pi+ni
I p/p+n, n/p+n = -p/(p+n) (log2 p/(p+n)) - n/(n+p) (log2 n/(p+n))
Onde
A = atributo
p = positivo
n = negativo
ID3: Algoritmo de aprendizagem
function APRENDIZAGEM_DA_ID3(exemplos,atributos,default) :
árvore de decisão
if (exemplos é vazio) then return default;
else if (todos os exemplos têm a mesma classificação)
then return (a classificação);
elseif (atributos é vazio) then return maioria(exexmplos);
else
melhor <- ESCOLHA_MELHOR_ATRIBUTO(atributos,exemplos);
árvore <- nova árvore com raiz “melhor”;
para cada valor vi de melhor faça
exemplosi <- exemplos onde melhor = vi;
subárvore <- APRENDIZAGEM_DA_ID3(exemplosi,
atributos-{melhor}, maioria(exemplos));
adicione subárvore como um ramo à árvore com
rótulo vi;
return arvore;
Árvore de Decisão “Induzida”
+: E1,E2,E4,E7,E10,E11,E12
-: E3, E5, E6, E8, E9
Sono?
+: - - -: E3, E5, E9
Não.
+: E1,E2,E4, E7
-: E6,E8
+: E10,E11,E12
-: - - -
Meio de
transporte?
Sim.
Carona
+: E1,E7
-: - - -
Sim.
+: E2,E4
-: E8
+: - - -: E6
Quer sair?
+: E2,E4
-: - - -
+: - - -: E8
Sim.
Não.
Não.
Regras

É possível mostrar o resultado como regras lógicas
• toma-se as folhas com conclusão positiva e sobe-se até a raiz

Exemplos:
• t Sono(Não,t)  VaiASoparia(t)
• t Sono(Pouco,t)  Transporte(Carro,t)  VaiASoparia(t)
• t Sono(Pouco,t)  Transporte(Carona,t)  QuerSair(Sim,t) 
VaiASoparia(t)
Dimensões para classificar tarefas e
técnicas de aprendizagem de máquina







Tarefas de aprendizagem: componente e aspeto do elemento de
performance a melhorar
Complexidade do ambiente do agente aprendiz
Retorno no processo de treinamento do agente
Controle dos mecanismos de aprendizagem e de ação
Formalismo de representação do conhecimento
Aproveitamento de conhecimento prévio
Visões unificadoras:
• aprendizagem = adquirir uma representação, geralmente aproximativa,
de uma função matemática
• aprendizagem = busca de uma região em um espaço de hipótese
explicando os dados (exemplos)
 Relação com otimização, analise numérica, estatística

Propriedades matemática e viés a priori sobre a função a
aproximar ou do espaço de hipótese a buscar
Técnicas de aprendizagem
Paradigma simbólico:
 Aprendizagem de conceitos por
busca no espaço de soluções
(version-space)
 Indução de árvores de decisão
e regras proposicionais
 Programação em lógica indutiva
 Aprendizagem por explicações
 Raciocínio baseado em casos
 Aprendizagem Q
 Agrupamento de conceitos
proposicionais
Paradigma probabilista:
 K Vizinhos mais próximo
 Regressão estatística
 Funções de bases radiais
 Aprendiz bayesiano ingênuo
Paradigma conexionista:
 Perceptron multicamada
 Memórias associativas
Paradima evolucionista:
 Algoritmos genéticos
Abordagens híbridos:
 Rede bayesianas
Tarefas de aprendizagem

Classificação: dados = instâncias  conceitos
• aprende novo conhecimento da forma:


CI: Estado(Ambiente,t) x Percepções(t)  Estado(Ambiente,t+1)
Previsão: dados(t)  conceitos  dados(t+1)
• aprende novo conhecimento da forma:


CP1: Estado(Ambiente,t)  Estado(Ambiente,t+1)
CP2: Estado(Ambiente,t) x Ações(t)  Estado(Ambiente,t+1)
• classificação destacando atributo tempo
• generaliza-se na identificação de serias temporais

Controle: dados política de comportamento
• aprende novo conhecimento da forma:



R: Percepções  Ações, ou
Cu1: Estado(Ambiente,t) x Objetivos(t)  Utilidade, ou
Cu2: Estado(Ambiente,t) x Ações(t) x Objetivos(t)  Utilidade
Tarefas de aprendizagem

Otimização:
•
•
•
•
•

aprender nova representação de conhecimento prévio
para melhorar desempenho do agente e não sua versatilidade
embora não envolve aprender nada de fundamentalmente novo
as vezes a diferença entre 2 representações do mesmo problema
é a diferença entre uma solução puramente teórica e uma solução
operacional na prática
Meta-aprendizagem
• aprender valores ótimas de parâmetros ou de representações de
viés para aprendizagem de conhecimento do domínio da aplicação

Aprendizagem multi-camada: muitas vezes,
• controle requer previsão, que requer classificação
• e o conhecimento assim obtido precisa ser otimizado para
execução em tempo real
• ex, futebol de robôs
Complexidade do ambiente
Acessível?
 Episódico?
 Discreto?
 Determinista? Ruidoso?
 Dinâmico?
 Relacional?
 Diverso?
 Grande?

Retorno no processo de treinamento

Aprendizagem supervisionada
• certo(ação) ou errado(ação)
• Dado conjunto de exemplos pré-classificados,
• Aprender descrição que abstraí a informação contida nesses
exemplos
• e que pode ser usada para prever casos futuros
• ex., concessão de crédito

Aprendizagem não-supervisionada
• se vire!
• Dada uma coleção de dados não classificados,
• Agrupá-los por regularidades
• ex., caixa de supermercado empacotando
Retorno no processo de treinamento

Aprendizagem por reforço: recompensa/punição
• certo(ação1(t0)/.../ação(tn) ou errado(ação1(t0)/.../ação(tn))
• dado sucesso ou insucesso global de um seqüência de ação,
determinar qual ação e’ a mais desejável em cada situação
• ex., DeepBlue jogando contra ele próprio: é por a
• propagar para trás recompensas e punições a partir do estado
final
Controle da aprendizagem
Aprende depois age ou aprende agindo (treinos x jogos)
 Agir sempre otimamente x aprender novas habilidades
 Busca de hipótese:

• incremental (exemplos apresentado ao poucos)
ou não (todos de uma vez)
• iterativa (exemplos re-apresentados em várias épocas) ou não
(uma apresentação de cada exemplo basta)
• top-down (refina hipótese geral para cobrir exemplos) ou
bottom-up (generaliza exemplos para abstrair hipótese) ou
bi-direcional
• gulosa (generaliza exemplos assim que encontrados) ou
preguiçosa (não generaliza exemplos com antecedência, apenas os
indexa para os adaptar ao receber novas consultas parecidas)
• global (aproxima função completa) ou
local (aproxima-la por partes)
Representação do conhecimento

Função matemática:
• domínio e escopo: {0,1}, Z, R
• monotonia, continuidade
• polinomial, exponencial, logarítmica

Lógica:
• proposicional (ordem 0), de atributos (ordem 0+)
• de Horn ou dos predicados (ordem 1)
• exóticas (ordem superior, temporal, modal, etc)
Distribuição de probabilidades
 Outros, ex.:

•
•
•
•
Pesos em redes conexionistas,
Representações orientada a objetos,
Árvores de decisão, etc...
se reduzem as 3 primeiras
Conhecimento prévio

Aprendizagem sem conhecimento prévio:
• dados (exemplos)  conhecimento

Aprendizagem com conhecimento prévio:
• dados x conhecimento prévio  conhecimento aprendido

Métodos de aprendizagem que permitem usar
conhecimento prévio em entrada:
• re-aproveitam de conhecimento:


adquirido com especialistas humanos
aprendido durante passos anteriores de KDD
• para aprendem a partir de muito menos dados
• Homogeneidade:
• Exemplos, conhecimento prévio e conhecimento aprendido pode
ser representados no mesmo formalismo?
Viés

Conhecimento prévio:
• conhecimento do domínio da aplicação inteligente
• ex, futebol de robôs, bolsa de valor, meteorologia, etc.
• no mesmo formalismo do que o conhecimento a aprender

Viés:
• meta-conhecimento prévio
• sobre a forma do conhecimento a aprender a partir dos dados,
ex.,






classe de função a aproximar (linear, polinomial, ...)
classe de função medindo o erro da aproximação (médio quadrado, …)
dimensionalidade do espaço de hipótese
distribuição probabilista dos pontos nesse espaço (normal, poisson, ..)
restrições lexicais e sintática da linguagem de representação do
conhecimento a aprender (ex, número de premissa ou conclusões de
regras, numero de grupos classificando exemplos, …)
Aprendizagem sem viés não tem poder de generalização !
Indução de árvore de decisão: características


Tarefas:
classificação,
previsão e controle
Ambiente:
•
•
•
•
•
•
•
•

inacessível: +
não episódico: +
contínuo: + ou ruidoso: +
dinâmico: +
relacional: diverso: grande: +
Supervisionado

Controle da aprendizagem:
•
•
•
•
•
•



Treino antes da ação
Não incremental
Não iterativo
Top-down
Guloso
Global
Representação do conhecimento: lógica
propocisional
Não pode aproveitar de conhecimento
prévio
Propriedades da função aproximada:
escada N dimensional
Problemas c/ ID3: Expressividade

Só pode tratar de um único objeto
• t Sono(Não,t)  VaiASoparia(t)
• t Sono(Pouco,t)  Transporte(Carro,t)  VaiASoparia(t)

Mais de um... não dá com eficiência
• Ex: “se posso ficar mais indisposto mais tarde, eu vou logo à
soparia”
• t1t2 MesmoDia(t1,t2)  Disposição(t1,d1)  Disposição(t2,d2)
 Maior (d1,d2)  VaiASoparia(t)
• alternativa: atributo possoFicarMaisIndisposto(t)
Problemas c/ ID3: Expressividade
Exemplo: Goal predicate = BomPesquisador (x)
 Como tratar atributos multi-valorados?

• Filiação(José, {USP, Unesp})

Como tratar atributos numéricos?
•

Tem entre 45 e 52 anos
Como tratar listas ordenadas?
• Formação = {graduação, mestrado, doutorado, pós}

Como inserir conhecimento a priori?
• Hierarquias conceituais
BR
NE
PE
PB
Norte
AL
CE
Problemas gerais: ambigüidade

Ambigüidade:
• Dois ou mais exemplos com a mesma descrição (em termos de
atributos) mas classificações diferentes

Causas:
• Ruído
• Atributos insuficientes

Soluções:
• tratamento estatístico
• indução construtiva
• etc.
Problemas gerais: overfitting

Overfitting (hiper-especialização):
• Evitar encontrar uma “regularidade” muito restrita nos dados

Soluções:
• Validação cruzada
• Pré-Poda: parar a construção da árvore cedo


não dividir um nó se isso resultar em um critério abaixo de um limiar
difícil escolher o limiar apropriado
• Pós-Poda: remover ramos de uma árvore completa



conjunto de dados e critério de qualidade da árvore diferentes
para a fase inicial de constução da árvore e
para a fase final de poda da árvore
Pós-poda de arvore de decisão:
Validação Cruzada


Serve para evitar overfitting e para averiguar
robustez dos resultados
Algoritmo
1) Divide o conjunto de exemplos em dois sub-conjuntos:
conjuntos de treinamento (TR) e de teste (TE)
2) Usa indução para gerar hipótese H sobre TR
3) Mede percentagem de erro de H aplicada à TE
4) Repete passos 1-3 com diferentes tamanhos de TE e TR,
e tendo elemento escolhidos aleatoriamente
Treinamento
Teste
Curva de aprendizagem