¿Hay algún algoritmo de agrupamiento no basado en la distancia?

Parece que para K-means y otros algoritmos relacionados, la agrupación se basa en el cálculo de la distancia entre puntos. ¿Hay alguno que funcione sin él?

Un ejemplo de tal método son los modelos de mezcla finita (por ejemplo, aquí o aquí ) utilizados para la agrupación. En FMM se tiene en cuenta la distribución ( ) de la variable X como una mezcla de K distribuciones ( f 1 , . . . , F k ):$f$$X$$K$$f_1,...,f_k$

donde es un vector de parámetros θ = ( π ' , θ ' 1 , . . . , θ ' k ) ' y π k es una proporción de k 'th distribución en la mezcla y θ k es un parámetro (o parámetros) de distribución f k .$\vartheta$$\vartheta = (\pi', \vartheta_1', ..., \vartheta_k')'$$\pi_k$$k$$\vartheta_k$$f_k$

Un caso específico para datos discretos es el Análisis de clase latente (por ejemplo, aquí ) definido como:

donde es la probabilidad de observar la clase k latente (es decir, π k ), P ( x ) es la probabilidad de observar un valor de x y P ( x | k ) es la probabilidad de que x esté en la clase k .$P(k)$$k$$\pi_k$$P(x)$$x$$P(x|k)$$x$$k$

Por lo general , se utiliza el algoritmo FMM y LCA EM para la estimación, pero el enfoque bayesiano también es posible, pero un poco más exigente debido a problemas como la identificación del modelo y el cambio de etiquetas (por ejemplo, el blog de Xi'an ).

Por lo tanto, no existe una medida de distancia, sino un modelo estadístico que define la estructura (distribución) de sus datos. Debido a ese otro nombre de este método es "agrupamiento basado en modelos".

Mira los dos libros sobre FMM:

• McLachlan, G. y Peel, D. (2000). Modelos de mezclas finitas. John Wiley & Sons.
• Frühwirth-Schnatter, S. (2006). Mezcla finita y modelos de conmutación de Markov. Saltador.

Uno de los paquetes de agrupamiento populares que utiliza FMM es mclust(marque aquí o aquí ) que está aplicado en la I . Sin embargo, también son posibles FMM más complicados, consulte por ejemplo el flexmixpaquete y su documentación . Para LCA hay un paquete R poLCA .

$\sim$

Hay muchos enfoques de agrupación basados ​​en cuadrículas . No calculan distancias porque eso a menudo generaría un tiempo de ejecución cuadrático. En cambio, dividen los datos y los agregan en celdas de cuadrícula. Pero la intuición detrás de tales enfoques generalmente está muy relacionada con las distancias.

Hay varios algoritmos de agrupamiento para datos categóricos como COOLCAT y STUCCO. Las distancias no son fáciles de usar con tales datos (la codificación de un solo uso es un truco y no produce distancias particularmente significativas). Pero no he oído hablar de nadie que use estos algoritmos ...

Existen enfoques de agrupación para gráficos. Pero o se reducen a problemas gráficos clásicos, como la búsqueda de camarillas o cerca de la camarilla y la coloración de gráficos, o están estrechamente relacionados con la agrupación basada en la distancia (si tiene un gráfico ponderado).

La agrupación basada en la densidad, como DBSCAN, tiene un nombre diferente y no se centra en minimizar las distancias; pero la "densidad" generalmente se especifica con respecto a una distancia, por lo que técnicamente estos algoritmos se basan en la distancia o en la cuadrícula.

La parte esencial de su pregunta que dejó fuera es ¿cuáles son sus datos ?

Además de las buenas respuestas anteriores, sugeriría considerar los modelos de mezcla de Dirichlet y los modelos de procesos jerárquicos de Dirichlet basados ​​en Bayesian . Para obtener una descripción general bastante completa y general de los enfoques y métodos para determinar un número óptimo de clústeres , consulte esta excelente respuesta en StackOverflow : /programming//a/15376462/2872891 .

Un enfoque puramente discriminatorio es la "maximización de información regularizada" por Gomes et al. . No existe ninguna noción de similitud / distancia en absoluto.

La idea es tener una regresión logística como modelo que ponga puntos en contenedores. Pero en lugar de entrenarlo para maximizar alguna forma de log-verosimilitud de las etiquetas de clase, la función objetivo es aquella que pone puntos en diferentes grupos.

Para controlar la cantidad de clústeres utilizados por el modelo, un término de regularización adicional ponderado por el hiperparámetro $\lambda$es usado Se reduce a la varianza inversa de un gaussiano anterior sobre los pesos.

La extensión a los métodos del núcleo o las redes neuronales para la agrupación no lineal es sencilla.