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:
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.
Initialize a
aoclda.clustering.kmeans()object with options set in the class constructor.Compute the k-means clusters using
aoclda.clustering.kmeans.fit().Perform further transformations or predictions using
aoclda.clustering.kmeans.transform()oraoclda.clustering.kmeans.predict().Extract results from the
aoclda.clustering.kmeans()object via its class attributes.
Initialize a
da_handlewithda_handle_typeda_handle_kmeans.Pass data to the handle using da_kmeans_set_data_?.
Set the number of clusters required and other options using da_options_set_? (see below).
Optionally set the initial centres using da_kmeans_set_init_centres_?.
Compute the k-means clusters using da_kmeans_compute_?.
Perform further computations as required, using da_kmeans_transform_? or da_kmeans_predict_?.
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_?:
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}