Trees of classifiers for detecting email spam

• US 7,930,353 B2
• Filed: 07/29/2005
• Issued: 04/19/2011
• Est. Priority Date: 07/29/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hulten, Geoffrey J., Rounthwaite, Robert L., Chickering, David M., Goodman, Joshua T., Meek, Christopher A., Heckerman, David E.
• Primary Examiner(s): SHIN, KYUNG H
• Application Number:
  US11/193,691
• Publication Number:
  US 20070038705A1
• Time in Patent Office: 2,090 Days
• Field of Search: 709/206, 726/22, 707/5
• US Class Current: 709/206
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

Decision trees populated with classifier models are leveraged to provide enhanced spam detection utilizing separate email classifiers for each feature of an email. This provides a higher probability of spam detection through tailoring of each classifier model to facilitate in more accurately determining spam on a feature-by-feature basis. Classifiers can be constructed based on linear models such as, for example, logistic-regression models and/or support vector machines (SVM) and the like. The classifiers can also be constructed based on decision trees. “Compound features” based on internal and/or external nodes of a decision tree can be utilized to provide linear classifier models as well. Smoothing of the spam detection results can be achieved by utilizing classifier models from other nodes within the decision tree if training data is sparse. This forms a base model for branches of a decision tree that may not have received substantial training data.

Claims

1. A system that facilitates classification of electronic mail, comprising:

a memory having stored therein computer executable components; and

a processor that executes the computer executable components that comprise;

a feature detection component configured to detect a feature of an obtained email, wherein the feature detected includes length of the obtained email;

an email classifier component configured to preprocess the obtained email by at least one of removing commented text that is invisible when reading the email or removing characters that are invisible when reading the email; and

a first decision tree including a classification component configured to classify the obtained email, the first decision tree including the classification component comprising;

a plurality of distinct email classifiers; and

a second decision tree including a feature classifier configured to select a distinct email classifier of the plurality of distinct email classifiers based at least on the feature detected in the obtained email and a subset of features from the feature classifier included in the second decision tree such that the distinct email classifier selected from the plurality of distinct email classifiers comprises an optimum email classifier for classifying the obtained email in comparison with other distinct email classifiers of the plurality of distinct email classifiers;

internal nodes of the first decision tree including the classification component correspond to the feature classifier; and

leaf nodes of the first decision tree including the classification component represent probability values of the feature associated with the plurality of distinct email classifiers compared with one or more spam confidence thresholds.

2. The system of claim 1, wherein in the first decision tree including the classification component, the classification component is configured to determine whether the obtained email is spam based at least on the distinct email classifier of the plurality of distinct email classifiers, and a classification of the obtained email comprises at least one of move, delete, or ignore when the obtained email is determined not to be spam.

3. The system of claim 1, wherein the first decision tree including the classification component uses a linear classifier, and the linear classifier comprises at least one of a logistic-regression classifier or a support vector machine (SVM).

4. The system of claim 1, wherein in the first decision tree including the classification component, the classification component smoothes a classification result of the obtained email when training data is sparse by employing a classifier that is based at least on one other classifier used in at least one other node of the first decision tree to form a base model for branches of the first decision tree lacking training data.

5. The system of claim 1, wherein the first decision tree including the classification component employs a linear classifier constructed from compound features based at least on nodes of the first decision tree.

6. The system of claim 5, wherein:

the compound features are based at least on at least one internal node of the first decision tree,

the linear classifier corresponding to an internal node of the first decision tree is trained as a function of the data relevant to the internal node,

the internal node is used to determine features of nodes below the internal node, and

a classification result of the obtained email is based at least on the classifiers within the first decision tree that are on a path from a root node of the first decision tree to a leaf node of the first decision tree.

7. A device employing the system of claim 1, comprising at least one of a computer, a server or a handheld electronic device.

8. The system of claim 1, wherein the at least one feature comprises at least one of:

a size of the obtained email,

a size of font in the obtained email,

whether a word is located in a subject line of the obtained email,

whether the word is located in a body portion of the obtained email,

whether an email has attachments,

a percentage of non-alphanumeric characters in the body portion of an email,

a percentage of non-alphanumeric characters in a subject area of an email,

a number of recipients of an email,

whether all letters of all words in a subject area or body of an email are capital letters, or

a percentage of uppercase letters making up words in the body of an email.

9. A method for facilitating classification of electronic mail, wherein the method is performed by a processor that executes acts comprising:

obtaining an email from a source as an obtained email;

preprocessing the obtained email by at least one of removing commented text that is invisible when reading the email or removing characters that are invisible when reading the email;

classifying the obtained email, via a first decision tree including a classification component comprising a decision tree of at least one feature classifier; and

selecting, using a second decision tree of classifier models including a feature classifier, a distinct email classifier of a plurality of distinct email classifiers for detecting whether the obtained email is spam, the selecting being based at least on detected features of the obtained email and a subset of the features from the feature classifier included in the second decision tree, the distinct email classifier of the plurality of distinct email classifiers being tailored as an optimum email classifier for the obtained email in comparison with other distinct email classifiers of the plurality of distinct email classifiers, and the features of the obtained email comprising at least length of the obtained email.

10. The method of claim 9, further comprising:

employing a linear model as at least one classifier of the decision tree of classifier models, the at least one classifier being based on at least one of a logistic-regression model or a support vector machine (SVM) model.

11. The method of claim 9, further comprising:

employing another decision tree as at least one classifier of the decision tree.

12. The method of claim 9, further comprising:

smoothing a detection result using a classifier model that incorporates, at least in part, another classifier model built for another node of the decision tree of classifier models.

13. The method of claim 9, further comprising:

employing at least one linear model constructed from compound features that are based on, at least in part, nodes of the decision tree of classifier models.

14. The method of claim 13, further comprising:

constructing compound features based on, at least in part, at least one internal node of the decision tree of classifier models.

15. The method of claim 14, wherein a linear classifier corresponding to an internal node of the decision tree of classifier models is trained as a function of data relevant to the internal node, the internal node being used to determine features of nodes below the internal node, and a detection result of the email being based at least on all classifiers within the decision tree of classifier models that are on a path from a root node of the decision tree of classifier models to a leaf node of the decision tree of classifier models.

16. A device employing the method of claim 9, comprising at least one of a computer, a server, or a handheld electronic device.

17. The method of claim 9, further comprising:

partitioning the obtained email based at least on a type of text, such that;

in an event the type of text of the obtained email includes HyperText Markup Language (HTML), the obtained email is, classified as a first type of email,

in an event the type of text of the obtained email does not include HTML, the obtained email is classified as a second type of email,

in an event the obtained email is classified as the second type of email and the type of text of the obtained email includes plain text, the obtained email is classified as a first sub type of the second type of email, and

in an event the obtained email is classified as the second type of email and the type of text of the obtained email does not include plain text, the obtained email is classified as a second sub type of the second type of email.

18. The method of claim 9, wherein the features of the email further comprise at least one of word choice, sender, or subject line.

19. One or more computer readable media, wherein the computer readable media is not a signal and has physical structure the computer readable media having stored therein computer executable components, the computer executable components upon execution by a processor configuring a computer to perform operations comprising:

detecting features of an obtained email, wherein at least one feature of the features of the obtained email detected includes content encoding;

classifying the obtained email, via a first decision tree including a classification component comprising a decision tree of at least one feature classifier;

selecting a distinct email classifier of a plurality of distinct email classifiers via a second decision tree including a feature classifier, the selecting being based at least on the feature detected in the obtained email and a subset of features from the feature classifier included in the second decision tree; and

classifying the obtained email based at least on the features of the obtained email and the distinct email classifier of the plurality of distinct email classifiers selected via the second decision tree, wherein;

root and interior nodes of the second decision tree comprise tests on the features of the at least one obtained email;

leaf nodes of the second decision tree are associated with the plurality of distinct email classifiers; and

the distinct email classifier of the plurality of distinct email classifiers selected via the second decision tree is tailored as an optimum email classifier for the obtained email in comparison with other distinct email classifiers of the plurality of distinct email classifiers.

20. The one or more computer readable media having physical structure of claim 19, wherein the at least one obtained email comprises HyperText Markup Language (HTML) messages or plain text messages, wherein the HTML messages are separated from the plain text messages, and wherein different filters are applied to each group of separated messages to classify obtained emails.