helpfn

530 IEEE SYSTEMS JOURNAL, VOL. 14, NO. 1, MARCH 2020

New Clustering Algorithms for Twitter Sentiment Analysis

Hajar Rehioui and Abdellah Idrissi

Abstract—In this last decade, the use of social networks became ubiquitous in our daily life. Twitter, one of the famous social net- works became a rich source of discussed topics. The users in Twitter express their sentiments or points of view by tweets concerning dif- ferent topics in variety of fields, such as politics, commercial prod- ucts, etc. These important information are exploited by sentiment analysis tools. Clustering algorithms are one of the used solutions to discover the sentiment provided by users in tweets. However, knowing that the users sentiments are generally divided into three categories: positive, negative, and neutral, it was mandatory to find a strong clustering algorithm, which leads to a good clustering per- formance and produce an appropriate number of clusters in an acceptable run time. To achieve this goal, we combine in this pa- per two well-known clustering methods: K-means and DENCLUE (DENsity-based CLUstEring) with its variants. This combination allows to exploit the precise number of cluster from K-means and the clustering performance from DENCLUE and its variants. Ex- perimental results on four Twitter datasets demonstrate the com- petitiveness of the proposed algorithms against the state-of-the- art methods to provide a tradeoff between clustering performance, number of returned clusters, and runtime.

Index Terms—Clustering, DENCLUE, K-means, sentiment analysis, social network, twitter.

I. INTRODUCTION

N OWADAYS, the use of social networks became the mostpowerful tool for information exchange. A huge number of people are gradually moving toward these networks. They are used for different purposes such as video sharing, friend connec- tivity, group collaboration, advertising, and video conferences. They also allow to discuss current issues, to express opinions, complains, or sentiments for products or topics. This multivari- ate use attracts internet surfers from all the world with common interests in order to share information. This huge and dispersed quantity of data must be exploited to extract useful informa- tion. For this reason, in recent years, sentiment analysis, one of the social networks analysis tools [1], has become a research field which has received a lot of considerable attention. The social networks were considered as a rich source of sentiment and emotional signals detected in user interaction, which can be helpful in sentiment analysis. This kind of analysis is done in

Manuscript received October 25, 2018; revised February 21, 2019; accepted April 17, 2019. Date of publication May 15, 2019; date of current version March 2, 2020. (Corresponding author: Hajar Rehioui.)

The authors are with Intelligent Processing Systems Team, Computer Science Laboratory (Laboratoire de Recherche en Informatique), Computer Sci- ence Department, Faculty of Sciences, Mohammed V University, Rabat 10500, Morocco (e-mail: [email protected]; [email protected]).

Digital Object Identifier 10.1109/JSYST.2019.2912759

order to discover public opinions and to distinguish between the different polarities of views in political, marketing, and others interesting fields. The goal is to determine whether the expressed text is positive, negative, or neutral. Twitter is one of the most popular social networks allowing the communication by short text messages of 140 characters (tweets) [2] and widely used in the Sentiment analysis. In the literature, the classification mech- anism is considered as a powerful tool to define the polarity of expressed sentiments in Twitter. The classification, one of data mining tools, are divided into supervised classification and un- supervised classification, also called clustering. Each of these type has its own characteristics. The use of supervised classi- fication needs more runtime especially in the learning process [3]. This paper is based on the unsupervised classification also called clustering. The strength of this type lies on its ability to discover clusters without predefined knowledge. Different meth- ods have been proposed for the tweet sentiment analysis using the clustering methods. A fuzzy clustering method for Twitter sentiment analysis had been proposed in [4]. This method is based on the dispersion of each object over various clusters and the quantification of the degree of belonging an object to unlike clusters by means measurement called membership coefficients. In [5], the authors propose to combine a fuzzy logic approach with a hierarchical method. The goal of this combination is to deal with uncertainty in the tweet information gathered for sen- timent analysis. Pandey et al. [2] used a hybrid method based on K-means and the cuckoo search algorithm. Riaz et al. [6] per- formed a novel sentiment analysis method in order to find out customer preference. Then, they applied K-means, as clustering algorithm, for placing the words in various clusters based on their intensity. Despite that the k-means is the most used clus- tering algorithm, it suffers from the low clustering performance. That is why, we decide to investigate the density-based family of methods.

In this paper, we use different density-based clustering meth- ods which are based on DENsity-based CLUstEring (DEN- CLUE) [7]. This method has proven its performance on dif- ferent data mining applications [7]–[10]. However, this family of methods suffers from the large number of generated clusters, especially when we know that the expressed sentiments are basi- cally divided into three clusters: positive, negative, and neutral. To overcome this limit, inspired by the K-means algorithm, we integrate on the exploited clustering methods the information of the number of clusters.

This paper is organized as follows. We describe in Section II DENCLUE algorithm and its variants. In Section III, we present

1937-9234 © 2019 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 04:03:10 UTC from IEEE Xplore. Restrictions apply.

REHIOUI AND IDRISSI: NEW CLUSTERING ALGORITHMS FOR TWITTER SENTIMENT ANALYSIS 531

our proposed approaches, then we prove their effectiveness based on the experimental results presented in Section IV. Finally, we conclude our work and discuss some perspectives in Section V.

II. DENSITY-BASED CLUSTERING ALGORITHMS

The clustering process is divided generally into five families [9], [11]: partitioning, hierarchical, density-based, grid-based, and model-based clustering algorithms. The density-based one, is characterized by the ability to discover clusters of arbitrary shapes and omit noisy objects. The noise which is ubiquitous in the tweets, must be filtered by a strong clustering algorithm in an acceptable run time. In this context, we focus on DENCLUE algorithm and its variants in order to classify the tweets and consequently analyze the sentiments of Twitter users.

A. DENCLUE

DENCLUE [7] is an algorithm based on connectivity and density functions. An obtained cluster is considered as connected dense components, it can grow in any direction that density leads. DENCLUE algorithm uses a cluster model defined by a local maximum of the estimated density function. It is characterized by its efficiency to cluster large datasets containing an amounts of noise. It is also much faster than the existing density-based algorithms such as DBSCAN [7], [9]. In order to find the clusters, DENCLUE has to reach a set of points called density attractors. An attractor is deemed to be a local maximum of the density function. The attracted points are the points forming a path with the density attractors. A hill climbing algorithm is used to find this maximum. DENCLUE algorithm was developed to classify large multimedia databases [7], because this type of databases contains large amounts of noise, and requires clustering high- dimensional feature vectors.

DENCLUE is based on the calculation of the influence of points between them, which characterize the influence of a data point in each other point in its neighborhood. There exist many influence functions based on the distance between two points x and y such as the Gaussian function derived from [7] and presented as follows:

fGauss(x, y) = exp − (

dist(x,y)2

2σ2

) (1)

where dist(x, y) is the Euclidean distance between x and y. Moreover, σ stands for the radius of the neighborhood contain- ing x. The total sum of these influence functions defines the density function presented in (2) and extracted from [7]

fD(x) =

N∑

i=1

fGauss(x, xi) (2)

where D corresponds to the set of points on the database, and N is its cardinal.

In DENCLUE, the data are presented by a structure of a hyper- rectangle. This structure is composed by many hyper-cubes, each one represented by a key and the dimension of the feature vector. DENCLUE manipulates the data by considering only populated cubes.

B. DENCLUE 2.0

A second version of the algorithm DENCLUE called DEN- CLUE 2.0 was introduced by Hinneburg and Gabriel [12]. In this version, a new hill climbing method for Gaussian Kernels was developed. This version is efficient because it automatically adjusts step size at no extra costs. Moreover, it is effective be- cause it converges to local maximum. The amelioration of the hill climbing converges exactly to a local maximum by reduc- ing it to a particular case of the expectation maximization (EM) algorithm. In DENCLUE 2.0, the modification is applied on the gradient ascent approach used by the classical hill climb- ing method. The modified formula is shown in the following equation extracted from [12]

x = ∑N

i=1 Ker ( x−xi σ

) xi

∑N i=1 Ker

( x−xi σ

) x(l+1) = ∑N

i=1 Ker ( x(l)−xi

σ

) xi

∑N i=1 Ker

( x(l)−xi

σ

) (3)

with Ker is the Gaussian Kernel presented as follows:

Ker(x) = (2π)(− d 2 ) exp

[ −x

2

2

] (4)

where d is the data dimension. The formula in (3) is reduced in the two EM steps as shown in the two formulas (5) and (6) extracted from [12]. Step E

θi = 1/N.Ker

(x(l) − xi σ

)

fD(x(l)) . (5)

Step M

x(l+1) =

∑N i=1 θixi∑N i=1 θi

. (6)

C. DENCLUE-SA and DENCLUE-GA

DENCLUE-SA [13] is amelioration of DENCLUE algorithm. This version has shown the capacity to reduce the execution time of DENCLUE in huge data. Its major goal is to adjust the sim- ulated annealing algorithm which is a metaheuristic algorithm used for the optimum search, and put it instead of the hill climb- ing algorithm in order to improve the local maximum search. Following the same philosophy, the DENCLUE-GA [13] algo- rithm replace the hill climbing by the genetic algorithm (GA) one.

D. DENCLUE-IM

Seeking density attractors becomes more difficult on large data, that is why Rehioui and Idrissi [14] have developed DENCLUE-IM. The algorithm brought modifications on the step of computing density attractors that are found by the hill climbing algorithm. This step is based on gradient calculations which are done for every point to find its density attractor. This is not obvious to obtain results in a reasonable time when it comes to work on large data. For that reason, DENCLUE-IM consid- ers a representative of all the points contained in a hyper-cube rather than the calculations made for each point in the dataset. The representative of the hyper-cube, denoted by the authors

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 04:03:10 UTC from IEEE Xplore. Restrictions apply.

532 IEEE SYSTEMS JOURNAL, VOL. 14, NO. 1, MARCH 2020

Fig. 1. Reduction of feature dimension based on the sum fusion rule.

xHcube, was considered as the point having the highest density in its hyper-cube as shown in (7). Consequently each hyper-cube represented by its xHcube is considered as an initial cluster. These clusters will be unified on the condition that there exist a path between their representatives

∀x ∈ Cp fD(x) ≤ fD(xHcube) (7) where Cp denotes a given populated hyper-cube in the con- structed hyper-rectangle.

III. PROPOSED APPROACHES

We recall that our aim was to integrate the number of clusters “K” on the different version of DENCLUE algorithm described in Section II. To do this, we apply the proposed methods on the tweets in order to identify the clusters of the expressed opinions. Before that, some steps are applied to the input data. The first one, preprocessing, consists to eliminate the noisy data, while the second step extracts feature vectors that will be considered as an input of the clustering methods. These steps are described in the following sections.

A. Preprocessing

The tweets are allowed to use 140 characters [2], hence, this limits increases the use of abbreviations (acronyms), irregular expressions, and infrequent words. This issue increments the level of noisy data, affecting the sentiment recognition per- formance on Twitter. To deal with this issue, different pre- processing methods are widely used before extracting the fea- tures. The challenge of this step is to eliminate the noise while conserving the right meaning of the tweets. This phase is pro- cessed as follows.

1) In order to omit the noise, the URLs and the punctua- tions including the “@” from the users name and the “#” from the hash-tags are removed as expressed in [2]. The sequence of spaces are also eliminated and replaced by a single space. Concerning the punctuations removal, we must note that the signals expressing emoticons are con- served.

2) To give the tweet more clarity before being processed, all the words are converted to lower case, then compared to the stop words dictionary [15] in the aim to remove the stop words as “a, the, of, and, etc.”, and also compared to the acronyms dictionary [16]. This last comparison allows

to replace the acronyms by its real meaning, e.g., (2nite → tonight).

B. Feature Vectors Extraction

We adopt in our work the feature extraction method proposed in [2], which produce a feature vector of 11 values. The 11 features consist of the following:

1) the count of total words in a tweet; 2) the count of positive emoticons; 3) the count of negative emoticons; 4) the count of neutral emoticons; 5) the count of positive exclamations; 6) the count of negative exclamations; 7) the count of negation words; 8) the count of positive words; 9) the count of negative words;

10) the count of neutral words; 11) the count of intense words. However, this feature contains some redundancy, which in-

creases its size without increasing its significance. That is why in this paper, we bring together the information that refer to the same thing by using the sum fusion rule [17]. In this way, the dimension of the feature vector is significantly reduced. Addi- tionally, we remove the number of intensive words information used for the sarcasm in tweets which is not the research field studied in our paper. This removed information is replaced by a crucial one, which is the topic value that helps to analyze the user’s sentiments. Finally, as illustrated in Fig. 1, the reduced feature vector is composed by the following.

1) The total number of words in the tweet after being pre- processed (e.g., if we have “love twitter ;)” as a tweet, the number “2” will represent the first value of the feature).

2) The total number of all positive expressions, i.e., the pos- itive emoticons [18] like “:)” and “:D”, the positive excla- mations [19], and the positive words [20] (e.g., if we have “love twitter ;)” as a tweet, its second feature value will be 2, because we have two positive expressions “love” and the emoticon “;)”).

3) The total number of all negative expressions: the negative emoticons [18], the negative exclamations [19], and the negative words [20] (e.g., if we have “love twitter ;)” as a tweet, its third feature value will be 0, because no negative opinion has been expressed).

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 04:03:10 UTC from IEEE Xplore. Restrictions apply.

REHIOUI AND IDRISSI: NEW CLUSTERING ALGORITHMS FOR TWITTER SENTIMENT ANALYSIS 533

4) The total number of all neutral expressions. It is about the sum number of the neutral emoticons [18], the neutral exclamations [19], and the neutral words [21] (e.g., if we have “twitter :-o” as a tweet, its fourth feature value will be 1, because the expressed emoticon “:-o” will be considered as neutral. In fact, we cannot determine if the expressed emoticon is a positive or negative).

5) The topics discussed in a given dataset. For example a dataset concerning opinions of competing products, ser- vices, celebrities, etc. Each product or service is con- sidered as a topic. A number is then attributed to each topic (e.g., the four discussed topics in Twitter-Sentiment- Corpus [22], each topic will be numbered as 1, 2, 3, and 4). Otherwise if we have dataset concerning multivariate and non competing products or a dataset concerning just opin- ions of one topic, we maintain just the first four features. We can say that this fifth feature is optional according to the processed dataset.

After this level of process the features are normalized in or- der to improve the accuracy and efficiency of the applied al- gorithms. This process is particularly useful for distance-based methods, such as clustering methods. It helps prevent attributes with initially large ranges by scaling their values in order to be all standardized and fall within a small-specified range, such as 0.0 to 1.0 [23]. In this paper, we use the z-score method [23]. This normalization is useful when the minimum and maximum of a given attribute are unknown. In z-score, the attributes of a given feature x are normalized based on the mean and standard deviation of x. An attribute a of x is normalized to a′ as shown in the following:

a′ = a − μx σx

(8)

where μx is the mean of x and σx represents the standard devi- ation of x. The extracted feature vector for each tweet will be used as input of the clustering methods.

C. Proposed Clustering Algorithms

In the sentiment analysis field, the expressed points of view are generally divided into three clusters: positive, negative, and neutral. The application of the clustering algorithms could not often give us the exact number of returned clusters helping in the sentiment analysis of a given service or product. That is why we integrate the number of clusters in the DENCLUE and its vari- ants based on the principle of the k-means algorithm. The goal of this process is to find a tradeoff between a fixed clusters number, a good quality of clusters and a reasonable response time. We call the proposed algorithms: K-DENCLUE, K-DENCLUE 2.0, K-DENCLUE-SA, K-DENCLUE-GA, and K-DENCLUE-IM. The general process of our proposed algorithms is illustrated in Fig. 2.As shown in this figure, a hyper-rectangle is constructed based on the normalized extracted features. The hyper-rectangle is constituted by hyper-cubes. Each one is represented by the di- mension of the feature vector points (i.e., the number of criteria) and by a key. This structure allows DENCLUE and its vari- ants to easy manipulate the data, by using the cubes keys, and

Fig. 2. Generalized flowchart of K-DENCLUE and its variants.

considering only populated cubes. The process of the hyper- rectangle is as follows. Step 1: Spread the input into a map whose each side is of 2σ,

consider only populated cubes. Step 2: Calculate the mean of each populated cubes. Step 3: Find highly populated cubes where the number of

points exceeds a threshold ξ. Step 4: Determine the connection between each highly pop-

ulated cube, and other cubes (highly or just popu- lated cubes) by the distance between their means. If d(mean(c1), mean(c2)) < 4σ, then the two cubes are connected.

Step 5: Only the highly populated cubes and cubes which are connected to a highly populated cube are considered in determining clusters.

After the construction of the hyper-rectangle, the den- sity attractor points in K-DENCLUE, K-DENCLUE 2.0, K- DENCLUE-SA, and K-DENCLUE-GA, or the representatives of the hyper-cubes in K-DENCLUE-IM are extracted and merged. Afterwards, the resulted density attractors or the re- sulted representatives of the cubes are considered as input in the K-means algorithm. Finally, when the clustered density at- tractors (or representatives of the hyper-cubes in the case of K-DENCLUE-IM) are obtained, we fill to each cluster by the appropriate attracted (or represented) points, then return the K-clusters.

We present in the Algorithm 1 the principle of the K- DENCLUE. We note that the other variants are relatively close to this principle and our approach is introduced into the DEN- CLUE’s variants in the same way it is introduced in DENCLUE.

The notation used in our algorithm are defined hereafter: Hr: the constructed hyper-rectangle; cube: the populated hyper-cube; x: a point belonging to a given cube; A: the set of density attractors; Aed(xHcube): the set of points attracted by a given density

attractors x∗; Cluster: a constructed cluster; Clusters: the final set of returned clusters;

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 04:03:10 UTC from IEEE Xplore. Restrictions apply.

534 IEEE SYSTEMS JOURNAL, VOL. 14, NO. 1, MARCH 2020

Algorithm 1: K-DENCLUE Algorithm.

1: procedure GETCLUSTERS (k, Hr, σ, ξ) 2: A = ∅ 3: Aed(null) = ∅ 4: Cluster = ∅ 5: Clusters = ∅ 6: for each cube ∈ Hr do 7: for each x ∈ cube do 8: x∗ = GETDENSITY ATTRACTOR(x) 9: if (fD(x∗) � ξ)

10: { 11: A = A ∪ {x∗} 12: Aed(x∗) = Aed(x∗) ∪ {x} 13: } 14: end for 15: end for 16: for each x∗i ∈ A do 17: for each x∗j ∈ A, i = j do 18: if (dist(x∗i, x

∗ j) � σ)

19: { 20: Aed(x∗i) = Aed(x

∗ i) ∪ Aed(x∗j)

21: remove x∗j from A 22: } 23: else{ 24: for each xl ∈ Aed(x∗i) do 25: for each xm ∈ Aed(x∗j) do 26: if ((dist(xl, xm) � σ) 27: and (fD(xl) � ξ) 28: and (fD(xm) � ξ)) 29: { 30: Aed(x∗i) = Aed(x

∗ i) ∪ Aed(x∗j)

31: remove x∗j from A 32: } 33: end for 34: end for 35: } 36: end for 37: end for 38: kClusters = kMeans(k, A) 39: for each kCluster ∈ kClusters do 40: for each x∗ ∈ A do 41: Cluster = Cluster ∪ Aed(x∗) 42: end for 43: add Cluster to Clusters 44: end for 45: Return Clusters 46: end procedure 47: 48: procedure GETDENSITYATTRACTOR (x) 49: t = 0 50: x0 = x 51: repeat

52: xt+1 = xt + δ ∇fDGauss(xt)

‖∇fDGauss(xt)‖ 53: t = t + 1 54: until fD(xt−1) > fD(xt) 55: Return xt−1

56: end procedure

TABLE I DESCRIPTION OF THE USED DATASETS

TABLE II DESCRIPTION OF THE USED VALIDITY METRICS

IV. EXPERIMENTAL RESULTS

To underline the impact of our proposed clustering algorithms to distinguish between the different feelings of Twitter’s users, we tested them on four Twitter datasets described briefly in Ta- ble I. To make a fair comparison, we compare the proposed clustering algorithms which are already exploited in the Twitter sentiment analysis context such as EM [4], [30], K-means [2], [6], [31], and DBSCAN [31]–[33]. In addition, we add a compar- ison with the DENCLUE algorithm which represents the base- line of all the proposed approaches. The comparison between the different methods are done by using several external and in- ternal metrics described in Table II. We note that each method has been executed ten times and the mean of each metric has been presented in the experimental results.

The clustering quality and the returned clusters number have been presented in Tables III and IV. The best values are made in bold. It can be observed based on the internal metrics, pre- sented in Table III and the mean returned values of the four dataset depicted in the last column, that DBSCAN obtained the best DI, DBI, and CP in two datasets, followed by DENCLUE (the best DI and CP in one dataset), then K-DENCLUE-SA (the best DI in one dataset), K-means (the best DBI in one dataset), K-DENCLUE (the best DBI in one dataset) and K-DENCLUE 2.0 (the best CP in one dataset). While in the mean values of all datasets, DBSCAN obtained the best DI value, K-DENCLUE- SA obtained the best DBI, and DENCLUE obtained the best CP.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 04:03:10 UTC from IEEE Xplore. Restrictions apply.

REHIOUI AND IDRISSI: NEW CLUSTERING ALGORITHMS FOR TWITTER SENTIMENT ANALYSIS 535

TABLE III TWEETS CLUSTERING RESULTS ACCORDING TO THE INTERNAL AND EXTERNAL VALIDITY METRICS

In terms of external metrics, DBSCAN and DENCLUE obtained each one the best CA values in three datasets. Based on the en- tropy, DBSCAN and K-DENCLUE 2.0 outperformed each one in two datasets. Concerning the NMI metric, K-DENCLUE-IM obtained the best values in two datasets, followed by DBSCAN and DENCLUE (one dataset for each algorithm). While in the mean values of all datasets, DENCLUE obtained the best CA and NMI values and K-DENCLUE 2.0 obtained the best Entropy.

Generally, DBSCAN and DENCLUE obtain the best values in the internal and external metrics, especially in terms of accuracy (CA) rather than EM and K-means, but still return a large number of clusters. Concerning the proposed algorithms, K-DENCLUE,

K-DENCLUE 2.0, K-DENCLUE-SA, K-DENCLUE-GA, and K-DENCLUE-IM, they obtain a balanced quality results be- tween the clustering performance and the number of returned clusters Based on Fig. 3, it is clearly observed that the difference between the CA values obtained by our approaches compared to the best obtained values is small. In terms of the mean value of CA measure, DENCLUE obtained the best value (65.1%), followed by DBSCAN (65%) and K-DENCLUE (62.9%), then K-DENCLUE-IM(62.7%), K-DENCLUE-SA (61%), K- DENCLUE-GA (60.8%), and K-DENCLUE 2.0 (59.4%). While EM and K-means obtained respectively 58,3% and 56,6%, more than 8% smaller than the best value.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 04:03:10 UTC from IEEE Xplore. Restrictions apply.

536 IEEE SYSTEMS JOURNAL, VOL. 14, NO. 1, MARCH 2020

Fig. 3. Computational comparison based on the means of CA, run time, and number of returned clusters.

TABLE IV COMPARISON BETWEEN THE ALGORITHMS ACCORDING TO THEIR

RETURNED NUMBER OF CLUSTERS

TABLE V COMPARISON BETWEEN THE ALGORITHMS ACCORDING TO

THEIR EXECUTION TIME (S)

In terms of run time measurement depicted in Table V and the mean value of the four datasets illustrated in Fig. 3, the EM algorithm obtained the highest execution time, fol- lowed by K-means, DBSCAN, DENCLUE, K-DENCLUE-GA, K-DENCLUE, K-DENCLUE-SA, K-DENCLUE 2.0, and fi- nally K-DENCLUE-IM. This growth of time is especially af- fected by the size growth of experimental Twitter datasets as analyzed in Table V. These experimental analysis let us fig- ure out that our proposed clustering algorithms found a trade- off between the quality, the run time, and the number of re- turned clusters. Precisely, the K-DENCLUE-IM remains a good choice to classify the large datasets. We must notice that for the

computational comparison, all algorithms were implemented in JAVA environment, on a Core i5 (2.70 GHz) PC with 8 GB of memory.

V. CONCLUSION

In this paper, new clustering algorithms have been introduced in order to analyze the sentiments of tweets based on K-means and DENCLUE. The proposed methods was conceived to con- serve an acceptable clustering quality and to decrease the large returned number of clusters, knowing that the sentiment ex- pressed by Twitter users are generally, divided into three clus- ters, positive, negative, and neutral. The new methods have been tested on four Twitter datasets and compared with four of state- of-the-art algorithms. The comparisons were done based on dif- ferent clustering performance criteria, the number of returned clusters as well as the runtime. Based on the experimental re- sults, the efficiency of the proposed methods has been observed in terms of quality and number of returned clusters in reasonable run time, especially in the case of K-DENCLUE-IM algorithm. In our future works, we will be interested in the study of sarcasm and irony of the tweets in the aim to deal with it, and conduct a detailed comparative study showing the impact of different fea- ture extraction methods on the clustering results. It will be also interesting to cluster the tweets sentiments based on emoticons and to apply our approaches in other research fields.

REFERENCES

[1] N. Ghali, M. Panda, A. E. Hassanien, A. Abraham, and V. Snasel, “Social networks analysis: Tools, measures, and visualization,” in Computational Social Networks. Berlin, Germany: Springer, 2012, pp. 3–23.

[2] A. C. Pandey, D. S. Rajpoot, and M. Saraswat, “Twitter sentiment analysis using hybrid cuckoo search method,” Inf. Process. Manage., vol. 53, no. 4, pp. 764–779, 2017.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 04:03:10 UTC from IEEE Xplore. Restrictions apply.

REHIOUI AND IDRISSI: NEW CLUSTERING ALGORITHMS FOR TWITTER SENTIMENT ANALYSIS 537

[3] A. Go, R. Bhayani, and L. Huang, “Twitter sentiment classification using distant supervision,” Stanford Univ., Stanford, CA, USA, Project Rep. CS224N, 2009, vol. 1, no. 12.

[4] H. Suresh et al., “An unsupervised fuzzy clustering method for twitter sentiment analysis,” in Proc. Int. Conf. Comput. Syst. Int. Technol. Sustain. Solutions, 2016, pp. 80–85.

[5] H. Suresh and S. G. Raj, “A fuzzy based hybrid hierarchical clustering model for twitter sentiment analysis,” in Proc. Int. Conf. Comput. Intell., Commun., Bus. Anal., 2017, pp. 384–397.

[6] S. Riaz, M. Fatima, M. Kamran, and M. W. Nisar, “Opinion mining on large scale data using sentiment analysis and k-means clustering,” Cluster Comput., pp. 1–16, 2017. [Online]. Available: https://link.springer.com/journal/10586/onlineFirst/page/75

[7] A. Hinneburg and D. A. Keim, “An efficient approach to clustering in large multimedia databases with noise,” Knowl. Discovery Data Mining, vol. 98, pp. 58–65, 1998.

[8] P. Berkhin, “A survey of clustering data mining techniques,” in Grouping Multidimensional Data. Berlin, Germany: Springer, 2006, pp. 25–71.

[9] A. Fahad et al., “A survey of clustering algorithms for big data: Taxonomy and empirical analysis,” IEEE Trans. Emerg. Topics Comput., vol. 2, no. 3, pp. 267–279, Sep. 2014.

[10] H. Rehioui, A. Idrissi, M. Abourezq, and F. Zegrari, “DENCLUE-IM: A new approach for big data clustering,” Procedia Comput. Sci., vol. 83, pp. 560–567, 2016.

[11] G. H. Shah, C. Bhensdadia, and A. P. Ganatra, “An empirical evaluation of density-based clustering techniques,” Int. J. Soft Comput. Eng., vol. 2, pp. 2231–2307, 2012.

[12] A. Hinneburg and H. H. Gabriel, “Denclue 2.0: Fast clustering based on kernel density estimation,” in Advances in Intelligent Data Analysis VII. Berlin, Germany: Springer, 2007, pp. 70–80.

[13] A. Idrissi, H. Rehioui, A. Laghrissi, and S. Retal, “An improved DEN- CLUE algorithm for data clustering,” in Proc. 5th Int. Conf. Inform. Com- mun. Technol. Accessibility, 2015, pp. 1–6.

[14] H. Rehioui and A. Idrissi, “A fast clustering approach for large multidi- mensional data,” Int. J. Bus. Intell. Data Mining, vol. 15, no. 3, 2019.

[15] “Stopwords dictionary,” 2014. [Online]. Available: https://github.com/ igorbrigadir/stopwords/blob/master/en/t101_minimal.txt. Accessed on: Oct. 24, 2018.

[16] “Acronyms dictionary,” 2015. [Online]. Available: http://www.netlingo. com/acronyms.php, Accessed on: Oct. 24, 2018.

[17] M. He et al., “Performance evaluation of score level fusion in multimodal biometric systems,” Pattern Recognit., vol. 43, no. 5, pp. 1789–1800, 2010.

[18] A. Hogenboom, D. Bal, F. Frasincar, M. Bal, F. De Jong, and U. Kaymak, “Exploiting emoticons in polarity classification of text.” J. Web Eng., vol. 14, no. 1/2, pp. 22–40, 2015. [Online]. Available: https:// people.few.eur.nl/hogenboom /files/EmoticonSentimentLexicon.zip

[19] “Exclamation dictionary,” 2015. [Online]. Available: http://www. vidarholen.net/contents/interjections/. Accessed on: Oct. 24, 2018.

[20] B. Liu, M. Hu, and J. Cheng, “Opinion observer: Analyzing and comparing opinions on the web,” in Proc. 14th Int. Conf. World Wide Web, 2005, pp. 342–351. [Online]. Available: https://github.com/ jeffreybreen/twitter-sentiment-analysis-tutorial-201107/tree/master/data/ opinion-lexicon-English

[21] “Neutral dictionary,” 2015. [Online]. Available: https://quizlet.com/ 25024874/ap-literature-neutral-tone-attitude-words-flash-cards/. Access- ed on: Oct. 24, 2018.

[22] “Sanders dataset,” 2011. [Online]. Available: http://www.sananalytics. com/lab/twitter-sentiment/. Accessed on: Oct. 23, 2017.

[23] L. Al Shalabi, Z. Shaaban, and B. Kasasbeh, “Data mining: A preprocess- ing engine,” J. Comput. Sci., vol. 2, no. 9, pp. 735–739, 2006.

[24] “Twitter dataset,” 2014. [Online]. Available: https://drive.google.com/ file/d/0BwPSGZHAP_yoN2pZcVl1Qmp1OEU/view. Accessed on: Oct. 24, 2018.

[25] “Testdata-manual-2009.06.14,” 2009. [Online]. Available: http://help. sentiment140.com/for-students/. Accessed on: Oct. 24, 2018.

[26] “Airline-twitter-sentiment,” 2015. [Online]. Available: https://www. crowdflower.com/data/airline-twitter-sentiment/. Accessed on: Mar. 29, 2018.

[27] J. C. Dunn, “Well-separated clusters and optimal fuzzy partitions,” J. Cy- bern., vol. 4, no. 1, pp. 95–104, 1974.

[28] D. L. Davies and D. W. Bouldin, “A cluster separation measure,” IEEE Trans. Pattern Anal. Mach. Intell., vol. PAMI-1, no. 2, pp. 224–227, Apr. 1979.

[29] E. Rendón, I. Abundez, A. Arizmendi, and E. Quiroz, “Internal versus external cluster validation indexes,” Int. J. Comput. Commun., vol. 5, no. 1, pp. 27–34, 2011.

[30] N. M. Shelke, S. Deshpande, and V. Thakre, “Exploiting expectation max- imization algorithm for sentiment analysis of product reviews,” in Proc. Int. Conf. Inventive Commun. Comput. Technol., 2017, pp. 390–396.

[31] S. S. Kumari and G. A. Babu, “Sentiment on social interactions using linear and non-linear clustering,” in Proc. 2nd Int. Conf. Adv. Elect., Electron., Inform., Commun. Bio-Inform., 2016, pp. 177–181.

[32] D. Stojanovski, I. Chorbev, I. Dimitrovski, and G. Madjarov, “Social networks VGI: Twitter sentiment analysis of social hotspots,” in Euro- pean Handbook of Crowdsourced Geographic Information. London, U.K.: Ubiquity Press, 2016, pp. 223–235.

[33] A. Babu and R. V. Pattani, “Efficient density based clustering of tweets and sentimental analysis based on segmentation,” Int. J. Comput. Techn., vol. 3, no. 3, pp. 53–57, 2016.

Hajar Rehioui is currently working toward the Ph.D. degree in computer science, speciality data science.

She is a member of Intelligent Processing Sys- tems Team with the Computer Science Laboratory (Laboratoire de Recherche en Informatique) of Com- puter Science Department, Faculty of Sciences, Mo- hammed V University, Rabat, Morocco.

Abdellah Idrissi received his Ph.D degree from the University of Picardie Jules Verne in Amiens, France.

He is currently a member of Computer Science Laboratory (Laboratoire de Recherche en Informa- tique) where he leads a research group named Intelli- gent Processing Systems Team. He has authored three books and authored and coauthored several publica- tions in international journals and conferences. His research domains include modeling, resolution and optimization of intelligent, and complex systems. His applications cover constraint programming, multia-

gent systems, intelligent transport systems, cloud computing, text, data, and web mining, big data, data warehouse, business intelligence, game theory, mo- bile ad-hoc networks, cognitive radio networks, etc.

Dr. Idrissi is a member of the editorial board of several international jour- nals and is also a member of the Technical Program Committee of several in- ternational conferences. He is a Leader of MOSAIC MAGHREB Technology Platform.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 04:03:10 UTC from IEEE Xplore. Restrictions apply.