python kmeans

python-ksignifica

Implementación en Python de la agrupación en clústeres de k-means. k-means es una técnica de aprendizaje no supervisada que intenta agrupar puntos de datos similares en un número de grupos especificado por el usuario. El siguiente ejemplo muestra la progresión de grupos para el conjunto de datos Iris utilizando el algoritmo de inicialización de centroide k-means++.

Descripción

k-means intenta identificar un número k(<N) de clústeres especificado por el usuario a partir de un conjunto de vectores de valor real N d-dimensionales. El algoritmo procede intentando minimizar la suma de las distancias al cuadrado desde el centro del grupo hasta los miembros del grupo. El algoritmo canónico se desarrolla en tres fases:

1. Inicialice k centroides aleatorios (centros de clúster);
2. asignar puntos de datos al grupo más cercano según la métrica de distancia (normalmente distancia euclidiana);
3. actualizar los centroides a la media de los miembros del grupo;
4. repita los pasos 2 y 3 hasta que las asignaciones del paso 2 no cambien.

El resultado del algoritmo es una asignación de clúster para cada punto de datos y un nivel final de "distorsión". El algoritmo no produce una solución demostrablemente óptima y los centros de conglomerados iniciales pueden hacer que el algoritmo se quede atascado en una solución localmente óptima que es claramente subóptima (consulte el ejemplo básico 2D en la sección Resultados).

Muchas investigaciones se han centrado en:

• selección de centros de conglomerados iniciales. K-Means++ es un método bien conocido y se incluye en esta implementación; el algoritmo se describe en la siguiente subsección.
• calcular distancias, es decir, utilizar medidas distintas a las euclidianas, ver aquí.

K-Medias++

En lugar de inicializar centroides aleatorios como en el paso 1 anterior, k-means++ extiende probabilísticamente los centroides iniciales para evitar una configuración inicial deficiente. El algoritmo es:

1. Elija el primer centroide al azar.
2. Para cada punto de datos x, calcule la distancia d(x), desde x hasta el centroide más cercano que ya se ha elegido.
3. Seleccione un punto de datos para que sea el siguiente centroide utilizando una probabilidad ponderada proporcional a d(x)2.

Esta técnica favorece los puntos de datos que no están cerca de otros centroides iniciales y utiliza una política de selección que recuerda a la selección de rueda de ruleta (o de aptitud proporcional) que se utiliza a menudo en los algoritmos genéticos.

Recursos

Algoritmo básico

• K-Means se describe en Los 10 principales algoritmos para minería de datos;

• K-Means se describe en Teoría de la información, inferencia y algoritmos de aprendizaje, extracto aquí;

• El profesor Andrew Moore de CMU tiene algunas buenas notas aquí;

• Ejemplo de Edureka, utilizando datos sobre delitos

Inicialización de clústeres

• K-Means++ y artículo completo aquí

• Un estudio comparativo de métodos de inicialización eficientes para el algoritmo de agrupación de K-Means

¿Por qué no utilizar SciPy?

SciPy tiene una implementación de k-means. El objetivo de este trabajo es construir una implementación pura de Python con el propósito de aprender y ayudar a otros a aprender el algoritmo k-means. Los lectores interesados ​​con una mínima experiencia en Python podrán leer y revisar este código sin la complejidad adicional de una biblioteca como SciPy. De ninguna manera está destinado al uso en producción :)

Ejecutando el código

Dependencias

• pitón 3.6.3
• matplotlib 2.1.1: consulte aquí para obtener instrucciones de instalación.

Ejecución

Ejecute el código con el intérprete de Python:

python kmeans.py ./resources/<config.cfg>

Donde config.cfg es un archivo de configuración de texto sin formato. El formato del archivo de configuración es un dictado de Python con los siguientes campos:

 {
   'data_file' : '\resources\iris.csv',
   'data_project_columns' : ['sepal_length','sepal_width','petal_length','petal_width','class'],
   'k' : 3,
   'cluster_atts' : ['sepal_length','sepal_width','petal_length','petal_width'],
   'init_cluster_func' : 'kmeans_plus_plus',
   'plot_config' :
    {'output_file_prefix' : 'iris',
     'plots_configs': [
        {'plot_atts' : ['sepal_length','sepal_width']},
        {'plot_atts' : ['sepal_length','petal_length']},
        {'plot_atts' : ['sepal_length','petal_width']},
        {'plot_atts' : ['sepal_width','petal_length']},
        {'plot_atts' : ['sepal_width','petal_width']},
        {'plot_atts' : ['sepal_width','petal_width']}
     ]
   }
}

Tienes que especificar:

• un archivo de datos csv;
• un subconjunto de campos para proyectar desde el archivo;
• el número de grupos a formar, k;
• el subconjunto de atributos utilizados en el proceso de agrupación;
• opcionalmente, especifique una función de clúster inicial (predeterminada = 'rand_init_centroids'), los autores interesados ​​deben agregar la suya propia al código y especificarla aquí;
• una configuración de trama que incluye
  • prefijo para archivos png creados durante el proceso en el directorio de trabajo, si no se especifica, las imágenes no se producirán;
  • las configuraciones de parcelas individuales, limitadas a 2 dimensiones por parcela.

Resultados

Conjunto de datos del iris

El conjunto de datos de Iris (iris.config), de Lichman, M. (2013). Repositorio de aprendizaje automático de la UCI. Irvine, CA: Universidad de California, Facultad de Información y Ciencias de la Computación, es un conjunto de datos muy conocido en la comunidad de aprendizaje automático. Aquí están los resultados de mis grupos iniciales aleatorios:

Datos sintéticos básicos 2D

Estos datos se generaron con fines de depuración (consulte basic2d.config) e ilustran el efecto de tener una mala elección de clústeres aleatorios iniciales. Los siguientes resultados demuestran una configuración de centroide inicial que impide que el algoritmo alcance la asignación de grupo obvia. En este caso, la ubicación del centroide rojo significa que el centroide azul captura todos los puntos de datos en los cuadrantes inferior izquierdo e inferior derecho.

Delito

El conjunto de datos sobre delitos (crime.config) es de Edureka, aquí.