Back to results
US 8,554,771 B2Granted
Technique for fast and efficient hierarchical clustering
AssigneeSandia Corporation
InventorChristopher Stork
Life of this patent
Estimating the term…
Abstract
A fast and efficient technique for hierarchical clustering of samples in a dataset includes compressing the dataset to reduce a number of variables within each of the samples of the dataset. A nearest neighbor matrix is generated to identify nearest neighbor pairs between the samples based on differences between the variables of the samples. The samples are arranged into a hierarchy that groups the samples based on the nearest neighbor matrix. The hierarchy is rendered to a display to graphically illustrate similarities or differences between the samples.
Claims22
A computer implemented method for hierarchical clustering of samples in a dataset, the method comprising:
- compressing the dataset to reduce a number of variables within each of the samples of the dataset;
- generating a nearest neighbor matrix identifying only nearest neighbor pairs between the samples based on differences between the variables of the samples and a corresponding proximity value associated with each of the nearest neighbor pairs;
- iteratively arranging the samples into a hierarchy that groups the samples based on the nearest neighbor matrix;
- and
- rendering the hierarchy to a display to graphically illustrate similarities or differences between the samples,
- wherein the nearest neighbor matrix is a separate data structure from the hierarchy that graphically illustrates similarities or differences between the samples, wherein the nearest neighbor matrix is iteratively updated to only identify updated nearest neighbor pairs with each iteration, and wherein each iteration of the separate data structure is used to generate a corresponding level of the hierarchy,
- wherein generating the nearest neighbor matrix comprises:
- calculating a vector component mean (VCM) for each of the samples;
- and
- for a given sample:
- calculating VCM differences between the VCM of the given sample and the VCM of all other samples;
- identifying a possible nearest neighbor to the given sample based at least indirectly on the VCM differences;
- calculating a distance using a proximity measure between the possible nearest neighbor and the given sample;
- and
- identifying a subset of additional possible nearest neighbors, base at least indirectly on the VCM differences and the distance calculated for just the possible nearest neighbor using the proximity measure, wherein a given nearest neighbor for the given sample is selected from amongst the possible nearest neighbor and the additional possible nearest neighbors, wherein the subset is less than all of the other samples.
12 more elements
A non-transitory computer-readable storage medium that provides instructions that, when executed by a machine, will cause the machine to perform operations comprising:
- compressing samples in a dataset to reduce a number of variables within each of the samples of the dataset;
- generating a nearest neighbor matrix identifying only nearest neighbor pairs between samples of a dataset based on differences between the variables of the samples and a corresponding proximity value associated with each of the nearest neighbor pairs;
- iteratively arranging the samples into a hierarchy that groups the samples based on the nearest neighbor matrix;
- and
- rendering the hierarchy to a display to graphically illustrate similarities or differences between the samples,
- wherein the nearest neighbor matrix is a separate data structure from the hierarchy that graphically illustrate similarities or differences between the samples, wherein the nearest neighbor matrix is iteratively updated to only identify updated nearest neighbor pairs with each iteration, and wherein each iteration of the separate data structure is used to generate a corresponding level of hierarchy,
- wherein generating the nearest neighbor matrix comprises:
- calculating a vector component mean (VCM) for each of the samples;
- and
- for a given sample:
- calculating VCM differences between the VCM of the given sample and the VCM of all other samples;
- identifying a possible nearest neighbor to the given sample based at least indirectly on the VCM differences;
- calculating a distance using a proximity measure between the possible nearest neighbor and the given sample;
- and
- identifying a subset of additional possible nearest neighbors, based at least indirectly on the VCM differences and the distance calculated for just the possible nearest neighbor using the proximity measure, wherein a given nearest neighbor for the given sample is selected from amongst the possible nearest neighbor and the additional possible nearest neighbors, wherein the subset is less than all of the other samples.
12 more elements
A non-transitory computer-readable storage medium that provides instructions that, when executed by a machine, will cause the machine to perform operations comprising:
- compressing an original dataset to generate a reduced dataset, wherein the reduced dataset includes samples each having a reduced number of variables than the samples of the original dataset;
- generating a nearest neighbor matrix based on the reduced dataset identifying only nearest neighbor pairs between the samples and a corresponding proximity value associated with each of the nearest neighbor pairs;
- iteratively arranging the samples into a hierarchy that clusters the samples based on measurements of similarity or dissimilarity between the samples;
- and
- rendering the hierarchy to display to graphically illustrate similarities or differences between the samples,
- wherein the nearest neighbor matrix is a separate data structure from the hierarchy that graphically illustrates similarities or differences between the samples, wherein the nearest neighbor matrix is iteratively updated to only identify updated nearest neighbor pairs with each iteration, and wherein each iteration of the separate data structure is used to generate a corresponding level of the hierarchy,
- wherein generating the nearest neighbor matrix comprises:
- calculating a vector component mean (VCM) for each of the samples;
- and
- for a given sample:
- calculating VCM differences between the VCM of the given sample and the VCM of all other samples;
- identifying a possible nearest neighbor to the given sample based at least indirectly on the VCM differences;
- calculating a distance using a proximity measure between the possible nearest neighbor and the given samples;
- and
- identifying a subset of additional possible nearest neighbors, based at least indirectly on the VCM differences and the distance calculated for the possible nearest neighbor using the proximity measure, wherein a given nearest neighbor for the given sample is selected from amongst the possible nearest neighbor and the additional possible nearest neighbors, wherein the subset is less than all of the other samples.
12 more elements
Dependencies are inferred from the claim text.