Systems and methods for using continuous optimization for ordering categorical data sets

• US 20020161736A1
• Filed: 03/19/2001
• Published: 10/31/2002
• Est. Priority Date: 03/19/2001
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Beygelzimer, Alina, Ma, Sheng, Hellerstein, Joseph L., Perng, Chang-Shing
• Granted Patent: US 6,615,211 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Techniques for ordering categorical attributes so as to better visualize data are provided. In accordance with one embodiment of the invention, an ordering algorithm comprises the steps of: (a) translating the discrete ordering problem to a continuous optimization problem; (b) solving the continuous optimization problem; and (c) mapping an optimal continuous solution to the closest discrete solution.

Claims

1. A computer-based method of ordering categorical values of one or more attributes associated with a data set, the method comprising the steps of:

obtaining the categorical values of the one or more attributes associated with the data set;

forming a task of ordering the categorical values of the one or more attributes associated with the data set as a continuous optimization ordering problem;

computing at least one continuous ordering solution to the continuous optimization ordering problem; and

making at least a portion of the computed continuous ordering solution available for use in accordance with a data visualization system.

2. The method of claim 1, further comprising the step of mapping the computed continuous ordering solution from a continuous space to a discrete space.

3. The method of claim 1, wherein the step of forming a task to order the categorical values as a continuous optimization ordering problem comprises the step of computing a similarity matrix based on the categorical values of the one or more attributes.

4. The method of claim 3, wherein the similarity matrix is based on one or more multi-set operations.

5. The method of claim 4, wherein the one or more multi-set operations comprise computing two types of similarity measurements, a first type being a similarity measure computed between two categorical values from the same attribute, and a second type being a similarity measure computed between two categorical values from different attributes.

6. The method of claim 3, wherein the step of forming a task to order the categorical values as a continuous optimization ordering problem further comprises the step of computing a Laplace matrix from the similarity matrix.

7. The method of claim 6, wherein the step of computing at least one continuous ordering solution to the continuous optimization ordering problem comprises the step of finding the smallest positive eigenvalue of the Laplace matrix.

8. The method of claim 7, wherein the step of computing at least one continuous ordering solution to the continuous optimization ordering problem further comprises the step of obtaining a corresponding optimal eigenvector from the smallest positive eigenvalue of the Laplace matrix.

9. The method of claim 8, further comprising the step of, prior to making the solution available for use in accordance with the data visualization system, ordering the categorical values in accordance with corresponding values associated with the optimal eigenvector.

10. The method of claim 1, wherein the categorical values relate to multiple attributes and further comprising the step of, prior to forming a task to order the categorical values as a continuous optimization ordering problem, mapping the categorical values relating to the multiple attributes into a set of objects such that the forming and computing steps are performed in association with the set of objects.

11. The method of claim 1, wherein the obtaining, forming and computing steps are performed in association with a preprocessing operation of the data visualization system.

12. The method of claim 1, wherein the obtaining, forming and computing steps are performed in association with a data management module of the data visualization system.

13. The method of claim 1, wherein the obtaining, forming and computing steps are performed in association with a data viewer module of the data visualization system.

16. The apparatus of claim 15, wherein the processor is further operative to map the computed continuous ordering solution from a continuous space to a discrete space.

17. The apparatus of claim 15, wherein forming a task to order the categorical values as a continuous optimization ordering problem comprises computing a similarity matrix based on the categorical values of the one or more attributes.

18. The apparatus of claim 17, wherein the similarity matrix is based on one or more multi-set operations.

19. The apparatus of claim 18, wherein the one or more multi-set operations comprise computing two types of similarity measurements, a first type being a similarity measure computed between two categorical values from the same attribute, and a second type being a similarity measure computed between two categorical values from different attributes.

20. The apparatus of claim 17, wherein forming a task to order the categorical values as a continuous optimization ordering problem further comprises computing a Laplace matrix from the similarity matrix.

21. The apparatus of claim 20, wherein computing at least one continuous ordering solution to the continuous optimization ordering problem comprises finding the smallest positive eigenvalue of the Laplace matrix.

22. The apparatus of claim 21, wherein computing at least one continuous ordering solution to the continuous optimization ordering problem further comprises obtaining a corresponding optimal eigenvector from the smallest positive eigenvalue of the Laplace matrix.

23. The apparatus of claim 22, wherein the processor is further operative to, prior to making the solution available for use in accordance with the data visualization system, order the categorical values in accordance with corresponding values associated with the optimal eigenvector.

24. The apparatus of claim 15, wherein the categorical values relate to multiple attributes and wherein the processor is further operative to, prior to forming a task to order the categorical values as a continuous optimization ordering problem, map the categorical values relating to the multiple attributes into a set of objects such that the forming and computing steps are performed in association with the set of objects.

25. The apparatus of claim 15, wherein the processor performs the obtaining, forming and computing steps in association with a preprocessing operation of the data visualization system.

26. The apparatus of claim 15, wherein the processor performs the obtaining, forming and computing steps in association with a data management module of the data visualization system.

27. The apparatus of claim 15, wherein the processor performs the obtaining, forming and computing steps in association with a data viewer module of the data visualization system.

14. A computer-based method of ordering categorical values of one or more attributes associated with a data set, the method comprising the steps of:

obtaining the categorical values of the one or more attributes associated with the data set;

modeling the categorical values as an original graph structure with vertices being the categorical values to be ordered and the weight of an edge representing the similarity of connected vertices;

approximating the original graph structure by a hierarchical sequence of one or more coarser graph structures, wherein vertices that have a similarly local structure are merged into a vertex in a coarser graph structure;

ordering the coarsest graph structure in accordance with a continuous optimization ordering operation;

propagating the ordering of the coarsest graph structure back through to the original graph structure; and

making at least a portion of the propagated ordering associated with the original graph structure available for use in accordance with a data visualization system.

15. Apparatus for ordering categorical values of one or more attributes associated with a data set, the apparatus comprising:

at least one processor operative to;

(i) obtain the categorical values of the one or more attributes associated with the data set;

(ii) form a task to order the categorical values of the one or more attributes associated with the data set as a continuous optimization ordering problem;

(iii) compute at least one continuous ordering solution to the continuous optimization ordering problem; and

(iv) make at least a portion of the computed continuous ordering solution available for use in accordance with a data visualization system.

28. Apparatus for ordering categorical values of one or more attributes associated with a data set, the apparatus comprising:

at least one processor operative to;

(i) obtain the categorical values of the one or more attributes associated with the data set;

(ii) model the categorical values as an original graph structure with vertices being the categorical values to be ordered and the weight of an edge representing the similarity of connected vertices;

(iii) approximate the original graph structure by a hierarchical sequence of one or more coarser graph structures, wherein vertices that have a similarly local structure are merged into a vertex in a coarser graph structure;

(iv) order the coarsest graph structure in accordance with a continuous optimization ordering operation;

(v) propagate the ordering of the coarsest graph structure back through to the original graph structure; and

(vi) make at least a portion of the propagated ordering associated with the original graph structure available for use in accordance with a data visualization system.

29. An article of manufacture for ordering categorical values of one or more attributes associated with a data set, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining the categorical values of the one or more attributes associated with the data set;

forming a task to order the categorical values of the one or more attributes associated with the data set as a continuous optimization ordering problem;

computing at least one continuous ordering solution to the continuous optimization ordering problem; and

making at least a portion of the computed continuous ordering solution available for use in accordance with a data visualization system.

30. An article of manufacture for ordering categorical values of one or more attributes associated with a data set, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining the categorical values of the one or more attributes associated with the data set;

modeling the categorical values as an original graph structure with vertices being the categorical values to be ordered and the weight of an edge representing the similarity of connected vertices;

approximating the original graph structure by a hierarchical sequence of one or more coarser graph structures, wherein vertices that have a similarly local structure are merged into a vertex in a coarser graph structure;

ordering the coarsest graph structure in accordance with a continuous optimization ordering operation;

propagating the ordering of the coarsest graph structure back through to the original graph structure; and

making at least a portion of the propagated ordering associated with the original graph structure available for use in accordance with a data visualization system.