Three-dimensional display of document set

• US 6,584,220 B2
• Filed: 09/26/2001
• Issued: 06/24/2003
• Est. Priority Date: 08/12/1996
• Status: Expired due to Fees

• Current Assignee: Battelle Memorial Institute
• Original Assignee: Battelle Memorial Institute
• Inventors: Schur, Anne, Thomas, James J., Pottier, Marc C., Lantrip, David B., Wise, James A., Pennock, Kelly A.
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): Dang, Duy M.
• Application Number:
  US09/962,213
• Publication Number:
  US 20020031254A1
• Time in Patent Office: 636 Days
• Field of Search: 382/305, 382/306, 382/307, 382/309, 382/185, 382/209, 382/225, 382/181, 382/159, 382/170, 382/224, 382/228, 707/10, 707/5, 707/2, 707/6, 707/100, 707/532
• US Class Current: 382/154
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method for spatializing text content for enhanced visual browsing and analysis. The invention is applied to large text document corpora such as digital libraries, regulations and procedures, archived reports, and the like. The text content from these sources may be transformed to a spatial representation that preserves informational characteristics from the documents. The three-dimensional representation may then be visually browsed and analyzed in ways that avoid language processing and that reduce the analysts'"'"' effort.

Claims

1. A method for presenting information by relative relationships of content and context of a plurality of documents, wherein the relative relationships are presented in a three-dimensional landscape with the relative size and height of a peak in the landscape representing the relative significance of a relationship of a topic attribute and each one of the documents, comprising the steps of:

(a) representing each document as a high dimensional vector;

(b) producing a partition set on the plurality of documents, said partition set resulting in a cluster centroid for each of the documents; and

(c) projecting each said high dimensional vector and at least one said cluster centroid into a 2-dimensional representation.

2. The method of claim 1, further comprising the steps of:

(d) producing a coordinate pair for each document; and

(e) displaying coordinate pairs for each document in a scatter plot yielding a Galaxies two-dimensional visualization.

3. The method of claim 2, further comprising the step of:

(f) producing a three-dimensional representation of said coordinate pairs, said three-dimensional representation resulting in a thematic landscape.

4. The method of claim 3, wherein step (f) comprises the steps of:

(1) receiving an n-dimensional context vector for each document from a text engine;

(2) clustering each document in n-dimensional space, thereby producing a cluster for each document; and

(3) receiving from a text engine, for said cluster, associated gisting terms or topics.

5. The method of claim 1, further comprising the step of:

(d) initially inputting each of the documents into a text engine.

6. The method of claim 1, wherein stop (b) comprises the step of creating a cluster centroid by grouping said high dimensionality vectors for a plurality of documents in a high dimensional space.

7. The method of claim 1, wherein step (b) comprises the step of applying a clustering algorithm with primary emphasis on k-means and complete linkage hierarchical clustering to create a cluster centroid.

8. The method of claim 7, wherein said step of creating said cluster centroid is known as Fast Divisive Clustering and comprises the steps of:

(i) selecting a number of seeds;

(ii) placing said seeds in hyperspace by sampling regions to ensure a specified distribution of seeds;

(iii) identifying non-overlapping hyperspheres for each cluster and assigning each document to said each cluster based on which hypersphere said document is located;

(iv) calculating a centroid coordinate, representing the center of the mass for each cluster; and

(v) repeating steps (iii) and (iv) until centroid movement is less than a specified threshold.

9. The method of claim 1, wherein step (c) comprises, for small data sets, the steps of:

(1) applying a Multi-dimensional Scaling Algorithm to cluster centroid coordinates in hyperspace;

(2) producing a vector for each document with distance measures from said document to each cluster centroid; and

(3) constructing an operator matrix and multiplying said matrix by said vector to produce two-dimensional coordinates for said each document.

10. The method of claim 1, wherein step (c) comprises, for large data sets, the steps of:

(1) applying an Anchored Least Stress Algorithm to cluster centroid coordinates in hyperspace;

(2) producing a vector for each document with distance measures from said document to each cluster centroid; and

(3) constructing an operator matrix and multiplying said matrix by said vector to produce two-dimensional coordinates for said each document.

11. A method for representing human comprehensible information in a low-dimensionality space based on a high dimensionality analysis thereof, the information comprising sets of semantic information, comprising the steps of:

(a) representing the sets of semantic information as a vector in a high-dimensional information space;

(b) segmenting the information space into a plurality or bounded continuous sub-spaces, each having a centroid;

(c) projecting the segmented bounded continuous subspaces of the high-dimensional information space onto a low dimensional space, in a manner sensitive to a relation of each set of semantic information to each centroid.

12. The method of claim 11, further comprising the steps of producing a low dimensionality coordinate for each document and outputting the low dimensionality coordinate as a graphic image.

13. The method according to claim 11, wherein said projection is presented as a two dimensional image representing a third dimension as a landscape.

14. The method according to claim 11, wherein said high dimensionality is defined by a semantic analysis and said low dimensionality is defined by a human perceptual analysis.

15. The method according to claim 11, wherein each bounded continuous sub-space is a non-overlapping hypersphere.

16. The method according to claim 11, wherein said plurality of bounded continuous sub-space are defined iteratively to approach an optimum condition.

17. The method according to claim 11, wherein said plurality of bounded continuous sub-space are defined iteratively to approach an optimum condition using an Anchored Least Stress Algorithm.

18. The method according to claim 11, wherein said projecting comprises producing a vector relationship of each set of semantic information with a respective centroid and multiplying an operator matrix by said respective vector relationships.

19. The method according to claim 11, further comprising the steps of receiving a user input semantically defining said sets of semantic information and producing a graphic output representing a relationship of said sets of semantic information and said user input.

20. The method according to claim 11, further comprising the steps of receiving a natural language query defining said sets of semantic information;

producing a visual graphic output representing a relationship of said sets of semantic information and said user input.

21. The method according to claim 11, further comprising the step of producing a visual graphic output representing a relationship of said sets of semantic information and said centroids, and inferring a content of a set of semantic information in dependence on said graphic output.

22. The method according to claim 11, further comprising the step of producing a visual graphic output representing a relationship of said sets of semantic information and said centroids, wherein sets of semantic information are represented on a surface, an elevation of said surface representing a density of said sets of semantic information in a local region of said surface.

23. A computer readable medium storing program instructions for programming a general purpose computer to perform a method for representing human comprehensible information in a low-dimensionality space based on a high dimensionality analysis thereof, the information comprising sets of semantic information, comprising the steps of:

(a) representing the sets of semantic information as a vector in a high-dimensional information space;

(b) segmenting the information space into a plurality of bounded continuous sub-spaces, each having a centroid;

(c) projecting the segmented bounded continuous subspaces of the high-dimensional information space onto a low dimensional space, wherein said projection is sensitive to a relation of each set of semantic information to each centroid.