Method and system for two-dimensional visualization of an information taxonomy and of text documents based on topical content of the documents

• US 5,625,767 A
• Filed: 03/13/1995
• Issued: 04/29/1997
• Est. Priority Date: 03/13/1995
• Status: Expired due to Fees

• Current Assignee: Bartell, Brian, Robert Clarke
• Original Assignee: Bartell, Brian, Robert Clarke
• Inventors: Bartell, Brian, Clarke, Robert
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/402,839
• Time in Patent Office: 778 Days
• Field of Search: 395/140, 395/133, 395/141, 395/155, 395/159-161, 395/600, 395/650, 395/63, 395/145, 395/147, 364/419.19
• US Class Current: 345/440
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and system for aiding users in visualizing the relatedness of retrieved text documents and the topics to which they relate comprises training a classifier by semantically analyzing an initial group of manually-classified documents, positioning the classes and documents in two-dimensional space in response to semantic associations between the classes, and displaying the classes and documents. The displayed documents may be retrieved by an information storage and retrieval subsystem in any suitable manner.

Claims

1. A method for visually representing the semantic relatedness between a predetermined plurality of classes and a plurality of documents, each document stored in a computer document retrieval system, said plurality of documents collectively comprising a plurality of terms in computer-readable format, each document having a tag representing the topical relatedness of said document to each said class, said method comprising the steps of:

generating a semantic space map in response to said terms and said tag of each document of said plurality of documents, said semantic space map representing the position in a plurality of dimensions of each class relative to every other said class, the spatial distance between said position of said each class and said every other class corresponding to the semantic relatedness of said each class to said every other class;

populating said semantic space map in response to said plurality of documents, said populated semantic space map representing the position in a plurality of dimensions of each class relative to every other class and of each document relative to each class, the spatial distance between said position of said each document relative to said each class corresponding to the semantic relatedness of said each document to said each class; and

displaying a visual representation of at least a portion of said populated semantic space map.

2. The method claimed in claim 1, wherein said step of generating a semantic space map comprises the steps of:

generating a semantic association between each said class and every other said class in response to said plurality of documents; and

multidimensionally scaling said plurality of classes in response to said semantic association between each said class and every other said class.

3. The method claimed in claim 2, wherein said step of generating a semantic space map further comprises the step of generating term frequency statistics in response to said plurality of documents.

4. The method claimed in claim 3, wherein said step of generating a semantic association comprises the step of generating a plurality of class conditional probability distributions, each corresponding to one of said classes and each comprising the probability of each said term occurring in said one of said classes.

5. The method claimed in claim 4, wherein said step of generating a semantic association comprises the steps of determining the Chi-Squared measure of distance between each class conditional probability distribution and every other said class conditional probability distribution.

6. The method claimed in claim 1, wherein said step of populating said semantic space map in response to said plurality of documents comprises the steps of:

producing a set of class scores for each said document using a statistical classifier to produce a classified document in response to said terms in said document; and

positioning said classified document in said plurality of dimensions.

7. The method claimed in claim 6, wherein:

said statistical classifier is trained in response to said plurality of documents; and

said step of populating said semantic space map comprises the steps of producing a set of class scores for a new document to produce a classified new document, and positioning said classified new document in said plurality of dimensions.

8. The method claimed in claim 6, wherein said step of producing a set of class scores comprises the step of performing a maximum likelihood estimation.

9. The method claimed in claim 8, wherein:

said step of generating a semantic association between each said class and every other said class comprises the step of computing the probability and frequency of each said term occurring in each said class; and

said set of class scores is computed in response to said probability of each said term occurring in each said class.

10. The method claimed in claim 9, wherein:

if the probability of a term occurring in a class is nonzero, each class score is computed by summing, over said terms in each said document, the logarithm of the quotient of the frequency of said term occurring in said class divided by the sum of the sum of the frequencies of all terms occurring in said class; and

if the probability of a term occurring in a class is zero, each class score is computed by summing, over said terms in each said class, the logarithm of the quotient of a predetermined constant divided by the sum of the frequencies of all terms occurring in said class.

11. The method claimed in claim 10, wherein said predetermined constant is greater than or equal to 0.001 and less than or equal to 1.0.

12. The method claimed in claim 6, wherein said step of positioning said classified document comprises the steps of:

selecting a predetermined number of class scores in each set, said selected class scores being greater than all other said class scores in said set;

normalizing said selected class scores to produce normalized class scores; and

determining the weighted average of said positions of said classes corresponding to said normalized class scores using said normalized class scores as weights.

13. The method claimed in claim 1, wherein said step of displaying a visual representation of at least a portion of said populated semantic space map comprises the steps of:

querying a document retrieval system to produce a set of located documents; and

displaying a visual representation of each said class and a visual representation of each said located document in response to said populated semantic space map.

14. The method claimed in claim 13, wherein:

the spatial distance between the visual representation of each class and the visual representation of every other said class corresponds to the semantic relatedness of said class to said every other said class; and

the spatial distance between the visual representation of each located document and the visual representation of every other said located document approximately corresponds to the semantic relatedness of said located document to said every other said located document.

15. A system for displaying a visual representation of documents and classes to which said documents relate, comprising:

a document retrieval subsystem having a user input device for receiving a user query, a user output device for displaying graphical representations of documents and a predetermined plurality of classes, and memory for storing said documents, each said document having a topical association with one of said classes, said document retrieval system providing retrieved documents in response to said user query;

a classification subsystem for computing a semantic relatedness between each class and every other one of said classes and for producing a set of class scores for each stored document, each class score in said set representing a semantic relatedness between said stored document and one of said classes; and

a visualization subsystem for producing a semantic space map in response to said semantic relatedness between each class and every other one of said classes, for populating said semantic space map with said stored documents in response to said sets of class scores and for displaying a populated semantic space map on said user output device.

16. A machine-readable computer data storage medium having stored therein a program, comprising:

a term frequency statistics generator for generating term frequency statistics in response to a plurality of pre-classified documents, each having a plurality of terms and each topically associated with a predetermined one of a predetermined plurality of classes;

a semantic space map generator for generating a semantic association between each class of said plurality of classes and every other class of said plurality of classes in response to said term frequency statistics and topical association between each document and predetermined one of said plurality of classes;

a multidimensional scaler for positioning said plurality of classes in a plurality of dimensions in a semantic space map in response to said semantic association between each said class and every other said class;

a statistical classifier for producing a set of class scores for a document in response to frequencies of terms in said document and for positioning said document in said semantic space map in response to said set of class scores, said set of class scores representing the semantic association between said document and each said class; and

a semantic space map populator for positioning said document corresponding to said set of class scores in said semantic space map.

17. The data storage medium claimed in claim 16, wherein said semantic space map generator generates a plurality of class conditional probability distributions, each corresponding to one of said classes and each comprising the probability of each said term occurring in said one of said classes.

18. The data storage medium claimed in claim 17, wherein said semantic space map generator computes said semantic association in response to the Chi-Squared measure of distance between each class conditional probability distribution and every other said class conditional probability distribution.

19. The data storage medium claimed in claim 16, wherein said statistical classifier computes said set of class scores in response to a maximum likelihood estimation.

20. The data storage medium claimed in claim 19, wherein:

if the probability of a term occurring in a class is nonzero, said statistical classifier computes each class score by summing, over said terms in each said pre-classified document, the logarithm of the quotient of the frequency of said term occurring in said class divided by the sum of the sum of the frequencies of all terms occurring in said class; and

if the probability of a term occurring in a class is zero, said statistical classifier computes each class score by summing, over said terms in each said class, the logarithm of the quotient of a predetermined constant divided by the sum of the frequencies of all terms occurring in said class.

21. The data storage medium claimed in claim 20, wherein said predetermined constant is greater than or equal to 0.001 and less than or equal to 1.0.

22. The data storage medium claimed in claim 16, wherein:

said semantic space map populator selects a predetermined number of class scores in each set, said selected class scores being greater than all other said class scores in said set;

said semantic space map populator normalizes said selected class scores to produce normalized class scores; and

said semantic space map populator computes a weighted average of said positions of said classes corresponding to said normalized class scores using said normalized class scores as weights.