Murat Derya &#214;zen - 1 year ago 470
Python Question

# Python Implementation of OPTICS (Clustering) Algorithm

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)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download