measures.cpp

orange源码 数据挖掘技术

  if (varType==TValue::INTVAR) {
    if (!handlesDiscrete)
      raiseError("cannot work with discrete classes");
  }
  else if (varType==TValue::FLOATVAR) {
    if (!handlesContinuous)
      raiseError("cannot work with continuous classes");
  }
}


TMeasureAttributeFromProbabilities::TMeasureAttributeFromProbabilities(const bool hd, const bool hc, const int unkTreat)
: TMeasureAttribute(Contingency_Class, hd, hc, hd), // we can compute thresholds, if we handle discrete attributes...
  unknownsTreatment(unkTreat)
{}


float TMeasureAttributeFromProbabilities::operator()(PContingency cont, PDistribution classDistribution, PDistribution aprior)
{ 
  // if unknowns are ignored, we only take the class distribution for examples for which the attribute's value was defined
  if (unknownsTreatment == IgnoreUnknowns)
    classDistribution = cont->innerDistribution;

  if (estimatorConstructor) {
    classDistribution = estimatorConstructor->call(classDistribution, aprior)->call();
    if (!classDistribution)
      raiseError("'estimatorConstructor' cannot return the distribution");
  }

  if (conditionalEstimatorConstructor) {
    PContingency cont_e = conditionalEstimatorConstructor->call(cont, aprior)->call();
    if (!cont_e)
      raiseError("'conditionalEstimatorConstructor cannot return contingency matrix");
    cont_e->outerDistribution = cont->outerDistribution;
    cont_e->innerDistribution = classDistribution;

    cont = cont_e;
  }

  TDiscDistribution *dcDist = classDistribution.AS(TDiscDistribution);
  if (!dcDist)
    raiseError("discrete class expected");

  return operator()(cont, *dcDist);
}


inline float round0(const float &x)
{ 
  return (x > -1e-6) && (x < 1e-6) ? 0.0 : x;
}


float getEntropy(const vector<float> &vf)
{ 
  float n = 0.0, sum = 0.0;
  int noDif0 = 0;
  const_ITERATE(vector<float>, vi, vf)
    if (*vi>0) {
      sum += (*vi)*log(*vi);
      n += *vi;
      noDif0++;
    }
  return (noDif0>1) ? (log(float(n))-sum/n) / log(2.0) : 0;
}


float getEntropy(PContingency cont, int unknownsTreatment)
{ 
  checkDiscrete(cont, "getEntropy");

  float sum = 0.0, N = 0.0;
  const TDiscDistribution &outer = CAST_TO_DISCDISTRIBUTION(cont->outerDistribution);
  TDistributionVector::const_iterator mostCommon(
     unknownsTreatment == TMeasureAttribute::UnknownsToCommon
       ? cont->discrete->begin() + outer.highestProbIntIndex()
       : cont->discrete->end());

  const_ITERATE(TDistributionVector, ci, *cont->discrete) {
    const TDiscDistribution &dist = CAST_TO_DISCDISTRIBUTION(*ci);
    if (ci == mostCommon) {
      TDiscDistribution dist2 = dist;
      dist2 += cont->innerDistributionUnknown;
      N += dist2.cases;
      sum += dist2.cases * getEntropy(dist2);
    }
    else {
      N += dist.cases;
      sum += dist.cases * getEntropy(dist.distribution);
    }
  }

  if (unknownsTreatment == TMeasureAttribute::UnknownsAsValue) {
    const float &cases = cont->innerDistributionUnknown->cases;
    N += cases;
    sum += cases * getEntropy(CAST_TO_DISCDISTRIBUTION(cont->innerDistributionUnknown));
  }

  return N ? sum/N : 0.0;
}



TMeasureAttribute_info::TMeasureAttribute_info(const int &unk)
: TMeasureAttributeFromProbabilities(true, false, unk)
{}


float TMeasureAttribute_info::operator()(PContingency probabilities, const TDiscDistribution &classProbabilities)
{ 
  // checkDiscrete is called by getEntropy

  const TDistribution &outer = probabilities->outerDistribution.getReference();
  if (!outer.cases)
    return 0.0;

  float info = getEntropy(classProbabilities) - getEntropy(probabilities, unknownsTreatment);
  if (unknownsTreatment == ReduceByUnknowns)
    info *= outer.cases / (outer.unknowns + outer.cases);

  return round0(info);
}


float TMeasureAttribute_info::operator()(const TDiscDistribution &dist) const
{ 
  return -getEntropy(dist);
}


TMeasureAttribute_gainRatio::TMeasureAttribute_gainRatio(const int &unk)
: TMeasureAttributeFromProbabilities(true, false, unk)
{}



float TMeasureAttribute_gainRatio::operator()(PContingency probabilities, const TDiscDistribution &classProbabilities)
{ 
  checkDiscrete(probabilities, "MeasureAttribute_gainRatio");

  const TDiscDistribution &outer = CAST_TO_DISCDISTRIBUTION(probabilities->outerDistribution);
  if (!outer.cases)
    return 0.0;

  float attributeEntropy;
  if (unknownsTreatment == UnknownsAsValue) {
    vector<float> dist(outer);
    dist.push_back(probabilities->innerDistributionUnknown->cases);
    attributeEntropy = getEntropy(dist);
  }
  else
    attributeEntropy = getEntropy(outer);

  if (attributeEntropy<1e-20)
    return 0.0;
  
  float gain = getEntropy(classProbabilities) - getEntropy(probabilities, unknownsTreatment);
  if (gain<1e-20)
    return 0.0;
  
  gain /= attributeEntropy;

  if (unknownsTreatment == ReduceByUnknowns)
    gain *= outer.cases / (outer.unknowns + outer.cases);

  return round0(gain);
}



float TMeasureAttribute_gainRatioA::operator()(const TDiscDistribution &dist) const
{ return round0(-getEntropy(dist) * log(float(dist.size()))); }




float getGini(const vector<float> &vf)
{ float sum = 0.0, N = 0.0;
  const_ITERATE(vector<float>, vi, vf) {
    N += *vi;
    sum += (*vi)*(*vi);
  }
  return N ? (1 - sum/N/N)/2 : 0.0;
}


float getGini(PContingency cont, int unknownsTreatment)
{ 
  float sum = 0.0, N = 0.0;
  const TDiscDistribution &outer = CAST_TO_DISCDISTRIBUTION(cont->outerDistribution);
  TDistributionVector::const_iterator mostCommon(
    unknownsTreatment == TMeasureAttribute::UnknownsToCommon
      ? cont->discrete->begin() + outer.highestProbIntIndex()
      : cont->discrete->end());

  const_ITERATE(TDistributionVector, ci, *cont->discrete) {
    const TDiscDistribution &dist = CAST_TO_DISCDISTRIBUTION(*ci);
    if (ci == mostCommon) {
      TDiscDistribution dist2 = dist;
      dist2 += cont->innerDistributionUnknown;
      N += dist2.cases;
      sum += dist2.cases * getGini(dist2);
    }
    else {
      N += dist.cases;
      sum += dist.cases * getGini(dist.distribution);
    }
  }

  if (unknownsTreatment == TMeasureAttribute::UnknownsAsValue) {
    const float &cases = cont->innerDistributionUnknown->cases;
    N += cases;
    sum += cases * getGini(CAST_TO_DISCDISTRIBUTION(cont->innerDistributionUnknown));
  }

  return N ? sum/N : 0.0;
}


TMeasureAttribute_gini::TMeasureAttribute_gini(const int &unk)
: TMeasureAttributeFromProbabilities(true, false, unk)
{}


float TMeasureAttribute_gini::operator()(PContingency probabilities, const TDiscDistribution &classProbabilities)
{ 
  checkDiscrete(probabilities, "MeasureAttribute_gini");
  
  const TDistribution &outer = probabilities->outerDistribution.getReference();
  if ((unknownsTreatment == ReduceByUnknowns) && (outer.unknowns == outer.cases))
    return 0.0;
 
  float gini = getGini(classProbabilities) - getGini(probabilities, unknownsTreatment);
  if (unknownsTreatment == ReduceByUnknowns)
    gini *= (outer.cases / (outer.unknowns + outer.cases));

  return round0(gini);
}


float TMeasureAttribute_gini::operator()(const TDiscDistribution &dist) const
{ return round0(-getGini(dist)); }



TMeasureAttribute_relevance::TMeasureAttribute_relevance(const int &unk)
: TMeasureAttributeFromProbabilities(true, false, unk)
{}



float TMeasureAttribute_relevance::valueRelevance(const TDiscDistribution &dval, const TDiscDistribution &classDist)
{ 

  TDiscDistribution::const_iterator ci(classDist.begin()), ce(classDist.end()), hci(ci);
  TDiscDistribution::const_iterator di(dval.begin()), de(dval.end());

  for (; (di!=de) && (ci!=ce) && (*ci<1e-20); ci++, di++);
  if ((ci==ce) || (di==de))
    return 0.0;

  /* 'leftout' is the element for the most probable class encountered so far
      If a more probable class appears, 'leftout' is added and new leftout taken
      If there is more than one most probable class, the one with higher aprior probability
      is taken (as this gives higher relevance). If there is more than one such class,
      it doesn't matter which one we take. */  
  float relev = 0.0;
  float highestProb = *di;
  float leftout = *di / *ci;

  while(++ci!=ce && ++di!=de) 
    if (*ci>=1e-20) {
      const float &tras = *di / *ci;
      if (   (*di >  highestProb)
          || (*di == highestProb) && (leftout < tras)) {
        relev += leftout;
        leftout = tras;
        highestProb = *di;
      }
      else
        relev += tras;
    }

  return relev;
}


float TMeasureAttribute_relevance::operator()(PContingency probabilities, const TDiscDistribution &classProbabilities)
{ 
  checkDiscrete(probabilities, "MeasureAttribute_relevance");
  
  const TDistribution &outer = probabilities->outerDistribution.getReference();
  if ((unknownsTreatment == ReduceByUnknowns) && (outer.unknowns == outer.cases))
    return 0.0;
 
  int C = 0;
  const_ITERATE(TDiscDistribution, di, classProbabilities)
    if (*di > 1e-20)
      C++;
  if (C<=1)
    return 0.0;

  TDistributionVector::const_iterator mostCommon (unknownsTreatment == UnknownsToCommon
    ? probabilities->discrete->begin() + outer.highestProbIntIndex()
    : probabilities->discrete->end());
 
  float relevance = 0.0;
  const_ITERATE(TDistributionVector, ci, *probabilities->discrete) {
    const TDiscDistribution &dist = CAST_TO_DISCDISTRIBUTION(*ci);
    if (ci == mostCommon) {
      TDiscDistribution dist2 = dist;
      dist2 += probabilities->innerDistributionUnknown;
      relevance += valueRelevance(dist2, classProbabilities);
    }
    else {
      relevance += valueRelevance(dist, classProbabilities);
    }
  }

  if (unknownsTreatment == TMeasureAttribute::UnknownsAsValue)
    relevance += valueRelevance(CAST_TO_DISCDISTRIBUTION(probabilities->innerDistributionUnknown), classProbabilities);

  relevance = 1.0 - relevance / float(C-1);

  if (unknownsTreatment == TMeasureAttribute::ReduceByUnknowns)
    relevance *= (outer.cases / (outer.unknowns + outer.cases));
  return round0(relevance);
}


#include "stat.hpp"

TMeasureAttribute_chiSquare::TMeasureAttribute_chiSquare(const int &unk, const bool probs)
: TMeasureAttributeFromProbabilities(true, false, unk),
  computeProbabilities(probs)
{}


float TMeasureAttribute_chiSquare::operator()(PContingency probabilities, const TDiscDistribution &classProbabilities)
{ 
  checkDiscrete(probabilities, "MeasureAttribute_chiSquare");
  
  const TDistribution &outer = probabilities->outerDistribution.getReference();
  if (   (classProbabilities.size() <= 0)
      || (probabilities->discrete->size() <= 0)
      || (unknownsTreatment == ReduceByUnknowns) && (outer.unknowns == outer.cases))
    return 0.0;

  TDiscDistribution expClass(classProbabilities);
  expClass.normalize();

  float df_in = -1.0, df_out = -1.0;
  ITERATE(TDiscDistribution, pi, expClass)
    if (*pi > 1e-6)
      df_in += 1.0;

  if (df_in == 0.0)
    return 0.0;

  float chisq = 0.0;
  const_ITERATE(TDistributionVector, ci, *probabilities->discrete) {
    float n0 = 0.0, psum = 0.0;
    const TDiscDistribution &dist = CAST_TO_DISCDISTRIBUTION(*ci);
    for(TDiscDistribution::const_iterator oi(dist.begin()), oe(dist.end()), pi(expClass.begin()), pe(expClass.end());
        (oi != oe) && (pi != pe); oi++, pi++) {
      if (*pi > 1e-6) {
        psum += *oi * *oi / *pi;
        n0 += *oi;
      }
    }
    if (n0 > 1e-6) {
      chisq += psum/n0 - n0;
      df_out += 1.0;
    }
  }

  if (df_out == 0.0)
    return 0.0;

  return computeProbabilities ? chisqprob(chisq, df_in * df_out) : chisq;
}




TMeasureAttribute_cost::TMeasureAttribute_cost(PCostMatrix costs)
: TMeasureAttributeFromProbabilities(true, false),
  cost(costs)
{}


float TMeasureAttribute_cost::majorityCost(const TDiscDistribution &dval)
{ float cost;
  TValue cclass;
  majorityCost(dval, cost, cclass);
  return cost;
}


void TMeasureAttribute_cost::majorityCost(const TDiscDistribution &dval, float &ccost, TValue &cclass)
{ 
  checkProperty(cost);

  int dsize = dval.size();
  if (dsize > cost->dimension)
    raiseError("cost matrix is too small");

  TRandomGenerator srgen(dval.sumValues());

  ccost = numeric_limits<float>::max();
  int wins = 0, bestPrediction;

  for(int predicted = 0; predicted < dsize; predicted++) {
    float thisCost = 0;
    for(int correct = 0; correct < dsize; correct++)
      thisCost += dval[correct] * cost->cost(predicted, correct);

    if (   (thisCost<ccost) && ((wins=1)==1)
        || (thisCost==ccost) && srgen.randbool(++wins)) {
      bestPrediction = predicted;
      ccost = thisCost; 
    }
  }
  
  ccost /= dval.abs;
  cclass = TValue(bestPrediction);
}


float TMeasureAttribute_cost::operator()(PContingency probabilities, const TDiscDistribution &classProbabilities)
{ 
  checkDiscrete(probabilities, "MeasureAttribute_cost");

  const TDistribution &outer = probabilities->outerDistribution.getReference();
  if ((unknownsTreatment == ReduceByUnknowns) && (outer.unknowns == outer.cases))
    return 0.0;
 
  checkProperty(cost);

  float stopCost = majorityCost(classProbabilities);
  
  TDistributionVector::const_iterator mostCommon = (unknownsTreatment == UnknownsToCommon)
    ? probabilities->discrete->begin() + outer.highestProbIntIndex()
    : probabilities->discrete->end();

  float continueCost = 0;
  float N = 0;
  const_ITERATE(TDistributionVector, ci, *probabilities->discrete) {