Simmilarity graph creation

A weighted graph is an ordered pair $G=(V,E)$ that is composed of a set $V$ of vertices together with a set $E$ of edges $(i,j,w)$ $i,j \in V,w \in R$. The number $w$, the weight, represent the simmilarity between $i$ and $j$.

In order to build a simmilarity graph two elements have to be defined:

Which are the neighbors for a given vertex. For this, a concrete type that inherit from NeighborhoodConfig has to be instantiated.
The simmilarity function between patterns. The function receives the element being evaluated and its neighbors and returns a vector with the simmilarities between them. The signature of the function has to be the following function weight(i::Integer, j::Vector{Integer}, e1, e2) where i::Int is the index of the pattern being evaluated, j::Vector{Integer} are the indices of the neighbors of i; e1 are the i-th pattern and e2 are the neighbors patterns.

Examples

Graph creation examples

Bibliography

ZmP004: Lihi Zelnik-manor and Pietro Perona. Self-tuning spectral clustering. In Advances in Neural Information Processing Systems 17. MIT Press, 2004.

Reference

Index

Content

SpectralClustering.CliqueNeighborhood — Type.

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.

source

SpectralClustering.KNNNeighborhood — Type.

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

source

SpectralClustering.KNNNeighborhood — Type.

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.

source

SpectralClustering.PixelNeighborhood — Type.

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.

source

SpectralClustering.RandomNeighborhood — Type.

struct RandomNeighborhood <: VertexNeighborhood
    k::Integer
end

For a given index jreturn k random vertices different from j

source

SpectralClustering.VertexNeighborhood — Type.

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.

source

SpectralClustering.create — Method.

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.

source

SpectralClustering.create — Method.

create(cfg::RandomKGraph)

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

source

SpectralClustering.create — Method.

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

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

source

SpectralClustering.local_scale — Method.

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

source

SpectralClustering.neighbors — Method.

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

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

source

SpectralClustering.neighbors — Method.

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

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

source

SpectralClustering.RandomKGraph — Type.

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.

source

SpectralClustering.weight — Method.

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.

source