System and method for improving feature selection for a spam filtering model

1. Field of the Invention

This invention relates to electronic message analysis and filtering. More particularly, the invention relates to a system and method for improving a spam filtering feature set.

2. Description of the Related Art

“Spam” is commonly defined as unsolicited bulk e-mail, i.e., email that was not requested (unsolicited) and sent to multiple recipients (bulk). Although spam has been in existence for quite some time, the amount of spam transmitted over the Internet and corporate local area networks (LANs) has increased significantly in recent years. In addition, the techniques used by “spammers” (those who generate spam) have become more advanced in order to circumvent existing spam filtering products.

Spam represents more than a nuisance to corporate America. Significant costs are associated with spam including, for example, lost productivity and the additional hardware, software, and personnel required to combat the problem. In addition, many users are bothered by spam because it interferes with the amount of time they spend reading legitimate e-mail. Moreover, because spammers send spam indiscriminately, pornographic messages may show up in e-mail inboxes of workplaces and children—the latter being a crime in some jurisdictions. Recently, there has been a noticeable increase in spam advertising websites which contain child pornography. “Phishing” emails are another type of spam that request account numbers, credit card numbers and other personal information from the recipient.

1. Real-Time Spam Filtering

Various techniques currently exist for filtering spam. Specifically, FIG. 1 illustrates an exemplary spam filtering architecture which includes an email analyzer module 101 , a mathematical model module 102 and a message processing module 103 .

The email analyzer module 101 analyzes each incoming email message to determine whether the email message contains one spam-like “features.” Features used in content-based spam filters can be divided into three basic categories:

(1) Header information: Features that describe the information path followed by a message from its origin to its destinations as well as Meta information such as date, subject, Mail Transfer Agents (MTA), Mail User Agents (MUA), content types, etc.

(2) Message body contents: Features that describe the text contained in the body of an email, such as words, phrases, obfuscations, URLs, etc.

(3) Meta features: Boolean combinations of other features used to improve accuracy

Once the features of an email message have been identified, a mathematical model 102 is used to apply “weights” to each of the features. Features which are known to be a relatively better indicator of spam are given a relatively higher weight than other features. The feature weights are determined via “training” of classification algorithms such as Naïve Bayes, Logistic Regression, Neural Networks, etc. Exemplary training techniques are described below with respect to FIG. 2 .

The combined weights are then used to arrive at a spam “score.” If the score is above a specified threshold value, then the email is classified as spam and filtered out by message processing module 103 . By contrast, if the score is below the specified value, then the spam processing module forwards the email on to a user's account to the email server 104 .

2. Training

As mentioned above, the weights applied to features within the feature set are determined through a process known as “training.” Different algorithms use different methods of weight calculation including maximum entropy, error backtracking, etc. The spam model is regularly trained in order to assign weights to newly extracted features and update the weights associated with older features. Regular training helps to keep the weights of features updated according to the latest spam techniques in use.

FIG. 2 illustrates an exemplary training scenario which employs machine learning, a training technique developed by the assignee of the present patent application. See, e.g., Proofpoint MLX Whitepaper (2005), currently available at www.proofpoint.com. In this scenario, an email training corpus 200 containing known spam and ham messages is provided as a data source. A feature detection module 201 identifies features from the feature set within each email and provides this information to a machine learning module 202 . The machine learning module 202 is also told whether each message is spam or ham. Using this information, the machine learning module 202 calculates a correlation between the features and spam messages, i.e., it determines how accurately certain features identify spam/ham. As mentioned above, various machine learning algorithms may be used such as Naïve Bayes, Logistic Regression, Neural Networks, etc.

The calculations performed by the machine learning module 202 are expressed in the form of a weight file 203 which associates a weight with each of the features in the feature set. For example, features which identify spam with relatively greater accuracy (e.g., “buy Viagra”) are provided with relatively larger weights than other features (e.g., “visit online”). The weight file is subsequently used to perform spam filtering operations as described above.

3. Feature Selection

To efficiently handle the continuous introduction of new types of spam emails, it becomes vitally important to continually add new features or attributes to the model (the terms “attributes” and “features” are used interchangeably herein). One very important step to keep classifiers “healthy” and efficient is to keep track of these attributes and monitor their discriminative ability. It is essential to keep “good” (highly discriminative) attributes to ensure ongoing classification accuracy. But it is also important to discard “bad” (irrelevant or ineffective) attributes for at least the following reasons:

Bad attributes increase the error in classification, bringing down overall effectiveness. As an increasingly large number of attributes are added the complexity of model complexity grows, resulting in increased classification times, memory usage and CPU utilization. There is a risk of over-fitting the model, caused by redundant or useless attributes as the model has to over train itself to produce high accuracy on the training data due to the presence of bad features. This overtraining results in a drop in accuracy in the test data and this effect is called over-fitting.

Being able to distinguish between good and bad features is essential for ensuring the long-term effectiveness of the model. The logic behind any feature extraction in spam filtering is that the feature should occur frequently in spam messages and infrequently in ham messages and vice versa. An ideal feature would “fire” only in spam or only in ham messages. As used herein, a feature “fires” when that feature is present in an email message.

Consequently, the methods used to evaluate the quality of extracted features are extremely important to ensure both high effectiveness in identifying spam and low false positive rate. One well known example is the open source spam filter SpamAssassin (“SA”), which calculates the effectiveness of a feature using the “S/O metric.” S/O calculates feature quality by measuring the Hit Frequency, which is defined as the proportion of the spam messages in which a feature fired. For example, if a feature is present in 800 out of 1000 spam messages, then its S/O value is 0.8

Measuring the quality of features based on their S/O value biases the feature set towards “all spam” features. This method of feature selection works satisfactorily for individual spam filters where a 2-3% false positive rate is tolerable. However, enterprise-class spam filters have more stringent performance requirements. In enterprise spam solutions, designed to protect the messaging systems of large organizations with thousands of end users, even false positive rates over 0.1% result in a large amount of customer dissatisfaction.

It can be seen from the foregoing description that the effectiveness of enterprise-class spam e-mail filters relies on the quality of the feature set used by the filter's classification model. Highly effective filters may employ an extremely large number of such features (e.g., 350,000 features), which can consume a significant amount of storage space and classification time. Due to the “adversarial” nature of spam, the quality of individual features keeps changing as spam email campaigns evolve or as new campaigns emerge. Regularly discarding features which have become ineffective (“bad features”) benefits the spam filter with reduced classification time (model training time and reduced email delivery time), reduced storage requirements, increased spam detection accuracy and less risk of over-fitting of the model.

Accordingly, improved techniques for selecting beneficial features and removing inefficient features are desirable.

A system and method are described for removing ineffective features from a spam feature set. In particular, in one embodiment of the invention, the an entropy value is calculated for the feature set based on the effectiveness of the feature set at differentiating between ham and spam. Features are then removed one at a time and the entropy is recalculated. Features which increase the overall entropy are removed and features which decrease the overall entropy are retained.

In another embodiment of the invention, the value of certain type of time consuming features (e.g., rules) is determined based on both the information gain associated with the features and the time consumed implementing the features. Those features which have relatively low information gain and which consume a significant amount of time to implement are removed from the feature set.

A better understanding of the present invention can be obtained from the following detailed description in conjunction with the following drawings, in which:

FIG. 1 illustrates an architecture of an exemplary prior art email filtering system.

FIG. 2 illustrates an exemplary architecture for training using machine learning techniques.

FIG. 3 illustrates one embodiment of a method for removing inefficient features form a feature set.

FIG. 4 illustrates one embodiment of a method for evaluating features based on information gain and feature timing.

FIG. 5 illustrates an exemplary value metric graph.

Throughout the description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without some of these specific details. In other instances, well-known structures and devices are shown in block diagram form to avoid obscuring the underlying principles of the present invention.

One embodiment of the invention selects features that are indicative of ham, in addition to spam, to lower the false positive rate. These features are associated with negative weights and balance the message score Si against redundant spam features that fire in ham messages. For example, one embodiment of the invention includes a feature referred to herein as ‘X_NO_RULES_FIRED’ which fires if a particular email message does cause any spam features to fire.

Table A illustrates the inadequacy of the S/O metric in evaluating these types of “hammy” features. In this example, ‘visit online’ has a higher S/O value than ‘X_NO_RULES_FIRED’ irrespective of the fact that ‘visit online’ fires equally in both spam and ham messages and hence has no discrimination ability. The ‘X_NO_RULES_FIRED’ feature is a good ham feature which will decrease the false positive rate whereas ‘visit online’ is a non-discriminative feature which will increase the false positive rate.

To address the inadequacy of prior feature selection techniques, one embodiment of the invention uses “Information Gain” (IG) techniques for feature selection in a pre-processing stage before training. Specifically, IG is used to determine the quality of a feature based on the number of times the feature fires in a particular class of message. The aim is to maintain features that fire frequently in one class (spam/ham) of message and therefore have high information gain.

FIG. 3 provides a high level overview of this embodiment of the invention in which the importance of a feature is measured as an expected reduction in entropy of the model due to an attribute. Entropy represents a level of randomness. Thus, if the randomness of the model decreases when a feature is removed, then that feature does not effectively differentiate between ham/spam, and should be removed from the feature set. A more detailed mathematical analysis is provided following the description of the process in FIG. 3 .

Turning now to the process, at 301 , the entropy of the current feature set is calculated using known techniques (see, e.g., the entropy equations below). At 302 , variable i is set to 1 and, at 303 , a first feature F i is removed from the feature set. At 304 , the entropy of the model is recalculated without the first feature. If the entropy decreases, determined at 305 , then the feature F; is permanently removed from the spam feature set at 307 . If, however, the entropy increases, then F i is retained in the feature set at 306 . To determine whether the entropy increases or decreases, the entropy of the full feature set may be subtracted from the entropy of the feature set without feature F i . As mentioned above, the reason for removing a feature which increases entropy of the model is that the entropy value represents a level of randomness. If entropy increases, then the model becomes more random, meaning that it is less effective at differentiating between ham and spam. At 308 , the variable i is increased by 1 and, unless F i is the last feature, determined at 309 , the process repeats from 303 with the new feature.

Having described the underlying principles of one embodiment of the invention with respect to FIG. 3 , additional details associated with the feature selection process will now be presented. As mentioned above, information gain measures the importance of a feature as an expected reduction in entropy of the model due to an attribute. Generally, for a training set S that consists of positive and negative examples of some target concept, the information gain of an attribute A that can take values from value(A) is given by

IG ( S,A )=Entropy( S )−Σ vεvalue(A) (| S v |/|S |)Entropy( S V )

S v is the subset of S for which attribute A has value v (i.e., S v ={sεS|A(s)=v}). For a given training set S, the Entropy is defined as

Entropy( S )=Σ iεClass −p i log 2 p i

Within the context of a spam filtering feature set, IG is used to judge the quality of a feature based on the number of times the feature fires in a particular class of message. The aim is to maintain features that fire frequently in one class (spam/ham) of message and hence should have high information gain. Consequently, the features that either fire less frequently or fire in both spam and ham will have low IG. This section explains the way IG is calculated for the spam model.

Let N T be the total number of messages, N H be the ham messages and N S be the spam messages in the training corpora. Let a feature be represented as F i . Let N Hi be the number of ham messages in which feature F i fires and let N Si be the number of spam messages in which feature F i fires. N Ti represents the total messages in which F i fires and is given by

N Ti =N Si +N Hi

Similarly N′ Hi and N′ Si are the ham and spam messages in which feature F i did not fire. N′ Ti is the total messages in which F i did not fire and is given by

N′ Ti =N′ Si +N′ Hi

Let H(S) be the total entropy of the training corpora and is given by

H ( S )=−( N S /N T )log 2 ( N S /N T )−( N H /N T )log 2 ( N H /N T )

H(F i ) is the entropy of messages in which feature F i fired and H′(F i ) is the entropy of messages in which feature did not fire. These are formulated as

H ( F i )=−( N Hi /N Ti )log 2 ( N Hi /N Ti )−( N Si /N Ti )log 2 ( N Si /N Ti )

H ′( F i )=−( N′ Hi /N′ Ti )log 2 ( N′ Hi /N′ Ti )− N′ Si /N′ Ti log 2 ( N′ Si /N′ Ti )

IG(F i ) is the information Gain of feature F i and is calculated as

IG ( F i )= H ( S )−( N Ti /N T ) H ( F i )−( N′ Ti /N T ) H ′( F i )

The value of IG for a feature varies between 0 and 1. In one embodiment of the invention, if the IG of a feature is less than a predefined threshold, the feature is considered to be useless and is discarded from the feature set. The threshold is usually based on the overall accuracy of the model.

In addition to the foregoing feature selection process, one embodiment of the invention evaluates the timing cost for certain types of time-consuming features such as “rules” to determine if the feature should be removed from the model. “Rules” are meta-features that exploit similarities in the spam messages for classification. These meta-features fire when some predefined condition is satisfied in a message (e.g., Buy Rolex OR Online Store OR Cheap OR Click Here). This meta-feature is a combination of four features: Rolex, Online Store, Cheap and Click Here. These features independently are not a good representation of spam but their combination in a rule makes them a useful feature. Another example of a rule is X_NO_RULES_FIRED, described above.

Rules are the most time consuming features used in the spam classification process. In one embodiment of the invention, rules that take an inordinately long amount of time and have relatively low discrimination capability are discarded, resulting in a logical tradeoff between timing cost and IG for a faster and safer spam processing system.

In one embodiment, timing cost of a feature is measured by sampling the system clock before and after each feature is evaluated, and then calculating the difference in time. For each feature the sum of times across all messages in the training corpora is collected.

FIG. 4 illustrates one embodiment of a process for factoring in timing cost using a “rule value metric”—a value representing the tradeoff between the timing cost of rules (and/or other time-consuming features) and their information gain. At 401 , the IG associated with the rule is calculated using, for example, the IG techniques described above. If the IG is above a specified threshold value, determined at 402 , then, at 403 , the rule value metric is set above a value metric threshold (in effect, retaining the rule regardless of its timing cost). In one embodiment of the invention, this means setting the value metric equal to the IG value.

If the IG is below a specified threshold value, determined at 404 , then, at 405 , the rule value metric is set below the value metric threshold value (in effect, removing the rule regardless of its timing cost). In one embodiment of the invention, this means setting the value metric equal to −1.

If the IG of the rule is between the first threshold IG threshold and the second IG threshold values, then at 406 , the value metric is calculated based on the IG value and a timing cost value associated with the rule (which indicates the time consumed to implement the rule). In one embodiment of the invention, the value metric is calculated by subtracting a normalized timing cost value with a normalized IG value.

If the value metric is below the value metric threshold, determined at 407 , then the rule is removed from the model at 408 . If, however, the value metric is above the value metric threshold, then the rule is retained in the model at 409 .

Additional mathematical details associated with one embodiment of the invention will now be provided. We assume a set of rule R as a subset of feature space. Let R i any rule that belongs to R. Let IG be the set of information gain of the corresponding elements in R and similarly T be the set of the timing cost of the corresponding rules. Let IG i be the value of information gain and T i be the value of the timing cost for any rule R i . The value metric of any rule R i is represented as V i .

The functions max(S) and min(S) return the maximum and minimum element of a set of real numbers S, respectively. Using these functions, the maximum and minimum elements of set IG and T may be found.

max IG =max( IG )

min IG =min( IG )

max T =max( T )

min T =min( T )

Let nIG i and nT i be the normalized value of the i th element of IG and T. This is calculated as:

nIG i =( IG i −min IG )/(max IG −min IG )

nT i =( T i −min T )/(max T −min t )

The value metric V i is then calculated as:

V i = { ⁢ IGi ⁢ if ⁢ ⁢ IG i > 0.002 ⁢ n ⁢ I ⁢ G i - nT i ⁢ if ⁢ ⁢ 0.002 < IG i < 1.0 ⁢ e - 09 ⁢ - 1 ⁢ if ⁢ ⁢ IG i < 1.0 ⁢ e - 09

A line chart of the value metrics of rules used in one exemplary test are illustrated in FIG. 5 . The features that form the negative spikes below the value metric threshold in FIG. 5 are removed. In one embodiment of the invention, the threshold of the value metric is set to −0.005 for accuracy reasons.

While the embodiments described above focus on evaluating “rules” based on a calculated value metric, it should be noted that the underlying principles of the invention are not limited to “rules.” In fact, the underlying principles of the invention may be used to evaluate any type of time-consuming spam features within a feature set.

Embodiments of the invention may include various steps as set forth above. The steps may be embodied in machine-executable instructions which cause a general-purpose or special-purpose computer processor to perform certain steps. Alternatively, these steps may be performed by specific hardware components that contain hardwired logic for performing the steps, or by any combination of programmed computer components and custom hardware components.

Elements of the present invention may also be provided as a machine-readable medium for storing the machine-executable instructions. The machine-readable medium may include, but is not limited to, floppy diskettes, optical disks, CD-ROMs, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, magnetic or optical cards, or other type of media/machine-readable medium suitable for storing electronic instructions.

Throughout the foregoing description, for the purposes of explanation, numerous specific details were set forth in order to provide a thorough understanding of the invention. It will be apparent, however, to one skilled in the art that the invention may be practiced without some of these specific details. For example, although some embodiments described above use changes in entropy to determine whether a feature should be removed from a feature set, the underlying principles of the invention may be implemented in the context of virtually any technique for evaluating the randomness of a model. Moreover, the underlying principles of the invention may be implemented within virtually any time of computing platform including standard personal computer configurations and server configurations.

Accordingly, the scope and spirit of the invention should be judged in terms of the claims which follow.