ch.usi.inf.sape.hac.agglomeration

Class SingleLinkage

java.lang.Object

ch.usi.inf.sape.hac.agglomeration.SingleLinkage

All Implemented Interfaces:

AgglomerationMethod

public final class SingleLinkage
extends Object
implements AgglomerationMethod

The "single linkage", "minimum", "shortest distance", or "nearest neighbor" method is a graph-based approach. The distance between two clusters is calculated as the smallest distance between two objects in opposite clusters. This method tends to produce loosely bound large clusters with little internal cohesion. Linear, elongated clusters are formed as opposed to the more usual spherical clusters. This pheonomenon is called chaining. [The data analysis handbook. By Ildiko E. Frank, Roberto Todeschini] This method can cause "chaining" of clusters.

See Also:

The general form of the Lance-Williams matrix-update formula: d[(i,j),k] = ai*d[i,k] + aj*d[j,k] + b*d[i,j] + g*|d[i,k]-d[j,k]| For the "single linkage" method: ai = 0.5 aj = 0.5 b = 0 g = -0.5 Thus: d[(i,j),k] = 0.5*d[i,k] + 0.5*d[j,k] - 0.5*|d[i,k]-d[j,k]| = 0.5*d[i,k] + 0.5*d[j,k] - | 0.5*d[i,k] - 0.5*d[j,k] | = d[i,j]

Constructor Summary

Constructors

Constructor and Description
SingleLinkage()

Method Summary

Methods

Modifier and Type	Method and Description
double	computeDissimilarity(double dik, double djk, double dij, int ci, int cj, int ck) Compute the dissimilarity between the newly formed cluster (i,j) and the existing cluster k.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SingleLinkage

public SingleLinkage()

Method Detail

computeDissimilarity

public double computeDissimilarity(double dik,
                          double djk,
                          double dij,
                          int ci,
                          int cj,
                          int ck)

Description copied from interface: AgglomerationMethod

Compute the dissimilarity between the newly formed cluster (i,j) and the existing cluster k.

Specified by:

computeDissimilarity in interface AgglomerationMethod

Parameters:

dik - dissimilarity between clusters i and k

djk - dissimilarity between clusters j and k

dij - dissimilarity between clusters i and j

ci - cardinality of cluster i

cj - cardinality of cluster j

ck - cardinality of cluster k

Returns:

dissimilarity between cluster (i,j) and cluster k.

toString

public String toString()

Overrides:

toString in class Object