de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical

Class SLINK<O,D extends Distance<D>>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,D,PointerHierarchyRepresentationResult<D>>

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.SLINK<O,D>

Type Parameters:

O - the type of DatabaseObject the algorithm is applied on

D - the type of Distance used

All Implemented Interfaces:

Algorithm, HierarchicalClusteringAlgorithm<D>, DistanceBasedAlgorithm<O,D>, Parameterizable

@Title(value="SLINK: Single Link Clustering")
@Description(value="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 (1973), No. 1, p. 30-34.",
           url="http://dx.doi.org/10.1093/comjnl/16.1.30")
@Alias(value={"de.lmu.ifi.dbs.elki.algorithm.clustering.SLINK","clustering.SLINK","SLINK","single-link","single-linkage"})
public class SLINK<O,D extends Distance<D>>
extends AbstractDistanceBasedAlgorithm<O,D,PointerHierarchyRepresentationResult<D>>
implements HierarchicalClusteringAlgorithm<D>

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

Reference:
R. Sibson: SLINK: An optimally efficient algorithm for the single-link cluster method.
In: The Computer Journal 16 (1973), No. 1, p. 30-34.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SLINK.Parameterizer<O,D extends Distance<D>> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG The logger for this class.

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
SLINK(DistanceFunction<? super O,D> distanceFunction) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
D	getDistanceFactory() Return the distance type that will be used by the algorithm.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
PointerHierarchyRepresentationResult<D>	run(Database database, Relation<O> relation) Performs the SLINK algorithm on the given database.
private void	step1(DBIDRef id, WritableDBIDDataStore pi, WritableDataStore<D> lambda) First step: Initialize P(id) = id, L(id) = infinity.
private void	step1double(DBIDRef id, WritableDBIDDataStore pi, WritableDoubleDistanceDataStore lambda) First step: Initialize P(id) = id, L(id) = infinity.
private void	step2(DBIDRef id, DBIDs processedIDs, DistanceQuery<O,D> distFunc, WritableDataStore<D> m) Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.
private void	step2double(DBIDRef id, DBIDs processedIDs, Relation<? extends O> relation, PrimitiveDoubleDistanceFunction<? super O> distFunc, WritableDoubleDistanceDataStore m) Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.
private void	step3(DBIDRef id, WritableDBIDDataStore pi, WritableDataStore<D> lambda, DBIDs processedIDs, WritableDataStore<D> m) Third step: Determine the values for P and L
private void	step3double(DBIDRef id, WritableDBIDDataStore pi, WritableDoubleDistanceDataStore lambda, DBIDs processedIDs, WritableDoubleDistanceDataStore m) Third step: Determine the values for P and L
private void	step4(DBIDRef id, WritableDBIDDataStore pi, WritableDataStore<D> lambda, DBIDs processedIDs) Fourth step: Actualize the clusters if necessary
private void	step4double(DBIDRef id, WritableDBIDDataStore pi, WritableDoubleDistanceDataStore lambda, DBIDs processedIDs) Fourth step: Actualize the clusters if necessary

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm

getDistanceFunction

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

makeParameterDistanceFunction, run

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.HierarchicalClusteringAlgorithm

run

Field Detail

LOG

private static final Logging LOG

The logger for this class.

Constructor Detail

SLINK

public SLINK(DistanceFunction<? super O,D> distanceFunction)

Constructor.

Parameters:

distanceFunction - Distance function

Method Detail

run

public PointerHierarchyRepresentationResult<D> run(Database database,
                                          Relation<O> relation)

Performs the SLINK algorithm on the given database.

step1

private void step1(DBIDRef id,
         WritableDBIDDataStore pi,
         WritableDataStore<D> lambda)

First step: Initialize P(id) = id, L(id) = infinity.

Parameters:

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

pi - Pi data store

lambda - Lambda data store

step2

private void step2(DBIDRef id,
         DBIDs processedIDs,
         DistanceQuery<O,D> distFunc,
         WritableDataStore<D> 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

processedIDs - the already processed ids

m - Data store

distFunc - Distance function to use

step3

private void step3(DBIDRef id,
         WritableDBIDDataStore pi,
         WritableDataStore<D> lambda,
         DBIDs processedIDs,
         WritableDataStore<D> m)

Third step: Determine the values for P and L

Parameters:

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

pi - Pi data store

lambda - Lambda data store

processedIDs - the already processed ids

m - Data store

step4

private void step4(DBIDRef id,
         WritableDBIDDataStore pi,
         WritableDataStore<D> lambda,
         DBIDs processedIDs)

Fourth step: Actualize the clusters if necessary

Parameters:

id - the id of the current object

pi - Pi data store

lambda - Lambda data store

processedIDs - the already processed ids

step1double

private void step1double(DBIDRef id,
               WritableDBIDDataStore pi,
               WritableDoubleDistanceDataStore lambda)

First step: Initialize P(id) = id, L(id) = infinity.

Parameters:

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

pi - Pi data store

lambda - Lambda data store

step2double

private void step2double(DBIDRef id,
               DBIDs processedIDs,
               Relation<? extends O> relation,
               PrimitiveDoubleDistanceFunction<? super O> distFunc,
               WritableDoubleDistanceDataStore 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

processedIDs - the already processed ids

m - Data store

relation - Data relation

distFunc - Distance function to use

step3double

private void step3double(DBIDRef id,
               WritableDBIDDataStore pi,
               WritableDoubleDistanceDataStore lambda,
               DBIDs processedIDs,
               WritableDoubleDistanceDataStore m)

Third step: Determine the values for P and L

Parameters:

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

pi - Pi data store

lambda - Lambda data store

processedIDs - the already processed ids

m - Data store

step4double

private void step4double(DBIDRef id,
               WritableDBIDDataStore pi,
               WritableDoubleDistanceDataStore lambda,
               DBIDs processedIDs)

Fourth step: Actualize the clusters if necessary

Parameters:

id - the id of the current object

pi - Pi data store

lambda - Lambda data store

processedIDs - the already processed ids

getDistanceFactory

public D getDistanceFactory()

Description copied from interface: HierarchicalClusteringAlgorithm

Return the distance type that will be used by the algorithm.

Specified by:

getDistanceFactory in interface HierarchicalClusteringAlgorithm<D extends Distance<D>>

Returns:

Distance factory.

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

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

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<PointerHierarchyRepresentationResult<D extends Distance<D>>>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<PointerHierarchyRepresentationResult<D extends Distance<D>>>

Returns:

the static logger