OPTICS-Clustering (UNDER CONSTRUCTION)

Ordering points to identify the clustering structure (OPTICS) is an algorithm for finding density-based clusters in spatial data. It was presented by Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel and Jörg Sander in 1999.

Introduction

This repository is home to a C++ implementation of the OPTICS algorithm as described by Ankerst et al.. It aims at providing an easy-to-use clustering algorithm which does not require knowledge of the number of clusters a priori.
For further explanation on how the algorithm works, see e.g. Wikipedia or YouTube.
The implementation relies on the boost::rtree to efficiently retrieve the neighbourhood of a given point.

Usage

Suppose you have a set of points in R^n, described in Cartesian coordinates, and wonder if they have a cluster structure. Then you might consider using this library, as it offers an interface that lets you visually inspect the cluster structure of the data space (using a reachability-plot) - and extract those clusters with three lines of code:

#include <optics/optics.h>

typedef std::vector<double> point; //A list of n cartesian coordinates makes a point
std::vector<point> points; //Your list of points goes here

int main(){
   auto reach_dists = optics::compute_reachability_dists<T,N>( points, min_pts, epsilon );
   optics::draw_reachability_plot( reach_dists, "./reachdists.bmp" );
   auto clusters = optics::get_cluster_indices( reach_dists, threshold );
}

Dependencies

Two lightweight header-only libraries, and boost (::geometry and ::index, to be exact)

Installation

Before the installation, make sure you have installed Boost. Subsequently, you can use one of the following two alternative ways to install OPTICS-Clustering:

Alternative 1:
Clone this repository

git clone https://github.com/CrikeeIP/OPTICS-Clustering

and execute the the install.sh script delivered with it.

Alternative 2:
If you're uncomfortable running who-knows-what-they'll-do foreign scripts (and are too tired to check them before execution), you can also do it manually:

Clone & include the Geometry header-lib,
Clone & install FunctionalPlus
Clone & install the OPTICS repository:

git clone https://github.com/CrikeeIP/OPTICS-Clustering
cd OPTICS-clustering
./configure && make && make install

Disclaimer

This librarys functionality initially grew due to my personal need for it - an easy to use clustering algorithm which does not need to know the number of clusters a priori. I try my best to make it error free and as comfortable to use as I can. The API still might change in the future. If you have any suggestions, find errors, miss some functions or want to give general feedback/criticism, I'd love to hear from you. Of course, contributions are also very welcome.

License

Distributed under the MIT Software License (X11 license). (See accompanying file LICENSE.)

strongdeer/OPTICS-Clustering