# Separating spam and ham emails using the ID3 algorithm

I have a machine learning project in which I have to separate spam and ham emails from a given dataset which has many txt files. Some of them are spam emails and the other ham emails. I have to implement an ID3 algorithm for this case.

How do I begin with this implementation?

Should I use a hashmap to have the words I read from the txt files and the times I read every single word? Something like HashMap<String, int> or should I use two arrays maybe?

Before thinking about implementation details such as what data structures to use, consider what you need as input for the ID3 algorithm. You need a training set which comprises a list of categorised objects (your email, categorised as 'spam' or 'ham'), where each object is represented as a list of features (preferably binary, but not necessarily).

What features are you going to use? This could be the existence of certain words, but maybe phrases might be more useful. Does the email contain more than 5% wrongly spelled words? Are there funny non-ASCII characters in the text? Anything you think might be useful in separating the spam from the ham could be a feature.

The proper term for this representation is as a feature vector, so once you come to the implementation stage, you might want an array/list/vector to represent the feature values for each email. This set of feature vectors is then the input to your ID£ algorithm.

So, to answer your question: start by thinking what features to use, how to extract them from the data, and how to represent them effectively. The better you plan this, the easier the implementation will be.

If you only have a labeled set of emails, it is definitely not enough - you need to extract features from the text, like common words, existence of the title, etc.

For the ID3 algorithm you need to work with entropy,

$$H(x) = -(p_-log_2p_- + p_+log_2p_+)$$

And information gain,

$$IG(x) = H(x) - \sum_{i=1}^{q}\dfrac{|\Delta y_i|}{|\Delta y|}H(y_i)$$

$$q$$ - is a total number of groups after splitting. $$\Delta y_i$$ - the number of elements of the sample where feature X has $$i$$-value

The pseudocode is the following:

def build(L):
Create node t
If the stopping criterion is True:
Assign a predictive model to t
Else:
Find the best binary split L = L_left + L_right using IG
t.left = build(L_left)
t.right = build(L_right)
Return t


Instead of entropy you can use the Gini impurity or misclassification error.

Separating spam and ham emails based on text using the ID3 algorithm and the Enron-Spam, Ling-Spam, PU data sets is possible but has limits in terms of usability. Let's first get through the questions in the body of this question.

How do I begin with this implementation?

Begin by studying the training sets and the ID3 algorithm described below. Then find all the implementations and compare them on the basis of what is important for the project, which may include programming language, comparative tests of training speed, and whether examples in the download are close to the spam detection scenario.

Should I use a hash map to have the words I read from the text files and the times I read every single word, ... like HashMap or should I use two arrays maybe?

Using a hash map is a great way to establish a list of words and their frequency in the text, but word counting of the training example texts requires that the same be done when the training is applied in the field, which leaves an easy attack vector for the spammers. They can then use the word counts in the training sets to write spam that uses words common to ham and avoid words common to spam.

Using training sets to detect fraudulent or unwanted items has several caveats, including these.

• Spamers can use them to train GANs to write spam that gets classified as ham.
• The distinction between ham and spam is subjective, as in user dependent.
• The distinction between ham and spam is time dependent even within a single user.

Therefore, whether ID3, LSTM, Q-learning, or some other strategy is used, continuous sensitivity to what is happening in the spam world and how the user is reacting to automated spam detection decisions is imperative. Therefore two feedback channels are employed in most highly deployed commercial products and services.

• Spam rule or fuzzy rule updates
• Adjustment of detection based on user exceptions indicated

The Seminal ID3 Papers

ID3 was introduced by J.R. Quinlan in Discovering rules by induction from large collections of examples, Kluwer Academic 1979, not easily found on the web except in Japanese but referenced by Expert systems in the micro electronics age, also JR Quinlan, Kluwer Academic 1986. Since Springer acquired Kluwer Academic in 2004 but does not even provide a title listing for either of these as of January 2019, their rights with regard to this excellent work are clearly forfeit per pertinent U.S. and global IP law. This is section 4 of the second of the two public domain papers.

One approach to the induction task above would be to generate all possible decision trees that correctly classify the training set and to select the simplest of them. The number of such trees is finite but very large, so this approach would only be feasible for small induction tasks. ID3 was designed for the other end of the spectrum, where there are many attributes and the training set contains many objects, but where a reasonably good decision tree is required without much computation. It has generally been found to construct simple decision trees, but the approach it uses cannot guarantee that better trees have not been overlooked.

The basic structure of ID3 is iterative. A subset of the training set called the window is chosen at random and a decision tree formed from it; this tree correctly classifies all objects in the window. All other objects in the training set are then classified using the tree. If the tree gives the correct answer for all these objects then it is correct for the entire training set and the process terminates. If not, a selection of the incorrectly classified objects is added to the window and the process continues. In this way, correct decision trees have been found after only a few iterations for training sets of up to thirty thousand objects described in terms of up to 50 attributes. Empirical evidence suggests that a correct decision tree is usually found more quickly by this iterative method than by forming a tree directly from the entire training set. However, O'Keefe (1983) has noted that the iterative framework cannot be guaranteed to converge on a final tree unless the window can grow to include the entire training set. This potential limitation has not yet arisen in practice.

The crux of the problem is how to form a decision tree for an arbitrary collection $$C$$ of objects. If $$C$$ is empty or contains only objects of one class, the simplest decision tree is just a leaf labelled with the class. Otherwise, let $$T$$ be any test on an object with possible outcomes $$O_1, O_2 .... O_w$$. Each object in $$C$$ will give one of these outcomes for $$T$$, so $$T$$ produces a partition $$[C_1, C_2 .... C_w\}$$ of $$C$$ with $$C_i$$ containing those objects having outcome $$O_i$$. This is represented graphically by the tree form of Figure 4. If each subset $$C_i$$ in this figure could be replaced by a decision tree for $$C_i$$, the result would be a decision tree for all of $$C$$. Moreover~ so long as two or more $$C_i$$'s are nonempty, each $$C_i$$ is smaller than $$C$$. In the worst case, this divide-and-conquer strategy will yield single-object subsets that satisfy the one-class requirement for a leaf. Thus, provided that a test can always be found that gives a non-trivial partition of any set of objects, this procedure will always produce a decision tree that correctly classifies each object in $$C$$.

The choice of test is crucial if the decision tree is to be simple. For the moment, a test will be restricted to branching on the values of an attribute, so choosing a test comes down to selecting an attribute for the root of the tree. The first induction programs in the ID series used a seat-of-the-pants evaluation function that worked reasonably well. Following a suggestion of Peter Gacs, ID3 adopted an information based method that depends on two assumptions. Let $$C$$ contain $$p$$ objects of class $$P$$ and $$n$$ of class $$N$$. The assumptions are:

(1) Any correct decision tree for $$C$$ will classify objects in the same proportion as their representation in $$C$$. An arbitrary object will be determined to belong to class $$P$$ with probability $$p / (p + n)$$ and to class $$N$$ with probability $$n / (p + n)$$.

(2) When a decision tree is used to classify an object, it returns a class. A decision tree can thus be regarded as a source of a message 'P' or 'N', with the expected information needed to generate this message given by

$$I_{(p, n)} = \, - \, \frac {p} {p + n} \log_2 \frac {p} {p + n} \, - \, \frac {n} {p + n} \log_2 \frac {n} {p + n}$$

If attribute $$A$$ with values $$[A_1, A_2, ... A_v]$$ is used for the root of the decision tree, -it will partition C into $$[C_1, C_a, ... C_v]$$ where $$C_i$$ contains those objects in $$C$$ that have value $$A_i$$ of $$A$$. Let $$C_i$$ contain $$P_i$$ objects of class $$P$$ and $$n_i$$ of class $$N$$. The expected information required for the sub-tree for $$C_i$$ is $$I_{(p_i, n_i)}$$. The expected information required for the tree with $$A$$ as root is then obtained as the weighted average

$$E(A) = \sum_{i=1}^{v} \frac {p_i + n_i} {p + n} I(p_i, n_i)$$

where the weight for the $$i^{th}$$ branch is the proportion of the objects in $$C$$ that belong to $$C_i$$. The information gained by branching on $$A$$ is therefore

$$\text{gain}(A) = I(p, n) - E(A)$$

A good rule of thumb would seem to be to choose that attribute to branch on which gains the most information3. ID3 examines all candidate attributes and chooses $$A$$ to maximize $$\text{gain}(A)$$, forms the tree as above, and then uses the same process recursively to form decision trees for the residual subsets $$C_1, C_E, ... C_v$$.

To illustrate the idea, let $$C$$ be the set of objects in Table 1. Of the 14 objects, 9 are of class $$P$$ and 5 are of class $$N$$, so the information required for classification is

$I(p, n) = \, - \, \frac {9} {14} \, log_2 \, \frac {9} {14} \, - \, \frac {5} {14} \, log_2 \, \frac {5} {14} = \, 0.940 \, \text{bits}$\$

Now consider the outlook attribute with values $$[ \text{sunny}, \text{overcast}, \text{rain} \}$$. Five of the 14 objects in $$C$$ have the first value (sunny), two of them from class $$P$$ and three from class $$N$$, so

$$p_1 = 2 \quad n_1 = 3 \quad I(p_1, h_1) = 0.971$$

and similarly

$$P_2 = 4 \quad n_2 = 0 \quad I(p_2, n_2) = 0 \\ P_3 = 3 \quad n_3 = 2 \quad I(p_3, n_3) = 0.971$$

The expected information requirement after testing this attribute is therefore

$$E (\text{outlook}) = \frac {5} {14} \, I(p_1, n_1) \, + \, \frac {4} {14} \, I(p_2, n_2) \, + \, \frac {5} {14} \, I(p_3, n_3) \, = \, 0.694 \, \text{bits}$$

The gain of this attribute is then gain(outlook) = 0.940 - E(outlook) = 0.246 bits. Similar analysis gives gain(temperature) = 0.029 bits, gain(humidity) = 0.151 bits, and gain(windy) = 0.048 bits, so the tree-forming method used in ID3 would choose outlook as the attribute for the root of the decision tree. The objects would then be divided into subsets according to their values of the outlook attribute and a decision tree for each subset would be induced in a similar fashion. In fact, Figure 2 shows the actual decision tree generated by ID3 from this training set.

A special case arises if $$C$$ contains no objects with some particular value $$A_j$$ of $$A$$, giving an empty $$C_j$$. ID3 labels such a leaf as 'null' so that it fails to classify any object arriving at that leaf. A better solution would generalize from the set $$C$$ from which $$C_j$$ came, and assign this leaf the more frequent class in $$C$$.

The worth of ID3's attribute-selecting heuristic can be assessed by the simplicity of the resulting decision trees, or, more to the point, by how well those trees express real relationships between class and attributes as demonstrated by the accuracy with which they classify objects other than those in the training set (their predictive accuracy). A straightforward method of assessing this predictive accuracy is to use only part of the given set of objects as a training set, and to check the resulting decision tree on the remainder.

Several experiments of this kind have been carried out. In one domain, 1.4 million Chess positions described in terms of 49 binary-valued attributes gave rise to 715 distinct objects divided 65%:35% between the classes. This domain is relatively complex since a correct decision tree for all 715 objects contains about 150 nodes. When training sets containing 20% of these 715 objects were chosen at random, they produced decision trees that correctly classified over 84% of the unseen objects. In another version of the same domain, 39 attributes gave 551 distinct objects with a correct decision tree of similar size; training sets of 20% of these 551 objects gave decision trees of almost identical accuracy. In a simpler domain (1,987 objects with a correct decision tree of 48 nodes), randomly-selected training sets containing 20% of the objects gave decision trees that correctly classified 98% of the unseen objects. In all three cases, it is clear that the decision trees reflect useful (as opposed to random) relationships present in the data.

This discussion of ID3 is rounded off by looking at the computational requirements of the procedure. At each non-leaf node of the decision tree, the gain of each untested attribute $$A$$ must be determined. This gain in turn depends on the values $$p_i$$ and $$n_i$$ for each value $$A_i$$ of $$A$$, so every object in $$C$$ must be examined to determine its class and its value of $$A$$. Consequently, the computational complexity of the procedure at each such node is $$O(|C| \cdot |A|)$$, where $$|A|$$ is the number of attributes above. ID3's total computational requirement per iteration is thus proportional to the product of the size of the training set, the number of attributes and the number of non-leaf nodes in the decision tree. The same relationship appears to extend to the entire induction process, even when several iterations are performed. No exponential growth in time or space has been observed as the dimensions of the induction task increase, so the technique can be applied to large tasks.

Footnotes

[3] Since $$I(p,n)$$ is constant for all attributes, maximizing the gain is equivalent to minimizing $$E(A)$$, which is the mutual information Of the attribute A and the class. Pearl (1978a) contains an excellent account of the rationale of information-based heuristics.