package jsat.clustering.evaluation;
import java.util.ArrayList;
import java.util.List;
import jsat.DataSet;
import jsat.SimpleDataSet;
import jsat.classifiers.DataPoint;
import jsat.clustering.ClustererBase;
import jsat.linear.MatrixStatistics;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
/**
* A measure for evaluating the quality of a clustering by measuring the
* distances of points to their centroids.
*
* @author Edward Raff
*/
public class DaviesBouldinIndex implements ClusterEvaluation
{
private DistanceMetric dm;
/**
* Creates a new DaviesBouldinIndex using the {@link EuclideanDistance}.
*/
public DaviesBouldinIndex()
{
this(new EuclideanDistance());
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public DaviesBouldinIndex(DaviesBouldinIndex toCopy)
{
this(toCopy.dm.clone());
}
/**
* Creates a new DaviesBouldinIndex
* @param dm the distance measure to use when computing
*/
public DaviesBouldinIndex(DistanceMetric dm)
{
this.dm = dm;
}
@Override
public double evaluate(int[] designations, DataSet dataSet)
{
return evaluate(ClustererBase.createClusterListFromAssignmentArray(designations, dataSet));
}
@Override
public double evaluate(List> dataSets)
{
/**
* Forumal for the DB measure
*
* /sigma + sigma \
* 1 __ n | i j|
* DB = - \ max |-----------------|
* n /__ i = 1 i neq j| d(c ,c ) |
* \ i j /
*
* where
* c_i is the centroid of cluster i
* sigma_i is the average distance of over point in cluster i to its centroid
* d(,) is a distance function
* n is the number of clusters
*/
List centroids = new ArrayList(dataSets.size());
double[] avrgCentriodDist = new double[dataSets.size()];
for(int i = 0; i < dataSets.size(); i++)
{
Vec mean = MatrixStatistics.meanVector(new SimpleDataSet(dataSets.get(i)));
centroids.add(mean);
for(DataPoint dp : dataSets.get(i))
avrgCentriodDist[i] += dm.dist(dp.getNumericalValues(), mean);
avrgCentriodDist[i]/=dataSets.get(i).size();
}
double dbIndex = 0;
for(int i = 0; i < dataSets.size(); i++)
{
double maxPenalty = Double.NEGATIVE_INFINITY;
for(int j = 0; j < dataSets.size(); j++)
{
if(j == i)
continue;
double penalty = (avrgCentriodDist[i] + avrgCentriodDist[j])/dm.dist(centroids.get(i), centroids.get(j));
maxPenalty = Math.max(maxPenalty, penalty);
}
dbIndex += maxPenalty;
}
return dbIndex / dataSets.size();
}
@Override
public DaviesBouldinIndex clone()
{
return new DaviesBouldinIndex(this);
}
}
Ads help maintain this website.