Mahalanobis Distance
I've spent many a CPU-hour experimenting with quite a few clustering algorithms and never been able to exceed the performance of KNN for Robocode targeting, and KNN is also much faster. So I'm a little skeptical at this point about approaches that assume a data point falls into a specific cluster. But this is interesting stuff... definitely WaveSim (or similar) makes testing this kind of thing a lot more feasible.
Mahalanobis distance can be combined with KNN search. Swap point distance calculation from euclidean to mahalanobis and you have it.
Another way of viewing mahalanobis distance is it rotates the data space, or have "diagonal" weights. Which is good when classifiers are not completely independent from each other.
i.e. lateral velocity and vertical velocity. If lateral velocity is 8, vertical velocity is always 0. Coordinates where both velocities are 8 are always empty. Mahalanobis distance then uses a "diagonal" weight so 5.6 lateral velocity and 5.6 vertical velocity (5.6, 5.6) is normalized as (8, 8). While (8, 0) is still normalized as (8, 0).
