Baixe o app para aproveitar ainda mais
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
Compartilhar