* In the present implementation, objects of type
* DiscreteDistribution are in fact immutable,
* so all one can do is create objects and retrieve information,
* such as median and mean, from them.
*
* This implementation is part of the master's thesis: "Studie * en implementatie van instantie-gebaseerde algoritmen voor gesuperviseerd * rangschikken", Stijn Lievens, Ghent University, 2004. *
* * @author Stijn Lievens (stijn.lievens@ugent.be) * @version $Revision: 5922 $ */ public class DiscreteDistribution implements Serializable, RevisionHandler { /** for serialization. */ private static final long serialVersionUID = 1954630934425689828L; /** * small tolerance to account for rounding errors when working * with doubles */ private static final double TOLERANCE=Utils.SMALL; /** the array of probabilities */ private double[] m_dd; /** * Create a DiscreteDistribution based on a
* DiscreteEstimator.
*
* @param e the DiscreteEstimator
*/
public DiscreteDistribution(DiscreteEstimator e) {
m_dd = new double[e.getNumSymbols()];
for (int i = 0; i < m_dd.length; i++) {
m_dd[i] = e.getProbability(i);
}
}
/**
* Create a DiscreteDistribution based on a
* CumulativeDiscreteDistribution.
*
* @param cdf the CumulativeDiscreteDistribution
*/
public DiscreteDistribution(CumulativeDiscreteDistribution cdf) {
m_dd = new double[cdf.getNumSymbols()];
if (m_dd.length != 0) {
m_dd[0] = cdf.getCumulativeProbability(0);
}
for (int i = 1; i < m_dd.length; i++) {
m_dd[i] = cdf.getCumulativeProbability(i)
- cdf.getCumulativeProbability(i - 1);
}
}
/**
* Create a DiscreteDistribution based on an
* array of doubles.
*
* @param dd the array of doubles representing a valid
* discrete distribution
* @throws IllegalArgumentException if dd
* does not represent a valid discrete distribution
*/
public DiscreteDistribution(double[] dd) throws IllegalArgumentException {
if (!validDiscreteDistribution(dd)) {
throw new IllegalArgumentException
("Not a valid discrete distribution");
}
m_dd = new double[dd.length];
System.arraycopy(dd,0,m_dd,0,dd.length);
}
/**
* Get the number of elements over which the
* DiscreteDistribution is defined.
*
* @return the number of elements over which the
* DiscreteDistribution is defined
*/
public int getNumSymbols() {
return (m_dd != null) ? m_dd.length : 0;
}
/**
* Get the probability of finding the element at
* a specified index.
*
* @param index the index of the required element
* @return the probability of finding the specified element
*/
public double getProbability(int index) {
return m_dd[index];
}
/**
* Calculate the mean of the distribution. The scores for
* calculating the mean start from 0 and have step size one,
* i.e. if there are n elements then the scores are 0,1,...,n-1.
*
* @return the mean of the distribution
*/
public double mean() {
double mean = 0;
for (int i = 1; i < m_dd.length; i++) {
mean += i * m_dd[i];
}
return mean;
}
/**
* Calculate the median of the distribution. This means
* the following: if there is a label m such that
* P(x <= m) >= ½ and
* P(x >= m) >= ½ then this label is returned.
* If there is no such label, an interpolation between the
* smallest label satisfying the first condition and the
* largest label satisfying the second condition is performed.
* The returned value is thus either an element label, or
* exactly between two element labels.
*
* @return the median of the distribution.
**/
public double median() {
/* cumulative probabilities starting from the left and
* right respectively
*/
double cl=m_dd[0];
double cr=m_dd[m_dd.length - 1]; // cumulative left and right
int i = 0;
while(cl < 0.5) {
cl += m_dd[++i]; // pre-increment
}
int j = m_dd.length - 1;
while(cr < 0.5) {
cr += m_dd[--j]; // pre-increment
}
return i == j ? i : ( (double) (i + j) ) / 2;
}
/**
* Get a sorted array containing the indices of the elements with
* maximal probability.
*
* @return an array of class indices with maximal probability.
*/
public int[] modes() {
int[] mm = new int[m_dd.length];
double max = m_dd[0];
int nr = 1; // number of relevant elements in mm
for (int i = 1; i < m_dd.length; i++) {
if (m_dd[i] > max + TOLERANCE) {
// new maximum
max = m_dd[i];
mm[0] = i;
nr = 1;
}
else if (Math.abs(m_dd[i] - max) < TOLERANCE) {
mm[nr++] = i;
}
}
// trim to correct size
int[] modes = new int[nr];
System.arraycopy(mm, 0, modes, 0, nr);
return modes;
}
/**
* Convert the DiscreteDistribution to an
* array of doubles.
*
* @return an array of doubles representing the
* DiscreteDistribution
*/
public double[] toArray() {
double[] dd = new double[m_dd.length];
System.arraycopy(m_dd, 0, dd, 0, dd.length);
return dd;
}
/**
* Get a string representation of the given
* DiscreteDistribution.
*
* @return a string representation of this object
*/
public String toString() {
// XXX MAYBE WE SHOULD USE STRINGBUFFER AND FIXED WIDTH ...
String s = "[" + getNumSymbols() + "]:";
for (int i = 0; i < getNumSymbols(); i++) {
s += " " + getProbability(i);
}
return s;
}
/**
* Checks if this is dominated by dd.
* @param dd the DiscreteDistribution to compare to
* @return true if this is dominated by
* dd , false otherwise
* @throws IllegalArgumentException if the two distributions don't
* have the same length
*/
public boolean stochasticDominatedBy(DiscreteDistribution dd) throws IllegalArgumentException {
return (new CumulativeDiscreteDistribution(this)).
stochasticDominatedBy
(new CumulativeDiscreteDistribution(dd));
}
/**
* Checks if the given array of doubles represents a valid discrete
* distribution.
*
* @param dd an array holding the doubles
* @return true if dd is a valid discrete distribution,
* false otherwise
*/
private static boolean validDiscreteDistribution(double[] dd) {
if (dd == null || dd.length == 0) {
return false;
}
double sum = 0;
for (int i = 0; i < dd.length; i++) {
if (dd[i] < 0) {
return false;
}
sum += dd[i];
}
return !(Math.abs(sum - 1) > TOLERANCE);
}
/**
* Returns the revision string.
*
* @return the revision
*/
public String getRevision() {
return RevisionUtils.extract("$Revision: 5922 $");
}
}