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>

Direct Known Subclasses:

NNChain

@Reference(authors="L. Kaufman, P. J. Rousseeuw",title="Agglomerative Nesting (Program AGNES)",booktitle="Finding Groups in Data: An Introduction to Cluster Analysis",url="https://doi.org/10.1002/9780470316801.ch5",bibkey="doi:10.1002/9780470316801.ch5") @Reference(authors="P. H. Sneath",title="The application of computers to taxonomy",booktitle="Journal of general microbiology, 17(1)",url="https://doi.org/10.1099/00221287-17-1-201",bibkey="doi:10.1099/00221287-17-1-201") @Reference(authors="R. M. Cormack",title="A Review of Classification",booktitle="Journal of the Royal Statistical Society. Series A, Vol. 134, No. 3",url="https://doi.org/10.2307/2344237",bibkey="doi:10.2307/2344237")
 @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³) 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, 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, 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

Since:

0.6.0

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
(package private) Linkage	linkage Current linkage method in use.
private static Logging	LOG Class logger

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

ALGORITHM_ID

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, Linkage linkage) Constructor.

Method Summary

Modifier and Type	Method and Description
protected int	findMerge(int end, MatrixParadigm mat, PointerHierarchyRepresentationBuilder builder) 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 void	initializeDistanceMatrix(MatrixParadigm mat, DistanceQuery<?> dq, Linkage linkage) Initialize a distance matrix.
protected void	merge(int end, MatrixParadigm mat, PointerHierarchyRepresentationBuilder builder, double mindist, int x, int y) Execute the cluster merge.
PointerHierarchyRepresentationResult	run(Database db, Relation<O> relation) Run the algorithm
protected static int	shrinkActiveSet(DBIDArrayIter ix, PointerHierarchyRepresentationBuilder builder, int end, int x) Shrink the active set: if the last x objects are all merged, we can reduce the working size accordingly.
protected void	updateMatrix(int end, MatrixParadigm mat, PointerHierarchyRepresentationBuilder builder, 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

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

Linkage linkage

Current linkage method in use.

Constructor Detail

AGNES

public AGNES(DistanceFunction<? super O> distanceFunction,
             Linkage 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

shrinkActiveSet

protected static int shrinkActiveSet(DBIDArrayIter ix,
                                     PointerHierarchyRepresentationBuilder builder,
                                     int end,
                                     int x)

Shrink the active set: if the last x objects are all merged, we can reduce the working size accordingly.

Parameters:

ix - Object iterator

builder - Builder to detect merged status

end - Current active set size

x - Last merged object

Returns:

New active set size

initializeDistanceMatrix

protected static void initializeDistanceMatrix(MatrixParadigm mat,
                                               DistanceQuery<?> dq,
                                               Linkage linkage)

Initialize a distance matrix.

Parameters:

mat - Matrix

dq - Distance query

linkage - Linkage method

findMerge

protected int findMerge(int end,
                        MatrixParadigm mat,
                        PointerHierarchyRepresentationBuilder builder)

Perform the next merge step in AGNES.

Parameters:

end - Active set size

mat - Matrix storage

builder - Pointer representation builder

Returns:

the index that has disappeared, for shrinking the working set

merge

protected void merge(int end,
                     MatrixParadigm mat,
                     PointerHierarchyRepresentationBuilder builder,
                     double mindist,
                     int x,
                     int y)

Execute the cluster merge.

Parameters:

end - Active set size

mat - Matrix paradigm

builder - Hierarchy builder

mindist - Distance that was used for merging

x - First matrix position

y - Second matrix position

updateMatrix

protected void updateMatrix(int end,
                            MatrixParadigm mat,
                            PointerHierarchyRepresentationBuilder builder,
                            double mindist,
                            int x,
                            int y,
                            int sizex,
                            int sizey)

Update the scratch distance matrix.

Parameters:

end - Active set size

mat - Matrix view

builder - Hierarchy builder (to get 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