The task of the SNOW 2014 Data Challenge is to mine Twitter streams to provide journalists a set of headlines and complementary information that summarize the most newsworthy topics for a number of given time intervals. We propose a 4-step approach to solve this. First, a classi er is trained to determine whether a Twitter user is likely to post tweets about newsworthy stories. Second, tweets posted by these users during the time interval of interest are clustered into topics. For this clustering, the cosine similarity between a boosted tf-idf representation of the tweets is used. Third, we use a classi er to estimate the con dence that the obtained topics are newsworthy. Finally, for each obtained newsworthy topic, a descriptive headline is generated together with relevant keywords, tweets and pictures. Experimental results show the e ectiveness of the proposed methodology.
Social media is an excellent source to detect events due
to their large data volume, broad user base and
realtime nature. Extensive work has shown that social
media can successfully detect events [
In this paper, we propose our methodology for a
solution to the SNOW 2014 Data Challenge. The
task of this challenge is to automatically mine social
streams to provide journalists with a set of headlines
and complementary information that summarize the
newsworthy topics for a number of timeslots (time
intervals) of interest. For an overview of the details
of this challenge, we refer to [
The remainder of this paper is structured as follows. We start with a review of related work in Section 2. Next, in Section 3, we describe our methodology for discovering newsworthy topics. Subsequently, Section 4 presents the experimental results. Finally, we conclude our work in Section 5. 2
There has been a lot of interest in detecting events and trending topics in social media. This research can be divided in two types of approaches. In the rst type, social media documents (e.g. tweets) are clustered. This is referred to as document-pivot. An event or topic is thus represented by a cluster of documents. The second line of work rst selects the most important words, which are then clustered. In this approach, referred to as feature-pivot, an event or topic is represented by a cluster of words.
Document-pivot approaches cluster social media
documents by leveraging some similarity metric
between them. TwitterStand [
Feature-pivot methods use statistical models to
extract sets of words that are representative for the most
important topics and events described in a corpus of
documents. In [4], for example, the authors analyze
the temporal and locational distributions of Flickr tag
usage to detect bursty tags in a given time window,
employing a wavelet transform to suppress noise.
Afterwards, the tags are clustered into events such that
each cluster consists of tags with similar locational
distribution patterns and with similar associated photos.
Finally, photos corresponding to each detected event
are extracted. EDCoW [
For a stream of tweets (called test set, T n), we want to determine the most newsworthy topics. In particular, for each time interval of interest i 2 I, m 1 newsworthy topics will be automatically extracted. To easily interpret the extracted topics, each topic will be in the form of a short headline that summarizes the topic, accompanied by a set of tweets, URLs of relevant pictures, and a set of keywords. To optimize the proposed methodology, we use a training set T k of tweets with known newsworthy topics.
For a given stream of tweets T n and a time interval i 2 I, we rst determine the users who posted the tweets during time interval i who are most likely to post about newsworthy stories. The tweets of these users are then clustered into topics. Thereafter, the obtained topics are ranked based on the con dence that they are newsworthy. Finally, for each detected newsworthy topic, the headline, most relevant tweets, tags and pictures are determined. The implementation of our methodology has been made publicly available to the research community.1 In the rest of this section, we will explain each step in more detail. 3.1
The rst step of the proposed methodology is to estimate the likelihood that a Twitter user will post tweets about newsworthy topics. We indicate Twitter users who almost always publish newsworthy tweets as `news publishers'. Examples are o cial twitter accounts of news papers, news programs or news websites. Given a set of tweets, the corresponding authors can then be ranked based on the probability that they are news publishers. Only tweets of the top ranked users will be used to detect newsworthy topics.
We rst manually annotate 10 000 Twitter users as `news publisher' or `other'. We call this set of user U . Second, we use 5-fold cross-validation on the set U to nd relevant user features and to train a classi er that optimizes the average precision of the users, which are sorted based on the likelihood that they are news publishers. As candidate classi ers, we consider all methods implemented in WEKA [8] as well as the Support Vector Machine (SVM) implementations of LibLinear [9]. The obtained features are shown in Table 1. The classi er which led to the largest average precision is a Bayesian belief network that uses a local K2 search algorithm [5].
Finally, user set U is used to train a Bayesian belief network which estimates the probability that the users which posted the tweets in test set T n during time interval i are news publishers. The users with 1https://github.com/svcanney/twittertopics probability larger than are considered as `news publishers', noted as set Pin. Similarly, for each i0 2 I0, the news publishers who posted tweets in the training set T k during time i0 are contained in the set Pik0 . Set I0 contains the considered time intervals corresponding to the training set T k. 3.2
In the second step of our methodology we cluster the tweets posted by users in Pin. Using only the tweets of news publishers, we signi cantly reduce the noisy tweets leading to `junk'-topics. The clustering is performed using the DBSCAN [6] algorithm with parameters and minimum number of points required to form a cluster minPts.
As distance measure we use the cosine distance between the boosted tf-idf representations of the tweets. The boosted tf-idf value of a word w in tweet t posted during time interval i is given by tf-idfiw = tf-idf w
E-boostw
T -boostiw
(1)
Factor tf-idf w is the standard term frequency-inverse
document frequency for word w in tweet t. The
document frequencies used for this tf-idf w value are
obtained from a set of tweets T e which is unrelated to T k
and T n. As T k and T n may contain tweets which are
related to a speci c event (see Section 4.1), we would
have much lower tf-idf w values for the event-speci c
words when these sets were used to calculate the
document frequencies. Nonetheless, these words can be
very relevant in the detected topics. By using an
unrelated set of tweets, we are thus able to use more
general event-independent document frequencies.
The rst boosting factor E-boostw is the boosting of
proper nouns and verbs, similar as in [
The second boosting factor T -boostiw is temporal boosting, in which we boost the words based on their relative document frequency in this time interval i versus the previous time intervals, thus the burstiness of the words. More concretely, we de ne piw = dfiw Ni (2) as the relative frequency of word w in time interval i, with dfiw the document frequency of the word in the time interval and Ni the total number of tweets posted during i. We boost each term with the following temwith p0w;i 1 the exponential moving average of the relative frequencies of the word w for the time intervals 0 until i 1, using a smoothing factor .
Finally, we de ne the center of a cluster c 2 Cin as vector centerc, obtained by averaging out all boosted tf-idf representations of the tweets in cluster c.
The detected topics from tweet test set T n during time interval i are given by Cin. Similarly, the detected topics of training set T k during interval i0 2 I0 are given by Cik0 . Additionally, we de ne set Ck = Si0 Cik0 . 3.3
We explore di erent features to describe the detected clusters of Cin in order to identify newsworthy topics. A classi er trained on Ck is then used to detect newsworthy topics in the set of clusters Cin during interval i, indicated by the set Sin.
The training set of detected topics Ck is used to nd
the optimal features and classi er. Similar to the
approach described in Section 3.1, we consider all
methods implemented in WEKA [8] as well as the Support
Vector Machine (SVM) implementations of LibLinear
[9] as candidate classi ers. We rst manually label
the topics in training set Ck as `newsworthy' or `not
newsworthy'. Second, Ck is partitioned into two
disjoint subsets of topics, based on their time intervals:
development set Cd comprises the rst two thirds, the
validation set Cv the last third. The topics of the
development set Cd are used to train a classi er. This
classi er is then used to estimate the likelihood that
a topic c 2 Cv is newsworthy. For a particular time
interval, the corresponding topics can then be ranked
based on this likelihood. The objective is thus to
optimize the mean average precision of these rankings.
The obtained features are shown in Table 2. These
features are divided in four categories. The rst category
takes the number of tweets in the clusters and their
type into account. For instance, a cluster with just a
few associated tweets may not be related to a
newsworthy topic. The second category considers the features
of the users. If the users who posted the tweets in
the clusters are very likely to be news publishers (e.g.
with probability higher than 0.9), the cluster
probably corresponds to a newsworthy topic. The third
category of features describes the topical coherence of
the cluster, based on the hypothesis that newsworthy
clusters tend to address a central topic, whereas noisy
non-newsworthy topics cover more heterogeneous
topics. The last category of features is used to exclude
clusters corresponding to a topic that was already
detected in a previous time interval, as we consider topics
only as newsworthy when they occur for the rst time.
The classi er that leads to the highest mean average
precision is Support Vector Machines (SVM) trained
using sequential minimal optimization [
The nal step in our methodology is the topic enrichment. This step starts from each obtained newsworthy topic s 2 Sin and generates a headline, extracts keywords, a list of associated tweets and a list of pictures. These steps are mostly handled individually and are discussed in the following subsections. 3.4.1
The headline of newsworthy topic s is constructed as a cleaned up version of the most representative tweet sentence in the set of tweets related to s. These tweet sentences are obtained by splitting each tweet in tweet sentences based on the presence of punctuation marks, and only retaining sentences containing at least one verb. To retrieve the most representative tweet sentence, we select the sentence with maximum cosine similarity between its boosted tf-idf representation and the vector associated with the topic center centers. Subsequently, we apply a set of rules to clean the obtained sentence: (1) Removing the mentions of users if they are part of a retweet mention. (2) Removing all URLS and emoticons. (3) Removing hashtags if they do not syntactically belong in the sentence. (4) Removing the `@' and `#'-symbols from the remaining hashtags and user mentions. (5) Removing parts of sentences inside parentheses. (6) Splitting the camel case words into di erent words. (7) End the headline with a punctuation mark. The keywords are chosen as the words present in the headline which are in the top 50% of the most important words associated to topic s. This importance of a word w is given by its tf-idfiw value in centers. 3.4.3
To extract a representative set of tweets, we rst expand the list of tweets related to our topic by including tweets from users which are not indicated as `news publishers'. In particular, we consider all tweets in T n posted during i with a cosine similarity between their boosted tf-idf representation and the center of the topic which is higher than !. Next, these tweets are ordered based on their relevance to the topic, denoted as relevancets. The relevancets value of tweet t is de ned as the cosine similarity between its boosted tfidf representation and the center of the topic centers, multiplied by the user factor. This factor is 1 if the user who posted tweet t is indicated as a `news publisher' and 1 otherwise. This ordered list of tweets related to topic s is denoted by Tsn.
The tweets associated with a single topic should be su ciently di erent from each other, therefore we discard tweets in Tsn which are near-duplicates of tweets that are ranked higher in the list. To measure the similarity between the tweets in Tsn, we use the cosine similarity between the non-boosted version of the tfidf representations of the tweets. In particular, tweets are considered as `near-duplicates' if their similarity is higher than '. We discard boosting in this step, since the goal of boosting was to increase the impact of the topic-related words, thereby diminishing the impact of the other words in the tweet. However, the tweets in Tsn are all related to the same topic, and all contain these topic-related words leading to a high cosine similarity of their boosted tf-idf representations, mainly caused by the presence of these topic-related words. As we want to obtain a coherent diverse set of tweets describing this topic, we want tweets that contain these topic-related words, but have a signi cant number of di erent non-topic-related words. If we had used the boosted tf-idf, the cosine similarity would almost only be impacted by the number of matching topic-related words. Finally, the top 5 tweets of this ltered Tsn list are considered as representative for topic s. 3.4.4
In order to obtain a full list of pictures related to topic s, the tweets of Tsn containing the same picture URL are grouped. Picture URLs are obtained by using the media entities associated with the tweets. The picture URLs are then sorted based on the sum of the relevancets values of the tweets containing the URL. Finally, the top 5 picture URLs are considered as relevant to topic s. 4 4.1
In order to evaluate our approach, we crawled the
Twitter posts meta-data of the given Twitter id's
related to the 2012 US elections event posted on Twitter
between November 6, 2012 23:30 GMT and November
7, 2012 7:00 GMT (training set, T k). The test set T n
contains tweets related to the Syria, Ukraine, terror
and bitcoin-problems mentioned on Twitter between
February 25, 2014 18:00 GMT and February 26, 2014
18:00 GMT. More details about the training and test
set can be found in [
As described in Section 3.1, we use 5-fold crossvalidation on the user set U to optimize and evaluate the methodology which detects news publisher. User set U contains 10 000 Twitter users who are manually annotated as `news publisher' or `other'. As a result of this process, 1.64% of the users were labeled as `news publisher'. The proposed methodology to rank users based on the likelihood that they are news publishers resulted in an average precision of 88.83%. In general, 99.41% of the users in U were correctly classi ed, which is signi cantly higher than the 98.36% accuracy when all users are classi ed as `other' (sign test, p < 0:001). 4.2.2
The training set of detected topics Ck is used to optimize and evaluate the topic ranking methodology, as described in Section 3.3. Set Ck contains 116 manually annotated clusters, of which 54 are labeled as `newsworthy'. For each considered time interval i0 corresponding to clusters in validation set Cv, the clusters of Cv associated with i0 are ranked based on the con dence that they are related to a newsworthy topic. The mean average precision of these rankings is 99.17%. In general, 82.05% of the clusters in the validation set were classi ed correctly. 4.2.3
Our methodology extracted 433 newsworthy topics from the test set, given by set Sn = Si Sin. The newsworthy topics of time intervals February 26, 2014 09:15 until 10:15 GMT are shown in Table 3. These results show the e ectiveness of our methodology to discover newsworthy topics in Twitter. As we only use tweets posted by `news publishers' to detect topics, most of the discovered topics are indeed newsworthy. However, we observe that some duplicates are not removed mainly because users sometimes discuss one topic in di erent words, i.e. the high similarity of these topics can not be detected using cosine similarity on their associated words (e.g. topic 7 and 10). In addition, some non-newsworthy topics were incorrectly extracted due to users who are classi ed as `news publisher' who post non-newsworthy content (e.g. topic 15). Finally, we observe that the obtained headlines are informative and that they are constructed in a syntactically correct way.
The extensive summary of the newsworthy topics extracted during time interval February 26, 2014 09:15 can be found in Table 4. We observe that the representative tweets for a particular topic are su ciently di erent from each other, i.e. no near-duplicates or retweets are given. Additionally, we note that the coherence of the tweets associated with topic 2 is higher than the coherence of the tweets associated with topic 1. In particular, topic 2 covers one clear topic (i.e. about So a monument's makeover), in contrast, topic 1 covers very similar, but di erent, topics (i.e. about a military vehicle in Kiev, Ukraine; and about a military vehicle in Sevastopol, Ukraine). The discovered pictures related to these newsworthy topics are shown in Figure 1. In total, 24% of the discovered newsworthy topics contains at least one related picture.
The newsworthy topics in Sn and their summaries
are evaluated across a mixture of quantitative and
qualitative dimensions by a panel of news professionals
selected by the SNOW 2014 Data Challenge
organizers. These o cial evaluation results of our
methodology are included in [
We proposed a methodology which automatically mines Twitter streams to provide journalists with a set of headlines and complementary information that summarizes the most important topics for a number of time intervals of interest. As we are only interested in newsworthy topics, we only use tweets of users who are classi ed as `news publishers'. These tweets are then grouped into topics using a DBSCAN clustering algorithm, whereby the similarity between the tweets is determined using the cosine similarity on their boosted tf-idf representations. Thereafter, a classi er is trained to estimate which of the detected topics is newsworthy. Finally, for each obtained newsworthy topic, a descriptive headline, together with relevant tweets, keywords and pictures is determined. Experimental results show the e ectiveness of the proposed methodology.
Steven Van Canneyt is funded by a Ph.D. grant of the Agency for Innovation by Science and Technology (IWT). 2010.
441, 2011. S. Papadopoulos, R. Skraba, A. Goker, I. Kompatsiaris, and A. Jaimes. Sensing trending topics in Twitter. IEEE Transactions on Multimedia, 15(6):1268{1282, 2013. [2] H. Becker, M. Naaman, and L. Gravano. Learning similarity metrics for event identi cation in social media. In Proc. of the 3rd ACM Int. Conf. on Web Search and Data Mining, pages 291{300, [3] H. Becker, M. Naaman, and L. Gravano. Beyond trending topics: Real-world event identi cation on Twitter. In Proc. of the 5th Int. AAAI
[4] L. Chen and A. Roy. Event detection from Flickr data through wavelet-based spatial analysis. In
[5] G. Cooper and E. Herskovits. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9(4):309{347, 1992. density-based algorithm for discovering clusters in large spatial databases with noise. In Proc. of
Mining, pages 226{231, 1996. [7] K. Gimpel, N. Schneider, B. O. Connor, and D. Das. Part-of-speech tagging for Twitter: Annotation, features, and experiments. Proc. of the 49th Annual Meeting of the Association for Computational Linguistics, pages 42{47, 2010. [8] M. Hall,
H. National, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten. The WEKA data mining software : An update.
[9] S. Keerthi, S. Sundararajan, and K. Chang. A sequential dual method for large scale multi-class linear SVMs. In Proc. of the 14th ACM SIGKDD