Agrupamento de Dados: uma Revisão

Data Clustering

Márcia de Oliveira AlvesJosé de Castro Neto

Maio 2006Universidade Federal de Campina Grande

Mestrado em Informatica

• O que é Agrupamento de Dados?• Qual a utilidade?

Niv

ela

men

to

• Contextualização;

• Processo de Agrupamento;

• Agrupamento de Dados;

• Uma Aplicacão: Mineração de Dados;

• Considerações Finais.

• Bibliografia

Rote

iro

• É 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

Con

textu

aliza

ção

Motivação

• 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

Con

textu

aliza

ção

Análise Automática de Dados

Objetivo

Figura 1: Gráfico ilustrativo de dados agrupados em quatro grupos

Pro

cesso d

e

Ag

rup

am

en

to

• Seleção e tratamento dos dados;

• Agrupamento de dados;

• Análise dos resultados;

EtapasP

rocesso d

e

Ag

rup

am

en

to

• 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.

Pro

cesso d

e

Ag

rup

am

en

toSeleção e Tratamento de Dados

• Métodos:– Hierárquicos;– Segmentação;

• Medidas de proximidade

– Dissimilaridade– Similaridade

Pro

cesso d

e

Ag

rup

am

en

toAgrupamento de Dados

• Métricas comuns em medidas de proximidade

Pro

cesso d

e

Ag

rup

am

en

toAgrupamento de Dados

Figura 2: Surpefícies observadas pelas distâncias Euclidiana, Mahalanobis e Manhattan

• Gráfico da Silhueta

Pro

cesso d

e

Ag

rup

am

en

toAnálise dos resultados

Figura 3: Gráfico da Silhueta

Análise dos resultados

• Valores da Silhueta

Pro

cesso d

e

Ag

rup

am

en

to

Tabela 1: 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.

• Os dados são segmentados sucessivamente, produzindo uma representação hierárquica dos agrupamentos

• Tipos:– Aglomerativos;– Divisivos;

Ag

rup

am

en

to d

e

Dad

os

Métodos Hierárquicos

• Aglomerativos

Ag

rup

am

en

to d

e

Dad

os

Métodos Hierárquicos

Figura 3: Método Hierárquico Aglomerativo

• Aglomerativos

– Principais desvantagens:• Os agrupamentos não podem ser

corrigidos;• Requerem muito espaço de memória e

tempo de processamento;

Ag

rup

am

en

to d

e

Dad

os

Métodos Hierárquicos

• Divisivos

Ag

rup

am

en

to d

e

Dad

os

Métodos Hierárquicos

Figura 4: Método Hierárquico Divisivo

• 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

Ag

rup

am

en

to d

e

Dad

os

Métodos Hierárquicos

• 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

Ag

rup

am

en

to d

e

Dad

os

Métodos de Segmentaçã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)C

on

textu

alização

Motivação

• Grandes volumes de dados heterogêneos;

• Necessidade de técnicas para extrair a informação que realmente seja relevantes.

Con

textu

alização

• Segmentação;

• Modelos de predição;

• Visualização;Min

era

ção d

e D

ad

os

e A

gru

pam

en

toAbordagem da Mineração de Dados

• Segmentação : Os métodos de agrupamento são utilizados para segmentar bases de dados em grupos homogêneos

Min

era

ção d

e D

ad

os

e A

gru

pam

en

toAbordagem 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.

Abordagem da Mineração de DadosM

inera

ção d

e D

ad

os

e A

gru

pam

en

to

• Visualização: o agrupamento de dados pode ser utilizado como tecnica que permite observar as informacoes em diferentes niveis e estruturas.

Abordagem da Mineração de DadosM

inera

ção d

e D

ad

os

e A

gru

pam

en

to

Aplicações citadas pelo autores

• Mineração em dados não estruturados WWW;

• Mineração em banco de dados geológicos;

Min

era

ção d

e D

ad

os

Ap

licações -

M

inera

ção d

e D

ad

os

Exemplo Banco de Dados Geológicos

• Regiao do Alasca

Ap

licações -

M

inera

ção d

e D

ad

os

Exemplo Banco de Dados Geológicos

• Regiao do Alasca

Ap

licações -

M

inera

ção d

e D

ad

os

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

Min

era

ção d

e D

ad

os

Bacia

do A

laska

Algoritmo K-medias

Algoritmo de agrupamento que segmenta os objetos em conjuntos de elementos semelhantes, segundo algum criterio

Min

era

ção d

e D

ad

os

Bacia

do A

laska

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;

Min

era

ção d

e D

ad

os

Bacia

do A

laska

Algoritmo K-medias

Inicialização dos centróides Atribuição das amostra

Procura de Novos centróides

• 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;

Como escolher um método?C

on

sid

era

ções

Fin

ais

• Tratar valores discrepantes (outliers);

• Tempo de execução;

• Dependência de ordem dos dados;

• Interpretabilidade dos resultados.

Con

sid

era

ções

Fin

ais

Como escolher um método?

• 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

ProblemasC

on

sid

era

ções

Fin

ais

Jain, A.K. & Murty, M.N. & Flynn, P.J. “Data Clustering: A Review” – ACM computing Surveys, vol. 31, nº 3, september 1999.

ComplementarVale, 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.

BásicaB

ibliog

rafi

a