Clustering

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes. (desde fevereiro de 2014). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

Clustering é uma técnica de Data Mining para fazer agrupamentos automáticos de dados segundo seu grau de semelhança. O critério de semelhança faz parte da definição do problema e, dependendo, do algoritmo.

O procedimento de Clustering também pode ser aplicado a bases de texto utilizando algoritmos de Text Mining, onde o algoritmo procura agrupar textos que falem sobre o mesmo assunto e separar textos de conteúdo diferentes.

Normalmente o usuário do sistema deve escolher a priori o número de grupos a serem detectados. Alguns algorítmos mais sofisticados pedem apenas o número mínimo, outros tem a capacidade de subdividir um grupo em dois.

Os tipos de algoritmos de agrupamento de dados mais comuns são os: Particionais e os Hierárquicos.

Função Distância[editar | editar código-fonte]

Clustersgeometricos.jpg

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 dividí-los em grupos para que, intuitivamente, objetos dentro do mesmo grupo estejam "próximos", e em diferentes grupos, "distantes".

Clustering de máximo espaçamento[editar | editar código-fonte]

Suponha que temos um conjunto U de n objetos p_{1}, p_{2},  ..., p_{n}. Para cada par, pi e pj, temos uma distância d numérica (p_{i}, p_{j}). Exigimos apenas que d(p_{i}, p_{j}) = 0 para todo i; que d(p_{i}, p_{j}) > 0 para i e j distintos; e que as distâncias sejam simétricas, ou seja, que d(p_{i}, p_{j}) = d(p_{i}, p_{j}). Suponha que queremos dividir os objetos de U em k grupos, para um determinado parâmetro k. Dizemos que um k-clustering de U é uma partição de U em k conjuntos não vazios C_{1}, C_{2},  ..., C_{k}. Definimos o espaçamento de um k-clustering para ser a distância mínima entre qualquer par de pontos situados em diferentes clusters. Dado que queremos pontos em diferentes clusters para serem distantes um do outro, um objetivo natural é buscar o k-clustering com o máximo espaçamento possível. Entretanto, há muitos k-clusterings diferentes de um conjunto U. O problema agora se resume em encontrar de forma eficiente o que tem espaçamento máximo.

Algoritmo do Clustering[editar | editar código-fonte]

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

Minimum-Spanning-Tree[editar | editar código-fonte]
Minimum spannig tree.jpg

O problema da minimum spanning tree 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 minimum spanning tree. Aqui, vamos mostrar um algoritmo guloso, o algoritmo de Prim.

Algoritmo de Prim[editar | editar código-fonte]
Primsdem.jpg

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 minimum spanning tree 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 minimum spanning tree para o subgrafo formado pelos nós u e v. Repetindo esse processo teremos uma minimum spanning tree para um dado grafo ao termos adicionado todos os seus nós ao novo grafo.

Descrição do algoritmo[editar | editar código-fonte]
Clustezinho.jpg

Agora temos o conhecimento necessário para compreender o algoritmo de encontrar k clusters 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 clusters 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 clusters 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 minimum spanning tree de um grafo conexo U, obteremos k clusters e o espaçamento entre eles será máximo.[2]

A otimalidade do algoritmo[editar | editar código-fonte]

Otimalidadedoalgoritmo.jpeg

Tome C o conjunto de clusters C_{1},C_{2},...,C_{k} que particiona um grafo conexo U. O espaçamento d^* de C é 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 esmpaçamento de qualquer outro conjunto de k clusters é, no máximo, d*. Seja C' um outro conjunto de k clusters que também particiona o grafo U em conjuntos não vazios C_{1}',C_{2}',...,C_{k}' .Como C e C' são diferentes, existe, necessariamente, um cluster C_{r} que não é subconjunto de nenhum C_{s}' pertencente a C'. Logo, existem pontos p_{i} e p_{j} em Cr que pertencem a clusters diferentes em C' - digamos pi pertencente a C_{s}' e p_{j} pertencente a C_{t}' diferente de C_{s}'. Dado que p_{i} e p_{j} pertencem a um mesmo cluster, nenhuma das arestas do caminho P entre eles foi deletado pelo algoritmo. Ou seja, cada aresta pertencente a P tem comprimento menor ou igual a d^*. Por outro lado, sabemos que pi pertence a C_{s}', mas p_{j} não; logo, tomemos p' como o primeiro nó em P que não pertence a C_{s}' e p o nó que vem logo antes de p' no caminho P. Sabemos que d(p,p') \leq d^* em C' e isso completa a prova, pois o d \leq d(p,p'), sendo d o espaçamento de C'.

Implementação e Análise da Complexidade[editar | editar código-fonte]

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 O(logm), onde m é o número de elementos na fila. A complexidade de montar a minimum spanning tree é O(nlogm), onde n é o número de nós no grafo e m o número de arestas. Já a complexidade de deletar k-1 arestas é O((k-1)log(n-1)). 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 U com n nós e arestas é uma tarefa que possuí tempo de execução O(nlogm).

Código em Racket[editar | editar código-fonte]

(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))))))

Referências

  1. Segaran, Toby. In: Toby. Programming Collective Intelligence. First. ed. [S.l.]: O’Reilly, 2007. ISBN 0-596-52932-5.
  2. Kleinberg, Jon; Tardos, Éva. In: Jon. Algorithm Design. First. ed. [S.l.]: Cornell University, 2006. ISBN 0-262-03293-7.
[editar | editar código-fonte]
Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.