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>
              de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,D>
                  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>, Loggable, Parameterizable

public class SLINK<O extends DatabaseObject,D extends Distance<D>>
extends DistanceBasedAlgorithm<O,D>

Efficient implementation of the Single-Link Algorithm SLINK of R. Sibson.

Author:

Elke Achtert

Nested Class Summary

class

SLINK.SLinkDistance Encapsulates the distance between two objects and their ids.

Field Summary

private HashMap<Integer,SLINK.SLinkDistance>	lambda The values of the function Lambda of the pointer representation.
private HashMap<Integer,SLINK.SLinkDistance>	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 Result<O>	result Provides the result of the algorithm.

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

Constructor Summary

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

Method Summary

Description	getDescription() Returns a description of the algorithm.
Result<O>	getResult() Returns the result of the algorithm.
private SLINK.SLinkDistance	min(SLINK.SLinkDistance d1, SLINK.SLinkDistance d2) Returns the minimum distance of the two given distances.
protected void	runInTime(Database<O> database) Runs the algorithm.
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

getAttributeSettings, getDistanceFunction, setParameters

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

description, isTime, isVerbose, run, setTime, setVerbose

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

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

debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, 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, getParameters, getPossibleOptions, inlineDescription

Field Detail

pi

private HashMap<Integer,Integer> pi

The values of the function Pi of the pointer representation.

lambda

private HashMap<Integer,SLINK.SLinkDistance> lambda

The values of the function Lambda of the pointer representation.

m

private HashMap<Integer,SLINK.SLinkDistance> m

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

result

protected Result<O extends DatabaseObject> result

Provides the result of the algorithm.

Constructor Detail

SLINK

public SLINK()

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

Method Detail

runInTime

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

Runs the algorithm.

Specified by:

runInTime in class AbstractAlgorithm<O extends DatabaseObject>

Parameters:

database - the database to run the algorithm on

Throws:

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

getResult

public Result<O> 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

min

private SLINK.SLinkDistance min(SLINK.SLinkDistance d1,
                                SLINK.SLinkDistance d2)

Returns the minimum distance of the two given distances.

Parameters:

d1 - the first distance

d2 - the second distance

Returns:

the minimum distance of the two given distances