In this project, we used 3 different metrics (Information Gain, Mutual Information, Chi Squared) to find important words and then we used them for the classification task. We compared the result at the end.

GitHub Link

This project has two parts. In the first part, we find features (words which are highly related to the topics). In the second part, we classify documents, using different feature sets and evaluate the results.

Part 1

Each document can be represented by the set of words that appear in it.
But some words are more important and has more effect for determination of the context of the document.
So we want to represent a document by a set of important words. In this part, we are going to find a set of 100 words that are more infomative for document classification.

Data Set

The dataset for this task is “همشهری” (Hamshahri) that contains 8600 persian documents.

Preproceesing

We did some preprocessing for building our data structures for processing.
We read each document and added its words to our vocabulary set and also a set for that document.
We then used this set to create a vocab_index dictionary for assigning an index for each word that appears in our dataset.
Our dataset consists of 5 different classes.

class_name

['ورزش', 'اقتصاد', 'ادب و هنر', 'اجتماعی', 'سیاسی']

There is some statistcs information about out dataset.

print("vocab size:", len(vocab))
print ("number of terms (all tokens):", number_of_terms)
print ("number of docs:", number_of_docs)
print ("number of classes:", cls_index)

vocab size: 65880
number of terms (all tokens): 3506727
number of docs: 8600
number of classes: 5

The probability of each classes are stored in the table below.

tmp_view = pd.DataFrame(probability_of_classess)
tmp_view

# Calculation of our metrics for each words in Vocabulary We are going to find 100 words that are good indicator of classes.
We want to use 3 different type of metrics

• Information Gain
• Mutual Information
• $\chi$ square

Information Gain

We used these metric. And the top 10 words with highest information gain can be seen in the table below.

preview.head(10)

If you think about the meaning of these words you can agree that since they a have high information gain they can be really good identifiers for categorizing a doc.
In the table below, you can see 5 worst words.

preview.tail(5)

Mutual Information

There is two formula for this metrics. One of them is introduced in the Lecture Slides.
Another one is introduced in Website: https://nlp.stanford.edu/IR-book/html/htmledition/mutual-information-1.html
We used both of them and then choose the better set.
Let's see the result of each of those different formulae for this metric.

First Model:

Calculating with formula in the Slides:

The result is

preview.head(10)

But there is a __problem__ here

The words in the table above, are infrequent words and because of that, they give use high information when they appear in a doc, but the probability of appearing such a word in any document is really small. So, in general, these words are not good identifiers.
You can see number of occurance of some of these words in each classes:

word_occurance_frequency_vs_class[word_index['نباریدن']], word_occurance_frequency_vs_class[word_index['مایکروسافت']],  word_occurance_frequency_vs_class[word_index['آلیاژی']]

(array([0, 4, 1, 0, 0]), array([0, 4, 1, 0, 0]), array([0, 5, 1, 0, 0]))

Second Model

Now we want to calculate it with formula in this link.

The formula is:

These words are better

They are not rare
You can see the frequency of some of these words in each classes:

print (list(reversed(class_name)))
word_occurance_frequency_vs_class[word_index['ورزشی']], word_occurance_frequency_vs_class[word_index['سیاسی']],  word_occurance_frequency_vs_class[word_index['پیروزی']],

['سیاسی', 'اجتماعی', 'ادب و هنر', 'اقتصاد', 'ورزش']





(array([1866,    9,    8,   66,   16]),
 array([  35,  300,   71,  372, 1602]),
 array([497,  44,  24,  60, 191]))

$ \chi$ Squared

Another Metric is $ \chi$ Squared.
Now we are goind to see the result of using $\chi$ squared as a mesure of importance.

Result Comparison

We can compare our three set of words here.
In the table below, you can see top 20 words for each metrics.
For mutual information, there are two sets because we used two different formula.

Output File

The output files are stored in CSV format files.
These files contain 100 most important words for each metrics.

Conclusion of Part 1

When you look at the last table you can see first three columns are similar to each other and have nearly same words but last columns’ (mutual information with formula 1) words are different from other columns
We can conclude that the Formula 1 has different behavior and probably is not efficient. So it is better to use formula 2 for calculating Mutual Information

For more accurate comparisons on which of these three metrics are better, we can test it.

In part 2 we are going to test which metric is better, with a classification task.

Part 2

In Part 1 we tried to find good features to vectorize documents. We used three metrics and extracted three set of 100 words.
Each document can be represented by the set of words that appear in the document.
In this part we want to use these sets of features to classify documents with SVM.

Evaluation

For evaluating our classification we used k-fold cross-validation with k=5.
We reported our average of these 5 confusion matrices.

## Vectorizing Documents We wanted to vectorize our documents. We did this with 4 different methods:

1) Using 1000 most frequent words as features set
2) Using Information Gain features
3) Using Mutual Information features
4) Using $\chi$ square features

Storing word frequencies

We need to store word frequency in each document for the processing

1) Using 1000 most frequent words as feature set

There is an ambiguity in defining the meaning of frequent.

• First meaning: A word is frequent if in lots of document there is at least one occurrence of this word.
  
• Second meaning: A word is frequent if the sum of the number of occurrence of this word in all documents is high. (Maybe in one document there are lots of occurrences but in another document, there is no occurrence.)
  

In this code, we chose the first meaning.

The above words are 10 most frequent words in our dataset. And all of them are stop words.

Making Vector X

We want to make the vector for each document and then use this vectors for classification.
We used our 1000 words for vectorizing.

Using SVM for classification

We used svm classifier for our classification.

Confusion Matrix for 1000 most frequent

print ("accuracy:", first_method_accuracy,'\n')
print ("confusion matrix:\n")
first_method_cm = confusion_matrix_avg
pd.DataFrame(first_method_cm)

accuracy: 0.8787209302325582 

confusion matrix:

2) Using 100-dimensional vector with Information Gain

Making Vector X

We want to make vector for each document and then use this vectors for classification

Using SVM for classification

print ("accuracy:", second_method_accuracy,'\n')
print ("confusion matrix:\n")
second_method_cm = confusion_matrix_avg
pd.DataFrame(second_method_cm)

accuracy: 0.806279069767442 

confusion matrix:

3) Using 100-dimensional vector with Mutal Information

We used the better formula for selecting 100 words.

features.head(10)

Making Vector X

We want to make vector for each document and then use this vectors for classification

Using SVM for classification

print ("accuracy:", third_method_accuracy,'\n')
print ("confusion matrix:\n")
third_method_cm = confusion_matrix_avg
pd.DataFrame(third_method_cm)

accuracy: 0.804186046511628 

confusion matrix:

4) Using 100-dimensional vector with $\chi$ Squared

features.head(10)

Making Vector X

We want to make vector for each document and then use this vectors for classification

Using SVM for classification

print ("accuracy:", forth_method_accuracy,'\n')
print ("confusion matrix:\n")
forth_method_cm = confusion_matrix_avg
pd.DataFrame(forth_method_cm)

accuracy: 0.8025581395348838 

confusion matrix:

Comparision

We compare our result with these 4 methods with confusion matrix and accuracy
The result is as follow

preview = pd.DataFrame({'1000words': [first_method_accuracy],
                        'InfoGain': [second_method_accuracy],
                        'mutual info': [third_method_accuracy],
                        "chi squared": [forth_method_accuracy]})
print ("accuracy:")
preview

accuracy:

preview = pd.concat([pd.DataFrame(first_method_confusion_matrix),       
                     pd.DataFrame(second_method_confusion_matrix),
                     pd.DataFrame(third_method_confusion_matrix),
                     pd.DataFrame(forth_method_confusion_matrix)], axis=1)
print ("confusion matrix:")
print ("\t1000 words\t\t\t IG \t\t \t MI \t\t   chi squared")
preview

confusion matrix:
	1000 words			 IG 		 	 MI 		   chi squared

Visualization

We are going to show each one in separated tables:

plt.figure()
plot_confusion_matrix(first_method_cm, classes=class_name,
                      title='Confusion matrix visualization for 1000 most frequent_normalized', normalize=True);
plt.show()

plt.figure()
plot_confusion_matrix(second_method_cm, classes=class_name,
                      title='Confusion matrix visualization for Information gain_normalized', normalize=True);
plt.show()

plt.figure()
plot_confusion_matrix(third_method_cm, classes=class_name,
                      title='Confusion matrix visualization for Mutual information_normalized', normalize=True);
plt.show()

plt.figure()
plot_confusion_matrix(forth_method_cm, classes=class_name,
                      title='Confusion matrix visualization for chi squared_normalized', normalize=True);
plt.show()

Now we want to test the result for most 100 frequent word vector

print ("accuracy:", first_method_accuracy_100,'\n')
print ("confusion matrix:\n")
first_method_cm_100 = confusion_matrix_avg
pd.DataFrame(first_method_cm_100)

accuracy: 0.803953488372093 

confusion matrix:

plt.figure()
plot_confusion_matrix(first_method_confusion_matrix_100, classes=class_name,
                      title='Confusion matrix visualization for 100 most frequent_normalized', normalize=True);
plt.show()

Conclusion

We know that 1000 words are not best words because these words include stop words that they are not informative. But because they are 1000 words rather than 100 words, the result is going to be better.
We test a set of 100 most frequent words. The result was acc = 0.8049 which is similar to other three methods. We also show the confusion matrix for 100 most frequent in the last table above. And you can see this table is also similar to other three ones
So we can guess that there is no significant difference between choosing these metrics for selecting words in document classification task.
And we also know that Information Gain doesn’t store every class information gains (We only stored one number Information Gain for every word). But we can consider each class information gain if we split the Sigma over classes in information gain formula.(And consider the meaning of Entropy for each class). So it has the same functionality as other metrics.
We guess that if the dimension of our vector increase we probably are going to get more accuracy.
And also maybe if we use different features depending on the sequence of words that appear each document, we can get more accuracy.