Methods and apparatuses for classifying electronic documents

• US 7,890,441 B2
• Filed: 04/14/2009
• Issued: 02/15/2011
• Est. Priority Date: 11/03/2003
• Status: Active Grant

• Current Assignee: Proofpoint Incorporated
• Original Assignee: Cloudmark Incorporated (Proofpoint Incorporated)
• Inventors: Prakash, Vipul V., Stemm, Mark
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US12/423,655
• Publication Number:
  US 20090259608A1
• Time in Patent Office: 672 Days
• Field of Search: 706/20, 706/45
• US Class Current: 706/20
• CPC Class Codes: H04L 51/212 using filtering or selective blocking
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Embodiments of the invention provide methods and apparatuses for classifying electronic documents (e.g., electronic communications) as either spam electronic documents or legitimate electronic documents. In accordance with one embodiment of the invention, each of a plurality of electronic communications is reduced to a corresponding multidimensional vector based on a multi-dimensional vector space. The multi-dimensional vectors represent corresponding electronic documents that have been classified as at least one type of electronic documents. Subsequent electronic documents to be classified are reduced to a corresponding multi-dimensional vector inserted into the multi-dimensional vector space. The electronic documents corresponding to an inserted multi-dimensional vector are classified based upon the proximity of the inserted multi-dimensional vector to at least one previously classified multi-dimensional vectors of the multi-dimensional vector space.

Claims

1. A method for processing a training set of electronic documents for document processing, the method implemented by computer instructions executing on a computer processor, said method comprising:

receiving said training set of electronic documents that are each assigned to two or more categories;

determining a first set of frequencies with which a set of document features appear in the training set of electronic documents;

determining a second set of frequencies with which the set of document features appear in each of the two or more categories of training the set of electronic documents;

selecting a subset of said set of document features for defining a multi-dimensional vector space for processing documents, said subset of document features selected from said set of document features based upon said first set of frequencies and said second set of frequencies; and

reducing each electronic document of the training set of electronic documents to a multi-dimensional vector in the multi-dimensional vector space.

2. The method for processing a training set of electronic documents for document processing as set forth in claim 1, the method further comprising:

reducing a new electronic document to a new multi-dimensional vector in the multi-dimensional vector space;

determining a set of nearest neighbor multi-dimensional vectors from electronic documents in said training set to the new multi-dimensional vector; and

computing a distance between said new multi-dimensional vector in the multi-dimensional vector space and each nearest neighbor multi-dimensional vector.

3. The method for processing a training set of electronic documents for document processing as set forth in claim 2 wherein computing said distance comprises calculating a cosine similarity distance metric.

4. The method for processing a training set of electronic documents for document processing as set forth in claim 2 wherein computing said distance comprises calculating a non-zero dimension proportionality metric.

5. The method for processing a training set of electronic documents for document processing as set forth in claim 2 wherein computing said distance comprises calculating a Euclidean distance metric.

6. The method for processing a training set of electronic documents for document processing as set forth in claim 2, the method further comprising:

classifying the new electronic document based upon a proximity of the new multi-dimensional vector to each of the nearest neighbor multi-dimensional vectors.

7. The method for processing a training set of electronic documents for document processing as set forth in claim 6 wherein said classifying said new electronic document comprises assigning said new electronic document a category of an electronic document from said training set if said distance is within a first threshold.

8. The method for processing a training set of electronic documents for document processing as set forth in claim 6 wherein said classifying said new electronic document comprises assigning said new electronic document a category based upon a vote of a set of electronic documents from said training set that are within a second threshold distance from said new electronic document in said multi-dimensional space.

9. The method for processing a training set of electronic documents for document processing as set forth in claim 6 wherein said classifying said new electronic document comprises

analyzing a set of electronic documents from said training set that are within a third threshold distance from said new electronic document in said multi-dimensional space to determine a potential category for said new electronic document;

and

assigning said new electronic document said potential category based if said analyzing results in an unambiguous classification.

10. A computer-readable medium, said computer-readable medium comprising a set of computer instructions that, when executed, implement a method for processing a training set of electronic documents for document processing, said method comprising:

receiving said training set of electronic documents that are each assigned to two or more categories;

determining a first set of frequencies with which a set of document features appear in the training set of electronic documents;

determining a second set of frequencies with which the set of document features appear in each of the two or more categories of training the set of electronic documents;

selecting a subset of said set of document features for defining a multi-dimensional vector space for processing documents, said subset of document features selected from said set of document features based upon said first set of frequencies and said second set of frequencies; and

reducing each electronic document of the training set of electronic documents to a multi-dimensional vector in the multi-dimensional vector space.

11. The computer-readable medium as set forth in claim 10, the method further comprising:

reducing a new electronic document to a new multi-dimensional vector in the multi-dimensional vector space;

determining a set of nearest neighbor multi-dimensional vectors from electronic documents in said training set to the new multi-dimensional vector; and

computing a distance between said new multi-dimensional vector in the multi-dimensional vector space and each nearest neighbor multi-dimensional vector.

12. The computer-readable medium as set forth in claim 11 wherein computing said distance comprises calculating a cosine similarity distance metric.

13. The computer-readable medium as set forth in claim 11 wherein computing said distance comprises calculating a non-zero dimension proportionality metric.

14. The computer-readable medium as set forth in claim 11 wherein computing said distance comprises calculating a Euclidean distance metric.

15. The computer-readable medium as set forth in claim 11, the method further comprising:

classifying the new electronic document based upon a proximity of the new multi-dimensional vector to each of the nearest neighbor multi-dimensional vectors.

16. The computer-readable medium as set forth in claim 15 wherein said classifying said new electronic document comprises assigning said new electronic document a category of an electronic document from said training set if said distance is within a first threshold.

17. The computer-readable medium as set forth in claim 15 wherein said classifying said new electronic document comprises assigning said new electronic document a category based upon a vote of a set of electronic documents from said training set that are within a second threshold distance from said new electronic document in said multi-dimensional space.

18. The computer-readable medium as set forth in claim 15 wherein said classifying said new electronic document comprises

analyzing a set of electronic documents from said training set that are within a third threshold distance from said new electronic document in said multi-dimensional space to determine a potential category for said new electronic document;

and

assigning said new electronic document said potential category based if said analyzing results in an unambiguous classification.