Shared farthest neighbour approach to clustering

Supplementary information

Introduction

The shared farthest neighbour approach to clustering is a method presented in a paper published on the Pattern Recognition journal:

Citation:
S. Rovetta, F. Masulli. Shared farthest neighbor approach to clustering of high dimensionality, low cardinality data. Pattern Recognition, Volume 39, Issue 12 (December 2006). Pages: 2415-2425. ISSN:0031-3203
DOI link:
10.1016/j.patcog.2006.06.021
Bibtex:
@article{Rovetta-PatternRecognition-2006,
  Author="Stefano Rovetta and Francesco Masulli",
  Title="Shared farthest neighbor approach to clustering of high
    dimensionality, low cardinality data",
  Journal="Pattern Recognition",
  Year="2006",
  Volume="39",
  Number="12",
  pages="2415-2425",
  Month="December",
  DOI="http://dx.doi.org/10.1016/j.patcog.2006.06.021"
}

It is a hierarchical, top-down, non-dichotomic clustering technique suitable for data sets having dimensionality much larger than cardinality.

This page includes additional material for the paper.

List of additional material

Pseudocode
Pseudocode listing of a possible implementation of the proposed approach
Software implementation
A software implementation is provided in the C language.

Pseudocode

Algorithm SFN
-------------
Data structures: 
   matrix D (n x n)
   matrix I (n x n)
   matrix R (n x n)
Input:
   training set X (cardinality n)

Compute D = proximity matrix for X according to δ
Compute R = ranks  of distances in D 
// (within each row)
Compute I = index matrix
// (by swapping cell contents with indexes in R)
for i = n to 1 {
   Sort rows of I using column i as key 
} 
Output:
   clusters 
// clusters at hierarchical depth i share the
// same value in column i of matrix I
end algorithm
Box 1 Pseudocode of a possible implementation of the method.

Software implementation