I'm looking for some advice on directions to head in a project I'm working on. Basically what I want to do is identify general (of varying size) groups in a 2-D grid of points belonging to one of three categories: red, blue or empty. I'm not completely new to machine learning, but not familiar enough with the variety of methods to know which is best. My first thought was still to use a clustering algorithm, since it seems like I'm basically looking for clusters of the types, but I was concerned with the low-dimensionality and concerned since I already know that they have in common, I more need to find the groups efficiently. I more need to be able to identify whether is a group that needs to be further analysed or if it is a points or just a couple of points grouped together. The problem size is small, 81-361 coordinates per analysis, but will have to be run after each update to the grid, most likely on the order of hundreds of times per run, but could extend to thousands. I'd really like some input on this and appreciate any advice someone could impart on the topic.
K-means seems to be the best choice, especially with the low dimensionality of the problem. Selecting the number of clusters seems likely to be be the most difficult part, but for the purpose of the project it may suffice to evenly subdivide the grid and then attempt the k-means. I think it will accomplish what needs to be done here the best.
We need more information regarding this problem, what is the morphology of the groups?! Do you have any sample visualizations?! Are the clusters globular on structure? Because if they aren't you won't have much success with k-means, since it uses euclidean distance, and as such is biased toward circular groups. Other techniques that will likely be of interest to you are hierarchical clustering and soft k-means (does overlapping happens?!).
Regarding efficiency of the method, keep in mind that k-means as a problem with initialization and as such multiple runs should be done to assure convergence. You can tradeoff accuracy for speed trough the use of k-means++.