Mike Donald

Tapi Nzali
email: tapinzali@lirmm.fr

Joël Maïzi

Pierre Pompidor

Sandra Bringay

Christian Lavergne

Caroline Bascoul-Mollevi

Joël Ma Ïzi

Explain sentiments using Conditional Random Field and a Huge Lexical Network

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In this article, we focus on a particular task of sentiment analysis which consists in explaining the target and the source of sentiments. For example, in the sentence "We like the green initiative", the sentiment is expressed by the verb "like", the target is "green initiative" and the source is "We". In [START_REF] Bringay | Identifying the targets of the emotions expressed in health forums[END_REF], we have proposed a method based on syntactic roles for English texts. Experiments have shown that our method is robust, even on the texts that are difficult to process : messages in health forums that contain misspelling and slang. Indeed, the method is not based on fine syntactic parsing. However, it is not possible to transpose this method directly to French because, to our knowledge, there is no resource available to explain semantic roles.

In this context, we propose a new approach based on machine learning methods and a very large lexical network, in French, issued from a contributory game JeuxDeMots1 . The challenge is twofold: 1) Instead of using fine syntactic parsing, we use a statistical modelling method called Conditional Random Field (CRF), to extract candidates for targets and sources in large volumes of texts issued from poorly written social web messages 2) we also exploit the huge French lexical network JeuxDeMots (more than 300, 000 nodes and 7, 000, 000 relations) to choose the best sources and targets among the candidates identified with CRF. This new method has been successfully exploited to analyse the sentiments expressed in the French tweets dealing with environment and climate change.

The paper is organized as follows. In section 2, we briefly present the state of the art. In section 3, we provide a description of our method. In section 4, we provide all the detail of the experiments carried out and the prime results. Finally in section 5, we conclude this work by providing the main perspectives associated with this work.

State of the Art

Since the early 2000s, sentiment analysis, also called "opinion mining", has experienced growing interest. Many methods have been developed to extract emotional states expressed or implied in texts. To identify sentiments, many resources exist (e.g. list of words, phrases, idioms), which were built mostly for English and polarity (e.g. Linguistic Inquiry and Word Count (Tausczik and Pennebaker, 2010)) or emotions (e.g. NRC lexicon (Mohammad and Turney, 2010a)). Some methods extend these vocabularies to specific domains [START_REF] Neviarouskaya | Affect analysis model: Novel rulebased approach to affect sensing from text[END_REF]. Others are not restricted to the use of lexicons as [START_REF] Strapparava | Learning to identify emotions in text[END_REF] who implement learning approaches.

Two categories of approaches are used to link sentiments and potential target and source. 1) Methods that essentially implement syntactical aspects, represented by combinations of rules [START_REF] Mudinas | Combining lexicon and learning based approaches for concept-level sentiment analysis[END_REF] as the polarity inverters (do not, just, very...), conjunctions (but, or), etc. The effectiveness of these methods is strongly linked to language style that impacts on the syntactic rules to take into account and are not adapted to social web texts. 2) Methods that are based on different distance computations between words denoting sentiments and potential targets and source (as the proximity [START_REF] Hu | Mining opinion features in customer reviews[END_REF] or the position in the syntactic tree [START_REF] Wu | Phrase dependency parsing for opinion mining[END_REF]). There are also many hybrid methods [START_REF] Ding | The utility of linguistic rules in opinion mining[END_REF]. In [START_REF] Bringay | Identifying the targets of the emotions expressed in health forums[END_REF], we proposed an efficient approach for English texts that requires a resource FrameNet 2 and the SEMAFOR parser 3 for explaining the semantic roles. To our best knowledge, such a resource does not exist in French. Consequently, we have proposed a method combining learning approach to find targets and sources candidates and a smart exploration of a large French lexical network to select the best one.

To choose the best candidate, we use the Games with a purpose JeuxDeMots, created in 2007 [START_REF] Lafourcade | Increasing Long Tail in Weighted Lexical Networks[END_REF], to build a huge lexical network for french. For example, the game asks the player ideas associated with term climatic change. The player freely associate terms such as bear. Other players have already faced the same term. The player wins credits if the proposed term has already been proposed by another player. The more the proposal is specific, the more points he obtains. The lexical network generated with this game is a directed graph, with terms (nodes) and typed and weighted relations (edges) between the terms. There are more than 50 types of relationships. To weight the edges, JeuxDeMots is based on crowdsourcing. Each relation is weighted by a strength of association, denoted C jdm representing the number of players who have associated two terms by the same relation. A first challenge is to explore the network to link terms in the sentences (sentiment and target/source) and explain these relations. The second challenge will be to exploit this very large network that includes more than 300000 terms and more than 7000000 relations.

Methods

The method is organised into 3 steps :

Step 1: Corpus. The corpus we used and annotations have been made in the Ucomp project 4 . These tweets deal with climate change. Table 1 and 2 present detailed statistics on the corpus.

Step 2: candidates generation with CRF. The CRF model was developed with domain indepen- • The original token from the text (word form);

• Surface features: capitalization of the token (all in upper/lower case, combination of both), and punctuation mark in the token (PUNCT, NO PUNCT);

• Lexical features: n-grams, number of consecutive repeats. Token frequency was computed based on the entire training corpus.

• Brown clustering: we used Percy Liang's implementation of Brown clustering [START_REF] Peter F Brown | Class-based n-gram models of natural language[END_REF], which is an HMM-based algorithm. In our work, we partition words into a base set of 100 clusters, and induces a hierarchy among those 100 clusters.

• Emotion lexicon:

We built semiautomatically a new lexicon of French sentiments [START_REF] Amine | Feel : French extended emotional lexicon[END_REF] by translating and expanding the English NRC lexicon (Mohammad and Turney, 2010b). This lexicon is free to download 5 . For each tokens, the corresponding feature takes the value "Yes" if the token appear in the lexicon and "No" otherwise. As a source and a target are usually surrounded by a sentiment token, we also consider the apparition of the sentiment in the neighborhood of the token (e.g. two tokens before or after the current token).

We experimented with standard tokenization (provided by TreeTagger) and custom tokenization [START_REF] Donald Tapi-Nzali | Analyse d'expressions temporelles dans les dossiers électroniques patients[END_REF] of French TreeTagger by adding some segmentation rules (e.g. apostrophe : l'image is segmented into l' and image).

Step 3: Lexical network construction of each sentence. The purpose of this step is to extract a part of the lexical network JeuxDeMots representing the relationship between the meaning of the word and the candidates identified in Step 2. The intuition of the algorithm is the following one. We cross the lexical network from node to node. We stop when we no longer encounter new words or if we reach a maximum depth. Two other constraints are used to limit the expansion of the graph.

Constraint 1. To consider only the parts of the network related to our topic (environment and sentiment), we expand a node to another if the new one belong to these two predefined lexical fields chosen via Larousse thesaurus6 . If there is no node in the lexical field, we expand to all neighboring nodes.

Constraint 2. We use the association strength C jdm weighting the edges and consider only the relations frequently instantiated by players. A threshold is set by default.

Step 4: Identification of shortest paths. The objective of this step is to identify in the graph generated in step 3, the paths that must correspond to a compromise between the shortest paths, with a little depth, most reliable according to strength of association C jdm . We have therefore redefined weights w rt to foster some relationships like synonymy or significant semantic roles such as patient and agent. To identify the paths, we have adapted the shortest path algorithm and used the weights computed according to formulas 1 and 2. The weight w i foster relationships that interest us with w rt while taking into account the strength of association C jdm . In equation 1, we verify a balance between w rt and C jdm terms. In equation 2, the term (n -1) 2 enables to penalize depth. We only consider paths which contain at least one agent or patient relationship. The path with the best score is proposed to the user to explain the link between the sentiment and the target or source.

w 1 = 1 1 -1 C jdm + w rt
(1)

w n = (max(w n-1 ) * 1 1 -1 C jdm + w rt ) * (n -1) 2 (2)

Experiments

Our experiments were carried out using 10-fold cross-validation. To do this, the training corpus was divided into 10 folds. To build our model, we need a training, development and test corpus. Cross-validation has been distributed as follows:

The model is built on 8 folds, the optimization of the construction is performed on the ninth part (development) and the model evaluation performed on the last fold (test).

To perform our experiments, we use Wapiti7 [START_REF] Lavergne | Practical very large scale crfs[END_REF]. It is a very fast toolkit for segmenting and labelling sequences with discriminative models. For the iterative estimation of the model parameters, we used the algorithm RPROP [START_REF] Riedmiller | Rprop-a fast adaptive learning algorithm[END_REF].

Table 3 of source and target correctly extracted over the total number of source and target marked the corpus used) and F-measure (the harmonic average of precision and recall). We show two types of results. the first is the results achieved by Exact match and the second by Partial match. We consider that there is an Exact match when the tokens obtained with our model match exactly those of the standard test annotation and we consider a Partial match when the obtained token are included. For example, governor partially matches The governor. Overall, with Exact match, configuration 1 is the best performing configuration. Results show that, we performed a good results with Partial match. Compared to other configurations, configuration 4 gives the best results on precision ( Precision 0.78), and configuration 1 and 2 give the same results and the best results on recall and F-measure (recall 0.52 and F-measure 0.62). Contrary, with the sentiment lexicon as feature, we increase precision, decrease recall and f-measure. Brown Clustering is good feature if we want to have a good precision.

If CRF is relevant for extracting target and source candidates, how can we link them to the sentiments also expressed in the sentences? In figure 1, a sentence is annotated after the exploration of the lexical network. Sentiment tokens are represented by red points. Target and Source obtained with CRF are colored (in blue and yellow). Arrows correspond to the paths identified in the network. The more the arrow is thick the more the path is valuated.

Conclusions and Future Work

A combination of CRF and huge lexical network exploration seems promising for explaining sentiments in social networks. By experimenting with the CRF model, we found that the results varied depending on the features. The best results are obtained with the features: lemmatization, cluster ID and Part Of Speech tagging.

The first advantage of this method is that we can detect multiple tokens (e.g. parc eolien terrestre, La France). Another advantage of this method is that it is efficient even if the sentence contains misspelling. For example, the system identify modèle de dévelopement durable (sustainable development model) even if the word dévelopement is misspelled. Finally, the main advantage of this contribution is not to restrict sentiment, source and target identification to the case in which sentiment word is present. Indeed, in most cases people express sentiments implicitly without using these sentiment words. An emotion cannot be limited to something a person feels about a fact and not the sentiment that a person expresses about this fact. Thus, it could be common to explicitly express sentiments about things, but it is more common to feel emotions without expressing them explicitly. Our method take into account this fact and try to identify source and target beyond the explicit cases.

The principal limitation of our method is the length of the sentences in the considered corpora (size of the tweets). In many sentences, there is no source or no target. Results are significantly reduced. Moreover, a quantitative study has to be performed on step 3 and 4 to evaluate the quality of the computed relations between sentiment and targets/sources.

Prospects associated with this work are numerous. First, in this work we focus only on the targets/sources expressed in sentences and we now have to focus on inter-sentence relationships at paragraph level. In future work, we are going to use the best model we obtained on health forum messages with longer sentences. We will also compare our method to identify relations between sentiments and source/target with the methods of the state of the art. We will also adapt CRF to extract directly relations. Finally, we will present to users the part of the network used to identify relations in order to help their interpretation

Figure 1 :

 1 Figure 1: Relation example

Table 2 :

 2 presents the results obtained by different CRF models on training set by cross validation. The features of four bests configurations are : Description of the corpusThe results of the evaluation are reported in terms of precision (the number of source and target correctly extracted over the total number of source and target extracted), recall (the number

	• Configuration 1 : Part Of Speech tagging +
	lemmatization + lowercase
	• Configuration 2 : Part Of Speech tagging +
	lemmatization + lowercase + brown cluster-
	ing
	• Configuration 3 : All (Part Of Speech tag-
	ging + lemmatization + lowercase + brown
	clustering + emotion lexicon
	• Configuration 4 : Part Of Speech tagging +
	lemmatization + lowercase + emotion lexicon
		Training	Test	All
	Tweets	3,001 1,783	4,784
	Tokens	78,771 48,612 127,383
	Source	1,131	604	1,735
	Target	3,954 2,251	6,205

Table 3 :

 3 Evaluation of source and target extraction in French tweet corpus.

	Class	Exact match Partial match P R F P R F
	SOURCE 0.64 0.38 0.48 0.76 0.45 0.57
	TARGET 0.34 0.20 0.25 0.79 0.47 0.59
	All	0.40 0.24 0.30 0.78 0.47 0.59

Table 4 :

 4 Results of best model on the test corpus

http://www.jeuxdemots.org/ jdm-accueil.php

fndrupal/home3 http://demo.ark.cs.cmu.edu/parse 4 http://www.ucomp.eu/ 5 http://www.lirmm.fr/ ˜abdaoui/FEEL. html

http://www.larousse.fr/dictionnaires/ francais/thesaurus/77857

http://wapiti.limsi.fr


Amine Abdaoui
email: amin.abdaoui@lirmm.fr

Mike Donald

Tapi Nzali

Jérôme Azé

Sandra Bringay

Christian Lavergne

Caroline Mollevi

Pascal Poncelet

Mike Donald Tapi Nzali
email: mike-donald.tapi-nzali@lirmm.fr

ADVANSE: Sentiment, Opinion and Emotion Analysis in French Tweets

Keywords: Sentiment, Opinion and Emotion Analysis Analyse de sentiments, analyse d'opinions, analyse d'émotions, analyse de subjectivité, fouille de textes Sentiment analysis, opinion analysis, emotion analysis, subjectivity analysis, text mining

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

L'analyse automatique de textes pour y détecter la présence d'états affectifs, leur polarité, les émotions associées et les opinions exprimées a suscité de nombreux travaux ces dernières années. Cet intérêt toujours croissant peut s'expliquer, en partie, par les perspectives d'applications qu'elle ouvre dans de nombreux domaines tels que : les systèmes de recommandation en ligne [START_REF] Tatemura | Virtual reviewers for collaborative exploration of movie reviews[END_REF], l'intelligence économique [START_REF] Melnik | Does a seller's ecommerce reputation matter ? evidence from ebay auctions[END_REF], la veille politique et gouvernementale [START_REF] Laver | Extracting policy positions from political texts using words as data[END_REF][START_REF] Mullen | A preliminary investigation into sentiment analysis of informal political discourse[END_REF], etc. Les méthodes appliquées sont généralement spécifiques aux types de textes traités : aux tweets [START_REF] Roberts | Empatweet : Annotating and detecting emotions on twitter[END_REF], aux titres de presse [START_REF] Strapparava | Learning to identify emotions in text[END_REF], aux commentaires des internautes [START_REF] Vincent | Construction et exploitation d'un corpus français pour l'analyse de sentiment[END_REF], etc. Si la majorité des méthodes proposées ont été créées pour l'Anglais et pour la polarité, quelques travaux plus récents existent aussi pour le Français [START_REF] Grouin | Deft'07 : une campagne d'évaluation en fouille d'opinion[END_REF] et pour les émotions [START_REF]Portable features for classifying emotional text[END_REF]. Dans cet article, nous nous intéressons à la classification de tweets en langue française. Nous présentons des systèmes que nous avons soumis à la onzième édition du défi de fouille de textes (DEFT 2015). La première tâche (tâche 1) à laquelle nous avons participé consiste à classifier les tweets selon leur polarité (positif, négatif ou neutre). Dans la seconde tâche (tâche 2.1), il s'agit de détecter la classe générique exprimée dans un tweet (information, opinion, sentiment ou émotion). La dernière tâche (tâche 2.2) à laquelle nous avons participé consiste à détecter la classe spécifique de l'opinion, du sentiment ou de l'émotion exprimée dans le tweet (18 classes ont été considérées telle que : colère, peur, tristesse, amour, plaisir surprise, accord, etc.). Nous avons obtenu 73,33% de macro-précision pour la tâche 1 à 0,27% du meilleur système. Pour la tâche 2.1 nous avons obtenu le meilleur système avec 61,29% de macro-précision. Cependant, nous n'avons pas considéré les bonnes classes lors de notre soumission pour la tâche 2.2, nous présentons ici nos résultats avec les bonnes classes. Les données d'apprentissage et de test ont été fournies par les organisateurs de la compétition ; les tableaux 1 et 2 montrent la distribution des classes sur le corpus d'apprentissage et de test. [START_REF] Church | Word association norms, mutual information, and lexicography[END_REF].

Lexique de sentiments et d'émotions FEEL

Ce lexique a été construit de manière semi-automatique en traduisant et en étendant le lexique de sentiments et d'émotions anglais NRC [START_REF] Mohammad | Emotions evoked by common words and phrases : Using mechanical turk to create an emotion lexicon[END_REF]. D'autres lexiques anglais existent à l'image de WordNet Affect [START_REF] Strapparava | Wordnet affect : an affective extension of wordnet[END_REF]) mais à notre connaissance, NRC-2010 est le plus complet. Il inclut à la fois les polarités et les émotions ; surtout donne de bons résultats pour des tâches similaires aux nôtres (Kiritchenko et al., 2014a). NRC-2010 associe à chaque terme une polarité (positive ou négative) et une ou plusieurs émotions parmi les six émotions proposées par [START_REF] Ekman | An argument for basic emotions[END_REF], à savoir : joie, colère, tristesse, dégoût, surprise et peur. Il a été construit manuellement en utilisant le service Amazon Mechanical Turk1 . Afin de construire une ressource similaire pour le français, nous avons adopté une approche de traduction et d'extension semi-automatique. D'abord, pour chaque entrée de la ressource initiale, nous avons interrogé six traducteurs automatiques (Google, Bing, Collinsdictionary, Reverso, Babla et Wordreference). Les traductions ont été validées ou pas par un traducteur humain expérimenté. Le traducteur avait la possibilité de changer les polarités et les émotions associées via une interface graphique. Ensuite, nous avons émis l'hypothèse que la polarité était conservée par la synonymie. Nous avons donc étendu notre lexique aux synonymes. Huit outils en ligne ont été utilisés pour la recherche des synonymes (Babla, le dico de l'Institut des Sciences Cognitives, reverso, sensagent, cnrtl, synonym, thefreedictionary et thesaurus). Enfin, nous avons étendu notre lexique aux antonymes (en inversant les polarités) et en utilisant encore une fois deux outils en ligne (antonyme et cnrtl). Finalement, nous avons obtenu une ressource avec plus de 14 000 termes distincts (lemmatisés), chacun associé à une polarité et à une ou plusieurs émotions2 .

Lexique de sentiments basé sur l'information mutuelle

Étant donné que les résultats des systèmes basés sur les lexiques dépendent du type de données et du domaine d'application [START_REF] Pang | Opinion mining and sentiment analysis[END_REF], nous avons décidé de construire automatiquement un lexique de sentiments en utilisant le corpus d'apprentissage fourni pour ce défi. Nous avons implémenté et adapté l'approche de (Kiritchenko et al., 2014b). Au lieu de calculer un seul score pour chaque mot w, nous avons calculé trois scores (un par polarité) pour permettre la prise en compte de la classe neutre. Les trois scores sont présentés dans les formules (1), ( 2) et (3). Chaque score est basé sur la PMI (Pointwise Mutual Information [START_REF] Bouma | Normalized (pointwise) mutual information in collocation extraction[END_REF]) du mot dans un ensemble de tweets comme présenté dans la formule (4). ScoreP ositif (w) = P M I(w, {positif }) -

P M I(w, {negatif } ∪ {neutre}) (1) ScoreN egatif (w) = P M I(w, {negatif }) -P M I(w, {positif } ∪ {neutre}) (2) ScoreN eutre(w) = P M I(w, {neutre}) -P M I(w, {positif } ∪ {negatif }) (3)
P M I(w, {N omDeLaClasse}) = log 2 f req(w, {N omDeLaClasse}) * N f req(w) * f req({N omDeLaClasse)} (

Prétraitements

Comme indiqué par [START_REF] Balahur | Sentiment analysis in social media texts[END_REF], les textes issus des réseaux sociaux ont des particularités linguistiques qui peuvent influencer les performances de la classification. Pour cette raison, nous avons appliqué les prétraitements suivants : 1) le remplacement de tous les liens hypertextes qui figurent dans les tweets par 'lienHTPP' ; 2) le remplacement de toutes les adresses mails présentes dans les tweets par 'mail' ; 3) le remplacement de tous les tags utilisateur par '@tag' ; 4) la lemmatisation de tous les mots en utilisant l'outil TreeTagger [START_REF] Schmid | Probabilistic part-of-speech tagging using decision trees[END_REF].

En outre, nous avons remarqué que certains prétraitements tels que le remplacement des mots d'argots, la mise en minuscules et le remplacement des mots allongés font chuter les macro-précisions (voir section 4). De ce fait, ces derniers n'ont pas été considéré dans nos soumissions.

Attributs

Pour la construction de nos attributs, nous avons d'abord testé ceux utilisés par [START_REF] Mohammad | Nrc-canada : Building the state-of-the-art in sentiment analysis of tweets[END_REF] -Lexique de sentiments FEEL : les attributs suivants ont été considérés : 1) le nombre de mots positifs ; 2) le nombre de mots négatifs ; 3) la somme des scores de tous les mots ; 4) le score le plus élevé ; 5) le score du dernier mot comme cela a été fait par [START_REF] Mohammad | Nrc-canada : Building the state-of-the-art in sentiment analysis of tweets[END_REF]. -Lexique d'émotions FEEL : les attributs suivants ont été considérés : 1) le nombre de mots exprimant la confiance ;

2) le nombre de mots exprimant la joie ; 3) le nombre de mots exprimant la colère ; 4) le nombre de mots exprimant la tristesse ; 5) le nombre de mots exprimant le dégoût ; 6) le nombre de mots exprimant la surprise ; 7) le nombre de mots exprimant la peur. -Lexique basé sur l'information mutuelle : les attributs suivants ont été considérés pour ce lexique : 1) le nombre de mots positifs ; 2) le nombre de mots négatifs ; 3) le nombre de mots neutres ; 4) la somme de tous les scores positifs ; 5) la somme de tous les scores négatifs ; 6) la somme de tous les scores neutres -Les mots allongés : nombre de mots avec au moins 3 caractères répétés séquentiellement (par exemple : mdrrrr).

-Négation : présence ou l'absence d'un négateur dans le tweet.

Concernant la négation, nous avons aussi essayé d'implémenter la méthode proposée dans (Kiritchenko et al., 2014a) en rajoutant un suffixe aux mots qui se trouvent sous la portée d'un négateur. Les résultats de cette approche sont décrits dans la section 4.

Sélection d'attributs

Afin de sélectionner les attributs les plus discriminants pour chaque tâche, nous avons appliqué une étape de sélection d'attributs en mesurant le gain d'information de chaque attribut par rapport à la classe [START_REF] Mitchell | Machine learning[END_REF]. L'équation 5 présente la formule utilisée :

GainInf ormation(attribut, classe) = Entropie(classe) -Entropie(classe|attribut)

(5)

Après avoir calculé le gain d'information pour chaque attribut, nous ne gardons que ceux pour lesquels ce gain est supérieur à 0. Pour la tâche 1, 762 attributs ont été sélectionnés dont les plus discriminants sont ceux obtenus à partir du lexique de la PMI suivis par ceux obtenus à partir du lexique FEEL. Pour la tâche 2.1, 460 attributs ont été sélectionnés dont les plus discriminants sont des mots comme : menacer, contre, lien, etc. Pour la tâche 2.2, 75 attributs ont été sélectionnés dont les plus discriminants sont ceux issus du lexique d'émotions FEEL et des mots comme : menacer, espèce, lien, etc.

Classification

Pour nos trois tâches, nous employons des méthodes d'apprentissage supervisé. Nous avons choisi d'utiliser les machines à vecteur de support SVM (Support Vector Machine) avec la méthode SMO (Sequential Minimal Optimization) [START_REF] Platt | Advances in kernel methods. chapter Fast Training of Support Vector Machines Using Sequential Minimal Optimization[END_REF] implémenté dans Weka [START_REF] Hall | The weka data mining software : an update[END_REF]. D'après l'état de l'art, cet algorithme d'apprentissage s'est avéré efficace sur des tâches de catégorisation de textes et spécifiquement d'analyse de sentiments et d'émotions. Il est robuste sur les grands espaces de caractéristiques. En effet, notre modèle de classification exploite une variété de surface de forme, sémantique et des sentiments caractéristiques issus des lexiques.

Afin de choisir le meilleur paramètre de complexité « C » de SVM, nous avons effectué 20 validations croisées à 10 plis sur le corpus d'apprentissage. Pour chaque tâche, nous avons testé toutes les valeurs comprises entre 0,1 et 2,0 avec un pas de 0,1. Pour les trois tâches, la meilleure macro précision en validation croisée a été obtenue avec la valeur 0,4. Nous avons donc choisi cette valeur pour le paramètre de complexité « C » dans les expérimentations décrites ci-dessous.

Dans cette section, nous présentons les configurations choisies pour chaque tâche, les résultats obtenus et leurs discussions.

4.1 Tâche 1 : Détection de la polarité d'un tweet L'objectif de cette tâche est de déterminer la polarité d'un tweet. Il s'agit de prédire si un tweet donné est positif, négatif ou neutre. Les attributs utilisés pour cette tâche sont les suivants : les n-grammes de mots, les n-grammes de caractères, les patrons syntaxiques, le lexique de sentiments FEEL, le lexique de sentiments de la PMI, la ponctuation, les émoticônes, les mots allongés et la négation (attribut booléen). Le tableau 3 présente les macro-précisions de plusieurs expérimentations que nous avons effectué pour déterminer l'effet des attributs que nous avons construit et des étapes que nous avons effectué. Nous testons plusieurs configurations en rajoutant ou en enlevant des attributs ou des étapes.

Expérimentations

Macro-précision Baseline (prédire la classe majoritaire) 33,33% Système proposé 73,33% -Unigrammes de mots lemmatisés 42,39% (-30,94%) -N-grammes de caractères de longueur 5 et 6 73,46% (+0,13%) -Lexique de polarités FEEL 72,45% (-0,88%) -Lexique de polarités PMI 73,32% (-0,01%) -Patrons syntaxiques les plus fréquents 72,32%(-0,01%) -Négation (attribut booléen) 73,33% (-0,00%) -Ponctuation, émoticônes, hashtags et mots allongés 73,45% (+0,12%) -Sélection d'attributs 68,92% (-4,41%) -Prétraitements {Lemmatisation, lien, mail, tag} 70,71% (-2,62%) + Prétraitements {Argots, minuscules, mots allongés} 73,00% (-0,33%) + Négation (rajouter un suffixe) 73,15% (-0,18%) TABLE 3 -Macro-Précisions obtenues pour la tâche 1

Nous avons entraîné des classifieurs de types SVM sur un ensemble de 7 867 tweets, puis nous avons appliqué les modèles appris sur les 3 379 tweets qui nous ont été fournis pour la phase de test. La mesure choisie par les organisateurs du défi est la macro-précision. Comme baseline, nous considérons un système qui prédit toujours la classe majoritaire (ici la classe neutre). La macro-précision obtenue par un tel système est de 33,33%. Concernant le système que nous avons soumis au défi, la macro-précision obtenue est de 73,33%. Nous constatons que les attributs donnant le plus de gain sont les unigrammes de mots lemmatisés, ils fournissent un gain de plus de 30,94%. Par contre, le fait d'enlever les n-grammes caractères fait augmenter la macro-précision de 0,13%. Ces derniers ne permettent donc pas d'améliorer les résultats, voir ils les font même chuter un peu. Le lexique de polarités FEEL permet d'obtenir un gain de 0,88%. Concernant la négation en utilisant un attribut booléen, les patrons syntaxiques les plus fréquents et le lexique de polarités de la PMI, ces attributs n'ont pas vraiment eu d'impact sur les performances de notre système. La ponctuation, les émoticônes, le nombre de hashtags et de mots allongés font chuter la macro-précision du système de 0,12%, alors que la sélection d'attributs parait une étape cruciale puisqu'elle permet d'obtenir un gain de 4,41%. Les prétraitements que nous avons appliqués nous ont permis d'obtenir un gain non négligeable de 2,62%. Finalement, le fait de rajouter les prétraitements que nous avons décidé d'écarter et la méthode de traitement de la négation par ajout de suffixe fait chuter la macro-précision de 0,33% et de 0,18% respectivement.

Tâche 2.1 : Identification de la classe générique

Il s'agit ici d'identifier la classe générique de l'information exprimée dans un tweet. Les 4 classes génériques proposées dans le cadre de cette tâche sont : information, opinion, sentiment et émotion. Les attributs utilisés pour cette tâche sont les suivants : les n-grammes de mots, les n-grammes de caractères, la ponctuation, les émoticônes, les mots allongés et la négation. Le tableau 4 présente les macro-précisions de plusieurs expérimentations que nous avons effectué pour déterminer l'effet des attributs que nous avons construit et des étapes que nous avons proposé pour la tâche 2.1. Nous testons plusieurs configurations en rajoutant ou en enlevant des attributs ou des étapes.

Expérimentations

Macro-précision Baseline (prédire la classe majoritaire) 25,00% Système proposé 61,29% -Unigrammes de mots lemmatisés 11,23% (-50,06%) -N-grammes de caractères de longueur 5 et 6 61,45% (-0,16%) -Négation (attribut booléen) 61,32% (+0,03%) -Ponctuation, émoticônes, hashtags et mots allongés 61,17% (-0,12%) -Sélection d'attributs 55,67% (-5,62%) -Prétraitements {Lemmatisation, lien, mail, tag} 62,27% (+0,98%) + Prétraitements {Argots, minuscules, mots allongés} 62,16% (+0,87%) + Négation (rajouter un suffixe) 61,26% (-0,03%) TABLE 4 -Macro-Précisions obtenues pour la tâche 2.1

Nous avons entraîné des classifieurs de types SVM sur un ensemble de 6 784 tweets, puis nous avons appliqué nos modèles sur les 3 379 tweets qui nous ont été fournis après pour la phase de test. Nous utilisons la même baseline qui consiste à prédire la classe majoritaire ce qui donnera cette fois 25% de macro-précision (puisqu'il y a quatre classes). La macroprécision obtenue par le système soumis au défi est de 61,29% (meilleur résultat pour cette tâche). Cependant, le tableau 4 montre qu'il est possible d'améliorer encore ce résultat pour dépasser les 62%. Les unigrammes de mots lemmatisés donnent le meilleur gain (plus de 50%). Ensuite et comme pour la première tâche, en faisant une sélection d'attributs on augmente les résultats de plus de 5%, ce qui rend cette étape aussi cruciale pour la tâche 1 que pour la tâche 2.1. Les n-grammes de caractères donnent de leur côté un faible de gain de 0,16%. Par ailleurs, la négation par attribut booléen et par ajout de suffixe n'a pas vraiment d'impact sur la macro-précision. La ponctuation, les émoticônes, le hashtags et les mots allongés font chuter la macro-précision de 0,12%. Les prétraitements que nous avons choisi d'appliquer (à savoir : la lemmatisation, le remplacement des liens, des mails, et des tags) semblent être inadaptés pour cette tâche puisqu'en les appliquant nous perdons 0,92%, alors qu'en appliquant les autres prétraitements (remplacement des mots d'argots, la mise en minuscules et le traitement des mots allongés) qui permettent d'obtenir un gain de 0,87%. Finalement et comme pour les deux premières tâches, la méthode de négation en rajoutant un suffixe à tous les mots qui se trouvent sous la portée d'un négateur fait chuter légèrement la macro-précision du système (0,07%).

Conclusion

Nous avons présenté les systèmes soumis à la onzième édition du défi de fouille de texte (DEFT 2015). Les systèmes proposés sont basés sur des classifieurs de types SVM exploitant des traits d'ordre morphologique, syntaxique et sémantique. De plus, nous avons construit et exploité deux lexiques de sentiments et d'émotions. Le premier est un lexique de sentiments et d'émotions obtenu en traduisant semi-automatiquement le lexique NRC alors que le deuxième est un lexique de sentiments obtenu d'une manière automatique en utilisant le corpus d'apprentissage. Le système soumis pour la tâche 1 a obtenu une macro-précision de 73,33% à 0,27% du meilleur système. Le système que nous avons proposé pour la tâche 2.1 a obtenu une macro-précision de 61,29% soit la meilleure macro-précision pour cette tâche. Le système soumis pour la tâche 2.2 et appris sur les bonnes classes a obtenu une macro-précision de 31,72%. À noter que pour cette tâche, nous obtenons une macro-précision de 37% pour une de nos expérimentations (en enlevant la négation), alors que le meilleur système pour cette tâche soumis au défi a obtenu 34.68%. À travers les résultats obtenus, nous préconisons l'utilisation de SVM comme classifieur et des unigrammes comme attributs pour les trois tâches proposées dans ce défi. De plus, nous constatons que la méthode de traitement de la négation en rajoutant un suffixe à tous les mots qui se trouvent sous la portée d'un négateur ne donne pas de meilleures macro-précisions pour les trois tâches. On pourrait donc rejoindre la conclusion de [START_REF] Vincent | Construction et exploitation d'un corpus français pour l'analyse de sentiment[END_REF] qui montre que cette approche qui a été créée pour l'anglais tend à ne pas fonctionner aussi bien pour le français. Enfin, nous soulignons l'importance de la sélection d'attributs pour les tâches 1 et 2.1 qui améliorent les macro-précisions de plus de 4%.

Comme perspectives, nous prévoyons de tester plusieurs autres configurations que nous n'avons pas eu le temps de tester pour ce défi. Une perspective à court terme est de rajouter comme attributs les identifiants des clusters de Brown obtenus sur le corpus d'apprentissage [START_REF] Brown | Class-based n-gram models of natural language[END_REF][START_REF] Blitzer | Semi-supervised learning for natural language processing[END_REF]. Le Clustering de Brown permet de représenter des textes sous un format moins sparse, et cela en regroupant les mots selon leurs contextes. Nous avons déjà implémenté cette méthode mais la construction des attributs prenant beaucoup de temps, nous n'avons donc pas pu les intégrer durant la période de test qui a duré 3 jours seulement. Une deuxième perspective est d'estimer le seuil du gain d'information de l'algorithme de sélection d'attributs en validation croisée comme cela a été fait pour le paramètre de complexité de SVM. En effet, ces estimations peuvent se faire en même temps comme décrits dans [START_REF] Li | A global optimization approach to multi-polarity sentiment analysis[END_REF]. Pour pallier au problème des classes non équilibrées dans la tâche 2.2, nous comptons aussi tester une technique de sur-échantillonnage implémentée dans Weka et appelée SMOTE (Synthetic Minority Oversampling TEchnique) (et. al., 2002). Cette technique crée de nouvelles instances pour les classes minoritaires en se basant sur les instances existantes. Finalement, il serait intéressant de tester nos méthodes sur d'autres domaines que l'environnement et d'autres types de données que les tweets et d'essayer d'en faire des méthodes génériques pour le français.

  ; 7) le score positif le plus élevé ; 8) le score négatif le plus élevé ; 9) le score neutre le plus élevé ; 10) le score positif du dernier mot ; 11) le score négatif du dernier mot ; 12) le score neutre du dernier mot. -Ponctuation : deux attributs ont été considérés : 1) le nombre de séquences continues de points d'exclamation, de points d'interrogation et des deux ; 2) la présence ou l'absence d'un point d'exclamation ou d'un point d'interrogation dans le dernier terme dans n'importe quel position. -Émoticônes : présence ou non d'un émoticône dans le tweet.

TABLE 1 -

 1 Distribution des classes pour la tâche 1 et la tâche 2.1 sur le corpus d'apprentissage et de test. Les données ont été accessibles par les identifiants des tweets et un script de téléchargement (fourni par les organisateurs)

		Tâche 2.2
	Classes	Apprentissage # %	#	Test	%
	déplaisir	47	67,72	21		1,54
	dérangement	13	0,4	6		0,44
	mépris	176	5,53	75		5,51
	surprise négative	10	0,31	4		0,29
	peur	274	8,60	114		8,37
	colère	210	15,16	87		6,39
	ennui	4	0,12	2		0,14
	tristesse	36	1,13	16		1,17
	plaisir	35	1,10	15		1,10
	apaisement	9	0,28	5		0,36
	amour	8	0,25	4		0,29
	surprise positive	4	0,12	2		0,14
	satisfaction	73	2,29	32		2,35
	insatisfaction	9	0,28	5		0,36
	accord	154	4,83	67		4,92
	valorisation	1504	47,25	644 20,23
	désaccord	216	6,77	92		6,76
	dévalorisation	401	12,60	170 12,49
	Total	3183	100	1361	100

TABLE 2 -

 2 Distribution des classes pour la tâche 2.2 sur le corpus d'apprentissage et de test. Les données ont été accessibles par les identifiants des tweets et un script de téléchargement (fourni par les organisateurs) Les méthodes d'analyse de sentiments, d'opinions et d'émotions sont généralement basées sur des techniques statistiques, de traitement automatique du langage et d'apprentissage supervisé. Les plus performantes se basent souvent sur des systèmes supervisés qui utilisent des lexiques adaptés[START_REF] Nakov | Semeval-2013 task 2 : Sentiment analysis in twitter[END_REF][START_REF] Rosenthal | Semeval-2014 task 9 : Sentiment analysis in twitter[END_REF]. Dans ce travail, nous avons choisi d'utiliser les machines à vecteurs de support (SVM) tout en exploitant deux lexiques de sentiments (polarités) et d'émotions que nous avons construit au préalable. Le premier est un lexique de sentiments et d'émotions qui a été construit utilisant le corpus d'apprentissage fourni par l'équipe d'organisation de DEFT 2015. Nous avons ensuite construit des attributs spécifiques pour prendre en considération ces deux lexiques dans l'apprentissage de nos modèles de classification. En plus des attributs exploitant les lexiques, nous en avons testé d'autres : les unigrammes de mots, les n-grammes de caractères (de longueur 5 et 6), le nombre d'émoticônes, le nombre de mots en majuscules, le nombre de lettres répétées, le nombre de hashtags, la présence de négateurs et les patrons syntaxiques les plus fréquents. Enfin, une étape de sélection d'attributs a été appliquée pour sélectionner les attributs les plus pertinents pour chaque tâche en ne conservant que les attributs pour lesquels le gain d'information est positif.

	Le reste de l'article sera organisé comme suit : la section 2 décrit la création des ressources de sentiments et d'émotions
	utilisées. La section 3 présente les méthodes proposées : prétraitements, constructions et sélection d'attributs, classifica-
	tion. La section 4 présente les configurations choisies pour chaque tâche et les résultats obtenus. Enfin, la section 5 conclut
	et donne nos principales perspectives.
	2 Création des ressources
	Beaucoup de travaux liés à l'analyse de sentiments se basent sur des lexiques d'expressions de sentiments (liste de mots,
	phrases, idiomes, etc.). À ce titre, (Mohammad et al., 2013) ont souligné l'importance des lexiques dans la classification
	des tweets suivant leur polarité. En effet, d'auteurs ont observé une augmentation qui dépasse les 8% de leurs macro
	F-scores en utilisant des lexiques qu'ils ont construit de manière manuelle et automatique. Cependant, la majorité de ces
	ressources a été construite pour l'anglais et la polarité. Très peu de lexiques existent pour le français et quand ils existent,
	ils ne contiennent pas beaucoup de termes. Pour cela, nous avons créé nous-mêmes deux ressources pour le français :
	le lexique de sentiments et d'émotions FEEL (Abdaoui et al., 2014) et le lexique de sentiments basé sur l'information
	mutuelle

en traduisant le lexique anglais NRC

[START_REF] Mohammad | Emotions evoked by common words and phrases : Using mechanical turk to create an emotion lexicon[END_REF]

d'une manière semi-automatique, supervisée par un traducteur humain expérimenté. Ce lexique a été étendu en anglais (avant traduction) et en français (après traduction) via l'étude des synonymes et des antonymes. Le deuxième est un lexique de sentiments (polarités seulement) construit d'une manière automatique en

  4)où freq(w, {NomDeLaClasse)} est le nombre de fois où le mot w apparaît dans un tweet appartenant à {NomDeLaClasse}, freq(w) est le nombre d'apparitions du mot w dans le corpus, freq ({NomDeLaClasse)} est le nombre de tweets appartenant à la classe NomDeLaClasse et N est le nombre total de termes dans le corpus.

	3 Méthodes

Pour chacune de nos trois tâches, nous appliquons d'abord des prétraitements. Ensuite, nous construisons des attributs pertinents pour la tâche en question. Une fois les attributs construits, nous ne sélectionnons que les plus pertinents. Enfin, nous apprenons un modèle de classification sur le corpus d'apprentissage et nous l'appliquons sur le corpus de test. Chacune de ces étapes est détaillée dans cette section.

  lors du défi SemEval-2013 sur des tweets en langue anglaise en validations croisées sur le corpus d'apprentissage. Ensuite, nous les avons adaptés pour le français et nous en avons rajouté d'autres. Chaque tweet a donc été représenté par un sous ensemble des attributs suivants : -Unigrammes de mots : présence ou absence des mots lemmatisés dans le tweet. -Caractères n-grammes : présence ou absence des séquences continues de 5 et de 6 caractères. Nous n'avons sélectionné que les séquences les plus fréquentes par classe (celles qui apparaissent au moins 550 fois dans une seule classe). Ce seuil a été fixé par plusieurs validations croisées sur le corpus d'apprentissage. -Les patrons syntaxiques les plus fréquents : pour construire ces attributs, nous avons d'abord utilisé l'outil Tree-Tagger pour remplacer chaque mot par son étiquette morphosyntaxique. Ensuite, nous avons utilisé l'algorithme de (Fournier-Viger et al., 2008) pour l'extraction de motifs séquentiels fréquents. Nous en avons extrait les 1% les

plus fréquents pour chaque classe. Nous n'avons gardé que les patrons discriminants, fréquents dans une classe et pas dans les autres. Ces derniers ont été rajoutés comme attributs de type « booléen ». Chaque attribut prendra la valeur vraie si l'étiquetage morphosyntaxique du tweet correspond au patron syntaxique en question.

TABLE 5 -

 5 Il s'agit d'identifier la classe de l'opinion, sentiment ou émotion. Étant donné un tweet, il faudrait reconnaître l'opinion/sentiment/émotion principal(e) exprimé(e) explicitement dans ce tweet. Pour cela, 18 classes sont proposées : colère, peur, tristesse, dégoût, ennui, dérangement, déplaisir, surprise négative, apaisement, amour, plaisir, surprise positive, insatisfaction, satisfaction, accord, valorisation, désaccord et dévalorisation. Lors de notre soumission nous n'avons pas considérés ces classes-là, nous avons donc obtenu des macro-précisions très faibles. Nous présentons ici les résultats du même système soumis mais en considérant les bonnes classes. Les attributs utilisés pour cette tâche sont les suivants : les n-grammes de mots, les n-grammes de caractères, le lexique d'émotions FEEL, la ponctuation, les émoticônes, les mots allongés et la négation. Le tableau 5 présente les macro-précisions de plusieurs expérimentations que nous avons effectué pour déterminer l'effet des attributs que nous avons construit et des étapes que nous avons effectué pour la tâche 2.2. Nous testons plusieurs configurations en rajoutant ou en enlevant des attributs ou des étapes au système proposé.Nous avons entraîné des classifieurs de types SVM sur un ensemble de 3 162 tweets, puis nous avons appliqué nos modèles sur les 3 379 tweets qui nous ont été fournis après pour la phase de test. Nous utilisons la même baseline qui consiste à prédire la classe majoritaire ce qui donnera cette fois 5,56% de macro-précision (puisqu'il y a 18 classes). La macroprécision obtenue par le système soumis au défi et appris sur les bonnes classes est de 31,72%. Cependant, le tableau 5 montre qu'il est possible d'améliorer encore ce résultat pour dépasser les 37%. Encore une fois, les unigrammes de mots lemmatisés donnent le meilleur gain (25,72%). Ensuite, le lexique de polarités FEEL, la ponctuation, les émoticônes, le hashtags et les mots allongés n'ont pas d'impact sur les résultats. Par contre, lexique d'émotions FEEL (qui contient 7 émotions seulement) et la négation par attributs booléen ont considérablement diminué la macro-précision. Le lexique a Macro-Précisions obtenues pour la tâche 2.2 adaptés pour cette tâche puisqu'en les appliquant nous obtenons un gain 1,78%. Les autres prétraitements (remplacement des mots d'argots, la mise en minuscules et le traitement des mots allongés) permettent d'obtenir un gain de 4,21%.

	4.3 Tâche 2.2 : Identification de la classe spécifique de l'opinion, du sentiment ou de l'émotion

causé une perte de 2,66%, alors que la négation par attribut booléen a causé une perte de 5,28%. À l'opposé des deux tâches précédentes, la sélection d'attributs a causé une perte 0,66% pour la tâche 2.2. Par ailleurs, les prétraitements que nous avons choisis d'appliquer (à savoir : la lemmatisation, le remplacement des liens, des mails, et des tags) semblent être

https://www.mturk.com/mturk/welcome

Ce lexique est en téléchargement libre sur le lien : http://www.lirmm.fr/ abdaoui/FEEL.html


Mohamed Khalil

El Mahrsi

Romain Guigourès
email: ro-main.guigoures@orange.com

Fabrice Rossi
email: fabrice.rossi@univ-paris1.fr

Marc Boullé
email: marc.boulle@orange.com

Mohamed K El Mahrsi

Co-Clustering Network-Constrained Trajectory Data

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Monitoring traffic on road networks is generally handled using dedicated sensors that provide estimations of the number of vehicles traversing the road portion on which they are deployed. Due to their prohibitive installation and maintenance costs, the deployment of these sensors is mainly limited to the primary road network (i.e. highways and main arteries). Consequently, the road network's state reported using this kind of solutions is partial and incomplete which complicates the application of data mining tasks that aim to extract meaningful knowledge about flow dynamics and mobility patterns.

Thanks to the advances in the fields of telecommunication and geo-positioning, an alternative approach may consist in taking advantage of GPS logs collected on moving objects that are equipped with ad hoc devices (such as smartphones). These logs can be acquired through dedicated data acquisition campaigns (using probing vehicles, buses, taxis, etc.), through crowdsourcing mechanisms in which users contribute their own trajectories, etc. Trajectory data can thus be harvested on a large scale which helps provide a better coverage of the road network compared to sensor data.

Clustering is a widely used technique in exploratory data analysis. Given a set of observations, cluster analysis consists in partitioning these observations into groups (called clusters) in such fashion that objects belonging to the same group are more similar to each other (w.r.t. a given criterion) than to objects from other groups. Most prior work on trajectory clustering focused on the case of moving objects evolving freely in the euclidean space [START_REF] Kalnis | On discovering moving clusters in spatio-temporal data[END_REF], Benkert et al., 2006, Lee et al., 2007, Jeung et al., 2008]. Often in real applications, however, moving objects must comply with the existence of an underlying network (for instance, vehicles evolve in the road network, airplanes must remain in invisible but well defined air corridors, etc.). The topological constraints imposed by this network play a key role in determining the similarity between trajectories and should logically be accounted for during the clustering process. Clustering network-constrained trajectories gained in popularity only recently with the publication of work such as [START_REF] Kharrat | Clustering algorithm for network constraint trajectories[END_REF], Liu et al., 2008, Roh and Hwang, 2010], etc.

The insightful idea of using a graph-based approach to cluster trajectory data was first used in [START_REF] Guo | A graph-based approach to vehicle trajectory analysis[END_REF]. We built upon the premisses of this idea in [El Mahrsi and Rossi, 2012b] where we used a graph representation to model the similarity relationships between trajectories and clustered this similarity graph to extract clusters of trajectories that exhibit similar mobility patterns. This approach was extended in [El Mahrsi and Rossi, 2012a] and used to regroup similar road segments that can eventually be used to further enhance the interpretability of trajectory clusters. In the present work, we retain this idea of using a graph representation as we model the interactions between trajectories and road segments using a bipartite graph and we study two different approaches to clustering its vertices.

The remainder of this paper is organized as follows. Our data model and proposed approaches are presented in Sect. 2. Section 3 illustrates our experimental study where we demonstrate our propositions' capacity to highlight and discover interesting trajectory and road segment clusters. Related work is briefly discussed in Sect. 4. Finally, conclusions and future work are presented in Sect. 5.

Clustering Approaches

In the network-constrained case, trajectories are often modeled using a symbolic data model [START_REF] Kharrat | Clustering algorithm for network constraint trajectories[END_REF], Lou et al., 2009, Roh and Hwang, 2010]. Each trajectory T is represented as a series of succeeeding road segments (this is done by applying a map-matching algorithm, such as [START_REF] Lou | Mapmatching for low-sampling-rate gps trajectories[END_REF], to the original GPS logs). Therefore, two entities are eligible for applying clustering techniques: (i) trajectories, and (ii) road segments.

We model the data as a bipartite graph G = (T , S , E ). T = {T 1 , T 2 , ..., T n } is the dataset of trajectories, S = {s 1 , s 2 , ..., s m } is the set of all the road segments composing the road network that registered at least one traversal, and E is the set of edges modeling interactions between trajectories and road segments (i.e. an edge e exists between a trajectory T and a road segment s if and only if T visited s at least once). This representation is illustrated in Fig. 1 depicting five trajectories T 1 , T 2 , T 3 , T 4 , and T 5 interacting with eight road segments and the corresponding bipartite graph.

s 2 s 1 s 3 s 4 s 6 s 8 s 5 s 7 s 9 T 4 T 2 T 3 T 1 T 1 T 2 T 3 T 4 T 5 T 5
s 1 s 2 s 3 s 4 s 5 s 6 s 7 s 8

Fig. 1 A bipartite graph is used to model interactions between the trajectories and the road network's segments. Each trajectory and each road segment is represented as a vertex in the graph. Edges are created between each trajectory and the set of road segments it visited.

We will first attempt to project the bipartite graph G on both its trajectory vertices T and road segment vertices S and study clustering the resulting graphs separately (Sect. 2.1). Secondly, we will process G directly using a co-clustering approach (Sect. 2.2).

Clustering the Projected Trajectory and Segment Graphs

Our bipartite graph G is composed of two types of vertices, trajectory vertices and road segment vertices. We can project G on the set of trajectory vertices T which produces a new, simple graph G T = (T , E T , W T ) that represents similarity relationships between trajectories. In this setting, T stands for vertices representing trajectories, E T are edges indicating the presence of similarities between pairs of trajectories (an edge e T i ,T j exists between two trajectories T i and T j if they share at least one common road segment), and W T are weights assigned to edges based on the strength of the similarity between trajectories they connect. An example of a projected trajectory similarity graph is depicted in Fig. 2.

T 1 T 2 T 3 T 4 T 5
Similarity(T 1 , T 3 ) Fig. 2 The trajectory similarity graph resulting from the projection of the bipartite graph depicted in Fig. 1 on its trajectory vertices. Here, each trajectory is represented as a vertex and weighted edges inter-connect trajectories based on their similarity.

The most basic weighting strategy is to assign to each edge e T i ,T j a weight ω T i ,T j that is equal to the count of common road segments between the two trajectories T i and T j . However, the main drawback of this approach is that it completely neglects the spatial properties of road segments (for instance, a very short road segment and a lengthy one have equal contributions to the similarity). Therefore, we proposed a more sophisticated and spatially-aware weighting strategy in [El Mahrsi and Rossi, 2012b]. It is this strategy that we will continue to use here.

For each road segment s visited by a trajectory T , we calculate its contribution (w.r.t. this trajectory) based not only on its spatial length but also on the frequency of its appearance in the dataset. This contribution is basically an adaptation of tf-idf (term frequency -inverse document frequency) weighting widely used in information retrieval, modified to account for spatiality. The contribution w s,T of segment s to trajectory T is calculated according to Eq. (1).

w s,T = n s,T • length(s) ∑ s ∈T n s ,T • length(s ) • log |T | |{T i : s ∈ T i }| . (1)
n s,T is the number of times the trajectory T visited the road segment s (usually equal to 1), length(s) is the spatial length of the segment. |T |, the total number of trajectories in T , and |{T i : s ∈ T i }|, the number of trajectories that visited s. The second term in w s,T is used to penalize frequently-traveled road segments (with the intuition that the more a segment is traveled, the less it is relevant w.r.t. similarity evaluation and vice versa).

We evaluate the similarity between pairs of trajectories using a cosine similarity and we assign the weights in G T accordingly (2):

ω T i ,T j = ∑ s∈S w s,T i • w s,T j ∑ s∈S w 2 s,T i • ∑ s∈S w 2 s,T j . ( 2
)
By analogy, we can project the bipartite graph G on the set of road segment vertices S in which case we obtain a segment similarity graph G S = (S , E S , W S ). In this graph, a similarity edge e s i ,s j indicates that at least one trajectory visited both road segments s i and s j . Here again, it is totally feasible to assign edge weights based solely on the count of common trajectories, but instead we define a weighting technique based on trajectory relevance [El Mahrsi and Rossi, 2012a] similarly to what we did earlier when processing trajectories. The similarity between two road segments s i and s j is expressed as follows (3):

ω s i ,s j = ∑ T ∈T w T,s i • w T,s j ∑ T ∈T w 2 T,s i • ∑ T ∈T w 2 T,s j . (3)
With :

w T,s = n s,T ∑ T ∈T n s,T • log |S | |s ∈ S : s ∈ T | . ( 4
)
The first part of w T,s evaluates the "contribution" (or importance) of trajectory T to the road segment s by calculating the ratio between the number of visits n s,T made by T to s and the number of visits s received from all the trajectories in T . The second parts evaluates the overall relevance of T based on comparing the number of different segments it visited |s ∈ S : s ∈ T | to the total number of road segments |S |.

We propose to cluster the projected trajectory and segment graphs separately in order to discover trajectory clusters on one side and road segment clusters on the other. To do so, we chose to apply modularity-based community detection using an algorithm that implements the directives described in [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF]. This choice is mainly motivated by the fact that vertices in such similarity graphs are expected to have high degrees and modularity-based clustering is reputed to outshine other approaches in such settings. Nevertheless, we do not exclude the use of other graph clustering algorithms (e.g. spectral clustering [START_REF] Meila | Learning Segmentation by Random Walks[END_REF]) if these can yield better results.

The used algorithm produces a hierarchy of nested (trajectory or segment) clusters that are suitable for multi-level exploration where the user can start by inspecting a few, coarse clusters in order to quickly understand the general motion trends then proceed to exploring clusters of interest with higher levels of detail by means of successive refinements. Also, once the trajectory and segment partitions are found, they can either be analyzed separately or cross-compared and interpreted based on each other.

Given a dataset of n trajectories that travelled on a road network composed of m segments, the time complexity for clustering the trajectory graph is theoretically in O(n 3 ) whereas clustering road segments is done in O(m 3 ) [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF].

Direct Co-Clustering of the Bipartite Graph

We now propose to study clustering the bipartite graph G directly. To achieve this end, we apply a co-clustering approach to the graph's adjacency matrix. In the adjacency matrix, trajectories are represented in the rows whilst road segments are represented on the columns. The intersection of row i with column j indicates the number of times trajectory T i visited the road segment s j (1 ≤ i ≤ n and 1 ≤ j ≤ m). Co-clustering works by rearranging the rows and columns of the adjacency matrix in order to highlight blocs that have homogeneous density. These blocs are then used to derive two partitions simultaneously (one partition for trajectories and the other for road segments in our case). A co-clustering structure, that we refer to as M hereafter, is usually defined through a set of modeling parameters. Ours are described in Table 1. The objective of co-clustering algorithms is to infer the best partition of the bipartite graph. By applying such approaches, trajectories are regrouped if they travel along common road segments and, vice versa, road segments are clustered together if they are visited by the same trajectories. The main advantage of these techniques is that they do not require preprocessing nor do they require the definition of an "artificial" similarity between trajectories or between segments. Nonetheless, they do present the drawback of being computationally expensive.

We opt for the MODL [Boullé, 2011] approach to conduct the co-clustering of G . We made this choice because this approach (i) is non-parametric and does not require user intervention or fine-tuning, (ii) is easily scalable and can, consequently, be used to analyze large datasets, and (iii) was already and successfully applied to geo-tagged data [START_REF] Guigourès | A triclustering approach for time evolving graphs[END_REF]. In MODL, a quality criterion is defined according to a Maximum A Posteriori (MAP) approach (5):

M * = argmax M P(M )P(D|M ) . (5)
First, an a priori probability P(M ) is defined based on the data (denoted D). This probability tries to characterize each of the modeling parameters of the model M by assigning to each one of them a penalty (which corresponds to their minimal coding length, calculated based on descriptive statistics of the data). Next, the likelihood of the data given the data model P(D|M ) is defined. The likelihood measures the cost of re-encoding D with the parameters of M . Consequently, the most likely co-clustering model is the one that is most faithful to the original data (in other terms, the likelihood tends to favor relevant and informative structures). Retrieving the best co-clustering (i.e. the one optimizing the global criterion M * ) consists in realizing the best trade-off between conciseness and accuracy.

Since co-clustering problems are often NP-complete, the clustering is conducted using an agglomerative greedy heuristic. Initially, the trivial, most refined model is considered (this model contains only one trajectory and one road segment per cluster). Then, all cluster merging operations are evaluated and the best merge is applied (if it results in a decrease of the quality criterion). Once no more merging operations are possible, the result of the heuristic is refined using a post-optimization step in which some elements swap their cluster memberships. The whole process is encapsulated within a VNS (Variable Neighborhood Search, [START_REF] Hansen | Variable neighborhood search: Principles and applications[END_REF]) metaheuristic that restarts the algorithm several times with different random cluster initializations. Full details and a thorough evaluation of the MODL approach can be retrieved in [Boullé, 2011].

MODL has a complexity of

O(|E | |E | log(|E |))
where E indicates the total number of edges in the bipartite graph G (which, in our case, translates to the overall number of road segment traversals). This complexity, however, is only observed in the worst and very unlikely case where each trajectory in the dataset T visits each single road segment in the road network.

Experimental Study

In this section, we demonstrate how the proposed approaches can be used to discover and analyze motion patterns in road networks. Our experimental setting is described in Sect. 3.1 whereas results and their interpretation are presented in Sect. 3.2 and Sect. 3.3.

Experimental Setting

In order to test our propositions, we use synthetic datasets of labeled trajectories. These datasets are generated intentionally to contain trajectories that are supposed to form natural clusters using the following strategy. The space covered by the road network (represented by the minimum bounding rectangle regrouping all of its vertices) is divided into a grid of equally-sized rectangular cells (or zones). For each of the clusters to be generated, a zone is selected randomly and all of its contained vertices are chosen to play the role of departure points. Similarly, a second zone (different from the first) is also selected randomly and its vertices are used as arrival points. For each trajectory to be included in the cluster, a departure (resp. arrival) vertex is drawn randomly from the set of departure (resp. arrival) vertices and the trajectory is generated as the set of road segments forming the shortest path linking the two vertices (the shortest path calculation is based on travel time and takes into account the characteristics of the visited road segments such as speed limitations, etc.).

The number of trajectories in each cluster is fixed randomly in-between two minimum and maximum user-defined values. The data generation process is conceived in such fashion that interactions between clusters can occur (examples of interactions include clusters converging from different departure zones to a common arrival zone, inverted clusters where the departure zone of one cluster is the arrival zone of the other and vice versa, etc.).

Since this experimental study is intended to showcase how our approaches can contribute to discovering meaningful knowledge about mobility in the road network, we make do with a case study involving a small dataset composed of 85 trajectories. These trajectories are spread across five distinct clusters (depicted in Fig. 3) and visited 485 road segments in total. We designate these original clusters as "classes" hereafter in order to distinguish them from those that will be retrieved using the clustering algorithms. The dataset is generated using the Oldenburg road network's graph (originally provided with the Brinkhoff generator [Brinkhoff, 2002]) which is composed of 6105 vertices (i.e. road intersections) and 14070 directed edges (i.e. road segments).

Analysis of Trajectory Clusters

Applying modularity-based clustering to the projected trajectory similarity graph produces a partition containing three clusters (in contrast with the original five classes). This is mainly due to the fact that some classes interact considerably. Their interactions were not visible when labeling the classes individually during the data generation process. The clustering algorithm, however, was able to detect these interactions and regroup the trajectories accordingly.

Since the algorithm we apply is a hierarchical algorithm that produces a multilevel hierarchy of nested clusters, we can further refine the clusters in a given level by exploring their subsequent clusters. In the case of the dataset at hand, the second level reveals the existence of eight trajectory clusters. The confusion matrix between these clusters and the original classes is illustrated in Fig. 4(a). In this level, all the clusters contained in the partition are pure. Three of the original five classes were retrieved flawlessly whereas the two remaining clusters were further refined (class 1 was divided into three clusters and class 3 into two). This "over-partitioning" is legitimate and can be justified considering the variability of the trajectories contained in the concerned classes.

Co-clustering, on the other hand, directly retrieves a partition that is faithful to the original data (cf. Fig. 4(b)). Here again two original classes were over-partitioned and three classes were retrieved correctly. Since the results (w.r.t. trajectory clusters) of applying MODL directly to the bipartite graph resemble those obtained by modularitybased clustering of the projected trajectory graph, it is more logical to use the former since it contains no preprocessing contrary to the latter where similarity calculations need to be performed first. Co-clustering trajectory clusters Ground-truth clusters (b) Co-Clustering Fig. 4 Confusion matrices of the original classes (ground-truth clusters) in the data and the clusters discovered by applying (a) the modularity-based approach and (b) the MODL co-clustering approach (cells are color-coded based on the ratio of the ground-truth cluster they contain). The modularitybased approach yields an Adjusted Rand Index (ARI) of 0.849, whereas MODL yields a slightly higher (i.e. better) ARI value of 0.862.

Mutual Analysis of Trajectory and Segment Clusters

Let's now study the adjacency matrix of the original bipartite graph G . We reordered the rows and columns of the matrix in order to bring together trajectories and segments belonging to the same clusters (cf. Fig. 5). We observe in the case of the projected graphs (Fig. 5(a)) that road segments are regrouped together based on common trajectories without accounting for the traffic's volume. Therefore, road segments that are rarely visited can be attached to segments that are visited frequently. This translates, when looking at the adjacency matrix, into the presence of blocs with heterogeneous distributions in which some segments are travelled by all the trajectories in the cluster whereas others are only visited by a limited subset of trajectories. In co-clustering, on the other hand, segments are correlated based on usage which results in blocs of homogeneous densities (Fig. 5(b)). By inspecting trajectory clusters and road segment clusters simultaneously, it is possible to characterize road segments based on the roles they play in traffic.This makes it possible to identify hubs that are frequently travelled by multiple groups of vehicles transiting to different regions (Figure 6(a)), secondary roads (Figure 6(b)), and even rarely frequented alleys. Therefore, our methodology makes it possible to characterize the topological structure of the underlying road network based on trajectories contributing their usage information.

Mutual information is frequently-used in co-clustering to quantify the correlations between partitions of the studied variables. These are, in our case, trajectories and road segments. Mutual information is always positive. High values of this metric usually indicate that trajectory clusters visit rather exclusive and unique segment clusters. We use mutual information in our study to quantify the relationship between pairs of trajectory and segment clusters and their contribution to the model's mutual information. Given a cluster of trajectories c T and a cluster of road segments c S , the contribution of the pair to mutual information, denoted mi(c S , c T ), is calculated as follows (6).

Where P(c S , c T ) is the probability of a segment traversal to belong to a trajectory in c T and covering a road segment that belongs to c S , P(c S ) is the probability of visiting a segment belonging to c S , and P(c T ) is the probability of having a trajectory belonging to c T .

A positive contribution to mutual information indicates that the number of visits of trajectories in c T to road segments in c S is higher than what is expected in case the two clusters were completely independent one from the other. Vice versa, a negative contribution is an indicator that quantity of traffic w.r.t. is inferior to normal. Finally, a null contribution to mutual information indicate that traffic either conforms to what is expected or is very low.

Figure 7(b) presents the contribution to mutual information for each couple of co-clusters discovered in the dataset at hand. For instance, if we take the left, top-most co-cluster we can notice that the segments are exclusively travelled by members of a single trajectory cluster and that, vice versa, trajectories in this trajectory cluster travel almost uniquely on the members of this segment cluster. In this case, the trajectory cluster comprises 21.6% of the studied trajectories and the road segments cluster 17.3% of segments in the dataset. If we suppose that both clusters are independent, then we can expect no more than observing 21, 6% × 17.3% = 3.7% of the total road segment traversals to be originating from both clusters. Here, however, we observe that no less than 17.3% from the total traversals belong to this co-cluster which largely exceeds the expected traffic in case of unrelated and independent clusters. Notice that the mutual information contributes an information that is different from the frequency matrix. We can observe that some road segment clusters are significantly traversed by members belonging to multiple trajectory clusters. This behavior is quite characteristic of hubs that vehicles coming from different regions cross in order to attend different destinations. Some of these clusters have very small contrast w.r.t. mutual information which indicates that traffic on the hub is rather balanced.

Related Work

Approaches to trajectory clustering are mainly adaptations of existing algorithms to the case of trajectories. These include moving clusters [START_REF] Li | Clustering moving objects[END_REF], flock patterns [START_REF] Benkert | Reporting flock patterns[END_REF], convoy patterns [START_REF] Jeung | Convoy queries in spatio-temporal databases[END_REF], the TRACLUS partitionand-group framework [START_REF] Lee | Trajectory clustering: a partitionand-group framework[END_REF], etc. The aforementioned algorithms use euclidean-based similarities and distances and disregard the presence of an underlying network. Therefore, they can be used only in the case of unconstrained trajectories. The insightful idea of using a graph-based approach to cluster trajectory data was first introduced in [START_REF] Guo | A graph-based approach to vehicle trajectory analysis[END_REF]. The approach is applied to free moving trajectories and considers the latter as sets of GPS points. Unlike our graph-based approaches, the authors do not rely on an underlying network as the basis of similarity calculations.

The first attempt to study the similarity between network-constrained trajectories is reported in [START_REF] Hwang | Spatio-temporal similarity analysis between trajectories on road networks[END_REF]. The proposition requiers a priori knowledge of points of interest in the road network and cannot, consequently, be used in an unsupervised learning context. An extension of moving clusters to network-constrained trajectories is presented in [START_REF] Liu | Continuous clustering of moving objects in spatial networks[END_REF]. Roh et Hwang [START_REF] Roh | Nncluster: An efficient clustering algorithm for road network trajectories[END_REF] present a network-aware approach to clustering trajectories where the distance between trajectories in the road network is measured using shortest path calculations. A baseline algorithm, using agglomerative hierarchical clustering, as well as a more efficient algorithm, called NNCluster, are presented for the purpose of regrouping the network constrained trajectories. In [START_REF] Kharrat | Clustering algorithm for network constraint trajectories[END_REF], the authors describe an approach to discovering "dense paths" or sequences of frequently traveled segments in a road network. The approach is extended in [START_REF] Kharrat | Caractérisation de la densité de trafic et de son évolution à partir de trajectoires d'objets mobiles[END_REF] to study the temporal evolution of dense paths.

Our approaches differ from existing propositions on two key aspects. First, the majority of existing work use density-based algorithms that require fine-tuning of their parameter values and assume that trajectories in the same cluster have a rather homogeneous density (which is rarely the case as discussed in [START_REF] Roh | Nncluster: An efficient clustering algorithm for road network trajectories[END_REF]). In contrast, we opt for non-parametric algorithms that rely on robust and well defined clustering quality criteria. Secondly, existing approaches often use flat clustering, thus producing a unique level of clusters that can be overwhelming to analyse in the case of large datasets. Our propositions produce hierarchies of nested clusters that are suitable for multi-level exploration: the user can start with a small number of clusters to quickly understand the macro-organization of flow dynamics in the road network, then proceed to refining clusters of interest to reveal more details.

Conclusions

In this paper, we studied clustering network-constrained trajectory data from the angle of a bipartite graph clustering problem. We notably studied this problem from two different perspectives. At first, we considered the problem as a community detection problem conducted separately on two simple graphs (one depicting resemblances between trajectories and the other depicting similarities between road segments). Then we proceeded to co-cluster the bipartite graph directly to automatically retrieve clusters of interacting trajectories and road segments.

The main contribution of this work resides in its methodology of applying graphbased techniques to trajectory data in order to extract clusters describing mobility patterns in road networks. These clusters can be used by experts and road planners in conjunction with other data sources in order to understand trafic and driver behaviors. The applied clustering algorithms (modularity-based clustering used on the projected graphs and MODL used for co-clustering the bipartite graph) were essentially used to showcase and illustrate the interestingness of our problem formulation. As such, they can be replaced by other graph clustering and co-clustering approaches.

In future work, we will mainly focus on experimenting with the co-clustering technique on a larger scale (bigger datasets) as well as in the presence of noisy data.

Fig. 3

 3 Fig.3Original classes in the dataset. Some of the classes present natural interactions. For instance, classes 2 and 3 start from the same departure zone and travel together for a given portion then diverge to different arrival zones. They also interact with class 1 in the central portion of the road network.

Fig. 5

 5 Fig. 5 Crossed matrices of trajectory clusters (columns) and road segment clusters (rows) retrieved through (a) modularity-based clustering and (b) co-clustering.

Fig. 6

 6 Fig. 6 Example of road segment clusters.

  mi(c S , c T ) = P(c S , c T ) log P(c S , c T ) P(c S )P(c T ).

Fig. 7

 7 Fig. 7 Frequency and mutual information of the retrieved co-clusters.

Table 1

 1 Notations. : set of traversals of road segments in S by trajectories in T C E = C T ∩C S : co-clusters of trajectory and road segments

	Bipartite graph G	Co-clustering model M
	T : set of trajectories	C T : set of trajectory clusters
	S : set of road segments	C

S : set of road segment clusters E = T ∩ S