DKM

A generic C++11 k-means clustering implementation

This is a k-means clustering algorithm written in C++, intended to be used as a header-only library. Requires C++11.

The algorithm is based on Lloyds Algorithm and uses the kmeans++ initialization method.

The library is located in the include directory and may be used under the terms of the MIT license (see LICENSE.md). The tests in the src directory are also licensed under the MIT license, except for lest.hpp, which has its own license (src/LICENSE_1_0.txt), the Boost Software License. The benchmarks located within the bench directory also fall under the MIT license. Benchmark data was obtained from the UCI Machine Learning Repository here.

A basic benchmark can be found in the bench folder. An example of the current results on an Intel i5-4210U:

OpenCV: 1.51998ms
DKM: 0.044276ms

This is only running k-means on a small data set (150 samples), and is only a single measurement, so do not interpret the results to mean that DKM is always faster than OpenCV.

Usage

To use the DKM k-means implementation, simply include include/dkm.hpp and call dkm::kmeans_lloyd() with your data (std::vector<std::array<>>) and the number of cluster centers the algorithm should calculate for the data set.

Example:

std::vector<std::array<float, 2>> data{{1.f, 1.f}, {2.f, 2.f}, {1200.f, 1200.f}, {2.f, 2.f}};
auto means = dkm::details::random_plusplus(data, 2);

Building (tests and benchmarks)

For tests and benchmarks DKM uses a standard CMake out-of-tree build model.

To make everything:

mkdir build
cd build
cmake .. && make

To build only the tests run make dkm_tests instead of make. To build only the benchmarks run make dkm_bench.

The tests can be run using the make test command or executing ./dkm_tests in the build directory, and the benchmarks can likewise be run with ./dkm_bench.

Compatability

The following compilers are officially supported on Linux and tested via Travis:

• Clang 3.6
• Clang 3.7
• GCC 4.9
• GCC 5.0+

GCC/Clang versions prior to the above are intentionally unsupported due to poor C++11 support. Other compilers may be considered, Microsoft VC++ is intended to be supported, but does not currently have a CI build set up.

Dependencies (test)

• CMake

Dependencies (bench)

• OpenCV 2.4
• CMake