Embedding

Eigenvector Embedding

Spectral clustering techniques require the computation of the extreme eigenvectors of matrices derived from patterns similarity . The Laplacian matrix obtained from the data is generally used as the starting point for decomposition into autovectors. Given the symmetric matrix $ W (i, j) = w_{ij}, W \in R^{n \times n} $ that contains information about similarity between the patterns, if $ D = W \mathbf {1} $, the unnormalized Laplacian matrix is defined as $ L = D-W $.

The matrix $ W $ can be seen as the incidence matrix of a weighted graph. The Simmilarity graph creation utilities implement functions that allow the construction of simmilarty graphs.

The Embedding utilities contain the functions for performing the embedding of the patterns in the space spanned by the $ k $ eigenvectors of a matrix derived from $W$.

Currently the module implements the techniques described in:

Examples

Embedding examples

Bibliography

Bibliography
NJW002
Andrew Y Ng, Michael I Jordan, and Yair Weiss. On spectral clustering: analysis and an algorithm. In Advances in neural information processing systems. 2002.
SM000
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 2000.
YS001
Stella X Yu and Jianbo Shi. Understanding popout through repulsion. In Computer Vision and Pattern Recognition , 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on, volume 2. IEEE, 2001.
YS004
Stella X Yu and Jianbo Shi. Segmentation given partial grouping constraints. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004.
LHW007
Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. Trajectory clustering: a partition-and-group framework. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data. ACM, 2007.

Index

Content

SpectralClustering.NgLaplacian — Type.
type NgLaplacian <: AbstractEmbedding

Members

  • nev::Integer. The number of eigenvectors to obtain
  • normalize::Bool. Wether normalize the obtained eigenvectors

Given a affinity matrix $W \in \mathbb{R}^{n \times n}$. Ng et al defines the laplacian as $L = D^{-\frac{1}{2}} W D^{-\frac{1}{2}}$ where $D$ is a diagonal matrix whose (i,i)-element is the sum of W's i-th row.

The embedding function solves a relaxed version of the following optimization problem: ``\begin{array}{crclcl} \displaystyle \max_{ U \in \mathbb{R}^{n\times k} \hspace{10pt} } & \mathrm{Tr}(U^T L U) &\ \textrm{s.a.} {U^T U} = I && \end{array}``

U is a matrix that contains the nev largest eigevectors of $L$.

References

source
SpectralClustering.PartialGroupingConstraints — Type.
struct PartialGroupingConstraints <: AbstractEmbedding

Members

  • nev::Integer. The number of eigenvector to obtain.
  • smooth::Bool. Whether to user Smooth Constraints
  • normalize::Bool. Whether to normalize the rows of the obtained vectors

Segmentation Given Partial Grouping Constraints Stella X. Yu and Jianbo Shi

source
SpectralClustering.ShiMalikLaplacian — Type.

The normalized laplacian as defined in $D^{-\frac{1}{2}} (D-W) D^{-\frac{1}{2}}$.

References:

  • Spectral Graph Theory. Fan Chung
  • Normalized Cuts and Image Segmentation. Jiambo Shi and Jitendra Malik
type ShiMalikLaplacian <: AbstractEmbedding

Members

  • nev::Integer. The number of eigenvector to obtain.
  • normalize::Bool. Wether normalize the obtained eigenvectors
source
SpectralClustering.embedding — Method.
embedding(cfg::NgLaplacian, L::SparseMatrixCSC)

Performs the eigendecomposition of the laplacian matrix of the weight matrix $W$ defined according to NgLaplacian

source
SpectralClustering.embedding — Method.
embedding(cfg::NgLaplacian, W::CombinatorialAdjacency)

Performs the eigendecomposition of the laplacian matrix of the weight matrix $W$ defined according to NgLaplacian

source
SpectralClustering.embedding — Method.
embedding(cfg::NgLaplacian, L::NormalizedAdjacency)

Performs the eigendecomposition of the laplacian matrix of the weight matrix $W$ defined according to NgLaplacian

source
SpectralClustering.embedding — Method.
embedding(cfg::PartialGroupingConstraints, gr::Graph, restrictions::Vector{Vector{Integer}})

Arguments

  • cfg::PartialGroupingConstraints
  • L::NormalizedAdjacency
  • restrictions::Vector{Vector{Integer}}
source
SpectralClustering.embedding — Method.
function embedding(cfg::PartialGroupingConstraints, L::NormalizedAdjacency, restrictions::Vector{Vector{Integer}})

Arguments

  • cfg::PartialGroupingConstraints
  • L::NormalizedAdjacency
  • restrictions::Vector{Vector{Integer}}
source
SpectralClustering.embedding — Method.
embedding(cfg::NgLaplacian, W::CombinatorialAdjacency)

Performs the eigendecomposition of the laplacian matrix of the weight matrix $W$ defined according to NgLaplacian

source
SpectralClustering.embedding — Method.
embedding(cfg::ShiMalikLaplacian, L::NormalizedLaplacian)

Parameters

  • cfg::ShiMalikLaplacian. An instance of a ShiMalikLaplacian that specify the number of eigenvectors to obtain
  • gr::Union{Graph,SparseMatrixCSC}. The Graph(@ref Graph) or the weight matrix of wich is going to be computed the normalized laplacian matrix.

Performs the eigendecomposition of the normalized laplacian matrix of the laplacian matriz L defined acoording to ShiMalikLaplacian. Returns the cfg.nev eigenvectors associated with the non-zero smallest eigenvalues.

source
SpectralClustering.embedding — Method.
function embedding(cfg::YuShiPopout,  grA::Graph, grR::Graph)

References

  • Grouping with Directed Relationships. Stella X. Yu and Jianbo Shi
  • Understanding Popout through Repulsion. Stella X. Yu and Jianbo Shi
source
SpectralClustering.embedding — Method.
function embedding(cfg::YuShiPopout,  grA::Graph, grR::Graph)

References

  • Grouping with Directed Relationships. Stella X. Yu and Jianbo Shi
  • Understanding Popout through Repulsion. Stella X. Yu and Jianbo Shi
source
SpectralClustering.embedding — Method.
embedding(cfg::T, gr::Graph) where T<:AbstractEmbedding

Performs the eigendecomposition of the laplacian matrix of the weight matrix $W$ derived from the graph gr defined according to NgLaplacian

source
SpectralClustering.embedding — Method.
embedding{T<:AbstractEmbedding}(cfg::T, neighborhood::VertexNeighborhood, oracle::Function, data)
source
SpectralClustering.PGCMatrix — Type.
struct PGCMatrix{T,I,F} <: AbstractMatrix{T}

Partial grouping constraint structure. This sturct is passed to eigs to performe the L*x computation according to (41), (42) and (43) of ""Segmentation Given Partial Grouping Constraints""

source