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.utilities.optionhandling.AbstractParameterizable
          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

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.
protected MultiResult	result Provides the result of the algorithm.
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.utilities.optionhandling.AbstractParameterizable

optionHandler

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

debug, logger

Constructor Summary

SLINK()
Creates a new instance of a single link algorithm.

Method Summary

Description	getDescription() Returns a description of the algorithm.
MultiResult	getResult() Returns the result of the algorithm.
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

getDistanceFunction, setParameters

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.utilities.optionhandling.AbstractParameterizable

addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription

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

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, collectOptions, getParameters, shortDescription

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.

result

protected MultiResult result

Provides the result of the algorithm.

Constructor Detail

SLINK

public SLINK()

Creates a new instance of a single link algorithm. Since SLINK is a non abstract class the option handler is initialized.

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

getResult

public MultiResult getResult()

Returns the result of the algorithm.

Returns:

the result of the algorithm

getDescription

public Description getDescription()

Returns a description of the algorithm.

Returns:

a description of the algorithm

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