Seminario classificadores

Classificadores

Cleiane GonCleiane Gonççalves Oliveiraalves OliveiraMestrado em Ciência da Computação

Universidade Federal de Uberlândia

Agenda

� A tarefa de classificação

� Um classificador lazy: KNN

� Um classificador eager: Redes bayesianas

� A ferramenta WEKA

A tarefa de Classificação

� Seguradora de automóveis

Sexo Idade Acidente

F 45 Não

M 25 Sim

F 18 Não

F 32 Não

M 37 Não

M 18 Sim

A tarefa de Classificação

� Seguradora de automóveis

Sexo Idade Acidente

F 45 Não

F 18 Não

F 32 Não

M 37 Não

M 18 Sim

M 25 Sim

Classificadores

� O que é um classificador?

� Classificação é uma técnica que consiste na aplicação de um conjunto

de exemplos pré-classificados para desenvolver um modelo capaz de

classificar uma população maior de registros.

Etapas do Processo

REGRAS

Classificador

Amostras

Classificadas Banco de

Testes

REGRAS CONFIÁVEIS

Etapas do Processo

Amostras

Classificadas

Amostras classificadas

Nome Idade Renda Profissão Classe

Daniel ≤ 30 Média Estudante Sim

João 31..50 Média-Alta Professor Sim

Carlos 31..50 Média-Alta Engenheiro Sim

Maria 31..50 Baixa Vendedora Não

Paulo ≤ 30 Baixa Porteiro Não

Otavio > 60 Média-Alta Aposentado Não

Etapas do Processo

REGRAS

Classificador

Amostras

Classificadas

Regras

� Se � idade = 41..50 e

�Renda = Media-Alta

então ClasseProdEletr = Sim.

� Se �Renda = Baixa

então ClasseProdEletr = Nao.

Etapas do Processo

REGRAS

Classificador

Amostras


Testes

Banco de testesNome Idade Renda Profissão Classe

Pedro 41 .. 50 Média-Alta Ecologista Não

José 41 .. 50 Média-Alta Professor Não

Luiza 41 .. 50 Média-Alta Assistente Social Não

Carla ≤ 30 Baixa Vendedora Não

Wanda ≤ 30 Baixa Faxineira Não

Felipe > 60 Média-Alta Aposentado Não

Se idade = 41..50 e Renda = Media-Alta

então ClasseProdEletr = Sim.

Se Renda = Baixa

então ClasseProdEletr = Nao.

Acurácia: 50%Acurácia: 50%

Etapas do Processo

REGRAS

Classificador

Amostras


Testes

REGRAS CONFIÁVEIS

Classificadores

� Classificadores lazy

�Método kNN (k-nearest-neighbor)

�Case-Based Reasoning (CBR)

Classificadores

� Classificadores eager

�Arvores de Decisão

�Redes Neuronais

�Redes Bayseanas

�Máquinas de Suporte Vetorial

KNN

Método

Dados: Banco de Dados de m tuplas classificadas (a1,...,an,C)

Método

Uma tupla X = (x1,...,xn) não classificada

Calcula-se a distância

de X a cada uma das

tuplas do banco de

dados.

Método

Pega-se as k tuplas do banco de dados mais

próximas de X.

A classe de X é a

classe que aparece

com mais frequência

entre as k tuplas mais

próximas de X.K = 3

Diferentes valores de K

K = 1 K = 2 K = 3

Banco de Dados com tuplas classificadas

� Qualidade de lenço de papel

X1 = durabilidade (segundos)

X2 = força (kg/metro quadrado)

Classificação

7 7 Ruim

7 4 Ruim

3 4 Bom

1 4 Bom

Tupla não classificada

� Qualidade de lenço de papel

X1 = durabilidade (segundos)

X2 = força (kg/metro quadrado)

Classificação

7 7 Ruim

7 4 Ruim

3 4 Bom

1 4 Bom

3 7 ?

Calcular a distância

� Distância Euclidiana

� Distância de Mahalanobis.

� Distância de Minkowsky.

� Hamming Distance.


� Distância Euclidiana

� As coordenadas das tuplas (px,py)

� As coordenadas da tupla a ser classificada (qx,qy)

∑=

−=

n

i

ii qpqpd1

2)(),(


X1 X2 Cálculo Resultado Classe Ranking

7 7 (7-3)2 + (7-7)2 16 Ruim

7 4 (7-3)2 + (4-7)2 25 Ruim

3 4 (3-3)2 + (4-7)2 9 Bom

1 4 (1-3)2 + (4-7)2 13 Bom

� K = 3

4

3

2

1

BOM!!!

Questões diversas

� Como calcular a distância quando existem

atributos cujos valores não são numéricos,

por exemplo o atributo Cor ?

� O que fazer quando a tupla a ser

classificada é incompleta, isto é, alguns

campos estão faltando ?

� Como determinar o melhor valor de k?

Considerações

� Técnica simples e facilmente

implementada

� Dispendiosa computacionalmente

� Necessidade de determinar o valor de K

� O tipo de cálculo de distância escolhido

pode gerar melhores resultados.

Aplicações

� Reconhecimento de voz

� Classificação de animais

� Mapas, definição de fronteiras

� Classificação automática de textos e

imagens

Redes Bayesianas

Rede Bayesiana

Z

X Y

Valores de X = { 1, 3}

Valores de Y = {2,4}

Valores de Z = {5,6}

X = 1

Y = 2

X = 1

Y = 4

X = 3

Y = 2

X = 3

Y = 4

Z = 5 0.5 0.3 0.2 0.1

Z = 6 0.5 0.7 0.8 0.9

P[Z |{X,Y}]

Como classificar usando uma Rede Bayesiana de Crença

� Output: P[C1|X], P[C2|X], ..., P[Cn|X]

� Input:

�um banco de tuplas classificadas

�uma rede bayseana de crença

�Um atributo da rede selecionado como sendo o atributo classe

�Uma tupla X a ser classificada.

Exemplo Histórico

FamiliarFumante

Efisema

DispnéiaRaio

X+

Câncer

Pulmão

Exemplo HF= 1

F = 1

HF= 1

F = 0

HF= 0

F = 1

HF= 0

F = 0

1 0.8 0.5 0.7 0.1

0 0.2 0.5 0.3 0.9

F=1 F= 0

1 0.03 0.2

0 0.97 0.8

CP=1 CP=0

1 0.9 0.02

0 0.1 0.98

HF F

CP E

DRX+

HF =história familiar E = Efisema

F = fumante D = Dispnéia

CP = câncer de pulmão RX+ = raio X +

CPT(CP)

CPT(E) CPT(RX+)

CPT(D)

CP=1

E=1

CP=1

E=0

CP=0

E=1

CP=0

E=0

1 0.99 0.3 0.2 0.01

0 0.01 0.7 0.8 0.99

X = (HF=1, F=1, E = 0, RX+ = 1, D=0)

Cálculo das probabilidades

P[C|X]

Teorema de Bayes

P[C|X] = P[X|C] * P[C]P[X]

P[x1|pais(x1)] * P[x2|pais(x2)] * ...* P[xn|pais(xn)]* P[Ci|pais(Ci)]

Cálculos

X = (HF=1, F=1, E = 0, RX+ = 1, D=0)

P[X|CP=0] * P[CP=0] =

HF F

CP E

DRX+P[HF=1] *

P[F=1] *

P[E=0 | F=1] *

P[RX=1 |CP=0]*

P[D=0 |CP=0, E=0] *

P[CP=0 | HF = 1, F=1).

Exemplo HF= 1

F = 1

HF= 1

F = 0

HF= 0

F = 1

HF= 0

F = 0

1 0.8 0.5 0.7 0.1

0 0.2 0.5 0.3 0.9

F=1 F= 0

1 0.03 0.2

0 0.97 0.8

CP=1 CP=0

1 0.9 0.02

0 0.1 0.98

HF F

CP E

DRX+




CPT(CP)

CPT(E) CPT(RX+)

CPT(D)

CP=1

E=1

CP=1

E=0

CP=0

E=1

CP=0

E=0

1 0.99 0.3 0.2 0.01

0 0.01 0.7 0.8 0.99

X = (HF=1, F=1, E = 0, RX+ = 1, D=0)

Cálculos

X = (HF=1, F=1, E = 0, RX+ = 1, D=0)

P[X|CP=0] * P[CP=0] =

1 *

1 *

0,97 *

0,02 *

0,99 *

0,2

HF F

CP E

DRX+

= 0,00384

Cálculos

X = (HF=1, F=1, E = 0, RX+ = 1, D=0)

P[X|CP=1] * P[CP=1] =

HF F

CP E

DRX+P[HF=1] *

P[F=1] *

P[E=0 | F=1] *

P[RX=1 |CP=1]*

P[D=0 |CP=1, E=0] *

P[CP=1 | HF = 1, F=1).

Exemplo HF= 1

F = 1

HF= 1

F = 0

HF= 0

F = 1

HF= 0

F = 0

1 0.8 0.5 0.7 0.1

0 0.2 0.5 0.3 0.9

F=1 F= 0

1 0.03 0.2

0 0.97 0.8

CP=1 CP=0

1 0.9 0.02

0 0.1 0.98

HF F

CP E

DRX+




CPT(CP)

CPT(E) CPT(RX+)

CPT(D)

CP=1

E=1

CP=1

E=0

CP=0

E=1

CP=0

E=0

1 0.99 0.3 0.2 0.01

0 0.01 0.7 0.8 0.99

X = (HF=1, F=1, E = 0, RX+ = 1, D=0)

Cálculos

X = (HF=1, F=1, E = 0, RX+ = 1, D=0)

P[X|CP=1] * P[CP=1] =

1 *

1 *

0,97 *

0,9 *

0,7 *

0,8

HF F

CP E

DRX+

= 0,48 > 0,00384

X = CP = 1

Aplicações

� Diagnóstico médico

� Aprendizado de mapas

� Sistema de exploração e aquisição de

conhecimento espacial

� Interpretação de linguagem

� Visão

Projetos

� ABS-Bayes: Sistema Especialista Probabilístico para Apoio ao Diagnóstico de Absenteísmo

� Agente Bayesiano de Apoio à Vigilância de Infecção Hospitalar - SAVIH

� Sistema especialista probabilístico para apoio ao diagnóstico de potencial econômico – SEPE

� Sistema de Avaliação da Evasão Escolar: E-Bayes

� Sistema Especialista de Apoio à Nutrição Enteral Pediátrica - SANEP

� Sistema de Avaliação do Crescimento Infantil - SACI

WEKA

Waikato Environment for Knowledge Analysis

Arquivo .ARFF@relation jogar_golfe

@attribute ceu {sol, nublado, chuva}

@attribute temperatura {alta,baixa,suave}

@attribute umidade {alta, normal}

@attribute vento {sim, nao}

@attribute classe {sim, nao}

@data

sol,alta,alta,nao,nao

sol,alta,alta,sim,nao

nublado,alta,alta,nao,sim

chuva,alta,alta,nao,sim

chuva,baixa,normal,nao,sim

chuva,baixa,normal,sim,nao

nublado,baixa,normal,sim,sim

Interface

� Weka

� Carregando arquivos

� Classificadores

� Executando um classificador Knn

�Algoritmo Ibk

�Correctly Classified Instances

�Matriz de discussão

� Executando um classificador bayesiano

�Algoritmo BayesNet

�Correctly Classified Instances

�Matriz de discussão

�Gráfico da rede bayesiana

�Utilização de algoritmos de busca para a confecção da rede e CPT

� Obrigada!

Technology

Seminario classificadores