Detection of Hot Topic in Tweets Using Modified Density Peak Clustering

Pohl et al. [1] discussed the social media clustering, indexing and the challenging task of identifying the events of real time data at the time of emergency. This paper shows the model which helps to classify the events based on the crisis related data. Learn and forget strategy, term frequency-inverse document frequency (TF-IDF) and incremental skewness were used. The overall model delivers a better opportunity to support emergency responders to construct a real-world emergency exercise.

Ai et al. [2] showed the usage of multidimensional sentence modelling and analysis of timeline in the detection of hot topic. To enhance the performance of the traditional system a methodology was developed using MapReduce operations which can handle huge data. Two important aspects considered in this methodology are a) micro-clustering using text selection, b) macro-clustering using topic selection.

Chen et al. [3] used automatic indexing and retrieval to get the relevant documents for a given user query. In this method, high order structure is formed by using the terms in the documents. Deerwester et al. [4] proposed a new approach for document indexing by using the factor analysis of count data.

Hofmann [5] showed the three-level structure for indexing and collection of various forms of data. This structure is formed based on the Bayesian network and it was named as Latent Dirichlet Allocation (LDA). Blei et al. [6] built a new probabilistic model to detect the topic by assigning the weights to features selected and using traditional vector model.

He et al. [7] showed the construction of the new model for topic detection. This model could update the new topic continuously by identifying the new patterns. Al Sumait et al. [8] design a model using word co-occurrence.

Newman et al. [9] proposed an enhanced single pass clustering method which uses Dirichlet allocation instead of conventional vector model. This picks the hot topic from blog. Huang et al. [10] designed a framework based on temporal features for clustering the hot topic. Chen et al. [11], also used LDA model to get the hot topic from the blog.

Ge et al. [12] used a pair of two terms and co-occurrence pattern to detect the hot topic from a small text. Lu et al. [13] devised an efficient algorithm build using Bayesian classifier to detect the hot topic over huge number of tweets online. Documents related to medical is taken as the dataset to measure the performance of proposed algorithm.

Fang et al. [14] proposed a novel methodology called multi-view clustering to pick the most discussed topic in tweets. The advantages of the proposed methodology are that it can show the relationship between the tweets and also can find the core keywords.

Huang et al. [15] proposed a new approach to detect the most discussed topic based on Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN) on Vector Space Model (VSM). Here, TF-IDF, cosine similarity has been used to cluster the documents.

Yang et al. [16] used hierarchical agglomerative clustering to detect the events. But this technique is very expensive in terms of complexity. In order to reduce the complexity K-Means is introduced in topic detection [17], but with prior definition of number of clusters.

Yu et al. [18] discovered the most discussed topic from continuous display of news occurring with very less time gap. Time related data is taken as a dataset to check the performance of proposed algorithm., Cosine similarity was used to calculate similarity between the news. Tu et al. [19], which used the advantage of density peak clustering to detect the anomalies in the spectral images. The gaussian distance measure is used to compute the local density of test data points.

Xu et al. [20] designed an enhanced adaptive density peaks clustering (DPC) to detect the overlapping communities. This uses the linear fitting to choose the cluster centroids of DPC. The gaussian distance measure is used to compute the local density of test data points. A few other works [19-21] also uses gaussian distance measure to compute local density and density peak clustering is applied for detecting the hot topic from the collected tweets.

Twitter trend analysis [22] is done using Term Frequency-Inverse Document Frequency (TF-IDF), Combined Component Approach (CCA) and Biterm Topic Model (BTM). Density peak clustering along with nearest neighbour technique to identify the noise node is shown in the reference [23]. This doesn’t rely on cut-off distance to identify the noise node. The cut-off distance computing using the Gini index in density peak clustering is shown in reference [24] and this is able to bring out better accuracy than the traditional density peak clustering. The work [25] used the online clustering for detection of trends in tweeter. The clusters are ranked based on the size and recency. The ranked clusters are persisted to Manhattan periodically for serving purposes. The Table 1 shows the recent research contribution in the area of hot topic detection.

In this hot topic detection and recommendation research work, a Modified Density Peak Clustering (MDPC) algorithm based hot topic detection is proposed. In recent years, many researchers have introduced various innovative techniques to detect hot topics in Twitter such as machine learning, data mining and swarm intelligence. The main advantage of using MDPC is that it extracts similar features of complex network data and divide the network dataset into several subsets with different clusters. Instead of using deep learning-based algorithm, these subset in MDPC algorithm minimizes the imbalance of multi-class network data and improve the detection rate of the minority classes. When compared to clustering algorithms, deep learning is considered as a very challenging issue to make recommendations because of its big scale, dynamic corpus and variety of unobservable external factors. In addition to that, Gaussian kernel is utilized by the MDPC algorithm instead of using cut-off journal in which the former one effectively measures the distance by implicitly mapping the raw data into a high-dimensional feature space. The local density of the data point is calculated by this Gaussian kernel function.

Table 1. Existing work

4.1 K-means clustering

K-means [26-28] comes under unsupervised data clustering algorithm. In this initially k-centroids are defined to form k-clusters. K can be any numerical number. Datapoints are assigned to the nearest cluster centroids by using the distance measure.

Steps in K-means cluster:

Step 1: Random ‘k’ number of centroids are selected from the given data set.

Step 2: Assign every datapoint to the nearest cluster centroids.

Step 3: New centroids are calculated after completion of step 2.

Step 4: Step 2 and Step 3 gets iterated until a fixed centroids are obtained.

Step 5: Again, every datapoints are assigned to the nearest new cluster centroid and returns the final clusters.

4.2 Spectral clustering

This clustering technique [29] is independent of shape of the cluster and cluster centroid whereas K-means algorithm can produce accurate output only when shape of the cluster is spherical and round. The best centroid can be obtained only after many iterations in K-means. The connected datapoints belong one cluster even though they are far apart. The datapoints which are not connected belong to different cluster. Steps of algorithm are shown below.

Steps:

• Compute weighted adjacency matrix for the corresponding graph and name as $^{\prime} W^{\prime}$.
• Compute the Laplacian $^{\prime} L^{\prime}$.
• Calculate the eigenvectors for first $e_{1}, e_{2}, e_{3}, \ldots \ldots e_{k}$ in $^{\prime} L^{\prime}$.
• Construct a matrix ‘U’ of vectors $e_{1}, e_{2,} e_{3}, \ldots \ldots e_{k}$ as columns.
• let $y_{i} \in R$ be the vector of ith row of U, where i=1,2,3…..n.
• Apply the K-means to assign the points $y_{i} \in R$ to one of the cluster.

Output: Cluster $A_{i}, \ldots \ldots A_{k}$ with $A_{i}=\left\{j \mid y_{j} \in C_{i}\right\}$.

4.3 Density peak clustering algorithm

Density peak clustering algorithm [30, 31] is used to group the words (represented in vector format using word embedding) taken from all the tweets. The word with highest term frequency is taken as core points for the clustering.

The underlying structure of unlabelled data space are analysed by the clustering procedure which is a significant unsupervised method. Based on the attribute similarity, the clustering procedure organizes the data into groups, such that the data from different clusters differ from each other and the data within the same cluster have similar properties.

The vector format of words is given as the input to the clustering process. The density peak clustering works based on the denser clusters. Initially, the datapoints with higher density are identified. The higher density datapoints are the datapoints which are surrounded by maximum number of neighbouring datapoints. The datapoint with maximum density and relatively large distance are considered as cluster centroids. The datapoints are assigned to their nearest cluster by measuring the distance between cluster centroid and itself. The local density $\rho_{i}$ is defined for every single data point x_i:

$\rho_{i}=\sum_{j} \chi\left(d_{i j}-d_{c}\right)$

$\chi(x)=\left\{\begin{array}{l}1, x<0 \\ 0, \text { others }\end{array}\right.$      (3)

In Eq. (3) $d_{c}$ is the cut-off distance/user specified parameter. The distance between any two datapoints $x_{i}$ and $x_{j}$ are represented as $d_{i j}$. If the distance between any two data points $x_{i}$ and $x_{j}$ are less than $d_{c}$, then those two datapoints are grouped into one cluster. The number of such data points $x_{i}$ is called density of data point $x_{i}$ represented as $\rho_{i}$.

The $\delta_{i}$ value is either taken as the minimum distance from $\mathrm{x}_{\mathrm{i}}$ to any other data point if there exists data point with a local density $>\rho\left(x_{i}\right)$ or the maximum distance from $x_{i}$ to any other data point if there exists no data point with a local density $>\rho$ $\left(x_{i}\right)$. The calculation of $\delta_{i}$ is shown the below Eq. (4).

$\delta_{i}$$=\left\{\begin{array}{c}\min _{j: \rho_{j}>\rho_{i}}\left(d_{i j}\right), x_{i} \text { is not the higher density point } \\ \max _{j}\left(d_{i j}\right), x_{i} \text { is the higher density point }\end{array}\right.$     (4) 

The steps of this algorithm are as follows:

Step 1: Compute the distance matrix for every datapoint.

Step 2: Define the cut-off distance $d_{c}$.

Step 3: Calculate the local density ρ for every data point with $d_{c}$ parameter.

$\rho_{i}=|\mathrm{A}(\mathrm{i})| / /$ Local density     (5)

where, A(i) denotes number of datapoints whose distance to point ‘i’ is less than the $d_{c}$ parameter. That is:

$\mathrm{A}(\mathrm{i})=\left\{\mathrm{j} \in \mathrm{X} \mid \mathrm{d}(\mathrm{i}, \mathrm{j})<d_{c}\right\}$     (6)

Step 4: Calculate the maximum distance between the datapoints.

$\delta_{i}=\max _{j} d_{i j}$     (7)

Step 5: For each datapoint $x_{i}$, calcule the $\gamma_{i}$ for each datapoint $x_{i}$.

$\gamma_{i}=\rho_{i} \delta_{i}$     (8)

Step 6: Arrange all the γ in the decreasing order and select the cluster centers.

Step 7: Assign rest of the datapoints to their nearest cluster centroid.

According to DPC, centroid node has two major characteristics: one is relative high density, and the other is relatively large distance from other higher density node.

The traditional Density Peak Clustering (DPC) calculates the local density by using the random dc (threshold distance) value. The random dc value shows the negative impact on the cluster formation. To avoid this, the local density of traditional DPC is modified by introducing the gaussian function for our application. This returns the hot topic irrespective of the user current location.

Main focus of our work is to detect the hot topic from the tweets irrespective of user current location. Here we have used the Modified density peak clustering to cluster the tweets and to get the largest cluster. The largest cluster is considered as the topic discussed by the most of twitter participants. The block diagram of the proposed work is shown in the Figure 1.

1.png

Figure 1. The block diagram of the proposed work

6.1 Collection of tweets

The EVENT 2012 dataset [32] is used in the experiment. A total of 30 million tweets are available, from these huge lists of tweets 159952 are labelled tweets according to the events. Twitter streaming API is used to collect the tweets. From the Wikipedia Current Event Portal and Amazon Mechanical Turk, 506 event types are collected. The collected datasets consist of the tweets discussed about Chemistry Nobel Prize and US presidential election results.

6.2 Text pre-processing

Based on the collected tweets, pre-processing is done. Pre-processing is defined by transforming the raw data into an understandable format. The text pre-processing eliminates the links, prepositions, abbreviations.

The following things are done in the pre-processing step: (i) punctuation removal, (ii) removal of stop-words such as, prepositions, articles, etc., (iii) removal of white spaces, unnecessary tabs and URLs, etc. and (iv) alteration of upper-case letters to lower case. The pre-processing is achieved by using the following procedures. In this pre-processing stage we don’t remove the hashtags as these are most valuable parts of Tweets to assign a topic.

6.2.1 Elimination of stop words

The English words which do not give much meaning to a sentence is termed as stop words. These meaningless words are removed without changing the meaning of the sentence. The, he, have etc. are the examples for this word. Normalization is described by removing the repeated words. Some letters in the words are repeated many times in social media text. This type of words cannot be found in the dictionary words and highly complex to deal with such words. Here, if any character repeats continuously for more than two times, then that character can be replaced with one single character. 

6.2.2 Stemming

Stemming means transforming the word into their root form. The root is a stem of a word which created the word. For example, the stem for the words “playing”, “played”, and “player” is “Play”.

6.3 Vector format using TF-IDF

Word embedding tool is used to convert the words into vectors of real numbers. The similar meaning words incline to be close in the vector space. Using the word embedding, words can be represented using low dimensional vector instead of high dimensional vector whereas encoding method represents the word in high dimensional vector. The computational power and generalization of learning models are enhanced by neural network toolkits and dense representations.

After the successful completion of the pre-processing, tweets are converted into vector format, where TF-IDF vector representation model is used.

TF-IDF is a way to judge the topic of an article. This is done by the kind of words it contains. Here words are given weight so it measures relevance, not frequency. Wordcounts are replaced with TF-IDF scores throughout dataset.

Word2vec produces one vector per word, whereas TF-IDF produces a score. Word2vec is great for going deeper into the documents we have and helps in identifying content and subsets of content. Its vectors represent each word’s context. (i.e., the n-gram of which it is a part). But, the biggest problem with word2vec is the inability to handle unknown or out-of-vocabulary (OOV) words. When compared to other methods, TF-IDF returns documents that are highly relevant to a particular query. Moreover, it is very easy to calculate the similarity between two documents.

6.3.1 TF-IDF vector representation

TF-IDF is used to represent the word into numerical format. The features are extracted for various NLP applications by using this technique. To apply statistical technique, the text must be transformed into numerical format. The numeric representation depicts the substantial characteristics of the text.

6.3.2 Term frequency

Term frequency represents the occurrence of word in each document. If the same word occurs a greater number of times in the document, then that word is considered as the most important word in that document.

The term frequency of a word is defined as follows:

$t f(w)=\frac{\text { Tweet.count }(w)}{\text { Total words in all tweets }}$      (14)

6.3.3 Inverse document frequency

Some word occurs very commonly in all the document and its contribution is very less in giving meaning. For example, like, make etc. are most common words that occur in every document. The occurrence of these words is extremely high when compared with the key words in the document. To reduce this effect, these words must be removed. Inverse document frequency is used to remove most frequent words.

$i d f(w)$$=\log \frac{\text { Total Number of tweets }}{\text { Number of tweets Containing word } w}$      (15)

The words like ‘what’, ‘and’ these words are common in every tweet/document. The common words in every tweet/document are not considered. These words can be picked out using the “Inverse document frequency (IDF)” shown in Eq. (15). IDF calculates the term with respect to a corpus of documents. The term which appears in every document/tweet doesn’t provide any important information to identify the topic.

$I D F($ "and" $)=\log \frac{(100))}{(100)}$=>0 [If the term “and” appears in every document].

$I D F($ "and" $)=\log \frac{(100))}{(98)}=>\log 1.02 \sim 0$ [If the term “and” appears in most of the document].

So, the terms whose value of IDF is 0 or nearly 0 is avoided and these terms are not considered.

6.3.4 Term frequency-inverse document frequency

If one term occurs regularly in a particular document, then the vector representation assigns high values for a given term. The IDF computed value will be zero, when the given term occurs in every single document. The Eq. (16) shows the calculation of TF-IDF.

$t f-i d f(w)=i d f(w) * t f(w)$      (16)

The word with highest TF-IDF value is the most important word in the document. Finally, the words in the tweets are represented as vector format and for each word in a tweet the TF–IDF value is calculated. Then by adding all the TF-IDF values of all the words in the tweet, we get value for each and every tweet. At the end of this step, we can get the value for all the tweets. These values are given as an input to the cosine similarity.

6.4 Similarity measure

In this paper, the cosine similarity measure is used to calculate the similarity between all the tweets. Here, cosine similarity matrix is formed by calculating the similarity among all the tweets.

Cosine similarity finds the dot product between two vectors. Cosine similarity produces the best accuracy in calculating the similarity between the texts and it is also low dimensional.

Cosine similarity is advantages because it returns the smaller angle, even if Euclidean distance between two similar documents is high. Smaller angle indicates high similarity.

For example, the two tweets are:

1. Julie loves me more than Linda loves me
2. Jane likes me more than Julie loves me

Count of words in both the tweets

me  2  2

Jane  0  1

Julie  1  1

Linda  1  0

likes  0  1

loves  2  1

more  1  1

than  1  1

The two vectors are, again:

a: [2, 0, 1, 1, 0, 2, 1, 1]

b: [2, 1, 1, 0, 1, 1, 1, 1]

Cos(a, b) = a . b / ||a|| * ||b||

a.b = 2*2+0*1+1*1+1*0+0*1+2*1+1*1+1*1 = 9

||a|| = sqrt[(2)^2+(0)^2+(1)^2+(1)^2+(0)^2+(2)^2+(1)^2+(1)^2]= 3.16

||b|| = sqrt[(2)^2+(1)^2+(1)^2+(0)^2+(1)^2+(1)^2+(1)^2+(1)^2] = 3.16

Cos(a, b) = 9 / (3.16 * 3.16) = 0.9.

6.5 Clustering

Density Peak Clustering (DPC) is one of the fastest clustering algorithms and requires less user input. Hence, we choose Density Peak Clustering algorithm in our work. Density peak clustering algorithm is the best at finding and can also work on arbitrary shape sample data sets.

Modified density peak clustering (MDPC) is used to detect the hot topic of discussion. This takes cosine similarity matrix as input and produces number of clusters. The similar tweets are grouped into a single cluster. The clusters having a greater number of tweets are considered as the interested topic discussed by the most of people. This interested topic is the hot topic of discussion.

The traditional DPC cannot bring the accurate output when we have different clusters with different densities and also random value of d_c (threshold distance) shows a negative impact on the cluster formation. So, instead of taking the random value of d_c, we have redefined the local density of traditional DPC by introducing the gaussian function in the calculation of d_c (threshold distance). Here the calculation of new $d_{c}{ }^{\prime}$ parameter is shown in the below Eq. (17). The d_c calculation is shown in the Eq. (18).

$d_{c}{ }^{\prime}=\left(-\left(d_{i j} / d_{c}\right) * * 2\right)$       (17)

where, $d_{i j}$ is the distance between any two datapoints.

$d_{c}=\frac{\text { Max-distance }+\text { Min-distance }}{2}$      (18)

Distances between all the datapoints are calculated. Among all the distance, the maximum distance is represented as Max-distance and minimum distance is represented as Min-distance.