Fast vector quantization with topology learning

• US 8,325,748 B2
• Filed: 09/13/2006
• Issued: 12/04/2012
• Est. Priority Date: 09/16/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Campos, Marcos M.
• Primary Examiner(s): Chung, Hoon J
• Assistant Examiner(s): Elliott, IV, Benjamin H
• Application Number:
  US11/519,781
• Publication Number:
  US 20070064627A1
• Time in Patent Office: 2,274 Days
• Field of Search: 370/411, 370/539, 370/541, 345/420, 382/240, 717/132, 717/133, 707/736, 707/737, 707/776
• US Class Current: 370/411
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts

Abstract

A new process called a vector approximation graph (VA-graph) leverages a tree based vector quantizer to quickly learn the topological structure of the data. It then uses the learned topology to enhance the performance of the vector quantizer. A method for analyzing data comprises receiving data, partitioning the data and generating a tree based on the partitions, learning a topology of a distribution of the data, and finding a best matching unit in the data using the learned topology.

Claims

1. A method for analyzing data comprising:

receiving data at a data processing system;

partitioning the data and generating a tree based on the partitions;

learning a topology of a distribution of the data using the generated tree to build a graph of the topology by linking a subtree based on a baseline graph and creating long-range links between nodes of the subtree wherein the long-range links are created by;

for each pair of nodes (u1, u2) connected by a link in the baseline graph and for each leaf s1 in the subtree rooted in u1, finding a closest leaf node s2 in the subtree rooted in u2;

creating a link between s1 and s2, if 1/dist(s1, s2) is greater than a smallest weight amongst links containing either s1 or s2; and

keeping the link with the smallest weight, if s2 was already linked to a node in the subtree rooted at u1; and

finding a best matching unit in the data using the learned topology.

2. The method of claim 1, wherein the data is partitioned by:

initializing a root node having a centroid equal to a mean of the data and having one leaf; and

recursively performing the steps of;

determining whether the number of leaves of a node is smaller than a desired codebook size,

if the number of leaves of a node is smaller than a desired codebook size, attempting to select an eligible leaf node having a largest cost measure value, wherein an eligible leaf node is a leaf node having at least a minimum number of assigned data vectors,

if an eligible leaf node is selected, splitting the eligible leaf node.

3. The method of claim 2, wherein the eligible leaf node is split by using a 2-means approach for computing centroids of two child nodes into which the eligible leaf node is split and for assigning data to the child nodes.

4. The method of claim 2, wherein the eligible leaf node is split by using a mean value of a component of the eligible leaf node having a largest variance to split the eligible leaf node using an axis parallel split.

5. The method of claim 2, wherein the cost measure value is determined using a mean quantization error associated with the eligible leaf node or using a number of input vectors assigned to the eligible leaf node.

6. The method of claim 1, wherein the topology of the distribution of the data is learned by:

creating a baseline graph of the tree.

7. The method of claim 6, wherein the baseline graph of the tree is created by:

identifying a level of quantization in a tree structure quantizer; and

applying Optimally Topology Preserving Maps to nodes quantized by the tree structure quantizer to construct a baseline graph.

8. The method of claim 7, wherein the level of quantization in a tree structure quantizer is identified by:

selecting all nodes in the tree for which C_j<

n and C_d(j)≧

n, wherein C_j is a number of inputs assigned to node j, d(j) is one index of two children of node j, and n is a user defined parameter.

9. The method of claim 1, wherein the subtree is linked based on the baseline graph by:

generating at least one random vector for each node in the baseline graph;

combining the generated random vectors for each node with centroid values of leaf nodes in the subtree to form a combined set;

finding and linking leaf nodes in the subtree for each row in the combined set; and

assigning a weight to each link.

10. The method of claim 9, wherein components of each random vector are between a minimum and a maximum of values of components of the leaf nodes in the subtree rooted at a respective baseline graph node.

11. The method of claim 9, wherein the weight assigned to each link is 1/dist(s1, s2), wherein dist(s1, s2) is a distance function.

12. The method of claim 11, wherein the distance function is a Euclidean metric.

13. A system for analyzing data comprising:

a processor operable to execute computer program instructions;

a memory operable to store computer program instructions executable by the processor; and

computer program instructions stored in the memory and executable to perform the steps of;

receiving data;

partitioning the data and generating a tree based on the partitions;

learning a topology of a distribution of the data using the generated tree to build a graph of the topology by linking a subtree based on a baseline graph and creating long-range links between nodes of the subtree wherein the long-range links are created by;

for each pair of nodes (u1, u2) connected by a link in the baseline graph and for each leaf s1 in the subtree rooted in u1, finding a closest leaf node s2 in the subtree rooted in u2;

creating a link between s1 and s2, if 1/dist(s1, s2) is greater than a smallest weight amongst links containing either s1 or s2; and

keeping the link with the smallest weight, if s2 was already linked to a node in the subtree rooted at u1; and

finding a best matching unit in the data using the learned topology.

14. The system of claim 13, wherein the data is partitioned by:

initializing a root node having a centroid equal to a mean of the data and having one leaf; and

recursively performing the steps of;

determining whether the number of leaves of a node is smaller than a desired codebook size,

if the number of leaves of a node is smaller than a desired codebook size, attempting to select an eligible leaf node having a largest cost measure value, wherein an eligible leaf node is a leaf node having at least a minimum number of assigned data vectors,

if an eligible leaf node is selected, splitting the eligible leaf node.

15. The system of claim 14, wherein the eligible leaf node is split by using a 2-means approach for computing centroids of two child nodes into which the eligible leaf node is split and for assigning data to the child nodes.

16. The system of claim 14, wherein the eligible leaf node is split by using a mean value of a component of the eligible leaf node having a largest variance to split the eligible leaf node using an axis parallel split.

17. The system of claim 13, wherein the cost measure value is determined using a mean quantization error associated with the eligible leaf node or using a number of input vectors assigned to the eligible leaf node.

18. The system of claim 13, wherein the topology of the distribution of the data is learned by:

creating a baseline graph of the tree.

19. The system of claim 18, wherein the baseline graph of the tree

is created by:

identifying a level of quantization in a tree structure quantizer; and

applying Optimally Topology Preserving Maps to nodes quantized by the tree structure quantizer to construct a baseline graph.

20. The system of claim 19, wherein the level of quantization in a tree structure quantizer is identified by:

selecting all nodes in the tree for which C_j<

n and C_d(j)≧

n, wherein C_j is a number of inputs assigned to node j, d(j) is one index of two children of node j, and n is a user defined parameter.

21. The system of claim 13, wherein the subtree is linked based on the baseline graph by:

generating at least one random vector for each node in the baseline graph;

combining the generated random vectors for each node with centroid values of leaf nodes in the subtree to form a combined set;

finding and linking leaf nodes in the subtree for each row in the combined set; and

assigning a weight to each link.

22. The system of claim 21, wherein components of each random vector are between a minimum and a maximum of values of components of the leaf nodes in the subtree rooted at a respective baseline graph node.

23. The system of claim 21, wherein the weight assigned to each link is 1/dist(s1, s2), wherein dist(s1, s2) is a distance function.

24. The system of claim 23, wherein the distance function is a Euclidean metric.

25. A computer program product for analyzing data comprising:

a non-transitory computer readable storage medium;

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of

receiving data;

partitioning the data and generating a tree based on the partitions;

learning a topology of a distribution of the data using the generated tree to build a graph of the topology by linking a subtree based on a baseline graph and creating long-range links between nodes of the subtree wherein the long-range links are created by;

for each pair of nodes (u1, u2) connected by a link in the baseline graph and for each leaf s1 in the subtree rooted in u1, finding a closest leaf node s2 in the subtree rooted in u2;

creating a link between s1 and s2, if 1/dist(s1, s2) is greater than a smallest weight amongst links containing either s1 or s2; and

keeping the link with the smallest weight, if s2 was already linked to a node in the subtree rooted at u1; and

finding a best matching unit in the data using the learned topology.

26. The computer program product of claim 25, wherein the data is partitioned by:

initializing a root node having a centroid equal to a mean of the data and having one leaf; and

recursively performing the steps of;

determining whether the number of leaves of a node is smaller than a desired codebook size,

if the number of leaves of a node is smaller than a desired codebook size, attempting to select an eligible leaf node having a largest cost measure value, wherein an eligible leaf node is a leaf node having at least a minimum number of assigned data vectors,

if an eligible leaf node is selected, splitting the eligible leaf node.

27. The computer program product of claim 26, wherein the eligible leaf node is split by using a 2-means approach for computing centroids of two child nodes into which the eligible leaf node is split and for assigning data to the child nodes.

28. The computer program product of claim 26, wherein the eligible leaf node is split by using a mean value of a component of the eligible leaf node having a largest variance to split the eligible leaf node using an axis parallel split.

29. The computer program product of claim 26, wherein the cost measure value is determined using a mean quantization error associated with the eligible leaf node or using a number of input vectors assigned to the eligible leaf node.

30. The computer program product of claim 25, wherein the topology of the distribution of the data is learned by:

creating a baseline graph of the tree.

31. The computer program product of claim 30, wherein the baseline graph of the tree is created by:

identifying a level of quantization in a tree structure quantizer; and

applying Optimally Topology Preserving Maps to nodes quantized by the tree structure quantizer to construct a baseline graph.

32. The computer program product of claim 31, wherein the level of quantization in a tree structure quantizer is identified by:

selecting all nodes in the tree for which C_j<

n and C_d(j)≧

n, wherein C_j is a number of inputs assigned to node j, d(j) is one index of two children of node j, and n is a user defined parameter.

33. The computer program product of claim 25, wherein the subtree is linked based on the baseline graph by:

generating at least one random vector for each node in the baseline graph;

combining the generated random vectors for each node with centroid values of leaf nodes in the subtree to form a combined set;

finding and linking leaf nodes in the subtree for each row in the combined set; and

assigning a weight to each link.

34. The computer program product of claim 33, wherein components of each random vector are between a minimum and a maximum of values of components of the leaf nodes in the subtree rooted at a respective baseline graph node.

35. The computer program product of claim 33, wherein the weight assigned to each link is 1/dist(s1, s2), wherein dist(s1, s2) is a distance function.

36. The computer program product of claim 35, wherein the distance function is a Euclidean metric.