Levantamento de Dados em Pesquisa - Aula 05

Prévia do material em texto

1
Levantamento de Dados
Classificação
Classificação
• Dado um banco de dados com N objetos 
D={O1,O2,…,On} e um conjunto de classes 
C={C1,…,Cm}, o problema da classificação 
consiste de definir um mapeamento 
f:D�C onde cada Oi é associado a uma 
classe
Classificação
• Dada um conjunto de objetos de dados a 
classificação deve ser encontrar um 
modelo capaz de dizer a qual classe o 
objeto pertence baseado nos atributos do 
objeto
• Um objetivo deve ser modelar objetos não 
vistos da melhor forma possível 
Classificação
• Conjunto de treinamento: subconjunto dos 
dados que é usados para treinar o 
algoritmo de classificação
• Conjunto de teste: subconjunto dos dados 
diferente do conjunto de treinamento que 
é utilizado para validar o modelo de 
classificação
Classificação
• Reconhecimento de fala: Classificar os 
sons em fonemas e formar palavras
• Reconhecimento tridimensional de 
imagens: Dados os pixels da imagem 
classificar as formas originais
• Reconhecimento de estrutura de 
proteínas: dada a seqüência de 
aminoácidos identificar os motivos da 
estrutura
Classificação
• Classificar o comportamento de um 
usuário no sistema como normal ou 
tentativa de invasão
• Dada uma imagem médica detectar se 
existe tumor ou não
• Verificar se existe um texto contém ou não 
uma característica
2
Classificação
• Verdadeiro positivo: Quando uma classe é atribuída a 
um objeto e esta classe é a correta (HIV positivo para 
pessoa doente) 
• Falso positivo: Quando uma classe é atribuída a um 
objeto e esta classe está errada (HIV positivo para 
pessoa saudável)
• Verdadeiro negativo: Quando uma classe não é 
atribuída a um objeto e o objeto realmente é de outra 
classe (HIV negativo para pessoa saudável)
• Falso negativo: Quando uma classe não é atribuída a 
um objeto e o objeto era daquela classe (HIV negativo 
para pessoa doente)
Árvore de Decisão
• Árvores de Decisão: dividem os atributos 
de valores (<,>, =) 
• Usam uma seqüência de regras para 
decidir se um objeto pertence a uma 
classe ou não
• Particiona o espaço em regiões 
retangulares 
• Os nós da Árvore são atributos os arcos 
são valores possíveis 
Árvore de Decisão
• Fáceis de entender
• Algoritmos relativamente rápidos
• Lida com todos os tipos de dados
• Útil para problemas reais
• Pode ser mapeado para regras sobre 
invasão, regras sobre negócios, etc.
Árvore de Decisão
Dado: 
– D = {O1, …, On} onde cada objeto Oi contém uma lista de valores Oi=<Oi1, …, Oih> 
– O banco de dados contém os nomes dos atributos 
{A1, A2, …, Ah}
– O conjunto de classes possíveis é C={C1, …., Cm}
Uma árvore de decisão ou classificação é uma estrutura D 
tal que:
– Cada nó é nomeado com um atributo Ai
– Cada arco é associado com uma característica (faixa 
de valores) aplicado ao atributo no nó
– Cada nó folha é nomeada com uma classe Cj
Classificação Ex: Menções
• Se x >= 90 então SS
• Se 70<=x<90 então 
MS
• Se 50<=x<70 então 
MM
• Se 30<=x<50 então 
MI
• Se x<30 então II
>=90<90
x
>=70<70
x
>=50<50
x
II
MS
SS
>=30<30
x MM
MI
Classificação Ex: Menções
3
Classificação Árvore de Decisão
Tid Refund Marital
Status
Taxable
Income Cheat
1 Yes Single 125K No
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No
10 No Single 90K Yes
10
ca
teg
or
ica
l
ca
teg
or
ica
l
co
nti
nu
ou
s
cla
ss
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
MarriedSingle, Divorced
< 80K > 80K
Splitting Attributes
Treinamento Árvore de Decisão
Árvore de Decisão
Tid Refund Marital
Status
Taxable
Income Cheat
1 Yes Single 125K No
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No
10 No Single 90K Yes
10
ca
teg
or
ica
l
ca
teg
or
ica
l
co
nti
nu
ou
s
cla
ss MarSt
Refund
TaxInc
YESNO
NO
NO
Yes No
Married
Single, 
Divorced
< 80K > 80K
There could be more than one tree that 
fits the same data!
Árvore de Decisão
Apply 
Model
Learn 
Model
Tid Attrib1 Attrib2 Attrib3 Class 
1 Yes Large 125K No 
2 No Medium 100K No 
3 No Small 70K No 
4 Yes Medium 120K No 
5 No Large 95K Yes 
6 No Medium 60K No 
7 Yes Large 220K No 
8 No Small 85K Yes 
9 No Medium 75K No 
10 No Small 90K Yes 
10 
 
Tid Attrib1 Attrib2 Attrib3 Class 
11 No Small 55K ? 
12 Yes Medium 80K ? 
13 Yes Large 110K ? 
14 No Small 95K ? 
15 No Large 67K ? 
10 
 
Árvore de Decisão
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
MarriedSingle, Divorced
< 80K > 80K
Refund Marital 
Status 
Taxable 
Income Cheat 
No Married 80K ? 
10 
 
Test Data
Start from the root of tree.
Árvore de Decisão
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
MarriedSingle, Divorced
< 80K > 80K
Refund Marital 
Status 
Taxable 
Income Cheat 
No Married 80K ? 
10 
 
Test Data
4
Árvore de Decisão
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
MarriedSingle, Divorced
< 80K > 80K
Refund Marital 
Status 
Taxable 
Income Cheat 
No Married 80K ? 
10 
 
Test Data
Árvore de Decisão
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
Married Single, Divorced
< 80K > 80K
Refund Marital 
Status 
Taxable 
Income Cheat 
No Married 80K ? 
10 
 
Test Data
Árvore de Decisão
Refund
MarSt
TaxInc
YESNO
NO
NO
Yes No
Married Single, Divorced
< 80K > 80K
Refund Marital 
Status 
Taxable 
Income Cheat 
No Married 80K ? 
10 
 
Test Data
Assign Cheat to “No”
Árvore de Decisão – Hunt
• Seja Dt o conjunto de dados de 
treinamento que chega até o nó 
atual t
• Algoritmo (recursivo):
– Se Dt contém apenas objetos 
que pertencem a mesma classe 
yt então o nó atual é 
considerado um nó folha e é 
chamado de yt
– Se Dt é um conjunto vazio 
então o nó atual é folha e a ele 
é associada a classe default yd
– Se Dt contém objetos que 
pertencem a mais de uma 
classe então se usa o teste de 
valor do atributo para dividir o 
conjunto em subconjunto 
menores
Tid Refund Marital 
Status 
Taxable 
Income Cheat 
1 Yes Single 125K No 
2 No Married 100K No 
3 No Single 70K No 
4 Yes Married 120K No 
5 No Divorced 95K Yes 
6 No Married 60K No 
7 Yes Divorced 220K No 
8 No Single 85K Yes 
9 No Married 75K No 
10 No Single 90K Yes 
1 0 
 
Dt
?
Hunt
Don’t 
Cheat
Refund
Don’t 
Cheat
Don’t 
Cheat
Yes No
Refund
Don’t 
Cheat
Yes No
Marital
Status
Don’t 
Cheat
Cheat
Single,
Divorced Married
Taxable
Income
Don’t 
Cheat
< 80K >= 80K
Refund
Don’t 
Cheat
Yes No
Marital
Status
Don’t 
Cheat
Cheat
Single,
Divorced Married
Tid Refund Marital
Status
Taxable
Income Cheat
1 Yes Single 125K No
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No
10 No Single 90K Yes
10
Árvore de Decisão
• Algoritmo greedy: procurar a árvore que 
otimiza o resultado de acordo com um 
determinado critério
• A forma dividir os conjuntos tem influencia 
no resultado
• Vários critérios podem ser usados na 
divisão
• Necessário dizer qual a profundidade 
máxima da árvore
5
Árvore de Decisão
• O teste da condição depende do tipo dos 
atributos
– Nominais
– Ordinais
– Contínuos
• Várias divisões podem serfeitas em 2 ou 
mais arcos
Árvore de Decisão
• Separação de atributo nominal em vários arcos:
• Separação de atributo nominal em dois arcos 
(binária) 
CarType
Family
Sports
Luxury
CarType{Family, 
Luxury} {Sports}
CarType{Sports, 
Luxury} {Family}
Árvore de Decisão
• Separação de atributo ordinal em todos os 
valores possíveis .
• Separação de atributo ordinal em dois 
valores possíveis
Size
Small
Medium
Large
Size{Medium, 
Large} {Small}
Size{Small, 
Medium} {Large}
Size{Small, 
Large} {Medium}
Árvore de Decisão
• Atributos contínuos: 
– Os valores podem ser discretizados de várias 
formas ( divisão igual, por freqüência, etc)
– Decisão binária: divide valores com (<=, < < , 
>, >=). Encontrar o ponto do corte pode ser 
difícil
Árvore de Decisão