Seeded K-means clustering (Lloyd iterations): Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Assign each point to its nearest mean and recompute nonempty means until assignments stop changing or the iteration limit is reached.

Select distinct input indices with a seeded partial shuffle. Assign each point to its nearest current mean, then replace each nonempty mean by its assigned coordinate averages. Repeat until assignments stabilize or the iteration limit is reached.

Open the 3D visualization

Seeded K-means clustering (Lloyd iterations) example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Seeded K-means clustering (Lloyd iterations)

Teaching centroid-based clustering, the effect of initialization and local convergence on a small planar data set.

Choosing an alternative

K-means minimizes squared Euclidean distance through alternating assignment and mean updates. It does not guarantee a globally optimal partition, and this initializer is a uniform index sample rather than K-means++.

Worked example: input and state changes

Example input

-8,-7;-7,-8;-6,-6;7,8;8,7;6,6|2,1,8

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Seed 1: rejection-sampled partial shuffle selects distinct input indices 0, 4.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7
      ],
      "active": [],
      "kind": "graph",
      "points": [
        [
          -8,
          -7
        ],
        [
          -7,
          -8
        ],
        [
          -6,
          -6
        ],
        [
          7,
          8
        ],
        [
          8,
          7
        ],
        [
          6,
          6
        ],
        [
          -8,
          -7
        ],
        [
          8,
          7
        ]
      ],
      "nodeLabels": [
        "P0 (-8, -7) unassigned",
        "P1 (-7, -8) unassigned",
        "P2 (-6, -6) unassigned",
        "P3 (7, 8) unassigned",
        "P4 (8, 7) unassigned",
        "P5 (6, 6) unassigned",
        "C0 mean (-8/1, -7/1)",
        "C1 mean (8/1, 7/1)"
      ],
      "pointLabelIndices": [
        6,
        7
      ],
      "vertexColors": [
        0,
        0,
        0,
        0,
        0,
        0,
        1,
        2
      ],
      "directed": false,
      "chosen": [],
      "visited": [],
      "result": 0,
      "output": []
    }
  2. Step 1: Assign points to nearest rational means; equal distances choose the lowest cluster index.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7
      ],
      "active": [
        0,
        1,
        2,
        3,
        4,
        5
      ],
      "kind": "graph",
      "points": [
        [
          -8,
          -7
        ],
        [
          -7,
          -8
        ],
        [
          -6,
          -6
        ],
        [
          7,
          8
        ],
        [
          8,
          7
        ],
        [
          6,
          6
        ],
        [
          -8,
          -7
        ],
        [
          8,
          7
        ]
      ],
      "nodeLabels": [
        "P0 (-8, -7) C0",
        "P1 (-7, -8) C0",
        "P2 (-6, -6) C0",
        "P3 (7, 8) C1",
        "P4 (8, 7) C1",
        "P5 (6, 6) C1",
        "C0 mean (-8/1, -7/1)",
        "C1 mean (8/1, 7/1)"
      ],
      "pointLabelIndices": [
        6,
        7
      ],
      "vertexColors": [
        1,
        1,
        1,
        2,
        2,
        2,
        1,
        2
      ],
      "directed": false,
      "chosen": [],
      "visited": [],
      "result": 0,
      "output": []
    }
  3. Step 3: Assign points to nearest rational means; equal distances choose the lowest cluster index.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7
      ],
      "active": [
        0,
        1,
        2,
        3,
        4,
        5
      ],
      "kind": "graph",
      "points": [
        [
          -8,
          -7
        ],
        [
          -7,
          -8
        ],
        [
          -6,
          -6
        ],
        [
          7,
          8
        ],
        [
          8,
          7
        ],
        [
          6,
          6
        ],
        [
          -7,
          -7
        ],
        [
          7,
          7
        ]
      ],
      "nodeLabels": [
        "P0 (-8, -7) C0",
        "P1 (-7, -8) C0",
        "P2 (-6, -6) C0",
        "P3 (7, 8) C1",
        "P4 (8, 7) C1",
        "P5 (6, 6) C1",
        "C0 mean (-21/3, -21/3)",
        "C1 mean (21/3, 21/3)"
      ],
      "pointLabelIndices": [
        6,
        7
      ],
      "vertexColors": [
        1,
        1,
        1,
        2,
        2,
        2,
        1,
        2
      ],
      "directed": false,
      "chosen": [],
      "visited": [],
      "result": 0,
      "output": []
    }
  4. Step 4: Iteration 2: update means; empty clusters keep previous means.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7
      ],
      "active": [
        6,
        7
      ],
      "kind": "graph",
      "points": [
        [
          -8,
          -7
        ],
        [
          -7,
          -8
        ],
        [
          -6,
          -6
        ],
        [
          7,
          8
        ],
        [
          8,
          7
        ],
        [
          6,
          6
        ],
        [
          -7,
          -7
        ],
        [
          7,
          7
        ]
      ],
      "nodeLabels": [
        "P0 (-8, -7) C0",
        "P1 (-7, -8) C0",
        "P2 (-6, -6) C0",
        "P3 (7, 8) C1",
        "P4 (8, 7) C1",
        "P5 (6, 6) C1",
        "C0 mean (-21/3, -21/3)",
        "C1 mean (21/3, 21/3)"
      ],
      "pointLabelIndices": [
        6,
        7
      ],
      "vertexColors": [
        1,
        1,
        1,
        2,
        2,
        2,
        1,
        2
      ],
      "directed": false,
      "chosen": [],
      "visited": [],
      "result": 1,
      "output": []
    }
  5. Step 5: Converged: assignments unchanged after 2 iterations.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7
      ],
      "active": [],
      "kind": "graph",
      "points": [
        [
          -8,
          -7
        ],
        [
          -7,
          -8
        ],
        [
          -6,
          -6
        ],
        [
          7,
          8
        ],
        [
          8,
          7
        ],
        [
          6,
          6
        ],
        [
          -7,
          -7
        ],
        [
          7,
          7
        ]
      ],
      "nodeLabels": [
        "P0 (-8, -7) C0",
        "P1 (-7, -8) C0",
        "P2 (-6, -6) C0",
        "P3 (7, 8) C1",
        "P4 (8, 7) C1",
        "P5 (6, 6) C1",
        "C0 mean (-21/3, -21/3)",
        "C1 mean (21/3, 21/3)"
      ],
      "pointLabelIndices": [
        6,
        7
      ],
      "vertexColors": [
        1,
        1,
        1,
        2,
        2,
        2,
        1,
        2
      ],
      "directed": false,
      "chosen": [],
      "visited": [],
      "result": 1,
      "output": [
        0,
        0,
        0,
        1,
        1,
        1,
        -21,
        -21,
        3,
        3,
        21,
        21,
        3,
        3,
        2,
        282475249,
        1
      ]
    }

Expected final state

Converged: assignments unchanged after 2 iterations.

Complexity and input bounds

Family: Optimization. Time complexity: O(I n k).

Implementation detail: One through eight integer points -10..10, up to three clusters, Park-Miller seed 1..2147483646 and one through eight iterations. Initialization uses rejection sampling. Downloads compare exact rational squared distances, return 1 converged or 0 iteration limit, and write assignments, [sumX,sumY,denominator,currentMemberCount] per cluster, iteration count, final PRNG state and convergence flag. An empty cluster retains the prior positive mean denominator. Invalid parameters return -1 without writing output. Independent BigInt fixtures include a forced rejected random draw, duplicate coordinates, empty clusters and limit outcomes in every language.

Space complexity: O(n+k) assignment, initialization and centroid storage, excluding frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..8 points x,y separated by ;, then |clusters,seed,maxIterations. Integer coordinates -10..10, k 1..min(3,n), seed 1..2147483646, iterations 1..8. Empty clusters retain their previous mean.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Equal coordinates can still occupy distinct sampled indices. Empty clusters retain their previous mean. Equal distances choose the lowest cluster index. Report a limit outcome separately from confirmed assignment convergence.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// Seeded Lloyd K-means. n 1..8 integer points -10..10, k 1..min(3,n), seed 1..2147483646, iteration limit 1..8. Partial Fisher-Yates initialization uses Park-Miller with rejection sampling and distinct point indices. Exact rational squared-distance comparisons, lowest-index ties; empty clusters retain their previous mean. Return 1 when assignments stabilize, 0 at the iteration limit, -1 for invalid parameters without output writes. Output n+4*k+3 integers: n assignments; each cluster [sumX,sumY,denominator,currentMemberCount]; iterations, final generator state, convergence flag. An empty cluster can retain a positive denominator from its previous mean. Finite Lloyd descent does not guarantee a global optimum. O(I*n*k) time, O(n+k) scratch; bounded products fit signed 32-bit arithmetic. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(x, y, n, k, seed, limit, output) {
    if (n < 1 || n > 8 || k < 1 || k > 3 || k > n || seed < 1 || seed > 2147483646 || limit < 1 || limit > 8) { return -1; }
    let order = Array(256).fill(0); let meanX = Array(256).fill(0); let meanY = Array(256).fill(0); let denominator = Array(256).fill(0); let labels = Array(256).fill(0); let sumX = Array(256).fill(0); let sumY = Array(256).fill(0); let members = Array(256).fill(0);
    let state = seed; let high = 0; let low = 0; let range = 0; let ceiling = 0; let value = 0; let pick = 0; let swapValue = 0; let iterations = 0; let converged = 0; let changed = 0; let best = 0; let dx = 0; let dy = 0; let bestDistance = 0; let distance = 0; let offset = 0;
    for (let i = 0; i < n; i++) { order[i] = i; labels[i] = -1; }
    for (let c = 0; c < k; c++) { range = n-c; ceiling = 2147483646-2147483646%range; value = ceiling; while (value >= ceiling) { high = Math.floor(state / 127773); low = state-high*127773; state = 16807*low-2836*high; if (state <= 0) { state += 2147483647; } value = state-1; } pick = c+value%range; swapValue = order[c]; order[c] = order[pick]; order[pick] = swapValue; meanX[c] = x[order[c]]; meanY[c] = y[order[c]]; denominator[c] = 1; }
    while (iterations < limit && converged == 0) { changed = 0; for (let c = 0; c < k; c++) { sumX[c] = 0; sumY[c] = 0; members[c] = 0; }
    for (let i = 0; i < n; i++) { best = 0; dx = x[i]*denominator[0]-meanX[0]; dy = y[i]*denominator[0]-meanY[0]; bestDistance = dx*dx+dy*dy; for (let c = 1; c < k; c++) { dx = x[i]*denominator[c]-meanX[c]; dy = y[i]*denominator[c]-meanY[c]; distance = dx*dx+dy*dy; if (distance*denominator[best]*denominator[best] < bestDistance*denominator[c]*denominator[c]) { best = c; bestDistance = distance; } } if (labels[i] != best) { changed = 1; } labels[i] = best; sumX[best] += x[i]; sumY[best] += y[i]; members[best]++; }
    for (let c = 0; c < k; c++) { if (members[c] > 0) { meanX[c] = sumX[c]; meanY[c] = sumY[c]; denominator[c] = members[c]; } } iterations++; if (changed == 0) { converged = 1; } }
    for (let i = 0; i < n; i++) { output[i] = labels[i]; }
    for (let c = 0; c < k; c++) { offset = n+4*c; output[offset] = meanX[c]; output[offset+1] = meanY[c]; output[offset+2] = denominator[c]; output[offset+3] = members[c]; }
    output[n+4*k] = iterations; output[n+4*k+1] = state; output[n+4*k+2] = converged; return converged;
}

Source

Lloyd supplies the foundational least-squares quantization iteration, not this playground seeding policy. Park-Miller supplies the reproducible generator. The playground uses bounded planar points, exact rational means, partial-shuffle initialization and explicit empty-cluster retention.