Parece que para K-means y otros algoritmos relacionados, agrupamiento se basa en calcular la distancia entre puntos. ¿Es hay uno que funciona sin ella?
¡Gracias!
Respuestas
¿Demasiados anuncios?
Un ejemplo de este método son Finitos Modelos de Mezcla (por ejemplo, aquí o aquí) que se utiliza para la agrupación. En FMM que tener en cuenta la distribución ($f$) de la variable $X$ como una mezcla de $K$ distribuciones ($f_1,...,f_k$):
$$f(x, \vartheta) = \sum^K_{k=1} \pi_k f_k(x, \vartheta_k)$$
where $\vartheta$ is a vector of parameters $\vartheta = (\pi', \vartheta_1', ..., \vartheta_k')'$ and $\pi_k$ is a proportion of $k$'th distribution in the mixture and $\vartheta_k$ is a parameter (or parameters) of $f_k$ distribution.
A specific case for discrete data is Latent Class Analysis (e.g. here) defined as:
$$P(x, k) = P(k) P(x|k)$$
where $P(k)$ is probability of observing latent class $k$ (i.e. $\pi_k$), $P(x)$ is probability of observing an $x$ value and $P(x|k)$ is probability of $x$ being in class $k$.
Usualmente, por tanto, FMM y LCA algoritmo EM se utiliza para la estimación, pero el enfoque Bayesiano también es posible, pero un poco más exigente, debido a problemas tales como la identificación del modelo y la etiqueta de conmutación (por ejemplo, Xi'an en el blog).
Así que no hay ninguna medida de distancia, sino más bien un modelo estadístico de la definición de la estructura (distribución) de sus datos. Debido a que el otro nombre de este método es el "modelo basado en la agrupación".
Compruebe que los dos libros en FMM:
- McLachlan, G. & Peel, D. (2000). Finito De Modelos De Mezcla. John Wiley & Sons.
- Frühwirth-Schnatter, S. (2006). Finito de la Mezcla y de Markov Switching Modelos. Springer.
Uno de los más populares de la agrupación de paquetes que utiliza el FMM mclust (marque aquí o aquí) que es implementado en R. Sin embargo, más complicado de FMM también son posibles, por ejemplo flexmix paquete y documentación. Para la LCA no es un R poLCA paquete.
Amadiere
Puntos
5606
K-means no es "en realidad" basado en la distancia. Minimiza la varianza. (Pero la varianza $\sim$ Euclídea al cuadrado de las distancias; por lo que cada punto se le asigna al centroide más cercano por la distancia Euclídea, también).
Hay un montón de grid basado en la agrupación de los enfoques. No calcular distancias debido a que a menudo se producen cuadrática en tiempo de ejecución. En su lugar, que la partición de los datos y el agregado en las celdas de la cuadrícula. Pero la intuición detrás de este tipo de enfoque es generalmente de muy estrechamente relacionado con las distancias.
Hay un número de algoritmos de clustering para datos categóricos como COOLCAT y ESTUCO. Las distancias no son fáciles de usar con estos datos (de una bañera de codificación es un hack, y no se produce especialmente significativo distancias). Pero no he oído de nadie que el uso de estos algoritmos...
Hay enfoques de agrupamiento para los gráficos. Pero tampoco se reduce a clásico gráfico de problemas tales como la camarilla o cerca de-la camarilla de encontrar y gráfico para colorear, o están estrechamente conectadas a distancia basado en la agrupación (si usted tiene un grafo ponderado).
Densidad de clustering basado en como DBSCAN tiene un nombre diferente, y no se centra en torno a la minimización de las distancias; pero la "densidad" es usualmente especificado con respecto a la distancia, así que técnicamente estos algoritmos son función de la distancia o basadas en la red.
La parte esencial de su pregunta que usted olvidarse de lo que sus datos?
AusTravel
Puntos
6
Además de la anterior agradable respuestas, yo sugeriría considerando Dirichlet modelos de mezcla y Bayesiano basado jerárquica de Dirichlet modelos de proceso. Para una más completa y visión general de los enfoques y métodos para determinar el número óptimo de clusters, por favor ver este excelente respuesta de StackOverflow: http://stackoverflow.com/a/15376462/2872891.
karatchov
Puntos
230
Puramente discriminativo enfoque es "regularización de la información maximización" por Gomes et al. No existe la noción de similitud/distancia que participan en ella en absoluto.
La idea es tener una regresión logística como modelo que pone los puntos en los contenedores. Pero en lugar de entrenamiento para maximizar algún tipo de log-verosimilitud de las etiquetas de clase, la función objetivo es el que pone los puntos en diferentes categorías.
Para controlar la cantidad de clusters utilizados por el modelo, un adicional de regularización plazo ponderado por el hyper parámetro $\lambda$ es utilizado. Se reduce a una la inversa de la varianza de una Gaussiana previo sobre los pesos.
Extensión del kernel o métodos de redes neuronales para el no-lineal de la agrupación es sencillo.
