multidecisiontreenode.h

Go to the documentation of this file.

/*

Copyright (c) 2003, Cornell University
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

   - Redistributions of source code must retain the above copyright notice,
       this list of conditions and the following disclaimer.
   - Redistributions in binary form must reproduce the above copyright
       notice, this list of conditions and the following disclaimer in the
       documentation and/or other materials provided with the distribution.
   - Neither the name of Cornell University nor the names of its
       contributors may be used to endorse or promote products derived from
       this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
THE POSSIBILITY OF SUCH DAMAGE.

*/

// -*- C++ -*-

#if !defined _CLUS_MULTIDECISIONTREENODE_H
#define _CLUS_MULTIDECISIONTREENODE_H

#include <list>

#include "vec.h"
#include "continuouslineartransformation.h"
#include "discretepermutationtransformation.h"
#include "statisticsgatherers.h"

using namespace TNT;

namespace CLUS
{

template< class T_Splitter >
class MultiDecisionTreeNode
{
    /// unique identifier of the cluster for a regression tree.
    int nodeId;
    
    /// the state of the node. At creation em. At load stable
    enum state { stable, split} State;
    
    /// the children of this node
    MultiDecisionTreeNode< T_Splitter > * Children[2], *parent;
    
    /// the predicted class labels for each of the trees
    int classLabel;
    
    /// splitter for split criterion
    T_Splitter Splitter;
    
    /// statistics for pruning. Individual statistics are maintained for each dataset
    /// sum of squared differences between prediction and true value
    Vector<int> pruningMistakes;

    /// number of samples in this node for pruning 
    Vector<int> pruningSamples;

    double ComputePruningCost(void)
    {
        int totalMistakes=0;
        int totalSamples=0;
        for (int i=0; i<pruningMistakes.dim(); i++)
        {
            totalMistakes+=pruningMistakes[i];
            totalSamples+=pruningSamples[i];
        }
        if (totalMistakes==0)
            return 0.0;
        return ((double)totalMistakes)/*/totalSamples*/;
    }

    double ComputeNodeWeight(void)
    {
        /// @todo add more code to implement new weighing schemes
        if (State==stable)
            return 0.0;
        else
            return 1.0;
    }

public:
    MultiDecisionTreeNode( MultiDecisionTreeNode< T_Splitter >* Parent,
                           int NodeId, const Vector<int> & DDomainSize,
                           int CsplitDim, int NoDatasets,
                           DiscretePermutationTransformation& discreteTransformer,
                           ContinuousLinearTransformation& continuousTransformer):
            nodeId(NodeId), State(split), parent(Parent), Splitter(DDomainSize,CsplitDim,NoDatasets,
                    discreteTransformer, continuousTransformer),
            pruningMistakes(NoDatasets), pruningSamples(NoDatasets)
    {
        Children[0]=Children[1]=0;
        Splitter.setNodeID(NodeId);
        cout << "Created node with ID=" << NodeId << endl;
    }


    ~MultiDecisionTreeNode(void)
    {
        if (Children[0]!=0)
            delete Children[0];
        Children[0]=0;

        if (Children[1]!=0)
            delete Children[1];
        Children[1]=0;
    }

    void StartLearningEpoch(void)
    {
        switch (State)
        {
        case stable:
            if (Children[0]!=0)
            {
                Children[0]->StartLearningEpoch();
                Children[1]->StartLearningEpoch();
            }
            break;
        case split:
            Splitter.InitializeSplitStatistics();
            break;
        }
    }

    void LearnSample(const int* Dvars, const double* Cvars, int classlabel, int datasetNo)
    {
        switch (State)
        {
        case stable:
            // Pass the sample to the right child
            if (Children[0]!=0)
            {
                Children[Splitter.ChooseBranch(Dvars,Cvars)]->LearnSample(Dvars,Cvars,classlabel,datasetNo);
            }
            break;
        case split:
            Splitter.UpdateSplitStatistics(Dvars, Cvars, classlabel, datasetNo);
            break;
        }
    }

    /** If the node is in splitting stage find the split attribute and if
       it has no shift add attribute to the attList.

       @return false if we have a bogus split and we should make the parent a leaf
    */
    bool FindSplitAttributes(list<int>& attList)
    {
        switch (State)
        {
        case stable:
            if (Children[0]!=0)
            {
                if (!Children[0]->FindSplitAttributes(attList) ||
                        !Children[1]->FindSplitAttributes(attList) )
                {
                    delete Children[0];
                    Children[0]=0;
                    delete Children[1];
                    Children[1]=0;
                }
            }
            break;

        case split:

            if (Splitter.GotNoData())
            {
                // make the parent a leaf
                return false;
            }


            //  cout << "I am node:" << nodeId << endl;
            if (!Splitter.ComputeSplitVariable(attList))
            {
                // make the node a leaf
                //  cout << "Making node a leaf: " << nodeId << endl;
                State=stable;
                Children[1]=0;
                classLabel=Splitter.ComputeClassLabel();
                // distroy datastructures
            }
            break;
        }

        return true;
    }

    double ComputeTotalWeight(void)
    {
        double totalWeight=ComputeNodeWeight();
        if (State==stable)
            if (Children[0]!=0)
                totalWeight+=Children[0]->ComputeTotalWeight()+
                             Children[1]->ComputeTotalWeight();
        return totalWeight;
    }

    /// sums 1/v_n, for the subtree with this as root, where v_n is the variance of the split point for attribute, as computed at node n
    double computeSumOfVarianceInverted(int attribute, int dataSetIndex)
    {
        if (Splitter.hasContinuousData(attribute, dataSetIndex))
        {
            double sum = (double)1/Splitter.getSplitVariance(attribute, dataSetIndex);
            if (State==stable)
                if (Children[0]!=0)
                {
                    sum+= Children[0]->computeSumOfVarianceInverted(attribute, dataSetIndex) +
                          Children[1]->computeSumOfVarianceInverted(attribute, dataSetIndex);
                }
            return sum;
        }
        else
            return 0.0;
    }

    /// Combines shifts for attribute for subtree with this as root.  Note: needs to be normalized.
    double combineSplits(int attribute, int dataSetIndex, double* sumInvVars)
    {

        double total=0;
        if (Splitter.hasContinuousData(attribute, dataSetIndex))
        {
            double var = Splitter.getSplitVariance(attribute, dataSetIndex) ;
            assert(!isnan(var) && var!=0);

            //  cerr << "SplitVariance: " << var << endl;
            double splitpt =  Splitter.getTentativeSplitPoint(attribute, dataSetIndex);
            assert(!isnan(splitpt));
            total = splitpt/var;
            *sumInvVars+=1.0/var;


            if (State==stable)
                if (Children[0]!=0)
                {
                    total+= Children[0]->combineSplits(attribute, dataSetIndex, sumInvVars) +
                            Children[0]->combineSplits(attribute, dataSetIndex, sumInvVars);
                }
        }
        //  cerr<< "In combineSplits for nodeID " << nodeId <<endl;
        return total;
    }

    double combineLabeledCenters(int attribute, int dataSetIndex, double* sumInvVars)
    {

        double total = 0.0;
        double posWeight = Splitter.getLabeledCount(attribute, dataSetIndex, true);
        double negWeight = Splitter.getLabeledCount(attribute, dataSetIndex, false);
        double posMeani =  Splitter.getLabeledCenter(attribute, dataSetIndex, true);
        double negMeani = Splitter.getLabeledCenter(attribute, dataSetIndex, false);
        double posMean0 =  Splitter.getLabeledCenter(attribute, 0, true);
        double negMean0 = Splitter.getLabeledCenter(attribute, 0, false);
        double posVar=Splitter.getLabeledCenterVariance(attribute, dataSetIndex, true);
        double negVar = Splitter.getLabeledCenterVariance(attribute, dataSetIndex, false);
        double combinedVar = (posWeight*posVar + negWeight*negVar)/(posWeight+negWeight);
        double currShift= (posWeight*(posMean0-posMeani) + negWeight*(negMean0-negMeani))/ (posWeight+negWeight);
        if (!isnan(combinedVar) && NonZero(combinedVar) && !isnan(currShift))
        {
            total += currShift/combinedVar;

            *sumInvVars+=1.0/combinedVar;
        }
        if (State==stable)
            if (Children[0]!=0)
            {
                total+= Children[0]->combineLabeledCenters(attribute, dataSetIndex, sumInvVars) +
                        Children[0]->combineLabeledCenters(attribute, dataSetIndex, sumInvVars);
            }
        // total+= (posWeight*(posMean0-posMeani) + negWeight*(negMean0-negMeani))/ posWeight+negWeight;
        return total;
    }
    bool labeledMeansSignificant(int attribute, int dataSetIndex)
    {
        return Splitter.labeledMeansSignificant(attribute, dataSetIndex);
    }

    bool negMeanLessThanPos(int attribute, int dataSetIndex)
    {
        return Splitter.negMeanLessThanPos(attribute, dataSetIndex);
    }

    double combineCenters(int attribute, int dataSetIndex, double* sumInvVars)
    {

        double total=0.0;
        if (Splitter.hasContinuousData(attribute, dataSetIndex))
        {
            double var = Splitter.getVariance(attribute, dataSetIndex) ;


            //  cerr << "Variance: " << var << endl;
            double splitpt =  Splitter.getTentativeCenter(attribute, dataSetIndex);
            // assert(!isnan(splitpt));
            if (!isnan(var) && NonZero(var) && !isnan(splitpt))
            {
                total = splitpt/var;
                *sumInvVars+=1.0/var;
            }

            if (State==stable)
                if (Children[0]!=0)
                {
                    total+= Children[0]->combineCenters(attribute, dataSetIndex, sumInvVars) +
                            Children[0]->combineCenters(attribute, dataSetIndex, sumInvVars);
                }
        }
        //  cerr<< "In combineCenters for nodeID " << nodeId <<endl;
        return total;
    }

    void AddDiscreteShiftStatistics(int SplitAttribute, Vector< BinomialStatistics >& statistics)
    {
        Splitter.AddDiscreteShiftStatistics(SplitAttribute, ComputeNodeWeight(), statistics);
        if (State==stable)
            if (Children[0]!=0)
            {
                Children[0]->AddDiscreteShiftStatistics(SplitAttribute,statistics);
                Children[1]->AddDiscreteShiftStatistics(SplitAttribute,statistics);
            }
    }

    void AddContinuousShiftStatistics(int SplitAttribute, Vector< NormalStatistics >& statistics)
    {
        Splitter.AddContinuousShiftStatistics(SplitAttribute, ComputeNodeWeight(), statistics);
        if (State==stable)
            if (Children[0]!=0)
            {
                Children[0]->AddContinuousShiftStatistics(SplitAttribute,statistics);
                Children[1]->AddContinuousShiftStatistics(SplitAttribute,statistics);
            }
    }

    /// @return true if more learning has to be done in future
    bool StopLearningEpoch(int splitType, int min_no_datapoints)
    {
        switch (State)
        {
        case stable:
            if (Children[0]!=0)
                return Children[0]->StopLearningEpoch(splitType, min_no_datapoints)
                       | Children[1]->StopLearningEpoch(splitType, min_no_datapoints); // || cannot be used since is shortcuted
            else
                return false;

        case split:

            State=stable;
            Splitter.ComputeSplitPoint();
            classLabel=Splitter.ComputeClassLabel();

            // Splitter.DeleteTemporaryStatistics();

            if (Splitter.MoreSplits(min_no_datapoints, nodeId))
            {
                Children[0] = new MultiDecisionTreeNode< T_Splitter >
                              ( this, nodeId*2, Splitter.GetDDomainSize(), Splitter.GetCSplitDim(),
                                Splitter.GetNoDatasets(),
                                Splitter.GetDiscreteTransformer(), Splitter.GetContinuousTransformer());

                Children[1] = new MultiDecisionTreeNode< T_Splitter >
                              ( this, nodeId*2+1, Splitter.GetDDomainSize(), Splitter.GetCSplitDim(),
                                Splitter.GetNoDatasets(),
                                Splitter.GetDiscreteTransformer(), Splitter.GetContinuousTransformer());
            }
            else
            {
                Children[0]=Children[1]=0;
            }

            return true;
            break;

        default:
            return true;

        }
    }

    Permutation ComputeDiscreteShift(bool label, int attribute, int datasetIndex)
    {

        return Splitter.ComputeDiscreteShift(label, attribute, datasetIndex);

    }

    /// Does the inference
    double Infer(const int* Dvars, const double* Cvars)
    {
        // cout << "I am node: " << nodeId << " and my classlabel is " << classLabel << endl;
        if (Children[0]==0)
        {
            // leaf node
            return classLabel;
        }
        else
        {
            return Children[Splitter.ChooseBranch(Dvars,Cvars)]->Infer(Dvars,Cvars);
        }
    }

    void InitializePruningStatistics(void)
    {
        pruningMistakes=0;
        pruningSamples=0;
        if (Children[0]!=0 && Children[1]!=0)
        {
            Children[0]->InitializePruningStatistics();
            Children[1]->InitializePruningStatistics();
        }
    }

    void UpdatePruningStatistics(const int* Dvars, const double* Cvars,  int classlabel /* true output */, int datasetNo  )
    {
        pruningSamples[datasetNo]++;
        if (classLabel!=classlabel)
            pruningMistakes[datasetNo]++;
        // update pruning statistics for the proper children
        if (Children[0]!=0 && Children[1]!=0)
            Children[Splitter.ChooseBranch(Dvars,Cvars)]->UpdatePruningStatistics(Dvars,Cvars,classlabel, datasetNo);
    }

    void FinalizePruningStatistics (void)
    {
        // nothing to do
    }

    /** Returns the optimal cost for this subtree and cuts the subtree to optimal size */
    double PruneSubtree(void)
    { // double alpha /* alpha is the cost for a leaf */){
        double pruningCost=ComputePruningCost();
        if (Children[0] == 0 && Children[1] == 0)
        {
            // node is a leaf
            return pruningCost; // CHANGE
        }
        else
        {
            // node is an intermediary node
            double pruningCostChildren=/*.5**/(Children[0]->PruneSubtree()+Children[1]->PruneSubtree());

            if (pruningCost<pruningCostChildren)
            {
                // prune the tree here
                delete Children[0];
                Children[0]=0;
                delete Children[1];
                Children[1]=0;

                return pruningCost;
            }
            else
            {
                // tree is good as it is
                return pruningCostChildren;
            }
        }
    }

    void SaveToStream(ostream& out)
    {
        out << "{" << endl << " nodeID " << nodeId <<  endl;


        out << endl;


        if (Children[0]!=0 && Children[1]!=0)
        {
            Splitter.SaveToStream(out, false);
            Children[0]->SaveToStream(out);
            Children[1]->SaveToStream(out);
        }
        else
        {
            out << " leaf " <<  endl;
            Splitter.SaveToStream(out, true);
        }
    }
};

}

#endif // _CLUS_MULTIDECISIONTREENODE_H

---