% by Mirella M. Moro; version: January/18/2012 @ 04:16pm
% -- 01/18/2012: more discussion on SBBD + JIDM; overall revision
% -- 09/03/2010: bib file with names for proceedings and journals; cls with shrinked {received}
% -- 08/27/2010: appendix, table example, more explanation within comments, editors' data

\documentclass[jidm,a4paper]{jidm}
\usepackage{listings}
\usepackage{tikz}
\usepackage{tkz-euclide}
\usetikzlibrary{plotmarks}
\usetikzlibrary{arrows,shapes,fit}
\usetkzobj{all}
\usepackage{pgfplots}
\usepackage{algorithm}
\usepackage{amsmath}
\usepackage{algpseudocode}
\usepackage{subfigure}
\usepackage{pbox}
\usepackage{commath}
\usepackage{soul}
\usepackage{caption}
\usepackage{multirow}
\input{images/tikz_functions}

\algnewcommand\algorithmicforeach{\textbf{for each}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}

\usepackage{graphicx,url}  
\usepackage[T1]{fontenc}   % avoids warnings such as "LaTeX Font Warning: Font shape 'OMS/cmtt/m/n' undefined"

%\usepackage{cite} % NOTE: do **not** include this package because it conflicts with jidm.bst

% Standard definitions
\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newdef{definition}[theorem]{Definition}
\newdef{remark}[theorem]{Remark}

% New environment definition
\newenvironment{latexcode}
{\ttfamily\vspace{0.1in}\setlength{\parindent}{18pt}}
{\vspace{0.1in}}

% ALL FIELDS UNTIL BEGIN{document} ARE MANDATORY

% The following data (volume, number and page) are given by the editors prior to publishing your article
\jidmVolume{8}
\jidmNumber{1}
\jidmYear{17}
\jidmMonth{April}
\setcounter{page}{1}

% Includes headers with simplified name of the authors and article title
\markboth{Marco A. Beber et. al.}
{Individual and Group Activity Recognition in Moving Object Trajectories}
%  -> \markboth{}{}
%         takes 2 arguments
%         ex: \markboth{M. M. Moro}{Any article title}


% Title of the article
\title{Individual and Group Activity Recognition in \\ Moving Object Trajectories}

% List of authors
%IF THERE ARE TWO or more institutions, please use:
%\author{Name of Author1\inst{1}, Name of Author2\inst{2}, Name of Author3\inst{2}}
\author{Marco Aurelio Beber\inst{1}, Carlos Andres Ferrero\inst{2}, Renato Fileto \inst{1}, Vania Bogorny \inst{1}}

%Affiliation and email
\institute{Programa de P\'{o}s-Gradua\c{c}\H{a}o em Ci\^{e}ncia da Computa\c{c}\H{a}o\\
Universidade Federal de Santa Catarina, Brazil \\ \email{marco.beber@posgrad.ufsc.br,\{r.fileto, vania.bogorny\}@ufsc.br}
\and Instituto Federal de Santa Catarina, Brazil \\
\email{andres.ferrero@ifsc.edu.br}
}

% Article abstract - it should be from 100 to 300 words
\begin{abstract}
The knowledge about which activities people do at certain places is useful for several application domains. Existing works for activity recognition from trajectory data assume that only one activity is performed at each place, and do not identify the objects involved in each activity. We claim that several activities may be performed at certain places, such as shopping centers, universities, and others. In this paper, we propose a new method to recognize multiple activities performed at a place by integrating GPS trajectories and social media data, labeling trajectories with activities and the individuals involved in each activity. Experiments show that the proposed solution achieved good results in labeling and recognizing both individual and group activities.
\end{abstract}

% ACM Computing Classification System categories
\category{H.2.8}{Database Management}{Database Applications}[Data Mining \and Spatial Databases and GIS ]
% Categories and Descriptors are available at the 1998 ACM Computing Classification System
% http://www.acm.org/about/class/1998/
%  -> \category{}{}{}
%         takes 3 arguments for the Computing Reviews Classification Scheme.
%         ex: \category{D.3.3}{Programming Languages}{Language Constructs and Features}
%                   [data types and structures]
%                   the last argument, in square brackets, is optional.

% Article keywords
\keywords{Activity Inference from Twitter Data, Activity Trajectory, Group Activity Inference, Semantic Trajectories, Social Networks, Trajectory Activity Recognition}
%  -> \keywords{} (in alphabetical order \keywords{document processing, sequences,
%                      string searching, subsequences, substrings})

\pgfplotsset{compat=1.14}
% THE ARTICLE BEGINS
\begin{document}

% This is optional:
\begin{bottomstuff}
This work was supported by the Brazilian agencies CAPES and CNPQ.
\end{bottomstuff}

\maketitle

\section{Introduction}

We are living the era of big data, where individuals are constantly leaving traces of their movements and their activities. Even though we are not fully aware of it, we are being tracked everyday. Our spatiotemporal traces can be delineated as \emph{moving object trajectories}. A  raw trajectory is a temporally ordered sequence of spatial positions, which do not present explicit semantics.

A raw trajectory can be split in stops and moves, where stops are the most important parts of a trajectory, and that can be enriched with more semantic information, such as the name of the place visited by the object \cite{Spaccapietra2008126}. \citeN{bogorny2014constant} proposes the Constant model, with the most important aspects for semantically describing trajectory segments, such as transportation means, environmental conditions, activities, and goals associated with these segments. \citeN{FiletoMRPKT15} proposes the Baquara ontological framework for semantically enriching trajectories with linked open data. Although the previous works propose a model to represent important aspects related to trajectories, they do not present a solution for individual and group activity inference.

Several recent works address semantic trajectory data analysis for different purposes such as estimating the attractiveness of places~\cite{furtado2013assessing}, semantic outlier discovery~\cite{de2013towards}, user profile inference~\cite{alencar2015}, etc. However, only a few works have focused on activity recognition, and even less on group activity inference. While it might be easy to discover visited places in many situations, determining the activities performed at these places and who are the individuals involved in these activities is not a trivial task. There is no unique association between each visited place, called \emph{Point of Interest} (POI or POI type) and the activities that can be performed at this POI. Several activities may be performed at a single POI, and there is a wide range of possibilities that vary in number and nature. For instance, at a shopping mall one could be eating, purchasing, working, socializing or even watching a movie. 

Although there are a few activities that could be a priori labeled as individual or group activities, such as socializing, that is normally performed in groups, most activities can be either performed alone or in group, such as studying, working, walking, etc. There is no unique way to infer human activities from movement data, and it is very challenging, since a group of individuals who do not know each other can still by chance be performing the same activity at the same place.

Some works in the literature are related to human activity recognition using different types of data. For instance, \citeN{Liu6406574}, \citeN{weerkamp2012activity}, and \citeN{Zhu2016103} perform activity recognition in textual data extracted from social media, such as tweets and tips from Foursquare, but not GPS trajectory data, which is the focus of this article. The few works on GPS trajectory data that recognize activities, such as \cite{Furletti:2013:IHA:2505821.2505830} and \cite{Njoo7344875} ignore an important aspect, that more than one activity can be performed at each POI. Their main limitation is the assignment of only one activity at a POI. In addition, they rely on specialists to manually label POIs (or POI types) with activities that can happen at these POIs (or POI types). Another limitation is the dependence of an annotated trajectory dataset to generate a classification model. Furthermore, the few works on GPS trajectory data that recognize group activities, such as \cite{hirano2013hybrid,gordon2014group,bourbia2016temporal} also have a limitation, they consider that the group performing the activity is already known, or that the group is defined by a buddy-list containing all individuals.

In this paper we propose a method to integrate GPS trajectories with social media data and census data in order to enrich semantic trajectories represented as stops with activities. We extend our previous work~\cite{beber2016} to recognize multiple activities that can be performed at certain POIs, and propose a method to discover if these activities are performed in groups. The input of the method is a set of semantic trajectories represented as stops and the output is this set annotated with activities and all individuals participating in each activity.

In summary, we make the following contributions: (i) we present an algorithm to associate multiple activities to trajectory data; and (ii)  propose the algorithm G-Activity to infer activities performed by groups of individuals, based on trajectory encounters and relationships.

The rest of this paper is organized as follows. Section 2 discusses related work. Section 3 presents the basic definitions. Section 4 describes our proposal for individual and group activity recognition. Section 5 presents the experimental evaluation, and finally, Section 6 presents the conclusions.

\section{Related Work}

There are different works in the literature related to human activity recognition using different types of data, such as social media and GPS trajectories. The works based on social media focus on text classification, and extract features from text and POIs to build classifiers for activity recognition. For instance, \citeN{Liu6406574} builds a classifier over tweets in order to predict the POI type of tweets linked to Foursquare. Although this work does not recognize activities, it recognizes POI types that can be related to different activities. \citeN{weerkamp2012activity} proposed an approach to predict the popular activities that will happen in a future time window, such as tonight, tomorrow, and next week, by using a future time-window and keywords related to activities. \citeN{Zhu2016103} builds a multi-label classifier using tweets manually annotated with activities in order to predict up to three activities. To build the classifier, it considers the tweet text, the tweet posting time, the POI type from Foursquare and POI name from Foursquare.

On the other hand, only a few works try to recognize activities on GPS trajectories. \citeN{moreno2010looking} proposed an algorithm that given a set of stops, uses a predefined set of rules that considers the minimum time and maximum speed to infer the goal of the movement. However, the set of rules has to be defined by a specialist, and the matching process is based on movement aspects of the goal, such as its minimum time and its maximum speed. Therefore, it ignores important aspects such as the place and the time of the goal. This paper, instead, focuses on recognizing activities, and we do not depend on a specialist, since we extract the knowledge from Twitter in order to build a knowledge base that describes the activities that can be performed at a POI. \citeN{Furletti:2013:IHA:2505821.2505830} proposed a method for activity recognition where a set of activities is manually defined for POI types, and given a trajectory, it finds the stops and matches the POI type of the stop with the manually defined activities. Our work on the other hand considers that multiple activities can happen at each POI and computes the similarity of the trajectory and the activities in the knowledge base in order to infer activities. \citeN{reumers2013semantic} uses a dataset of semantic trajectories annotated with activities and proposes to infer activities using a decision-tree based model. To build the tree, it uses the start time, duration and activity of each stop, but does not consider the place where the activity happened and depends on the annotated trajectory data to build the model. \citeN{kim2014activity} builds a classification model to recognize groups of activities, as for instance, home, work and transportation. It uses spatial regions annotated with the frequency of time, duration and frequency of the activities. However, it does not infer activities, just groups of activities, and it also depends on the annotated trajectory data to build the model. \citeN{Njoo7344875} also manually defines an activity for each POI type, and using a dataset of semantic trajectories annotated with activities it builds classifiers with trajectories from the same moving object, to represent the routine of the object. However, if the moving object goes to a place that was not previously seen, it matches the POI type with the manually defined activity.

Regarding group activity recognition, a few works use trajectory and sensor data. For instance, \citeN{hirano2013hybrid} use bluetooth data and a buddy-list to identify individuals performing activities together. If the bluetooth signals of the individuals are near each other, and they are present in each other's buddy-list, then they are in a group activity. The problem with this approach is that it is limited to the individuals in the buddy-list. For instance, a man introducing his girlfriend to his parents at a dinner party. The girlfriend is not in the parents' buddy-list, only in the buddy-list of the man, so she will not be considered as a member of the family group activity. We solve this problem by considering the indirect connection in encounters, which means that if people are performing the same activity together and share a common connection, they are in the same group activity. \citeN{bourbia2016temporal} uses several sensors to collect data about how people interact with the environment and uses a set of rules to identify group activities. The sensor data are used to access an ontology that defines the relationships between sensor data and their corresponding actions. These actions are combined in the form of logic rules to describe group activities. Our approach does not use rules to identify group activities. Instead, we find encounters of individuals that have a strong relationship.

Overall, our work is different from the previous approaches since we do not depend on a specialist to build the knowledge base, instead, we extract the knowledge from Twitter and census data. We also consider that multiple activities can take place at each POI, and we propose an algorithm to match trajectories with the knowledge base to infer activities. Furthermore, we consider the indirect connection in encounters to recognize group activities. 

\section{Basic Definitions}

In this section we present the main definitions to understand our proposal. We start with the concept of semantic trajectory, which has several definitions in the literature, such as \cite{bogorny2014constant} and \cite{Spaccapietra2008126}. In this work we simplify the concept of semantic trajectory considering only stops that can be associated with POIs. The stops are the most relevant parts of a trajectory and represent the part where the object stayed for a minimal amount of time and where he/she probably performed an activity. Definition \ref{def:st} shows the formal definition of semantic trajectory.

\begin{definition}[\textbf{Semantic Trajectory}] \label{def:st} 
A semantic trajectory $S = \langle s_0, s_1,..., s_n \rangle$ is a sequence of stops, where the $i$th stop is a tuple $s_i$ = $(x_i, y_i, startTime_i, endTime_i, poi_i)$, with $x_i$ and $y_i$ being the spatial coordinates of the stop at the POI $poi_i$, starting at $startTime_i$ and finishing at $endTime_i$.
\end{definition}

A stop of a trajectory occurs at a place, called Point of Interest (POI), given in Definition \ref{def:poi}.

\begin{definition}[\textbf{Point of Interest}]
\label{def:poi} A point of interest is a tuple $poi$ = $(type, x, y, ot, ct)$ where $type$ is the type of the POI (e.g.  Restaurant, Gym, University, Shopping Mall), $x$ and $y$ its location, and $ot$ and $ct$ are, respectively, the opening and closing hours of the point of interest.
\end{definition}

The moving object stops at POIs to perform one or more activities. For instance, a student stops (stays) at a university to study. A worker stops at a restaurant to work as a cook, while clients stop at the restaurant to eat. Furthermore, the activity can be performed alone or by a group of people. The definition of activity is given in Definition~\ref{def:def_act}.

\begin{sloppypar}
\begin{definition}[\textbf{Activity}] \label{def:def_act} 
An activity is a tuple $a$ = $(act.startTime, act.endTime, label, P)$ where $act.startTime$ and $act.endTime$ are respectively, the start and end times of the activity $label$ and $P$ is the set of moving objects that performed the activity.
\end{definition}
\end{sloppypar}

We extend the definition of semantic trajectory to cope with activities, and call it activity trajectory, which is given in Definition \ref{def:at1}.

\begin{definition}[\textbf{Activity Trajectory}] \label{def:at1} 
An activity trajectory $T = \langle t_0, t_1,..., t_n \rangle$ is a sequence of tuples $t_i$ = $(s_i, A_i)$, with  $s_i$ being a stop and $A_i = \{ a_0, a_1,..., a_n\}$ being the set of activities performed at $s_i$.
\end{definition}

Different activities can happen at the same POI type. In order to know which are the activities that happen at each POI type we extract information from social media data, such as the frequency that each activity happens at a POI type and the average time it is performed, resulting in what we call a \emph{POI Type Profile}, given in Definition~\ref{def:ptp}.

\begin{sloppypar}
\begin{definition}[\textbf{POI Type Profile}] \label{def:ptp}
A POI type profile is a tuple $pro$ = $(POItype, act, meanTime, sdTime, meanDuration, sdDuration, frequency)$, where $meanTime$ is the mean time of the observed occurrences of the activity $act$ at the POI type $POItype$; $sdTime$ is the standard deviation of this time, $meanDuration$ is the mean duration time of $act$ at $POItype$, $sdDuration$ is the standard deviation of this duration, and $frequency$ is the frequency of $act$ at $POItype$ relative to the total number of activity occurrences observed at $POItype$.
\end{definition}
\end{sloppypar}

In the following section we present the proposed approach for activity recognition.

\section{Activity Recognition from Movement Data and Social Networks}

Our approach to infer activities  has three main steps. The first one is to build an activity knowledge base in the form of POI type profiles, which is extracted from Twitter, Foursquare and census data. The second step is to infer individual activities in trajectories by matching the stops of the moving object  with the POI type profiles in the knowledge base. The third step is to infer group activities, by computing the encounters of the moving objects at the same POIs and their relationship degree. These steps are described in the following sections.

\subsection{Building the Knowledge Base} \label{sec:proposed_building_kb}

The knowledge base is a representation of the distribution of activity time and duration that happen at each POI type. It contains the following information: POI type, activity name, average duration,  standard deviation of the duration, average time,  standard deviation of activity time and relative frequency. Table \ref{table:shopping_mall} shows an example of the knowledge base for the POI Type \emph{Shopping Mall}. For instance, based on social media data analysis  it is possible to measure that the average time that people  are watching movies at a \emph{Shopping Mall} is at $16.35$ (16h21min), with a standard deviation of $3.12$ (03h07min). The average time (duration) that people stay at a \emph{Shopping Mall} watching a movie is $2.27$ (02h16min), with a standard deviation of $0.77$ (46min), and the relative frequency of the activity watching movies at a \emph{Shopping Mall} is $10\%$.

\begin{table}[b]
\tiny
	\centering
    \caption{Knowledge Base for POI Type \emph{Shopping Mall}}
   	\label{table:shopping_mall}
    \begin{tabular}{|c|c|c|c|c|c|c|}
    \hline
    POI Type & Activity Name & \pbox[c][20pt]{\textwidth}{Avg Time} & \pbox[20pt]{\textwidth}{Time Sd} & \pbox[c][20pt]{\textwidth}{Avg  \\ Duration} & \pbox[20pt]{\textwidth}{Duration Sd} & \pbox[c][20pt]{\textwidth}{Relative \\ Frequency} \\ \hline
    Shopping Mall & \pbox[c][18pt]{\textwidth}{Consumer  Purchases} & 13.98 & 3.57 & 0.74 & 0.86 & 0.17 \\ \hline
    Shopping Mall & \pbox[c][18pt]{\textwidth}{Socializing,  Relaxing, \\ and Leisure} & 14.57 & 4.00 & 0.78 & 0.99 & 0.45  \\ \hline
    Shopping Mall & \pbox[c][18pt]{\textwidth}{Eating \&  Drinking} & 14.17 & 3.52 & 0.63 & 0.48 & 0.28 \\ \hline
    Shopping Mall & \pbox[c][18pt]{\textwidth}{Movies} & 16.35 & 3.12 & 2.27 & 0.77 & 0.10   \\ \hline
    \end{tabular}
\end{table}

Each attribute is described as follows: (i) POI Type is extracted from Foursquare, and it is present in the tweet to show where the activity happened; (ii) Activity Name is the activity we want to infer; (iii) Average Duration is the average time people spend doing an activity at a POI type. We can extract this information from any set or taxonomy of activities; (iv) Duration Std Dev is the standard deviation of the average duration. This information can be extracted from any set or taxonomy of activities; (v) Average Time is the post time of the activity at the POI type. This information is extracted from the tweets; (vi) Time Std Dev is the standard deviation of the average time. This information is extracted from the tweets; and finally (vii) Relative Frequency is the proportion of tweets of an activity that happened at the POI type.

Algorithm~\ref{alg:extract_features} describes how we build the POI type profiles knowledge base. The inputs of this algorithm are a set of georeferenced tweets annotated with activities (more details are given in Section~\ref{sec:kbfromtwitter}), and  a census dataset, which consists of activity diaries containing for each activity the place where it was performed (POI), and the time spent performing the activity. We use the census dataset as complementary data for each activity, because only the posting time of each tweet is not enough to infer activities.

This algorithm iterates the set of tweets (lines 4 to 8), extracting the  posting time of the tweets to an auxiliary structure organized by POI types and activities (line 5). Then, for each tweet it adds one to the frequency of the respective POI type and activity in the same auxiliary data structure (line 6), and adds one to the frequency regardless of the activity (line 7) in order to obtain the relative frequency of the activities at each POI type. After that, it iterates the auxiliary structure $A$ (lines 9 to 18) and obtains the POI type and activity of each instance (lines 10 and 11). After that, it calls the method $C.getDuration$, which has a list of durations for each POI type/activity,  to get the activity duration list filtered by POI type and activity (line 12), and calculates the mean and standard deviation of the durations (lines 13 and 14). Then, it calculates the mean and standard deviation of the tweet posting times (lines 15 and 16), and the relative frequency of the activity for the respective POI type (line 17). Finally, it returns the POI type profiles as the knowledge base $K$ (line 19). This algorithm iterates only once the set of tweets and the auxiliary dictionary $A$ of POI types and activities. So the complexity is $O(n_d + n_t * n_a)$, where $n_d$ is the number of tweets, $n_t$ is the number of unique POI types, and $n_a$ is the number of unique activities.

\input{algorithms/extractfeatures}

In the next section we describe the algorithm T-Activity and show how to infer activities using the knowledge base.

\subsection{Individual Activity Recognition}

The moving object can perform multiple activities at a POI, so the question is how to distinguish, for instance, if a person is purchasing items at a store, eating at a restaurant or watching a movie at
a cinema, when we only know that this person is in a shopping center? In addition, even when this person is in a smaller POI, such as a cafe, there are many possible activities that this person can be doing there, such as eating, having just a drink, reading, socializing, working, and so on. Thus, it is necessary first to determine sub-stops in smaller places that can be inside a bigger place such as a shopping center, and then, for each sub-stop, determine the activity performed.

In order to identify multiple activities at the same POI, we propose to split each stop at a big place into sub-stops, i.e. in smaller places contained in the bigger place. This can be done by using the method to detect sub-stops proposed by \citeN{moreno2010looking}. For example, let us consider Figure~\ref{fig:example_sub} as a trajectory of a student that has a stop at a university. Inside this stop, he has a sub-stop at a classroom (A), a sub-stop at the laboratory (B) and a sub-stop at the university cafeteria (C). By using the concept of sub-stops we can identify more than one activity at each stop.

\input{images/semantic_trajectory_example2}

The speed of the movement of an object inside a shopping mall is more similar than the movement speed outside, where the object is moving between places. The methods to compute stops, such as CB-SMoT~\cite{palma} are not able to distinguish different sub-stops inside a single place as a shopping mall. To solve this problem, \citeN{moreno2010looking} proposed a method to find sub-stops inside stops, which considers the points inside each stop as a trajectory and runs the algorithm CB-SMoT a second over these points. The formal definition of sub-stop is given in Definition~\ref{desc:ss}.

\begin{sloppypar}
\begin{definition}[\textbf{Sub-Stop}] \label{desc:ss} A sub-stop is a tuple $sub = (s, t.startTime, t.endTime, x, y)$ where $sub$ is the sub-stop that happens inside the stop $s$, starting at $t.startTime$ and finishing at $t.endTime$, with $x$ and $y$ being the coordinates of the centroid of the sub-stop.
\end{definition}
\end{sloppypar}

In order to recognize activities, the objective is to find the activity in the POI type profiles that is more similar to the sub-stops in the trajectories. Therefore, we compute the time and duration similarity between the POI type profiles and the sub-stops. The time similarity is computed in Equation~\ref{eq:time}, where $K$ is the POI type profile, $st$ is the sub-stop start time, $meanTime$ is the average time the activity starts in the POI type profile and $K_{sdTime} / K_{meanTime}$ is the variation coefficient of the time in the POI type profile.

\begin{equation}
\label{eq:time}
TimeSim(K, st) = 1 - \abs{\frac{K_{meanTime} - st}{K_{meanTime}}} * \frac{K_{sdTime}}{K_{meanTime}}
\end{equation}

The idea behind this formula is to obtain the similarity between the activity which can be performed at the POI type and the sub-stop. We consider the similarity as the inverse of the distance between the start time of the sub-stop and the average time in the profile. Also, we use the coefficient of variation to penalize the similarity score, such that as the standard deviation grows in relation to the mean, the similarity score decreases.

The similarity of the duration of the sub-stop and each activity in the POI type profile is computed using Equation~\ref{eq:duration}, where $K$ is the POI type profile, $d$ is the sub-stop duration, $meanDur$ is the average duration of the activity in the POI type profile and $K_{sdDur} / K_{meanDur}$ is the variation coefficient of the duration in the POI type profile.

\begin{equation}
\label{eq:duration}
DurationSim(K, d) = 1 - \abs{\frac{K_{meanDur} - d}{K_{meanDur}}} * \frac{K_{sdDur}}{K_{meanDur}}
\end{equation}

We consider the similarity as the inverse of the distance between the duration of the sub-stop and the average duration in the profile. We also use the coefficient of variation $K_{sdDur} / K_{meanDur}$, to penalize the similarity score, which means that as the standard deviation grows in relation to the mean, the similarity score decreases, helping us to distinguish activities with similar durations. 

If the score between the activities of the same POI is too similar, the time and duration cannot describe which activity happened. Therefore, our model also considers the frequency of the activities to help us to distinguish between activities. However, using the frequency of the activities can lead to activities that cannot be inferred if the frequency is too low. This is seen in Equation~\ref{eq:model}, where $K$ is a POI type profile, $K_{frequency}$ is the relative frequency of the activity at the POI type, $d$ is the sub-stop duration, $st$ is the sub-stop starting time, and $DurationSim$ and $TimeSim$ are respectively, the duration similarity function and the time similarity function.

\begin{equation}
\label{eq:model}
ModelSim(K, d, st) = K_{frequency} * DurationSim(K, d) * TimeSim(K, st)
\end{equation}

Algorithm~\ref{alg:t_activity}, called T-Activity, describes the activity recognition. It receives as input a semantic trajectory $S$, a knowledge base in the form of POI Type profiles $K$, a radius $radius$ that is used to create a buffer at the centroid of each sub-stop to check if the sub-stops intersect each other, and the parameters of the algorithm ESD~\cite{AndreESB}, to find the sub-stops in the same way as proposed by~\citeN{moreno2010looking}.

\input{algorithms/tactivity}

The algorithm starts by initializing the activity trajectory $T$, computing the sub-stops by calling the function \emph{computeSubStops}. It calls the algorithm ESD, which is a clustering algorithm based on time and distance variation between neighbor points of the trajectory. It evaluates the trajectory points and finds clusters where neighbor points are within a given distance and the time difference between the initial point and last point of the stop is greater than a given threshold. If no sub-stop is found, it considers the whole stop as the sub-stop (line 1). After that, it iterates the stops and sub-stops of the trajectory (lines 2 to 14). Then, for each sub-stop, it creates a buffer with a radius of size $radius$ from the sub-stop centroid (line 4) and calls the method $intersect$ to find all sub-stops that intersect this buffer (line 5). The algorithm groups the near sub-stops because we are interested in the whole time that was spent performing the activity. For instance, an individual works for 08h00min, but it leaves the company for lunch. By using sub-stops, we would find two sub-stops of 04h00min, hence we group them to account for one activity and sum their duration, resulting in 08h00min. After that, the algorithm computes the similarity between the sub-stop $sub$ and the activities in the knowledge base $K$. First, it gets the set of relative frequencies for the activities at the POI type of the stop from the knowledge base $K$ (line 7). Then it computes the set of time similarity scores for the activities at the POI type of the stop using Equation~\ref{eq:time} (line 8). Then it computes the set of duration similarity scores for the activities at the POI type of the stop using Equation~\ref{eq:duration} (line 9). Then, it computes the score of the set of the activities by multiplying the activity scores of each set using Equation~\ref{eq:model} (line 10), and selects the activity with the highest score (line 11). Finally, it appends the activity with the highest score (line 12), and returns the activity trajectory (line 15). The complexity of this algorithm is $O(n_s * n_{sub}^2)$, where $n_s$ is the number of stops and $n_{sub}$ is the number of sub-stops. Also, as we execute algorithm ESD outside the loop, it adds $O(n_{p})$ to the complexity, where $n_p$ is the number of points of the stops. In the following section we describe the proposed approach for group activity recognition. 

\subsection{Group Activity Recognition}

People perform different activities at different types of places, alone or in groups. The problem to determine group activities is that people that are together not necessarily are performing group activities. They can be close just by chance in many situations. For instance, people having dinner at a restaurant are not necessarily interacting with each other. Proximity is not an option to solve this problem, because data with sufficient precision is usually not available, and people can share tables or be close just due to limited space in a POI. Therefore, in this work a \emph{group activity} is an activity that is performed by a group of people that have a certain relationship degree and that are at the same place, at the same time.

In order to identify groups of individuals with potential to be doing something together, we identify encounters, which are two or more moving objects meeting at the same place, at the same time, and for a minimum amount of time. We can do that by comparing trajectories and checking if the respective moving objects are near to each other at the same time and stay together for a certain time. For instance, when students meet at the classroom, when people are commuting by public transport, and so on. In this article we use the concept of encounter defined in~\cite{santos2015}.

\begin{sloppypar}
\begin{definition}[\textbf{Encounter}] \label{desc:encounter} Let $R_1 = \langle p_1,p_2,p_3, ..., p_n \rangle$ and $R_2 = \langle q_1,q_2,q_3, ..., q_m \rangle$ be two trajectories. Let $straj_1 = \langle p_a, p_{a+1}, ...,p_{a+u} \rangle$ and $straj_2 = \langle q_b, q_{b+1}, ..., q_{b+v} \rangle$ be two subtrajectories of $R_1$ and $R_2$ respectively. $R_1$ and $R_2$ have an encounter at two maximal subtrajectories $straj_1$ and $straj_2$ w.r.t a spatial distance $\Delta_d$, a temporal tolerance $\Delta_t$ and a minimum duration $minTime$ IIF the following conditions hold:
\begin{itemize}
\item $\forall p_i \in straj_1, \exists q_j \in straj_2 |$ spatialDist($p_i$, $q_j$) $< \Delta_d$ $\land$ temporalDist($p_i$, $q_j$) $< \Delta_t$ 
\item $\forall q_j \in straj_2, \exists p_i \in straj_1 |$ spatialDist($q_j$, $p_i$) $< \Delta_d$ $\land$ temporalDist($q_j$, $p_i$) $< \Delta_t$
\item (min($p_{a+u}$.t,$q_{b+v}$.t) - max($p_a$.t,$q_b$.t)) $>$ minTime
\end{itemize}
where the functions $spatialDist()$ and $temporalDist()$ compute, respectively, the Euclidean distance and the temporal distance between the points $p_i$ and $q_j$.
\end{definition}
\end{sloppypar}

Although encounters can be used to infer group activities, the fact that objects stay together in space and time does not mean that they are doing a joint activity. For instance, objects which are together in a park are not necessarily doing joint activities and may not even know each other. In this work we assume that a group activity involves people that have a relationship and/or are indirectly connected by a common relationship in an encounter. Therefore, we use the relationship degree of individuals, proposed in \cite{santos:thesis:2015}, to infer group activities. In this article we use the algorithm MORE++~\cite{santos:thesis:2015} to compute the relationship degree by weighting scores based on the number of encounters objects have at different days, the number of different places where objects meet, and the amount of time people spend together. The formal definition is given in Definition~\ref{desc:relationshipdegree}.

\begin{definition}[\textbf{Relationship Degree}]   \label{desc:relationshipdegree} Let DB = $e_1, e_2, ..., e_n$ be a set of encounters w.r.t $\Delta_d$, $\Delta_t$ and $minTime$ of all sets of moving objects in a trajectory database. Let $E(o_i, o_j)$ denote the set of all encounters between $o_i$ and $o_j$. The relationship degree between $o_i$ and $o_j$ is computed as:

\begin{equation}
R(o_1, o_2) = R_{f}(o_1, o_2).w_{R_f} + R_{d}(o_1, o_2).w_{R_d} +
R_{a}(o_1, o_2).w_{R_a}
\end{equation}

where $w_{R_f} + w_{R_d} + w_{R_a}$ = 1 and $R_{f}$, $R_{d}$ and $R_{a}$ being respectively, the relationship based on the frequency of the encounters, the relationship based on the duration of the encounters and the relationship based on the number of different areas of the encounters, with each of these functions representing the proportion of days, duration, and different areas the objects had encounters.

\end{definition}

The relationship degree is a number between zero and one, and the higher the number (closer to one) the stronger is the relationship. Lower relationship degrees may reveal individuals that had encounters by chance and may not necessarily have a relationship. Therefore, we use the relationship degree as an indicator whether people know each other or not, which is the information we need to recognize group activities. We select only strong relationships, and represent them as the edges of a graph, where the vertices represent the moving objects, as shown in Figure~\ref{fig:sub:2}.
  
\begin{figure}[b]
  \centering
  \begin{minipage}[b]{0.35\textwidth}
    \caption{Strong Relationship Degrees (A,B and B,C)}
    \label{fig:sub:2}
    \includegraphics[scale=0.5]{images/graph_2}
  \end{minipage}
  \hfill
  \begin{minipage}[b]{0.56\textwidth}
	\caption{Having Dinner at a Restaurant}
    \label{fig:connection_restaurant}
    \includegraphics[scale=0.4]{images/encounter_restaurant_indirect_connection}
	\caption*{Source: http://santosesantosarquitetura.com.br}
  \end{minipage}
\end{figure}

To better understand why weak relationships are not considered, let us observe Figure~\ref{fig:connection_restaurant}, that shows a group of individuals $A,B,C,D,E,F$ having an encounter at a restaurant. Looking at the figure we can notice that although all objects are at the restaurant, having an encounter, they are not doing a group activity, since they are at different tables. To discover if the objects are in fact doing joint activities we analyze all previous encounters of all objects, giving us a higher probability that the individuals did not meet by chance. For instance, let us consider that objects in the encounter $A,B,C,D,E,F$ also had the following encounters: $e_1 = (A,B)$ at the cafeteria, $e_2 = (B,C)$ at the university, $e_3 = (A,B)$ at the mall, and $e_4 = (B,C)$ at work. For this example, we compute the relationship degree as the number of different places the individuals met, dividing these numbers by the maximum number of encounters of an individual, which is object $B$ with 5 encounters, resulting in the scores showed in Table~\ref{table:results_example_gact}. For objects that have strong relationships, i.e., the relationship degree is higher than a given threshold, suppose 0.5 in this example, we build a graph. By this graph we exclude individuals $D,E,F$, as the weaker relationship degree indicates that they met by chance.

Going back to our previous example, although individuals $A,C$ have a weak relationship because they only met once at the restaurant in Figure~\ref{fig:connection_restaurant}, we still cannot exclude them from the group activity inference because they are connected by a common individual. Filtering strong relationships increases the probability that people that are together are performing a joint activity, but it does not mean that people with weak relationships cannot perform activities in group. For those cases, we check individuals that are indirectly connected through the relationship graph, as given in Definition~\ref{desc:rte}.

\begin{sloppypar}
  \begin{definition}[\textbf{Encounter Indirect Connection}] \label{desc:rte} 
Let $oid_1$, $oid_2$ and $oid_3$ be moving objects in the encounter $E$. To represent the indirect connection between the individuals in the encounter, we adopt the concept of transitivity, which states:
\begin{itemize}
\item $oid_1, oid_2, oid_3 \in E : hasConnection(G, oid_1, oid_2) \land hasConnection(G, oid_2, oid_3) \Rightarrow hasConnection(G, oid_1, oid_3)$
\end{itemize}
where the function hasConnection computes a breadth-first search in the graph $G$ to check if $oid_1,oid_3$ share the common connection $oid_2$.
\end{definition}
\end{sloppypar}

Having described the definitions, Algorithm~\ref{alg:awareencounters} shows how to use the graph to filter encounters to find group activities. It receives as input the graph representing the relationship degrees and an encounter to analyze. It starts by initializing an empty set of filtered encounters (line 1), the index of the filtered encounter (line 2), the individuals involved in the encounter (line 3) and then filtering the vertices that represent the individuals (line 4). After that, it iterates the vertices of the graph $G$ (line 5 to 24). It extracts the edges of the vertex (line 6) and checks whether it is the first iteration or not (line 7). If so, it creates a list to store the individuals that have a relationship (line 8), and adds the vertex (individual) to this group (line 9 and 10).

\begin{table}[t]
\centering
\caption{Example for Area Relationship Degree}
\small
\label{table:results_example_gact}
\subtable{
\begin{tabular}{|c|c|}
\hline
Oid   & Rel. Degree \\ \hline
A,B   & 3/5 = 0.6 \\ \hline
\end{tabular}
}
\subtable{
\begin{tabular}{|c|c|}
\hline
Oid   & Rel. Degree \\ \hline
B,C   & 3/5 = 0.6 \\ \hline
\end{tabular}
}
\subtable{
\begin{tabular}{|c|c|}
\hline
Oid   & Rel. Degree \\ \hline
A,B,C,D,E,F & 1/5 = 0.2 \\ \hline
\end{tabular}
}
\end{table}

\begin{minipage}[b]{0.51\textwidth}
\null 
 \begin{algorithm}[H]
	\footnotesize
        \caption{Filter Encounters}
        \label{alg:awareencounters}
		\begin{algorithmic}[1]
        \Require
	    	\Statex $G$ // relationship graph
			\Statex $E$ // encounter
			
\State $FilteredEncounters$ = empty list;
\State $index$ = $0;$
\State $individuals = E.oids;$ //hashset
\State $vertices = G.vertices[individuals];$

\ForEach {$vertex$ in $vertices$}
	\State $edges$ = $vertex.edges;$
    \If {$FilteredEncounters.size()$ == $0$}
    	\State $Group$ = $new$ $empty$ $list$;
        \State $FilteredEncounters.add(Group)$
		\State $FilteredEncounters[index].add(vertex);$
	\Else 
    	\If {$vertex$ not in $FilteredEncounters[index]$}
    		\State $index$ = $index + 1;$
            \State $Group$ = $new$ $empty$ $list$;
            \State $FilteredEncounters.add(Group)$
	        \State $FilteredEncounters[index].add(vertex);$
    	\EndIf
    \EndIf

	\For {$edge$ in $edges$}
    	\If {$edge$ in $individuals$}
        	\State $FilteredEncounters[index].add(edge);$
        \EndIf
    \EndFor
\EndFor
\\
\Return $FilteredEncounters;$
\end{algorithmic}
\end{algorithm}
\end{minipage}%
\hfill
\begin{minipage}[b]{0.45\textwidth}
\null
\begin{algorithm}[H]
	\footnotesize
        \caption{G-Activity}
        \label{alg:groupactivity}
		\begin{algorithmic}[1]
        \Require
			\Statex $T$ // activity trajectories
			\Statex $G$ // relationship graph
      		\Statex $E$ // set of encounters

\ForEach {$encounter$ in $E$}
	\State $filEnc$ = $filterEncounters(G, encounter);$
	\ForEach {$traj$ in $T[encounter.trajectories]$}
		\ForEach {$filtered$ in $filEnc$}
			\If {$traj.oid$ in $filtered.oids$}
        		\State $traj.P.add(filtered.oids);$
        	\EndIf
		\EndFor
    \EndFor
\EndFor
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\Statex 
\end{algorithmic}
\end{algorithm}
\end{minipage}

After that it iterates the edges (relationships) of the vertex (individual) (line 19 to 23) and checks if each edge is from any individual in the encounter $E$ (line 20). If this is the case, it adds the edge to the filtered encounter (line 21). For the next iterations of the vertices, it checks whether the vertex was already filtered out (line 12). If not, it creates a new list that represents a group of individuals that have a relationship (line 14), and adds the vertex (individual) to this group (lines 15 and 16). Finally, it returns the set of filtered encounters (line 25). As an example, if the input is an encounter of one couple plus 4 people that do not have a strong relationship, the output will be just the couple, as they have a strong relationship. As this algorithm iterates the vertices of the graph $G$ once and all the edges of the graph $G$ once it has a complexity of $O(n_v + n_e)$, where $n_v$ is the number of vertices of the relationship graph $G$ and $n_e$ is the total number of edges from the vertices that are iterated. The idea of the algorithm is similar to a Breadth-First Search (BFS), however, as the relationship graph is represented by a centered vertex connected to several other vertices (similar to a star), we perform several BFS, searching only one level for each vertex and checking if the discovered edges are in the encounter $E$. Also, as we represent the individuals of the encounter $E$ as a hashset, we maintain a linear behavior.

Finally, algorithm~\ref{alg:groupactivity}, called G-Activity, describes how we recognize group activities. It has as input a set of activity trajectories $T$, a relationship graph $G$ and a set of encounters $E$. This algorithm is the most expensive to compute, as it has to compute the algorithm \emph{filterEncounters} for each encounter in the set $E$ (lines 1 and 2). It iterates the trajectories and matches them with the filtered encounters (lines 3 and 4). Then it checks if the moving object is part of the filtered encounter, and adds all individuals of the encounter as participants of the group activity (lines 5 and 6). As an example, if the input is a set of three trajectories from one encounter, where two individuals know each other, the algorithm will annotate two trajectories with two participants (activity performed in group) and one trajectory with just one participant (activity performed alone). The time complexity of the algorithm is $O(n_e * (n_g + n_t * n_f))$, where $n_e$ is the total number of encounters, $n_g$ is the time complexity of the algorithm~\ref{alg:awareencounters}, which iterates the graph $G$ in linear time, $n_t$ is the number of activity trajectories $T$ and $n_f$ is the number of filtered encounters.

\section{Experimental Evaluation}

In this chapter we evaluate the proposed approach with three different datasets, two GPS trajectory datasets and one synthetic trajectory dataset generated over activity diaries extracted from census data. The GPS trajectories were collected in Florian\'{o}polis, Brazil, and Pisa, Italy, and are annotated with activities. The dataset generated from census data is the North American census, which contains the activities that a person performs during a day, the place the activity is performed and for how long. For building the knowledge base we use a dataset of georeferenced tweets generated from Foursquare collected for the period of 14/09/2010 to 11/05/2015. Table~\ref{table:db_stats} shows the list of activities an its frequency in each dataset.

We start the experimental evaluation presenting the knowledge base construction in Section~\ref{sec:kbfromtwitter} and the evaluation of T-Activity and G-Activity in the remaining sections.

\begin{table}[b]
\tiny
\centering
\caption{Dataset Statistics}
\label{table:db_stats}
  \subtable{
    \begin{tabular}{|c|c|c|c|c|}
    \hline Activity & \pbox[c][20pt]{\textwidth}{Twitter \\ Dataset} & \pbox[c][20pt]{\textwidth}{Florian\'{o}polis \\ Dataset} & \pbox[c][20pt]{\textwidth}{Pisa \\ Dataset} & \pbox[c][20pt]{\textwidth}{Census \\ Dataset} \\ \hline
    \pbox[c][20pt]{\textwidth}{Socializing, \\ Relaxing, \\ and Leisure} & 295 & 3 & 33 & 344 \\ \hline
\pbox[c][20pt]{\textwidth}{Eating \& \\ Drinking} & 548 & 38 & 3 & 1315 \\ \hline
\pbox[c][20pt]{\textwidth}{Education} & 170 & 53 & 0 & 342 \\ \hline
\pbox[c][20pt]{\textwidth}{Consumer \\ Purchases} & 222 & 21 & 21 & 3033 \\ \hline
\pbox[c][20pt]{\textwidth}{Sports, \\ Exercise, \\ and Recreation} & 226 & 13 & 0 & 209 \\ \hline
    \end{tabular}
  }
  \subtable{
    \begin{tabular}{|c|c|c|c|c|}
    \hline Activity & \pbox[c][20pt]{\textwidth}{Twitter \\ Dataset} & \pbox[c][20pt]{\textwidth}{Florian\'{o}polis \\ Dataset} & \pbox[c][20pt]{\textwidth}{Pisa \\ Dataset} & \pbox[c][20pt]{\textwidth}{Census \\ Dataset} \\ \hline
    \pbox[c][20pt]{\textwidth}{Movies} & 31 & 0 & 0 & 0 \\ \hline
\pbox[c][20pt]{\textwidth}{Working} & 0 & 0 & 29 & 0 \\ \hline
\pbox[c][20pt]{\textwidth}{Waiting \\ the Bus} & 0 & 0 & 8 & 0 \\ \hline
\pbox[c][20pt]{\textwidth}{Healthcare} & 0 & 0 & 1 & 0 \\ \hline
\pbox[c][20pt]{\textwidth}{\textbf{Total}} & \textbf{1492} & \textbf{128} & \textbf{95} & \textbf{5243} \\ \hline
    \end{tabular}
  }
\end{table}

\subsection{Building the Knowledge Base}
\label{sec:kbfromtwitter}

We gathered tweets from the Twitter Public Streaming API to feed the knowledge base. We selected 137,509 georeferenced tweets generated from Foursquare from 14/09/2010 to 11/05/2015. Took the ones written in Portuguese, with coordinates inside Brazil's bounding box, and with at least 3 words. To build the knowledge base, the first step was to extract the POI information from Foursquare, using the Venue Search API. We did that by looking the Venue at the coordinates present in the tweet. As a result we had the tweet text, the tweet time, the POI type and the POI name. Then, for this experiment we filtered the tweets by the following POI types: Restaurant, Gym, Supermarket, University and Shopping Mall, which are the existing types in the trajectory datasets. The result was a corpus with 45,209 tweets.

To identify the activities from tweets, we follow the method proposed by Zhu et al. in \cite{Zhu2016103}, which consists in building a classification model to assign each tweet to an activity. We randomly selected a sample of tweets stratified by POI type, with the size determined by a confidence level of 95\% and a confidence interval of 5\%, and manually classify each one to an activity present in the ATUS taxonomy accordingly to the text of the tweet. We tried to use verbs to identify activities, but the results were not satisfactory, since the amount of geo-referenced tweets containing verbs was insignificant. Therefore we ignored the grammatical class of the words and adopted the metric TF-IDF to weight the words.

Having the annotated tweets, we build a classification model considering the following features: (i) POI Type: as each tweet is georeferenced to a Foursquare POI, we extract the POI type and construct a matrix containing 11 binary features, each one representing a general POI type; (ii) Tweet Text: by extracting the most relevant uni-grams and bi-grams weighted by TF-IDF, we obtain 9394 features from the text; (iii) POI Name: the same way we extract features from the tweet text we extract the POI name, as some POI names can be indicative of activities (e.g. Japanese Restaurant, Fourth Street Market); Posting Time: we chunk the tweet posting time by hour of the day to construct a matrix of 24 features. We combine the previous features in a matrix and build a SVM linear model with L1-regularization for feature selection and squared hinge loss. We evaluate the tweet classification model by splitting the manually labeled dataset into training and testing data, with a proportion of 70/30, obtaining an accuracy of 78.57\%, and average precision of 83.33\%, and an average recall of 75.83\%. After building and evaluating the classification model, we classify the remaining tweets. In addition, we run Algorithm~\ref{alg:extract_features} to extract the mean and standard deviation of time and duration and also the relative frequency of the activities to store in the knowledge base. Table~\ref{table:kb_completa} shows the knowledge base generated for this experiment, where the majority of the POI types have multiple activities. For instance, \emph{Shopping Mall} has four different activities, where the most common activity is \emph{Socializing, Relaxing, and Leisure}. It is important to notice that the average time is an approximation of multiple distributions, which explains the high standard deviations of time.

\begin{table}[t]
\tiny
    \centering
    \caption{Entire Knowledge Base}
   	\label{table:kb_completa}
    \begin{tabular}{|c|c|c|c|c|c|c|}
    \hline
    POI Type      & Activity Name & Avg Time (hrs) & Time Std Dev & Avg Duration (hrs) & Duration Std Dev & \pbox[c][18pt]{\textwidth}{Rel. Freq. (\%)} \\ \hline
    Shopping Mall & \pbox[c][18pt]{\textwidth}{Consumer Purchases} & 13.98 & 3.57 & 0.74 & 0.86 & 0.17 \\ \hline
    Shopping Mall & \pbox[c][18pt]{\textwidth}{Socializing, Relaxing, \\ and Leisure} & 14.57 & 4.00 & 0.78 & 0.99 & 0.45  \\ \hline
    Shopping Mall & \pbox[c][18pt]{\textwidth}{Eating \&  Drinking} & 14.17 & 3.52 & 0.63 & 0.48 & 0.28 \\ \hline
    Shopping Mall & \pbox[c][18pt]{\textwidth}{Movies} & 16.35 & 3.12 & 2.27 & 0.77 & 0.10   \\ \hline
    Supermarket & \pbox[c][18pt]{\textwidth}{Consumer Purchases}                 & 15.12 & 4.52 & 0.69 & 0.52 & 0.73 \\ \hline
    Supermarket & \pbox[c][18pt]{\textwidth}{Eating \&  Drinking}                 & 14.50 & 5.17 & 0.54 & 0.47 & 0.27 \\ \hline
    Restaurant  & \pbox[c][18pt]{\textwidth}{Eating \&  Drinking}                 & 12.24 & 6.83 & 1.00  & 0.62 & 0.78 \\ \hline
   Restaurant & \pbox[c][18pt]{\textwidth}{Socializing, Relaxing, \\ and Leisure} & 14.60 & 6.59 & 1.47  & 1.34  & 0.18 \\ \hline
    Restaurant  & \pbox[c][18pt]{\textwidth}{Consumer \\ Purchases}                 & 14.51 & 5.28 & 0.16 & 0.19 & 0.04 \\ \hline
    University  & \pbox[c][18pt]{\textwidth}{Socializing,  Relaxing, \\ and Leisure} & 14.52 & 5.69 & 0.73 & 0.88 & 0.02 \\ \hline
    University  & \pbox[c][18pt]{\textwidth}{Education}                          & 13.38 & 5.37  & 3.16  & 1.90  & 0.96 \\ \hline
    University  & \pbox[c][18pt]{\textwidth}{Eating \&  Drinking}                 & 13.96 & 4.51 & 0.51 & 0.30 & 0.02 \\ \hline
    Gym & \pbox[c][18pt]{\textwidth}{Sports, Exercise, \\ and Recreation}   & 13.25 & 5.98 & 0.99 & 0.67 & 1.00 \\ \hline
    \end{tabular}
\end{table}
\normalsize

\subsection{Dataset Description}

The Florianopolis GPS trajectory dataset was collected from 14/04/2016 to 08/06/2016 by 8 participants in the city of Florian\'{o}polis, Brazil. As we can see in Table~\ref{table:db_stats}, this dataset contains 21 \emph{Consumer Purchases} that happened at supermarkets and malls, 38 \emph{Eating \& Drinking} that happened at restaurants and universities, 13 \emph{Sports, Exercise and Recreation} that happened at gyms, 53 \emph{Education} that happened at universities and 3 \emph{Socializing, Relaxing and Leisure} that happened at universities and restaurants. In addition, the dataset is composed of 59 trajectories, 100 stops and 128 sub-stops labeled by the participants.

The Pisa dataset has 38 trajectories collected during 14 days by 7 users and are manually annotated with stops, individual activities and group activities. Although this is a small dataset to validate our approach, it is important since there are not many ground truth trajectory datasets for activity recognition. It contains 95 stops, where 29 happened at \emph{Home}, 29 at \emph{University/Research Institute}, 21 at \emph{Market}, 8 at \emph{Bus Stop}, 4 at \emph{Bar}, 1 at \emph{Hospital}, and 3 at \emph{Bakery}.

Considering the difficulty for obtaining a large semantic trajectory dataset with ground truth, we use a dataset generated from the ATUS dataset~\cite{atus}. This dataset consists of activity diaries, where each diary corresponds to the semantic trajectory of a resident of the United States of America. The diary contains the activity, the place where the activity was performed (POI), and the start and end times of the activity. From this dataset we selected all households that have activity entries with more than 5 days, resulting in 41 households with 2440 stops and 5243 sub-stops. In order to identify sub-stops, we considered as stop every POI where an activity is performed and, as we have multiple entries at the same POI, we consider them as sub-stops. Table~\ref{table:db_stats} shows the distribution of activities in this dataset, which has 3033 \emph{Consumer Purchases}, 1315 \emph{Eating \& Drinking}, 209 \emph{Sports, Exercise and Recreation}, 342 \emph{Education} and 344 \emph{Socializing, Relaxing and Leisure}.

\subsection{Evaluation of T-Activity}
\label{sec:traj}

To evaluate T-Activity we perform experiments in two different datasets. First we evaluate it on the Florian\'{o}polis dataset, where we consider as input the POI type profiles in Table~\ref{table:kb_completa} and set the parameter $radius$ to 10 meters. Figure \ref{fig:precision_recall_comparison} shows the f1-score in comparison to~\citeN{Furletti:2013:IHA:2505821.2505830}, \citeN{reumers2013semantic}, and \citeN{Njoo7344875}.

On analyzing the f1-score we can see that T-Activity presents the best result. In addition, Furletti and Njoo have the same score as our approach where the main activity is the only activity at the POI, such as \emph{Consumer Purchases} for \emph{Supermarket} and \emph{Sports, Exercise and Recreation} for \emph{Gym}, otherwise it has a lower score. Reumers on the other hand, only considers the duration and start time of the activities, and as some activities have similar start times and durations the f1-score is affected. It is important to notice that our work is the only one able to recognize the activity \emph{Socializing, Relaxing and Leisure} as it is not the main activity of any place.

In addition, on considering the difficulty for obtaining a semantic trajectory dataset with ground truth, we evaluate T-Activity with a dataset generated from the ATUS dataset~\cite{atus}, and considered as input the POI Type Profiles in Table~\ref{table:kb_completa}, generated from the Twitter dataset. Figure \ref{fig:precision_recall_comparison_census} shows the f1-score in comparison to~\citeN{Furletti:2013:IHA:2505821.2505830}, \citeN{reumers2013semantic}, and \citeN{Njoo7344875}.

\begin{figure}[b]
\centering
\caption{Comparison of f1-Score at Florianopolis Dataset}
\label{fig:precision_recall_comparison}
\includegraphics[width=0.80\textwidth]{images/florianopolis_fmeasure}
\end{figure}

Analyzing the f1-score we can see that our work outperforms the existing works for almost all activities. The work of Furletti and Njoo have a lower score for almost all classes. This happens because each POI type is matched to an exclusive activity, and our method considers the similarity of the activities along the relative frequency of the activities. However, considering the relative frequency

\begin{figure}[t]
\centering
\caption{Comparison of f1-Score at Census Dataset}
\label{fig:precision_recall_comparison_census}
\includegraphics[width=0.80\textwidth]{images/census_fmeasure}
\end{figure}

\begin{minipage}[h]{0.50\textwidth}
\begin{table}[H]
\small
\centering
\caption{Results for Group Activities at Pisa Dataset}
	\label{table:exp_pisa_gact}
	\begin{tabular}{|c|c|c|c|c|}
	\hline
	\multirow{2}{*}{Participants} & 			\multicolumn{4}{c|}{Activity}                                             \\ \cline{2-5} & \multicolumn{1}{c|}{Socializing} & \multicolumn{1}{c|}{Working} & \multicolumn{1}{c|}{Purchasing} & \multicolumn{1}{c|}{\pbox[c][20pt]{\textwidth}{Waiting \\ the Bus}} \\ \hline
	1, 2 & 8/8 & 2/2 & 2/2 & 0/0 \\ \hline
	1, 3 & 2/2 & 4/4 & 0/0 & 0/0\\ \hline
	2, 3 & 6/6 & 4/4 & 0/0 & 0/0\\ \hline
	1, 2, 3 & 9/9 & 12/12 & 6/6 & 6/6\\ \hline
	5, 6, 7 & 3/3 & 3/3 & 0/3 & 0/0\\ \hline
	\end{tabular}  
\end{table}
\end{minipage}%
\hfill
\begin{minipage}[h]{0.38\textwidth}
\begin{table}[H]
\small
    \centering
    \caption{Relationships at Pisa Dataset}
   	\label{table:exp_pisa_more}
    \begin{tabular}{|c|c|}
    \hline
    \pbox[c][20pt]{\textwidth}{Object Id} & \pbox[c][25pt]{\textwidth}{Relationship \\ Degree} \\ \hline
    1,2,3 & 0.407 \\ \hline
    1,2 & 0.788 \\ \hline
    1,3 & 0.467 \\ \hline
    2,3,4 & 0.284 \\ \hline
    2,3 & 0.536 \\ \hline
    5,6,7 & 0.479 \\ \hline
	\end{tabular}
\end{table}
\end{minipage}

\noindent
is problematic for activities that are too similar and have a low frequency, such as \emph{Socializing, Relaxing and Leisure}. On the other hand, as Reumers does not consider the POI type, the f1-score has the lowest result for all classes. 

\subsection{Evaluation of G-Activity}

To evaluate G-Activity we perform experiments on the Pisa dataset. As the stops are annotated with activities that happened in groups, we analyze the accuracy of our method for group activity recognition. In total, 27 out of 28 encounters were correctly detected in this dataset using the algorithm \emph{BeingTogether} with parameters $\Delta_t$ = 300sec (time tolerance), $\Delta_d$ = 50m (distance threshold), and $minTime$ = 10 minutes (minimal time duration for an encounter). Table~\ref{table:exp_pisa_more} shows the relationship degree of the individuals, where each row represents the relationship of a group with a score ranging from 0 to 1, with 0 being the weakest relationship and 1 the strongest. We computed the relationship degrees using algorithm MORE++ with parameters $w_{R_d} = 0$ (weight for feature duration), $w_{R_a} = 0.5$ (weight for feature area), and $w_{R_f} = 0.5$ (weight for feature frequency). We ignored the feature duration due to some gaps in the dataset affecting the score. 

As input to \emph{G-Activity}, we use the Pisa dataset, the set of detected encounters, the relationship degree in Table~\ref{table:exp_pisa_more} and a relationship threshold $\Delta_r = 0.5$ to prune weak relationships. Table~\ref{table:exp_pisa_gact} summarizes the output of \emph{G-Activity} to show the groups that performed activities together and which activities they performed in comparison to the ground-truth, where each row represents a group that performed activities together, one or more times. In this table we can see that the activities \emph{Socializing}, \emph{Working} and \emph{Waiting the Bus} were all correctly identified, while activity \emph{Purchasing} had $8$ out of $11$ instances correctly identified. In fact, only $3$ \emph{Purchasing} activities from participants \emph{5,6,7} were not identified. This happened because one of their encounters was not found by the algorithm \emph{BeingTogether}, resulting in activities that could not be found by \emph{G-Activity}. Overall, \emph{G-Activity} correctly found $67$ out of $70$ activities performed in groups, resulting in an accuracy of $95.71\%$. 

\section{Conclusion}

In this article we proposed a method for activity recognition in moving object trajectories, extracting the possible activities from tweets posted at POI types and matching these activities with the stops of moving object trajectories. Indeed, we proposed a new method for group activity recognition, identifying encounters and checking whether the participants have relationships with each other and are performing the same activity. Even though activity recognition is broadly performed with different types of data, infer individual and group activities in moving object trajectories is not a trivial task. As future work, we will go deeper in the activity analysis, defining and recognizing unusual activities, using Gaussian Mixture Models to calculate the statistics for time and duration in the knowledge base and improving the score functions by using a probability density function instead of the frequency.
	
\begin{received}
\end{received}

\vspace{-0.3cm}
\bibliographystyle{jidm}
\bibliography{jidmb}

\end{document}