kdd clustering

Prévia do material em texto

ClusteringClustering
Prof. Rodrigo Leite Durães.
rodrigo_l_d@yahoo.com.br
O que é Análise de Agrupamentos?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 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 ClusteringExemplos 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?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 Requirementos para Clustering em 
Data Mining 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
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 Principais Etapas da Formação de 
AgrupamentosAgrupamentos
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
Principais Etapas da Formação de Principais Etapas da Formação de 
AgrupamentosAgrupamentos
Medida da Qualidade de um AgrupamentoMedida 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:
Dissimilaridade entre objetosDissimilaridade entre objetos
 Distancias são normalmente usadas como medida de 
dissimilaridade entre objetos
 Entre as mais populares: distancia de Minkowski 
onde i = (xi1, xi2, …, xip) e j = (xj1, xj2, …, xjp) são dois vetores p-
dimensionais, e q é um inteiro positivo
 Se q = 1, d é a distância de Manhattan
q q
pp
qq
jxixjxixjxixjid )||...|||(|),( 2211 
||...||||),(
2211 pp jxixjxixjxixjid 
Dissimilaridade entre objetosDissimilaridade entre objetos
 Se q = 2, d é a distância:
• 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.
)||...|||(|),( 22
22
2
11 pp jxixjxixjxixjid 
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óriasEstruturas classificatórias
0
1
2
3
4
5
0 1 2 3 4 5
e
e
e
e
e
1
2
3
4
5



K
lP
PK
1
)2
 se- tem,,1)1



0
1
2
3
4
5
0 1 2 3 4 5
e
e
e
e
e
1
2
3
4
5
PartiçãoCobertura 


ml PP
Km
 então
ml e ,,1,)3 
Estruturas ClassificatóriasEstruturas Classificatórias
PiramideHierarquia
 
hhhhhh
Hhh
Hee
H




ou 
:se- tem,)3
 então )2
)1
1 432 5


 de intervalo um é ,
 que tal ordem uma Existe)4
ou se- tem,)3
hHh
HhhhhHhh


0
1
2
3
4
5
0 1 2 3 4 5
e
e
e
e
e
1
2
3
4
5
Métodos de AgrupamentoMétodos de Agrupamento
Em Taxinomia Numérica distingue-se três grupos de Em Taxinomia Numérica distingue-se três grupos de 
métodosmétodos
Técnicas de OtimizaçãoTécnicas de Otimização
Objetivo: obter uma partição. Número de grupos Objetivo: obter uma partição. Número de grupos 
fornecido pelo usuáriofornecido pelo usuário
Técnicas hierárquicasTécnicas hierárquicas
Objetivo: obter uma hierarquia (ou uma pirâmide) Objetivo: obter uma hierarquia (ou uma pirâmide) 
Pode-se obter uma partição “cortando-se” a Pode-se obter uma partição “cortando-se” a 
hierarquia em um determinado nível.hierarquia em um determinado nível.
Métodos de AgrupamentoMétodos de Agrupamento
Técnicas de CoberturaTécnicas de Cobertura
Objetivo: obter grupos que eventualmente podem Objetivo: obter grupos que eventualmente podem 
partilhar indivíduos.partilhar indivíduos.
Outros Aspectos Relativos aos Métodos de Outros Aspectos Relativos aos Métodos de 
AgrupamentoAgrupamento
Métodos Aglomerativos versus Métodos DivisivosMétodos Aglomerativos versus Métodos Divisivos
Métodos Monotéticos versus Métodos PoliteticosMétodos Monotéticos versus Métodos Politeticos
Outros Aspectos Relativos aos Métodos de Outros Aspectos Relativos aos Métodos de 
AgrupamentoAgrupamento
Agrupamento Hard versus Agrupamento FuzzyAgrupamento Hard versus Agrupamento Fuzzy
Métodos Incrementais versus Métodos não Métodos Incrementais versus Métodos não 
IncrementaisIncrementais
Métodos Paramétricos versus Métodos não Métodos Paramétricos versus Métodos não 
ParamétricosParamétricos
Métodos Geométricos versus Métodos não Métodos Geométricos versus Métodos não 
GeométricosGeométricos
Principais Métodos de AgrupamentoPrincipais 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 deDensidade: 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 tenta-
se achar o melhor ajustamento entre o modelo e o 
cluster
Métodos que fornecem uma partição: Métodos que fornecem uma partição: 
Conceitos básicosConceitos 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
• k-means (MacQueen’67): Cada grupo é representado pelo seu 
centro
O Método O Método K-MeansK-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 O Método K-MeansK-Means 
 Exemplo
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
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
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 Comentários sobre o método K-MeansK-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 Variantes do K-MeansK-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
MétodosMétodos Paramétricos 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étodosMétodos Paramétricos 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 HierarquicosMé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 Step 1 Step 2 Step 3 Step 4
b
d
c
e
a a b
d e
c d e
a b c d e
Step 4 Step 3 Step 2 Step 1 Step 0
aglomerativo
(AGNES)
divisivo
(DIANA)
AGNES (Agglomerative Nesting)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
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
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
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)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
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
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 HierarquicosMé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
CHAMELEONCHAMELEON
 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 CHAMELEONContexto global de CHAMELEON
Construção de
Um grafo esparço Partição do grafo
Fusão da Partição
Grupos finaiss
Dados
Métodos baseados em DensidadeMé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
DBSCAN: Density Based Spatial DBSCAN: Density Based Spatial 
Clustering of Applications with NoiseClustering 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
Core
Border
Outlier
Eps = 1cm
MinPts = 5
DBSCAN: O algoritmoDBSCAN: 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: (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
Ordem de 
agrupamento 
dos objetos
indefinido
 ‘
DENCLUE: using density functionsDENCLUE: using density functions
 DENsity-based CLUstEring by Hinneburg & 
Keim (KDD’98)
 Principais 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
 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.
Denclue: EssenciaDenclue: Essencia
Métodos baseados em Grade Métodos baseados em Grade 
 Usa uma estrutura de dados grade de multipla 
resolução
STING: Uma abordagem Grade com STING: Uma abordagem Grade com 
Informações EstatísticasInformaçõ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
STINGSTING
• 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: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)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
WaveCluster (1998)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 n-
dimensional
• 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)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)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 etapasCLIQUE: 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 Vantagens e desvantagens de CLIQUECLIQUE
 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 ModelosClustering 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
COBWEBCOBWEB
Uma árvore de classificação
Clustering baseado em EstatísticaClustering baseado em Estatística
 Limitações do COBWEB
• 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
 CLASSIT
• Extensão de COBWEB para agrupamento incremental de 
dados contínuos
• Sofre dos mesmos problemas de COBWEB 
 AutoClass (Cheeseman and Stutz, 1996)
• Usa analise Bayesiana para estimar o número de grupos
• Popular na industria
Outros Métodos de Agrupamento Outros Métodos de Agrupamento 
baseado em Modelosbaseado 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 “vencedor-
leva-tudo” para o objeto sendo correntemente 
apresentado
Self-organizing feature maps (SOMs)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 vencedore 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 DesafiosProblemas e Desafios
 Progressos consideráveis forem realizados em 
métodos de agrupamento escalaveis
• Partição: k-means
• 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árioSumá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
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57