<jupyter_start><jupyter_text>Tarea 4. Algoritmo K-Means. Imagen recuperada de: https://upload.wikimedia.org/wikipedia/commons/e/ea/K-means_convergence.gif___  1. Programar el algoritmo K-Means en una función. 1. Inicialización aleatoria de los centroides: para este punto, podemos elegir $k$ puntos aleatorios sobre los que queremos llevar a cabo el clustering como centroides.   La función `np.random.randint` puede ser de mucha utilidad.<jupyter_code># Import numpy
import numpy as np
def init_centroids(X, k):
    """
    Centroids initialization for K-Means algorithm.
    :param X: Data.
    :param int k: Number of clusters.
    :return: Randomly chosen centroids.
    """
    # Dimension
    N, d = X.shape
    
    # Choose k random points from X (Hint: Use np.random.randint(N, size=k)
    # Your code goes here:
    centroids = ...
    
    # The centroids must be a k x d array.
    assert centroids.shape == (k, d)
    
    return centroids<jupyter_output><empty_output><jupyter_text>2. Encontrar centroide más cercano: para este punto, debemos calcular las distancias (norma 2) de cada punto a cada centroide, y después encontrar el centroide más cercano de acuerdo a estas distancias.   La función `np.linalg.norm` puede ser de mucha utilidad.<jupyter_code>def closest_centroids(X, centroids):
    """
    Find the closest centroid to each data point.
    :param X: Data.
    :param centroids: k x d array of centroids.
    :return: Cluster ids assigned to each data point.
    """
    # Dimension
    N, d = X.shape
    # Number of clusters
    k = centroids.shape[0]
    
    # Distances initialization: Position i,j corresponds to the distance from point i to centroid j
    distances = np.zeros((N, k))
    
    for j in range(k):
        # Calculate the distances from all points to centroid j (Hint: Use np.linalg.norm(., axis=1))
        # Your code goes here:
        distances[:, j] = ...
    
    # Get the closest centroid to each data point
    return distances.argmin(axis=1)<jupyter_output><empty_output><jupyter_text>3. Actualizar centroides: para este punto, debemos actualizar los centroides como la media de los puntos asignados a cada centroide.   La función `np.mean` puede ser de mucha utilidad.<jupyter_code>def update_centroids(X, cluster_id, k):
    """
    Find the closest centroid to each data point.
    :param X: Data.
    :param cluster_id: Array of cluster ids.
    :param int k: Number of clusters.
    :return: Updated centroids.
    """
    # Dimension
    N, d = X.shape
    
    # Centroids initialization
    centroids = np.zeros((k, d))
    
    for j in range(k):
        # Update the centroid j as the mean of the points belonging to cluster j (Hint: Use .mean(., axis=0) method)
        # Your code goes here:
        centroids[j, :] = ...
    
    # Updated centroids
    return centroids<jupyter_output><empty_output><jupyter_text>Con lo anterior, el algoritmo K-Means lo podemos escribir de la siguiente manera:<jupyter_code>def kmeans(X, k, max_iter=1000):
    """
    This function implements the K-Means algorithm.
    :param X: Data.
    :param int k: Number of clusters.
    :param int max_iter: Maximum number of iterations.
    :return: Cluster ids and centroids.
    """
    # Parameter validation
    N, d = X.shape
    if k >= N:
        raise ValueError(f"The number of clusters k={k} must be less than the number of data points N={N}.")
    
    # Centroids initialization
    centroids = init_centroids(X, k)

    # Cluster id initialization
    cluster_id_aux = -np.ones(N)
    
    # Repeat until convergence
    i = 0
    while i < max_iter:
        print(i)
        # For each point find the closest centroid to assign the cluster
        cluster_id = closest_centroids(X, centroids)
        
        # Update centroids
        centroids = update_centroids(X, cluster_id, k)
        
        # Check convergence
        if np.linalg.norm(cluster_id - cluster_id_aux) == 0:
            break
        else:
            cluster_id_aux = cluster_id
        
        i += 1
    
    return cluster_id, centroids<jupyter_output><empty_output><jupyter_text>Ahora, probemos nuestro algoritmo:<jupyter_code># Importamos función para generar datos
from bank_customer_data import generate_bank_customer_data
# Importamos pyplot
from matplotlib import pyplot as plt
# Generamos datos
data = generate_bank_customer_data()
c_id, centroids = kmeans(data[["income", "debt"]].to_numpy(), k=3)
# Gráfico
plt.scatter(data["income"], data["debt"], c=c_id, cmap="Accent", alpha=0.6)
plt.plot(centroids[0, 0], centroids[0, 1], "*g", ms=20)
plt.plot(centroids[1, 0], centroids[1, 1], "*b", ms=20)
plt.plot(centroids[2, 0], centroids[2, 1], "*k", ms=20)
plt.xlabel("Ingresos mensuales (x100k MXN)")
plt.ylabel("Deuda (x100k MXN)")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09727707337351901, 'fraction_numerical': 0.00914570775306589, 'mean_word_length': 3.155440414507772, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 22, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '391951', 'license': 'MIT', 'n_tokens_mistral': 1617, 'n_tokens_neox': 1608, 'n_words': 514, 'path': 'modulo2/tema1/tarea4.ipynb', 'repo_name': 'luismaria8992ramirez/mebo2021', 'size': '4811'}