algoritmo de agrupamiento para datos no dimensionales

12

Tengo un conjunto de datos de miles de puntos y un medio para medir la distancia entre dos puntos, pero los puntos de datos no tienen dimensionalidad. Quiero un algoritmo para encontrar centros de clúster en este conjunto de datos. Me imagino que debido a que los datos no tienen dimensiones, un centro de clúster podría constar de varios puntos de datos y una tolerancia, y la membresía dentro del clúster podría determinarse por el promedio de la distancia de un punto de datos a cada punto de datos en el centro del clúster.

perdóneme si esta pregunta tiene una solución bien conocida, ¡sé muy poco sobre este tipo de problema! mi (muy limitada) investigación solo ha encontrado algoritmos de agrupamiento para datos dimensionales, pero me disculpo de antemano si me he perdido algo obvio.

¡gracias!

machine-learning lg.learning clustering lata de pintura
fuente

¿Por qué la no dimensionalidad hace que este problema sea especial?

Raphael

1

Algunos algoritmos que vi para el agrupamiento (realmente solo k-means) requieren la generación de puntos de datos aleatorios como semillas, lo que no es posible con datos adimensionales. Por lo tanto, el requisito especial es que los centros de clúster deben estar representados por un conjunto de puntos de datos existentes (quizás ponderados).

paintcan

15

Si la función de distancia es una métrica, puede emplear el agrupamiento de centros (donde se minimiza el radio máximo de una bola) o el agrupamiento de medios (que minimiza la suma de las distancias a los centros de los conglomerados). La agrupación del centro es fácil: simplemente seleccione los puntos lejanos y tendrá la garantía de obtener una aproximación de 2 a través de la desigualdad triangular (este es un resultado antiguo debido a González). $k$ $k$ $k$ $k$

Para el agrupamiento -median, ha habido un montón de trabajo, demasiado para revisar aquí. Michael Shindler de UCLA tiene una buena encuesta de las ideas principales. $k$

Ambos problemas son NP-hard en general, y son difíciles de aproximar dentro de un factor arbitrario. Tenga en cuenta que si deja de ser métrico, las cosas empeorarán en términos de aproximación.

Otro enfoque más heurístico que podría estar bien para su aplicación es usar una técnica como MDS (escalamiento multidimensional) para incrustar su matriz de distancia en un espacio euclidiano, y luego usar uno de los muchos métodos de agrupación euclidiana diferentes (o incluso agrupación de medios . ) Si está seguro de que su función de distancia es métrica, puede hacer una incrustación un poco más inteligente en el espacio euclidiano y obtener una garantía demostrable (aunque débil) sobre la calidad de su respuesta. $k$

En última instancia, como con la mayoría de los problemas de agrupamiento, su elección final depende de la aplicación, el tamaño de sus datos, etc.

Suresh Venkat
fuente

3

Gracias por la descripción rápida y clara. Me llevará al menos unos días determinar si ha respondido mi pregunta. Parece que tengo mucho que aprender antes de entender mi problema lo suficiente :)

paintcan

5

También hay agrupación de correlación , que tiene como información de entrada para cada par de elementos que indican si pertenecen al mismo clúster o a clústeres diferentes.

Warren Schudy
fuente

Sí, ese es otro buen ejemplo. ¡Y, por supuesto, Warren es un experto en esto! Sin embargo, no sé si la entrada del OP fue +/-, o si se pudo convertir a través del umbral. Si es así, esta es definitivamente una opción viable.

Suresh Venkat

5

Si solo está buscando un buen rendimiento empírico, el algoritmo de propagación de afinidad generalmente funciona mejor que k-medians. Hay un código disponible en varios idiomas y las publicaciones que describen el algoritmo con más detalle están aquí: http://www.psi.toronto.edu/index.php?q=affinity%20propagation

\sum_{i} s (i, c_{i})

$\sum_{i} s(i, c_i)$

$s$ $c_i \in \mathbf{c}$ $i$ $s(i, i)$

dan_x
fuente

5

Su pregunta parece implicar que está buscando un algoritmo con un tiempo de cálculo decente. Dado el tamaño de sus vértices (o puntos) sería crear una representación gráfica ponderada de sus datos y usar el Algoritmo de Clúster de Markov (MCL) para agrupar el gráfico.

http://www.micans.org/mcl/

MCL se basa en recorridos aleatorios a través de gráficos ponderados y no ponderados para encontrar subgráficos densos. Es capaz de manejar gráficos grandes y se ha utilizado en muchos programas bioinformáticos conocidos y bien utilizados (como BLAST). -Boucher

Christina Boucher
fuente

1

Considere el algoritmo vecino k-más cercano .

Rafael
fuente

Raphael, el algoritmo k-NN no es realmente un algoritmo de agrupamiento, ¿verdad? a menos que extraiga repetidamente los k vecinos de un nodo?

Suresh Venkat

k

$k$

algoritmo de agrupamiento para datos no dimensionales

Respuestas: