A spatial,temporal and sentiment based framework for indexing and clustering in twitter blogosphere

Abstract

As the number of social networks users has increased day by day so has the user’s dependency for communication on the social networks. Social networks enable people to connect with one another in many different ways. Many social networks such as Twitter provide their users the functionality to tag the user’s current location to the post. This geographical information can be used in various information retrieval processes. Currently many methods are present which cluster the tweets using traditional K-means algorithm in which user has to specify the number of clusters to be formed, and if the tweets do not lie within those clusters they are then treated as outliers and discarded. This paper presents a framework which focuses on clustering and indexing of tweets on the basis of its geographical and temporal features. The X-means clustering has been used which does not require the cluster number input from the user but rather it takes input from the index of the specified characteristics created from tweets. The indexing mechanism will not only help in ease of searching but will also aid in many retrieval tasks. The experimental analysis shows that the proposed framework generates improved results over traditional tweet clustering methods.

Keywords

Tweet indexing tweet clustering microblog information retrieval

1 Introduction

Last few years have seen an exponential growth towards the power of publication of the online media. More and more publications, are shifting their focus from the print media to the online media. And the peer to peer sharing/broadcast of this online media is done through the social networking platforms. These social networking sites provides users ways to share the information among the group of people they know. In addition these Social Networking Sites not only allow the users to share news and other information but are also used to share the content that is generated by the user i.e. user-generated content. In blogs and microblogs the users can share the information with a specific group of people or broadcast it to all of the users, it may be a personal information related to an individual or some information related to the current happenings around the world. A tweet is similar to a microblog post. It also contains vast amount of information either in its body or in its meta-data. Figure 1 represents the characteristics of the tweet which are related to the proposed work.

Fig.1

Parts of a tweet.

A microblog is a platform where clients post short messages to convey their opinions or feelings on some particular topic. In microblogs the users usually express thoughts on a topic or examine current social issues and share it with each other instantly due to which large amount of information is present in microblogs. Important and trending issues are extracted from the microblog based on the time of the tweet. Besides time being an important factor the geo-location or spatial features of the post are also important as described by X. Li et al. [1]. Microblogs are like online journals, but there is also a limit on how much a user can share in a single microblog post (e.g. 140-character point of confinement of a tweet in Twitter). Since the launch of Twitter there has been an exponential increase in the number of users of microblogs. Most of the microblog posts that are related to a topic are considered to be relevant if they are within some time scope after which they are considered as irrelevant. Currently time is considered as an important feature in different fields of infromation retrieval. Most common algorithm used for cluster creation is K-means, after which the features can be extracted. T. Mansouri et al. demonstrate a variation of K-means algorithm to show that it can support real time streams for clustering, which is very helpful as it will accommodate all the new posts that arrive in real-time [2].

There are several methods present that cluster the tweets in different ways but they have several drawbacks. Some methods use only time for the clustering process, some methods consider only geo-coordinate for the clustering process, while others use variations of these features. For example, A. Samuel et al. proposed a variation of Lex-Rank algorithm to extract different types of temporal information present in the tweet for summary creation [3]. If more features are included in the clustering process then this will not only improve the results but will also provide results on the basis of multiple features. The motivation of this paper is to develop a framework that includes the temporal features, geo-coordinates and the sentiments of the tweet which will use them to create the clusters from which the index will be created for the event summarization process. Let us assume the clusters based on time and location are created using the traditional clustering algorithm such as K-means. For the clustering process one had to run the clustering algorithm multiple times to obtain the best results as the optimal number of clusters are not known initially and multiple runs of the algorithm are necessary. The proposed framework uses X-means algorithm which itself finds out the optimal value of clusters for the best results. Previous works have provided methods in which the number of clusters to be formed have to be given by the user for cluster formation.

2 Related works

X. Li et al. characterized two types of time-based questions in TREC accumulations that contain news chronicles: one dependably supports the latest archives and the other has pertinent records inside of a particular historical period [1]. To join time data into recovery models, they proposed a period based dialect model utilizing the previous model in light of an exponential or a typical appropriation relying upon the sorts of recency questions. Efron et al. proposed an estimator for the rate parameter of an exponential dispersion that joins the data related to the query [4]. They likewise recommended a period smoothing dialect which uses a period element to appraise the blending parameter for dialect model smoothing. Diaz et al. proposed a worldly question model, indicated P(t|Q), which was characterized as the standardized total of the significant scores of recovered records that are distributed at time t for inquiry Q [5]. They utilized fleeting components for question execution forecast [6] and worldly inquiry order [5] undertakings.

Keikha et al. proposed a period based pertinence model for online journal food recovery, which utilizes the P(t|Q) presented by Diaz et al. [6] as a weight of the terms in the pseudo-significance input setting [7]. Dakka et al. proposed a general system to assess P(t|Q). They organized the top recovered reports into containers and appointed evaluated significance worth to these canisters [8].

Peetz et al. displayed a versatile transient question demonstrating for web journal food recovery, in that they broke down the top recovered reports as far as fleeting histogram to discover the blasts [9]. They utilized reports with the most elevated scores from the blasts for inquiry extension and weighted every input record with the separation from the top that contains most archives.

Massoudi et al. gave an inquiry extension model for microblogs, which chooses terms transiently closer to the question accommodation time [10]. Their model functioned admirably for discovering archives identified with occasions as of now incident in any case, not also for past occasions. Metzler et al. proposed a fleeting inquiry development strategy for microblogs in view of the worldly co-event of terms in a timespan [11]. They initially performed pseudo-important timespan recovery for an occasion inquiry (e.g., tremor) and utilized those timespan for question extension. The transient inquiry development strategy demonstrated that selecting significant timespan is urgent for question extension for microblog archives. In the event that the fleeting question development lives up to expectations for an occasion inquiry, it may be valuable for specially appointed hunt inquiries.

Jones et al. and Kwak et al. attempted to recover applicable as well as crisp reports [5, 12]. Lavernko et al. and Jones et al. considered the other vital transient presumption, i.e., the occasion’s top time point [5, 13]. Jones et al. proposed a strategy to give more weight to these reports around top focuses [5]. Lavernko et al. attempted to consolidate question development on transient variety with recency keeping in mind the end goal to enhance the recovery execution [13].

X. Li et al. proposed a method to figure out how to rank for time-sensitive web look, in any case, there is distinctive strengths in microblog pursuit, and the greater part of their components are not pertinent in the microblog seek any more [1]. The issue of the substantial contrasts among distinctive questions can be tended to by inquiry ward positioning methodologies. There’re distinctive misfortune capacities to utilize the inquiry contrast to enhance the recovery viability, for example, question characterization based methodology [10], question bunching based methodology [11] and closest neighbor-based methodology [14]. With respect to web look, inquiries can be navigational, educational or value-based as described by Peetz et al. in [9]. Then again, the questions in time touchy microblog pursuit may have distinctive examples.

P. Su et al. proposed a method to cluster the data on the hierarchical basis while using different parameters. It provided improved results over existing methods [15]. Demiriz et al. proposed a method to analyse the data on the basis of their spatial and temporal features and used it in the domain of fraud detection using fuzzy rules that provided improved results [16].

Hawking et al. explained a way to reorder the index to the desired state according to certain characteristics such that the index does not lose it’s effectiveness [17]. Huston et al. presented a method for indexing the repeated n-grams in documents which is trivial for infromation retrieval [18]. De Vries et al. demonstrates the technique that is used for the cluster evaluation, and identifies the ineffective clusters formed as they have a high score but they do not have any value as they do not provide any clustering solution [19]. O’Hare et al. presented a method to extract the location using Flicker photos as ground truth and then using the photographs the locations were geo-tagged [20].

One major problem which the previous researchers have not been able to cope up with is the major drawback of the K-means algorithm. K-means is the prominent clustering algorithm which has a serious drawback as one is not able to determine how many clusters will be formed from the dataset, but one of the initial inputs of the K-means clustering algorithm is the number of clusters the user wants to form, which is basically a hit and miss methodology and usually the clusters formed are not the best case scenario. Therefore, this paper presents a framework which overcomes the drawback of traditional clustering algorithms and develops a multi level cluster where level 1 is based on spatial features and the level 2 is based on temporal features. Also tweets can be clustered on the basis of their sentiments. A dictionary is created which contains all the negative and positive sentiment words (approx. 2000 positive and 4800 negative sentiment words). Two clusters are created for negative and positive tweets. If a tweet contains positive sentiment then it is added to the positive sentiment cluster and if a tweet contains negative sentiment then it is added to the negative cluster.

3 Proposed framework

The proposed framework focuses on creation of clusters and indexing of tweets on the basis of the temporal, geo-locational and sentiment features of the tweets. The previous methods depended on the user for specifying the number of clusters to be formed but the proposed system will automatically evaluate the number of clusters on the basis of the indexes created. The method proposed by Pelleg et al. (X-means) which is an improvement of the K-means clustering algorithm is taken into consideration in the proposed framework, which helps in determining the number of clusters from tweets on the basis of the temporal, geographical and sentiment characteristics of the tweet [21].

A dataset can be defined as D = {d₁, d₂, d₃, …, d_n} which contains total of n documents and has a total of m-dimensions and different proxy models M_j = {C₁, C₂, …, C_k}, (e.g., for different values of k there are different models present) and the last prospect P (M_j | D) using which the scoring of the models will be done. The Schwarz criterion can be used to approximate the posteriors.

The Schwarz criterion is described as follows in Equation 1: $BIC (M_{j}) = \hat{l_{j}} (D) - \frac{p_{j}}{2} log n$ (1) where l_j(D) is the loglikelihood of D according to the jth model and taken at the maximum likelihood point, and p_j is the number of parameters in M_j. The model with the largest score is selected. Under the identical spherical Gaussian distribution, the maximum likelihood estimate for variance is defined in Equation 2: ${\hat{σ}}^{2} = \frac{1}{n - k} \sum_{i = 1}^{n} {(x_{i} - μ_{(i)})}^{2}$ (2) where μ_(i) represents the centroid which is related with the object x_i, i.e., which represents the index of centroid nearest to x_i. The point probabilities are as follows in Equation 3:

$\begin{matrix} \hat{P} (x_{i}) & = & \frac{| C_{(i)} |}{n} . \frac{1}{\sqrt{2 π} {\hat{σ}}^{d}} \\ \exp (- \frac{1}{2 π {\hat{σ}}^{2}} ∥ x_{i} - μ_{(i)} ∥^{2}) \end{matrix}$ (3)

Thus, the loglikelihood of the data is defined in Equation 4 as below:

$\begin{matrix} l (D) & = & log \prod_{i = 1}^{n} \hat{P} (x_{i}) = \sum_{i = 1}^{n} (log \frac{1}{\sqrt{2 π} {\hat{σ}}^{d}} - \frac{1}{2 π {\hat{σ}}^{2}} \\ ∥ x_{i} - μ_{(i)} ∥^{2} + log \frac{| C_{(i)} |}{n}) \end{matrix}$ (4)

The number of free parameters p_j is k - 1 + dk + 1 = (d + 1) k. X-means globally uses the Schartz criterion to select the best model it encounters and locally to guide the centroid splits. [k_min, k_max] represents the range of k. Initially X-means starts with k = k_min and continues to add centroids when required until upper limit is reached. For addition of the centroids they are splitted into two in according to the Schwarz criterion. During the process, the centroid set with the best score is recorded as the best run and considered as output.

A tweet can be defined with the help of the following tuples as described in Equation 5: $Tweet = (T_{ID}, U, T, T_{P}, G, L, U_{ID}, H R_{U}, R_{T}, N_{RT})$ (5) where,

T_ID = TweetID

U = User name

T = Main text body of tweet

T_P = Tweet Posting Time

G = Geo-location of tweet

L = Language of tweet

U_ID = User ID

H = Hash-tags contained in the tweet

R_U = Reply to User name

R_T = Re-tweet

N_RT = No. of Re-tweet

A tweet has more than 30 characteristics which may or may not be present in a every tweet. For the proposed work only a few characteristics are to be utilized and are considered as important. For example, we take only those tweets that contains the geographical location information (geo-coordinates), other tweets are then removed from the database.

The indexing of the tweets can be done on the basis of many different criteria but taking into consideration the query based method in which the user provides the system with a topic for searching and using that keyword an index is created by the system. Not all the tweets are relevant for the system as many of them are just re-tweets and others may just be in reply to some user and lack original content. So for index creation we will initially pre-process the tweets for noisy data. According to the Pareto’s Principle [22] based on Zipf’s law [23] states that 20% of the user queries represents the 80% of the total requests.

Equation 6 shows that the re-tweets and reply to user tweets are removed from the database as they do not contain original content. $N = N - R_{T} - R_{U}$ (6)

Here, N represents the tweet database, R_T represents re-tweets and R_U represents the reply to user tweets.

Algorithm 1 removes the ’re-tweets’ and ’reply-to-users’ tweets from the database as it is necessary to not to incorporate those tweets that repeat the information from the same user again and again. For example, if the user re-tweets another persons tweet then the tweet will contain the same information as the original post and will be of no use to us. Also, those tweets which contain a reply to a user are usually comments containing some sort of praise or insult and does not relate to any original content and is useless for us.

Algorithm 1 Tweet preprocessing for indexing

Require:N ≥ 0

for All Tweet belonging to N do

ifR_T = 1&&R_U=1 then

Tweet ≠ N

Remove Tweet from N.

end if

end for

where,

N = Total number of Tweets

R_U = Reply to User name

R_T = Re-tweet

Tweet = Tweet

After the pre-processing the user query (Q) is taken into account. The user query represents the keyword which must relate to the query that must be represented in the search items.

Figure 2 describes the proposed framework for clustering and indexing of tweets based on the temporal and spatial features.

Fig.2

Framework of the proposed system.

All the remaining characteristics are considered as noise and are removed. After that the tweets are normalized using the tweet dictionary which contains the latest lingos and short forms of regular texts used by the twitter users. It is necessary to normalize the tweets as many of the users, due to the character limit of the microblogs, use some sort of short form of the words to effectively relay their message. After the normalization process the stop-words are removed form the tweets. After the stop-word removal the tweets are then tokenized and then stemming is performed on the tweets. The words before and after the tokenization are stored in the database, two data-frames are created. The first data-frame contains all the named entities from the tweets in their normalized from and the second data frame contains the named entities in the stemmed from. These data frames will be a useful tool in creation of the index for the tweets. The query (Q) is then matched with the tweets taken from N. If the word is present in the data frames then the tweet will be added to a new dataset, N_Q. This new database represents only those tweets that are in accordance to the query given by the user. An initial index is to be created w.r.t. the query given by the user. The initial indexing of the tweets is done according to the number of re-tweets and the similarity measure between the query and tweets. The similarity measure used is related to the cosine distance. Equation 7 determines the similarity between the document and the query: $Sim (t, q) = \frac{\vec{V} (t) \cdot \vec{V} (q)}{∣ \vec{V} (q) ∣ ∣ \vec{V} (t) ∣}$ (7)

The creation of an initial index is necessary as the user might not be interested in the geographical and temporal aspect of the tweet and simply wants the tweets that relate to his/her query. Algorithm 2 represents the initial index creation where, T = {t₁, …, t_n} and Q = {q₁, …, q_n} and T and Q represents tweet and query respectively.

Algorithm 2 Initial Index Creation (I_i)

Require:N_Q ≥ 0

for Tweet belonging to N_Qdo

ifN_RTx > N_RTx+1then

N_RTx is bigger

Move the tweet up in index.

else

N_RTx+1 is bigger

Move the tweet up in index.

end if

end for

where,

N_Q = Total number of Tweets in N_Q

N_RTx = No. of re-tweets of tweet x

N_RTx+1 = No. of re-tweets of tweet x+1

Here ‘x’ corresponds to the number of total tweets. After the initial index is created the tweets are then clustered in accordance to their temporal and spatial features. A temporal tagger is applied to obtain any mention of dates from the tweets which is compared to the time of post creation for discovery of relational temporal expression. Now from the G (geo-coordinates) of the tweets, the region of origin of tweets is obtained and distance of the tweet locations of the tweet is calculated based on the variance of the great-circle distance which is derived from Vincenty distance. A distance threshold is set to include the tweets in the cluster.

The number of locations are obtained and this number corresponds to the number of the clusters formed, using the X-means clustering algorithm which is the variation of the K-means algorithm and discovers the optimal number of clusters without user intervention. The X-means obtains the best clusters for the given data and produces much more accurate result.

After the initial clusters formation then the X-means is applied to the cluster on the basis of the date of the creation of the post on it & again the clusters are formed. Then the final clusters are obtained that represent the tweets that emerged from a particular geographical location and within a specified period of time, which can be used to obtain trending topics, peaks, regional interests, story generation, etc. Figure 2 demonstrates the framework of the proposed system.

Equation 8 demonstrates the tweet cluster formation on the basis of the threshold distance and great circle distance formula. Where, T_GCD is the great circle distance, T_H is the threshold distance, C_x is the cluster and the T_c is the flag which determines whether the tweet belongs to the cluster or not. $T = {\begin{matrix} T_{x_{GCD}} \leq T_{H} & T_{c} = 1, C_{x} \\ T_{x_{GCD}} \geq T_{H} & T_{c} = 0, C_{x + 1} \end{matrix}$ (8)

Algorithm 3 demonstrates the initial cluster formation process based on the geo-coordinates.

Algorithm 3 Cluster fromation on the basis of Geo-coordinates

Require:N ≥ 0, φ, λ

Ensure: ∀T ← φ, λ

Calculate T_GCD

ifT_GCD < T_hthen

T ← C₁

end if

ifT_GCD > T_hthen

from new cluster from F_C

T ← C₂

end if

where,

N = Total number of Tweets

φ = Latitude

λ = Longitude

T = Tweet

T_GCD = Great circle distance of tweet

T_h = Threshold of the tweet (constant)

C₁, C₂ = Clusters

F_C = Data-frame of cluster

In the algorithm described above the clusters are formed on the basis of the geo-coordinates. First the great circle distance is calculated between tweets so as to determine the distance between them.

After the clustering of tweets on the basis of the geo-coordinates a second index (I_G) is created on the basis of the cluster formed. The index is created as follows in Algorithm 4:

Algorithm 4 Index Creation on the basis of spatial features

Require:C_G (Clustersfromed)

Ensure:C_G ≥ 0

for Tweet belonging to cluster C_xdo

ifN_Cx > N_Cx+1then

N_Cx is bigger

Move the cluster up in index.

else

N_Cx+1 is bigger

Move the tweet up in index.

end if

end for

for All Tweet belonging to cluster C_x in the index do

ifN_RTy > N_RTy+1then

N_RTy is bigger

Move the cluster up in index.

else

N_RTy+1 is bigger

Move the tweet up in index.

end if

end for

where,

N_Q = Total number of Tweets in N_Q

C_G = Clusters fromed on basis of spatial features

C_x, C_x+1 = Clusters in the index

N_RTy, N_RTy+1 = No. of re-tweets in cluster y

Here ‘x’ corresponds to half of the number of centroids according to the heuristic criterion for how promising they are to split and then split then. After that X-means is run. Equation 9 demonstrates the cluster formation on the basis of the temporal features of the tweet. Where, T_P is the time of the post, T_C is the cluster time, T_c is the tweet flag for determining whether the tweet belongs to the cluster or not and C_y is the cluster.

$T = {\begin{matrix} T_{P} \leq T_{C} & T_{c} = 1, C_{y} \\ T_{P} \geq T_{C} & T_{c} = 0, C_{y + 1} \end{matrix}$ (9)

Algorithm 5 demonstrates the final cluster formation process based on the temporal features.

Algorithm 5 Cluster formation on the basis of temporal features

Require:T_userpost, T_event

Ensure:P ← T

ifT_userpost < T_eventthen

T ← T_P

else

T ← - T_P

Discard User Post

end if

whileN_Q ≠ 0 do

ifT_P < Cthen

T ← C

N_Q ← N_Q - 1

else {T_P > C}

T ≠ C

Select different cluster

end if

end while

where,

T_userpost = User’s posting time

T_event = Time of event

T = Tweet

T_P = Time of Post

N_Q = Total Post

C = Cluster

After the clustering based on the temporal features of the tweet is done on each of the clusters formed by the geographical features, level 2 clusters are obtained within the geographical features w.r.t. time of the post. The index formation of the time based clusters is defined in Algorithm 6.

Algorithm 6 Index Creation on the basis of temporal features

Require:C_T (Clustersfromed)

Ensure:C_T ≥ 0

for Tweet belonging to cluster C_ado

ifN_Ca > N_Ca+1then

N_Ca is bigger

Move the cluster up in index.

else

N_Ca+1 is bigger

Move the tweet up in index.

end if

end for

for All Tweet belonging to cluster C_a in the index do

ifN_RTb > N_RTb+1then

N_RTb is bigger

Move the cluster up in index.

else

N_RTb+1 is bigger

Move the tweet up in index.

end if

end for

where,

N_Q = Total number of Tweets in N_Q

C_T = Clusters fromed on basis of temporal features

C_a, C_a+1 = Clusters in the index

N_RTb, N_RTb+1 = No. of re-tweets in cluster b

Initially Algorithm 3 constructs the clusters on the basis of the city names which are calculated with geopy and the distance is calculated using the great circle distance which is more effective for calculating large distance on an arc. A threshold value is set that will specify the minimum number of tweets that are required to from a cluster and then the outliers are allocated to the closest neighbouring clusters. After that individual clusters are taken and then the clustering on the basis of the time of post is done.

If the user wants to cluster the tweets on the basis of their sentiments then it is also possible. A dictionary is created containing all the negative and positive sentiments & emoticons. Algorithm 7 depicts the cluster formation on the basis of sentiments.

Algorithm 7 Cluster Creation on the basis of sentiments

Require:S_D, T

Ensure:N_Q ← T

whileN_Q ≠ 0 do

ifTcontainsS_{D
_P}then

T ← C_P

N_Q ← N_Q - 1

else

T ← - T

Check for Negative Sentiment

end if

ifTcontainsS_{D
_N}then

T ← C_N

N_Q ← N_Q - 1

end if

end while

ifT ≠ S_{D
_P} && T ≠ S_{D
_N}then

Discard Tweet as Neutral

end if

where,

S_D = Sentiment Dictionary

T = Tweet

S_{D
_P} = Positive Sentiment & Emoticon

S_{D
_N} = Negative Sentiment & Emoticon

N_Q = Total Post

C_P = Positive Sentiment Cluster

C_N = Negative Sentiment Cluster

Figure 3 shows the code for cluster formation process.

Fig.3

Cluster formation code.

4 Experimental setup

The configuration of the system used for experimental purposes is as follows: a) Processor:- Intel Core i7 (5th Gen, 3.2 GHz), b) HDD:- 1 TB, c) RAM:- 16 GB (DDR3, 1600 MHz), d) GPU:- Nvidia Geforce GT960M (3840 MB, approx. 1960 cores). The Twitter data is obtained using Fire-hose API, which results in getting all the tweets. There are 134,538 tweets that contain the geographical location. The data was collected during Feb’ 2016 and May 2016. Tweets which were in English were only taken into consideration. The database and framework used was Pandas. The two data frames are created for searching and indexing process.

The maximum tweets obtained contained the following G’s:

1:- (28.6538100, 77.2289700)

2:- (19.0728300, 72.8826100)

which corresponds to Delhi and Mumbai respectively using the geopy library.

The distance is to be calculated between the two locations so as to be certain that the locations fall within the threshold value as set by the user. If the tweet is outside the threshold value then a separate cluster is fromed of the tweet. The distance between two geo-coordinates is calculated using the special case of Great-Circle distance based on Vincenty fromula [24] as in Equation 10: $\begin{matrix} Δ σ = arctan \\ \frac{\sqrt{{(cos φ_{2} \cdot sin (Δ λ))}^{2} + {(cos φ_{1} \cdot sin φ_{1} - sin φ_{1} \cdot cos φ_{2} \cdot cos (Δ λ))}^{2}}}{sin φ_{1} \cdot sin φ_{2} + cos φ_{1} \cdot cos φ_{2} \cdot cos (Δ λ)} \end{matrix}$ (10)

where,

φ₁, λ₁ = Latitude and Longitude of Point 1

φ₂, λ₂ = Latitude and Longitude of Point 2

Δφ, Δλ = Absolute difference of Latitudes and Longitudes

Δσ = Central Angle between the Points

After using both co-ordinates in the equation the resultant distance between the two locations is obtained which comes out to be 1154 Kms or 717 Miles. Calculating the distance between the tweets and using the given threshold value the clusters are formed.

Now the clusters are obtained based on the geo-location of the tweets. The clusters are labelled on the basis of the maximum number of tweets from a location. Now within the clusters the tweets are again clustered on the basis of the date of posting the tweet. Again this is done using the X-means clustering but this time the temporal aspect of the tweets is taken into consideration. Finally, clusters are obtained based on the date of the creation of the post.

5 Results

The clusters obtained are first geographically clustered and then those clusters are again clustered using the time of creation of the post. Figure 4 depicts the clusters formed on the basis of the geo-coordinates.

Fig.4

Level 1 cluster fromed on the basis of the geo-location of the tweets (Red ’X’ represents the center of the cluster).

Figure 5 depicts the clusters fromed on the basis of the time of the tweets in location 1 cluster.

Fig.5

Level 2 cluster fromed on the basis of the time of the tweets in location 1.

The evaluation is done using two methods: Davies - Bouldin Index and Silhouette Coefficient.

Davies - Bouldin Index: The Davies - Bouldin index (DBI) [25] can be calculated by the following Equation 11: $DB = \frac{1}{n} \cdot \sum_{c_{i} \in C} max_{c_{i} \neq c_{j}} (\frac{σ_{i} + σ_{j}}{d (\bar{c_{i}}, \bar{c_{j}})})$ (11) where,

n = Number of clusters,

c_x = Centroid of cluster x,

σ_x = Average distance between elements in x w.r.t. c_x,

d (c_i, c_j) = Distance between centroids c_i and c_j.

DBI relates the average distance of elements of each cluster to their respective centroids to the distance of the centroids of the two clusters.

Since algorithms that produce clusters with low intra-cluster distances (high intra-cluster similarity) and high inter-cluster distances (low inter-cluster similarity) will have a low DBI, the clustering algorithm that produces a collection of clusters with the smallest DBI is considered the best algorithm based on this criterion.

Silhouette - Coefficient: Silhouette analysis [26] is used to study the separation distance between the resulting clusters. The silhouette plot displays a measure of how close each point in one cluster is to points in the neighbouring clusters and thus provides a way to visually assess parameters like number of clusters. This measure has a range of [-1, 1].

Silhoette coefficients (as these values are referred to as) near +1 indicate that the sample is far away from the neighbouring clusters. A value of 0 indicates that the sample is on or very close to the decision boundary between two neighbouring clusters and negative values indicate that these samples might have been assigned to the wrong cluster as shown in Equation 12. $s (i) = \frac{b (i) - a (i)}{max {a (i), b (i)}}$ (12)

Which can be also written as in Equation 13: $s (i) = {\begin{matrix} 1 - a (i) / b (i), & if & a (i) < b (i) \\ 0 & if & a (i) = b (i) \\ b (i) / a (i) - 1 & if & a (i) > b (i) \end{matrix}$ (13)

For each datum i, let a(i) be the average dissimilarity of i with all other data within the same cluster. a(i) represents as how well i is assigned to its cluster (the smaller the value, the better the assignment). Then define the average dissimilarity of point i to a cluster c as the average of the distance from i to all points in c. Let b(i) be the lowest average dissimilarity of i to any other cluster, of which i is not a member. The cluster with this lowest average dissimilarity is said to be the ’neighbouring cluster’ of i because it is the next best fit cluster for point i.

For s(i) to be close to 1 a(i) ⪡ b(i) required. As a(i) is a measure of how dissimilar i is to its own cluster, a small value means it is well matched. Furthermore, a large b(i) implies that i is badly matched to its neighbouring cluster. Thus an s(i) close to one means that the datum is appropriately clustered. If s(i) is close to negative one, then by the same logic i would be more appropriate if it was clustered in its neighbouring cluster. An s(i) near zero means that the datum is on the border of two natural clusters.

The average s(i) over all data of a cluster is a measure of how tightly grouped all the data in the cluster are. Thus the average s(i) over all data of the entire dataset is a measure of how appropriately the data has been clustered. If there are too many or too few clusters, as may occur when a poor choice of k is used in the clustering algorithm, some of the clusters will typically display much narrower silhouettes than the rest. Thus silhouette plots and averages may be used to determine the natural number of clusters within a dataset.

Table 1 shows the cluster evaluation of the different methods M1 by Morchid et al. [27], M2 by Khan et al. [28], M3 by Kalee et al. [29], M4 by Doulamis et al. [30] and the proposed method. Three different runs on different numbers of tweets have been performed. In all different scenarios the proposed system performs better than the existing clustering systems.

Table 1

Cluster evaluation

No. of Tweets	58,000		89,000		120,000
Method	DB-Index	S-Coeff.	DB-Index	S-Coeff.	DB-Index	S-Coeff.
M1	0.4163	0.4247	0.4427	0.4587	0.4839	0.4623
M2	0.4724	0.4895	0.4962	0.5053	0.5150	0.5203
M3	0.5044	0.5187	0.5337	0.5354	0.5493	0.5602
M4	0.5411	0.5432	0.5667	0.5671	0.5749	0.5892
Proposed	0.5906	0.5988	0.6079	0.6552	0.6145	0.6932

The index created in accordance to the user query is as described below. First the query word given is ‘kejriwal’ and the tweets are then first collected and then initial index is created by removing the re-tweets and reply to posts. Table 2 shows the initial index (I_i) created.

Table 2

Initial index (I_i)

Username	Text
@nnarorraa	“@SChotepur: Shame shame BJP-Akali Congress,Throwing Stones on our leader’s Car at Ludhiana. Kejriwal Safe.” Frustrated Sad-BJP On last leg
@bindaldeepak	@IndiaToday @AashishKhetan mcd should take over its all functionality of funding and kick off kejriwal govt. Kejriwal ruined Delhi.
@kam0361	Delhi Chief Minister Arvind Kejriwal to announce tomorrow decision on bringing back odd-even rule for cars
@adityaamitykar	Meeting the CM of Delhi. Our Very Own Mr. Arvind Kejriwal! Honour https://www.instagram.com/p/BB5Vymxgr-DMufsTYfANk8MetcLYtmiyjunJEA0/...
@tylgouravt	“@NitinTyagiAAP: Pehla saal, bemisal Har saal, Kejriwal”

After the level 1 clusters are formed for each cluster the indexing is done on the basis of the similarity of the query and the text and the number of re-tweets. Here the indexing is done in cluster with geo-coordinates for Mumbai.

After the level 2 clusters are generated the index is created based on the basis of the temporal features. The keyword taken here is ‘kejriwal’ and the tweet is indexed on the basis of the time of the post.

Tables 3 and 4 represents the clusters formed The complexity of the proposed framework is O (N log K), which means that the execution time of the proposed method is directly proportional to the logarithm of the input data. The method does not have to use all the data. Whereas on the other hand the complexity of the k-means method is O (n^dk+1 log n), which means that the run time of the algorithm depends on the number of factors such as n which is the number of items to be clustered, k which is the number of clusters to be formed and d which is the dimensions. This shows that the proposed method is less complex than the traditions tweet clustering algorithms.

Table 3

Index created on the basis of spatial features (I_G)

Username	Text
@goupalkanand	kejriwal creates conflicts and wastes time of all for his publicity he is psycho rightly said by an MP on oddeven silly rule
@tusharg	Kejriwal should have challaned him in Parliament.
@soniaraj2306	BJP MP Paresh Rawal apologises to Kejriwal for violating Odd Even rule – The Indian Express -...
@gurunaamsingh	MPs try to find a way out of the Odd-Even scheme in Delhi: Delhi Chief Minister Arvind Kejriwal’s pet odd-even...
@bhaveshmb3	Kejriwal claimed to support Punjab but he contradctd his own words &filed affidavit against Punjab

Table 4

Index created on the basis of temporal features (I_T)

UserName	Text
@bjpdelhistate	Arvind Kejriwal’s entire focus is on self-promotion. He is more interested in elections in other states rather than development of Delhi
@ra_bies	I think Kejriwal rightly regrets changing the name of Aurangzeb Road to Kalam road. A barbaric dictator shouldn’t tolerate his idol’s insult
@ajaymaken	Delhi HC issues notice to Kejriwal Govt. in corruption case against Minister Imran Hussain! State asked to ensure safety of the complainant
@upadhyaybjp	Motorists r complaining abt extortion &bribe by AAP volunteers in #OddEven. Kejriwal has now institutionalised corruption @ grassroot level

6 Conclusion

In this paper a framework has been presented that forms the clusters from the tweets on the basis of the temporal features, geographical location and the sentiment of the tweets. The proposed framework gives a way to cluster the tweets that belong to a particular location, a particular time period or belonging to a particular sentiment that can be searched by the user as per the query. Two indexes are created before the clustering using the proposed framework, one is for non-stemmed keywords and another for stemmed keywords, which will not only aid in the searching process but also in the summarization process. The clusters that are created using this framework will not only decrease the effort needed to search the tweets but the search time will be decreased. In future, the proposed work can be extended in the following directions: the database can taken as dynamic i.e. real-time, both internal and external evaluation is needed for improved validation as no gold standard exists, the authenticity of the tweet can be evaluated and finding a way to normalize the non geo-tagged tweets to nearest geo-location.

References

and Croft

W.B.

, Time-based language models, in Proceedings of the Twelfth International Conference on Information and Knowledge Management ACM, 2003, pp. 469–475.

Mansouri

, Ravasan

A.Z.

and Gholamian

M.R.

, A novel hybrid algorithm based on k-means and evolutionary computations for real time clustering, International Journal of Data Warehousing and Mining (IJDWM)10(3) (2014), 1–14.

Samuel

and Sharma

D.K.

, Modified lexrank for tweet summarization, International Journal of Rough Sets and Data Analysis (IJRSDA)3(4) (2016), 79–90.

Efron

and Golovchinsky

, Estimation methods for ranking recent information, in Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval ACM, 2011, pp. 495–504.

Jones

and Diaz

, Temporal profiles of queries, ACM Transactions on Information Systems (TOIS)25(3) (2007), 14.

Diaz

and Jones

, Using temporal profiles of queries for precision prediction, in Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval ACM, 2004, pp. 18–24.

Keikha

, Gerani

and Crestani

, Time-based relevance models, in Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval ACM, 2011, pp. 1087–1088.

Dakka

, Gravano

and Ipeirotis

P.G.

, Answering general time-sensitive queries, Knowledge and Data Engineering, IEEE Transactions on24(2) (2012), 220–235.

Peetz

M.-H.

, Meij

, de Rijke

and Weerkamp

, Adaptive temporal query modeling, in Advances in Information Retrieval, Springer, 2012, pp. 455–458.

10.

Massoudi

, Tsagkias

, De Rijke

and Weerkamp

, Incorporating query expansion and quality indicators in searching microblog posts, in Advances in Information Retrieval, Springer, 2011, pp. 362–367.

11.

Metzler

, Cai

and Hovy

, Structured event retrieval over microblog archives, in Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Association for Computational Linguistics, 2012, pp. 646–655.

12.

Kwak

, Lee

, Park

and Moon

, What is twitter, a social network or a news media? in Proceedings of the 19th International Conference on World Wide Web ACM, 2010, pp. 591–600.

13.

Lavrenko

and Croft

W.B.

, Relevance based language models, in Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval ACM, 2001, pp. 120–127.

14.

Metzler

and Croft

W.B.

, A markov random field model for term dependencies, in Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval ACM, 2005, pp. 472–479.

15.

, Shang

and Shen

, A hierarchical fuzzy cluster ensemble approach and its application to big data clustering, Journal of Intelligent & Fuzzy Systems28(6) (2015), 2409–2421.

16.

Demiriz

and Ekizoğlu

, Fuzzy rule-based analysis of spatio-temporal atm usage data for fraud detection and prevention1, Journal of Intelligent & Fuzzy Systems, no. Preprint, 1–12.

17.

Hawking

and Jones

, Reordering an index to speed query processing without loss of effectiveness, in Proceedings of the Seventeenth Australasian Document Computing Symposium ACM, 2012, pp. 17–24.

18.

Huston

, Moffat

and Croft

W.B.

, Efficient indexing of repeated n-grams, in Proceedings of the Fourth ACM International Conference on Web Search and Data Mining ACM, 2011, pp. 127–136.

19.

Vries

C.M.D.

, Geva

and Trotman

, Document clustering evaluation: Divergence from a random baseline, CoRR, vol. abs/1208.5654, 2012.

20.

O’Hare

and Murdock

, Modeling locations with social media, Information Retrieval16(1) (2013), 30–62.

21.

Pelleg

, Moore

A.W.

, et al., X-means: Extending k-means with efficient estimation of the number of clusters, in ICML, vol. 1, 2000.

22.

Wikipedia, Pareto principle, wikipedia, the free encyclopedia, 2016, [Online; accessed 30-May-2016]. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Pareto_principle&oldid=716693442

23.

Wikipedia, Zipf’s law, wikipedia, the free encyclopedia, 2016, [Online; accessed 30-May-2016]. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Zipf27s_law&oldid=721460097

24.

Vincenty

, Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations, Survey Review23(176) (1975), 88–93.

25.

Davies

D.L.

and Bouldin

D.W.

, A cluster separation measure, Pattern Analysis and Machine Intelligence, IEEE Transactions on2 (1979), 224–227.

26.

Rousseeuw

P.J.

, Silhouettes: A graphical aid to the interpretation and validation of cluster analysis, Journal of Computational and Applied Mathematics20 (1987), 53–65.

27.

Morchid

, Portilla

, Josselin

, Dufour

, Altman

, El-Beze

, Cossu

J.-V.

, Linarès

and Reiffers Masson

, An author-topic based approach to cluster tweets and mine their location, Procedia Environmental Sciences27 (2015), 26–29.

28.

Khan

M.A.H.

, Bollegala

, Liu

and Sezaki

, Multitweet summarization of real-time events, in Social Computing (SocialCom), 2013 International Conference on IEEE, 2013, pp. 128–133.

29.

Kaleel

S.B.

and Abhari

, Cluster-discovery of twitter messages for event detection and trending, Journal of Computational Science6 (2015), 47–57.

30.

Doulamis

N.D.

, Doulamis

A.D.

, Kokkinos

and Varvarigos

, Event detection in twitter microblogging, IEEE Transaction on Cybernetics46(12) (2015), 2810–2824.

31.

, Li

and Li

, Mssf: A multi-document summarization framework based on submodularity, in Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval ACM, 2011, pp. 1247–1248.

32.

Yih

W.-T.

, Goodman

, Vanderwende

and Suzuki

, Multi-document summarization by maximizing informative content-words, in IJCAI, vol. 7, 2007, pp. 1776–1782.

33.

Kumar

, Mahadevan

and Sivakumar

, A graphtheoretic approach to extract storylines from search results, in Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ACM, 2004, pp. 216–225.

34.

Lee

D.D.

and Seung

H.S.

, Algorithms for non-negative matrix factorization, in Advances in Neural Information Processing Systems, 2001, pp. 556–562.

35.

Wang

, Li

, Zhu

and Ding

, Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization, in Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval ACM, 2008, pp. 307–314.

36.

Shi

and Malik

, Normalized cuts and image segmentation, Pattern Analysis and Machine Intelligence, IEEE Transactions on22(8) (2000), 888–905.

37.

Wei

, Li

, Lu

and He

, Query-sensitive mutual reinforcement chain and its application in query-oriented multidocument summarization, in Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval ACM, 2008, pp. 283–290.

38.

Allan

, Introduction to topic detection and tracking, in Topic Detection and Tracking, Springer, 2002, pp. 1–16.

39.

Lavrenko

, Allan

, DeGuzman

, LaFlamme

, Pollard

and Thomas

, Relevance models for topic detection and tracking, in Proceedings of the Second International Conference on Human Language Technology Research Morgan Kaufmann Publishers Inc., 2002, pp. 115–121.

40.

Morinaga

and Yamanishi

, Tracking dynamics of topic trends using a finite mixture model, in Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ACM, 2004, pp. 811–816.

41.

Kleinberg

, Bursty and hierarchical structure in streams, Data Mining and Knowledge Discovery7(4) (2003), 373–397.

42.

Eisenstein

, O’Connor

, Smith

N.A.

and Xing

E.P.

, A latent variable model for geographic lexical variation, in Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing Association for Computational Linguistics, 2010, pp. 1277–1287.

43.

Watanabe

, Ochi

, Okabe

and Onai

, Jasmine: A real-time local-event detection system based on geolocation information propagated to microblogs, in Proceedings of the 20th ACM International Conference on Information and Knowledge Management ACM, 2011, pp. 2541–2544.

44.

Sakai

and Tamura

, Identifying bursty areas of emergency topics in geotagged tweets using density-based spatiotemporal clustering algorithm, in Computational Intelligence and Applications (IWCIA), 2014 IEEE 7th International Workshop on IEEE, 2014, pp. 95–100.

45.

Sugitani

, Shirakawa

, Hara

and Nishio

, Detecting local events by analyzing spatiotemporal locality of tweets, in Advanced Information Networking and Applications Workshops (WAINA), 2013 27th International Conference on IEEE, 2013, pp. 191–196.

46.

De Vries

C.M.

, Geva

and Trotman

, Document clustering evaluation: Divergence from a random baseline, arXiv preprint arXiv:1208.5654, 2012.

47.

Alonso

, Strötgen

, Baeza-Yates

R.A.

and Gertz

, Temporal information retrieval: Challenges and opportunities, in WWW 2011 Workshop on Linked Data on the Web, Hyderabad, India, 2011, 1–8.