abstract type AbstractLandmarkSelection end

Abstract type that defines how to sample data points. Types that inherint from AbstractLandmarkSelection has to implements the following interface:

select_landmarks{L<:AbstractLandmarkSelection}(c::L, X)

The select_landmarksfunction returns an array with the indices of the sampled points.

Arguments

• c::T<:AbstractLandmarkSelecion. The landmark selection type.
• d::D<:DataAccessor. The DataAccessor type.
• X. The data. The data to be sampled.

struct CliqueNeighborhood <: VertexNeighborhood

CliqueNeighborhood specifies that the neighborhood for a given vertex $j$ in a graph of $n$ vertices are the remaining n-1 vertices.

Co-regularized Multi-view Spectral Clustering

Abhishek Kumar, Piyush Rai, Hal Daumé

type DNCuts

Multiscale Combinatorial Grouping for Image Segmentation and Object Proposal Generation

Jordi Pont-Tuset, Pablo Arbeláez, Jonathan T. Barron, Member, Ferran Marques, Jitendra Malik

struct EvenlySpacedLandmarkSelection <: AbstractLandmarkSelection

The EvenlySpacedLandmarkSelection selection method selects n evenly spaced points from a dataset.

Graph(n_vertices::Integer=0; vertex_type::DataType  = Any ,initial_value=nothing, weight_type::DataType = Float64)

Construct an undirected weighted grpah of n_vertices vertices.

struct KMeansClusterizer <: EigenvectorClusterizer
    k::Integer
    init::Symbol
end

struct KNNNeighborhood <: VertexNeighborhood
    k::Integer
    tree::KDTree
end

KNNNeighborhood specifies that the neighborhood for a given vertex $j$ are the $k$ nearest neighborgs. It uses a tree to search the nearest patterns.

Members

• k::Integer. The number of k nearest neighborgs to connect.
• tree::KDTree. Internal data structure.
• f::Function. Transformation function

KNNNeighborhood(X::Matrix, k::Integer)

Create the KNNNeighborhood type by building a k-nn tre from de data X

Return the indexes of the config.k nearest neigbors of the data point j of the data X.

Large Scale Spectral Clustering with Landmark-Based Representation Xinl ei Chen Deng Cai

Members

• landmark_selector::{T <: AbstractLandmarkSelection} Method for extracting landmarks
• number_of_landmarks::Integer Number of landmarks to obtain
• n_neighbors::Integer Number of nearest neighbors
• nev::Integer Number of eigenvectors
• w::Function Number of clusters to obtain
• normalize::Bool

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

• On Spectral Clustering: Analysis and an algorithm. Andrew Y. Ng, Michael I. Jordan, Yair Weiss

type NystromMethod{T<:AbstractLandmarkSelection}
landmarks_selector::T
number_of_landmarks::Integer
w::Function
nvec::Integer
end

The type NystromMethod proposed in Spectral Grouping Using the Nystrom Method by Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik. It has to be defined:

• landmarks_selector::T<:AbstractLandmarkSelection. A mechanism to select the sampled

points.

• number_of_landmarks::Integer. The number of points to sample
• w::Function. The weight function for compute the similiarity. The signature of the weight function has to be weight(i, j, e1,e2). Where e1 and e2 ara the data elements i-th and j-th respectivily, obtained via get_element, usually is a vector.
• nvec::Integer. The number of eigenvector to obtain.
• threaded::Bool. Default: True. Specifies whether the threaded version is used.

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

struct PixelNeighborhood  <: VertexNeighborhood

PixelNeighborhood defines neighborhood for a given pixel based in its spatial location. Given a pixel located at (x,y), returns every pixel inside $(x+e,y), (x-e,y)$ and $(x,y+e)(x,y-e)$.

Members

• e:: Integer. Defines the radius of the neighborhood.

struct RandomNeighborhood <: VertexNeighborhood
    k::Integer
end

For a given index jreturn k random vertices different from j

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

abstract type VertexNeighborhood end

The abstract type VertexNeighborhood provides an interface to query for the neighborhood of a given vertex. Every concrete type that inherit from VertexNeighborhood must define the function

neighbors{T<:VertexNeighborhood}(cfg::T, j::Integer, data)

which returns the neighbors list of the vertex j for the given data.

A view

struct View
    embedder::NgLaplacian
    lambda::Float64
end

Members

- embedder::EigenvectorEmbedder
- lambda::Float64

Multiclass Spectral Clustering

function assign!(vec::T, val::C) where T<:AbstractArray where C<:Colorant

This function assigns the components of the color component val to a vector v

function clusterize{T<:EigenvectorEmbedder, C<:EigenvectorClusterizer}(cfg::T, clus::C, X)

Given a set of patterns X generates an eigenvector space according to T<:EigenvectorEmbeddder and then clusterize the eigenvectors using the algorithm defined by C<:EigenvectorClusterize.

function connect!(g::Graph, i::Integer, neighbors::Vector, weigths::Vector)

connect!(g::Graph,i::Integer,j::Integer,w::Number)

Connect the vertex i with the vertex j with weight w.

create(w_type::DataType, neighborhood::VertexNeighborhood, oracle::Function,X)

Given a VertexNeighborhood, a simmilarity function oracle construct a simmilarity graph of the patterns in X.

create(cfg::RandomKGraph)

Construct a RandomKGraph such that every vertex is connected with other k random vertices.

create(neighborhood::VertexNeighborhood, oracle::Function,X)

Given a VertexNeighborhood, a simmilarity function oracle construct a simmilarity graph of the patterns in X.

disconnect(g::Graph,i::Integer,j::Integer)

Removes the edge that connects the i-th vertex to the j-th vertex.

embedding(cfg::CoRegularizedMultiView, X::Vector)

Arguments

- `cfg::CoRegularizedMultiView`
- `X::Vector{Graph}`

An example that shows how to use this methods is provied in the Usage section of the manual

embedding(cfg::LandmarkBasedRepresentation, X)

embedding(cfg::NgLaplacian, L::SparseMatrixCSC)

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

embedding(cfg::NgLaplacian, W::CombinatorialAdjacency)

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

embedding(cfg::NgLaplacian, L::NormalizedAdjacency)

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

embedding(cfg::NystromMethod, X)

This is an overloaded function

embedding(cfg::NystromMethod, landmarks::Vector{Int}, X)

Arguments

• cfg::[NystromMethod](@ref)
• landmarks::Vector{Int}
• x::Any

Return values

• (E, L): The approximated eigenvectors, the aprooximated eigenvalues

Performs the eigenvector embedding according to

embedding(cfg::NystromMethod, A::Matrix, B::Matrix, landmarks::Vector{Int})

Performs the eigenvector approximation given the two submatrices A and B.

embedding(cfg::PartialGroupingConstraints, gr::Graph, restrictions::Vector{Vector{Integer}})

Arguments

• cfg::PartialGroupingConstraints
• L::NormalizedAdjacency
• restrictions::Vector{Vector{Integer}}

function embedding(cfg::PartialGroupingConstraints, L::NormalizedAdjacency, restrictions::Vector{Vector{Integer}})

Arguments

• cfg::PartialGroupingConstraints
• L::NormalizedAdjacency
• restrictions::Vector{Vector{Integer}}

embedding(cfg::NgLaplacian, W::CombinatorialAdjacency)

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

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.

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

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

embedding(d::DNCuts, L)

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

embedding{T<:AbstractEmbedding}(cfg::T, neighborhood::VertexNeighborhood, oracle::Function, data)

function get_element!(o::Matrix,  img::Matrix{C}, i::Vector{Integer}) where C<:Colorant

get_element!{T<:AbstractArray}(vec::T,  img::Matrix{Gray}, i::Integer)

Return throughvec the intensity image element [x,y, i], where $x,y$ are the spatial position of the pixel and the value i of the pixel $(x,y)$.

function get_element( img::Matrix{RGB}, i::Vector)

function get_element(data::Array{T, 3}, i::Vector)  where T<:Number

local_scale(neighborhood::KNNNeighborhood, oracle::Function, X; k::Integer = 7)

Computes thescale of each pattern according to Self-Tuning Spectral Clustering. Return a matrix containing for every pattern the local_scale.

Arguments

- `neighborhood::KNNNeighborhood`
- `oracle::Function`
- `X`
  the data

"The selection of thescale $ \sigma $ can be done by studying thestatistics of the neighborhoods surrounding points $ i $ and $ j $ .i " Zelnik-Manor and Perona use $ \sigmai = d(si, sK) $ where sK$ is the $ K $ neighbor of point $ s_i $ . They "used a single value of $K=7$, which gave good results even for high-dimensional data " .

neighbors(config::CliqueNeighborhood, j::Integer, X)

Return every other vertex index different from $j$. See CliqueNeighborhood

neighbors(cfg::PixelNeighborhood, j::Integer, img)

Returns the neighbors of the pixel j according to the specified in PixelNeighborhood

number_of_patterns{T<:Any}(X::Matrix{T,3})

Return the number of pixels in the image

function random_graph(iterations::Integer; probs=[0.4,0.4,0.2], weight=()->5, debug=false)

Create a random graphs. probs is an array of probabilities. The function create a vertex with probability probs[1], connect two vertices with probability probs[2] and delete a vertex with probability probs[2]. The weight of the edges is given by weight

remove_vertex!(g::Graph,i::Integer)

Remove the i-th vertex.

select_landmarks(c::EvenlySpacedLandmarkSelection,n::Integer, X)

select_landmarks(c::RandomLandmarkSelection,d::T,n::Integer, X)

The function returns nrandom points according to RandomLandmarkSelection

Arguments

• c::RandomLandmarkSelection.
• n::Integer. The number of data points to sample.
• X. The data to be sampled.

 spatial_position(X::Matrix, i::Int)

Returns the sub indexes from the linear index i

target_vertex(e::Edge,v::Vertex)

Given an edge e and a vertex v returns the other vertex different from v

type Edge

type LargeScaleMultiView

Large-Scale Multi-View Spectral Clustering via Bipartite Graph. In AAAI (pp. 2750-2756).

Li, Y., Nie, F., Huang, H., & Huang, J. (2015, January).

Matlab implementation

Members

• k::Integer. Number of clusters.
• n_salient_points::Integer. Number of salient points.
• k_nn::Integer. k nearest neighbors.
• 'gamma::Float64`.

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""

struct RandomKGraph

The type RandomKGraph defines the parameters needed to create a random k-graph. Every vertex it is connected to k random neigbors.

Members

• number_of_vertices::Integer. Defines the number of vertices of the graph.
• k::Integer. Defines the minimum number of neighborhood of every vertex.

length(v::Vertex)

Return the number of edges connected to a given vertex.

adjacency_matrix(g[, T=Int; dir=:out])

Return a sparse adjacency matrix for a graph, indexed by [u, v] vertices. Non-zero values indicate an edge between u and v. Users may override the default data type (Int) and specify an optional direction.

Optional Arguments

dir=:out: :in, :out, or :both are currently supported.

Implementation Notes

This function is optimized for speed and directly manipulates CSC sparse matrix fields.

nv(g::Graph)

Return the number of vertices of g.

createAB(cfg::NystromMethod, X)

Arguments:

• cfg::NystromMethod
• X

#Return values

• Sub-matrix A
• Sub-matrix B
• Vector{Int}. The sampled points used build the sub-matrices

This is an overloaded method. Computes the submatrix A and B according to create_A_B(::NystromMethod, ::Vector{Int}, ::Any). Returns the two submatrices and the sampled points used to calcluate it

createAB(cfg::NystromMethod, landmarks::Vector{Int},X)

Arguments:

• cfg::NystromMethod. The method configuration.
• landmarks::Vector{T}. A vector of integer that containts the $n$ indexes sampled from the data.
• X is the data that containt $ N $ patterns.

Let $ W \in \mathbb{R}^{N \times N}, W = \begin{bmatrix} A & B^T \ B & C \end{bmatrix}, A \in \mathbb{R}^{ n \times n }, B \in \mathbb{R}^{(N-n) \times n}, C \in \mathbb{R}^{(N-n)\times (N-n)} $ . $A$ represents the subblock of weights among the random samples, $B$ contains the weights from the random samples to the rest of the pixels, and $C$ contains the weights between all of the remaining pixels. The function computes $A$ and $B$ from the data X using the weight function defined in cfg.

weight{T<:DataAccessor}(w::Function,d::T, i::Int,j::Int,X)

Invoke the weight function provided to compute the similarity between the pattern i and the pattern j.