Como agrupar objetos (sem coordenadas)

Question

Eu tenho uma lista de objetos opacos. Eu sou apenas capaz de calcular a distância entre eles (não é verdade, apenas a criação das condições para o problema):

class Thing {
    public double DistanceTo(Thing other);
}

Gostaria de agrupar esses objetos. Eu gostaria de controlar o número de clusters e eu gostaria de "fechar" objetos para estar no mesmo cluster:

List<Cluster> cluster(int numClusters, List<Thing> things);

Alguém pode sugerir (e link para ;-)) alguns algoritmos de agrupamento (quanto mais simples, melhor!) Ou bibliotecas que podem me ajudar?

Clarificação A maioria dos algoritmos de agrupamento exige que os objetos ser colocado para fora em algum espaço N-dimensional. Este espaço é usado para encontrar "centróides" de clusters. No meu caso, eu não sei o que N é, nem sei como extrair um sistema de coordenadas dos objetos. Tudo o que sei é quão distantes 2 objetos são. eu gostaria de encontrar um algoritmo bom agrupamento que usa apenas essa informação.

Imagine que você está agrupando por base o "cheiro" de um objeto. Você não sabe como colocar "cheira out" em um plano 2D, mas você sei se dois cheiros são semelhantes ou não.

Answer 1

Eu acho que você está procurando K-Medoids . É como K-means em que você especificar o número de clusters, K , com antecedência, mas não exigem que você tenha uma noção de "média" o que você está objetos de agrupamento como K- meios faz.

Em vez disso, cada cluster tem um representante medoide , que é o membro do cluster mais próximo do meio. Você pode pensar nisso como uma versão do K-means que encontra "medianas" em vez de "meio". Tudo que você precisa é de uma distância métrica para as coisas de fragmentação, e eu usei isso em alguns dos meu próprio trabalho exatamente pelas mesmas razões que você cita.

Naive K-medoids não é o algoritmo mais rápido, mas existem variantes rápidas que provavelmente são bons o suficiente para seus propósitos. Aqui estão as descrições dos algoritmos e links para a documentação para suas implementações em R :

1. PAM é o básico O (n ^ 2) aplicação de K-medoides.
2. CLARA é um tanto mais rápido, versão do PAM amostrados. Ele funciona por agrupamento subconjunto amostrados aleatoriamente de objectos com a PAM e agrupamento de todo o conjunto de objectos com base no subconjunto. Você deve ainda ser capaz de obter muito bons agrupamentos rápido com isso.

Se precisar de mais informações, aqui está uma papel que dá uma Resumo dos estes e outros K-medoids métodos.

Answer 2

Aqui está um esboço de um algoritmo de agrupamento que não tem a exigência de K-médias de encontrar um baricentro.

1. Determinar a distância entre todos os objetos. Grave n a maioria dos objetos separados.
   [ encontra raízes de nossos clusters, tempo de O (n ^ 2) ]
2. Atribuir cada um desses n pontos aleatórios para n novos grupos distintos .
3. Para todos os outros objetos:
   [ objetos atribuir a grupos, tempo de O (n ^ 2) ]
   1. Para cada cluster:
      1. Calcular a distância média de um cluster para esse objeto pela média a distância de cada objeto no cluster para o objeto.
         
   2. Atribuir o objeto ao cluster mais próximo.

Este algoritmo irá certamente agrupar os objetos. Mas seu tempo de execução é O (n ^ 2) . Além disso, ele é guiado por aqueles primeira n pontos escolhidos.

Alguém pode melhorar esse (melhor perf tempo de execução, menos dependente de escolhas iniciais)? Gostaria muito de ver suas idéias.

Answer 3

Aqui está um algoritmo rápido.

While (points_left > 0) {
 Select a random point that is not already clustered
 Add point and all points within x distance 
   that aren't already clustered to a new cluster.
}

Como alternativa, leia página wikipedia. K-means agrupamento é uma boa escolha:

Os K-means atribui a cada ponto ao cluster cujo (também chamado de centróide) centro é mais próximo. O centro é a média de todos os pontos do cluster -. Isto é, as suas coordenadas são a média aritmética para cada dimensão separadamente ao longo de todos os pontos do cluster

Os passos do algoritmo são:

* Choose the number of clusters, k.
* Randomly generate k clusters and determine the cluster centers, or
  directly generate k random points as cluster centers.
* Assign each point to the nearest cluster center.
* Recompute the new cluster centers.
* Repeat the two previous steps until some convergence criterion is
  met (usually that the assignment hasn't changed).

As principais vantagens deste algoritmo são a sua simplicidade e velocidade que permite que ele seja executado em grandes conjuntos de dados. Sua desvantagem é que ele não faz se obter o mesmo resultado com cada execução, uma vez que os aglomerados resultantes dependem as atribuições aleatórias iniciais. isto minimiza a variação intra-agrupamento, mas não garante que o resultado tem um mínimo global de variância. Outro desvantagem é a necessidade de o conceito de um meio para ser definível o que nem sempre é o caso. Por tal conjuntos de dados a variante k-medoides está apropriada.

Answer 4

Como sobre essa abordagem:

1. Atribuir todos os objetos para um cluster.
2. Localize os dois objetos, a e b , que estão dentro do mesmo cluster, k , e que são uma distância máxima de intervalo. Para esclarecer, deve haver um a e b para todo o conjunto, não um a e b para cada cluster.
3. aglomerado Dividir k em dois clusters, k1 e K2 , um com objeto a e um com objeto b .
4. Para todos os outros objetos no cluster k , adicioná-los à k1 ou K2 , determinando a distância média mínima para todos os outros objetos em que cluster.
5. Repita os passos 2-5 até aglomerados N são formados.

Eu acho que este algoritmo deve dar-lhe um bom agrupamento, embora a eficiência pode ser muito ruim. Para melhorar a eficiência que você pode alterar o passo 3 para que você encontrar a distância mínima para somente o objeto original que iniciou o cluster, em vez da distância média a todos os objetos já no cluster.

Answer 5

A análise da sequência de ADN filogenética utiliza regularmente agrupamento hierárquico em cadeias de texto, com matrizes de distância [alinhamento]. Aqui está uma boa R tutorial para o agrupamento:

• http://www.statmethods.net/advstats/cluster.html

(atalho: ir direto para a seção "hierárquico aglomerativo" ...)

Aqui estão alguns outros [língua] bibliotecas:

• http: //bonsai.ims.u-tokyo .ac.jp / ~ mdehoon / software / cluster /
• http://code.google.com/p/scipy-cluster/

Esta abordagem pode ajudar a determinar quantos [k] aglomerados "naturais" existem e quais objetos para usar como raízes para os k-médias se aproxima acima.