Clustering#

This chapter contains functions for performing clustering computations.

k-means clustering#

k-means clustering aims to partition a set of \(n_{\mathrm{samples}}\) data points \(\{x_1, x_2, \dots, x_{n_{\mathrm{samples}}}\}\) into \(n_{\mathrm{clusters}}\) groups. Each group is described by the mean of the data points assigned to it \(\{\mu_1, \mu_2, \dots, \mu_{n_{\mathrm{clusters}}}\}\). These means are commonly known as the cluster centres or centroids and are not generally points from the original data matrix.

Various k-means algorithms are available, but each one proceeds by attempting to minimize a quantity known as the inertia, or the within-cluster sum-of-squares:

\[\sum^{n_{\mathrm{samples}}}_{i=1}\min_{1\le j\le n_{\mathrm{clusters}}}\left(\|x_i-\mu_j\|^2\right).\]

Since this is an NP-hard problem, algorithms are heuristic in nature and converge to local optima. Therefore it is often desirable to run the algorithms several times and select the result with the smallest inertia.

Outputs from k-means clustering#

After a k-means clustering computation the following results are stored:

  • cluster centres - the centre of the clusters.

  • labels - the cluster each sample in the data matrix belongs to.

  • inertia - the sum of the squared distances of each sample to its closest cluster centre.

  • iterations - the number of iterations that were performed.

Two post-processing operations may be of interest:

  • transform - given a data matrix \(X\) in the same coordinates as the original data matrix \(A\), express \(X\) in terms of new coordinates in which each dimension is the distance to the cluster centres previously computed for \(A\).

  • predict - given a data matrix \(Y\) find the closest cluster centre out of the clusters previously computed for \(A\).

Typical workflow for k-means clustering#

The standard way of using k-means clustering in AOCL-DA is as follows.

  1. Initialize a aoclda.clustering.kmeans() object with options set in the class constructor.

  2. Compute the k-means clusters using aoclda.clustering.kmeans.fit().

  3. Perform further transformations or predictions using aoclda.clustering.kmeans.transform() or aoclda.clustering.kmeans.predict().

  4. Extract results from the aoclda.clustering.kmeans() object via its class attributes.

  1. Initialize a da_handle with da_handle_type da_handle_kmeans.

  2. Pass data to the handle using da_kmeans_set_data_?.

  3. Set the number of clusters required and other options using da_options_set_? (see below).

  4. Optionally set the initial centres using da_kmeans_set_init_centres_?.

  5. Compute the k-means clusters using da_kmeans_compute_?.

  6. Perform further computations as required, using da_kmeans_transform_? or da_kmeans_predict_?.

  7. Extract results using da_handle_get_result_?.

Options#

The available Python options are detailed in the aoclda.factorization.kmeans() class constructor.

The following options can be set using da_options_set_?:

k-means options#

Option Name

Type

Default

Description

Constraints

convergence tolerance

real

\(r=10^{-4}\)

Convergence tolerance.

\(0 \le r\)

algorithm

string

\(s=\) lloyd

Choice of underlying k-means algorithm.

\(s=\) elkan, hartigan-wong, lloyd, or macqueen.

initialization method

string

\(s=\) random

How to determine the initial cluster centres.

\(s=\) k-means++, random, random partitions, or supplied.

seed

integer

\(i=0\)

Seed for random number generation; set to -1 for non-deterministic results.

\(-1 \le i\)

max_iter

integer

\(i=300\)

Maximum number of iterations.

\(1 \le i\)

n_init

integer

\(i=10\)

Number of runs with different random seeds (ignored if you have specified initial cluster centres).

\(1 \le i\)

n_clusters

integer

\(i=1\)

Number of clusters required.

\(1 \le i\)

Note that if the initialization method is set to random then the initial cluster centres are chosen randomly from the sample points. If it is set to random partitions then the sample points are assigned to a random cluster and the corresponding cluster centres are computed and used as the starting point.

The standard algorithm for solving k-means problems is Lloyd’s algorithm. Elkan’s algorithm can be faster on naturally clustered datasets but uses considerably more memory. For more information on the available algorithms see Elkan [2003], Hartigan and Wong [1979], Lloyd [1982] and MacQueen [1967].

Examples (clustering)#

The code below is supplied with your installation (see Python examples).

  1# Copyright (C) 2024 Advanced Micro Devices, Inc. All rights reserved.
  2#
  3# Redistribution and use in source and binary forms, with or without modification,
  4# are permitted provided that the following conditions are met:
  5# 1. Redistributions of source code must retain the above copyright notice,
  6#    this list of conditions and the following disclaimer.
  7# 2. Redistributions in binary form must reproduce the above copyright notice,
  8#    this list of conditions and the following disclaimer in the documentation
  9#    and/or other materials provided with the distribution.
 10# 3. Neither the name of the copyright holder nor the names of its contributors
 11#    may be used to endorse or promote products derived from this software without
 12#    specific prior written permission.
 13#
 14# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 15# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 16# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 17# IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 18# INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 19# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
 20# OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 21# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 22# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 23# POSSIBILITY OF SUCH DAMAGE.
 24#
 25
 26"""
 27k-means clustering example Python script
 28"""
 29
 30import sys
 31import numpy as np
 32from aoclda.clustering import kmeans
 33
 34
 35def kmeans_example():
 36    """
 37    k-means clustering example
 38    """
 39
 40    # Define data arrays
 41    a = np.array([[2., 1.],
 42                  [-1., -2.],
 43                  [3., 2.],
 44                  [2., 3.],
 45                  [-3., -2.],
 46                  [-2., -1.],
 47                  [-2., -3.],
 48                  [1., 2.]])
 49
 50    c = np.array([[1., 1.],
 51                  [-3., -3.]])
 52
 53    x = np.array([[0., 1.],
 54                  [0., -1.]])
 55
 56    print("\nk-means clustering for a small data matrix\n")
 57    try:
 58        km = kmeans(n_clusters=2)
 59        km.fit(a, c)
 60        x_transform = km.transform(x)
 61        x_labels = km.predict(x)
 62    except RuntimeError:
 63        sys.exit(1)
 64
 65    # Print results
 66    print("\nComputed cluster centres:\n")
 67    print(km.cluster_centres)
 68    print("\nLabels for original data matrix:\n")
 69    print(km.labels)
 70    print("\nx_transform:\n")
 71    print(x_transform)
 72    print("\nx labels:\n")
 73    print(x_labels)
 74
 75    # Check against expected results
 76
 77    expected_centres = np.array([[2., 2.], [-2., -2.]])
 78    expected_labels = np.array([0, 1, 0, 0, 1, 1, 1, 0])
 79
 80    expected_x_transform = np.array([[2.23606797749979, 3.605551275463989],
 81                                     [3.605551275463989, 2.23606797749979]])
 82    expected_x_labels = np.array([0, 1])
 83
 84    norm_components = np.linalg.norm(
 85        km.cluster_centres - expected_centres)
 86    norm_x_transform = np.linalg.norm(x_transform - expected_x_transform)
 87
 88    incorrect_labels = np.any(
 89        expected_labels - km.labels) or np.any(expected_x_labels - x_labels)
 90
 91    tol = 1.0e-12
 92
 93    if norm_components > tol or norm_x_transform > tol or incorrect_labels:
 94        print("\nSolution is not within expected tolerance\n")
 95        sys.exit(1)
 96
 97    print("\nk-means clusters successfully computed\n")
 98
 99
100if __name__ == "__main__":
101    kmeans_example()

The code below can be found in kmeans.cpp in the examples folder of your installation.

  1/*
  2 * Copyright (C) 2024 Advanced Micro Devices, Inc. All rights reserved.
  3 *
  4 * Redistribution and use in source and binary forms, with or without modification,
  5 * are permitted provided that the following conditions are met:
  6 * 1. Redistributions of source code must retain the above copyright notice,
  7 *    this list of conditions and the following disclaimer.
  8 * 2. Redistributions in binary form must reproduce the above copyright notice,
  9 *    this list of conditions and the following disclaimer in the documentation
 10 *    and/or other materials provided with the distribution.
 11 * 3. Neither the name of the copyright holder nor the names of its contributors
 12 *    may be used to endorse or promote products derived from this software without
 13 *    specific prior written permission.
 14 *
 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 17 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 18 * IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 19 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 20 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
 21 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 22 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 24 * POSSIBILITY OF SUCH DAMAGE.
 25 *
 26 */
 27
 28#include "aoclda.h"
 29#include <iostream>
 30
 31/*
 32 * Basic k-means example
 33 *
 34 * This example computes k-means clustering for a small data matrix.
 35 */
 36
 37int main() {
 38
 39    // Initialize the handle
 40    da_handle handle = nullptr;
 41
 42    std::cout << "-----------------------------------------------------------------------"
 43              << std::endl;
 44    std::cout << "Basic k-means" << std::endl;
 45    std::cout << "k-means clustering for a small data matrix" << std::endl << std::endl;
 46    std::cout << std::fixed;
 47    std::cout.precision(5);
 48
 49    int exit_code = 0;
 50    bool pass = true;
 51
 52    // Input data
 53    double A[16] = {2.0, -1.0, 3.0, 2.0, -3.0, -2.0, -2.0, 1.0,
 54                    1.0, -2.0, 2.0, 3.0, -2.0, -1.0, -3.0, 2.0};
 55    double C[4] = {1.0, -3.0, 1.0, -3.0};
 56
 57    da_int n_samples = 8, n_features = 2, n_clusters = 2, lda = 8, ldc = 2;
 58
 59    // Create the handle and pass it the data matrix
 60    pass = pass && (da_handle_init_d(&handle, da_handle_kmeans) == da_status_success);
 61
 62    pass = pass && (da_kmeans_set_data_d(handle, n_samples, n_features, A, lda) ==
 63                    da_status_success);
 64
 65    // Set options
 66    pass = pass &&
 67           (da_options_set_int(handle, "n_clusters", n_clusters) == da_status_success);
 68    pass = pass && (da_options_set_int(handle, "n_init", 1) == da_status_success);
 69    pass = pass && (da_options_set_string(handle, "initialization method", "supplied") ==
 70                    da_status_success);
 71
 72    // Set the initial cluster centres
 73    pass = pass && (da_kmeans_set_init_centres_d(handle, C, ldc) == da_status_success);
 74
 75    // Compute the clusters
 76    pass = pass && (da_kmeans_compute_d(handle) == da_status_success);
 77
 78    // Extract results from the handle
 79    da_int cluster_centres_dim = n_clusters * n_features;
 80    da_int labels_dim = n_samples;
 81    double *cluster_centres = new double[cluster_centres_dim];
 82    da_int *labels = new da_int[labels_dim];
 83
 84    pass = pass && (da_handle_get_result_d(handle, da_kmeans_cluster_centres,
 85                                           &cluster_centres_dim,
 86                                           cluster_centres) == da_status_success);
 87    pass = pass && (da_handle_get_result_int(handle, da_kmeans_labels, &labels_dim,
 88                                             labels) == da_status_success);
 89
 90    // Transform another data matrix into the cluster space and predict its labels
 91    double X[4] = {0.0, 0.0, 1.0, -1.0};
 92    da_int m_samples = 2, m_features = 2, ldx = 2, ldx_transform = 2;
 93    double *X_transform = new double[m_samples * n_clusters];
 94    da_int *X_labels = new da_int[m_samples];
 95    pass =
 96        pass && (da_kmeans_transform_d(handle, m_samples, m_features, X, ldx, X_transform,
 97                                       ldx_transform) == da_status_success);
 98
 99    pass = pass && (da_kmeans_predict_d(handle, m_samples, m_features, X, ldx,
100                                        X_labels) == da_status_success);
101
102    // Check status (we could do this after every function call)
103    if (pass) {
104        std::cout << "k-means clustering computed successfully" << std::endl << std::endl;
105
106        std::cout << "Cluster centres:" << std::endl;
107        for (da_int j = 0; j < n_clusters; j++) {
108            for (da_int i = 0; i < n_features; i++) {
109                std::cout << cluster_centres[n_clusters * i + j] << "  ";
110            }
111            std::cout << std::endl;
112        }
113        std::cout << std::endl;
114
115        std::cout << "Labels:" << std::endl;
116        for (da_int i = 0; i < n_samples; i++) {
117            std::cout << labels[i] << "  ";
118        }
119        std::cout << std::endl;
120
121        // Check against expected results
122        double cluster_centres_exp[4] = {2.0, -2.0, 2.0, -2.0};
123        da_int labels_exp[8] = {0, 1, 0, 0, 1, 1, 1, 0};
124        double X_transform_exp[4] = {2.23606797749979, 3.605551275463989,
125                                     3.605551275463989, 2.23606797749979};
126        da_int X_labels_exp[2] = {0, 1};
127
128        double tol = 1.0e-14;
129        double err = 0.0;
130        for (da_int i = 0; i < cluster_centres_dim; i++)
131            err = std::max(err, std::abs(cluster_centres[i] - cluster_centres_exp[i]));
132        bool incorrect_labels = false;
133        for (da_int i = 0; i < labels_dim; i++) {
134            if (labels[i] != labels_exp[i]) {
135                incorrect_labels = true;
136                break;
137            }
138        }
139        for (da_int i = 0; i < m_samples * n_clusters; i++) {
140            err = std::max(err, std::abs(X_transform[i] - X_transform_exp[i]));
141            std::cout << X_transform[i] << " " << X_transform_exp[i] << std::endl;
142        }
143        for (da_int i = 0; i < m_samples; i++) {
144            if (X_labels[i] != X_labels_exp[i]) {
145                incorrect_labels = true;
146                break;
147            }
148        }
149        if (err > tol || incorrect_labels) {
150            std::cout << "Solution is not within the expected tolerance: " << err
151                      << std::endl;
152            exit_code = 1;
153        }
154    } else {
155        exit_code = 1;
156    }
157
158    // Clean up
159    da_handle_destroy(&handle);
160    delete[] cluster_centres;
161    delete[] labels;
162    delete[] X_transform;
163    delete[] X_labels;
164
165    std::cout << "-----------------------------------------------------------------------"
166              << std::endl;
167
168    return exit_code;
169}