Kohonen para dados simbólicos

Anderson Bergabsd@cin.ufpe.br

12 de novembro de 2010Anderson Berg Kohonen para dados simbólicos 1 / 21

Introdução

Motivação

Diagramas para visualização de dados

Procurar por estruturas, clusters, tendências, dependências ouanomalias

Anderson Berg Kohonen para dados simbólicos 2 / 21

Introdução

Redes SOM

Anderson Berg Kohonen para dados simbólicos 3 / 21

Introdução

Vizinhança

Anderson Berg Kohonen para dados simbólicos 4 / 21

Kohonen para dados simbólicos intervalares

Kohonen para visualização de dados simbólicos

• Vértices P1, . . . ,Pm de uma grade retangular L com ’b’ linhas e ’a’colunas• Cada vértice Pi representa Ci e zi

Anderson Berg Kohonen para dados simbólicos 5 / 21

Kohonen para dados simbólicos intervalares

SYKSOM

• Abordagem clássica de Kohonen: pontos xk = (xk1, . . . , xkp)

• SYKSOM: generalização para dados simbólicos do tipo intervalo

n vetores de intervalos x1, . . . , xn:

xk =

[ak1,bk1]...[

akp,bkp]

Anderson Berg Kohonen para dados simbólicos 6 / 21

Kohonen para dados simbólicos intervalares

SYKSOM

k \ j Var.1 Var.2 Var. 31 [8.4, 10.0] [13.0, 15.2] [5.0, 8.2]2 [6.3, 9.1] [14.1, 16.0] [6.3, 7.2]3 [7.9, 11.8] [11.6, 13.5] [4.9, 6.5]4 [9.0, 11.0] [10.9, 12.5] [7.1, 8.1]

Por exemplo:

x4 =

[9.0,11.0][10.9,12.5]

[7.1,8.1]

Anderson Berg Kohonen para dados simbólicos 7 / 21

Kohonen para dados simbólicos intervalares

SYKSOM

xk descreve o item k e é um hiper-cubo

Qk = [ak ,bk ] ⊂ <p

Onde:

ak =

ak1...

akp

e bk =

bk1...

bkp

Anderson Berg Kohonen para dados simbólicos 8 / 21

Kohonen para dados simbólicos intervalares

Abordagem simbólica de Kohonen (etapas)

1 Hiper-cubos agrupados em m "mini-clusters"C1, . . . ,Cm(m = b · a)

2 Cada mini-cluster Ci é caracterizado por um hiper-cubo protótipozi

3 Cada mini-cluster e cada protótipo é atribuído a um vértice Pvi

4 Dois protótipos quaisquer zi , zj que são vizinhos são atribuídos adois vértices Pvi e Pvj também vizinhos na grade.

Produzindo: uma partição final (C1, . . . ,Cm) de objetos e descrevecada mini-cluster Ci por um hiper-cubo zi , chamado de protótipo.

Anderson Berg Kohonen para dados simbólicos 9 / 21

Kohonen para dados simbólicos intervalares

Etapas básicas do SYKSOM

• Série de etapas t = 0,1,2, . . .• Inclusos os primeiros t hiper-cubos

• Resultado preliminar: C(t)1 , . . . ,C(t)

m e z(t)1 , . . . , z(t)

m

• A etapa t+1 inclui o (t + 1)-ésimo retângulo xt+1 e sãoatualizados os clusters e protótipos anteriores

Anderson Berg Kohonen para dados simbólicos 10 / 21

Kohonen para dados simbólicos intervalares

Inicialização

1 Em t = 0: conjunto inicial de m = b · a classes vaziasC(0)

1 = ∅, . . .C(0)m = ∅ e m protótipos z(0)

1 , . . . , z(0)m

2 A classe C(0)i é atribuída ao vértice Pi da grade.

Anderson Berg Kohonen para dados simbólicos 11 / 21

Kohonen para dados simbólicos intervalares

Etapa de iteração

Ao final da etapa t foram processados t hiper-cubosx1 = [a1,b1], . . . , xt = [at ,bt ] e obtidos:

• C(t) = (C(t)1 , . . . ,C(t)

m )

• Z(t) = (z(t)1 , . . . , z(t)

m ), z(t)i = [u(t)

i , v (t)i ]

Anderson Berg Kohonen para dados simbólicos 12 / 21

Kohonen para dados simbólicos intervalares

Distância mínima

d(xt+1, z(t)i∗ ) = minj=1,...,md(xt+1, z

(t)j )

C(t+1)i∗ := C(t)

i∗ ∪ t + 1

C(t+1)i := C(t)

i , para todo i , com i 6= i∗

Anderson Berg Kohonen para dados simbólicos 13 / 21

Kohonen para dados simbólicos intervalares

Atualização dos protótipos

• Todos os m protótipos z(t)1 , . . . , z(t)

j são atualizados.

• Cada protótipo z(t)j = [u(t)

j , v (t)j ] é deslocado em direção a xt+1

• O tamanho do deslocamento depende da distância δ(Pj ,Pi∗)

• Ordenação topológica

Anderson Berg Kohonen para dados simbólicos 14 / 21

Kohonen para dados simbólicos intervalares

Deslocamento dos retângulos

u(t+1)j = u(t)

j + αt+1 · Ki∗j · (at+1 − u(t)j ))

v (t+1)j = v (t)

j + αt+1 · Ki∗j · (bt+1 − v (t)j ))

• (α1, α2, . . . )⇒ sequência decrescente de fatores deaprendizado αt > 0• Ki∗j := K (δ(Pi∗ ,Pj)) = Kji∗

• K (δ) é uma "ponderação"crescente ou função "kernel"

Anderson Berg Kohonen para dados simbólicos 15 / 21

Kohonen para dados simbólicos intervalares

Ciclos iterativos e parada

• O primeiro ciclo (l = 1) resulta C(n) = (C(n)1 , . . .C(n)

m ) eZ(n) = (z(n)

1 , . . . z(n)m )

• O algoritmo segue na série de ciclos (l = 2,3, . . . )• Os protótipos do l-ésimo ciclo são usados para inicializar o

(l + 1)-ésimo ciclo• Os ciclos terminam após c ciclos pre-determinados, ou se os

protótipos atingirem um estado estacionário

Anderson Berg Kohonen para dados simbólicos 16 / 21

Kohonen para dados simbólicos intervalares

Regra de parada

O algoritmo é parado depois de t = l · n atualizações, onde l ≥ c ou:

∆l :=

∑mi=1 ‖ z(l·n)

i − z(l−1)·ni ‖2∑m

i=1 ‖ z(l·n)i ‖2

< δ

Senão um novo ciclo (l + 1) é realizado.

Anderson Berg Kohonen para dados simbólicos 17 / 21

Kohonen para dados simbólicos intervalares

Visualizando a saída do SYKSOM através do Kohonen

O SODAS disponibiliza três módulos:• VMAP⇒ exibe a grade L com ícones, zoom stars e diagramas

descrevendo as propriedades das classes em mapas (ordenadostopologicamente)• VIEW⇒ exibe os protótipos das classes, por exemplo, com

zoom stars• VPLOT⇒ exibe a projeção dos protótipos em um espaço

Euclidiano bidimensional composto por duas variáveis que podemser selecionadas pelo usuário.

Anderson Berg Kohonen para dados simbólicos 18 / 21

Kohonen para dados simbólicos intervalares

VMAP

p∏j=1

(vij − uij)

1/p

Anderson Berg Kohonen para dados simbólicos 19 / 21

Kohonen para dados simbólicos intervalares

VIEW

Anderson Berg Kohonen para dados simbólicos 20 / 21

Kohonen para dados simbólicos intervalares

VPLOT

Anderson Berg Kohonen para dados simbólicos 21 / 21