\chapter{Separating the Wheat from the Chaff: Events Detection in Twitter Data}\label{chap:urban-computing-ed}
{

\begin{quote}
\textit{This Chapter presents a system for the detection and validation of macro and micro-events in cities (e.g. concerts, business meetings, car accidents) through the analysis of geolocalized messages from Twitter. A simple but effective method is proposed for unknown event detection designed to alleviate computational issues in traditional approaches. The method is exploited by a web interface that in addition to visualizing the results of the automatic computation exposes interactive tools to inspect, validate the data and refine the processing pipeline. Researchers can exploit the web application for the rapid creation of macro and micro-events datasets of geolocalized messages currently unavailable and needed to perform accurate supervised events classification on Twitter. The system has been evaluated in terms of precision.
\footnote{This Chapter has been previously published as \dquote{Separating the Wheat from the Chaff: Events Detection in Twitter Data} in \textit{Proceedings of the Content-based Multimedia Indexing International Workshop (CBMI 2017)}~\cite{ferracani2017separating}.}
}
\end{quote}


\section{Introduction}
Social networking sites such as Twitter have become platforms where people communicate and share knowledge on a daily basis through text messages, photos, videos. This huge amount of social data produced by participatory and crowd-generated sensing represent an opportunity to extract knowledge and give valuable insights on urban dynamics. The flow of information from Twitter is realtime, covers diverse topics and can describe actual events. These events can even be quite small such as parties, companies' presentations, road accidents and so on. Well-established networking mechanisms can improve the information gain through the analysis of this flow's dynamics. Number of messages in time, social reactions such as \emph{likes}, \emph{retweets} and direct replies, geolocation along with multimedia features can be processed in order to detect the occurrences of events using statistical models. 
In November, 2016 Twitter counted 317 active millions users. Roughly 80\% of these users access the platform through a mobile device and about 2\% of them choose to share their GPS location. This is a small percentage but nevertheless it is a large number of people who produce significant contextual information, especially in densely populated urban areas. \\
In this Chapter a method for unknown event detection is proposed which relies on this geolocated data. The method uses a lightweight statistical approach and can alleviate common issues on this subject related to computational cost and systems scalability. Most of the works in the literature exploit content-based unsupervised approaches for event detection with a considerable computational complexity (see Sec.\ref{sec:related-work}). The huge amount of text streams to be processed in realtime, the sparsity of geolocalized data and the noisy nature of Twitter messages are some of the main obstacles researchers have to cope with. These issues make often unfeasible an implementation in a real system. \\

In this Chapter we describe a method based on geographic spatial grids and implemented in a processing pipeline, explained in Sec.~\ref{sec:detection}, which combines several algorithms for statistical analysis without exploiting mining techniques highly computationally intensive. The approach focuses on the analysis of  temporal and spatial characteristics of tweets distributions in order to detect abnormalities and accumulations. The method can be effective for macro and micro-events detection as it accounts for the historical time series in terms of volumes and density of data. Supervised approaches can of course perform better but they may require an hard and time consuming work for tweets discovery and labeling not feasible for unspecified events. In order to support supervise classification, our method has been implemented in a web interface which provides researchers with tools to validate and categorize events automatically discovered by the system and to store them in datasets of geolocated tweets. To the best of our knowledge, there are no datasets of Twitter macro and micro-events available to researchers which contain exclusively geolocated data and cover diverse topics. Sec.~\ref{sec:evaluation} reports the result of an evaluation of our system in building a dataset of events with geolocated messages published in London and New York. 

\section{Related Work}\label{sec:related-work}
Previous studies have addressed the problem of detecting events in social data and specifically on Twitter through the identification of abnormalities in its temporal flow. Exploited features are mainly frequency and density of terms, hashtags, named entities, reactions, emoticons. All these works use a variety of techniques ranging from K-means clustering, SVM, gradient boosted decision trees to generative language models and temporal query expansion~\cite{becker, sakaki, popescu, massoudi, metzler}. 

Wang et al.~\cite{wang} improve clustering quality enriching Twitter messages with term expansion on~\emph{Wordnet}. Generative models and statistical clustering on textual data from Twitter has been used more recently in~\cite{walther} and~\cite{lau}. Nguyen et al.~\cite{nguyen} consider keyword occurrences (Occurence-Score) over time, number of participants involved (Diffusion-Degree) and speed of information spread (Diffusion-Sensitivity) to calculate the probability that an event occurred on the basis of term score distribution. Hierarchical clustering of terms and~\emph{Wordnet} expansion have been used in~\cite{unankard} for emerging event detection. The authors observe changes in events' popularity defined as number of messages in events clusters. Irregularities in the rate of messages are exploited in~\cite{ranneries} and in~\cite{zhou} where also location and topical clustering is performed. As regard to applications, closest to our work is the~\emph{CityBeat}~\cite{xia} system which detects abnormal signals combining time series and classification methods based on spatial, meta, textual and historical features. 
 The main issue with existing approaches on event detection from tweets is mainly the computational cost of extracting and elaborating a lot of features. Twitter messages are composed by very small sentences filled with mispelled words, hashtags, symbols, urls that need to be cleaned and normalized. This noisy realtime data is huge and not easily manageable from a computational point of view. Studies such as~\cite{wang, walther, lau, nguyen} aim to function in real-time on all this data but their performance is poor in terms of processing time and system scalability. Furthermore performances are evaluated only on small~\emph{corpora} or not evaluated at all.\\
For addressing these challenges, we propose a processing pipeline designed keeping in mind that an event occurs in time and space. From our perspective, in order to reduce processing time and implement algorithms in a usable tool it is feasible to reverse common approaches and to take into account exclusively geolocated data. This may be regarded as a limit but we think it is definitely a~\emph{plus} for the main objective of our system which is the implementation of a method for the detection of geolocalized macro and micro-events exploited by a tool for events datasets creation. In fact, this choice 1) decreases false positives; 2) filters the information reducing the amount of data to be processed; 3) allows the rapid creation of datasets of events through our tool, that otherwise would require a considerable amount of work for searching and inspecting the Twitter knowledge-base.\\
Our pipeline combines some algorithms and techniques, explained in Sec.~\ref{sec:detection} and is implemented in a web system. The system provides an exploratory interface which allows to refine and improve the detection adjusting the spatial and temporal parameters exploited by the algorithms, allowing a fine-grained analysis which works on subsets of data. The main outcome of this work is the design and implementation of a lightweight and configurable system for ~\emph{1)}~the semi-automatic detection of macro and micro-events of urban geo-data extracted from Twitter (see Sec.~\ref{sec:detection}) and~\emph{2)}~the easily creation and management of datasets of micro-events, currently unavailable for research studies on Twitter data\footnote{video available at~\url{https://vimeo.com/miccunifi/twitter-events-detection}}.


\section{Detection and Mining}~\label{sec:detection}

The proposed processing pipeline used in our system contemplates three main steps:~\emph{a)} tweets extraction;~\emph{b)} abnormalities detection;~\emph{c)} mining and visualization.


\paragraph{Tweets extraction} tweets are extracted daily through the Twitter API using the Java library twitter4j~\footnote{\url{http://twitter4j.org/en}} and stored in a mySQL database for post-processing.
\paragraph{Abnormalities detection} we use a grid-based method to analyze all the geo-referenced data in a certain urban area. The area is divided arbitrarily in cells of predefined dimensions. Tweets in each cell of the grid are analyzed with our method which combines temporal and spatial density analysis.
The idea of the method is to firstly divide tweets spatially into a grid, then to use time series analysis (exploiting DTW and Crest Detection) to detect anomalies in the volume of tweets of the cell, and finally exploit spatial clustering to infer a possible event from anomalies. For each cell $c$, we create a time series $V$ containing the number of unique users per hour who have published at least a geolocated tweet in the cell $c$. We define a time interval $T$ (e.g.  24 hours), and we divide the initial time series $V$ in windows of size $T$ obtaining a set of time series $V_i$, with $i \in {[0,N_{windows}]}$. We then compute the average time series $\overline{V}$. On this basis we perform our method for abnormalities and event detection which consists in a pipeline of three core algorithms described below:


\begin{enumerate} [wide, labelwidth=!, labelindent=0pt]
	\item \textbf{DTW} Dynamic Time Warping is an algorithm which allows to measure the similarity and the distance between two time-series. DTW is widely adopted in information retrieval to cope with deformations of time-dependent data~\cite{senin}. For each time window $i$, we compute the DTW distance between the time series $V_i$ and the average time series $\overline{V}$, obtaining a measure of distance $d_i$. To detect windows of time where the distribution of tweets is unusual, we consider the average of the distance $\overline{d}$ and the standard deviation $\sigma_d$. All the time series for which $d_i > \overline{d} + \sigma_d$ or $d_i < \overline{d} + \sigma_d$ are considered as abnormalities and sent to the step 2 (Crest Detection).
         \item \textbf{Crest-detection} is an algorithm which uses peaks windowing in order to detect anomalies in data distribution. We consider the time series marked as abnormal in step 1. For each time-step $t$, $t \in [0,T]$, we compare the values of unique tweetters in that hour $v(t)$ with the values of the time series in a temporal interval of size $\Gamma_t$ that precedes and follows $t$. A peak is detected at time $t$ if $v(t) > \sum_{j=1,..,\Gamma_t}v(t - j) +  \epsilon$ and $ v(t) > \sum_{j=1,..,\Gamma_t}v(t + j) + \epsilon.$ Values of $\Gamma_t$ and $\epsilon$ are set to $2$ as default (customizable through the interface, see Sec.~\ref{sec:interface})   \item \textbf{DBSCAN} Density-based spatial clustering of Applications with Noise~\cite{ester} is a data clustering algorithm that given a set of point in the space groups together the points that are closer in the distribution. The algorithm divides the points (i.e. tweets with~\emph{lat, lng}) in `core points', `border points' and `noise points'. A point $p$ is a `core point' if at least a minimum number $minPts$ of points are comprised in a distance $\epsilon$ and are directly reachable from $p$. Mutually density-connected `core points' form a cluster. A point $q$ is a`border point' part of the cluster if a path exists between $p$ and $q$ so that all the `core points' in the cluster are density-reachable from any point of the cluster itself. All the other not reachable points are considered `noise points'. An event is proposed by the system if at least one cluster is detected by DBSCAN for the tweets posted during the temporal interval of the peaks detected in step 2. As default the system sets $\epsilon=5$ meters and $minPts=3$ (customizable using the interface).
\end{enumerate}

\paragraph{Mining and visualization} Once the event clusters has been identified by the DBSCAN algorithm, the event is visualized on the web interface and positioned in its center of mass with respect to the geolocalization of each tweet (see Sec.~\ref{sec:interface}). Text mining is performed on the tweets that are part of the cluster in order to show content features of the detected event. We extract:~\emph{I)} most frequent words;~\emph{II)} hashtags;~\emph{III)} named entities (i.e. timestamps, names of persons and organizations, places);~\emph{IV)} attached photos and videos;~\emph{V)} part-of-speech tagging. Visualization of metadata and related multimedia material is essential in order to help users in verifying the correctness of the event detection and to build categorized datasets.


% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
% Note that IEEEtran v1.7 and later has special internal code that
% is designed to preserve the operation of \label within \caption
% even when the captionsoff option is in effect. However, because
% of issues like this, it may be the safest practice to put all your
% \label just after \caption rather than within \caption{}.
%
% Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
% option should be used if it is desired that the figures are to be
% displayed while in draft mode.
%
%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{myfigure}
% where an .eps filename suffix will be assumed under latex, 
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
%\caption{Simulation results for the network.}
%\label{fig_sim}
%\end{figure}

% Note that the IEEE typically puts floats only at the top, even when this
% results in a large percentage of a column being occupied by floats.


% An example of a double column floating figure using two subfigures.
% (The subfig.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfloat command,
% and the \label for the overall figure must come after \caption.
% \hfil is used as a separator to get equal spacing.
% Watch out that the combined width of all the subfigures on a 
% line do not exceed the text width or a line break will occur.
%
%\begin{figure*}[!t]
%\centering
%\subfloat[Case I]{\includegraphics[width=2.5in]{box}%
%\label{fig_first_case}}
%\hfil
%\subfloat[Case II]{\includegraphics[width=2.5in]{box}%
%\label{fig_second_case}}
%\caption{Simulation results for the network.}
%\label{fig_sim}
%\end{figure*}
%
% Note that often IEEE papers with subfigures do not employ subfigure
% captions (using the optional argument to \subfloat[]), but instead will
% reference/describe all of them (a), (b), etc., within the main caption.
% Be aware that for subfig.sty to generate the (a), (b), etc., subfigure
% labels, the optional argument to \subfloat must be present. If a
% subcaption is not desired, just leave its contents blank,
% e.g., \subfloat[].


% An example of a floating table. Note that, for IEEE style tables, the
% \caption command should come BEFORE the table and, given that table
% captions serve much like titles, are usually capitalized except for words
% such as a, an, and, as, at, but, by, for, in, nor, of, on, or, the, to
% and up, which are usually not capitalized unless they are the first or
% last word of the caption. Table text will default to \footnotesize as
% the IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}[!t]
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
% if using array.sty, it might be a good idea to tweak the value of
% \extrarowheight as needed to properly center the text within the cells
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}


% Note that the IEEE does not put floats in the very first column
% - or typically anywhere on the first page for that matter. Also,
% in-text middle ("here") positioning is typically not used, but it
% is allowed and encouraged for Computer Society conferences (but
% not Computer Society journals). Most IEEE journals/conferences use
% top floats exclusively. 
% Note that, LaTeX2e, unlike IEEE journals/conferences, places
% footnotes above bottom floats. This can be corrected via the
% \fnbelowfloat command of the stfloats package.

% SELECT * FROM `event_detected` WHERE `date` BETWEEN '2016-03-31 00:00:00' AND '2016-04-09 23:59:59'

\section{The Web Interface}~\label{sec:interface}
The Web Interface has been developed in Java and deployed as a servlet in a Tomcat container~\footnote{\url{http://tomcat.apache.org/}}. The interface has been designed with the main goal to visualize on a map the results of the automatic event detection pipeline described in Sec.~\ref{sec:detection}. Furthermore, the web system exposes semi-automatic tools which may help researchers to tune the exploited algorithms in order to improve the event detection. Not least, the system allows the creation of datasets of events from Twitter.

The interface provides two main views (see Fig.~\ref{fig:visualization-map}), both map-based~\footnote{Interactive maps are provided using~\url{http://leafletjs.com/}}, with two different access levels:~\emph{1)} the visualization view shows on the map the events automatically detected by the system;~\emph{2)} the validation view allows an authorized user to confirm (or not) the correctness of the detection and to customize the search.

In the visualization view each event is represented by a marker that can have three color: blue, red and green. Blue pins are the events detected by the algorithm but still not validated by a human; red and green pins instead are events respectively misclassified or correctly classified as confirmed by a user. The user can search and zoom the map and define a temporal range for the visualization of events detected by the algorithm with the defaults parameters. Each marker can be activated in order to open an info-box window which shows the data and metadata associated with the event: the hour, the category and all the extracted features (tweets, word occurrences, related multimedia, named entities, POS tagging). Authorized users can access the editing and validation view. The view shows a transparent grid super-imposed on the geographic area of interest.
%(in our demo New York and London). 
\begin{figure}[!htb]
\centering
\includegraphics[width=1\columnwidth]{figs/interface-twitter.jpg}
\caption{The two main views of the system: 1. Visualization. 2. Editing and Validation}
\label{fig:visualization-map}
\end{figure}
The dimensions of the cells of the grid are predefined and the grid is positioned arbitrarily to cover all the geolocalized tweets published in a configurable radius. The user can select a cell, as shown in Fig.~\ref{fig:visualization-map}, in order to show an info-box where all the events detected in that area can be inspected. In this modal interface the user is also provided with advanced graphical widgets through which he can adjust the several parameters used by the algorithms. Hence, the computation can be started again asynchronously in order to discover events previously not detected by the algorithm with the default parameters. Configurable parameters are:~\emph{1)} the position and the dimensions of the grid cell (Fig~\ref{fig:graphic-tools}.1); ~\emph{2)} the time interval of the event detection;~\emph{3)} the time period and/or periodicity over which to calculate the average and the standard deviation of the DTW distances for the cell; ~\emph{4)} the threshold value over the average~\emph{plus} the standard deviation beyond which the system reports an abnormality;~\emph{5)} the time window and the $\epsilon$ used in the crest-detection algorithm (Fig.~\ref{fig:time-series});~\emph{6)} the $minPts$ and the $\epsilon$ used by the DBSCAN algorithm for the identification of clusters of tweets on the peaks detected by the Crest Detection algorithm (Fig.~\ref{fig:graphic-tools}.2). 
The flexibility provided by the system in tuning parameters as well as the configurability of spatial cells dimensions, density and time intervals allow the system to work in realtime on subsets of data with good performance. Furthermore, the choice between periodicity and/or temporal continuity for the computation of historical data can improve the search. In general big events tend to be periodical (e.g. football games are usually played every two weeks) and an abnormality could be detected comparing, for example, the time series of the day to the time series of the last ten days. On the contrary, a micro-event such as a small company meeting can increase the number of tweets in a certain day with respect to a periodicity average (e.g. every Thursday) but not in a continuous time interval.

\begin{figure}[!htb]
\centering
\includegraphics[width=1\columnwidth]{figs/graphic-tools.jpg}
\caption{In 2.1: the draggable and resizable widget to select a specific area on the map. In 2.2: $\epsilon$ and $minPts$ of DBSCAN can be defined dragging the circles' circumference on a distribution of points.}
\label{fig:graphic-tools}

\end{figure}

\begin{figure}[!htb]
\centering
\includegraphics[width=1\columnwidth]{figs/timeseries.jpg}
\caption{Time series of Twitter users who published geolocalized posts in Trafalgar Square, London, on 2016, April 1. The system detected 4 events at 7am, 11am, 2pm and 7 pm. $\epsilon$ and time interval can be changed interactively resizing the gray rectangle on the time series plot.}
\label{fig:time-series}
\end{figure}


\section{Evaluation}~\label{sec:evaluation}
To evaluate the detection accuracy of our system we manually validated the events automatically discovered between March 31 and April 9, 2016. The tweets published in the city centers of two big cities in these ten days, London and New York, were analyzed. This time period was chosen since the interval registered the highest number of tweets in the year. In details $17176$ users published $44932$ tweets in London, while $17378$ users published $43186$ tweets in New York provided with geolocalization. The system detected a total of $1240$ events, $340$ in London and $900$ in New York using the algorithms with default parameters. The significant difference in the events' count is probably due to the diversity in population density in the two city centers (30000/km\textsuperscript{2} in Manhattan and between 10.000/km\textsuperscript{2} and 15.000/km\textsuperscript{2} in the central districts of London).
The overall error rate of the classification was $0.43$ with $190$ confirmed events in London and $516$ in New York. This is a very good result in terms of precision, not far from state-of-the-art supervised approaches for event detection which range from $0.64$ to $0.85$~\cite{zhou}. Results of a recent method following a more similar approach on geolocated tweets and Instagram photos ~\cite{ranneries} achieved a precision of just $0.20$. The recall of the system has not been computed due to the unavailability of Twitter annotated datasets of macro and micro-events provided with geolocated messages. 



\section{Conclusion}
In this Chapter we have presented a lightweight method for the automatic detection of unknown macro and micro-events exploiting geolocalized data from Twitter. The system uses a combination of algorithms to discover possible events using a pure statistical approach. 
The method is exploited by a web system which helps researchers in building datasets of geolocalized events. Default parameters of the algorithms can be changed on the fly in order to refine the detection and to validate and categorize the events proposed. These data can be useful to other researchers for improving supervised event detection and classification techniques on Twitter messages.


\section{Acknowledgment}
Research partially supported by MIUR Cluster project Social Museum and Smart Tourism.

