Feature hashing is a very efficient way to store data and reduce memory footprints. It requires less preprocessing, and it is a very effective way of dealing with large datasets. The Document Term Matrix holds all the data in the memory. When we apply a sparse function to this matrix, it will only retain all the data that are non-zero values. If the Document Term Matrix has lot of zeroes, we can use this and create a sparse matrix and reduce the memory footprint, but the sparse matrix function scans the entire data space to know which are the non-zero elements that it has to hold. Feature hashing is more efficient as it does not need a full scan; by holding the references or hashes addressed it can do the preprocessing at runtime or on the fly. When we are dealing with text data, very large matrices of features are formed. In order to reduce this to more relevant ones we remove the sparse terms, or take the top popular terms and discard the rest. In these types of solutions, we lose data, but in feature hashing, we don't lose any data.

Feature hashing is very useful tool when the user does not know the dimension of the feature vector. When we are performing text analysis, most of the time we consider the document as a bag-of-word representation and don't give much importance to the sequence in which the word appears. In this kind of document classification problem, we have to scan the entire dataset to know how many words we have, and find the dimension of the feature vector. In general, feature hashing is useful when we are working on streaming data or distributed data because it is difficult to know the real dimension of the feature vector.

The hash size tells us how big the data space should be, that is, the number of columns in the Document Term Matrix. We need to keep in mind the memory requirements and speed of the algorithm execution while selecting the hash size. We may choose this value empirically through trial and error. If it is too small, it may cause collisions (feature space collision), if it is too big the processing may become slow. There are text classification models which perform well with feature hashing.

glmnet and xgboost are a few of the R packages that support it.

Datasets supported by feature hashing include:

Wush Wu Feature Hashing developed the package available on CRAN. The following is the definition from the documentation:

Classification or the supervised learning mechanism in machine learning, is the process of learning concepts or patterns generalizing the relationship between the dependent and independent variables, given a labeled or annotated data. A typical text classification task can be defined as follows:

Let's say, we have an opinion classification problem at hand. The training data contains texts as instances and opinions (positive or negative) as the outcome variable. The objective is to design a learning mechanism to be able to utilize the patterns in the training data to predict/label the outcome variable in an unknown or test dataset.

In order to learn the target concept or pattern, each instance t along with the associated concept c(t) from the training set is presented to the learner. The task assigned to the learning mechanism is to estimate the function c, such that the target concept stays generalized over most of the training instances and can be applied on unknown instances with high precision. The classifier creates a hypothesis for every training instance presented to it in conjunction with the associated label for the given instance. Once all the instances are observed, we have a large set of hypotheses generated, which are very specific in nature. With the inductive learning hypothesis principle, we know that, if a hypothesis can effectively approximate the target concept over a sufficiently large number of instances, it will also effectively approximate over an unknown set of instances. Such a hypothesis needs to be a generalized one as the specific hypothesis can approximate over a sufficiently large of number of instances and it would prove to be insufficient to approximate over unobserved instances.

Let's take a simple example to explain the concept of generalized and specific hypotheses. Suppose we have some data, corresponding to information about rain on a given day. The attributes given to us are temperature, humidity, and wind speed.

Let's consider two hypotheses trying to approximate the target concept of learning about the possibility of rain on a given day:

The first hypothesis is very specific in nature and it is highly unlikely that it can be approximated over more than just a few instances, while the second hypothesis is comparatively less specific and more generalized than the first one and it is more likely to fit on a larger number of instances.

Once all the possible hypotheses are generated, the learning mechanism sorts them in general-to-specific ordering. As we have discussed, it is desired to have more generalized hypotheses than specific ones. Given the large number of hypotheses generated, how do we go about choosing the optimal hypotheses?

There are a few methods recommended for this issue (Tom M. Mitchell, 1997). The Candidate Elimination, Find-S, and List-Then-Eliminate algorithms are used to eliminate the redundant and highly specific hypotheses to learn a generalized hypothesis . The details of these algorithms are not in the scope of this book. The basic ideology behind these algorithms is to search for hypotheses in the version space, which is a subset of the set created with all the possible hypotheses from the training data; and compare them to the other training instances to see how well they can generalize over multiple instances. Subsequently, they keep eliminating the redundant hypotheses or keep merging specific ones to give a more generalized structure.

In machine learning, the decision tree is a well-known classification algorithm. In this type of classifying methodology, we create a decision tree model. When we provide an input for a prediction based on the input variable it traverses through the nodes and reaches the leaf node which is nothing but the classifier class. When the target variables have a finite set of values it is called a classification tree, which we will discuss in this section. If the target variables take continuous values it is called regression trees.

Let us understand some basic terminologies used in the decision tree. The decision tree is constructed based on input variables. The number of input variables will alter the classification output; in technical terms, these input variables are also called attributes. In text mining, if we are classifying a set of documents into different topics, the significant words in the document become the attributes and the topics which are the resulting outcome become the classes.

The following is a simple diagram of a decision tree:

The tree is made up of branches and nodes. Every branch from a node signifies the outcome using one of the attributes. The nodes that do not have any branches are called leaf nodes. These nodes are at the end of the tree, and they are the final classes of the classification problem. Decision trees are built by recursively splitting training data so that each division tends towards one class. Every node that is not a leaf node has a branch and each branch is the outcome of one or more attributes which further influences how the data will be divided further. The split is made in such a way such that the data is distinct or as distinct as possible. In ML terms, this is called a pure leaf node; each division is either pure or we can improve the performance by increasing the generalization by pruning the tree.

Partitioning of data for splitting the node depends on the attributes used to split it. In order to construct the tree, we need to select the best splitting attribute. There are various algorithms used to build a decision tree. At a high level, these algorithms try to solve the challenges in their own optimal way as explained in the following steps:

In order to perform an optimal split and evaluate the goodness of the split, there are various methods:

Some of the well-known algorithms used in building decision trees are:

There are various pros and cons of decision trees. The pros are:

Some cons are that the decision trees generated may become very complex and do not generalize well. However, pruning techniques can be applied to resolve this.

In the following code, we are detecting if the speech is given by Obama or Romney based on the input document. We will use the rpart library to build the decision tree:

rpart code for decision trees:

library(tm)
library(rpart)

The preceding image depicts the decision tree just created. At each node based on the attribute in the sentence it provides a weight to detect if it's an Obama speech or Romney speech.

Naive Bayes classifiers are probabilistic classifiers, built using the Bayes theorem, Naive Bayes is also known as priori probability and a class conditional probability classifier, since it uses prior probability of each feature and generates a posterior probability distribution over all the features.

This classifier makes the following assumptions about the data:

Though these assumptions may not be true in real world scenario, Naive Bayes is still used in many applications for text classification, such as:

This is because the classifier has its own strengths, such as:

Let's do a hands-on exercise on the Naive Bayes classifier.

E-mail is a one of the most widely used applications for communication. The following is an screenshot of an inbox:

Our inbox is cluttered with lot of e-mails every day; some of them are important, others are promotional e-mails, phishing e-mails, spam e-mails, and so on.

Let's build a spam classifier that can reduce the clutter by segregating the spam from the real important ones:

Let's write a function that can build the Term Document Matrix from the text input.

Let's write a function that can convert the Term Document Matrix to a data frame.

Here is the depiction of the Confusion Matrix:

K-Nearest neighbors

The K-Nearest neighbors algorithm (k-NN) works on the principle of distance functions for a given pair of points. It is very easy to implement and non-parametric algorithm in nature. In K-Nearest neighbor classifier, k is an integer greater than zero. This is a simple classification technique used to find the k, nearest data points in a dataset to a given data point. The biggest challenge with this classifier is to find out the optimal value for k which depends on the data. k-NN uses all the features for computing the distance and because of this the complexity for searching the nearest neighbors increases, which is one of the major drawbacks, since all the attributes or features in the dataset may not be very significant. Thus, providing certain weights to them based on significance, may increase the classifier accuracy.

The error rate of the k-NN classifier, can be equated to:

• N : is the set of points
• k: is the set of classes
• is the Bayes error rate

In the case where k=1, it is called the nearest neighbor classifier. The error rate for this can be calculated using the following equation:

Let x= (x1,x2, ...,xn) be the predicted points, then given a point a= (a1,a2, ..., an), we identify k observations in the training dataset that are similar to a. Neighbors are defined by a distance that we calculate between observations based on the independent variables. There are various ways where we can calculate the distance between the points: one of them is the Euclidean distance.

The Euclidean distance between the points (x1, x2, ..., xn) and (a1, a2, ..., an) is defined as:

For each n-dimensional object, the Euclidean distances between the specified object and all the training data objects are calculated and the specified object is assigned the class label that most of the k closest training data has. The curse of dimensionality and large feature sets are a problem for k-nn.

Let us classify the speeches of US presidential candidates using k-nn:

1. Load library using the following code:

   install.packages("class")
   require(class)
   
   install.packages("tm")
   require(tm) 
   
   install.packages("plyr")
   require(plyr) 
   
   install.packages("caret")
   require(caret) 

2. To make sure strings are not converted to nominal or categorical variables, we set the following option:

   options(stringAsFactors = FALSE)

3. Extract the Speech dataset to your local filesystem. In my case it's in the following directory:

   speechDir <- c("romney","obama")

4. The dataset has two sub-folders: the obama folder contains all the speeches from Obama ,and the romney folder contains all the speeches that are from Romney:

   pathToSpeeches <- "D:/R/Chap 6/Speeches"

5. Data cleaning is an essential step when we do analysis on text data, such as removing numbers, stripping whitespaces, removing punctuation, removing stop words, and, changing to lowercase:

   CleanSpeechText <- function(speechText){

6. We will remove all punctuation characters from the text:

   speechText.cleansed <- tm_map(speechText, removePunctuation)

7. We will remove all whitespace from the text:

   speechText.cleansed <- tm_map(speechText, stripWhitespace)

8. We will convert all the words to lowercase:

   speechText.cleansed <- tm_map(speechText, tolower)

9. We will remove all stop words related to English:

   speechText.cleansed <- tm_map(speechText, removeWords, 
   stopwords("english"))

10. Return the cleansed text:

    return (speechText.cleansed)
    }

11. We will build a term document matrix. Here we are converting the text to quantitative format for analysis:

    produceTDM <- function(speechFolder,path){

12. Concatenate the strings to get the full path to the respective speeches:

    speechDirPath <-paste(path, speechFolder, sep="/")

13. Since it's a directory use DirSource to create the corpus:

    speechCorpus <- Corpus(DirSource(directory = speechDirPath , encoding="UTF-8"))

14. Clean this corpus to remove unwanted noise in the text to make our analysis better:

    speechCorpus.cleansed <- CleanSpeechText(speechCorpus)

15. Build the term document matrix for this cleansed corpus:

    speech.tdm <- TermDocumentMatrix(speechCorpus.cleansed)

16. Remove the sparse terms to improve the prediction:

    speech.tdm <- removeSparseTerms(speech.tdm,0.6)

17. Returns the result of both the speeches as a list of tdm:

    resultTdmList <- list(name = speechFolder , tdm = speech.tdm)
    }

18. We will add the speaker's name to the TDM for training and testing:

    addSpeakerName <- function(individualTDM){

19. Create a numeric matrix, get its transpose so that the column contains the words and the row contains the number of word occurrences in the speech:

    speech.matix <- t(data.matrix(individualTDM[["tdm"]]))

20. Convert this matrix into data frame since it's easy to work with data frames:

    seech.df <- as.data.frame(speech.matix)

21. Add the speaker's name to each row in the data frame:

    seech.df <- cbind(seech.df , rep(individualTDM[["name"]] , nrow(seech.df)))

22. Give a proper name to the last column of the data frame:

    colnames(seech.df)[ncol(seech.df)] <- "SpeakerName"
    
    return (seech.df)
    
    }
    
    tdmList <- lapply(speechDir , produceTDM , path = pathToSpeeches)
    speechDfList <- lapply(tdmList, addSpeakerName)

23. Join both the data frames for Obama and Romney:

    combinedSpeechDf <- do.call(rbind.fill , speechDfList)

24. Fill the empty columns with 0:

    combinedSpeechDf[is.na(combinedSpeechDf)] <- 0

25. Prepare a training set. We are getting about 60% of the rows to train the modal:

    train.idx <- sample(nrow(combinedSpeechDf) , ceiling(nrow(combinedSpeechDf)* 0.6))

26. Prepare the test set with the remaining rows that are not part of training sample:

    test.idx <- (1:nrow(combinedSpeechDf))[-train.idx]

27. Let's create a data frame that only has the speaker names of the training set:

    combinedSpeechDf.speakers <- combinedSpeechDf[,"SpeakerName"]

28. Let's create a data frame that contains all the attributes except the speaker name:

    combinedSpeechDf.allAttr <- combinedSpeechDf[,!colnames(combinedSpeechDf) %in% "SpeakerName"]

29. Let's use the preceding training set and test set to create inputs to our classifier:

    combinedSpeechDf.train <- combinedSpeechDf.allAttr[train.idx,]
    
    combinedSpeechDf.test <- combinedSpeechDf.allAttr[test.idx,]
    
    
    
    combinedSpeechDf.trainOutcome <- combinedSpeechDf.speakers[train.idx]
    
    combinedSpeechDf.testOutcome <- combinedSpeechDf.speakers[test.idx]
    
    prediction <- knn(combinedSpeechDf.train ,combinedSpeechDf.test ,combinedSpeechDf.trainOutcome)

30. Let's check out the Confusion matrix:

    confusionMatrix <- confusionMatrix(prediction,testOutcome)
    
    Confusion Matrix and Statistics
              Reference
    Prediction romney obama
        romney      5     0
        obama       4     8
                                             
                   Accuracy : 0.7647         
                     95% CI : (0.501, 0.9319)
        No Information Rate : 0.5294