Ocean::ClusteringSpectral Class Reference

This class implements spectral clustering. More...

#include <ClusteringSpectral.h>

Public Member Functions
	ClusteringSpectral (const Matrix &affinityMatrix, const unsigned int numberCluster)
	Determines the symmetric Laplacian matrix of input given and computes the eigen system of the Laplacian matrix.
std::vector< Indices32 >	clusterRotation (RandomGenerator &randomGenerator, const unsigned int iterations=100u, const Scalar convergenceThreshold=Scalar(0.0001))
	Performances the actual clustering.

Static Protected Member Functions
static Matrix	determineLaplacianMatrix (const Matrix &affinityMatrix)
	Determines unnormalized graph Laplacian matrix.
template<bool tSimplify>
static Matrix	determineRandomWalkLaplacianMatrix (const Matrix &affinityMatrix)
	Determines normalized graph Laplacian matrix closely connected to a random walk.
template<bool tSimplify>
static Matrix	determineSymmetricLaplacianMatrix (const Matrix &affinityMatrix)
	Determines symmetric (normalized) graph Laplacian matrix.
template<typename T >
static bool	pairSortAscending (const std::pair< T, MatrixT< T > > &firstElem, const std::pair< T, MatrixT< T > > &secondElem)
	Sorts a list of eigenvectors with corresponding eigenvalues in ascending order.

Protected Attributes
Matrix	reducedEigenvectors
	Column matrix of eigen vectors ordered by eigen values and reduced to [numberCluster] vectors.

Detailed Description

This class implements spectral clustering.

Constructor & Destructor Documentation

ClusteringSpectral()

Ocean::ClusteringSpectral::ClusteringSpectral	(	const Matrix &	affinityMatrix,
		const unsigned int	numberCluster
	)

Determines the symmetric Laplacian matrix of input given and computes the eigen system of the Laplacian matrix.

Parameters

affinityMatrix	a square weight matrix derived from similarity matrix (must be non-negative)
numberCluster	number of cluster to be returned (0, infinity)

Member Function Documentation

clusterRotation()

std::vector< Indices32 > Ocean::ClusteringSpectral::clusterRotation	(	RandomGenerator &	randomGenerator,
		const unsigned int	iterations = 100u,
		const Scalar	convergenceThreshold = Scalar(0.0001)
	)

Performances the actual clustering.

The algorithm is implemented according to "Huang et al. Spectral rotation versus K-means in spectral clustering. AAAI'13". The initial cluster assignment is drawn at random and the algorithm does not restart, so a single call can settle in a local optimum and two calls can disagree.

Parameters

randomGenerator	The random generator used to draw the initial assignment, so that a caller can reproduce a result and can run several attempts
iterations	Upper limit of iterations to be performed [1, infinity)
convergenceThreshold	Differential threshold used as convergence criteria (0, infinity)

Returns

Indices of cluster elements (number of cluster was given in constructor)

determineLaplacianMatrix()

static Matrix Ocean::ClusteringSpectral::determineLaplacianMatrix ( const Matrix &  affinityMatrix )

staticprotected

Determines unnormalized graph Laplacian matrix.

L = D - W. W is the weight matrix and D is a diagonal matrix containing the row sum of W

Parameters

affinityMatrix

a square weight matrix derived from similarity matrix (must be non-negative)

Returns

Laplacian matrix

determineRandomWalkLaplacianMatrix()

template<bool tSimplify>

static Matrix Ocean::ClusteringSpectral::determineRandomWalkLaplacianMatrix ( const Matrix &  affinityMatrix )

staticprotected

Determines normalized graph Laplacian matrix closely connected to a random walk.

L = I - D^{-1} * W. W is the weight matrix, I is the identity matrix and D is a diagonal matrix containing the row sum of W

Template Parameters

tSimplify

indicating whether a simplified version is used, then substraction with identity matrix is obmitted. Mathematically wrong but commonly used

Parameters

affinityMatrix

a square weight matrix derived from similarity matrix (must be non-negative)

Returns

Laplacian matrix

determineSymmetricLaplacianMatrix()

template<bool tSimplify>

static Matrix Ocean::ClusteringSpectral::determineSymmetricLaplacianMatrix ( const Matrix &  affinityMatrix )

staticprotected

Determines symmetric (normalized) graph Laplacian matrix.

L = I - D^{-1/2} * W * D^{-1/2}. W is the weight matrix, I is the identity matrix and D is a diagonal matrix containing the row sum of W

Template Parameters

tSimplify

indicating whether a simplified version is used, then substraction with identity matrix is obmitted. Mathematically wrong but commonly used

Parameters

affinityMatrix

a square weight matrix derived from similarity matrix (must be non-negative)

Returns

Laplacian matrix

pairSortAscending()

template<typename T >

bool Ocean::ClusteringSpectral::pairSortAscending ( const std::pair< T, MatrixT< T > > &  firstElem, const std::pair< T, MatrixT< T > > &  secondElem  )

inlinestaticprotected

Sorts a list of eigenvectors with corresponding eigenvalues in ascending order.

Parameters

firstElem	First pair of eigenvalue and eigenvector
secondElem	Second pair of eigenvalue and eigenvector

Returns

first eigenvalue is smaller than eigenvalue of second element

Field Documentation

reducedEigenvectors

Matrix Ocean::ClusteringSpectral::reducedEigenvectors

protected

Column matrix of eigen vectors ordered by eigen values and reduced to [numberCluster] vectors.

---

The documentation for this class was generated from the following file:

• ClusteringSpectral.h