K-means en Python y Scikit-learn, con ejemplos

El K-means es un método de Clustering que separa ‘K’ grupos de objetos (Clusters) de similar varianza, minimizando un concepto conocido como inercia, que es la suma de las distancias al cuadrado de cada objeto del Cluster a un punto ‘μ’ conocido como Centroide (punto medio de todos los objetos del Cluster).

El algoritmo de los K-means tienen como objetivo elegir ‘K’ centroides que reduzcan al mínimo la inercia:

El funcionamiento de este algoritmo comienza eligiendo un centroide para cada uno de los ‘K’ Clusters. El método de elección de estos centroides puede ser cualquiera; siendo los dos más comunes, el inicializarlo de forma aleatoria o el de elegir ‘K’ objetos del data set, bien sea de forma aleatoria o haciendo un pre-procesamiento de los datos. Lo recomendable sería la segunda opción e inicializar estos Clusters con objetos del data set. Una vez inicializados los centroides, el algoritmo continua alternando los dos siguientes pasos (asignación y actualización) de forma iterativa hasta que los centroides converjan:

• Asignación: Se asigna cada objeto al Cluster más cercano, aplicando alguna medida de distancia (como por ejemplo la distancia euclídea) entre el objeto y el centroide del Cluster.
  
• Actualización: Calcula los nuevos centroides, haciendo la media de los objetos que forman el Cluster.
  

Se considera que el algoritmo finaliza cuando los centroide convergen o cuando la diferencia entre el valor de los centroides de una iteración a otra es inferior a un determinado umbral.

Veamos a continuación un ejemplo de ejecución del K-means para 3 Clusters, dado un data set en el que cada objeto esta representado por un punto en un espacio de dos dimensiones:

1. Inicialización de los Clusters: Para ello cogemos al azar 3 puntos del data set y los asignamos a un Cluster. Como cada Cluster solo tiene un punto, será ese punto el centroide del Cluster:

2. Primera asignación y actualización: Tras haber elegido al azar 3 Clusters, se asigna cada punto al Cluster más cercano. Una vez que están asignados todos los puntos, se calcula un nuevo centroide siendo este el valor medio de todos los puntos.

3. Segunda asignación y actualización: Con los nuevos centroides, volvemos a calcular para cada punto cual es el centroide más cercano y asignamos ese punto al centroide. Una vez asignados los puntos a los Clusters, volvemos a calcular los centroides.

4. Converge y resultado final: Estos pasos de asignación y actualización se repiten hasta que los centroides de los Clusters converjan; es decir, hasta que el valor de los centroides de la última iteración de actualización coincida con el valor de los centroides de la iteración anterior de actualización:

Veamoslo de forma animada:

Definido el funcionamiento del algoritmo paso por paso y con un ejemplo, pasamos a mostrarlo en pseudocódigo:

En los dos siguientes puntos: Implementación del K-means y K-means con scikit-learn, se va a mostrar la implementación del K-means y el uso de la librería scikit-learn para la resolución de un problema de Clustering con el algoritmo del K-means respectivamente, cuyo código se puede obtener en el siguiente repositorio:

https://github.com/RicardoMoya/KMeans_Python

El código que se encuentra en este repositorio hace uso de las librerías de numpy, matplotlib, scipy y scikit-learn. Para descargar e instalar (o actualizar a la última versión con la opción -U) estas librerías; con el sistema de gestión de paquetes pip, se deben ejecutar los siguiente comandos:

pip install -U numpy
pip install -U matplotlib
pip install -U scipy
pip install -U scikit-learn

Implementación del K-means

En este apartado se va a mostrar la implementación del K-means (desde un punto de vista didáctico) en el que los objetos van a estar representados por un punto en dos dimensiones {x,y}. La implementación realizada en este ejemplo permite que los objetos puedan estar representados con más dimensiones, pero sin perder la perspectiva didáctica de este ejemplo los mostramos en dos dimensiones para que podamos visualizar los resultado en un plano y así entender el correcto funcionamiento de este método.

Para implementar el K-means, vamos a tener objetos que serán representados como puntos en 2D, por tanto implementaremos una clase Punto (Point.py) para representar los objetos. Por otro lado se implementa una clase Cluster (Cluster.py) para representar a los Clusters y que estará compuesta por un conjunto de objetos de la clase Punto. Por último tendremos un script (KMeans.py) en el que estará implementado del K-means con sus dos pasos de asignación y actualización para ‘k’ Clusters. A continuación se muestra a un alto nivel de abstracción el diagrama de clases de la implementación propuesta del K-means:

Los data sets a utilizar en este ejemplo (que se encuentran dentro de la carpeta dataSet) van a ser ficheros de texto en los que en cada línea van a estar las coordenadas de cada punto {x,y} separados por el separador “::”. A continuación mostramos un ejemplo de estos ficheros:

1.857611652::2.114033851
2.34822574::1.58264984
1.998326848::4.118143019
1.714362835::2.468639613
1.656134484::1.909955747

Esto quiere decir que el primer punto va a estar posicionado en las coordenadas {1.85,2.11} y el segundo punto en las coordenadas {2.34,1.58}.

Para los ejemplos disponemos de 4 data sets con las siguientes características:

Visto el diagrama de clases y la estructura de los date sets a utilizar, vamos a pasar a mostrar la implementación de la clases Punto (Point.py). A esta clase se le va a pasar en el constructor un “numpy array” con las coordenadas del punto y va a tener como atributos esa coordenada y las dimensiones de la misma, que para el ejemplo que vamos a mostrar será de 2:

class Point:

    def __init__(self, coordinates):
        self.coordinates = coordinates
        self.dimension = len(coordinates)

    def __repr__(self):
        return 'Coordinates: ' + str(self.coordinates) + \
               ' -> Dimension: ' + str(self.dimension)

Por otro lado vamos a tener la clase Cluster (Cluster.py) que se le va a pasar en el constructor una lista de puntos que van a ser los que formen el Cluster. Esta clase va a tener como atributos la lista de puntos del Cluster (points), la dimensión de los puntos (dimension), el centroide del Cluster (centroid) y un atributo (converge) que nos va a indicar si el centroide es igual (por tanto converge) que el calculado en el paso de actualización de la iteración anterior. Con la lista de puntos que van a formar el Cluster, hacemos las comprobaciones pertinentes (que el Cluster tenga por lo menos un punto y que todos los puntos sean de la misma dimensión), para no lanzar ninguna excepción. Veamos a continuación el constructor de esta clase:

import numpy as np

class Cluster:
    
    def __init__(self, points):
        if len(points) == 0:
            raise Exception("Cluster cannot have 0 Points")
        else:
            self.points = points
            self.dimension = points[0].dimension

        # Check that all elements of the cluster have the same dimension
        for p in points:
            if p.dimension != self.dimension:
                raise Exception(
                    "Point %s has dimension %d different with %d from the rest "
                    "of points") % (p, len(p), self.dimension)

        # Calculate Centroid
        self.centroid = self.calculate_centroid()
        self.converge = False

Como se observa en el atributo centroid, se llama al método calculate_centroid() para asignarle el centroide al Cluster en función de la lista de puntos del Cluster. Este método calcula el centroide como el punto medio de todos los puntos que forman el Cluster.

    def calculate_centroid(self):
        
        sum_coordinates = np.zeros(self.dimension)
        for p in self.points:
            for i, x in enumerate(p.coordinates):
                sum_coordinates[i] += x

        return (sum_coordinates / len(self.points)).tolist()

Por otro lado implementamos el método update_cluster(points), que es el método encargado de actualizar el estado del Cluster, calculando el nuevo centroide con los nuevos puntos del Cluster tras el paso de asignación y comprobando si convergen los centroides mirando el valor del centroide del paso anterior y del actual. En resumen, con este método actualizamos el estado del Cluster.

    def update_cluster(self, points):

        old_centroid = self.centroid
        self.points = points
        self.centroid = self.calculate_centroid()
        self.converge = np.array_equal(old_centroid, self.centroid)

Una vez explicadas las Clases Punto y Cluster que necesitamos para estructurar la información, vamos a pasar a explicar la implementación del K-means propiamente dicha. Esta implementación esta en el script KMeans.py que mostramos a continuación y que posteriormente vamos a explicar cada fragmento de código relevante:

import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import distance
from Point import Point
from Cluster import Cluster

# -*- coding: utf-8 -*-
__author__ = 'RicardoMoya'

DATASET1 = "./dataSet/DS_3Clusters_999Points.txt"
DATASET2 = "./dataSet/DS2_3Clusters_999Points.txt"
DATASET3 = "./dataSet/DS_5Clusters_10000Points.txt"
DATASET4 = "./dataSet/DS_7Clusters_100000Points.txt"
NUM_CLUSTERS = 3
ITERATIONS = 1000
COLORS = ['red', 'blue', 'green', 'yellow', 'gray', 'pink', 'violet', 'brown',
          'cyan', 'magenta']


def dataset_to_list_points(dir_dataset):
    """
    Read a txt file with a set of points and return a list of objects Point
    :param dir_dataset:
    """
    points = list()
    with open(dir_dataset, 'rt') as reader:
        for point in reader:
            points.append(Point(np.asarray(map(float, point.split("::")))))
    return points


def get_nearest_cluster(clusters, point):
    """
    Calculate the nearest cluster
    :param clusters: old clusters
    :param point: point to assign cluster
    :return: index of list cluster
    """
    dist = np.zeros(len(clusters))
    for i, c in enumerate(clusters):
        dist[i] = distance.euclidean(point.coordinates, c.centroid)
    return np.argmin(dist)


def print_clusters_status(it_counter, clusters):
    print '\nITERATION %d' % it_counter
    for i, c in enumerate(clusters):
        print '\tCentroid Cluster %d: %s' % (i + 1, str(c.centroid))


def print_results(clusters):
    print '\n\nFINAL RESULT:'
    for i, c in enumerate(clusters):
        print '\tCluster %d' % (i + 1)
        print '\t\tNumber Points in Cluster %d' % len(c.points)
        print '\t\tCentroid: %s' % str(c.centroid)


def plot_results(clusters):
    plt.plot()
    for i, c in enumerate(clusters):
        # plot points
        x, y = zip(*[p.coordinates for p in c.points])
        plt.plot(x, y, linestyle='None', color=COLORS[i], marker='.')
        # plot centroids
        plt.plot(c.centroid[0], c.centroid[1], 'o', color=COLORS[i],
                 markeredgecolor='k', markersize=10)
    plt.show()


def k_means(dataset, num_clusters, iterations):
    # Read data set
    points = dataset_to_list_points(dataset)

    # Select N points random to initiacize the N Clusters
    initial = random.sample(points, num_clusters)

    # Create N initial Clusters
    clusters = [Cluster([p]) for p in initial]

    # Inicialize list of lists to save the new points of cluster
    new_points_cluster = [[] for i in range(num_clusters)]

    converge = False
    it_counter = 0
    
while (not converge) and (it_counter < iterations):
        # Assign points in nearest centroid
        for p in points:
            i_cluster = get_nearest_cluster(clusters, p)
            new_points_cluster[i_cluster].append(p)

        # Set new points in clusters and calculate de new centroids
        for i, c in enumerate(clusters):
            c.update_cluster(new_points_cluster[i])

        # Check that converge all Clusters
        converge = [c.converge for c in clusters].count(False) == 0

        # Increment counter and delete lists of clusters points
        it_counter += 1
        new_points_cluster = [[] for i in range(num_clusters)]

        # Print clusters status
        print_clusters_status(it_counter, clusters)

    # Print final result
    print_results(clusters)

    # Plot Final results
    plot_results(clusters)


if __name__ == '__main__':
    k_means(DATASET1, NUM_CLUSTERS, ITERATIONS)

Lo primero que se hace al ejecutar el script es llamar el método k_means() al que se le pasa como parámetros el data set que contiene el conjunto de puntos, el número de Clusters que queremos obtener y el número máximo de iteraciones a realizar por si no convergen nunca los centroides. Estos parámetros los tenemos definidos como constantes en el script ya que tenemos disponibles 4 data sets.

if __name__ == '__main__':
    k_means(DATASET1, NUM_CLUSTERS, ITERATIONS)

El método k_means() implementa el algoritmo de los K-means tal y como se indica en el pseudocódigo mostrado anteriormente. En primer lugar leemos de un fichero el data set con el método dataset_to_list_points(file) e inicializamos ‘N’ Clusters (num_clusteres) seleccionando de forma aleatoria ‘N’ puntos del data set. Posteriormente iniciamos los pasos de asignación y actualización de los Clusters hasta que estos converjan o hasta que lleguemos al número máximo de iteraciones (iterations). Esto lo hacemos dentro del bucle “While”. En cada iteración asignamos cada uno de los puntos del data set al Cluster que tenga el centroide más cercano (Asignación) con el método get_nearest_cluster() que calcula la distancia euclídea entre el punto y el centroide y devuelve el índice del Cluster con centroide más cercano, y una vez asignados recalculamos los centroides de los Clusters. Posteriormente comprobamos la convergencia de los centroides para ver si seguimos iterando o no. En la implementación vemos los métodos print_clusters_status(), print_results() y plot_results() que son métodos auxiliares que utilizamos para mostrar el estado de los Clusters en cada iteración y mostrar y pintar (con la librería matplotlib) el resultado final:

def k_means(dataset, num_clusters, iterations):

    points = dataset_to_list_points(dataset)

    # INICIALIZACIÓN: Selección aleatoria de N puntos y creación de los Clusters
    initial = random.sample(points, num_clusters)
    clusters = [Cluster([p]) for p in initial]

    # Inicializamos una lista para el paso de asignación de objetos
    new_points_cluster = [[] for i in range(num_clusters)]

    converge = False
    it_counter = 0
    while (not converge) and (it_counter < iterations):
        # ASIGNACION
        for p in points:
            i_cluster = get_nearest_cluster(clusters, p)
            new_points_cluster[i_cluster].append(p)

        # ACTUALIZACIÓN
        for i, c in enumerate(clusters):
            c.update_cluster(new_points_cluster[i])

        # ¿CONVERGE?
        converge = [c.converge for c in clusters].count(False) == 0

        # Incrementamos el contador
        it_counter += 1
        new_points_cluster = [[] for i in range(num_clusters)]

        print_clusters_status(it_counter, clusters)

    print_results(clusters)

    plot_results(clusters)

Veamos a continuación un ejemplo de la ejecución de este script en el que se mostrará el estado de cada Cluster en cada una de las iteraciones hasta la obtención del resultado final. Para el ejemplo utilizaremos el data set 1 (DATASET1) que tiene 999 y que los agruparemos en 3 Clusters:

1. Elección de 3 puntos al azar para inicializar los Clusters. Como cada Cluster será inicializado con un solo punto, ese será su centroide:

CLUSTER 1:
Centroid: [1.537719613, 6.803222336]
Dimension: 2
Puntos: [ 1.53771961  6.80322234]

CLUSTER 2:
Centroid: [4.56416743, 5.372954912]
Dimension: 2
Puntos: [ 4.56416743  5.37295491]

CLUSTER 3:
Centroid: [2.580421023, 2.887390198]
Dimension: 2
Puntos: [ 2.58042102  2.8873902 ]

2. Iniciamos las iteraciones. Primera asignación y actualización de centroides, quedando estos de la siguiente manera:

ITERATION 1
	Centroid Cluster 1: [1.0075506731128203, 6.89332954671282]
	Centroid Cluster 2: [4.965693151866954, 4.989117886197427]
	Centroid Cluster 3: [2.097612910089318, 2.0566417310823106]

3. Iteración 2:

ITERATION 2
	Centroid Cluster 1: [1.0110313303520406, 6.881641713040817]
	Centroid Cluster 2: [4.902010815637452, 4.87296486188048]
	Centroid Cluster 3: [2.0337844236032625, 2.0092213794438396]

4. Iteración 3:

ITERATION 3
	Centroid Cluster 1: [1.0110313303520406, 6.881641713040817]
	Centroid Cluster 2: [4.888163414869566, 4.864725364043481]
	Centroid Cluster 3: [2.0297243138036376, 2.002597935785454]

5. Iteración 4: Convergen los centroides, teniendo los mismos valores que en la iteración 3.

ITERATION 4
	Centroid Cluster 1: [1.0110313303520406, 6.881641713040817]
	Centroid Cluster 2: [4.888163414869566, 4.864725364043481]
	Centroid Cluster 3: [2.0297243138036376, 2.002597935785454]

6. Resultado final y representación:

FINAL RESULT:
	Cluster 1
		Number Points in Cluster 196
		Centroid: [1.0110313303520406, 6.881641713040817]
	Cluster 2
		Number Points in Cluster 253
		Centroid: [4.888163414869566, 4.864725364043481]
	Cluster 3
		Number Points in Cluster 550
		Centroid: [2.0297243138036376, 2.002597935785454]

Tenemos como resultado final (representado en 2D) lo siguiente:

Para el resto de Data Sets tenemos los siguientes resultados pintados en 2 dimensiones:

Resultado final para el Data Set 2 con 999 puntos y 3 Clusters:

Resultado final para el Data Set 3 con 10000 puntos y 5 Clusters:

Resultado final para el Data Set 4 con 100000 puntos y 7 Clusters:

K-means con scikit-learn

En la librería de “scikit-learn” esta implementado el K-means de forma bastante optimizada, pudiendo ser ejecutado de diferentes formas en función de los parámetros que se le pase.

Dado que las librerías en general y esta de Machine Learning en particular evolucionan y son modificadas en el tiempo, no vamos a entrar a explicar cada uno de los parámetros que se le puede pasar al constructor de la clase sklearn.cluster.KMeans() (para eso ya está la documentación de scikit-learn) pero si que vamos a mostrar aquellos parámetros que se consideran importantes para cualquier implementación del K-means.

En la versión 0.17 de la librería (última versión estable hasta la fecha de realización de este libro) el constructor de la clase KMeans presenta los siguientes parámetros (si no se especifican tiene unos valores definidos por defecto):

class sklearn.cluster.KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001,precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=1)

Como parámetros necesarios e importantes a especificar para que la ejecución del K-means sea correcta según el data set utilizado, debemos de definir correctamente los siguientes dos parámetros:

1. n_clusters: Indicaremos el número de Clusters que queremos obtener para agrupar los objetos del data set.
2. max_iter: número máximo de ejecuciones de los pasos de asignación y actualización a realizar en el caso de que no converjan los centroides.

De forma opcional podemos definir una serie de parámetros con los valores que consideremos, siendo los más prácticos (según la opinión del autor) los siguientes:

1. init: indicamos la forma de inicializar los Clusters. Anteriormente se propusieron diferentes formas de inicializar estos Clusters bien sea de forma aleatoria o cogiendo al azar ‘k’ objetos del data set. En este caso se proponen dos forma: una la opción ‘random’ que inicializa los Clusters de forma aleatoria y otra la opción ‘k-means++’ que hace un pequeño pre-procesamiento de los datos del data set para inicializar los Clusters con unos centroides que sean lo suficientemente buenos para que el algoritmo converja rápidamente.
2. tol: Con este valor indicamos el umbral, tolerancia o margen de error para la convergencia de los centroides de los Clusters; es decir, que el valor de los centroides no tiene porque ser iguales de una iteración a otra pero si que su diferencia se inferior a la indicada en este parámetro.
3. n_jobs: Le indicamos el número de hilos (threads) a utilizar.

Una vez construido el objeto de la clase KMeans, debemos de llamar a los métodos pertinentes para que nos agrupe los objetos del data set en los diferentes Clusters. En este caso y para el ejemplo que a continuación mostramos, vamos a llamar el método fit(x) al que pasamos como parámetro una lista de puntos (cada punto en un numpy array) y nos devuelve los centroides de los Clusters (en el atributo cluster_centers_), una lista alineada con la lista de puntos que le pasamos en el que nos dice a que Cluster pertenece cada punto (en el atributo labels_) y la inercia (en el atributo inertia_).

A continuación mostramos el script completo en el que mostramos los resultados del K-means para uno de los 4 data sets:

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

# -*- coding: utf-8 -*-
__author__ = 'RicardoMoya'

# Constant
DATASET1 = "./dataSet/DS_3Clusters_999Points.txt"
DATASET2 = "./dataSet/DS2_3Clusters_999Points.txt"
DATASET3 = "./dataSet/DS_5Clusters_10000Points.txt"
DATASET4 = "./dataSet/DS_7Clusters_100000Points.txt"
NUM_CLUSTERS = 3
MAX_ITERATIONS = 10
INITIALIZE_CLUSTERS = ['k-means++', 'random']
CONVERGENCE_TOLERANCE = 0.001
NUM_THREADS = 8
COLORS = ['red', 'blue', 'green', 'yellow', 'gray', 'pink', 'violet', 'brown',
          'cyan', 'magenta']


def dataset_to_list_points(dir_dataset):
    """
    Read a txt file with a set of points and return a list of objects Point
    :param dir_dataset: path file
    """
    points = list()
    with open(dir_dataset, 'rt') as reader:
        for point in reader:
            points.append(np.asarray(map(float, point.split("::"))))
    return points


def print_results(centroids, num_cluster_points):
    print '\n\nFINAL RESULT:'
    for i, c in enumerate(centroids):
        print '\tCluster %d' % (i + 1)
        print '\t\tNumber Points in Cluster %d' % num_cluster_points.count(i)
        print '\t\tCentroid: %s' % str(centroids[i])


def plot_results(centroids, num_cluster_points, points):
    plt.plot()
    for nc in range(len(centroids)):
        # plot points
        points_in_cluster = [boolP == nc for boolP in num_cluster_points]
        for i, p in enumerate(points_in_cluster):
            if bool(p):
                plt.plot(points[i][0], points[i][1], linestyle='None',
                         color=COLORS[nc], marker='.')
        # plot centroids
        centroid = centroids[nc]
        plt.plot(centroid[0], centroid[1], 'o', markerfacecolor=COLORS[nc],
                 markeredgecolor='k', markersize=10)
    plt.show()


def k_means(dataset, num_clusters, max_iterations, init_cluster, tolerance,
            num_threads):
    # Read data set
    points = dataset_to_list_points(dataset)

    # Object KMeans
    kmeans = KMeans(n_clusters=num_clusters, max_iter=max_iterations,
                    init=init_cluster, tol=tolerance, n_jobs=num_threads)

    # Calculate Kmeans
    kmeans.fit(points)

    # Obtain centroids and number Cluster of each point
    centroids = kmeans.cluster_centers_
    num_cluster_points = kmeans.labels_.tolist()

    # Print final result
    print_results(centroids, num_cluster_points)

    # Plot Final results
    plot_results(centroids, num_cluster_points, points)


if __name__ == '__main__':
    k_means(DATASET1, NUM_CLUSTERS, MAX_ITERATIONS, INITIALIZE_CLUSTERS[0],
            CONVERGENCE_TOLERANCE, NUM_THREADS)

A continuación pasamos a explicar detalladamente como hemos realizado el script. Todo el trabajo se realiza en el método k_means(dataset, num_clusters, max_iterations, init_cluster, tolerance, num_threads) al que se le pasan como parámetros del data set, el número de Clusters, el número máximo de iteracciones, el método de inicialización de los Clusters (random o k-means++), el umbral de convergencia y el número de threads para la ejecución; en resumen, todos los parámetros explicados anteriormente. A este método le vamos a llamar desde el ‘main’, siendo los parámetros que se le pasan constantes definidas al principio del script:

# Constant
DATASET1 = "./dataSet/DS_3Clusters_999Points.txt"
NUM_CLUSTERS = 3
MAX_ITERATIONS = 100
INITIALIZE_CLUSTERS = ['k-means++', 'random']
CONVERGENCE_TOLERANCE = 0.001
NUM_THREADS = 8

----------------------------------------------------------------------------------

if __name__ == '__main__':
    k_means(DATASET1, NUM_CLUSTERS, MAX_ITERATIONS, INITIALIZE_CLUSTERS[0],
            CONVERGENCE_TOLERANCE, NUM_THREADS)

Dentro del método k_means() empezamos leyendo los datos (puntos) del data set del que le indicamos, metiendo esos puntos en una lista de numpy arrays:

def k_means(dataset, num_clusters, max_iterations, init_cluster, tolerance,
            num_threads):
    # Read data set
    points = dataset_to_list_points(dataset)

Inicializamos el objeto de la Clase KMeans (de scikit-learn), pasándole como parámetros el número de Clusters (n_clusters), número máximo de iteraciones (max_iter), forma de inicializar los Clusters (init), el umbral de tolerancia (tol) y el número de threads o ejecuciones en paralelo (n_jobs):

kmeans = KMeans(n_clusters=num_clusters, max_iter=max_iterations,
               init=init_cluster, tol=tolerance, n_jobs=num_threads)

Llamamos al método fit(x) al que le pasamos la lista de puntos (numpy array), para que calcule los centroides de los Clusters, el Cluster al que pertenece cada punto y la inercia:

kmeans.fit(points)

El valor de los centroides y el Cluster al que pertenece cada punto lo tenemos en los atributos cluster_centers_ y labels_ respectivamente, siendo el atributo cluster_centers_ un numpy array de numpy arrays y labels_ una lista de enteros que indica el número del Cluster al que pertenece cada punto del date set:

centroids = kmeans.cluster_centers_
num_cluster_points = kmeans.labels_.tolist()

Por último implementamos dos métodos para imprimir por pantalla los resultados obtenidos (centroides, y número de puntos de cada Cluster) y para pintar (con la librería matplotlib), los centroides y los puntos asignados a cada Cluster:

print_results(centroids, num_cluster_points)
plot_results(centroids, num_cluster_points, points)

Aplicando este script para los 4 data sets propuestos, tenemos los siguientes resultados:

Data Set 1: Resultado final para el Data Set 1 con 999 puntos y 3 Clusters (scikit-learn):

FINAL RESULT:
	Cluster 1
		Number Points in Cluster 550
		Centroid: [ 2.02972431  2.00259794]
	Cluster 2
		Number Points in Cluster 196
		Centroid: [ 1.01103133  6.88164171]
	Cluster 3
		Number Points in Cluster 253
		Centroid: [ 4.88816341  4.86472536]

Data Set 2: Resultado final para el Data Set 2 con 999 puntos y 3 Clusters (scikit-learn):

FINAL RESULT:
	Cluster 1
		Number Points in Cluster 191
		Centroid: [ 2.02022231  4.00032196]
	Cluster 2
		Number Points in Cluster 575
		Centroid: [ 2.04429024  1.99783017]
	Cluster 3
		Number Points in Cluster 233
		Centroid: [ 5.15350073  3.09247426]

Data Set 3: Resultado final para el Data Set 3 con 10000 puntos y 5 Clusters (scikit-learn):

FINAL RESULT:
	Cluster 1
		Number Points in Cluster 1977
		Centroid: [ 3.96715056  5.01607862]
	Cluster 2
		Number Points in Cluster 1999
		Centroid: [ 0.00084638  0.0212526 ]
	Cluster 3
		Number Points in Cluster 2003
		Centroid: [ 7.01565609  5.00501468]
	Cluster 4
		Number Points in Cluster 2009
		Centroid: [ 5.03315337  2.01020813]
	Cluster 5
		Number Points in Cluster 2012
		Centroid: [ 2.01509102  2.96339142]

Data Set 4: Resultado final para el Data Set 3 con 100000 puntos y 7 Clusters (scikit-learn):

FINAL RESULT:
	Cluster 1
		Number Points in Cluster 14235
		Centroid: [ 3.99180237  5.01440659]
	Cluster 2
		Number Points in Cluster 14338
		Centroid: [ 2.0156146   2.99755542]
	Cluster 3
		Number Points in Cluster 14356
		Centroid: [ -5.19034931e-03   5.99360853e+00]
	Cluster 4
		Number Points in Cluster 14285
		Centroid: [ 0.00899975 -0.01445316]
	Cluster 5
		Number Points in Cluster 14273
		Centroid: [ 5.01486554  1.99725272]
	Cluster 6
		Number Points in Cluster 14227
		Centroid: [-1.00989699  2.99240803]
	Cluster 7
		Number Points in Cluster 14286
		Centroid: [ 7.00982285  5.00231668]