Clustering

Quando se tem um conjunto de objetos é natural olhar para eles tentando perceber o quão semelhantes ou diferentes eles são uns dos outros. Uma abordagem comum consiste em definir uma função de distância entre os objetos, com a interpretação de que objetos a uma distância menor são mais semelhantes uns aos outros. Assim, a distância assume um significado mais abstrato. Por exemplo, podemos definir a distância entre pessoas como a diferença do ano em que nasceram. O clustering, que traduz-se em agrupamento, surge quando tentamos classificar ou organizar objetos em grupos coerentes. Dada uma função de distância, o problema pretende dividi-los em grupos para que, intuitivamente, objetos dentro do mesmo grupo estejam "próximos", e em diferentes grupos, "distantes".

Suponha que temos um conjunto ${\displaystyle U}$  de n objetos ${\displaystyle p_{1},p_{2},...,p_{n}}$ . Para cada par, ${\displaystyle p_{i}}$ e ${\displaystyle p_{j}}$ , temos uma distância d numérica ${\displaystyle (p_{i},p_{j})}$ . Exigimos apenas que ${\displaystyle d(p_{i},p_{j})=0}$  para todo ${\displaystyle i}$ =j; que ${\displaystyle d(p_{i},p_{j})>0}$  para ${\displaystyle i}$  e ${\displaystyle j}$  distintos; e que as distâncias sejam simétricas, ou seja, que ${\displaystyle d(p_{i},p_{j})=d(p_{j},p_{i})}$ . Suponha que queremos dividir os objetos de ${\displaystyle U}$  em k grupos, para um determinado parâmetro k. Denominamos por k-grupo de ${\displaystyle U}$  cada elemento duma qualquer partição de ${\displaystyle U}$  em k conjuntos não vazios ${\displaystyle C_{1},C_{2},...,C_{k}}$ . Definimos ainda o espaçamento de um k-grupo, como sendo a distância mínima entre qualquer ponto pertencente a esse k-grupo e qualquer ponto situado num k-grupo diferente. Sendo o objetivo do agrupamento de dados a criação de grupos bem distintos entre si, e portanto com elevadas distâncias entre pontos pertencentes a grupos diferentes, um objetivo natural é buscar k-grupos com o máximo espaçamento possível. Entretanto, há muitos k-grupos diferentes num conjunto ${\displaystyle U}$ . O problema agora se resume em encontrar de forma eficiente a partição de ${\displaystyle U}$  que nos conduza ao espaçamento máximo.

Para a argumentação do funcionamento do algoritmo, necessita-se do conceito de árvore de extensão mínima, também conhecida por minimum spanning tree.

O problema da árvore de extensão mínima se resume, basicamente, em buscar a forma mais barata de conectar todos os nós de um grafo, uma vez que podemos usar apenas um subconjunto de suas arestas para conectá-los. Isto pode ser útil na construção de uma rede elétrica, na construção do núcleo de uma rede rodoviária ou ferroviária, no estabelecimento de um circuito, ou mesmo na realização de algumas formas de agrupamento.^[1]

Existem diversos algoritmos para encontrar uma árvore de extensão mínima. Aqui, vamos mostrar um algoritmo guloso, o algoritmo de Prim.

Tomamos um nó no grafo como inicial e todas as arestas que o tem como extremidade como arestas viáveis. Adicionamos ao novo grafo a aresta viável de menor custo e, consequentemente, o nó recém descoberto de sua outra extremidade. Assim, o conjunto de arestas viáveis passa ser todas as arestas que tem como extremidade ao menos um dos nós já descobertos. Seguimos adicionando as arestas de menor custo desde que um dos nós de suas extremidades ainda não esteja descoberto. Não entraremos no mérito de demonstrar que o algoritmo de Prim de fato funciona e é eficiente, entretanto daremos a intuição. A cada passo do algoritmo, encontramos uma árvore de extensão mínima para um subgrafo contido no grafo original. Digamos que o algoritmo é executado a partir de um nó inicial v, construindo assim um novo grafo. Sendo (v,u) a aresta de menor custo que liga v a um de seus vizinhos, digamos u, adicionaremos ela ao novo grafo e, consequentemente, teremos uma árvore de extensão mínima para o subgrafo formado pelos nós u e v. Repetindo esse processo, teremos uma árvore de extensão mínima para um dado grafo ao termos adicionado todos os seus nós ao novo grafo.

Agora temos o conhecimento necessário para compreender o algoritmo de encontrar k grupos de máximo espaçamento de um determinado grafo conexo.

Ao deletarmos uma aresta de uma árvore, criamos dois componentes conexos que também são árvores, tal fato é usado fortemente neste algoritmo. Encontrar k grupos consiste em deletar arestas de um grafo até obtermos k componentes conexos. No problema que estamos tratando, desejamos, além de encontrar k componentes conexos, que estes componentes sejam o mais distantes possível entre si. Definiremos o espaçamento de um conjunto de grupos de um grafo como a menor distância entre dois nós que pertencem a componentes conexos distintos. Provaremos agora, que ao deletar as k-1 maiores arestas de uma árvore de extensão mínima de um grafo conexo U, obteremos k grupos e o espaçamento entre eles será máximo.^[2]

Tome ${\displaystyle C}$  o conjunto de grupos (ou clusters) ${\displaystyle C_{1},C_{2},...,C_{k}}$  que particiona um grafo conexo ${\displaystyle U}$ . O espaçamento ${\displaystyle d^{*}}$  de ${\displaystyle C}$  é o comprimento da (k-1)-ésima aresta mais custosa da árvore de extensão mínima, que é a última aresta deletada pelo algoritmo de agrupamento. Para confirmarmos essa afirmação, precisamos provar que o espaçamento de qualquer outro conjunto de k grupos é, no máximo, d*. Seja ${\displaystyle C'}$  um outro conjunto de k grupos que também particiona o grafo ${\displaystyle U}$  em conjuntos não vazios ${\displaystyle C_{1}',C_{2}',...,C_{k}'}$  .Como ${\displaystyle C}$  e ${\displaystyle C'}$  são diferentes, existe, necessariamente, um grupo ${\displaystyle C_{r}}$  que não é subconjunto de nenhum ${\displaystyle C_{s}'}$  pertencente a ${\displaystyle C'}$ . Logo, existem pontos ${\displaystyle p_{i}}$  e ${\displaystyle p_{j}}$  em ${\displaystyle Cr}$  que pertencem a grupos diferentes em ${\displaystyle C'}$  - digamos ${\displaystyle p_{i}}$ pertencente a ${\displaystyle C_{s}'}$  e ${\displaystyle p_{j}}$  pertencente a ${\displaystyle C_{t}'}$  diferente de ${\displaystyle C_{s}'}$ . Dado que ${\displaystyle p_{i}}$ e ${\displaystyle p_{j}}$ pertencem a um mesmo grupo, nenhuma das arestas do caminho ${\displaystyle P}$  entre eles foi deletado pelo algoritmo. Ou seja, cada aresta pertencente a ${\displaystyle P}$  tem comprimento menor ou igual a ${\displaystyle d^{*}}$ . Por outro lado, sabemos que ${\displaystyle p_{i}}$ pertence a ${\displaystyle C_{s}'}$ , mas ${\displaystyle p_{j}}$  não; logo, tomemos ${\displaystyle p'}$  como o primeiro nó em ${\displaystyle P}$  que não pertence a ${\displaystyle C_{s}'}$  e ${\displaystyle p}$  o nó que vem logo antes de ${\displaystyle p'}$  no caminho ${\displaystyle P}$ . Sabemos que ${\displaystyle d(p,p')\leq d^{*}}$  em ${\displaystyle C'}$  e isso completa a prova, pois o ${\displaystyle d\leq d(p,p')}$ , sendo ${\displaystyle d}$  o espaçamento de ${\displaystyle C'}$ .

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 árvore de extensão mínima - 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 ${\displaystyle O(logm)}$ , onde m é o número de elementos na fila. A complexidade de montar a árvore de extensão mínima é ${\displaystyle O(nlogm)}$ , onde ${\displaystyle n}$  é o número de nós no grafo e ${\displaystyle m}$  o número de arestas. Já a complexidade de deletar k-1 arestas é ${\displaystyle O((k-1)log(n-1))}$ . Logo, o tempo de execução é dominado pela construção da árvore de extensão mínima. Conclui-se, então, que encontrar k grupos em um grafo ${\displaystyle U}$  com ${\displaystyle n}$  nós e ${\displaystyle m}$ arestas é uma tarefa que possuí tempo de execução ${\displaystyle O(nlogm)}$ .

(require data/heap)

(define (neib g node)
  (dict-ref g node))

(define (nodes g)
  (map (lambda (x) (car x)) g))

(struct edge (name val))

(define (edge<-list lst)
  (edge (cdr lst) (car lst)))

(define (list<-edge edg)
  (cons (edge-val edg) (edge-name edg)))

(define (edge<=? x y)
    (<= (edge-val x) (edge-val y)))

(define (edge>=? x y)
    (>= (edge-val x) (edge-val y)))

(define (minimum-spanning-tree g x)
  (let ([v-checked (make-vector (length g) 0)]
        [res empty]
        [binary-tree (make-heap edge<=?)])
    (vector-set! v-checked (- x 1) 1)
    (heap-add-all! binary-tree (map (lambda (y) (edge<-list y)) (neib g x)))
    (let loop ()
      (let ([u (heap-min binary-tree)])
        (heap-remove-min! binary-tree)
        (when (or (equal? (vector-ref v-checked (- (car (edge-name u)) 1)) 0)
                  (equal? (vector-ref v-checked (- (cdr (edge-name u)) 1)) 0))
          (set! res (cons (list<-edge u) res))
          (if (equal? (vector-ref v-checked (- (car (edge-name u)) 1)) 0)
              (and (vector-set! v-checked (- (car (edge-name u)) 1) 1)
                   (heap-add-all! binary-tree (map (lambda (y) (edge<-list y)) (neib g (car (edge-name u))))))
              (and (vector-set! v-checked (- (cdr (edge-name u)) 1) 1)
                   (heap-add-all! binary-tree (map (lambda (y) (edge<-list y)) (neib g (cdr (edge-name u)))))))))
      (when (not (equal? (heap-count binary-tree) 0))
        (loop)))
    (reverse res)))

(define (k-cluster g k)
  (let ([binary-tree (make-heap edge>=?)]
        [count (- k 1)]
        [mstree (minimum-spanning-tree g 1)])
    (heap-add-all! binary-tree (map edge<-list mstree))
    (let loop()
      (heap-remove-min! binary-tree)
      (set! count (- count 1))
      (when (not (equal? count 0))
        (loop)))
      (map list<-edge (vector->list (heap->vector binary-tree)))))

;Exemplo de grafo
(define grafo  '(1 . ((7 . (1 . 2)) (1 . (1 . 4)) (2 . (1 . 5)) (2 . (1 . 7)) (5 . (1 . 8))))
		(2 . ((7 . (1 . 2)) (1 . (2 . 6)) (6 . (2 . 8)) (5 . (2 . 9))))
		(3 . ((1 . (3 . 4)) (2 . (3 . 5)) (2 . (3 . 7))))
		(4 . ((1 . (1 . 4)) (1 . (3 . 4)) (1 . (4 . 5)) (1 . (4 . 7))))
		(5 . ((2 . (1 . 5)) (2 . (3 . 5)) (1 . (4 . 5)) (5 . (5 . 9))))
		(6 . ((1 . (2 . 6)) (8 . (6 . 7))))
		(7 . ((2 . (1 . 7)) (2 . (3 . 7)) (1 . (4 . 7)) (8 . (6 . 7))))
		(8 . ((5 . (1 . 8)) (6 . (2 . 8)) (2 . (8 . 9))))
		(9 . ((5 . (2 . 9)) (5 . (5 . 9)) (2 . (8 . 9))))))