Upload
marcelo-alves
View
214
Download
0
Embed Size (px)
Citation preview
Marcus SampaioDSC/UFCG
Marcus SampaioDSC/UFCG
A Lógica dos Algoritmos“Covering”
• A estratégia é selecionar cada classe do conjunto-treinamento, e procurar as regras condições ou o antecedente que 'cobrem' ("cover") as instâncias da classe, por sucessivos refinamentos– Se ? então classe X
• Note que o objetivo pode não ser cobrir todas as instâncias de uma classe, ou pode não ser obter regras puras– Acurácia de treinamento de 100% pode não ser a meta
• Regras do tipo– Se <conjunção_de_condições> então
(<atributo_de_classificação> = <classe>)
Marcus SampaioDSC/UFCG
Marcus SampaioDSC/UFCG
• Regras para a classe a– Primeiro refinamento
• se x > 1.2 então classe = a– Segundo refinamento
• se x > 1.2 e y > 2.6 então classe = a– Terceiro refinamento (ainda existe a não coberto)
• ...
Marcus SampaioDSC/UFCG
• Regras para a classe b– Primeiro refinamento
• se x 1.2 então classe = b– Segundo refinamento
• se x 1.2 então classe = b• se x > 1.2 e y 2.6 então classe = b
– Terceiro refinamento (a segunda regra é impura)• ...
Marcus SampaioDSC/UFCG
• Árvore de decisão– Conjunto de regras– Cada regra é um ‘galho’ da árvore
• Um algoritmo "covering" produz regras diferentes daquelas obtidas de árvores de decisão, para o mesmo conjunto-treinamento
• Dado um conjunto-treinamento, quem é melhor– Árvore de Decisão?– Regras de Classificação stricto sensu?
Regras de Classificação versus Árvores de Decisão
Marcus SampaioDSC/UFCG
• A diferença essencial entre algoritmos de árvore de decisão e algoritmos “covering” reside no tipo de abordagem– Árvore de decisão: top down
• Primeiro, o antecedente; depois, a classe
– “Covering”: bottom up• Primeiro, a classe; depois, o antecedente
Marcus SampaioDSC/UFCGO Algoritmo “Covering” Prism
young myope no reduced none
young myope no normal soft
young myope yes reduced none
young myope yes normal hard
young hypermetrope no reduced none
young hypermetrope no normal soft
agespectacle
prescriptiomastigmatism tear production
raterecommendedlens
Marcus SampaioDSC/UFCG
young hypermetrope yes reduced none
young hypermetrope yes normal hard
pre-presbyopic myope no reduced none
pre-presbyopic myope no normal soft
pre-presbyopic myope yes reduced none
pre-presbyopic myope yes normal hard
Marcus SampaioDSC/UFCG
pre-presbyopic hypermetrope no reduced none
pre-presbyopic hypermetrope no normal soft
pre-presbyopic hypermetrope yes reduced none
pre-presbyopic hypermetrope yes normal none
presbyopic myope no reduced none
presbyopic myope no normal none
Marcus SampaioDSC/UFCG
presbyopic myope yes reduced none
presbyopic myope yes normal hard
presbyopic hypermetrope no reduced none
presbyopic hypermetrope no normal soft
presbyopic hypermetrope yes reduced none
presbyopic hypermetrope yes normal none
Marcus SampaioDSC/UFCG
If ? then Recommended = hardAge = young 2/8Age = pre-presbyopic 1/8Age = presbyopic 1/8Spectacle prescription = myope 3/12 Spectacle prescription = hypermetrope 1/12 Astigmatism = no 0/12Astigmatism = yes 4/12Tear production rate = reduced 0/12 Tear production rate = normal 4/12If Astigmatism = yes then Recommended = hard
Acurácia
Marcus SampaioDSC/UFCG
young myope yes reduced none
young myope yes normal hard
young hypermetrope yes reduced none
young hypermetrope yes normal hard
pre-presbyopic myope yes reduced none
pre-presbyopic myope yes normal hard
Marcus SampaioDSC/UFCG
pre-presbyopic hypermetrope yes reduced none
pre-presbyopic hypermetrope yes normal none
presbyopic myope yes reduced none
presbyopic myope yes normal hard
presbyopic hypermetrope yes reduced none
presbyopic hypermetrope yes normal none
Marcus SampaioDSC/UFCG
If Astigmatism = yes and ? then Recommended = hardAge = young 2/4Age = pre-presbyopic 1/4Age = presbyopic 1/4Spectacle prescription = myope 3/6Spectacle prescription = hypermetrope 1/6Tear production rate = reduced 0/6Tear production rate = normal 4/6
If Astigmatism = yes and Tear production rate = normal then Recommended = hard
Marcus SampaioDSC/UFCG
• Buscar regras exatas (ou perfeitas, ou puras)
young myope yes normal hard
young hypermetrope yes normal hard
pre-presbyopic myope yes normal hard
pre-presbyopic hypermetrope yes normal none
presbyopic myope yes normal hard
presbyopic hypermetrope yes normal none
Marcus SampaioDSC/UFCG
If Astigmatism = yes and Tear production rate = normal and ? then Recommended = hardAge = young 2/2Age = pre-presbyopic 1/2Age = presbyopic 1/2Spectacle prescription = myope 3/3Spectacle prescription = hypermetrope 1/3
If Astigmatism = yes and Tear production rate = normal and Spectacle prescription = myope then Recommended = hard
Marcus SampaioDSC/UFCG
• A regra só cobre 3 das 4 instâncias ‘hard’• O algoritmo remove então as 3 instâncias já
cobertas, e começa de novo, para o conjunto-treinamento sem as 3 instâncias (24 – 3 = 21 instâncias)
Marcus SampaioDSC/UFCG
If ? then Recommended = hard...If Age = young and Astigmatism = yes andTear production rate = normalthen Recommended = hard
Note que, quanto mais complexa (= mais cláusulasconjuntivas) a regra, maior a probabilidade de “overfitting” A regra acima só cobre uma instância
Marcus SampaioDSC/UFCG
• Suponha que todas as instâncias classificadas como 'hard' foram cobertas
• O algoritmo prossegue com as instâncias classificadas como 'soft', e assim por diante
Marcus SampaioDSC/UFCG
Marcus SampaioDSC/UFCG
• Note que uma regra exata não é necessariamente boa “overfitting” , se– Cobrir poucas instâncias (baixa qualidade
estatística)– Muito complexa (cláusula conjuntiva muito grande)– As duas coisas
• Uma versão mais sofisticada do Prism – Analisa a qualidade das regras exatas– Pode gerar regras não exatas, porém com maior
valor estatístico• Mecanismos específicos de poda
– A meta é uma boa acurácia de previsão
Marcus SampaioDSC/UFCG
Prism Processadocom WEKA
Marcus SampaioDSC/UFCG