Algoritimos para Analise de Dados II

Prévia do material em texto

Inserir Título Aqui 
Inserir Título Aqui
Algoritmos para 
Análise de Dados
Algoritmos de clustering
Responsável pelo Conteúdo:
Prof. Dr. Alberto Messias
Revisão Textual:
Prof. Ms. Luciano Vieira Francisco
Nesta unidade, trabalharemos os seguintes tópicos:
• Introdução ao Tema
• Orientações para leitura Obrigatória
• Material Complementar Fonte: iStock/Getty Im
ages
Objetivos
• Compreender as definições iniciais sobre os algoritmos de clustering.
• Entender o funcionamento do algoritmo kmeans, as técnicas de validação do modelo 
criado pelo algoritmo e, por fim, um caso prático de execução do qual.
Caro Aluno(a)!
Normalmente, com a correria do dia a dia, não nos organizamos e deixamos para o 
último momento o acesso ao estudo, o que implicará o não aprofundamento no material 
trabalhado ou, ainda, a perda dos prazos para o lançamento das atividades solicitadas.
Assim, organize seus estudos de maneira que entrem na sua rotina. Por exemplo, você 
poderá escolher um dia ao longo da semana ou um determinado horário todos ou alguns 
dias e determinar como o seu “momento do estudo”.
No material de cada Unidade, há videoaulas e leituras indicadas, assim como sugestões 
de materiais complementares, elementos didáticos que ampliarão sua interpretação e 
auxiliarão o pleno entendimento dos temas abordados.
Após o contato com o conteúdo proposto, participe dos debates mediados em fóruns de 
discussão, pois estes ajudarão a verificar o quanto você absorveu do conteúdo, além de 
propiciar o contato com seus colegas e tutores, o que se apresenta como rico espaço de 
troca de ideias e aprendizagem.
Bons Estudos!
Algoritmos de clustering
UNIDADE 
Algoritmos de clustering
Introdução ao Tema
Algoritmos de Clustering
Os algoritmos de clustering são métodos de aprendizado não supervisionado, os 
quais utilizados na criação de grupos homogêneos, dado um conjunto de dados com 
base em sua estrutura interna.
Clustering é um método frequentemente usado para análise exploratória dos dados, 
onde não há estimativas de quaisquer valores ou agrupamentos, de modo que as criações 
dos grupos ocorrem apenas na semelhança entre os dados e os organizando em clusters.
A ideia de semelhanças pode ser explicada com questões sobre como fazer para:
1. Agrupar esses documentos por tópico;
2. Realizar segmentação de clientes para permitir programas de marketing dire-
cionados ou especiais.
Note que a definição de “similaridade” é específica ao domínio do problema. Assim, 
estamos definindo semelhanças entre esses pontos de dados com a mesma característica 
de “tópico” ou de clientes que podem ser perfilados para uma mesma “faixa etária/
renda/gênero” ou a um “padrão de compra”.
Se tivermos um vetor de medidas de um atributo de dados, os pontos desses dados 
agrupados em um cluster terão valores para a medição próxima uns dos outros – em 
relação aos pontos de dados agrupados em um cluster diferente. Em outras palavras, a 
distância – um inverso de semelhança – entre os pontos dentro de um cluster é sempre 
menor do que a distância entre os pontos em um cluster diferente.
Reforçando, em um cluster, acabamos em um grupo apertado – homogêneo – de pontos 
de dados que estão distantes dos pontos de dados que acabam em um cluster diferente.
Note que a escolha do tipo de medida de distância é importante para a execução 
dos algoritmos que usam medidas de similaridade, pois neste caso a principal função de 
distância utilizada é a euclidiana.
Segue um exemplo de agrupamento:
Figura 1 – Exemplo de clusters
Fonte: Theodoridis e Koutroumbas, 2008
6
7
À esquerda há dois agrupamentos que criam formas e à direita, agrupamentos com 
pontos aleatórios, neste caso usando duas dimensões, características, ou ainda atributos 
para a classificação.
Na literatura são encontrados diversos tipos de algoritmos de clustering, entre os quais:
• Métodos de partição – aos quais são criados os clusters e são agregadas as 
instâncias a cada um dos clusters, dada a execução dos algoritmos;
• Métodos de clusters hierárquicos – criam-se tuplas e se aumenta o número de 
participantes dos clusters, além de agrupar as instâncias conforme a similaridade, 
tal como se observa na Figura 2, onde um dendograma é formado pela execução 
do algoritmo, em que no eixo vertical se observa a escala de similaridade e no eixo 
horizontal, as instâncias a serem agrupadas. Note que a cada nível é ampliado o 
número de participantes do cluster, chegando ao máximo – que será o número 
total de instâncias do modelo:
Figura 2 – Dendograma gerado pelo método de clustering hierárquico
Fonte: Duda, Hart e Stork, 2000
• Métodos com base em densidade de objetos – a ideia principal é continuar o 
crescimento de um cluster à medida que sua densidade ou quantidade de objetos 
em sua vizinhança tenha uma proximidade determinada. Este método permite 
criar clusters de forma arbitrária, com regiões densas separadas entre si por 
dados dispersos, de modo que o algoritmo comumente mencionado na literatura 
é o DBSCAN:
Figura 3 – Exemplo de clusters utilizando a técnica de densidade
Fonte: Zaki e Meira, 2014
7
UNIDADE 
Algoritmos de clustering
• Métodos que utilizam estruturas de grafo – neste caso, os vértices são os objetos, 
enquanto que as suas ligações – ou arestas – são as suas similaridades, de modo que 
ao analisar a estrutura do grafo ou rede gerada é possível criar tais clusters:
Figura 4 – Exemplo de clusters usando a estrutura dos grafos
Fonte: Theodoridis e Koutroumbas, 2008
Observe que os objetos devem ser representados por seus atributos, por exemplo: 
idade, peso, sexo, cor de pele e altura, podendo ser características ou atributos que 
representarão um indivíduo.
Segue um exemplo de representação de instâncias:
P1 = {34, 71, M, Branca, 1.72}
P1 = {34, 58, F, Branca, 1.65}
O Algoritmo Kmeans
O algoritmo de clustering kmeans foi proposto inicialmente por MacQueen, em 
1967, e utiliza medidas de similaridade entre os objetos.
Deve receber como parâmetro a quantidade de grupos ou clusters nos quais se 
deseja agrupar os objetos. Assim, o algoritmo escolhe aleatoriamente N objetos que se 
tornam representantes de cada cluster, chamados de centroides. A cada iteração do 
algoritmo, os outros objetos são alocados nos clusters, ou seja, o objeto é colocado no 
cluster do centroide mais próximo. Por sua vez, a cada iteração, o algoritmo recalcula o 
centroide, usando a média das distâncias entre todos os integrantes do cluster. Segue a 
Figura que ilustra o funcionamento do algoritmo:
8
9
Figura 5 – Representação em duas dimensões de iterações do algoritmo kmeans
Fonte: Duda, Hart e Stork, 2000
A Figura representa, em duas dimensões, algumas iterações do algoritmo kmeans, 
onde inicialmente os centroides definidos aleatoriamente e a cada iteração do algoritmo 
vão convergindo e ficando mais próximos das instâncias de seu cluster. Note que os 
centroides vão mudando de lugar e suas respectivas formações/divisões entre os grupos 
também o fazem, conforme as linhas marcadas com 1, 2 e 3 vão se modificando.
Quando não ocorrerem mais variações nos posicionamentos dos centroides, significa 
que o algoritmo convergiu. A seguinte Figura ilustra o pseudocódigo do algoritmo:
Figura 6 – Pseudocódigo do algoritmo kmeans
Fonte: Dougherty, 2012
9
UNIDADE 
Algoritmos de clustering
Tal algoritmo executa da seguinte maneira:
• Escolha K, o número de clusters que se deseja classificar;
• Aleatoriamente, defina os posicionamentos de cada um dos K centroides;
• Atribua cada instância ao seu centroide mais próximo;
• Recalcule o valor de cada um dos centroides dada a média de todas as instâncias 
do cluster;
• Repita a função de atribuir instâncias e recalcular as posições dos centroides até que 
não ocorram mais variações no posicionamentodesses.
Note que o algoritmo kmeans é relativamente simples, de modo que seu tempo 
de execução dependerá da quantidade de K, da escolha dos valores iniciais para os 
centroides e do critério de parada, podendo ser o número máximo de iterações ou, 
caso se tenha como fato, cessará a execução do algoritmo apenas após a paralização 
completa das posições dos centroides.
Segue mais um exemplo ilustrado do passo a passo que ocorre com a execução do 
algoritmo para uma condição hipotética com k = 3:
Figura 7 – Passo 1
No passo 1 observa-se a escolha inicial dos centroides.
10
11
Figura 8 – Passo 2
No passo 2 observa-se que o algoritmo calcula a distância de cada instância para os 
centroides e atribui dada instância a um cluster específico.
Figura 9 – Passo 3
Neste passo 3, ao se atribuírem as instâncias a cada um dos grupos, a posição de 
cada centroide deve ser revisada, usando a média da posição de cada instância existente 
em seu cluster.
11
UNIDADE 
Algoritmos de clustering
Figura 10
As repetições dos passos 2 e 3 ocorrem até que os centroides fiquem estáveis ou que 
as suas variações sejam extremamente pequenas e aceitáveis.
A saída do algoritmo deverá corresponder aos respectivos valores dos centroides e às 
instâncias utilizadas no modelo e classificadas em seus respectivos clusters.
Existem diversas ferramentas que implementam o algoritmo kmeans, por exemplo: 
o software Weka; a plataforma Mahout, que pode ser instalada sobre o Hadoop; a 
plataforma Spark, que também é executada sobre o Hadoop; o software R, bastante 
utilizado em análise de big data; entre outros softwares para análise de dados, de modo 
que algumas dessas ferramentas serão elencadas nas leituras obrigatórias ou materiais 
complementares.
Validação de Clusters
Outro aspecto importante em análise e reconhecimento de padrões é a validação dos 
modelos propostos pelos algoritmos.
Na análise de clustering é sempre importante conhecer o domínio de aplicação para 
que se possa fazer a análise do modelo criado e utilizar técnicas de validação – embora 
não sejam técnicas simples para a implementação algorítmica.
Dada a grande variedade de algoritmos de clustering, observa-se também considerável 
diversidade de técnicas de validação que levam em consideração medidas internas aos 
clusters e externas, considerando o modelo completo (ZAKI; MEIRA, 2014):
• Medidas externas – utilizam critérios que não são inerentes ao conjunto de dados, 
mas sim ao domínio de aplicação. Isso pode se dar na forma de conhecimento prévio 
ou especializado sobre os clusters, por exemplo: as instâncias foram previamente 
etiquetadas, com informações oriundas de conhecimento de especialistas e se faz 
uma validação a partir dos erros e acertos do algoritmo, sem levar em consideração 
12
13
medidas específicas. Para esse tipo de técnica, pode-se usar as medidas chamadas 
de F-measure, que mensurarão a precisão do algoritmo como um todo, técnica 
comumente utilizada para validação de classificadores ou detecção de outliers;
• Medidas internas – empregam critérios que são derivados dos dados em si, por 
exemplo: podemos usar distâncias intracluster e intercluster para obter medidas 
de coesão do cluster – por exemplo, quão semelhantes são os pontos no mesmo 
cluster? – e de separação – por exemplo, quão distantes estão os pontos em 
diferentes clusters?
Observe que a validação de um modelo de cluster, na verdade, corresponde à 
avaliação se a quantidade de clusters ou grupos gerados for adequada ao conjunto de 
dados utilizados para a geração do modelo. 
Agora nos concentraremos em duas medidas internas de validação de clusters, a 
medida interna que utiliza a soma dos erros quadrados e o coeficiente de silhueta.
Medida de Soma dos Erros Quadrados
A medida de soma dos erros quadrados mostrará o valor da soma total das 
distâncias entre cada instância e seus respectivos centroides, utilizando, neste 
caso, a distância euclidiana como medida. Caso esse valor seja muito alto, 
significa que o cluster em si não é coeso e possivelmente poderá ser separado; 
mas se esse valor é muito baixo, significa que o cluster está muito especializado, 
ou seja, poderá se juntar ao outro.
Segue a especificação da equação para a soma dos erros quadrados, utilizando a 
distância euclidiana, esta que é dada por:
d p pik jk
k
n
= −
=
∑( )2
1
O SSE, ou a soma dos erros quadrados será a soma da distância euclidiana ao 
quadrado de cada instância do cluster para o seu centroide, dada por:
SSE C d x cii
i
n
( )) ( , )=∑ 2
Ou seja, calculando apenas a coesão de um dado cluster; mas pode-se também 
calcular o erro quadrado do modelo completo – neste caso, tal valor é dado pelo 
somatório do SSE de cada cluster:
SSE SSE Ci
i
k
=∑ ( )
Para validar o modelo proposto é importante executar tal validação para inúmeros 
valores de K. Trata-se de executar o algoritmo iniciando com K igual a 1 e aumentando 
gradativamente para cada execução do algoritmo, a fim de calcular o SSE total e plotar 
13
UNIDADE 
Algoritmos de clustering
em um gráfico. Desse modo, a minimização de tal soma de erro quadrado ilustrará 
graficamente a qualidade do modelo gerado. Nesse sentido, segue um gráfico que ilustra 
um modelo hipotético:
Figura 11 – Decaimento de ESS para a validação do modelo proposto
Fonte: Souza, 2015
O ponto ideal do número de cluster será no chamado “joelho da curva”. No gráfico 
ilustrado pela Figura 11, observa-se o valor de K = 5. Note que com k = 1, o modelo 
possui um erro muito grande; enquanto que para K = 20, o modelo fica extremamente 
especializado, neste caso, com K tendendo ao número de instância e o erro quadrado 
tendendo a 0. Assim, o meio termo é um número ideal de clusters para tal modelo.
Medida do Coeficiente de Silhueta
O coeficiente de silhueta é uma medida de coesão e separação de clusters. É 
baseado na diferença entre a distância média de um ponto aos pontos de seu cluster 
e a distância média de um objeto a todos os objetos do cluster mais próximo.
Inicialmente, deve-se calcular o coeficiente de silhueta para cada objeto i. Para isso, 
deve-se calcular a distância média de um objeto i para todos os objetos de seu cluster, 
dado por:
s i b ai i( ) = −
max(a , b )i i
Onde ai é a distância média do objeto i em relação a todos os outros objetos 
do seu cluster, enquanto bi é a distância média do objeto i em relação a todos os 
outros objetos do cluster vizinho mais próximo.
14
15
O próximo passo é calcular o coeficiente de silhueta para todo o modelo. Assim, a 
média s(i) para todos os objetos i presentes nos dados é fornecida por:
SWC
N
s i
i
N
=
−
∑1
0
( )
Para validar o modelo proposto é importante executar essa validação para inúmeros 
valores de K. Trata-se de executar o algoritmo iniciando com K igual a 1 e aumentar 
gradativamente para cada execução do algoritmo, a fim de calcular o SWC e plotar em 
um gráfico. Tipicamente, o SWC será um valor entre -1 e 1, sendo que o modelo com 
K que melhor agrupa o conjunto de dados será aquele que possuir valor mais próximo 
de 1. Segue um gráfico que ilustra um modelo hipotético:
Figura 12 – Valores do coeficiente de silhueta pela quantidade de clusters
 Fonte: Souza, 2015
O ponto ideal de quantidade de clusters para o exemplo notadamente é o valor de 5 
grupos, conforme se observa no gráfico, sendo o valor mais próximo de 1.
Caso Prático de Execução do Algoritmo Kmeans
Utilizaremos o software Weka para fazer um experimento com a execução do 
algoritmo kmeans. Tal experimento será com uma base de dados Iris Flower Dataset, 
comumente utilizada para ilustrar o funcionamento do algoritmo relacionado ao 
reconhecimento de padrões.
Trata-se de um software livre e muito comum para o processamento de bases de dados 
e validações experimentais,com a possibilidade de importar arquivos, fazer conexões 
diretas com bancos de dados, ou ainda gerar dados aleatórios para experimentos.
15
UNIDADE 
Algoritmos de clustering
Figura 13 – Tela do Weka ao se carregar o arquivo da base de dados
Fonte: Weka
Na tela é possível observar os valores mínimos, máximos, a média e o desvio padrão, 
além da quantidade de instâncias na base e os atributos existentes.
Cada aba do software possui um conjunto de algoritmos com a mesma finalidade, 
como algoritmos de classificação, cluster, regras de associação, seleção de atributos e 
visualização dos dados e resultados.
A Figura 14 ilustra a aba de algoritmos de clustering, neste caso, ao clicar no botão 
choose pode-se escolher o algoritmo desejado:
Figura 14
Fonte: Weka
16
17
Neste caso, o algoritmo selecionado é o SimpleKMeans, em sua implementação 
principal. A Figura 15 apresenta os parâmetros possíveis para o algoritmo kmeans:
Figura 15
Fonte: Weka
Na tela exibida na Figura 16, pode-se observar a escolha da métrica de distância – 
euclidiana –, além de outros parâmetros como, por exemplo, a quantia de clusters K e 
a quantidade máxima de iterações do algoritmo:
Figura 16
Fonte: Weka
17
UNIDADE 
Algoritmos de clustering
=== Run information ===
Scheme: weka.clusterers.SimpleKMeans -init 0 -max-candidates 
100 -periodic-pruning 10000 -min-density 2.0 -t1 -1.25 -t2 -1.0 -N 
3 -A “weka.core.EuclideanDistance -R first-last” -I 500 -num-slots 
1 -S 10
Relation: iris
Instances: 150
Attributes: 5
 sepallength
 sepalwidth
 petallength
 petalwidth
 class
Test mode: evaluate on training data
=== Clustering model (full training set) ===
kMeans
======
Number of iterations: 3
Within cluster sum of squared errors: 7.817456892309574
Initial starting points (random):
Cluster 0: 6.1,2.9,4.7,1.4,Iris-versicolor
Cluster 1: 6.2,2.9,4.3,1.3,Iris-versicolor
Cluster 2: 6.9,3.1,5.1,2.3,Iris-virginica
Missing values globally replaced with mean/mode
Final cluster centroids:
 Cluster#
Attribute Full Data 0 1 2
 (150.0) (50.0) (50.0) (50.0)
A listagem exibe a saída do algoritmo na tela principal de execução dos algoritmos 
no Weka:
18
19
===========================================================
sepallength 5.8433 5.936 5.006 6.588
sepalwidth 3.054 2.77 3.418 2.974
petallength 3.7587 4.26 1.464 5.552
petalwidth 1.1987 1.326 0.244 2.026
class Iris-setosa Iris-versicolor Iris-setosa Iris-
virginica
Time taken to build model (full training data) : 0 seconds
=== Model and evaluation on training set ===
Clustered Instances
0 50 ( 33%)
1 50 ( 33%)
2 50 ( 33%)
Observe, na saída do algoritmo, os pontos principais e respectivos como:
• Os parâmetros passados na execução do algoritmo;
• A quantidade de instâncias da base de dados;
• Os atributos presentes na base;
• O número de iterações do algoritmo;
• O valor de erro quadrado do modelo gerado;
• Os centroides gerados pelo algoritmo;
• Uma tabela com as informações sobre as instâncias classificadas em cada cluster; e
• A quantidade de instâncias em cada cluster.
A Figura 17 ilustra o resultado das instâncias separadas em clusters, ao clicar 
com o botão direito do mouse sobre o experimento e ir na opção visualizar o 
modelo gerado, conforme se vê a seguir:
19
UNIDADE 
Algoritmos de clustering
 
Figura 17
Fonte: Weka
Então, clique para exibir o modelo de clusters gerado. Note que as instâncias classifi-
cadas em seus respectivos grupos estão com cores que identificam o cluster específico.
Figura 18 – Modelo de clusters gerado e as instâncias classifi cadas
Fonte: Weka
Dado que na saída do algoritmo é exibido o erro quadrado do modelo, é possível, 
então, validá-lo ao executar o algoritmo variando o número de clusters.
Para o experimento de verificação da minimização dos erros quadrados para a 
validação do modelo, o algoritmo foi executado treze vezes, variando o K entre 1 e 10 
e, logo após, com 50, 100 e 146 clusters, conforme se vê na Tabela extraída com as 
somas dos erros quadrados:
Tabela 1
Clusters Erro quadrado
1 141,1381720229770
2 62,1436882815797
20
21
3 7,8174568923096
4 6,6138232746904
5 6,2935568618108
6 6,1318396310806
7 5,2024143888778
8 4,8527343852958
9 4,6720734767839
10 4,6239733170433
50 0,6325772361931
100 0,1908186705859
146 1.0030885127016854E-34
Fonte: elaborada pelo professor conteudista.
Observe que inicialmente a soma dos erros quadrados para um único cluster traz 
um valor bastante alto e ao se aumentar o número de clusters, tal modelo vai se 
especializando, de modo que esse erro é minimizado. Note também que ao se aproximar 
do número total de instância, o erro tende a zero, porém, o modelo fica extremamente 
especializado – o que não é um bom resultado.
A Figura 19 ilustra graficamente o decaimento da soma dos erros quadrados:
Figura 19
Fonte: elaborada pelo professor conteudista.
Conforme informado, a quantidade ideal de clusters para dado modelo ocorre 
quando há um “joelho no gráfico”. Assim, note que o valor ideal de clusters para a base 
usada é de três. O erro inicialmente é bastante alto, mas quando se chega ao número 
ideal, cai bruscamente e, logo após, a redução do erro é pequena, sendo que no final 
tende a zero, conforme se observa na execução do algoritmo com 146 clusters, sendo 
que a base total possui 150 instâncias.
O software Weka será interessante para se fazer a modelagem inicial dos conjuntos e 
tipos de dados a se trabalhar, antes de se implementar o modelo usando tecnologias de 
big data como, por exemplo, Hadoop ou Spark.
Vale destacar ainda que o software Weka possui uma Application Programming 
Interface (API) em linguagem de programação java, permitindo o uso de suas 
implementações algorítmicas em seus projetos java, de modo a permitir uma integração 
mais profunda em seus projetos de business intelligence ou mineração de dados.
21
UNIDADE 
Algoritmos de clustering
Orientações para leitura Obrigatória
Segue a indicação de leitura obrigatória de uma apresentação existente no site de 
documentação do software Weka, disponível em: https://goo.gl/1iwuvs 
Dá uma visão importante sobre as possibilidades existentes nesse software.
Leia também o capítulo 13 do livro Data mining and analysis: fundamental concepts and 
algorithms, disponível em: https://goo.gl/ytF97R 
Discorre sobre algoritmos de clustering, englobando o algoritmo kmeans.
Finalmente, segue também a indicação de leitura do capítulo 17 do mesmo livro, Data mining 
and analysis: fundamental concepts and algorithms, disponível em: https://goo.gl/ytF97R.
Agora sobre algoritmos de clustering e acerca dos métodos de validação dos modelos 
de clustering.
22
23
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Sites
UCI
Segue a indicação do site de repositórios de bases de dados livres para experimentos.
https://goo.gl/c8s2kg
 Leitura
The Weka Workbench
Assim como a introdução ao Weka, no site desse software.
https://goo.gl/xD7W7i
Clustering de Dados Biomédicos com Algoritmos baseados em Critérios Entrópicos
Mais a dissertação de Mestrado que aborda o tema da aplicação do algoritmo de clustering 
em dados biomédicos
https://goo.gl/Tssvno
Introduction to K-means Clustering
Artigo sobre o algoritmo kmeans
https://goo.gl/MM9tBV
23
UNIDADE 
Algoritmos de clustering
Referências
DOUGHERTY, G. Pattern Recognition and Classification: An Introduction. 2013. 
ed. [S.l.]: Springer, 2012.
DUDA, R. O.; HART, P. E.; STORK, D. G. Pattern classification. 2nd ed. [S.l.]: 
Wiley-Interscience, 2000.
SOUZA, A. M. da C. Uma nova arquitetura para internet das coisas com análise e 
reconhecimento de padrões e processamento com big data. 2015. Tese (Doutorado 
em SistemasEletrônicos) - Escola Politécnica da Universidade de São Paulo, São 
Paulo, 2015. Disponível em: <http://www.teses.usp.br/teses/disponiveis/3/3142/
tde-20062016-105809>. Acesso em: 7 mar. 2017.
THEODORIDIS, S.; KOUTROUMBAS, K. Pattern recognition 4th ed. [S.l.]: 
Academic Press, 2008.
ZAKI, M. J.; MEIRA JR. W. Data mining and analysis: fundamental concepts and 
algorithms. New York: Cambridge University, 2014. Disponível em: <http://www.
dataminingbook.info/pmwiki.php/Main/BookPathUploads?action=downloadman&u
pname=book-20160121.pdf>. Acesso em: 7 mar. 2017.
24