Marcus Sampaio
DSC/UFCG
A Lógica dos Algoritmos
“Covering”
Marcus Sampaio
DSC/UFCG
• A estratégia é selecionar cada classe do
conjunto-treinamento, e procurar as regras
que 'cobrem' ("covers") as instâncias da
classe
• Regras do tipo
– Se <conjunção_de_condições> então
(<atributo_de_classificação> = <classe>)
A Lógica … (2)
Marcus Sampaio
DSC/UFCG
A Lógica … (3)
• 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
• ...
Marcus Sampaio
DSC/UFCG
A Lógica … (4)
• 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
• ...
Marcus Sampaio
DSC/UFCG
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
O Algoritmo Prism
spectacle
age
astigmatism
prescriptiom
tear production
rate
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 = myope
Astigmatism = no
Astigmatism = yes
Tear production rate = reduced
Tear production rate = normal
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
O Algoritmo Prism (9)
• 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 = myope
1/3
If Astigmatism = yes and Tear production rate = normal and
Spectacle prescription = myope then Recommended = hard
O Algoritmo Prism (11)
Marcus Sampaio
DSC/UFCG
• A regra só cobre 3 das 4 instâncias
• O algoritmo remove então as 3 instâncias já
cobertas, e começa de novo, para o conjuntotreinamento restante (24 instâncias – 3
instâncias = 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”
O Algoritmo Prism (13)
Marcus Sampaio
DSC/UFCG
• Nesta altura, 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
O Algoritmo Prism (15)
Marcus Sampaio
DSC/UFCG
• Note que uma regra exata não é
necessariamente boa  “overfiting” , 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