La determinación de la mejor k de k vecino más cercano

Question

Yo tengo necesidad de hacer un análisis de cluster en un conjunto de datos dimensionales 2 (que puede añadir dimensiones adicionales en el camino).

El análisis en sí formará parte de los datos que se alimenta en una visualización, en lugar de las entradas en otro proceso (por ejemplo Radial Basis Function Networks).

Con este fin, me gustaría encontrar un conjunto de clusters, que principalmente "se ve bien", en lugar de la aclaración de algunos patrones ocultos.

Mi intuición es que k-means sería un buen punto de partida para esto, pero que encontrar el número correcto de clústeres para ejecutar el algoritmo sería problemático.

El problema que estoy viniendo a es la siguiente:

Cómo determinar la 'mejor' valor de kde tal manera que los grupos formados son estables y visualmente verificable?

Preguntas:

• Suponiendo que esto no es NP-completo, ¿cuál es la complejidad de tiempo para encontrar un buen k. (probablemente se informó en varias ocasiones para ejecutar el algoritmo k-means).
• es k-significa un buen punto de partida para este tipo de problema? Si es así, ¿qué otros enfoques recomendaría? Un ejemplo específico, respaldado por una anécdota/experiencia sería maxi-bon.
• lo cortes/aproximaciones corta me recomiendan para aumentar el rendimiento.

Answer 1

lo podría hacer en los papeles en el grupo de validación. Here's one que se cita en trabajos que implican análisis de microarrays, que implica la agrupación de genes con niveles de expresión relacionados.

Una de estas técnicas es Medida de silueta que evalúa qué tan cerca está un punto etiquetado de su centroide. La idea general es que, si se asigna un punto a un centroide pero todavía está cerca de otros, tal vez se asignó al centroide incorrecto. Al contar estos eventos a través de conjuntos de entrenamiento y mirando a través de varias k-means agrupamientos, se busca la k tal que los puntos marcados en general caen en el "mejor" o mínimamente ambigua arreglo.

Hay que decir que la agrupación es más de una visualización de datos y la técnica de la exploración. Puede ser difícil dilucidar con certeza que una agrupación explica los datos correctamente, por encima de todos los demás. Lo mejor es fusionar sus agrupaciones con otra información relevante. ¿Hay algo funcional o de otra manera informativo sobre sus datos, de modo que usted sepa que algunos agrupamientos son imposibles? Esto puede reducir considerablemente el espacio de su solución.

Answer 2

Desde su enlace Wikipedia:

En cuanto a la complejidad computacional, las k-medias problema es la agrupación:

• NP-hard, en general, el espacio euclidiano D incluso para 2 grupos
• NP-hard de un número general de clusters k incluso en el plano
• Si k y d son fijos, el problema puede ser resuelto exactamente en el tiempo O (NDK + 1 log n), donde n es el número de entidades a ser agrupado

Por lo tanto, una variedad de heuristic algorithms generalmente se usan.

Dicho esto, encontrar un buen valor de k suele ser un proceso heurístico (es decir, prueba algunas y selecciona la mejor).

Creo que k-means es un buen punto de partida, es simple y fácil de implementar (o copiar). Solo busque más si tiene serios problemas de rendimiento.

Si el conjunto de puntos que desea agrupar es excepcionalmente grande, una optimización de primer orden sería seleccionar aleatoriamente un pequeño subconjunto, use ese conjunto para encontrar sus k-medias.

Answer 3

Para utilizar k-means, debe saber cuántos clústeres hay. No puede intentar una meta-optimización ingenua, ya que mientras más clúster agregue (hasta 1 clúster para cada punto de datos), más lo llevará a un ajuste excesivo. Puede buscar algunos métodos de validación de clúster y optimizar el hiperparámetro k con él, pero por mi experiencia, rara vez funciona bien. Es muy costoso también

Si fuera usted, haría una PCA, eventualmente en un espacio polinomial (cuide su tiempo disponible) dependiendo de lo que sepa de su entrada, y aglutine a lo largo de los componentes más representativos.

Más información en su conjunto de datos sería muy útil para una respuesta más precisa.

Answer 4

aquí está mi solución aproximada:

1. de inicio con k = 2.
2. Para un número de intentos:
   1. Ejecutar el algoritmo k-medias para encontrar k racimos.
   2. Encuentra la distancia cuadrada media desde el origen hasta los centroides del grupo.
3. Repita el 2-3, para encontrar una desviación estándar de las distancias. Este es un proxy para la estabilidad de los clusters.
4. Si la estabilidad de las agrupaciones de k < estabilidad de las agrupaciones de k - 1 luego regresar k - 1
5. Incremento k por 1.

La tesis detrás de este algoritmo es que el número de conjuntos de k clusters es pequeño para los valores "buenos" de k.

Si podemos encontrar un óptimo local para esta estabilidad, o un delta óptimo para la estabilidad, entonces podemos encontrar un buen conjunto de conglomerados que no se pueden mejorar agregando más conglomerados.

Answer 5

Para problemas con un número desconocido de clústeres, aglomeración de clústeres jerárquicos es a menudo una mejor ruta que k-means.

Agglomerative clustering produce una estructura de árbol, mientras que cuanto más cerca esté del tronco, menor será el número de conglomerados, por lo que es fácil escanear todos los números de conglomerados. El algoritmo comienza asignando cada punto a su propio clúster, y luego agrupa repetidamente los dos centroides más cercanos. Hacer un seguimiento de la secuencia de agrupamiento permite una instantánea instantánea para cualquier cantidad de clústeres posibles. Por lo tanto, a menudo es preferible utilizar esta técnica sobre k-means cuando no sabes cuántos grupos querrás.

Existen otros métodos de agrupación jerárquica (vea el documento sugerido en los comentarios de Imran). La principal ventaja de un enfoque aglomerativo es que hay muchas implementaciones disponibles para su uso.

Answer 6

En un previous answer, expliqué cómo se puede usar Self-Organizing Maps (SOM) en la agrupación visual.

De lo contrario, existe una variación del algoritmo K-medias llamada X-Means que es capaz de encontrar el número de grupos mediante la optimización de la Criterio de Información Bayesiano (BIC), además de resolver el problema de escalabilidad mediante el uso de KD-trees.
Weka incluye una implementación de X-Means junto con muchos otros algoritmos de clúster, todo en una herramienta GUI fácil de usar.

Por último, puede consultar this page que trata sobre el Método de codo, entre otras técnicas, para determinar la cantidad de clústeres en un conjunto de datos.

Answer 7

Elegir el mejor K se puede ver como un problema Model Selection. Un posible enfoque es Minimum Description Length, que en este contexto significa: Puede almacenar una tabla con todos los puntos (en cuyo caso K = N). En el otro extremo, tiene K = 1, y todos los puntos se almacenan como distancias desde un único centroide. This Section de Introducción a la Recuperación de Información por Manning y Schutze sugieren minimizar el Akaike Information Criterion como heurística para una K. óptima

Answer 8

Esta problemática pertenece a la clase "evaluación interna" de los "problemas de optimización de la agrupación", que curent estado de la solución de la técnica parece utilizar la silueta ** * * Coeficiente como se indica here

https://en.wikipedia.org/wiki/Cluster_analysis#Applications

y here:

https://en.wikipedia.org/wiki/Silhouette_(clustering):

"parcelas silueta y los promedios se pueden utilizar para determinar el número natural de c lustres dentro de un conjunto de datos"

scikit-learn proporciona una implementación de ejemplos de uso de la metodología here http://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_silhouette_analysis.html