Aprendizado não-supervisionado

Algoritmos de Agrupamento

Hierárquico, K-Means e ISODATA

Julio Cesar Duarte

Algoritmos de agrupamento

Partição em grupos

Inter-similaridade alta

Intra-similaridade baixa

Exemplo

Dendograma

Tipos de agrupamento Estrutura

Hierárquico Agrupamentos são sub-classes de outros

Não-hierárquico ou flat Sem relação entre agrupamentos

Propriedade Estrito

Objeto x Agrupamento (1xN) Livre

Probabilidade de pertencer (Incerteza, multiplicidade)

Tipos de agrupamento

Hierárquico <--> Estrito Não-hierárquico <--> Estrito ou Livre

Características Hierárquico

Análise detalhada Mais informação Vários algoritmos ótimos Menos eficiente

Não-hierárquico Mais eficiente Métodos simples Resultados suficientes

Agrupamento hierárquico

Estratégias: Bottom-up:

Objetos se agrupando Algoritmo Aglomerativo

Top-Down: Grande agrupamento sendo dividido Algoritmo Divisivo

Notação X – Conjunto de objetos n – Tamanho de X C – Conjunto de agrupamentos sim – Função de similaridade

sim(x,y) = 1/(1+d(x,y)) Monotônica

Sim (c, c1 U c2) ≤ min(Sim (c, c1), Sim (c, c2)) coh – Função de coerência

Coh(c) ?x1,x2εcsim(x1,x2)

Algoritmo Aglomerativo

C = Xwhile len(C)>1:

[c1, c2] = argmaxc1,c2εC Sim(c1, c2)

cj = [c1, c2]C.remove(c1)C.remove(c2)C.append(cj)

Algoritmo Divisivo

C = [X]while з i C[i]>1:

cj = argmin cjεC coh(cj)

[cj1, cj2] = dividir(cj)C.remove(cj)C.append(cj1)C.append(cj2)

Funções de similaridade

Ligação simples: Similaridade dos dois membros mais

similares Ligação completa

Similaridade dos dois membros menos similares

Média grupal Média das similaridades dos membros

Simples x Completa

Simples Completa

Simples x Completa Simples:

Coerência local Agrupamentos alongados ou efeito da corrente Relação com AGm

Remove maior aresta recursivamente Explica formação das ilhas do Hawaii O(n2)

Completa: Coerência global Agrupamentos justos Relação com clique Melhor intuitivamente

Grupos em torno de um centróide O(n2logn)

Média grupal

Compromisso entre ligação simples e completa

O(n3) O(n2) sim(x,y) = cos(x,y)

Agrupamento top-down Similaridade <--> coerência

Simples: menor similaridade na agm do agrupamento

Completa: menor similaridade entre dois membros

Média grupal: similaridade média no agrupamento

Divisão: Função do agrupamento Algoritmo bottom-up

Agrupamento não-hierárquico

Agrupamento inicial aleatório

Iterativamente troca de elementos

Critério de parada: Medida de verossimilhança Número de agrupamentos

K-Means

Não-hierárquico

Estrito

Agrupamentos <--> centros de massas

Algoritmo K-Means

Centros de massas aleatórios iniciais Iteração:

Elemento ε agrupamento (centro de massa mais próximo)

Recálculo dos centros de massa Iteração enquanto não CP:

ex: sem alterações

Algoritmo K-Means

Função de distância: Euclidiana

Mais sensível a outliers Norma L1

L1(X, Y) = ∑k |xk-yk|

Complexidade: Se número de iterações constante O(n)

Exemplo

Algoritmo K-Means

Quebra de empates: Aleatória não-convergência Perturbação de elementos

K-Means Livre

1a Estratégia: minimizar o erro quadrático Σimincd(i-µc)2

Δµc=Σi η.d(i-µc), i mais próximo de µc

0 , c.c. µc = µc + Δµc

K-Means Livre 2a Estratégia: Contribuição de todos

)(

)()(/1

)(/1

2

2

)(

)(

2

2

ci

y

yd

id

c

ciy c

cc

ide

e

ou

idyd

id

c

c

ISODATA

IIterative Self-Organizing Data Analysis Technique Algorithm Extensão do K-Means: seleção automática

de k (qtde de agrupamentos) Parâmetros:

NMIN_EX:no mínimo de elementos por agrupamento Nd: número aproximado de agrupamentos σs

2: parâmetro máximo de abertura para divisão DM:distância máxima de separação para união NM: número máximo de agrupamentos a serem unidos

ISODATA

Algoritmo:Algoritmo:1. K-Means2. Dividir agrupamentos segundo critério

de dissimilaridade3. Unir dois agrupamentos próximos4. Repetir

ISODATA

ISODATA Vantagens::

Auto-organização Eliminação de agrupamentos pequenos Divisão de agrupamentos dissimilares União de agrupamentos similares

Desvantagens: Dados linearmente separáveis Parâmetros iniciais

Impacto na performance Performance Baixa x Muitos Dados Garantia de convergência

Agrupamentos não sobrepostos

Referências Manning Schuetze

Foundations Of Statistical Natural Language Processing

Soumen Chakrabarti Mining The Web Discovering Knowledge From

Hypertext Data Ricardo Gutierrez-Osuna

Introduction to Pattern Recognition Irina Rish, Daniel Oblinger

Lectures in Statistical Pattern Recognition