package jsat.classifiers.bayesian;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
import jsat.exceptions.FailedToFitException;
import jsat.exceptions.UntrainedModelException;
import jsat.utils.IntSet;
/**
* The conditional probability table (CPT) is a classifier for categorical attributes. It builds the whole
* conditional probability table for a data set. The size of the CPT grows exponentially with the number of dimensions and options,
* and requires exponentially more data to get a good fit. CPTs can be useful for small data sets, or as a building
* block for another algorithm
*
* @author Edward Raff
*/
public class ConditionalProbabilityTable implements Classifier
{
private static final long serialVersionUID = -287709075031023626L;
/**
* The predicting target class
*/
private CategoricalData predicting;
/**
* The flat array that stores the n dimensional table
*/
private double[] countArray;
/**
* Set subset of the variables we will be using
*/
private Map valid;
/**
* Maps the index order for the CPT to the index values from the training data set
*/
private int[] realIndexToCatIndex;
/**
* Maps the index values of the training set to the index values used by the CPT.
* A value of '-1' indicates that the feature is not in the CPT
*/
private int[] catIndexToRealIndex;
/**
* the dimension size for each category, ie: the number of options for each category
*/
private int[] dimSize;
/**
* The index of the predicting attribute, which is the number of categorical features in the training data set.
*/
private int predictingIndex;
public CategoricalResults classify(DataPoint data)
{
if(catIndexToRealIndex[predictingIndex] < 0)
throw new UntrainedModelException("CPT has not been trained for a classification problem");
CategoricalResults cr = new CategoricalResults(predicting.getNumOfCategories());
int[] cord = new int[dimSize.length];
dataPointToCord(new DataPointPair(data, -1), predictingIndex, cord);
for(int i = 0; i < cr.size(); i++)
{
cord[catIndexToRealIndex[predictingIndex]] = i;
cr.setProb(i, countArray[cordToIndex(cord)]);
}
cr.normalize();//Turn counts into probabilityes
return cr;
}
/**
* Returns the number of dimensions in the CPT
* @return the number of dimensions in the CPT
*/
public int getDimensionSize()
{
return dimSize.length;
}
/**
* Converts a data point pair into a coordinate. The paired value contains the value for the predicting index.
* Though this value will not be used if the predicting class of the original data set was not used to make the table.
*
* @param dataPoint the DataPointPair to convert
* @param targetClass the index in the original data set of the category that we would like to predict
* @param cord the array to store the coordinate in.
* @return the value of the target class for the given data point
* @throws ArithmeticException if the cord array does not match the {@link #getDimensionSize() dimension} of the CPT
*/
public int dataPointToCord(DataPointPair dataPoint, int targetClass, int[] cord)
{
if(cord.length != getDimensionSize())
throw new ArithmeticException("Storage space and CPT dimension miss match");
DataPoint dp = dataPoint.getDataPoint();
int skipVal = -1;
//Set up cord
for(int i = 0; i < dimSize.length; i++)
{
if(realIndexToCatIndex[i] == targetClass)
{
if(targetClass == dp.numCategoricalValues())
skipVal = dataPoint.getPair();
else
skipVal = dp.getCategoricalValue(realIndexToCatIndex[i]);
}
if(realIndexToCatIndex[i] == predictingIndex)
cord[i] = dataPoint.getPair();
else
cord[i] = dp.getCategoricalValue(realIndexToCatIndex[i]);
}
return skipVal;
}
public void train(ClassificationDataSet dataSet, boolean parallel)
{
train(dataSet);
}
public void train(ClassificationDataSet dataSet)
{
Set all = new IntSet();
for(int i = 0; i < dataSet.getNumCategoricalVars()+1; i++)
all.add(i);
trainC(dataSet, all);
}
/**
* Creates a CPT using only a subset of the features specified by categoriesToUse.
*
* @param dataSet the data set to train from
* @param categoriesToUse the attributes to use in training. Each value corresponds to the categorical
* index in dataSet, and adding the value {@link DataSet#getNumCategoricalVars() }, which is
* not a valid index, indicates to used the {@link ClassificationDataSet#getPredicting() predicting class}
* of the data set in the CPT.
*/
public void trainC(ClassificationDataSet dataSet, Set categoriesToUse)
{
if(categoriesToUse.size() > dataSet.getNumFeatures()+1)
throw new FailedToFitException("CPT can not train on a number of features greater then the dataset's feature count. "
+ "Specified " + categoriesToUse.size() + " but data set has only " + dataSet.getNumFeatures());
CategoricalData[] tmp = dataSet.getCategories();
predicting = dataSet.getPredicting();
predictingIndex = dataSet.getNumCategoricalVars();
valid = new HashMap();
realIndexToCatIndex = new int[categoriesToUse.size()];
catIndexToRealIndex = new int[dataSet.getNumCategoricalVars()+1];//+1 for the predicting
Arrays.fill(catIndexToRealIndex, -1);//-1s are non existant values
dimSize = new int[realIndexToCatIndex.length];
int flatSize = 1;//The number of bins in the n dimensional array
int k = 0;
for(int i : categoriesToUse)
{
if(i == predictingIndex)//The predicint class is treated seperatly
continue;
CategoricalData dataInfo = tmp[i];
flatSize *= dataInfo.getNumOfCategories();
valid.put(i, dataInfo);
realIndexToCatIndex[k] = i;
catIndexToRealIndex[i] = k;
dimSize[k++] = dataInfo.getNumOfCategories();
}
if(categoriesToUse.contains(predictingIndex))
{
//Lastly the predicing quantity
flatSize *= predicting.getNumOfCategories();
realIndexToCatIndex[k] = predictingIndex;
catIndexToRealIndex[predictingIndex] = k;
dimSize[k] = predicting.getNumOfCategories();
valid.put(predictingIndex, predicting);
}
countArray = new double[flatSize];
Arrays.fill(countArray, 1);//Laplace correction
int[] cordinate = new int[dimSize.length];
for(int i = 0; i < dataSet.getSampleSize(); i++)
{
DataPoint dp = dataSet.getDataPoint(i);
for (int j = 0; j < realIndexToCatIndex.length; j++)
if (realIndexToCatIndex[j] != predictingIndex)
cordinate[j] = dp.getCategoricalValue(realIndexToCatIndex[j]);
else
cordinate[j] = dataSet.getDataPointCategory(i);
countArray[cordToIndex(cordinate)]+= dp.getWeight();
}
}
/**
* Queries the CPT for the probability that the class value of targetClas would occur with the given DataPointPair.
* @param targetClass the index in the original data set of the class that we want the probability of
* @param dataPoint the data point of values paired with the value of the predicting attribute in the original training set
* @return the probability in [0,1] of the target class value occurring with the given DataPointPair
*/
public double query(int targetClass, DataPointPair dataPoint)
{
int[] cord = new int[dimSize.length];
int skipVal = dataPointToCord(dataPoint, targetClass, cord);
return query(targetClass, skipVal, cord);
}
/**
* Queries the CPT for the probability of the target class occurring with the specified value given the class values of the other attributes
*
* @param targetClass the index in the original data set of the class that we want to probability of
* @param targetValue the value of the targetClass that we want to probability of occurring
* @param cord the coordinate array that corresponds the the class values for the CPT, where the coordinate of the targetClass may contain any value.
* @return the probability in [0, 1] of the targetClass occurring with the targetValue given the information in cord
* @see #dataPointToCord(jsat.classifiers.DataPointPair, int, int[])
*/
public double query(int targetClass, int targetValue, int[] cord)
{
double sumVal = 0;
double targetVal = 0;
int realTargetIndex = catIndexToRealIndex[targetClass];
CategoricalData queryData = valid.get(targetClass);
//Now do all other target class posibilty querys
for (int i = 0; i < queryData.getNumOfCategories(); i++)
{
cord[realTargetIndex] = i;
double tmp = countArray[cordToIndex(cord)];
sumVal += tmp;
if (i == targetValue)
targetVal = tmp;
}
return targetVal/sumVal;
}
/**
* Computes the index into the {@link #countArray} using the given coordinate
* @param cords the coordinate value in question
* @return the index for the given coordinate
*/
private int cordToIndex(int... cords)
{
if(cords.length != realIndexToCatIndex.length)
throw new RuntimeException("Something bad");
int index = 0;
for(int i = 0; i < cords.length; i++)
{
index = cords[i] + dimSize[i]*index;
}
return index;
}
/**
* Computes the index into the {@link #countArray} using the given data point
* @param dataPoint the data point to get the index of
* @return the index for the given data point
*/
@SuppressWarnings("unused")
private int cordToIndex(DataPointPair dataPoint)
{
DataPoint dp = dataPoint.getDataPoint();
int index = 0;
for(int i = 0; i < dimSize.length; i++)
index = dp.getCategoricalValue(realIndexToCatIndex[i]) + dimSize[i]*index;
return index;
}
public boolean supportsWeightedData()
{
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public Classifier clone()
{
throw new UnsupportedOperationException("Not supported yet.");
}
}
Ads help maintain this website.