Package elki.clustering.hierarchical.linkage

Class MinimumVarianceLinkage

  • All Implemented Interfaces:
    Linkage
    @Reference(authors="J. Podani",title="New Combinatorial Clustering Methods",booktitle="Vegetatio 81(1/2)",url="https://doi.org/10.1007/978-94-009-2432-1_5",bibkey="doi:10.1007/978-94-009-2432-1_5") @Reference(authors="E. Diday, J. Lemaire, J. Pouget, F. Testu",title="Elements d\'analyse de donnees",booktitle="",bibkey="books/misc/DidayLPT85")
@Alias("variance")
public class MinimumVarianceLinkage
extends java.lang.Object
implements Linkage
    Minimum increase in variance (MIVAR) linkage.

    This is subtly different from Ward's method (WardLinkage, MISSQ), because variance is normalized by the cluster size; and Ward minimizes the increase in sum of squares (without normalization). \[d_{\text{MIVAR}}(A\cup B,C)= \left(\tfrac{|A|+|C|}{|A|+|B|+|C|}\right)^2 d(A,C) + \left(\tfrac{|B|+|C|}{|A|+|B|+|C|}\right)^2 d(B,C) - \tfrac{|C|\cdot(|A|+|B|)}{(|A|+|B|+|C|)^2} d(A,B)\] or equivalently: \[d_{\text{MIVAR}}(A\cup B,C)=\tfrac{(|A|+|C|)^2 d(A,C) + (|B|+|C|)^2 d(B,C) - |C|\cdot(|A|+|B|) d(A,B)}{(|A|+|B|+|C|)^2}\]

    Reference:

    J. Podani
    New Combinatorial Clustering Methods
    Vegetatio 81(1/2)

    attributes this to (but we did not verify):

    E. Diday, J. Lemaire, J. Pouget, F. Testu
    Elements d'analyse de donnees

    Since:
    0.7.5
    Author:
    Erich Schubert

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  MinimumVarianceLinkage.Par
      Class parameterizer.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      double combine​(int sizex, double dx, int sizey, double dy, int sizej, double dxy)
      Compute combined linkage for two clusters.
      double initial​(double d, boolean issquare)
      Initialization of the distance matrix.
      double restore​(double d, boolean issquare)
      Restore a distance to the original scale.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • MinimumVarianceLinkage

        @Deprecated
public MinimumVarianceLinkage()
        Deprecated.
        use the static instance STATIC instead.
        Constructor.

    • Method Detail

      • initial

        public double initial​(double d,
                      boolean issquare)
        Description copied from interface: Linkage
        Initialization of the distance matrix.
        Specified by:
        initial in interface Linkage
        Parameters:
        d - Distance
        issquare - Flag to indicate the input values are already squared
        Returns:
        Initial value

      • restore

        public double restore​(double d,
                      boolean issquare)
        Description copied from interface: Linkage
        Restore a distance to the original scale.
        Specified by:
        restore in interface Linkage
        Parameters:
        d - Distance
        issquare - Flag to indicate the input values were already squared
        Returns:
        Initial value

      • combine

        public double combine​(int sizex,
                      double dx,
                      int sizey,
                      double dy,
                      int sizej,
                      double dxy)
        Description copied from interface: Linkage
        Compute combined linkage for two clusters.
        Specified by:
        combine in interface Linkage
        Parameters:
        sizex - Size of first cluster x before merging
        dx - Distance of cluster x to j before merging
        sizey - Size of second cluster y before merging
        dy - Distance of cluster y to j before merging
        sizej - Size of candidate cluster j
        dxy - Distance between clusters x and y before merging
        Returns:
        Combined distance