[Bug] KMeansSMOTE fails when clusters have identical points and generates more samples than requested

[saitejabandaru-in]

Describe the bug

When using KMeansSMOTE, two issues occur:

1. ValueError due to identical points in valid clusters:
   If a dataset contains duplicates or discrete features such that all points in some valid clusters are identical, the Euclidean distances between them will be 0. This results in cluster_sparsities = 0 for all valid clusters. When computing cluster_weights, it attempts to divide by cluster_sparsities.sum() which is 0, resulting in an array of NaNs. The subsequent call to math.ceil() raises ValueError: cannot convert float NaN to integer.

2. Excessive generated samples:
   KMeansSMOTE relies on math.ceil for computing the number of samples each cluster should generate:

   cluster_n_samples = int(
       math.ceil(n_samples * cluster_weights[valid_cluster_idx])
   )

   Because math.ceil is applied to each cluster independently, the total number of generated samples can exceed the total n_samples requested in sampling_strategy. For example, if n_samples=3 and weight is 0.5, ceil(1.5)=2. So 2 clusters generate 2+2=4 samples total, exceeding the requested 3. fit_resample then returns more samples than specified by the user's exact sampling_strategy.

Steps/Code to Reproduce

Reproducing Issue 1 (ValueError with identical points)

import numpy as np
from imblearn.over_sampling import KMeansSMOTE
from sklearn.cluster import KMeans

X = np.array([
    [1.0, 1.0], [1.0, 1.0], [1.0, 1.0], [1.0, 1.0], # identical minority
    [2.0, 2.0], [2.0, 2.0], [2.0, 2.0], [2.0, 2.0], # identical majority
    [3.0, 3.0], [3.0, 3.0], [3.0, 3.0], [3.0, 3.0]  
])
y = np.array([1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0])

smote = KMeansSMOTE(kmeans_estimator=KMeans(n_clusters=2, random_state=42), random_state=42, cluster_balance_threshold=0.1)
smote.fit_resample(X, y) # Raises ValueError

Reproducing Issue 2 (Excessive samples generated)

import numpy as np
from imblearn.over_sampling import KMeansSMOTE
from sklearn.cluster import KMeans

X = np.array([
    [1.0, 1.0], [1.1, 1.1], [0.9, 0.9], [1.0, 0.9],
    [5.0, 5.0], [5.1, 5.1], [4.9, 4.9], [5.0, 4.9],
    [2.0, 2.0], [3.0, 3.0], [4.0, 4.0], [6.0, 6.0], [7.0, 7.0] 
])
y = np.array([1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0])

# Target 11 samples, which means we want to generate EXACTLY 3 samples.
smote = KMeansSMOTE(sampling_strategy={1: 11}, kmeans_estimator=KMeans(n_clusters=2, random_state=42), random_state=42, cluster_balance_threshold=0.1)

X_res, y_res = smote.fit_resample(X, y)
print("Generated samples:", len(y_res) - len(y))
# Outputs: 4 (exceeds the requested 3 samples)

Expected Results

1. KMeansSMOTE should handle cases where cluster_sparsities.sum() == 0 gracefully (e.g., fallback to uniform weighting among valid clusters).
2. The total sum of cluster_n_samples across all valid clusters should exactly match n_samples generated by using a proportional allocation method.

Versions

Tested on imbalanced-learn==0.14.2