vfbn1.c

数据挖掘方面的源码

      numCPTEntries += BNNodeGetNumValues(bnn) * 
                       BNNodeGetNumCPTRows(bnn);
   }

   return numCPTEntries * kOneOverE;
}

long _BoundsUsedInComparison(BeliefNet first, BeliefNet second);
long _BoundsUsedInComparison(BeliefNet first, BeliefNet second) {
   BNUserData firstData = BNGetUserData(first);
   BNUserData secondData = BNGetUserData(second);
   BeliefNetNode bnn;
   int i1, i2, i;
   long numBoundsUsed;
   
   numBoundsUsed = 0;
   i1 = i2 = -1;

   if(firstData->changedOne) {
      bnn = firstData->changedOne;
      i = i1 = BNNodeGetID(bnn);

      numBoundsUsed += (BNNodeGetNumValues(bnn) *
                       BNNodeGetNumCPTRows(bnn)) + BNNodeGetNumCPTRows(bnn);
   }

   if(firstData->changedTwo) {
      bnn = firstData->changedTwo;
      i = i2 = BNNodeGetID(bnn);

      numBoundsUsed += (BNNodeGetNumValues(bnn) *
                       BNNodeGetNumCPTRows(bnn)) + BNNodeGetNumCPTRows(bnn);
   }

   if(secondData->changedOne) {
      bnn = secondData->changedOne;
      i = BNNodeGetID(bnn);
      if(i != i1 && i != i2) {
         /* don't compare same nodes twice */
         numBoundsUsed += (BNNodeGetNumValues(bnn) *
                       BNNodeGetNumCPTRows(bnn)) + BNNodeGetNumCPTRows(bnn);
      }
   }

   if(secondData->changedTwo) {
      bnn = secondData->changedTwo;
      i = BNNodeGetID(bnn);
      if(i != i1 && i != i2) {
         /* don't compare same nodes twice */
         numBoundsUsed += (BNNodeGetNumValues(bnn) *
                       BNNodeGetNumCPTRows(bnn)) + BNNodeGetNumCPTRows(bnn);
      }
   }

   return numBoundsUsed;
}

static BeliefNetNode _BNGetNodeByID(BeliefNet bn, BeliefNet current, int id) {
   BNUserData netData;

   netData = BNGetUserData(bn);

   if(netData->changedOne) {
      if(BNNodeGetID(netData->changedOne) == id) {
         return netData->changedOne;
      }
   }
   if(netData->changedTwo) {
      if(BNNodeGetID(netData->changedTwo) == id) {
         return netData->changedTwo;
      }
   }

   return BNGetNodeByID(current, id);
}

static double _CalculateCP(BeliefNetNode bnn, double event, double row) {
   /* HERE HERE Heuristic hack */
   return (event + 1.0) / (row + (float)BNNodeGetNumValues(bnn));
   //return event / row;
}

static double _GetEpsilonNormal(BeliefNet first, BeliefNet second, BeliefNet current) {
   BNUserData firstData = BNGetUserData(first);
   BNUserData secondData = BNGetUserData(second);
   BeliefNetNode bnn;
   int i, j, k, numCPTRows, n1, n2;
   double likelihood, numSamples;
   double bound;
   StatTracker st;
   
   bound = 0;


   n1 = n2 = -1;
   if(firstData->changedOne) {
      bnn = firstData->changedOne;
      n1 = BNNodeGetID(bnn);
      st = StatTrackerNew();

      numCPTRows = BNNodeGetNumCPTRows(bnn);
      numSamples = BNNodeGetNumSamples(bnn);
      for(j = 0 ; j < numCPTRows ; j++) {
         /* HACK for efficiency break BNN ADT */
         for(k = 0 ; k < BNNodeGetNumValues(bnn) ; k++) {
            likelihood = (bnn->eventCounts[j][k] / numSamples) * 
               log(_CalculateCP(bnn, bnn->eventCounts[j][k],
                                     bnn->rowCounts[j]));
            for(i = 0 ; i < bnn->eventCounts[j][k] ; i++) {
               StatTrackerAddSample(st, likelihood);
            }
         }
      }

      bound += StatTrackerGetNormalBound(st, gDeltaStar);
      StatTrackerFree(st);


      bnn = _BNGetNodeByID(second, current, n1);
      st = StatTrackerNew();

      numCPTRows = BNNodeGetNumCPTRows(bnn);
      numSamples = BNNodeGetNumSamples(bnn);
      for(j = 0 ; j < numCPTRows ; j++) {
         /* HACK for efficiency break BNN ADT */
         for(k = 0 ; k < BNNodeGetNumValues(bnn) ; k++) {
            likelihood = (bnn->eventCounts[j][k] / numSamples) * 
               log(_CalculateCP(bnn, bnn->eventCounts[j][k],
                                     bnn->rowCounts[j]));
            for(i = 0 ; i < bnn->eventCounts[j][k] ; i++) {
               StatTrackerAddSample(st, likelihood);
            }
         }
      }

      bound += StatTrackerGetNormalBound(st, gDeltaStar);
      StatTrackerFree(st);
   }

   if(firstData->changedTwo) {
      bnn = firstData->changedTwo;
      n2 = BNNodeGetID(bnn);
      st = StatTrackerNew();

      numCPTRows = BNNodeGetNumCPTRows(bnn);
      numSamples = BNNodeGetNumSamples(bnn);
      for(j = 0 ; j < numCPTRows ; j++) {
         /* HACK for efficiency break BNN ADT */
         for(k = 0 ; k < BNNodeGetNumValues(bnn) ; k++) {
            likelihood = (bnn->eventCounts[j][k] / numSamples) * 
               log(_CalculateCP(bnn, bnn->eventCounts[j][k],
                                     bnn->rowCounts[j]));
            for(i = 0 ; i < bnn->eventCounts[j][k] ; i++) {
               StatTrackerAddSample(st, likelihood);
            }
         }
      }

      bound += StatTrackerGetNormalBound(st, gDeltaStar);
      StatTrackerFree(st);


      bnn = _BNGetNodeByID(second, current, n2);
      st = StatTrackerNew();

      numCPTRows = BNNodeGetNumCPTRows(bnn);
      numSamples = BNNodeGetNumSamples(bnn);
      for(j = 0 ; j < numCPTRows ; j++) {
         /* HACK for efficiency break BNN ADT */
         for(k = 0 ; k < BNNodeGetNumValues(bnn) ; k++) {
            likelihood = (bnn->eventCounts[j][k] / numSamples) * 
               log(_CalculateCP(bnn, bnn->eventCounts[j][k],
                                     bnn->rowCounts[j]));
            for(i = 0 ; i < bnn->eventCounts[j][k] ; i++) {
               StatTrackerAddSample(st, likelihood);
            }
         }
      }

      bound += StatTrackerGetNormalBound(st, gDeltaStar);
      StatTrackerFree(st);
   }

   if(secondData->changedOne) {
      bnn = secondData->changedOne;
      if(BNNodeGetID(bnn) != n1 && BNNodeGetID(bnn) != n2) {
         st = StatTrackerNew();

         numCPTRows = BNNodeGetNumCPTRows(bnn);
         numSamples = BNNodeGetNumSamples(bnn);
         for(j = 0 ; j < numCPTRows ; j++) {
            /* HACK for efficiency break BNN ADT */
            for(k = 0 ; k < BNNodeGetNumValues(bnn) ; k++) {
               likelihood = (bnn->eventCounts[j][k] / numSamples) * 
                  log(_CalculateCP(bnn, bnn->eventCounts[j][k],
                                     bnn->rowCounts[j]));
               for(i = 0 ; i < bnn->eventCounts[j][k] ; i++) {
                  StatTrackerAddSample(st, likelihood);
               }
            }
         }

         bound += StatTrackerGetNormalBound(st, gDeltaStar);
         StatTrackerFree(st);



         bnn = _BNGetNodeByID(first, current, BNNodeGetID(bnn));
         st = StatTrackerNew();

         numCPTRows = BNNodeGetNumCPTRows(bnn);
         numSamples = BNNodeGetNumSamples(bnn);
         for(j = 0 ; j < numCPTRows ; j++) {
            /* HACK for efficiency break BNN ADT */
            for(k = 0 ; k < BNNodeGetNumValues(bnn) ; k++) {
               likelihood = (bnn->eventCounts[j][k] / numSamples) * 
                  log(_CalculateCP(bnn, bnn->eventCounts[j][k],
                                     bnn->rowCounts[j]));
               for(i = 0 ; i < bnn->eventCounts[j][k] ; i++) {
                  StatTrackerAddSample(st, likelihood);
               }
            }
         }

         bound += StatTrackerGetNormalBound(st, gDeltaStar);
         StatTrackerFree(st);
      }
   }

   if(secondData->changedTwo) {
      bnn = secondData->changedTwo;
      if(BNNodeGetID(bnn) != n1 && BNNodeGetID(bnn) != n2) {
         st = StatTrackerNew();

         numCPTRows = BNNodeGetNumCPTRows(bnn);
         numSamples = BNNodeGetNumSamples(bnn);
         for(j = 0 ; j < numCPTRows ; j++) {
            /* HACK for efficiency break BNN ADT */
            for(k = 0 ; k < BNNodeGetNumValues(bnn) ; k++) {
               likelihood = (bnn->eventCounts[j][k] / numSamples) * 
                  log(_CalculateCP(bnn, bnn->eventCounts[j][k],
                                     bnn->rowCounts[j]));
               for(i = 0 ; i < bnn->eventCounts[j][k] ; i++) {
                  StatTrackerAddSample(st, likelihood);
               }
            }
         }

         bound += StatTrackerGetNormalBound(st, gDeltaStar);
         StatTrackerFree(st);


         bnn = _BNGetNodeByID(first, current, BNNodeGetID(bnn));
         st = StatTrackerNew();

         numCPTRows = BNNodeGetNumCPTRows(bnn);
         numSamples = BNNodeGetNumSamples(bnn);
         for(j = 0 ; j < numCPTRows ; j++) {
            /* HACK for efficiency break BNN ADT */
            for(k = 0 ; k < BNNodeGetNumValues(bnn) ; k++) {
               likelihood = (bnn->eventCounts[j][k] / numSamples) * 
                  log(_CalculateCP(bnn, bnn->eventCounts[j][k],
                                     bnn->rowCounts[j]));
               for(i = 0 ; i < bnn->eventCounts[j][k] ; i++) {
                  StatTrackerAddSample(st, likelihood);
               }
            }
         }

         bound += StatTrackerGetNormalBound(st, gDeltaStar);
         StatTrackerFree(st);
      }
   }

   return bound;
}

static double _GetComparedNodesScoreRange(BeliefNet first,
                                                      BeliefNet second) {
   BNUserData firstData = BNGetUserData(first);
   BNUserData secondData = BNGetUserData(second);
   BeliefNetNode bnn;
   int i;
   double scoreRange;
   
   scoreRange = 0;

   /* HERE is this right or should it be 2x this? */

   if(firstData->changedOne) {
      bnn = firstData->changedOne;
      i = BNNodeGetID(bnn);

      scoreRange += _GetNodeScoreRange(bnn);
   }

   if(firstData->changedTwo) {
      bnn = firstData->changedTwo;
      i = BNNodeGetID(bnn);

      scoreRange += _GetNodeScoreRange(bnn);
   }

   if(secondData->changedOne) {
      bnn = secondData->changedOne;
      i = BNNodeGetID(bnn);

      scoreRange += _GetNodeScoreRange(bnn);
   }

   if(secondData->changedTwo) {
      bnn = secondData->changedTwo;
      i = BNNodeGetID(bnn);

      scoreRange += _GetNodeScoreRange(bnn);
   }

   return scoreRange;
}

static int _IsLinkCoveredIn(BeliefNetNode parent, BeliefNetNode child, 
                                                      BeliefNet bn) {
   /* x->y is covered in bn if par(y) = par(x) U x */
   /* this is important for checking equivilance because 
        G and G' are equivilant if identical except for reversal of x->y
                           iff x -> y is covered in G */
   /* NOTE this is k^2 but could be k if the parent lists were kept sorted */

   int i;
   BeliefNetNode childParent;
   int covered = 1;

   if(BNNodeGetNumParents(parent) != BNNodeGetNumParents(child) - 1) {
      covered = 0;
   }

   for(i = 0 ; i < BNNodeGetNumParents(child) && covered ; i++) {
      childParent = BNNodeGetParent(child, i);
      if((parent != childParent) && (!BNNodeHasParent(parent, childParent))) {
         covered = 0;
      }
   }

   return covered;
}

/* 
  2 possibilities with nodes (a, b):
   no link : make new net for each with a parent link added
   a -> b  : for a make new net with no link for b new net & reverse link

   remember: don't add any BNs with cycles!
   also: don't add any BNs that are equivilent
*/
void _GetOneStepChoicesForBN(BeliefNet bn, VoidListPtr list) {
   int i, j, srcParentOfDstIndex, dstParentOfSrcIndex;
   BeliefNet newBN;
   BeliefNetNode srcNode, dstNode;
   BNNodeUserData data;
   BNUserData netData;
   int isLinkCovered;
   long preAllocation;

   _InitUserData(bn, bn);

   //if(gDoBatch) {
   /* with pedro's new bound I don't know if we need bother with
         taking advantage of old samples, bound has to use min #
         samples in the compared nodes cause it bounds avg difference */
   BNZeroCPTs(bn);
   //}

   newBN = BNCloneNoCPTs(bn);
   _InitUserData(newBN, bn);
   VLAppend(list, newBN);

   if(gOnlyEstimateParameters) {
      return;
   }

   for(i = 0 ; i < BNGetNumNodes(bn) ; i++) {
      for(j = i + 1 ; j < BNGetNumNodes(bn) ; j++) {
         srcNode = BNGetNodeByID(bn, i);
         dstNode = BNGetNodeByID(bn, j);

         dstParentOfSrcIndex = BNNodeLookupParentIndex(srcNode, dstNode);