Clustering: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 60:
Tome <math>C</math> o conjunto de clusters <math>C_{1},C_{2},...,C_{k}</math> que particiona um grafo conexo <math>U</math>. O espaçamento <math>d^*</math> de <math>C</math> é o comprimento da (k-1)-ésima aresta mais custosa da minimum spanning tree, que é a última aresta deletada pelo algoritmo de clustering.
Para confirmarmos essa afirmação, precisamos provar que o
Seja <math>C'</math> um outro conjunto de k clusters que também particiona o grafo <math>U</math> em conjuntos não vazios <math>C_{1}',C_{2}',...,C_{k}'</math> .Como <math>C</math> e <math>C'</math> são diferentes, existe, necessariamente, um cluster <math>C_{r}</math> que não é subconjunto de nenhum <math>C_{s}'</math> pertencente a <math>C'</math>. Logo, existem pontos <math>p_{i}</math> e <math>p_{j}</math> em <math>Cr</math> que pertencem a clusters diferentes em <math>C'</math> - digamos pi pertencente a <math>C_{s}'</math> e <math>p_{j}</math> pertencente a <math>C_{t}'</math> diferente de <math>C_{s}'</math>.
Dado que <math>p_{i}</math> e <math>p_{j}</math> pertencem a um mesmo cluster, nenhuma das arestas do caminho <math>P</math> entre eles foi deletado pelo algoritmo. Ou seja, cada aresta pertencente a <math>P</math> tem comprimento menor ou igual a <math>d^*</math>. Por outro lado, sabemos que pi pertence a <math>C_{s}'</math>, mas <math>p_{j}</math> não; logo, tomemos <math>p'</math> como o primeiro nó em <math>P</math> que não pertence a <math>C_{s}'</math> e <math>p</math> o nó que vem logo antes de <math>p'</math> no caminho <math>P</math>. Sabemos que <math>d(p,p') \leq d^*</math> em <math>C'</math> e isso completa a prova, pois o <math>d \leq d(p,p')</math>, sendo <math>d</math> o espaçamento de <math>C'</math>.
Linha 66:
==== Implementação e Análise da Complexidade ====
Implementar este algoritmo consiste em descobrir uma maneira eficiente de encontrar a aresta menos custosa dentro de um subconjunto de arestas do grafo original - para construir a minimum spanning tree - e a mais custosa - para deletá-la na segunda etapa do algoritmo. Tais operações são facilmente realizadas com o uso de uma fila de prioridades que pode ser mantida com complexidade <math>O(logm)</math>, onde m é o número de elementos na fila.
A complexidade de montar a minimum spanning tree é <math>O(nlogm)</math>, onde <math>n</math> é o número de nós no grafo e <math>m</math> o número de arestas. Já a complexidade de deletar k-1 arestas é <math>O((k-1)log(n-1))</math>. Logo, o tempo de execução é dominado pela construção da minimum spanning tree. Conclui-se, então, que encontrar k clusters em um grafo <math>U</math> com <math>n</math> nós e
<big>
| |||