BalancedKmeansClustering: Balanced k-Means Clustering Using BKM+

In FCPS: Fundamental Clustering Problems Suite

Balanced k-Means Clustering Using BKM+

Description

Performs balanced k-means clustering using an independent base-R implementation of Balanced k-Means Revisited (BKM+) [de Maeyer et al., 2023].

The method combines squared-Euclidean k-means optimization with an adaptive cluster-size penalty. It searches for a partition whose difference between the largest and smallest cluster sizes does not exceed MaxDiff, while retaining a low total within-cluster sum of squares.

Usage

BalancedKmeansClustering(
  Data,
  ClusterNo = 2,
  MaxDiff = 1,
  IterMax = 1000,
  Switch = 10,
  Nstart = 1,
  Centers = NULL,
  Seed = NULL,
  PartlyRemainingFraction = 0.15,
  IncreasingPenaltyFactor = 1.01,
  UseFunctionIter = TRUE,
  StopWhenBalanced = FALSE,
  PlotIt = FALSE,
  Verbose = FALSE,
  KeepHistory = TRUE
)

Arguments

Data	[1:n,1:d] matrix containing the dataset to be clustered. It consists of n cases of d-dimensional data points. Every case has d attributes, variables or features.
ClusterNo	Positive integer number of clusters. It must lie between one and the number of observations.
MaxDiff	Non-negative integer giving the largest permitted difference between the largest and smallest cluster sizes. Default is 1. MaxDiff = 0 requests equal cluster sizes and is feasible only when ClusterNo divides the number of observations.
IterMax	Positive integer maximum number of adaptive-penalty iterations per start. Default is 1000.
Switch	Non-negative integer maximum number of pairwise switch-refinement passes. Switch = 0 disables this refinement. Default is 10.
Nstart	Positive integer number of initializations. Default is 1. If Centers is supplied, Nstart must equal one.
Centers	Optional initial centroid matrix with ClusterNo rows and the same number of columns as Data. Values must be finite and real. Default is NULL.
Seed	NULL or one non-negative integer used for random initialization. An explicit seed is local to the function call: the previous global random-number-generator state is restored on exit, including after errors. With Seed = NULL, initialization advances the ordinary R random number stream.
PartlyRemainingFraction	Finite numeric scalar strictly between zero and one. It supplies the fractional term used in the adaptive cluster-size penalty after an observation is temporarily removed from its current cluster. Default is 0.15.
IncreasingPenaltyFactor	Finite numeric scalar at least one. Constant multiplier used to increase the balancing penalty when UseFunctionIter = FALSE. Default is 1.01.
UseFunctionIter	Logical scalar. If TRUE, an iteration-dependent penalty multiplier is used. If FALSE, IncreasingPenaltyFactor is used. Default is TRUE.
StopWhenBalanced	Logical scalar. If TRUE, a feasible size-balanced iteration that no longer improves the best feasible SSE may terminate the balancing phase. Default is FALSE.
PlotIt	Logical scalar. If TRUE, plots the selected clustering with ClusterPlotMDS(). At least three observations are required. Default is FALSE.
Verbose	Logical scalar. If TRUE, reports the SSE, cluster-size difference, and termination status for every start. Default is FALSE.
KeepHistory	Logical scalar. If TRUE, retains balancing and switch-refinement histories in the returned object. Default is TRUE.

Details

Feature data only

BKM+ updates arithmetic centroids in the original feature space. In addition to objects of class "dist", a finite numeric square matrix is rejected as a distance matrix when it is approximately symmetric, has an approximately zero diagonal, and has no materially negative entries. A square feature matrix that also has all of these properties is therefore ambiguous and is rejected deliberately.

Initialization

If Centers = NULL, ClusterNo observations are sampled without replacement as initial centers. Initial assignment uses squared Euclidean distance and chooses the first cluster in exact ties.

Duplicate observations or supplied centers may create empty initial clusters. Each empty cluster is initialized with a high-error observation taken from a non-singleton donor cluster. This repair is confined to initialization.

Adaptive-penalty balancing

The algorithm performs sequential observation reassignments. It never removes an observation from a singleton cluster. Candidate target clusters are evaluated using squared centroid distance and an adaptive cluster-size penalty.

A partition is considered balanced when

\max_k n_k - \min_k n_k \leq \mathrm{MaxDiff}.

The best feasible assignment is retained according to total within-cluster SSE. A stored feasible assignment is not discarded if the iteration limit is subsequently reached.

When UseFunctionIter = TRUE, the next finite penalty threshold is multiplied by

1.1009 - 0.0009 s

for iteration step s \leq 100, and by 1.01 thereafter. When UseFunctionIter = FALSE, IncreasingPenaltyFactor is used.

Switch refinement

After the balancing phase, the algorithm considers pairwise exchanges of observations between clusters. Exchanges are accepted when they reduce total within-cluster SSE. Because observations are exchanged in pairs, cluster sizes remain unchanged.

Multiple starts

Feasible starts always outrank infeasible starts. Among feasible starts, the smallest total within-cluster SSE is selected. Among infeasible starts, the smallest cluster-size difference is selected first, with SSE used as a tie-breaker.

Classification and output order

The classification is represented consistently by Cls. It is a numerical vector with labels 1:ClusterNo. No post-fitting sorting or renumbering by centroid coordinates is applied. Thus Cls[i] always refers to Data[i, ], and all cluster-indexed outputs use the same native cluster numbering in contrast to the referenced algorithm in C.

Detailed object fields

The returned Object includes:

Cls

Same numerical cluster vector as the main output.

centers

Final centroid matrix.

size

Cluster sizes.

withinss

Within-cluster SSE by cluster.

tot.withinss

Total within-cluster SSE.

MSE

tot.withinss / n.

iter

Balancing iterations executed.

best.iter

Iteration associated with the retained assignment.

penalty

Penalty associated with the retained assignment.

last.penalty

Final penalty reached by the balancing loop.

maxdiff

Final maximum cluster-size difference.

balanced

Whether maxdiff <= MaxDiff.

hard.balanced

Whether maxdiff <= 1.

converged

Balancing convergence indicator.

termination

Character termination reason.

initial.centers

Initial centers of the selected start.

initial.empty.clusters

Number of repaired empty initial clusters.

sse.before.switch

SSE before switch refinement.

switch.iter

Number of switch passes.

switches

Total number of exchanged observation pairs.

switch.converged

Switch-refinement convergence indicator.

history

Balancing history when requested.

switch.history

Switch-pass history when requested.

nstart

Number of requested starts.

starts

Summary data frame for all starts.

best.start

Index of the selected start.

maxdiff.requested

Requested maximum size difference.

parameters

Principal input parameters.

call

Matched call.

Value

A list with components:

Cls	Numerical vector of length n containing integer-valued cluster labels from 1 through ClusterNo. Element Cls[i] is the cluster assigned to row i of Data. The input-row order and the native cluster numbering of the selected run are preserved.
Object	Detailed BKM+ result. Important fields include Cls, centers, size, withinss, tot.withinss, MSE, iter, best.iter, penalty, last.penalty, maxdiff, balanced, hard.balanced, converged, termination, initial.centers, initial.empty.clusters, sse.before.switch, switch.iter, switches, switch.converged, history, switch.history, nstart, best.start, starts, maxdiff.requested, parameters, and call. Object$Cls is identical to the main output Cls.
Centroids	Final centroid matrix, identical to Object$centers. Row j corresponds to cluster j in Cls.

Author(s)

Michael Thrun

References

[de Maeyer et al., 2023] de Maeyer, R., Sieranoja, S., and Franti, P.:Balanced k-means revisited, Applied Computing and Intelligence, 3(2), 145-179. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.3934/aci.2023008")}, 2023

See Also

kmeansClustering, kmeans

Examples

data('Hepta')

out=BalancedKmeansClustering(Hepta$Data,ClusterNo = 7,PlotIt=FALSE)

## Not run: 
set.seed(1)

Data <- rbind(
  matrix(rnorm(60, mean = 0), ncol = 2),
  matrix(rnorm(60, mean = 5), ncol = 2)
)

result <- BalancedKmeansClustering(
  Data = Data,
  ClusterNo = 2,
  MaxDiff = 1,
  Nstart = 10,
  Seed = 123
)

table(result$Cls)
result$Centroids
result$Object$tot.withinss

## End(Not run)

FCPS documentation built on Oct. 3, 2026, 9:06 a.m.