K-Means++ Clustering – Files

Custom Python component for Grasshopper which gives a lot of freedom to tweak the parameters and customization of the standard algorithm, such as for example comparative studies of different feature vector set-ups.

Our OpenAccess eCAADe 2025 Paper “Condensing Complexity: K-means clustering of geometric data sets as a design tool” – documenting our approach and usage – can be found on:

ResearchGate:
https://www.researchgate.net/publication/401344242_Condensing_Complexity_K-means_clustering_of_geometric_data_sets_as_a_design_tool

CumInCAD:
https://papers.cumincad.org/cgi-bin/works/paper/ecaade2025_521

Python 3 code component for Rhino 8+Grasshopper:

k-means_pp.gh (as ZIP file)Download

Python 3 code for Rhino 8+Grasshopper code as a .py file:

k-means_pp.py (as ZIP file)Download

Python 3 for Rhino 8+Grasshopper code as plain text:

import math
import random as rnd
import ghpythonlib.treehelpers as th

# Function to remap a value from one range to another
def translate(value, leftMin, leftMax, rightMin, rightMax):
    leftSpan = leftMax - leftMin
    rightSpan = rightMax - rightMin
    valueScaled = (value - leftMin) / leftSpan
    return rightMin + (valueScaled * rightSpan)

# Function to normalize values to a target range [0, 1]
def normalize_values(lst, min_val, max_val):
    return [
        [translate(value, min_val, max_val, 0, 1) for value in sublist] 
        for sublist in lst
    ]

# Euclidean distance function for two vectors
def vector_dist(v1, v2):
    return math.sqrt(sum((v2[i] - v1[i])**2 for i in range(len(v1))))

# KMeans++ initialization: Select initial cluster centers
def kMeansPlusPlusInitialization(vals, cls_num, first_center_index):
    if not ini:
        rnd.seed(42)  # Set fixed seed for deterministic results
        
    cluster_centers = [] 
    first_center = vals[first_center_index]  # Choose first cluster center manually via component input
    cluster_centers.append(first_center)
    
    for _ in range(1, cls_num):
        distances = [
            min(vector_dist(val, center) for center in cluster_centers) 
            for val in vals
        ]
        total_distance = sum(distances)
        probabilities = [dist / total_distance for dist in distances]

        cumulative_probabilities = []
        cumulative_sum = 0
        for p in probabilities:
            cumulative_sum += p
            cumulative_probabilities.append(cumulative_sum)
        
        r = rnd.random()
        for i, cumulative_prob in enumerate(cumulative_probabilities):
            if r < cumulative_prob:
                cluster_centers.append(vals[i])
                break
    
    return cluster_centers

# Main K-Means clustering algorithm
def kMeanClustering(vals, pt_geometry, cls_num, iterations, first_center_index):
    # Normalize the input values
    norm_list = normalize_values(vals, min_val, max_val)
    
    # Initialize cluster centers using KMeans++
    cluster_centers = kMeansPlusPlusInitialization(norm_list, cls_num, first_center_index)
    
    for _ in range(iterations):
        clusters = [[] for _ in cluster_centers]
        clusters_ids = [[] for _ in cluster_centers]
        geom_clusters = [[] for _ in cluster_centers]
        
        for i, norm_val in enumerate(norm_list):
            # Find the closest cluster center for each value
            distances = [vector_dist(norm_val, center) for center in cluster_centers]
            best_center_id = distances.index(min(distances))
            
            clusters[best_center_id].append(norm_val)
            clusters_ids[best_center_id].append(i)
            geom_clusters[best_center_id].append(pt_geometry[i])
        
        # Update cluster centers as the mean of assigned points
        for i, cluster in enumerate(clusters):
            if cluster:
                new_center = [sum(dim) / len(cluster) for dim in zip(*cluster)]
                cluster_centers[i] = new_center
            else:
                cluster_centers[i] = rnd.choice(norm_list)
    
    # Compute geometric averages
    avg_geometry = []
    for cluster in geom_clusters:
        if cluster:
            avg_geom = [sum(dim) / len(cluster) for dim in zip(*cluster)]
            avg_geometry.append(avg_geom)
        else:
            avg_geometry.append([])
    
    # Map the cluster centers back to the original domain
    mapped_centers = [
        [translate(center[i], 0, 1, min_val, max_val) for i in range(len(center))]
        for center in cluster_centers
    ]
    
    # Return cluster IDs, mapped cluster centers, and geometric averages as Grasshopper DataTrees
    return th.list_to_tree(clusters_ids), th.list_to_tree(mapped_centers), th.list_to_tree(avg_geometry)

# Main script execution
# Flattened input: Extract values from Grasshopper tree structure
values = [[item for item in branch] for branch in feature_vector.Branches]
pt_geom = [[item for item in branch] for branch in pt_geometry.Branches]

# Compute min_val and max_val for the entire dataset
all_values = [item for sublist in values for item in sublist]
min_val = min(all_values)
max_val = max(all_values)

# Perform clustering
ids, avg_feature_vector, avg_geometry = kMeanClustering(values, pt_geom, clusters, iterations, first_center_index)

This work and all files related to it are shared under the Creative Commons: Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) Licence.

← Back to Repository