Spectral clustering.
Applies clustering to a projection of the normalized graph Laplacian [1]. Instead of clustering the points in their original space, the algorithm builds an affinity (similarity) matrix between all pairs of samples, computes the eigenvectors associated with the smallest eigenvalues of its normalized graph Laplacian, and runs k-means on that spectral embedding.
In practice spectral clustering is very useful when the individual clusters are non-convex (e.g. nested circles), a setting where plain k-means on the original space performs poorly [2].
The eigendecomposition of the dense {num_samples, num_samples} Laplacian
gives a time complexity of $O(N^3)$ and a memory complexity of $O(N^2)$,
where $N$ is the number of samples.
References:
Summary
Functions
Performs spectral clustering on the sample inputs x.
Functions
Performs spectral clustering on the sample inputs x.
If affinity: :rbf (the default), x is expected to be a
{num_samples, num_features} tensor of samples. If affinity: :precomputed,
x is expected to be a symmetric {num_samples, num_samples} affinity matrix.
Self-loops are discarded when building the graph Laplacian, i.e. the diagonal
of the affinity matrix is ignored, matching scipy.sparse.csgraph.laplacian.
Options
:num_clusters(pos_integer/0) - Required. The number of clusters to form, as well as the dimension of the spectral embedding.:affinity- How to construct the affinity matrix, either of::rbf- construct the affinity matrix using a radial basis function (RBF) kernel, $\exp(-\gamma \|x_i - x_j\|^2)$.:precomputed- interpret the input as a precomputed affinity matrix, i.e. a symmetric{num_samples, num_samples}tensor of non-negative similarities.
The default value is
:rbf.:gamma- Kernel coefficient for the:rbfaffinity. Ignored for:precomputed. The default value is1.0.:num_runs(pos_integer/0) - Number of times the k-means algorithm will be run on the spectral embedding with different centroid seeds. The final result is the best output in terms of inertia. The default value is10.:max_iterations(pos_integer/0) - Maximum number of iterations of the k-means algorithm for a single run. The default value is300.:key- Determines random number generation for centroid initialization of the k-means step. If the key is not provided, it is set toNx.Random.key(System.system_time()).
Return Values
The function returns a struct with the following parameters:
:labels- Cluster labels of each point.:embedding- The{num_samples, num_clusters}spectral embedding, i.e. the eigenvectors of the normalized graph Laplacian associated with itsnum_clusterssmallest eigenvalues, rescaled as in the relaxed Ncut problem ($u = D^{-1/2} v$) and with a deterministic sign (the entry with the largest absolute value of each eigenvector is positive).
Examples
iex> key = Nx.Random.key(42)
iex> x = Nx.tensor([[0.0, 0.0], [0.1, 0.1], [3.0, 3.0], [3.1, 3.1]])
iex> Scholar.Cluster.SpectralClustering.fit(x, num_clusters: 2, key: key).labels
#Nx.Tensor<
s32[4]
[0, 0, 1, 1]
>