K-Means Clustering

The selection of initial cluster centers critically impacts convergence speed and the quality of the recovered constellation. Random initialization can lead to suboptimal local minima, while K-Means++ intelligently spreads initial centroids across the IQ plane to improve consistency. In signal processing, domain-specific initialization using constant modulus pre-scaling or angular histogram peaks often outperforms generic methods by leveraging the geometric structure of digital modulations.

The core objective function, often called inertia, quantifies the compactness of clusters by summing the squared Euclidean distances between each IQ sample and its assigned centroid. The algorithm iteratively executes two steps:

• Assignment Step: Each sample is assigned to the nearest centroid, forming Voronoi regions.
• Update Step: Centroids are recomputed as the arithmetic mean of all samples in their region. This process monotonically decreases WCSS until convergence, effectively acting as a blind minimum-distance decoder.

A raw K-Means output recovers the relative geometry of the constellation but not its absolute phase orientation. The resulting cluster centers will exhibit an arbitrary fixed rotational offset. This phase ambiguity is typically resolved in post-processing by:

• Computing the fourth-power phase estimator for QPSK-like symmetries.
• Aligning the recovered centroids with a known unique word or pilot sequence.
• Applying differential decoding to render the absolute rotation irrelevant.

The number of clusters K corresponds to the modulation order M (e.g., K=4 for QPSK, K=16 for 16-QAM). When M is unknown, it is estimated using validation metrics:

• Elbow Method: Plotting WCSS against increasing K to identify the point of diminishing returns.
• Silhouette Analysis: Measuring how similar a sample is to its own cluster compared to neighboring clusters.
• Gap Statistic: Comparing the WCSS curve to its expectation under a null reference distribution of the data.

K-Means is inherently sensitive to additive white Gaussian noise (AWGN) and impulsive outliers because the squared Euclidean distance heavily penalizes large deviations. A single high-noise sample can significantly skew a centroid estimate. Mitigation strategies include:

• Preprocessing with a median filter to suppress impulse noise.
• Using K-Medoids, which selects actual data points as centers, for improved robustness.
• Applying data cleaning to discard samples with an EVM exceeding a statistical threshold before clustering.

The standard Lloyd's algorithm has a complexity of O(n * K * d * i), where n is the number of IQ samples, d is the dimensionality (2 for IQ data), and i is the number of iterations. For real-time spectrum classification, this can be prohibitive. Acceleration techniques include:

• Mini-batch K-Means, which processes random subsets of samples per iteration.
• Triangle inequality acceleration (Elkan's algorithm) to skip unnecessary distance calculations.
• Hardware implementation on FPGAs using parallel distance computation pipelines.

The process of calculating the geometric center of a cluster of received IQ samples, typically by averaging, to estimate the location of the original transmitted constellation point. In K-Means, the algorithm iteratively refines these centroids by minimizing the within-cluster sum of squares (WCSS). Accurate centroid estimation is the direct output of convergence, providing a blind estimate of the transmitted symbol locations without prior knowledge of the modulation format.

A probabilistic model that represents the distribution of received IQ samples as a weighted sum of Gaussian components, each corresponding to a constellation point. Unlike K-Means' hard assignment, a GMM provides soft, probabilistic cluster memberships using the Expectation-Maximization (EM) algorithm. This is a direct upgrade over K-Means for modulation classification, as it accounts for the variance of noise clouds around each ideal constellation point.

An optimal detection strategy that classifies a received signal point by selecting the constellation symbol with the smallest Euclidean distance to the observation. K-Means clustering implicitly performs this operation: once centroids are estimated, new incoming symbols are assigned to the nearest centroid. This is the decision-making step that follows clustering, minimizing the probability of symbol error in additive white Gaussian noise (AWGN).

The convex polygon surrounding a constellation point that contains all locations in the IQ plane closer to that point than to any other. K-Means partitions the signal space into these regions, defining the decision boundaries for demodulation. The algorithm's convergence effectively constructs a Voronoi tessellation of the complex plane, where each region corresponds to a cluster and its associated centroid.

A quantitative metric measuring the Euclidean distance between the ideal reference constellation point and the actual received signal point. After K-Means estimates the centroids, EVM can be calculated by comparing each received sample to its assigned centroid. This provides a single figure of merit for modulation fidelity, quantifying the combined impact of noise, interference, and hardware impairments on the recovered constellation.

A signal processing technique that recovers the original transmitted constellation from a distorted received signal without requiring a known training sequence. K-Means clustering is a form of blind processing, as it directly partitions the received IQ cloud into clusters. When combined with algorithms like the Constant Modulus Algorithm (CMA), clustering can help initialize equalizer taps or directly estimate the distorted constellation geometry.