ParallelKMeans.jl Package

AbstractKMeansAlg

Abstract base type inherited by all sub-KMeans algorithms.

ClusteringResult

Base type for the output of clustering algorithm.

Coreset()

Coreset algorithm implementation, based on "Lucic, Mario & Bachem, Olivier & Krause, Andreas. (2015). Strong Coresets for Hard and Soft Bregman Clustering with Applications to Exponential Family Mixtures."

Coreset supports following arguments:

• m: default 100, subsample size
• alg: default Lloyd(), algorithm used to clusterize sample

It can be used directly in kmeans function

X = rand(30, 100_000)   # 100_000 random points in 30 dimensions

# 3 clusters, Coreset algorithm with default Lloyd algorithm and 100 subsamples
kmeans(Coreset(), X, 3)

# 3 clusters, Coreset algorithm with Hamerly algorithm and 500 subsamples
kmeans(Coreset(m = 500, alg = Hamerly()), X, 3)
kmeans(Coreset(500, Hamerly()), X, 3)

# alternatively short form can be used for defining subsample size or algorithm only
kmeans(Coreset(500), X, 3) # sample of the size 500, Lloyd clustering algorithm
kmeans(Coreset(Hamerly()), X, 3) # sample of the size 100, Hamerly clustering algorithm

Elkan()

Elkan algorithm implementation, based on "Charles Elkan. 2003. Using the triangle inequality to accelerate k-means. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning (ICML’03). AAAI Press, 147–153."

This algorithm provides much faster convergence than Lloyd algorithm especially for high dimensional data. It can be used directly in kmeans function

X = rand(30, 100_000)   # 100_000 random points in 30 dimensions

kmeans(Elkan(), X, 3) # 3 clusters, Elkan algorithm

Hamerly()

Hamerly algorithm implementation, based on "Hamerly, Greg. (2010). Making k-means Even Faster. Proceedings of the 2010 SIAM International Conference on Data Mining. 130-140. 10.1137/1.9781611972801.12."

This algorithm provides much faster convergence than Lloyd algorithm with realtively small increase in memory footprint. It is especially suitable for low to medium dimensional input data.

It can be used directly in kmeans function

X = rand(30, 100_000)   # 100_000 random points in 30 dimensions

kmeans(Hamerly(), X, 3) # 3 clusters, Hamerly algorithm

KmeansResult{C,D<:Real,WC<:Real} <: ClusteringResult

The output of kmeans and kmeans!.

Type parameters

• C<:AbstractMatrix{<:AbstractFloat}: type of the centers matrix
• D<:Real: type of the assignment cost
• WC<:Real: type of the cluster weight

C is the type of centers, an (abstract) matrix of size (d x k)

D is the type of pairwise distance computation from points to cluster centers

WC is the type of cluster weights, either Int (in the case where points are

unweighted) or eltype(weights) (in the case where points are weighted).

Lloyd <: AbstractKMeansAlg

Basic algorithm for k-means calculation.

Yinyang()

Yinyang algorithm implementation, based on "Yufei Ding et al. 2015. Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with Consistent Speedup. Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015"

Generally it outperform Hamerly algorithm and has roughly the same time as Elkan algorithm with much lower memory consumption.

Yinyang supports following arguments: auto: Bool, indicates whether to perform automated or manual grouping group_size: Int, estimation of average number of clusters per group. Lower numbers corresponds to higher calculation speed and higher memory consumption and vice versa.

It can be used directly in kmeans function

X = rand(30, 100_000)   # 100_000 random points in 30 dimensions

# 3 clusters, Yinyang algorithm, with deault 7 group_size
kmeans(Yinyang(), X, 3)

# Following are equivalent
# 3 clusters, Yinyang algorithm with 10 group_size
kmeans(Yinyang(group_size = 10), X, 3)
kmeans(Yinyang(10), X, 3)

# One group with the size of the number of points
kmeans(Yinyang(auto = false), X, 3)
kmeans(Yinyang(false), X, 3)

# Chinese writing can be used
kmeans(阴阳(), X, 3)

Fit the specified ParaKMeans model constructed by the user.

See also the [package documentation](https://pydatablog.github.io/ParallelKMeans.jl/stable).

chunk_colwise!(target, x, y, i, weights, r, idx)

Utility function for the calculation of the weighted distance between points x and centroid vector y[:, i]. UnitRange argument r select subarray of original design matrix x that is going to be processed.

chunk_initialize(alg::Hamerly, containers, centroids, X, weights, metric, r, idx)

Initial calulation of all bounds and points labeling.

chunk_update_bounds(alg::Hamerly, containers, r1, r2, pr1, pr2, metric::Euclidean, r, idx)

Updates upper and lower bounds of point distance to the centers, with regard to the centers movement when metric is Euclidean.

chunk_update_bounds(alg::Hamerly, containers, r1, r2, pr1, pr2, metric::Metric, r, idx)

Updates upper and lower bounds of point distance to the centers, with regard to the centers movement when metric is Euclidean.

chunk_update_centroids(alg::Hamerly, containers, centroids, X, weights, metric, r, idx)

Detailed description of this function can be found in the original paper. It iterates through all points and tries to skip some calculation using known upper and lower bounds of distances from point to centers. If it fails to skip than it fall back to generic point_all_centers! function.

create_containers(::Lloyd, k, nrow, ncol, n_threads)

Internal function for the creation of all necessary intermidiate structures.

• centroids_new - container which holds new positions of centroids
• centroids_cnt - container which holds number of points for each centroid
• labels - vector which holds labels of corresponding points

distance(metric, X1, X2, i1, i2)

Allocationless calculation of distance between vectors X1[:, i1] and X2[:, i2] defined by the supplied distance metric.

distance(X1, X2, i1, i2)

Allocationless calculation of square eucledean distance between vectors X1[:, i1] and X2[:, i2]

double_argmax(p)

Finds maximum and next after maximum arguments.

Kmeans!(alg::AbstractKMeansAlg, containers, design_matrix, k; n_threads = nthreads(), k_init="k-means++", max_iters=300, tol=1e-6, verbose=true)

Mutable version of kmeans function. Definition of arguments and results can be found in kmeans.

Argument containers represent algorithm specific containers, such as labels, intermidiate centroids and so on, which are used during calculations.

kmeans([alg::AbstractKMeansAlg,] design_matrix, k; n_threads = nthreads(),
k_init="k-means++", max_iters=300, tol=1e-6, verbose=true, rng = Random.GLOBAL_RNG)

This main function employs the K-means algorithm to cluster all examples in the training data (design_matrix) into k groups using either the k-means++ or random initialisation technique for selecting the initial centroids.

At the end of the number of iterations specified (max_iters), convergence is achieved if difference between the current and last cost objective is less than the tolerance level (tol). An error is thrown if convergence fails.

Arguments:

• alg defines one of the algorithms used to calculate k-means. This

argument can be omitted, by default Lloyd algorithm is used.

• n_threads defines number of threads used for calculations, by default it is equal

to the Threads.nthreads() which is defined by JULIA_NUM_THREADS environmental variable. For small size design matrices it make sense to set this argument to 1 in order to avoid overhead of threads generation.

• k_init is one of the algorithms used for initialization. By default k-means++ algorithm is used,

alternatively one can use rand to choose random points for init.

• max_iters is the maximum number of iterations
• tol defines tolerance for early stopping.
• verbose is verbosity level. Details of operations can be either printed or not by setting verbose accordingly.

A KmeansResult structure representing labels, centroids, and sum_squares is returned.

move_centers(::Hamerly, containers, centroids, metric)

Calculates new positions of centers and distance they have moved. Results are stored in centroids and p respectively.

point_all_centers!(containers, centroids, X, i, metric)

Calculates new labels and upper and lower bounds for all points.

point_all_centers!(containers, centroids, X, i)

Calculates new labels and upper and lower bounds for all points.

smart_init(X, k; init="k-means++")

This function handles the random initialisation of the centroids from the design matrix (X) and desired groups (k) that a user supplies.

k-means++ algorithm is used by default with the normal random selection of centroids from X used if any other string is attempted.

A named tuple representing centroids and indices respecitively is returned.

spliiter(n, k)

Internal utility function, splits 1:n sequence to k chunks of approximately same size.

sum_of_squares(x, labels, centre, k)

This function computes the total sum of squares based on the assigned (labels) design matrix(x), centroids (centre), and the number of desired groups (k).

A Float type representing the computed metric is returned.

update_containers(::Hamerly, containers, centroids, n_threads, metric)

Calculates minimum distances from centers to each other.

@parallelize(n_threads, ncol, f)

Parallelize function and run it over n_threads. Function should require following conditions:

1. It should not return any values.
2. It should accept parameters two parameters at the end of the argument list. First

accepted parameter is range, which defines chunk used in calculations. Second parameter is idx which defines id of the container where results can be stored.

ncol argument defines range 1:ncol which is sliced in n_threads chunks.