Reddit is a social media platform contains a massive collection of forums where people can share news and content or comment on other people’s post, and each comment in reddit has a score which is the number of upvotes minus the number of downvotes for the comment. In this project, we focus on the comments in English relate to COVID-19 pandemic. The aim of this project is to classify comments into popular and unpopular classes according to their scores using logistic regression model, and find the potential combinations of words which may lead to a high score. To achieve this, one of the association rule mining algorithms, Frequent-Pattern Growth algorithm will be implemented, which will find the word set contains all the words or combinations of words appear more than a certain number efficiently, and this number is also called the minimum support. Thus, one can build a binary sparse matrix with comments to be rows, and elements in word set to be columns of the matrix, e.g. if a certain word or combination of words appear in one comment, then we assign 1 to that position and 0s elsewhere, and repeat this procedure for every comment. Finally, as each comment associates with a score, we will be able to classify them into popular and unpopular classes, for example, if the score is lower than 300 will be assigned to unpopular class and vice versa. According to the logistic regression model, we will also be able to investigate the weights of elements in word set, thus find the elements with more weight may potentially lead the comments to a high score.
Preamble
Preamble
Data Collection and Exploration
Data Collection and Exploration
The data was fetched from Reddit API, and filtered contents with query “covid-19” and four keys which are “author”, “body”, “created_utc” and “score”. We purposely collected comments with low score and high score, and saved in Excel format, there are 501 comments with score lower than 300 and 100 comments with score higher than 300.
Import data fetched from Reddit API:
In[]:=
data=Import["redditcomments.xlsx"][[1]];
Length of the data:
In[]:=
Length[data]
Out[]=
601
Keys of the data:
In[]:=
keys={"author","body","created_utc","score"};
Create a dataset:
In[]:=
Rasterize[dswith601comments=Dataset[Table[AssociationThread[keysdata[[i]]],{i,Length[data]}]]]
Out[]=
Number of comments with score lower than 300:
In[]:=
Length[dswith601comments[Select[#[["score"]]<300&]]]
Out[]=
501
Number of comments with score higher than 300:
In[]:=
Length[dswith601comments[Select[#[["score"]]>300&]]]
Out[]=
100
The score of comments ranges from 0 to 12831:
In[]:=
MinMax[dswith601comments[[;;,"score"]]]
Out[]=
{0.,12831.}
The time period is between “Wed 12 Feb 2020 15:28:01” to “Thu 4 Jun 2020 02:30:02” in GMT+1:
In[]:=
MinMax[FromUnixTime/@Normal[dswith601comments[[;;,"created_utc"]]]]
Out[]=
,
Frequent-Pattern Growth (FP-Growth) Algorithm
Frequent-Pattern Growth (FP-Growth) Algorithm
Definition (Itemset):
A set of items consists of two or more items is called an itemset. An itemset that occurs more than a certain number of times is called a frequent itemset, and that number is called the minimum support. Thus frequent itemset mining is a data mining technique to identify the items that often occur together.
A set of items consists of two or more items is called an itemset. An itemset that occurs more than a certain number of times is called a frequent itemset, and that number is called the minimum support. Thus frequent itemset mining is a data mining technique to identify the items that often occur together.
Definition (Frequent Pattern Mining(FPM)):
The frequent pattern mining (AKA Association Rule Mining) algorithm is used to discover frequent itemsets and relationships between different items in a dataset. These relationships are represented in the form of association rules, and FPM has many applications in the field of data analysis, software bugs, cross-marketing, etc.
The frequent pattern mining (AKA Association Rule Mining) algorithm is used to discover frequent itemsets and relationships between different items in a dataset. These relationships are represented in the form of association rules, and FPM has many applications in the field of data analysis, software bugs, cross-marketing, etc.
Definition (Apriori algorithm):
Apriori algorithm was the first algorithm that was proposed for frequent itemset mining, and is a sequence of steps to be followed to find the most frequent itemset in the given database.This data mining technique will first scan the database and counts all individual items, and prune individual items that do not appear with the number equal or more than the minimum support threshold assumed by the user, because any itemset contain these individuals will also not appear more than minimum support threshold of times either. Thus a candidate list is generated which contains all feasible individuals, the algorithm starts to find all feasible 2-itemset by joining a new item to the previously found feasible individuals in candidate list, prune any 2-itemsets do not satisfy condition and generate a new candidate list. The algorithm follows the join and the prune steps iteratively until it reaches k-itemset where there is no k+1-itemset frequent.
Apriori algorithm was the first algorithm that was proposed for frequent itemset mining, and is a sequence of steps to be followed to find the most frequent itemset in the given database.This data mining technique will first scan the database and counts all individual items, and prune individual items that do not appear with the number equal or more than the minimum support threshold assumed by the user, because any itemset contain these individuals will also not appear more than minimum support threshold of times either. Thus a candidate list is generated which contains all feasible individuals, the algorithm starts to find all feasible 2-itemset by joining a new item to the previously found feasible individuals in candidate list, prune any 2-itemsets do not satisfy condition and generate a new candidate list. The algorithm follows the join and the prune steps iteratively until it reaches k-itemset where there is no k+1-itemset frequent.
Definition (FP-Growth algorithm):
The FP-Growth algorithm is an improvement to the Apriori method. Because Apriori required multiple scans of the database to check the support count of each item and itemsets. When the database is huge, this will cost a significant amount of storage and computing power. However, FP-growth algorithm will only read off the whole database twice and represents the database in the form of a tree called a frequent pattern tree or FP tree, and generates frequent pattern without the need for candidate generation.
The FP-Growth algorithm is an improvement to the Apriori method. Because Apriori required multiple scans of the database to check the support count of each item and itemsets. When the database is huge, this will cost a significant amount of storage and computing power. However, FP-growth algorithm will only read off the whole database twice and represents the database in the form of a tree called a frequent pattern tree or FP tree, and generates frequent pattern without the need for candidate generation.
The complete FP-growth algorithm implementation is below, and we will explain this with an example in the next section.
In[]:=
sortedminsupcandidatelist[list_,minsup_]:=Module[{ex1,orderedex,exintersection,excandidatelist,conditione,searchlist,l2,sublist,drope,subord,subinter},ex1=DeleteDuplicates/@list;orderedex=ReverseSortBy[Select[Normal[Counts[Flatten[ex1]]],Values[#]≥minsup&],Values[#]&];exintersection=Delete[Intersection[#,Keys[orderedex]]&/@ex1,Position[Intersection[#,Keys[orderedex]]&/@ex1,{}]];excandidatelist=Table[Reverse[exintersection[[i]][[Ordering[Association[orderedex][#]&/@exintersection[[i]]]]]],{i,Length[exintersection]}];searchlist=Drop[Reverse[Keys[orderedex]],-1];{searchlist,excandidatelist,orderedex}]
In[]:=
checking[overalllist_,minsup_,node_,path_,orderedex_]:=Module[{drope,subord,sublist,subinter,newsearchlist,newpath},sublist=overalllist[[#[[1]],;;#[[2]]]]&/@Position[overalllist,node];drope=Drop[#,-1]&/@sublist;subord=Select[Normal[Counts[Flatten[drope]]],Values[#]≥minsup&];subinter=Delete[Intersection[#,Keys[subord]]&/@drope,Position[Intersection[#,Keys[subord]]&/@drope,{}]];newsearchlist=Keys[subord][[Ordering[Association[orderedex][#]&/@Keys[subord]]]];newpath=Catenate[{path,{node}}];{newsearchlist,subinter,{sublist,newpath}}]
In[]:=
sm[input_,minsup_]:=Module[{},Table[NestWhileList[checking[#[[2]],minsup,#[[1,1]],#[[-1,2]],sortedminsupcandidatelist[input,minsup][[-1]]]&,Nest[checking[#[[2]],minsup,#[[1,i]],#[[-1,2]],sortedminsupcandidatelist[input,minsup][[-1]]]&,input,1],Length[#[[1]]]>0&],{i,Length[input[[1]]]}]]
In[]:=
re[input_,minsup_]:=DeleteDuplicates[Catenate[{Flatten[sm[input,minsup],1][[;;,-1]],Module[{kk},If[Length[(kk=Select[Flatten[sm[input,minsup],1],Length[#[[1]]]>1&])]>0,Flatten[Table[sm[kk[[i]],minsup],{i,Length[kk]}],2][[;;,-1]],{}]]}]]
In[]:=
final[input_,minsup_]:=Reverse[#[[-1]]]Length[#[[-2]]]&/@re[input,minsup]
In[]:=
fpgrowth[comments_,minsup_]:=Catenate[{Flatten[final[checking[sortedminsupcandidatelist[comments,minsup][[2]],minsup,#,{},sortedminsupcandidatelist[comments,minsup][[-1]]],minsup]&/@sortedminsupcandidatelist[comments,minsup][[1]],1],sortedminsupcandidatelist[comments,minsup][[-1]]}]
Example of FP-Growth Algorithm
Example of FP-Growth Algorithm
Complete FP Tree Generator
Complete FP Tree Generator
The FP-growth algorithm can be split into two parts, complete FP tree generation and extraction of information. We will start with complete FP tree generation according to each transaction of items, the FP tree is constructed using two passes over the database. Below we are given an example with 10 transactions:
Think about {a, b} to be our first comment, and each letter represents a word.
In[]:=
example={{"a","b","b","a"},{"c","b","d"},{"e","a","d","c"},{"d","a","d","e"},{"a","b","c"},{"b","c","b","d","a"},{"a"},{"b","a","b","c"},{"b","a","d"},{"b","c","e"}};
Number of transactions in example:
In[]:=
Length[example]
Out[]=
10
Visualise data in grid form:
In[]:=
Grid[Catenate[{{{"Transaction","Items"}},Transpose[{Table[i,{i,Length[example]}],example}]}],FrameAll]
Out[]=
Transaction | Items |
1 | {a,b,b,a} |
2 | {c,b,d} |
3 | {e,a,d,c} |
4 | {d,a,d,e} |
5 | {a,b,c} |
6 | {b,c,b,d,a} |
7 | {a} |
8 | {b,a,b,c} |
9 | {b,a,d} |
10 | {b,c,e} |
The first step in FP-growth is to delete duplicates and sort items order in each transaction according to the counts of items in the database.
Counts of items:
In[]:=
sortedminsupcandidatelist[example,2][[-1]]
Sorted items in each transaction:
We have completed the first scan which includes scan data and find support for each item, discard infrequent items and sort items in each transaction. Now we can use sorted items to build the complete FP Tree.
Notice every transaction is coming from a root:
Paths according to each transaction:
Below is the generation of complete FP tree according to each transaction, and the number on the edge representing the number of current items and itemsets, e.g. for the first transaction, there is currently one path from “root” to “a”, and one path from “root” to “a” to “b”:
The function below will generate a complete FP tree according to the complete set of transactions and minimum support threshold, and the second pass has been completed by going through each sorted transactions.
This is the complete FP tree for our example with minimum support = 2 :
Extraction of Information according to complete FP Tree
Extraction of Information according to complete FP Tree
For the second part the algorithm we will extract frequent itemsets directly from the complete FP-tree by searching through it. This will require Bottom-up algorithm which starts from the leaves towards the root, e.g. first search “e”, then {“d”, “e”}, etc. . . then “d”, then {“c”, ”d”}, etc. ., we will give an example below which looks for frequent itemsets ending in “e”.
Recall sorted items:
Extract prefix path end in “e”:
The function below will generate a sub-tree with a choice of node and minimum support, here we have chosen our node to be “e” and minimum support = 2:
As “e” is frequent (count = 3) so we can first extract {“e”}→3 as a frequent set. And now we will need to build a conditional tree which basically discard all nodes end in “e” and discard infrequent items in previous sub-tree.
Simply discard the last element in every transactions:
Discard infrequent nodes, in this case count for “b” is 1 so remove “b”:
The function below is only for illustration purpose for conditional trees generated:
The FP tree conditional on “e”:
As “d” is frequent, count “d” = 2, so {“d”,”e”} →2.
Next we want to consider “d” and “e”, in other words find paths end in “d”, also as previously mentioned we will need to discard the “d” for FP tree conditional on “de”.
Recall transactions conditional on “e”:
Extract prefix path in FP tree conditional on “e” end in “d”:
As “a” is frequent, count “a” = 2, so extract frequent itemset {“a”,“d”,”e”} →2.
Finally we are going to consider “c” according to our previous FP tree conditional on “e”
Recall transactions condition on “e”:
Extract prefix path in FP tree conditional on “e” end in “c”:
As “c” is frequent, count = 2 so extract frequent itemset {“c”,”e”} →2, as “c” is the last leaf node in our bottom-up search we end up here.
The above procedure will go through in every leaf node and iterates itself. In conclusion we have the following:
Analysis of comments
Analysis of comments
This will filter the comment in English language:
We will delete the element “covid-19” as it was used as a searching query so essentially every comment will have “covid-19”, we also delete the stopwords and convert to words to lower case:
After filtering the comments to English only, we have 584 comments instead:
Generating individual items and k-itemsets using FP-growth algorithm with minimum support = 20:
There are 379 individual items and k-itemsets in total:
Convert our original dataset to English only comments dataset:
We have found the word set which contains all the words or combinations of words appear more than a certain number efficiently. Thus, one can build a binary matrix with comments to be rows, and elements in word set to be columns of the matrix, e.g. if a certain word or combination of words appear in one comment, then we assign 1 to that position with 0s elsewhere, and repeat this procedure for every comment.
Create a zero matrix for later insertion:
The dimensions of the zero matrix is {584, 379} which corresponds to 584 comments and 379 elements in word set:
Assign 1 to specific position in zero matrix:
We classify the comments into high and low classes according to their score, if the score is lower than 300 then class low and vice versa:
Assign a class to each row of zero matrix after assigning 1s:
A random sample of 80% overall comments have been selected for training set:
The rest will be test set:
Convert both training and test sets to sparse matrix for faster evaluation:
Use the Classify superfunction with logistic regression method for classification:
Use test set for classifier measurements:
The accuracy of our model:
Generate ROC curve and confusion matrix plots for both classes:
The FPR for high class is small which means there are only a few low class comments, in fact from the confusion matrix plot we know there are 4 out of 101 low class comments misclassified as high class. The FPR for low class is relatively high, and again from the confusion matrix plot, there are 14 out 16 high class comments misclassified as low class. Also, ROC curves for both classes are seem to be good but not excellent, this may hint us to increase the size of data for a more accurate result.
Select the model in our classifier and find out the weights on each element in word set:
Below the top 10 most weighted elements for high class and low class have been selected:
In conclusion this model is accurate with 84.6% accuracy, and for elements in word set, we find the for comments including {“china”, “virus”, “chinese”}, {“just”, “said”}, or {“just”, “cases”} will have a high probability to be more popular, and elements for leading to lower class generally have more weights than elements lead to high class. This also corresponds to FPR discussed previously, that the model makes a more accurate result on classifying the low class. However, there are many more lower class comments than high class comments in our dataset, hence there are several improvements we can make:
1. Increase the number of comments especially the comments with high score;
2. Try more minimum support values;
1. Increase the number of comments especially the comments with high score;
2. Try more minimum support values;
Keywords
Keywords
◼
COVID-19
◼
Association rule mining
◼
Frequent-Pattern Growth algorithm
◼
NLP
Acknowledgment
Acknowledgment
Mentor: Jesse Galef
I wish to take this opportunity to express sincere gratitude to Jesse Galef, who has helped me since the beginning of summer school. He is always patient and positive, and trying his best to help me with any difficulties in this project. I have learnt something that I had no previous knowledge and successfully got something out of it, but I will never be able to achieve this without his help. I would also like to thank all the staff in Wolfram Summer School, for providing such a wonderful and memorable experience during this special time.
References
References
◼
Verhein, F., 2020. [online] Wimleers.com. Available at: <https://wimleers.com/sites/wimleers.com/files/FP-Growth %20 presentation %20 handouts %20 % E2 %80 %94 % C2 % A0Florian %20 Verhein.pdf> [Accessed 10 July 2020].
◼
Ngai, A., 2020. Understand And Build FP-Growth Algorithm In Python. [online] Medium. Available at: <https://towardsdatascience.com/understand-and-build-fp-growth-algorithm-in-python-d8b989bab342> [Accessed 8 July 2020].
◼
GitHub. 2020. Pushshift/Api. [online] Available at: <https://github.com/pushshift/api> [Accessed 5 July 2020].