View Javadoc

    1   package baseCode.algorithm.learning.unsupervised.cluster;
    2
    3   import java.util.TreeSet;
    4
    5   import cern.colt.list.ObjectArrayList;
    6   import cern.colt.matrix.DoubleMatrix2D;
    7   import cern.colt.matrix.impl.DenseDoubleMatrix2D;
    8
    9   /***
    10   * Start with all items in separate clusters.
    11   *
    12   * Compute the distances between all clusters
    13   *
    14   * Find the clusters with the highest similarity. Combine them into one cluster
    15   *
    16   * Iterate until there is only one cluster.
    17   *
    18   * Output: for each cluster, print the clusters it contains.
    19   *
    20   *
    21   * <hr>
    22   * <p>
    23   * Copyright (c) 2004 Columbia University
    24   *
    25   * @author pavlidis
    26   * @version $Id: HierarchicalClusterer.java,v 1.6 2004/08/14 15:19:05 pavlidis Exp $
    27   */
    28  public class HierarchicalClusterer extends ClusteringAlgorithm {
    29
    30     /***
    31      * How many values we cache
    32      */
    33     int STORED = 10;
    34
    35     /***
    36      * At the end of the run, this contains the cluster tree.
    37      */
    38     ClusterNode nodes;
    39
    40
    41     /***
    42      * Distance matrix
    43      */
    44     DoubleMatrix2D distances;
    45
    46     /***
    47      * The objects that are getting clustered.
    48      */
    49     ObjectArrayList objects;
    50
    51     /***
    52      * @param c Objects to be clustered. These must be Distanceable
    53      */
    54     public HierarchicalClusterer( ObjectArrayList c ) {
    55        this.objects = c;
    56        distances = new DenseDoubleMatrix2D( c.size(), c.size() );
    57     }
    58
    59     /***
    60      * Perform a hierarchical clustering on the objects.
    61      *
    62      * Initialize: compute the distances between all objects.
    63      *    Find the closest pair to initialize the clustering.
    64      *
    65      *
    66      *
    67      * @see baseCode.algorithm.learning.unsupervised.cluster.Algorithm#Run()
    68      */
    69     public void run() {
    70
    71        // keep a running list of the best distances.
    72        TreeSet closestPairs = new TreeSet();
    73        AverageLinkageDistancer ald = new AverageLinkageDistancer();
    74        closestPairs.add( new ClusterNode( Double.MAX_VALUE, null, null ) );
    75
    76        // compute all the distances. Keep track of the best distances.
    77        for ( int i = 0; i < objects.size(); i++ ) {
    78           Cluster elA = ( Cluster ) objects.elements()[i];
    79           for ( int j = i + 1; j < objects.size(); j++ ) {
    80              Cluster elB = ( Cluster ) objects.elements()[j];
    81              double d = elA.distanceTo( elB );
    82              distances.setQuick( i, j, d );
    83              distances.setQuick( j, i, d );
    84              if ( closestPairs.first() == null
    85                    || d < ( ( ClusterNode ) closestPairs.first() ).getDistance() ) {
    86                 closestPairs.add( new ClusterNode( d, elA, elB ) );
    87                 if ( closestPairs.size() > STORED ) {
    88                    closestPairs.remove( closestPairs.last() );
    89                 }
    90              }
    91           }
    92        }
    93
    94        // make a new cluster.
    95
    96
    97
    98        // while there are still nodes left, keep finding the closest pairs.
    99
    100
    101
    102
    103
    104    }
    105
    106    /***
    107     * @return
    108     */
    109    public Object[] getResults() {
    110       // TODO Auto-generated method stub
    111       return null;
    112    }
    113
    114 }
    115
    116 /* just a helper to store the infor about a cluster node. */
    117
    118 class ClusterNode implements Comparable {
    119    private double distance;
    120    private Cluster firstThing;
    121    private Cluster secondThing;
    122
    123    /***
    124     * @param distance double
    125     * @param firstThing Cluster
    126     * @param secondThing Cluster
    127     */
    128    public ClusterNode( double distance, Cluster firstThing, Cluster secondThing ) {
    129       super();
    130       this.distance = distance;
    131       this.firstThing = firstThing;
    132       this.secondThing = secondThing;
    133    }
    134
    135    public double getDistance() {
    136       return distance;
    137    }
    138
    139    public void setDistance( double distance ) {
    140       this.distance = distance;
    141    }
    142
    143    public Cluster getFirstThing() {
    144       return firstThing;
    145    }
    146
    147    public void setFirstThing( Cluster firstThing ) {
    148       this.firstThing = firstThing;
    149    }
    150
    151    public Cluster getSecondThing() { // this could be another cluster node.
    152       return secondThing;
    153    }
    154
    155    public void setSecondThing( Cluster secondThing ) {
    156       this.secondThing = secondThing;
    157    }
    158
    159    /* (non-Javadoc)
    160     * @see java.lang.Comparable#compareTo(java.lang.Object)
    161     */
    162    public int compareTo( Object o ) {
    163       // TODO Auto-generated method stub
    164       return 0;
    165    }
    166 }
    167