Mineração em Data Streams - Clustering Profa. Elaine Faria ...elaine/disc/MFCD2018/Aula2.pdf ·...

Mineração em Data Streams - Clustering

Profa. Elaine Faria UFU - 2018

Mineração de Dados

• Tarefas de mineração– Tarefas Preditivas

• Classificação • Regressão• Detecção de Anomalias

Tarefas Descritivas• Agrupamento• Descoberta de Regras de Associação• Descoberta de Padrões Sequenciais

Qual a diferença entre agrupamento e classificação

• Agrupamento– Aprendizado não-supervisionado sem

rótulo

• Classificação– Aprendizado supervisionado usa os rótulos

Exemplo de Agrupamento

Nome Idade Peso

João 25 60

Ana 50 75

Pedro 60 90

Maria 22 65

Paulo 18 68

Aldo 15 80

Aplicação de uma técnica

agrupamento

João

Maria

Paulo

AldoAna

Pedro

Agrupamento - definições

Análise de grupos ou clusters é o estudo de algoritmos e métodos para agrupar objetos de acordo com suas características.

Cluster (grupo) é uma aglomeração de pontos no espaço tal que a distância entre quaisquer dois pontos no cluster é menor que a distância entre qualquer ponto no cluster e qualquer ponto que não está nele.

Jain, A. K.; Dubes, R. C. Algorithms for Clustering Data, Prentice Hall, 1988.

Agrupamento - questões

• O que é um grupo ideal?

• Quantos grupos devem ser formados?

• Há um agrupamento natural dos dados?

• Como podemos definir o que é semelhante?

Agrupamento

Quantos grupos?

Tan P., SteinBack M. e Kumar V. Introduction to Data Mining, Pearson, 2006

Agrupamento

Quantos grupos?

Tan P., SteinBack M. e Kumar V. Introduction to Data Mining, Pearson, 2006

Agrupamento

Quantos grupos?

Tan P., SteinBack M. e Kumar V. Introduction to Data Mining, Pearson, 2006

Agrupamento

Quantos grupos?

Tan P., SteinBack M. e Kumar V. Introduction to Data Mining, Pearson, 2006

Agrupamento• Como agrupar os objetos??

• Alguns dos possíveis agrupamento

Keogh, E. A g. Introduction to Machine Learning and Data Mining for the Database Community, SBBD 2003, Manaus.

Agrupamento - questões

JAIN, A. K. 2008. Data Clustering: 50 Years Beyond K-Means, Pattern Recognition Letters, vol. 31, n 8, 2010.

Dados de entrada Agrupamento desejado

Agrupamento

• Semelhança entre objetos

Keogh, E. A g. Introduction to Machine Learning and Data Mining for the Database Community, SBBD 2003, Manaus.

Agrupamento

Após realizar o agrupamento o problema acabou?

Não, agora é preciso interpretar os resultados obtidos!!!!Analisar e avaliar o agrupamento!

Importância do agrupamento

• Será que agrupamento é mesmo importante?– Mais de 50 anos de estudo sobre técnicas de

agrupamento– Milhares de aplicações– Dezenas de ferramentas na internet para

fazer agrupamento automático– Milhares de artigos publicados na área

Exemplos de aplicações de agrupamento de dados

• Marketing– Ex: Agrupamento de clientes para direcionar

campanhas de marketing• Documentos

– Ex: agrupar documentos que tratam do mesmo assunto

• Imagens– Ex: Segmentar imagens usando técnicas de

agrupamento• Biologia

– Ex: agrupar animais de acordo com o reino, ramo, classe, ordem, gênero, ....

Processo de Agrupamento

Jain, A. K., Murty, M. N., Flynn, P. J., Data clustering: a review, ACM Computing Surveys, vol. 31, n 3, 1999.

Mas e ai, por onde eu começo?

Tipos de Agrupamento

• Seja X = {x1, x2,..., xn} o conjunto de todos os dados– Tarefa: colocar cada Xi em um dos m clusters

C1, C2, ..., Cm

– Clusters podem ser de dois tipos:– Tipo 1: duro (crisp)– Tipo 2: fuzzy

Tipos de Agrupamento

• Cluster Crisp– Cada exemplo Xi pertence ou não a cada

cluster Cj

– Exemplo em Ci é mais semelhante a outros em Ci que àqueles em Cj, i ≠ j

Tipos de Agrupamento

• Cluster Fuzzy– Usa uma função de pertinência para definir o

quanto um elemento pertence a um grupo

Matriz de Partição

• Matriz com K linhas (nro de grupos) e N colunas (nro de objetos) no qual cada elemento Xij indica o grau de pertinência do j-ésimo elemento ao i-ésimo grupo

• Matriz rígida (sem sobreposição) – Se a matriz for binária– Se restrição for satisfeita

iijX 1

Diferentes Tipos de Agrupamento

• Agrupamento Particional– Divisão do conjunto de dados em grupos (não

sobrepostos) tal que cada objeto está em exatamente um grupo

X• Agrupamento Hierárquico

– Conjunto de grupos aninhados que estão organizados como uma árvore

– Cada nó (grupo) na árvore (exceto as folhas) é a união de dos seus filhos (subgrupos)

– A raiz contém todos os objetos da base

Diferentes Tipos de Agrupamento

Keogh, E. A g. Introduction to Machine Learning and Data Mining for the Database Community, SBBD 2003, Manaus.

Diferentes Tipos de Agrupamento

• Exclusivo– Associa cada objeto a um único cluster

X• Sobreposição (não exclusivo)

– Um objeto pode pertencer simultaneamente a mais que um grupo

X• Fuzzy

– Cada objeto pertence a cada grupo com um grau de pertinência entre 0 e 1

Diferentes Tipos de Agrupamento

• Completo– Associa cada objeto a um cluster

X• Parcial

– Não associa cada objeto a um cluster– Motivação: alguns objetos no conjunto de

dados podem não pertencer a grupos bem definidos

• Ex: ruídos ou outliers

Diferentes Tipos de Grupos

• Baseado em Grafos– Dados são representados como grafos – Os nós são os objetos e as arestas são as

conexões entre os objetos – Cluster: é um componente conectado

• Baseado em Densidade– Região densa de objetos que é circundada

por uma região de baixa densidade

Algoritmos Particionais

• Características– São baseados na minimização de uma função de

custo– Objetos agrupados em um número K de grupos– Cada objeto é agrupado no grupo que minimiza a

função de custo– Uma única partição é obtida

• Vantagem– Um objeto pode mudar de grupo ao longo do

agrupamento

k-Means• Algoritmo Básico

– Escolher K centróides • K é um parâmetro especificado pelo usuário• K representa o nro de grupos

– Cada objeto é associado ao seu centróide mais próximo

• Cada coleção de objetos associados a um centróide forma um grupo

– Recalcule os centros dos grupos– Repetir os dois passos anteriores até que não haja

mudança nos grupos ou equivalentemente, até que os centróides permaneçam o mesmo

k-MeansSelecione K objetos como centróidesRepita

Forme K grupos associando cada objeto ao seu centróide mais próximoRecalcule os centróides de cada grupo

Até que Convergência seja obtida

k-Means

• Centróides iniciais– Ex de Técnica: Escolher aleatoriamente

objetos do conjunto de dados

• Associar um objeto ao seu grupo mais próximo– Usar uma medida de proximidade que

quantifica a noção de mais próximo– Ex: usar distância Euclidiana

k-Means

• Critérios de Convergência– Número máximo de iterações é obtido– Limiar mínimo de mudanças nos centróides

k-Means

• Função Objetivo– Objetivo do agrupamento

Minimizar a distância quadrada de cada objeto ao seu centróide mais próximo

d: distância Euclidiana

k

c Cxcj

cj

xxdJ1

2),(

k-Means

• Limitações– Escolha do valor de K– Problemas quando os grupos têm

• Diferentes densidades• Formatos não hiper-esféricos

– Problemas quando os dados possuem outliers

k-Means – Grupos com diferentes tamanhos

Figura retirada dos slides do prof. André C. P. L. F. Carvalho – disciplina Aprendizado de Máquina – ICMC-USP

k-Means – Grupos com diferentes densidades

Figura retirada dos slides do prof. André C. P. L. F. Carvalho – disciplina Aprendizado de Máquina – ICMC-USP

k-Means – Grupos não globulares

Figura retirada dos slides do prof. André C. P. L. F. Carvalho – disciplina Aprendizado de Máquina – ICMC-USP

Agrupamento em Data Streams

• Problema a ser tratado– Manter continuamente um agrupamento

consistente e bom das sequências observadas até o momento, usando uma pequena quantidade de memória e tempo

– Tratar a evolução dos dados ao longo do tempo

– Tratar mudança no número de grupos ao longo do tempo

Agrupamento em Data Streams

• Algoritmos– BIRCH (Zhang et 1996) desenvolvido para

grandes bases de dados– CluStream (Aggarwall et al., 2003)– DenStream (Cao et al., 2006)– StreamKM++ (Ackerman et al., 2010)– Clustree (Kranen et al., 2011)

Agrupamento em Data Streams

• Visão geral dos algoritmos

Retirado de: SILVA, J. A.; FARIA, E. R.; BARROS, R. C.; HRUSCHKA, E. R.; CARVALHO, A. C.P. L. F. d.; GAMA, J. a. Data stream clustering: A survey. ACM Comput. Surv., ACM,New York, NY, USA, v. 46, n. 1, p. 13:1–13:31, jul. 2013

Agrupamento em Data Streams

• Conceitos– CF-Vetor (Vetor de Características)

• N: número de objetos• LS: soma linear dos N objetos• SS: soma dos quadrados dos N objetos

• AditividadeCF1+CF2 = (N1 + N2, LS1+LS2, SS1+SS2)

• IncrementalidadeLS LS + x SS SS + x2 N N + 1

Agrupamento em Data Streams

• Usando o CF-Vetor importantes medidas podem ser calculadas

Agrupamento Particional em Data Streams

• CluStream (Aggarwall et al., 2003)– Framework para trabalhar com data streams

– Fase online (micro-agrupamento)• Mantém um sumário estatístico periodicamente

– q micro-grupos são mantidos (extensão do CF-Vetor)

– Fase offline (macro-agrupamento)• Agrupamento dos micro-grupos

– Modificação do K-Means

Obs.: q micro-grupos iniciais obtidos pela execução do K-Means

Agrupamento Particional em Data Streams

q micro-grupos

Extensão Temporal do CF-Vector

N: número de objetos

LS: soma linear dos N objetos

SS: soma do quadrado dos N objetos

CF1: soma dos timestamps

CF2: soma dos quadrados dos timestamps

CluStream (Aggarwall et al, 2003)

Agrupamento Particional em Data Streams

• CluStream (Aggarwall et al., 2003)– q micro-grupos são armazenados na memória

representando o snapshot atual• M1,... , Mq, sendo que cada M tem um id• Se Ma e Mb são unidos

– Lista de id’s é criada

– Se o marcador de tempo é divisível por (α^l)• Micro-grupos são armazenados no disco• Micro-grupos antigos são removidos se eles

excedem um certo limiar

CluStream – Algoritmo

Fase Offline:Executar o K-Means nos InitN primeiros exemplos da base de dados, gerando q micro-grupos iniciais

Fase Online: Para cada novo exemplo x

Encontre o micro-grupo c mais próximo a xSe dist(c,x) < δ

Atualize c com xCaso Contrário

Crie um novo micro-grupo para cSe algum micro-grupo é um outlier

Remova o micro-clusterCaso contrário

Una os dois micro-grupos mais próximos

Agrupamento Particional em Data Streams

• CluStream – Complexidade– Inserir um novo elemento: O(q x d)– Inserir todos os elementos: O(N x q x d)

• q: nro de micro-grupos• d: dimensão dos dados• N: nro de elementos do data streams (supondo

que ele é finito)– Unir os dois micro-grupos mais próximos:

O(q2 x d)

Agrupamento Hierárquico• É um procedimento para transformar uma matriz

de proximidade em uma sequência de partições aninhadas

• Produz uma sequência (hierarquia) de agrupamentos

• Usado em áreas que utilizam estrutura de agrupamento hierárquica– Ex: biologia e arqueologia

Agrupamento Hierárquico• Seja B= {G1, G2, ..., Gm} uma partição dos dados

X = {x1, x2, ..., xn}

• Uma partição B está aninhada em C (B ⊂ C)– Se cada componente de B é um subconjunto de um

componente de C• C é formado unindo componentes de B

Exemplo: B está aninhando em CC={(x1,x3,x5,x7),(x2,x4,x6,x8),(x9,x10)}B={(x1,x3),(x5,x7),(x2),(x4,x6,x8),(x9,x10)}

Agrupamento Hierárquico

• É sempre exibido graficamente usando um diagrama chamado dendograma– Mostra os grupos-subgrupos e a ordem na

qual os grupos foram unidos (visão aglomerativa) ou divididos (visão divisiva)

• Para dados com 2 dimensões, o agrupamento hierárquico pode ser visto usando o diagrama de grupos aninhados

Agrupamento Hierárquico

Representação de agrupamento hierárquico

Imagem reitrada de Tan P., SteinBack M. e Kumar V. Introduction to Data Mining, Pearson, 2006

Dendograma Conjunto de diagrama aninhado

Agrupamento Hierárquico

Exemplo de Dendograma

Exemplo retirado de Jain, A. K.; Dubes, R. C. Algorithms for Clustering Data, Prentice Hall, 1988.

Agrupamento Hierárquico• Aglomerativo

– Inicia com os elementos como grupos individuais– A cada passo, o par de elementos mais próximos é

unido– Exige a definição de uma noção de proximidade

• Divisivo– Inicia com um grupo, contendo todos os elementos– A cada passo, dividir o grupo até que grupos com um

único elemento sejam obtido– É necessário decidir qual grupo dividir a cada passo e

como fazer essa divisão

Agrupamento Hierárquico

Figura retirada dos slides do prof. André C. P. L. F. Carvalho – disciplina Aprendizado de Máquina – ICMC-USP

Algoritmo Básico para Agrupamento Hierárquico Aglomerativo

Compute a matriz de proximidade, se necessário.

repita unir os dois grupos mais próximos

atualize a matriz de proximidade para refletir a proximidade entre o novo grupo e os grupos originais

Até que somente um grupo seja obtido

Definindo Proximidade entre Grupos

• Min• Max• Média do grupo• Centróide• Técnica alternativa

– Método Ward’s

Método Divisivos

• Ideia Geral– Iniciar com um grupo contendo todos os

elementos– Dividir o grupo em 2– Recursivamente sub-dividir cada grupo em 2

até que grupos com um elemento sejam encontrados

Método Divisivos

• Pouco explorados na literatura. Por que?Alta Complexidade Computacional

Métodos Algomerativos:Todas as possíveis junções em

Métodos Divisivos:Todas as possíveis divisões em dois conjuntos não-vazios em :

2)1(2

nnCn

12 1 n

Agrupamento Hierárquico em Data Streams

• BIRCH (Zhang et 1996)– Constrói uma estrutura hierárquica CF-Árvore

• Árvore B+• Os nós não-folhas contêm no máximo B entradas,

cada entrada CF-Vetor e um ponteiro-filho• Os nós folhas contêm no máximo L entradas, cada

entrada CF-Vetor– Fase 1 (Online): Construção da CF-Árvore– Fase 2 (Offline): Agrupamento das folhas

Agrupamento Hierárquico em Data Streams

CF-Vetor

Nó não-folha

Soma do CF-Vetor dos Filhos

Nó RaizBirch (Zhang et al, 1996)

BIRCH

Imagem retirada de: http://engr.case.edu/zhang_xiang/teaching/eecs435/presentation/He.Jiang.pdf

Birch- AlgorithmInserção na CF-TreeEntrada: T: limiar que indica o raio máximo de uma folha, B = nro

máximo de entradas em um nó folha, L = nro máximo de entradas em um nó não-folha

Descer da raiz até as folhas seguindo o caminho do CF mais próximo

Ao chegar na folhaSe a entrada mais próxima no nó-folha pode absorver o exemplo (usando T)

Atualize o seu CFCaso contrário

Crie um novo CFSe há espaço na folha para inserir o CF (max = B)

Insira-oCaso Contrário

Divida o nó paiAtualize o CF de todo o caminho percorrido por x

Birch – AlgoritmoRefazendo a CF-Tree

Se não há mais espaço na memóriaAumente o limiar TRefaça a árvore com os dados já inseridos usando TContinue a inserção de novos dados

1 2 3 4 75

BIRCHExemplo de Inserção Split (B=3 e L=3):

63

1 2 3

R

PCF2 PCF3CF1

CF2

CF3 CF4 CF5

CF6CF7

PCF1

CF

6

Imagem retirada dos slides do aluno Jonathan Andrade - apresentação na disciplina Agrupamento de Dados do ICMC - USP - 2010.

1 2 5 6 7

BIRCHExemplo de Inserção Split (B=3 e L=3):

64

PCF4

PCF2 PCF3

CF1

CF2CF3

CF4 CF5CF6 CF7

CF

PCF1

R

1 4 2 3

43Imagem retirada dos slides do aluno Jonathan Andrade - apresentação na disciplina Agrupamento de Dados do ICMC - USP - 2010.

BIRCHExemplo de Inserção Split (B=3 e L=3):

65

PCF4

PCF2 PCF3

CF1

CF2CF3

CF4 CF5CF6 CF7CF

PCF1

ACF1ACF2

2 3

R

1 2

1 4

1 2 3 4 5 6 7Imagem retirada dos slides do aluno Jonathan Andrade - apresentação na disciplina Agrupamento de Dados do ICMC - USP - 2010.

Algoritmos Baseados em Densidade

• Baseiam-se na ideia de densidade– Clusters são regiões de alta densidade separadas por

regiões de baixa densidade• Características

– Descoberta de grupos de formato arbitrário– Tratamento de ruído– Não é necessário informar o número de grupos

• Mas outros parâmetros relativos à densidade são necessários

• Exemplos de algoritmos– DBSCAN, OPTICS, DENCLUE e CLIQUE

DBSCAN

• É um método de agrupamento baseado em densidade– Parâmetros: Eps – raio máximo de uma vizinhança e

MinPts – nro mínimo de pontos em uma vizinhança Eps daquele ponto

• É um método baseado em centro– A densidade é estimada para um ponto particular no conjunto de dados, contando o nro de pontos dentro de um raio, Eps, daquele ponto (que inclui ele mesmo)

Imagem reitrada de Tan P., SteinBack M. e Kumar V. Introduction to Data Mining, Pearson, 2006

DBSCAN

• Classificação dos pontos de acordo com a densidade baseada em centro– Core points

• Estão no interior de um cluster baseado em densidade• Um ponto é um core point se o nro de pontos dentro de uma

dada vizinhança ao redor do ponto (determinada por Eps e uma função de distância) excede um limiar MinPts

– Border points• Um exemplo que não é core point, mas que está dentro da

vizinhança de um core point

– Noise points• Um ponto que não é core point nem border point

DBSCAN

Imagem reitrada de Tan P., SteinBack M. e Kumar V. Introduction to Data Mining, Pearson, 2006

DBSCAN

• Ideia Geral– Quaisquer dois core points que estão próximo o

suficiente – dentro de uma distância Eps um do outro – são colocados no mesmo cluster

– Qualquer border point que está próximo o suficiente de um core point é colocado no mesmo cluster que esse core point

• Pode haver empates se um border point está igualmente próximo a dois ou mais core points de diferentes clusters

– Noise points são descartados

DBSCAN - Algoritmo1. Rotule todos os pontos como core, border

ou noise2. Elimine os pontos rotulados como noise3. Coloque uma aresta entre todos os pontos

core que estão a um distância Eps um do outro

4. Faça cada componente conectado de pontos core um cluster separado

5. Associe cada border ao clusters de um dos seus core associados1. Resolva empates se houver objetos core

associados a diferentes clusters

DBSCAN

• Complexidade– Tempo: O (n x tempo para encontrar os

pontos na vizinhança Eps)• n é o nro de pontos• Pior caso O(n2)• Há estruturas como kd-trees que permitem

eficientemente recuperar todos os pontos dentro de uma dada distância de um ponto específico com complexidade O (n log n)

– Espaço: O (n)• Armazenar somente os pontos e um rótulo

DBSCAN

• Vantagens– Resistente a ruídos– Eficiente em grandes bases de dados– Trata clusters de diferentes formatos e tamanhos– Não é necessário especificar o nro de grupos

• Desvantagem– Sensível aos parâmetros MinPts e Eps– Sensível a bases com alta dimensionalidade– Problema quando os clusters possuem diferentes

densidades

DBSCAN – Questões a sem tratadas

• Seleção dos Parâmetros Eps e MinPts– Proposta Básica

• Observar o comportamento da distância de um ponto aos seus k-ésimos vizinhos mais próximos k-dist

– Para pontos no mesmo cluster, k-dist será pequeno se o k não for maior que o tamanho do cluster

– Para pontos que não estão no mesmo grupo (tais como ruídos), k-dist será relativamente grande

• Computar k-dist para todos os pontos para algum k, ordenar em ordem crescente e plotar os valores ordenados

– É esperado encontrar uma mudança no valor de k-dist que corresponde a um valor adequado para Eps

– Usar k-dist para o valor de Eps e K para MinPts

Agrupamento baseado em densidade em Data Streams

• DenStream– Baseado no paradigma de agrupamento por

densidade– Também propõe o uso do CF-Vector

• Associa um peso (w) a cada micro-cluster– Indica a importância do exemplo com base na temporalidade

DenStream

• O algoritmo é dividido em duas fases• Fase online

– Usa duas estruturas p-micro-cluster (ou potencial micro-cluster) e o-micro-cluster (ou outlier micro-cluster).

– p-micro-cluster: – o-micro-cluster:

β e μ são parâmetros de entrada

DenStream

• Os primeiros p-micro-clusters são obtidos aplicando o DBSCAN em um conjunto inicial de dados do fluxo

DenStream

Retirado do TCC de Jean de Sousa Ferreira - Comparação entre métodos de agrupamentos para fluxos contínuos de dados - UFU - 2016

Desafios Futuros• Criar algoritmos em que não seja preciso configurar

parâmetros críticos– Número de grupos– Densidade dos grupos– Tamanho da janela– Fator de decaímento dos elementos

• Tratar o problema dos outliers– Diferenciar o surgimento de novos grupos de ruídos ou outliers

nos dados

• Lidar com a distribuição não-estacionária dos dados

• Lidar com diferentes tipos de dadosRetirado de: SILVA, J. A.; FARIA, E. R.; BARROS, R. C.; HRUSCHKA, E. R.; CARVALHO, A. C.P. L. F. d.; GAMA, J. a. Data stream clustering: A survey. ACM Comput. Surv., ACM,New York, NY, USA, v. 46, n. 1, p. 13:1–13:31, jul. 2013

Desafios Futuros

• Possíveis aplicações– Dados produzidos por dispositivos móveis– Dados de redes sociais– Dados de sistemas distribuídos em tempo

real

Referências• Jain, A. K., Murty, M. N., Flynn, P. J., Data clustering: a

review, ACM Computing Surveys, vol. 31, n 3, 1999.• Jain, A. K. 2008. Data Clustering: 50 Years Beyond K-

Means, Pattern Recognition Letters, vol. 31, n 8, 2010.• Jain, A. K.; Dubes, R. C. Algorithms for Clustering Data,

Prentice Hall, 1988.• Tan P., SteinBack M. e Kumar V. Introduction to Data

Mining, Pearson, 2006.• Keogh, E. A g. Introduction to Machine Learning and

Data Mining for the Database Community, SBBD 2003, Manaus.

Referências

• Aggarwal, C. C., Han J., Wang, J. & Yu, P. S. A Framework for Clustering Evolving Data Stream. In Proc. of the 29th VLDB Conference (2003).

• Zhang, T.; R., R.; Livny, M. , BIRCH: An efficient data clustering method for very large databases, SIGMOD '96, ACM Press (2006).

• Gama, J. Knowledge Discovery from Data Streams, Chapman & Hall, 2010.