CLUSTERING: UMA REVISÃO
AOS ALGORITMOS BÁSICOS
HECTOR ENRIQUE DE LA HOZ LEÓN
ORDEM DA APRESENTAÇÃO
• Introdução
• Motivação
• Componentes de algoritmos de
clustering
• Definições.
• Algoritmos de clustering
• Aplicação.
INTRODUÇÃO
• Clustering: É o processo de classificação
não supervisionada de padrões em grupos
chamados de clusters.
dados
Aprendizado
supervisionado
Classificação
dados
Aprendizado
NÃO
supervisionado
DADOS NÃO
CLASSIFICADOS
DADOS
CLUSTERIZADOS
MOTIVAÇÃO
• Grandes quantidades de dados são
geradas
e
armazenadas
diariamente.
• A pressão da competência é forte.
• Os Computadores são poderosos e
baratos.
COMPONENTES DOS SISTEMAS DE
CLUSTERING
Dado
Representação
de padrões
Extração de
características
Medida de
Similaridade
Loop de
Feedback
Clusters
Agrupamento
CARACTERÍSTICAS
S E L E Ç ÃO
• Ao processo de
Identificar o
conjunto mais
representativo de
características.
As características podem
ser:
• Qualitativas .
• Quantitativas.
E X T R AÇ ÃO
• Utilizar uma ou mais
transformações no
conjunto de
características para
gerar novas
propriedades ainda
mais representativas.
REPRESENTAÇÃO DOS CLUSTERS
• Pelo centroide do cluster.
• Por pontos distantes do
cluster.
• Utilizando nós em arvores de
classificação.
• Utilizando expressões logicas
conjuntivas.
FUNÇÃO DE SIMILARIDADE
• Os clusters
estão formados
por dados com
características
semelhantes.
•
•
•
•
Euclidiana.
Minkowski (p>2)
Mahalonobis
Manhattan
• São as
relações que
medem a
distância entre
um par de
padrões no
espaço de
características
𝒅
(𝒙𝒊,𝒌 − 𝒙𝒋,𝒌 )𝟐
𝑫 𝒙𝒊 , 𝒙𝒋 =
𝒌=𝟏
AGRUPAMENTO
CLASSIFICAÇÃO DOS ALGORITMOS
DE CLUSTERING
Clustering
Hierárquico
Divisional
Erro
quadrático
Link
completo
Link
simples
k-means
Busca
Teoria de
grafos
CSP
Max. da
esperança
ABORDAGENS PARA
CLUSTERIZAÇÃO (PARTE I)
• Aglomeração.
• Inicia tantos cluster quantos dados.
• Separação.
• Inicia um clusters só.
• Monothetic.
• Todas as características são utilizadas
simultaneamente.
• Polithetic.
• As características são utilizadas sequencialmente.
ABORDAGENS PARA
CLUSTERIZAÇÃO (PARTE II)
• Duro
• Cada dado pertence a um e só um cluster.
• Fuzzi
• Cada dado é classificado com uma variável de
pertinência a cada cluster
EXEMPLOS DAS ABORDAGENS
Aglomerativo
Monothetic
Fuzzi
DEFINIÇÕES FUNDAMENTAIS
(PARTE I)
• Padrão: Itens de dados utilizados pelos algoritmos de
clustering. Representados por um vetor de
características.
𝒙 = 𝑥1 , 𝑥2 , … , 𝑥𝑛
• Características: Cada uma das componentes dos
padrões (Atributos).
• Conjunto de dados: O conjunto de padrões
analisados pelo algoritmo.
𝐗 = 𝒙1 , 𝒙2 , … , 𝒙𝑑
DEFINIÇÕES FUNDAMENTAIS
(PARTE II)
• Classe:
• Estado da natureza que governa a geração de
padrões.
• uma fonte de padrões cuja distribuição no espaço
de característica esta governada por uma
determinada função de densidade de
probabilidade.
• Rotulo:
• É o valor assignado pelo algoritmo de clustering
aos dados que pertencem à mesma classe.
CLUSTERING HIERARQUICOS
(LINK SIMPLES)
•
Iniciar o algoritmo colocando cada padrão do conjunto de
dados em um cluster diferente.
•
Construir a lista das distâncias 𝑑𝑘 entre os padrões e
organiza-la em forma ascendente.
•
Percorrer a lista de distâncias ordenadas, e aglomerar os
padrões com distancias menores do que um determinado D.
•
Repetir até obter o numero de clusters desejados:
• Calcular a distância entre todos os pares de padrões de
classes diferentes.
• Aglomerar as classes cuja mínima distância seja menor do
que D.
• Atualizar as distâncias e atualizar D caso necessário.
CLUSTERING HIERARQUICOS
LINK SIMPLES
LINK COMPLETO
CLUSTERING TEORIA DE GRAFOS
• Calcular o
minimal spanning
tree (MST).
• Formar os
cluster
eliminando as
ramas de maior
valor.
CLUSTERING INCREMENTAL
• Iniciar o algoritmo associando um padrão ao primer
cluster
• Analisar o seguinte padrão do conjunto de dados e
classifica-lo em algum dos clusters existentes ou em um
novo cluster baseando-se em algum critério de
similaridade.
• Repetir o passo anterior até todos os padrões estarem
classificados.
CLUSTERING INCREMENTAL
K-MEANS
• Escolher k pontos, dentro do espaço de
características, representando os centros
dos k clusters em que é desejado dividir o
conjunto de dados.
• Assignar cada padrão ao centro mais próximo
de acordo com a função de similaridade.
• Recalcular os centros dos clusters
utilizando os dados membros de cada
cluster.
• Repetir o algoritmo desde o item dois até
atingir um critério de parada.
CARACTERÍSTICAS DO K-MEANS
• O seu tempo de convergência é proporcional ao
numero de padrões n, ao numero de clusters k e
ao numero de iterações l.
• O espaço de memoria requerido é proporcional
ao numero de dados e ao numero de clusters.
• Para um dado conjunto inicial de centros, o
algoritmo gera a mesma partição de dados sem
importar a ordem em que os dados são
apresentados.
• sensibilidade com respeito à seleção dos k
primeiros centros.
SELEÇÃO DOS K CENTROS.
• Selecionar os extremos e/ou o centro do espaço
de características como centroides iniciais dos
clusters.
• Dividir o espaço de características e selecionar
randomicamente em cada seção algum ponto como
centroide de um cluster. Isto garante que os
centroides estejam espalhados por todo o espaço
de caraterísticas.
• Selecionar os centros dos clusters perto do
centro de massa do conjunto de dados. Cada
centro é obtido adicionando um valor randômico
ao centro de massa dos dados.
COMPARAÇÃO ENTRE TÉCNICAS
Complexidade
Algoritmo de
clustering
Tempo
Espaço
Líder
K-Means
ISODATA
O(kn)
O(knl)
O(knl)
O(k)
O(k)
O(k)
Shortest
Spanning
Path (SPP)
O(𝑛2 )
O(n)
Link Simples
O(𝑛2 log 𝑛)
O(𝑛2 )
Link
Completo
O(𝑛2 log 𝑛)
O(𝑛2 )
APLICAÇÃO EM
BINARIZAÇÃO DE
IMAGENS DIGITAIS
APLICAÇÃO EM BINARIZAÇÃO DE
IMAGENS DIGITAIS (OTSU)
• Efetuar o cálculo
do histograma da
intesidade dos
pixeis.
• Calcular o limiar
que maximize a
variância
ponderada entre
as classes
𝝈𝟐 = 𝝎𝟏 𝝉 𝝈𝟐 𝟏 𝝉 + 𝝎𝟐 (𝝉) 𝝈𝟐 𝟐 (𝝉)
APLICAÇÃO EM BINARIZAÇÃO DE
IMAGENS DIGITAIS (OTSU)
APLICAÇÃO EM BINARIZAÇÃO DE
IMAGENS DIGITAIS (OTSU)
APLICAÇÃO EM BINARIZAÇÃO DE
IMAGENS DIGITAIS (K-MEANS)
•
Efetuar o cálculo do histograma de cores.
• Seleção das cinco cores de maior frequência
como possível centroide do cluster.
• Escolhe-se como semente aquela que possui
maior quantidade de pixeis a uma distância de
Manhattan menor do que um limiar τ (utilizouse nesta aplicação um limiar τ=20).
APLICAÇÃO EM BINARIZAÇÃO DE
IMAGENS DIGITAIS (K-MEANS)
𝑑𝑖 𝑝, 𝑞 = 𝑝 − 𝑞𝑖
APLICAÇÃO EM BINARIZAÇÃO DE
IMAGENS DIGITAIS (K-MEANS)
OBRIGADO