Videoaula_12_M4_Tecnicas_de_agrupamento_revisto

Prévia do material em texto

<p>Técnicas de agrupamento</p><p>Técnicas de agrupamento (clustering) buscam encontrar grupos</p><p>de objetos similares em um conjunto de dados.</p><p>Uma questão natural nesse contexto é como definir similaridade</p><p>entre objetos.</p><p>Não existe uma resposta imediata para tal questão, pois</p><p>similaridade depende tanto do problema como da natureza dos</p><p>dados.</p><p>Técnicas de agrupamento</p><p>Por exemplo, suponha que a distância entre pontos seja a</p><p>medida de similaridade:</p><p>Definindo grupos de modo que a</p><p>soma das distâncias entre os</p><p>elementos de um mesmo grupo</p><p>seja a menor possível entre todos</p><p>os possíveis grupos, obtemos:</p><p>Neste caso, a distância entre pontos</p><p>foi uma medida de similaridade</p><p>adequada para identificar os grupos.</p><p>Neste caso, a distância</p><p>entre pontos não foi capaz</p><p>de identificar os grupos.</p><p>dados originais</p><p>Técnicas de agrupamento</p><p>Medidas de similaridade também dependem dos dados:</p><p>DTW</p><p>séries temporais</p><p>euclideana</p><p>dados multivariados</p><p>Introdução a Ciencia de Dados</p><p>Levenshtein</p><p>Introdução 2 CienTia DOS Dados</p><p>sequências de caracteres</p><p>Técnicas de agrupamento</p><p>Existem muitas técnicas de</p><p>agrupamento:</p><p> Kmeans;</p><p> agrupamento hierárquico;</p><p> DBSCAN;</p><p> agrupamento spectral;</p><p> ...</p><p>Kmeans</p><p>O método Kmeans parte de uma ideia muito simples.</p><p>Suponha que o número de grupos a ser calculado seja conhecido</p><p>e que o centroide de cada grupo também seja conhecido.</p><p>OBS.: o centroide de um conjunto de pontos é o ponto cujas</p><p>coordenadas são dadas pela média de cada coordenada dos</p><p>pontos do conjunto.</p><p>A partir dos centroides, os elementos de cada grupo podem ser</p><p>definidos como os que estão mais perto do centroide do grupo.</p><p>Kmeans</p><p>centroides</p><p>pontos mais próximos</p><p>do centroides</p><p>grupos</p><p>Kmeans</p><p>Por outro lado, conhecidos os grupos, os centroides podem ser</p><p>facilmente calculados como a média das coordenadas dos pontos</p><p>em cada grupo.</p><p>O problema é que, na prática, não se conhecem nem os centroides</p><p>nem os grupos.</p><p>A ideia do método Kmeans é repetir os seguintes passos</p><p>iterativamente:</p><p>1. assuma que os centroides são conhecidos e calcule os grupos e</p><p>2. assuma que os grupos são conhecidos e calcule os centroides.</p><p>Começando com os centroides em qualquer posição, os passos 1 e 2</p><p>são repetidos até que a posição dos centroides não varie mais entre</p><p>iterações.</p><p>Kmeans</p><p>1 2 3</p><p>4 5 6</p><p>Kmeans: propriedades</p><p>1. Kmeans é muito eficiente, encontrando os grupos</p><p>rapidamente;</p><p>2. o número de grupos deve ser fixado no início do processo;</p><p>3. tende a encontrar grupos contidos em regiões ”convexas”</p><p>do espaço e</p><p>4. realiza operações no espaço cartesiano para calcular os</p><p>centroides, sendo difícil de ser adaptado para dados não</p><p>cartesianos, como séries temporais, por exemplo (embora</p><p>existam versões que utilizam somente a função de</p><p>similaridade, evitando operações no espaço cartesiano).</p><p>Agrupamento hierárquico</p><p>O agrupamento hierárquico busca identificar grupos de objetos</p><p>semelhantes, utilizando uma das seguintes estratégias:</p><p>1. dividir, sucessivamente, o conjunto de dados original até que</p><p>algum critério aponte o momento de cessar a divisão</p><p>(método de particionamento) e</p><p>2. agrupar, sucessivamente, os objetos até que um critério</p><p>aponte o momento de cessar o agrupamento (agrupamento</p><p>aglomerativo).</p><p>O critério de parada, em ambos os casos, pode ser o número de</p><p>grupos desejado (embora muitos outros critérios possam ser</p><p>adotados).</p><p>Técnicas de agrupamento</p><p>Agrupamentos hierárquicos podem operar diretamente nas</p><p>informações de similaridade, evitando cálculos em espaços</p><p>cartesianos.</p><p>Tais métodos assumem como entrada a matriz de ”distâncias”</p><p>entre os objetos.</p><p>matriz de dados matriz de distâncias</p><p>Agrupamento hierárquico aglomerativo</p><p>Métodos aglomerativos operam em duas etapas:</p><p>1. identificação dos elementos mais similares e</p><p>2. união dos elementos mais similares e novo cálculo de</p><p>distâncias.</p><p>Os passos 1 e 2 são executados até que o número de grupos</p><p>desejado seja atingido ou até que a distância entre os elementos</p><p>a serem unidos seja maior que um limiar desejado.</p><p>Um dos problemas é como definir a ”distância” (similaridade)</p><p>entre grupos de objetos, uma vez que as métricas operam em</p><p>pares de objetos, não em grupos.</p><p>?</p><p>Agrupamento hierárquico aglomerativo</p><p>Exemplo:</p><p>Como calcular a similaridade</p><p>entre os grupos</p><p>Várias alternativas:</p><p> menor distância entre</p><p>os elementos de cada</p><p>conjunto;</p><p> maior distância entre</p><p>os elementos de cada</p><p>conjunto e</p><p> distância média entre</p><p>pares de elementos</p><p>dos conjuntos.</p><p>Agrupamento hierárquico aglomerativo</p><p>Agrupamento hierárquico aglomerativo</p><p>A ordem em que os grupos são</p><p>unidos dá origem a uma estrutura</p><p>chamada dendograma.</p><p>4 grupos</p><p>2 grupos</p><p>1 grupo</p><p>Agrupamento hierárquico aglomerativo:</p><p>propriedades</p><p>1. permite interpretar visualmente como os grupos foram</p><p>gerados;</p><p>2. possibilita identificar facilmente outliers;</p><p>3. a visualização fica bastante confusa no caso de grandes</p><p>conjuntos de dados e</p><p>4. tem um custo computacional maior que o Kmeans (pode levar</p><p>algum tempo para se calcularem os grupos).</p><p>Técnicas de agrupamento</p><p>Como avaliar a qualidade de um agrupamento?</p><p>Existem diversas abordagens:</p><p> comparar os clusters obtidos com aqueles adquiridos a partir</p><p>de dados randômicos;</p><p> verificar o quão coesos os clusters obtidos são, quando</p><p>comparados a dados supervisionados (os grupos são</p><p>previamente conhecidos), e</p><p> comparar clusters obtidos a partir de diferentes técnicas e</p><p>utilizar alguma métrica de ”coesão de grupos” para identificar</p><p>que grupos são os mais coesos.</p><p>TODOS OS DIREITOS RESERVADOS.</p>