Group Based Spam Classification

• US 20100191819A1
• Filed: 04/05/2010
• Published: 07/29/2010
• Est. Priority Date: 01/24/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: AOL Inc. (Apollo Global Management, Inc.)
• Inventors: Kolcz, Aleksander, Alspector, Joshua, Chowdhury, Abdur
• Granted Patent: US 8,504,627 B2
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

An e-mail filter is used to classify received e-mails so that some of the classes may be filtered, blocked, or marked. The e-mail filter may include a classifier that can classify an e-mail as belonging to a particular class and an e-mail grouper that can detect substantially similar, but possibly not identical, e-mails. The e-mail grouper determines groups of substantially similar e-mails in an incoming e-mail stream. For each group, the classifier determines whether one or more test e-mails from the group belongs to the particular class. The classifier then designates the class to which the other e-mails in the group belong based on the results for the test e-mails.

Claims

1. A method of classifying e-mails, the method comprising:

receiving e-mails that include a header portion and a content portion;

storing the received e-mails;

analyzing the content portions of the stored e-mails to cluster the e-mails into multiple groups of substantially duplicate e-mails;

storing the multiple groups of substantially duplicate e-mails;

selecting one or more test e-mails from at least one of the stored groups;

determining a class for the one or more test e-mails; and

classifying at least one non-test e-mail in the at least one stored group based on the determined class of the one or more test e-mails.

2. The method of claim 1 wherein analyzing the content portions of the stored e-mails to cluster the e-mails into multiple groups of substantially duplicate e-mails comprises:

performing duplicate detection on a received e-mail when the e-mail is received to determine if the received e-mail is a substantial duplicate of e-mails in an existing group of substantially duplicate e-mails;

adding the received e-mail to the existing group of substantially duplicate e-mails when the received e-mail is a substantial duplicate of e-mails in the existing group; and

using the received e-mail to start a new group of substantially duplicate e-mails when the received e-mail is not a substantial duplicate of e-mails in the existing group of substantially duplicate e-mails.

3. The method of claim 1 wherein analyzing the content portions of the stored e-mails to cluster the e-mails into multiple groups of substantially duplicate e-mails comprises:

performing duplicate detection on the set of stored e-mails to cluster the set of stored e-mails into groups of substantially duplicate e-mails.

4. The method of claim 1 further comprising:

receiving a new e-mail;

performing duplicate detection on the new e-mail to determine if the new e-mail is a substantial duplicate of the e-mails in the at least one stored group;

classifying the new e-mail based on the class of the one or more test e-mails when the new e-mail is a substantial duplicate of the e-mails in the at least one stored group.

5. The method of claim 1 wherein the substantially duplicate e-mails in the at least one stored group are part of a larger population of substantially duplicate e-mails, the method further comprising selecting a size for the at least one stored group such that a proportion of the e-mails in the at least one stored group belonging to a particular class accurately reflects a proportion of the e-mails in the larger population that belong to the particular class.

6. The method of claim 1 wherein selecting one or more test e-mails comprises selecting multiple test e-mails.

7. The method of claim 6 wherein classifying at least one non-test e-mail comprises classifying the at least one non-test e-mail into a particular class when a proportion of the multiple test e-mails belonging to the particular class exceeds a threshold proportion.

8. The method of claim 7 wherein selecting multiple test e-mails comprises selecting a sufficient number of test e-mails such that a proportion of the multiple test e-mails belonging to the particular class accurately reflects a proportion of the e-mails in the at least stored group that belong to the particular class.

9. The method of claim 8 wherein the particular class is spam.

10. The method of claim 9 wherein the threshold proportion is based on a misclassification cost of misclassifying spam e-mail as non-spam e-mail and a misclassification cost of misclassifying non-spam e-mail as spam e-mail.

11. The method of claim 1 wherein determining a class for the one or more test e-mails comprises determining whether the one or more e-mails are spam e-mails such that spam e-mail in the received e-mails can be filtered.

12. A computer-usable medium having a computer program embodied thereon for classifying e-mails, the computer program comprising instructions for causing a computer to perform the following operations:

receive e-mails that include a header portion and a content portion;

store the received e-mails;

analyze the content portions of the stored e-mails to cluster the stored e-mails into multiple groups of substantially duplicate e-mails;

store the multiple groups of substantially duplicate e-mails;

select one or more test e-mails from at least one of the stored groups;

determine a class for the one or more test e-mails;

classify at least one non-test e-mail in the at least stored group based on the determined class of the one or more test e-mails.

13. The computer-usable medium of claim 12 wherein, to analyze the content portion of the stored e-mails to cluster the stored e-mails into multiple groups of substantially duplicate e-mails, the computer program further comprises instruction for causing a computer to:

perform duplicate detection on a received e-mail when the e-mail is received to determine if the received e-mail is a substantial duplicate of e-mails in an existing group of substantially duplicate e-mails;

add the received e-mail to the existing group of substantially duplicate e-mails when the received e-mail is a substantial duplicate of e-mails in the existing group; and

use the received e-mail to start a new group of substantially duplicate e-mails when the received e-mail is not a substantial duplicate of e-mails in the existing group of substantially duplicate e-mails.

14. The computer-usable medium of claim 12 wherein, to analyze the content portion of the stored e-mails to cluster the stored e-mails into groups of substantially duplicate e-mails, the computer program further comprises instruction for causing a computer to:

perform duplicate detection on the set of stored e-mails to cluster the set of stored e-mails into groups of substantially duplicate e-mails.

15. The computer-usable medium of claim 12 wherein the computer program further comprises instruction for causing a computer to:

receive a new e-mail;

perform duplicate detection on the new e-mail to determine if the new e-mail is substantially identical to the e-mails in the at least one stored group;

classify the new e-mail based on the class of the one or more test e-mails when the new e-mail is substantially identical to the e-mails in the at least one stored group.

16. The computer-usable medium of claim 12 wherein the substantially duplicate e-mails in the at least one stored group are part of a larger population of substantially duplicate e-mails, the computer program further comprising instruction for causing a computer to select a size for the at least one stored group such that a proportion of the e-mails in the at least one stored group belonging to a particular class accurately reflects a proportion of the e-mails in the larger population that belong to the particular class.

17. The computer-usable medium of claim 12 wherein, to select one or more test e-mails, the computer program further comprises instruction for causing a computer to select multiple test e-mails.

18. The computer-usable medium of claim 17 wherein, to classify at least one non-test e-mail, the computer program further comprises instruction for causing a computer to classify the at least one non-test e-mail into a particular class when a proportion of the multiple test e-mails belonging to the particular class exceeds a threshold proportion.

19. The computer-usable medium of claim 18 wherein, to select multiple test e-mails, the computer program further comprises instruction for causing a computer to select a sufficient number of test e-mails such that a proportion of the multiple test e-mails belonging to the particular class accurately reflects a proportion of the e-mails in the at least one stored group that belong to the particular class.

20. The computer-usable medium of claim 19 wherein the particular class is spam.

21. The computer-usable medium of claim 20 wherein the threshold proportion is based on a misclassification cost of misclassifying spam e-mail as non-spam e-mail and a misclassification cost of misclassifying non-spam e-mail as spam e-mail.

22. The computer-usable medium of claim 12 wherein, to determine a class for the one or more test e-mails, the computer program further comprises instruction for causing a computer to determine whether the one or more e-mails are spam e-mails such that spam e-mail in the received e-mails can be filtered.