cluster.cpp

一ＯＣＲ的相关资料。．希望对研究ＯＣＲ的朋友有所帮助．

PROTOTYPE *NewSphericalProto(UINT16 N,
                             CLUSTER *Cluster,
                             STATISTICS *Statistics);

PROTOTYPE *NewEllipticalProto(INT16 N,
                              CLUSTER *Cluster,
                              STATISTICS *Statistics);

PROTOTYPE *NewMixedProto(INT16 N, CLUSTER *Cluster, STATISTICS *Statistics);

PROTOTYPE *NewSimpleProto(INT16 N, CLUSTER *Cluster);

BOOL8 Independent (PARAM_DESC ParamDesc[],
INT16 N, FLOAT32 * CoVariance, FLOAT32 Independence);

BUCKETS *GetBuckets(DISTRIBUTION Distribution,
                    UINT32 SampleCount,
                    FLOAT64 Confidence);

BUCKETS *MakeBuckets(DISTRIBUTION Distribution,
                     UINT32 SampleCount,
                     FLOAT64 Confidence);

UINT16 OptimumNumberOfBuckets(UINT32 SampleCount);

FLOAT64 ComputeChiSquared(UINT16 DegreesOfFreedom, FLOAT64 Alpha);

FLOAT64 NormalDensity(INT32 x);

FLOAT64 UniformDensity(INT32 x);

FLOAT64 Integral(FLOAT64 f1, FLOAT64 f2, FLOAT64 Dx);

void FillBuckets(BUCKETS *Buckets,
                 CLUSTER *Cluster,
                 UINT16 Dim,
                 PARAM_DESC *ParamDesc,
                 FLOAT32 Mean,
                 FLOAT32 StdDev);

UINT16 NormalBucket(PARAM_DESC *ParamDesc,
                    FLOAT32 x,
                    FLOAT32 Mean,
                    FLOAT32 StdDev);

UINT16 UniformBucket(PARAM_DESC *ParamDesc,
                     FLOAT32 x,
                     FLOAT32 Mean,
                     FLOAT32 StdDev);

BOOL8 DistributionOK(BUCKETS *Buckets);

void FreeStatistics(STATISTICS *Statistics);

void FreeBuckets(BUCKETS *Buckets);

void FreeCluster(CLUSTER *Cluster);

UINT16 DegreesOfFreedom(DISTRIBUTION Distribution, UINT16 HistogramBuckets);

int NumBucketsMatch(void *arg1,   //BUCKETS                                       *Histogram,
                    void *arg2);  //UINT16                        *DesiredNumberOfBuckets);

int ListEntryMatch(void *arg1, void *arg2);

void AdjustBuckets(BUCKETS *Buckets, UINT32 NewSampleCount);

void InitBuckets(BUCKETS *Buckets);

int AlphaMatch(void *arg1,   //CHISTRUCT                             *ChiStruct,
               void *arg2);  //CHISTRUCT                             *SearchKey);

CHISTRUCT *NewChiStruct(UINT16 DegreesOfFreedom, FLOAT64 Alpha);

FLOAT64 Solve(SOLVEFUNC Function,
              void *FunctionParams,
              FLOAT64 InitialGuess,
              FLOAT64 Accuracy);

FLOAT64 ChiArea(CHISTRUCT *ChiParams, FLOAT64 x);

BOOL8 MultipleCharSamples(CLUSTERER *Clusterer,
                          CLUSTER *Cluster,
                          FLOAT32 MaxIllegal);

double InvertMatrix(const float* input, int size, float* inv);

//--------------------------Public Code--------------------------------------
/** MakeClusterer **********************************************************
Parameters:	SampleSize	number of dimensions in feature space
      ParamDesc	description of each dimension
Globals:	None
Operation:	This routine creates a new clusterer data structure,
      initializes it, and returns a pointer to it.
Return:		pointer to the new clusterer data structure
Exceptions:	None
History:	5/29/89, DSJ, Created.
****************************************************************************/
CLUSTERER *
MakeClusterer (INT16 SampleSize, PARAM_DESC ParamDesc[]) {
  CLUSTERER *Clusterer;
  int i;

  // allocate main clusterer data structure and init simple fields
  Clusterer = (CLUSTERER *) Emalloc (sizeof (CLUSTERER));
  Clusterer->SampleSize = SampleSize;
  Clusterer->NumberOfSamples = 0;
  Clusterer->NumChar = 0;

  // init fields which will not be used initially
  Clusterer->Root = NULL;
  Clusterer->ProtoList = NIL;

  // maintain a copy of param descriptors in the clusterer data structure
  Clusterer->ParamDesc =
    (PARAM_DESC *) Emalloc (SampleSize * sizeof (PARAM_DESC));
  for (i = 0; i < SampleSize; i++) {
    Clusterer->ParamDesc[i].Circular = ParamDesc[i].Circular;
    Clusterer->ParamDesc[i].NonEssential = ParamDesc[i].NonEssential;
    Clusterer->ParamDesc[i].Min = ParamDesc[i].Min;
    Clusterer->ParamDesc[i].Max = ParamDesc[i].Max;
    Clusterer->ParamDesc[i].Range = ParamDesc[i].Max - ParamDesc[i].Min;
    Clusterer->ParamDesc[i].HalfRange = Clusterer->ParamDesc[i].Range / 2;
    Clusterer->ParamDesc[i].MidRange =
      (ParamDesc[i].Max + ParamDesc[i].Min) / 2;
  }

  // allocate a kd tree to hold the samples
  Clusterer->KDTree = MakeKDTree (SampleSize, ParamDesc);

  // execute hook for monitoring clustering operation
  // (*ClustererCreationHook)( Clusterer );

  return (Clusterer);
}                                // MakeClusterer


/** MakeSample ***********************************************************
Parameters:	Clusterer	clusterer data structure to add sample to
      Feature		feature to be added to clusterer
      CharID		unique ident. of char that sample came from
Globals:	None
Operation:	This routine creates a new sample data structure to hold
      the specified feature.  This sample is added to the clusterer
      data structure (so that it knows which samples are to be
      clustered later), and a pointer to the sample is returned to
      the caller.
Return:		Pointer to the new sample data structure
Exceptions:	ALREADYCLUSTERED	MakeSample can't be called after
      ClusterSamples has been called
History:	5/29/89, DSJ, Created.
*****************************************************************************/
SAMPLE *
MakeSample (CLUSTERER * Clusterer, FLOAT32 Feature[], INT32 CharID) {
  SAMPLE *Sample;
  int i;

  // see if the samples have already been clustered - if so trap an error
  if (Clusterer->Root != NULL)
    DoError (ALREADYCLUSTERED,
      "Can't add samples after they have been clustered");

  // allocate the new sample and initialize it
  Sample = (SAMPLE *) Emalloc (sizeof (SAMPLE) +
    (Clusterer->SampleSize -
    1) * sizeof (FLOAT32));
  Sample->Clustered = FALSE;
  Sample->Prototype = FALSE;
  Sample->SampleCount = 1;
  Sample->Left = NULL;
  Sample->Right = NULL;
  Sample->CharID = CharID;

  for (i = 0; i < Clusterer->SampleSize; i++)
    Sample->Mean[i] = Feature[i];

  // add the sample to the KD tree - keep track of the total # of samples
  Clusterer->NumberOfSamples++;
  KDStore (Clusterer->KDTree, Sample->Mean, (char *) Sample);
  if (CharID >= Clusterer->NumChar)
    Clusterer->NumChar = CharID + 1;

  // execute hook for monitoring clustering operation
  // (*SampleCreationHook)( Sample );

  return (Sample);
}                                // MakeSample


/** ClusterSamples ***********************************************************
Parameters:	Clusterer	data struct containing samples to be clustered
      Config		parameters which control clustering process
Globals:	None
Operation:	This routine first checks to see if the samples in this
      clusterer have already been clustered before; if so, it does
      not bother to recreate the cluster tree.  It simply recomputes
      the prototypes based on the new Config info.
        If the samples have not been clustered before, the
      samples in the KD tree are formed into a cluster tree and then
      the prototypes are computed from the cluster tree.
        In either case this routine returns a pointer to a
      list of prototypes that best represent the samples given
      the constraints specified in Config.
Return:		Pointer to a list of prototypes
Exceptions:	None
History:	5/29/89, DSJ, Created.
*******************************************************************************/
LIST ClusterSamples(CLUSTERER *Clusterer, CLUSTERCONFIG *Config) {
  //only create cluster tree if samples have never been clustered before
  if (Clusterer->Root == NULL)
    CreateClusterTree(Clusterer);

  //deallocate the old prototype list if one exists
  FreeProtoList (&Clusterer->ProtoList);
  Clusterer->ProtoList = NIL;

  //compute prototypes starting at the root node in the tree
  ComputePrototypes(Clusterer, Config);
  return (Clusterer->ProtoList);
}                                // ClusterSamples


/** FreeClusterer *************************************************************
Parameters:	Clusterer	pointer to data structure to be freed
Globals:	None
Operation:	This routine frees all of the memory allocated to the
      specified data structure.  It will not, however, free
      the memory used by the prototype list.  The pointers to
      the clusters for each prototype in the list will be set
      to NULL to indicate that the cluster data structures no
      longer exist.  Any sample lists that have been obtained
      via calls to GetSamples are no longer valid.
Return:		None
Exceptions:	None
History:	6/6/89, DSJ, Created.
*******************************************************************************/
void FreeClusterer(CLUSTERER *Clusterer) {
  if (Clusterer != NULL) {
    memfree (Clusterer->ParamDesc);
    if (Clusterer->KDTree != NULL)
      FreeKDTree (Clusterer->KDTree);
    if (Clusterer->Root != NULL)
      FreeCluster (Clusterer->Root);
    iterate (Clusterer->ProtoList) {
      ((PROTOTYPE *) (first (Clusterer->ProtoList)))->Cluster = NULL;
    }
    memfree(Clusterer);
  }
}                                // FreeClusterer


/** FreeProtoList ************************************************************
Parameters:	ProtoList	pointer to list of prototypes to be freed
Globals:	None
Operation:	This routine frees all of the memory allocated to the
      specified list of prototypes.  The clusters which are
      pointed to by the prototypes are not freed.
Return:		None
Exceptions:	None
History:	6/6/89, DSJ, Created.
*****************************************************************************/
void FreeProtoList(LIST *ProtoList) {
  destroy_nodes(*ProtoList, FreePrototype);
}                                // FreeProtoList


/** FreePrototype ************************************************************
Parameters:	Prototype	prototype data structure to be deallocated
Globals:	None
Operation:	This routine deallocates the memory consumed by the specified
      prototype and modifies the corresponding cluster so that it
      is no longer marked as a prototype.  The cluster is NOT
      deallocated by this routine.
Return:		None
Exceptions:	None
History:	5/30/89, DSJ, Created.
*******************************************************************************/
void FreePrototype(void *arg) {  //PROTOTYPE     *Prototype)
  PROTOTYPE *Prototype = (PROTOTYPE *) arg;

  // unmark the corresponding cluster (if there is one
  if (Prototype->Cluster != NULL)
    Prototype->Cluster->Prototype = FALSE;

  // deallocate the prototype statistics and then the prototype itself
  if (Prototype->Distrib != NULL)
    memfree (Prototype->Distrib);
  if (Prototype->Mean != NULL)
    memfree (Prototype->Mean);
  if (Prototype->Style != spherical) {
    if (Prototype->Variance.Elliptical != NULL)
      memfree (Prototype->Variance.Elliptical);
    if (Prototype->Magnitude.Elliptical != NULL)
      memfree (Prototype->Magnitude.Elliptical);
    if (Prototype->Weight.Elliptical != NULL)
      memfree (Prototype->Weight.Elliptical);
  }
  memfree(Prototype);
}                                // FreePrototype


/** NextSample ************************************************************
Parameters:	SearchState	ptr to list containing clusters to be searched
Globals:	None
Operation:	This routine is used to find all of the samples which
      belong to a cluster.  It starts by removing the top
      cluster on the cluster list (SearchState).  If this cluster is
      a leaf it is returned.  Otherwise, the right subcluster
      is pushed on the list and we continue the search in the