A Density-based Nonparametric Model for Online Event Discovery from the Social Media Data

1 Introduction

The geo-temporal-tagged data in social media services (i.e. Flickr, Twitter, Blog) are well matching the 3W perspective (what, when, where) of events in the real world, thus, are popularly used for the task of event discovery. In general, most of the existing discovery techniques only work on a fixed static collection of the dataset [Guo and Gong, 2016; Zhao et al., 2016; Pan and Mitra, 2011]. This seriously restrains their application scope in the context of online streaming data from the social media, which are incrementally generated by users along the time.

Practically, users desire the mining work (i.e. document summarization, item recommendation, emergency detection) could be achieved in an online manner. The requirement motivated researchers towards the online techniques, and generated several works for the online event discovery. However, the existing algorithms reveal several limitations when applying them to social media. In this paper, we are going to tackle the problem and propose a robust parameter-free online algorithm for the event discovery from the social media data.

1.1 Limitations of the Existing Online Techniques

In order to deal with incremental streaming texts, both Recurrent Chinese Restaurant Process(RCRP)[Ahmed and Xing,

∗Corresponding author.

2008] and Dynamic Clustering Topic model(DCT)[Liang et al., 2016] are built on a sequence of continuous epochs along the time frame. The generation of topics in the current epoch are jointly influenced by the data distribution from prior and current epochs. One of the main deficiencies of RCRP and DCT is that no one knows what should be the optimal setting for the length of the epoch.

To solve the problem, [Du et al., 2015] modeled the temporal dynamics of events with an approach named DirichletHawkes Process. Specifically, the Hawkes Process utilized a fixed number of Gaussian kernels with different predefined bandwidths (variances), and set the means of those kernels to some points (called reference time points in the paper) along the timeframe. The current document is temporally influenced by the history of the stream by summing all those weighted kernels. However, it is not clear how to set the reference time points, the different bandwidths of the kernels, and the number of those kernels.

Besides the limitations addressed above, none of them take into account the geospatial influences of the documents. It is intuitive that geographical features of social messages are capable to better define and distinguish events. In this paper, we are going to tackle those problems.

1.2 Contributions

In this paper, we propose a nonparametric model for the online event discovery from social media data.

We assume the document stream is generated under a density function over the temporal space. By regarding the generating time (temporal tag) of each document as a sampling point in the temporal space, we can estimate the density function λ(t) using the summation of Gaussian kernels [Hinneburg et al., 1998]. When a document d arrives at time t, we regard the temporal influence on d from the stream as λ(t).

For the online event discovery, the number of the events (topics) may dynamically increase with more documents arriving. To accommodate this complexity, Dirichlet Process is exploited to infer the parameters in the model. When the new arrival of a document tells a different story from the previous, a new event is likely to be generated according to Dirichlet Process.

The social media data are not only tagged with temporal features, but also geospatial features. It is intuitive that a real world event may occur in one region or across several regions and one region may encompass multiple events along the time. We assume that events detected from the social media are distributed over a set of regions, and a mixture of Gaussians is thus employed to model the geographical distributions of events.

We integrate all those components together to formulate the Density Based Dirichlet Process for the online event discovery. Sequential Monte Carlo [Arnaud Doucet, 2001] is applied to perform the inference.

To summarize, we make the following contributions

• We incorporate the textual contents, timestamps and geo-locations of the social media data in a uniformed model for the online event discovery.
• We combine Dirichlet Process and density-based temporal dynamic technique together, where Dirichlet Process is used to capture the diversity of events while density estimation technique is exploited to learn the temporal influence of the document stream. To our best knowledge, this is the first model with parameter-free for the online event discovery in the joint space crossing temporal and geographical dimensions.
• We perform extensive experiments on two different real datasets to evaluate the proposed model, which show that our model is capable to discover meaningful events in terms of low perplexity and high coherence.

1.3 Organization of the Paper

The rest of this paper is organized as follows. In Section 2, we give a brief introduction of Dirichlet Process and density estimation method. Section 3 presents the proposed model and inference process. We discuss the experimental results in Section 4 and introduce the related work in Section 5. Section 6 concludes our work.

2 Preliminaries

In this section, we give a brief introduction to two fundamental techniques used in the paper, Dirichlet Process and the sample-based density estimation algorithm.

2.1 Dirichlet Process

Dirichlet Process [Teh et al., 2006] is one member of the nonparametric stochastic processes, which is used to model the data in a "rich get richer" fashion without specifying the parameter (e.g. topic number). We write G ∼ DP(α,G0) to denote the draw from a DP which is parameterized by a concentration parameter α and base distribution G0. We can draw samples θ1:n from it since G itself is a distribution. Specifically, we resort to the scenario of Chinese Restaurant Process to illustrate this process, where each data point is regarded as a customer of entering a Chinese Restaurant with infinite tables and dishes (topics). When the first customer arrives, she can randomly select one empty table (cluster), sit and order one dish. Then, the second customer can either join with the first customer and share the dish, or she can start a new table and order a new dish. In this way, when the nth customer arrives, she can select one table from k occupied tables with probability proportional to the number of guests already seated there, or start a new table with probability proportional to α. Formally, the conditional probability can be written as

where mk represents the number of guests selecting θk and n is the total number of customers in the restaurant by now.

2.2 Density Estimation

Suppose points t1, t2, ..., tN in an interval [a, b] are randomly generated under a density distribution λ(t), then λ(t) can be estimated using those samples as ˆλN(t) [Fukunaga and Hostetler, 1975]

where κ(ti, t, σ) = e- (t-ti)2 2σ2 is Gaussian kernel, and σ is called bandwidth of the Gaussian kernel, which indicates the influence range of the kernel. Theoretically, the value of σ varies depending on N, that is σ = σN, such that limN→∞σN = 0 in order to guarantee the unbiasedness of the estimate. A condition N · σN → ∞ is required to ensure limN→∞ ˆλN(t) = λ(t) consistently [Fukunaga and Hostetler, 1975]. Therefore, the value of σN should be set smaller if the number of samples (N) is larger.

3 ProposedModel

If we take each new arriving document dj(w, l, t) as a sample, it is intuitive to utilize Dirichlet Process for deriving topics (events) incrementally. Since the documents for the same event are temporally cohesive, we use the estimated density over time dimension to bring the temporal influence from the prior documents to the current one. Further, the documents for the same event may also be spatially clustered, a mixture of Gaussians is used for modeling the spatial distribution of events.

The overall model is presented in Figure 1, where notations in shade are observed variables, notations in dotted circles are hyper parameters, and the remains are latent variables. In detail, (ti, ..., tj) are the arriving time points of documents in the L-length sliding window (which will be discussed in the following subsection), w and l are the bag of words and location of the current document, respectively; z is the event (topic) which is generated jointly from the influence of prior documents in the sliding window and Dirichlet Process; r is the region variable with mean µ and variance Σ; w and l are generated from respective distribution ϕ and π given event z.

3.1 SlidingWindow and the Dynamic Bandwidth

In the situation of online modeling, documents are received continuously in a stream manner. We suppose the first document d1 in the stream arrives at time t1 and the current document dj arrives at tj. As introduced before, if we take all those received documents until tj as the samples in [t1, tj] then, the density at tj can be roughly estimated as:

where σj indicates the bandwidth, which is associated with both the number of points in [t1, tj ] and length of the temporal space (|tj - t1|).

This estimation dynamically brings the influences of all those prior documents on the current document dj in a natural manner. However, there are two problems when using it directly in the online modeling: (1) the dynamic increasing of the temporal space [t1, tj] which requires all previous documents to be in the computation, and (2) the previously determined optimal value of σj may become improper along the document streaming.

To deal with the first problem, we introduce a sliding window [tj -L, tj ] to account only documents arriving after time tj - L for the density estimation at tj. The intuition of this measure is based on the significant decay of the Gaussian kernel influence to ˆλN(tj) when |ti - tj| is large enough (i.e. larger than L).

To solve the second problem, we suppose the arriving of documents is generated uniformly under the density function λ(t) in a relatively short time duration with fixed length Γ (i.e. a duration of one or two months). However, the arriving of documents may become nonuniform in a larger timeframe because of the the significant increase of users in the social media system along the time. Let σj denote the bandwidth in the timeframe [tj -Γ, tj], and Nj denote the number of documents received in this period. Then, σj will be dynamically tuned to maintain σ0N0 ≈ σjNj, where σ0 is the optimal setting for the bandwidth in the initial period [t1, t1 + Γ].

3.2 Generating Topics

The joint process of Dirichlet Process and temporal density is parameterized by an intensity parameter α and a base distribution G over a given space θ. Each event is associated with an unique θ .

Let D = {dj-Lj , dj-Lj+1, ..., dj} denote the set of documents in the sliding window of the current document dj, and Lj is the number of documents in it. The probability of sampling θ for document dj is computed as:

where λθk (tj) := ∑ji=j-Lj κ(ti, tj, σj)I[θ(ti) = θk] denotes the aggregated influence to the current document dj from the documents in the corresponding sliding widow, whose event assignments are θk.

Therefore, the combination of Dirichlet Process and temporal density can not only infer the event number automatically, but also take into account the temporal influence of the documents in the stream.

3.3 Generating Location andWord

It is intuitive that a real world event may occur in one region or across several regions, and one region may encompass multiple events along the time. To capture the footprints of events from the social media, we assume that each event geographically is distributed over a set of regions, and each region is modeled by a Bi-Variant Gaussian parameterized as (µ, Σ). Thus the spatial distribution of an event is represented by a mixture of Gaussians, and geographical popularity of a region to a specific event is determined by its weight. Such spatial modeling allows a complex and diverse spatial pattern of an event. In detail, given an event indicator z of document d, the probability of generating location l is computed as:

where r denotes the geospatial region, πz denotes the weights of the Gaussian mixture for topic z, and N is the number of regions.

In general, documents generated from social media (e.g. Twitter, Weibo and Flickr photos) share a common property that each of them is short and always tells one story. Hence in our problem setting, each document is only assigned to one event. Under such an assumption, given an event z the probability of generating the content w of document d is computed as:

3.4 SMC Inference Process

Given the documents arriving in a stream manner, our goal is to conduct an online computation of the posterior distribution P(z1:n, r1:n|d1:n), where d1:n, z1:n and r1:n represent all the past documents, their event indicators and region assignments.

At time t = n - 1, let P(zi:n-1, ri:n-1|di:n-1) denote the posterior distribution in the corresponding sliding window. With the new document dn arriving, the posterior would yield the most recent value P(zi:n, ri:n|di:n) by reusing P(zi:n-1, ri:n-1|di:n-1) , which motivates us to apply Sequential Monte Carlo (SMC) method [Doucet et al., 2000; Arnaud Doucet, 2001] to infer the sampling process.

The overall structure of Sequential Monte Carlo (SMC) is described in Algorithm1. Briefly, the posterior approximation is maintained as a set of particles, each of which represents a hypothesis about the latent variables. There is an importance weight associated with each particle to indicate how well the hypothesis explains the data. The main ingredient for designing an SMC is the proposal distribution Q(zi:n, ri:n|di:n) which can be regarded as the biased posterior estimation given the streaming documents in our online model. The weight ωfn of each particle f ∈ {1, ..., F} is therefore defined as the ratio of the true posterior distribution over the proposal distribution ωfn = P(zi:n,ri:n|di:n) Q(zi:n,ri:n|di:n) . In order to minimize the variance of resulting particle weights, a commonly used technique in SMC [Arnaud Doucet, 2001; Ahmed et al., 2011b], is to take Q(zn, rn|zi:n-1, ri:n-1, di:n) as the posterior P(zn, rn|zi:n-1, ri:n-1, di:n). Therefore the unnormalized importance weight for particle ωfn can be up-

Since each document is denoted by a triplet di = {wi, ti, li}, the above equation can be detailed as

The event and region indicator can be alternatively sampled for each newly arriving document in the following way.

Sampling event indicator z. When the new document dn = {wn, tn, ln} arrives, the probability of its topic assignment is computed as

where P(zn|tn, rest) is computed by Equation 1. Because of the one-event restriction for each document in our context, the probability of generating textual content w for document d can be computed as

where ndv records the occurrence number of word v in document d, nzv describes the co-occurrence number of word v and event z, nvz denotes the word number assigned to event z, and nd records word number in document d.

Sampling region indicator r. Given the event indicator and new document, the probability of sampling region is

4 Experimental Evaluation

All the experiments are conducted on a computer with Intel Core i7 2.93GHz CPU and 8GB RAM, and all the algorithms are implemented using Visual C#.

4.1 Experimental Setup

Dataset. Our experiments are based on two real datasets, which are crawled from Flickr through its API 1 . The first

1 http://www.flickr.com/services/api

Algorithm 1 SMC algorithm over document stream

1: Initialize ωf 1 to 1F for all f ∈ {1, ..., F} 2: for each document dn, n = 1, 2, ... do 3: for f ∈ {1, ..., F} do 4: Sample event indicator zfn by Equation 3 5: Sample region indicator rfn by Equation 5 6: Update each particle weight ωfn by Equation 2 7: end for 8: Normalize particle weights 9: if ||ωn||-2 2 = 1/∑Ff=1 (ωfn )2 < threshold then 10: Resample particles 11: end if 12: end for

dataset is collected for Paris, which consists of more than 26 thousands photos from June to August 22th in 2010. The second dataset is for New York (NY), which includes more than 40 thousands photos from January to March in 2010. For each dataset, the photos without any textual description are discarded, and we split the Flickr tag (phrase) into single word and remove the irrelevant words (e.g. camera names). After the preprocessing, the statistics of the two datasets are as shown in Table 1.

Compared methods.

• RCRP-geo. RCRP is regarded as one of the benchmark algorithms in modeling online event detection [Ahmed and Xing, 2008]. Since RCRP does not involve spatial distributions of events, we extend it to the spatiotemporal space by associating each topic with regions using a mixture of Gaussians(the same as the proposed model). The extended model is referred to as RCRP-geo.
• DCT-geo. DCT is one of the-state-of-art algorithms for modeling online topics [Liang et al., 2016]. Similar to RCRP-geo, we extend it to spatial-temporal space. The topic number is predefined as the same value as DPdensity.
• DP-density-fixed. It is a variation of the proposed model by fixing the event number as predefined. This model is used to measure the effectiveness of the proposed approach in inferring the right number of events.

4.2 Event Discovery from the Datasets

Content Analysis. First of all, to have an intuitive idea of events discovered from streaming datasets, Figure 2 shows some interesting events extracted from New York city, including Women Summit, Orchid Show, New York Fashion Week and Chinese New Year Parade. Even though tag vocabulary attached to Women Summit photos are very concise, still the semantic feature of this event is quite clear. From the perspective of interpretability and word coherence, our proposed model can effectively discover the meaningful events.

(b) Cumulative density dis-

tribution

Figure 3: Event of Chinese New Year Parade in the temporal space

Temporal Dynamics. Figure 3 (a) and (b) plot the density and cumulative density distribution of Chinese New Year Parade on February 21th, respectively. As we notice, during the first one and half hour, indicated from the density value of Figure 3 (a), document arrivals are sparse, which is also confirmed by the gradient of cumulative density distribution in Figure 3 (b). Starting from 11:30 to 13:00, this event starts to be popular since the density value approximately keeps stable around 0.4. In the duration from 13:00 to 14:30, more documents are densely received and density value ranges from 0.4 to the peak of 1.6. During the last interval, the arrivals of documents are decreased as shown in the figure.

4.3 Perplexity Evaluation

In this section, we quantitatively evaluate the performance of the proposed method.

Metric perplexity [Blei et al., 2003] is widely used to measure how well a probabilistic model predicts a sample. A lower perplexity indicates a better generalization of the model. Distinct from the conventional random selection of the testing dataset in the offline models, a set of documents are collected at each regular interval along the time, the aggregated testing collection accounts for 10% of the overall dataset. Specifically, the text perplexity is defined as

where M represents the testing collection, Nd records the number of words in document d, and wd denote the words in document d.

Perplexity over varying temporal epochs. Figure 4 plots the perplexity value via varying numbers of epochs over both New York and Paris dataset. As we notice, our proposed model DP-density achieves a significant decrease in perplexity compared with competitor models over the two datasets. The performances of RCRP-geo and DCT-geo are greatly affected by the manual setting of epoch numbers, both of which gain their optimal value at the epoch number of 50 in two datasets. Specifically, DCT-geo outperforms RCRP-geo at any setting of epoch numbers in New York dataset.

Perplexity over varying event numbers. Figure 5 shows the comparison between the proposed DP-density and its variation DP-density-fixed. In the case of Paris dataset, the automatically inferred event number by the proposed model ranges from 55 to 62 through many trials, which is consistent with the performance of DP-density-fixed in terms of perplexity metric. In the New York dataset, perplexity of DPdensity-fixed tells the optimal event number around 75, which is coincided with the automatical derived result (ranging from 70 to 75) by the proposed approach.

4.4 TermCoherence

We proceed to validate the interpretability of each discovered event using the coherence measure. Similar to [Guo and Gong, 2016], we define the coherence of the top-10 terms of each event as the average of PMI(Pointwise Mutual Information), which is calculated based on the coherence computation from [Röder et al., 2015]. A higher PMI-Score indicates the terms within an event are more coherent and consistent to describe the event.

The coherence results are presented in Figure 6. It is observed that the coherence score of DP-density is always higher with any setting of epoch numbers, while the performances of RCRP-geo and DCT-geo decrease with the growing epoch number. In Paris dataset, RCRP-geo performs better than DCT-geo before the setting of 50 epoch number, and gains close result with DCT-geo as the epoch number increases. In New York dataset, DCT-geo outperforms RCRPgeo at any setting of epoch number, which is consistent with perplexity performance.

4.5 Efficiency

Figure 7 presents the event number with time evolution and document efficiency in Paris dataset. Since the event number is automatically learned in our proposed model, it is observed the event number grows gradually over time and keeps constant at 63 in Figure 7 (a) . Correspondingly, we expect average time cost of processing each document keeps roughly stable after running a time period, which is confirmed by the Figure 7 (b) from 18000th document after the long build-up period.

5 RelatedWork

Most of online event detection models are extensions of Latent Dirichlet Allocation(LDA) [Blei et al., 2003]. We summarize the related work into two categories, Sequential

(a) Paris dataset RCRP-geo DCT-geo DP-density

20 30 40 50 60

#Epoch Number

(b) NY dataset

(a) Event number with time

evolution

Figure 7: Event number with time evolution and document efficiency in Paris dataset

Monte Carlo (SMC) based and Gibbs Sampling based inference approach according to the way of estimation.

Sequential Monte Carlo based inference process [Doucet et al., 2000; Arnaud Doucet, 2001], requires one time pass over the streaming data since it sequentially processes the documents according to their arriving time. [Canini et al., 2009] introduced online inference of SMC based on LDA while [May et al., 2014] improved rejuvenation step of SMC. Whereas these two methods suffer from the manual setting of topic number in the case of online modeling. [Ahmed et al., 2011b; 2011a] relieved such a setting and applied SMC inference to detect a hybrid of topics and storylines. However, all these methods fail to depict dynamic density of topics along the time. [Du et al., 2015] exploited Dirichlet-Hawkes Process model to detect online topics from streaming news articles. But how to give the specific the number of kernels, and their respective locations and widths is an challenge, since documents are received continuously along the time. An-

Perplexity

320

260

200

140

80

other drawback is that it fails to investigate the function of spatial patterns of topics. In comparison, we proposed a density based online model in the joint spatio-temporal space, and temporal dynamics of events are flexibly learned from estimated density distribution in a sliding window.

Gibbs Sampling based inference process, requires multiple passes over the streaming collection to obtain a stable sampling for each document. Thus it is unsuitable for streaming data. Given the set of predefined time epochs, both RCRP[Ahmed and Xing, 2008] and DCT[Liang et al., 2016] detected the most recent topic depending on learned results from previous epochs. One of main deficiencies of RCRP, DCT and their related work [Blei and Lafferty, 2006; Cheng et al., 2014] is that it requires an explicit division of streaming documents into unit episode. Rather than divide time, [Wei et al., 2007; Iwata et al., 2009; Wang et al., 2012; Amoualian et al., 2016] built online topic modelings on the assumption of dependency between temporal consecutive documents. Among them, [Wei et al., 2007; Wang et al., 2012] modeled the dependency of topic distribution while [Iwata et al., 2009; Amoualian et al., 2016] modeled dependency of both topic distribution and topic transition between consecutive documents. However, the dependency assumption is rigid, since two consecutive documents from a dense document stream is possibly contributed by two simultaneous events and there is no temporal dependency between them. [Yin and Wang, 2016] presented an online clustering scheme in which the number of clusters (topics) is flexible to grow with data but limited by a predefined threshold. In contrast, the proposed DP-density aims to detect online events from social media data where both event number and event density can be flexibly learned without restrictions.

Besides, there are other online studies focused on specific events. [Zhang et al., 2016] aimed to detect real-time local events from geo-tagged tweet streams. [Sakaki et al., 2010] explored real-time earthquake detection while [Li et al., 2012] detected crime and disaster events(CDE) with selfadaptive crawler.

6 Conclusion

We present a novel online event discovery model for social media data. The key aspects of our model are (1) flexibly inferring event number using Dirichlet Process to accommodate the complexity of continuous document arrivals, (2) dynamically learning the temporal dynamics of events using density estimation, (3) integrating combination of DP and density estimation into topic modeling in the joint spatio-temporal space. Our extensive experiments have demonstrated that our proposed model is able to discover interpretable events in terms of low perplexity and high coherence.

Acknowledgments

This work was supported in part by Fund of Science and Technology Development of Macau Government under FDCT/116/2013/A3 and FDCT/007/2016/AFJ and in part by University Macau Research Committee under MYRG201500070-FST and MYRG2017-00212-FST.