Since a bunch of my hobby projects have gravitated into the land of vector quantization (which I managed to rediscover by accident) I figured I'd make some (more) generic code towards that, maybe solve some of the issues I've had with my earlier implementations and maybe even learn some (more) modern c++ features while at it.
I'm sure there's tons of ready built VQ libraries out there, but this is a learning journey so I didn't even check.
I started off with a really simple use case. Have integers 0..1023 and ask for 16 groupings. So you'd expect 16 groups of 64 values, or to be more precise the centers of those groups, so each center is 64 apart.
As a starting point, since from the algorithms point of view it "shouldn't" matter what the initial selections are (typical instructions say "start from random numbers"), I just selected values 0..15, which is pretty much the worst. As seen in the image, it converges pretty nicely (yes, that's 284 iterations), but to my surprise did not give optimal result.
I figured it must be about integer rounding so I changed the data type to doubles, but got the exact same result.
expected actual delta
32 27.5 4.5
96 84 12
160 141.5 18.5
224 200 24
288 259.5 28.5
352 320 32
416 381.5 34.5
480 444.5 35.5
544 508.5 35.5
608 573.5 34.5
672 640 32
736 707.5 28.5
800 776 24
864 845.5 18.5
928 916 12
992 987.5 4.5
The steps range from 56.5 to 71.5. They do average to 64, though! The +/-11% difference from optimum feels pretty high though.
If I start from the optimal position the algorithm doesn't muck it up, at least.. but finding the optimal position is kinda what the algorithm is meant to do.
Either I'm missing something, or this is just one of those things I have to live with..