Bayesian Spam Filter - Felix John COLIBRI.

• abstract : presentation and implementation of a spam elimination tool which uses Bayesian Filtering techniques
  
• key words : tutorial - machine learning - text classifier - Bayes - spam filter - string hash table - iterator - bounded insert sort
  
• software used : Windows XP Home, Delphi 6
  
• hardware used : Pentium 2.800Mhz, 512 M memory, 140 G hard disc
  
• scope : Delphi 1 to 2006, Turbo Delphi for Windows, Kylix
  Delphi 5, 6, 7, 8 Delphi 2005, 2006, Turbo Delphi, Turbo 2007, Rad Studio 2007
  
• level : Delphi developer
  
• plan :
  
  • E-mail Spam Removal
    
  • Spam Elimination
    
  • Paul GRAHAM's Bayes Spam Filter
    
  • The Delphi Implementation of the Bayes classifier
    
  • Download the Sources of the Spam Filter
    

1 - E-mail Spam Removal

2 - Spam Elimination

2.1 - Spam Definition

The problem is how can we sort those mails in two parts: the spam and the "good" mail.

We caracterize spam as

• unsolicited e-mails unrelated to our domains of interest. These include:
  
  • porn text
    
  • sales pitches about many popular topics:
    
    • pharmaceuticals
      
    • medical treatments, health, age, fitness improvement program
      
    • stock market information (gold or whatever)
      
    • luxury goods (watches, fashion articles)
      
  • contacts supposed to make us richer quickly
    
    • ponzi schemes (= pyramids)
      
    • lottery gains
      
    • offers to transfer money of some african colonel who suddenly died in some accident leaving huge piles of unspent dough somewhere
      
  • phishing (enquiries to send our bank or credit card pin or passwords because of some supposed security risks)
    
  • advertising for some products
    
    • computer sales, printer toner
      
    • OEM software, "legal" discounted software
      
    • printer offers for printing visit cards, posters, books
      
    • offers for building web sites (well, well, well ...)
      
    • offers to tune, improve or otherwise reference our web sites
      
• text linking to web site with any of the previous content
  

• orders or enquiries for trainings, Delphi developments or programming consulting
  
• contacts from other developers, whether for comments about our articles, help requests, references to similar topics
  
• news letter subscription (David Intersimone, Joel on Software, Jot)
  
• on our personal mailbox, family, friends or old school buddies e-mails
  
• for all the products we ordered (for instance Amazon), feedback (delivery notices, advertising about similar products). On the other hand, continued advertising flood from a used car sales site where we happened to once tried to sell our old car are not welcome. In the middle, we want our travel agency's ticket notifications, but not their constant advertising.
  

2.2 - To remove or not to remove

Automatic spam removal's goal is to automatically eliminate the spam, and let you concentrate on the "good" mail.

100 % spam filtering is not possible: some e-mails are in a gray area (are aggressive promotion from a company we ordered some product from spam or not) and some e-mails generally considered as spam might not be (an order form a pharmaceutical company).

The best we can do therefore is to eliminate, with some error margin, the spam.

The main problem in spam removal, which is severe, is to guarantee never to remove any legitimate mail. We would prefer to read many pharmaceutical junk mails and perhaps find one day a business request among them, rather than throw them all away.

2.3 - Spam Removal Techniques

• sender (name or URL) blacklists, coupled with "friendly" lists
  
• sheer size of the e-mail
  
• filtering out the spam by analyzing the text of the e-mail
  

E-mail size could eliminate some pictures, viruses or random huge texts, but we also sometimes receive photographs from friends, .ZIP attachments or screen captures from our customers. So this is also not an option.

The filtering based on the content of the e-mail therefore looks like the best candidate. We can analyze

• the e-mail headers (for instance the "To", the "Subject")
  
• the text, if any, in standard Notepad format or .HTML format
  
• the type and content of any attachments
  

To analyze the content, you have to extract the tokens and classify the e-mail based on this token list.

2.4 - Content Filtering

Our first approach was to build a database of tokens which always indicate spam. No customer ever contacted us with e-mail containing blatent porn tokens (maybe a friend with some jokes, but if we miss those it would not be catastrophic, and they could also be saved by looking up a "friendly" sender list). So, over time, and with regular updates, we did build a list of all the "spam words", and the mere presence of one of those tokens allowed us to classify the e-mail as "spam", "maybe spam", "good". This simple one word test allowed us to eliminate 30 % of our e-mail which were spam, but we still had to look at the "maybe" cases (around 65 %) to make sure we did not miss a "good" mail.

We certainly could have improved this "one bad world" check by using several words and some boolean expression ("xxx" AND "yyy" OR "uuu" AND NOT "ttt"). In fact we have published a textual analyzer implementing such a boolean content analysis.

2.5 - Text Classification

• given two historical sets of texts, build a piece of software which decides how to classify any of those texts in our categories

• when a new text comes in, determine to which category it belongs

• we split the historical sets in two parts, the learning sets and the test sets:

• the classifier is trained (parametrized) using the learning set:

• we validate (check, adjust) our model using the test set

• finally we use the classifier to filter spam:

• KNN (k Nearest Neighbours)
  
• Artificial Neural Networks
  
• Genetic Programming
  
• Simmulated Annealing
  
• Support Vector Machine
  
• Bayesian Classification
  

3 - Paul GRAHAM's Bayes Spam Filter

3.1 - The Algorithm

• manually classify your previous mails in two categories: spam and good:

  In each category, e-mails contain words which are

  • spam ("sex", "casino" ...), in red in the figure below
    
  • good ("training", "order", "delphi" ...), in green
    
  • neutral ("hello", "regards" ...)
    
    

  Notice that there usually are

  • some "good" words in the spam corpus (a spam with "order")
    
  • and some "spam" words in the good corpus (a friend's joke with "sex")
    
    
• for those two categories, build the list of their tokens (= words) and count their frequencies

• build the list of all tokens (spam an good) and compute the probability that a token is a spam token

• build the token list of this e-mail:

• using the token spam probability list, compute the spam probability of each token or this e-mail, and then compute a combined index of being spam

3.2 - Bayes Text Classification

From a more formal point of view

• let's assume that we have a population with e-mails wich are spam or ok e-mail

• In this population, there is also a distribution of "bad words" (in red):

• from those facts, we can compute
  
  • the probability of spam mails, P(spam) : 0.67
    
  • the probability of ok mails, P(ok) : 0.33

  • the probability of bad words, when we know that we are in the spam area, P(bad | spam) : 6/(6+1)= 0.86
    
  • the probability of bad words when we know that we are in the ok area, P(bad | ok) : 1/(6 1) = 0.14
    
  • the probability of bad words P(bad) : .47
    
  And, the main point, as stated by the Bayes theorem, the probability that a mail is spam when we know that it contains bad words:

  P(spam | bad) = P(bad | spam) * P(spam)         / ( P(bad | spam) * P(spam) + P(bad | ok)* P(ok) )

  or .86 * .67 / ( .86 * .67+ .14* .33), which is .93
  

3.3 - GRAHAM's Algorithm

Here are the steps:

• compute the frequency lists of both spam and ok mails
  
• build the list of all tokens, and compute a spam probability with the following steps:
  • if the occurence of a token in both sets is less than 6, discard this token
    
  • if the token belongs to the ok mails only (not to any spam mail), set its spam probability to 0.1
    
  • if the token belongs to the spam mails only (not to any ok mail), set its probability to 0.9
    
  • in the other cases, set the probability to

    ok_factor:= ok_frequency / ok_e_mail_count; spam_factor:= spam_frequency / spam_e_mail_count; probability:= spam_factor / (ok_factor + spam_factor);

    
    
• to classify an e-mail
  
  • compute its token list (frequencies are apparently not used)
    
  • compute the 15 "more interesting" spam probabilities. To do so
    
    • for each token t
      
      • compute the spam probability of each token in the previous list, using the corpus spam probability list p
        
      • the "interesting" factor computes the distance from 0.5 (to only keep the lowest and highest probabilities). The computation uses

        i = Abs( 0.5- p )

      • only keep the 15 highest "interesting" factors
        
  • combine those "interesting" factors to create a spam indicator.

    If a, b, c ... are the "intersting" factors, the indicator is:

    indicator:= abc / ( abc + (1 - a)(1 - b)(1 - c) )

    
    

• to bias the computation to avoid missing ok e-mails, the ok frequency is multiplied by 2 when we compute the spam probability
  
• when a token is only in the spam corpus, we can set increased probabilities if there are many of those tokens. For instance 0.9 for small frequencies, 0.99 for frequencies greater than 10.
  

• the denominator of the probability computations are the spam or e-mail counts (and NOT the token counts. It is assumed that spam tokens are repetitive, and using e-mail counts tilts the balance in favor of ok e-mails
  
• the use of a minimum 0.1 and maximum 0.9 avoids that a single token dominates the composite indicator computation (0 would influence the abc... value, and 1 the (1-a)... value)
  

4 - The Delphi Implementation of the Bayes classifier

4.1 - The Steps and Structures

• from our e-mail 2 kind of mail history, build the token frequency list, and then the spam probability list
  
• for each mail extract its token list and compute a composite spam ratio of this e-mail
  

4.2 - Build a collection of spam and good mail

It can only be done by visual inspection, since we assume that no tool is available to do the job for us. In addition, no automatic tool can do it for us, since the kind of spam we receive, and what WE consider as "good" is a matter of self judgement.

Either both collections already exist, or we have to start creating such a list (saving each incoming mail in one or the other collection), and we only start the other steps when we have a substantial corpus of manually categorized mails. In our case, we started in January 2008 and implemented the spam filter in March.

In our implementation, each e-mail is a .TXT file, and they are saved in two separate folders, SPAM\ and GOOD\. We accumulated around 5,700 spam mails, and 1,900 ok mails.

4.3 - Tokenizing the spam and good archives

To do so

• we load the text into a buffer
  
• we use 2 basic loops
  
  • the first loop skips the characters we consider as separators: spaces, new lines, brackets etc
    
  • the second loop accumulates all characters considered as part of a token, until we hit a separator or the end of the text
    

• a first one which scans everything
  
• a more elaborate parser which takes the structure of e-mail into account.
  

• letters, digits, underscores as belonging to tokens
  
• all other characters as separators
  

The raw token extraction is:

If we want to take into account that the texts are e-mails, we first assume that it has the following structure:

• POP3 headers (TO, FROM, SUBJECT, DATE etc)
  
• a blank line
  
• a combination of
  
  • ASCII text
    
  • .HTML text
    
  • uuEncoded text
    
  • possibly with multipart Mime structure, with some of the following Content-Types
    • text/plain
      
    • text/html
      
    • image
      
    • application
      
  The textual parts may contain Mime encoding (=HH for coding non-english characters), and line breaks (= followed by Return LineFeed, to keep the lines shorter than 72 characters)
  

• for =HH (hex digits: 0..9, A..F), we simply include them in the token (assuming that when a token contains some =HH, this will be the case for all e-mails)
  
• for =RL, we remove them if they occur in the middle of some token
  

4.4 - Building the Token frequency list

4.4.1 - Requirements

• store (string, integer) values in memory
  
• for each new token, lookup for the list to check whether a string already exists, and increment the frequencies if this is the case. This involves searching the list for an entry
  
• eventually after the analysis, persist this structure on disc to be able to avoid reanalyzing the training set each time we want to filter new mail
  

4.4.2 - The Delphi String Hash Table

and

• each hash cell contains the string and the frequency (plus the probability which is used for the spam probability list)
  
• those cells are stored in buckets, where hash cells are added when no entry exists for this string
  
• the hash table
  
  • builds a predefined number of buckets
    
  • uses f_string_hash_value to compute the hash bucket. Any string hash function will do (CRC, ELF or whatever)
    
  • calls f_pt_add_hash_data to create a new entry with frequency 1 or increment the frequency by 1
    
  • uses f_pt_search_hash_data return the data cell or NIL if no such cell exists. The FUNCTION is used to check whether an entry already exists or to retrieve a cell when we later use the hash table
    

So this is just a minimal hash table, and in fact it accelerated the computation compared to our first tStringList trial.

4.4.3 - Building token frequency lists

• create the token frequency list
  
• create a scanner and load the text
  
• while there are tokens in the text, add those tokens to the list, either creating a new token with frequency 1 or incrementing the frequency for some already entered token.
  

• for analyzing each spam or ok mail. In this case
  
  • for spam, the list is created first, and we iterate thru the corpus spam mails, to scan and add the mail tokens to the spam token frequency list
    
  • same technique for the ok mails
    
• for analyzing each new mail. A new list is then created and filled only for this mail
  

4.5 - The token spam probability list

4.5.1 - The algorithm

Each entry in this list is spam only, good only or both spam and good. One way to build this list is the following:

• start with one list, say good
  
• for each token in this first list
  
  • get its frequency
    
  • look up the other list and get its frequency
    
  • then combine the frequencies to compute the probability
    
• take the other list, say spam
  
• for each token
  
  • if this token does not belong to the first list (ie has not been handled), then add an entry with a 1.0 probability
    

4.5.2 - The spam probability list requirements

We could have build a specific (String, Double) hash table, but we chose to recycle the previous string hash table, adding a Double field just for this spam probability list.

4.6 - The c_bayes_spam_filter CLASS

4.6.1 - The CLASS definition

and:

• m_e_mail_scanning allows to select either raw scanning (all text) or mail scanning (only content, and after some MIME decoding)
  
• m_c_ok_hash_token_frequency_list and m_c_spam_hash_token_frequency_list will contain the token frequencies from our two training sets
  
• m_c_spam_token_probability_list is the training token spam probability list
  
• _add_raw_tokens and _add_e_mail_file_tokens are helper function for building raw or e-mail frequency lists

• add_file_tokens is called to add the frequencies of each mail from the training sets:

  procedure c_bayes_spam_filter.add_file_tokens(p_full_file_name: string;     p_is_spam: Boolean);   begin     with c_mail_scanner.create_mail_scanner('', m_token_length_min) do     begin       f_load_from_file(p_full_file_name);       if m_e_mail_scanning         then _add_e_mail_file_tokens(f_c_self, Nil, p_is_spam)         else _add_raw_tokens(f_c_self, Nil, p_is_spam);       Free;     end; // with c_mail_scanner   end; // add_file_tokens

• compute_spam_probabilities does just what the name indicates:

  procedure c_bayes_spam_filter.compute_spam_probabilities;   procedure compute_token_probability(p_token: String;       p_ok_frequency, p_spam_frequency: Integer);     var l_ok_frequency, l_spam_frequency: Integer;         l_ok_factor, l_spam_factor, l_probability: Double;     begin        l_ok_frequency:= p_ok_frequency* m_ok_token_weight;        l_spam_frequency:= p_spam_frequency;        // -- only compute if has found significant occurences in the        // --   spam+ ok corpus        if l_ok_frequency + l_spam_frequency >= m_min_token_count         then begin             if l_spam_frequency= 0               then l_probability:= m_score_min               else                 if l_ok_frequency= 0                   then begin                       // -- special case for Spam-only tokens.                       // --   - 0.9998 for tokens only found in spam,                       // --   - 0.9999 if found more than 10 times                       if l_spam_frequency > m_certain_spam_count                         then l_probability:= m_certain_spam_score                         else l_probability:= m_likely_spam_score;                     end                   else begin                       // -- in both spam and ok sets                       l_ok_factor:= l_ok_frequency / m_ok_e_mail_count;                       l_spam_factor:= l_spam_frequency / m_spam_e_mail_count;                       l_probability:= l_spam_factor / (l_ok_factor + l_spam_factor);                     end;             // -- now add the probability entry             // -- include the total occurence, only for analysis             m_c_spam_token_probability_list.f_pt_add_hash_probability_data(p_token,                 l_ok_frequency + l_spam_frequency, l_probability);           end; // occured more than 5 time     end; // compute_token_probability   var l_ok_token, l_spam_token: String;       l_pt_spam_hash_data: t_pt_hash_data;       l_ok_frequency, l_spam_frequency: Integer;   begin // compute_spam_probabilities     m_c_spam_token_probability_list.Free;     m_c_spam_token_probability_list:= c_hash_table.create_hash_table('');     with c_hash_iterator.create_hash_iterator('',         m_c_ok_hash_token_frequency_list) do     begin       while f_move_next do         with f_pt_current_hash_data^ do         begin           l_ok_frequency:= m_hash_frequency;           l_ok_token:= m_hash_string;           // -- find out if this token also has a spam value           l_pt_spam_hash_data:=               m_c_spam_hash_token_frequency_list.f_pt_search_hash_data(l_ok_token);           if l_pt_spam_hash_data<> nil             then l_spam_frequency:= l_pt_spam_hash_data.m_hash_frequency             else l_spam_frequency:= 0;           compute_token_probability(l_ok_token, l_ok_frequency, l_spam_frequency);         end; // while f_move_next       Free;     end; // with c_hash_iterator.create_hash_iterator     with c_hash_iterator.create_hash_iterator('',         m_c_spam_hash_token_frequency_list) do     begin       while f_move_next do         with f_pt_current_hash_data^ do         begin           // -- eliminate what was added while browsing the "ok" list           l_spam_token:= m_hash_string;           if m_c_ok_hash_token_frequency_list.f_pt_search_hash_data(l_spam_token)= Nil             then begin                 l_spam_frequency:= m_hash_frequency;                 compute_token_probability(l_spam_token, 0, l_spam_frequency);               end;         end; // while f_move_next       Free;     end; // with c_hash_iterator.create_hash_iterator   end; // compute_spam_probabilities

• f_test_mail is used to compute the composite spam coefficient of any mail. Before presenting the code, we will show our "most interesting" structure
  

4.6.2 - Computing the 15 most interesting values

This involves extracting the top 15 values in a list of Double.

We first used a sorted tStringList, converting the Doubles into formatted strings. Feeling that this conversion was not efficient, we then used a binary tree, sorted on the double value. Because the tree keeps all the values, we changed again to use an array limited to 15 values, wich is sorted to easily keep track of the lowest value.

This is not the most interesting part of the code (pun intended), but here it is:

4.6.3 - Testing a new mail

We must

• build the frequency list for this text
  
• compute the array of the 15 most interesting values
  
• merge those values into a composite index
  

4.7 - The main project

• we use our usual DirectoryListbox / tFileListBox to select the files. Spam training mails are located in a SPAM\ folder, ok training mails in OK\, spam testing mails in TEST_SPAM\ and ok testing mails in TEST_OK\
  
• the "compute" button analyzes the files in the training folders. A proportion of those files is not included, but copied instead in the test folders
  
• the "compute_probabilities_" computes the token spam probability list. The result may be examined in a tMemo
  
• the "test_ok_mail_" and "test_spam_mail_" buttons analyze the mails kept for testing. The result is displayed in a tListBox on the right, and clicking on the listbox displays
  • the most interesting tokens with their probabilities
    
  • the raw mail, the content text and .html, the full token list
    

After clicking "test_spam_mail" this becomes:

where the first column is the composite index, followed by the e-mail file name.

We can check the tokens of an e-mail to get some explanation why some mail is considered as spam, by clicking on this item in the tListBox :

Well, this sure explains it ! More seriously, notice that

• the list is presented in "interesting order", which means the most away from the .5 value come first. The spam probabilities are also displayed.
  
• "inches" is the highest on the spam probability list (nobody ever wrote us to order "inches", or comment about "inches". On the other hand ... )
  
• some are in between : "increase" (could be the increase of an order quote) or "pleasure" (like "my pleasure" maybe)
  
• "sexdrive" and other dubiouos tokens are in the middle and were assigned the modest default .40 value, because they were neither in the bad nor in the ok training sets
  

• the raw e-mail content
  
• the ASCII and .HTML parts (no headers, no binary attachment)
  
• the token list (sorted by frequency or alphabetically)
  

4.8 - Mini HowTo

and:

• (1) is the tDirectoryListbox containing the sub folders with all our e-mail files
  
• (2 ) allows to limit the number of files to include in the training phase, -1 for "all files"
  
• (3) is the training / test ratio. "80" means 1 out of 80 files will be kept for testing
  
• (4) is the tFileListBox where we can display the files of some folder. Clicking on one of them will analyze it (.HTML extraction and token frequencies) and display in the right "parse_mail_" tab
  
• (5) starts the training. The result (file count, token count, time) is displayed in the "result_" tab on the right
  
• (6) allows to toggle between raw scanning and .HTML scanning
  
• "compute_probability_" will create the token spam probability list
  
• (7) is used to specify how many token probabilities are kept for the final computation
  
• (8) will test all the ok mail (spam mail, any other mail). The list or the results appears in "result_" on the right, with a tListbox. Clicking one of the items will display its token list with their probabilities
  

4.9 - The Results

• our training database consists of 5,700 spam mails and 1,900 ok mails, with 75,000 and 46,000 token
  
• training took 1 minute on a freshly booted PC (2.8 Meg clock, 512 Meg memory), and 10 seconds for the next trials (due to the cache)
  
• on 163 ok test mails, 1 was at 0.006 (a two line congratulation mail), the rest at 0 (1e-7)
  
• on 152 spam test mails
  
  • 105 were at more than 0.96
    
  • 15 between 0.96 and 0.10
    
  • 31 near 0
    

• we had no ok mail considered as spam
  
• we still need to read 46 mails only to throw them out as spam
  

As usual, the nice thing of having a Delphi project (versus a shrink wrapped spam filter) is that it allows us to accumulate all kinds of statistics in order optimize spam elimination, and in addition we can include it in our mail POP3 downloader and mail viewer suite.

5 - Improvements, Implementation and Comments

5.1 - Downloading Mail

This e-mail files approach nicely fit with the filter learning, since we had kept enough spam (fearing to have missed some ok mail) to train the Bayes filter.

Nevertheless, many users do not use this two step approach (download with one software and read the files with another). So it would be nice to tie the filter to Outlook or any other popular downloader / reader. This has been done with some spam filtering projects like SpamAssassin. We will not investigate this further, unless some customer asks us to do it.

Notice that coupling the Bayesian filter with Indy (or ICS, Synapse or whatever) POP3 mail clients should not be very difficult.

5.1.1 - The Options

Among the possibilities

• increase the minimum token length. Because of uuEncoded text, our one word filter did not check for tokens smaller than 6 characters. The "sex" or "xanax" combination can be present in any uuEncoded text (this is a bitter memory since we once missed an order because of this).

  With the .HTML scanner presented here, we would not scan the uuEncoded text, and could well include 3 characters spam ("sex"), 4 character ones ("loan", "cock") or 5 character ones ("stock", "watch", "gucci", "cialis")

• we could also build a case for splitting, or even eliminating from the analysis, too long tokens. In our case, they occured when we scanned uuEncoded text which was not included in a MIME multipart. Decoding uuEncoded text would remove this option

• for our "1 token filter", and for the first trials of the Bayesian filter, we used to scan the full text. We then realized that most mails are rather short. In our case, when we send mail, we use only ASCII text (no .HTML monkeing), and 30 or 40 lines max. The average in our training set is around 3100 bytes. Spam on the other hand is rather bulky. Our training spam set's mean size is near 19,300 bytes. This is not a surprise, since spam often contains attached images, binary viruses or whatever MIME encoded stuff.

  To reduce the development time, we first limited the analyzed text to 4 K. It turned out that this is even more than our .HTML parser analyzes (he only looks at "text/plain" and "text/html", and quits at the first occurence of an "image" or other multipart.

  But you might change this 4 K scanner limit.
  

5.1.2 - Which tokens should we use

Among the other possibilities, we can mention

• add "!" and "?" when they are present at the end of a token ("free!!!"). This catches many otherwise innocuous tokens, but multiplies the tokens ("free", "free!", "free!!" etc)
  
• keep the casing. This also increases the token count (which is like decreasing the training population). Many phishing from Africa are uppercase only, and this would be a good cue.
  
• one word filtering was fought back by spammers by including look-alike characters ("v|agra" or "c0ck") doubling some vowels ("viiiiagra") or inserting consonants ("Buyz nViagra"). Our one word filters did try to remove those, but of course this slowed the filtering down. On the other hand modified or mangled tokens ("st0ck") would be much more incrimating than usual ones ("stock")
  
• we added hex-digits since the occur in .HTML colors, which are sometimes used by spammers in the desparate attempt to draw your attention
  

• decode uuEncoded text (for this project, we scanned the whole thing "as is", which is meaningless. We somehow remember that some mail writer only sends uuEncoded text, but this is not a significant proportion of our e-mails.
  
• perform some "link following". Many porn spams simply invite you to visit some site, with some surprises if you go there. The actual e-mail is short, and therefore quite difficult to classify. Link following would require to add some .HTML downloader or .HTML spider. We presented those kind of tools on this site, and it would be easy to add them to the filter
  
• perform some special handling of "very short mails" (10 or 20 tokens) which spammer send you just to waste your time. Legitimate mail usually is longer (saying "Hello", "Regards", signiture already takes around 10 tokens)
  

5.1.3 - The Containers

• we kept a default 1024 bucket structure, but this could be tailored to the training set
  
• we chose the first available hash function. Some experiments could demonstrate that other hash function would better spread the tokens among the buckets
  
• within buckets, we used tLists, but maybe some more efficient structure could improve speed
  
• we used the same CLASS for both frequency counts and spam probability. We could easily create 2 separate structures, or implement an abstract hash table CLASS with two descendents. This has been done, for instance by Peter BELOW, with source code in Code Central. We did not check, but believe that the hash data must then be in a CLASS, and this would necessitate allocation of 121,000 objects for the training, whereas we only had to allocate as many pointed RECORDS.

  With Delphi 2008, we might even use Generics In a 3 day development, you have to take some shortcuts, and we kept our single structure. The 1 minute training (10 seconds for the next ones) just fitted the bill, and this is only an optimizing concern which is not the main goal when developing such a new project.
  

In retrospect, our e-mail contain on average about 12 token ( (75,000+46,000)/(5,700+1,900) ) so it looks like a lot of work for a small gain. And the binary tree avoids any index computing, which is usually a huge time gain.

Therefore we might reintroduce our beloved binary tree in the next version.

The goal of the training phase is to compute the token spam probability list. If the training set is huge (or if more elaborate scanners which take more time are used), it becomes necessary to separate the training / testing from the production phase.

This then requires the persistence of the token spam probability list on disc. Hash tables are easy to save into a file (or a database), since reading them back will produce the same structure. There is no degenerescence risk as with binary trees.

We could adopt all kind of intermediate steps: persist the token frequency lists, and recompute the token spam probability list from those, or use a sliding window approach for the learning (persist each monthly result on disc, compute only the current month, and build the new monthly values from the current month values plus some previous month's values)

In C#, can use some predefined CLASSes, like the Dictionary, hash tables. We also have scanners and regular expression parsers. We did not try to code the filter in C#, and we do not expect any speed improvements from coding in C#, to say the least. So, coding might be quicker (assuming we have climbed the learning curve to understand all those wondeful CLASSes), but the training and production speed might not improve.

5.2 - Why Bayesian Filtering Works

The answer is easy: adaptation to what YOU consider as spam or ok mails. Whether unsolicited Amazon advertising or request to review Delphi products is spam or not is your choice. And the Bayesian learning will adapt to it.

Will it always work ? Well as long as the spam and ok training sets can be analyzed by Bayesian statistical techniques. For the present time, we classify the spammers in several categories:

• the ones that try to sell you something. The corpus of there spam by necessity contains the tokens in the domain of what they are trying to sell you, and the statistical analysis will quickly eliminate those.

• the ones which simply try to waste your time. The same kind of guy which scraches your car, tags your home, or spend time writing viruses.

  Those are the potentially dangerous one. They could one day adapt the spam to your domain of interest. We started to receive some e-mail which contained a shuffling of programming words. The spammers can find our e-mail on our web pages. Then could therefore analyze this page's content, and build some text based on similar words (Delphi, CLASSes, Sockets etc).

  However, even if they did adopt such a strategy, they will not be able to closely target the content to the same category as our "good" e-mails, as derived from our history list, since they have never seen our ok mail list. What they can analyze is one or two of our web pages, what then cannot analyze is our "good" e-mail corpus. The domain of all our web pages is not the same as the domain of the e-mails we want to read.

• the last category includes gray mails : the one we accept or reject based on context (we ordered a plane ticket and wait for the acknowlegement versus we receive advertising for some trip. Or worse, we throw away tax reduction schemes, but when the tax filing time comes, we might accept the same mail in the hope to learn some new tricks). Removing those spam would require enought data to separate the spam from the good, and this will seldom be the case.
  

5.3 - Anti Spam bottom line

• keep blacklists based on FROM. Some companies keep sending us time and again, the same commercial offer (for printer toner, or presenting resumes of job candidates, for instance)
  
• since we now have a "reasonably efficient" parser, implement some boolean logic filters based on some blatent spam tokens ("xxx OR yyy").
  
• the remainder will pass thru the Bayesian filter
  

5.4 - Other use of the Bayesian filter

If we want to classify in more than 2 categories, we would have to generalize the algorithm. And we have to remove the strong "spam filtering" bias of the present tool.

6 - Download the Sources of the Spam Filter

• bayesian_spam_filter.zip: the project and all the necessary units (54 K)
  

• the main program (.DPR, .DOF, .RES), the main form (.PAS, .DFM), and any other auxiliary form
  
• any .TXT for parameters, samples, test data
  
• all units (.PAS) for units
  

• are self-contained: you will not need any other product (unless expressly mentioned).
  
• for Delphi 6 projects, can be used from any folder (the pathes are RELATIVE)
  
• will not modify your PC in any way beyond the path where you placed the .ZIP (no registry changes, no path creation etc).
  

• create or select any folder of your choice
  
• unzip the downloaded file
  
• using Delphi, compile and execute
  

The Pascal code uses the Alsacian notation, which prefixes identifier by program area: K_onstant, T_ype, G_lobal, L_ocal, P_arametre, F_unction, C_lass etc. This notation is presented in the Alsacian Notation paper.

As usual:

• please tell us at fcolibri@felix-colibri.com if you found some errors, mistakes, bugs, broken links or had some problem downloading the file. Resulting corrections will be helpful for other readers
  
• we welcome any comment, criticism, enhancement, other sources or reference suggestion. Just send an e-mail to fcolibri@felix-colibri.com.
  
• or more simply, enter your (anonymous or with your e-mail if you want an answer) comments below and clic the "send" button

  Name :
  E-mail :
  Comments * :

• and if you liked this article, talk about this site to your fellow developpers, add a link to your links page ou mention our articles in your blog or newsgroup posts when relevant. That's the way we operate: the more traffic and Google references we get, the more articles we will write.
  

7 - References

• first, it is established that other before GRAHAM used Bayesian classifiers for spam. But he the person who really started this ball rolling
  
• Paul GRAHAM's bayes filtering algorithm was described and improved in his two seminal papers:
  • A plan for spam - August 2002 : explains what spam is, why Bayesian technique can filter spam, and presents the algorithm (in Lisp) and some results
    
  • Better Bayesian Filtering - January 2003 : ideas about improving the basic filter
    
  Both articles are a MUST read. His web site also contains other pages about spam (FAQ etc).

  My only comment is that GRAHAM believes spammers always try to sell you something. We think that some of them also try to waste your time. And more paranoic people believe that companies selling spam filters are the ones trying to flood us with spam (the same argument as with anti-virus).
  

• SpamAssassin. Their site also contains a corpus of spam and ok mail, which can be used to evaluate any anti spam tool and to check that your tool does not miss some important case. And they use many heuristics which might be worth looking at.

  It seems that there are no more developments for this tool
  

In addition, let me mention that he hosts our web sites since 2001. We chose him because:

• he accepts binary CGIs. In addition to the usage of Interbase or Firebird if your site requires some database
  
• I can download the IIS log of all my sites every morning and know which articles interest my readers
  
• in 7 years, we spotted that 2 or 3 times, there were holes in the hourly download profile. We called him, and we had him on the phone within 5 minutes. He is a Delphi guy, so the discussion is very easy, and those rare problems were solved within the hour
  

Here are the papers related to this filter on this site:

• the Web Spider or the Web Downloader which can be included in an anti spam tool to perform link following
  
• the Coliget Text Search Engine : a project implementing textual search
  
• the Delphi Generics Tutorial : an introduction to Generics (parameterized types) which will be included in Delphi 2008 and can be used to implement hash table hierarchies
  
• we also published many articles about socket programming (see the top left menu), in case you want to implement you own POP3 downloader.
  

8 - The author