cluster.cpp File Reference

#include <cfloat>
#include <cmath>
#include <vector>
#include "cluster.h"
#include "cutil.h"
#include "emalloc.h"
#include "genericheap.h"
#include "helpers.h"
#include "kdpair.h"
#include "matrix.h"
#include "tprintf.h"

Go to the source code of this file.

Classes
struct	TEMPCLUSTER
struct	STATISTICS
struct	BUCKETS
struct	CHISTRUCT
struct	ClusteringContext

Macros
#define	HOTELLING   1
#define	FTABLE_X   10
#define	FTABLE_Y   100
#define	MINVARIANCE   0.0004
#define	MINSAMPLESPERBUCKET   5
#define	MINSAMPLES   (MINBUCKETS * MINSAMPLESPERBUCKET)
#define	MINSAMPLESNEEDED   1
#define	BUCKETTABLESIZE   1024
#define	NORMALEXTENT   3.0
#define	Odd(N)   ((N)%2)
#define	Mirror(N, R)   ((R) - (N) - 1)
#define	Abs(N)   (((N) < 0) ? (-(N)) : (N))
#define	SqrtOf2Pi   2.506628275
#define	LOOKUPTABLESIZE   8
#define	MAXDEGREESOFFREEDOM   MAXBUCKETS
#define	MAXNEIGHBORS   2
#define	MAXDISTANCE   FLT_MAX
#define	CHIACCURACY   0.01
#define	MINALPHA   (1e-200)
#define	INITIALDELTA   0.1
#define	DELTARATIO   0.1
#define	ILLEGAL_CHAR   2

Typedefs
using	ClusterPair = tesseract::KDPairInc< float, TEMPCLUSTER * >
using	ClusterHeap = tesseract::GenericHeap< ClusterPair >
typedef double(*	DENSITYFUNC) (int32_t)
typedef double(*	SOLVEFUNC) (CHISTRUCT *, double)

Functions
void	CreateClusterTree (CLUSTERER *Clusterer)
void	MakePotentialClusters (ClusteringContext *context, CLUSTER *Cluster, int32_t Level)
CLUSTER *	FindNearestNeighbor (KDTREE *Tree, CLUSTER *Cluster, float *Distance)
CLUSTER *	MakeNewCluster (CLUSTERER *Clusterer, TEMPCLUSTER *TempCluster)
int32_t	MergeClusters (int16_t N, PARAM_DESC ParamDesc[], int32_t n1, int32_t n2, float m[], float m1[], float m2[])
void	ComputePrototypes (CLUSTERER *Clusterer, CLUSTERCONFIG *Config)
PROTOTYPE *	MakePrototype (CLUSTERER *Clusterer, CLUSTERCONFIG *Config, CLUSTER *Cluster)
PROTOTYPE *	MakeDegenerateProto (uint16_t N, CLUSTER *Cluster, STATISTICS *Statistics, PROTOSTYLE Style, int32_t MinSamples)
PROTOTYPE *	TestEllipticalProto (CLUSTERER *Clusterer, CLUSTERCONFIG *Config, CLUSTER *Cluster, STATISTICS *Statistics)
PROTOTYPE *	MakeSphericalProto (CLUSTERER *Clusterer, CLUSTER *Cluster, STATISTICS *Statistics, BUCKETS *Buckets)
PROTOTYPE *	MakeEllipticalProto (CLUSTERER *Clusterer, CLUSTER *Cluster, STATISTICS *Statistics, BUCKETS *Buckets)
PROTOTYPE *	MakeMixedProto (CLUSTERER *Clusterer, CLUSTER *Cluster, STATISTICS *Statistics, BUCKETS *NormalBuckets, double Confidence)
void	MakeDimRandom (uint16_t i, PROTOTYPE *Proto, PARAM_DESC *ParamDesc)
void	MakeDimUniform (uint16_t i, PROTOTYPE *Proto, STATISTICS *Statistics)
STATISTICS *	ComputeStatistics (int16_t N, PARAM_DESC ParamDesc[], CLUSTER *Cluster)
PROTOTYPE *	NewSphericalProto (uint16_t N, CLUSTER *Cluster, STATISTICS *Statistics)
PROTOTYPE *	NewEllipticalProto (int16_t N, CLUSTER *Cluster, STATISTICS *Statistics)
PROTOTYPE *	NewMixedProto (int16_t N, CLUSTER *Cluster, STATISTICS *Statistics)
PROTOTYPE *	NewSimpleProto (int16_t N, CLUSTER *Cluster)
bool	Independent (PARAM_DESC *ParamDesc, int16_t N, float *CoVariance, float Independence)
BUCKETS *	GetBuckets (CLUSTERER *clusterer, DISTRIBUTION Distribution, uint32_t SampleCount, double Confidence)
BUCKETS *	MakeBuckets (DISTRIBUTION Distribution, uint32_t SampleCount, double Confidence)
uint16_t	OptimumNumberOfBuckets (uint32_t SampleCount)
double	ComputeChiSquared (uint16_t DegreesOfFreedom, double Alpha)
double	NormalDensity (int32_t x)
double	UniformDensity (int32_t x)
double	Integral (double f1, double f2, double Dx)
void	FillBuckets (BUCKETS *Buckets, CLUSTER *Cluster, uint16_t Dim, PARAM_DESC *ParamDesc, float Mean, float StdDev)
uint16_t	NormalBucket (PARAM_DESC *ParamDesc, float x, float Mean, float StdDev)
uint16_t	UniformBucket (PARAM_DESC *ParamDesc, float x, float Mean, float StdDev)
bool	DistributionOK (BUCKETS *Buckets)
void	FreeStatistics (STATISTICS *Statistics)
void	FreeBuckets (BUCKETS *Buckets)
void	FreeCluster (CLUSTER *Cluster)
uint16_t	DegreesOfFreedom (DISTRIBUTION Distribution, uint16_t HistogramBuckets)
int	NumBucketsMatch (void *arg1, void *arg2)
int	ListEntryMatch (void *arg1, void *arg2)
void	AdjustBuckets (BUCKETS *Buckets, uint32_t NewSampleCount)
void	InitBuckets (BUCKETS *Buckets)
int	AlphaMatch (void *arg1, void *arg2)
CHISTRUCT *	NewChiStruct (uint16_t DegreesOfFreedom, double Alpha)
double	Solve (SOLVEFUNC Function, void *FunctionParams, double InitialGuess, double Accuracy)
double	ChiArea (CHISTRUCT *ChiParams, double x)
bool	MultipleCharSamples (CLUSTERER *Clusterer, CLUSTER *Cluster, float MaxIllegal)
double	InvertMatrix (const float *input, int size, float *inv)
CLUSTERER *	MakeClusterer (int16_t SampleSize, const PARAM_DESC ParamDesc[])
SAMPLE *	MakeSample (CLUSTERER *Clusterer, const float *Feature, int32_t CharID)
LIST	ClusterSamples (CLUSTERER *Clusterer, CLUSTERCONFIG *Config)
void	FreeClusterer (CLUSTERER *Clusterer)
void	FreeProtoList (LIST *ProtoList)
void	FreePrototype (void *arg)
CLUSTER *	NextSample (LIST *SearchState)
float	Mean (PROTOTYPE *Proto, uint16_t Dimension)
float	StandardDeviation (PROTOTYPE *Proto, uint16_t Dimension)

Variables
const double	FTable [FTABLE_Y][FTABLE_X]

Macro Definition Documentation

Abs

#define Abs

(

N

)

(((N) < 0) ? (-(N)) : (N))

Definition at line 209 of file cluster.cpp.

BUCKETTABLESIZE

#define BUCKETTABLESIZE   1024

define the size of the table which maps normalized samples to histogram buckets. Also define the number of standard deviations in a normal distribution which are considered to be significant. The mapping table will be defined in such a way that it covers the specified number of standard deviations on either side of the mean. BUCKETTABLESIZE should always be even.

Definition at line 161 of file cluster.cpp.

CHIACCURACY

#define CHIACCURACY   0.01

DELTARATIO

#define DELTARATIO   0.1

FTABLE_X

#define FTABLE_X   10

Definition at line 32 of file cluster.cpp.

FTABLE_Y

#define FTABLE_Y   100

Definition at line 33 of file cluster.cpp.

HOTELLING

#define HOTELLING   1

Definition at line 31 of file cluster.cpp.

ILLEGAL_CHAR

#define ILLEGAL_CHAR   2

INITIALDELTA

#define INITIALDELTA   0.1

LOOKUPTABLESIZE

#define LOOKUPTABLESIZE   8

define lookup tables used to compute the number of histogram buckets that should be used for a given number of samples.

Definition at line 229 of file cluster.cpp.

MAXDEGREESOFFREEDOM

#define MAXDEGREESOFFREEDOM   MAXBUCKETS

Definition at line 230 of file cluster.cpp.

MAXDISTANCE

#define MAXDISTANCE   FLT_MAX

MAXNEIGHBORS

#define MAXNEIGHBORS   2

MINALPHA

#define MINALPHA   (1e-200)

MINSAMPLES

#define MINSAMPLES   (MINBUCKETS * MINSAMPLESPERBUCKET)

Definition at line 152 of file cluster.cpp.

MINSAMPLESNEEDED

#define MINSAMPLESNEEDED   1

Definition at line 153 of file cluster.cpp.

MINSAMPLESPERBUCKET

#define MINSAMPLESPERBUCKET   5

define the absolute minimum number of samples which must be present in order to accurately test hypotheses about underlying probability distributions. Define separately the minimum samples that are needed before a statistical analysis is attempted; this number should be equal to MINSAMPLES but can be set to a lower number for early testing when very few samples are available.

Definition at line 151 of file cluster.cpp.

MINVARIANCE

#define MINVARIANCE   0.0004

define the variance which will be used as a minimum variance for any dimension of any feature. Since most features are calculated from numbers with a precision no better than 1 in 128, the variance should never be less than the square of this number for parameters whose range is 1.

Definition at line 143 of file cluster.cpp.

Mirror

#define Mirror	(		N,
			R
	)		((R) - (N) - 1)

Definition at line 208 of file cluster.cpp.

NORMALEXTENT

#define NORMALEXTENT   3.0

Definition at line 162 of file cluster.cpp.

Odd

#define Odd

(

N

)

((N)%2)

Definition at line 207 of file cluster.cpp.

SqrtOf2Pi

#define SqrtOf2Pi   2.506628275

the following variables describe a discrete normal distribution which is used by NormalDensity() and NormalBucket(). The constant NORMALEXTENT determines how many standard deviations of the distribution are mapped onto the fixed discrete range of x. x=0 is mapped to -NORMALEXTENT standard deviations and x=BUCKETTABLESIZE is mapped to +NORMALEXTENT standard deviations.

Definition at line 219 of file cluster.cpp.

Typedef Documentation

ClusterHeap

using ClusterHeap = tesseract::GenericHeap<ClusterPair>

Definition at line 170 of file cluster.cpp.

ClusterPair

using ClusterPair = tesseract::KDPairInc<float, TEMPCLUSTER*>

Definition at line 169 of file cluster.cpp.

DENSITYFUNC

typedef double(* DENSITYFUNC) (int32_t)

Definition at line 204 of file cluster.cpp.

SOLVEFUNC

typedef double(* SOLVEFUNC) (CHISTRUCT *, double)

Definition at line 205 of file cluster.cpp.

Function Documentation

AdjustBuckets()

void AdjustBuckets	(	BUCKETS *	Buckets,
		uint32_t	NewSampleCount
	)

This routine multiplies each ExpectedCount histogram entry by NewSampleCount/OldSampleCount so that the histogram is now adjusted to the new sample count.

Parameters

Buckets	histogram data structure to adjust
NewSampleCount	new sample count to adjust to

Returns

none

Definition at line 2162 of file cluster.cpp.

                                                              {
  int i;
  double AdjustFactor;

  AdjustFactor = (((double) NewSampleCount) /
    ((double) Buckets->SampleCount));

  for (i = 0; i < Buckets->NumberOfBuckets; i++) {
    Buckets->ExpectedCount[i] *= AdjustFactor;
  }

  Buckets->SampleCount = NewSampleCount;

}                                // AdjustBuckets

AlphaMatch()

int AlphaMatch	(	void *	arg1,
		void *	arg2
	)

This routine is used to search a list of structures which hold pre-computed chi-squared values for a chi-squared value whose corresponding alpha field matches the alpha field of SearchKey.

It is called by the list search routines.

Parameters

arg1	chi-squared struct being tested for a match
arg2	chi-squared struct that is the search key

Returns

TRUE if ChiStruct's Alpha matches SearchKey's Alpha

Definition at line 2204 of file cluster.cpp.

                           {  //CHISTRUCT                             *SearchKey)
  CHISTRUCT *ChiStruct = (CHISTRUCT *) arg1;
  CHISTRUCT *SearchKey = (CHISTRUCT *) arg2;

  return (ChiStruct->Alpha == SearchKey->Alpha);

}                                // AlphaMatch

ChiArea()

double ChiArea	(	CHISTRUCT *	ChiParams,
		double	x
	)

This routine computes the area under a chi density curve from 0 to x, minus the desired area under the curve. The number of degrees of freedom of the chi curve is specified in the ChiParams structure. The desired area is also specified in the ChiParams structure as Alpha (or 1 minus the desired area). This routine is intended to be passed to the Solve() function to find the value of chi-squared which will yield a desired area under the right tail of the chi density curve. The function will only work for even degrees of freedom. The equations are based on integrating the chi density curve in parts to obtain a series that can be used to compute the area under the curve.

Parameters

ChiParams	contains degrees of freedom and alpha
x	value of chi-squared to evaluate

Returns

Error between actual and desired area under the chi curve.

Definition at line 2310 of file cluster.cpp.

                                               {
  int i, N;
  double SeriesTotal;
  double Denominator;
  double PowerOfx;

  N = ChiParams->DegreesOfFreedom / 2 - 1;
  SeriesTotal = 1;
  Denominator = 1;
  PowerOfx = 1;
  for (i = 1; i <= N; i++) {
    Denominator *= 2 * i;
    PowerOfx *= x;
    SeriesTotal += PowerOfx / Denominator;
  }
  return ((SeriesTotal * exp (-0.5 * x)) - ChiParams->Alpha);

}                                // ChiArea

ClusterSamples()

LIST ClusterSamples	(	CLUSTERER *	Clusterer,
		CLUSTERCONFIG *	Config
	)

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.

Parameters

Clusterer	data struct containing samples to be clustered
Config	parameters which control clustering process

Returns

Pointer to a list of prototypes

Definition at line 506 of file cluster.cpp.

                                                                 {
  //only create cluster tree if samples have never been clustered before
  if (Clusterer->Root == nullptr)
    CreateClusterTree(Clusterer);

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

  //compute prototypes starting at the root node in the tree
  ComputePrototypes(Clusterer, Config);
  // We don't need the cluster pointers in the protos any more, so null them
  // out, which makes it safe to delete the clusterer.
  LIST proto_list = Clusterer->ProtoList;
  iterate(proto_list) {
    PROTOTYPE *proto = reinterpret_cast<PROTOTYPE *>(first_node(proto_list));
    proto->Cluster = nullptr;
  }
  return Clusterer->ProtoList;
}                                // ClusterSamples

ComputeChiSquared()

double ComputeChiSquared	(	uint16_t	DegreesOfFreedom,
		double	Alpha
	)

This routine computes the chi-squared value which will leave a cumulative probability of Alpha in the right tail of a chi-squared distribution with the specified number of degrees of freedom. Alpha must be between 0 and 1. DegreesOfFreedom must be even. The routine maintains an array of lists. Each list corresponds to a different number of degrees of freedom. Each entry in the list corresponds to a different alpha value and its corresponding chi-squared value. Therefore, once a particular chi-squared value is computed, it is stored in the list and never needs to be computed again.

Parameters

DegreesOfFreedom	determines shape of distribution
Alpha	probability of right tail

Returns

Desired chi-squared value

Definition at line 1799 of file cluster.cpp.

{
  static LIST ChiWith[MAXDEGREESOFFREEDOM + 1];

  CHISTRUCT *OldChiSquared;
  CHISTRUCT SearchKey;

  // limit the minimum alpha that can be used - if alpha is too small
  //      it may not be possible to compute chi-squared.
  Alpha = ClipToRange(Alpha, MINALPHA, 1.0);
  if (Odd (DegreesOfFreedom))
    DegreesOfFreedom++;

  /* find the list of chi-squared values which have already been computed
     for the specified number of degrees of freedom.  Search the list for
     the desired chi-squared. */
  SearchKey.Alpha = Alpha;
  OldChiSquared = (CHISTRUCT *) first_node (search (ChiWith[DegreesOfFreedom],
    &SearchKey, AlphaMatch));

  if (OldChiSquared == nullptr) {
    OldChiSquared = NewChiStruct (DegreesOfFreedom, Alpha);
    OldChiSquared->ChiSquared = Solve (ChiArea, OldChiSquared,
      (double) DegreesOfFreedom,
      (double) CHIACCURACY);
    ChiWith[DegreesOfFreedom] = push (ChiWith[DegreesOfFreedom],
      OldChiSquared);
  }
  else {
    // further optimization might move OldChiSquared to front of list
  }

  return (OldChiSquared->ChiSquared);

}                                // ComputeChiSquared

ComputePrototypes()

void ComputePrototypes	(	CLUSTERER *	Clusterer,
		CLUSTERCONFIG *	Config
	)

This routine decides which clusters in the cluster tree should be represented by prototypes, forms a list of these prototypes, and places the list in the Clusterer data structure.

Parameters

Clusterer	data structure holding cluster tree
Config	parameters used to control prototype generation

Returns

None

Definition at line 894 of file cluster.cpp.

                                                                    {
  LIST ClusterStack = NIL_LIST;
  CLUSTER *Cluster;
  PROTOTYPE *Prototype;

  // use a stack to keep track of clusters waiting to be processed
  // initially the only cluster on the stack is the root cluster
  if (Clusterer->Root != nullptr)
    ClusterStack = push (NIL_LIST, Clusterer->Root);

  // loop until we have analyzed all clusters which are potential prototypes
  while (ClusterStack != NIL_LIST) {
    // remove the next cluster to be analyzed from the stack
    // try to make a prototype from the cluster
    // if successful, put it on the proto list, else split the cluster
    Cluster = (CLUSTER *) first_node (ClusterStack);
    ClusterStack = pop (ClusterStack);
    Prototype = MakePrototype(Clusterer, Config, Cluster);
    if (Prototype != nullptr) {
      Clusterer->ProtoList = push (Clusterer->ProtoList, Prototype);
    }
    else {
      ClusterStack = push (ClusterStack, Cluster->Right);
      ClusterStack = push (ClusterStack, Cluster->Left);
    }
  }
}                                // ComputePrototypes

ComputeStatistics()

STATISTICS * ComputeStatistics	(	int16_t	N,
		PARAM_DESC	ParamDesc[],
		CLUSTER *	Cluster
	)

This routine searches the cluster tree for all leaf nodes which are samples in the specified cluster. It computes a full covariance matrix for these samples as well as keeping track of the ranges (min and max) for each dimension. A special data structure is allocated to return this information to the caller. An incremental algorithm for computing statistics is not used because it will not work with circular dimensions.

Parameters

N	number of dimensions
ParamDesc	array of dimension descriptions
Cluster	cluster whose stats are to be computed

Returns

Pointer to new data structure containing statistics

Definition at line 1360 of file cluster.cpp.

                                                                         {
  STATISTICS *Statistics;
  int i, j;
  float *CoVariance;
  float *Distance;
  LIST SearchState;
  SAMPLE *Sample;
  uint32_t SampleCountAdjustedForBias;

  // allocate memory to hold the statistics results
  Statistics = (STATISTICS *) Emalloc (sizeof (STATISTICS));
  Statistics->CoVariance = (float *)Emalloc(sizeof(float) * N * N);
  Statistics->Min = (float *) Emalloc (N * sizeof (float));
  Statistics->Max = (float *) Emalloc (N * sizeof (float));

  // allocate temporary memory to hold the sample to mean distances
  Distance = (float *) Emalloc (N * sizeof (float));

  // initialize the statistics
  Statistics->AvgVariance = 1.0;
  CoVariance = Statistics->CoVariance;
  for (i = 0; i < N; i++) {
    Statistics->Min[i] = 0.0;
    Statistics->Max[i] = 0.0;
    for (j = 0; j < N; j++, CoVariance++)
      *CoVariance = 0;
  }
  // find each sample in the cluster and merge it into the statistics
  InitSampleSearch(SearchState, Cluster);
  while ((Sample = NextSample (&SearchState)) != nullptr) {
    for (i = 0; i < N; i++) {
      Distance[i] = Sample->Mean[i] - Cluster->Mean[i];
      if (ParamDesc[i].Circular) {
        if (Distance[i] > ParamDesc[i].HalfRange)
          Distance[i] -= ParamDesc[i].Range;
        if (Distance[i] < -ParamDesc[i].HalfRange)
          Distance[i] += ParamDesc[i].Range;
      }
      if (Distance[i] < Statistics->Min[i])
        Statistics->Min[i] = Distance[i];
      if (Distance[i] > Statistics->Max[i])
        Statistics->Max[i] = Distance[i];
    }
    CoVariance = Statistics->CoVariance;
    for (i = 0; i < N; i++)
      for (j = 0; j < N; j++, CoVariance++)
        *CoVariance += Distance[i] * Distance[j];
  }
  // normalize the variances by the total number of samples
  // use SampleCount-1 instead of SampleCount to get an unbiased estimate
  // also compute the geometic mean of the diagonal variances
  // ensure that clusters with only 1 sample are handled correctly
  if (Cluster->SampleCount > 1)
    SampleCountAdjustedForBias = Cluster->SampleCount - 1;
  else
    SampleCountAdjustedForBias = 1;
  CoVariance = Statistics->CoVariance;
  for (i = 0; i < N; i++)
  for (j = 0; j < N; j++, CoVariance++) {
    *CoVariance /= SampleCountAdjustedForBias;
    if (j == i) {
      if (*CoVariance < MINVARIANCE)
        *CoVariance = MINVARIANCE;
      Statistics->AvgVariance *= *CoVariance;
    }
  }
  Statistics->AvgVariance = (float)pow((double)Statistics->AvgVariance,
                                       1.0 / N);

  // release temporary memory and return
  free(Distance);
  return (Statistics);
}                                // ComputeStatistics

CreateClusterTree()

void CreateClusterTree

(

CLUSTERER *

Clusterer

)

This routine performs a bottoms-up clustering on the samples held in the kd-tree of the Clusterer data structure. The result is a cluster tree. Each node in the tree represents a cluster which conceptually contains a subset of the samples. More precisely, the cluster contains all of the samples which are contained in its two sub-clusters. The leaves of the tree are the individual samples themselves; they have no sub-clusters. The root node of the tree conceptually contains all of the samples.

Parameters

Clusterer

data structure holdings samples to be clustered

Returns

None (the Clusterer data structure is changed)

Definition at line 678 of file cluster.cpp.

                                             {
  ClusteringContext context;
  ClusterPair HeapEntry;
  TEMPCLUSTER *PotentialCluster;

  // each sample and its nearest neighbor form a "potential" cluster
  // save these in a heap with the "best" potential clusters on top
  context.tree = Clusterer->KDTree;
  context.candidates = (TEMPCLUSTER *)
    Emalloc(Clusterer->NumberOfSamples * sizeof(TEMPCLUSTER));
  context.next = 0;
  context.heap = new ClusterHeap(Clusterer->NumberOfSamples);
  KDWalk(context.tree, (void_proc)MakePotentialClusters, &context);

  // form potential clusters into actual clusters - always do "best" first
  while (context.heap->Pop(&HeapEntry)) {
    PotentialCluster = HeapEntry.data;

    // if main cluster of potential cluster is already in another cluster
    // then we don't need to worry about it
    if (PotentialCluster->Cluster->Clustered) {
      continue;
    }

    // if main cluster is not yet clustered, but its nearest neighbor is
    // then we must find a new nearest neighbor
    else if (PotentialCluster->Neighbor->Clustered) {
      PotentialCluster->Neighbor =
        FindNearestNeighbor(context.tree, PotentialCluster->Cluster,
                            &HeapEntry.key);
      if (PotentialCluster->Neighbor != nullptr) {
        context.heap->Push(&HeapEntry);
      }
    }

    // if neither cluster is already clustered, form permanent cluster
    else {
      PotentialCluster->Cluster =
          MakeNewCluster(Clusterer, PotentialCluster);
      PotentialCluster->Neighbor =
          FindNearestNeighbor(context.tree, PotentialCluster->Cluster,
                              &HeapEntry.key);
      if (PotentialCluster->Neighbor != nullptr) {
        context.heap->Push(&HeapEntry);
      }
    }
  }

  // the root node in the cluster tree is now the only node in the kd-tree
  Clusterer->Root = (CLUSTER *) RootOf(Clusterer->KDTree);

  // free up the memory used by the K-D tree, heap, and temp clusters
  FreeKDTree(context.tree);
  Clusterer->KDTree = nullptr;
  delete context.heap;
  free(context.candidates);
}                                // CreateClusterTree

DegreesOfFreedom()

uint16_t DegreesOfFreedom	(	DISTRIBUTION	Distribution,
		uint16_t	HistogramBuckets
	)

This routine computes the degrees of freedom that should be used in a chi-squared test with the specified number of histogram buckets. The result is always rounded up to the next even number so that the value of chi-squared can be computed more easily. This will cause the value of chi-squared to be higher than the optimum value, resulting in the chi-square test being more lenient than optimum.

Parameters

Distribution	distribution being tested for
HistogramBuckets	number of buckets in chi-square test

Returns

The number of degrees of freedom for a chi-square test

Definition at line 2113 of file cluster.cpp.

                                                                                {
  static uint8_t DegreeOffsets[] = { 3, 3, 1 };

  uint16_t AdjustedNumBuckets;

  AdjustedNumBuckets = HistogramBuckets - DegreeOffsets[(int) Distribution];
  if (Odd (AdjustedNumBuckets))
    AdjustedNumBuckets++;
  return (AdjustedNumBuckets);

}                                // DegreesOfFreedom

DistributionOK()

bool DistributionOK

(

BUCKETS *

Buckets

)

This routine performs a chi-square goodness of fit test on the histogram data in the Buckets data structure. TRUE is returned if the histogram matches the probability distribution which was specified when the Buckets structure was originally created. Otherwise FALSE is returned.

Parameters

Buckets

histogram data to perform chi-square test on

Returns

TRUE if samples match distribution, FALSE otherwise

Definition at line 2040 of file cluster.cpp.

                                      {
  float FrequencyDifference;
  float TotalDifference;
  int i;

  // compute how well the histogram matches the expected histogram
  TotalDifference = 0.0;
  for (i = 0; i < Buckets->NumberOfBuckets; i++) {
    FrequencyDifference = Buckets->Count[i] - Buckets->ExpectedCount[i];
    TotalDifference += (FrequencyDifference * FrequencyDifference) /
      Buckets->ExpectedCount[i];
  }

  // test to see if the difference is more than expected
  if (TotalDifference > Buckets->ChiSquared)
    return false;
  else
    return true;
}                                // DistributionOK

FillBuckets()

void FillBuckets	(	BUCKETS *	Buckets,
		CLUSTER *	Cluster,
		uint16_t	Dim,
		PARAM_DESC *	ParamDesc,
		float	Mean,
		float	StdDev
	)

This routine counts the number of cluster samples which fall within the various histogram buckets in Buckets. Only one dimension of each sample is examined. The exact meaning of the Mean and StdDev parameters depends on the distribution which is being analyzed (this info is in the Buckets data structure). For normal distributions, Mean and StdDev have the expected meanings. For uniform and random distributions the Mean is the center point of the range and the StdDev is 1/2 the range. A dimension with zero standard deviation cannot be statistically analyzed. In this case, a pseudo-analysis is used.

Parameters

Buckets	histogram buckets to count samples
Cluster	cluster whose samples are being analyzed
Dim	dimension of samples which is being analyzed
ParamDesc	description of the dimension
Mean	"mean" of the distribution
StdDev	"standard deviation" of the distribution

Returns

None (the Buckets data structure is filled in)

Definition at line 1905 of file cluster.cpp.

                               {
  uint16_t BucketID;
  int i;
  LIST SearchState;
  SAMPLE *Sample;

  // initialize the histogram bucket counts to 0
  for (i = 0; i < Buckets->NumberOfBuckets; i++)
    Buckets->Count[i] = 0;

  if (StdDev == 0.0) {
    /* if the standard deviation is zero, then we can't statistically
       analyze the cluster.  Use a pseudo-analysis: samples exactly on
       the mean are distributed evenly across all buckets.  Samples greater
       than the mean are placed in the last bucket; samples less than the
       mean are placed in the first bucket. */

    InitSampleSearch(SearchState, Cluster);
    i = 0;
    while ((Sample = NextSample (&SearchState)) != nullptr) {
      if (Sample->Mean[Dim] > Mean)
        BucketID = Buckets->NumberOfBuckets - 1;
      else if (Sample->Mean[Dim] < Mean)
        BucketID = 0;
      else
        BucketID = i;
      Buckets->Count[BucketID] += 1;
      i++;
      if (i >= Buckets->NumberOfBuckets)
        i = 0;
    }
  }
  else {
    // search for all samples in the cluster and add to histogram buckets
    InitSampleSearch(SearchState, Cluster);
    while ((Sample = NextSample (&SearchState)) != nullptr) {
      switch (Buckets->Distribution) {
        case normal:
          BucketID = NormalBucket (ParamDesc, Sample->Mean[Dim],
            Mean, StdDev);
          break;
        case D_random:
        case uniform:
          BucketID = UniformBucket (ParamDesc, Sample->Mean[Dim],
            Mean, StdDev);
          break;
        default:
          BucketID = 0;
      }
      Buckets->Count[Buckets->Bucket[BucketID]] += 1;
    }
  }
}                                // FillBuckets

FindNearestNeighbor()

CLUSTER * FindNearestNeighbor	(	KDTREE *	Tree,
		CLUSTER *	Cluster,
		float *	Distance
	)

This routine searches the specified kd-tree for the nearest neighbor of the specified cluster. It actually uses the kd routines to find the 2 nearest neighbors since one of them will be the original cluster. A pointer to the nearest neighbor is returned, if it can be found, otherwise nullptr is returned. The distance between the 2 nodes is placed in the specified variable.

Parameters

Tree	kd-tree to search in for nearest neighbor
Cluster	cluster whose nearest neighbor is to be found
Distance	ptr to variable to report distance found

Returns

Pointer to the nearest neighbor of Cluster, or nullptr

Definition at line 775 of file cluster.cpp.

{
  CLUSTER *Neighbor[MAXNEIGHBORS];
  float Dist[MAXNEIGHBORS];
  int NumberOfNeighbors;
  int32_t i;
  CLUSTER *BestNeighbor;

  // find the 2 nearest neighbors of the cluster
  KDNearestNeighborSearch(Tree, Cluster->Mean, MAXNEIGHBORS, MAXDISTANCE,
                          &NumberOfNeighbors, (void **)Neighbor, Dist);

  // search for the nearest neighbor that is not the cluster itself
  *Distance = MAXDISTANCE;
  BestNeighbor = nullptr;
  for (i = 0; i < NumberOfNeighbors; i++) {
    if ((Dist[i] < *Distance) && (Neighbor[i] != Cluster)) {
      *Distance = Dist[i];
      BestNeighbor = Neighbor[i];
    }
  }
  return BestNeighbor;
}                                // FindNearestNeighbor

FreeBuckets()

void FreeBuckets

(

BUCKETS *

buckets

)

This routine properly frees the memory used by a BUCKETS.

Parameters

buckets

pointer to data structure to be freed

Definition at line 2078 of file cluster.cpp.

                                   {
  Efree(buckets->Count);
  Efree(buckets->ExpectedCount);
  Efree(buckets);
}                                // FreeBuckets

FreeCluster()

void FreeCluster

(

CLUSTER *

Cluster

)

This routine frees the memory consumed by the specified cluster and all of its subclusters. This is done by recursive calls to FreeCluster().

Parameters

Cluster

pointer to cluster to be freed

Returns

None

Definition at line 2093 of file cluster.cpp.

                                   {
  if (Cluster != nullptr) {
    FreeCluster (Cluster->Left);
    FreeCluster (Cluster->Right);
    free(Cluster);
  }
}                                // FreeCluster

FreeClusterer()

void FreeClusterer

(

CLUSTERER *

Clusterer

)

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 nullptr 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.

Parameters

Clusterer

pointer to data structure to be freed

Returns

None

Definition at line 538 of file cluster.cpp.

                                         {
  if (Clusterer != nullptr) {
    free(Clusterer->ParamDesc);
    if (Clusterer->KDTree != nullptr)
      FreeKDTree (Clusterer->KDTree);
    if (Clusterer->Root != nullptr)
      FreeCluster (Clusterer->Root);
    // Free up all used buckets structures.
    for (int d = 0; d < DISTRIBUTION_COUNT; ++d) {
      for (int c = 0; c < MAXBUCKETS + 1 - MINBUCKETS; ++c)
        if (Clusterer->bucket_cache[d][c] != nullptr)
          FreeBuckets(Clusterer->bucket_cache[d][c]);
    }

    free(Clusterer);
  }
}                                // FreeClusterer

FreeProtoList()

void FreeProtoList

(

LIST *

ProtoList

)

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.

Parameters

ProtoList

pointer to list of prototypes to be freed

Returns

None

Definition at line 563 of file cluster.cpp.

                                    {
  destroy_nodes(*ProtoList, FreePrototype);
}                                // FreeProtoList

FreePrototype()

void FreePrototype

(

void *

arg

)

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.

Parameters

arg	prototype data structure to be deallocated

Returns

None

Definition at line 575 of file cluster.cpp.

                              {  //PROTOTYPE     *Prototype)
  PROTOTYPE *Prototype = (PROTOTYPE *) arg;

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

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

FreeStatistics()

void FreeStatistics

(

STATISTICS *

Statistics

)

This routine frees the memory used by the statistics data structure.

Parameters

Statistics

pointer to data structure to be freed

Returns

None

Definition at line 2066 of file cluster.cpp.

                                            {
  free(Statistics->CoVariance);
  free(Statistics->Min);
  free(Statistics->Max);
  free(Statistics);
}                                // FreeStatistics

GetBuckets()

BUCKETS * GetBuckets	(	CLUSTERER *	clusterer,
		DISTRIBUTION	Distribution,
		uint32_t	SampleCount,
		double	Confidence
	)

This routine returns a histogram data structure which can be used by other routines to place samples into histogram buckets, and then apply a goodness of fit test to the histogram data to determine if the samples belong to the specified probability distribution. The routine keeps a list of bucket data structures which have already been created so that it minimizes the computation time needed to create a new bucket.

Parameters

clusterer	which keeps a bucket_cache for us.
Distribution	type of probability distribution to test for
SampleCount	number of samples that are available
Confidence	probability of a Type I error

Returns

Bucket data structure

Definition at line 1624 of file cluster.cpp.

                                       {
  // Get an old bucket structure with the same number of buckets.
  uint16_t NumberOfBuckets = OptimumNumberOfBuckets(SampleCount);
  BUCKETS *Buckets =
      clusterer->bucket_cache[Distribution][NumberOfBuckets - MINBUCKETS];

  // If a matching bucket structure is not found, make one and save it.
  if (Buckets == nullptr) {
    Buckets = MakeBuckets(Distribution, SampleCount, Confidence);
    clusterer->bucket_cache[Distribution][NumberOfBuckets - MINBUCKETS] =
        Buckets;
  } else {
    // Just adjust the existing buckets.
    if (SampleCount != Buckets->SampleCount)
      AdjustBuckets(Buckets, SampleCount);
    if (Confidence != Buckets->Confidence) {
      Buckets->Confidence = Confidence;
      Buckets->ChiSquared = ComputeChiSquared(
          DegreesOfFreedom(Distribution, Buckets->NumberOfBuckets),
          Confidence);
    }
    InitBuckets(Buckets);
  }
  return Buckets;
}                                // GetBuckets

Independent()

bool Independent	(	PARAM_DESC *	ParamDesc,
		int16_t	N,
		float *	CoVariance,
		float	Independence
	)

This routine returns TRUE if the specified covariance matrix indicates that all N dimensions are independent of one another. One dimension is judged to be independent of another when the magnitude of the corresponding correlation coefficient is less than the specified Independence factor. The correlation coefficient is calculated as: (see Duda and Hart, pg. 247) coeff[ij] = stddev[ij] / sqrt (stddev[ii] * stddev[jj]) The covariance matrix is assumed to be symmetric (which should always be true).

Parameters

ParamDesc	descriptions of each feature space dimension
N	number of dimensions
CoVariance	ptr to a covariance matrix
Independence	max off-diagonal correlation coefficient

Returns

TRUE if dimensions are independent, FALSE otherwise

Definition at line 1579 of file cluster.cpp.

                                                              {
  int i, j;
  float *VARii;                // points to ith on-diagonal element
  float *VARjj;                // points to jth on-diagonal element
  float CorrelationCoeff;

  VARii = CoVariance;
  for (i = 0; i < N; i++, VARii += N + 1) {
    if (ParamDesc[i].NonEssential)
      continue;

    VARjj = VARii + N + 1;
    CoVariance = VARii + 1;
    for (j = i + 1; j < N; j++, CoVariance++, VARjj += N + 1) {
      if (ParamDesc[j].NonEssential)
        continue;

      if ((*VARii == 0.0) || (*VARjj == 0.0))
        CorrelationCoeff = 0.0;
      else
        CorrelationCoeff =
          sqrt (sqrt (*CoVariance * *CoVariance / (*VARii * *VARjj)));
      if (CorrelationCoeff > Independence)
        return false;
    }
  }
  return true;
}                                // Independent

InitBuckets()

void InitBuckets

(

BUCKETS *

Buckets

)

This routine sets the bucket counts in the specified histogram to zero.

Parameters

Buckets

histogram data structure to init

Returns

none

Definition at line 2183 of file cluster.cpp.

                                   {
  int i;

  for (i = 0; i < Buckets->NumberOfBuckets; i++) {
    Buckets->Count[i] = 0;
  }

}                                // InitBuckets

Integral()

double Integral	(	double	f1,
		double	f2,
		double	Dx
	)

This routine computes a trapezoidal approximation to the integral of a function over a small delta in x.

Parameters

f1	value of function at x1
f2	value of function at x2
Dx	x2 - x1 (should always be positive)

Returns

Approximation of the integral of the function from x1 to x2.

Definition at line 1881 of file cluster.cpp.

                                                 {
  return (f1 + f2) * Dx / 2.0;
}                                // Integral

InvertMatrix()

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

Compute the inverse of a matrix using LU decomposition with partial pivoting. The return value is the sum of norms of the off-diagonal terms of the product of a and inv. (A measure of the error.)

Definition at line 2409 of file cluster.cpp.

                                                              {
  // Allocate memory for the 2D arrays.
  GENERIC_2D_ARRAY<double> U(size, size, 0.0);
  GENERIC_2D_ARRAY<double> U_inv(size, size, 0.0);
  GENERIC_2D_ARRAY<double> L(size, size, 0.0);

  // Initialize the working matrices. U starts as input, L as I and U_inv as O.
  int row;
  int col;
  for (row = 0; row < size; row++) {
    for (col = 0; col < size; col++) {
      U[row][col] = input[row*size + col];
      L[row][col] = row == col ? 1.0 : 0.0;
      U_inv[row][col] = 0.0;
    }
  }

  // Compute forward matrix by inversion by LU decomposition of input.
  for (col = 0; col < size; ++col) {
    // Find best pivot
    int best_row = 0;
    double best_pivot = -1.0;
    for (row = col; row < size; ++row) {
      if (Abs(U[row][col]) > best_pivot) {
        best_pivot = Abs(U[row][col]);
        best_row = row;
      }
    }
    // Exchange pivot rows.
    if (best_row != col) {
      for (int k = 0; k < size; ++k) {
        double tmp = U[best_row][k];
        U[best_row][k] = U[col][k];
        U[col][k] = tmp;
        tmp = L[best_row][k];
        L[best_row][k] = L[col][k];
        L[col][k] = tmp;
      }
    }
    // Now do the pivot itself.
    for (row = col + 1; row < size; ++row) {
      double ratio = -U[row][col] / U[col][col];
      for (int j = col; j < size; ++j) {
        U[row][j] += U[col][j] * ratio;
      }
      for (int k = 0; k < size; ++k) {
        L[row][k] += L[col][k] * ratio;
      }
    }
  }
  // Next invert U.
  for (col = 0; col < size; ++col) {
    U_inv[col][col] = 1.0 / U[col][col];
    for (row = col - 1; row >= 0; --row) {
      double total = 0.0;
      for (int k = col; k > row; --k) {
        total += U[row][k] * U_inv[k][col];
      }
      U_inv[row][col] = -total / U[row][row];
    }
  }
  // Now the answer is U_inv.L.
  for (row = 0; row < size; row++) {
    for (col = 0; col < size; col++) {
      double sum = 0.0;
      for (int k = row; k < size; ++k) {
        sum += U_inv[row][k] * L[k][col];
      }
      inv[row*size + col] = sum;
    }
  }
  // Check matrix product.
  double error_sum = 0.0;
  for (row = 0; row < size; row++) {
    for (col = 0; col < size; col++) {
      double sum = 0.0;
      for (int k = 0; k < size; ++k) {
        sum += static_cast<double>(input[row * size + k]) * inv[k * size + col];
      }
      if (row != col) {
        error_sum += Abs(sum);
      }
    }
  }
  return error_sum;
}

ListEntryMatch()

int ListEntryMatch	(	void *	arg1,
		void *	arg2
	)

This routine is used to search a list for a list node whose contents match Key. It is called by the list delete_d routine.

Returns

TRUE if ListNode matches Key

Definition at line 2148 of file cluster.cpp.

                               {  //Key
  return (arg1 == arg2);

}                                // ListEntryMatch

MakeBuckets()

BUCKETS * MakeBuckets	(	DISTRIBUTION	Distribution,
		uint32_t	SampleCount,
		double	Confidence
	)

This routine creates a histogram data structure which can be used by other routines to place samples into histogram buckets, and then apply a goodness of fit test to the histogram data to determine if the samples belong to the specified probability distribution. The buckets are allocated in such a way that the expected frequency of samples in each bucket is approximately the same. In order to make this possible, a mapping table is computed which maps "normalized" samples into the appropriate bucket.

Parameters

Distribution	type of probability distribution to test for
SampleCount	number of samples that are available
Confidence	probability of a Type I error

Returns

Pointer to new histogram data structure

Definition at line 1669 of file cluster.cpp.

                                        {
  const DENSITYFUNC DensityFunction[] =
    { NormalDensity, UniformDensity, UniformDensity };
  int i, j;
  BUCKETS *Buckets;
  double BucketProbability;
  double NextBucketBoundary;
  double Probability;
  double ProbabilityDelta;
  double LastProbDensity;
  double ProbDensity;
  uint16_t CurrentBucket;
  bool Symmetrical;

  // allocate memory needed for data structure
  Buckets = static_cast<BUCKETS *>(Emalloc(sizeof(BUCKETS)));
  Buckets->NumberOfBuckets = OptimumNumberOfBuckets(SampleCount);
  Buckets->SampleCount = SampleCount;
  Buckets->Confidence = Confidence;
  Buckets->Count =
      static_cast<uint32_t *>(Emalloc(Buckets->NumberOfBuckets * sizeof(uint32_t)));
  Buckets->ExpectedCount = static_cast<float *>(
      Emalloc(Buckets->NumberOfBuckets * sizeof(float)));

  // initialize simple fields
  Buckets->Distribution = Distribution;
  for (i = 0; i < Buckets->NumberOfBuckets; i++) {
    Buckets->Count[i] = 0;
    Buckets->ExpectedCount[i] = 0.0;
  }

  // all currently defined distributions are symmetrical
  Symmetrical = true;
  Buckets->ChiSquared = ComputeChiSquared(
      DegreesOfFreedom(Distribution, Buckets->NumberOfBuckets), Confidence);

  if (Symmetrical) {
    // allocate buckets so that all have approx. equal probability
    BucketProbability = 1.0 / (double) (Buckets->NumberOfBuckets);

    // distribution is symmetric so fill in upper half then copy
    CurrentBucket = Buckets->NumberOfBuckets / 2;
    if (Odd (Buckets->NumberOfBuckets))
      NextBucketBoundary = BucketProbability / 2;
    else
      NextBucketBoundary = BucketProbability;

    Probability = 0.0;
    LastProbDensity =
      (*DensityFunction[(int) Distribution]) (BUCKETTABLESIZE / 2);
    for (i = BUCKETTABLESIZE / 2; i < BUCKETTABLESIZE; i++) {
      ProbDensity = (*DensityFunction[(int) Distribution]) (i + 1);
      ProbabilityDelta = Integral (LastProbDensity, ProbDensity, 1.0);
      Probability += ProbabilityDelta;
      if (Probability > NextBucketBoundary) {
        if (CurrentBucket < Buckets->NumberOfBuckets - 1)
          CurrentBucket++;
        NextBucketBoundary += BucketProbability;
      }
      Buckets->Bucket[i] = CurrentBucket;
      Buckets->ExpectedCount[CurrentBucket] +=
        (float) (ProbabilityDelta * SampleCount);
      LastProbDensity = ProbDensity;
    }
    // place any leftover probability into the last bucket
    Buckets->ExpectedCount[CurrentBucket] +=
      (float) ((0.5 - Probability) * SampleCount);

    // copy upper half of distribution to lower half
    for (i = 0, j = BUCKETTABLESIZE - 1; i < j; i++, j--)
      Buckets->Bucket[i] =
        Mirror(Buckets->Bucket[j], Buckets->NumberOfBuckets);

    // copy upper half of expected counts to lower half
    for (i = 0, j = Buckets->NumberOfBuckets - 1; i <= j; i++, j--)
      Buckets->ExpectedCount[i] += Buckets->ExpectedCount[j];
  }
  return Buckets;
}                                // MakeBuckets

MakeClusterer()

CLUSTERER* MakeClusterer	(	int16_t	SampleSize,
		const PARAM_DESC	ParamDesc[]
	)

This routine creates a new clusterer data structure, initializes it, and returns a pointer to it.

Parameters

SampleSize	number of dimensions in feature space
ParamDesc	description of each dimension

Returns

pointer to the new clusterer data structure

Definition at line 399 of file cluster.cpp.

                                                                 {
  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 = nullptr;
  Clusterer->ProtoList = NIL_LIST;

  // 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);

  // Initialize cache of histogram buckets to minimize recomputing them.
  for (int d = 0; d < DISTRIBUTION_COUNT; ++d) {
    for (int c = 0; c < MAXBUCKETS + 1 - MINBUCKETS; ++c)
      Clusterer->bucket_cache[d][c] = nullptr;
  }

  return Clusterer;
}                                // MakeClusterer

MakeDegenerateProto()

PROTOTYPE * MakeDegenerateProto	(	uint16_t	N,
		CLUSTER *	Cluster,
		STATISTICS *	Statistics,
		PROTOSTYLE	Style,
		int32_t	MinSamples
	)

This routine checks for clusters which are degenerate and therefore cannot be analyzed in a statistically valid way. A cluster is defined as degenerate if it does not have at least MINSAMPLESNEEDED samples in it. If the cluster is found to be degenerate, a prototype of the specified style is generated and marked as insignificant. A cluster is also degenerate if it does not have at least MinSamples samples in it.

If the cluster is not degenerate, nullptr is returned.

Parameters

N	number of dimensions
Cluster	cluster being analyzed
Statistics	statistical info about cluster
Style	type of prototype to be generated
MinSamples	minimum number of samples in a cluster

Returns

Pointer to degenerate prototype or nullptr.

Definition at line 1027 of file cluster.cpp.

                                                   {
  PROTOTYPE *Proto = nullptr;

  if (MinSamples < MINSAMPLESNEEDED)
    MinSamples = MINSAMPLESNEEDED;

  if (Cluster->SampleCount < MinSamples) {
    switch (Style) {
      case spherical:
        Proto = NewSphericalProto (N, Cluster, Statistics);
        break;
      case elliptical:
      case automatic:
        Proto = NewEllipticalProto (N, Cluster, Statistics);
        break;
      case mixed:
        Proto = NewMixedProto (N, Cluster, Statistics);
        break;
    }
    Proto->Significant = FALSE;
  }
  return (Proto);
}                                // MakeDegenerateProto

MakeDimRandom()

void MakeDimRandom	(	uint16_t	i,
		PROTOTYPE *	Proto,
		PARAM_DESC *	ParamDesc
	)

This routine alters the ith dimension of the specified mixed prototype to be D_random.

Parameters

i	index of dimension to be changed
Proto	prototype whose dimension is to be altered
ParamDesc	description of specified dimension

Returns

None

Definition at line 1304 of file cluster.cpp.

                                                                        {
  Proto->Distrib[i] = D_random;
  Proto->Mean[i] = ParamDesc->MidRange;
  Proto->Variance.Elliptical[i] = ParamDesc->HalfRange;

  // subtract out the previous magnitude of this dimension from the total
  Proto->TotalMagnitude /= Proto->Magnitude.Elliptical[i];
  Proto->Magnitude.Elliptical[i] = 1.0 / ParamDesc->Range;
  Proto->TotalMagnitude *= Proto->Magnitude.Elliptical[i];
  Proto->LogMagnitude = log ((double) Proto->TotalMagnitude);

  // note that the proto Weight is irrelevant for D_random protos
}                                // MakeDimRandom

MakeDimUniform()

void MakeDimUniform	(	uint16_t	i,
		PROTOTYPE *	Proto,
		STATISTICS *	Statistics
	)

This routine alters the ith dimension of the specified mixed prototype to be uniform.

Parameters

i	index of dimension to be changed
Proto	prototype whose dimension is to be altered
Statistics	statistical info about prototype

Returns

None

Definition at line 1326 of file cluster.cpp.

                                                                          {
  Proto->Distrib[i] = uniform;
  Proto->Mean[i] = Proto->Cluster->Mean[i] +
    (Statistics->Min[i] + Statistics->Max[i]) / 2;
  Proto->Variance.Elliptical[i] =
    (Statistics->Max[i] - Statistics->Min[i]) / 2;
  if (Proto->Variance.Elliptical[i] < MINVARIANCE)
    Proto->Variance.Elliptical[i] = MINVARIANCE;

  // subtract out the previous magnitude of this dimension from the total
  Proto->TotalMagnitude /= Proto->Magnitude.Elliptical[i];
  Proto->Magnitude.Elliptical[i] =
    1.0 / (2.0 * Proto->Variance.Elliptical[i]);
  Proto->TotalMagnitude *= Proto->Magnitude.Elliptical[i];
  Proto->LogMagnitude = log ((double) Proto->TotalMagnitude);

  // note that the proto Weight is irrelevant for uniform protos
}                                // MakeDimUniform

MakeEllipticalProto()

PROTOTYPE * MakeEllipticalProto	(	CLUSTERER *	Clusterer,
		CLUSTER *	Cluster,
		STATISTICS *	Statistics,
		BUCKETS *	Buckets
	)

This routine tests the specified cluster to see if it can be approximated by an elliptical normal distribution. If it can be, then a new prototype is formed and returned to the caller. If it can't be, then nullptr is returned to the caller.

Parameters

Clusterer	data struct containing samples being clustered
Cluster	cluster to be made into an elliptical prototype
Statistics	statistical info about cluster
Buckets	histogram struct used to analyze distribution

Returns

Pointer to new elliptical prototype or nullptr.

Definition at line 1205 of file cluster.cpp.

                                                 {
  PROTOTYPE *Proto = nullptr;
  int i;

  // check that each dimension is a normal distribution
  for (i = 0; i < Clusterer->SampleSize; i++) {
    if (Clusterer->ParamDesc[i].NonEssential)
      continue;

    FillBuckets (Buckets, Cluster, i, &(Clusterer->ParamDesc[i]),
      Cluster->Mean[i],
      sqrt ((double) Statistics->
      CoVariance[i * (Clusterer->SampleSize + 1)]));
    if (!DistributionOK (Buckets))
      break;
  }
  // if all dimensions matched a normal distribution, make a proto
  if (i >= Clusterer->SampleSize)
    Proto = NewEllipticalProto (Clusterer->SampleSize, Cluster, Statistics);
  return (Proto);
}                                // MakeEllipticalProto

MakeMixedProto()

PROTOTYPE * MakeMixedProto	(	CLUSTERER *	Clusterer,
		CLUSTER *	Cluster,
		STATISTICS *	Statistics,
		BUCKETS *	NormalBuckets,
		double	Confidence
	)

This routine tests each dimension of the specified cluster to see what distribution would best approximate that dimension. Each dimension is compared to the following distributions in order: normal, random, uniform. If each dimension can be represented by one of these distributions, then a new prototype is formed and returned to the caller. If it can't be, then nullptr is returned to the caller.

Parameters

Clusterer	data struct containing samples being clustered
Cluster	cluster to be made into a prototype
Statistics	statistical info about cluster
NormalBuckets	histogram struct used to analyze distribution
Confidence	confidence level for alternate distributions

Returns

Pointer to new mixed prototype or nullptr.

Definition at line 1245 of file cluster.cpp.

                                             {
  PROTOTYPE *Proto;
  int i;
  BUCKETS *UniformBuckets = nullptr;
  BUCKETS *RandomBuckets = nullptr;

  // create a mixed proto to work on - initially assume all dimensions normal*/
  Proto = NewMixedProto (Clusterer->SampleSize, Cluster, Statistics);

  // find the proper distribution for each dimension
  for (i = 0; i < Clusterer->SampleSize; i++) {
    if (Clusterer->ParamDesc[i].NonEssential)
      continue;

    FillBuckets (NormalBuckets, Cluster, i, &(Clusterer->ParamDesc[i]),
      Proto->Mean[i],
      sqrt ((double) Proto->Variance.Elliptical[i]));
    if (DistributionOK (NormalBuckets))
      continue;

    if (RandomBuckets == nullptr)
      RandomBuckets =
        GetBuckets(Clusterer, D_random, Cluster->SampleCount, Confidence);
    MakeDimRandom (i, Proto, &(Clusterer->ParamDesc[i]));
    FillBuckets (RandomBuckets, Cluster, i, &(Clusterer->ParamDesc[i]),
      Proto->Mean[i], Proto->Variance.Elliptical[i]);
    if (DistributionOK (RandomBuckets))
      continue;

    if (UniformBuckets == nullptr)
      UniformBuckets =
        GetBuckets(Clusterer, uniform, Cluster->SampleCount, Confidence);
    MakeDimUniform(i, Proto, Statistics);
    FillBuckets (UniformBuckets, Cluster, i, &(Clusterer->ParamDesc[i]),
      Proto->Mean[i], Proto->Variance.Elliptical[i]);
    if (DistributionOK (UniformBuckets))
      continue;
    break;
  }
  // if any dimension failed to match a distribution, discard the proto
  if (i < Clusterer->SampleSize) {
    FreePrototype(Proto);
    Proto = nullptr;
  }
  return (Proto);
}                                // MakeMixedProto

MakeNewCluster()

CLUSTER * MakeNewCluster	(	CLUSTERER *	Clusterer,
		TEMPCLUSTER *	TempCluster
	)

This routine creates a new permanent cluster from the clusters specified in TempCluster. The 2 clusters in TempCluster are marked as "clustered" and deleted from the kd-tree. The new cluster is then added to the kd-tree.

Parameters

Clusterer	current clustering environment
TempCluster	potential cluster to make permanent

Returns

Pointer to the new permanent cluster

Definition at line 810 of file cluster.cpp.

                                                                        {
  CLUSTER *Cluster;

  // allocate the new cluster and initialize it
  Cluster = (CLUSTER *) Emalloc(
      sizeof(CLUSTER) + (Clusterer->SampleSize - 1) * sizeof(float));
  Cluster->Clustered = FALSE;
  Cluster->Prototype = FALSE;
  Cluster->Left = TempCluster->Cluster;
  Cluster->Right = TempCluster->Neighbor;
  Cluster->CharID = -1;

  // mark the old clusters as "clustered" and delete them from the kd-tree
  Cluster->Left->Clustered = TRUE;
  Cluster->Right->Clustered = TRUE;
  KDDelete(Clusterer->KDTree, Cluster->Left->Mean, Cluster->Left);
  KDDelete(Clusterer->KDTree, Cluster->Right->Mean, Cluster->Right);

  // compute the mean and sample count for the new cluster
  Cluster->SampleCount =
      MergeClusters(Clusterer->SampleSize, Clusterer->ParamDesc,
                    Cluster->Left->SampleCount, Cluster->Right->SampleCount,
                    Cluster->Mean, Cluster->Left->Mean, Cluster->Right->Mean);

  // add the new cluster to the KD tree
  KDStore(Clusterer->KDTree, Cluster->Mean, Cluster);
  return Cluster;
}                                // MakeNewCluster

MakePotentialClusters()

void MakePotentialClusters	(	ClusteringContext *	context,
		CLUSTER *	Cluster,
		int32_t	Level
	)

This routine is designed to be used in concert with the KDWalk routine. It will create a potential cluster for each sample in the kd-tree that is being walked. This potential cluster will then be pushed on the heap.

Parameters

context	ClusteringContext (see definition above)
Cluster	current cluster being visited in kd-tree walk
Level	level of this cluster in the kd-tree

Definition at line 745 of file cluster.cpp.

                                                            {
  ClusterPair HeapEntry;
  int next = context->next;
  context->candidates[next].Cluster = Cluster;
  HeapEntry.data = &(context->candidates[next]);
  context->candidates[next].Neighbor =
      FindNearestNeighbor(context->tree,
                          context->candidates[next].Cluster,
                          &HeapEntry.key);
  if (context->candidates[next].Neighbor != nullptr) {
    context->heap->Push(&HeapEntry);
    context->next++;
  }
}                                // MakePotentialClusters

MakePrototype()

PROTOTYPE * MakePrototype	(	CLUSTERER *	Clusterer,
		CLUSTERCONFIG *	Config,
		CLUSTER *	Cluster
	)

This routine attempts to create a prototype from the specified cluster that conforms to the distribution specified in Config. If there are too few samples in the cluster to perform a statistical analysis, then a prototype is generated but labelled as insignificant. If the dimensions of the cluster are not independent, no prototype is generated and nullptr is returned. If a prototype can be found that matches the desired distribution then a pointer to it is returned, otherwise nullptr is returned.

Parameters

Clusterer	data structure holding cluster tree
Config	parameters used to control prototype generation
Cluster	cluster to be made into a prototype

Returns

Pointer to new prototype or nullptr

Definition at line 937 of file cluster.cpp.

                                           {
  STATISTICS *Statistics;
  PROTOTYPE *Proto;
  BUCKETS *Buckets;

  // filter out clusters which contain samples from the same character
  if (MultipleCharSamples (Clusterer, Cluster, Config->MaxIllegal))
    return nullptr;

  // compute the covariance matrix and ranges for the cluster
  Statistics =
      ComputeStatistics(Clusterer->SampleSize, Clusterer->ParamDesc, Cluster);

  // check for degenerate clusters which need not be analyzed further
  // note that the MinSamples test assumes that all clusters with multiple
  // character samples have been removed (as above)
  Proto = MakeDegenerateProto(
      Clusterer->SampleSize, Cluster, Statistics, Config->ProtoStyle,
      (int32_t) (Config->MinSamples * Clusterer->NumChar));
  if (Proto != nullptr) {
    FreeStatistics(Statistics);
    return Proto;
  }
  // check to ensure that all dimensions are independent
  if (!Independent(Clusterer->ParamDesc, Clusterer->SampleSize,
                   Statistics->CoVariance, Config->Independence)) {
    FreeStatistics(Statistics);
    return nullptr;
  }

  if (HOTELLING && Config->ProtoStyle == elliptical) {
    Proto = TestEllipticalProto(Clusterer, Config, Cluster, Statistics);
    if (Proto != nullptr) {
      FreeStatistics(Statistics);
      return Proto;
    }
  }

  // create a histogram data structure used to evaluate distributions
  Buckets = GetBuckets(Clusterer, normal, Cluster->SampleCount,
                       Config->Confidence);

  // create a prototype based on the statistics and test it
  switch (Config->ProtoStyle) {
    case spherical:
      Proto = MakeSphericalProto(Clusterer, Cluster, Statistics, Buckets);
      break;
    case elliptical:
      Proto = MakeEllipticalProto(Clusterer, Cluster, Statistics, Buckets);
      break;
    case mixed:
      Proto = MakeMixedProto(Clusterer, Cluster, Statistics, Buckets,
                             Config->Confidence);
      break;
    case automatic:
      Proto = MakeSphericalProto(Clusterer, Cluster, Statistics, Buckets);
      if (Proto != nullptr)
        break;
      Proto = MakeEllipticalProto(Clusterer, Cluster, Statistics, Buckets);
      if (Proto != nullptr)
        break;
      Proto = MakeMixedProto(Clusterer, Cluster, Statistics, Buckets,
                             Config->Confidence);
      break;
  }
  FreeStatistics(Statistics);
  return Proto;
}                                // MakePrototype

MakeSample()

SAMPLE* MakeSample	(	CLUSTERER *	Clusterer,
		const float *	Feature,
		int32_t	CharID
	)

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.

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

Returns

Pointer to the new sample data structure

Definition at line 452 of file cluster.cpp.

                                   {
  SAMPLE *Sample;
  int i;

  // see if the samples have already been clustered - if so trap an error
  // Can't add samples after they have been clustered.
  ASSERT_HOST(Clusterer->Root == nullptr);

  // allocate the new sample and initialize it
  Sample = (SAMPLE *) Emalloc (sizeof (SAMPLE) +
    (Clusterer->SampleSize -
    1) * sizeof (float));
  Sample->Clustered = FALSE;
  Sample->Prototype = FALSE;
  Sample->SampleCount = 1;
  Sample->Left = nullptr;
  Sample->Right = nullptr;
  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, Sample);
  if (CharID >= Clusterer->NumChar)
    Clusterer->NumChar = CharID + 1;

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

  return (Sample);
}                                // MakeSample

MakeSphericalProto()

PROTOTYPE * MakeSphericalProto	(	CLUSTERER *	Clusterer,
		CLUSTER *	Cluster,
		STATISTICS *	Statistics,
		BUCKETS *	Buckets
	)

This routine tests the specified cluster to see if it can be approximated by a spherical normal distribution. If it can be, then a new prototype is formed and returned to the caller. If it can't be, then nullptr is returned to the caller.

Parameters

Clusterer	data struct containing samples being clustered
Cluster	cluster to be made into a spherical prototype
Statistics	statistical info about cluster
Buckets	histogram struct used to analyze distribution

Returns

Pointer to new spherical prototype or nullptr.

Definition at line 1170 of file cluster.cpp.

                                                {
  PROTOTYPE *Proto = nullptr;
  int i;

  // check that each dimension is a normal distribution
  for (i = 0; i < Clusterer->SampleSize; i++) {
    if (Clusterer->ParamDesc[i].NonEssential)
      continue;

    FillBuckets (Buckets, Cluster, i, &(Clusterer->ParamDesc[i]),
      Cluster->Mean[i],
      sqrt ((double) (Statistics->AvgVariance)));
    if (!DistributionOK (Buckets))
      break;
  }
  // if all dimensions matched a normal distribution, make a proto
  if (i >= Clusterer->SampleSize)
    Proto = NewSphericalProto (Clusterer->SampleSize, Cluster, Statistics);
  return (Proto);
}                                // MakeSphericalProto

Mean()

float Mean	(	PROTOTYPE *	Proto,
		uint16_t	Dimension
	)

This routine returns the mean of the specified prototype in the indicated dimension.

Parameters

Proto	prototype to return mean of
Dimension	dimension whose mean is to be returned

Returns

Mean of Prototype in Dimension

Definition at line 628 of file cluster.cpp.

                                                 {
  return (Proto->Mean[Dimension]);
}                                // Mean

MergeClusters()

int32_t MergeClusters	(	int16_t	N,
		PARAM_DESC	ParamDesc[],
		int32_t	n1,
		int32_t	n2,
		float	m[],
		float	m1[],
		float	m2[]
	)

This routine merges two clusters into one larger cluster. To do this it computes the number of samples in the new cluster and the mean of the new cluster. The ParamDesc information is used to ensure that circular dimensions are handled correctly.

Parameters

N	# of dimensions (size of arrays)
ParamDesc	array of dimension descriptions
n1,n2	number of samples in each old cluster
m	array to hold mean of new cluster
m1,m2	arrays containing means of old clusters

Returns

The number of samples in the new cluster.

Definition at line 852 of file cluster.cpp.

                                            {
  int32_t i, n;

  n = n1 + n2;
  for (i = N; i > 0; i--, ParamDesc++, m++, m1++, m2++) {
    if (ParamDesc->Circular) {
      // if distance between means is greater than allowed
      // reduce upper point by one "rotation" to compute mean
      // then normalize the mean back into the accepted range
      if ((*m2 - *m1) > ParamDesc->HalfRange) {
        *m = (n1 * *m1 + n2 * (*m2 - ParamDesc->Range)) / n;
        if (*m < ParamDesc->Min)
          *m += ParamDesc->Range;
      }
      else if ((*m1 - *m2) > ParamDesc->HalfRange) {
        *m = (n1 * (*m1 - ParamDesc->Range) + n2 * *m2) / n;
        if (*m < ParamDesc->Min)
          *m += ParamDesc->Range;
      }
      else
        *m = (n1 * *m1 + n2 * *m2) / n;
    }
    else
      *m = (n1 * *m1 + n2 * *m2) / n;
  }
  return n;
}                                // MergeClusters

MultipleCharSamples()

bool MultipleCharSamples	(	CLUSTERER *	Clusterer,
		CLUSTER *	Cluster,
		float	MaxIllegal
	)

This routine looks at all samples in the specified cluster. It computes a running estimate of the percentage of the characters which have more than 1 sample in the cluster. When this percentage exceeds MaxIllegal, TRUE is returned. Otherwise FALSE is returned. The CharID fields must contain integers which identify the training characters which were used to generate the sample. One integer is used for each sample. The NumChar field in the Clusterer must contain the number of characters in the training set. All CharID fields must be between 0 and NumChar-1. The main function of this routine is to help identify clusters which need to be split further, i.e. if numerous training characters have 2 or more features which are contained in the same cluster, then the cluster should be split.

Parameters

Clusterer	data structure holding cluster tree
Cluster	cluster containing samples to be tested
MaxIllegal	max percentage of samples allowed to have more than 1 feature in the cluster

Returns

TRUE if the cluster should be split, FALSE otherwise.

Definition at line 2353 of file cluster.cpp.

{
  static BOOL8 *CharFlags = nullptr;
  static int32_t NumFlags = 0;
  int i;
  LIST SearchState;
  SAMPLE *Sample;
  int32_t CharID;
  int32_t NumCharInCluster;
  int32_t NumIllegalInCluster;
  float PercentIllegal;

  // initial estimate assumes that no illegal chars exist in the cluster
  NumCharInCluster = Cluster->SampleCount;
  NumIllegalInCluster = 0;

  if (Clusterer->NumChar > NumFlags) {
    free(CharFlags);
    NumFlags = Clusterer->NumChar;
    CharFlags = (BOOL8 *) Emalloc (NumFlags * sizeof (BOOL8));
  }

  for (i = 0; i < NumFlags; i++)
    CharFlags[i] = FALSE;

  // find each sample in the cluster and check if we have seen it before
  InitSampleSearch(SearchState, Cluster);
  while ((Sample = NextSample (&SearchState)) != nullptr) {
    CharID = Sample->CharID;
    if (CharFlags[CharID] == FALSE) {
      CharFlags[CharID] = TRUE;
    }
    else {
      if (CharFlags[CharID] == TRUE) {
        NumIllegalInCluster++;
        CharFlags[CharID] = ILLEGAL_CHAR;
      }
      NumCharInCluster--;
      PercentIllegal = (float) NumIllegalInCluster / NumCharInCluster;
      if (PercentIllegal > MaxIllegal) {
        destroy(SearchState);
        return true;
      }
    }
  }
  return false;

}                                // MultipleCharSamples

NewChiStruct()

CHISTRUCT * NewChiStruct	(	uint16_t	DegreesOfFreedom,
		double	Alpha
	)

This routine allocates a new data structure which is used to hold a chi-squared value along with its associated number of degrees of freedom and alpha value.

Parameters

DegreesOfFreedom	degrees of freedom for new chi value
Alpha	confidence level for new chi value

Returns

none

Definition at line 2222 of file cluster.cpp.

                                                                 {
  CHISTRUCT *NewChiStruct;

  NewChiStruct = (CHISTRUCT *) Emalloc (sizeof (CHISTRUCT));
  NewChiStruct->DegreesOfFreedom = DegreesOfFreedom;
  NewChiStruct->Alpha = Alpha;
  return (NewChiStruct);

}                                // NewChiStruct

NewEllipticalProto()

PROTOTYPE * NewEllipticalProto	(	int16_t	N,
		CLUSTER *	Cluster,
		STATISTICS *	Statistics
	)

This routine creates an elliptical prototype data structure to approximate the samples in the specified cluster. Elliptical prototypes have a variance for each dimension. All dimensions are normally distributed and independent.

Parameters

N	number of dimensions
Cluster	cluster to be made into an elliptical prototype
Statistics	statistical info about samples in cluster

Returns

Pointer to a new elliptical prototype data structure

Definition at line 1476 of file cluster.cpp.

                                                      {
  PROTOTYPE *Proto;
  float *CoVariance;
  int i;

  Proto = NewSimpleProto (N, Cluster);
  Proto->Variance.Elliptical = (float *) Emalloc (N * sizeof (float));
  Proto->Magnitude.Elliptical = (float *) Emalloc (N * sizeof (float));
  Proto->Weight.Elliptical = (float *) Emalloc (N * sizeof (float));

  CoVariance = Statistics->CoVariance;
  Proto->TotalMagnitude = 1.0;
  for (i = 0; i < N; i++, CoVariance += N + 1) {
    Proto->Variance.Elliptical[i] = *CoVariance;
    if (Proto->Variance.Elliptical[i] < MINVARIANCE)
      Proto->Variance.Elliptical[i] = MINVARIANCE;

    Proto->Magnitude.Elliptical[i] =
      1.0 / sqrt(2.0 * M_PI * Proto->Variance.Elliptical[i]);
    Proto->Weight.Elliptical[i] = 1.0 / Proto->Variance.Elliptical[i];
    Proto->TotalMagnitude *= Proto->Magnitude.Elliptical[i];
  }
  Proto->LogMagnitude = log ((double) Proto->TotalMagnitude);
  Proto->Style = elliptical;
  return (Proto);
}                                // NewEllipticalProto

NewMixedProto()

PROTOTYPE * NewMixedProto	(	int16_t	N,
		CLUSTER *	Cluster,
		STATISTICS *	Statistics
	)

This routine creates a mixed prototype data structure to approximate the samples in the specified cluster. Mixed prototypes can have different distributions for each dimension. All dimensions are independent. The structure is initially filled in as though it were an elliptical prototype. The actual distributions of the dimensions can be altered by other routines.

Parameters

N	number of dimensions
Cluster	cluster to be made into a mixed prototype
Statistics	statistical info about samples in cluster

Returns

Pointer to a new mixed prototype data structure

Definition at line 1518 of file cluster.cpp.

                                                                              {
  PROTOTYPE *Proto;
  int i;

  Proto = NewEllipticalProto (N, Cluster, Statistics);
  Proto->Distrib = (DISTRIBUTION *) Emalloc (N * sizeof (DISTRIBUTION));

  for (i = 0; i < N; i++) {
    Proto->Distrib[i] = normal;
  }
  Proto->Style = mixed;
  return (Proto);
}                                // NewMixedProto

NewSimpleProto()

PROTOTYPE * NewSimpleProto	(	int16_t	N,
		CLUSTER *	Cluster
	)

This routine allocates memory to hold a simple prototype data structure, i.e. one without independent distributions and variances for each dimension.

Parameters

N	number of dimensions
Cluster	cluster to be made into a prototype

Returns

Pointer to new simple prototype

Definition at line 1540 of file cluster.cpp.

                                                       {
  PROTOTYPE *Proto;
  int i;

  Proto = (PROTOTYPE *) Emalloc (sizeof (PROTOTYPE));
  Proto->Mean = (float *) Emalloc (N * sizeof (float));

  for (i = 0; i < N; i++)
    Proto->Mean[i] = Cluster->Mean[i];
  Proto->Distrib = nullptr;

  Proto->Significant = TRUE;
  Proto->Merged = FALSE;
  Proto->Style = spherical;
  Proto->NumSamples = Cluster->SampleCount;
  Proto->Cluster = Cluster;
  Proto->Cluster->Prototype = TRUE;
  return (Proto);
}                                // NewSimpleProto

NewSphericalProto()

PROTOTYPE * NewSphericalProto	(	uint16_t	N,
		CLUSTER *	Cluster,
		STATISTICS *	Statistics
	)

This routine creates a spherical prototype data structure to approximate the samples in the specified cluster. Spherical prototypes have a single variance which is common across all dimensions. All dimensions are normally distributed and independent.

Parameters

N	number of dimensions
Cluster	cluster to be made into a spherical prototype
Statistics	statistical info about samples in cluster

Returns

Pointer to a new spherical prototype data structure

Definition at line 1445 of file cluster.cpp.

                                                     {
  PROTOTYPE *Proto;

  Proto = NewSimpleProto (N, Cluster);

  Proto->Variance.Spherical = Statistics->AvgVariance;
  if (Proto->Variance.Spherical < MINVARIANCE)
    Proto->Variance.Spherical = MINVARIANCE;

  Proto->Magnitude.Spherical =
    1.0 / sqrt(2.0 * M_PI * Proto->Variance.Spherical);
  Proto->TotalMagnitude = (float)pow((double)Proto->Magnitude.Spherical,
                                     (double) N);
  Proto->Weight.Spherical = 1.0 / Proto->Variance.Spherical;
  Proto->LogMagnitude = log ((double) Proto->TotalMagnitude);

  return (Proto);
}                                // NewSphericalProto

NextSample()

CLUSTER* NextSample

(

LIST *

SearchState

)

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 left subcluster. This continues until a leaf is found. If all samples have been found, nullptr is returned. InitSampleSearch() must be called before NextSample() to initialize the search.

Parameters

SearchState

ptr to list containing clusters to be searched

Returns

Pointer to the next leaf cluster (sample) or nullptr.

Definition at line 606 of file cluster.cpp.

                                       {
  CLUSTER *Cluster;

  if (*SearchState == NIL_LIST)
    return (nullptr);
  Cluster = (CLUSTER *) first_node (*SearchState);
  *SearchState = pop (*SearchState);
  while (TRUE) {
    if (Cluster->Left == nullptr)
      return (Cluster);
    *SearchState = push (*SearchState, Cluster->Right);
    Cluster = Cluster->Left;
  }
}                                // NextSample

NormalBucket()

uint16_t NormalBucket	(	PARAM_DESC *	ParamDesc,
		float	x,
		float	Mean,
		float	StdDev
	)

This routine determines which bucket x falls into in the discrete normal distribution defined by kNormalMean and kNormalStdDev. x values which exceed the range of the discrete distribution are clipped.

Parameters

ParamDesc	used to identify circular dimensions
x	value to be normalized
Mean	mean of normal distribution
StdDev	standard deviation of normal distribution

Returns

Bucket number into which x falls

Definition at line 1975 of file cluster.cpp.

                                    {
  float X;

  // wraparound circular parameters if necessary
  if (ParamDesc->Circular) {
    if (x - Mean > ParamDesc->HalfRange)
      x -= ParamDesc->Range;
    else if (x - Mean < -ParamDesc->HalfRange)
      x += ParamDesc->Range;
  }

  X = ((x - Mean) / StdDev) * kNormalStdDev + kNormalMean;
  if (X < 0)
    return 0;
  if (X > BUCKETTABLESIZE - 1)
    return ((uint16_t) (BUCKETTABLESIZE - 1));
  return (uint16_t) floor((double) X);
}                                // NormalBucket

NormalDensity()

double NormalDensity

(

int32_t

x

)

This routine computes the probability density function of a discrete normal distribution defined by the global variables kNormalMean, kNormalVariance, and kNormalMagnitude. Normal magnitude could, of course, be computed in terms of the normal variance but it is precomputed for efficiency.

Parameters

x	number to compute the normal probability density for

Note

Globals: kNormalMean mean of a discrete normal distribution kNormalVariance variance of a discrete normal distribution kNormalMagnitude magnitude of a discrete normal distribution

Returns

The value of the normal distribution at x.

Definition at line 1850 of file cluster.cpp.

                                {
  double Distance;

  Distance = x - kNormalMean;
  return kNormalMagnitude * exp(-0.5 * Distance * Distance / kNormalVariance);
}                                // NormalDensity

NumBucketsMatch()

int NumBucketsMatch	(	void *	arg1,
		void *	arg2
	)

This routine is used to search a list of histogram data structures to find one with the specified number of buckets. It is called by the list search routines.

Parameters

arg1	current histogram being tested for a match
arg2	match key

Returns

TRUE if arg1 matches arg2

Definition at line 2133 of file cluster.cpp.

                                {  // uint16_t *DesiredNumberOfBuckets)
  BUCKETS *Histogram = (BUCKETS *) arg1;
  uint16_t *DesiredNumberOfBuckets = (uint16_t *) arg2;

  return (*DesiredNumberOfBuckets == Histogram->NumberOfBuckets);

}                                // NumBucketsMatch

OptimumNumberOfBuckets()

uint16_t OptimumNumberOfBuckets

(

uint32_t

SampleCount

)

This routine computes the optimum number of histogram buckets that should be used in a chi-squared goodness of fit test for the specified number of samples. The optimum number is computed based on Table 4.1 on pg. 147 of "Measurement and Analysis of Random Data" by Bendat & Piersol. Linear interpolation is used to interpolate between table values. The table is intended for a 0.05 level of significance (alpha). This routine assumes that it is equally valid for other alpha's, which may not be true.

Parameters

SampleCount

number of samples to be tested

Returns

Optimum number of histogram buckets

Definition at line 1764 of file cluster.cpp.

                                                      {
  uint8_t Last, Next;
  float Slope;

  if (SampleCount < kCountTable[0])
    return kBucketsTable[0];

  for (Last = 0, Next = 1; Next < LOOKUPTABLESIZE; Last++, Next++) {
    if (SampleCount <= kCountTable[Next]) {
      Slope = (float) (kBucketsTable[Next] - kBucketsTable[Last]) /
          (float) (kCountTable[Next] - kCountTable[Last]);
      return ((uint16_t) (kBucketsTable[Last] +
          Slope * (SampleCount - kCountTable[Last])));
    }
  }
  return kBucketsTable[Last];
}                                // OptimumNumberOfBuckets

Solve()

double Solve	(	SOLVEFUNC	Function,
		void *	FunctionParams,
		double	InitialGuess,
		double	Accuracy
	)

This routine attempts to find an x value at which Function goes to zero (i.e. a root of the function). It will only work correctly if a solution actually exists and there are no extrema between the solution and the InitialGuess. The algorithms used are extremely primitive.

Parameters

Function	function whose zero is to be found
FunctionParams	arbitrary data to pass to function
InitialGuess	point to start solution search at
Accuracy	maximum allowed error

Returns

Solution of function (x for which f(x) = 0).

Definition at line 2246 of file cluster.cpp.

{
  double x;
  double f;
  double Slope;
  double Delta;
  double NewDelta;
  double xDelta;
  double LastPosX, LastNegX;

  x = InitialGuess;
  Delta = INITIALDELTA;
  LastPosX = FLT_MAX;
  LastNegX = -FLT_MAX;
  f = (*Function) ((CHISTRUCT *) FunctionParams, x);
  while (Abs (LastPosX - LastNegX) > Accuracy) {
    // keep track of outer bounds of current estimate
    if (f < 0)
      LastNegX = x;
    else
      LastPosX = x;

    // compute the approx. slope of f(x) at the current point
    Slope =
      ((*Function) ((CHISTRUCT *) FunctionParams, x + Delta) - f) / Delta;

    // compute the next solution guess */
    xDelta = f / Slope;
    x -= xDelta;

    // reduce the delta used for computing slope to be a fraction of
    //the amount moved to get to the new guess
    NewDelta = Abs (xDelta) * DELTARATIO;
    if (NewDelta < Delta)
      Delta = NewDelta;

    // compute the value of the function at the new guess
    f = (*Function) ((CHISTRUCT *) FunctionParams, x);
  }
  return (x);

}                                // Solve

StandardDeviation()

float StandardDeviation	(	PROTOTYPE *	Proto,
		uint16_t	Dimension
	)

This routine returns the standard deviation of the prototype in the indicated dimension.

Parameters

Proto	prototype to return standard deviation of
Dimension	dimension whose stddev is to be returned

Returns

Standard deviation of Prototype in Dimension

Definition at line 639 of file cluster.cpp.

                                                              {
  switch (Proto->Style) {
    case spherical:
      return ((float) sqrt ((double) Proto->Variance.Spherical));
    case elliptical:
      return ((float)
        sqrt ((double) Proto->Variance.Elliptical[Dimension]));
    case mixed:
      switch (Proto->Distrib[Dimension]) {
        case normal:
          return ((float)
            sqrt ((double) Proto->Variance.Elliptical[Dimension]));
        case uniform:
        case D_random:
          return (Proto->Variance.Elliptical[Dimension]);
        case DISTRIBUTION_COUNT:
          ASSERT_HOST(!"Distribution count not allowed!");
      }
  }
  return 0.0f;
}                                // StandardDeviation

TestEllipticalProto()

PROTOTYPE * TestEllipticalProto	(	CLUSTERER *	Clusterer,
		CLUSTERCONFIG *	Config,
		CLUSTER *	Cluster,
		STATISTICS *	Statistics
	)

This routine tests the specified cluster to see if ** there is a statistically significant difference between the sub-clusters that would be made if the cluster were to be split. If not, then a new prototype is formed and returned to the caller. If there is, then nullptr is returned to the caller.

Parameters

Clusterer	data struct containing samples being clustered
Config	provides the magic number of samples that make a good cluster
Cluster	cluster to be made into an elliptical prototype
Statistics	statistical info about cluster

Returns

Pointer to new elliptical prototype or nullptr.

Definition at line 1069 of file cluster.cpp.

                                                       {
  // Fraction of the number of samples used as a range around 1 within
  // which a cluster has the magic size that allows a boost to the
  // FTable by kFTableBoostMargin, thus allowing clusters near the
  // magic size (equal to the number of sample characters) to be more
  // likely to stay together.
  const double kMagicSampleMargin = 0.0625;
  const double kFTableBoostMargin = 2.0;

  int N = Clusterer->SampleSize;
  CLUSTER* Left = Cluster->Left;
  CLUSTER* Right = Cluster->Right;
  if (Left == nullptr || Right == nullptr)
    return nullptr;
  int TotalDims = Left->SampleCount + Right->SampleCount;
  if (TotalDims < N + 1 || TotalDims < 2)
    return nullptr;
  std::vector<float> Covariance(static_cast<size_t>(N) * N);
  std::vector<float> Inverse(static_cast<size_t>(N) * N);
  std::vector<float> Delta(N);
  // Compute a new covariance matrix that only uses essential features.
  for (int i = 0; i < N; ++i) {
    int row_offset = i * N;
    if (!Clusterer->ParamDesc[i].NonEssential) {
      for (int j = 0; j < N; ++j) {
        if (!Clusterer->ParamDesc[j].NonEssential)
          Covariance[j + row_offset] = Statistics->CoVariance[j + row_offset];
        else
          Covariance[j + row_offset] = 0.0f;
      }
    } else {
      for (int j = 0; j < N; ++j) {
        if (i == j)
          Covariance[j + row_offset] = 1.0f;
        else
          Covariance[j + row_offset] = 0.0f;
      }
    }
  }
  double err = InvertMatrix(&Covariance[0], N, &Inverse[0]);
  if (err > 1) {
    tprintf("Clustering error: Matrix inverse failed with error %g\n", err);
  }
  int EssentialN = 0;
  for (int dim = 0; dim < N; ++dim) {
    if (!Clusterer->ParamDesc[dim].NonEssential) {
      Delta[dim] = Left->Mean[dim] - Right->Mean[dim];
      ++EssentialN;
    } else {
      Delta[dim] = 0.0f;
    }
  }
  // Compute Hotelling's T-squared.
  double Tsq = 0.0;
  for (int x = 0; x < N; ++x) {
    double temp = 0.0;
    for (int y = 0; y < N; ++y) {
      temp += static_cast<double>(Inverse[y + N * x]) * Delta[y];
    }
    Tsq += Delta[x] * temp;
  }
  // Changed this function to match the formula in
  // Statistical Methods in Medical Research p 473
  // By Peter Armitage, Geoffrey Berry, J. N. S. Matthews.
  // Tsq *= Left->SampleCount * Right->SampleCount / TotalDims;
  double F = Tsq * (TotalDims - EssentialN - 1) / ((TotalDims - 2)*EssentialN);
  int Fx = EssentialN;
  if (Fx > FTABLE_X)
    Fx = FTABLE_X;
  --Fx;
  int Fy = TotalDims - EssentialN - 1;
  if (Fy > FTABLE_Y)
    Fy = FTABLE_Y;
  --Fy;
  double FTarget = FTable[Fy][Fx];
  if (Config->MagicSamples > 0 &&
      TotalDims >= Config->MagicSamples * (1.0 - kMagicSampleMargin) &&
      TotalDims <= Config->MagicSamples * (1.0 + kMagicSampleMargin)) {
    // Give magic-sized clusters a magic FTable boost.
    FTarget += kFTableBoostMargin;
  }
  if (F < FTarget) {
    return NewEllipticalProto (Clusterer->SampleSize, Cluster, Statistics);
  }
  return nullptr;
}

UniformBucket()

uint16_t UniformBucket	(	PARAM_DESC *	ParamDesc,
		float	x,
		float	Mean,
		float	StdDev
	)

This routine determines which bucket x falls into in the discrete uniform distribution defined by BUCKETTABLESIZE. x values which exceed the range of the discrete distribution are clipped.

Parameters

ParamDesc	used to identify circular dimensions
x	value to be normalized
Mean	center of range of uniform distribution
StdDev	1/2 the range of the uniform distribution

Returns

Bucket number into which x falls

Definition at line 2008 of file cluster.cpp.

                                     {
  float X;

  // wraparound circular parameters if necessary
  if (ParamDesc->Circular) {
    if (x - Mean > ParamDesc->HalfRange)
      x -= ParamDesc->Range;
    else if (x - Mean < -ParamDesc->HalfRange)
      x += ParamDesc->Range;
  }

  X = ((x - Mean) / (2 * StdDev) * BUCKETTABLESIZE + BUCKETTABLESIZE / 2.0);
  if (X < 0)
    return 0;
  if (X > BUCKETTABLESIZE - 1)
    return (uint16_t) (BUCKETTABLESIZE - 1);
  return (uint16_t) floor((double) X);
}                                // UniformBucket

UniformDensity()

double UniformDensity

(

int32_t

x

)

This routine computes the probability density function of a uniform distribution at the specified point. The range of the distribution is from 0 to BUCKETTABLESIZE.

Parameters

x	number to compute the uniform probability density for

Returns

The value of the uniform distribution at x.

Definition at line 1864 of file cluster.cpp.

                                 {
  static double UniformDistributionDensity = (double) 1.0 / BUCKETTABLESIZE;

  if ((x >= 0.0) && (x <= BUCKETTABLESIZE))
    return UniformDistributionDensity;
  else
    return (double) 0.0;
}                                // UniformDensity

Variable Documentation

FTable

const double FTable[FTABLE_Y][FTABLE_X]

Definition at line 36 of file cluster.cpp.