PaperlayerView exact revision on arXiv

Source-linked AI summary

Sector-Mean: Deterministic Initialization of K-Means Centroids via Angular Sector Partitioning

Abhiyan Dhakal, Pranish Kafle, Rajani Chulyadyo

arXiv:2609.06468v1cs.LG

TL;DR

K-Means’ results depend heavily on its initial centroids, motivating methods that improve initialization. Sector-Mean partitions two-dimensional data into angular sectors and initializes centroids with sector means. It reduces initialization time relative to K-Means++ and Max-Min while maintaining statistically comparable clustering quality.

  • Problem

    K-Means performance depends heavily on initial centroids, which can affect convergence speed and clustering outcomes.

    Source: §I · p. 1

  • Method

    Sector-Mean deterministically partitions two-dimensional data into angular sectors around the global mean and uses sector-wise means to initialize centroids in O(N) time.

    Source: §I · p. 1

  • Results

    Sector-Mean reduces initialization time by an average of 74.9% compared to K-Means++ and 59.8% compared to Max-Min, with statistically comparable clustering quality.

    Source: A. Computational Efficiency · p. 5, C. Statistical Significance Analysis · p. 6

  • Takeaways & Limitations

    Sector-Mean is a computationally efficient and reproducible alternative for two-dimensional spatial clustering while preserving clustering quality.

    Source: §VII · p. 6

Abstract

from arXiv · show

K-Means is one of the most widely used clustering algorithms, but its susceptibility to initial centroid selection remains a primary bottleneck for its convergence speed and clustering accuracy. This paper proposes Sector-Mean Initialization, a deterministic initialization strategy with O(N) time complexity that partitions the two-dimensional data space into angular sectors around the global centroid and initializes centroids using sector-wise means. We evaluate the method on established two-dimensional benchmarks (SIPU, Birch) and multiple real-world datasets, comparing against random, K-Means++, and Max-Min initialization under identical Lloyd iterations. The statistical analysis of Friedman's test (p<0.05) and Nemenyi post-hoc comparison indicates that, while delivering equivalent clustering quality as K-Means++ and Max-Min, Sector-Mean offers significant computational efficiency. Experimental results show that Sector-Mean reduces the initialization time by 74.9% and 59.8% in comparison to K-Means++ and max-min, respectively. And, it yields the lowest average number of iterations, achieving approximately 5% fewer iterations than K-Means++ and 16% fewer than max-min. These results highlight that Sector-Mean initialization offers a deterministic and computationally efficient initialization strategy while preserving cluster quality.

I. INTRODUCTION

Sector-Mean addresses K-Means’ sensitivity to initial centroids with a deterministic, linear-time initializer for two-dimensional data. The paper situates it among initialization strategies with different trade-offs and evaluates methods in a unified setup.

I. INTRODUCTION

  • K-Means performance depends heavily on initial centroids, and poor choices can slow convergence, destabilize outcomes, and lead to suboptimal solutions.K-Means assigns points to their nearest centroid and updates centroids to assigned-point means until convergence.Source: §I · p. 1

II. RELATED WORKS

  • Prior approaches trade off reproducibility, computational cost, and data-geometry sensitivity: K-Means++ is stochastic, while deterministic partitioning and distance-based methods add other costs or sensitivities.K-Means++ uses probabilistic seeding; Max-Min relies on repeated distances, while divisive methods may add projection, sorting, or recursive operations.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • Sector-Mean partitions two-dimensional data into angular sectors around the global mean and uses sector means as initial centroids, with O(N) time complexity.The paper presents it as deterministic and intended to preserve clustering quality while reducing initialization latency.Source: §I · p. 1
  • The evaluation compares Random, K-Means++, and Max-Min with Sector-Mean across datasets in a common experimental setup.The paper describes systematic comparison under consistent settings as limited in prior work.Source: §I · p. 1
  • Statistical validation reports that Sector-Mean reduces initialization time and iteration count without compromising clustering accuracy.The reported analyses use Friedman’s test and Nemenyi post-hoc comparison.Source: §I · p. 2

II. RELATED WORKS

  • Angular predecessors use geometric information but may require complex selection or sorting, whereas Sector-Mean is presented as a vectorized, single-pass alternative for two-dimensional spatial data.The paper also describes grid methods as potentially ill-suited to irregular clusters and density methods as requiring extra computation.Source: §II · p. 2

III. PROPOSED ALGORITHM

Sector-Mean initializes Lloyd’s algorithm by dividing two-dimensional data into angular sectors relative to the dataset’s global mean. It defines sectors by point angles and uses the mean within each sector as its centroid.

III. PROPOSED ALGORITHM

  • Sector-Mean partitions the input space into k angular sectors relative to the dataset’s global mean to provide a representative, deterministic initial distribution of centroids.The method is presented for initializing Lloyd’s algorithm.Source: §III · p. 2

A. Mathematical Framework

  • The framework defines the global geometric center c as the mean of all data points and measures each point’s angular displacement relative to c.The dataset consists of N points in R2, with k as the desired number of clusters.Source: A. Mathematical Framework · p. 2
  • Each point is assigned by its angle to one of k disjoint sectors, with the angle θi = π assigned to sector k − 1.Sector-Mean uses each sector’s mean as an initial centroid and defaults an empty sector’s centroid to the global mean.Source: A. Mathematical Framework · p. 3

B. Step-by-Step Algorithmic Flow

The section introduces pseudocode for the Sector-Mean algorithm.

B. Step-by-Step Algorithmic Flow

1) Step 1: Compute Global Mean:

The algorithm computes the dataset’s global mean, calculates each point’s angle relative to that mean, and partitions the angular range into equal sectors for assignment.

1) Step 1: Compute Global Mean:

  • The algorithm computes the geometric center of the dataset as the origin for the polar-coordinate transformation.This center is the global mean.Source: 1) Step 1: Compute Global Mean · p. 3

2) Step 2: Calculate Angular Positions:

3) Step 3: Define Angular Sectors:

5) Step 5: Compute Sector Centroids:

Sector-Mean initializes centroids with sector-wise means, using the global mean for empty sectors. The section also outlines the algorithm pseudocode and experimental setup.

5) Step 5: Compute Sector Centroids:

IV. EXPERIMENTAL SETUP

  • Experiments used a controlled local environment, direct Python implementations of the baselines, and the same software configuration across runs.NumPy, Pandas, Matplotlib, and scikit-learn utilities supported computation, analysis, visualization, data handling, and metric computation.Source: §IV · p. 3

C. Pseudocode Implementation

A. Datasets

The evaluation covers 15 two-dimensional datasets, with sample cardinality and the number of clusters summarized in Table I.

A. Datasets

1) Synthetic Datasets:

The dataset suite combines synthetic benchmarks and real-world data projected or represented in two dimensions. All methods use K-Means, differing only in centroid initialization.

1) Synthetic Datasets:

  • SIPU A-series datasets contain 3,000, 5,250, and 7,500 samples with 20, 35, and 50 clusters; S-series each contain 5,000 samples and 15 clusters.Source: 1) Synthetic Datasets · p. 3
  • Birch1–Birch3 each contain 100,000 points distributed across 100 clusters.Source: 1) Synthetic Datasets · p. 4

2) Real World Datasets:

  • Real-world inputs include UJIIndoorLoc and California Housing coordinates, while Iris, Wine, and MNIST are projected to two dimensions with PCA.UJIIndoorLoc has 19,937 samples and 4 clusters; California Housing has 20,640 points and 4 clusters.Source: 2) Real World Datasets · p. 4

B. Clustering Protocol

  • All methods use K-Means and differ only in centroid initialization, with Random, K-Means++, and Max-Min as baselines.Source: B. Clustering Protocol · p. 4

1) Random Initialization:

  • Random initialization samples k centroids uniformly from the data and is susceptible to stochastic variability and poor starts.The passage associates poor initialization with slow convergence and suboptimal local minima, especially for complex or overlapping clusters.Source: 1) Random Initialization · p. 4

2) K-Means++ Initialization:

The section describes K-Means++ and Max-Min baselines and frames evaluation around cluster quality, computational efficiency, and statistical testing.

2) K-Means++ Initialization:

  • K-Means++ chooses its first centroid randomly, then samples each next centroid proportional to squared distance from the nearest chosen centroid.The implementation controls the random seed for reproducibility across repeated runs.Source: 2) K-Means++ Initialization · p. 4

3) Max-Min Initialization:

  • Max-Min starts with a random centroid and then selects the point farthest from previously chosen centroids, favoring dispersed centers.Its reliance on extreme distances makes it sensitive to outliers and uneven-density clusters.Source: 3) Max-Min Initialization · p. 4

V. EVALUATION

  • Evaluation assesses cluster quality and computational efficiency across datasets, with statistical tests used to assess whether performance differences are consistent.Source: §V · p. 4

A. Evaluation Metrics

  • Clustering quality is assessed with both internal optimization measures and external clustering-quality metrics.Source: A. Evaluation Metrics · p. 4

1) Inertia (Sum of Squared Errors, SSE):

This section defines the cluster-quality and runtime metrics, external-label checks, and cross-dataset significance procedure used to compare initialization strategies.

1) Inertia (Sum of Squared Errors, SSE):

  • Inertia is the total sum of squared distances from data points to their assigned centroids; lower values indicate more cohesive clusters.It also reflects optimization of the clustering objective.Source: 1) Inertia (Sum of Squared Errors, SSE) · p. 4

2) Computational Efficiency:

  • Efficiency is measured by centroid-initialization time, total clustering runtime, and iterations to convergence.These indicators represent the computational overhead of each initialization strategy.Source: 2) Computational Efficiency · p. 4

3) Silhouette Coefficient:

  • Silhouette scores range from −1 to 1 and assess within-cluster compactness alongside between-cluster separation.For scalability, scores use a random subsample of 10,000 observations.Source: 3) Silhouette Coefficient · p. 4

4) External Validation (ARI and NMI):

  • When ground-truth labels are available, ARI and NMI measure agreement between predicted clusters and true class distributions.Values near 1 indicate strong alignment with ground truth; results are reported in the appendix.Source: 4) External Validation (ARI and NMI) · p. 4

B. Statistical Significance Analysis

  • The analysis uses Friedman tests and, when significant at α = 0.05, Nemenyi pairwise tests; CD diagrams summarize average method ranks.Metrics are ranked according to whether lower or higher values are better.Source: B. Statistical Significance Analysis · p. 4

VI. RESULTS AND DISCUSSION

The results compare initialization strategies on runtime and convergence, with Sector-Mean showing faster average initialization and a lower Birch1 iteration count.

VI. RESULTS AND DISCUSSION

  • The evaluation examines efficiency-quality trade-offs with non-parametric validation; Table IV compares strategies across 15 datasets at α = 0.05.Source: §VI · p. 4, Table IV · p. 5

A. Computational Efficiency

B. Clustering Quality

Sector-Mean has clustering quality comparable to K-Means++ and Max-Min in statistical comparisons, while the conclusion emphasizes its efficiency for two-dimensional clustering.

C. Statistical Significance Analysis

B. Clustering Quality

VII. CONCLUSION

  • The conclusion frames Sector-Mean as a deterministic O(N) initialization alternative for 2D spatial clustering, with gains in initialization time and convergence iterations.Source: §VII · p. 6
Loading 2609.06468v1…