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

Class AGNES<O>

java.lang.Object

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

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

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.AGNES<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Algorithm, HierarchicalClusteringAlgorithm, DistanceBasedAlgorithm<O>

@Reference(authors="L. Kaufman and P. J. Rousseeuw",
           title="Agglomerative Nesting (Program AGNES)",
           booktitle="Finding Groups in Data: An Introduction to Cluster Analysis",
           url="http://dx.doi.org/10.1002/9780470316801.ch5")
@Alias(value={"HAC","NaiveAgglomerativeHierarchicalClustering","de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.NaiveAgglomerativeHierarchicalClustering"})
public class AGNES<O>
extends AbstractDistanceBasedAlgorithm<O,PointerHierarchyRepresentationResult>
implements HierarchicalClusteringAlgorithm

Hierarchical Agglomerative Clustering (HAC) or Agglomerative Nesting (AGNES) is a classic hierarchical clustering algorithm. Initially, each element is its own cluster; the closest clusters are merged at every step, until all the data has become a single cluster. This is the naive O(n^3) algorithm. See SLINK for a much faster algorithm (however, only for single-linkage). This implementation uses the pointer-based representation used by SLINK, so that the extraction algorithms we have can be used with either of them. The algorithm is believed to be first published (for single-linkage) by:

P. H. Sneath
The application of computers to taxonomy
Journal of general microbiology, 17(1).

This algorithm is also known as AGNES (Agglomerative Nesting), where the use of alternative linkage criterions is discussed:

L. Kaufman and P. J. Rousseeuw
Agglomerative Nesting (Program AGNES),
in Finding Groups in Data: An Introduction to Cluster Analysis

Reference for the unified concept:

G. N. Lance and W. T. Williams
A general theory of classificatory sorting strategies 1. Hierarchical systems
The computer journal 9.4 (1967): 373-380.

See also:

R. M. Cormack
A Review of Classification
Journal of the Royal Statistical Society. Series A, Vol. 134, No. 3

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	AGNES.Parameterizer<O> Parameterization class

Field Summary

Fields

Modifier and Type	Field and Description
static Void	ADDITIONAL_REFERENCE Additional historical reference for single-linkage.
(package private) LinkageMethod	linkage Current linkage method in use.
private static Logging	LOG Class logger

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
AGNES(DistanceFunction<? super O> distanceFunction, LinkageMethod linkage) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected int	findMerge(int size, double[] scratch, DBIDArrayIter ix, DBIDArrayIter iy, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableIntegerDataStore csize) Perform the next merge step in AGNES.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected static <O> void	initializeDistanceMatrix(double[] scratch, DistanceQuery<O> dq, DBIDArrayIter ix, DBIDArrayIter iy, boolean square) Initialize a distance matrix.
protected void	merge(int size, double[] scratch, DBIDArrayIter ix, DBIDArrayIter iy, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableIntegerDataStore csize, double mindist, int x, int y) Execute the cluster merge.
PointerHierarchyRepresentationResult	run(Database db, Relation<O> relation) Run the algorithm
protected static int	triangleSize(int x) Compute the size of a complete x by x triangle (minus diagonal)
protected void	updateMatrix(int size, double[] scratch, DBIDArrayIter ij, WritableDoubleDataStore lambda, WritableIntegerDataStore csize, double mindist, int x, int y, int sizex, int sizey) Update the scratch distance matrix.

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

Class logger

linkage

LinkageMethod linkage

Current linkage method in use.

ADDITIONAL_REFERENCE

@Reference(authors="P. H. Sneath",
           title="The application of computers to taxonomy",
           booktitle="Journal of general microbiology, 17(1)",
           url="http://dx.doi.org/10.1099/00221287-17-1-201")
public static final Void ADDITIONAL_REFERENCE

Additional historical reference for single-linkage.

Constructor Detail

AGNES

public AGNES(DistanceFunction<? super O> distanceFunction,
     LinkageMethod linkage)

Constructor.

Parameters:

distanceFunction - Distance function to use

linkage - Linkage method

Method Detail

run

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

Run the algorithm

Parameters:

db - Database

relation - Relation

Returns:

Clustering hierarchy

triangleSize

protected static int triangleSize(int x)

Compute the size of a complete x by x triangle (minus diagonal)

Parameters:

x - Offset

Returns:

Size of complete triangle

initializeDistanceMatrix

protected static <O> void initializeDistanceMatrix(double[] scratch,
                                DistanceQuery<O> dq,
                                DBIDArrayIter ix,
                                DBIDArrayIter iy,
                                boolean square)

Initialize a distance matrix.

Parameters:

scratch - Scratch space to be used.

dq - Distance query

ix - Data iterator

iy - Data iterator

square - Flag to use squared distances.

findMerge

protected int findMerge(int size,
            double[] scratch,
            DBIDArrayIter ix,
            DBIDArrayIter iy,
            WritableDBIDDataStore pi,
            WritableDoubleDataStore lambda,
            WritableIntegerDataStore csize)

Perform the next merge step in AGNES.

Parameters:

size - Data set size

scratch - Scratch space.

ix - First iterator

iy - Second iterator

pi - Parent storage

lambda - Lambda (join distance) storage

csize - Cluster sizes

Returns:

x, for shrinking the working set.

merge

protected void merge(int size,
         double[] scratch,
         DBIDArrayIter ix,
         DBIDArrayIter iy,
         WritableDBIDDataStore pi,
         WritableDoubleDataStore lambda,
         WritableIntegerDataStore csize,
         double mindist,
         int x,
         int y)

Execute the cluster merge.

Parameters:

size - Data set size

scratch - Scratch space.

ix - First iterator

iy - Second iterator

pi - Parent storage

lambda - Lambda (join distance) storage

csize - Cluster sizes

mindist - Distance that was used for merging

x - First matrix position

y - Second matrix position

updateMatrix

protected void updateMatrix(int size,
                double[] scratch,
                DBIDArrayIter ij,
                WritableDoubleDataStore lambda,
                WritableIntegerDataStore csize,
                double mindist,
                int x,
                int y,
                int sizex,
                int sizey)

Update the scratch distance matrix.

Parameters:

size - Data set size

scratch - Scratch matrix.

ij - Iterator to reuse

lambda - Lambda (join distance) storage

csize - Cluster sizes

mindist - Distance that was used for merging

x - First matrix position

y - Second matrix position

sizex - Old size of first cluster

sizey - Old size of second cluster

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>

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>

Returns:

the static logger