modelsearch.c

数据挖掘方面的源码

               if(gMaxParentsPerNode != -1 &&
                        BNNodeGetNumParents(netData->changedOne) > 
                                                    gMaxParentsPerNode) {
                  gNumByParentLimit++;
               } else if(gLimitBytes != -1 &&
                       ((MGetTotalAllocation() - preAllocation) >
                                                gMaxBytesPerModel)) {
                  gNumByMemoryLimit++;
               } else if(ms->linkChangeCounts[i] > 2) {
                  gNumByChangeLimit++;
               } else if(gMaxParameterCount != -1 && 
                     (BNNodeGetNumParameters(netData->changedOne)
                                              > gMaxParameterCount)) {
                  gNumByParameterLimit++;
               }

               _FreeUserData(netData);
            }
         } else if(gAllowRemove && 
                 BNNodeLookupParentIndex(currentNode, parentNode) != -1) {
            /* Consider removing the link */
            preAllocation = MGetTotalAllocation();

            netData = _InitUserData(ms->nodeID, 1, i, 0, ms->currentModel);

            DebugMessage(1, 3, " allocated new net, size %ld\n",
                   MGetTotalAllocation() - preAllocation);

            if((gMaxParameterCount == -1 ||
                    (BNNodeGetNumParameters(netData->changedOne) <= 
                                                  gMaxParameterCount)) &&

               (ms->linkChangeCounts[i] <= 2) &&

               (gLimitBytes == -1 ||
                      ((MGetTotalAllocation() - preAllocation) 
                                   <=  gMaxBytesPerModel)) &&

                  !_BNHasCycle(netData)) {
               VLAppend(ms->choices, netData);
            } else {
               if(gLimitBytes != -1 &&
                       ((MGetTotalAllocation() - preAllocation) >
                                                gMaxBytesPerModel)) {
                  gNumByMemoryLimit++;
               } else if(ms->linkChangeCounts[i] > 2) {
                  gNumByChangeLimit++;
               } else if(gMaxParameterCount != -1 && 
                     (BNNodeGetNumParameters(netData->changedOne) > 
                                                     gMaxParameterCount)) {
                  gNumByParameterLimit++;
               }

               _FreeUserData(netData);
            }
         }
      }
   }
}



static void _PickCurrentBestAsWinner(ModelSearch ms) {
   int i, bestIndex;
   BNUserData bestNet, compareNet;

   _UpdateNodeAveDataLL(BNGetNodeByID(ms->currentModel, ms->nodeID));

   /* do one pass to update scores & find best */
   bestNet = VLIndex(ms->choices, 0);
   bestIndex = 0;
   _UpdateNetScore(bestNet);

   if(VLLength(ms->choices) < 2) {
      /* we must have found a winner somehow, maybe only ever made 1*/
      DebugMessage(1, 3, "*******Warning: comparing one pick best\n");

      if(_IsCurrentNet(VLIndex(ms->choices, 0))) {
         gNumCurrentByWin++;
      }
      return;
   }

   for(i = 1 ; i < VLLength(ms->choices) ; i++) {
      compareNet = VLIndex(ms->choices, i);
      _UpdateNetScore(compareNet);


      if(!_IsFirstNetBetter(bestNet, compareNet)) {
         bestNet = compareNet;
         bestIndex = i;
      }

      //if(!_IsFirstNetBetter(bestNet, compareNet) || 
      //                            _IsCurrentNet(compareNet)) {
      //   if(!_IsCurrentNet(bestNet)) {
      //      bestNet = compareNet;
      //      bestIndex = i;
      //   }
      //}
   }

   for(i = VLLength(ms->choices) - 1 ; i >= 0 ; i--) {
      if(i != bestIndex) {
         _FreeUserData(VLRemove(ms->choices, i));
      }
   }

   if(_IsCurrentNet(VLIndex(ms->choices, 0))) {
      gNumCurrentInTie++;
   }
}

static void _CompareNetsBoundFreeLoosers(ModelSearch ms) {
//BeliefNet current, VoidListPtr netChoices) {

   int i, bestIndex, secondIndex;
   BNUserData bestNet, secondNet, compareNet;
   double deltaScore;
   double epsilon;
   double scoreRangeNode;

   _UpdateNodeAveDataLL(BNGetNodeByID(ms->currentModel, ms->nodeID));

   /* do one pass to update scores & find two best nets */
   bestNet = VLIndex(ms->choices, 0);
   bestIndex = 0;
   _UpdateNetScore(bestNet);

   if(VLLength(ms->choices) < 2) {
      /* we must have found a winner somehow, maybe only ever made 1*/
      DebugMessage(1, 3, "*******Warning: comparing one\n");

      if(_IsCurrentNet(VLIndex(ms->choices, 0))) {
         gNumCurrentByWin++;
      }

      return;
   }

   compareNet = VLIndex(ms->choices, 1);
   _UpdateNetScore(compareNet);
   if(!_IsFirstNetBetter(bestNet, compareNet)) {
      secondNet = bestNet;
      secondIndex = bestIndex;

      bestNet = compareNet;
      bestIndex = 1;
   } else {
      secondNet = compareNet;
      secondIndex = 1;
   }


   for(i = 2 ; i < VLLength(ms->choices) ; i++) {
      compareNet = VLIndex(ms->choices, i);
      _UpdateNetScore(compareNet);

//printf("id %d, changedParent %d, complexity %d\n", ms->nodeID, bestNet->changedParentID, bestNet->changeComplexity);
//printf("id %d, changedParent %d, complexity %d\n", ms->nodeID, compareNet->changedParentID, compareNet->changeComplexity);
      if(!_IsFirstNetBetter(bestNet, compareNet)) {
         secondNet = bestNet;
         secondIndex = bestIndex;

         bestNet = compareNet;
         bestIndex = i;
      } else if(!_IsFirstNetBetter(secondNet, compareNet)) {
         secondNet = compareNet;
         secondIndex = i;
      }
   }

   /* see if the bestNet beats the secondNet */
   deltaScore = _GetDeltaScore(bestNet, secondNet);

   scoreRangeNode = fabs(_GetComparedNodesScoreRange(bestNet, secondNet));

   /* HERE for missing data or unequal in compare */
   epsilon = _GetEpsilonNormal(bestNet, secondNet, ms->currentModel);

   DebugMessage(1, 3, " delta %lf epsilon %lf nodeRange: %f times-tau: %f\n",
          deltaScore, epsilon, scoreRangeNode, scoreRangeNode * gTau);
   if(deltaScore - epsilon > 0) {
      DebugMessage(1, 2,
               "Finish by winner, diff %f, epsilon %f were %d left\n", 
               deltaScore, epsilon, VLLength(ms->choices));

      gNumByWin += VLLength(ms->choices) - 1;
      gNumBoundsUsed += VLLength(ms->choices) - 1;

      if(_IsCurrentNet(bestNet)) {
         gNumCurrentByWin++;
      }

      for(i = VLLength(ms->choices) - 1 ; i >= 0 ; i--) {
         if(i != bestIndex) {
            _FreeUserData(VLRemove(ms->choices, i));
         }
      }
   } else {
      /* tie if it won't cost more than range * tau */
      if(fabs(deltaScore) <= epsilon &&
                    epsilon <= (gTau * scoreRangeNode)) {
         /* that's a tie */

         DebugMessage(1, 2, 
                "Finish by tie diff %f epsilon %f range %f with %d left\n",
             deltaScore, epsilon, scoreRangeNode, VLLength(ms->choices));
         //DebugMessage(1, 3, "  best %p compare %p\n", bestNet, secondNet);

         gNumByTie += VLLength(ms->choices) - 1;
         gNumBoundsUsed += VLLength(ms->choices) - 1;

         _PickWinnerInTieFreeRest(ms, bestIndex);

      } else if(fabs(deltaScore) < epsilon) {
         /* see if we could possibly call a tie */
         //if(tauNeededToQuitNode < epsilon / scoreRangeNode) {
         //   tauNeededToQuitNode = epsilon / scoreRangeNode;
         //}
      }
   }

   /* if not do another pass deactivating clear loosers */
   if(VLLength(ms->choices) > 1) {
      for(i = VLLength(ms->choices) - 1 ; i >= 0 ; i--) {
         if(i != bestIndex && i != secondIndex) {
            compareNet = VLIndex(ms->choices, i);
            deltaScore = _GetDeltaScore(secondNet, compareNet);
            scoreRangeNode = 
                  fabs(_GetComparedNodesScoreRange(secondNet, compareNet));

            /* HERE for missing data or unequal in compare */
            epsilon = _GetEpsilonNormal(secondNet, compareNet,
                                                ms->currentModel);

            if(deltaScore - epsilon > 0) {
               DebugMessage(1, 2, 
                 "Early freeing a net, diff %f, epsilon %f now %d left\n", 
                  deltaScore, epsilon, VLLength(ms->choices));
               gNumByWin++;
               gNumBoundsUsed++;

               if(_IsCurrentNet(compareNet)) {
                  DebugMessage(1, 2, 
                    " Current best freed bound - delta %lf epsilon %lf.\n", 
                                                    deltaScore, epsilon);
               }
               _FreeUserData(VLRemove(ms->choices, i));
            } 
         }
      }
   }
}

ModelSearch MSNew(BeliefNet currentBN, int nodeID) {
   int i;
   ModelSearch ms = MNewPtr(sizeof(ModelSearchStruct));

   ms->initialExampleNumber = -1;
   ms->lastParentAdded = -1;
   ms->isActive = 0;

   ms->choices = VLNew();
   ms->isDone = 0;
   ms->doneCollectingExamples = 0;

   ms->currentModel = currentBN;
   ms->nodeID       = nodeID;

   /* MEM this may leak some memory, but should only happen once */
   _InitCurrentUserData(currentBN);

   ms->linkChangeCounts = MNewPtr(sizeof(int) * BNGetNumNodes(currentBN));
   for(i = 0 ; i < BNGetNumNodes(currentBN) ; i++) {
      ms->linkChangeCounts[i] = 0;
   }

   return ms;
}

void MSFree(ModelSearch ms) {
   MSDeactivate(ms);
   VLFree(ms->choices);
   MFreePtr(ms->linkChangeCounts);
   MFreePtr(ms);
}

int MSGetNodeID(ModelSearch ms) {
   return ms->nodeID;
}

void MSAddExample(ModelSearch ms, ExamplePtr e, long exampleNumber) {
   int i;
   BNUserData netData;

   if(ms->initialExampleNumber == -1) {
      ms->initialExampleNumber = exampleNumber;
   } else if(exampleNumber == ms->initialExampleNumber) {
      /* we are at the end of looping through all the examples */
      /*  so just pick the best one as the winner and maybe print warning */

      ms->doneCollectingExamples = 1;

      gNumUsedWholeDB++;

      DebugMessage(1, 0, "******Looped through all examples\n");
   }

   if(!ms->doneCollectingExamples) {
      BNNodeAddSample(BNGetNodeByID(ms->currentModel, ms->nodeID), e);
      for(i = 0 ; i < VLLength(ms->choices) ; i++) {
         netData = VLIndex(ms->choices, i);
         if(netData->changedOne) {
            BNNodeAddSample(netData->changedOne, e);
         }
      }
   }
}

void MSTerminateSearch(ModelSearch ms) {
   ms->doneCollectingExamples = 1;
}

int MSIsDone(ModelSearch ms) {
   return ms->isDone;
}

static void _ApplyWinner(ModelSearch ms) {
   BNUserData winnerData;
   BNNodeUserData nodeData;
   BeliefNetNode changedNode;
   long samples;

   winnerData = VLRemove(ms->choices, 0);

   samples = BNNodeGetNumSamples(_BNGetNodeByID(winnerData, ms->nodeID));

   if(samples > 0) {
      gMinSamplesInDecision = min(samples, gMinSamplesInDecision);
      gMaxSamplesInDecision = max(samples, gMaxSamplesInDecision);
      gTotalSamplesInDecision += samples;
   } else {
      gNumZeroSamplesInDecision++;
   }


   /* if doing nothing wins then set isDone */
   if(_IsCurrentNet(winnerData)) {
      DebugMessage(1, 2, "Current net wins for %d\n", ms->nodeID);
      ms->isDone = 1;
   } else if(!_BNHasCycle(winnerData)) {
      ms->linkChangeCounts[winnerData->changedParentID]++;

      /* apply any winner to the current model */
      BNFlushStructureCache(ms->currentModel);
      BNNodeFreeCPT(BNGetNodeByID(ms->currentModel, ms->nodeID));

      if(winnerData->changeComplexity == -1) {
         gNumRemoved++;

         changedNode = BNGetNodeByID(ms->currentModel, ms->nodeID);
         BNNodeRemoveParent(changedNode,
           BNNodeLookupParentIndexByID(changedNode,
                                 winnerData->changedParentID));

         nodeData = BNNodeGetUserData(changedNode);
         nodeData->p0 = 1.0;

         DebugMessage(1, 2, "Winner for %d remove parent %d now %d parents\n", 
            ms->nodeID, winnerData->changedParentID,
             BNNodeGetNumParents(BNGetNodeByID(ms->currentModel, ms->nodeID)));
      } else if(winnerData->changeComplexity == 2) {
         gNumAdded++;

         changedNode = BNGetNodeByID(ms->currentModel, ms->nodeID);
         BNNodeAddParent(changedNode,
              BNGetNodeByID(ms->currentModel, winnerData->changedParentID));

         nodeData = BNNodeGetUserData(changedNode);
         nodeData->p0 = 1.0;

         DebugMessage(1, 2, "Winner for %d new parent %d now %d parents\n", 
            ms->nodeID, winnerData->changedParentID,
             BNNodeGetNumParents(BNGetNodeByID(ms->currentModel, ms->nodeID)));
      }


      BNNodeInitCPT(BNGetNodeByID(ms->currentModel, ms->nodeID));

      /* EFF I don't think I need this SetCPTFrom call */
      //BNNodeSetCPTFrom(BNGetNodeByID(ms->currentModel, ms->nodeID),
      //              BNGetNodeByID(winnerData->changedOne, ms->nodeID));

   }

   _FreeUserData(winnerData);

   MSDeactivate(ms);
}

int MSCheckForWinner(ModelSearch ms) {
   int foundWinner;

   if(MSIsDone(ms) || !MSIsActive(ms)) {
      foundWinner = 0;
   } else if(ms->doneCollectingExamples) {
      _PickCurrentBestAsWinner(ms);
      foundWinner = 1;
   } else {
      _CompareNetsBoundFreeLoosers(ms);

      if(VLLength(ms->choices) == 1) {
         foundWinner = 1;
      } else {
         foundWinner = 0;
      }
   }

   if(foundWinner) {
      _ApplyWinner(ms);
   }

   return foundWinner;
}

void MSModelChangedHandleConflicts(ModelSearch ms) {
   int i;
   BNUserData netData;

   /* apply the changes to each of the search alternatives */
   /* check each for cycles and if there are any free them */
   for(i = VLLength(ms->choices) - 1 ; i >= 0 ; i--) {
      netData = VLIndex(ms->choices, i);
      if(_BNHasCycle(netData)) {
         gNumByCycleConflict++;
         _FreeUserData(netData);
         VLRemove(ms->choices, i);

         //} else if(gMaxParameterCount != -1 &&
         //              (BNGetNumParameters(bn) > gMaxParameterCount)) {
         //      gNumByParameterConflict++;
         //      _FreeUserData(netData);
         //      VLRemove(ms->choices, i);
      }
   }

   if(VLLength(ms->choices) == 1) {
      /* if only one left then handle the winner */
      if(_IsCurrentNet(VLIndex(ms->choices, 0))) {
         gNumCurrentByDefault++;
      }
      _ApplyWinner(ms);
   } else if(VLLength(ms->choices) == 0) {
      /* if everyone is free then deactivate and let someone else cope */      
      MSDeactivate(ms);
   }
}


int MSIsActive(ModelSearch ms) {
   return ms->isActive;
}

void MSActivate(ModelSearch ms) {
   if(!ms->isActive) {
      _GetOneStepChoicesForSearch(ms);
      ms->isActive = 1;
      ms->doneCollectingExamples = 0;

      ms->numSearchOptions = VLLength(ms->choices);

      DebugMessage(1, 3, "    activated with %d alternatives\n",
                              ms->numSearchOptions);

      if(ms->numSearchOptions <= 1) {
         gNumCurrentByDefault++;
      }
   }
}

void MSDeactivate(ModelSearch ms) {
   int i;

   if(ms->isActive) {
      for(i = VLLength(ms->choices) - 1 ; i >= 0 ; i--) {
         _FreeUserData(VLRemove(ms->choices, i));
      }

      ms->isActive = 0;
   }
}

int MSNumActiveAlternatives(ModelSearch ms) {
   return VLLength(ms->choices);
}