K-Means Clustering (K-Means Clustering)

Definition

K-Means is a classic centroid-based clustering algorithm that partitions data into $K$ clusters, minimizing the sum of squared Euclidean distances from data points to cluster centroids. K-Means is simple and efficient, widely used in data mining, pattern recognition, and image segmentation.

Algorithm Principles

Objective Function

K-Means aims to minimize the sum of squared errors (SSE):

Where $\boldsymbol{\mu}_i$ is the centroid of the $i$-th cluster and $\mathcal{C}_i$ is the set of data points in the $i$-th cluster.

Algorithm Steps

1. Randomly initialize $K$ centroids
2. Repeat until convergence:
   • Assignment step: Assign each data point to the nearest centroid
   • Update step: Recalculate each cluster's centroid as the mean of data points in the cluster

Convergence

K-Means algorithm is guaranteed to converge after finite iterations but may get stuck in local optima. The commonly used $K$-Means++ initialization method improves initial centroid selection.

Application in Cislunar SSA Architecture Analysis

Klonowski (2025) used K-Means and K-Medoids clustering methods to classify Pareto-optimal architectures in cislunar space SSA architecture design:

Feature Extraction

Extract feature vectors from architecture configurations:

• Number of observation satellites
• Orbital family distribution
• Coverage performance metrics
• Cost metrics

Clustering Analysis

1. Apply K-Means clustering to the Pareto optimal solution set
2. Identify different types of architecture configurations
3. Analyze characteristics and applicable scenarios of each cluster

Core Elements

Mathematical Definition

K-Means partitions dataset $\mathcal{X} = \{\mathbf{x}_1, ..., \mathbf{x}_N\}$ into $K$ disjoint clusters $\mathcal{C} = \{\mathcal{C}_1, ..., \mathcal{C}_K\}$, minimizing the SSE objective function.

Key Properties

K-Means time complexity is $O(I \cdot N \cdot K \cdot d)$, where $I$ is number of iterations, $N$ is number of data points, $K$ is number of clusters, and $d$ is dimensionality. The algorithm assumes spherical clusters of similar size.

Comparison with K-Medoids

Related Concepts

• K-Medoids Clustering
• NSGA II
• Pareto Optimality

References

• MacQueen J. Some methods for classification and analysis of multivariate observations[C]. Berkeley Symposium on Mathematical Statistics and Probability, 1967.
• Klonowski M, Owens-Fahrner N, Heidrich C, et al. Cislunar space domain awareness architecture design and analysis for cooperative agents[J]. The Journal of the Astronautical Sciences, 2024.