Using Social Media to Enhance Emergency Situation Awareness: Extended Abstract

1 Introduction

Social media has emerged as a popular channel for providing new sources of information and rapid communications, particularly during mass emergencies. First-hand information from people on the scene often conveys timely and actionable information, which is greatly valuable for official authorities to better respond to the emergencies. Augmenting the traditional communication means such as phones with social media significantly increases the amount of information exchanged between affected people and emergency responders. This leads to higher situational awareness which in return translates to faster and more informed decisions and actions. Disaster management using Twitter has recently been studied for humanitarian crises and natural disasters such as earthquakes, bushfires, and cyclones [Sakaki et al., 2010; Vieweg et al., 2010; Li et al., 2012; McMinn et al., 2014].

Harnessing credible information on emergency events from social media is however very challenging. Twitter for example only allows short textual messages called tweets of up to 140 characters. It thus encourages its users to use abbreviations to shorten their tweets. Language of Twitter users can be largely different to formal text, with users often communicating in colloquial language which is not handled effectively by well-established natural language processing techniques. The sheer volume of information that is spread by millions of users is also overwhelming. It requires text mining algorithms that can handle massive amounts of data in real time and filter through this data to find the right information. Twitter users also often avoid using automatic geotagging of their tweets. While that is often to protect their privacy, it poses challenges to the applications that require location information to make sense of the tweet content.

∗This paper is an extended abstract of the IEEE IS journal publication [Yin et al., 2012].

To overcome these challenges, we investigate several key text and data mining techniques for extracting situation awareness information from Twitter. These techniques cover a series of sub-problems ranging from detecting events from streaming data, classifying and filtering large datasets for relevant information, to discovering geolocations in user posts. Due to unexpected nature of natural disasters, statistical methods that detect a sudden increase in the frequency of counts are often candidate approaches. We adapt burst detection techniques for identifying early indicators of unexpected events. To avoid information overload, we develop classification and online clustering methods for filtering and summarizing disaster-related information from Twitter messages. Geolocating the tweets based on their content helps identify where help is needed or what areas are affected during emergencies. We present our new algorithm that aggregates location clues from tweet and infers a coherent locational focus.

2 Burst Detection

Burst detection focuses on monitoring a feed of Twitter messages, and raising an alert for immediate attention when an unexpected event is detected. In the data mining area, burst detection techniques have been studied to identify emergent patterns from data streams [Fung et al., 2005; Kleinberg, 2003]. To achieve real-time efficiency, we adopt a parameterfree algorithm [Fung et al., 2005] to identify bursty words from Twitter text streams. The basic idea is to determine whether a word is bursty based on its probability distribution in a time window. Specifically, we compute the probability of the number of tweets that contain a word vj in a time window Wi, denoted as P(ni,j), using a binomial distribution:

where N is the number of tweets in a time window. It is worth noting that, although the number of tweets, Ni, in each time window may be different, we can re-scale it in all time windows by adjusting the frequencies of words, such that all Ni become the same and N is thus not considered as a parameter.

In the above distribution, pj is the expected probability of the tweets that contain a word vj in a random time window, and is therefore the average of the observed probability of vj in all time windows containing vj, which is defined as pj = 1L ∑Li=0 Po(ni,j ), where Po(ni,j ) = ni,j N andL is the number of time windows containing vj .

We determine whether a word vj is bursty or not by comparing the actual probability Po(ni,j) that the word vj occurs in the time window Wi against the expected probability pj of the word vj occurring in a random window. If Po(ni,j) is noticeably higher than the expected probability of the word vj(pj), it indicates that vj exhibits an abnormal behavior in Wi, and we thus consider vj as a bursty word in Wi.

In our implementation, a training set of around 30 million tweets captured between June and September 2010 was used. We preprocessed the tweets by removing stopwords and stemming which resulted in a set of about 2.6 million distinct word features, based on which our background alert model was built. In the online phase, we devised an alerting scheme which evaluates a sliding five-minute window of features against the alert model every minute.

For evaluation, we annotated about 8,400 features in a sixmonth Twitter dataset collected in 2010. A burst is defined as one word that suddenly occurs frequently in a time window and its occurrence lasts more than one minute. The performance of burst detection was evaluated using two metrics: detection rate and false alarm rate. Our experiments show that, our burst detection mechanism achieves an overall detection rate of 72.1% and a false alarm rate of 1.4%.

3 Tweet Filtering

When monitoring Twitter for a specific event, a large volume of tweets published every second are considered irrelevant. Even when the tweets are discussing an event of interest, depending on the application one may be interested in prioritizing different classes of messages.

To address this need in the context of disaster management, we study three different tweet classification settings: disaster or not [Karimi et al., 2013], disaster type [Karimi et al., 2013], and impact assessment [Yin et al., 2012]. Disaster or not is a binary classifier that classifies whether or not a tweet is talking about a disastrous event. Disaster type classifier classifies tweets into a representative disaster type: earthquake, flooding, fire, storm, other disasters (e.g., traffic accident and civil disorders), and non-disaster.

Another level of filtering is to identify tweets reporting a damage to infrastructure during a disaster. Infrastructure is defined as roads, bridges, railways, airports, commercial and residential buildings, water, electricity, gas, and sewerage supplies. Identifying tweets that contain such information assists authorities to better plan their response to disasters.

A cross-disaster classification setting is also studied [Karimi et al., 2013] as an extension to disaster type classification. The goal is to investigate if a classifier is trained on specific disasters, such as earthquake, fire, and flooding, how would that perform in identifying other disaster types such as storm. This is important because we may not always have enough training data for all the possible disaster types.

3.1 Methodology

Support Vector Machines (SVM) and Na¨ıve Bayes classifiers are shown the most effective for text classification. We therefore used the two classification algorithms in our experiments. To extract features we examined a number of different feature combinations. For infrastructure classification these features were used: word unigrams, word bigrams, word length, the number of hashtags, the number of user mentions, whether a tweet is retweeted, and whether a tweet is replied to by other users. Disaster or not and disaster type classifiers utilized word unigram, word bigram, hashtag, hashtag count (number of hashtags in a tweet), mention, mention count (number of user mentions in a tweet), link (a binary feature whether or not a link exists in a tweet), and tweet length.

3.2 Evaluation

We evaluated the classifiers using accuracy metric, which indicates the percentage of correctly classified tweets.

For impact assessment classification, 10-fold crossvalidation of a manually annotated dataset of 450 tweets was used. Using all the features, Na¨ıve Bayes and SVM achieve classification accuracy of 86.2% and 87.5%, respectively.

For disaster or not and disaster type classifiers, we used a time-split evaluation scheme [Karimi et al., 2015] that prevents any biases in evaluations that may occur due to the dependencies among Twitter data. In our time-split evaluation, a dataset of 5,747 tweets was sorted in chronological order and divided into two sets of training and testing. Therefore, the training data represents older tweets based on their tweet time. For both of the classifiers, using a combination of hashtags and word unigrams performed better than other feature combinations once at least 50% of the data was used for training. Once trained on 90% of the data, both of the classifiers were accurate over 90% of the time. SVM classifier consistently outperformed Na¨ıve Bayes in all the feature settings and therefore Na¨ıve Bayes was left unreported.

A cross-disaster setting was also evaluated [Karimi et al., 2013]. We evaluated all the possible settings between four types of disasters (earthquake, flooding, fire, and storm) in which three disasters were kept for the training and one for the testing. The results showed that more generic features, such as hashtag count or mention count, were more effective than incident-specific features, such as actual hashtag or mention values, for identifying previously unseen types of disasters. Accuracies for the best setting (unigram plus hashtag count) varied between 60% to 73%.

4 Online Clustering

Online clustering aims to automatically group similar tweets into a set of clusters, such that each cluster corresponds to an event-specific topic. For this task, desirable clustering algorithms should be scalable to handle the massive volume of tweets under the one-pass constraint of streaming scenarios.

4.1 AlgorithmDescription

To meet this need, we propose a new clustering algorithm [Yin, 2013], which intelligently divides the computational process into two phases, i.e., an online discovery phase and an offline cluster merging phase.

Online Discovery Phase The online phase provides a one scan algorithm over the incoming Twitter stream to identify base clusters, with each cluster consisting of a set of similar tweets. To represent textual content of tweets, we employ a traditional vector-space model, in which a tweet mi is represented as a vector of words (v1, v2, . . . , vd), where d is the size of word vocabulary and vj is the TF-IDF weight of j th term in tweet mi. In streaming scenarios, because word vocabulary dynamically changes over time, it is very computationally expensive to recalibrate the inverse document frequency of TF-IDF. We thus use term frequency as the term weight and adopt a sparse matrix representation to deal with dynamically changing vocabulary in our clustering algorithm.

In order to cluster tweets into temporally-related groups, we incorporate temporal information for measuring the similarity between two tweets. The similarity measure used in our clustering algorithm is defined as

We use cosine similarity to measure textual similarity between tweets mi and mj and penalize the similarity if their publication times are far away. |mti -mtj | indicates the difference between tweets' publication times, represented as the number of days, and λ is the number of days of one month, whose value is application dependent.

To maintain sufficient statistics about clusters, for each cluster Ci, we store the textual centroid C v i , which is a feature vector where each element indicates the average weight of the corresponding words for all tweets in cluster Ci, time centroid C t i , which is the mean publication time of all tweets forming cluster Ci, and cluster size |Ci|, which is the number of tweets included in cluster Ci.

Given a Twitter stream in which the tweets are sorted according to their published time, our algorithms works as follows. First, it takes the first tweet from the stream and uses it to form a cluster. Next, for each incoming tweet, say m, it computes its similarity with any existing clusters Ci, that is, sim(m,Ci) = cos(m,Cv i ) · exp(- |mti -Ct i | λ ). Let C ∗ be the cluster having the maximum similarity with m. If sim(m,C∗ ) is greater than a threshold δ, which is to be determined empirically, the tweet m is added to the cluster C ∗ ; otherwise, a new cluster is created. To further improve efficiency, we maintain a list of active clusters. If no more tweets are added to a cluster for a period of time, the cluster is considered inactive and it is removed from the active list. The algorithm only considers those clusters that are in the active list as candidates to which a new tweet can be added.

Offline Cluster Merging Phase The base clusters generated during the online phase serve as an intermediate statistical representation of the Twitter stream. The offline phase is utilized to merge a list of relevant clusters into event-based clusters. There is no need to process the voluminous tweets, but the compactly stored summary statistics of clusters.

For a particular event, since users tend to convey the same or a similar meaning using different words, the online phase would organize the tweets reporting the same event, but expressed using different words, into different clusters. Thus, our algorithm merges together the base clusters that are related with respect to the same event. The principle is to merge a pair of clusters that have a larger inter-cluster similarity, calculated as link(Ci, Cj ) = cos(C v i ,Cv j ) · exp(- |Ct i -Ct j | λ ).

The offline phase provides the flexibility for an analyst to perform queries about clusters and retrieve event-based clusters upon demand at any time horizon. Given a list of clusters generated during the online phase, our algorithm iteratively merges two clusters Ci∗ and Cj ∗ such that link(Ci∗,Cj ∗) is maximized. We use the notion of separation to measure the clustering quality, which is defined as S(k) = 1 N(N-1) ∑i ∑j link(Ci,Cj), where N is the number of clusters obtained at step k. The smaller value this metric has, the better clusters are separated from each other. Based on this metric, we design a criterion to decide whether or not to stop the merging process. At each step k, given two candidate clusters to be merged, we compute a validation index as ∆k = S(k+1)-S(k) S(k) , which represents the relative change in inter-cluster similarity after a merge is made. If ∆k < 0, that means a cluster merge can improve the separation of clusters. We then proceed with merging the two clusters. Otherwise, if ∆k ≥ 0, we stop the cluster merging process. In this way, the optimal number of clusters can be automatically determined.

4.2 Evaluation

The dataset we used for evaluation is an annotated corpus of tweets collected from July 2011 to September 2011 [Petrovi´c et al., 2012]. The corpus was distributed as a set of tweet IDs and their annotations. We re-retrieved the tweets using Twitter search API and obtained a set of 2,633 tweets. Each tweet was annotated as one out of 27 real-world events, such as London riots or Earthquake in Virginia.

We compared our algorithm with two baselines: (1) A standard incremental clustering (IC) algorithm [Becker et al., 2011]. It determines the assignment of a tweet solely based on its similarity to the textual centroids of clusters; (2) ICTime, which is a variant of our proposed algorithm that only uses the online phase to discover clusters. F-measure [Larsen and Aone, 1999] was used as the evaluation metric.

Using bag-of-words and hashtags as features, our proposed algorithm achieved an F-measure of 0.958, in comparison to

0.892 achieved by IC, and 0.905 by IC-Time. By removing the # symbol and treating hashtags as normal words, the clustering accuracies for three algorithms were observed to increase; our proposed algorithm achieved an F-measure of 0.966, while IC and IC-Time achieved an F-measure of 0.899, and 0.910, respectively. We believe this improvement is because removing the # symbol contributes to increasing the term frequency of the same topic word in the tweets, which leads to better clustering performance.

5 Geotagging Locational Focus

Geotagging is the process of finding all mentions of textual references to geographic locations in a text (toponym recognition), and determining where on the map these toponyms collectively refer to (toponym recognition). Because a tweet can contain textual references to more than one locations, we aim to find the locational focus of the tweet that may be geographically identifiable on a map. In our work, we define a location as a combination of both geographic location, such as country, state, city, or suburb, and Point of Interest (POI), such as hotel, shopping center, or restaurant. While the majority of the existing studies focus on estimating the users' locations [Cheng et al., 2010; Li et al., 2011; Mahmud et al., 2012], we are interested in deriving a coherent locational focus that is referred to in a tweet if it exists.

5.1 AlgorithmDescription

To this aim, we propose a novel algorithm [Yin et al., 2014], which identifies all location mentions from tweets and then uses a gazetteer to infer the most probable locational focus.

Finding LocationMentions Identifying location mentions is the first crucial step in inferring the locational focus of a tweet. Because tweets are often very short, tweet text alone cannot provide sufficient evidence for disambiguating location mentions and finding a coherent locational focus. Therefore, we take three sources of information into account: tweet text, hashtags, and user profiles.

We retrained Stanford Named Entity Recognizer on Twitter data to tag location mentions in tweet text, following our prior work [Lingad et al., 2013]. Because hashtags may contain locational clues (e.g., #sydneyfire, #ukfloods), we adopt a hashtag segmentation algorithm which uses a greedy maximal matching method that refers to a word list to break hashtags. The word list is composed of an English dictionary augmented with major states and cities in Australia and New Zealand, as well as their short abbreviations. We also use location information that the users register in their user profiles, especially when specific location information is missing in the tweet content. However, we weight user profile locations less than location mentions found in tweet text and hashtags.

Inferring Locational Focus After location mentions are identified, the next step is to infer a locational focus being referred to by a tweet. Because not all the location mentions equally contribute to the focus, we use a gazetteer database as an external knowledge source to help disambiguate the location mentions and infer the locational focus.

Our gazetteer is built based on two freely available data sources, including gazetteer of Australia 2010 and GeoNames New Zealand gazetteer, augmented with the information from OpenStreetMap on roads, streets, highways, and POIs. We organize our gazetteer as a hierarchy of different geographic substructures: (1) Level 1: Country; (2) Level 2: State/Territory/Region; (3) Level 3: City/Suburb/Town/Nonspecific POIs (e.g., mountains or national parks); and (4) Level 4: Specific POIs (e.g., school or airport).

Our algorithm first queries the gazetteer for each location mention identified in a tweet, and builds an inference tree to summarize all the matches against the gazetteer. Each match is a full path from the matched leaf node via its ancestors to the root. For each matched leaf node, we calculate an importance score that balances the granularities of places in the gazetteer and how well their names match the terms of a given query (measured using Jaccard similarity). To capture both explicit and implicit matches, we also calculate an importance score for each intermediate node in the inference tree, by recursively aggregating the scores of its child nodes in a bottom-up manner. Finally, our algorithm performs a topdown traversal over the inference tree to find an optimal path having the maximum score, which is the locational focus of the tweet. It uses an entropy threshold δ to decide at which granularity level the traversal should stop.

5.2 Evaluation

We evaluated the effectiveness of our proposed algorithm using a dataset of 1,441 tweets annotated with their location mentions and locational focus. We used a random validation set of 80 tweets to tune the entropy threshold (δ = 3.4) and the rest of 1,318 tweets for testing. When calculating the base scores, we set the weights as 0.6, 0.3, and 0.1, for tweet text, hashtags, and user profile, respectively.

We tested the accuracy of our algorithm when different information sources are used. Among others, a combination of all the three sources (tweet text, hashtags, and user profiles) significantly outperformed each of the individual sources; 89.9% accuracy was achieved for identifying countries (Level 1), 73.5% for states/regions (Level 2), 51.0% for cities/suburbs (Level 3), and 29.7% for specific POIs (Level 4). Hashtags were found useful in finding countries, states, or cities, as people often use hashtags to indicate the type of an event together with its associated city or country (e.g., #sydneyfire). User profile locations were helpful for identifying country, but had almost no contribution to detecting POIs. Expectedly, finding POIs was most difficult with only about 30% correctly identified when all the three sources were used.

We also compared our proposed algorithm with a service provided by Yahoo! BOSS Geo services 1 , called PlaceFinder. While there was no significant difference at the country level (around 90%), our algorithm remarkably outperformed this service at finer levels of granularities; for example, our algorithm achieved an accuracy of 73.5% and 51.0% for identifying states/regions, and cities/suburbs, respectively, in comparison to 59.1% and 23.5% by PlaceFinder.

1 http://developer.yahoo.com/boss/geo/

6 Conclusion

The growing use of social media during natural disasters and crises provides on-the-ground information reported from the general public. This work focused on analyzing Twitter messages generated during humanitarian crises, and presented key relevant methods for burst detection, tweet filtering and classification, online clustering, and geotagging. Development and evaluation of these methods showed that if the right information is sifted through social media, it can facilitate the right authorities to enhance their awareness of time-critical situations and make better decisions for emergency response.