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.
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.
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 );
}Two lightweight header-only libraries, and boost (::geometry and ::index, to be exact)
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-Clusteringand 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 installThis 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.
Distributed under the MIT Software License (X11 license). (See accompanying file LICENSE.)
