System and method of context vector generation and retrieval

• US 5,619,709 A
• Filed: 11/21/1995
• Issued: 04/08/1997
• Est. Priority Date: 09/20/1993
• Status: Expired due to Term

• Current Assignee: Fair Isaac Corporation
• Original Assignee: HNC Incorporated
• Inventors: Oing, Pu, Caid, William R.
• Primary Examiner(s): Weinhardt, Robert A.
• Assistant Examiner(s): Thomas, Joseph
• Application Number:
  US08/561,167
• Time in Patent Office: 504 Days
• Field of Search: 364/419.19, 364/419.01, 364/419.08, 364/419.11, 364/419.13, 395/600, 395/650, 395/375
• US Class Current: 715/209
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system and method for generating context vectors for use in storage and retrieval of documents and other information items. Context vectors represent conceptual relationships among information items by quantitative means. A neural network operates on a training corpus of records to develop relationship-based context vectors based on word proximity and co-importance using a technique of "windowed co-occurrence". Relationships among context vectors are deterministic, so that a context vector set has one logical solution, although it may have a plurality of physical solutions. No human knowledge, thesaurus, synonym list, knowledge base, or conceptual hierarchy, is required. Summary vectors of records may be clustered to reduce searching time, by forming a tree of clustered nodes. Once the context vectors are determined, records may be retrieved using a query interface that allows a user to specify content terms, Boolean terms, and/or document feedback. The present invention further facilitates visualization of textual information by translating context vectors into visual and graphical representations. Thus, a user can explore visual representations of meaning, and can apply human visual pattern recognition skills to document searches.

Claims

1. In a computer having a processor and storage, a computer-implemented process of generating a set of summary vectors in a relative vector space such that for any subset of summary vectors associated with a subset of records there is a single logical relative orientation of the summary vectors that defines the relative meaning of the records, and a plurality of absolute orientations of the summary records, comprising the steps of:

(a) providing a training set of records for processing by the processor, each record containing a plurality of information elements;

(b) assigning to selected information elements in each record an initial context vector consisting solely of a plurality of randomly generated component data values;

(c) for selected information elements in each record, modifying the initial context vector of the selected information element by a function of the context vectors of information elements within a selected proximity to the selected information element and a proximity constraint that varies a magnitude of the modification to the initial context vector;

(d) for each record, determining a summary vector by combining the modified context vectors of the information elements of the record according to program instructions in the storage and executed on the processor; and

(e) storing the determined summary vectors in the computer storage.

2. The computer-implemented process of claim 1, further comprising the steps of:

(f) determining whether an additional iteration is required to modify the initial context vector using a stopping criterion; and

(g) responsive to the results of step (f), selectively repeating steps (c) through (e).

3. The computer-implemented process of claim 1, wherein:

the records comprise documents; and

the information elements comprise words.

4. The computer-implemented process of claim 3, further comprising the steps of:

(a.1) removing stop-listed words from the documents;

(a.2) marking multiple-word phrases to be treated as single words; and

(a.3) converting words into word stems.

5. The computer-implemented process of claim 1, wherein:

the records comprise documents describing medical procedures; and

the information elements comprise ICD[9] codes.

6. The computer-implemented process of claim 1, wherein step (c) comprises the substeps of, for selected information elements in each record:

(c.1) designating the selected information element as a target element;

(c.2) defining a window comprising the target element and a plurality of neighbor information elements within the selected proximity, each neighbor information element having a position in the window relative to the target element; and

(c.3) modifying the context vector of the target element as a function of the context vectors of the neighbor elements, the position of the neighbor elements, a frequency function determined by a number of records containing each neighbor element, and the proximity constraint.

7. The computer-implemented process of claim 6, wherein substep (c.3) comprises the substeps of, for selected neighbor elements:

(c.3.1) determining an error vector representing a difference between the context vector of the target element and the context vector of the neighbor element; and

(c.3.2) applying the error vector to the context vector of the target element.

8. The computer-implemented process of claim 7, further comprising the substep of, for selected neighbor elements, adjusting the magnitude of the error vector according to the relative proximity of the neighbor element to the target element.

9. The computer-implemented process of claim 7, further comprising the substep of, for selected neighbor elements, adjusting the magnitude of the error vector according to a function dependent on the relative proximity of the neighbor element to the target element.

10. The computer-implemented process of claim 6, further comprising the substep of, for selected neighbor elements, determining the proximity constraint according to relative co-importance of the target element and the neighbor element.

11. The computer-implemented process of claim 10, further comprising the substep of, for selected neighbor elements, determining the relative co-importance according to the relative importance of the target element and the relative importance of the neighbor element.

12. The computer-implemented process of claim 11, further comprising the substeps of:

for the target element, determining the relative importance inversely according to the frequency of occurrence of the target element in the training set; and

for selected neighbor elements, determining the relative importance inversely according to the frequency of occurrence of the target element in the training set.

13. The computer-implemented process of claim 11, further comprising the substeps of:

for the target element, determining the relative importance by the equation;

##EQU9## wherein;

B represents a predefined lower bound;

ND_j represents the number of records containing the target element; and

TND represents the total number of records; and

for selected neighbor elements, determining the relative importance by the equation;

##EQU10## wherein;

B represents a predefined lower bound;

ND_j represents the number of records containing the neighbor element; and

TND represents the total number of records.

14. The computer-implemented process of claim 1, wherein step (d) comprises adding the context vectors of the information elements of the record.

15. The computer-implemented process of claim 1, wherein step (d) comprises the substeps of:

(d.1) for a selected information element, generating a weight depending inversely on the frequency of occurrence of the information element in the training set of records;

(d.2) for a selected information element, applying the weight to the context vector to generate an adjusted context vector; and

(d.3) adding the adjusted context vectors of the information elements of the record.

16. The computer-implemented process of claim 1, further comprising the step of normalizing the summary vector for each record.

17. The computer-implemented process of claim 1, wherein step (e) comprises storing the determined summary vectors using convergent k-means clustering.

18. The computer-implemented process of claim 17, wherein the step of storing using convergent k-means clustering comprises the substeps of:

(e.1) initially partitioning the summary vectors into a plurality of clusters, each cluster containing at least one summary vector;

(e.2) determining a centroid vector for each cluster;

(e.3) for each summary vector, performing the steps of;

(e.3.1) determining the distance between the summary vector and each centroid vector;

(e.3.2) determining which centroid vector has the smallest distance to the summary vector;

(e.3.3) responsive to the determined centroid vector not being associated with the cluster containing the summary vector, adjusting the contents of the clusters so that the cluster associated with the determined centroid contains the summary vector;

(e.4) adjusting the centroid vectors for the clusters that have been adjusted; and

(e.5) responsive to a stopping criterion not having been achieved, repeating steps (e.1) through (e.5).

19. The computer-implemented process of claim 1, wherein step (e) comprises storing the determined summary vectors using Kohonen self-organization with conscience.

20. The computer-implemented process of claim 1, further comprising the steps of:

accepting a query from a user containing at least one query information element;

determining a query context vector as a function of context vectors for each of the query information elements;

comparing the query context vector with the summary vectors; and

accumulating a list of summary vectors ranked according to the results the comparing step.

21. The computer-implemented process of claim 20, further comprising the step of retrieving a subset of summary vectors according to the results of the comparing step.

22. The computer-implemented process of claim 20, wherein the comparing step comprises the substep of performing a dot product operation with the query context vector and the summary vectors.

23. The computer-implemented process of claim 20, further comprising the steps of:

accepting a signal from the user indicating which summary vectors are most relevant;

determining a revised query context vector based on the accepted signal; and

repeating the comparing and accumulating steps.

24. A system for generating a set of summary vectors, comprising:

a storage device containing a training set of records, each record containing a plurality of information elements;

an initial context vector generator, coupled to the storage device, for assigning to selected information elements in each record an initial context vector comprising solely a plurality of randomly generated component data values;

an iterative training device, coupled to the storage device, for modifying the initial context vector of the selected information elements by a function of the context vectors of information elements within a selected proximity to the selected information element and a proximity constraint that varies a magnitude of the modification to the initial context vector;

a vector combiner, coupled to the storage device, for combining the context vectors of the information elements of each record to determine a summary vector for the record and storing the determined summary vectors in the storage device.

25. The system of claim 24, wherein:

the records comprise documents; and

the information elements comprise words.

26. The system of claim 25, further comprising a preprocessor, coupled to the storage device, for removing stop-listed words from the documents, marking multiple-word phrases to be treated as single words, and converting words into word stems.

27. The system of claim 24, wherein the iterative training device comprises:

a function providing a movable window that iteratively selects a target element and a plurality of neighbor elements proximate to the target elements;

a proximity determiner that determines a proximity of each neighbor element to the target element;

a co-importance determiner that determines the relative importance of the target element and each of the neighbor elements in the window; and

a context vector modifier for modifying the context vector for the target element responsive to the results of the proximity determiner and the co-importance determiner for each neighbor element.

28. The system of claim 24, further comprising:

an input device for accepting a query from a user;

a query context vector determiner, coupled to the input device, for determining a query context vector;

a comparator, coupled to the query context vector determiner, for comparing the query context vector with the context vectors of the records in the corpus; and

a list generator, coupled to the comparator, for accumulating a list of records in the corpus ranked according to the results of the comparator.

29. A computer-implemented process of generating a dictionary of information elements each associated with a context vector for a database of records, each record containing at least one information element, each information element having a determinate proximity to other information elements, comprising the steps of:

(a) selecting a plurality of information elements for including in the dictionary;

(b) assigning to the selected information elements an initial context vector consisting solely of a plurality of randomly generated component data values;

(c) for each selected information element being a target information element, iteratively modifying its context vector by the context vectors of neighbor information elements as a function of the proximity of the neighbor information elements to the target information element, the modified context vectors of the selected information elements forming the dictionary of context vectors.

30. The computer-implemented process of claim 29, wherein modifying the context vector of a target information element further comprises:

(c.1) for each neighbor information element, modifying the context vector of the target information element by a function of;

i) an error vector being the difference between the context vector of the target information element and the context vector of the neighbor information element; and

,

ii) a proximity constraint being a function of the relative co-importance of the target information element and the neighbor information element in the database of records.

31. The computer-implemented process of claim 30, further comprising determining the relative co-importance according to the relative importance of the target information element and the relative importance of the neighbor information element.

32. The computer-implemented process of claim 31, wherein determining the relative co-importance comprises:

determining the relative importance of the target information element, inversely according to the frequency of occurrence of the target information element in the training set of records; and

,

determining the relative importance of the neighbor information element inversely according to the frequency of occurrence of the neighbor information element in the training set.

33. The computer-implemented process of claim 32, further comprising the substeps of:

determining the relative importance of the target information element by the equation;

##EQU11## wherein;

B represents a predefined lower bound;

ND_j represents the number of records containing the target information element; and

TND represents the total number of records; and

,

determining the relative importance of the neighbor information element by the equation;

##EQU12## wherein;

B represents a predefined lower bound;

ND_j represents the number of records containing the neighbor element; and

,

TND represents the total number of records.

34. The computer-implemented process of claim 29, further comprising:

;

(d) for at least one record in the database;

(d.1) for each information element in the record that matches an information element in the dictionary, obtaining a modified context vector associated with the matching information element in the dictionary as the context vector for the information element; and

,

(d.2) summing the obtained context vectors to produce a summary vector for the record.

35. The computer-implemented process of claim 29, wherein a proximity constraint varies a magnitude of the modification to the context vector of the target information element as a function of both the frequency of occurrence of the target information element and the frequency of the occurrence of each neighbor information element.

36. The computer implemented process of claim 29, wherein the proximity between information elements is a quantifiable value based on at least one of:

a distance between the information elements;

an orientation of an information element with respect to another information element;

a frequency of occurrence of an information element relative to a frequency of occurrence another information element; and

a temporal relationship between two or more information elements.

37. In a computer system including a storage device containing a plurality of records, each record containing a plurality of information elements, a computer readable memory for configuring and controlling a processor in the computer system to generate a dictionary of context vectors, the computer readable memory comprising:

an initial context vector generator, coupled to the storage device, for assigning to selected information elements in each record an initial context vector comprising solely of a plurality of randomly generated component data values; and

,

an iterative training device, coupled to the storage device, for iteratively modifying the context vector of each selected information element, being a target information element, by the context vectors of neighbor information elements as a function of the proximity of the neighbor information element to the target information element, the modified context vectors of the selected information elements forming the dictionary of context vectors.

38. The computer readable memory of claim 37, wherein a proximity constraint varies a magnitude of the modification to the context vector of the target information element as a function of both the frequency of occurrence of the target information element and the frequency of the occurrence of each neighbor information element.

39. The computer readable memory of claim 37, further comprising:

a vector combiner, coupled to the storage device, for combining the context vectors of the information elements of each record to determine a summary vector for the record, and for storing the determined summary vector of each record in the storage device.