Actionable pattern discovery for Sentiment Analysis on Twitter Data in clustered environment

2.1 Sentiment analysis and twitter data

The following research papers primarily performed sentimental analysis on twitter data.

Authors A. Balahur et al. [7] employs hybrid approach, using supervised learning with Support Vector Machines Sequential Minimal optimization (Platt, 1998) linear kernel, on unigram and bigram features, emotion lists, slang lists and other social media emotion features for a lexicon based sentimental analysis on the twitter data. The analysis involves two phases, preprocessing and then sentiment classifications. The processed tweets are then passed through the sentiment classification module. Training models were developed on the cluster of computers using Weka data software.

Authors A. Agarwal et al. [9] performed sentimental analysis on the twitter data. As part of the paper, they primarily experimented three types of models, unigram model, a feature based model and a tree kernel based model for two classification tasks, binary task which classifies the sentiment to positive and negative and 3-way task which classifies the sentiment to neutral along with the positive and negative category. The twitter data is first preprocessed using emotion dictionary, acronym dictionary and stop word dictionary. The comparative analysis on the models by experiment proved that tree kernel and feature based models outperform the unigram baseline.

Authors A. Chellal et al. [10] proposed multi-criterion real time tweet summarization based upon adaptive method. This method provides new relevant and non-redundant information about an event as soon as it occurs. The tweets selection is based on the following three criterions: informativeness, novelty and relevance with regards of the user’s interest which are combined as conjunctive condition. Experiments were carried out on TREC MB RTF-2015 data set.

Authors Yu. Xu et al. [15] proposed methods to infer a user’s expertise based on their posts on the popular micro-blogging site twitter. They proposed a sentiment-weighted and topic relation-regularized learning model. Sentiment intensity of a tweet is used to evaluate user’s expertise and the relatedness between expertise topics is exploited to model inference problem. The following four common metrics were used for evaluation: accuracy, precision, recall and F1- score.

Authors F. Marquez et al. [23] proposed a simple model for transferring sentiment labels from words to tweets and vice versa by representing both tweets and words using feature vectors residing in the same feature space. Tweet centroid model developed in this paper outperformed the classification performance of the popular emoticon-based method for data labelling and better results than a classifier trained from tweets labelled based on the polarity of their words.

2.2 Action rules mining

The following research papers deal with Action Rule mining.

Action Rules was first introduced in [11] by Z.W. Ras and A. Wieczorkowska. Action Rules have been extracted using two approaches for more than a decade. One approach is using rule-based approach which extracts intermediate classification rules using algorithms like LERS [5] (to extract classification rules from complete information system) or ERID [3] (to extract rules from incomplete information system) from which Action Rules can be extracted using system DEAR [11] (uses two classification rules to get Action Rules) or system ARoGS [13] (uses single classification rule to extract Action Rules). Second approach is object-based -approach to extract Action Rules directly from the information system, without pre-existing classification rules, using system ARED [6] or Association Action Rules [14]. In this paper, we focus on rule- based approach much like ARoGS [13] and to generate Action Rules.

Performance prediction on Hadoop based distribution systems are generally carried out in two ways. First approach is the machine learning approach, which is often used to predict system performance leveraging past system execution data [9] and can achieve reasonable prediction accuracy. But this requires training the dataset. Second approach is the modelling based approach. Unlike the machine learning approach, modeling based approaches predict performance through modeling system behavior [9], and often can provide a better understanding regarding internal execution of a program and resulting performance.

2.3 Performance prediction analysis for distributed framework

The following research papers deal with performance prediction analysis for distributed processing frameworks.

Authors G. Song et al. [25] propose a framework to predict the performance of a Hadoop MapReduce job. The framework comprises of two modules which are, a lightweight job analyzer module and prediction module. The job analyzer module analyzes the submitted job and collects features related to the jobs and parameters related to the clusters. The prediction module makes use of the collected parameters to train the developed local linear model using local weighted linear regression method. The experimental results vouch the accuracy of the method’s performance prediction.

Authors K. Wang et al. [24] propose a framework to predict the performance of Spark jobs. They apply analytical approaches to predict the performance of Apache Spark jobs. They leverage the multi-stage execution structure of Apache Spark jobs to develop hierarchical models that can effectively capture the execution behavior of different execution stages. They predict the job performance based on the limited scale execution job performance data on cluster. The experimental results show that the prediction accuracy evaluated for iterative and non- iterative algorithms is found to be high for execution time and memory, however the I/O cost prediction varied for different applications.

Authors A. Tzacheva et al. [1] have performed sentimental analysis on the twitter data via Action Rules generated. They implemented the ARoGS [14] algorithm proposed by Ras and Wyrzykowska, to generate the Action Rules. The real-time twitter data is extracted from the twitter API and then fed into the Hadoop Distributed File System – HDFS using MapReduce. Stanford core Natural Language Processing – NLP library was used to identify the polarity attribute through parts of speech (POS) of the tweets. MapReduce programs implementing the ARoGS algorithm was implemented on the twitter data. Experiments were conducted to generate Action Rules to make the user positive and increase the friends count.

In this work, we adapt the Action Rules mining algorithm [13] for twitter data processing. We follow model based approach to evaluate the existing single node machine model, MapReduce model [1] and our proposed Spark model for the Action Rule mining implementation on twitter data. We extend the work proposed by A. Tzacheva et al. [1] by incorporating Spark model for Action Rule mining and comparing performance with the MapReduce model. The proposed model involves simulation of the Action Rules generation by modifying the number of nodes in the cluster. Further, we perform sentiment analysis of twitter data based on discovering actionable patterns through Action Rules.

3.1 Pre-processing

In Pre-processing phase, we perform discretization on the following attributes, friends count, and followers count by placing their values into intervals. As part of this phase, we perform data cleaning for missing values, feature selection and remove unnecessary values. We retained the following attributes Retweet Count, Is Favorited, User ID, Tweet Text, User Language, User Friends Count, User Favorites Count, and User Followers Count.

3.2 Sentiment analysis

In this phase, we add two additional attributes to the existing attribute set, first is sentiment attribute which can take the following values: positive, negative, neutral, very positive, very negative and the second is action attribute with attribute verb for actionable pattern mining because verbs suggest actionable knowledge. The latter was taken from the extracted part of speech from the tweets.

Stanford core NLP powered by Java was used for sentiment analysis. The general sentiment analysis process is shown in Figs. 1 and 2. This NLP suite provides set of natural language analysis tools. The basic distribution provides model files for the analysis of well-edited english, but the engine is compatible with models for other languages [16]. This NLP suite provides various annotators making use of java’s Unicode support, by default UTF-8 encoding but also supports any character encoding. POS – Part of speech, Label tokens with their part-of-speech (POS) tag, using a maximum entropy POS tagger. Out of the annotators we are using tokenizer, part-of-speech, sentiment analysis in our work.

OPEN IN VIEWER

Fig.1

Actionable Pattern Mining system for Twitter Sentiment Analysis.

OPEN IN VIEWER

Fig.2

Sentiment Analysis.

We used LERS [26] algorithm to extract classification rules from twitter data. Classified each tweet as positive, negative, neutral, very positive, very negative. LERS [26] is a Learning from Examples based on Rough Sets which we use to extract classification rules from the information system. Our implementation follows distributed strategy of generating classification rules using LERS system. Figure 3 gives the LERS algorithm. Using the information system S from Table 1, LERS strategy can find all certain and possible rules describing decision attribute d in terms of attributes a, b, and c. LERS can be used as a data strategy to generate classification rules. LERS produces a set of certain and possible rules [26]. We consider only marked certain rules to construct the Action Rules. Since LERS follows bottom-up strategy, it constructs rules with a conditional part of length x, then it continues to construct rules with a conditional part of length x + 1 during the following iterations.

OPEN IN VIEWER

Fig.3

Part-Of-Speech Tagger – Verbs.

For the information system given in Table 1, consider the following as decision support: ( d 1 ) * = { x 1 , x 2 , x 5 , x 8 }(1)( d 2 ) * = { x 3 , x 4 , x 6 , x 7 }(2)

LERS module given in Fig. 4. For the given information system S, extracts certain and possible rules which are given in Table 2.

OPEN IN VIEWER

Fig.4

LERS Algorithm.

ARoGS is Action Rules Discovery Based on Grabbing Strategy, which uses LERS. It was given by Ras and Wyrzykowska in paper [14] as an alternative to system DEAR [19] which extracts Action Rules from a pair of classification rules. The foremost advantage of using ARoGS is that it uses single classification rule to provoke Action Rules. ARoGS uses LERS kind of algorithm to extract Action Rules, without the need of verifying the validity of the certain relations. It just should check if these relations are marked previously by LERS. ARoGS presumes that system LERS construct classification rules describing target decision value. Figures 4 and 5. Together gives the algorithm of ARoGS Fig. 6. Algorithm AR takes each candidate classification rule and form an Action Rule schema which in turn is given to the algorithm ARoGS to build a cluster of Action Rules around each schema. For the classification rules in Table 2, algorithm AR generates following set of Action Rule schema: ARs 1 ( d 1 ⟶ d 2 ) = ( A , ⟶ a 2 ) ^ ( B , ⟶ b 2 ) → ( D , d 1 ⟶ d 2 )(3)ARs 2 ( d 1 ⟶ d 2 ) = ( A , ⟶ a 2 ) ^ ( C , c 2 ) → ( D , d 1 ⟶ d 2 )(4)ARs 3 ( d 1 ⟶ d 2 ) = ( B , ⟶ b 1 ) ^ ( C , c 2 ) → ( D , d 1 ⟶ d 2 )(5)ARs 4 ( d 1 ⟶ d 2 ) = ( B , ⟶ b 2 ) ^ ( C , c 1 ) → ( D , d 1 ⟶ d 2 )(6)

OPEN IN VIEWER

Fig.5

AR (Action Rules) Algorithm in distributed environment using MapReduce.

OPEN IN VIEWER

Fig.6

ARoGs (Action Rules Discovery Based on Grabbing Strategy) in a distributed environment using MapReduce.

Algorithm ARoGS Fig. 6 takes each Action Rule schema and using their flexible and stable attributes, generates following Action Rules which imply d1 ⟶ d2. For the Action Rule schema ARs1, the algorithm ARoGS finds all missing flexible attributes AM: {a1, a3, b1}. Each missing flexible attribute is filled into appropriate action terms. In ARoGS, the maximum number of Action Rules generated = AM. For ARs1, ARoGS produces following Action Rules: AR 1 ( d 1 ⟶ d 2 ) = ( A , a 1 ⟶ a 2 ) ^ ( B , ⟶ b 2 ) → ( D , d 1 ⟶ d 2 )(7)AR 2 ( d 1 ⟶ d 2 ) = ( A , a 3 ⟶ a 2 ) ^ ( B , ⟶ b 2 ) → ( D , d 1 ⟶ d 2 )(8)

Let an action rule R takes a form of: ( Y 1 ⟶ Y 2 ) → ( Z 1 ⟶ Z 2 )(9) where,

Y is the condition part of R

Z is the decision part of R

Y1 is a set of all left side of the all condition action terms

Y1 is a set of all right side of the all condition action terms

Z1 is the decision attribute value on left side

Z2 is the decision attribute value on right side

Let an Action Rule R takes a form of: (Y1 ⟶ Y2) ⟶ (Z1 ⟶ Z2) where, Y is the condition part of R, Z is the decision part of R.

Y1 is a set of all left side of the all condition action terms Y2 is a set of all right side of the all condition action terms Z1 is the decision attribute value on left side Z2 is the decision attribute value on right side.

In [13], the support and confidence of an Action Rule R is given as, Support ( R ) = min { card ( Y 1 ∩ Z 1 ) , card ( Y 2 ∩ Z 2 ) }(10)Confidence ( R ) = [ card ( Y 1 ∩ Z 1 ) ] / Card ( Y 1 ) · [ card ( Y 2 ∩ Z 2 ) ] / card ( Y 2 )(11)

In this paper, we use the following support and confidence formula given by Tzacheva et al. [18] to reduce the complexity. Support ( R ) = { card ( Y 2 ∩ Z 2 ) }(12)Confidence ( R ) = [ card ( Y 2 ∩ Z 2 ) ] / Card ( Y 2 )(13)

Overview of MR – Random-Forest algorithm for distributed Action Rules discovery using Apache Hadoop framework and Google MapReduce [4] is shown in Fig. 7. An overview of the proposed algorithm is shown on Fig. 8. We take as an input a set of files: the data, the attribute names, user specified parameters such as: minimum support, and confidence thresholds, stable attribute names, flexible attribute names, decision attribute choice, decision attribute value to change from, and decision attribute value to change to, which is the desired value of decision attribute (desired object state). We import these input files into the HDFS (Hadoop Distributed File System).

OPEN IN VIEWER

Fig.7

MR – Overview of MapReduce execution. The data partitions and results from Map and Reduce tasks reside in the distributed file system. The Map tasks and Reduce tasks are done in the distributed systems in a parallel fashion.

OPEN IN VIEWER

Fig.8

MR – Random Forest Algorithm for Distributed Action Rules Discovery.

The Action Rules generated in section B comprises only one specific action terms. The left side of other action terms are empty. These Action Rules can give only a limited knowledge to the user and leave the clueless due to the lack of specific action terms. In this paper, we propose a new algorithm Specific Action Rule discovery based on Grabbing Strategy (SARGS) as an alternative to the algorithm ARoGS to fill all missing values in the Action Rule schema in an efficient time.

Algorithm SARGS takes each Action Rule schema and finds all missing flexible attribute values. The algorithm then combines each missing value with other values giving a complete set of values that can fill all missing (left-side) of the conditional part of the Action Rule. For example, consider the Action Rule schema ARs1 shown in Section B. The algorithm SARGS finds all missing flexible attribute values AM: {{a1, a3}, {b1}}. Note that AM takes a form of main set containing a collection of multiple sets.

The algorithm then combines each element in the inner set with other elements in other inner sets. Thus, we get a combination of attribute values AC 1 = {a1, b1} and AC 2 = {a3, b1}. The algorithm puts each combination into corresponding Action Rule schema to generate following Action Rules:

New AR (Action Rules) Algorithm in a distributed environment using MapReduce AR 3 : ( d 1 ⟶ d 2 ) = ( A , a 1 ⟶ a 2 ) · ( B , b 1 ⟶ b 2 ) ⟶ ( D , d 1 ⟶ d 2 )(14)AR 4 : ( d 1 ⟶ d 2 ) = ( A , a 3 ⟶ a 2 ) · ( B , b 1 ⟶ b 2 ) ⟶ ( D , d 1 ⟶ d 2 )(15)

Unlike the algorithm ARoGS, algorithm SARGS does not produce any incomplete Action Rules. Instead it provides more specific Action Rules.

Spark [21] is a framework like MapReduce [4] to process large quantity of data in a short span of time. Spark introduces a distributed memory abstraction method called Resilient Distributed Datasets (RDD). Lineage graph utilized by RDD’s is shown in Fig. 11. Spark framework can outperform Hadoop MapReduce because of its in-memory capability, especially for iterative algorithms. Sparks performs as shown in Fig. 9. In [18], Hadoop manages data distribution over the nodes in a cluster and all algorithms ARoGS [13] and Association Action Rules [14], are implemented using MapReduce. When Hadoop manages data distribution, there are some possibilities that all records of single decision value move to a single Partition which can cause some loss of valuable Action Rules. In this paper, we propose a method similar to stratified sampling for data distribution to all partitions. We split the given data into groups where each group consists of records matching single decision value. We then measure how much proportion of data each decision value takes. According to this proportion, we take random samples of data from each group. By this way, each partition contains same proportion of data which is equal to the original dataset.

OPEN IN VIEWER

Fig.9

Overview of Spark execution using Resilient Distributed Datasets (RDD). Tasks such as transformations are given to the slave nodes. Slaves after performing the tasks, cache the result in RAM. Results can be given back to the Driver node.

Figure 10 Shows an example data partition for the information system S shown in Table 1. Our algorithms LERS and SARGS executes on each of these partitions and final Action Rules are grouped together. In Spark, reading each file: attributes, parameters and data creates three different RDDs. We manually split the data file into ‘d’ files, where d is a distinct number of decision values. Each file contains samples of records from the given data file. Spark on reading each of these files create ‘d’ RDDs. We also broadcast RDDs created from reading attributes and parameters file, so that all nodes can access them. Algorithms LERS and SARGS runs on each of d RDDs using Map Partition function, which is used to perform computations on each and every partition of data, and results in their own set of Action Rules with support and confidence. All Action Rules from the Map Partition function are sorted by the attribute name and returned as (Key, Value) pairs. We chose Action Rule to be a Key and support and confidence pair to be a Value. We then use groupByKey method to group all supports and confidences of a single Action Rule and aggregate them to calculate final support ‘fs’ and confidence ‘fc’ of an Action Rule. We output these Action Rules to a text file if fs > = minimumSupport and fc > = minimumConfidence. Now we describe the LERS, ARoGS algorithms and new SARGS method in detail. Consider an information system S: S = ( X , A , VA )(16) where,

X is a set of objects: X ={ x1,  x2,  x3,  x4,  x5 }

OPEN IN VIEWER

Fig.10

Data Distribution to partitions.

OPEN IN VIEWER

Fig.11

Spark Lineage Graph Example.

A is a set of attributes: A = A, B, C, D and

VA represents a set of values for each attribute in A. For Example, VB = b0, b2.

We use the sample information system S shown in Table 1 to demonstrate outputs from the above-mentioned algorithms. Consider attribute C to be a Stable Attribute, attributes A, B to be Flexible Attributes, attribute D to be the Decision Attribute, and that the user desires the decision value to change from d1 to d2. Also, consider that the user is interested in Action Rules with minimum support of 1 and minimum confidence of 80%. Instead of giving the data entirely to the Spark, we do some pre-processing step to make partitions of data to be given to Spark. All algorithms are then made to run on each partition of data. Following sub- sections talk about our implementation of these algorithms in a distributed environment.

This experiment is focused in improving the user friends and followers count. The input attribute details are as follows: Stable Attributes are User Id and UserLanguage; Decision attribute is UserFriendsCount; Minimum support is 2 and confidence is 60%. The sample Action Rule generated for the experiment is recorded in the Tables 5 and 6.

This experiment is focused in transforming the tweet sentiment attribute value from negative to positive. The input attribute details are as follows: Stable Attribute is UserLanguage; Decision attribute is Tweet Sentiment; Minimum support is 2 and confidence is 60%. The sample Action Rule generated for the experiment is recorded in the Tables 7 and 8.

This experiment is focused in transforming the tweet sentiment attribute value from negative to positive. The input attribute details are as follows: Stable Attribute is UserLanguage; Decision attribute is Tweet Sentiment; Minimum support is 2 and confidence is 60%. The sample Action Rule generated for the experiment is recorded in the Tables 9 and 10.

Our experiments show that with the volume of Twitter data, the processing of the proposed algorithm runs faster on distributed environment than on single machine. The experimental results explaining the time taken for the Hadoop and Spark system to generate the Action Rules and the number of Action Rules generated are tabulated in the Table 11.

The Action Rules are assessed using the support and confidence metrics. User specified threshold of support 2, and confidence 60% were applied.