Computer-implemented system and method for text-based document processing

• US 6,996,575 B2
• Filed: 05/31/2002
• Issued: 02/07/2006
• Est. Priority Date: 05/31/2002
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Cox, James A., Dain, Oliver M.
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US10/159,792
• Publication Number:
  US 20030225749A1
• Time in Patent Office: 1,348 Days
• Field of Search: 707 1- 10, 707/100, 707/102
• US Class Current: 707/739
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: Y10S 707/915 Image
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A computer-implemented system and method for processing text-based documents. A frequency of terms data set is generated for the terms appearing in the documents. Singular value decomposition is performed upon the frequency of terms data set in order to form projections of the terms and documents into a reduced dimensional subspace. The projections are normalized, and the normalized projections are used to analyze the documents.

Claims

1. A computer-implemented method for processing text-based documents, comprising the steps of:

generating frequency of terms data for terms appearing in the documents;

performing singular value decomposition upon the frequency of terms data in order to form projections of the terms and documents into a reduced dimensional subspace,

normalizing the projections to a pre-selected length; and

using the normalized projections to provide structured data about the documents.

2. The method of claim 1 wherein the documents comprise unstructured data.

3. The method of claim 2 wherein the documents comprise free-form text.

4. The method of claim 3 wherein the documents comprise images.

5. The method of claim 1 wherein the frequency of terms data is generated for a subset of the terms appearing in the documents.

6. The method of claim 1 further comprising the step of:

parsing the documents so as to generate the frequency of terms data, said frequency of terms data indicating the frequency of terms within the documents.

7. The method of claim 6 wherein the terms comprise single word entries.

8. The method of claim 6 wherein the terms comprise a multi-word token.

9. The method of claim 6 wherein the terms comprise entities.

10. The method of claim 1 wherein the frequency of terms data comprises unweighted frequency of terms data, said singular value decomposition being performed upon the frequency of terms data which is unweighted.

11. The method of claim 1 wherein the frequency of terms data comprises weighted frequency of terms data, said singular value decomposition being performed upon the frequency of terms data which has been weighted.

12. The method of claim 11 wherein the weighting of the frequency of terms data is used to provide discrimination among documents.

13. The method of claim 11 wherein the weighting of the frequency of terms data is based upon frequency that a term appears in the documents.

14. The method of claim 11 wherein the weighting of the frequency of terms data is based upon a local weighting approach.

15. The method of claim 11 wherein the weighting of the frequency of terms data is based upon a global weighting approach.

16. The method of claim 11 wherein the weighting of the frequency of terms data is based upon a target variable.

17. The method of claim 11 wherein the weighting of the frequency of terms data is based upon a mutual information weighting process.

18. The method of claim 11 wherein the weighting of the frequency of terms data is based upon an information gain weighting process.

19. The method of claim 1 wherein the frequency of terms data comprises a rectangular un-normalized data set, said performing singular value decomposition step including performing the singular value decomposition upon the rectangular un-normalized data set.

20. The method of claim 1 wherein the singular value decomposition reduces the dimension of the frequency of terms data from n-dimensional space to k-dimensional subspace.

21. The method of claim 1 wherein the singular value decomposition uses a truncated singular value decomposition to reduce the dimension of the frequency of terms data from n-dimensional space to k-dimensional subspace.

22. The method of claim 1 wherein the normalized projections force their vectors to lie on the surface of a unit sphere around zero.

23. The method of claim 1 wherein the singular value decomposition results in the documents being represented as vectors in a best-fit k-dimensional subspace, wherein the vectors are normalized with respect to a unit measurement thereby creating a normalized reduced dimensional subspace, said normalized reduced dimensional subspace being used in analysis of the documents.

24. The method of claim 23 wherein the number of k dimensions is selected in order to exclude noise within the normalized reduced dimensional space while including the signal in the normalized reduced dimensional space.

25. The method of claim 23 wherein the sum of the squared distances of the magnitudes of two vectors is isomorphic to the cosines between the vectors.

26. The method of claim 1 wherein a vector within the normalized reduced dimensional subspace can be represented on a unit hypersphere so that Euclidean distances between points directly correspond to the dot products of their vectors.

27. The method of claim 1 wherein the projections within the normalized dimensional subspace automatically account for polysemy existing within the documents.

28. The method of claim 27 wherein the projections within the normalized dimensional subspace automatically account for synonymy existing within the documents.

29. The method of claim 1 wherein a predetermined document analysis algorithm uses the normalized projections to analyze the documents.

30. The method of claim 1 wherein Latent Semantic Analysis uses the normalized projections to analyze the documents.

31. The method of claim 1 further comprising the step of:

using the normalized projections for clustering the documents.

32. The method of claim 1 further comprising the step of:

using the normalized projections for categorizing the documents.

33. The method of claim 1 further comprising the step of:

using the normalized projections for combining at least one of the documents within a pre-existing corpus of structured documents.

34. The method of claim 1 further comprising the step of:

using the normalized projections in predictive modeling of the documents.

35. The method of claim 34 wherein a memory-based reasoning module uses the normalized projections to predict document categories for the documents.

36. The method of claim 34 wherein a neural network uses the normalized projections to predict document categories for the documents.

37. Computer software stored on a computer readable media, the computer software comprising program code for carrying out a method according to claim 1.

38. The method of claim 1 further comprising:

using the normalized projections in order to cluster. categorize, and combine with other documents.

39. The method of claim 1 further comprising:

receiving a search term; and

using the normalized projections with latent semantic analysis (LSA) in order to determine which of the documents are relevant to the search term.

40. The method of claim 1 further comprising:

receiving a search term; and

using the normalized projections with a nearest neighbor procedure to determine a subset of the documents based upon the received search term.

41. The method of claim 40 wherein the nearest neighbor procedure performs steps comprising:

receiving the search term that seeks neighbors to a probe data point;

evaluating nodes in a data tree to determine which data points neighbor a probe data point, wherein the data points are based upon the normalized projections,

wherein the nodes contain the data points, wherein the nodes are associated with ranges for the data points included in their respective branches; and

determining which data points neighbor the probe data point based upon the data point ranges associated with a branch.

42. The method of claim 41 wherein the nearest neighbor procedure uses the normalized projections to determine distances between the probe data point and the data points of the tree based upon the ranges.

43. The method of claim 42 wherein the nearest neighbor procedure determines nearest neighbors to the probe data point based upon the determined distances.

44. The method of claim 41 wherein the nearest neighbor procedure uses the normalized projections to determine distances between the probe data point and the data points of the tree based upon the ranges,

wherein the nearest neighbor procedure selects as nearest neighbors a preselected number of the data points whose determined distances are less than the remaining data points.

45. The method of claim 44 wherein the nearest neighbor procedure constructs the data tree by partitioning the data points from a database into regions.

46. The method of claim 40 wherein the nearest neighbor procedure uses a KD-Tree procedure.

47. The method of claim 40 wherein the nearest neighbor procedure uses a nearest neighbor procedure means.

48. The method of claim 1 wherein the documents comprise unstructured patent documents.

49. A computer-implemented method for processing unstructured text-based documents, comprising the steps of:

using a dimensionality reduction procedure in order to form projections of unstructured documents'"'"' terms into a reduced dimensional subspace;

using the reduced dimensional subspace to generate structured data about the unstructured documents;

combining the structured document data with additional structured data; and

analyzing the combined structured data.

50. The method of claim 49 wherein the dimensionality reduction procedure uses a truncation procedure.

51. The method of claim 49 wherein the dimensionality reduction procedure uses a singular value decomposition procedure.

52. The method of claim 49 wherein the dimensionality reduction procedure uses singular value decomposition procedure means and normalization procedure means.

53. The method of claim 49 wherein the dimensionality reduction procedure uses a singular value decomposition procedure to form the projections of the unstructured documents'"'"' terms into the reduced dimensional subspace,

wherein the projections are normalized to a pre-selected length,

wherein the normalized projections are used to generate structured data about the unstructured documents.

54. The method of claim 53 wherein the reduced dimensional subspace is a normalized reduced dimensional subspace containing the normalized projections.

55. The method of claim 49 wherein the additional structured data comprises structured data generated independently of the generation of the structured document data.

56. The method of claim 49 wherein the additional structured data comprises structured data generated independently of the use of the reduced dimensional subspace to generate the structured document data.

57. The method of claim 49 wherein the unstructured documents include stock news reports, wherein the additional structured data comprises company financial data.

58. The method of claim 57 wherein the analyzing of the combined structured data comprises predicting stock performance.

59. A computer-implemented apparatus for processing text-based documents, comprising:

means for generating frequency of terms data for terms appearing in the documents;

means for performing singular value decomposition upon the frequency of terms data in order to form projections of the terms and documents into a reduced dimensional subspace,

means for normalizing the projections to a pre-selected length; and

means for using the normalized projections to provide structured data about the documents.

60. A memory for storing data for access by a computer program being executed on a data processing system, comprising a data structure stored in said memory, said data structure including:

frequency of terms data for terms appearing in unstructured text-based documents; and

normalized reduced projections of the frequency of terms data,

wherein the normalized reduced projections are used by the computer program to generate structured data about the unstructured text-based documents.