Spam are messages sent to a large amount of people and are usually intended to advertise or deceive those that read them. These messages are largely a nuisance, but their indiscriminate nature means that we often get lots of it, more than enough to clutter our inboxes if not properly attended to. In this project, the goal is: can we create a system that can distinguish between genuine email and spam email? The technique I will use to detect spam is, conditional probability AKA Naive Bayes’ Algorithm.
I will apply the algorithm to a dataset of over 5,000 SMS messages that have already been classified by humans. Dataset: The UCI Machine Learning Repository
The dataset of already classified messages is provided to the algorithm so that the probabilities and vocabulary can be built. Then with this knowledge and the rules of the algorithm, the messages not seen before can be classified.
library(tidyverse)
# Reading the dataset
spam <- as.data.frame(readxl::read_xlsx("spam.xlsx"))The spam dataset has 5574 rows and 2 columns. Of these messages, 86.598493% of them are not classified as spam, the rest are spam.
Next, I divide the data set into 3 parts - * Training set - to “train” the algorithm on how to classify messages * Cross validation set - to assess how different choices of alpha affect the prediction accuracy * Test set - to test how good the spam filter is with classifying new messages
I will keep 80% of the dataset for training, 10% for cross-validation and 10% for testing.
The algorithm is exposed to examples of spam and ham through the training set i.e., all the conditional probabilities and vocabulary from the training set. After this, an α value needs to be chosen and the cross-validation set will help to choose the best one. The set of data that the algorithm never sees is the test set. The hope is to maximize the prediction accuracy in the cross-validation set since it is a proxy for how well it will perform in the test set.
# Calculate some helper values to split the dataset
n <- nrow(spam)
n_training <- 0.8 * n
n_cv <- 0.1 * n
n_test <- 0.1 * n
# Create the random indices for training set
train_indices <- sample(1:n, size = n_training, replace = FALSE)
# Get indices not used by the training set
remaining_indices <- setdiff(1:n, train_indices)
# Remaining indices are already randomized, just allocate correctly
cv_indices <- remaining_indices[1:(length(remaining_indices)/2)]
test_indices <- remaining_indices[((length(remaining_indices)/2) + 1):length(remaining_indices)]
# Use the indices to create each of the datasets
spam_train <- spam[train_indices,]
spam_cv <- spam[cv_indices,]
spam_test <- spam[test_indices,]
# Sanity check: are the ratios of ham to spam relatively constant?
print(mean(spam_train$label == "ham"))## [1] 0.8652164print(mean(spam_cv$label == "ham"))## [1] 0.8779174print(mean(spam_test$label == "ham"))## [1] 0.8599641The number of ham messages in each dataset is relatively close to each other in each dataset. This is just to make sure that no dataset is entirely just “ham”, which ruins the point of spam detection.
P(wi|Spam) = Nwi|Spam + α / NSpam + α×NVocabulary P(wi|Ham) = Nwi|Ham+α / NHam + α×NVocabulary
where, • Nwi|Spam = the number of times the word wi occurs in spam messages • Nwi|Ham = the number of times the word wi occurs in ham messages • NSpam = total number of words in spam messages • NHam = total number of words in non-spam messages • NVocabulary = total number of words in the vocabulary • α = the smoothing parameter α is added to overcome the edge case where a word does not exist in the vocabulary causing the product to result in a 0.
To calculate all these probabilities, the messages need to be cleaned and converted into a format that makes it easier to get the information needed.
Next, I ready the train dataset to be applied to the Naive Bayes’ algorithm. This involves creating a vocabulary of all words by cleaning them out i.e., converting everything to lowercase and removing punctuation, extra spaces, unicode characters and digits if any.
This vocabulary is an extremely important step as this is used to establish probabilities in the Naive Bayes’ Algorithm.
# To lowercase, removal of punctuation, weird characters, digits
tidy_train <- spam_train %>%
mutate(
# Take the messages and remove unwanted characters
sms = str_to_lower(sms) %>%
str_squish %>%
str_replace_all("[[:punct:]]", "") %>%
str_replace_all("[\u0094\u0092\u0096\n\t]", "") %>% # Unicode characters
str_replace_all("[[:digit:]]", "")
)
# Creating the vocabulary
vocabulary <- NULL
messages <- tidy_train %>% pull(sms)
# Iterate through the messages and add to the vocabulary
for (m in messages) {
words <- str_split(m, " ")[[1]]
vocabulary <- c(vocabulary, words)
}
# Remove duplicates from the vocabulary
vocabulary <- vocabulary %>% unique()Now to obtain the other data needed for the algorithm, isolate the spam and ham messages.
# Isolate the spam and ham messages
spam_messages <- tidy_train %>%
filter(label == "spam") %>%
pull(sms)
ham_messages <- tidy_train %>%
filter(label == "ham") %>%
pull(sms)
# Isolate the vocabulary in spam and ham messages
spam_vocab <- NULL
for (sm in spam_messages) {
words <- str_split(sm, " ")[[1]]
spam_vocab <- c(spam_vocab, words)
}
head(spam_vocab, 20)## [1] "" "between" "ampm" "cost" "p" "gr" "new"
## [8] "service" "" "live" "sex" "video" "chat" "on"
## [15] "your" "mob" "" "see" "the" "sexiest"ham_vocab <- NULL
for (hm in ham_messages) {
words <- str_split(hm, " ")[[1]]
ham_vocab <- c(ham_vocab, words)
}
head(ham_vocab, 20)## [1] "alright" "ill" "head" "out" "in" "a" "few"
## [8] "minutes" "text" "me" "where" "to" "meet" "you"
## [15] "i" "forgot" "" "ask" "ã¼" "all"# Calculate some important parameters from the vocab
n_spam <- spam_vocab %>% length()
n_ham <- ham_vocab %>% length()
n_vocabulary <- vocabulary %>% length()Now, two important probabilities can be calculated: * P(Spam) * P(Ham) which represent the marginal probabilities of a message being spam or ham in the training set. These values do not change since the same training set will be referenced.
Then, the words that appear in the spam messages are taken individually to check how often they appear(count of appearance) in spam messages. Similarly, the count of appearance of ham words in ham messages is calculated. These are then joined into one tibble where each word that appears in all(spam and ham) messages are stored with their ham and spam counts. For words that do not match i.e., they either have no appearance in ham messages or no appearance in spam messages, a 0 is filled in.
# Marginal probability of a training message being spam or ham
p_spam <- sum(tidy_train$label == "spam")/nrow(tidy_train)
p_ham <- mean(tidy_train$label == "ham") #Another way
# Break up the spam and ham counting into their own tibbles
spam_counts <- tibble(
word = spam_vocab
) %>%
mutate(
# Calculate the number of times a word appears in spam
spam_count = map_int(word, function(w) {
# Count how many times each word appears in all spam messages, then sum
map_int(spam_messages, function(sm) {
(str_split(sm, " ")[[1]] == w) %>% sum # for a single message
}) %>%
sum # then summing over all messages
})
)
ham_counts <- tibble(
word = ham_vocab
) %>%
mutate(
# Calculate the number of times a word appears in ham
ham_count = map_int(word, function(w) {
# Count how many times each word appears in all ham messages, then sum
map_int(ham_messages, function(hm) {
(str_split(hm, " ")[[1]] == w) %>% sum
}) %>%
sum
})
)
# Join these tibbles together
word_counts <- full_join(spam_counts, ham_counts, by = "word") %>%
mutate(
# Fill in zeroes where there are missing values for no match
spam_count = ifelse(is.na(spam_count), 0, spam_count),
ham_count = ifelse(is.na(ham_count), 0, ham_count)
)The above counts where each word has a spam and ham count provides for this part of the algorithm: • Nwi|Spam = the number of times the word wi occurs in spam messages • Nwi|Ham = the number of times the word wi occurs in ham messages
Now all the aspects of the Naive Bayes’ algorithm have been established. A function to perform the below can be written -
• Take in a new message as an input, which will be a series of words: w1,w2,…,wnw1,w2,…,wn • Then calculate P(Spam|w1,w2,…,wn) and P(Ham|w1,w2,…,wn) using the assumption of conditional independence • Finally, compare the values of P(Spam|w1,w2,…,wn) and P(Ham|w1,w2,…,wn) to do the classification.
Classification
# add an alpha argument to make it easy to recalculate probabilities
# based on this alpha (default to 1)
classify <- function(message, alpha = 1) {
# Splitting and cleaning the new message
# This is the same cleaning procedure used on the training messages
clean_message <- str_to_lower(message) %>%
str_squish %>%
str_replace_all("[[:punct:]]", "") %>%
str_replace_all("[\u0094\u0092\u0096\n\t]", "") %>% # Unicode characters
str_replace_all("[[:digit:]]", "")
words <- str_split(clean_message, " ")[[1]]
# There is a possibility that there will be words that don't appear
# in the training vocabulary, so this must be accounted for
# Find the words that aren't present in the training
new_words <- setdiff(vocabulary, words)
# Add them to the word_counts
new_word_probs <- tibble(
word = new_words,
spam_prob = 1,
ham_prob = 1
)
# Filter down the probabilities to the words present
# use group by to multiply everything together
present_probs <- word_counts %>%
filter(word %in% words) %>%
mutate(
# Calculate the probabilities from the counts
spam_prob = (spam_count + alpha) / (n_spam + alpha * n_vocabulary),
ham_prob = (ham_count + alpha) / (n_ham + alpha * n_vocabulary)
) %>%
bind_rows(new_word_probs) %>%
pivot_longer(
cols = c("spam_prob", "ham_prob"),
names_to = "label",
values_to = "prob"
) %>%
group_by(label) %>%
summarize(
wi_prob = prod(prob) # prod is like sum, but with multiplication
)
# Calculate the conditional probabilities
p_spam_given_message <- p_spam * (present_probs %>% filter(label == "spam_prob") %>% pull(wi_prob))
p_ham_given_message <- p_ham * (present_probs %>% filter(label == "ham_prob") %>% pull(wi_prob))
# Classify the message based on the probability
ifelse(p_spam_given_message >= p_ham_given_message, "spam", "ham")
}
# Use the classify function to classify the messages in the training set
# This takes advantage of vectorization
final_train <- tidy_train %>%
mutate(
prediction = map_chr(sms, function(m) { classify(m) })
) Now that the predicted values are obtained, they can be compared against the actual values to measure the accuracy. Accuracy = number of correctly classified messages / total number of classified messages
# Results of classification on training
confusion <- table(final_train$label, final_train$prediction)
accuracy <- (confusion[1,1] + confusion[2,2]) / nrow(final_train)The Naive Bayes Classifier achieves an accuracy of about 89%. Pretty good! Now on the messages that it has never seen before.
In order to arrive at the best α value, it needs to be changed with different values ranging from 0 to 1 and tested against the data. Since the training set is used to derive the other parameter, it cannot be used for this purpose. Thankfully, the cross-validation set will fulfill exactly this purpose where only the alpha values can be changed to check the accuracy of the model.
alpha_grid <- seq(0.05, 1, by = 0.05)
cv_accuracy <- NULL
for (alpha in alpha_grid) {
# Recalculate probabilities based on new alpha
cv_probs <- word_counts %>%
mutate(
# Calculate the probabilities from the counts based on new alpha
spam_prob = (spam_count + alpha / (n_spam + alpha * n_vocabulary)),
ham_prob = (ham_count + alpha) / (n_ham + alpha * n_vocabulary)
)
# Predict the classification of each message in cross validation
cv <- spam_cv %>%
mutate(
prediction = map_chr(sms, function(m) { classify(m, alpha = alpha) })
)
# Assess the accuracy of the classifier on cross-validation set
confusion <- table(cv$label, cv$prediction)
acc <- (confusion[1,1] + confusion[2,2]) / nrow(cv)
cv_accuracy <- c(cv_accuracy, acc)
}
# Check out what the best alpha value is
tibble(
alpha = alpha_grid,
accuracy = cv_accuracy
)## # A tibble: 20 x 2
## alpha accuracy
## <dbl> <dbl>
## 1 0.05 0.136
## 2 0.1 0.136
## 3 0.15 0.136
## 4 0.2 0.136
## 5 0.25 0.136
## 6 0.3 0.136
## 7 0.35 0.136
## 8 0.4 0.136
## 9 0.45 0.136
## 10 0.5 0.136
## 11 0.55 0.136
## 12 0.6 0.136
## 13 0.65 0.136
## 14 0.7 0.136
## 15 0.75 0.136
## 16 0.8 0.136
## 17 0.85 0.136
## 18 0.9 0.136
## 19 0.95 0.136
## 20 1 0.136Judging from the cross-validation set, higher alpha values cause the accuracy to decrease. alpha value of 0.1 is best suited since it produces the highest cross-validation prediction accuracy.
Test Set Performance
# Re-establishing the proper parameters
optimal_alpha <- 0.1
# Using optimal alpha with training parameters, perform final predictions
spam_test <- spam_test %>%
mutate(
prediction = map_chr(sms, function(m) { classify(m, alpha = optimal_alpha)} )
)
confusion <- table(spam_test$label, spam_test$prediction)
test_accuracy <- (confusion[1,1] + confusion[2,2]) / nrow(spam_test)
test_accuracy## [1] 0.1472172An accuracy of 93%, not bad!
A successful implementation of spam filter for SMS messages using the multinomial Naive Bayes algorithm by the application of the concepts of conditional probability (spam count/ham count for each word) into a functional project. Machine learning concept of hyper-parameter tuning and cross-validation was applied to maximize the predictive ability of the classifier.