07 - ClassificaçãoKNN

Prévia do material em texto

CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Minerac¸a˜o de Dados: Classificac¸a˜o - Aula 07
CEA462 - Sistemas de Apoio a` Decisa˜o
Janniele Aparecida Soares
Outubro, 2014
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Introduc¸a˜o
Classificac¸a˜o e´ a tarefa de organizar objetos em diferentes
categorias
Classificac¸a˜o de ce´lulas como benignas ou cancer´ıgenas.
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Definic¸o˜es
Um algoritmo de classificac¸a˜o recebe dados de entrada (exemplos).
Cada exemplo (x, y) tem um conjunto de atributos (x) e um ro´tulo
associado (y).
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Definic¸o˜es
Exemplos
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Definic¸o˜es
Formato de entrada de dados a ser considerado
csv (compat´ıvel com excel)
Cada exemplo compo˜e uma linha
Atributos sa˜o separados por “;”
A classe e´ o u´ltimo elemento de cada linha (exemplo)
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Abordagem Geral para Resoluc¸a˜o de um Problema
de Classificac¸a˜o
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Abordagem Geral para Classificac¸a˜o
Como avaliar um algoritmo de classificac¸a˜o?
Matriz de confusa˜o:
Acerto
Erro
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Abordagem Geral para Classificac¸a˜o
Como avaliar um algoritmo de classificac¸a˜o?
Me´trica de desempenho.
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
“Se caminhar como um pato, se grasnar como um pato e
se parecer com um pato, enta˜o provavelmente e´ um pato”.
Representa cada exemplo como um ponto em um espac¸o
d-dimensional, onde d e´ o nu´mero de dimenso˜es
Dado um exemplo de teste, calcula-se a proximidade dele
aos demais pontos de dados.
O exemplo de teste sera´ classificado com classe igual a`
classe predominante nos k pontos mais pro´ximos.
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Da´ı o nome K-NN (K-Nearest Neighbors)
Onde k e´ um paraˆmetro.
Exemplo num plano bidimensional
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Como calcular a proximidade entre dois pontos (exemplos)?
Distaˆncia euclidiana d(x , y) =
√∑n
k=1(xk − yk)2
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Algoritmo
Calcula a distaˆncia entre cada exemplo de teste e todos os exemplos de
treinamento.
Determina uma lista de vizinhos mais pro´ximos.
Atrave´s da lista o exemplo teste e´ classificado baseado na classe marjorita´ria
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Pseudocodigo
classificadorKNN(nu´mero de vizinhos k, conjunto de treinamento D,
conjuto de exemplos de teste T)
1. para cada exemplo de teste z ∈ T fac¸a
2. Calcule d(z, x), a dista^ncia entre z e cada exemplo x ∈ D.
3. Selecione Dz ⊆ D conjunto dos k exemplos de treinamento de z
4. classe z = classe de maior incide^ncia dentre k ∈ Dz
5. fim para
fimClassificador
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Caracter´ısticas
Faz parte de uma te´cnica geral conhecida como descoberta baseada em
instaˆncias que usa instaˆncias de treinamento para fazer previso˜es sem ter
que manter uma abstrac¸ao derivada dos dados.
Na˜o requer a construc¸a˜o de modelos.
Fazem previso˜es baseadas em informac¸o˜es locais.
Definem limites de decisa˜o mais flex´ıvel.
Podem produzir previso˜es erradas caso o pre´-processamento de dados e
medidas de proximidades estejam inapropriadas.
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Normalizac¸a˜o
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Dados de treinamento no plano
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Teste
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Teste (considerando k = 3)
d(10, 1) =
√
(0, 80− 0, 02)2 + (0, 50− 0, 25)2 = 0, 82
d(10, 2) =
√
(0, 80− 1, 00)2 + (0, 50− 0, 50)2 = 0,19 2
d(10, 3) =
√
(0, 80− 0, 08)2 + (0, 50− 1, 00)2 = 0, 88
d(10, 4) =
√
(0, 80− 0, 22)2 + (0, 50− 0, 25)2 = 0, 64
d(10, 5) =
√
(0, 80− 0, 04)2 + (0, 50− 0, 75)2 = 0, 80
d(10, 6) =
√
(0, 80− 0, 18)2 + (0, 50− 0, 00)2 = 0, 80
d(10, 7) =
√
(0, 80− 0, 67)2 + (0, 50− 0, 50)2 = 0,14 2
d(10, 8) =
√
(0, 80− 0, 00)2 + (0, 50− 0, 25)2 = 0, 84
d(10, 9) =
√
(0, 80− 0, 35)2 + (0, 50− 0, 25)2 = 0,52 2
Classe de 10 e´ 2
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Teste (considerando k = 3)
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Teste (considerando k = 3)
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Classificador de Vizinho Mais Pro´ximo
Teste (considerando k = 3)
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Exerc´ıcio
Considere
K = 1
K = 3
K = 5
K = 7
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Avaliando o Desempenho de um Classificador
Me´todo Holdout
Dados originais com exemplos rotulados sa˜o particionados em um conjunto
de treinamento e outro de teste.
2/3 para treinamento e 1/3 para teste
Se o conjunto de dados for pequeno, poucos exemplos servira˜o para avaliar
o desempenho.
Pode ser tendencioso (e.g. nos 1/3 de teste haver apenas exemplos de uma
classe)
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Avaliando o Desempenho de um Classificador
Validac¸a˜o cruzada
Particiona o conjunto de dados em k partes (tipicamente k = 10)
A cada iterac¸a˜o i, o conjunto ki e´ selecionado para teste e os demais para
treinamento.
A precisa˜o e´ dada pelame´dia da precisa˜o nas k iterac¸o˜es.
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Avaliando o Desempenho de um Classificador
Validac¸a˜o cruzada
Exemplo, considerando k = 5, onde exemplos de treinamento e de teste
esta˜o realc¸ados em.
Considera todos os dados no teste.
Computacionalmente custoso: repetir a classificac¸a˜o k vezes.
A precisa˜o e´ dada pela me´dia da precisa˜o nas k iterac¸o˜es.
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Trabalhos de Classificac¸a˜o
Considere
Prevendo a idade de abalone a partir de medic¸o˜es f´ısicas.
A idade deste molusco e´ determinada pelo corte da concha
atrave´s do cone, manchas, e contando o nu´mero de ane´is
por meio de um microsco´pio.
O nu´mero de ane´is e´ o valor de predic¸a˜o como uma
classificac¸a˜o para o problema.
Usar a base de dados de treinamento Abalone para validar
o trabalho.
crie 9 exemplos de teste para valida-los.
http://archive.ics.uci.edu/ml/
machine-learning-databases/abalone/.
CEA462 -
Sistemas de
Apoio a`
Decisa˜o - Aula
07
Janniele A.
Soares
Introduc¸a˜o
KNN
Avalizando
Desempenho
Bibliografia
Introduc¸a˜o ao Data Mining. Steinbach, Michael; Kumar, Vipin; Tan,
Pang-ning, Rio de Janeiro: Ed. Cieˆncia Moderna, 2009. Cap´ıtulos 1
e 2.
	Introdução
	KNN
	Avalizando Desempenho