Large Scale Sentiment Analysis on Twitter with Spark

Abstract

Sentiment analysis on Twitter data has attracted much attention recently. One of the system's key features, is the immediacy in communication with other users in an easy, user-friendly and fast way. Consequently, people tend to express their feelings freely, which makes Twitter an ideal source for accumulating a vast amount of opinions towards a wide diversity of topics. This amount of information o ers huge potential and can be harnessed to receive the sentiment tendency towards these topics. However, since none can invest an in nite amount of time to read through these tweets, an automated decision making approach is necessary. Nevertheless, most existing solutions are limited in centralized environments only. Thus, they can only process at most a few thousand tweets. Such a sample, is not representative to de ne the sentiment polarity towards a topic due to the massive number of tweets published daily. In this paper, we go one step further and develop a novel method for sentiment learning in the Spark framework. Our algorithm exploits the hashtags and emoticons inside a tweet, as sentiment labels, and proceeds to a classi cation procedure of diverse sentiment types in a parallel and distributed manner. Moreover, we utilize Bloom lters to compact the storage size of intermediate data and boost the performance of our algorithm. Through an extensive experimental evaluation, we prove that our solution is e cient, robust and scalable and con rm the quality of our sentiment identi cation.

-

big data; Bloom lters; classi cation; MapReduce; Spark; sentiment analysis; text mining; Twitter c 2016, Copyright is with the authors. Published in the Workshop Proceedings of the EDBT/ICDT 2016 Joint Conference (March 15, 2016, Bordeaux, France) on CEUR-WS.org (ISSN 1613-0073). Distribution of this paper is permitted under the terms of the Creative Commons license CCby-nc-nd 4.0

1. INTRODUCTION

Nowadays, users tend to disseminate information, through short 140-character messages called "tweets", on di erent aspects on Twitter. Furthermore, they follow other users in order to receive their status updates. Naturally, Twitter constitutes a wide spreading instant messaging platform and people use it to get informed about world news, recent technological advancements, etc. Inevitably, a variety of opinion clusters that contain rich sentiment information is formed. Sentiment is de ned as "A thought, view, or attitude, especially one based mainly on emotion instead of reason"1 and describes someone's mood or judge towards a speci c entity.

Knowing the overall sentiment inclination towards a topic, may be proved extremely useful in certain cases. For instance, a technological company would like to know what their customers think about the latest product, in order to receive helpful feedback that will utilize in the production of the next device. So, it is obvious that an inclusive sentiment analysis for a time period after the release of the new product is needed. Moreover, user-generated content that captures sentiment information has proved to be valuable among many internet applications and information systems, such as search engines or recommendation systems.

In the context of this work, we utilize hashtags and emoticons as sentiment labels to perform classi cation of diverse sentiment types. Hashtags are a convention for adding additional context and metadata and are extensively utilized in tweets [ 23 ]. Their usage is twofold: they provide categorization of a message and/or highlight of a topic and they enhance the searching of tweets that refer to a common subject. A hashtag is created by pre xing a word with a hash symbol (e.g. #love). Emoticon refers to a digital icon or a sequence of keyboard symbols that serves to represent a facial expression, as :-( for a sad face2. Both, hashtags and emoticons, provide a ne-grained sentiment learning at tweet level which makes them suitable to be leveraged for opinion mining.

The problem of sentiment analysis has been studied extensively during recent years. The majority of existing so1http://www.thefreedictionary.com/sentiment 2http://dictionary.reference.com/browse/emoticon lutions is bounded in centralized environments and base on natural language processing techniques and machine learning approaches. However, this kind of techniques are timeconsuming and computationally intensive [ 16, 22 ]. As a result, it is prohibitive to process more than a few thousand tweets without exceeding the capabilities of a single server.

On the contrary, millions of tweets are published daily on Twitter. Consequently, underline solutions are neither su cient nor suitable for opinion mining, since there is a huge mismatch between their processing capabilities and the exponential growth of available data [ 16 ]. It is more than clear that there is an imperative need to turn to high scalable solutions. Cloud computing technologies provide tools and infrastructure to create such solutions and manage the input data in a distributed way among multiple servers. The most prominent and notably e cient tool is the MapReduce [ 7 ] programming model, developed by Google, for processing large-scale data.

In this paper, we propose a novel distributed algorithm implemented in Spark [ 13, 21 ], an open source platform that translates the developed programs into MapReduce jobs. Our algorithm exploits the hashtags and emoticons inside a tweet, as sentiment labels, in order to avoid the timeintensive manual annotation task. After that, we perform a feature selection procedure to build the feature vectors of training and test set. Additionally, we embody Bloom lters to increase the performance of the algorithm. Finally, we adjust an existing MapReduce classi cation method based on AkNN queries to perform a fully distributed sentiment classi cation algorithm. We study various parameters that can a ect the total computation cost and classi cation performance, such as size of dataset, number of nodes, increase of k, etc. by performing an extensive experimental evaluation. We prove that our solution is e cient, robust and scalable and verify the classi cation accuracy of our approach.

The rest of the paper is organized as follows: in Section 2 we discuss related work, the MapReduce model and Spark framework and in Section 3 we present how our algorithm works. More speci cally, we explain how to build the feature vectors (for both the training and test dataset), we brie y describe the Bloom lter integration and display our Spark classi cation algorithm using pseudo-code. After that, we proceed to the experimental evaluation of our approach in Section 4, while in Section 5 we conclude the paper and present future steps.

PRELIMINARIES

Previous Work

Although the notion of sentiment analysis, or opinion mining, is relatively new, the research around this domain is quite extensive. Early studies focus on document level sentiment analysis concerning movie or product reviews [ 11, 30 ] and posts published on web pages or blogs [ 29 ]. Due to the complexity of document level opinion mining, many e orts have been made towards the sentence level sentiment analysis. The solutions presented in [ 25, 26, 28 ] examine phrases and assign to each one of them a sentiment polarity (positive, negative, neutral). A less investigated area is the topic-based sentiment analysis [ 15, 17 ] due to the difculty to provide an adequate de nition of topic and how to incorporate the sentiment factor into the opinion mining task.

The most common approaches to confront the problem of sentiment analysis include machine learning and/or natural language processing techniques. In [ 20 ], the authors employ Naive Bayes, Maximum Entropy and Support Vector Machines to classify movie reviews as positive or negative, and perform a comparison between the methods in terms of classi cation performance. On the other hand, Nasukawa and Yi [ 18 ] strive to identify semantic relationships between the sentiment expressions and the subject. Together with a syntactic parser and a sentiment lexicon their approach manages to augment the accuracy of sentiment analysis within web pages and online articles. Furthermore, Ding and Liu [ 8 ] de ne a set of linguistic rules together with a new opinion aggregation function to detect sentiment orientations in online product reviews.

During the last ve years, Twitter has received much attention for sentiment analysis. In [ 2 ], the authors proceed to a 2-step classi cation process. In the rst step, they separate messages as subjective and objective and in the second step they distinguish the subjective tweets as positive or negative. Davidov et al. [ 6 ] evaluate the contribution of di erent features (e.g. n-grams) together with a kNN classi er. They take advantage of the hashtags and smileys in tweets to de ne sentiment classes and to avoid manual annotation. In this paper, we adopt this approach and greatly extend it to support the analysis of large scale Twitter data. Agarwal et al. [ 1 ] investigate the use of a tree kernel model for detecting sentiment orientation in tweets. A three-step classi er is proposed in [ 12 ] that follows a target-dependent sentiment classi cation strategy. Moreover, a graph-based model is proposed in [ 23 ] to perform opinion mining in Twitter data from a topic-based perspective. A more recent approach [ 27 ], builds a sentiment and emoticon lexicon to support multidimensional sentiment analysis of Twitter data. A large scale solution is presented in [ 14 ] where the authors build a sentiment lexicon and classify tweets using a MapReduce algorithm and a distributed database model. Although the accuracy of the method is good, it su ers from the timeconsuming construction of the sentiment lexicon. Our approach is much simpler and fully exploits the capabilities of Spark framework. To our best knowledge, we are the rst to present a Spark-based large scale approach for opinion mining on Twitter data without the need of building a sentiment lexicon or proceeding to any manual data annotation. 2.2

MapReduce Model

Here, we brie y describe the MapReduce model [ 7 ]. The data processing in MapReduce is based on input data partitioning; the partitioned data is executed by a number of tasks in many distributed nodes. There exist two major task categories called Map and Reduce respectively. Given input data, a Map function processes the data and outputs keyvalue pairs. Based on the Shu e process, key-value pairs are grouped and then each group is sent to the corresponding Reduce task. A user can de ne his own Map and Reduce functions depending on the purpose of his application. The input and output formats of these functions are simpli ed as key-value pairs. Using this generic interface, the user can solely focus on his own problem. He does not have to care how the program is executed over the distributed nodes, about fault tolerant issues, memory management, etc. The architecture of MapReduce model is depicted in Figure 1.

Spark Framework

Apache Spark [ 13, 21 ] is a fast and general engine for large-scale data processing. In essence, it is the evolution of Hadoop [ 10, 24 ] framework. Hadoop is the the open source implementation of the MapReduce model and is widely used for distributed processing among multiple servers. It is ideal for batch-based processes when we need to go through all data. However, its performance drops rapidly for certain problem types (e.g. when we have to deal with iterative or graph-based algorithms).

Spark is a uni ed stack of multiple closely integrated components and overcomes the issues of Hadoop. It has a Directed Acyclic Graph (DAG) execution engine that supports cyclic data ow and in-memory computing. As a result, it can ran programs up to 100x faster than Hadoop in memory, or 10x faster on disk. Spark includes a stack of libraries that combine SQL, streaming, machine learning and graph processing in a single engine. Spark o ers many high level mechanisms, such as caching, and makes easy to build distributed applications in Java, Python, Scala and R. The applications are translated into MapReduce jobs and run in parallel. Furthermore, Spark can access di erent data sources, such as HDFS or HBase.

3. SENTIMENT CLASSIFICATION FRAME

WORK

In the beginning of this section, we de ne some notation used throughout this paper and then provide a formal de nition of the confronted problem. After that, we introduce the features we use to build the feature vector. Finally, we describe our Spark algorithm using pseudo-code and proceed to a step by step explanation. Table 1 lists the symbols and their meanings.

Assume a set of hashtags H = fh1; h2; : : : ; hng and a set of emoticons E = fem1; em2; : : : ; emmg associated with a set of tweets T = ft1; t2; : : : ; tlg (training set). Each t 2 T carries only one sentiment label from L = H [ E. This means that tweets containing more that one labels from L are not candidates for T , since their sentiment tendency may be vague. However, there is no limitation in the number of hashtags or emoticons a tweet can contain, as long as they are non-con icting with L. Given a set of unlabelled tweets T T = ftt1; tt2; : : : ; ttkg (test set), we aim to infer the sentiment polarities p = fp1; p2; : : : ; pkg for T T , where pi 2 L [ fneug and neu means that the tweet carries no sentiment information. We build a tweet-level classi er C and adopt a kNN strategy to decide the sentiment tendency 8tt 2 T T . We implement C by adapting an existing MapReduce classi cation algorithm based on AkNN queries [ 19 ], as described in Subsection 3.3. 3.1

Feature Description

In this subsection, we present in detail the features used in order to build classi er C. For each tweet we combine its features in one feature vector. We apply the features proposed in [ 6 ] with some necessary modi cations. The reason of these alterations is to adapt the algorithm to the needs of large-scale processing in order to achieve an optimal performance. 3.1.1

Word and N-Gram Features

Each word in a tweet is treated as a binary feature. Respectively, a sequence of 2-5 consecutive words in a sentence is regarded as a binary n-gram feature. For each word or Nf n-gram feature f we estimate its weight as wf = count(f) . Consequently, rare words and n-grams have a higher weight than common words and have a greater e ect on the classication task. Moreover, if we encounter sequences of two or more punctuation symbols inside a tweet, we consider them as word features. Unlike what authors propose in [ 6 ], we do not include the substituted meta-words for URLs, references and hashtags (URL, REF and TAG respectively) as word features (see and Section 4). Additionally, the common word RT, which means "retweet", does not constitute a feature. The reason for omission of these words from the feature list lies in the fact that they appear in the majority of tweets inside the dataset. So, their contribution as features is negligible, whilst they lead to a great computation burden during the classi cation task. 3.1.2

Pattern Features

We apply the pattern de nitions given in [ 5 ] for automated pattern extraction. The words are divided into three categories: high-frequency words (HFWs), content words (CWs) and regular words (RWs). Assume a word f and its corpus frequency f rf ; if f rf > FH , then f is considered to be a HFW. On the other hand, if f rf < FC , then f is considered to be a CW. The rest of the words are characterized as RWs. The word frequency is estimated from the training set rather than from an external corpus. In addition, we treat as HFWs all consecutive sequences of punctuation characters as well as URL, REF, TAG and RT meta-words for pattern extraction, since they play an important role in pattern detection. We de ne a pattern as an ordered sequence of HFWs and slots for content words. The upper bound for FC is set to 1000 words per million and the lower bound for FH is set to 10 words per million. In contrary to [ 5 ], where FH is set to 100 words per million, we provide a smaller lower bound since the experimental evaluation produced better results. Observe that the FH and FC bounds allow overlap between some HFWs and CWs. To address this issue, we follow a simple strategy as described next: if f rf 2 FH ; FH +2FC the word is classi ed as HFW, else if f rf 2 h FH +2FC ; FC the word is classi ed as CW. More strategies can be explored but this is out of the scope of this paper and is left for future work.

We seek for patterns containing 2-6 HFWs and 1-5 slots for CWs. Moreover, we require patterns to start and to end with a HFW, thus a minimal pattern is of the form [HFW][CW slot][HFW]. Additionally, we allow approximate pattern matching in order to enhance the classi cation performance. Approximate pattern matching resembles exact matching, with the di erence that an arbitrary number of RWs can be inserted between the pattern components. Since the patterns can be quite long and diverse, exact matches are not expected in a regular base. So, we permit approximate matching in order to avoid large sparse feature vectors. The Np weight wp of a pattern feature p is de ned as wp = count(p) Np in case of exact pattern matching and as wp = count(p) in case of approximate pattern matching, where = 0:1 in all experiments. 3.1.3

Punctuation Features

The last feature type is divided into ve generic features as follows: 1) tweet length in words, 2) number of exclamation mark characters in the tweet, 3) number of question mark characters in the tweet, 4) number of quotes in the tweet and 5) number of capital/capitalized words in the tweet. The weight wp of a punctuation feature p is de ned as wp = Mp (Mw+MNpng+Mpa)=3 , where Mw; Mng; Mpa declare the maximal values for word, n-gram and pattern feature groups, respectively. So, wp is normalized by averaging the maximal weights of the other feature types. 3.2

Bloom Filter Integration

Bloom lters are data structures proposed by Bloom [ 3 ] for checking element membership in any given set. A Bloom lter is a bit vector of length z, where initially all the bits are set to 0. We can map an element into the domain between 0 and z 1 of the Bloom lter, using q independent hash functions hf1; hf2; :::; hfq. In order to store each element e into the Bloom lter, e is encoded using the q hash functions and all bits having index positions hfj (e) for 1 j q are set to 1.

Bloom lters are quite useful and are primary used to compress the storage space needed for the elements, as we can insert multiple objects inside a single Bloom lter. In the context of this work, we employ Bloom lters to transform our features to bit vectors. In this way, we manage to boost the performance of our algorithm and slightly decrease the storage space needed for feature vectors. Nevertheless, it is obvious that the usage of Bloom lters may impose errors when checking for element membership, since two di erent elements may end up having exactly the same bits set to 1. The error probability is decreased as the number of bits and hash functions used grows. As shown in the experimental evaluation, the side e ects of Bloom lters are negligible. 3.3

kNN Classification Algorithm In order to assign a sentiment label for each tweet in T T , we apply a kNN strategy. Initially, we build the feature vectors for all tweets inside the training and test datasets (FT and FT T respectively). Then, for each feature vector u in FT T we nd all the feature vectors in V FT that share at least one word/n-gram/pattern feature with u (matching vectors). After that, we calculate the Euclidean distance d(u; v); 8v 2 V and keep the k lowest values, thus forming Vk V and each vi 2 Vk has an assigned sentiment label Li; 1 i k. Finally, we assign u the label of the majority of vectors in Vk. If no matching vectors exist for u, we assign a "neutral" label. We build C by adjusting an already implemented AkNN classi er in MapReduce to meet the needs of opinion mining problem. 3.4

Algorithmic Description

In this subsection, we describe in detail the sentiment classi cation algorithm as implemented in the Spark framework. Our approach consists of a single Spark program that runs in parallel. The logical ow of our solution can be divided into four consecutive steps:

Feature Extraction: Extract the features from all tweets in T and T T Feature Vector Construction: Build the feature vectors FT and FT T respectively Distance Computation: For each vector u 2 FT T nd the matching vectors (if any exist) in FT Sentiment Classi cation: Assign a sentiment label 8tt 2 T T

The pseudo-code of our approach follows and we analyze each step in detail. Our algorithm receives as input the les containing the training and the test datasets. After reading the les, it creates a uni ed dataset in memory which is required for further processing.

At rst, the algorithm utilizes the cached data and derives the aforementioned features using the function GetFeatures(). According to the feature type, it extracts for each tweet in the dataset the corresponding features. Then, it groups features by key and creates an inverted index. The feature plays the role of the key and the value is a list of tweets that contain the feature, along with the corresponding weight of the feature for each tweet. The union of all inverted indexes consists the feature vectors.

In the next step, for each feature we separate the tweets that contain it into two lists, LST (training set tweets) and Sentiment Classi cation Algorithm 1: function SCA(training f ile; test f ile) 2: t = GetContent(training f ile); 3: tt = GetContent(test f ile); 4: d = t:union(tt); // Create a united dataset 5: d:cache(); // Cache dataset to memory 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: // Get all feature types wf = GetFeatures(W ORD; d); ngf = GetFeatures(N GRAM; d); pf = GetFeatures(P AT T ERN; d); puf = GetFeatures(P U N CT U AT ION; d); // Get feature vectors f v = wf:union(ngf ):union(pf ):union(puf ); // Get matching vectors mvm = f v:f latM ap(newM V M ap()); mvp = mvm:mapT oP air(newM V P M ap()); mv = mvp:groupByKey(); // Compute distances dcm = mv:f latM ap(newDistCalcM ap()); dcpm = dcm:mapT oP air(newDistCalcP M ap()); distCalc = dcpm:groupByKey(); 21: // Tweet classification 22: tc = distCalc:mapV alues(newM axClass()); 23: // Calculate accuracy and return it 24: j = tc:join(tt); 25: f = j:f ilter((x; y) : x:class == y:class); 26: returnf:count=tt:count; 27: end function 28: function GetFeatures(type; dataset) 29: // Create feature objects based on type 30: f m = dataset:f latM ap(newRecordM ap(type)); 31: // Map each object to a feature key 32: f p = f m:mapT oP air(newF eatureP airM ap()); 33: // Find feature weight in each tweet 34: f = f p:groupByKey():mapV alues(newW eight()); 35: returnf:cache(); 36: end function LST T (test set tweets). After that, 8ltt 2 LST T we create pairs for all elements in LST . As a result, 8tt 2 T T we construct a set of matching vectors V . Using this set, we calculate the Euclidean distances and keep the k lowest values and form Vk V . Finally, we assign 8tt 2 T T the label of the majority of vectors in their respective Vk. The algorithm returns the classi cation accuracy of our method.

Our solution relies on high level operators o ered by Spark. These operators (e.g. atMap, mapToPair, etc.) are designed to distribute the workload equally among the nodes of the cluster to achieve high performance. Although our algorithm resembles a sequential execution of commands, it is fully distributed and exploits the capabilities o ered by the framework.

EXPERIMENTAL EVALUATION

In this section, we conduct a series of experiments to evaluate the performance of our method under many di erent perspectives. More precisely, we take into consideration the e ect of k and Bloom lters, the space compaction ratio, the size of the dataset and the number of nodes in the performance of our solution.

Our cluster includes 4 computing nodes (VMs), each one of which has four 2.4 GHz CPU processors, 11.5 GB of memory, 45 GB hard disk and the nodes are connected by 1 gigabit Ethernet. On each node, we install Ubuntu 14.04 operating system, Java 1.8.0 66 with a 64-bit Server VM, and Spark 1.4.1. One of the VMs serves as the master node and the other three VMs as the slave nodes. Moreover, we apply the following changes to the default Spark con gurations: we use 12 total executor cores (4 for each slave machine), we set the executor memory equal to 8 GB and the driver memory to 4 GB.

We evaluate our method using two Twitter datasets (one for hashtags and one for emoticons) that we have collected through the Twitter Search API3 between November 2014 to August 2015. We have used four human non-biased judges to create a list of hashtags and a list emoticons that express strong sentiment (e.g #amazed and :(). Then, we proceed to a cleaning task to exclude from the lists the hashtags and emoticons that either were abused by twitter users (e.g. #love) or returned a very small number of tweets. We ended up with a list of 13 hashtags (i.e. H = f#amazed, #awesome, #beautiful, #bored, #excited, #fun, #happy, #lol, #peace, #proud, #win, #wow, #wtfg) and a list of 4 emoticons (i.e. E = f :), :(, xD, <3g).

We preprocessed the datasets we collected and kept only the English tweets which contained 5 or more proper English words4 and do not contain two or more hashtags or emoticons from the aforementioned lists. Moreover, during preprocessing we have replaced URL links, hashtags and references by URL/REF/TAG meta-words as stated in [ 6 ]. The nal hashtags dataset contains 942188 tweets (72476 tweets for each class) and the nal emoticons dataset contains 1337508 tweets (334377 tweets for each class). The size of the hashtags dataset is 102.78 MB and the size of the emoticons dataset is 146.4 MB. In both datasets, hashtags and emoticons are used as sentiment labels and for each sentiment label there is an equal amount of tweets. Finally, in order to produce no-sentiment datasets we used Sentiment140 API5 [ 9 ] and the dataset used in [ 4 ], which is publicly available6. We fed the no hashtags/emoticons tweets contained in this dataset to the Sentiment140 API and kept the set of neutral tweets. We produced two no-sentiment datasets by randomly sampling 72476 and 334377 tweets from the neutral dataset. These datasets are used for the binary classi cation experiments (see Section 4.1).

We assess the classi cation performance of our algorithm using the 10-fold cross validation method and measuring the accuracy. For the Bloom lter construction we use 999 bits and 3 hash functions. In order to avoid a signi cant amount of computations that greatly a ect the running performance of the algorithm, we de ne a weight threshold w = 0:005 for feature inclusion in the feature vectors. In essence, we eliminate the most frequent words that have no substantial contribution to the nal outcome. 3https://dev.twitter.com/rest/public/search 4To identify the proper English word we used an available WN-based English dictionary 5http://help.sentiment140.com/api 6https://archive.org/details/twitter_cikm_2010

Classification Performance

In this subsection, we measure the classi cation performance of our solution using the classi cation accuracy. We de ne classi cation accuracy as acc = jCT j=jT T j, where jCT j is the number of test set tweets that were classi ed correctly and jT T j is the cardinality of T T . We present the results of two experimental con gurations, the multi-class classi cation and the binary classi cation. Under multi-class classi cation setting, we attempt to assign a single sentiment label to each of vectors in the test set. In the binary classi cation experiment, we check if a sentence is suitable for a speci c label or does not carry any sentiment inclination. As stated and in [ 6 ], the binary classi cation is a useful application and can be used as a lter that extracts sentiment sentences from a corpus for further processing. Moreover, we measure the in uence of Bloom lters in the classi cation performance. The value k for the kNN classi er is set to 50. The results of the experiments are displayed in Table 2. In case of binary classi cation, the results depict the average score for all classes.

Looking at the outcome in Table 2 we observe that the performance of multi-class classi cation in not very good, although is way above the random baseline. Furthermore, the results with and without Bloom lters di er marginally. The same thing happens for the binary classi cation con guration, however this time the accuracy of our approach is notably better. This is expected due to the lower number of sentiment types. This behavior can also be explained by the ambiguity of hashtags and some overlap of sentiments. Nevertheless, there is a slight increase in the classi cation performance of our algorithm when employing Bloom lters, which is somewhat unexpected. Table 3 presents the fraction of test set tweets that are classi ed as neutral because no matching vectors are found. Notice that the integration of Bloom lters, leads to a bigger number of tweets with no matching vectors. Obviously, the excluded tweets have an slight e ect to the performance of the kNN classi er. Overall, the results for binary classi cation verify the usefulness of our approach. 4.2

Effect of k

In this subsection, we measure the e ect of k in the classication performance of the algorithm. We test four di erent con gurations where k 2 f50; 100; 150; 200g. The outcome of this experimental evaluation is demonstrated in Table 4. For both binary and multi-class classi cation, increasing k a ects slightly (or not at all) the classi cation accuracy when we embody Bloom lters. In the contrary ,without Bloom lters, there is a bigger enhancement in the accuracy performance for both classi cation con gurations (up to 3%). The inference of this experiment, is that larger values of k can provide a good impulse in the performance of the algorithm when not using Bloom lters. However, larger values of k mean more processing time. Thus, Bloom lters manage to improve the binary classi cation performance of the algorithm and at the same time they reduce the total processing cost. 4.3

Space Compression

As stated and above, the Bloom lters can compact the space needed to store a set of elements. In this subsection, we elaborate on this aspect and present the compression ratio in the feature vectors when exploiting Bloom lters (in the way presented in Section 3.2) in our framework. The outcome of this measurement is depicted in Table 5. In the majority of the cases, the Bloom lters manage to marginally diminish the storage space required for the feature vectors (up to 3%). In one case (multi-class hashtags), the decrease in the required space is signi cant (almost 9%). The reasons for these small di erences are two. First of all, in each Bloom lter we store only one feature (instead of more) because of the nature of our problem. Secondly, we keep in memory a Bloom lter object instead of a String object. But, the size that each object occupies in main memory is almost the same (Bloom lter is slightly smaller). Since the size of our input is not very big, we expect this gap to increase for larger datasets that will produce signi cantly more spaceconsuming feature vectors. Consequently, we deduce that Bloom lters can be very bene cial when dealing with large scale sentiment analysis data, that generate an exceeding amount of features during the feature vector construction step. 4.4

Running Time

In this experiment, we compare the running time for multiclass and binary classi cation. Initially, we calculate the execution time in all cases in order to detect if the Bloom lters speedup or slow down the running performance of our algorithm. The results when k = 50 are presented in Figure 2. It is worth noted that in all cases, Bloom lters slightly or greatly boost the execution time performance. Especially for the multi-class hashtags and binary emoticons cases, the level of time reduction reaches 17%. Despite needing more preprocessing time to produce the features with Bloom lters, in the end they pay o since the Spark operations work faster with Bloom lter objects. Moreover, observe that these con gurations have the biggest compaction ratio according to Table 5. According to the analysis made so far, the importance of Bloom lters in our solution is threefold. They manage to preserve a good classi cation performance, despite any errors they impose, slightly compact the storage space of the feature vectors and enhance the running performance of our algorithm. 4.5

Scalability and Speedup

In this nal experiment, we investigate the scalability and speedup of our approach. We test the scalability only for the emoticons dataset in the multi-class classi cation case, since it is the biggest dataset in MB. We create new chunks smaller in size that are a fraction F of the original dataset, where F 2 f0.2, 0.4, 0.6, 0.8g. Moreover, we set the value of k to 50. Figure 3 presents the scalability results of our approach. From the outcome, we deduce that our algorithm scales almost linearly as the data size increases in both cases.

Finally, we estimate the e ect of the number of computing nodes. We test three di erent cluster con gurations and the cluster consist of N 2 f1; 2; 3g slave nodes each time. Once again, we test the cluster con gurations against the emoticons dataset in the multi-class classi cation case when k = 50. Figure 4 presents the speedup results of our approach. We observe that total running time of our solution tends to decrease as we add more nodes to the cluster. Due to the increment of number of computing nodes, the intermediate data are decomposed to more partitions that are processed in parallel. As a result, the amount of computations that undertakes each node decreases respectively.

The last two gures prove that our solution is e cient, robust, scalable and therefore appropriate for big data sentiment analysis.

CONCLUSIONS AND FUTURE WORK

In the context of this work, we presented a novel method for sentiment learning in the Spark framework. Our algorithm exploits the hashtags and emoticons inside a tweet, as sentiment labels, and proceeds to a classi cation procedure of diverse sentiment types in a parallel and distributed manner. Also, we utilize Bloom lters to compact the storage size of intermediate data and boost the performance of our algorithm. Through an extensive experimental evaluation, we prove that our system is e cient, robust and scalable.

In the near future, we plan to extend and improve our framework by exploring more features that may be added in the feature vector and will increase the classi cation performance. Furthermore, we wish to explore more strategies for FH and FC bounds in order to achieve better separation between the HFWs and CWs. Also, we schedule to investigate the e ect of di erent Bloom lter bit vector sizes, in classi cation performance and storage space compression. Finally, we plan to compare the classi cation performance of our solution with other classi cation methods, such as Naive Bayes or Support Vector Machines. 6.

References

[1] A. Agarwal , B. Xie , I. Vovsha , O. Rambow , and R. Passonneau . Sentiment analysis of twitter data . In Proceedings of the Workshop on Languages in Social Media , pages 30 { 38 , 2011 .

[2] L. Barbosa and J. Feng . Robust sentiment detection on twitter from biased and noisy data . In Proceedings of the 23rd International Conference on Computational Linguistics: Posters , pages 36 { 44 , 2010 .

[3] B. H. Bloom . Space/time trade-o s in hash coding with allowable errors . Commun. ACM , 13 ( 7 ): 422 { 426 , 1970 .

[4] Z. Cheng , J. Caverlee, and K. Lee . You are where you tweet: A content-based approach to geo-locating twitter users . In Proceedings of the 19th ACM International Conference on Information and Knowledge Management , pages 759 { 768 , 2010 .

[5] D. Davidov and A. Rappoport . E cient unsupervised discovery of word categories using symmetric patterns and high frequency words . In Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics , pages 297 { 304 , 2006 .

[6] D. Davidov , O. Tsur , and A. Rappoport . Enhanced sentiment learning using twitter hashtags and smileys . In Proceedings of the 23rd International Conference on Computational Linguistics: Posters , pages 241 { 249 , 2010 .

[7] J. Dean and S. Ghemawat . Mapreduce: Simpli ed data processing on large clusters . In Proceedings of the 6th Symposium on Operating Systems Design and Implementation , pages 137 { 150 , 2004 .

[8] X. Ding and B. Liu. The utility of linguistic rules in opinion mining . In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval , pages 811 { 812 , 2007 .

[9] A. Go , R. Bhayani , and L. Huang . Twitter sentiment classi cation using distant supervision . Processing , pages 1 { 6 , 2009 .

[10] Hadoop . The apache software foundation: Hadoop homepage . http://hadoop.apache.org/, 2015 . [Online; accessed 20-September-2015].

[11] M. Hu and B. Liu . Mining and summarizing customer reviews . In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages 168 { 177 , 2004 .

[12] L. Jiang , M. Yu , M. Zhou , X. Liu , and T. Zhao . Target-dependent twitter sentiment classi cation . In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1 , pages 151 { 160 , 2011 .

[13] H. Karau , A. Konwinski , P. Wendell , and M. Zaharia . Learning Spark: Lightning-Fast Big Data Analysis. O'Reilly Media , 2015 .

[14] V. N. Khuc , C. Shivade , R. Ramnath , and J. Ramanathan . Towards building large-scale distributed systems for twitter sentiment analysis . In Proceedings of the 27th Annual ACM Symposium on Applied Computing , pages 459 { 464 , 2012 .

[15] C. Lin and Y. He . Joint sentiment/topic model for sentiment analysis . In Proceedings of the 18th ACM Conference on Information and Knowledge Management , pages 375 { 384 , 2009 .

[16] J. Lin and C. Dyer . Data-Intensive Text Processing with MapReduce . Morgan and Claypool Publishers, 2010 .

[17] Q. Mei , X. Ling , M. Wondra , H. Su , and C. Zhai . Topic sentiment mixture: Modeling facets and opinions in weblogs . In Proceedings of the 16th International Conference on World Wide Web , pages 171 { 180 , 2007 .

[18] T. Nasukawa and J. Yi . Sentiment analysis: Capturing favorability using natural language processing . In Proceedings of the 2Nd International Conference on Knowledge Capture , pages 70 { 77 , 2003 .

[19] N. Nodarakis , E. Pitoura , S. Sioutas , A. K. Tsakalidis , D. Tsoumakos , and G. Tzimas . kdann+: A rapid aknn classi er for big data. T. Large-Scale Data- and Knowledge-Centered Systems , 23 : 139 { 168 , 2016 .

[20] B. Pang , L. Lee , and S. Vaithyanathan . Thumbs up?: Sentiment classi cation using machine learning techniques . In Proceedings of the ACL-02 Conference on Empirical Methods in Natural Language Processing - Volume 10 , pages 79 { 86 , 2002 .

[21] Spark . The apache software foundation: Spark homepage . http://spark.apache.org/, 2015 . [Online; accessed 27-December-2015].

[22] M. van Banerveld , N. Le-Khac , and M. T. Kechadi . Performance evaluation of a natural language processing approach applied in white collar crime investigation . In Future Data and Security Engineering - First International Conference, FDSE 2014, Ho Chi Minh City , Vietnam, November 19-21 , 2014 , Proceedings, pages 29 { 43 , 2014 .

[23] X. Wang , F. Wei , X. Liu , M. Zhou , and M. Zhang. Topic sentiment analysis in twitter: A graph-based hashtag sentiment classi cation approach . In Proceedings of the 20th ACM International Conference on Information and Knowledge Management , pages 1031 { 1040 , 2011 .

[24] T. White. Hadoop: The De nitive Guide , 3rd Edition. O'Reilly Media / Yahoo Press, 2012 .

[25] T. Wilson , J. Wiebe , and P. Ho mann. Recognizing contextual polarity in phrase-level sentiment analysis . In Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing , pages 347 { 354 , 2005 .

[26] T. Wilson , J. Wiebe , and P. Ho mann. Recognizing contextual polarity: An exploration of features for phrase-level sentiment analysis . Comput. Linguist. , 35 ( 3 ): 399 { 433 , Sept . 2009 .

[27] Y. Yamamoto , T. Kumamoto , and A. Nadamoto . Role of emoticons for multidimensional sentiment analysis of twitter . In Proceedings of the 16th International Conference on Information Integration and Web-based Applications &#38; Services , pages 107 { 115 , 2014 .

[28] H. Yu and V. Hatzivassiloglou . Towards answering opinion questions: Separating facts from opinions and identifying the polarity of opinion sentences . In Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing , pages 129 { 136 , 2003 .

[29] W. Zhang , C. Yu , and W. Meng . Opinion retrieval from blogs . In Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management , pages 831 { 840 , 2007 .

[30] L. Zhuang , F. Jing , and X.-Y. Zhu . Movie review mining and summarization . In Proceedings of the 15th ACM International Conference on Information and Knowledge Management , pages 43 { 50 , 2006 .