Skilgannon: Reply to Mahalanobis Distance

2012-10-19T17:34:04Z

New page

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): [http://ai.stanford.edu/~ang/papers/nips01-spectral.pdf] and you'll need a matrix library like [http://code.google.com/p/efficient-java-matrix-library/ EJML] or [http://acs.lbl.gov/software/colt/ 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!

Thread:User talk:AW/KNN/Mahalanobis Distance/reply (4) - Revision history

Skilgannon: Reply to Mahalanobis Distance