Principles and implementation of k-means and k-means++ in python

# Define the Euclidean distance
import numpy as np
def get_distance(x1, x2):
    return (((x1-x2)))

import random
# Define the center initialization function, the center point is chosen as the sample feature
def center_init(k, X):
    n_samples, n_features = 
    centers = ((k, n_features))
    selected_centers_index = []
    for i in range(k):
        # Each cycle randomly selects a category center, determining not to duplicate centers
        sel_index = (list(set(range(n_samples))-set(selected_centers_index)))
        centers[i] = X[sel_index]
        selected_centers_index.append(sel_index)
    return centers

# Determines how close a sample point is to a center, the index of the center is returned.
## For example, if there are three center points, the return is 0, 1, 2 ##
def closest_center(sample, centers):
    closest_i = 0
    closest_dist = float('inf')
    for i, c in enumerate(centers):
        # Select the category to which the centroid with the smallest distance belongs based on the Euclidean distance judgment
        distance = get_distance(sample, c)
        if distance < closest_dist:
            closest_i = i
            closest_dist = distance
    return closest_i

# Define the process of constructing clusters
# The content of each clustering store is an index of the sample, i.e., clustering on the sample index, for ease of operation
def create_clusters(centers, k, X):
    clusters = [[] for _ in range(k)]
    for sample_i, sample in enumerate(X):
        # Classify samples into the nearest category area
        center_i = closest_center(sample, centers)
        # Indexes where samples are stored
        clusters[center_i].append(sample_i)
    return clusters

# Calculate new centroids based on the clustering results from the previous step
def calculate_new_centers(clusters, k, X):
    n_samples, n_features = 
    centers = ((k, n_features))
    # With the current mean of each class sample as the new center point
    for i, cluster in enumerate(clusters):  # cluster is the index of each class after categorization
        new_center = (X[cluster], axis=0) # Average by column
        centers[i] = new_center
    return centers

# Get the clustering category to which each sample belongs
def get_cluster_labels(clusters, X):
    y_pred = ((X)[0])
    for cluster_i, cluster in enumerate(clusters):
        for sample_i in cluster:
            y_pred[sample_i] = cluster_i
            #print('Group the sample {} into {} classes'.format(sample_i,cluster_i))
    return y_pred

# Define the kmeans algorithm flow based on each of the above processes
def Mykmeans(X, k, max_iterations,init):
    # 1. Initialize the center point
    if init == 'kmeans':
        centers = center_init(k, X)
    else: centers = get_kmeansplus_centers(k, X)
    # Iterate over the solution
    for _ in range(max_iterations):
        # 2. Clustering based on current centroids
        clusters = create_clusters(centers, k, X)
        # Save the current center point
        pre_centers = centers
        # 3. Calculate new centroids based on clustering results
        new_centers = calculate_new_centers(clusters, k, X)
        # 4. Set the convergence condition as whether the center point changes or not
        diff = new_centers - pre_centers
        # Explain that the center point has not changed, stop updating
        if () == 0:
            break
    # Return the final clustering labels
    return get_cluster_labels(clusters, X)

# Test execution
X = ([[0,2],[0,0],[1,0],[5,0],[5,2]])
# Set the clustering categories to 2 and the maximum number of iterations to 10
labels = Mykmeans(X, k = 2, max_iterations = 10,init = 'kmeans')
# Print the label of the category to which each sample belongs
print("Final categorized results",labels)
## The output is [1. 1. 1. 0. 0.]

# Verify with sklearn
from  import KMeans
X = ([[0,2],[0,0],[1,0],[5,0],[5,2]])
kmeans = KMeans(n_clusters=2,init = 'random').fit(X)
# The results may be different due to the randomness of center
print(kmeans.labels_)

## Getting the kmean++ center point
def get_kmeansplus_centers(k, X):
    n_samples, n_features = 
    init_one_center_i = (range(n_samples))
    centers = []
    (X[init_one_center_i])
    dists = [ 0 for _ in range(n_samples)]

    # Execution
    for _ in range(k-1):
        total = 0
        for sample_i,sample in enumerate(X):
            # Get the shortest distance
            closet_i = closest_center(sample,centers)
            d = get_distance(X[closet_i],sample)
            dists[sample_i] = d
            total += d
        total = total * ()

        for sample_i,d in enumerate(dists): # Roulette wheel method to select the next clustering center
            total -= d
            if total > 0:
                continue
            # Pick a new center point
            (X[sample_i])
            break
    return centers

X = ([[0,2],[0,0],[1,0],[5,0],[5,2]])
# Set the clustering categories to 2 and the maximum number of iterations to 10
labels = Mykmeans(X, k = 2, max_iterations = 10,init = 'kmeans++')
print("Final categorized results",labels)
## The output is [1. 1. 1. 0. 0.]

# Verify with sklearn
X = ([[0,2],[0,0],[1,0],[5,0],[5,2]])
kmeans = KMeans(n_clusters=2,init='k-means++').fit(X)
print(kmeans.labels_)