Agrupamento de Dados: uma Revisão
Data Clustering
Márcia de Oliveira Alves
José de Castro Neto
Maio 2006
Universidade Federal de Campina Grande
Mestrado em Informatica
Nivelamento
• O que é Agrupamento de Dados?
• Qual a utilidade?
Roteiro
• Contextualização;
• Processo de Agrupamento;
• Agrupamento de Dados;
• Uma Aplicacão: Mineração de Dados;
• Considerações Finais.
• Bibliografia
Contextualização
Motivação
• É crescente a migração dos dados para a
mídia digital;
• Na informação reside o conhecimento;
• O volume de informação é cada vez maior;
Análise Automática dos Dados
Contextualização
Análise Automática de Dados
• Previsão de Dados
– Fluxo de Caixa Previsto
• Classificação de Dados
– Relatório gerado segundo consulta
• Análise de Agrupamentos
– Data Mining – Mineração de Dados
Processo de Agrupamento
Objetivo
Figura 1: Gráfico ilustrativo de dados agrupados em quatro grupos
Processo de Agrupamento
Etapas
• Seleção e tratamento dos dados;
• Agrupamento de dados;
• Análise dos resultados;
Processo de Agrupamento
Seleção e Tratamento de Dados
• Eliminação de dados duplicados ou corrompidos;
• Tratamento de outliers;
• Valores faltantes ou inválidos;
• Transformação dos dados;
– Tratamento de Atributos:
• Adequar os diferentes tipos de atributos para o processo de
agrupamento.
– Normalização:
• Tratar dados com atributos de diferentes dimensões, quando
se pretende que eles tenham a mesma influência no
processo.
Processo de Agrupamento
Agrupamento de Dados
• Métodos:
– Hierárquicos;
– Segmentação;
• Medidas de proximidade
– Dissimilaridade
– Similaridade
Processo de Agrupamento
Agrupamento de Dados
• Métricas comuns em medidas de
proximidade
Figura 2: Surpefícies observadas pelas distâncias Euclidiana, Mahalanobis e Manhattan
Processo de Agrupamento
Análise dos resultados
• Gráfico da Silhueta
Figura 3: Gráfico da Silhueta
Processo de Agrupamento
Análise dos resultados
• Valores da Silhueta
Valor
Descrição
0,71 – 1,00 Uma estrutura forte foi encontrada.
0,51 – 0,70 Uma estrutura razoável foi encontrada.
0,26 – 0,50 A estrutura é fraca e pode ser superficial.
≤0,25
Nenhuma estrutura substancial foi
encontrada.
Tabela 1: Valores da Silhueta
Agrupamento de Dados
Métodos Hierárquicos
• Os dados são segmentados
sucessivamente, produzindo uma
representação hierárquica dos
agrupamentos
• Tipos:
– Aglomerativos;
– Divisivos;
Agrupamento de Dados
Métodos Hierárquicos
• Aglomerativos
Figura 3: Método Hierárquico Aglomerativo
Agrupamento de Dados
Métodos Hierárquicos
• Aglomerativos
– Principais desvantagens:
• Os agrupamentos não podem ser corrigidos;
• Requerem muito espaço de memória e tempo
de processamento;
Agrupamento de Dados
Métodos Hierárquicos
• Divisivos
Figura 4: Método Hierárquico Divisivo
Agrupamento de Dados
Métodos Hierárquicos
• Divisivos
– Principais vantagens
• Considera muitas divisões no primeiro passo;
– Principais desvantagens:
• Capacidade computacional maior que os
hierárquicos aglomerativos (grande número
de combinações);
• Requerem muito espaço de memória e tempo
de processamento
Agrupamento de Dados
Métodos de Segmentação
• Constroem uma única partição k grupos,
isto é, classificam os dados em k grupos
– Cada grupo deve conter no mínimo um objeto;
– Todo objeto foi atribuído a um grupo.
• Tipos:
– Exclusivos
• Cada objeto pertence a exatamente um grupo
– Não-exclusivos
• A escolha do grupo do objeto é definida com base no
grau de pertinência do mesmo
Contextualização
Mineração de Dados
“A extração de Conhecimento de base de
dados é o processo de identificação de
padrões válidos, novos, potencialmente
úteis e compreensíveis embutidos nos
dados” (Fayyad, Piatetsky-Shapiro e
Smyth citado por Rezende)
Contextualização
Motivação
• Grandes volumes de dados heterogêneos;
• Necessidade de técnicas para extrair a
informação que realmente seja
relevantes.
Mineração de Dados e
Agrupamento
Abordagem da Mineração de Dados
• Segmentação;
• Modelos de predição;
• Visualização;
Mineração de Dados e
Agrupamento
Abordagem da Mineração de Dados
• Segmentação
: Os métodos de
agrupamento são utilizados para
segmentar bases de dados em grupos
homogêneos
Mineração de Dados e
Agrupamento
Abordagem da Mineração de Dados
• Modelos
de Prediticao : Usam o
agrupamento de dados para agrupar
itens, a fim de
inferir regras,
caracterizar os grupos e sugerir
modelos.
Mineração de Dados e
Agrupamento
Abordagem da Mineração de Dados
• Visualização: o agrupamento de dados
pode ser utilizado como tecnica que
permite observar as informacoes em
diferentes niveis e estruturas.
Mineração de Dados
Aplicações citadas pelo autores
• Mineração em dados não estruturados
WWW;
• Mineração em banco de dados
geológicos;
Aplicações - Mineração
de Dados
Exemplo Banco de Dados Geológicos
• Regiao do Alasca
Aplicações - Mineração
de Dados
Exemplo Banco de Dados Geológicos
• Regiao do Alasca
Aplicações - Mineração
de Dados
Mineração de dados da bacia do Alaska
• Definição do contexto
• Descoberta
das
estruturas
primitivas para agrupamento;
• Definição do contexto em termos
relevantes
para
agrupamento
homogêneos de dados;
• Aplicação do algoritmo k-medias
Mineração de Dados
Bacia do Alaska
Algoritmo K-medias
Algoritmo de agrupamento que segmenta
os objetos em conjuntos de elementos
semelhantes, segundo algum criterio
Mineração de Dados
Bacia do Alaska
Algoritmo K-medias
• Etapas
• Define-se
o
número
de
grupamentos;
• Inicia-se os agrupamentos através
de
atributos
arbitrários
ou
centróides;
• Atribuição das amostras
• Volta-se ao passo 3 até um critério
de convergência ser cumprido;
Mineração de Dados
Bacia do Alaska
Algoritmo K-medias
Inicialização dos centróides
Atribuição das amostra
Procura de Novos
centróides
Considerações Finais
Como escolher um método?
• Tipo de atributos que o algoritmo opera;
• Escalabilidade para grandes conjuntos de
dados;
• Definição da melhor métrica de
similaridade;
• Habilidade de operar com uma dimensão
grande de variáveis;
Considerações Finais
Como escolher um método?
• Tratar valores discrepantes (outliers);
• Tempo de execução;
• Dependência de ordem dos dados;
• Interpretabilidade dos resultados.
Considerações Finais
Problemas
• Ferramentas atuais
• Dependência dos usuários
– Informação para início do processo
– Capacidade de interpretação dos
resultados
– Decisão sobre a utilização do método
adequado
Bibliografia
Básica
Jain, A.K. & Murty, M.N. & Flynn, P.J. “Data
Clustering: A Review” – ACM computing Surveys,
vol. 31, nº 3, september 1999.
Complementar
Vale, Marcos Neves do. “Agrupamentos de dados : avaliação de
métodos e desenvolvimento de aplicativo para análise de
grupos” - Orientadores: Marley M. B. R. Vellasco, Ricardo
Tanscheit. – Rio de Janeiro : PUC, Departamento de
Engenharia Elétrica, 2005.
Rezende, Solange de Almeida “Mineração de Dados ”
Lubia Vinhas, Gilberto Ribeiro Queiroz, Karine Reis Ferreira,
gilberto Câmara, Jão Argemiro C. Paiva – “Programação
Genética Aplicada a Algoritmos Geográficos ”- INPE – São
José dos Campos SP.