Package elki.clustering.hierarchical

Class SLINK<O>

java.lang.Object

elki.clustering.hierarchical.SLINK<O>

Type Parameters:

O - the type of DatabaseObject the algorithm is applied on

All Implemented Interfaces:

Algorithm, HierarchicalClusteringAlgorithm

Direct Known Subclasses:

CLINK

@Title("SLINK: Single Link Clustering")
@Description("Hierarchical clustering algorithm based on single-link connectivity.")
@Reference(authors="R. Sibson",
           title="SLINK: An optimally efficient algorithm for the single-link cluster method",
           booktitle="The Computer Journal 16 (1)",
           url="https://doi.org/10.1093/comjnl/16.1.30",
           bibkey="DBLP:journals/cj/Sibson73")
@Alias({"single-link","single-linkage"})
@Priority(200)
public class SLINK<O>
extends java.lang.Object
implements HierarchicalClusteringAlgorithm

Implementation of the efficient Single-Link Algorithm SLINK of R. Sibson.

For ELKI 0.8.0, this was rewritten to no longer use the original "pointer" output format, but instead generate an easier to use merge history now.

This is probably the fastest exact single-link algorithm currently in use.

Reference:

R. Sibson
SLINK: An optimally efficient algorithm for the single-link cluster method
In: The Computer Journal 16 (1)

Since:

0.6.0

Author:

Elke Achtert, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	SLINK.Par<O>	Parameterization class.

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

Modifier and Type	Field	Description
protected Distance<? super O>	distance	Distance function used.
private static Logging	LOG	The logger for this class.

Constructor Summary

Constructors

Constructor	Description
SLINK(Distance<? super O> distance)	Constructor.

Method Summary

Modifier and Type	Method	Description
protected static ClusterMergeHistoryBuilder	convertOutput(ClusterMergeHistoryBuilder builder, ArrayDBIDs oids, DBIDDataStore pi, DoubleDataStore lambda)	Convert a SLINK pointer representation to a cluster merge history.
TypeInformation[]	getInputTypeRestriction()	Get the input type restriction used for negotiating the data query.
protected Logging	getLogger()	Get the (static) class logger.
protected void	process(DBIDRef id, ArrayDBIDs ids, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)	SLINK main loop.
ClusterMergeHistory	run(Relation<O> relation)	Performs the SLINK algorithm on the given database.
private void	slinkstep3(DBIDRef id, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)	Third step: Determine the values for P and L
private void	slinkstep4(DBIDRef id, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda)	Fourth step: Actualize the clusters if necessary
private void	step2(DBIDRef id, DBIDArrayIter it, int n, DistanceQuery<? super O> distQuery, WritableDoubleDataStore m)	Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.
private void	step2primitive(DBIDRef id, DBIDArrayIter it, int n, Relation<? extends O> relation, PrimitiveDistance<? super O> distance, WritableDoubleDataStore m)	Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface elki.clustering.hierarchical.HierarchicalClusteringAlgorithm

autorun

Field Detail

LOG

private static final Logging LOG

The logger for this class.

distance

protected Distance<? super O> distance

Distance function used.

Constructor Detail

SLINK

public SLINK(Distance<? super O> distance)

Constructor.

Parameters:

distance - Distance function

Method Detail

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from interface: Algorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Returns:

Type restriction

run

public ClusterMergeHistory run(Relation<O> relation)

Performs the SLINK algorithm on the given database.

Parameters:

relation - Data relation to use

convertOutput

protected static ClusterMergeHistoryBuilder convertOutput(ClusterMergeHistoryBuilder builder,
                                                          ArrayDBIDs oids,
                                                          DBIDDataStore pi,
                                                          DoubleDataStore lambda)

Convert a SLINK pointer representation to a cluster merge history.

Parameters:

builder - Builder

oids - original DBIDs

pi - Parent pointer

lambda - Parent distance

Returns:

Builder

step2

private void step2(DBIDRef id,
                   DBIDArrayIter it,
                   int n,
                   DistanceQuery<? super O> distQuery,
                   WritableDoubleDataStore m)

Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.

Parameters:

id - the id of the object to be inserted into the pointer representation

it - Array iterator

n - Last object

distQuery - Distance query

m - Data store

step2primitive

private void step2primitive(DBIDRef id,
                            DBIDArrayIter it,
                            int n,
                            Relation<? extends O> relation,
                            PrimitiveDistance<? super O> distance,
                            WritableDoubleDataStore m)

Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.

Parameters:

id - the id of the object to be inserted into the pointer representation

it - Array iterator

n - Last object

m - Data store

relation - Data relation

distance - Distance function to use

process

protected void process(DBIDRef id,
                       ArrayDBIDs ids,
                       DBIDArrayIter it,
                       int n,
                       WritableDBIDDataStore pi,
                       WritableDoubleDataStore lambda,
                       WritableDoubleDataStore m)

SLINK main loop.

Parameters:

id - Current object

ids - All objects

it - Array iterator

n - Last object to process at this run

pi - Parent

lambda - Height

m - Distance

slinkstep3

private void slinkstep3(DBIDRef id,
                        DBIDArrayIter it,
                        int n,
                        WritableDBIDDataStore pi,
                        WritableDoubleDataStore lambda,
                        WritableDoubleDataStore m)

Third step: Determine the values for P and L

Parameters:

id - the id of the object to be inserted into the pointer representation

it - array iterator

n - Last object to process at this run

pi - Pi data store

lambda - Lambda data store

m - Data store

slinkstep4

private void slinkstep4(DBIDRef id,
                        DBIDArrayIter it,
                        int n,
                        WritableDBIDDataStore pi,
                        WritableDoubleDataStore lambda)

Fourth step: Actualize the clusters if necessary

Parameters:

id - the id of the current object

it - array iterator

n - Last object to process at this run

pi - Pi data store

lambda - Lambda data store

getLogger

protected Logging getLogger()

Get the (static) class logger.