I'm looking for a decent implementation of the OPTICS algorithm in Python. I will use it to form density-based clusters of points ((x,y) pairs).
I'm looking for something that takes in (x,y) pairs and outputs a list of clusters, where each cluster in the list contains a list of (x, y) pairs belonging to that cluster.
EDIT: the following is known to not be a complete implementation of OPTICS.
I did a quick search and found the following (Optics). I can't vouch for its quality, however the algorithm seems pretty simple, so you should be able to validate/adapt it quickly.
Here is a quick example of how to build clusters on the output of the optics algorithm:
def cluster(order, distance, points, threshold): ''' Given the output of the options algorithm, compute the clusters: @param order The order of the points @param distance The relative distances of the points @param points The actual points @param threshold The threshold value to cluster on @returns A list of cluster groups ''' clusters = [] points = sorted(zip(order, distance, points)) splits = ((v > threshold, p) for i,v,p in points) for iscluster, point in splits: if iscluster: clusters[-1].append(point) elif len(clusters[-1]) > 0: clusters.append() return clusters rd, cd, order = optics(points, 4) print cluster(order, rd, points, 38.0)