Estoy tratando de cluster un gráfico usando el arracimar espectral. Sin embargo desconozco el número de clases que existen en los datos. ¿Sería una buena idea para aplicar el ACP en la matriz de la adyacencia del gráfico para encontrar el número real de clústeres en el conjunto de datos? ¿Hay alguna otra opción?
Respuestas
¿Demasiados anuncios?
user2121
Puntos
179
El problema de encontrar el número correcto de las clases está sin resolver y hay muchos enfoques que se ocupan de este problema. Para los enfoques generales, usted puede tener una mirada en el problema de encontrar de k en k-means.
Al realizar el análisis espectral, puede utilizar el eigengap método para encontrar una buena aproximación del número de clases. Consiste en el cómputo de las diferencias entre los consecutivos ordenó autovalores de la gráfica de Laplace.
Si la diferencia entre decir, la 4ª y la 5ª autovalores es grande en comparación con las otras diferencias, entonces es probable que no será de 4 clases en el gráfico. Sin embargo, nótese que no hay un método perfecto para decir si una diferencia es lo suficientemente grande o no. En particular, considerando la mayor diferencia podría no conducir a la mejor partición.
Una técnica común es considerar varios números de las clases y realizar varios k-means (o de cualquier otra agrupación). A continuación, mantener la partición de tener la más alta calidad de acuerdo a algunos externos medida.
ebricca
Puntos
31
Si usted está usando R o Python (o incluso C), usted puede tener una mirada en el excelente igraph paquete. Especialmente, un vistazo a los distintos comunidad de algoritmos de detección de este paquete implementa. Lo que hablamos está estrechamente relacionado con el principal vector propio algoritmo de Newman (2006). Aquí es el papel de la introducción de este algoritmo, es una lectura muy interesante.
Una buena estrategia es implementar varias de la comunidad de algoritmos de detección y agregar los resultados. Esto conduce a un algoritmo independiente, más estable y resultados significativos. Aquí hay un enlace a una función que escribí para ese propósito. Uno externo "medida" (como menciona el P. N. Mougel arriba) que se puede utilizar es la modularidad.
