Methods and apparatuses for determining and designating classifications of electronic documents

• US 20050149546A1
• Filed: 11/01/2004
• Published: 07/07/2005
• Est. Priority Date: 11/03/2003
• Status: Abandoned Application

• Current Assignee: Cloudmark Incorporated (Proofpoint Incorporated)
• Original Assignee: Cloudmark Incorporated (Proofpoint Incorporated)
• Inventors: Prakash, Vipul Ved, Stemm, Mark
• Application Number:
  US10/979,604
• Publication Number:
  US 20050149546A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes

Abstract

Embodiments of the invention provide methods and apparatuses for automatically determining and designating classifications of electronic documents. In accordance with one embodiment of the invention, each of a plurality of electronic documents is reduced to a corresponding multidimensional vector based on a multi-dimensional vector space. The distances between multi-dimensional vectors are then evaluated. Multi-dimensional vectors within a specified distance of one another are considered to be a multi-dimensional vector cluster. The multi-dimensional vector space may contain one or more such clusters. Each cluster represents a distinct classification and the electronic documents corresponding to the multi-dimensional vectors of a cluster are classified as such. For one embodiment of the invention features of the electronic documents corresponding to the multi-dimensional vectors of a cluster are used to designate the classification represented by the cluster.

Claims

1. A method comprising:

defining a multi-dimensional vector space;

reducing each of a plurality of electronic documents to a corresponding multi-dimensional vector based upon the defined multi-dimensional vector space;

calculating a distance between each corresponding multi-dimensional vector of one or more portions of the plurality of corresponding multi-dimensional vectors, each portion of the plurality of corresponding multi-dimensional vectors containing a plurality of corresponding multi-dimensional vectors; and

determining one or more classifications for one or more respective portions of the electronic documents based upon the calculated distances, properties of the multi-dimensional vectors, and properties of the defined multi-dimensional vector space.

2. The method of claim 1 where the electronic documents have been initially assigned to one of a number of categories.

3. The method of claim 1 wherein the dimensions of the multi-dimensional vector space are defined by at least one feature.

4. The method of claim 3 wherein each of the at least one feature is selected based upon the differentiation ability of the feature.

5. The method of claim 3 wherein the at least one feature is based upon criteria selected from the group consisting of selected words, selected phrases, algorithms, phone numbers, and URLs.

6. The method of claim 5 where an algorithm returns a description of the structure and text of the electronic document.

7. The method of claim 6 where the algorithm extracts a pattern from the electronic document.

8. The method of claim 7 where the algorithm is a regular expression.

9. The method of claim 3 wherein each of the at least one feature is weighted based upon a differentiation ability of the feature.

10. The method of claim 9 wherein the feature weighting is based upon a rarity of occurrence in the multi-dimensional vector space.

11. The method of claim 9 wherein the feature weighting is based upon an occurrence in particular category and non-occurrence in at least one other category.

12. The method of claim 3 wherein the at least one feature is derived from a corpus of categorized electronic documents.

13. The method of claim 3 wherein the electronic document is reduced to a corresponding multi-dimensional vector based upon an occurrence and frequency of the at least one feature.

14. The method of claim 1 wherein the electronic document is an electronic communication.

15. The method of claim 14 wherein the electronic communication is an e-mail.

16. The method of claim 1 wherein the electronic document is an electronic publication.

17. The method of claim 16 wherein the electronic document is a world wide web page.

18. The method of claim 1 wherein the corresponding multi-dimensional vector indicates an occurrence and a frequency of one or more of the features in the defined vector space.

19. The method of claim 1 wherein determining one or more classifications for one or more respective portions of the electronic documents further comprises:

comparing the calculated distance between each corresponding multi-dimensional vector to a specified distance;

determining if the distance between two or more multi-dimensional vectors is within a specified distance;

determining that two or more multi-dimensional vectors having a distance between them that is within the specified distance constitute a cluster; and

designating a classification for this cluster.

20. The method of claim 19 further comprising:

designating the classification of a cluster based upon the features of the two or more multi-dimensional vectors that constitute the cluster.

21. The method of claim 1 wherein the distance between each corresponding multi-dimensional vector of one or more portions of the plurality of corresponding multi-dimensional vectors is calculated using a specific distance metric.

22. The method of claim 21 wherein the specific distance metric is a cosine similarity distance metric.

23. The method of claim 21 wherein the specific distance metric is a ratio of weighted feature frequencies for the features the two multi-dimensional vectors have in common and weighted feature frequencies for the all features for the two multi-dimensional vectors.

24. The method of claim 21 wherein the specific distance metric is selected from the group of distance metrics consisting of a non-zero dimension proportionality distance metric, a Manhattan distance metric, a Euclidean distance metric, a cosine similarity distance metric, and combinations thereof.

25. The method of claim 19 wherein the specified distance is a distance range.

26. The method of claim 19 further comprising:

specifying a second distance;

comparing the calculated distance between each corresponding multi-dimensional vector to the second distance;

determining if the distance between two or more multi-dimensional vectors is within the second distance;

determining that two or more multi-dimensional vectors having a distance between them that is within the second distance constitute an additional cluster; and

designating a classification to the additional cluster.

27. The method of claim 1 wherein a plurality of classifications has been determined, further comprising:

specifying a second distance;

examining the classifications that result from the calculated distances, properties of the multi-dimensional vectors, and properties of the defined multi-dimensional vector space; and

determining one or more additional classifications for one or more respective portions of the electronic documents based upon the second distance and the classifications that result from the calculated distances, properties of the multi-dimensional vectors, and properties of the defined multi-dimensional vector space.

28. A machine-readable medium having stored thereon a set of instructions which when executed cause a system to perform a method comprising:

defining a multi-dimensional vector space;

reducing each of a plurality of electronic documents to a corresponding multi-dimensional vector based upon the defined multi-dimensional vector space;

calculating a distance between each corresponding multi-dimensional vector of one or more portions of the plurality of corresponding multi-dimensional vectors, each portion of the plurality of corresponding multi-dimensional vectors containing a plurality of corresponding multi-dimensional vectors; and

determining one or more classifications for one or more respective portions of the electronic documents based upon the calculated distances, properties of the multi-dimensional vectors, and properties of the defined multi-dimensional vector space.

29. The machine-readable medium of claim 28 where the electronic documents have been initially assigned to one of a number of categories.

30. The machine-readable medium of claim 28 wherein the dimensions of the multi-dimensional vector space are defined by at least one feature.

31. The machine-readable medium of claim 30 wherein each of the at least one feature is selected based upon the differentiation ability of the feature.

32. The machine-readable medium of claim 30 wherein the at least one feature is based upon criteria selected from the group consisting of selected words, selected phrases, algorithms, phone numbers, and URLs.

33. The machine-readable medium of claim 32 where an algorithm returns a description of the structure and text of the electronic document.

34. The machine-readable medium of claim 33 where the algorithm extracts a pattern from the electronic document.

35. The machine-readable medium of claim 34 where the algorithm is a regular expression.

36. The machine-readable medium of claim 30 wherein each of the at least one feature is weighted based upon a differentiation ability of the feature.

37. The machine-readable medium of claim 36 wherein the feature weighting is based upon a rarity of occurrence in the multi-dimensional vector space.

38. The machine-readable medium of claim 36 wherein the feature weighting is based upon an occurrence in particular category and non-occurrence in at least one other category.

39. The machine-readable medium of claim 30 wherein the at least one feature is derived from a corpus of categorized electronic documents.

40. The machine-readable medium of claim 30 wherein the electronic document is reduced to a corresponding multi-dimensional vector based upon an occurrence and frequency of the at least one feature.

41. The machine-readable medium of claim 28 wherein the electronic document is an electronic communication.

42. The machine-readable medium of claim 41 wherein the electronic communication is an e-mail.

43. The machine-readable medium of claim 28 wherein the electronic document is an electronic publication.

44. The machine-readable medium of claim 43 wherein the electronic document is a world wide web page.

45. The machine-readable medium of claim 28 wherein the corresponding multi-dimensional vector indicates an occurrence and a frequency of one or more of the features in the defined vector space.

46. The machine-readable medium of claim 28 wherein the method further comprises:

comparing the calculated distance between each corresponding multi-dimensional vector to a specified distance;

determining if the distance between two or more multi-dimensional vectors is within a specified distance;

determining that two or more multi-dimensional vectors having a distance between them that is within the specified distance constitute a cluster; and

designating a classification for this cluster.

47. The machine-readable medium of claim 46 wherein the method further comprises:

designating the classification of a cluster based upon the features of the two or more multi-dimensional vectors that constitute the cluster.

48. The machine-readable medium of claim 28 wherein the distance between each corresponding multi-dimensional vector of one or more portions of the plurality of corresponding multi-dimensional vectors is calculated using a specific distance metric.

49. The machine-readable medium of claim 48 wherein the specific distance metric is a cosine similarity distance metric.

50. The machine-readable medium of claim 48 wherein the specific distance metric is a ratio of weighted feature frequencies for the features the two multi-dimensional vectors have in common and weighted feature frequencies for the all features for the two multi-dimensional vectors.

51. The machine-readable medium of claim 48 wherein the specific distance metric is selected from the group of distance metrics consisting of a non-zero dimension proportionality distance metric, a Manhattan distance metric, a Euclidean distance metric, a cosine similarity distance metric, and combinations thereof.

52. The machine-readable medium of claim 46 wherein the specified distance is a distance range.

53. The machine-readable medium of claim 46 wherein the method further comprises:

specifying a second distance;

comparing the calculated distance between each corresponding multi-dimensional vector to the second distance;

determining if the distance between two or more multi-dimensional vectors is within the second distance;

determining that two or more multi-dimensional vectors having a distance between them that is within the second distance constitute an additional cluster; and

designating a classification to the additional cluster.

54. The machine-readable medium of claim 28 wherein the method further comprises, upon determination of a plurality of classifications:

specifying a second distance;

examining the classifications that result from the calculated distances, properties of the multi-dimensional vectors, and properties of the defined multi-dimensional vector space; and

determining one or more additional classifications for one or more respective portions of the electronic documents based upon the second distance and the classifications that result from the calculated distances, properties of the multi-dimensional vectors, and properties of the defined multi-dimensional vector space.

55. A system comprising:

a processor;

a network interface coupled to the processor; and

a machine-readable medium having stored thereon a set of instructions which when executed cause the system to perform a method comprising;

reducing each of a plurality of electronic documents to a corresponding multi-dimensional vector based upon the defined multi-dimensional vector space;

calculating a distance between each corresponding multi-dimensional vector of one or more portions of the plurality of corresponding multi-dimensional vectors, each portion of the plurality of corresponding multi-dimensional vectors containing a plurality of corresponding multi-dimensional vectors; and

determining one or more classifications for one or more respective portions of the electronic documents based upon the calculated distances, properties of the multi-dimensional vectors, and properties of the defined multi-dimensional vector space.

56. The system of claim 55 where the electronic documents have been initially assigned to one of a number of categories.

57. The system of claim 55 wherein the dimensions of the multi-dimensional vector space are defined by at least one feature.

58. The system of claim 57 wherein each of the at least one feature is selected based upon the differentiation ability of the feature.

59. The system of claim 57 wherein the at least one feature is based upon criteria selected from the group consisting of selected words, selected phrases, algorithms, phone numbers, and URLs.

60. The system of claim 59 where an algorithm returns a description of the structure and text of the electronic document.

61. The system of claim 60 where the algorithm extracts a pattern from the electronic document.

62. The system of claim 61 where the algorithm is a regular expression.

63. The system of claim 57 wherein each of the at least one feature is weighted based upon a differentiation ability of the feature.

64. The system of claim 63 wherein the feature weighting is based upon a rarity of occurrence in the multi-dimensional vector space.

65. The system of claim 63 wherein the feature weighting is based upon an occurrence in particular category and non-occurrence in at least one other category.

66. The system of claim 57 wherein the at least one feature is derived from a corpus of categorized electronic documents.

67. The system of claim 57 wherein the electronic document is reduced to a corresponding multi-dimensional vector based upon an occurrence and frequency of the at least one feature.

68. The system of claim 55 wherein the electronic document is an electronic communication.

69. The system of claim 68 wherein the electronic communication is an e-mail.

70. The system of claim 55 wherein the electronic document is an electronic publication.

71. The system of claim 70 wherein the electronic document is a world wide web page.

72. The system of claim 55 wherein the corresponding multi-dimensional vector indicates an occurrence and a frequency of one or more of the features in the defined vector space.

73. The system of claim 55 wherein the method further comprises:

comparing the calculated distance between each corresponding multi-dimensional vector to a specified distance;

determining if the distance between two or more multi-dimensional vectors is within a specified distance;

determining that two or more multi-dimensional vectors having a distance between them that is within the specified distance constitute a cluster; and

designating a classification for this cluster.

74. The system of claim 73 wherein the method further comprises:

designating the classification of a cluster based upon the features of the two or more multi-dimensional vectors that constitute the cluster.

75. The system of claim 55 wherein the distance between each corresponding multi-dimensional vector of one or more portions of the plurality of corresponding multi-dimensional vectors is calculated using a specific distance metric.

76. The system of claim 75 wherein the specific distance metric is a cosine similarity distance metric.

77. The system of claim 75 wherein the specific distance metric is a ratio of weighted feature frequencies for the features the two multi-dimensional vectors have in common and weighted feature frequencies for the all features for the two multi-dimensional vectors.

78. The system of claim 75 wherein the specific distance metric is selected from the group of distance metrics consisting of a non-zero dimension proportionality distance metric, a Manhattan distance metric, a Euclidean distance metric, a cosine similarity distance metric, and combinations thereof.

79. The system of claim 73 wherein the specified distance is a distance range.

80. The system of claim 73 wherein the method further comprises:

specifying a second distance;

comparing the calculated distance between each corresponding multi-dimensional vector to the second distance;

determining if the distance between two or more multi-dimensional vectors is within the second distance;

determining that two or more multi-dimensional vectors having a distance between them that is within the second distance constitute an additional cluster; and

designating a classification to the additional cluster.

81. The system of claim 55 wherein the method further comprises, upon determination of a plurality of classifications:

specifying a second distance;

examining the classifications that result from the calculated distances, properties of the multi-dimensional vectors, and properties of the defined multi-dimensional vector space; and

determining one or more additional classifications for one or more respective portions of the electronic documents based upon the second distance and the classifications that result from the calculated distances, properties of the multi-dimensional vectors, and properties of the defined multi-dimensional vector space.