Fundamentos de Inteligencia Artificial [5COP099]
Dr. Sylvio Barbon JuniorSaulo Martiello Mastelini
Departamento de Computacao - UEL
1o Semestre
Assunto
Aula 12Modelos Preditivos - Random Forests
2 de 34
Aula 12 - Random Forests
Sumario
Introducao
Random ForestsAlgoritmoConstrucao das arvores
Aspectos importantesOut-of-Bag ErrorImportancia de VariaveisProximidade de Casos
Consideracoes finais
Referencias
3 de 34
Aula 12 - Random Forests
Sumario
Introducao
Random ForestsAlgoritmoConstrucao das arvores
Aspectos importantesOut-of-Bag ErrorImportancia de VariaveisProximidade de Casos
Consideracoes finais
Referencias
4 de 34
Aula 12 - Random Forests
Forca dos preditores
• Profundidade das arvores:◦ Sem poda: geracao de overfitting (sobreajuste)◦ Com poda: aumento na taxa de erros
• Conjuntos de dados complexos:◦ Preditores individuais muitas vezes nao possuem poder de
generalizacao suficiente.
• Preditores fracos e fortes:◦ Dependencia da taxa de erro obtida pelo classificador.◦ Alta taxa de erro ⇒ preditor fraco.◦ Baixa taxa de erro ⇒ preditor forte.
5 de 34
Aula 12 - Random Forests
Ensemble Learning
• Juncao de varios preditores (potencialmente) fracos: ensemble depreditores.
• Combinacao das respostas originadas por cada preditor paracompor a resposta final do sistema.
• Estrategias para composicao dos conjuntos de preditores: boostinge bagging.
6 de 34
Aula 12 - Random Forests
Ensemble Learning
• Boosting :◦ Utilizacao de todo o conjunto de treinamento para geracao de cada
preditor;◦ Atribuicao de maior peso para instancias que foram incorretamente
classificadas em preditores anteriores;◦ Maior foco em instancias com maior pesagem na construcao dos
proximos classificadores;◦ Exemplo de tecnica: Adaboost.
• Bagging :◦ Geracao de um conjunto de treinamento para cada preditor;◦ Uso de amostragem com reposicao (bootstrap sampling).◦ Exemplo de tecnica: Random Forests.
7 de 34
Aula 12 - Random Forests
Random Forests
• Tecnica proposta por Leo Breiman, em 2001.
• Floresta: Conjunto de arvores de decisao.
• Random ⇒ Aspectos de aleatoriedade:◦ Construcao de conjuntos de treinamento para cada arvore (bagging);◦ Selecao de subconjuntos de atributos para construcao de cada
preditor.
• Uma das tecnicas “estado da arte” (Fernandez-Delgado et. al.,2014).
8 de 34
Aula 12 - Random Forests
Random Forests: Vantagens X Desvantagens
• Vantagens:◦ Alto nıvel de acuracia;◦ Poucos hiperparametros;◦ Lida com grandes datasets e com grande numero de atributos;◦ Gera metricas internas de erro, importancia de variaveis e proximidade
de instancias;◦ Possibilita metodo efetivo de substituicao de dados ausentes;◦ A natureza aleatoria de construcao de cada arvore minimiza o
sobreajuste;◦ Tende a ter bom desempenho com dados desbalanceados.
• Desvantagens:◦ Metodo “Caixa Preta”◦ Construcao e manipulacao de varias arvores.
9 de 34
Aula 12 - Random Forests
Sumario
Introducao
Random ForestsAlgoritmoConstrucao das arvores
Aspectos importantesOut-of-Bag ErrorImportancia de VariaveisProximidade de Casos
Consideracoes finais
Referencias
10 de 34
Aula 12 - Random Forests
Random Forests: Algoritmo
• ntree ⇒ numero de arvores na floresta.
• mtry ⇒ numero de atributos utilizados para construir cada arvore.
• N ⇒ numero de instancias no conjunto de treinamento.
Algoritmo
Repita ntree vezes:
1. Crie um novo conjunto de treinamento com o tamanho N,utilizando amostragem com reposicao no conjunto original.
2. Construa uma arvore (sem poda) utilizando mtry atributos doconjunto de treinamento, selecionados aleatoriamente (semreposicao).
11 de 34
Aula 12 - Random Forests
Random Forests: Taxa de erros
• Taxa de erros depende de dois aspectos
1. Correlacao entre as arvores na floresta: ↗ Correlacao ⇒ ↗ Erro2. Forca dos preditores individuais: ↗ Forca ⇒ ↘ Erro
• Reduzir mtry ⇒↘ Correlacao, ↘ Forca
• Aumentar mtry ⇒↗ Correlacao, ↗ Forca⇒ Balanceamento do valor de mtry.
• mtry e o parametro que mais impacta na performance de umaRandom Forest.
12 de 34
Aula 12 - Random Forests
Random Forests: Predicao (classificacao)
• O conjunto de teste e submetido a floresta.
• Voto majoritario:◦ Os votos de cada arvore sao computados: a classe com mais votos e a
resposta final.
• Voto com pesagem:◦ Pesos diferentes podem ser atribuıdos para cada classe (e.g, dados
desbalanceados);◦ Computa-se o valor ponderado da contagem de votos de cada classe,
vezes o peso atribuıdo a classe em questao.◦ Resposta final: classe com maior valor ponderado.
13 de 34
Aula 12 - Random Forests
Construcao das arvores
• A construcao de cada arvore segue o algoritmo CART
• Metrica de separacao dos dados ou funcao de merito: Gini Gain.
• O Ganho Gini utiliza como Kernel a metrica Gini Impurity◦ Medida de impureza dos dados.◦ 0 (zero) se todos os dados pertencem a mesma classe.
• Gini Impurity:
Gini(S) = 1−m∑i=1
p2i
onde S e conjunto de dados, m e quantidade de classes, e pi e aprobabilidade de ocorrencia da classe i .
14 de 34
Aula 12 - Random Forests
Gini Impurity: Exemplo
Tempo Temperatura Umidade Vento JogarChuvoso 71 91 Sim NaoEnsolarado 69 70 Nao SimEnsolarado 80 90 Sim NaoNublado 83 86 Nao SimChuvoso 70 96 Nao SimChuvoso 65 70 Sim NaoNublado 64 65 Sim SimNublado 72 90 Sim SimEnsolarado 75 70 Sim SimChuvoso 68 80 Nao SimNublado 81 75 Nao SimEnsolarado 85 85 Nao NaoEnsolarado 72 95 Nao NaoChuvoso 75 80 Nao Sim
15 de 34
Aula 12 - Random Forests
Gini Impurity: Exemplo
• Classes (Jogar): Sim e Nao
• Numero de instancias: 14
• [9sim, 5nao ]
• Gini(Jogar) = 1− ( 914 )2 − ( 5
14 )2
• Gini(Jogar) = 0.4591837
16 de 34
Aula 12 - Random Forests
Gini Gain
• O corte em cada no na arvore e baseado no Ganho Gini.
• Atributo com maior Ganho e utilizado para realizacao do corte.
GiniGain(A,S) = Gini(S)−n∑
i=1
|Si ||S |∗ Gini(Si )
onde:◦ A e um atributo;◦ S e o conjunto de dados;◦ n e o numero de nıveis da variavel A;◦ Si e a particao induzida em S pelo valor i da variavel A;◦ A notacao “‖” indica o tamanho, comprimento.
17 de 34
Aula 12 - Random Forests
Gini Gain: Exemplo 1
• Exemplo: GiniGain(Vento, Jogar)◦ Vento = Sim ⇒ Jogar[3sim, 3nao ]◦ Vento = Nao ⇒ Jogar[6sim, 2nao ]
◦ GiniGain(Vento, Jogar) =0.4591837− 6
14 ∗ Gini(Vento = sim)− 814 ∗ Gini(Vento = nao)
◦ Gini(Vento = sim) = 1− ( 36 )2 − ( 3
6 )2 = 0.5
◦ Gini(Vento = nao) = 1− ( 68 )2 − ( 2
8 )2 = 0.375
◦ GiniGain(Vento, Jogar) = 0.4591837− 614 ∗ 0.5− 8
14 ∗ 0.375 =0.03061224
18 de 34
Aula 12 - Random Forests
Gini Gain: Exemplo 2
• Atributos numericos ⇒ corte no ponto com maior ganho:◦ Valores do atributo ordenados;◦ Determinacao dos valores de corte;◦ Calculo de Ganho para cada particao;◦ Particao com maior Ganho sera escolhida.
• Exemplo: GiniGain(Temperatura)◦ Valores ordenados: [64, 65, 68, 69, 70, 71, 72, 72, 75, 75, 80, 81, 83, 85].◦ Valores de corte: [64.5, 66.5, 68.5, 69.5, 70.5, 71.5, 73.5, 77.5, 80.5, 82.0,
84.0]
19 de 34
Aula 12 - Random Forests
Gini Gain: Exemplo 2
• Ganhos obtidos:◦ GiniGain(Temperatura(64.5)) = 0.0196232339
◦ GiniGain(Temperatura(66.5)) = 0.0068027211
◦ GiniGain(Temperatura(68.5)) = 0.0003092146
◦ GiniGain(Temperatura(69.5)) = 0.0091836735
◦ GiniGain(Temperatura(70.5)) = 0.0274376417
◦ GiniGain(Temperatura(71.5)) = 0.0008503401
◦ GiniGain(Temperatura(73.5)) = 0.0008503401
◦ GiniGain(Temperatura(77.5)) = 0.0163265306
◦ GiniGain(Temperatura(80.5)) = 0.0003092146
◦ GiniGain(Temperatura(82.0)) = 0.0068027211
◦ GiniGain(Temperatura(84.0)) = 0.0635792779⇐
20 de 34
Aula 12 - Random Forests
Gini Gain: Exemplo 2
Corte em 73.5:
Tempo Temperatura’ Umidade Vento JogarChuvoso ≤ 73.5 91 Sim NaoEnsolarado ≤ 73.5 70 Nao SimEnsolarado > 73.5 90 Sim NaoNublado > 73.5 86 Nao SimChuvoso ≤ 73.5 96 Nao SimChuvoso ≤ 73.5 70 Sim NaoNublado ≤ 73.5 65 Sim SimNublado ≤ 73.5 90 Sim SimEnsolarado > 73.5 70 Sim SimChuvoso ≤ 73.5 80 Nao SimNublado > 73.5 75 Nao SimEnsolarado > 73.5 85 Nao NaoEnsolarado ≤ 73.5 95 Nao NaoChuvoso > 73.5 80 Nao Sim
21 de 34
Aula 12 - Random Forests
Gini Gain: Exemplo 2
Tempo Temperatura’ Umidade Vento JogarChuvoso A 91 Sim NaoEnsolarado A 70 Nao SimEnsolarado B 90 Sim NaoNublado B 86 Nao SimChuvoso A 96 Nao SimChuvoso A 70 Sim NaoNublado A 65 Sim SimNublado A 90 Sim SimEnsolarado B 70 Sim SimChuvoso A 80 Nao SimNublado B 75 Nao SimEnsolarado B 85 Nao NaoEnsolarado A 95 Nao NaoChuvoso B 80 Nao Sim
22 de 34
Aula 12 - Random Forests
Criterios de parada
1. Quando todas as instancias em um no pertencem a mesma classe;
2. Todas as amostras no no sao localmente constantes:
a1 a2 classeV F 1
V F 1
V F 2
V F 1
• Classe majoritaria;
• Amostragem com pesagemprobabilıstica.
23 de 34
Aula 12 - Random Forests
Sumario
Introducao
Random ForestsAlgoritmoConstrucao das arvores
Aspectos importantesOut-of-Bag ErrorImportancia de VariaveisProximidade de Casos
Consideracoes finais
Referencias
24 de 34
Aula 12 - Random Forests
Out-of-Bag Error
• As arvores utilizam amostragem com reposicao do conjunto detreinamento original.
• Breiman afirma que cerca de 1/3 das instancias sao deixadas defora em cada arvore.
• Conjunto de “teste” com cerca de 1/3 do tamanho total da base(cada arvore)
• Out-of-Bag error : utilizacao das amostras nao utilizadas paraconstrucao da arvore:◦ Estimativa imparcial de taxa de erro;◦ Pode ser utilizada para estimar a importancia das variaveis.
25 de 34
Aula 12 - Random Forests
Importancia de variaveis
• Ideia: Avaliar o impacto que cada variavel tem na predicao.
• Para cada variavel:
1. Calcule Out-of-Bag (oob) Error;2. Permute aleatoriamente os valores da variavel nos conjuntos oob;3. Recalcule o erro oob;4. Compare o impacto no erro.
• ⇒ Ranking de importancia de atributos
26 de 34
Aula 12 - Random Forests
Proximidade de variaveis
• Ideia: Verificar similaridades entre as instancias na base detreinamento/teste.
• Uso de matriz de proximidades NxN, onde N e a quantidade deinstancias na base.
• A base e submetida a floresta.
• Cada vez que uma instancia i chega a mesma folha que a instanciaj ⇒ proxi ,j++.
• Estimativa de proximidade entre variaveis.
• Utilizada, por exemplo, para deteccao de outliers.
• Metrica util, porem custosa de ser calculada.
27 de 34
Aula 12 - Random Forests
Sumario
Introducao
Random ForestsAlgoritmoConstrucao das arvores
Aspectos importantesOut-of-Bag ErrorImportancia de VariaveisProximidade de Casos
Consideracoes finais
Referencias
28 de 34
Aula 12 - Random Forests
Random Forests X All
Fonte: Fernandez-Delgado et. al., 2014
29 de 34
Aula 12 - Random Forests
Random Forests
Duvidas?
30 de 34
Aula 12 - Random Forests
Sumario
Introducao
Random ForestsAlgoritmoConstrucao das arvores
Aspectos importantesOut-of-Bag ErrorImportancia de VariaveisProximidade de Casos
Consideracoes finais
Referencias
31 de 34
Fundamentos de Inteligencia Artificial
Referencias (1)
Leo Breiman.Random forests.Machine learning, 45(1):5–32, 2001.
Leo Breiman, Jerome Friedman, Charles J Stone, and Richard AOlshen.Classification and regression trees.CRC press, 1984.
Chao Chen, Andy Liaw, and Leo Breiman.Using random forest to learn imbalanced data.University of California, Berkeley, pages 1–12, 2004.
32 de 34
Fundamentos de Inteligencia Artificial
Referencias (2)
Manuel Fernandez-Delgado, Eva Cernadas, Senen Barro, andDinani Amorim.Do we need hundreds of classifiers to solve real worldclassification problems?J. Mach. Learn. Res., 15(1):3133–3181, January 2014.
Max Kuhn. Contributions from Jed Wing, Steve Weston, AndreWilliams, Chris Keefer, Allan Engelhardt, Tony Cooper, ZacharyMayer, Brenton Kenkel, the R Core Team, Michael Benesty,Reynald Lescarbeau, Andrew Ziem, Luca Scrucca, Yuan Tang,and Can Candan.caret: Classification and Regression Training, 2016.R package version 6.0-68.
33 de 34
Fundamentos de Inteligencia Artificial
Referencias (3)
Andy Liaw and Matthew Wiener.Classification and regression by randomforest.R news, 2(3):18–22, 2002.
Jiong Zhang, Mohammad Zulkernine, and Anwar Haque.Random-forests-based network intrusion detection systems.IEEE Transactions on Systems, Man, and Cybernetics, Part C(Applications and Reviews), 38(5):649–659, 2008.
34 de 34