Method and system for visualization of clusters and classifications

• US 6,216,134 B1
• Filed: 06/25/1998
• Issued: 04/10/2001
• Est. Priority Date: 06/25/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meek, Christopher A., Chickering, David Maxwell, Heckerman, David E., Fayyad, Usama M.
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/104,751
• Time in Patent Office: 1,020 Days
• Field of Search: 707/2, 707/3, 707/5, 707/10, 707/104, 707/4, 707/100, 707/103, 707/200, 707/522, 381/41, 705/23, 705/5, 705/10, 705/26, 706/2, 704/9, 704/103, 704/522, 701/200, 701/202, 701/206, 701/208, 345/347, 455/2, 455/4.2, 382/225, 382/229, 711/157, 711/173, 713/200, 709/201, 709/219
• US Class Current: 707/749
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor
• CPC Class Codes: G06Q 30/0643 Graphical representation of items or shoppers
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system that provides for the graphic visualization of the categories of a collection of records. The graphic visualization is referred to as “category graph.” The system optionally displays the category graph as a “similarity graph” or a “hierarchical map.” When displaying a category graph, the system displays a graphic representation of each category. The system displays the category graph as a similarity graph or a hierarchical map in a way that visually illustrates the similarity between categories. The display of a category graph allows a data analyst to better understand the similarity and dissimilarity between categories. A similarity graph includes a node for each category and an arc connecting nodes representing categories whose similarity is above a threshold. A hierarchical map is a tree structure that includes a node for each base category along with nodes representing combinations of similar categories.

Claims

1. A method in a computer system for displaying a representation of categories of data, the method comprising:

for each category, determining a similarity of that category to every other category so that a similarity is determined for each pair of categories;

displaying an indication of each category; and

for each pair of categories, displaying an indication of the determined similarity of the pair of categories, wherein the displayed indication is an arc connecting the displayed indication of each category in the pair of categories.

2. The method of claim 1 wherein the establishing of a similarity threshold includes receiving from a user an indication of the similarity threshold.

3. The method of claim 2 including displaying a slider so that the user can indicate the similarity threshold.

4. The method of claim 3 wherein the slider is displayed horizontally.

5. The method of claim 3 wherein the slider is displayed vertically.

6. The method of claim 2 wherein when the user establishes a new similarity threshold, adjusting the displayed indications of determined similarity to reflect the new similarity threshold.

7. A method in a computer system for displaying a representation of categories of data, the method comprising:

for each category, determining a similarity of that category to every other category so that a similarity is determined for each pair of categories;

displaying an indication of each category;

for each pair of categories, displaying an indication of the determined similarity of the pair of categories;

establishing a similarity threshold; and

displaying the indication of the determined similarity for only those pairs of categories whose determined similarity is above the established similarity threshold.

8. A method in a computer system for displaying a representation of categories of data, the method comprising:

for each category, determining a similarity of that category to every other category so that a similarity is determined for each pair of categories;

displaying an indication of each category; and

for each pair of categories, displaying an indication of the determined similarity of the pair of categories, wherein the displayed indication is an arc and thickness of the arc indicates the determined similarity between the pair of categories.

9. A method in a computer system for displaying a representation of categories of data, the method comprising:

for each category, determining a similarity of that category to every other category so that a similarity is determined for each pair of categories;

displaying an indication of each category;

for each pair of categories, displaying an indication of the determined similarity of the pair of categories;

receiving a selection of a displayed indication of a category; and

in response to the selection, displaying information relating to the category;

wherein the data includes attributes and the information relating to the selected category identifies attributes that discriminate the selected category from another category.

10. The method of claim 9 wherein the identified attributes are ordered according to their ability to discriminate.

11. The method of claim 9 wherein a discrimination metric is given by the following equation:

$\mathrm{discrim}(x_i<br><br><br><br>G_1,G_2)=p(\text{\hspace{1em}<br><br>}<br><br>x_i<br><br><br><br>G_1)-p<br><br>\left(x_i<br><br><br><br>G_2)\right)<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{p<br><br>\left(x_i<br><br><br><br>G_1\right)}{p<br><br>\left(x_i<br><br><br><br>G_2\right)}+(p(x_i<br><br><br><br>G_2)-p<br><br>\left(x_i<br><br><br><br>G_1)\right)<br><br>\log <br><br>\frac{\text{\hspace{1em}<br><br>}<br><br>1-p<br><br>\left(x_i<br><br><br><br>G_1\right)}{1-p<br><br>\left(x_i<br><br><br><br>G_2\right)}$

where x_i represents a value of attribute i and where p(x_i|G) represents the conditional probability that a record with an attribute value x_i given that the record is in category G.

12. The method of claim 11 wherein $p(x_i$



G)=∑

hj

ε

G

p

(hj)

∏

i

 

 



 



p(xi



hj)∑

hj

ε

G

p

(hj)

where h_j represents category j, where p(h_j) represents the probability that a record is in h_j, and where p(x_i|h_j) is the conditional probability that a record has the value X_i for attribute i is given that the record is in h_j.

13. A method in a computer system for displaying a representation of categories of data, the method comprising:

for each category, determining a similarity of that category to every other category so that a similarity is determined for each pair of categories;

displaying an indication of each category;

for each pair of categories, displaying an indication of the determined similarity of the pair of categories;

receiving an indication to de-emphasize a category; and

in response to the indication to de-emphasize a category, de-emphasizing the displayed indication of the category.

14. The method of claim 13 including:

in response to receiving the indication to de-emphasize a category, removing the displayed indication of the de-emphasized category.

15. The method of claim 13 wherein the de-emphasizing is dimming of the displayed indication of the de-emphasized category.

16. The method of claim 13 wherein the de-emphasizing is hiding of the displayed indication of the category.

17. A method in a computer system for displaying a representation of categories of data, the method comprising:

for each category, determining a similarity of that category to every other category so that a similarity is determined for each pair of categories;

displaying an indication of each category;

for each pair of categories, displaying an indication of the determined similarity of the pair of categories;

receiving an indication to split a combined category; and

in response to the indication to split a combined category, displaying an indication of a pair of categories for the combined category.

18. The method of claim 17 including:

displaying a slider and wherein movement of the displayed slider indicates to split a combined category.

19. The method of claim 17 wherein the displaying an indication of a pair of categories includes displaying an animation of splitting the indication of the combined category into the pair of indications of categories.

20. The method of claim 17 wherein the category to be split is the combined category that was last combined.

21. The method of claim 17 including:

displaying a control and wherein selection of the control indicates to split categories.

22. A method in a computer system for displaying a representation of categories of data, the method comprising:

receiving a hierarchical organization of the categories, the categories including a root category and leaf categories, each category except the leaf categories being a combined category;

displaying an indication of each category in the hierarchical organization;

receiving an indication to de-emphasize a specific category; and

in response to the indication to de-emphasize a category, de-emphasizing the displayed indications of categories in a sub-tree of which the specific category is a root.

23. The method of claim 22 including wherein the de-emphasizing is removing of the displayed indications.

24. The method of claim 22 wherein the de-emphasizing is dimming of the displayed indications.

25. The method of claim 22 wherein the de-emphasizing is hiding of the displayed indications.

26. A method in a computer system for displaying a representation of categories of data, the method comprising:

receiving a hierarchical organization of the categories, the categories including a root category and leaf categories, each category except the leaf categories being a combined category;

displaying an indication of each category in the hierarchical organization;

receiving an indication to de-emphasize a specific category; and

in response to the indication to de-emphasize a category, removing all displayed indications of categories in a sub-tree of which the specific category is a root, excluding the displayed indication of the category corresponding to the root of the sub-tree.

27. A method in a computer system for displaying a representation of categories of data, the method comprising:

receiving a hierarchical organization of the categories, the categories including a root category and leaf categories, each category except the leaf categories being a combined category;

displaying an indication of each category in the hierarchical organization;

receiving a selection of a displayed indication of a category; and

in response to the selection, displaying information relating to the selected category.

28. The method of claim 27 wherein the information is comparison information with a category that is a parent of the selected category.

29. The method of claim 27 wherein the information is comparison information with a category that is a sibling of the selected category.

30. The method of claim 27 wherein the information is comparison information with all categories other than the selected category.

31. The method of claim 27 wherein the information is comparison information with child categories of the selected category.

32. The method of claim 27 wherein the information is weights of evidence information.

33. The method of claim 27 wherein the data includes attributes and the information relating to the selected category identifies attributes that discriminate the selected category from an other category.

34. The method of claim 33 wherein the identified attributes are ordered according to their ability to discriminate.

35. The method of claim 34 wherein a discrimination metric, reflecting the identified attributes, is given by the following equation:

$\mathrm{discrim}(x_i<br><br><br><br>G_1,G_2)=p(\text{\hspace{1em}<br><br>}<br><br>x_i<br><br><br><br>G_1)-p<br><br>\left(x_i<br><br><br><br>G_2)\right)<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{p<br><br>\left(x_i<br><br><br><br>G_1\right)}{p<br><br>\left(x_i<br><br><br><br>G_2\right)}+(p(x_i<br><br><br><br>G_2)-p<br><br>\left(x_i<br><br><br><br>G_1)\right)<br><br>\log <br><br>\frac{\text{\hspace{1em}<br><br>}<br><br>1-p<br><br>\left(x_i<br><br><br><br>G_1\right)}{1-p<br><br>\left(x_i<br><br><br><br>G_2\right)}$

where x_i represents a value of attribute i and where p(x_i|G) represents the conditional probability that a record with an attribute value x_i given that the record is in category G.

36. The method of claim 35 wherein $p(x_i$



G)=∑

hj

ε

G

p

(hj)

∏

i

 

 



 



p(xi



hj)∑

hj

ε

G

p

(hj)

where h_j represents category j, where p(h_j) represents the probability that a record is in h_j, and where p(x_i|h_j) is the conditional probability that a record has the value X_i for attribute i is given that the record is in h_j.

37. The method of claim 27 wherein the data includes attributes and wherein the information relating to the selected category identifies attributes are characteristic of the selected category.

38. The method of claim 27 wherein the information relating to the selected category is indicates the homogeneity of the category.

39. The method of claim 27 wherein a homogeneity is given by the following equation:

$\mathrm{hom}<br><br>\left(G\right)=\underset{\mathrm{users}}{\sum <br><br>}<br><br>p(G<br><br><br><br>x_1,\mathrm{\dots <br><br>},x_m)<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>p(x_1,\mathrm{\dots <br><br>},x_m<br><br><br><br>G)$

where G represents a category or combined category, where p(G|x₁, . . . ,x_m) represents the probability that category G contains the record with attribute values x₁, . . . ,x_m, and where p(x₁, . . . ,x_m|G) represents the conditional probability that a record has attribute values x₁, . . . ,x_m given that it is in category G.

40. The method of claim 27 wherein the displayed information relates to the similarity of a sub-categories of a combined category.

41. A method in a computer system for displaying a representation of categories of data, the method comprising:

receiving a hierarchical organization of the categories, the categories including a root category and leaf categories, each category except the leaf categories being a combined category; and

displaying an indication of each category in the hierarchical organization;

wherein the displayed indication of each category includes an indication of the number of records in said each category.

42. The method of claim 41 wherein the indication of the number of records is shading of a portion of the displayed indication of the category in proportion to the number of records in the category to total number of records in all categories.