Method and Apparatus for Representing Multidimensional Data

• US 20090307248A1
• Filed: 03/30/2007
• Published: 12/10/2009
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: Nodality Inc.
• Original Assignee: Cira Discovery Sciences, Inc.
• Inventors: Holyst, Herbert Alan, Rogers, Wade Thomas, Moser, Allan Robert
• Granted Patent: US 8,214,157 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01N 15/1429 Signal processing
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 18/10 Pre-processing; Data cleansing
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/20 Supervised data analysis

Abstract

The present invention relates to methods for representing multidimensional data. The methods of the present invention are well suited but not limited to the representation of multidimensional data in such a way as to enable the comparison and differentiation of data sets. For example, the invention may be applied to the representation of flow cytometric data. The invention further relates to a program storage device having instructions for controlling a computer system to perform the methods, and to a program storage device containing data structures used in the practice of the methods.

Claims

1. A program storage device readable by a machine, said device tangibly embodying at least one program of instructions executable by the machine to cause the machine to perform steps for a method of representing data at multiple resolutions, said method comprising:

a. providing a data set;

b. representing said data in a multidimensional space;

c. dividing said multidimensional space into discrete data bins; and

d. subdividing data from each bin into finer resolution bins, wherein for at least one current bin, the subdividing comprises;

i. determining the direction of maximum variance of data contained within the current bin;

ii. rotating the coordinates of the data space in the direction of maximum variance, wherein the first axis of the rotated coordinates is parallel to the direction of maximum variance;

iii. determining the median value of the first coordinate in the rotated coordinate system for the collection of data comprising the selected bin;

iv. splitting the data comprising the current bin into two finer resolution bins, the first portion of the selected, split bin being comprised of events with a first coordinate less than or equal to the median, the second portion of the selected, split bin being comprised of events with a value of the first coordinate greater than the median; and

v. recording the rotation and median value (split value) associated with the current, split bin to a storage device.

2. The program storage device of claim 1, further comprising instructions for:

j. forming a bin of lowest resolution encompassing the complete data space and comprising all of the data within the data set; and

k. beginning with the lowest resolution, iterating over each level of resolution, subdividing each bin at a given resolution to form two bins at a higher resolution, continuing said subdivision until the desired number of bins is obtained.

3. The program storage device of claim 2, further comprising instructions for:

l. rotating the data space by applying the rotation matrix corresponding to the current bin after said subdividing; and

m. splitting the data comprising the current bin into two bins at the next hierarchical resolution level by using the split value for the current bin, wherein the first portion of the split bin is comprised of events with a first coordinate value less than or equal to the median, further wherein the second portion of the split bin is comprised of events with a first coordinate value is greater than the median.

4. The program storage device of claim 1, further comprising instructions for determining hyperplane boundaries of said bins, said method comprising:

a. specifying a rotation matrix of unit diagonal and zero off diagonal elements as the parent of the lowest resolution bin;

b. starting with the bin of lowest resolution, defining the hyperplane boundaries as the set of boundaries read in from the storage device;

c. beginning with the lowest resolution, iterating over each level of resolution, intersecting the hyperplane boundaries of the current bin with the hyperplane boundary utilized to split the current bin into its two children bins of higher resolution; and

d. recording the two sets of boundaries determined by the intersection as the hyperplane boundaries of the two children bin.

5. The program storage device of claim 4, wherein step c) of the method further comprises:

i. multiplying the rotation matrix for a bin by the rotation matrix of its parent bin;

ii. associating this product matrix with the current bin to be used as a parent bin in the next step in the iteration;

iii. constructing a direction vector from the elements of the first column of the product matrix computed in the previous step of the iteration;

iv. finding the hyperplane perpendicular to the direction vector constructed in the previous step of the iteration, wherein the vector passes through the split value for the current bin; and

v. identifying the hyperplane found in the previous step as the boundary utilized to split the current bin into its two children bins of higher resolution.

6. The program storage device of claim 1, further comprising instructions for determining one-dimensional lists of numbers comprising fingerprints for a set of instances relative to the representation of a multidimensional data set processed by the binning procedure, the method comprising forming a template instance by combining the events from a set of instances into a single data set.

7. The program storage device of claim 6, further comprising instructions for calculating an event density for each bin by dividing the number of events in each bin by the total number of events comprising the instance, for each of the instances in the set of instances.

8. The program storage device of claim 6, further comprising instructions for enumerating the bins in order of hierarchies of increasing resolution, and within a resolution level, in the order in which the bins were determined.

9. The program storage device of claim 8, further comprising instructions for the step of recording the list of numbers on a storage device.

10. The program storage device of claim 6, further comprising instructions for determining one-dimensional lists of numbers comprising fingerprints for sets of instances relative to the representations of two or more multidimensional data sets, the method comprising:

a. specifying two or more sets of instances, each set comprising a class of data sets; and

b. for each class, determining a set of bins representing each template instance and forming a template instance for that class by combining the events from the set of instances comprising the class into single data set;

11. The program storage device of claim 10, further comprising instructions, for each feature in the fingerprints for instances comprising each class, for calculating the average and standard deviation of each feature, further wherein an average and standard deviation are associated with each bin for each class.

12. The program storage device of claim 10, further comprising instructions for, for each class, for the instances not comprising that class, binning the data comprising each instance not of that class relative to template instance for that class, and for the binned representations of instances found in the previous step, enumerating the bins in order of hierarchies of increasing resolution, and within a resolution level, in the order in which the bins were determined, in order to form fingerprints for each instance.

13. The program storage device of claim 11, further comprising instructions for, for each fingerprint in each class, calculating a z-score for each feature in the fingerprint by subtracting the average associated with the class for the corresponding feature and then dividing that result by the standard deviation associated with the class for the corresponding feature, wherein the resulting values provide a set of fingerprints for each instance, the number of elements of that set being equal to the number of classes.

14. The program storage device of claim 12, further comprising instructions for, for each fingerprint in each class, calculating a z-score for each feature in the fingerprint by subtracting the average associated with the class for the corresponding feature and then dividing that result by the standard deviation associated with the class for the corresponding feature, wherein the resulting values provide a set of fingerprints for each instance, the number of elements of that set being equal to the number of classes.

15. The program storage device of claim 12, further comprising instructions for, for each instance, combining the set of fingerprints by concatenating the lists of elements in each fingerprint, thereby forming a single fingerprint for each instance which contains that instance'"'"'s z-score calculated relative to every class.

16. The program storage device of claim 6, further comprising instructions for forming a categorical fingerprint, the method comprising:

a. defining a many-to-one mapping of continuous valued numbers into a discrete set of values, said values being at least one member selected from the group consisting of integers and a discrete label, wherein the method of mapping is at least one mathematical transform selected from the group consisting of quantization, a transform based on a machine learning method, or any transform capable of a many-to-one mapping;

b. applying the mapping to each feature of the fingerprint; and

c. creating a list of the mapped features,

thereby forming a fingerprint consisting of categorical features.

17. The program storage device of claim 10, further comprising instructions for forming a categorical fingerprint, the method comprising:

a. defining a many-to-one mapping of continuous valued numbers into a discrete set of values, said values being at least one member selected from the group consisting of integers and a discrete label, wherein the method of mapping is at least one mathematical transform selected from the group consisting of quantization, a transform based on a machine learning method, or any transform capable of a many-to-one mapping;

b. applying the mapping to each feature of the fingerprint; and

c. creating a list of the mapped features,

thereby forming a fingerprint consisting of categorical features.

18. The program storage device of claim 16, further comprising instructions for forming a binary fingerprint, the method comprising:

a. specifying the number of non-redundant, discrete features that comprise a categorical fingerprint;

b. assigning a integer ordinal to each categorical feature;

c. creating a mapping of each categorical feature to a string of binary digits, the number of elements in the string being equal to the number of categorical features, by setting all digits in the string to zero excepting the element whose position in the string corresponds to the ordinal of the categorical feature, which ordinal-corresponding element being set to one;

d. applying the mapping described in the previous step to each feature of the categorical fingerprint; and

e. creating a list of the mapped features,

thereby forming a fingerprint consisting of binary features.

19. A program storage device readable by a machine, said device tangibly embodying at least one program of instructions executable by the machine to cause the machine to perform steps for a method of representing data at multiple resolutions, said method comprising:

a. providing a first data set;

b. representing said data in a multidimensional space;

c. dividing said multidimensional space into discrete data bins;

d. subdividing data from each bin into finer resolution bins;

e. determining the direction of maximum variance of data contained within at least one bin;

f. rotating the coordinates of the data space in the direction of maximum variance, wherein the first axis of the rotated coordinates is parallel to the direction of maximum variance, further wherein the rotation is based on the data from said first data set;

g. determining the median value of the first coordinate in the rotated coordinate system for the collection of data comprising the selected bin;

h. splitting the data comprising the selected bin into two bins at the next hierarchical resolution level, the first portion of the selected, split bin being comprised of events with a first coordinate value less than or equal to the median, the second portion of the selected, split bin being comprised of events with a first coordinate value greater than the median;

i. recording the rotation matrix and median value (split value) associated with the current, split bin to a storage device,

j. representing a second data set in a second multidimensional space;

k. dividing said second multidimensional space into a second set of discrete data bins;

l. subdividing data from each of said second bins into finer resolution bins;

m. rotating the coordinates of the second data space based on the corresponding rotation matrix from said first data set;

n. in a selected second bin, splitting the data comprising the second selected bin into two bins at the next hierarchical resolution level, the first portion of the second selected, split bin being comprised of events with a first coordinate value less than or equal to the median of the corresponding bin determined for said first data set in step g.), the second portion of the second selected, split bin being comprised of events with a first coordinate value greater than the median of the corresponding bin determined for said first data set in step g.); and

o. determining one-dimensional lists of numbers comprising fingerprints for a set of instances relative to the representation of a multidimensional data set processed by the binning procedure, the method comprising forming a template instance by combining the events from a set of instances into a single data set.

20. A computing environment providing a device readable by a machine, said device tangibly embodying at least one program of instructions executable by the machine to cause the machine to perform steps for a method of representing data at multiple resolutions, said method comprising:

a. providing a data set;

b. representing said data in a multidimensional space;

c. dividing said multidimensional space into discrete data bins;

d. subdividing data from each bin into finer resolution bins;

e. determining the direction of maximum variance of data contained within at least one bin;

f. rotating the coordinates of the data space in the direction of maximum variance, wherein the first axis of the rotated coordinates is parallel to the direction of maximum variance;

g. determining the median value of the first coordinate in the rotated coordinate system for the collection of data comprising the selected bin;

h. splitting the data comprising the selected bin into two bins at the next hierarchical resolution level, the first portion of the selected, split bin being comprised of events with a first coordinate value less than or equal to the median, the second portion of the selected, split bin being comprised of events with a first coordinate value greater than the median; and

i. recording the rotation matrix and median value (split value) associated with the current, split bin to a storage device.