twl09008181 / kmeans

KMeans implementation

Basic Information

KMeans is a famous algorithm for clustering, it is easy to implmenet and use.
It is widely used in data analysis and machine learning sphere.
A lot of algorithm is based on this simple and classical algorithm, like Spectral Clustering or data Preprocessing for reducing the complexity for latter training.
Generally, you can use KMeans when you want to group some data with similar attributes.

Usage

interface

c++

// data set ptr

using T = double;
// prepare data
dataset<T> mnist = load_mnist<T>("./mnist/train-images-idx3-ubyte","./mnist/train-labels-idx1-ubyte"); 
dataSetPtr<T> mnistPtr(mnist.num, mnist.dim, &mnist.data[0]);


// kmeans setting
int threadNum = 8;
size_t k = 10;
bool simd = false;
bool verbose = true;
int maxIter = 300;
double tol = 1e-4;
kmeans<T> kms(k, maxIter, tol, verbose, simd, threadNum);


// fit 
kms.fit(mnistPtr);

// get center
auto centers = kms._cluster_centers;
// prediction
auto labels = kms.predict(mnistPtr);

python

$PYTHONPATH=build python3 example/python/example.py

# import module
import kmeans as myKMeans

# prepare data
data, labels = load_digits(return_X_y=True)
(n_samples, n_features), n_digits = data.shape, np.unique(labels).size
reduced_data = PCA(n_components=2).fit_transform(data)

# kmeans setting
kmeans = myKMeans.kmeans64(10,300,1e-4,False,True,16)

# fit
kmeans.fit(reduced_data)

# Plot the decision boundary. For that, we will assign a color to each
x_min, x_max = reduced_data[:, 0].min() - 1, reduced_data[:, 0].max() + 1
y_min, y_max = reduced_data[:, 1].min() - 1, reduced_data[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))

# predict
Z = kmeans.predict(np.c_[xx.ravel(), yy.ravel()])

example

check example/

c++

$ make c++example

0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000011000000000000
0000000000001111110000000000
0000000000011111111000000000
0000000000000000111100000000
0000000000000000011100000000
0000000000000000001100000000
0000000000000000001100000000
0000000000000000011100000000
0000000000000000011000000000
0000000000000000111000000000
0000000000000001111000000000
0000000000001111110000000000
0000000000111111110000000000
0000000011111111110000000000
0000000111111111111000000000
0000000111111111111000000000
0000001111111111000000000000
0000000111111000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000011000000000000
0000000000000111000000000000
0000000000001110000000000000
0000000000001110000000000000
0000000000011100000000000000
0000000000011000000000000000
0000000000111000000000000000
0000000000111000000000000000
0000000001110000111100000000
0000000001110001111100000000
0000000001110011111110000000
0000000001110110001110000000
0000000001111100001110000000
0000000001111100011100000000
0000000001111111111100000000
0000000000111111110000000000
0000000000011111100000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000011111100000000000
0000000000111111110000000000
0000000001111111110000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000011100000000000
0000000000011111110000000000
0000000000111111110000000000
0000000000011111111000000000
0000000000000000011100000000
0000000000000000001100000000
0000000000000000001100000000
0000000000000000001100000000
0000000000000000001100000000
0000000000000000011100000000
0000000000100001111100000000
0000000001111111111000000000
0000000000111111100000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000001000000000
0000000000001111111110000000
0000000000111110011110000000
0000000000111000001110000000
0000000000110000011100000000
0000000001100000011100000000
0000000000000000111000000000
0000000000000001111000000000
0000000000000011110000000000
0000000000000011110000000000
0000000000000011100000000000
0000000000000111000000000000
0000000000000111000000000000
0000000000001110000000000000
0000000000011100000000000000
0000000000011100000000000000
0000000000011000000000000000
0000000000010000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000111000000000
0000000000000111111110000000
0000000000001111111110000000
0000000000011110001110000000
0000000000011100000100000000
0000000000011000001100000000
0000000000011000011000000000
0000000000011000110000000000
0000000000011111110000000000
0000000000011111100000000000
0000000000011111100000000000
0000000000011111100000000000
0000000000000001110000000000
0000000000000000110000000000
0000000000000001110000000000
0000000000000001110000000000
0000000011111111100000000000
0000000011111111000000000000
0000000001111110000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000111100000000000
0000000000011111111000000000
0000000000111111111100000000
0000000001111110111110000000
0000000011110000000111000000
0000000011100000000011100000
0000000111100000000011100000
0000000111000000000001100000
0000001110000000000001110000
0000001110000000000001110000
0000001110000000000001110000
0000001110000000000011100000
0000001110000000000011100000
0000001110000000000111000000
0000001111000000001111000000
0000000111100000111110000000
0000000011111111111100000000
0000000001111111110000000000
0000000000011111000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000001100000000000000000
0000000011100000000000000000
0000000011000000001000000000
0000000111000000011100000000
0000000110000000011100000000
0000000110000000011100000000
0000000111000000111100000000
0000000111100111111100000000
0000000011111111111100000000
0000000000000000111000000000
0000000000000000011000000000
0000000000000000011000000000
0000000000000000011000000000
0000000000000000011000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000001100000000000
0000000000000001100000000000
0000000000000011100000000000
0000000000000011100000000000
0000000000000011000000000000
0000000000000111000000000000
0000000000000111000000000000
0000000000000111000000000000
0000000000000111000000000000
0000000000001110000000000000
0000000000001110000000000000
0000000000001110000000000000
0000000000001100000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000111100000000000
0000000000111111111000000000
0000000001111000111000000000
0000000001110000111000000000
0000000001100000011000000000
0000000001000000111000000000
0000000001000000111000000000
0000000000000001111000000000
0000000000000001110000000000
0000000000000001110000000000
0000000000000001110000000000
0000000000000001110000000000
0000000000000001100000000000
0000000000000011100000000000
0000000000000011100000000000
0000000000000011000000000000
0000000000000011000000000000
0000000000000010000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000111100000000
0000000000000011111110000000
0000000000000111111111000000
0000000000001111111111000000
0000000000011111000111000000
0000000000111110000011000000
0000000001111100000011000000
0000000001111000000011000000
0000000011110000000111000000
0000000011100000000111000000
0000000111000000000111000000
0000000111000000001110000000
0000001110000000011110000000
0000001110000000111100000000
0000001110000011111000000000
0000001111111111110000000000
0000001111111111100000000000
0000000111111110000000000000
0000000001110000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000

python

$ make pyexample
or 
$PYTHONPATH=build python3 example/python/example.py