Upload
internet
View
108
Download
1
Embed Size (px)
Citation preview
CLUSTERING: UMA REVISÃO AOS ALGORITMOS
BÁSICOS
H E C T O R E N R I Q U E D E L A H O Z L E Ó 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.
Aprendizado supervisiona
do
dados
Classificação
Aprendizado NÃO
supervisionado
dados
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
Clusters
Representação de padrõesDado
Extração de características
Medida de Similaridade
Agrupamento
Loop de Feedback
CARACTERÍSTICAS
SELEÇÃO
• Ao processo de Identificar o conjunto mais representativo de características.
EXTRAÇÃO
• Utilizar uma ou mais transformações no conjunto de características para gerar novas propriedades ainda mais representativas.
As características podem ser:• Qualitativas .• Quantitativas.
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.
• Os clusters estão formados por dados com características semelhantes.
• São as relações que medem a distância entre um par de padrões no espaço de características
FUNÇÃO DE SIMILARIDADE
𝑫 (𝒙 𝒊 , 𝒙 𝒋 )=∑𝒌=𝟏
𝒅
√(𝒙 𝒊 ,𝒌−𝒙 𝒋 ,𝒌)𝟐
• Euclidiana.• Minkowski (p>2)• Mahalonobis• Manhattan
AGRUPAMENTO
CLASSIFICAÇÃO DOS ALGORITMOS DE CLUSTERING
Clustering
Hierárquico Divisional
Link completo
Busca
Link simples
Erro quadrático CSP
Max. da esperança
k-means
Teoria de grafos
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.
• Duro• Cada dado pertence a um e só um cluster.
• Fuzzi• Cada dado é classificado com uma variável de
pertinência a cada cluster
ABORDAGENS PARA CLUSTERIZAÇÃO (PARTE II)
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.
• Características: Cada uma das componentes dos padrões (Atributos).
• Conjunto de dados: O conjunto de padrões analisados pelo algoritmo.
• 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.
DEFINIÇÕES FUNDAMENTAIS (PARTE II)
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
L I N K S I M P L E S L I N K C O M P L E T O
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.
• 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.
CARACTERÍSTICAS DO K-MEANS
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
Algoritmo de
clustering
Complexidade
Tempo Espaço
Líder O(kn) O(k)K-Means O(knl) O(k)ISODATA O(knl) O(k)Shortest Spanning
Path (SPP)
O() O(n)
Link Simples O() O()
Link Completo O() O()
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)
• 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 τ (utilizou-se 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)
APLICAÇÃO EM BINARIZAÇÃO DE IMAGENS DIGITAIS (K-MEANS)
OBRIGADO