Microblogs are an important source of information in emergency management as lots of situational information is shared, both by citizens and official sources. It has been shown that incident-related information can be identified in the huge amount of available information using machine learning. Nevertheless, the currently used classification techniques only assign a single label to a micropost, resulting in a loss of important information that would be valuable for crisis management. With this paper we contribute the first in-depth analysis of multi-label classification of incident-related tweets. We present an approach assigning multiple labels to these messages, providing additional information about the situation at-hand. An evaluation shows that multi-label classification is applicable for detecting multiple labels with an exact match of 84.35%. Thus, it is a valuable means for classifying incident-related tweets. Furthermore, we show that correlation between labels can be taken into account for these kinds of classification tasks.
Social media platforms are widely used by citizens for
sharing information covering personal opinions about
various topics (e.g., politics) as well as information about events
such as incidents. In the latter case, citizens act as observers
and create valuable incident-related information. For
instance, during incidents such as the Oklahoma grass fires
and the Red River floods in April 2009 [
However, the discovery of incident-related information is
a complex task, requiring the separation of valuable
information from daily chatter in the vast amount of information
created on social platforms. This can be realized based on
techniques from data mining and machine learning.
Classification is one method which can be utilized to extract
relevant information from social networks (for tweets, see
[
THIS CAR HIT THE FIRE HYDRANT AND CAUGHT FIRE....SOMEONE HOLIDAY ALTERED
A single label would necessarily lack relevant information. A better approach is the concurrent assignment of all three labels, which is known as multi-label learning. In the example, all labels (”fire”, ”crash”, and ”injuries”) would be assigned concurrently using an appropriate learning algorithm. The example also shows that the assignment of multiple labels is not necessarily an independent process. Once the label for an incident type such as ”crash” is assigned the probability of assigning the label ”injuries” is changing. This dependency is known as label correlation and needs to be investigated in the context of multi-label learning.
With our analysis we want to investigate three important aspects of applying multi-label learning on incident-related tweets: (1) how to apply multi-label learners on tweets, (2) if the classification accuracy of multi-label classification approaches is comparable to the accuracy of multi-class classification approaches, and (3) if correlation between labels is a factor that needs to be taken into account for incidentrelated information. With this paper we contribute the first in-depth analysis of multi-label classification of incidentrelated tweets. In summary, our contributions are twofold: • We show that multi-label classification on incidentrelated tweets is applicable and able to detect the exact combinations of labels in 84.35% of the cases. Thus, we show that compared to common multi-class classification approaches, multi-label classification of incidentrelated tweets is a valuable means. • We evaluate the influence of label correlation on the classification results of incident-related tweets. We show that for classification tasks label correlation needs to be taken into account.
The remainder of the paper is organized as follows. First, we describe and discuss related approaches. Second, the considered multi-label classification algorithms as well as the technical infrastructure (a machine learning pipeline) used for the analysis are presented. Next, we introduce our data collection setup and describe the evaluation of our approach. We close with a conclusion and future work. 2.
Techniques of multi-label classification have been applied
to domains such as text categorization [
A common application for texts is the classification of
news articles [
In contrast, texts such as tweets are mostly unstructured
and noisy, because of their limitations in size and the often
used colloquial language. Related work on such short texts
with a focus on solving multi-class problems exists, e.g., for
sentiment analysis [
Applying multi-label learning on very short texts is a topic
of open research. Only two respective examples are known
to the authors: Sajnani et al. [
Summarized, although many related approaches cope with multi-class classification of short texts such as microblogs, multi-label classification is an open research issue. Especially for the domain of crisis management, no prior research on this topic exists. 3.
In this section, we give an overview on multi-label classification. Multi-label classification refers to the task of learning a function that maps instances xi = (xi,1, . . . , xi,a) ∈ X ⊆ Ra to label subsets or label vectors yi = (yi,1, . . . , yi,n) ∈ {0, 1}n, where L = {λ1, . . . , λn}, n = |L| is a finite set of predefined labels and where each label attribute yi corresponds to the absence (0) or presence (1) of label λi. Thus, in contrast to multi-class classification, alternatives are not assumed to be mutually exclusive, such that multiple labels may be associated with a single instance.
This makes multi-label data particularly interesting from the learning perspective, since, in contrast to binary or multi-class classification, there are label dependencies and interconnections in the data which can be detected and exploited in order to obtain additional useful information or just better classification performance. Some examples for our particular Twitter dataset were already shown up in the introduction. As we show, around 15% of our tweets could be assigned to more than one label, thus, we believe that it is not unusual to encounter tweets with several possible labels, so that in our opinion the view of microblogs as multi-labeled data seems more natural, more realistic, and more general. Nonetheless, previous work focuses on the multi-class labeling of tweets and this is the first work known to the authors which tries to exploit label dependencies on tweets.
In the following, we will describe commonly used
approaches for multi-label classification: Binary Relevance
(BR), Label Powerset (LP), and Classifier Chains (CC).
All described techniques are based on the decomposition
or transformation of the original multi-label problem into
single-label binary problems, as most multi-label techniques
do [
The most common approach for multi-label classification is to use an ensemble of binary classifiers, where each classifier predicts if an instance belongs to one specific class or not. The union of all classes that were predicted is taken xi x1 x2 . . .
Labels ∈ {0, 1}n (y1,1, . . . , y1,n) (y2,1, . . . , y2,n) ... . . . ... as the multi-label output. This approach is comparable to classical one-against-all for a multi-class problem. Formally, we convert a training example pair (xi, yi) into n separate pairs (xi, yi,j ), j = 1 . . . n, one for each of the n base classifiers hj. The predicted labels yˆj for a test instance x are then the result of hj(x) ∈ {0, 1}.
This method is fast and simple, however, it is not able to
take label dependencies into account since each base
classifier is trained independently from the other classifiers. As
was recently stated by Dembczynski et. al [
The basic idea of this algorithm is to transform multilabel problems into a multi-class classification problem by considering each member of the powerset of labels in the training set as a single class. Hence, each training example is converted into (xi, σ(yi)) with σ, σ−1 denoting a bijective function that maps between the label powerset of L and a set of 2n meta-classes. The classifier hLP is trained e.g. with one-against-all (like in our setting), and the prediction for x is obtained with σ−1(hLP (x)).
LP takes label dependencies into account to some extent,
as each distinct occurrence of a label pattern is treated as
a new class. It is hence able to model the joint label
distribution, but not explicitly and directly specific dependencies
(correlations, implications, etc.) between labels. As a
consequence, LP is tailored towards predicting exactly the correct
label combination. As it is pointed out in [
In addition to the obvious computational costs problem due to the exponential grow of meta-labels, the sparsity of some label combinations, especially with an increasing number of labels, often causes that some classes contain only few examples. This effect can also be observed in our data, cf. Table 2. 3.3
As stated before in Section 1, it is very likely in our dataset
that injured people are mentioned when also any incident
type is mentioned (200 of 967 cases). On the other hand, it
seems almost a matter of course that there was an incident
if there is an injured person. Although this only happens
in 200 out of 232 cases in our data we consider it relevant
for larger data sets. The classifier chains approach (CC) of
Read et al. [
The idea of this approach is to construct a chain of n binary classifiers hjCC , for which (in contrast to BR) each binary base classifier hjCC depends on the predictions of the previous classifiers h1CC . . . hjC−C1. Particularly, we extent the feature space of the training instances for the base classifier hjCC to ((xi,1 . . . xi,a, yi,1 . . . yi,j−1), yi,j ). Since the true labels yi are not known during prediction, CC uses the predictions of the preceding base classifiers instead. Hence, the unknown yj are replaced by the predictions yˆj = hjCC (x, yˆ1 . . . yˆj−1).
This shows up one problematic aspect of this approach, namely the order of the classifiers in the chain. Depending on the ordering, CC can only capture one direction of dependency between two labels. More specifically, CC can only capture the dependencies of yi on y1, . . . , yi−1, but there is no possibility to consider dependencies of yi on yi+1, . . . , yn. Recovering our example from the beginning, we can either learn the dependency of the label incident given injury or the other way around, but not both. In addition, the effect of error propagation caused by the chaining structure may also depend on the label permutation. We will evaluate the effect of choosing different orderings for our particular dataset later on in Section 5.3.
Furthermore, CC has advantages compared to LP. CC
is considered to predict the correct label-set, such as LP
[
In the following, the data used for multi-label classification of incident-related tweets is described in detail. The taken approach is composed of three steps. As a first step, unstructured text has to be converted into structured text. As a second step, the structured information needs to be transformed to features that can be used by a multi-label learner. Third, these features are used to train and evaluate a classifier. 4.1
Our overall goal is to apply text mining on short
documents that are present in social media, thus, they need to
be represented by a set of features. As texts in social media
are mostly unstructured, they first need to be converted into
a representation which enables feature generation. Hence, as
a first step, we apply Natural Language Processing. Firstly,
we remove all re-tweets as these are just duplicates of other
tweets and do not provide additional information. Secondly,
@-mentions of Twitter users are removed from the tweet
message as we want to prevent overfitting towards certain
user tokens. Before further processing is applied, the text is
converted to Unicode, as some tweets contain non-Unicode
characters. Third, abbreviations are resolved using a
dictionary of abbreviations based on the data provided by the
Internet Slang Dictionary&Translator2. Then, we identify
and replace URLs with a common token ”URL”. As a next
step, stopwords are removed. This is important as very
frequent words have limited influence when it comes to
classifying tweets due to their relative frequency. Based on the
resulting text, we conduct tokenization. Thus, the text is
divided into discrete words (tokens) based on different
delimiters such as white spaces. Every token is then analyzed
and non-alphanumeric characters are removed or replaced.
Also, lemmatization is applied to normalize all tokens.
Additionally to the common NLP processing steps, we identify
and replace location mentions such as ”Seattle” with a
common token to allow semantic abstraction. For this, we use
the approach presented in [
After finishing the initial preprocessing steps, we
extracted several features from the tweets that are used for
training a classifier. We conducted a comprehensive feature
selection, analyzing the value of each feature for the
overall classification performance. We compared word-n-grams,
char-n-grams, TF-IDF [
We focus on three different incident types throughout the paper in order to differentiate incident-related tweets. Three classes have been chosen, because we identified them as the most common incident types using the Seattle Real Time Fire Calls dataset3, which is a frequently updated source for official incident information. We included also injury as an additional label. This results in four labels consisting of very common and distinct incident types and the injury label: Fire, Shooting, Crash, and Injury.
We collected public tweets in English language using the Twitter Search API, which provides geotagged tweets as well as tweets for which Twitter inferred a geolocation based on the user profile. For the collection, we used a 15km radius around the city centers of Seattle, WA and Memphis, TN. We focused on only two cities, as for our analyses we are interested in the stream of tweets for these cities and a specific time period instead of a scattered sample of the world, which could be retrieved using the Twitter Streaming API. This gave us a set of 7.5M tweets collected from 11/19/12 to 02/07/13. Though we know about the limitations of the Search API, we think that we collected a relevant sample for our experiments.
The dataset was further reduced to be usable for high quality labeling as well as the machine learning experiment. We first identified and extracted tweets mentioning incidentrelated keywords. Compared to other approaches that completely rely on filtering using hashtags, we take the whole message into account for identifying incident-related keywords. We retrieved a set of different incident types using the ”Seattle Real Time Fire 911 Calls” dataset and defined one general keyword set with keywords that are used in all types of incidents like ’incident’, ’injury’, ’police’, etc. For each incident type, we further identified specific keywords. For instance, for the incident type ’Motor Vehicle Accident Freeway’ we use the keywords ’vehicle’, ’accident’, and ’road’. Based on these words, we use WordNet4 to extend this set by adding the direct hyponyms. For instance, the keyword ’accident’ was extended with ’collision’, ’crash’, ’wreck’, ’injury’, ’fatal accident’, and ’casualty’. Based on these incident-related keywords, we filtered the datasets. Furthermore, we removed all re-tweets, as the originated tweets are also contained in our datasets and only these are needed for our experiments. Based on this filtered dataset, we randomly selected 20.000 tweets.
The selected tweets have been labeled manually by one researcher of our department. Out of these tweets, we randomly selected 2.000 tweets for further re-labeling for our multi-label classification problem. Those tweets were manually examined by five researchers using an online survey. To assign the final coding, we differentiated between two types of agreement: 3http://data.seattle.gov 4http://wordnet.princeton.edu Real-World Incident
Type • if less than four coders agree on one label, all labels which at least two coders assumed as correct are assigned as possible labels and further verified in a group discussion
The final labeled dataset consists of 10 different label combinations. The distribution for every combination is outlined in Table 2. The distribution indicates that around 15% (232) of all tweets in our dataset have been labeled with multiple labels. Another observation is that almost exactly 50% of the tweets do not have any label assigned, which is rather unusual compared to typically used and analyzed multi-label datasets5. In addition, the label cardinality, i.e., the average number of labels assigned to an instance, is around 0.59, whereas common datasets have at least more than 1 assigned. On the other hand, this is mainly due to the low number of total labels, since the label density (the average percentage of labels which are true) is 15%, which is a relatively high value. From a multi-label learning perspective, this is an interesting property of this dataset since it is not clear how commonly used techniques will behave under this circumstance. For example, many algorithms ignore instances without any label given. 5We refer to the repository at http://mulan.sourceforge. net/datasets.html for an overview of the statistics of the commonly used benchmark datasets in multi-label classification 5.
In the following section, we provide the evaluation results for the presented multi-label classification approaches on our dataset. We also present the result for a keyword-based approach as a simple way for conducting multi-label classification. 5.1
We performed our experiments with Mulan, an
opensource library for multi-label classification based on Weka
[
The evaluation of multi-label problems requires different measures compared to those used for multi-class problems. In our paper, we use the following metrics:
Exact Match: Exact match is the percentage of the m test instances for which the labelsets were exactly correctly classified (with [[z]] as indicator function returning 1 if z is true, otherwise 0) m ExactM atch(h) = 1 X [[yi = h(xi)]] m i=1 (1)
Hamming Loss: The instance-wise Hamming loss [
Recall, Precision and F1: We use micro-averaged
precision and recall measures to evaluate our results, i.e.,
we compute a two-class confusion matrix for each label
(yi = 1 vs. yi = 0) and eventually aggregate the results
by (component-wise) summing up all n matrices into one
global confusion matrix (cf. [
As mentioned before, we use a keyword-based pre-filtering for selecting an initial set of tweets that is suitable for labeling. A first and simple approach for detecting incident related tweets is to use these keywords for classification.
In Table 1, the real-world incident types from the Seattle Real Time Fire Calls dataset and the corresponding number of extracted keywords is shown. For the injury class, no specific type in the Seattle dataset could be found, thus, we extended the set with a manually created list of keywords and their direct hyponyms.
The results for classifying each individual class are shown in Table 3. The results indicate that precision as well as recall are rather low. Only for the fire class a high recall could be achieved.
Furthermore, if the keywords would be used for applying multi-label classification, a precision of 32.22% and a recall of 64.90% is achieved, which is a rather bad result. Also exact match (28.45%) and h-loss (27.08%) are bad, thus, we conclude that with simple keyword-based filtering, multilabel classification cannot be done accurately. 5.3
As a first step, we coped with the question if correlation between labels is taken into account and beneficial for the classification results. Thus, we evaluated all different label sequences using the classifier chains algorithm for our labels Fire (F), Shooting (S), Crash (C), and Injury (I). The values for exact match for each sequence are shown in Figure 2 (using SVM as our base learner).
The results indicate that the label sequence has indeed an influence on the classification performance. In our case, we get a difference of 1% between the best sequence Shooting, Crash, Fire, Injury and the worst Injury, Crash, Fire, Shooting. Also, we see that the Injury label is best used after incident labels have been classified - for the best cases even as one of the last labels in the sequence. It is also remarkable that classifying Shooting as first label followed up by either Crash or Fire is always a good option. This can be explained on the one hand by the generally good individual prediction performance for Shooting (cf., Table 5), hence leading to low error propagation, and on the other hand by the resulting label dependencies given the Shooting label is known: for instance, we can see from Table 2 that we can safely exclude Crash or Fire if there was a Shooting. This shows that our initial assumption that correlation between labels needs to be taken into account is true.
Based on the respective best (MAX) and the worst sequence (MIN), we compared CC to the multi-label approaches with the two different base learners. In Table 4 these evaluation results are shown. The first observation is that Naive Bayes is not adequate for classifying tweets, since though it achieves the best recall values using CC, this is in exchange of very low results on the remaining metrics and approaches. We will therefore focus on the results obtained by applying LibLinear as base learner. The results show that, if there is the opportunity of pre-optimizing the ordering of the labels, e.g., by performing a cross-validation on the training data, then classifier chains is able to slightly outperform the other approaches, which is most likely because the label correlation is valuable. This is also reflected in the good performance with respect to exact match, where the worst CC even outperforms LP, which is particularly tailored towards matching the exact label combination. Note also that LP is a common approach used for circumventing the need for a multi-label classification by creating metaclasses, as already mentioned in the introduction. However, this approach is always inferior to the compared approaches, which demonstrates the need for more advanced techniques in this particular use case.
We can also observe that improving the prediction of the exact label combinations may come at the expense of reducing the performance on label-wise measures, since the additional features used by CC generally lead to a higher potential deterioration (MIN) than potential improvement (MAX) for Hamming loss, recall, precision and F1, whereas for exact match this is not as clear.
As a last evaluation step, we evaluated the accuracy of each approach for every individual label. This is important as we want to understand how well a classifier performs for each label. The following Table 5 depicts the accuracy of individual labels using SVM with the best label order.
The results show that the precision for individual labels is high with about 90% to 95% for each label, which is much better compared to the keyword-based classification. The differences between all approaches are nearly the same, thus, all approaches seem to be appropriate for classifying the individual labels. However, the recall drops significantly, depending on the label type. For instance, injuries often remain undetected. In this case, classifier chains show the best results for precision and recall. Note that the results for BR and CC on Shooting are the same, since the first classifier in the CC ordering is exactly trained like the corresponding BR classifier (cf. also Figure 1). This also shows that along the chain, CC slightly reduces the good precision of BR in exchange of improved recall. 5.4
Though the results show the advantage of multi-label classification, we want to understand the limitations of our approach. Thus, we first created a confusion matrix for the classifier chains approach with the best label order. The matrix shows that most misclassifications occur due to an assignment of instances to the ”no incident” label combination {}. The other wrong classifications are mostly a result of not detecting the injury label or of predicting it wrongly.
The examples show that certain words such as ”fire” or digits in the message might lead to wrong classifications. This could be avoided by adding additional features or with a larger training set.
In this section we have first shown that a simple keywordbased classification approach is not suitable for multi-label classification. Second, we presented results of state-ofthe-art multi-label classification approaches and we showed that these perform quite well for classifying incident-related tweets. Compared to current approaches for the classification of microblogs, which rely on assigning only one label to an instance, the results show that it is possible to infer important situational information with only one classification step. The results also indicate that the label sequence has an influence on the classification performance, thus, this factor should be taken into account for following approaches. 6.
In this paper we have shown how to apply multi-label learning on social media data for classification of incidentrelated tweets. Furthermore, we analyzed that we are able to identify multiple labels with an exact match of 84.35%. This is an important finding, as multiple labels assigned with one classification approach provide important information about the situation at-hand, which could not be easily derived from previously used multi-class classification approaches. Furthermore, we have shown that the natural relation of labels, which represents for instance the relation between incidents and injuries in the real-world, can be used and exploited by classification approaches in order to obtain better results.
For future work, we aim to add costs to our classifications. For instance, not detecting incident labels should be heavily punished compared to misclassifying the incident type. Furthermore, we aim to improve the overall performance of our approach by taking different features and a larger training set into account.
This work has been partly funded by the German Federal Ministry for Education and Research (BMBF, 01|S12054). #Microposts2014 4th Workshop on Making Sense of Microposts