Formação de agrupamentos:
conceitos básicos e algoritmos
prof. Luis Otavio Alvares
INE/UFSC
Parte desta apresentação é baseada em material do livro
Introduction to Data Mining de Tan, Steinbach, Kumar
e de material do prof. José Leomar Todesco (UFSC)
Conceitos
O problema de Clustering é descrito como: recebido
um conjunto de dados (de objetos), tentar agrupálos de forma que os elementos que compõem
cada grupo sejam mais parecidos entre si do que
parecidos com os elementos dos outros grupos.
Em resumo, é colocar os iguais (ou quase iguais)
juntos num mesmo grupo e os desiguais em
grupos distintos.
Prof. Luis Otavio Alvares
2
2
O que é formação de agrupamentos (clustering)?
Dado um conjunto de objetos,
colocar os objetos em grupos
baseados na similaridade entre
eles

Como agrupar os animais
seguintes?

Inerentemente é um problema
não definido claramente

Adaptado de material de Marcílio C. P. de Souto - DIMAp/UFRN
O que é formação de agrupamentos (clustering)?
Dado um conjunto de objetos,
colocar os objetos em grupos
baseados na similaridade entre
eles

Como agrupar os animais
seguintes?

Com bico
Inerentemente é um problema
não definido claramente

Sem bico
Adaptado de material de Marcílio C. P. de Souto - DIMAp/UFRN
O que é formação de agrupamentos (clustering)?
Dado um conjunto de objetos,
colocar os objetos em grupos
baseados na similaridade entre
eles

Como agrupar os animais
seguintes?

Inerentemente é um problema
não definido claramente

Água
Terra
Adaptado de material de Marcílio C. P. de Souto - DIMAp/UFRN
O que é formação de agrupamentos (clustering)?
Dado um conjunto de objetos,
colocar os objetos em grupos
baseados na similaridade entre
eles

Como agrupar os animais
seguintes?

Ave
Inerentemente é um problema
não definido claramente

Mamífero
Adaptado de material de Marcílio C. P. de Souto - DIMAp/UFRN
O que é formação de agrupamentos (clustering)?

Dado um conjunto de objetos, colocar os objetos em
grupos baseados na similaridade entre eles
Distâncias intracluster são
minimizadas
Distâncias entre
cluster são
maximizadas
Aplicações de clustering

Entendimento
– Agrupar documentos
relacionados, agrupar
proteínas com
funcionalidades similares,
agrupar ações com as
mesmas flutuações de
preço

Discovered Clusters
1
2
3
4
Applied-Matl-DOWN,Bay-Network-Down,3-COM-DOWN,
Cabletron-Sys-DOWN,CISCO-DOWN,HP-DOWN,
DSC-Comm-DOWN,INTEL-DOWN,LSI-Logic-DOWN,
Micron-Tech-DOWN,Texas-Inst-Down,Tellabs-Inc-Down,
Natl-Semiconduct-DOWN,Oracl-DOWN,SGI-DOWN,
Sun-DOWN
Apple-Comp-DOWN,Autodesk-DOWN,DEC-DOWN,
ADV-Micro-Device-DOWN,Andrew-Corp-DOWN,
Computer-Assoc-DOWN,Circuit-City-DOWN,
Compaq-DOWN, EMC-Corp-DOWN, Gen-Inst-DOWN,
Motorola-DOWN,Microsoft-DOWN,Scientific-Atl-DOWN
Fannie-Mae-DOWN,Fed-Home-Loan-DOWN,
MBNA-Corp-DOWN,Morgan-Stanley-DOWN
Baker-Hughes-UP,Dresser-Inds-UP,Halliburton-HLD-UP,
Louisiana-Land-UP,Phillips-Petro-UP,Unocal-UP,
Schlumberger-UP
Sumarização
– Reduzir o tamanho de
grandes conjuntos de
dados
Agrupando a
precipitação na
Austrália
Industry Group
Technology1-DOWN
Technology2-DOWN
Financial-DOWN
Oil-UP
A noção de cluster pode ser ambígua
Quantos clusters?
Seis Clusters
Dois Clusters
Quatro Clusters
Dificuldades
Encontrar o melhor agrupamento para um
conjunto de objetos não é uma tarefa simples, a
não ser que n (número de objetos) e k (número
de clusters) sejam extremamente pequenos,
visto que o número de partições distintas em
que podemos dividir n objetos em k clusters é
aproximadamente
kn/k!
Ex. k=2 e n=5 então são 16 formas de dividir 5
elementos em 2 grupos.
Prof. Luis Otavio Alvares
10
10
Dificuldades
Para agrupar 25 objetos em 5 grupos,
existem 2.436.684.974.110.751 maneiras
possíveis.
E se o número de clusters é
desconhecido, precisamos somar todas
as partições possíveis para cada número
de clusters entre 2 e 5 (desconsiderando
um só cluster).
11
Dificuldades
Porque a efetividade dos algoritmos de Clustering é um
problema:
1. Quase todos os algoritmos de Clustering requerem
valores para os parâmetros de entrada que são
difíceis de determinar, especialmente para conjuntos
de dados do mundo real contendo objetos com
muitos atributos.
12
Dificuldades
2. Os algoritmos são muito sensíveis a estes valores de
parâmetros, freqüentemente produzindo partições
muito diferentes do conjunto de dados mesmo para
ajustes de parâmetros significativamente pouco
diferentes.
3. Conjuntos de dados reais de alta dimensão (muitos
atributos) têm uma distribuição muito ampla o que
dificulta a análise.
13
Medidas de Similaridade
As medidas de similaridade fornecem valores
numéricos que expressam a “distância” entre
dois objetos.
Quanto menor o valor desta “distância”, mais
semelhantes serão os objetos, e tenderão a
ficar no mesmo cluster.
Quanto maior a “distância”, menos similares
serão os objetos e, em conseqüência, eles
deverão estar em grupos distintos.
14
Medidas de Similaridade
Uma função de distância deve ser tal que:
• não assuma valores negativos (o menor valor é 0);
• ser simétrica (a distância do objeto i ao j tem que ser
igual à distância do objeto j ao i);
• forneça o valor 0 quando calculada a distância do objeto
a si mesmo ou quando dois objetos são idênticos;
• respeite a desigualdade triangular, (dados 3 objetos, a
distância entre dois deles tem que ser menor ou igual a
soma das distâncias entre esses dois objetos e o
terceiro).
Prof. Luis Otavio Alvares
15
Medidas de Similaridade
 Distância
Euclidiana
d ( x, y)  ( x1  y1 ) 2  ( x2  y2 ) 2  ...  ( x p  y p ) 2

City block (Manhattan, taxicab, L1 norm,
Hamming)
– Um exemplo comum é a distância de Hamming, que é o número de bits
que é diferente entre dois vetores binários
d ( x, y )  x1  y1  x2  y2  ...  x p  y p
Prof. Luis Otavio Alvares
16
Medidas de Similaridade
Não há uma medida de similaridade que sirva para
todos os tipos de variáveis que podem existir
numa base de dados.
Variáveis numéricas:
A medida que é normalmente usada para
computar as dissimilaridades de objetos
descritos por variáveis numéricas é a
Distancia Euclidiana
A normalização faz com que todas as variáveis tenham um peso
igual. A normalização deve ser efetuada para todos os atributos.
17
Medidas de Similaridade
Exemplos para strings:
Cores = {Branco, Amarelo, Vermelho, Marrom, Preto}
x1 = Branco
y1 = Amarelo
Opção1: medida binária de similaridade
0, se a1 = a2
d(x1,y1) =
1, se a1  a2
Prof. Luis Otavio Alvares
18
Medidas de Similaridade
Opção2: transformar o string em um valor
numérico (mais usado quando há ordem
entre os valores nominais)
Branco
Amarelo
Vermelho
Marrom
Preto
0
0,25
0,5
0,75
1
E usar a distância Euclidiana
Principais abordagens de Clustering
 Particionamento
(K-médias e variantes)
– Divide os pontos (dados) em conjuntos disjuntos (clusters) tal que cada
ponto pertence a um único cluster
 Hierárquica
– Um conjunto de clusters aninhados organizados como uma árvore
 Baseadas
em densidade
– Encontra clusters baseado na densidade de regiões
 Baseadas
em grade (Grid-based)
– Encontra clusters baseado no número de pontos em cada célula
Prof. Luis Otavio Alvares
20
K-médias (K-means)

Abordagem por particionamento

Cada cluster está associado a um centróide (ponto central)

Cada ponto é associado ao cluster cujo centróide está mais
próximo

Número de clusters, K, precisa ser especificado

O algoritmo básico é bem simples:
K-médias: exemplo do funcionamento
Prof. Luis Otavio Alvares
22
K-médias: partição
Diagrama de Voronoi – poliedros convexos em torno dos centróides
Prof. Luis Otavio Alvares
23
k-means (Exemplo)
Usar k=2 (parâmetro informado pelo usuário)
Dataset a ser clusterizado
Item
A
B
C
D
Variáveis
x1
5
-1
1
-3
Prof. Luis Otavio Alvares
x2
3
1
-2
-2
24
k-means (Exemplo)
Passo 1
Determina-se os centróides iniciais (normalmente
pega-se ao acaso k pontos (registros): por exemplo
os registros A e B),
isto é:
C1(1) = (5,3)
C2(1) = (-1,1)
Prof. Luis Otavio Alvares
25
k-means (Exemplo)
Passo 2:
Calcula-se as distâncias de cada ponto
centróides, para definir os cluster iniciais.
aos
Os clusters são:
C1 = {A}
C2 = {B,C,D}
Pois C e D estão mais
perto de B do que de A
Prof. Luis Otavio Alvares
26
k-means (Exemplo)
Passo 3: cálculo dos novos centróides
C1(2)= (5,3)
C2(2)=
Prof. Luis Otavio Alvares
27
k-means (Exemplo)
Passo 4: novo cálculo dos clusters
Os clusters são:
C1 = {A}
C2 = {B,C,D}
Pois:
• A está mais perto de C12 do
que de C22
• B, C e D estão mais perto de
C22 do que de C12
Como os elementos dos clusters não se alteraram, os
centróides vão ser os mesmos e com isso o algoritmo para.
Prof. Luis Otavio Alvares
28
Outros exemplos com o k-médias
Prof. Luis Otavio Alvares
29
Dois conjuntos de clusters diferentes
gerados pelo K-médias
3
2.5
Pontos originais
2
y
1.5
1
0.5
0
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
x
2.5
2.5
2
2
1.5
1.5
y
3
y
3
1
1
0.5
0.5
0
0
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
x
Particionamento ótimo
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
x
Particionamento sub-ótimo
Importância de escolher os centróides iniciais
Iteration 6
1
2
3
4
5
3
2.5
2
y
1.5
1
0.5
0
-2
-1.5
-1
-0.5
0
x
0.5
1
1.5
2
Importância de escolher os centróides iniciais
Iteration 1
Iteration 2
Iteration 3
2.5
2.5
2.5
2
2
2
1.5
1.5
1.5
y
3
y
3
y
3
1
1
1
0.5
0.5
0.5
0
0
0
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
-2
-1.5
-1
-0.5
x
0
0.5
1
1.5
2
-2
Iteration 4
Iteration 5
2.5
2
2
2
1.5
1.5
1.5
1
1
1
0.5
0.5
0.5
0
0
0
-0.5
0
x
0.5
1
1.5
2
0
0.5
1
1.5
2
1
1.5
2
y
2.5
y
2.5
y
3
-1
-0.5
Iteration 6
3
-1.5
-1
x
3
-2
-1.5
x
-2
-1.5
-1
-0.5
0
x
0.5
1
1.5
2
-2
-1.5
-1
-0.5
0
x
0.5
Avaliando os clusters gerados
A medida mais comum é a soma dos erros quadrados
(Sum of Squared Error - SSE)
 Para cada ponto, o erro é a distância ao centróide mais próximo
K
SSE    dist2 (mi , x)
i 1 xCi
 x é um ponto de dados no cluster Ci e mi é o ponto
representativo (centróide) do cluster Ci
 Uma maneira fácil de reduzir o SSE é aumentar K, o número de
clusters
Um bom particionamento com um K pequeno pode ter um SSE
menor do que um mau particionamento com um K maior

Importância da escolha dos centróides iniciais
Iteration 5
1
2
3
4
3
2.5
2
y
1.5
1
0.5
0
-2
-1.5
-1
-0.5
0
x
0.5
1
1.5
2
Importância da escolha dos centróides iniciais
Iteration 1
Iteration 2
2.5
2.5
2
2
1.5
1.5
y
3
y
3
1
1
0.5
0.5
0
0
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
-2
-1.5
-1
-0.5
x
0
0.5
Iteration 3
2.5
2
2
2
1.5
1.5
1.5
y
2.5
y
2.5
y
3
1
1
1
0.5
0.5
0.5
0
0
0
-1
-0.5
0
x
0.5
2
Iteration 5
3
-1.5
1.5
Iteration 4
3
-2
1
x
1
1.5
2
-2
-1.5
-1
-0.5
0
x
0.5
1
1.5
2
-2
-1.5
-1
-0.5
0
x
0.5
1
1.5
2
Exemplo com 10 clusters
Iteration 4
1
2
3
8
6
4
y
2
0
-2
-4
-6
0
5
10
15
20
x
Iniciando com dois centróides em um cluster para cada par de clusters
Exemplo com 10 clusters
Iteration 2
8
6
6
4
4
2
2
y
y
Iteration 1
8
0
0
-2
-2
-4
-4
-6
-6
0
5
10
15
20
0
5
x
6
6
4
4
2
2
0
-2
-4
-4
-6
-6
x
15
20
0
-2
10
20
Iteration 4
8
y
y
Iteration 3
5
15
x
8
0
10
15
20
0
5
10
x
Iniciando com dois centróides em um cluster para cada par de clusters
Exemplo com 10 clusters
Iteration 4
1
2
3
8
6
4
y
2
0
-2
-4
-6
0
5
10
15
20
x
Iniciando com um par de clusters tendo 3 centróides iniciais e outro par com somente um.
Exemplo com 10 clusters
Iteration 2
8
6
6
4
4
2
2
y
y
Iteration 1
8
0
0
-2
-2
-4
-4
-6
-6
0
5
10
15
20
0
5
8
8
6
6
4
4
2
2
0
-2
-4
-4
-6
-6
5
10
x
15
20
15
20
0
-2
0
10
x
Iteration
4
y
y
x
Iteration
3
15
20
0
5
10
x
Iniciando com um par de clusters tendo 3 centróides iniciais e outro par com somente um.
Pré e Pós-processamento
 Pré-processamento
– Normalize os dados
– Elimine exceções (outliers)
 Pós-processamento
– Elimine clusters pequenos que podem representar
outliers
– Divida clusters “fracos” i.e., clusters com SSE
relativamente alto
– Junte clusters que estão “perto” e que tenham SSE
relativamente baixo
Limitações do K-médias
 K-médias
tem problemas quando os clusters têm
– Tamanhos diferentes
– Densidades diferentes
– Formato não esférico
 K-médias
tem problemas quando os dados
contêm outliers.
Limitações do K-médias: tamanhos diferentes
Pontos originais
K-médias (3 Clusters)
Limitações do K-médias: densidades diferentes
pontos originais
K-médias (3 Clusters)
Limitações do K-médias: formatos não esféricos
Pontos originais
K-médias (2 Clusters)
Superando as limitações do K-médias
Pontos originais
Clusters do K-médias
Uma solução é usar muitos clusters.
Encontra partes de clusters, mas que precisam ser unidos.
Superando as limitações do K-médias
Pontos originais
clusters do K-médias
Superando as limitações do K-médias
Pontos originais
clusters do K-médias
O algoritmo K-médias é sensível a ruídos visto
que um objeto com um valor extremamente
grande pode, distorcer a distribuição de dados.
Para diminuir essa sensibilidade, no algoritmo
K- medoids, ao invés de utilizar o valor médio dos
objetos em um cluster como um ponto referência,
a mediana é utilizada, que é o objeto mais
centralmente localizado em um cluster.
Métodos de K-medoids (K-medianas)
Em vez de médias (centróides), usa objetos
representativos chamados medoids
PAM (Partitioning Around Medoids, 1987) – inicia com um
conjunto de medoids e iterativamente substitui um dos
medoids por um dos pontos não-medoids se ele melhora
a distância total do particionamento resultante
 CLARA (Clustering Large Applications, 1990) – It draws
multiple samples of the data set, applies PAM on each
sample, and gives the best clustering as the output
 CLARANS (“Randomized “CLARA, 1994) – mais eficiente
e escalável que CLARA e PAM

Prof. Luis Otavio Alvares
49
Exercício
+
+
Prof. Luis Otavio Alvares
50