Clustering: diferenças entre revisões

 

==== A otimalidade do algoritmo ====

 

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.

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>.

 

==== Implementação e Análise da Complexidade ====