Embed Size (px)
Citation preview
Agrupamento de Agrupamento de padrões Métodos padrões Métodos
hierárquicoshierárquicosJairo LucasJairo Lucas
Wesley MenenguciWesley Menenguci
Agrupamento de padrõesAgrupamento de padrões
IntroduçãoIntrodução Motivação Motivação Mineração de DadosMineração de Dados Métodos hierarquicosMétodos hierarquicos
Hierárquico DivisivoHierárquico Divisivo Hierárquico AglomerativoHierárquico Aglomerativo
BibliografiaBibliografia
IntroduçãoIntrodução
Atualmente cresce cada vez mais o Atualmente cresce cada vez mais o volume e a velocidade com que dados volume e a velocidade com que dados digitais são armazenados e digitais são armazenados e disponibilizados para o usuário, da disponibilizados para o usuário, da mesma forma cresce a necessidade e a mesma forma cresce a necessidade e a expectativa de poder se obter, de expectativa de poder se obter, de forma automatizada, informações forma automatizada, informações implícitas nestes dados sem a implícitas nestes dados sem a necessidade de prévio conhecimento necessidade de prévio conhecimento dos mesmosdos mesmos
MotivaçãoMotivação
Empresas como a Unimed e a Visa Empresas como a Unimed e a Visa possuem atualmente mais de 2 possuem atualmente mais de 2 milhões de associados no Brasil, milhões de associados no Brasil, como segmentar estes associados em como segmentar estes associados em grupos com perfis semelhantes?grupos com perfis semelhantes?
Como reconhecer áreas semelhantes Como reconhecer áreas semelhantes em imagens geográficas de satelites?em imagens geográficas de satelites?
Agrupamento de padrõesAgrupamento de padrões
A mineração de dados (data mining) A mineração de dados (data mining) através de técnicas de classificação através de técnicas de classificação automática e KDD KnowLedge Discovery automática e KDD KnowLedge Discovery em database) procuram ajudar em em database) procuram ajudar em soluções para este tipo de problema.soluções para este tipo de problema.
Existem uma vasta diversidade de Existem uma vasta diversidade de métodos e técnicas de classificação métodos e técnicas de classificação (baseadas em associação, regressão, (baseadas em associação, regressão, sumarização, agrupamento). sumarização, agrupamento).
Agrupamento de padrõesAgrupamento de padrões
Agrupamento de padrões (clustering) - Agrupamento de padrões (clustering) - Técnica não supervisionada que busca Técnica não supervisionada que busca extrair conhecimentos úteis de uma base extrair conhecimentos úteis de uma base de dados.de dados.
Diversas técnicasDiversas técnicas HierárquicosHierárquicos
DivisivoDivisivo AglomerativoAglomerativo
GenéticosGenéticos MemeticosMemeticos K-meansK-means
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
O método hierárquico divisivo cria O método hierárquico divisivo cria uma decomposição da base uma decomposição da base principal, onde no primeiro passo, principal, onde no primeiro passo, todos os dados pertencem ao mesmo todos os dados pertencem ao mesmo cluster , sendo separados em cluster cluster , sendo separados em cluster menores nos passos subsequentes.menores nos passos subsequentes.
Solução top downSolução top down
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
Medidas de similaridadeMedidas de similaridade Distância Euclidiana quadráticaDistância Euclidiana quadrática
Distância de ManhatanDistância de Manhatan
Escolha do maior clusterEscolha do maior cluster Baseado na soma das distância quadráticas (SSE)Baseado na soma das distância quadráticas (SSE)
Menos suscetível a ruídos da baseMenos suscetível a ruídos da base Sofre maior influência do número de elementos do Sofre maior influência do número de elementos do
clustercluster
p
i
xy YiXiYpXpYXYXd1
2222...2211
Soma das distâncias de todos os Soma das distâncias de todos os elementos até o centro de massa de elementos até o centro de massa de centróide (centro de massa)centróide (centro de massa)
Baseado na dimensionalidadeBaseado na dimensionalidade Mais suscetível a ruídos da baseMais suscetível a ruídos da base Não sofre influência do número de elementos Não sofre influência do número de elementos
do clusterdo cluster
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
TécnicaTécnica
Agrupamento de padrões – Agrupamento de padrões – hierárquico Divisivohierárquico Divisivo
Matriz de distância entre os elementosMatriz de distância entre os elementos
Ex: D(a,b) = 25-32 ^2 + 56 – 80 ^2 + 160 -187 ^2 + 1 -1 ^ 2 Ex: D(a,b) = 25-32 ^2 + 56 – 80 ^2 + 160 -187 ^2 + 1 -1 ^ 2 = 3.364 = 3.364
Agrupamento de padrões – Agrupamento de padrões – hierárquico Divisivohierárquico Divisivo
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
Agrupamento de padrões – Agrupamento de padrões – hierárquico Divisivohierárquico Divisivo
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo – hierárquico Divisivo
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
Agrupamento de padrões Agrupamento de padrões – hierárquico Divisivo– hierárquico Divisivo
Agrupamento de padrões – Agrupamento de padrões – hierárquico Divisivohierárquico Divisivo
• ComplexidadeComplexidade• Montar a matriz de distâncias : nMontar a matriz de distâncias : n22 /2 /2• Calcular o SSE : K * n (k= nr partições)Calcular o SSE : K * n (k= nr partições)• Possui tempo assintótico de O nPossui tempo assintótico de O n2 2
Principais VantagensPrincipais Vantagens* Apresenta solução clara e “rastreavel”* Apresenta solução clara e “rastreavel”* Fácil implementação* Fácil implementação
Principais limitaçõesPrincipais limitações* Custo computacional* Custo computacional* Não possui backing tracking * Não possui backing tracking
Agrupamento de padrões Agrupamento de padrões – hierárquico – hierárquico AglomerativoAglomerativo No início cada elemento forma um cluster, nas No início cada elemento forma um cluster, nas
interações seguintes os cluster vão se unindo interações seguintes os cluster vão se unindo até atingir o número de cluster desejados.até atingir o número de cluster desejados.
Solução Botom – upSolução Botom – up
Utiliza distância euclidiana para unir os Utiliza distância euclidiana para unir os cluster mais próximoscluster mais próximos
Em Cluster com mais de um elemento a Em Cluster com mais de um elemento a distância é medida em relação ao seu distância é medida em relação ao seu centróide.centróide.
Agrupamento de padrões Agrupamento de padrões – hierárquico – hierárquico AglomerativoAglomerativo
Agrupamento de padrões Agrupamento de padrões – hierárquico – hierárquico AglomerativoAglomerativo
Agrupamento de padrões – Agrupamento de padrões – hierárquico Aglomerativohierárquico Aglomerativo
Agrupamento de padrões Agrupamento de padrões – hierárquico – hierárquico AglomerativoAglomerativo
Agrupamento de padrões Agrupamento de padrões – hierárquico – hierárquico AglomerativoAglomerativo
Agrupamento de padrões – Agrupamento de padrões – hierárquico Aglomerativohierárquico Aglomerativo
Agrupamento de padrões – Agrupamento de padrões – hierárquico Aglomerativohierárquico Aglomerativo
Agrupamento de padrões – Agrupamento de padrões – hierárquico Aglomerativohierárquico Aglomerativo
Agrupamento de padrões – Agrupamento de padrões – hierárquico Aglomerativohierárquico Aglomerativo
• ComplexidadeComplexidade• Montar a matriz de distâncias : nMontar a matriz de distâncias : n22 /2 /2• Calcular o centróide e distâncias até ele : K * n Possui Calcular o centróide e distâncias até ele : K * n Possui
tempo assintótico de O ntempo assintótico de O n2 2
Principais VantagensPrincipais Vantagens* Apresenta solução clara e “rastreavel”* Apresenta solução clara e “rastreavel”* Fácil implementação* Fácil implementação
Principais limitaçõesPrincipais limitações* Custo computacional* Custo computacional* Não possui backing tracking * Não possui backing tracking * É mais suscetível a ruídos que o divisivo.* É mais suscetível a ruídos que o divisivo.
Agrupamento de padrões – Agrupamento de padrões – hierárquico Aglomerativohierárquico Aglomerativo
Bibliografia:Bibliografia: Prass, Fernando Sarturi: Estudo de Prass, Fernando Sarturi: Estudo de
comparativo entre algoritmos de análise de comparativo entre algoritmos de análise de agrupamento em Data Minning – Dissertação agrupamento em Data Minning – Dissertação de mestrado submetida a Universidade de mestrado submetida a Universidade Federal de Santa Catarina – SC 2004Federal de Santa Catarina – SC 2004
Metz, Jean e Monard, Maria Carolina - Estudo Metz, Jean e Monard, Maria Carolina - Estudo e análise das diversas representações e e análise das diversas representações e estrutura de dados utilizadas nos algoritmos estrutura de dados utilizadas nos algoritmos de clustering hierárquico – Relatório técnico de clustering hierárquico – Relatório técnico do ICMC – USP – 2006do ICMC – USP – 2006
