Computer graphics processing and selective visual display system – Display driving control circuitry – Controlling the condition of display elements
Reexamination Certificate
1998-06-24
2001-10-16
Bayerl, Raymond J. (Department: 2173)
Computer graphics processing and selective visual display system
Display driving control circuitry
Controlling the condition of display elements
C345S215000
Reexamination Certificate
active
06304260
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data visualization. More particularly, the present invention relates to using a computer to generate and display views of hierarchically clustered data.
BACKGROUND OF THE INVENTION
A common problem in computerized data analysis is forming groups, or clusters, of similar items based on a number of variables describing the items. For example, in a business environment it is often important to form customer groups for precision marketing. The overall goal of clustering is to divide the data into a number of classes, using the variables that describe the data, such that each class contains members that are similar to each other and dissimilar to members of other classes. There are many known techniques for performing clustering. One of the most common techniques is called hierarchical clustering.
Hierarchical clustering does not require, as some other prior art techniques do, that the number of resulting clusters be pre-defined. Instead, the hierarchical clustering technique builds a binary tree in which the original data items are the leaves, and interior nodes represent clusters of items. Each interior node also stores a representation of a measure of the dissimilarity between the two sets of child clusters of the node. Once the binary tree is created, a user analyzing the data can cut the tree at a given level of dissimilarity to create clusterings with different numbers of groups without the need to re-run the clustering algorithm. This ability to cut the tree without the need to re-run the clustering algorithm is very important in the study of large data sets because it allows a user to run a potentially very slow algorithm on a large data set one time, and then examine the resulting structure in various ways without the need to re-run the algorithm and recreate the tree structure. Methods for performing hierarchical clustering are well known in the art and will therefore not be described in detail herein. Such methods are described in,
Cluster Analysis
, Everitt, B. S., 3d ed., Halsted Press, N.Y. (1993), which is incorporated by reference herein. The particular method used to perform the hierarchical clustering is not critical to the present invention.
Once the tree structure has been created using an appropriate hierarchical clustering method, the tree must be visualized, i.e., a representation of the tree must be generated and displayed on the computer screen for a user. One technique for visualizing the results of a hierarchical clustering algorithm is to simply generate and display a view of the tree structure. However, this technique becomes too cumbersome with even moderate sized data sets.
A better technique is to generate and display a tree-map, which is a technique for visualizing a tree that makes maximal use of screen space. The basic version takes a specified rectangular area and recursively subdivides it up based on the tree structure. The method looks at the first level of the tree and splits up the viewing area horizontally into n rectangles, where n is the number of children of the first node. Each rectangle is allocated an area proportional to the size of the subtree beneath each child node. The method then looks at the next level of the tree and for each node performs the same algorithm, except it recursively divides the area vertically. The algorithm continues doing this subdivision in alternating directions until either the maximum specified depth is reached or a leaf node is reached. In either case, the rectangular area for that node is then drawn with user-specified characteristics such as color, shading and labeling. The algorithm for generating a tree map is well known in the art and is described in,
Tree Visualization with Tree Maps
; a 2D Space-Filling Approach, Schniederman, ACM Transactions on Graphics, January 1992, which is incorporated herein by reference.
SUMMARY OF THE INVENTION
The present invention is an improved technique for generating and displaying views of hierarchically clustered data. Specifically, we have recognized that an improvement in generating tree maps can be realized by generating display groupings based on a measure of dissimilarity of data clusters rather than the prior art technique of cutting a tree at a given level without regard to dissimilarity.
In accordance with one embodiment of the invention, the nodes of a tree which are stored in the memory of a computer system are traversed and a display area is recursively split until nodes having a prescribed measure of dissimilarity are reached. This recursive splitting to a prescribed measure of dissimilarity produces a tree map which is a better visualization of the data clusters because the resulting groupings are more closely related to the similarity of the clusters. Advantageously, such a visualization conveys more useful information to a user analyzing the underlying data.
In accordance with another aspect of the invention, we have recognized that it is beneficial to symbolically display all data items in the tree, rather than to only display representations of accumulated groups of data items as taught by the prior art. This technique provides more useful information to a user analyzing the underlying data.
In accordance with another aspect of the invention, the tree map is recursively split along the longest axis of rectangles, rather than alternating between vertical and horizontal splits as previously done according to the prior art. Splitting along the longest axis of rectangles results in a tree map having rectangles which are more square, as opposed to the prior art technique which tends to result in long skinny triangles. Advantageously, the more square rectangles resulting from employing the invention make it easier for a user to visualize the underlying data.
In accordance with yet another aspect of the invention, when the level of dissimilarity is changed and a new tree map is generated, the data items remain in the same relative positions in the tree map. All that is changed is the display of groupings around the data items. This aspect of the invention provides for better comparisons of groups at different levels of dissimilarity.
REFERENCES:
patent: 5581797 (1996-12-01), Baker et al.
patent: 5821945 (1998-10-01), Yeo et al.
patent: 6057843 (2000-05-01), Van Overveld et al.
patent: WO 98 46998 A (1998-10-01), None
Jin et al (“Tennis Viewer: a browser for competition trees”, IEEE Computer Graphics and Applications, v17/4, Jul.-Aug. 1997, pp. 63-65).*
Turo et al (“Hierarchial Visualization with treemaps: Making sense of pro basketball data”, Proceedings of the CHI '94 conference companion on Human factors in computing systems, 1994, p 441).*
Johnson et al (“Tree-maps: a space-filling approach to the visualization of hierarchical information structures”, Visualization, 1991, Proceedings IEEE Conference, pp. 284-291).*
Shneiderman (“Tree visualization with tree-maps: 2-d space-filling approach”, ACM Trans. Graph. 11, 1, Jan. 1992, pp. 92-99).*
Shneiderman (“Beyond intelligent machines: just do it”, IEEE Software vol. 10 1, Jan. 1993, pp. 100-103).*
Asahi et al. (“Visual decision-making: Using treemaps for the Analytic Hierarchy Process”, ACM Conference companion on Human factors in computing systems 1995, pp. 405-406.*
B. Johnson et al., “Tree-Maps: A Space-Filling Approach To The Visualization of Hierarchical Information Structures”,Proceedings of the Annual Conference On Visualization, Los Alamitos, vol. Conf. 2, pp. 284-291.
R.D. Clark, “Optisim: An Extended Dissimilarity Selection Method For Finding Diverse Representative Subsets”, Journal of Chemical Information and Computer Sciences, vol. 37, 1997, pp. 1181-1188.
David Turo, Brian Johnson, Improving the Visualization of Hierarchies with Treemaps: Design Issues and Experimentation, 0-8186-2897-9/92, IEEE, 1992.
Stephen G. Eick, Graham J. Wills, High Interaction Graphics, European Journal of Operational Research 81 (1995) 445-459.
Bayerl Raymond J.
Lucent Technologies - Inc.
Luu Sy D.
LandOfFree
Method and apparatus for generating and displaying views of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating and displaying views of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating and displaying views of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2572535