Please enable JavaScript.
Coggle requires JavaScript to display documents.
Clusterização / Clustering (Abstração e Algoritmo (ALGORITMO (ÁRVORE…
Clusterização / Clustering
Clusterização
Técnica de aprendizado não-supervisionado.
Clustering
Dado um conjunto de objetos, colocar os objetos em grupos baseados na similaridade entre eles.
Objetos similares no mesmo conjunto.
Problema fundamental: muitas aplicações
EXEMPLOS: agrupamento de fotografias, espécies, páginas, comunidades em redes sociais, etc.
Aprendizado não supervisionado
Medindo Similaridade
Função de distância depende do domínio
K: número de conjuntos a serem produzidos. Existem muitas maneiras de agrupar n objetos em k conjuntos.
Espaçamento
menor distância entre quaisquer objetos de grupos diferentes.
Melhor agrupamento é aquele que tem maior espaçamento
Objetivo: produzir um agrupamento ótimo (maximizar o espaçamento)
Abstração e Algoritmo
Abstração via grafos
Vértices: objetos
Pesos nas arestas: distância entre objetos
Guloso: agrupar objetos mais próximos primeiro
Grupos são as componentes conexas
ALGORITMO
Começar com grafo totalmente desconexo
Adicionar arestas em ordem crescente de peso (mais próximo primeiro)
Parar quando tiver exatamente k componentes conexos
Cada aresta: ou uni dois compenentes conexos; ou add aresta dentro de um componente conexo
ÁRVORE GERADORA MÍNIMA
krustal
Obter a AGM e remover as k-1 mais pesadas
Para gerar os clusters basta eliminar (k-1) das arestas mais pesadas.
GRAFOS ESPARSOS (K-NN)
Grafo dos k-vizinhos mais próximos, ou grafo KNN.
Cada vértice corresponde à um objeto e é ligado aos seus k-vizinhos mais similares.
O peso da aresta representa a similaridade entre os dois objetos que a mesma conecta.
Shared Nearst neighbor Simlarity (SNN)
Se 2 pontos são similares a muitos dos mesmos pontos, então eles são similares uns aos outros, mesmo que uma medida direta de similaridade não indique isso.
Jarvis-Patrick
Utiliza o conceito de similaridade SNN ao invés da similaridade direta.
Construa o grafo de similaridade SNN
Remova do grafo todas as arestas que possuem peso menor do que um threshold T especificado pelo usuário.
Encontre os componentes conexos (clusters) do grafo obtido ao final da etapa 2.