# Clustering based on partial information?

I'm open to suggestions on how to improve the title.

My problem is this, but I think it's a more general problem. In my context, I have a lot of data which has location data (Lat/Lon) as well as various characteristics of my objects. I'm interested in clustering based on location in such a way that it controls for effects based on weather and other local effects.

So what I want is a clustering which, after trained, determines the cluster of a new object solely based on its GPS coordinates. However, I want the clusters not to just cluster based on locational clusters (there are lots of objects in this ball in Florida, this ball in California, etc.) but to make clusters so that within the clusters, objects are more similar than you would expect.

So for example, k-means would not accomplish this; it would just identify pockets of objects based on location clustering, or it would require more information to determine the cluster of a new object (neither are desirable).

Another way would be to run k-means a bunch of times, rate the results based on comparing homogeneity within clusters, and pick the best, but this seems both computationally annoying and unlikely to get good results (it would tend to identify circular clusters, rather than e.g. picking out things within 10 miles of a coast, or whatever turns out to be useful).

I feel like someone has thought of this before and come up with something. What sorts of algorithms (classical or not) might help with this?

I don't mind re-implementing something on my own, and I don't mind stacking/etc. classifiers. My dataset is fairly small for now, so even if there isn't a fast algorithm for this, it should be okay (even $O(n^2 \log(n))$ algorithms are doable, I've found).