Apparatus and accompanying methods for visualizing clusters of data and hierarchical cluster classifications

• US 7,333,998 B2
• Filed: 03/24/2004
• Issued: 02/19/2008
• Est. Priority Date: 06/25/1998
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bradley, Paul S., Chickering, David M., Meek, Christopher A., Heckerman, David E.
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US10/808,064
• Publication Number:
  US 20040181554A1
• Time in Patent Office: 1,427 Days
• Field of Search: 707/3, 707/4, 707/5, 707/10, 707/103.R, 707/104.1, 707/6, 707/7, 707/101, 707/102, 701/200, 701/202, 701/206, 701/208, 704/9, 704/103, 704/522, 704/202, 704/206, 705/5, 705/10, 705/23, 706/2, 709/201, 709/203, 709/218, 709/219, 711/157, 711/173, 713/200, 345/347
• US Class Current: 1/1
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor
• CPC Class Codes: G06Q 30/0641 Shopping interfaces
• 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/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system that incorporates an interactive graphical user interface for visualizing clusters (categories) and segments (summarized clusters) of data. Specifically, the system automatically categorizes incoming case data into clusters, summarizes those clusters into segments, determines similarity measures for the segments, scores the selected segments through the similarity measures, and then forms and visually depicts hierarchical organizations of those selected clusters. The system also automatically and dynamically reduces, as necessary, a depth of the hierarchical organization, through elimination of unnecessary hierarchical levels and inter-nodal links, based on similarity measures of segments or segment groups. Attribute/value data that tends to meaningfully characterize each segment is also scored, rank ordered based on normalized scores, and then graphically displayed. The system permits a user to browse through the hierarchy, and, to readily comprehend segment inter-relationships, selectively expand and contract the displayed hierarchy, as desired, as well as to compare two selected segments or segment groups together and graphically display the results of that comparison. An alternative discriminant-based cluster scoring technique is also presented.

Claims

1. A computer-implemented system for automatically categorizing unknown incoming data and a category visualization (CV) system that displays a graphic representation of each category as a hierarchical map, comprising:

a node corresponding to each base category;

nodes corresponding to combinations of similar categories;

a leaf node corresponding to a base category, the leaf node is positioned as a cluster of nodes at a lowest level of the hierarchy wherein combinations of similar categories are positioned on top of the leaf node, forming successively higher levels of the hierarchy;

a root node corresponding to a category that contains all records in a collection, the root node forms top of the hierarchy;

a non-leaf node corresponding to each combined category, wherein similar base categories are combined into a combined category;

wherein each non-leaf node has two arcs that connect the non-leaf node to two nodes corresponding to sub-categories of the combined category; and

wherein if a node is selected, the system displays additional information about corresponding category, the additional information is at least one of number of records in the category or characteristic attributes of the category, and

wherein if an arc is selected, the system displays information relating to categories connected by the arc, such as similarity value for the connected categories.

2. The system of claim 1, wherein the base category is a category identified by a categorization process (classification and clustering).

3. The system of claim 1, wherein the combined category is assigned the records of two or more base categories.

4. The system of claim 1, wherein the additional information further comprises characteristic and discriminating information such as attribute-value discrimination, attribute-value discrimination refers to how well the value of an attribute distinguishes the records of one category from the records of another category.

5. The system of claim 4, wherein the attribute-value discrimination is determined by employing the following equation:

$\mathrm{discrim}<br><br>\left(x_i|G_1,G_2\right)=\left(p<br><br>\left(x_i|G_1\right)-p<br><br>\left(x_i|G_2\right)\right)<br><br>\log <br><br>\frac{p<br><br>\left(x_i|G_1\right)}{p<br><br>\left(x_i|G_2\right)}+\left(p<br><br>\left(x_i|G_2\right)-p<br><br>\left(x_i|G_1\right)\right)<br><br>\log <br><br>\frac{1-p<br><br>\left(x_i|G_1\right)}{1-p<br><br>\left(x_i|G_2\right)}$

where discrim(x_i|G₁,G₂) is the measurement of how well the value of an attribute distinguishes the records of one combined category from the records of another combined category,

G₁ is the first combined category,

G₂ is the second combined category,

x_i is the records in one of the combined categories,

p (x_i|G₁) is the probability that a record containing specific attributes is in combined category G₁, and

p (x_i|G₂) is the probability that a record containing specific attributes is in combined category Gx₁|G₁.

6. The system of claim 1, wherein similarity value refers to a rating of the differences between attribute values of records in one category and attribute values of records in another category, a high value for similarity indicates that there is little difference between the records in the two categories.

7. The system of claim 6, wherein the similarity value for a pair of base categories is determined by employing the following equation:

$\mathrm{dist}<br><br>\left(h_1,h_2\right)=\underset{x_1,{\mathrm{\dots <br><br>x}}_m}{\sum <br><br>}<br><br>\left(p<br><br>\left(x_1,\mathrm{\dots <br><br>}<br><br>,x_m|h_1\right)-p<br><br>\left(x_1,\mathrm{\dots <br><br>}<br><br>,x_m\right)\right)<br><br>\log <br><br>\frac{p<br><br>\left(x_1,\mathrm{\dots <br><br>}<br><br>,x_m|h_1\right)}{p<br><br>\left(x_1,\mathrm{\dots <br><br>}<br><br>,x_m|h_2\right)}$

where dist(h₁, h₂) is the distance and similarity between two categories,

X₁, . . . , X_m is the attribute values,

h₁, h₂ is a count of a total number of records in categories 1 and 2,

p(x₁X_m|h₁) is a conditional probability that a record has attribute values x₁, . . . X_m given that it is a record from category 1, and

p(x₁X_m|h₂) is a conditional probability that a record has attribute values x₁, . . . X_m given that it is a record from category 2.

8. The system of claim 6, wherein the similarity for a pair of base categories is determined by employing the following equation:

$\mathrm{dist}<br><br>\left(h_1,h_2\right)=\underset{i}{\sum <br><br>}<br><br>\underset{x_i}{\sum <br><br>}<br><br>\left(p<br><br>\left(x_i|h_1\right)-p<br><br>\left(x_i|h_2\right)\right)<br><br>\log <br><br>\frac{p<br><br>\left(x_i|h_1\right)}{p<br><br>\left(x_i|h_2\right)}$

where dist(h₁,h₂) is the distance and similarity between two categories,

x_i is the attribute values,

h₁,h₂ is a count of a total number of records in categories 1 and 2,

x_i|h₁) is a conditional probability that a record has attribute values x_i given that it is a record from category 1, and

x_i|h₂) is a conditional probability that a record has attribute values x1 given that it is a record from category 2.

9. The system of claim 6, wherein the similarity for two combined categories is determined by employing the following equation:

$\mathrm{dist}<br><br>\left(G_1,G_2\right)=\underset{h_j\in <br><br>G_1,h_k\in <br><br>G_2}{\sum <br><br>}<br><br>(p<br><br>\left(h_j\right)<br><br>p<br><br>\left(h_k\right)<br><br>\mathrm{dist}<br><br>\left(h_j\right)<br><br>p<br><br>\left(h_j,h_k\right)$

where dist(G₁,G₂) is the distance and similarity between two combined categories,

G₁ is the first combined category,

G₂ is the second combined category,

h_j,h_k is a count of a total number of records in combined categories 1 and 2, and

p(h_j)p(h_k) is a probability that a record is in each of the combined categories.

10. The system of claim 6, wherein the similarity for two combined categories is determined by employing the following equation:

dist(G₁,G₂)=min{dist(h_j)(h_k)|h_j∈

G₁,h_k∈

G₂}

where dist(G₁,G₂) is the minimum distance between two combined categories,

G₁ is the first combined category,

G₂ is the second combined category, and

h₁,h_k is a count of a total number of records in combined categories 1 and 2.

11. The system of claim 6, wherein the similarity for two combined categories is determined by employing the following equation:

dist(G₁,G₂)=max{dist(h_j)(h_k)|h_j∈

G₁,h_k∈

G₂}

where dist(G₁,G₂) is the maximum distance between two combined categories,

G₁ is the first combined category,

G₂ is the second combined category, and

h₁, h_k is a count of a total number of records in combined categories 1 and 2.

12. The system of claim 1, wherein the graphic representation of each category is displayed as a decision tree, further comprising:

nodes that correspond to each attribute of the corresponding base categories; and

arcs that correspond to values of that attribute;

wherein each node, except the root node, represents a setting of attribute values as indicated by arcs in a path from a first node to the root node.

13. The system of claim 12, wherein the selection of a node, results in display of a probability for each category that a record in the category will have attribute settings that are represented by the path.

14. A computer-readable storage medium containing a plurality of categorized data records and a computer-implemented method of calculating and displaying a graphic representation of various characteristics and discriminating information for each category, comprising:

providing nodes that represent each base category;

providing nodes that represent combined categories, wherein combinations of similar categories are grouped together to form the combined categories;

utilizing a leaf node to form the bottom of the graphic representation;

utilizing a root node to form the top of the graphic representation

connecting nodes representing sub-categories of a combined category via arcs;

combining the two base categories that are the most similar into a combined category;

repeating process of combining similar categories until one combined category represents all records in a collection; and

allowing a node to be selected, wherein the system displays additional information about corresponding category, the additional information is at least one of number of records in the category or characteristic attributes of the category, and allowing an arc to be selected,

wherein the system displays information relating to categories connected by the arc, such as similarity value for the connected categories.

15. The system of claim 14, further comprising de-emphasizing specific nodes and focusing on specific non-de-emphasized nodes.