View source for User talk:AW/KNN

So, I was reading about Mahalanobis distance and it sounds as if it is designed for classifying data that have a definite center about which they are clustered. Has anyone tried using this with robocode?

I've thought about it, but it needs a covariance matrix and it is slow to build a covariance matrix of the entire tree. There might be faster approximate methods though...

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).

I've also been a bit wary of class-based methods as a solution for our problem, which is actually pure regression. However, I do have one idea which might just make using classes worth it - spectral clustering. On certain types of datasets spectral clustering can get ~30% better performance than pure convex-Euclidean-geometry based classification systems, and Robocode with its patterns and limited possibilities for positioning setups might just be one of those. The problem is getting spectral clustering to run at a reasonable speed - it depends on getting the eigenvectors for a NxN matrix (and never mind populating that matrix with e^x values first), which is O(n^3) and for us with our 20k datapoints isn't really feasible without some major modifications. We could use a sparse matrix and lots of kNN instead of a brute force for the population of that matrix, but it's still going to be horribly slow.

If anybody wants to mess around with spectral clustering here is a good paper on it (yes, I've been thinking about this for a while): [1] and you'll need a matrix library like EJML or Colt - EJML is faster for dense matrices but Colt supports sparse matrices which might be a necessary component of our solution to this problem.

As always, an incremental solution would probably be best =) And sorry to hijack a Mahalanobis thread!

I tried. Found 2 problems in using mahalanobis distance instead of euclidean distance.

First problem is finding a covariance matrix, which is the mahalanobis equivalent of a weight vector. I tried using sampled covariance matrixes, but they are not always valid. You need a positive semi-definite covariance matrix to use it in mahalanobis distance calculations. There are methods for finding a nearest positive semi-definite matrix from a sampled matrix, but the methods are too slow to be calculated online.

Second problem is optimizing KNN search. Methods like kd-trees only work with euclidean distance. I don´t know of any data structure designed for mahalanobis distances and which supports online learning at the same time.

The first problem can be addressed with genetic tuning to find a valid covariance matrix offline, but I didn´t try it yet. In theory it can be stronger than euclidean distance search due to higher amount of weights to tune.

The second problem is not a serious problem if the data set is not too big. I managed to make a bot work using only real waves (no tick waves), a sampled covariance matrix and simple linear KNN search without skipping turns.

The problem is the matrix was sometimes valid, sometimes not. It fallbacked to euclidean distance (using only the main diagonal) whenever the matrix became invalid. The bot performance decreased and I never uploaded it to the rumble. But again, genetic tuning with an offline covariance matrix may fix it.

Because the weights are always positive it should actually be possible to use a kD-Tree for Mahalanobis distance. Bounding box calculations can be done exactly like before, they just need to be adjusted by the weights.