for i in range(len(weights) - 1, -1, -1):
The defects. The naive seeding routine draws r = random() * total (so r ∈ [0, total)) and scans with a non-strict cumsum >= r:
random() + non-strict compare. random() can return exactly 0.0. Then r = 0.0 and cumsum >= r is true at index 0 — the wheel picks point 0 even when it carries zero probability mass (e.g. it was already chosen as a centroid). This biases the seeding toward the first data point and re-selects chosen centroids.log(0) infinities. Some inverse-CDF variants build the CDF through logarithms (-log(u) per bin, or log of normalized masses). math.log(0.0) raises ValueError; np.log(0.0) returns -inf, which then poisons the CDF.The fix (full module in ~/kmeanspp_fix.py):
def inverse_cdf_sample(weights, rng):
"""Draw i with probability weights[i] / sum(weights)."""
total = sum(weights)
if total <= 0.0:
raise ValueError("no positive weight")
# FIX 1: (0, total], never 0 -> no exact-zero draw sticks on index 0
r = (1.0 - rng.random()) * total
# FIX 2: strict inequality -> zero-mass bins (cum unchanged) are skipped
cum = 0.0
for i, w in enumerate(weights):
cum += w
if cum > r:
return i
# Only reachable if r == total exactly (random() == 0.0, or rounding):
# last positive-mass bin, so selection remains without replacement.
for i in range(len(weights) - 1, -1, -1):
if weights[i] > 0.0:
return i
raise RuntimeError("unreachable")
def kmeans_plusplus_seed(points, k, rng=None, first=None):
rng = rng if rng is not None else random.Random()
n = len(points)
if n == 0 or k <= 0:
return []
k = min(k, n)
chosen = [rng.randrange(n) if first is None else first]
for _ in range(1, k):
d2 = _min_sq_distances(points, chosen) # min D^2 to ALL chosen
for ci in chosen: # FIX 3: without replacement
d2[ci] = 0.0
total = sum(d2)
if total <= 0.0:
break # coincident points
chosen.append(inverse_cdf_sample(d2, rng)) # FIX 4: no logarithms
return chosen
Before/after of the one buggy line:
# BUG r = rng.random() * total # [0, total) -> r can be 0.0
# FIX r = (1.0 - rng.random()) * total # (0, total] -> never 0.0
# BUG if cum >= r: ... # lands on zero-mass bin at r==0
# FIX if cum > r: ... # skips zero-mass bins exactly
A vectorized NumPy variant is also provided (kmeans_plusplus_seed_np), using np.searchsorted(cumsum(d2), r, side="right") — which implements exactly the strict cumsum > r comparison — plus a fallback to the last positive-mass bin when r == total.
Verified with `~/test_kmeanspp_fix.py` (pure stdlib; numpy used only for the optional variant). **13/13 checks passed.**
| # | Test | Result |
|---|------|--------|
| 1 | Sampler histogram vs theory, 200k draws, weights `[1,2,3,4,5]` — chi²=0.32 (df=4, crit 18.47), max rel. error 0.21% | ✅ |
| 2 | Zero-mass bins `[0,3,0,7,0]` — indices 0/2/4 never picked; ratio 3:7 measured 0.4267 (theory 0.4286) | ✅ |
| 3 | Adversarial `r == 0.0` (via `random()→1.0`): picks first **positive**-mass index (1), not index 0 | ✅ |
| 4 | Adversarial `r == total` (via `random()→0.0`): falls back to last positive-mass index (3), no infinite loop | ✅ |
| 5 | `k == n` on 60 distinct 2-D points: returns exactly 60 **distinct** indices (without replacement) | ✅ |
| 6 | 2000 seeded runs, `k=8`: zero duplicate selections | ✅ |
| 7 | 10 coincident points: stops after 1 centroid (`total == 0`) instead of crashing | ✅ |
| 8 | `k == 1` → 1 centroid; `k > n` → clamped to `n` distinct | ✅ |
| 9 | Fixed seed → identical output (deterministic) | ✅ |
| 10 | End-to-end `k=2` on `{0,1,2}`: empirical second-centroid marginals `[0.4303, 0.1337, 0.4360]` vs theory `[0.4333, 0.1333, 0.4333]`, chi²=2.37 (crit 13.82) | ✅ |
| 11 | Extreme magnitudes `[1e-300, 1e300, 1.0, 0.0]`: stays finite, zero-mass index never picked, no `inf`/`nan` | ✅ |
| 12 | First-point bias regression: buggy `random()+>=` with `r=0` returns index 0 (zero mass); fixed returns index 1 | ✅ |
| 13 | NumPy vectorized variant: 30 distinct centroids for `k=30` | ✅ |
The `log(0)` failure mode of the old code was demonstrated directly: `math.log(0.0)` → `ValueError: expected a positive input, got 0.0`; `np.log(0.0)` → `-inf` (which corrupts the CDF). The corrected sampler contains no logarithms and instead uses a direct linear inverse-CDF scan, so this class of failure is structurally impossible.
---{"model": "deepseek-v4-flash", "problem_class": "python-kmeanspp-seeding-roulette-bias", "result": "passed", "tests": 13}The defects. The naive seeding routine draws r = random() * total (so r ∈ [0, total)) and scans with a non-strict cumsum >= r:
random() + non-strict compare. random() can return exactly 0.0. Then r = 0.0 and cumsum >= r is true at index 0 — the wheel picks point 0 even when it carries zero probability mass (e.g. it was already chosen as a centroid). This biases the seeding toward the first data point and re-selects chosen centroids.log(0) infinities. Some inverse-CDF variants build the CDF through logarithms (-log(u) per bin, or log of normalized masses). math.log(0.0) raises ValueError; np.log(0.0) returns -inf, which then poisons the CDF.The fix (full module in ~/kmeanspp_fix.py):
def inverse_cdf_sample(weights, rng):
"""Draw i with probability weights[i] / sum(weights)."""
total = sum(weights)
if total <= 0.0:
raise ValueError("no positive weight")
# FIX 1: (0, total], never 0 -> no exact-zero draw sticks on index 0
r = (1.0 - rng.random()) * total
# FIX 2: strict inequality -> zero-mass bins (cum unchanged) are skipped
cum = 0.0
for i, w in enumerate(weights):
cum += w
if cum > r:
return i
# Only reachable if r == total exactly (random() == 0.0, or rounding):
# last positive-mass bin, so selection remains without replacement.
for i in range(len(weights) - 1, -1, -1):
if weights[i] > 0.0:
return i
raise RuntimeError("unreachable")
def kmeans_plusplus_seed(points, k, rng=None, first=None):
rng = rng if rng is not None else random.Random()
n = len(points)
if n == 0 or k <= 0:
return []
k = min(k, n)
chosen = [rng.randrange(n) if first is None else first]
for _ in range(1, k):
d2 = _min_sq_distances(points, chosen) # min D^2 to ALL chosen
for ci in chosen: # FIX 3: without replacement
d2[ci] = 0.0
total = sum(d2)
if total <= 0.0:
break # coincident points
chosen.append(inverse_cdf_sample(d2, rng)) # FIX 4: no logarithms
return chosen
Before/after of the one buggy line:
# BUG r = rng.random() * total # [0, total) -> r can be 0.0
# FIX r = (1.0 - rng.random()) * total # (0, total] -> never 0.0
# BUG if cum >= r: ... # lands on zero-mass bin at r==0
# FIX if cum > r: ... # skips zero-mass bins exactly
A vectorized NumPy variant is also provided (kmeans_plusplus_seed_np), using np.searchsorted(cumsum(d2), r, side="right") — which implements exactly the strict cumsum > r comparison — plus a fallback to the last positive-mass bin when r == total.
Verified with `~/test_kmeanspp_fix.py` (pure stdlib; numpy used only for the optional variant). **13/13 checks passed.**
| # | Test | Result |
|---|------|--------|
| 1 | Sampler histogram vs theory, 200k draws, weights `[1,2,3,4,5]` — chi²=0.32 (df=4, crit 18.47), max rel. error 0.21% | ✅ |
| 2 | Zero-mass bins `[0,3,0,7,0]` — indices 0/2/4 never picked; ratio 3:7 measured 0.4267 (theory 0.4286) | ✅ |
| 3 | Adversarial `r == 0.0` (via `random()→1.0`): picks first **positive**-mass index (1), not index 0 | ✅ |
| 4 | Adversarial `r == total` (via `random()→0.0`): falls back to last positive-mass index (3), no infinite loop | ✅ |
| 5 | `k == n` on 60 distinct 2-D points: returns exactly 60 **distinct** indices (without replacement) | ✅ |
| 6 | 2000 seeded runs, `k=8`: zero duplicate selections | ✅ |
| 7 | 10 coincident points: stops after 1 centroid (`total == 0`) instead of crashing | ✅ |
| 8 | `k == 1` → 1 centroid; `k > n` → clamped to `n` distinct | ✅ |
| 9 | Fixed seed → identical output (deterministic) | ✅ |
| 10 | End-to-end `k=2` on `{0,1,2}`: empirical second-centroid marginals `[0.4303, 0.1337, 0.4360]` vs theory `[0.4333, 0.1333, 0.4333]`, chi²=2.37 (crit 13.82) | ✅ |
| 11 | Extreme magnitudes `[1e-300, 1e300, 1.0, 0.0]`: stays finite, zero-mass index never picked, no `inf`/`nan` | ✅ |
| 12 | First-point bias regression: buggy `random()+>=` with `r=0` returns index 0 (zero mass); fixed returns index 1 | ✅ |
| 13 | NumPy vectorized variant: 30 distinct centroids for `k=30` | ✅ |
The `log(0)` failure mode of the old code was demonstrated directly: `math.log(0.0)` → `ValueError: expected a positive input, got 0.0`; `np.log(0.0)` → `-inf` (which corrupts the CDF). The corrected sampler contains no logarithms and instead uses a direct linear inverse-CDF scan, so this class of failure is structurally impossible.
---{"model": "deepseek-v4-flash", "problem_class": "python-kmeanspp-seeding-roulette-bias", "result": "passed", "tests": 13}