k-NN e
Funções de Dissimilaridade
Tiago Buarque
<[email protected]>
Roteiro
•
•
•
•
Motivação
Definições
k-NN
Funções de Dissimilaridade
– Entre atributos numéricos
– Entre atributos categóricos
– Funções de disssililaridade heterogênias
• Testes
• Referências
Motivação
• NCM [Wang 2006]
• Funções de Distância
– Problema não resolvido
– Grande aplicabilidade
• Aprendizagem de Máquina
– Classificadores
– IBL
• k-NN
– Redes Neurais
• RBF
• Kohonen
– Agrupamento
• k-means
Definições
• Base de dados
– Conjunto de elementos
• Elemento ou instância (E)
– E = {v, c}
– v, é um vetor de atributos
– c, classe
• Classificador
– C(v) = c
– C : dom(v)  dom(c)
Definições [2]
• Atributo (vetor de atributos)
–
–
–
–
Nominal ou Categórico
Ordinal
Intervalar
Racional ou Numérico
• Funções de Dissimilaridade
d ( x, y) : V V  
x, y V  {conjuntodos vetores de atributos}
Tipos de Dados
• Domínio da Base de Dados
– Vetor de atributos com n elementos
– Posição a, 1 ≤ a ≤ n, do vetor tem o mesmo tipo para
todos os elementos da base
– Se a é categórico, existe dom(a)
• Todos os possíveis valores no conjunto de treino
– Se a é numérico, existe max(a) e min(a)
• O máximo e o mínimo assumido por esse atributo entres os
elementos da base de treinamento
6
k-NN
• k-Nearest Neighbor
• Regras de classificação
– Sem peso
• Maioria nos votos
– Com peso
• Peso pela distância wi 
– Energia
• Perda de energia
wi 
d ( xk , t )  d ( xi, t )
d ( xk , t )  d ( x1, t )
1
d ( xi, t ) n
kNN – Algoritmo
• classifique(elemento X, int k)
– Calcule a distância de X para cada elemento da base
de treinamento
– Ordene os elementos a partir da menor distância a X
– Selecione os k mais próximos de X
– Use uma regra de classificação X
• Maioria na votação
• Peso pela distância
• Influência por perda de energia*
Funções de Distância
• Distâncias
– entre valores numéricos
• Euclidiana,
– entre valores categóricos
• Hamming, vdm
• Distâncias entre um vetor de atributos
– Cada atributo é um valor
– Distância entre cada atributo
• Atributos categóricos e numéricos (heterogêneos)
• Distâncias Heterogêneas
– HEOM, HVDM, DVDM,IVDM, NCM (e variações)
Distância entre
Vetores de Atributos Numéricos
• Distância Euclidiana
• Manhattan (city-block)
n
D( x, y)   xa  ya
E ( x, y ) 
n
 (x
a
a 1
 ya ) 2
• Chebychev
a 1
n
D( x, y)  max xa  ya
a 1
• Euclidiana Normalizada


xa  ya

En( x, y )   

a 1  max(a )  min(a ) 
n
2
• Camberra
n
D ( x, y )  
a 1
xa  ya
xa  ya
10
Distância entre
Vetores de Atributos Categóricos
• Distância de Hamming
1, se xa  ya
ha( xa, ya)  
0, se xa  ya
n
H ( x, y )   ha( xa, ya)
a 1
• VDM –Value Difference Metric
– Semelhança entre as distribuições das classes
VDM ( x, y ) 
n
 vdm ( x
a
a,
ya )
a 1
C
vdm a ( x, y )  
c 1
Na , x , c Na , y , c

Na , x
Na , y
q
C
  Pa , x , c  Pa , y , c
q
c 1
11
Distâncias Heterogenias
• Combinação de distância entre atributos
• Normalização das distância entre atributos
• HEOM
– Heterogeneous Euclidian-Overlap Metric
• HVDM
– Heterogeneous Value Difference Metric
• DVDM
– Discretized Value Difference Metric
• IVDM
– Interpolated Value Difference Metric
• NCM + variações
– Neighborhood Counting Measure
12
HEOM
• Heterogeneous Euclidian-Overlap Metric
• Atributos Numéricos
– Distância Euclidiana
• Atributos Categóricos
– Overlap – Distâncias de Hamming
HEOM( x, y ) 
n
2
heom
a
(
x
a
,
y
a
)

a 1
1, se xa  ya é desconhecido
0, se xa  ya são desconhecidos

heoma ( xa, ya )  
ha ( xa, ya ), se a é categórico
difa ( xa, ya ), se a é num érico
1, se xa  ya
ha( xa, ya)  
0, se xa  ya
difa( xa, ya) 
xa  ya
max(a)  min(a13
)
HVDM
• Heterogeneous Value Difference Metric
• Atributos Numéricos
– Distância Euclidiana
• Atributos Categóricos
– VDM
HVDM ( x, y ) 
n
2
hvdm
a
(
x
a
,
y
a
)

a 1
1, se xa  ya é desconhecido
0, se xa  ya são desconhecidos

hvdma ( xa, ya )  
vdma ( xa, ya ), se a é categórico
difa ( xa, ya ), se a é num érico
C
vdma( x, y)   Pa , x , c  Pa , y , c
q
c 1
difa( xa, ya) 
xa  ya
max(a)  min(a14
)
DVDM
• Discretized Value Difference Metric
• Atributos Numéricos ou Categóricos
– VDM
 xa, se a é categórico

discretizea ( xa )  
xa  min(a) 
 s  max(a)  min(a)   1, se a é num érico


DVDM ( x, y ) 
n
2
dvdm
a
(
x
a
,
y
a
)

a 1
C
vdma( x, y)   Pa , x , c  Pa , y , c
q
1, se xa  ya é desconhecido
c 1

dvdma ( xa, ya )  0, se xa  ya são desconhecidos
vdma (discretize( xa ), discrestize( ya )), para os outros casos

15
IVDM
• Interpolated Value Difference Metric
• Atributos Numéricos
x  m eioa , u


Pa , c ( xa )  Pa , u , c  
  Pa , u  1, c  Pa , u , c 
 m eioa , u  1  m eioa , u 
– VDM – interpolado
• Atributos Categóricos
u  discretize( xa )
– VDM
m eioa , u  min(a )  max(a )  min(a )   u  0.5
IVDM ( x, y ) 
n
2
ivdm
a
(
x
a
,
y
a
)

a 1
C
1, se xa  ya é desconhecido
q
vdma( x, y)   Pa , x , c  Pa , y , c
0, se xa  ya são desconhecidos
c 1

ivdma ( xa, ya )  vdma ( xa, ya ), se a é categórico
C
 Pa , c ( xa )  Pa , c ( ya ) 2 , se a é num érico
 c 1
16
NCM
• Neighborhood Counting Measure
• Medida de similaridade
• Mais vizinhanças  mais semelhantes
17
NCM
• Contando vizinhanças
n
NCM ' ( x, y)   viza( xa, ya)
a 1
n
NCM ( x, y )  
a 1
viza ( xa, ya )
viza ( xa )
2 ma 1 , se a é categóricoe xa  ya
 ma 2
viza( xa, ya)  2 , se a é categóricoe xa  ya
max(a)  max({xa , ya})  1  min({xa , ya})  min(a)  1, se a é num érico

2 ma 1 , se a é categórico
viza ( xa)  
max(a)  xa  1  xa ,  min(a)  1, se a é num érico
18
NCM
• Medidas de distância
NCM 1( x, y)  1  NCM ( x, y)
n
NCM 1( x, y)  1  
a 1
n
NCM 2( x, y)  1  
a 1
viza( xa, ya)
viza( xa)  viza( ya) 2
n
NCMm( x, y)  1  
a 1
n
NCM 3( x, y)  1  
a 1
viza( xa, ya)
viza( xa)
viza( xa, ya)
min(viza( xa), viza( ya))
viza( xa, ya)
viza( xa)viza( ya)
n
NCMM ( x, y)  1  
a 1
viza( xa, ya)
max(viza( xa), viza( ya))
19
Testes[1/2]
• 10-fold cross validation [3]
– 10 vezes
• Bases
– UCI Repository
• kNN
–k
– Função de distância
– Regra de classificação
• RBF
– Função de disttância
Testes
Resultados
• k-NN (média nas 14 bases)
– Três regras: sem peso[sp], com peso[cp], energia[en]
– k = 1, 6, 11, 16, 21, 31, max
22
Resultados
• VDM
– Categóricos
• NCM2
– Numéricos
Conclusão
• Comportamento das funções de distância
– Base de dados
– Algoritmo
• parâmetros
• Um classificador que utilize funções de distância
pode melhorar usando uma função de distância
diferente
• As funções de distância apresentadas podem
ser combinadas para se adaptar mais ainda à
base de dados
Referências
• Tiago Buarque, Um estudo sobre Funções de Distância Aplicadas a
Algoritmos de Aprendizagem de Máquina,Trabalho de Graduação
CIn 2007.1
• Hui Wang, “Nearest Neighbor by Neighborhood Counting”, IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol.28,
no.6, pp. 942-953, june 2006
• D. R. Wilson and T. R. Martinez, “Improved Heterogeneous
Distance Functions”, J. Artificial Intelligence Research, vol.6, pp.134,1997.
• UCI Machine Learning Repository,
http://www.ics.uci.edu/~mlearn/MLRepository.html, acesso em 2007