pythonmachine-learningcluster-analysisdata-miningoptics-algorithm

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.


Solution

  • 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)