8.1.1.6. sklearn.cluster.SpectralClustering

class sklearn.cluster.SpectralClustering(n_clusters=8, eigen_solver=None, random_state=None, n_init=10, gamma=1.0, affinity='rbf', n_neighbors=10, k=None, eigen_tol=0.0, assign_labels='kmeans', mode=None)

Apply clustering to a projection to the normalized laplacian.

In practice Spectral Clustering is very useful when the structure of the individual clusters is highly non-convex or more generally when a measure of the center and spread of the cluster is not a suitable description of the complete cluster. For instance when clusters are nested circles on the 2D plan.

If affinity is the adjacency matrix of a graph, this method can be used to find normalized graph cuts.

When calling fit, an affinity matrix is constructed using either the Gaussian (aka RBF) kernel of the euclidean distanced d(X, X):

np.exp(-gamma * d(X,X) ** 2)

or a k-nearest neighbors connectivity matrix.

Alternatively, using precomputed, a user-provided affinity matrix can be used.

Parameters:

n_clusters : integer, optional

The dimension of the projection subspace.

affinity: string, ‘nearest_neighbors’, ‘rbf’ or ‘precomputed’ :

gamma: float :

Scaling factor of Gaussian (rbf) affinity kernel. Ignored for affinity='nearest_neighbors'.

n_neighbors: integer :

Number of neighbors to use when constructing the affinity matrix using the nearest neighbors method. Ignored for affinity='rbf'.

eigen_solver: {None, ‘arpack’ or ‘amg’} :

The eigenvalue decomposition strategy to use. AMG requires pyamg to be installed. It can be faster on very large, sparse problems, but may also lead to instabilities

random_state : int seed, RandomState instance, or None (default)

A pseudo random number generator used for the initialization of the lobpcg eigen vectors decomposition when eigen_solver == ‘amg’ and by the K-Means initialization.

n_init : int, optional, default: 10

Number of time the k-means algorithm will be run with different centroid seeds. The final results will be the best output of n_init consecutive runs in terms of inertia.

eigen_tol : float, optional, default: 0.0

Stopping criterion for eigendecomposition of the Laplacian matrix when using arpack eigen_solver.

assign_labels : {‘kmeans’, ‘discretize’}, default: ‘kmeans’

The strategy to use to assign labels in the embedding space. There are two ways to assign labels after the laplacian embedding. k-means can be applied and is a popular choice. But it can also be sensitive to initialization. Discretization is another approach which is less sensitive to random initialization.

Notes

If you have an affinity matrix, such as a distance matrix, for which 0 means identical elements, and high values means very dissimilar elements, it can be transformed in a similarity matrix that is well suited for the algorithm by applying the Gaussian (RBF, heat) kernel:

np.exp(- X ** 2 / (2. * delta ** 2))

Another alternative is to take a symmetric version of the k nearest neighbors connectivity matrix of the points.

If the pyamg package is installed, it is used: this greatly speeds up computation.

References

• Normalized cuts and image segmentation, 2000 Jianbo Shi, Jitendra Malik http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.2324
• A Tutorial on Spectral Clustering, 2007 Ulrike von Luxburg http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.165.9323
• Multiclass spectral clustering, 2003 Stella X. Yu, Jianbo Shi http://www1.icsi.berkeley.edu/~stellayu/publication/doc/2003kwayICCV.pdf

Attributes

affinity_matrix_	array-like, shape (n_samples, n_samples)	Affinity matrix used for clustering. Available only if after calling fit.
labels_ :		Labels of each point

Methods

fit(X)	Creates an affinity matrix for X using the selected affinity, then applies spectral clustering to this affinity matrix.
fit_predict(X[, y])	Performs clustering on X and returns cluster labels.
get_params([deep])	Get parameters for the estimator
set_params(**params)	Set the parameters of the estimator.

__init__(n_clusters=8, eigen_solver=None, random_state=None, n_init=10, gamma=1.0, affinity='rbf', n_neighbors=10, k=None, eigen_tol=0.0, assign_labels='kmeans', mode=None)

fit(X)

Creates an affinity matrix for X using the selected affinity, then applies spectral clustering to this affinity matrix.

Parameters:

X : array-like or sparse matrix, shape (n_samples, n_features)

OR, if affinity==`precomputed`, a precomputed affinity matrix of shape (n_samples, n_samples)

fit_predict(X, y=None)

Performs clustering on X and returns cluster labels.

Parameters:

X : ndarray, shape (n_samples, n_features)

Input data.

Returns:

y : ndarray, shape (n_samples,)

cluster labels

get_params(deep=True)

Get parameters for the estimator

Parameters:

deep: boolean, optional :

If True, will return the parameters for this estimator and contained subobjects that are estimators.

k

DEPRECATED: ‘k’ was renamed to n_clusters and will be removed in 0.15.

mode

DEPRECATED: ‘mode’ was renamed to eigen_solver and will be removed in 0.15.

set_params(**params)

Set the parameters of the estimator.

The method works on simple estimators as well as on nested objects (such as pipelines). The former have parameters of the form <component>__<parameter> so that it’s possible to update each component of a nested object.

Returns:self :