#include "kdtree.h"
#include "oldlist.h"
Go to the source code of this file.
|
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) |
|
int32_t | MergeClusters (int16_t N, PARAM_DESC ParamDesc[], int32_t n1, int32_t n2, float m[], float m1[], float m2[]) |
|
◆ InitSampleSearch
◆ MAXBUCKETS
◆ MINBUCKETS
◆ CLUSTER
◆ SAMPLE
◆ DISTRIBUTION
Enumerator |
---|
normal | |
uniform | |
D_random | |
DISTRIBUTION_COUNT | |
Definition at line 55 of file cluster.h.
◆ PROTOSTYLE
Enumerator |
---|
spherical | |
elliptical | |
mixed | |
automatic | |
Definition at line 43 of file cluster.h.
◆ ClusterSamples()
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 483 of file cluster.cpp.
485 if (Clusterer->
Root ==
nullptr)
486 CreateClusterTree(Clusterer);
493 ComputePrototypes(Clusterer,
Config);
498 auto *proto = reinterpret_cast<PROTOTYPE *>(
first_node(proto_list));
499 proto->Cluster =
nullptr;
◆ FreeClusterer()
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 |
Definition at line 514 of file cluster.cpp.
515 if (Clusterer !=
nullptr) {
517 if (Clusterer->
KDTree !=
nullptr)
519 if (Clusterer->
Root !=
nullptr)
520 FreeCluster (Clusterer->
Root);
◆ 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 |
Definition at line 538 of file cluster.cpp.
◆ 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 |
Definition at line 549 of file cluster.cpp.
550 auto *Prototype = static_cast<PROTOTYPE *>(arg);
553 if (Prototype->Cluster !=
nullptr)
554 Prototype->Cluster->Prototype =
false;
557 free(Prototype->Distrib);
558 free(Prototype->Mean);
560 free(Prototype->Variance.Elliptical);
561 free(Prototype->Magnitude.Elliptical);
562 free(Prototype->Weight.Elliptical);
◆ MakeClusterer()
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 376 of file cluster.cpp.
387 Clusterer->
Root =
nullptr;
393 for (i = 0; i < SampleSize; i++) {
401 (ParamDesc[i].
Max + ParamDesc[i].
Min) / 2;
◆ 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 429 of file cluster.cpp.
441 1) * sizeof (
float)));
445 Sample->
Left =
nullptr;
446 Sample->
Right =
nullptr;
450 Sample->
Mean[i] = Feature[i];
455 if (CharID >= Clusterer->
NumChar)
456 Clusterer->
NumChar = CharID + 1;
◆ 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 602 of file cluster.cpp.
603 return (Proto->
Mean[Dimension]);
◆ 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 824 of file cluster.cpp.
833 for (i = N; i > 0; i--, ParamDesc++, m++, m1++, m2++) {
834 if (ParamDesc->Circular) {
838 if ((*m2 - *m1) > ParamDesc->HalfRange) {
839 *m = (n1 * *m1 + n2 * (*m2 - ParamDesc->Range)) / n;
840 if (*m < ParamDesc->Min)
841 *m += ParamDesc->Range;
843 else if ((*m1 - *m2) > ParamDesc->HalfRange) {
844 *m = (n1 * (*m1 - ParamDesc->Range) + n2 * *m2) / n;
845 if (*m < ParamDesc->Min)
846 *m += ParamDesc->Range;
849 *m = (n1 * *m1 + n2 * *m2) / n;
852 *m = (n1 * *m1 + n2 * *m2) / n;
◆ NextSample()
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 580 of file cluster.cpp.
586 *SearchState =
pop (*SearchState);
588 if (Cluster->
Left ==
nullptr)
590 *SearchState =
push (*SearchState, Cluster->
Right);
591 Cluster = Cluster->
Left;
◆ 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 613 of file cluster.cpp.
614 switch (Proto->
Style) {
616 return (static_cast<float>(sqrt (static_cast<double>(Proto->
Variance.
Spherical))));
618 return (static_cast<float>(sqrt (static_cast<double>(Proto->
Variance.
Elliptical[Dimension]))));
620 switch (Proto->
Distrib[Dimension]) {
622 return (static_cast<float>(sqrt (static_cast<double>(Proto->
Variance.
Elliptical[Dimension]))));