Skip to content
C++ implementation of the mean shift clustering algorithm with OpenMP
C++ Python TeX CMake M4 Shell Other
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
ClusteringTests
MeanShift
Paper
ReadmeImg
Slides Add experiments setup slide Jun 13, 2019
.gitattributes Add .pdf in .gitattributes Jan 8, 2019
.gitignore
LICENSE
README.md Write slide template Jun 12, 2019

README.md

MeanShift

C++ implementation of the mean shift clustering algorithm with OpenMP.

In this README you will find instructions about how to compile the program and how to execute it. In the directory Paper there is a technical paper about the algorithm and the comparison of the sequential version with the parallel version.

Compiling

If you are used to CLion, you could open the directory MeanShift with the IDE. You will find all the necessary build configurations.

Otherwise, go to the MeanShift directory, create a build folder and change directory to that folder:

$ cd Meanshift
$ mkdir build
$ cd build

Then you can compile the program in two versions:

  • A sequential version:
$ cmake -DCMAKE_BUILD_TYPE=Release ../
$ make meanshift
  • A parallel version, with OpenMP:
$ cmake -DCMAKE_BUILD_TYPE=Release DCMAKE_CXX_FLAGS=-fopenmp ../
$ make meanshift

The parallel version will be much faster, because it uses the OpenMP directives to perform multithreading operations.

Usage

The result of the compilation is an executable called meanshift. It takes as input a CSV file containing the points to cluster and the bandwidth parameter of the mean shift algorithm. The points in the CSV file must be all of the same dimension (each row of the CSV file must contains the same number of columns) and there must be only numerical values. To get the clustering result, you must append to the command the string --write-output <filename>: the program will generate a file <filename>.csv containing the points where the last number of each row is the cluster to which the point belongs.

In the directory ClusteringTests/datasets there are some datasets to perform some tests.

I strongly reccomend you to use the python script plot_clusters.py located in the directory ClusteringTests to execute the program and plot the results. It requires Python >= 3.5, numpy and matplotlib. plot_clusters.py take as input the CSV file and the bandwidth parameter. Pay attention where the meanshift executable is located, you could set the right path in the script plot_clusters.py.

Example

The dataset data8.csv contains 10000 points distributed in three gaussian blobs with standard deviation 1.

If we execute the mean shift algorithm with bandwidth 1 we get exactly the three clusters:

$ python plot_clusters datasets/data8.csv 1
File: datasets/data8.csv
Number of points: 10000
Number of dimensions: 3
Number of clusters: 3
Elapsed time: 6.66942 s

3clusters

If we increase the bandwidth value to 10, then all the points will go in the same cluster:

$ python plot_clusters.py datasets/data8.csv 10
File: datasets/data8.csv
Number of points: 10000
Number of dimensions: 3
Number of clusters: 1
Elapsed time: 22.963 s

1cluster

Speedup

The file speeduptest in the directoryClusteringTests is a BASH script that executes the sequential version and then executes different parallel versions with a different number of threads to estimate the speedup obtained by parallelizing the algorithm.

The results and the analysis of the speedup is described in the technical paper in the directory Paper.

You can’t perform that action at this time.