de.lmu.ifi.dbs.elki.algorithm.clustering
Class SLINK<O extends DatabaseObject,D extends Distance<D>>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O,R>
          de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,D,MultiResult>
              de.lmu.ifi.dbs.elki.algorithm.clustering.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<O,MultiResult>, 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")
public class SLINK<O extends DatabaseObject,D extends Distance<D>>
extends DistanceBasedAlgorithm<O,D,MultiResult>

Efficient implementation of the 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.

Author:

Elke Achtert

Field Summary

private HashMap<Integer,D>	lambda The values of the function Lambda of the pointer representation.
private HashMap<Integer,D>	m The values of the helper function m to determine the pointer representation.
private HashMap<Integer,Integer>	pi The values of the function Pi of the pointer representation.
private static AssociationID<Distance<?>>	SLINK_LAMBDA Association ID for SLINK lambda value
private static AssociationID<Integer>	SLINK_PI Association ID for SLINK pi pointer

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

DISTANCE_FUNCTION_ID, DISTANCE_FUNCTION_PARAM

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug, logger

Constructor Summary

SLINK(Parameterization config)
Constructor, adhering to Parameterizable

Method Summary

protected MultiResult	runInTime(Database<O> database) Performs the SLINK algorithm on the given database.
private void	step1(int newID) First step: Initialize P(id) = id, L(id) = infinity.
private void	step2(int newID, ArrayList<Integer> processedIDs) Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.
private void	step3(int newID, ArrayList<Integer> processedIDs) Third step: Determine the values for P and L
private void	step4(int newID, ArrayList<Integer> processedIDs) Fourth step: Actualize the clusters if necessary

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

getDistanceFactory, getDistanceFunction

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

isTime, isVerbose, run, setTime, setVerbose

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, progress, verbose, warning

Methods inherited from class java.lang.Object

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

Field Detail

SLINK_PI

private static final AssociationID<Integer> SLINK_PI

Association ID for SLINK pi pointer

SLINK_LAMBDA

private static final AssociationID<Distance<?>> SLINK_LAMBDA

Association ID for SLINK lambda value

pi

private HashMap<Integer,Integer> pi

The values of the function Pi of the pointer representation.

lambda

private HashMap<Integer,D extends Distance<D>> lambda

The values of the function Lambda of the pointer representation.

m

private HashMap<Integer,D extends Distance<D>> m

The values of the helper function m to determine the pointer representation.

Constructor Detail

SLINK

public SLINK(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

Method Detail

runInTime

protected MultiResult runInTime(Database<O> database)
                         throws IllegalStateException

Performs the SLINK algorithm on the given database.

Specified by:

runInTime in class AbstractAlgorithm<O extends DatabaseObject,MultiResult>

Parameters:

database - the database to run the algorithm on

Returns:

the Result computed by this algorithm

Throws:

IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

step1

private void step1(int newID)

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

Parameters:

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

step2

private void step2(int newID,
                   ArrayList<Integer> processedIDs)

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

Parameters:

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

processedIDs - the already processed ids

step3

private void step3(int newID,
                   ArrayList<Integer> processedIDs)

Third step: Determine the values for P and L

Parameters:

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

processedIDs - the already processed ids

step4

private void step4(int newID,
                   ArrayList<Integer> processedIDs)

Fourth step: Actualize the clusters if necessary

Parameters:

newID - the id of the current object

processedIDs - the already processed ids