|| || || || || ||

---

MakeRandomTree.h

Go to the documentation of this file.

#ifndef Impala_Core_Feature_MakeRandomTree_h
#define Impala_Core_Feature_MakeRandomTree_h

#include "Core/Histogram/Entropy.h"
#include "Core/Feature/RandomTree.h"
#include "Util/FilterOperations.h"
#include "Util/MakeFilter.h"
#include "Util/Random.h"

namespace Impala
{
namespace Core
{
namespace Feature
{
    
typedef Table::TableTem<Vector::ColumnVectorSet,
                        Column::ColumnInt32> AnnotatedFeatureTable;

void
Dump(AnnotatedFeatureTable* t, std::ostream& os)
{
    for(int i=0 ; i<t->Size() ; ++i)
    {
        os << t->Get2(i) <<"   ";
        Vector::VectorReal64 v = t->Get1(i);
        for(int i=0 ; i<v.Size() ; ++i)
            os << v[i] <<" ";
        os << "\n";
    }
}
    
/***************************************************************
 * Input for MakeRandomForest is a collection of raw feature vectors with a
 * class id (nrClasses denotes how many class ids are in use). It tries to find
 * a decision tree so that each node separates as best a possible (the best
 * found in a number of random tries) the class id's of it's two children.
 * The children are called left and right in the code; the split point consist
 * of a dimension (column in the VectorSet) and a value to which values of the
 * same dimension (column) are compared.
 * To minimise memory conumption the data is never changed when we split, rather
 * we use filters of type bool* that denote for every row in the table if it is
 * or isn't included. So every level in the tree these filters become more
 * sparse.
 * Note: There are a lot of subroutines here, perhaps some functions are general
 * enough to have their own file
 ****************************************************************/    

Histogram::Histogram1dTem<int>*
MakeHistogram(const AnnotatedFeatureTable* data, int nrClasses, bool* filter)
{
    int outLyers;
    Histogram::Histogram1dTem<int>* hist =
        new Histogram::Histogram1dTem<int>(-0.5, nrClasses+0.5, nrClasses,
                                           &outLyers);
    String a=data->GetInfo();
    for(int y=0 ; y<data->Size() ; ++y)
        if(filter[y])
            hist->AddWeight(data->Get2(y), 1.);
    return hist;
}

double
Gain(const AnnotatedFeatureTable* data, int nrClasses, bool* left, bool* right)
{
    int size = data->Size();
    double nrL = Util::Count(left, size);
    double nrR = Util::Count(right, size);
    double total = nrL+nrR;
    if(total==0)
        return 0;
    Histogram::Histogram1dTem<int>* histL = MakeHistogram(data, nrClasses, left);
    Histogram::Histogram1dTem<int>* histR = MakeHistogram(data, nrClasses, right);
    double gain = - (nrL / total) * Entropy(histL) - (nrR / total) * Entropy(histR);
    delete histL;
    delete histR;
    return gain;
}

void
SplitSet(bool*& left, bool*& right, int dimension, double value,
         const AnnotatedFeatureTable* data, bool* filter)
{
    int size = data->Size();
    bool* less = Util::MakeFilterElemLess(data->GetColumn1()->GetStorage(),
                                          dimension, value);
    left = Util::MakeIntersection(filter, less, size);
    right = Util::MakeRelativeComplement(filter, left, size);
    delete less;
}

void
TryRandomSplit(int& dimension, double& value, double& gain,
               const AnnotatedFeatureTable* data, bool* filter, int nrClasses,
               Util::Random& rng)
{
    dimension = rng.GetInt(data->GetColumn1()->GetVectorLength(0));
    int n = Util::Count(filter, data->Size());
    int index;
    if(n==0)
        index = rng.GetInt(data->Size());
    else
        index = Util::IndexOfNth(filter, data->Size(), rng.GetInt(n));
    value = data->Get1(index)[dimension];
    bool* left = 0;
    bool* right = 0;
    SplitSet(left, right, dimension, value, data, filter);
    gain = Gain(data, nrClasses, left, right);
    delete left;
    delete right;
}

void
FindSplit(int& dimension, double& value, const AnnotatedFeatureTable* data,
          bool* filter, int nrClasses, int nrTrials,
          Util::Random& rng)
{
    int bestDim;
    double bestVal;
    double bestGain;
    TryRandomSplit(bestDim, bestVal, bestGain, data, filter, nrClasses, rng);
    for(int i=1 ; i<nrTrials ; ++i)
    {
        int dim;
        double val;
        double gain;
        TryRandomSplit(dim, val, gain, data, filter, nrClasses, rng);
        if(gain > bestGain)
        {
            bestGain = gain;
            bestVal = val;
            bestDim = dim;
        }
    }
    dimension = bestDim;
    value = bestVal;
}

int
GetCodeWord()
{
    static int sCodeWord=-1;
    ++sCodeWord;
    return sCodeWord;
}

Feature::RandomTree*
MakeRandomTree(const AnnotatedFeatureTable* data, bool* filter,
               int nrClasses, int maxDepth, int nrTrials,
               Util::Random& rng)
{
    ILOG_FUNCTION(MakeRandomTree);
    if(maxDepth <= 0)
    {
        int code = GetCodeWord();
        ILOG_PROGRESS("code word "<< code, 4.);
        return new RandomTree(code, Util::Count(filter, data->Size()));
    }
    
    // find dimension and value to split on
    int dimension;
    double value;
    FindSplit(dimension, value, data, filter, nrClasses, nrTrials, rng);
    // construct filters for the left and right child
    bool* leftFilter=0;
    bool* rightFilter=0;
    SplitSet(leftFilter, rightFilter, dimension, value, data, filter);
    // make sub trees
    RandomTree* left =
        MakeRandomTree(data, leftFilter, nrClasses, maxDepth-1, nrTrials, rng);
    RandomTree* right =
        MakeRandomTree(data, rightFilter, nrClasses, maxDepth-1, nrTrials, rng);
    delete leftFilter;
    delete rightFilter;
    return new RandomTree(dimension, value, left, right);
}

// access point initialises a filter and calls recursive routine
RandomTree*
MakeRandomTree(const AnnotatedFeatureTable* data,
               int nrClasses, int maxDepth, int nrTrials,
               Util::Random& rng)
{
    int size = data->Size();
    bool* filter = new bool[size];
    for(int i=0 ; i<size ; ++i)
    {
        filter[i] = true;
    }
    RandomTree* tree = MakeRandomTree(data, filter, nrClasses, maxDepth, nrTrials, rng);
    delete filter;
    return tree;
}

} // namespace Koen
} // namespace Sandbox
} // namespace Impala

#endif

---