Lista 7- Agrupamentos4 11

Prévia do material em texto

2.5 
-5, 2 2 0, 2 5, 2 
1.5 
 
-5, 1 1 
 
0.5 
 
 
-4 -2 0 
-0.5 
 
-1 5, -1 
 
-1.5 
-5, -2 -2 0, -2 5, -2 
-2.5 
PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS 
Instituto de Ciências Exatas e Informática - Curso de Ciência da Computação 
Disciplina: Inteligência Artificial 
Professor: Cristiane Neri Nobre 
 
Aluno: Luam Gonçalves 
 
LISTA 7 
 
 
QUESTÃO 1 
Considere o seguinte conjunto de 8 exemplos de pares de pontos no plano real, Dado os 
exemplos indicados na tabela abaixo, caracterizados por dois atributos (pontos em R2), 
aplique o algoritmo K-means para determinar uma partição adequada desses dados em 
2 grupos. Realize a primeira execução do algoritmo, partindo dos exemplos 3 (Ex3 -> 
X=0 e Y=2) e 4 (Ex4 -> X=0 e Y = -2). Utilize a distância euclidiana para o cálculo de 
distância. 
 
Exemplo X Y 
Ex1 -5 2 
Ex2 5 -2 
Ex3 0 2 
Ex4 0 -2 
Ex5 -5 1 
Ex6 -5 -2 
Ex7 5 2 
Ex8 5 -1 
 
 
 
 
 
𝑑(𝑥,𝑦) = √(𝑥1 − 𝑦1 )2 + (𝑥2 − 𝑦2)2 
2 
+ ⋯ + (𝑥𝑝 − 𝑦𝑝) 
-6 
CENTRÓIDE EX3 CENTRÓIDE EX4 
Ponto Distância Ponto Distância 
Ex1 5 Ex1 6.40 
Ex2 6.4 Ex2 5 
Ex4 4 Ex3 4 
Ex5 5.1 Ex5 5.8 
Ex6 6.4 Ex6 5 
Ex7 5 Ex7 6.4 
Ex8 5.8 Ex8 5.1 
 
 
QUESTÃO 2 
Cite e explique o funcionamento de duas métricas para avaliação de agrupamento. 
Sillhouete Index: é uma medida de avaliação que avalia a coesão e a separação dos 
clusters, e baseia se na diferença entre a distância média dos pontos pertencentes ao 
cluster mais próximo para os pontos de um grupo. 
 
Elbow: Ele usa a soma das distâncias quadradas [SSE] entre os pontos de dados e seus 
respectivos centróides ou médias de cluster atribuídos. Em seguida, selecione o valor k na 
posição em que o SSE começa a achatar e formar um cotovelo. 
 
QUESTÃO 3 
Assista ao vídeo e analise as limitações deste algoritmo. 
https://www.youtube.com/watch?v=E2M_yTulcmU 
- O usuário deve informar o numéro de clusters (k) no inicio do algoritmo. 
- K-means é um algoritmo exclusivo para atributos numéricos. 
- K-means assume que lidamos com clusters esféricos e que cada cluster tem igualmente 
o mesmo número de observações. 
 
QUESTÃO 4 
Faça um resumo do artigo “A Comprehensive Survey Of Clustering” que está no 
CANVAS. 
A obra trata dos pontos fortes e fracos dos algoritmos de agrupamento, devido a sua comple- 
xidade de informação. Foram analisadas pelos autores diversas métricas, como distâncias ou 
similaridades d de medidas e indicadores avaliativos. O uso de distâncias ou dissimilaridade 
https://www.youtube.com/watch?v=E2M_yTulcmU
é uma métrica indicada para dados quantitativos, é uma métrica para reconhecimento de re- 
lacionamento entre dados. Por outro lado, a similaridade é uma métrica indicada para dados 
qualitativos. 
A principal proposta de indicadores avaliativos é testar a validade de um algoritmo. A avali- 
ação interna testa os dados internos de um agrupamento e a avaliação externa, considerada 
padrão ouro para método de testes, avalia os dados externos do agrupamento. 
Tradicionalmente temos nove categorias de algoritmos para clustering: 
- baseado em partição: método de agrupamento classifica as informações em vários grupos 
com base nas características e semelhanças dos dados. São os analistas de dados que devem 
especificar o número de clusters que devem ser gerados para os métodos de clustering 
- baseado em hierarquia: é um algoritmo que agrupa objetos semelhantes em grupos chamados 
clusters. O endpoint é um conjunto de clusters, onde cada cluster é distinto um do outro cluster 
e os objetos dentro de cada cluster são amplamente semelhantes entre si. 
- baseado em teoria fuzzy: forma de agrupamento em que cada ponto de dados pode pertencer 
a mais de um agrupamento. Clustering ou análise de cluster envolve a atribuição de pontos de 
dados a clusters de forma que os itens no mesmo cluster sejam tão semelhantes quanto 
possível, enquanto os itens pertencentes a clusters diferentes são tão diferentes quanto possí- 
vel. 
- baseado em distribuição: está diretamente relacionado ao uso de modelos de distribuição 
(por exemplo, Gaussiano / Normal) em estatísticas. Fundamentalmente, os clusters são defi- 
nidos com base na probabilidade de os objetos incluídos pertencerem à mesma distribuição. 
- baseado em densidade: refere-se a métodos de aprendizagem não supervisionados que iden- 
tificam grupos / clusters distintos nos dados, com base na ideia de que um cluster em um 
espaço de dados é uma região contígua de alta densidade de pontos, separada de outros clus- 
ters por regiões contíguas de baixa densidade de pontos. 
- baseado em teoria dos grafos: Na teoria dos grafos, um ramo da matemática, um gráfico de 
agrupamento é um gráfico formado a partir da união disjunta de gráficos completos. Equiva- 
lentemente, um gráfico é um gráfico de agrupamento se e somente se não tiver um caminho 
induzido por três vértices; por esse motivo, os gráficos de cluster também são chamados de 
gráficos livres de P3. 
- baseado em grade: 
um método de agrupamento hierárquico eficiente para conjuntos de dados muito grandes. ... 
O comportamento de tempo de execução do algoritmo supera todos os métodos hierárquicos 
convencionais. Uma comparação dos tempos de execução com os de outros algoritmos de 
clustering comumente usados e uma análise heurística de tempo de execução são apresenta- 
dos. 
- Baseado em teoria de fractal: Clustering é uma técnica de descoberta de conhecimento am- 
plamente usada. O novo algoritmo que chamamos de Fractal Clustering (FC) coloca pontos 
de forma incremental no cluster para o qual a mudança na dimensão fractal após adicionar o 
ponto é a menor 
 
Algoritmos modernos de clustering são dividos em dez categorias: 
-baseado em núcleo, 
-baseado em ensamble 
- baseado em enxames inteligentes, 
- baseados em teoria quântica 
- baseado em teoria grafo espectral 
- baseado em propagação de afinidade 
- baseado em afinidade e distância, 
- baseado em dado espacial 
- baseado fluxo de dados 
- baseado em dados de larga escala 
 
 
QUESTÃO 5 
5.1 , 5.2, 5.3, 5.4, 5.5 As respostas estão comentadas no código no link : 
https://drive.google.com/file/d/1puF-
i2B70AIOk0vP1LrJn9RhZNiOdNrp/view?usp=sharing