Group based spam classification
View Patent ↗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.
1. A method of classifying e-mails, the method comprising:
receiving a plurality of e-mails that each include a respective header portion and content portion;
storing the received plurality of e-mails;
analyzing, using at least one processor, the content portions of the stored plurality of e-mails to cluster the plurality of e-mails into multiple groups of substantially duplicate e-mails;
storing the multiple groups of substantially duplicate e-mails;
selecting a test e-mail from a group of the stored multiple groups;
determining a class for the test email based on the content portion of the test e-mail; and
classifying a non-test e-mail in the group based on the determined class of the test e-mail.
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 plurality of e-mails to cluster the plurality of e-mails into multiple groups of substantially duplicate e-mails comprises:
performing duplicate detection on a set of stored plurality of e-mails to cluster the set of stored plurality of 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 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 group.
5. The method of claim 1 wherein the substantially duplicate e-mails in the group are part of a larger population of substantially duplicate e-mails, the method further comprising selecting a size for the group such that a proportion of the e-mails in the 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 further comprising:
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 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 test e-mail comprises determining whether the e-mail is a spam e-mail such that spam e-mail in the received e-mails can be filtered.
12. A non-transitory computer-usable storage medium having a computer program embodied thereon for classifying e-mails, the computer program comprising instructions for causing at least one processor to perform the following operations:
receive a plurality of e-mails that each include a respective header portion and content portion;
store the received plurality of e-mails;
analyze the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate e-mails;
store the multiple groups of substantially duplicate e-mails;
select a test e-mail from a group of the stored multiple groups;
determine a class for the test e-mail based on the content portion of the test e-mail; and
classify a non-test e-mail in the group based on the determined class of the test e-mail.
13. The computer-usable storage medium of claim 12 wherein, to analyze the content portion of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate e-mails, the computer program further comprises instructions for causing to the at least one processor 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 storage medium of claim 12 wherein, to analyze the content portion of the stored plurality of e-mails to cluster the stored plurality of e-mails into groups of substantially duplicate e-mails, the computer program further comprises instructions for causing the at least one processor 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 instructions for causing the at least one processor 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 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 group.
16. The computer-usable storage medium of claim 12 wherein the substantially duplicate e-mails in the group are part of a larger population of substantially duplicate e-mails, the computer program further comprising instructions for causing the at least one processor to select a size for the 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 storage medium of claim 12 wherein the computer program further comprises instructions for causing the at least one processor to select multiple test e-mails.
18. The computer-usable storage medium of claim 17 wherein, to classify at least one non-test e-mail, the computer program further comprises instructions for causing the at least one processor 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 storage medium of claim 18 wherein, to select multiple test e-mails, the computer program further comprises instructions for causing the at least one processor 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 one stored group that belong to the particular class.
20. The computer-usable storage medium of claim 19 wherein the particular class is spam.
21. The computer-usable storage 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 storage medium of claim 12 wherein, to determine a class for the test e-mail, the computer program further comprises instructions for causing the at least one processor to determine whether the e-mail is a spam e-mail such that spam e-mail in the received e-mails can be filtered.
23. The method of claim 1 , wherein analyzing the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate emails comprises:
determining hash representations of the stored plurality of e-mails; and
clustering the stored plurality of e-mails into multiple groups based on the determined hash representations.
24. The method of claim 1 , wherein analyzing the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate emails comprises:
comparing attributes of the stored plurality of e-mails to a predetermined set of attributes;
determining fingerprints for the stored plurality of e-mails based on the comparison; and
clustering the stored plurality of e-mails into multiple groups based on the determined fingerprints.
25. The computer-usable storage medium of claim 12 , wherein the instructions for causing the computer to analyze the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate e-mails comprise instructions for causing the at least one processor to:
determine hash representations of the stored plurality of e-mails; and
cluster the stored plurality of e-mails into multiple groups based on the determined hash representations.
26. The computer-usable storage medium of claim 12 , wherein the instructions for causing the computer to analyze the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate e-mails comprise instructions for causing the at least one processor to:
compare attributes of the stored plurality of e-mails to a predetermined set of attributes;
determine fingerprints for the stored plurality of e-mails based on the comparison; and
cluster the stored plurality of e-mails into multiple groups based on the determined fingerprints.