binaryobliquesplitter.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_BINARYOBLIQUESPLITTER_H
#define _CLUS_BINARYOBLIQUESPLITTER_H

#include "general.h"
#include "binarysplitter.h"
#include "splitpointcomputation.h"
#include "statisticsgatherers.h"
#include <math.h>

#include <stdlib.h>
#include <iostream>

using namespace TNT;

namespace CLUS
{

class BinaryObliqueSplitter: public BinarySplitter
{
protected:
    int N;
    Vector<ProbabilisticBinomialStatistics>  discreteStatistics;
    MultidimNormalStatistics continuousStatistics;

    bool purePart;

    double ProbabilityLeftPrivate(const int* Dvars, const double* Cvars)
    {
        /* use the fact that SeparatingHyperplane is normalized */
        if (SplitVariable==-1)
        {
            // split on a hyperplane
            double crit=SeparatingHyperplane[0];
            for (int i=0; i<csplitDim+regDim; i++)
                crit+=Cvars[i]*SeparatingHyperplane[i+1];

            return 1.0-PValueNormalDistribution(0.0,1.0,crit);
        }
        else
            if (SplitVariable <=-2)
            {
                // split on a continuous variable
                double crit=SeparatingHyperplane[0]+
                            Cvars[-SplitVariable-2]*SeparatingHyperplane[-SplitVariable-1];

                return  1.0-PValueNormalDistribution(0.0,1.0,crit);
            }
            else
            {
                // split on a discrete variable
                int value=Dvars[SplitVariable];
                return splitSetProbability[value];
            }
    }

public:
    BinaryObliqueSplitter():BinarySplitter(), N(0), purePart(false)
    {}
    BinaryObliqueSplitter(const Vector<int>& DDomainSize,int CsplitDim, int RegDim):
            BinarySplitter(DDomainSize,CsplitDim,RegDim), N(0),purePart(false)
    {}
    BinaryObliqueSplitter(BinarySplitter& aux):
            BinarySplitter(aux)
    { }


    /// which of the three methods is used for computation of separating hyperplane
    enum MultidimNormalStatistics::SeparationType CSepHypType; 

    /// Should be called after ComputeSplitVariable()
    ///
    /// @return true if the children given by branch will be splitted in the future
    bool MoreSplits(int branch, int Min_no_datapoints)
    {
        if (purePart)
            return false;

        // cout << "s_p1=" << continuousStatistics.GetS_P1() << "\ts_p2=" << continuousStatistics.GetS_P2() << "\tmin_no_datapoints=" << Min_no_datapoints << endl;

        if (branch==0)
            return continuousStatistics.GetS_P1()>=Min_no_datapoints;
        else
            return continuousStatistics.GetS_P2()>=Min_no_datapoints;
    }

    /// Compute the probability to take the left branch
    double ProbabilityLeft(const int* Dvars, const double* Cvars)
    {
        if (ProbabilityLeftPrivate(Dvars,Cvars)>.5)
            return 1.0;
        else
            return 0.0;
    }

    int ChooseBranch( const int* Dvars, const double* Cvars)
    {
        if (ProbabilityLeftPrivate(Dvars,Cvars)>.5)
            return 0;
        else
            return 1;
    }

    void InitializeSplitStatistics(void)
    {
        discreteStatistics.newsize(dsplitDim);
        for (int i=0; i<dsplitDim; i++)
        {
            discreteStatistics[i].ResetDomainSize(dDomainSize[i]);
        }

        continuousStatistics.Resize(csplitDim+regDim);
    }

    void UpdateSplitStatistics( const int* Dvars, const double* Cvars,
                                double p1I, double p2I, double probability)
    {
        N++;

        double p1=p1I*probability;
        double p2=p2I*probability;

        // update the discrete var statistics
        for(int i=0; i<dsplitDim; i++)
        {
            discreteStatistics[i].UpdateStatisticsP(Dvars[i],p1,p2);
        }

        continuousStatistics.UpdateStatistics(Cvars,p1,p2);
    }

    void DeleteTemporaryStatistics(void)
    {
        // free the space ocupied by the suficient statistics
        discreteStatistics.newsize(0);
        continuousStatistics.Resize(0);
    }

    int ComputeSplitVariable(int type = MultidimNormalStatistics::LDA)
    {
        double maxgini;

        if (N==0)
            goto error;

        // compute the best oblique split
        maxgini=continuousStatistics.ComputeGiniGain(type);
        SplitVariable=continuousStatistics.GetSplitVariable();

        // look for a cathegorical split that is better

        for (int i=0; i<dsplitDim; i++)
        {
            double gini=discreteStatistics[i].ComputeGiniGain();

            //cout << "Var: " << i << " gini=" << gini << endl;

            if (gini>maxgini)
            {
                maxgini=gini;
                SplitVariable=i;
            }
        }

        if (maxgini==0.0)
            goto error; // nobody makes any improvement

        if (SplitVariable>=0)
        {
            splitSetProbability=discreteStatistics[SplitVariable].GetProbabilitySet();
        }
        else
        {
            SeparatingHyperplane=continuousStatistics.GetSeparatingHyperplane();
        }

        // anything is hopefully donne at this point

        // if we are very close to maximum achievable gini we do no more splits in future
        if (fabs(maxgini-continuousStatistics.MaxGini()) < TNNearlyZero )
            purePart=true;

#if 0
        //cout << "maxgini=" << maxgini << " maxpossible=" << 2*alpha_1*alpha_2 << endl;
        cout << "SplitVariable=" << SplitVariable << endl;
        if (SplitVariable>=0)
        {
            cout << " [[ ";
            for (int i=0; i<splitSetProbability.size(); i++)
                cout << splitSetProbability[i] << " ";
            cout << " ]]" << endl;
            ;
        }
#endif

        return 0;

error:
        cout << "Error encountered, killing node" << endl;

        return -1;
    }
};

}

#endif // _CLUS_BINARYOBLIQUESPLITTER_H

---