binarymulticlassificationsplitter.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_BINARYMULTICLASSICICATIONSPLITTER_H
#define _CLUS_BINARYMULTICLASSICICATIONSPLITTER_H

#include "statisticsgatherers.h"
#include "discretepermutationtransformation.h"

using namespace TNT;

namespace CLUS
{
class BinaryMultiClassificationSplitter
{
    /// number of discrete split variables
    int dsplitDim;

    /// number of continuous split variables
    int csplitDim;

    /// id of owner node
    int id;
    
    bool noWeighting;

    int noDatasets;
    
    const Vector<int>& dDomainSize;
    
    /// indicates on what variable this node splits on
    int SplitVariable;
    
    // split point if continuous variable is split variable
    double splitPoint;
    
    /** The list of values for the left child for the separating variable if
    the split is not oblique. Contains values in order so that
    binary search can be used. */
    Vector<int> SeparatingSet;

    DiscretePermutationTransformation& discreteTransformer;
    ContinuousLinearTransformation& continuousTransformer;

    /** Statistics for split decision. One for each attributeXdataset
    If an attribute already has the shift determined keep statistics 
    about all datasets in the location for the first dataset
    */
    Vector< Vector<BinomialStatistics> > discreteStatistics;
    Vector< Vector<NormalStatistics> > continuousStatistics;

    /// one per attribute
    Vector< Vector<Permutation> > discreteShifts;

    /// one per attribute
    Vector< Vector<double> > continuousShifts;
    
    Vector<int> examplesSeen;
    Vector<int> examples0Seen;

    /// statistics for class label determination
    int count;
    int countC0;
    
public:
    BinaryMultiClassificationSplitter(const Vector<int>& DDomainSize,int CsplitDim,
                                      int NoDatasets,
                                      DiscretePermutationTransformation& DiscreteTransformer,
                                      ContinuousLinearTransformation& ContinuousTransformer):
            dsplitDim(DDomainSize.dim()-1), csplitDim(CsplitDim), noWeighting(true), /* was false */
            noDatasets(NoDatasets), dDomainSize(DDomainSize),
            discreteTransformer(DiscreteTransformer), continuousTransformer(ContinuousTransformer),
            discreteStatistics(0), continuousStatistics(0), 
            discreteShifts(0), continuousShifts(0),
            examplesSeen(noDatasets), examples0Seen(noDatasets)
    {}

    ~BinaryMultiClassificationSplitter(void)
    {}
    void setNodeID(int ID)
    {
        id=ID;
    }

    bool GotNoData(void)
    {
        return count==0;
    }

    int GetCSplitDim(void)
    {
        return csplitDim;
    }
    
    int GetDSplitDim(void)
    {
        return dsplitDim;
    }
    
    int GetNoDatasets(void)
    {
        return noDatasets;
    }
    
    const Vector<int>& GetDDomainSize(void)
    {
        return dDomainSize;
    }

    double getLabeledCount(int attribute, int dataSetIndex, bool b)
    {
        if (b)
            return continuousStatistics[attribute][dataSetIndex].getcountC1();
        else
            return continuousStatistics[attribute][dataSetIndex].getcountC0();
    }

    DiscretePermutationTransformation& GetDiscreteTransformer(void)
    {
        return discreteTransformer;
    }

    ContinuousLinearTransformation& GetContinuousTransformer(void)
    {
        return continuousTransformer;
    }

    /// Initializes the datastructures used in split variable selection
    void InitializeSplitStatistics(void)
    {
        count=0;
        countC0=0;

        discreteStatistics.newsize(dsplitDim);
        for (int i=0; i<dsplitDim; i++)
        {
            // for each discrete attribute determine if the shifts are fixed
            if (discreteTransformer.HasAttributeShifts(i))
            {
                discreteStatistics[i].newsize(1);
                discreteStatistics[i][0].ResetDomainSize(dDomainSize[i]);
            }
            else
            {
                discreteStatistics[i].newsize(noDatasets);
                for (int j=0; j<noDatasets; j++)
                    discreteStatistics[i][j].ResetDomainSize(dDomainSize[i]);
            }
        }

        continuousStatistics.newsize(csplitDim);
        for (int i=0; i<csplitDim; i++)
        {
            // for each discrete attribute determine if the shifts are fixed
            if (continuousTransformer.HasAttributeShifts(i))
            {
                continuousStatistics[i].newsize(1);
            }
            else
            {
                continuousStatistics[i].newsize(noDatasets);
            }
        }
    }

    /// Choose a branch
    ///
    /// @param Dvars         discrete variables
    /// @param Cvars         continuous variables
    /// @return              0 is left and 1 right
    int ChooseBranch( const int* Dvars, const double* Cvars)
    {
        if (SplitVariable <=-1)
        {
            // split on a continuous variable
            // the split variable is actually -SplitVariable-1
            if (Cvars[-SplitVariable-1]<=splitPoint)
                return 0;
            else
                return 1;
        }
        else
        {
            // split on a discrete variable
            int value=Dvars[SplitVariable];
            // look for value in SeparatingSet
            bool pickleft=false;
            int l=0, r=SeparatingSet.dim()-1;

            assert(r>=0);

            while ( l<=r && !pickleft )
            {
                int m=(l+r)/2;
                int vm=SeparatingSet[m];
                if ( vm ==value )
                {
                    pickleft=true;
                    break;
                }
                if ( vm < value )
                    l=m+1;
                else
                    r=m-1;
            }
            if (pickleft)
                return 0;
            else
                return 1;
        }
    }

    /// Update split stats with new data
    ///
    /// @param Dvars         discrete variables
    /// @param Cvars         continuous variables
    /// @param classLabel    classification label
    /// @param datasetNo     dataset number
    void UpdateSplitStatistics( const int* Dvars, const double* Cvars,
                                int classLabel, int datasetNo)
    {
        count++;
        examplesSeen[datasetNo]++;
        if (classLabel==0)
        {
            countC0++;
            examples0Seen[datasetNo]++;
        }

        // update discrete statistics
        for (int i=0; i<dsplitDim; i++)
        {
            // for each discrete attribute determine if the shifts are fixed
            if (discreteTransformer.HasAttributeShifts(i))
                (discreteStatistics[i])[0].UpdateStatistics(Dvars[i],classLabel);
            else
                (discreteStatistics[i])[datasetNo].UpdateStatistics(Dvars[i],classLabel);
        }

        for (int i=0; i<csplitDim; i++)
        {
            // for each discrete attribute determine if the shifts are fixed
            if (continuousTransformer.HasAttributeShifts(i))
                (continuousStatistics[i])[0].UpdateStatistics(Cvars[i],classLabel);
            else
                (continuousStatistics[i])[datasetNo].UpdateStatistics(Cvars[i],classLabel);
        }
    }
    
    bool labeledMeansSignificant(int attribute, int dataSetIndex)
    {
        return continuousStatistics[attribute][dataSetIndex].labeledMeansSignificant();
    }

    bool negMeanLessThanPos(int attribute, int dataSetIndex)
    {
        return continuousStatistics[attribute][dataSetIndex].negMeanLessThanPos();
    }

    bool hasContinuousData(int attribute, int dataSetIndex)
    {
        return continuousStatistics[attribute][dataSetIndex].hasData();
    }

    void DeleteTemporaryStatistics(void)
    {
        // discreteStatistics.newsize(0);
        // continuousStatistics.newsize(0);
    }

    /** Computes the split variable. If the variable needs a shift (doesn't have one already)
        add the variable to the attList

        @param attList       list of attribute values
        @return              If not enough data return false: make node a leaf
    */
    bool ComputeSplitVariable(list<int>& attList)
    {
        cerr << "nodeID " << id<< endl;
        cout << "Counts:"  << countC0 << "," << count-countC0 << endl;
        if (countC0<2 || count-countC0<2)
        {
#ifdef DEBUG_PRINT
            cout << "Making the node a leaf. Counts: " << countC0 << "," << count-countC0 << endl;
#endif

            return false; // make the node a leaf; not enough data to compute splits
        }

        // type is ignored, gini is used always
        double maxgini=0.0;

        // go over the discrete attributes and find the best one
        // when an attribute without shifts set is encountered the gini is average of ginies over datasets
        for (int i=0; i<dsplitDim; i++)
        {
            double curr_gini=0.0;

            // printing statistics
            //for (int j=0; j<noDatasets; j++){
            //cout << "DiscreteStatistics " << i << " " << j << endl;
            //discreteStatistics[i][j].Print();
            //}

            if (discreteTransformer.HasAttributeShifts(i))
            {
                curr_gini=discreteStatistics[i][0].ComputeGiniGain();
            }
            else
            {
                double total=0;
                double weight=0;
                // compute average gini
                for (int j=0; j<noDatasets; j++)
                {
                    weight = discreteStatistics[i][j].getCount();
                    curr_gini+=weight*discreteStatistics[i][j].ComputeGiniGain();
                    total += weight;
                }

                curr_gini/=total;
            }
            if (curr_gini>maxgini)
            {
                maxgini=curr_gini;
                SplitVariable=i;
            }
        }

        // continuous attributes now
        for (int i=0; i<csplitDim; i++)
        {
            double curr_gini=0.0;

            // printing statistics
            //  for (int j=0; j<noDatasets; j++){
            // cout << "ContinuousStatistics " << i << " " << j << endl;
            //continuousStatistics[i][j].Print();
            //  }


            if (continuousTransformer.HasAttributeShifts(i))
            {
                curr_gini=continuousStatistics[i][0].ComputeGiniGain();
            }
            else
            {
                double weight =0;
                double total=0;

                for (int j=0; j<noDatasets; j++)
                {

                    NormalStatistics stat = continuousStatistics[i][j];
                    if (stat.nonZero())
                    {
                        weight = continuousStatistics[i][j].getcountC0() + continuousStatistics[i][j].getcountC1();
                        curr_gini+=weight*continuousStatistics[i][j].ComputeGiniGain();
                        total+=weight;
                    }
                }

                curr_gini/=total;
            }
            if (curr_gini>maxgini)
            {
                maxgini=curr_gini;
                SplitVariable=-(i+1);
            }
        }



        //      cout << "Maxgini=" << maxgini << endl;

        if (maxgini==0.0)
            return false; // make the node a leaf, nobody can do a reasonable split

        // put the variable in attList if it requires a shift computation and not already there
        cout << "Chosen split variable" << SplitVariable << " maxgini=" << maxgini << endl;
        if ( (SplitVariable>=0 && !discreteTransformer.HasAttributeShifts(SplitVariable)) ||
                (SplitVariable<0 && !continuousTransformer.HasAttributeShifts(-SplitVariable-1)) )
        {
            // add attribute to the list
            attList.push_front(SplitVariable);
        }

        return true;
    }

    Permutation ComputeDiscreteShift(bool label, int attribute, int datasetIndex)
    {
        if (label)
            return discreteStatistics[attribute][0].ComputeShift(labeled, discreteStatistics[attribute][datasetIndex]);
        else
            return discreteStatistics[attribute][0].ComputeShift(unlabeled, discreteStatistics[attribute][datasetIndex]);
    }
    
    void AddDiscreteShiftStatistics(int SplitAttribute, double weight,
                                    Vector< BinomialStatistics >& statistics)
    {
        if (weight==0.0)
            return;

        for (int i=0; i<statistics.dim(); i++)
            statistics[i].AddWeightedStatistics(discreteStatistics[SplitAttribute][i], weight);
    }

    // used from silly weighting scheme
    /*
    void AddContinuousShiftStatistics(int SplitAttribute, double weight,
          Vector< NormalStatistics >& statistics) {

        if (weight==0.0)
            return;

        for (int i=0; i<statistics.dim(); i++)
            statistics[i].AddWeightedStatistics(continuousStatistics[SplitAttribute][i], weight);
    }*/

    void ComputeCenter(void)
    {

        // don't forget to propagate shifts if you have to
        if (SplitVariable>=0)
        {
            // discrete variable
            int noDatasets=discreteStatistics[SplitVariable].dim();
            if (noDatasets>1)
            {
                // variable was shifted, have to propagate the shifts
                for (int i=1; i<noDatasets; i++)
                {

                    discreteStatistics[SplitVariable][0].AddStatisticsShifted(discreteStatistics[SplitVariable][i],
                            discreteTransformer.GetShift(SplitVariable, i));
                }
            }
            discreteStatistics[SplitVariable][0].ComputeGiniGain(); // computes the shift also
            SeparatingSet=discreteStatistics[SplitVariable][0].GetSplit();


        }
        else
        {
            int splitVar=-SplitVariable-1;
            if (continuousStatistics[splitVar].dim()>1)
            {
                // variable was shifted, have to propagate the shifts
                for (int i=1; i<noDatasets; i++)
                {
                    continuousStatistics[splitVar][0].AddStatisticsShifted(continuousStatistics[splitVar][i],
                            continuousTransformer.GetShift(splitVar, i));
                }
            }
            continuousStatistics[splitVar][0].ComputeGiniGain();
            splitPoint=continuousStatistics[splitVar][0].GetCenter();
            //  cout << "Selected split point of " << splitPoint << "for var " << SplitVariable << endl;
        }
    }

    double getLabeledCenter(int attribute, int dataSetIndex, bool b)
    {
        return continuousStatistics[attribute][dataSetIndex].getLabeledCenter(b);
    }

    double getLabeledCenterVariance(int attribute, int dataSetIndex, bool b)
    {
        return continuousStatistics[attribute][dataSetIndex].getLCVariance(b);
    }

    double getVariance(int attribute, int dataSetIndex)
    {
        return continuousStatistics[attribute][dataSetIndex].getVariance();
    }

    /// For continuous attributes only
    ///
    /// @param attribute
    /// @param dataSetIndex
    double getSplitVariance(int attribute, int dataSetIndex)
    {
        if (noWeighting)
            return 1;
        return continuousStatistics[attribute][dataSetIndex].getSplitVariance();
    }

    /// For continuous attributes not chosen as split attribute at current node
    ///
    /// @param attribute
    /// @param dataSetIndex
    double getTentativeSplitPoint(int attribute, int dataSetIndex)
    {
        return continuousStatistics[attribute][dataSetIndex].GetSplit();
        //return continuousStatistics[attribute][dataSetIndex].GetSplit();
    }

    // For continuous attributes not chosen as split attribute at current node
    ///
    /// @param attribute
    /// @param dataSetIndex
    double getTentativeCenter(int attribute, int dataSetIndex)
    {
        return continuousStatistics[attribute][dataSetIndex].GetCenter();
        //return continuousStatistics[attribute][dataSetIndex].GetSplit();
    }

    void ComputeSplitPoint(void)
    {
        // don't forget to propagate shifts if you have to
        if (SplitVariable>=0)
        {
            // discrete variable
            int noDatasets=discreteStatistics[SplitVariable].dim();
            if (noDatasets>1)
            {
                // variable was shifted, have to propagate the shifts
                for (int i=1; i<noDatasets; i++)
                {

                    discreteStatistics[SplitVariable][0].AddStatisticsShifted(discreteStatistics[SplitVariable][i],
                            discreteTransformer.GetShift(SplitVariable, i));
                }
            }
            discreteStatistics[SplitVariable][0].ComputeGiniGain(); // computes the shift also
            SeparatingSet=discreteStatistics[SplitVariable][0].GetSplit();
        }
        else
        {
            int splitVar=-SplitVariable-1;
            if (continuousStatistics[splitVar].dim()>1)
            {
                // variable was shifted, have to propagate the shifts
                for (int i=1; i<noDatasets; i++)
                {
                    continuousStatistics[splitVar][0].AddStatisticsShifted(continuousStatistics[splitVar][i],
                            continuousTransformer.GetShift(splitVar, i));
                }
            }
            continuousStatistics[splitVar][0].ComputeGiniGain();
            splitPoint=continuousStatistics[splitVar][0].GetSplit();
            //cout << "Selected split point of " << splitPoint << "for var " << SplitVariable << endl;
        }
    }

    int ComputeClassLabel(void)
    {
        if (countC0>=count-countC0)
            return 0;
        else
            return 1;
    }

    double getContinuousShift(int attribute, int dataSetIndex)
    {
        return continuousTransformer.GetShift(attribute, dataSetIndex);
    }

    bool MoreSplits(int min_no_datapoints, int nodeID)
    {
        bool discreteSplitGoneBad = (SplitVariable>=0 && SeparatingSet.size()==0);
        return ( (count>=min_no_datapoints) && countC0!=0 && countC0!=count && !discreteSplitGoneBad); //REBA ADDED SECOND CLAUSES
    }

    void SaveToStream(ostream& out, bool isLeaf)
    {

        out << " label " << ComputeClassLabel()  << endl;
        for (int j=0; j < noDatasets; j++)
        {
            //  out << " Seen " <<  examplesSeen[j] << " examples from data set " << j << ", "
            //      << examples0Seen[j] << " of them labelled 0" << endl;
        }
        out << "}" << endl << endl;

        if (!isLeaf)
        {
            out << " split attribute: " << SplitVariable;
            if (SplitVariable<0)
                out << ", split point: " << splitPoint << endl << "}" << endl << endl;
            else
            {
                out << ", split set: ";
                for (int i=0; i<SeparatingSet.dim(); i++)
                    out << SeparatingSet[i] << " ";
                out << endl << "}" << endl << endl;
            }

        }
    }

};
}

#endif // _CLUS_MULTIDECISIONTREENODE_H

---