k-NN eFunções de Dissimilaridade

Tiago Buarque

<tbac@cin.ufpe.br>

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

}{,

:),(

atributosdevetoresdosconjuntoVyx

VVyxd

6

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

k-NN

• k-Nearest Neighbor• Regras de classificação

– Sem peso• Maioria nos votos

– Com peso• Peso pela distância

– Energia• Perda de energia

),(),(

),(),(

1 txdtxd

txdtxdw

k

iki

ni

itxd

w),(

1

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)

10

Distância entreVetores de Atributos Numéricos• Distância Euclidiana

• Euclidiana Normalizada

• Manhattan (city-block)

• Chebychev

• Camberra

n

a

aa yxyxE1

2)(),(

2

1 )min()max(),(

n

a

aa

aa

yxyxEn

n

a

aa yxyxD1

),(

aa

n

ayxyxD

1max),(

n

a aa

aa

yx

yxyxD

1

),(

11

Distância entreVetores de Atributos Categóricos• Distância de Hamming

• VDM –Value Difference Metric– Semelhança entre as distribuições das classes

n

a

aaa yxhyxH1

),(),(

aa

aaaaa

yxse

yxseyxh

,0

,1),(

n

a

aaa yxvdmyxVDM1

, )(),(

C

c

qcyacxa

qC

c ya

cya

xa

cxaa PP

N

N

N

Nyxvdm

1

,,,,

1 ,

,,

,

,,),(

12

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

13

HEOM

• Heterogeneous Euclidian-Overlap Metric• Atributos Numéricos

– Distância Euclidiana

• Atributos Categóricos– Overlap – Distâncias de Hamming

n

a

aaa yxheomyxHEOM1

2),(),(

numéricoéaseyxdif

categóricoéaseyxh

dosdesconhecisãoyxse

dodesconheciéyxse

yxheom

aaa

aaa

aa

aa

aaa

),,(

),,(

,0

,1

),(

aa

aaaaa

yxse

yxseyxh

,0

,1),(

)min()max(),(

aa

yxyxdif

aaaaa

14

HVDM

• Heterogeneous Value Difference Metric • Atributos Numéricos

– Distância Euclidiana

• Atributos Categóricos– VDM

)min()max(),(

aa

yxyxdif

aaaaa

n

a

aaa yxhvdmyxHVDM1

2),(),(

numéricoéaseyxdif

categóricoéaseyxvdm

dosdesconhecisãoyxse

dodesconheciéyxse

yxhvdm

aaa

aaa

aa

aa

aaa

),,(

),,(

,0

,1

),(

C

c

qcyacxaa PPyxvdm

1

,,,,),(

15

DVDM

• Discretized Value Difference Metric• Atributos Numéricos ou Categóricos

– VDM

C

c

qcyacxaa PPyxvdm

1

,,,,),(

n

a

aaa yxdvdmyxDVDM1

2),(),(

casosoutrososparayediscrestizxdiscretizevdm

dosdesconhecisãoyxse

dodesconheciéyxse

yxdvdm

aaa

aa

aa

aaa

)),(),((

,0

,1

),(

numéricoéaseaa

axs

categóricoéasexa

xdiscretize aaa,1

)min()max(

)min(

,

)(

16

IVDM

• Interpolated Value Difference Metric• Atributos Numéricos

– VDM – interpolado

• Atributos Categóricos– VDM

C

c

qcyacxaa PPyxvdm

1

,,,,),(

n

a

aaa yxivdmyxIVDM1

2),(),(

C

c

acaaca

aaa

aa

aa

aaa

numéricoéaseyPxP

categóricoéaseyxvdm

dosdesconhecisãoyxse

dodesconheciéyxse

yxivdm

1

2,, ,)()(

),,(

,0

,1

),(

5.0)min()max()min(

)(

)(

,

,,,1,,1,

,,,,

uaaameio

xdiscretizeu

PPmeiomeio

meioxPxP

ua

a

cuacuauaua

uacuaaca

17

NCM

• Neighborhood Counting Measure• Medida de similaridade• Mais vizinhanças mais semelhantes

18

NCM

• Contando vizinhanças

numéricoéaseayxyxa

yxecategóricoéase

yxecategóricoéase

yxviz

aaaa

aam

aam

aaaa

a

,1)min(})min({1})max({)max(

,2

,2

),(

,,

2

1

),(),('1

aaa

n

a

yxvizyxNCM

)(

),(),(

1 aa

aaan

a xviz

yxvizyxNCM

numéricoéaseaxxa

categóricoéasexviz

aa

m

aa

a

,1)min(1)max(

,2)(

,

1

19

NCM

• Medidas de distância),(1),(1 yxNCMyxNCM

)(

),(1),(1

1 aa

aaan

a xviz

yxvizyxNCM

2)()(

),(1),(2

1 aaaa

aaan

a yvizxviz

yxvizyxNCM

)()(

),(1),(3

1 aaaa

aaan

a yvizxviz

yxvizyxNCM

))(),(min(

),(1),(

1 aaaa

aaan

a yvizxviz

yxvizyxNCMm

))(),(max(

),(1),(

1 aaaa

aaan

a yvizxviz

yxvizyxNCMM

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

22

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

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.1-34,1997.

• UCI Machine Learning Repository, http://www.ics.uci.edu/~mlearn/MLRepository.html, acesso em 2007