Clustering
Prof. Francisco de A. T. de Carvalho
[email protected]
O que é Análise de Agrupamentos?

Cluster: um grupo de objetos
• Similares entre si quando no mesmo grupo
• Dissimilares em relação a objetos em outros grupos

Análise de Agrupamentos
• Agrupamento de objetos em grupos
Agrupamento é um método de classificação não
supervisionada: as classes não são definidas
previamente
 Aplicações típicas

• Como uma ferramenta autonoma para obter pistas sobre a
distribuição de dados
• Como uma etapa de preprocessamento para outros algoritmos
Aplicações de Clustering
Reconhecimento de Padrões
 Análise de Dados Espacial

• detecte clusters espaciais e explique-os no contexto da
mineração de dados espaciais
Processamento de Imagens
 Economia (especialmente pesquisa de mercado)
 WWW

• Classificação de documentos
• Agrupamento de dados provenientes do Weblog para descobrir
grupos de acesso similares
Exemplos de Aplicações de Clustering




Marketing: Ajuda os marqueteiros a descobrir grupos
de clientes e usa esse conhecimento para orientar as
campanhas publicitárias
Solo: Identificação de áreas de propriedades similares
Seguro: Identificação de grupos de segurados com um
custo médio elevado de reembolso
Planejamento Urbano: Identificação de grupos de
habitação segundo o tipo, valor e localização geográfica
O que é um bom agrupamento?

Um bom método de agrupamento fornece grupos de
alta qualidade com
• Alta similaridade intra-grupo
• baixa similaridade inter-grupo


A qualidade do resultado de um agrupamento depende
tanto da medida de similaridade usada pelo método
como da sua implementação.
A qualidade de um método de agrupamento é também
medido pela sua habilidade para descobrir os padrões
escondidos.
Requirementos para Clustering em
Data Mining




Scalabilidade
Abilidade para tratar com diferentes tipos de
atributos
Descoberta de grupos de forma arbitrária
Requerimentos mínimos do conhecimento do dominio
em relação aos parâmetros de entrada

Capaz de tratar ruidos e valores aberrantes

Insensível à ordem dos registros de entrada

Alta dimensionalidade

Incorporação de restrições fornecidas pelo usuário

Interpretabilidade e usabilidade
Principais Etapas da Formação de
Agrupamentos
a) aquisição dos dados
1) Seleção das observações (indivíduos,
objetos, casos, itens)
2) Seleção das variáveis (caracteres,
descritores) e das correspondentes escalas
3) Construção da Tabela de Dados
b) Pré-processamento dos dados
1) Mudança de escala
2) Normalização
3) Extração de caracteres
Principais Etapas da Formação de
Agrupamentos
c) Construção da Tabela de Dados
d) Cálculo da Proximidade
1) Escolha de um Índice de Proximidade
2) Construção da Matriz de Proximidades
e) Seleção de um Algoritmo de Formação de
Grupos em função do tipo de agrupamento
desejado
f) Análise e Interpretação dos Resultados
A Representação dos Dados


Matrix de Dados
Matrix de
Dissimilaridade
 x11

 ...
x
 i1
 ...
x
 n1
... x1f
... ...
... xif
...
...
... xnf
 0
 d(2,1)
0

 d(3,1) d ( 3,2)

:
 :
d ( n,1) d ( n,2)
... x1p 

... ... 
... xip 

... ... 
... xnp 





0

:

... ... 0
Medida da Qualidade de um Agrupamento
Proximidade: é uma função que mede a similaridade ou a
dissimilaridade entre um par de observações
 Uma função a parte mede a qualidade de um grupo.
 As funções de proximidade dependem da escala das
variáveis: proporcional, intervalar, ordinal, nominal,
binária, mista
 Pode-se associar pesos as variáveis como
conheciemento do domínio.
 É extremamente difícil definir o que são dois objetos
“bastante similares”

•
a resposta é quase sempre subjetiva.
Tipos de Dados

Variáveis de escala intervalar:

Variáveis Binárias:

Variáveis Nominais, Ordinais, Proporcionais:

Variáveis de tipo mixto:
Variáveis de escala intervalar

Padronização

Calcule o desvio médio absoluto:
sf  1
n (| x1 f  m f |  | x2 f  m f | ... | xnf  m f |)
onde

mf  1
n (x1 f  x2 f
 ... 
xnf )
.
Calculale a medida padronizada (z-escore)
xif  m f
zif 
sf

O desvio médio absoluto é mais robusto do que o desvio
padrão
Dissimilaridade entre objetos


Distancias são normalmente usadas como medida de
dissimilaridade entre objetos
Entre as mais populares: distancia de Minkowski
d (i, j)  q (| x  x |q  | x  x |q ... | x  x |q )
i1
j1
i2
j2
ip
jp
onde i = (xi1, xi2, …, xip) e j = (xj1, xj2, …, xjp) são dois vetores pdimensionais, e q é um inteiro positivo

Se q = 1, d é a distância de Manhattan
d (i, j) | x  x |  | x  x | ... | x  x |
i1 j1 i2 j2
ip jp
Dissimilaridade entre objetos

Se q = 2, d é a distância:
d (i, j)  (| x  x |2  | x  x |2 ... | x  x |2 )
i1 j1
i2
j2
ip
jp
• Properties



d(i,j)  0, d(i,i) = 0, d(i,j) = d(j,i)
d(i,j)  d(i,k) + d(k,j)
Outras alternativas: distância ponderada, correlação
(similaridade), etc.
Variávais binárias

Tabela de contingencia para dados binários
Objeto j
Objeto i
1
0
1
0
soma
a
c
b
d
ab
cd
soma a  c b  d
p
Simple matching (invariante, se a variável binaria é
bc
simetrica):
d (i, j) 
a bc  d
 Jaccard (não invariante se a variável binaria é

asimetrica)
d (i, j) 
bc
a bc
Variáveis Nominais


Variável de escala nominal que pode assumir mais de 2
categorias, e.x., vermelho, amarelo, azul, verde
Metodo 1: Concordancias simples
• m: # das concordancias, p: numero de variáveis
m
d (i, j)  p 
p

Metodo 2: usa um grande numero de variáveis binárias
• Criação de uma nova variável binária para cada uma das M
categorias
Variáveis ordinais

Uma variável ordinal pode ser qualitativa ou quantitativa

A ordem é importante, e.x., rank

Pode ser tratada como uma variável de escala intervalar
rif {1,...,M f }
• Trocando xif pelo seu rank
• Mapear a amplitude de cada variável em [0, 1] trocando rif por
zif
rif 1

M f 1
• Calcular a dissimilaridade usando os métodos das variáveis de
escala intervalar
Variáveis de escala proporcional


variável de escala proporcional: medida em uma escala
não linear, aproximadamente exponencial, tal como AeBt
ou Ae-Bt
Metodos:
• Trata-las como variáveis de escala intervalar — não é uma boa
escolha! (porque?)
• Aplicar uma tansfirmação logaritmica
yif = log(xif)
• Trata-las como os dados ordinais quantitativos tratam os seus
ranks como escala intervalar.
Variaveis de vários tipos

Uma base de dados pode conter todos os 6 tipos:
• simetrica binaria, assimetrica binária, nominal, ordinal,
intervalar e proporcional.

Pode-se usar uma expressão ponderada para combinalas.
 pf  1 ij( f ) dij( f )
d (i, j) 
• f é binária ou nominal:
 pf  1 ij( f )
dij(f) = 0 se xif = xjf , ou dij(f) = 1 senão
• f é intervalar: use a distancia normalizada
• f é ordinal ou de escala proporcional
 Calcule ranks rif e
 E trate zif como intervalar
zif

r
M
1
if
f
1
Outros aspectos relativos aos índices de
proximidade
•Escala das Variáveis
•Correlação entre as Variáveis
•Descrições heterogêneas (Variáveis de diferentes
tipos)
•Índices de proximidade entre padrões descritos por
strings ou árvores
•Índices de proximidade dependentes do contexto
•Índices de proximidade conceptual
Estruturas classificatórias
Cobertura
Partição
5
5
e5
4
e4
3
e5
4
e3
e4
3
e2
2
e1
1
e3
e2
2
e1
1
0
0
1
2
3
4
5
0
0
1)  1,, K tem - se P  
K
2) Pl  
 1
1
2
3
4
5
3), m  1,, K e l  m
então Pl  Pm  
Estruturas Classificatórias
Hierarquia
Piramide
5
e5
4
e4
3
e3
e2
2
e1
1
0
0
1
2
3
4
1)  H
2)e   entãoe H
3)h, h  H tem- se :
h  h    h  h ou h  h
5
3)h, h  H tem- se h  h   ou h  h  H
4)Existeuma ordem talque
h  H , h é um intervalode 
Métodos de Agrupamento
Em Taxinomia Numérica distingue-se três grupos de
métodos
Técnicas de Otimização
Objetivo: obter uma partição. Número de grupos
fornecido pelo usuário
Técnicas hierárquicas
Objetivo: obter uma hierarquia (ou uma pirâmide)
Pode-se obter uma partição “cortando-se” a
hierarquia em um determinado nível.
Métodos de Agrupamento
Técnicas de Cobertura
Objetivo: obter grupos que eventualmente podem
partilhar indivíduos.
Outros Aspectos Relativos aos Métodos de
Agrupamento
Métodos Aglomerativos versus Métodos Divisivos
Métodos Monotéticos versus Métodos Politeticos
Outros Aspectos Relativos aos Métodos de
Agrupamento
Agrupamento Hard versus Agrupamento Fuzzy
Métodos Incrementais versus Métodos não
Incrementais
Métodos Paramétricos versus Métodos não
Paramétricos
Métodos Geométricos versus Métodos não
Geométricos
Principais Métodos de Agrupamento

Métodos que fornecem uma partição: Construa várias
partições que são então avaliadas segundo algum critério

Métodos Hierarquicos: Fornece uma decomposição
hierarquica dos objetos segundo um critério particular

Métodos de Densidade: basedos em conectividade e
funções de densidade

Grid: baseado em estruturas de níveis de granularidade
multipla

Modelo: Supõe-se um modelo para cada cluster e tentase achar o melhor ajustamento entre o modelo e o
cluster
Métodos que fornecem uma partição:
Conceitos básicos


Métodos que fornecem uma partição: Produz uma
partição de uma base de dados D de n objetos em k
grupos
Dado k, encontre uma partição em k grupos que otimiza
um dado critério
• Otimo global: enumeração exaustiva de todas as partições
• Heuristicas: k-means e k-medoids
• k-means (MacQueen’67): Cada grupo é representado pelo seu
centro
• k-medoids ou PAM (Partition around medoids) (Kaufman &
Rousseeuw’87): Cada grupo é representado por um objeto no
grupo
O Método K-Means
 Dado
k, o algoritmo k-means é implementado
em 4 passos:
• Partição dos objetos em k grupos não vazios
• Defina as sementes como os centroides dos
grupos da partição atual.
• Afete cada objeto ao grupo cuja semente é a
mais próxima ao mesmo.
• Volte para o passo 2, pare quando não houver
novas afetações.
O Método K-Means

Exemplo
10
10
9
9
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
0
0
0
1
2
3
4
5
6
7
8
9
10
0
10
10
9
9
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
0
1
2
3
4
5
6
7
8
9
10
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
Comentários sobre o método K-Means

Pontos fortes
• Relativamente eficiente: O(tkn), onde n é # objetos, k é #
grupos, e t é # iterações. Normalmente, k, t << n.
• Frequentemente termina em um otimo local. O otimo global pode
ser encontrado usando tecnicas tais como: deterministic
annealing e algoritmos geneticos

Pontos fracos
• Aplicavel apenas quando a média é definida, o que fazer com
dados categóricos?
• É necessário especificar a priori k, o número de grupos
• É sensível a ruidos e valores aberrantes
• Não é apropriado para a descoberta de grupos não esféricos
Variantes do K-Means

Algumas variantes do k-means diferem em
• Seleção das k medias iniciais
• Calculo das dissimilaridades
• Estratégias para calcular as médias dos grupos

Dados categóricos: k-modas (Huang’98)
• Troca das medias pelas modas dos grupos
• Uso de novas medidas de dissimilaridade para tratar dados
categóricos
• Uso de um método baseado na frequencia para atualizar as
modas
• Mistura de dados categóricos e numéricos: método k-prototype
O MétodoK-Medoids


Encontre objetos representativos, chamados medoids,
nos grupos
PAM (Partitioning Around Medoids, 1987)
• Inicie com um conjunto inicial de medoids e iterativamente
troque um deles por um não medoide se a distancia total do
agrupamento melhora
• PAM funciona para conjuntos de dados pequenos, mas não
possui escalabilidade suficiente para os grandes
CLARA (Kaufmann & Rousseeuw, 1990)
 CLARANS (Ng & Han, 1994): Amostragem aleatória

PAM (Partitioning Around Medoids) (1987)

PAM (Kaufman et al, 1987), implementado em Splus

Usa objetos reais para representar os grupos
• Selecione k objetos representativos arbitrariamente
• Para cada par de objetos não selecionados h e selecionados i,
calcule o custo total de troca TCih
• Para cada par i e h,


Se TCih < 0, i é trocado por h
Afete cada objeto não selecionado ao objeto
representativo mais similar
• Repita os passos 2-3 até que não haja mais mudança
CLARA (Clustering Large Applications) (1990)

CLARA (Kaufmann and Rousseeuw in 1990)
• Implementado em pacotes estatísticos, tais como S+


Seleciona multiplas amostras dos dados, aplica PAM em
cada amostra, e fornece o melhor agrupamento
Força: se aplica a conjuntos de dados maiores do que
PAM

Fraquezas:
• A eficiencia depende do tamanho da amostra
• Um bom agrupamento com base em amostras não representa
necessariamente um bom agrupamento do conjunto de dados se
a amostra é viesada
CLARANS (“Randomized” CLARA) (1994)




CLARANS seleciona amostras de vizinhos
dinamicamente
O processo de agrupamento pode ser apresentado como
uma busca em um grafo onde cada nó é uma solução
potencial, isto é, um conjunto de k medoids
Se o ótimo local é encontrado, CLARANS recomeça com
novos nós selecionados dinamicamente na busca por um
novo ótimo local
É mais eficiente e escalavel do que PAM e CLARA
Métodos Paramétricos
Modelo: Mistura finita de distribuições
Mistura: conjunto de k distribuições de probabilidade
que representam k grupos e que determinam os valores
dos atributos para os membros de um grupo
Cada distribuição fornece a probabilidade de que uma
instancia particular apresente um certo conjunto de
valores caso se saiba que ela pertence a um dado grupo
A cada grupo é associado uma distribuição distinta
Métodos Paramétricos
Uma instancia pertence a apenas um grupo, mas não se
sabe qual
Os grupos não são igualmente prováveis
Situação mais simples: um atributo numérico com
distribuição normal para cada grupo, mas com
diferentes médias e variâncias
Problema: a partir de um conjunto de instancias inferir
a media e a variância de cada grupo (distribuição)
Métodos Paramétricos
Exemplo: Dois grupos A e B de distribuição normal com
médias e desvios-padrão A e A para A e B e B para B
Seleciona-se instancias dessas distribuições (de A com
probabilidade pA e de B com probabilidade pB)
Dados: (A,51), (A,43), (B,62), (B,64), (A,45), (A,42),
(A,46), (A,45), (A,45), (B,62), (B,47), (A,52), (B,64),
(A,51), (B,65), (A,48), (A,49), (A,46), (B,64), (B,51)
Problema: Imagine os dados sem as classes (rótulos) e
suponha que se queira determinar os parâmetros
A, A, B, B, pA e pB
Métodos Paramétricos
Conhecendo-se as classes das instancias esses
parâmetros seriam facilmente estimados:
x1    xn
x
n
2
2
(
x

x
)



(
x

x
)
n
s2  1
n 1
pA e pB são estimados pela proporção das instancias em
cada grupo A e B
Conhecendo-se esses parâmetros, dada uma instancia x,
a probabilidade de que ela seja do grupo A é
P( x | A) P( A)
f ( x;  A , A ) p A
P( A | x) 

P( x)
f ( x;  A , A ) p A  f ( x;  B , B ) pB
Métodos Paramétricos
Abordagem probabilista
Os dados D são uma mistura de k distribuições
normais uni-variadas de mesma variância 2
Cada observação é descrita pelo vetor (xi, zi1, …, zik),
onde
a) xi é o valor da i-ésima observação;
b) zij = 1 se a observação é proveniente do j-ésimo
grupo e zij = 0, senão
Diz-se também que xi é a variável observada e zi1, …,
zik são as variáveis ocultas
Métodos Paramétricos
Abordagem probabilista
Trata-se de estimar (aprender) as médias de cada
uma das k distribuições normais:
Encontrar a hipótese h = < 1,…, k > que maximiza a
verossimilhança dessa médias, isto é, encontrar
a hipótese h = < 1… k > que maximiza p(D/h)
Métodos Paramétricos
O Algoritmo EM (Expectation, Maximisation)
Inicialização: h = < 1,…, k >, onde 1,…, k são valores
iniciais arbitrários
Etapa 1: Calcular o valor esperado E[zij] de cada
variável oculta zij, supondo verdadeira a hipótese
atual h = < 1,…, k >
Métodos Paramétricos
O Algoritmo EM (Expectation, Maximisation)
E[zij] é a probabilidade de que a observação xi tenha
sido gerada pela j-ésima distribuição normal
 ( xi   j ) 
exp 

2
p( x  xi |    j )



E[ zij ]  k
 k
( xi   n ) 

p( x  xi |    n )  exp 


2



n 1
n 1
O Algoritmo EM (Expectation, Maximisation)
Etapa 2: Calcular a nova hipótese h’ = < ’1,…, ’k > de
máxima verossimilhança, supondo que os valores de
cada variável oculta zij é o seu valor esperado E[zij]
calculado no Passo 1.
Substituir a hipótese h = < 1,…, k > pela hipótese h’ =
< ’1,…, ’k > e recomeçar.
O Algoritmo EM (Expectation, Maximisation)
Nesse caso, a hipótese de máxima verossimilhança é
dada por:
m
j 
 E[ z
i 1
m
ij
 E[ z
i 1
] xi
ij
]
Esse algoritmo converge para uma hipótese h que
representa um máximo de verossimilhança local
Métodos Hierarquicos

Usa uma matriz de distancias como critério de agrupamento.
Esse métodos não requerem o número de grupos k como entrada,
mas precisa de uma condição de parada
Step 0
a
Step 1
Step 2 Step 3 Step 4
ab
b
abcde
c
cde
d
de
e
Step 4
aglomerativo
(AGNES)
Step 3
Step 2 Step 1 Step 0
divisivo
(DIANA)
AGNES (Agglomerative Nesting)

Introduzido por Kaufmann and Rousseeuw (1990)

Implementado em pacotes estatísticos, e.x., Splus

Usa o método Single-Link e a matriz de dissimilaridade.

Fusiona nós que tem as menores dissimilaridades

Eventualmente todos os nós pertencem ao mesmo grupo
10
10
10
9
9
9
8
8
8
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
1
2
3
4
5
6
7
8
9
10
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
Um Dendrograma mostra como os grupos
são fusionados hierarquicamente
Decompõe os objetos em vários níveis de partições
embutidas (árvore de grupos, chamado de dendrograma).
Um agrupamento dos objetos é obtido pelo corte do
dendrograma em um nível desejado e então cada
componente conectado forma um grupo.
DIANA (Divisive Analysis)

Introduzido por Kaufmann and Rousseeuw (1990)

Implementado em pacotes estatísticos, ex., Splus

Ordem inversa de AGNES

Eventualmente cada nó forma um grupo unitário
10
10
10
9
9
9
8
8
8
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
Métodos Hierarquicos

Pontos fracos dos métodos aglomerativos de
agrupamento
• Não são escalaveis: complexidade em tempo pelo menos em
O(n2), onde n é o número total de objetos
• Nunca pode desfazer o que já fez previamente

Integração de agrupamentos hierárquicos com
agrupamentos baseado em distancias
• BIRCH (1996): usa árvore CF e ajusta incrementalmente a
qualidade dos subgrupos
• CURE (1998): seleciona pontos bem espalhados do grupo e então
encolhe-os para o centro dos grupos segundo uma fração
especificada
• CHAMELEON (1999): agrupamento hierárquico usando
modelagem dinamica
BIRCH (1996)


Birch: Balanced Iterative Reducing and Clustering using
Hierarchies, by Zhang, Ramakrishnan, Livny
(SIGMOD’96)
Constroi incrementalmente uma árvore CF (Clustering
Feature)
• Fase 1: scanear a DB para contruir uma árvore CF inicial em
memoria
• Fase 2: usa um algoritmo arbitrário de agrupamento para
fusionar os nos da árvore CF

Escalabilidade linear: encontra bons grupos com um

Fraqueza: trata apenas de dados numéricos, é sensível a
simples escaneamento e melhora a qualidade dos mesmos
com alguns escaneamentos adicionais
ordem em que os dados são registrados.
Vetor Clustering Feature
Clustering Feature: CF = (N, LS, SS)
N: Numero de objetos
LS: Ni=1=Xi
SS: Ni=1=Xi2
CF = (5, (16,30),(54,190))
10
9
8
7
6
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9
10
(3,4)
(2,6)
(4,5)
(4,7)
(3,8)
Árvore CF
Raíz
B=7
CF1
CF2 CF3
CF6
L=6
child1
child2 child3
child6
nó
CF1
CF2 CF3
CF5
child1
child2 child3
child5
folha
prev CF1 CF2
CF6 next
folha
prev CF1 CF2
CF4 next
CURE (Clustering Using
REpresentatives )

CURE: proposto por Guha, Rastogi & Shim, 1998
• Para a criação de uma hierarquia de grupos se um nível
consiste de k grupos
• Usa multiplos pontos representativos para avaliar a distancia
entre grupos, se ajusta bem a grupos de forma arbitrária e
evita os efeitos la ligação simples (single-link)

Inconvenientes dos métodos de agrupamento
baseados em distancia
• Considera apenas um ponto como o representante de um
grupo
• Bom apenas para formas convexas, tamanho e densidade
similar, e se k pode ser estimado razoávelmente
Cure: Algoritmo
• Tiragem de uma amostra aleatória s.
• Particionar a amostra em p partições de tamanho
s/p
• Agrupar parcialmente as partições em s/pq grupos
• Eliminar valores aberrantes

Por amostragem aleatória

Se um grupo cresce muito lentamente, elimina-
lo.
• Agrupar grupos parciais.
• Rotular os dados no disco
CHAMELEON
CHAMELEON: G. Karypis, E.H. Han and V. Kumar’99
 Mede a similaridade baseda em um modelo dinamico

• 2 grupos são fusionados apenas se a interconectividade e
proximity entre 2 grupos são altas em relação a
interconectividade interna dos grupos e a proximidade dos
itens nos grupos

Um algoritmo de 2 fases
• 1. Usa um algoritmo de particionamento de um grafo: agrupa
objetos em um grande número de sub-grupos relativamente
pequenos
• 2. Usa um algoritmo hierarquico aglomerativo: encontra os
verdadeiros grupos pela fusão desses sub-grupos
Contexto global de CHAMELEON
Construção de
Partição do grafo
Um grafo esparço
Dados
Fusão da Partição
Grupos finaiss
Métodos baseados em Densidade
Agrupamento baseado em densidade (critério de cluster
local, tal como a densidade de pontos conectados
 Caracteristicas princiapais:

• Descoberta de grupos de forma arbitrária
• Tratamento de ruido
• Apenas uma escaneada
• É necessário parametros de densidade como condição
de parada

Várias abordagens:
•
•
•
•
DBSCAN: Ester, et al. (KDD’96)
OPTICS: Ankerst, et al (SIGMOD’99).
DENCLUE: Hinneburg & D. Keim (KDD’98)
CLIQUE: Agrawal, et al. (SIGMOD’98)
Preliminares

2 parametros:
• Eps: Raio máximo da vizinhança
• MinPts: Número de pontos minimo em um Eps desse ponto

NEps(p):
{q pertence a D | dist(p,q) <= Eps}

Um ponto p é diretamente alcançavel pela densidade de
um ponto q Eps, MinPts se
• 1) p pertence a NEps(q)
• 2) condição de ponto núcleo:
|NEps (q)| >= MinPts
p
q
MinPts = 5
Eps = 1 cm
Preliminares (II)

Alcançavel pela densidade:
• Um ponto p é alcançavel pela densidade
de um ponto q Eps, MinPts se existe
uma cadeia de pontos p1, …, pn, p1 = q, pn
= p tal que pi+1 é diretamente alcançavel
pela densidade de pi

p
p1
q
Conectado pela Densidade
• Um ponto p é conectado pela densidade
a um ponto q Eps, MinPts se existe um
ponto o tal que ambos, p and q são
alcançaveis pela densidade de o wrt.
Eps e MinPts.
p
q
o
DBSCAN: Density Based Spatial
Clustering of Applications with Noise
Um grupo é definido como um conjunto de pontos
máximo conectados pela densidade
 Descobre grupos de forma arbitrária em BD espaciais
com ruido

Outlier
Border
Eps = 1cm
Core
MinPts = 5
DBSCAN: O algoritmo
• Selecione um pointo p arbitrariamente
• Recupere todos os pontos alcançaveis pela
densidade de p wrt Eps and MinPts.
• Se p é um ponto core, forma-se um grupo.
• Se p é um ponto de fronteira, não há pontoas
aclcançaveis pela densidade de p e DBSCAN visita o
proxímo ponto da base de dados.
• Continue o processo até que todos os pontos
tenham sido processados.
OPTICS: (1999)
 OPTICS:
Ordering Points To Identify the
Clustering Structure
• Ankerst, Breunig, Kriegel, and Sander
(SIGMOD’99)
• Produz uma ordenação especial da base de dados em
relação a sua estrutura de agrupamento baseada em
densidade
• Esse ordenamento de grupo contém informação
equivalente a agrupamento baseado em densidade
correspondente a uma ampla faixa de ajuste de
parametros
• Bom tanto para agrupamento automático como
iterativo, incluindo a procura da estrutura de
agrupamento intrinsica
• Pode ser representado graficamente ou usar
tecnicas de visualização
Distancia
alcançavel
indefinido

‘

Ordem de
agrupamento
dos objetos
DENCLUE: using density functions
 DENsity-based
Keim (KDD’98)
 Principais
CLUstEring by Hinneburg &
Caracteristicas
• Fundamentos matematicos solidos
• Bom para dados com presença maciça de ruido
• Permite uma descrição matemática compacta de
grupos de forma arbitrária para dados
multidemensionais
• Significativamente mais rápido do que os algoritmos
existentes (mais rápido do que DBSCAN por um fator
de até 45)
• No entanto precisa de uma enorme quantidade de
parametros
Denclue: Essencia





Usa celulas em grade mas guarda informações apenas
sobre aquelas que realmente contém pontos e manipula
essa celulas em uma estrutura de acesso tipo árvore.
Função de influencia: descreve o impacto dos dados na
sua vizinhança.
A densidade global do espaço de dados pode ser
calculada como a soma da função de influencia de todos
os pontos.
Os grupos podem ser determinados matematicamente
pela identificação de atratores de densidade.
Atratores de densidade são máximos locais da função
densidade global.
Gradiente:

Exemplo
f Gaussian ( x , y )  e
f
D
Gaussian
f

d ( x , y )2
22
( x )   i 1 e
N

d ( x , xi ) 2
2 2
( x, xi )  i 1 ( xi  x)  e
D
Gaussian
N

d ( x , xi ) 2
2 2
Métodos baseados em Grade


Usa uma estrutura de dados grade de multipla
resolução
Vários métodos interessantes
• STING (a STatistical INformation Grid approach) by
Wang, Yang and Muntz (1997)
• WaveCluster by Sheikholeslami, Chatterjee, and Zhang
(VLDB’98)

Uma abordagem de agrupamento multi resolução
usando um método wavelet
• CLIQUE: Agrawal, et al. (SIGMOD’98)
STING: Uma abordagem Grade com
Informações Estatísticas
Wang, Yang and Muntz (VLDB’97)
 A área espacial é dividida em células retangulares
 Há vários níveis de celulas correspondente a vários
níveis de resolução

STING
• Cada célula em um nível mais alto é particionada em um
número menor de celulas no próximo nível abaixo
• Calcula-se e armazena-se de antemão informações
estatísticas de cada célula e usa-se a mesma para
responder consultas
• Parametros de células de nível mais altos são facilmente
calculadas à partir de parametros de células de nivel mais
baixo
 count, mean, s, min, max
 tipo de distribuição—normal, uniforme, etc.
• Usa uma abordagem top-down para responder consultas
espaciais
• Inicia a partir de uma camada pre-selecionada—
tipicamente com um pequeno número de celulas
• Para cada célula do nível corrente calcule o intervalo de
confiança
STING:
• Remoção de células irrelevantes para consideração
adicional
• Quando acabar o exame da camada corrente, passe
para a próxima camada de nível mais baixo
• Repita esse processo até alcançar a camada inferior
• Vantagens:
 Independente de consultas, facil de paralelizar,
atualização incremental
 O(K), onde K é o número de células na grade ao
nível mais baixo
• Desvantagens:
 Todas as fronteiras dos grupos ou são
horizontais ou verticais; fronteiras diagonais não
são detectadas
WaveCluster (1998)


Sheikholeslami, Chatterjee, and Zhang (VLDB’98)
Uma abordagem de agrupamento multi resolução que aplica
transformada de wavelet no espaço de características
•


Uma transformada de wavelet é uma tecnica de processamento de
sinais que decompõe o sinal em diferentes sub-bandas de
frequencia.
É ao mesmo tempo um método baseado em grade e em
densidade
Parametros de entrada:
• # das celulas da grade para cada dimensão
• a wavelet, e o # de aplicações de transformada wavelet.
WaveCluster (1998)
 Como
aplicar transformada de wavelet para
encontrar grupos
• Simplifique os dados pela imposição de uma
estrutura de grade multidimensional no espaço dos
dados
• Esse objetos espaciais multidimensionais são
representados em um espaço de caracteristicas ndimensional
• Aplicar a transformada de wavelet no espaço de
caracteristicas para encontrar regiões densas
nesse espaço
• Aplicar transformada de wavelet várias vezes que
resulta em grupos de diferentes escalas da mais
fina a mais grosseira
WaveCluster (1998)

Porque a transformada wavelet é útil para agrupamento
• Agrupamento não supervisionado
Usa filtros para enfatizar regiões cujos pontos agrupam, e
simulteneamente suprime informações mais fracas na fronteira
• Remoção eficaz de valores aberrantes
• Multi-resolução
• Eficiencia do custo

Principais caracteristicas:
•
•
•
•
Complexidade O(N)
Detecção de grupos de forma arbitrária em diferentes escalas
Insensível ao ruido ou a ordem dos dados de entrada
Aplicavel apenas a dados de poucas dimensões
CLIQUE (Clustering In QUEst)

Agrawal, Gehrke, Gunopulos, Raghavan (SIGMOD’98).

Identifica automaticamente regiões que permitem um
melhor agrupamento do que o espaço original

CLIQUE é ao mesmo tempo baseada em densidade e em
grade
• Particiona cada dimensão no mesmo número de intervalos de igual
tamanho
• Particiona o espaço m-dimensional em retangulos sem intersecção
• Uma unidade é densa se a fração dos pontos contida nessa
unidade excede os parametros do modelo
• Um grupo é um conjunto máximo de unidades densas concectadas
em um subespaço
CLIQUE: Principais etapas



Particione o espaço de dados e encontre o número de pontos
que se encontram dentro de cada celula da partição.
Identifique os subespaços que contém grupos usando o
principio do Apriori
Identificaçãod e grupos:
• Determine unidades densas em todos os subespaços de interesse
• Determine unidades densas conectadas em todos os subespaços de
interesse.

Gere a descrição mínima dos grupos
• Determine regiões máximas que cobrem um grupo de unidades densas
conectadas para cada grupo
• Determinação da cobertura mínima de cada grupo
Vantagens e desvantagens de CLIQUE

Pontos fortes
• Encontra automaticamente regiões de máxima
dimensionalidade tal que existe clusters de alta densidade
neles
• É insensível a ordem de apresentação dos objetos e não é
necessário supor nenhuma distribuição a priori para os dados
• Escalabilidade linear com o numero de objetos e boa
escalabilidade quando o numero de dimensãoes dos dados
cresce

Pontos fracos
• A precisão dos resultados do agrupamento pode ser
degradada em função da simplicidade requerida pelo método
Clustering baseado em Modelos
Procura otimizar o ajustamento entre os dados e um
modelo matemático particular
 Abordagens Estística e de AI

• Agrupamento Conceptual



Uma forma de agrupamento em aprendizagem de máquina
Fornece uma classificação para um conjunto de objetos não
rotulados
Encontra a descrição característica de cada conceito (classe)
• COBWEB (Fisher’87)



Um método de agrupamento conceptual incremental
Cria um agrupamento hierarquico expresso por uma árvore de
classificação
Cada nó representa um conceito e contém uma descrição
probabilistica do mesmo
COBWEB
Uma árvore de classificação
Clustering baseado em Estatística

Limitações do COBWEB

CLASSIT

AutoClass (Cheeseman and Stutz, 1996)
• A suposição de que os atributos são independentes é muito
forte: podem existir correlações
• Não é apropriado para o agrupamento de grandes bases de
dados
• Extensão de COBWEB para agrupamento incremental de
dados contínuos
• Sofre dos mesmos problemas de COBWEB
• Usa analise Bayesiana para estimar o número de grupos
• Popular na industria
Outros Métodos de Agrupamento
baseado em Modelos
 Abordagens
redes Neurais
• Representa cada grupo como um exemplo, que age
como um “prototipo” do grupo
• Novos objetos são distribuidos para o grupo cujo
exemplar é o mais similar segundo uma dada
distancia
 Aprendizagem
Competitiva
• Involve uma arquitetura hierárquica de várias
unidades (neuronios)
• Os neuronios competem em um modo “vencedorleva-tudo” para o objeto sendo correntemente
apresentado
Self-organizing feature maps (SOMs)
O
Agrupamento é realizado pela competição
de várias unidades pelo objeto corrente
 A unidade cujo vetor de pesos é a mais
próxima do objeto corrente vence
 O vencedor e seus vizinhos aprendem pelo
ajustamento de seus pesos
 Bem adaptado para a visualização de dados
multi-dimensionais em 2 ou 3 dimensões
Problemas e Desafios

Progressos consideráveis forem realizados em
métodos de agrupamento escalaveis
• Partição: k-means, k-medoids, CLARANS
• Hierarquia: BIRCH, CURE
• Densidade: DBSCAN, CLIQUE, OPTICS
• Grid: STING, WaveCluster
• Modelo: Autoclass, Denclue, Cobweb


Os métodos atuais de agrupamento não satisfazem
todos os requerimentos desejáveis adequadamente
Agrupamento sob restrições: Restrições estão
presentes no espaço de dados ou nas consultas dos
usuários
Sumário
Cluster analysis agrupa objetos com base nas suas
similaridades e tem uma ampla faixa de aplicações
 Medidas de similaridade podem ser calculadas para
varios tipos de dados
 Os Métodos de agrupamento podem ser divididos em
métodos de partição, hierarquicos, baseados em
densidade, baseados em grade e baseados em modelos
 Ainda há muitos progressos a serem realizados em
análise de agrupamentos tais como em agrupamento
baseado em restrições
