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

Class MiniMaxAnderberg<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.MiniMaxAnderberg<O>

All Implemented Interfaces:

Algorithm, HierarchicalClusteringAlgorithm, DistanceBasedAlgorithm<O>

@Reference(authors="M. R. Anderberg",
           title="Hierarchical Clustering Methods",
           booktitle="Cluster Analysis for Applications",
           bibkey="books/academic/Anderberg73/Ch6")
 @Priority(value=195)
public class MiniMaxAnderberg<O>
extends AbstractDistanceBasedAlgorithm<O,PointerHierarchyRepresentationResult>
implements HierarchicalClusteringAlgorithm

This is a modification of the classic MiniMax algorithm for hierarchical clustering using a nearest-neighbor heuristic for acceleration.

This optimization is attributed to M. R. Anderberg.

This particular implementation is based on AnderbergHierarchicalClustering

Reference:

M. R. Anderberg
Hierarchical Clustering Methods
Cluster Analysis for Applications
ISBN: 0120576503

Since:

0.7.5

Author:

Julian Erhard, Erich Schubert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
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
MiniMaxAnderberg(DistanceFunction<? super O> distanceFunction) Constructor.

Method Summary

Modifier and Type	Method and Description
protected void	findBest(int size, double[] scratch, double[] bestd, int[] besti, int j)
protected int	findMerge(int size, MatrixParadigm mat, DBIDArrayMIter prots, PointerHierarchyRepresentationBuilder builder, it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters, double[] bestd, int[] besti, DistanceQuery<O> dq) Perform the next merge step.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private static void	initializeNNCache(double[] scratch, double[] bestd, int[] besti) Initialize the NN cache.
protected void	merge(int size, MatrixParadigm mat, DBIDArrayMIter prots, PointerHierarchyRepresentationBuilder builder, it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters, DistanceQuery<O> dq, double[] bestd, int[] besti, int x, int y) Execute the cluster merge
PointerHierarchyRepresentationResult	run(Database db, Relation<O> relation) Run the algorithm
private void	updateCache(int size, double[] scratch, double[] bestd, int[] besti, int x, int y, int j, double d) Update the cache.
private void	updateMatrices(int size, MatrixParadigm mat, DBIDArrayMIter prots, PointerHierarchyRepresentationBuilder builder, it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters, DistanceQuery<O> dq, double[] bestd, int[] besti, int x, int y) Update the entries of the matrices that contain a distance to y, the newly merged cluster.

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

Constructor Detail

MiniMaxAnderberg

public MiniMaxAnderberg(DistanceFunction<? super O> distanceFunction)

Constructor.

Parameters:

distanceFunction - Distance function to use

Method Detail

run

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

Run the algorithm

Parameters:

db - Database

relation - Relation

Returns:

Clustering hierarchy

initializeNNCache

private static void initializeNNCache(double[] scratch,
                                      double[] bestd,
                                      int[] besti)

Initialize the NN cache.

Parameters:

scratch - Scratch space

bestd - Best distance

besti - Best index

findMerge

protected int findMerge(int size,
                        MatrixParadigm mat,
                        DBIDArrayMIter prots,
                        PointerHierarchyRepresentationBuilder builder,
                        it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters,
                        double[] bestd,
                        int[] besti,
                        DistanceQuery<O> dq)

Perform the next merge step.

Parameters:

size - size of the data set

mat - matrix view

prots - the prototypes of merges between clusters

builder - Result builder

clusters - the current clustering

bestd - the distances to the nearest neighboring cluster

besti - the nearest neighboring cluster

dq - the range query

Returns:

x, for shrinking the active set.

merge

protected void merge(int size,
                     MatrixParadigm mat,
                     DBIDArrayMIter prots,
                     PointerHierarchyRepresentationBuilder builder,
                     it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters,
                     DistanceQuery<O> dq,
                     double[] bestd,
                     int[] besti,
                     int x,
                     int y)

Execute the cluster merge

Parameters:

size - size of data set

mat - Matrix paradigm

prots - the prototypes of merges between clusters

builder - Result builder

clusters - the current clustering

dq - the range query

bestd - the distances to the nearest neighboring cluster

besti - the nearest neighboring cluster

x - first cluster to merge, with x > y

y - second cluster to merge, with y < x

updateMatrices

private void updateMatrices(int size,
                            MatrixParadigm mat,
                            DBIDArrayMIter prots,
                            PointerHierarchyRepresentationBuilder builder,
                            it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters,
                            DistanceQuery<O> dq,
                            double[] bestd,
                            int[] besti,
                            int x,
                            int y)

Update the entries of the matrices that contain a distance to y, the newly merged cluster.

Parameters:

size - size of data set

mat - matrix view

prots - the prototypes of merges between clusters

builder - Result builder

clusters - the current clustering

dq - the range query

bestd - the distances to the nearest neighboring cluster

besti - the nearest neighboring cluster

x - first cluster to merge, with x > y

y - second cluster to merge, with y < x

updateCache

private void updateCache(int size,
                         double[] scratch,
                         double[] bestd,
                         int[] besti,
                         int x,
                         int y,
                         int j,
                         double d)

Update the cache.

Parameters:

size - Working set size

scratch - Scratch matrix

bestd - Best distance

besti - Best index

x - First cluster

y - Second cluster, y < x

j - Updated value d(y, j)

d - New distance

findBest

protected void findBest(int size,
                        double[] scratch,
                        double[] bestd,
                        int[] besti,
                        int j)

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