Dear Steve, At 11:21 AM 3/15/02 +1100, you wrote: >The aim is to group 5000 points into 500 groups so that the sum of the >straight >line distances between the points in each group is the minimum or optimised. > >I think I am looking for a clustering algorithm.
Yes. Specifically, if you define the "value" of a cluster to be the sum of distances between all pairs of points in the cluster, you want to minimize the sum of the values (summed over all clusters). I researched this two years ago and concluded, after contacting some experts in the clustering field (it's pretty hot nowadays because of applications to web searching), that an algorithm does not yet exist. (If one has emerged in the meantime I would be delighted to hear about it.) An approximate one does, based on swapping points and moving points among tentative clusters, but it does not always reach an optimum. If instead you minimize the sum of squares of distances among all mutual points in a cluster, the solution is identical to the KMeans clustering, a well-known algorithm for which you can find Fortran source code on the Web and which is implemented in many statistical packages. The best way currently known for solving your problem as stated is spatial simulated annealing. For instance, Dick Brus's group at Alterra (Wageningen, The Netherlands) has been using SSA with good success to solve even more complex clustering problems that minimize mean semivariances among clusters based on a geostatistical model. A good text on simulated annealing is the one by Aarts & Korst, especially if you can borrow it because it's outrageously expensive. I have no software to offer you because everything I'm aware of has been implemented in ArcView. Cheers, Bill Huber www.quantdec.com _______________________________________________________________________ List hosting provided by Directions Magazine | www.directionsmag.com | To unsubscribe, send e-mail to [EMAIL PROTECTED] and put "unsubscribe MapInfo-L" in the message body.
