Ensemble Leaning ou aprendizado por agrupamento

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Ensemble Leaning
Aluno: Antonino Calisto dos Santos Neto
Profº: Dr. Aristófanes Corrêa Silva
1
Sumário
Introdução
Razões para utilizar um Ensemble Learning
Diversidade
Métricas de diversidade
Criando um Ensemble Learning 
Resultados
Conclusão
2
Introdução
O que é aprendizado automático?
Subárea da inteligência artificial, também conhecida como “machine learning” ou “aprendizado de máquina”;
Surgiu da ideia de criar programas que aprendam um determinado comportamento ou padrão automaticamente a partir de exemplos ou observações.
Qual a relação com a mineração de dados ?
A mineração de dados é o processo de extração automática de conhecimento a partir de grandes bases de dados;
Algoritmos de aprendizado automático podem ser vistos como algoritmos que extraem um padrão de comportamento a partir de dados (exemplos) ou podem aprender a partir da interação, e serem classificados.
3
Introdução
Problema da dúvida e busca-se vários especialistas (ex. ensemble);
Atribuímos pesos/valores a cada opinião;
Com a combinação das opiniões se espera obter uma opinião que seja a mais bem informada de todas; 
Diferença dos classificadores que baseiam-se em uma opinião única, os Ensembles Learning (EL) utilizam algoritmos que combinam as opiniões de vários classificadores para tomar uma decisão;
Vários nomes: Ensemble Learning, Multiple Classifier Systems, Committee of Classifiers, Mixture of Experts, aprendizagem por ensemble, ou ainda aprendizado por agrupamento. 
4
Razões para utilizar um EL
5
Razões para utilizar um EL
Razões Estatísticas
Quando se trabalha com Redes Neurais ou classificadores automatizados:
Um bom desempenho no conjunto de treinamento não prediz um bom desempenho de generalização;
Um conjunto de classificadores com desempenhos similares no conjunto de classificação podem ter diferentes desempenhos de generalização;
A combinação das saídas produzidas pelos classificadores reduz o risco de uma escolha infeliz por um classificador com um pobre desempenho.
Não seguir apenas a “recomendação” de um único especialista.
6
Razões para utilizar um EL
Razões Computacionais
A quantidade de dados a serem analisadas pode ser muito grande para serem efetivamente manipulados por um único classificador;
Particionar dados em subconjuntos, o chamado “dividir para conquistar”;
Geralmente mais eficaz;
7
Razões Representacionais
 A utilização de um único classificador pode não ser suficiente para representar de forma assertiva a classificação das classes;
Razões para utilizar um EL
Razões Computacionais e representacionais
A fronteira de decisão que separa os dados de diferentes classes pode ser muito complexa ou estar fora do escopo do classificador (mesma ideia: dividir e conquistar).
8
Razões para utilizar um EL
Razões Computacionais e representacionais
A fronteira de decisão que separa os dados de diferentes classes pode ser muito complexa ou estar fora do escopo do classificador (mesma ideia: dividir e conquistar).
9
 Seleção de modelo:
Considerada a principal razão para o uso de EL;
Qual o classificador mais apropriado para um dado problema de classificação?
Diversidade
O sucesso de um EL, é habilidade em corrigir erros de alguns dos membros, depende fortemente da diversidade do classificadores que o compõem;
Cada classificador deve fazer diferentes erros em diferentes instâncias dos dados;
A ideia é construir muitos classificadores e então combinar suas saídas de modo que o desempenho final seja melhor do que o desempenho de um único classificador;
A diversidade de classificadores pode ser obtida de diferentes formas;
10
Diversidade
Uso de diferentes conjuntos de dados de treinamentos:
Os subconjuntos são normalmente obtidos por meio de técnicas de resampling como bootstrapping ou bagging, na maioria das vezes com reposição.
Classificadores diferentes são usados para garantir que as fronteiras geradas pelos indivíduos são adequadamente diferentes, mesmo usando dados de treinamento substancialmente similares;
11
Diversidade
 Como é dada:
12
Diversidade
 
13
Medidas de Diversidade
Uso de diferentes conjuntos de dados de treinamentos:
Existem propostas para avaliar quantitativamente a diversidades dos classificadores;
Dado 2 hipóteses Hi e HJ (quando Hi é o que realmente está na base): 
14
Hié correto (HJ)
Hié incorreto (HJ)
Hié classificado como correto
A
C
Hiéclassificado comoincorreto
B
D
a = VP
b = FN
c = FP
d = VN
Medidas de Diversidade
Correlação: a diversidade é medida como a correlação entre as saídas de dois classificadores.
Q-Statistic:
Q assume valores positivos se as instâncias são corretamente classificadas por ambos os classificadores e valores negativos caso contrário;
Assim como na correlação uma alta diversidade é obtida próximo de 0. 
15
a = VP
b = FN
c = FP
d = VN
Medidas de Diversidade
Medidas de desacordo e falta dupla:
DiJ = b + c (quanto acertou);
DFiJ = d;
Entropia: 
N é a cardinalidade da base; T numero de classificadores; Operador ceiling é o nº de classif. que classificam incorretamente um padrão Xi (FN + FP). 
A entropia varia entre 0 e 1: 0 indica que todos os classificadores são praticamente os mesmos e 1 indica uma alta diversidade;
Variância de Kohavi-Wolpert similar a DiJ:
 N é o número de classificadores. “Dis” é o desacordo dos classificadores;
16
a = VP
b = FN
c = FP
d = VN
Criando um Ensemble Learning
Dois componentes chave:
Escolha da estratégia para a construção de um EBS composto por classificadores o mais diverso quanto possível:
Algumas estratégias são: Bagging, Boosting, AdaBoost.
Estratégia necessária para a combinação das saídas de cada classificador que compõem o EBS:
Combinação que deve amplificar a quantidade de decisões corretas e anular as ocorrência das incorretas.
17
Criando um Ensemble Learning
Como os classificadores serão gerados?
Como tais classificadores irão diferir entre eles?
Respostas: determinarão a diversidade dos classificadores = performance final do EL;
Uma estratégia para geração dos membros de um EL deve buscar uma melhora da diversidade;
Não existe uma única medida de diversidade aceita uniformemente;
O aumento da diversidade em EL é tratado com um problema de busca - com emprego de heurísticas- usando procedimentos de seleção de diferentes parâmetros de treinamento.
18
Criando um Ensemble Learning
Algoritmo de Bagging:
Bagging = Bootstrap Agreggating
Um dos métodos de agrupamento mais simples.
Criado por Leo Breiman em 1996.
Baseia-se na criação de bootstraps = amostras diferentes da base de dados que são usadas para aprender hipóteses diferentes.
A previsão final para um exemplo de teste é a média da previsão de cada hipótese.
Um fator crítico para que o Bagging funcione é a instabilidade do algoritmo de aprendizado.
Bagging funciona melhor quanto maior for a instabilidade do algoritmo.
19
Criando um Ensemble Learning
Algoritmo de Bagging:
20
Criando um Ensemble Learning
Algoritmo de Bagging:
21
Criando um Ensemble Learning
Algoritmo de Bagging:
22
Criando um Ensemble Learning
Algoritmo de Bagging:
23
Criando um Ensemble Learning
Algoritmo de Bagging (desvantagens):
Perde-se na interpretação.
Em vez de uma única hipótese, temos uma combinação, que é mais difícil de ser entendida (escolhe optar pela 1ª ou 2ª classificação).
Tem um custo computacional adicional.
Só funciona quando o algoritmo é instável.
24
Criando um Ensemble Learning
Algoritmo de Boosting:
A idéia do algoritmo de agrupamento Boosting (também chamado de aceleração) é construir hipóteses sucessivas, de tal modo que exemplos classificados incorretamente por hipóteses anteriores sejam melhor classificados por hipóteses seguintes.
Supõe que o algoritmo de aprendizado utilizado trabalhe com conjuntos de treinamento ponderados.
Quanto mais alto o peso de um exemplo, mais alta deve ser importância dada a ele pelo algoritmo (parecido com aprendizado sensível a custos).
Desvantagens: 
Distribuição dos pesos;
25
Criando um Ensemble Learning
Algoritmo de Boosting:
26
Criando um Ensemble Learning
Algoritmo de Boosting:
27
Criando um Ensemble Learning
Algoritmo de Boosting:
28
Criando um Ensemble Learning
Algoritmo de AdaBoost:
O Adaptive Boosting (AdaBoost) é uma versão mais genérica do algoritmo de Boosting original;
O AdaBoost gera um conjunto de hipóteses e as combina por meio da votação ponderada, porém com classificações cartezianas;
As hipóteses são geradas por meio do treinamento de classificadores usando uma distribuição dos dados iterativamente ajustada; 
Passo 1: calcula a taxa de erro et;
Passo 2: Pesa o classificador at;
Passo 3: Na outra hipótese, mudar peso dt;
29
Criando um Ensemble Learning
Algoritmo de AdaBoost:
Passo 1: calcula a taxa de erro et;
 I(h(x) ≠ y) = Erros do classificador; 
 
Passo 2: Pesa o classificador at;
 			 ln é igual a “2,3 * log X”. Neste caso X = 
Passo 3: Na outra hipótese, mudar peso dt;
 W é o cálculo dos pesos.
 Zt é a normalização dos pesos;
 Hf é dados pelo somatório das importâncias dos classificadores 
30
Criando um Ensemble Learning
Algoritmo de AdaBoost:
31
Criando um Ensemble Learning
Algoritmo de AdaBoost:
32
Calcula a taxa de erro (e): 3/10 = 0,3
Calcula a importância (a): ½ * [2,3* log(2,3)] = 0,42 
W = 1/10 = 0,1 (cálculo do peso igual pra todos). Incorretos : 0,1* exp(0,42) = 0,1*1.52 = 0,152 Corretos: 0,1*exp(-0,42) = 0,066
Normalizar: (7*0,066) +(3*0,152) = 0,918 Incorretos : 0,152/0,918= 0,165 Corretos: 0,066/0,918 = 0,072
Criando um Ensemble Learning
Algoritmo de AdaBoost:
33
Calcula a taxa de erro (e): 3/10 = 0,3
Calcula a importância (a): ½ * [2,3* log(2,3)] = 0,42 
W = 1/10 = 0,1 (cálculo do peso igual pra todos). Incorretos : 0,1* exp(0,42) = 0,1*1.52 = 0,152 Corretos: 0,1*exp(-0,42) = 0,066
Normalizar: (7*0,066) +(3*0,152) = 0,918 Incorretos : 0,152/0,918= 0,165 Corretos: 0,066/0,918 = 0,072
Criando um Ensemble Learning
Algoritmo de AdaBoost:
34
Calcula a taxa de erro (e): 3*0,072 = 0,21
Calcula a importância (a): ½ * [2,3* log(3,76)] = 0,65 
Calcula o peso Utilizando os erros anteriores: Incorretos : 0,165 * exp(0,65) = 0,165*1.91 = 0,315 Corretos: 0,072 * exp(-0,65) = 0,037
Normalizar: (7*0,037) +(3*0,315) = 1,204 Incorretos : 0,315/1,204 = 0,26 Corretos: 0,037/1,204= 0,03
Criando um Ensemble Learning
Algoritmo de AdaBoost:
35
Calcula a taxa de erro (e): 3*0,072 = 0,21
Calcula a importância (a): ½ * [2,3* log(3,76)] = 0,65 
Calcula o peso Utilizando os erros anteriores: Incorretos : 0,165 * exp(0,65) = 0,165*1.91 = 0,315 Corretos: 0,072 * exp(-0,65) = 0,037
Normalizar: (7*0,037) +(3*0,315) = 1,204 Incorretos : 0,315/1,204 = 0,26 Corretos: 0,037/1,204= 0,03
Criando um Ensemble Learning
Algoritmo de AdaBoost:
36
Criando um Ensemble Learning
Algoritmo de AdaBoost:
37
Criando um Ensemble Learning
Algoritmo de AdaBoost (desvantagens):
Ao contrário de bagging, há o risco de super-ajuste (over-fitting);
Principalmente em casos onde há muito ruído na base de dados.
Caso haja erros de classificação nos dados de treinamento, o AdaBoosting irá colocar muito peso nesses dados.
38
Resultados
Chess (King-Rook vs. King-Pawn) Data Set
3196 indivíduos;
36 características;
2 Classes.
Tem como objetivo a análise probabilística do jogador de peças brancas ganhar (“win”) ou não ganhar (“nowin”) a partida. 
Disponível em: 
Link: https://archive.ics.uci.edu/ml/datasets/Chess+(King-Rook+vs.+King-Pawn)
39
Resultados
40
Teste
Acurácia (%)
Sensibilidade (%)
Especificidade (%)
70/30
 99,4
99,6
99,3
30/70
 98,2
98,9 
97,4
Cross-Validation
99,6 
99,6 
 99,3
70/30
 91,5
95,4
87,5
30/70
89,3 
93,3
86
Cross-Validation
90,9 
92,5 
89,1
70/30
 98,6
98,4
98,5
30/70
97,3 
97,9
98,7 
Cross-Validation
98,4 
98,6
98,3
Classificador
J48
NaiveBayes
Combinação
Conclusão
Foi possível observar que a combinação de classificadores diversos (um do tipo Bayes e do tipo árvore, como no exemplo) pode obter um bom resultado, porém depende do algoritmo de estratégia e dos classificadores. 
41