Clustering neighboring points inside ArcGIS Desktop?

Question

I am using ArcGIS Desktop 10x.

I have a shapefile of 300 points which I need to make groups, each of which will contain exactly 9 points which are closest neighbors.

I tried the 'near' tool, which have added NEAR_FID and NEAR_DIST to the attribute table but couldn't use it to group 9 neighbors. I also tried 'grouping analysis' tool but this only makes 2 groups overall with variable number of members each time.

Anyone have any better idea?

Answer 1

Result of clustering technique suggested by @Albert shown by colours of points in the picture below. Output will greatly depend on physical order of points in a feature class. At some stage it will result in "islands", that are grouped in a very disperse "cluster", e.g. red points in group "C" below. Note that points are labelled by their FID.

Algorithm that I described multiple times (see my comments to this post) successfully negotiates this issue, producing continious clusters. Output shown by colours of rectangles:

Picture below shows algorithm applied to 297 points by 9 in groups:

UPDATE:

To produce above result I computed Voronoi polygons for points of interest and followed steps described here. Perhaps you can do the same and see if you like output.

Alternatively: Call your points NODES in the table of content (shapefiles only!).

arcpy.AddGeometryAttributes_management("NODES")
arcpy.SpatialJoin_analysis("NODES", "NODES", "./links.shp", "JOIN_ONE_TO_MANY","INTERSECT", search_radius="1500 Meters")
arcpy.SelectLayerByAttribute_management("links",""""TARGET_FID" = "JOIN_FID"""")
arcpy.DeleteFeatures_management(in_features="links")
arcpy.AddField_management("links", "TIMES", "DOUBLE")
arcpy.CalculateField_management("links", "TIMES", "math.hypot( !POINT_X! - !POINT_X_1!, !POINT_Y!- !POINT_Y_1! )", ."PYTHON_9.3")
arcpy.AddField_management("NODES", "RCVNODE","LONG")
arcpy.AddField_management("NODES", "P2013","LONG")
arcpy.CalculateField_management("NODES", "P2013", "1")

Create tool as shown in hyperlinked post and run it. Check values in field RCVNODE of NODES, this is a group number assigned to your points. If script fails it means that distance in spatial join is too small and you've got islands not connected to the rest of network. Increase distance.

Remember that any solution is only one out of countless possible solutions. If you don't like it try to reorder nodes in the table.

Note that with very little efforts you can visualize your LINKS points into lines connecting NODES:

Answer 2

Like LMB said, the groups would differ depending on the seed you use.

You could do this in Python and it's relatively easy. This is the general idea, of course you will need some loops and counters to assign groups.

1. Create a memory layer with all your points.
2. Select a starting point manually from your original dataset, ideally a point in a corner.
3. Calculate its group (group = 1 until you reach 9 recursions, then group = group +1)
4. Delete the same point ID of the selected point from the memory layer
5. Find the closest point from the selected point against the memory layer with the near tool
6. Select this same ID in the original dataset and start again from step 3

The idea is to run the near tool and find the closest point which will be in the same group until you start the following group. The principal thing is deleting the points already assigned when running the near tool again.

Answer 3

Genetic Algorithms have been found to be useful for clustering. Perhaps the one of these solutions could be constrained to yield clusters of 9 points.

Using Genetic Algorithms in Clustering Problems

Genetic algorithm-based clustering technique

Clustering Genetic Algorithm