Cómo agrupar objetos (sin coordenadas)

Question

Tengo una lista de objetos opacos. Sólo soy capaz de calcular la distancia entre ellos (no es cierto, sólo la creación de las condiciones para el problema):

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

me gustaría agrupar estos objetos. Me gustaría controlar el número de racimos y me gustaría que los objetos "Cerrar" para estar en el mismo grupo:

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

Puede alguien sugerir (y enlace a ;-)) algunos algoritmos de agrupamiento (el más simple, ¡mejor!) o bibliotecas que pueden ayudarme?

Aclaración La mayoría de los algoritmos de agrupación requieren que los objetos se distribuyan en algún espacio N-dimensional. Este espacio se usa para encontrar "centroides" de clusters. En mi caso, no sé qué es N, ni sé cómo extraer un sistema de coordenadas de los objetos. Todo lo que sé es qué tan separados están 2 objetos. Me gustaría encontrar un buen algoritmo de agrupamiento que use solo esa información.

Imagine que se está agrupando según el "olor" de un objeto. No sabes cómo poner "olores" en un avión 2D, pero sí sabes si dos olores son similares o no.

Answer 1

Creo que está buscando K-Medoids. Es como K-means en el que especifica el número de clústeres, K, de antemano, pero no requiere que tenga la noción de "promediar" los objetos que está agrupando como lo hace K-means.

En su lugar, cada clúster tiene un representante medoid, que es el miembro del clúster más cercano al centro. Se podría pensar que es una versión de K-means que encuentra "medianas" en lugar de "medias". Todo lo que necesita es una medida de distancia para agrupar las cosas, y lo he usado en mi propio trabajo por exactamente las mismas razones que usted cita.

Naive K-medoids no es el algoritmo más rápido, pero hay variantes rápidas que probablemente sean lo suficientemente buenas para sus propósitos. Aquí están las descripciones de los algoritmos y los enlaces a la documentación de sus implementaciones en R:

1. PAM es la aplicación básica de O (n^2) de K-medoids.
2. CLARA es una versión de PAM mucho más rápida y muestreada. Funciona agrupando subgrupos de objetos aleatoriamente muestreados con PAM y agrupando todo el conjunto de objetos en función del subconjunto. Todavía deberías ser capaz de obtener muy buenos agrupamientos rápidos con esto.

Si necesita más información, here's a paper que da una visión general de estos y otros métodos de K-medoids.

Answer 2

Aquí hay un 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. 
} 

Alternativamente, leer the wikipedia page. K-means clustering es una buena opción:

El algoritmo K-means asigna cada punto al clúster cuyo centro (también llamado centroide) es el más cercano. El centro es el promedio de todos los puntos del clúster, es decir, sus coordenadas son la media aritmética de cada dimensión por separado sobre todos los puntos del clúster.

Las etapas de algoritmo son:

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

Las principales ventajas de este algoritmo son su simplicidad y la velocidad que permite que se ejecute en grandes conjuntos de datos. Su desventaja es que no produce el mismo resultado con cada ejecución, ya que los clústeres resultantes dependen de las asignaciones aleatorias iniciales. Es minimiza la variación dentro del clúster, pero no garantiza que el resultado tenga un mínimo de varianza global . Otra desventaja de es el requisito de el concepto de un medio que se puede definir que no siempre es el caso. Para tales conjuntos de datos , la variante k-medoides es apropiada.

Answer 3

Aquí hay un esquema para un algoritmo de agrupación que no tiene el requisito K-means de encontrar un centroide.

1. Determina la distancia entre todos los objetos. Registre n objetos más separados.
   [encuentra raíces de nuestros clusters, tiempo O (n^2)]
2. Asignar cada uno de estos n puntos aleatorios a n nuevos grupos distintos.
3. Para todos los demás objetos:
   [objetos asignar a grupos, el tiempo O (n^2)]
   1. Para cada cluster:
      1. calcular la distancia media de un grupo a ese objeto por promediando la distancia de cada objeto en el grupo al objeto.
         
   2. Asigne el objeto al clúster más cercano.

Este algoritmo será sin duda agrupar los objetos. Pero su tiempo de ejecución es O (n^2). Además, está guiado por los primeros n puntos elegidos.

¿Alguien puede mejorar esto (mejor rendimiento de tiempo de ejecución, menos dependiente de las opciones iniciales)? Me encantaría ver tus ideas

Answer 4

¿Qué hay de este enfoque:

1. Asignar todos los objetos a un clúster.
2. Encuentra los dos objetos, un y b, que están dentro de la misma agrupación, k, y que son la distancia máxima de separación. Para aclarar, no debería haber una un y b para todo el conjunto, no uno un y b para cada clúster.
3. clúster de Split k en dos grupos, k1 y k2, una con objeto un y una con objeto b.
4. Para todos los otros objetos en racimo k, añadirlo a k1 o k2 mediante la determinación de la distancia media mínima para todos los demás objetos que clúster.
5. Repita los pasos 2 a 5 hasta que se formen N racimos.

Creo que este algoritmo debería darle una agrupación bastante buena, aunque la eficacia podría ser bastante mala. Para mejorar la eficiencia, puede modificar el paso 3 para que encuentre la distancia mínima solo al objeto original que inició el clúster, en lugar de la distancia promedio a todos los objetos que ya están en el clúster.

Answer 5

El análisis de la secuencia de ADN filogenético utiliza regularmente clústeres jerárquicos en cadenas de texto, con matrices de distancia [de alineación].He aquí un buen tutorial para el agrupamiento R:

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

(Atajo: ir directamente a la sección de "jerárquica Aglomerativo" ...)

Aquí están algunas otras bibliotecas [idioma]:

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

Este enfoque podría ayudar a determinar cuántos [k] clusters "naturales" hay y qué objetos usar como raíces para los enfoques de k de arriba.