What you will learn: How to apply k-means clustering on a Riemann manifold (Hypersphere) using Geomstats, contrasted with its implementation in Euclidean space, using scikit-learn library.
Notes:
- Environments: Python 3.10.10, Geomstats 2.7.0, Scikit-learn 1.4.2, Matplotlib 3.8.3
- This article assumes that the reader is somewhat familiar with differential and tensor calculus [ref 1]. Please refer to our previous articles related to geometric learning [ref 2, 3, 4].
- Source code is available at Github.com/patnicolas/Data_Exploration/manifolds
- To enhance the readability of the algorithm implementations, we have omitted non-essential code elements like error checking, comments, exceptions, validation of class and method arguments, scoping qualifiers, and import statements.
Introduction
The primary goal of learning Riemannian geometry is to understand and analyze the properties of curved spaces that cannot be described adequately using Euclidean geometry alone. Riemannian geometry enables to describe the geometric structures of manifolds equipped with a metric, which defines the concept of distance and angle on these spaces.
This article is the seventh part of our ongoing series focused on geometric learning. In this installment, we utilize the Geomstats Python library [ref. 5] and explore the ubiquitous K-means clustering algorithm on the hypersphere manifold. The hypersphere which was introduced in a previous piece, Geometric Learning in Python: Manifolds - Hypersphere and is detailed in the Geomstats API [ref. 6].
I highly recommend watching the comprehensive series of 22 YouTube videos Tensor Calculus - Eigenchris to familiarize yourself with fundamental concepts of differential geometry. Summaries of my earlier articles on this topic can be found in the Appendix
There are many benefits for clustering data on a manifold for complex data sets [ref 7]:
- Grouping of dense, continuous non-linear data depends on the 'shape' of data
- Projection to Euclidean space may introduce distortion
- Loss, distances are better assessed and computed through geodesics than Euclidean metrics (i.e. sphere)
K-means
Among the array of unsupervised learning algorithms, K-means stands out as one of the most well-known. This algorithm has a straightforward goal: to divide the data space so that data points within the same cluster are as similar as possible (intra-cluster similarity), and data points in different clusters are as dissimilar as possible (inter-cluster similarity). K-means aims to identify a predetermined number of clusters in an unlabeled dataset. It employs an iterative approach to finalize the clustering, which depends on the number of clusters specified by the user (denoted by the variable K).
Given K, Ck clusters each with a centroid mk, the input data xi is distributed across the cluster so to minimize the reconstruction error:\[Rerr(K)=\max_{C_k}\sum_{k=1}^{K}\sum_{x_i\in C_k}^{}\left \| x_i-m_k\right \|^2\]
Clustering data on a manifold
To assess and contrast the k-means model in both Euclidean space and on a hypersphere, it's necessary to create clustered data. This involves a two-step process:
- Generate a template cluster by employing a random generator on the manifold.
- Generate 4 clusters from the template using a special orthogonal Lie group in 3-dimensional space, SO(3).
Randomly generated manifold data
Let's evaluate and compare the following random generators for data points on the hypersphere we introduced in a previous article [ref 8]
- Uniform distribution
- Uniform distribution with constraints
- von Mises-Fisher distribution
Uniform distribution
We start with the basic random uniform generator over interval [0, 1].\[r=rand_{[0,1]}(x)\]. The data points for the 4 clusters are visualized in the following plot.
4-Cluster random generation using uniform distribution
Constrained uniform random generator.In this scenario, we constrain random values r on each of the 3 dimension (or axis) within a sub-interval [ai, bi].\[r=rand_{[0,1]}(x)\ \ \ a_i < r_i < b_i\]
4-Cluster random generation using constrained uniform distribution
von mises-Fisher random generator
This approach relies on a generative mixture-model approach to clustering directional data based on the von Mises-Fisher distribution [ref 9].
Given a d-dimensional unit random vector x on a hypersphere of dimension d-1, the d-variate von Moses-Fisher distribution is defined by the following probability density distribution:\[f(x|\mu , \kappa )=C_d(\kappa).e^{\kappa \mu^Tx} \ \ \ \ C_d(\kappa)=\frac{\kappa^{\frac{d}{2}-1}}{2\pi^{\frac{d}{2}}I_{\frac{d}{2}-1}(\kappa)}\]Id is the Bessel function and Cd is the normalization factor.
I
As anticipated, using a pure uniform random generator distributes data evenly across the hypersphere, rendering it ineffective for evaluating KMeans.
Instead, we will employ the von Mises-Fisher distribution and a constrained uniform random generator to more effectively analyze the performance of KMeans on a Riemann manifold.
Synthetic clusters using SO(3)
We leverage the SO(3) Lie group to replicate the randomly generated cluster.
Although the discussion of Lie groups and special orthogonal group in 3-dimensional space is beyond the scope of this article, here is a short summary:
In differential geometry, Lie groups play a crucial role by connecting the concepts of algebra and geometry. A Lie group is a mathematical structure that is both a group and a differentiable manifold. This means that the group operations of multiplication and taking inverses are smooth (differentiable), and it allows the application of calculus within the group structure.
The Special Orthogonal Lie group in 3-dimension space SO(3) is simply a group of 3 x 3 orthogonal matrices with determinant = 1. These represent rotation in
n-dimensional space and form a compact Lie group.
Implementation
Setup
Let's wraps the random generators and k-means training methods in a class, KMeansOnManifold.
The von Mises-Fisher generator for the data in the initial cluster is initialized with a mean, _mu and a kappa arbitrary value. The constrained uniform random generator, accepts random values in each dimension x: [-1, -0.35], y: [0.3, 1] and z: [-1. 0.4].
The SO(3) Lie group is initialized without metric (equip=False) to generate the 4 synthetic clusters.
# ---- Code Snippet 1 --------
from geomstats.geometry.hypersphere import Hypersphere
from geomstats.geometry.special_orthogonal import SpecialOrthogonal
class KMeansOnManifold(object):
def __init__(self,
num_samples: int,
num_clusters: int,
random_gen: AnyStr):
# Step 1: Initialize the manifold
self.hypersphere = Hypersphere(dim=2, equip=True)
# Step 2: ingle cluster with random data points on hypersphere match random_gen:
case 'random_von_mises_fisher':
# Select a pivot or mean value
_mu = self.hypersphere.random_uniform(n_samples=1)
# Generate the cluster
cluster = self.hypersphere.random_von_mises_fisher( mu=_mu[0],
kappa=60,
n_samples=num_samples,
max_iter=200)
case 'random_riemann_normal':
cluster = self.hypersphere.random_riemannian_normal( n_samples=num_samples,
max_iter=300)
case 'random_uniform':
cluster = self.hypersphere.random_uniform( n_samples=num_samples
)
case 'constrained_random_uniform'
# Generate random values with constrains on each dimension.
y = [x for x in self.hypersphere.random_uniform( n_samples=100000)
if x[0] <= -0.35 and x[1] >= 0.3 and x[2] <= -0.40]
cluster = np.array(y)[0:num_samples] case _:
raise ValueError(f'{random_gen} generator is not supported')
# Step 3: Generate other clusters using SO(3) manifolds
so3_lie_group = SpecialOrthogonal(3, equip=False)
# Generate the clusters
self.clusters = [cluster @ so3_lie_group.random_uniform()
for _ in range(num_clusters)]
Data in Euclidean space
The data class, KMeansCluster encapsulates the output (centroid and label) of the training of the k-means algorithm on the synthetic clustered data.
# ---- Code Snippet 2 --------
@dataclass
class KMeansCluster:
center: np.array
label: np.array
We rely k-means implementation in scikit-learn library [ref 10] (class KMeans) on the to identify the clusters in the Euclidean space, selecting the elkan algorithm, and k-means++ initialization.
# ---- Code Snippet 3 --------
def euclidean_clustering(self) -> List[KMeansCluster]:
from sklearn.cluster import KMeans
kmeans = KMeans(
n_clusters=len(self.clusters),
init='k-means++',
algorithm='elkan',
max_iter=140)
# Create a data set from points in clusters
data = np.concatenate(self.clusters, axis=0)
kmeans.fit(data)
# Extract centroids and labels
centers = kmeans.cluster_centers_
labels = kmeans.labels_
return [KMeansCluster(center, label) for center, label
in zip(centers, labels)]
Output:
Cluster Center: [ 0.56035023 -0.4030522 0.70054776], Label: 0
Cluster Center: [-0.1997325 -0.38496744 0.8826764 ], Label: 2
Cluster Center: [0.04443849 0.86749237 0.46118632], Label: 3
Cluster Center: [-0.83876485 -0.45621187 0.23570083], Label: 1
Clearly, this implementation of k-means was not able to identify the proper clusters
Data on hypersphere
The methods to train k-means on the hypersphere uses the same semantic as its sklearn counterpart. It leverage the Geomstats, RiemannianKMeans class method.
# ---- Code Snippet 4 --------
def riemannian_clustering (self) -> List[KMeansCluster]:
from geomstats.learning.kmeans import RiemannianKMeans
# Invoke the Geomstats Riemann Means
kmeans = RiemannianKMeans(space=self.hypersphere, n_clusters=len(self.clusters))
# Build the data set from the clustered data points
data = gs.concatenate(self.clusters, axis =0)
kmeans.fit(data)
# Extract predictions, centroids and labels
centers = kmeans.centroids_
labels = kmeans.labels_
return [KMeansCluster(center, label) for center, label
in zip(centers, labels)]
Similar to k-means in Euclidean space, we identify the centroids for 4 clusters using 500 randomly generated samples.
# ---- Code Snippet 5 ------
num_samples = 500
num_clusters = 4
kmeans = KMeansOnManifold(num_samples,
num_clusters,
'random_von_mises_fisher')
kmeans_cluster = kmeans.riemannian_clustering()
Output:
500 random samples on 4 clusters with von-mises-Fisher distribution
Cluster Center: [ 0.17772496 -0.36363422 0.91443097], Label: 2
Cluster Center: [ 0.44403679 0.06735507 -0.89347335], Label: 0
Cluster Center: [ 0.85407911 -0.50905801 0.10681211], Label: 3
Cluster Center: [ 0.90899637 0.02635062 -0.41597025], Label: 1
500 random samples on 4 clusters with constrained uniform distribution
Cluster Center: [-0.05344069 -0.91613807 0.3972847 ], Label: 1
Cluster Center: [ 0.6796575 0.39400079 -0.61873181], Label: 2
Cluster Center: [ 0.51799972 -0.67116261 -0.530299 ], Label: 0
Cluster Center: [ 0.49290501 -0.45790221 -0.73984473], Label: 3
Note: The labels are arbitrary indices assigned to each cluster for the purpose of visualization and validation against true labels.
