24
Marcus Sampaio DSC/UFCG

Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

Embed Size (px)

Citation preview

Page 1: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

Marcus SampaioDSC/UFCG

Page 2: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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>)

Page 3: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

Marcus SampaioDSC/UFCG

Page 4: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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)

• ...

Page 5: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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)• ...

Page 6: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 7: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 8: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 9: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 10: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 11: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 12: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 13: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 14: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 15: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 16: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 17: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 18: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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)

Page 19: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 20: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 21: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

Marcus SampaioDSC/UFCG

Page 22: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

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

Page 23: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

Marcus SampaioDSC/UFCG

Prism Processadocom WEKA

Page 24: Marcus Sampaio DSC/UFCG. Marcus Sampaio DSC/UFCG A Lógica dos Algoritmos “Covering” A estratégia é selecionar cada classe do conjunto- treinamento, e

Marcus SampaioDSC/UFCG