Marcus Sampaio
DSC/UFCG
A Lógica dos Algoritmos
“Covering”
Marcus Sampaio
DSC/UFCG
• A estratégia é selecionar cada classe do conjuntotreinamento, 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 Sampaio
DSC/UFCG
Marcus Sampaio
DSC/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 Sampaio
DSC/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)
• ...
Regras de Classificação versus
Árvores de Decisão
Marcus Sampaio
DSC/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?
Marcus Sampaio
DSC/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
O Algoritmo “Covering” Prism
spectacle
age
astigmatism
prescriptiom
tear production
rate
Marcus Sampaio
DSC/UFCG
recommended
lens
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
Marcus Sampaio
DSC/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 Sampaio
DSC/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 Sampaio
DSC/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 Sampaio
DSC/UFCG
If ? then Recommended = hard
Age = young
Age = pre-presbyopic
Age = presbyopic
Spectacle prescription = myope
Spectacle prescription = hypermetrope
Astigmatism = no
Astigmatism = yes
Tear production rate = reduced
Tear production rate = normal
Acurácia
2/8
1/8
1/8
3/12
1/12
0/12
4/12
0/12
4/12
If Astigmatism = yes then Recommended = hard
Marcus Sampaio
DSC/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 Sampaio
DSC/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 Sampaio
DSC/UFCG
If Astigmatism = yes and ? then Recommended = hard
Age = young
2/4
Age = pre-presbyopic
1/4
Age = presbyopic
1/4
Spectacle prescription = myope
3/6
Spectacle prescription = hypermetrope
1/6
Tear production rate = reduced
0/6
Tear production rate = normal
4/6
If Astigmatism = yes and Tear production rate = normal then
Recommended = hard
Marcus Sampaio
DSC/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 Sampaio
DSC/UFCG
If Astigmatism = yes and Tear production rate = normal and ?
then Recommended = hard
Age = young
2/2
Age = pre-presbyopic
1/2
Age = presbyopic
1/2
Spectacle prescription = myope
3/3
Spectacle prescription = hypermetrope
1/3
If Astigmatism = yes and Tear production rate = normal and
Spectacle prescription = myope then Recommended = hard
Marcus Sampaio
DSC/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 conjuntotreinamento sem as 3 instâncias (24 – 3 = 21
instâncias)
Marcus Sampaio
DSC/UFCG
If ? then Recommended = hard
...
If Age = young and Astigmatism = yes and
Tear production rate = normal
then Recommended = hard
Note que, quanto mais complexa (= mais cláusulas
conjuntivas) a regra, maior a probabilidade de
“overfitting”
A regra acima só cobre uma instância
Marcus Sampaio
DSC/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 Sampaio
DSC/UFCG
Marcus Sampaio
DSC/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
Prism Processado
com WEKA
Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG