Keywords: Signaux sociaux, recherche d'information sociale, réseaux sociaux, propriétés sociales, modèle de tri, corrélation Social signals, social information retrieval, social networks, social properties, ranking model, correlation

Exploitation de signaux sociaux pour estimer la pertinence a priori d'une ressource

Ismail Badache, Mohand Boughanem

Institut de Recherche en Informatique de Toulouse, UMR 5505 CNRS, SIG 118 Route de Narbonne F-31062 Toulouse cedex 9 France {Ismail. Badache, Mohand.Boughanem}@irit.fr RÉSUMÉ. Dans cet article nous proposons une approche de recherche d'information (RI) qui prend en compte le contenu social associé à une ressource pour mesurer sa pertinence a priori vis-à-vis d'une requête. Nous démontrons comment ces caractéristiques, qui sont sous forme d'actions relevant d'activités sociales (signaux sociaux) tels que le nombre de "j'aime" et de "partage", peuvent être combinées pour quantifier des propriétés sociales telles que la popularité et la réputation. Nous proposons de modéliser ces propriétés comme des probabilités a priori que nous intégrons dans un modèle de langue. Nous avons évalué l'efficacité de notre approche sur la collection d'IMDb contenant 32706 documents et leurs caractéristiques sociales collectées sur plusieurs réseaux sociaux. Nos résultats expérimentaux sont très prometteurs et montrent l'intérêt de l'intégration des propriétés sociales dans un modèle de recherche pour améliorer la RI. ABSTRACT. In this paper we propose an information retrieval (IR) approach which takes into account the social content associated with a resource to measure its a priori relevance to a query. We show how these characteristics, which are of the form of actions (social signals) such as the number of "like" and "share", can be combined to quantify social properties such as popularity and reputation. We propose to model these properties as a priori probabilities that we integrate into a language model. We evaluated the effectiveness of our approach on the IMDb dataset containing 32706 documents and their social characteristics collected from several social networks. Our experimental results are very promising and show the interest of integrating social properties in search model to enhance IR.

Introduction

Les systèmes de recherche d'information (RI) visent à rechercher des documents pertinents en réponse à un besoin de l'utilisateur, habituellement exprimé par une requête. La plupart des modèles de recherche utilisent les statistiques des termes, telles que la fréquence du terme dans le document et dans la collection de documents. Outre ces facteurs, les modèles de RI sont souvent étendus avec d'autres sources d'évidence indépendantes de la requête qui mesurent l'importance (ou l'intérêt) a priori du document [START_REF] Craswell | Relevance weighting for query independent evidence[END_REF]. On y trouve par le nombre de liens entrants, la longueur d'un document [START_REF] Kraaij | The importance of prior probabilities for entry page search[END_REF] et le PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual Web search engine[END_REF].

Une des sources importantes que l'on peut également exploiter pour mesurer l'intérêt d'une page Web ou de manière générale une ressource, est le Web social. En effet, grâce aux outils proposés par le Web 2.0 les utilisateurs interagissent de plus en plus entre eux et/ou avec les ressources. Ces interactions, traduites par des annotations, des commentaires ou des votes sur des ressources, produisent de l'information sociale utile et intéressante pour caractériser une ressource, en termes de popularité, de réputation et de fraîcheur.

Dans cet article, nous proposons d'exploiter les signaux sociaux laissés par les utilisateurs sur les ressources pour mesurer la pertinence (l'intérêt) a priori d'une ressource. Cette connaissance a priori est combinée avec la pertinence thématique dans un modèle de langue qui prend en compte ces sources d'évidence. Les questions de recherche auxquelles nous souhaitons répondre dans cet article sont les suivantes : L'article est structuré de la façon suivante : nous présentons dans la section 2 un aperçu sur certains travaux connexes. Ensuite, nous détaillons notre approche sociale dans la section 3. La section 4 est consacrée à l'expérimentation effectuée sur une collection issue d'IMDb 1 . Enfin la section 5 conclut l'article et annonce des perspectives.

État de l'art

Dans cette section, nous présentons les travaux exploitant des sources d'évidence indépendantes de la requête pour mesurer la pertinence (l'importance) a priori d'une ressource.

L'une des sources d'évidence largement exploitée en RI est la structure des hyperliens. Un grand nombre de liens entrants dans un document indique que de nombreux documents considèrent le document en question important ou autoritaire. Les premiers algorithmes ayant exploités cette source d'évidence sont PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual Web search engine[END_REF] et HITS [START_REF] Kleinberg | Authoritative sources in a hyperlinked environment[END_REF]. Ils associent une valeur d'autorité à chaque page Web, cette valeur est d'autant plus forte que les documents qui pointent cette page possèdent eux aussi une valeur forte. Une autre source de connaissance a priori est le localisateur uniforme de ressource (URL). Chaque document sur le Web est identifié par une adresse URL qui se compose d'un nom du serveur, un chemin d'accès et un nom de fichier. [START_REF] Kraaij | The importance of prior probabilities for entry page search[END_REF] ont défini quatre types d'URL. L'évaluation sur la collection TREC-Web 2001 a montré que le fait que les pages d'entrée tendent à avoir des URL plus courtes que les autres documents peut être exploité avec succès par un algorithme de classement.

Certains travaux exploitent d'autres types de caractéristiques de document issues des réseaux sociaux. (Chelaru et al., 2012) étudient l'impact des signaux sociaux (aime, n'aime pas, commentaires, etc.) sur l'efficacité de la recherche sur "YouTube.com". Ils montrent que, bien que les critères de base basés sur la similarité de la requête avec le titre vidéo et les annotations sont efficaces pour la recherche vidéo, les critères sociaux sont également très utiles et améliorent le classement des résultats de la recherche pour 48% des requêtes. Ils ont utilisé "greedy feature selection algorithm" et six algorithmes d'apprentissage. Notre approche exploite le même principe, mais contrairement à l'approche ci-dessus, nous n'utilisons pas de techniques d'apprentissage, et nous exploitons davantage de signaux issus de réseaux sociaux multiples. (Karweg et al., 2011) proposent une approche combinant un score thématique et un score social basé sur deux facteurs : (a) premièrement, l'intensité d'engagement d'un utilisateur pendant une interaction avec un document, mesurée à partir du nombre de clics, nombre de votes, nombre d'enregistrement et recommandation; (b) deuxièmement, le degré de confiance mesuré à partir du graphe social pour chaque utilisateur selon sa popularité, en utilisant l'algorithme de PageRank. Ils montrent que les résultats de la recherche sociale sont plus pertinents. En particulier, ils diminuent le temps requis pour le processus de recherche et augmentent la satisfaction des utilisateurs. De même, [START_REF] Khodaei | Social-Textual Search and Ranking[END_REF] proposent une approche de classement fondé sur plusieurs paramètres sociaux combinés avec la pertinence textuelle classique. Ces facteurs sont l'importance des utilisateurs et des documents en fonction des relations entre les utilisateurs et les actions des utilisateurs (nombre de lectures d'un titre sur last.fr) effectuées sur les documents. Ils ont mené un ensemble d'expériences sur des données issues du site Internet de Radio en ligne last.fm. Les résultats expérimentaux ont été prometteurs et montrent une amélioration significative pour le classement socio-textuelle par rapport au textuel.

Par rapport à la RI sur Twitter, (Alonso et al., 2010) considèrent que la présence d'un lien URL est un critère important pour distinguer les tweet intéressants, avec plus de 80% de précision. Cependant, cette règle risque de considérer de nombreux tweet intéressants comme étant non intéressants, juste parce qu'ils ne contiennent pas de liens. (Yang et al., 2012) considèrent qu'un tweet intéressant doit attirer l'attention des utilisateurs au-delà du réseau propre à l'auteur (followers) et les pousse à retweeter. De même pour [START_REF] Hong | Predicting Popular Messages in Twitter[END_REF] qui qualifient le nombre de retweet comme une mesure de popularité, qui peut être exploitée au sein d'un classifieur pour prédire si de nouveaux messages seront retweetés à l'avenir et à quelle fréquence ? Cependant, des tweet banals (ex. rumeurs, sans intérêts, etc.) peuvent être très populaires tels que ceux concernant des célébrités, qui possèdent généralement un très grand nombre de followers. (Yang et al., 2012) modélisent Twitter comme un graphe de noeuds utilisateur et tweet reliés par des liens retweet et présentent une variante de l'algorithme HITS basée sur ce graphe pour produire un classement de tweet. (Pal et Counts, 2011) proposent un modèle d'identification des auteurs les plus influents dans le réseau de Twitter. Cette solution, utilisée en RI, est basée sur le modèle de mélange gaussien en exploitant des données sociales à partir de Twitter, telles que : le nombre de retweet, nombre de tweet conversationnel et le nombre de followers actifs par rapport au sujet d'intérêt.

Modèle de RI sociale

Notre approche de RI consiste à exploiter les signaux sociaux comme connaissances a priori pour définir des propriétés sociales à prendre en compte dans un modèle de recherche. Nous nous appuyons sur un modèle de langue pour combiner la pertinence thématique de la ressource vis-à-vis de la requête et son importance, modélisée elle aussi comme une probabilité a priori.

Notations

L'information sociale que nous exploitons dans le cadre de notre modèle peut être représentée par le quintuplet < U, R, A, T, RS > où U, R, A, T, RS sont des ensembles finis d'instances : Utilisateurs, Ressources, Actions, Temps et Réseaux sociaux. Temps : Il représente l'historique des actions, soit l'ensemble k moments (date) à laquelle une action ai a été produite. Un instant de temps t représente la date et l'heure (datetime) de l'action effectuée par un utilisateur u sur une ressource D.

Ressources

Réseaux sociaux : Il existe un ensemble de z réseau social. Chaque réseau social spécifique contient un ou plusieurs signaux sociaux spécifiques réalisés sur une ressource r.

Modèle de langue et probabilité a priori

Nous exploitons les modèles de langues pour mesurer la pertinence d'un document vis-à-vis d'une requête. Nous utilisons un modèle classique. La probabilité qu'une ressource D soit pertinente étant donnée une requête Q est estimée de la façon suivante en recourant au théorème de Bayes :

En supposant que l'ordre des documents est indépendant de P(Q) et les termes sont indépendants entre eux, on a : Où représente les mots de la requêtes Q.

L'estimation de , peut être effectuée en utilisant différents modèles (Jelineck Mercer, Dirichlet). Nous avons pour notre part utilisé le modèle JM : Donc : La probabilité correspond à la probabilité de tirer un mot au hasard dans la collection C, définit la probabilité de tirer un mot au hasard dans le document D et λ est le paramètre d'interpolation. Ce dernier s'estime habituellement comme une constante. Finalement, nous devrons estimer la probabilité a priori de pertinence d'un document . Nous notons que les modèles de langues fournissent une manière fondée théoriquement pour prendre en compte la notion de probabilités a priori d'un document .

Estimation des probabilités a priori

Pour estimer la probabilité a priori d'une ressource , nous avons étudié trois propriétés sociales : a) la popularité de la ressource; b) la réputation de la ressource et c) la fraîcheur de la ressource. Les deux premières propriétés sont quantifiées à partir du nombre d'occurrences d'une ou plusieurs actions spécifiques pour chacune des deux propriétés. Tandis que la fraîcheur est mesurée à partir des dates des dernières actions pour une ressource Web donnée.

Popularité de la ressource

La popularité d'une ressource Web est un phénomène social qui dicte quel est le plus connu dans le public. Grâce à l'influence des pairs, des ressources cibles peuvent rapidement monter dans la façon dont ils sont omniprésents dans la société. Donc, la popularité peut être estimée en fonction de l'intensité de partage de ces ressources entre les utilisateurs à travers les signaux sociaux. Nous considérons qu'une ressource est dite populaire si elle a été publiée et partagée par plusieurs utilisateurs dans plusieurs réseaux sociaux, au point de devenir très connue dans le grand public.

Réputation de la ressource

Nous supposons que si l'indice de popularité d'une ressource est important, cette ressource est relativement intéressante. Mais la popularité d'une ressource ne reflète pas forcément sa bonne ou mauvaise réputation. La réputation d'une ressource est une opinion sur cette ressource, généralement un résultat de l'évaluation sociale sur un ensemble de critères. Nous pensons que l'estimation de cette propriété peut être calculée à partir des actions relevant d'activités sociales qui portent un sens positif tel que le j'aime de -Document D1 :

-Document D2 :

Fraîcheur de la ressource

La fraîcheur d'une ressource est un facteur de pertinence important, exploité par plusieurs moteurs de recherche. La fraîcheur d'une information revient souvent à sa date de publication, mais nous ne pouvons pas dire qu'une information est obligatoirement obsolète parce qu'elle a été publiée il y a deux ans. Nous supposons qu'une ressource est dite fraiche, si des signaux sociaux très récents ont été associés à cette ressource. Pour cela, nous proposons cette définition de fraîcheur: « La date de la dernière interaction (ex. commentaire, mention, etc.) avec une ressource dans les réseaux sociaux, peut être utilisée pour mesurer la fraîcheur de l'information ».

Où :

représente le moment (date) à laquelle la dernière action ai du même type a été produite.

représente la récence d'une action ai dans la ressource , d'où nous estimons la fraîcheur de la ressource en elle-même.

estime le temps écoulé depuis la dernière action ai du même type pour une ressource . Nous notons que pour chaque action, la date est initialisée par défaut à : 01-01-1970 00:00:00. -Document D2 :

Exemple

-Document D3 : donc :

Combinaison des probabilités a priori

Dans notre cas, nous disposons de diverses sources d'informations sociales qui influence la probabilité a priori de pertinence. Cette probabilité est calculée par la combinaison de plusieurs propriétés sociales (Fraîcheur, Popularité et Réputation), dont ces dernières sont quantifiées par des caractéristiques sociales. De manière générale, le problème peut être formalisé comme suit [START_REF] Peng | Combination of document priors in Web information retrieval[END_REF]

Evaluation expérimentale

Afin de valider notre modèle, nous avons effectué une série d'expérimentations sur la collection IMDb (Internet Movie Database). En effet, nous faisons une étude sur l'apport des propriétés sociales au modèle de recherche basé uniquement sur le contenu. Dans nos expérimentations nous avons utilisé le modèle de RI décrit dans la section 3.2. Les probabilités a priori dans notre modèle soit P( ) sont définies dans la section 3.3, mais quantifiées de la façon présentée dans la section 4.2. Nous détaillons dans ce qui suit notre protocole d'expérimentation.

Description de la collection de test

Nous avons collecté 32706 documents en anglais extraits du site "imdb.com". Chaque document décrit un film, et est représenté par un ensemble de métadonnées, listées dans le Tableau 1. Chaque document a été indexé en fonction des mots clés se trouvant dans les balises ayant le statut indexé dans le Tableau 1. L'indexation est classique, utilisation de Porter et les mots vides sont supprimés. Les signaux sociaux ont été associés pour chaque propriété selon leur nature et signification, qui correspondent à la définition que nous avons donnée en section 3.2. Dans le tableau 3, nous remarquons que les signaux sociaux estimant la réputation portent des opinions positives, par exemple, marquer un lien d'une ressource par un utilisateur sur Delicious signifie que ce lien a été rajouté à sa liste de favoris. Pour le j'aime et +1, l'utilisateur clique sur ces deux boutons pour indiquer qu'il a apprécié le contenu de cette ressource. Donc la présence de cet ensemble de signaux sociaux dans une ressource augmente le degré de réputation de cette ressource. De même pour la popularité, les signaux sociaux exploités pour estimer cette dernière, nous permettent de savoir la position en termes de tendance et propagation de cette ressource sur le Web. Enfin, comme les dates des derniers signaux sociaux effectués ne sont pas disponibles, l'estimation de la fraîcheur est calculée à partir des dates des derniers partages et commentaires sur Facebook.

Le tableau 4 montre un exemple de signaux sociaux pour quelques documents. L'URL du document est donnée par la syntaxe suivante: www.imdb.com/title/{id}/

Tableau 5. Exemple de requêtes d'évaluation

Pour obtenir les jugements de pertinence des documents, nous avons impliqué 12 participants. Il y avait 6 femmes et 6 hommes, la tranche d'âge était entre 23 et 31 ans. Tous les participants étaient de la discipline informatique dont 4 sont des étudiants, 3 doctorant, 2 enseignants, et le reste sont des développeurs.

Nous avons demandé à chaque participant de choisir trois requêtes de notre ensemble de requêtes. Ensuite, nous avons attribué à chaque participant deux ou trois requêtes et leur avons demandé d'évaluer les 100 premiers documents affichés pour une requête donnée en utilisant une échelle d'évaluation à 3 points (nonpertinent, peu pertinent et pertinent). Nous notons que chaque requête est jugée par 3 utilisateurs. Pour éviter tout biais, aucun des signaux sociaux n'a été affiché avec les documents, mais toutes les métadonnées textuelles sont affichées pour faciliter la tâche de jugement.

Pour évaluer la performance de notre approche, nous calculons les métriques de précision, le nDCG (Jarvelin et [START_REF] Järvelin | Cumulated gain-based evaluation of information retrieval techniques[END_REF] et la MAP. Néanmoins, il est intéressant d'examiner combien d'accord entre les juges y a eu sur les jugements de pertinence. Dans les sciences sociales, une mesure commune d'un accord entre les juges représente la statistique de kappa [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF].

Résultats et discussion

Nous comparons notre approche avec deux modèles de base, exploitant uniquement le contenu du document, soient BM25 (Robertson et Walker, 1994) et le modèle de langue [START_REF] Hiemstra | A linguistically motivated probabilistic model of information retrieval[END_REF]. Nous avons utilisé le modèle de Hiemstra, comme modèle de base pour le calcul de la pertinence thématique. En ce qui concerne le paramétrage, nous avons attribué la valeur par défaut 0.85 pour le paramètre λ (voir formule 3). La valeur optimale du paramètre μ semble varier d'une collection à l'autre, bien que dans la plupart des cas elle est autour de 2000 [START_REF] Zhai | A study of smoothing methods for language models applied to information retrieval[END_REF], dans notre cas nous avons attribué la valeur 250 pour le paramètre de lissage . Les résultats obtenus sont présentés dans le tableau suivant : Le Tableau 6 récapitule les résultats de précision et de nDCG (Normalized Discounted Cumulative Gain) pour les 10 et 20 premiers documents retournés, ainsi que la MAP (Mean Average Precision). Nous remarquons dans tous les cas, avec la prise en compte des caractéristiques sociales, les résultats obtenus sont significativement meilleurs que ceux obtenus par les modèles de base. Nous constatons que la prise en compte de chaque signal social individuellement améliore les résultats, mais ils sont moins bons que ceux obtenus par la combinaison partielle/globale de ces caractéristiques sociales. Nous avons remarqué aussi que la mesure de l'accord Kappa [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF]) varie entre 0.69 et 0.86 pour l'ensemble des requêtes. La valeur moyenne de l'accord entre les évaluateurs est de 81.24%, ce qui correspond à un bon accord.

Nous constatons également que les meilleurs résultats sont obtenus avec la prise en compte des signaux sociaux combinés sous forme de propriétés qualitatives (popularité et réputation) et temporelle. Enfin la combinaison des trois propriétés est la configuration qui apporte les meilleurs résultats comparativement à toutes les autres configurations. La fraîcheur dans notre étude est vue par rapport à la récence des actions relevant d'activités sociales, le nombre d'action sur une ressource est lié à sa fraîcheur dans les réseaux sociaux, mais des ressources qui possèdent des signaux plus frais sont supposées être mieux classées. Enfin, on constate également que la prise en compte de la fraîcheur seule et combinée avec les autres signaux améliore également les résultats. Il est par ailleurs à noter que la fraîcheur dans notre cas est corrélée à la présence de signaux sociaux. Donc une question demeure posée, est-ce juste la présence du signal qui améliore la pertinence ou bien c'est la fraîcheur du signal qui contribue également à cette amélioration. Des analyses un peu plus approfondies sont nécessaires pour répondre cette question.

Analyse de corrélation des rangs

Selon une étude en Juin 2013 par Searchmetrics 2 , les signaux sociaux représentent 5 des 6 facteurs les plus fortement corrélés avec les résultats de recherche Google. En outre, l'enquête BrightEdge 3 publié en Janvier 2012, révèle que 84% des marketeurs de recherche disent que les signaux sociaux tels que le j'aime, tweet, et Google+1 seront soit plus important (53%) ou beaucoup plus important (31%) à leur référencement cette année par rapport à 2011 et 2012.

Nous avons effectué une analyse de corrélation des rangs en utilisant le coefficient de corrélation de Spearman [START_REF] Bolboaca | Pearson versus Spearman, Kendall's tau correlation analysis on structure-activity relationships of biologic active compounds[END_REF] entre les signaux sociaux des documents et le degré de pertinence. La figure 1 présente les valeurs de corrélations des rangs des signaux sociaux par rapport au degré de pertinence des documents. L'étude montre que le j'aime (0.29) a la plus forte corrélation, suivi par le nombre de commentaire (0.28). D'autres caractéristiques de haut rang incluent le nombre de partage (0.27) et le nombre de tweet (0.23).

Conclusion

Nous avons proposé dans cet article un modèle de recherche des ressources Web basé sur des propriétés sociales. Ces propriétés, considérées comme des probabilités a priori, ont été définies à partir des signaux sociaux. Le modèle proposé s'appuie sur un modèle de langue qui incorpore ces nouvelles connaissances a priori. L'évaluation expérimentale menée sur la collection IMDb montre que la prise en compte de ces propriétés sociales au sein d'un modèle de recherche textuel permet d'améliorer la qualité des résultats de recherche retournés.

En perspective, nous prévoyons de répondre à certaines limitations de l'étude en cours. Tout d'abord, nous envisageons d'estimer d'autres types de connaissances a priori et d'étudier la distribution de ces contenus sociaux dans les documents Web. Ensuite, nous comptons améliorer la manière de prendre en compte le temps dans le calcul de l'intérêt de la ressource. D'autres expérimentations à plus grande échelle sur d'autres types de collections sont également envisagées. Ceci étant même avec ces éléments simples, les premiers résultats obtenus nous encouragent à investir davantage cette piste.

  (a) Comment traduire les signaux sociaux en propriétés sociales ? (b) Quelles sont les propriétés sociales utiles pour évaluer la pertinence a priori d'une ressource? (c) Quel modèle théorique pour combiner la pertinence a priori d'une ressource et sa pertinence thématique ? (d) Impact des propriétés sociales dans les performances d'un système de recherche d'information ?

:

  Nous considérons une collection de n ressources. Une ressource D peut être un document traditionnel comme une page Web ou une ressource Web 2.0 comme une vidéo ou toute autre entité similaire. Nous supposons qu'une ressource D peut être représentée à la fois comme par un ensemble de mots-clés textuels, soit Dm, et comme un ensemble de caractéristiques sociales réalisées sur cette ressource, Ds={a1,a2,…am}. Actions : Il existe un ensemble de m actions (signaux sociaux) que les utilisateurs peuvent effectuer sur les ressources. Ces actions représentent la relation entre l'ensemble des utilisateurs et les ressources R. Par exemple sur Facebook, les utilisateurs peuvent effectuer les actions relevant d'activités sociales suivantes : publier, aimer, partager ou commenter.

Figure 1 .

 1 Figure 1. Corrélation des signaux sociauxLa figure 2 démontre que la combinaison des signaux sociaux selon leur nature pour définir les propriétés sociales (popularité, réputation et fraîcheur) augmente le taux de corrélation des rangs par rapport à la pertinence des documents.

Figure 2 .

 2 Figure 2. Corrélation des propriétés sociales

  Facebook ou le marquage d'une ressource comme favoris sur Delicious. En effet, la réputation d'une ressource est vue par rapport à son degré d'appréciation dans les réseaux sociaux.Pour la suite de l'article nous utilisons les notations suivantes :Nous définissons la probabilité a priori relative à la popularité/réputation d'une ressource par la formule suivante : c est une constante permettant de traduire le simple comptage la fonction Count() en distribution de probabilité. Cette constante peut être relative au document ou à une collection de documents ou encore à un type de signal. Pour nombre part, dans cet article, nous considérons cette constante relativement au sous-ensemble de documents renvoyés par une requête, elle est traduite par . Elle est de ce fait dépendante juste du type de signal considéré. En appliquant un lissage Dirichlet[START_REF] Zhai | A study of smoothing methods for language models applied to information retrieval[END_REF] on aura :

	-aux nombres de +1 et de J'aime. En appliquant la formule 5 pour les deux propriétés représente le nombre d'apparition d'une action spécifique dans
	la collection C. sociales on aura :
	-			représente le nombre total d'apparition de toutes les actions
		spécifiques	dans la collection C.
	Où	estime le nombre de fois qu'une action spécifique	apparait dans la
	collection C relativement à l'ensemble des actions de la collection.	est un
	paramètre appelé pseudo-fréquence. La formule est comme suit :
	Exemple : soient deux ressources D1 et D2 représentées par les signaux sociaux
	suivants :
				J'aime	+1	Partage Commentaire
	-	D1 désigne la propriété sociale estimée à partir d'un ensemble 155 78 49 250 d'actions spécifiques. D2 100 88 310 120
	-			représente la probabilité a priori relative à la propriété sociale x, 50000 20000 60000 30000
		où est la ressource représentée par ses caractéristiques sociales. 1300 1100 1500 1200
	-		représente le nombre d'apparition d'une action spécifique	dans
		la ressource .	désigne l'action exploitée pour mesurer la propriété x.
	-Nous estimons dans cet exemple la popularité représente le nombre total d'apparition d'une action par rapport aux nombres de Commentaire et de Partage, tant dis que la réputation est estimée par rapport
		spécifiques	dans toutes les ressources retournées	.

Signaux sociaux Somme Min Max Moyenne Facebook

  Nous l'avons mis dans la balise UGC (User Generated Content). Ce champ n'a pas été indexé. Le tableau 2 donne quelques statistiques sur le nombre de signaux sociaux dans la collection de documents.Afin de quantifier ces propriétés sociales, nous associons les signaux sociaux pour chaque propriété sociale comme suit (Tableau 3).

	4.2. Quantification des propriétés sociales
	Propriétés sociales	Signaux sociaux		Réseaux sociaux
	Champ		Description Nombre de « Commentaire »		Statut Facebook
	ID Popularité (PSoc) identifiant du film (le document). Nombre de « Tweet »			Twitter	-
	Title	le titre du film. Nombre de « Partage »		indexé LinkedIn, Facebook
	Year	l'année de sortie du film. Nombre de « +1 »			indexé Google+
	Rated Réputation (RSoc) classement des films selon le type du contenu. Nombre de « J'aime »	Facebook	-
	Released date de réalisation du film. Nombre de « Marque »			indexé Delicious
	Runtime durée du film. Fraîcheur (FSoc) Date de la dernière action			indexé Facebook
	Genre	genre de film (Action, Drame, etc.).			indexé
	Director le directeur du projet du film. Tableau 3. Liste des signaux sociaux exploités dans la quantification indexé
	Writer	les écrivains et les scénaristes du film.			indexé
	Actors	les acteurs principaux du film.			indexé
	Plot	résumé textuel du film.				indexé
	Poster	le lien URL de l'affiche du film.			-
	url	le lien URL qui mène à la source originale du document.	-
	UGC	Les différents signaux sociaux récupérés.
	Network J'aime	5056517	0	79693	154
			Partage	5778414	0	41618	176
		Commentaire	6717573	0	60081	205
	Twitter	Tweet	1097204	0	22954	33
	Google+	+1	139189	0	1368	4
	Delicious	Marque	32810	0	1033	1
	LinkedIn	Partage	57545	0	25215	1
	Tableau 2. Statistiques sur le nombre des signaux sociaux dans la collection

-

Tableau 1. Liste des différents champs d'un document dans la collection

A chaque document est également associé un certain nombre de signaux sociaux.

. Requêtes et jugement de pertinence

  Nous avons défini 25 requêtes, dont 20 requêtes sont issues de la collection INEX IMDb et 5 sont créés par nous-même. Le tableau suivant montre un exemple de requêtes:

	4.3Requête				Description
	"true story event movies"		recherche des films basés sur des évènements inspirés d'une histoire vraie.
	"christmas familly movies"		recherche des films familiaux de noël.
	"Martial arts sport movies documentary"	recherche de documentaires ou de films sur les arts martiaux ou toutes activités sportives.
	Réseaux		Facebook			Google+ Twitter Delicious LinkedIn
	Id	J'aime Partage Commentaire	+1	Tweet	Marque Partage
	tt1730728	30	11	2		0	0	0	0
	tt1922777 12363	11481	20614		238	2522	12	14
	tt1925050	0	2	7		0	0	0	0
	Tableau 4. Statistique sur le nombre des signaux sociaux de 3 documents


Ngoc Nguyen

Chan

Karn Yongsiriwit

Walid Gaaloul

Jan Mendling

Mining Event Logs to Assist the Development of Executable Process Variants

Keywords: process mining, business process design, neighborhood context, context matching

Developing process variants has been proven as a principle task to flexibly adapt a business process model to different markets. Contemporary research on variant development has focused on conceptual process models. However, process models do not always exist, even when process logs are available in information systems. Moreover, process logs are often more detailed than process models and reflect more closely to the behavior of the process. In this paper, we propose an activity recommendation approach that takes into account process logs for assisting the development of executable process variants. To this end, we define a notion of neighborhood context for each activity based on logs, which captures order constraints between activities with their occurrence frequency. The similarity of the neighborhood context between activities provides us then with a basis to recommend activities during the process of creating a new process model. The approach has been implemented as a plug-in for ProM. Furthermore, we conducted experiments on a large collection of process logs. The results indicate that our approach is feasible and applicable in real use cases.

Introduction

A process variant is an adjustment of a business process to flexibly adapt the business model to a specific context. Enterprises or organizations usually need to support many variants of the same process due to constraints from regulations, geography, religion, etc. For example, car rental companies, such as Hertz, Avis or Sixt, need to customize their reservation process to follows laws in a country or culture of a region. Suncorp, one of the largest Australian insurance group, has developed more than 30 different variants of the process of handling an insurance claim [START_REF] Van Der Aalst | Configurable services in the cloud: supporting variability while enabling cross-organizational process mining[END_REF].

In recent years, there have been many efforts on facilitating the development of business process variants such as (i) using available reference models to be individualized to fit the requirements [START_REF] Stephens | Supply chain operations reference model version 5.0: A new tool to improve supply chain efficiency and achieve best practice[END_REF][START_REF] Curran | SAP R/3 business blueprint: understanding the business process reference model[END_REF], or (ii) finding existing similar models to inspire the new process design [START_REF] Yan | Fast business process similarity search with feature-based similarity estimation[END_REF][START_REF] Aalst | Process equivalence: Comparing two process models based on observed behavior[END_REF][START_REF] Dijkman | Graph matching algorithms for business process model similarity search[END_REF]. However, the design with reference models is still labor-intensive, which is often the cause for error-prone and time-consuming design [START_REF] Aalst | Correctness ensuring process configuration: an approach based on partner synthesis[END_REF]. Meanwhile, recommending entire process models costs much computation time, especially when the number of activities is large. Large models are also not handy for a designer who needs to pick a specific piece of functionality from them. In this context, it is desirable to recommend only a small but well-selected set of activities in order to help the designer.

Prior research has emphasized the advantages of recommendations during process model design [START_REF] Hornung | Recommendation based process modeling support: Method and user experience[END_REF][START_REF] Chan | Composition context matching for web service recommendation[END_REF][START_REF] Chan | Context-based service recommendation for assisting business process design[END_REF][START_REF] Chan | Assisting business process design by activity neighborhood context matching[END_REF]. However, business process models do not always exist in large-scale information systems such as ERP, CRM, or workflow management systems [START_REF] Van Der Aalst | Workflow mining: Discovering process models from event logs[END_REF], even when process logs are available. Executable process models also require detailed technical activities to be recommended, while conceptual process models often describe processes in a coarse-granular way [START_REF] Baier | Bridging abstraction layers in process mining by automated matching of events and activities[END_REF]. Moreover, process models do not explicitly show the importance of activities or connection flows, which can be a valuable parameter to compute more precisely the similarity between two activities. Meanwhile, this information is recorded in process event logs in the form of traces and their frequency.

In this paper, we propose an approach that builds upon process event logs for making activity recommendations during the development of executable process variants. We examine the relation between activities based on their execution order and frequency as recorded in logs. We define the notion of a neighborhood context of an activity as a fragment of the log-based model that contains the considered activity and relations to its neighbors. Relations between activities and their occurrence frequency provide the basis for the computation of the similarity between activities. In the process design phase, this similarity is used to recommend activities which might be closely related to the one that has just been added to the model.

The rest of the paper is organized as follows. Section 2 presents an example that motivates our approach. Section 3 continues with the process model and the neighborhood context graph extracted from logs. Section 4 defines the recommendation approach. Section 5 presents the implementation and experimental results. Section 6 discusses related work before Section 7 concludes the paper.

Motivating example

Consider a process designer who is about to develop a new variant of a liability claim process of an insurance company (inspired from [START_REF] Rozinat | Discovering colored petri nets from event logs[END_REF]). She starts her work by either retrieving an existing process or quickly designing a new one based on her experiences (Fig. 1): first, some data related to the claim is registered (cf. activity A), and then a full check is performed (B). Afterwards, the claim will be evaluated (D), and then it is either rejected (F) or approved (E and G). Finally, the case is archived and closed (H ).

To develop a new variant, the designer may need recommendations for certain positions of the current process. Our approach assist her by providing recommended activities for at each selected position. For example, in Fig. 2, K is recommended for A, C is recommended for B and so on. These recommenda-tions possibly help her easily have new ideas to design a new process variant, for instance, as given in Fig. 3. Recommendations for each activity are made based on their similarity. The computation of this similarity can be based on process event logs even when a a-priori process model is not available.

To elaborate the steps to recommendations in our approach, we use the example of a liability claim process within an insurance company that was presented in [START_REF] Rozinat | Discovering colored petri nets from event logs[END_REF] and another example of a customer subscription process. Table 1 and Table 2 present the process event logs of these processes. Each process instance is recorded as a trace. Each trace is a sequence of activities, which presents their execution order within a process instance. In a trace, the following activity (activity on the right) is performed after the followed activity (activity on the left). For example, consider a trace σ = ABCD, activity B is performed after activity A and before activity C. The third column of Table 1 and Table 2 presents the repetition of a trace that was previously executed.

In the following, we present an approach to build log-based business process models based on process event logs. These models provide the basis for defining a notion of activity neighborhood context, which we utilize for computing the similarity between activities.

Exploiting activity neighborhood context from logs

In this section, we present the log-based business process and the neighborhood context that are captured from business process logs. We firstly present some definitions related to business process logs (section 3.1). Then, we present definitions of the log-based business process (section 3.2) and the activity neighborhood context (section 3.3).

Preliminaries

According to [START_REF] Van Der Aalst | Workflow mining: Discovering process models from event logs[END_REF] and [START_REF] Schonenberg | Supporting flexible processes through recommendations based on history[END_REF], a business process log is defined as follows.

Definition 1 (Log trace, business process log, L). Let A be a set of activities. A * denotes the set of finite sequences over A and σ = a 1 a 2 . . . a n ∈ A * is a log trace. L ∈ P(A * ) is a business process log 4 .

As explained in [START_REF] Van Der Aalst | Workflow mining: Discovering process models from event logs[END_REF][START_REF] Schonenberg | Supporting flexible processes through recommendations based on history[END_REF], a business process log does not consider the repetition of a trace. For example, in Table 1, L includes only traces 1, 2, 3, 6 and 7. Traces 4 and 5 are excluded by L as they repeat traces 2 and 1. In our approach, we extend Definition 1 to define the full business process log (see Definition 2) that includes all log traces. Definition 2 (Full business process log, L * ). A full business process log is the business process log that includes all executed traces. The full business log is denoted by L * , L * ∈ P * (A * ). L ⊆ L * .

For example, in Table 1, L * includes all traces from 1 to 7. In Table 2, L * includes all traces from 1 to 5, while L includes only trace 1 and 2.

Definition 3 (Log-based ordering relation, > L ). Let L be a business process log over A, i.e., L ∈ P

(A * ). Let a, b ∈ A. a > L b iff ∃σ = a 1 a 2 . . . a n , i ∈ {1, 2, . . . , n -1}: σ ∈ L ∧ a i = a ∧ a i+1 = b.
For example, from the logs given in Table 1, we have A > L B, A > L C, C > L D, B > L D, and so on.

Log-based business process

The sequence of activities in a log trace σ = a 1 a 2 . . . a n ∈ A * presents their ordering relations. A relation between an activity a i and its followed activity a i+1 in the trace σ, 1 ≤ i ≤ n -1 can be presented as a directed edge from a i to a i+1 . The activity relations in a business process log L can be presented as a weighted directed graph where the edge's weight presents the number of times that the edge was repeated in the log L. This graph is called log-based business process graph (Definition 4).

Definition 4 (Log-based business process graph).

A log business process graph is a weighted directed graph G L = (V L , E L , w) built from a business process log L * ∈ P * (A * ) where:

-V L = A = {a 1 , a 2 , . . . , a n }, -E L = {(a i , a j ) ∈ A × A : a i > L a j } ⊆ A × A, -w is a weight function from E L to N : w : E L -→ N (a i , a j ) → |a i > L a j | |a i > L a j | is number of times that a i > L a j comes about in the log L * w(a i , a j ) = 0 if ∄σ = a 1 a 2 . . . a n , k ∈ {1, 2, . . . , n -1} : a k = a i ∧ a k+1 = a j
For example, the log-based business process graphs of the event logs given in Table 1 and Table 2 are depicted in Fig. 4. The weight of each flow is the number of times that the flow is executed. It is emphasized by the arrow's thickness. The log-based graph presents the execution of a business process in reality, regardless its conceptual model. The weights of edges present their execution frequency which indicates the strength of relations between activities. In the following, we present our approach to build the neighborhood context of an activity based on these relations.

Log-based neighborhood context

We define the log-based neighborhood context as a directed labeled graph that presents the shortest path from an activity to its neighbors. Intuitively, the closeness between activities is presented by the paths connecting them. The shortest path between activities presents their closest relation. The log-based neighborhood context of an activity presents the best relations between the activity and its neighbors.

In a log-based neighborhood context graph, each vertex is associated to a number that indicates the shortest path length from it to the associated activity. Vertexes that have the same shortest path length are considered to be located on the same layer around the associated activity. Thus, we name the number associated to each activity in a neighborhood context graph layer number. The layer number of an activity a is denoted by l(a). The area limited between two adjacent layers is called zone. The edge connecting two vertexes in a neighborhood context graph belongs to a zone as the vertexes are on the same or adjacent layers. We assign to each edge a number, so-call zone number, which determines the zone that the edge belongs to.

The edge connecting a j , a k in the neighborhood context graph of an activity a i is assigned a zone number z(a j , a k ) = min(l(a j ), l(a k )) + 1. This means, if a j and a k are located on two adjacent layers, the edge (a j , a k ) will belongs to the zone limited by l(a j ) and l(a k ). In the case that a j and a k are located on the same layer, the edge connecting them belongs to the outer zone of their layer, which is limited by layers l(a j ) and l(a j ) + 1.

Definition 5 (Activity neighborhood context graph). The neighborhood context graph of an activity a i , denoted by G C (a i ), is an extension of the log-based graph G L = (V L , E L , w) with vertex layer numbers and edge zone numbers. The layer number of an vertex a j , denoted by l(a j ) G C (ai) , is the shortest path length from a j to a i and the zone number of an edge (a j , a k ), denoted by z(a j , a k ) G C (ai) , has value min(l(a j ) G C (ai) , l(a k ) G C (ai) ) + 1:

1. l(a j ) G C (ai) = ShortestP athLength(a j , a i ), 2. z(a j , a k ) G C (ai) = min(l(a j ) G C (ai) , l(a k ) G C (ai) ) + 1, a j > L a k ∨ a k > L a j .
For example, the neighborhood context graphs of activity D and J in Fig. 4 are depicted in Fig. 5.

6 (k th -neighbor). a is the k th -neighbor of b, iff l(a) G C (b) = k. Set of k th -neighbors (k ≥ 1) of an activity a i is denoted by N k (a i ). N k (a i ) = {a j : l(a j ) G C (ai) = k}.
For example, in Fig. 4a,

N 1 (A) = {B, C}, N 2 (A) = {D}, N 3 (A) = {F, E, G}, N 1 (D) = {C, B, F, E, G}, N 2 (D) = {A, H}, N 3 (D) = ∅,
and so on.

Activity recommendation based on neighborhood context matching

The layer number and the zone number in a neighborhood context graph present the closeness between activities, while the weights of edges in the log-based graph present the strength of their relations. In this section, we detail our approach with log-based neighborhood context matching and activity recommendation.

Neighborhood context matching

To compute the matching between two neighborhood contexts, we (1) compute the matching of their edges in each zone, (2) multiply this matching with a zone-weight value and (3) sum up the matching in all zones.

We apply the vector space model (VSM) to compute the matching of edges in each zone of two neighborhood context graphs. VSM is a common technique used in Information Retrieval to compute the similarity between two items. It presents items in vectors and compute their similarity based on the cosine of the angle between the two corresponding vectors. In our approach, we present each zone as a vector of which elements are edges and values are their corresponding weights. Then, we align elements that connect the same activities in the same layers. Next, we present these vectors in the same space by filling 0 values in corresponding positions of the unaligned elements. Finally, we compute the cosine value of these two zone-vectors.

Particularly, in the first zone, we match the edges that connect the two associated activities to the same activities in the first layer. To formalize our computation, we define the two associated activities as root activities and name them r 0 .

Concretely, assume that P p and P q are two log-based business processes constructed from event logs L p and L q . Let A p , A q be sets of activities of P p and P q respectively. We compute the similarity between activities a ∈ A p and b ∈ A q by applying VSM as following.

Let E k Pp (a) and E k Pq (b) be sets of edges in k th -zone of a ∈ P p and b ∈ P q respectively. Let --→ e(a), --→ e(b) be corresponding zone vectors.

E k Pp (a) = {(x, y) : z(x, y) = k, x, y ∈ A p } = {(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x m , y m )} --→ e(a) = (w(x 1 , y 1 ), w(x 2 , y 2 ), . . . , w(x m , y m )) E k Pq (b) = {(e, f ) : z(e, f ) = k, e, f ∈ A q } = {(e 1 , f 1 ), (e 2 , f 2 ), . . . , (e n , f n )} --→ e(b) = (w(e 1 , f 1 ), w(e 2 , f 2 ), . . . , w(e n , f n )) Let N k-1 c (a, b) and N k c (a, b
) be the sets of common neighbors of a and b on layers k -1 and k, k > 0. We have:

N k-1 c (a, b) = N k-1 Pp (a) ∩ N k-1 Pq (b) N k c (a, b) = N k Pp (a) ∩ N k Pq (b)
As we define the two associated activities as root activities and name them r, we have:

N 0 Pp (a) = a = r 0 , N 0 Pq (b) = b = r 0 and N 0 c (a, b) = r 0 .
Let E k c be the set of common edges of a and b in k th -zone.

E k c = {(r, t) : (r ∈ N k-1 c (a, b), t ∈ N k c (a, b)|r > Lp t ∧ r > Lq t) ∪(r ∈ N k c (a, b), t ∈ N k-1 c (a, b)|r > Lp t ∧ r > Lq t)} = {(r 1 , t 1 ), (r 2 , t 2 ), . . . , (r m , t m )}

Let

---→ e c (a), --→ e c (b) be vectors of weights of these common edges. ---→ e c (a) = (w(r 1 , t 1 ), w(r 2 , t 2 ), . . . , w(r z , t z )), (r i , t

i ) ∈ E L (A p ), 1 ≤ i ≤ z --→ e c (b) = (w(r 1 , t 1 ), w(r 2 , t 2 ), . . . , w(r z , t z )), (r i , t i ) ∈ E L (A q ), 1 ≤ i ≤ z
By applying VSM, the similarity between a and b in the k th zone is given by Equation. 1.

M k (a, b) = ---→ e c (a) • --→ e c (b) | --→ e(a)| × | -- e(b)| (1)
For example, we have: the common neighbors of D and J in the 1 st -layer are N 1 c (D, J) = {F, G, B}. So, ---→ e c (D) = (w(D, F ), w(D, G), w(B, D)) = (3, 3, 4), ---→ e c (J) = (w(J, F ), w(J, G), w(B, J)) = (3, 2, 5) and their matching in the 1 st -zone is:

M 1 (D, J) = 3 × 3 + 3 × 2 + 4 × 5 √ 3 2 + 1 2 + 3 2 + 3 2 + 4 2 × √ 3 2 + 2 2 + 5 2 = 0.86
In the 2 nd -zone, we have the common edges of these two context graphs are: (F, G) and (G, H). So, their matching in this zone is:

M 2 (D, J) = 3 × 3 + 1 × 2 √ 3 2 + 4 2 + 3 2 + 3 2 + 1 2 + 1 2 + 3 2 × √ 5 2 + 3 2 + 2 2 = 0.24
The behavior of an activity is strongly reflected by the connections to its closet neighbors. Therefore, we propose to consider a zone weight in our matching. Concretely, as the zone-weight has to have greater values in smaller k th connection zone, we propose to assign the zone-weight a value computed by a polynomial function which is w z j = k + 1j k , where j is the zone number (1 ≤ j ≤ k), k is the number of considered zones around an associated activity. The closest zone to the associated activity has a weight 1 and the farthest zone has a weight 1 k . The final matching formula improved with the zone weight consideration is given in Equation 2.

M * (a, b) = 2 k + 1 × k i=1 k + 1 -i k × M i (a, b) (2)
For example, the matching between the neighborhood contexts of D and J (in 2 zones) with zone weights is:

M * (D, J) = 2 3 × (M 1 (D, J) + 1 2 × M 2 (D, J)) = 2 3 × (0.86 + 1 2 × 0.24) = 0.65

Activity recommendation

The neighborhood context graph presents the interactions between the associated activity and its neighbors in layers. It can infer the behavior of the associated activity. Therefore, the matching between neighborhood context graphs exposes the similarity between the associated activities. In our approach, the higher the matching value is, the more similar the activities are. Basically, the steps to make recommendations based on log-based neighborhood context matching are:

1. We represent the business execution logs in a log-based graph. This graph contains relations between activities and their weight values. 2. For each activity in the log-based graph, we build a neighborhood context graph which contains the closet relations between the associated activity and its neighbors. In a neighborhood context graph, activities are presented in layers and relations between them are presented in zones. 3. We compute the matching between neighborhood context graphs using vector space model. This matching presents the similar between two corresponding activities in terms of relations to their neighbors. 4. Finally, for a selected activity, we sort other activities in descending order of similarity and pick up top-n activities for recommendation.

Computational complexity

In our approach, only the connection flows connecting common neighbors in two adjacent layers are taken into account for the matching computation. So, by using queues (data structure) to store the common neighbors and track them from the nearest layers to the furthest layers, we avoid the redundant checking of unrelated neighbors. On the other hand, the number of activities as well as the number of common neighbors in a log-based business process are not great5 , our algorithm can run fast in computing the neighborhood context matching of two activities.

The worst case of this algorithm's computation time is

O(n A × n P × n × k),
where n A is the number of activities, n P is the number of business processes, n is the maximum number of common activities located on a layer and k is the number of considered layers. The worst case only happens when all the business processes in the system are entirely matched. In addition, the performance of the algorithm can be improved by processing the neighborhood context matching periodically off-line.

Implementation and experiments

To validate our approach, we implement a tool that generates recommendations based on business process logs. We also perform experiments on a large public dataset shared by the IBM Business Integration Technologies (BIT) team. Details of our implementation (section 5.1) and experiments (section 5.2) are presented as follows.

Implementation

Fig. 6: A screen shot of the log-based activity recommendation application

We implemented an activity recommendation plug-in and integrated it into ProM. This plug-in interacts with either a database or log files to retrieve recommendations for each selected activity in the ProM interface. This application6 was developed to validate our approach as a proof of concept.

The screen-shot of our application is shown in Fig. 6. It includes of 8 areas. Areas 1 and 4 allow selecting event log resources, which can be either from a database or a log files directory. The designer selects a working process in area 2 and specifies a zone number to be considered by the algorithm in area 3. The working process is shown in area 5. The designer can select an activity in the working process to obtain recommendations. Area 6 shows the top-5 recommended activities without zone-weight in the computation. Meanwhile, area 7 shows the top-10 recommended activities with zone-weight consideration. If the designer selects a recommended activity in area 6 or 7, this activity and its involved process will be shown in area 8 (the selected activity is highlighted).

Experiments

A big challenge of our approach is the availability of real business process logs. We attempted to search and contact other research groups for both public and private logs. However, process event logs are not published or they are not under a disclosure agreement. There are very few logs that are shared for the competition of the BPI challenge7 . But they are not usable in our approach as they are just logs of one business process while we need logs of several different processes.

We performed experiments on logs generated from real business processes. Data of these processes were shared by the IBM Business Integration Technologies (BIT) team. This dataset includes 735 different processes in Petri net Markup Language (PNML) format. These processes are designed for insurance, banking, customer relationship, as well as construction and automotive supply chain domains [START_REF] Fahland | Instantaneous soundness checking of industrial business process models[END_REF].

We transformed the collected business process models from PNML format to the Colored Petri Net (CPN) format. Then, we used CPN Tools8 to load the transformed process models to generate process event logs, which are resulted in XES files. Finally, these log files were imported by our application, which is a ProM plugin, to display the log-based business process graphs, compute the similarity between activities and show recommendations (as presented in Fig. 6). Details of the log-based dataset is given in Table 3. We perform two experiments to evaluate the feasibility and the accuracy of our approach. In the first experiment, we vary the k th -zone values from 1 to 5 and make statistics on the number of recommended activities for each selected activities. Fig. 7 shows the percentage of activities that have at least 1 recommended activity with the similarity value is greater than 0, 0.5 and 0.8. Concretely, we obtained that more than 76.56% activities that have at least one similarity value greater than 0 with k varies from 1 to 5. With k = 1, we obtained 53.68% activities with similarity value greater than 0.5 and 23.31% activities with similarity value greater than 0.8. These results show that our approach can provide recommendations for a majority activities as we can retrieve similar activities for more than 3/4 number of activities in average. It means that our approach is feasible and can be applied in real use-cases.

Min. Max
In the second experiment, we evaluate the accuracy of our approach based on Precision and Recall metrics. As our approach takes into account neighborhood contexts instead of activity identifiers, we consider activity identifiers as groundtruth data in computing Precision and Recall. Concretely, consider a selected activity a in a log-based business process P . Assume that a appears in n logbased business processes. The recommendations for this selected position consist of l activities, in which t(t ≤ l) activities are a. Precision and Recall of these recommendations are given by Equation 3.

P recision = t l ; Recall = t n (3)
The primary objective of the experiment is to retrieve a small share of activities that are likely irrelevant (high precision). It is of secondary importance to retrieve the full range of potentially relevant activities (moderate recall) in order to avoid the designer being overwhelmed.

In our experiment, we computed the Precision and Recall with l (number of activities recommended for each selected activity) equal to 1, 4, 7 and 10. We performed the experiment with k th -zone=1 and on activities that appear in at least 2, 5, 7 and 10 different business processes. 8 shows that we obtained good Precision values (from 0.42 to 0.59) in case of recommending 1 activity for each selected activity. These values decrease when we increase the number of recommended activities. On the other hand, activities that appear in more processes will have greater Precision values. It also shows that the Recall values increase when l (or top-N) changes from 1 to 10. This means that we can retrieve more relevant activities when the number of recommended activities increases. The highest Recall value in our experiment is 0.264 when l=10.

Fig. 9 shows the average Precision and Recall values of our approach with different k th -zone values. It shows that our approach achieved much better results than an approach that generates recommendations randomly (in average, 8.6 times greater the Precision value and 17.4 times greater the Recall value).

The Precision and Recall values showed that our approach retrieve not only the right activities but also new relevant activities for each selected position and the number of new activities increases when the number of recommended activities increases. These results showed that our approach can be applied in real use-cases as we can provide the designer the flexibility in using existing process fragments or designing new process variants.

Related work

Computing the similarity of two process models first requires the definition of a mapping between the activities using automatic matching techniques [START_REF] Ehrig | Measuring similarity between semantic business process models[END_REF]. Principles for matching process models have been integrated in the ICoP framework [START_REF] Weidlich | The icop framework: identification of correspondences between process models[END_REF] and extended with semantic matching techniques [START_REF] Leopold | Probabilistic optimization of semantic process model matching[END_REF]. Applications in the area of supporting process model design adopt such semantic techniques, as for instance the approach based on the process descriptor space [START_REF] Lincoln | Machine-assisted design of business process models using descriptor space analysis[END_REF] and the recommendation approach reported in [START_REF] Hornung | Recommendation based process modeling support: Method and user experience[END_REF]. Approaches to harmonize structure [START_REF] Polyvyanyy | Structuring acyclic process models[END_REF] and labels [START_REF] Leopold | On the refactoring of activity labels in business process models[END_REF] were also proposed. Service recommendation [START_REF] Chan | Web services recommendation based on user's behavior[END_REF][START_REF] Chan | A web service recommender system using vector space model and latent semantic indexing[END_REF] can be also applied in the context of activity recommendation. Behavioral abstractions such as trace adjacency [START_REF] Bae | Development of distance measures for process mining, discovery and integration[END_REF][START_REF] Zha | A workflow net similarity measure based on transition adjacency relations[END_REF] and weak order relations [START_REF] Eshuis | Structural matching of bpel processes[END_REF][START_REF] Weidlich | Efficient consistency measurement based on behavioral profiles of process models[END_REF] provide a means to compare process behavior [START_REF] Dijkman | Graph matching algorithms for business process model similarity search[END_REF][START_REF] Kunze | Metric trees for efficient similarity search in large process model repositories[END_REF][START_REF] Dijkman | A short survey on process model similarity[END_REF]. These notions are applied, e.g., for identifying connections between actions [START_REF] Smirnov | Action patterns in business process model repositories[END_REF] comparable to our notion of activity neighborhood. Our approach builds on this observation to make recommendations for executable processes. In addition, we focus on process fragments instead of the entire model. We recommend activities instead of process models and we do not face the computational complexity problem.

In our previous work [START_REF] Chan | Composition context matching for web service recommendation[END_REF][START_REF] Chan | Context-based service recommendation for assisting business process design[END_REF][START_REF] Chan | Assisting business process design by activity neighborhood context matching[END_REF], we exploited activity relations in process models and we did not take into account the occurrence frequency of activities. In this work, we realize that knowledge from process logs can be also utilized for process design by applying process mining techniques. Different techniques have been defined for automatically discovering whole models from logs, e.g. [START_REF] Van Der Aalst | Workflow mining: Discovering process models from event logs[END_REF][START_REF] Maggi | Efficient discovery of understandable declarative process models from event logs[END_REF][START_REF] Engel | Mining interorganizational business process models from edi messages: A case study from the automotive sector[END_REF]. The automatic matching between event logs and process models is discussed in [START_REF] Baier | Bridging abstraction layers in process mining by automated matching of events and activities[END_REF] showing that logs on the execution level are often much more detailed than models. The challenge of process mining is the observation that process models often turn out to be overwhelmingly complex, so-called spaghetti models [START_REF] Van Der Aalst | Process Mining -Discovery, Conformance and Enhancement of Business Processes[END_REF]. The approach reported in this paper helps to present correlations between activities in a context-specific way, which allows us to hide the complexity of the behavior. Hidden knowledge in process event logs are discovered for assisting business process design. In this way, we complement log-based recommendation approaches to support process designers at runtime [START_REF] Barba | User recommendations for the optimized execution of business processes[END_REF] or at configuration time [START_REF] Buijs | Mining configurable process models from collections of event logs[END_REF].

In this paper, we addressed the challenge of supporting the designer during the act of modeling, even in cases where no comparable process models exist. We present an approach that effectively utilizes knowledge extracted from business process logs for recommending activities. This approach is based on a notion of activity neighborhood and a corresponding calculation of similarity. The approach has been implemented as a plug-in for ProM and evaluated using generated log data of 735 processes from practice.

In future work, we aim to extend the similarity calculation with other properties of an activity such as descriptions, actors, resources and dependencies. We also plan to integrate our neighborhood matching technique with a specific query language to help to retrieve activities that have similar contexts based on a requested activity context.

  Fig. 1: Initial design

Fig. 4 :

 4 Fig. 4: Log-based business process graphs

Fig. 5 :

 5 Fig. 5: Neighborhood context graphs of the given event logs Definition6 (k th -neighbor). a is the k th -neighbor of b, iff l(a) G C (b) = k. Set of k th -neighbors (k ≥ 1) of an activity a i is denoted by N k (a i ). N k (a i ) = {a j : l(a j ) G C (ai) = k}.

Fig. 7 :

 7 Fig.7: Percentage of activities that have at least one recommended activity with the similarity value greater than 0, 0.5 and 0.8.

Fig. 8 :

 8 Fig. 8: Precision and Recall values of activities that are occurrence in at least 2, 5, 7 and 10 different processes, k th -zone=1 and l is equal to 1, 4, 7 and 10

Fig. 9 :

 9 Fig. 9: Average Precision and Recall values with different zone layers Fig.8shows that we obtained good Precision values (from 0.42 to 0.59) in case of recommending 1 activity for each selected activity. These values decrease when we increase the number of recommended activities. On the other hand, activities that appear in more processes will have greater Precision values. It also shows that the Recall

Table 1 :

 1

Event logs of the liability claim process (

[START_REF] Rozinat | Discovering colored petri nets from event logs[END_REF]

)

Table 2 :

 2 Event logs of a customer subscription process

Table 3 :

 3 Details of the dataset in XES format

zone number Precison and Recall values

	0.500
	0.100 0.200 0.300 0.400					Our approach Precision Random case Precision Our approach Recall Random case Recall
	0.000	5	4	3	2	1
			k-

On making statistics on the public dataset used in our experiment, we have that in average, there are 11.36 services in a business process (section 5)

published at: http://www-inf.it-sudparis.eu/SIMBAD/tools/LogRec/

http://www.win.tue.nl/bpi/

CPN Tools is an application to generate synthetic process event logs from models described in CPN format. It is available at: http://cpntools.org/


Ngoc Nguyen

Chan

Walid Gaaloul

Querying Services Based on Composition Context

Finding suitable services to be composed in a service-based business process is always a big challenge. In this paper, we present a query language that addresses this challenge by exploiting relations between services in process models. Concretely, we define the composition context of a service as a process fragment around it. We match composition contexts to compute the similarity between services. Finally, we conduct the query based on this computed similarity and flexibly added constraints. Our proposed query helps to retrieve services that have similar composition context with the queried service. It can be applied in process design or execution phase. We perform experiments on a large dataset of real process models. Experimental results show that our approach is feasible and efficient.

I. INTRODUCTION

Services have been developed as loosely-coupled applications that can be composed in service-based processes to achieve different business goals. Designing service-based business process is a crucial task that enables companies to sketch out their business, preview the process in real time execution, determines opportunities and risks involved in their business [START_REF] Van Der Aalst | Business process management: A survey[END_REF], [START_REF] Van Der Aalst | Business process management: A personal view[END_REF]. The importance of process design involves many frameworks and applications developed to facilitate this task. Most of recent efforts attempt to analyze business process topology, such as [START_REF] Beeri | Monitoring business processes with queries[END_REF], [START_REF] Deutch | Querying structural and behavioral properties of business processes[END_REF], [START_REF] Awad | Semantic querying of business process models[END_REF], [START_REF] Sakr | A framework for querying graph-based business process models[END_REF], to assist process designer by finding business processes that are similar to an ongoing designed one.

However, finding similar processes is not always helpful as the process designer may have difficulty to be inspired by large-scale, complex processes. Moreover, in some circumstances, process designer needs to find services instead of whole business processes. For example, a process designer may want to find suitable services to plug into some specific positions to complete his design (see Fig. 1a). In another case, he may want to find alternatives of a service to replace it in case of failure (see Fig. 1b). Fig. 1: Finding services to be composed in a business process

In this paper, we present an approach that assist process designers by finding services that are similar to a selected service's position in an ongoing designed process. We propose and develop a query language as a tool to search for similar services. We take existing process models as input in order to learn from the past design, not to reinvent the wheel. We exploit the knowledge acquired for previous designed process to infer service similarity. Concretely, similarity between services is computed based on their composition context, which is constructed based on relations between services in existing process models.

By providing a query language and focusing on service composition context, the objective of our approach is twofold: (i) to propose a new approach to compute the similarity of component services in services-based processes based on their composition context and (ii) to provide a useful query tool for service selection. Our approach does not only help to facilitate process design but also can improve the availability of services by identifying alternatives of services in order to replace them in case of failure.

Our paper is organized as follows. The next section elaborates our approach to compute the similarity between services based on their composition context. Section III presents our proposed query. Experiments are shown in section IV. We present the related work in section V and conclude our work in section VI.

II. SERVICE SIMILARITY BASED ON COMPOSITION

CONTEXT

This section elaborates our approach to compute the similarity between two services based on their composition context. To illustrate our approach, we assume that a process designer is designing a train reservation process. Fig. 2 shows the incomplete process and the designer is looking for suitable services to plug into the missing position (a x ). We also assume that there exists a flight reservation process (Fig. 3) in the repository of designed processes. We demonstrate in the following the computation of similarity between service 'Request credit card Info.' (a 6 ) and the queried service (a x ).

A. Preliminaries

In our work, terminal events (start events, end events) are considered as terminal services. We define a connection element as either a connecting object (e.g. sequence, message flow), or a gateway, (e.g. AND-split, OR-split, etc.), or an intermediate event (e.g. error message, message-catching, etc.).

Let A P be the set of services and C P be the set of connection elements in a process P . Definition II.1 (next relation) Let e i , e j ∈ A P ∪C P . A next relation from e i to e j , denoted by e i → P e j , indicates that e j situates right after e i in P .

Definition II.2 (connection flow)

A connection flow from a i to a j , a i , a j ∈ A P , denoted by aj ai f P , is a sequence of connection elements c 1 , c 2 , . . . , c n ∈ C P that satisfies:

a i → P c 1 , c 1 → P c 2 , . . . , c n-1 → P c n , c n → P a j . aj ai f P ∈ C * P , C * P is the set of sequences of connection elements in P .
For example, in Fig. 3, the connection flow from s 2 to a 5 or from a 5 to a 2 is 'flow-transition'; the connection flow from a 2 to e 3 is 'event-based-gateway''message-catching'; the connection flow from a 2 to a 7 is 'event-based-gateway''messagecatching''parallel-split' and so on. Definition II.3 (connection path) A connection path from a i to a j , denoted by aj ai P P , is a sequence of services a 1 , a 2 , . . . , a k where a 1 = a i , a k = a j and ∃(

at+1 at f P ∈ C * P ∨ at at+1 f P ∈ C * P ) ∀1 ≤ t ≤ k -1.

Definition II.4 (connection path length)

The length of a connection path The shortest connection path between a i and a j , denoted by aj ai S P , is the connection path between them that has the minimum connection path length.

For example, in Figure 3, the shortest connection path from a 5 to a 7 is a 5 a 2 a 7 and its length is 2.

Definition II.6 (k th -layer neighbor) a j is a k th -layer neighbor of a i in a process P iff ∃ aj ai P P : L( aj ai P P ) = k. The set of k th -layer neighbors of a service a i is denoted by N k P (a i ). N 0 P (a i ) = {a i }. For example in Fig. 3, s 2 and a 2 are the 1 st -layer neighbors of a 5 ; a 5 , e 3 , a 7 and a 6 are the 1 st -layer neighbors of a 2 ; a 7 is one of the 2 nd -layer neighbors of a 5 and so on.

As the distance from a service a i to its k th -layer neighbors is k, we can imagine that the k th -layer neighbors of a service a i are located on a latent circle whose center is a i and k is the radius. We call this latent circle a connection layer and the area limited by two adjacent latent circles a connection zone. Connection layers and connection zones of a service are numbered. A connection flow connecting two (k -1) th -layer neighbors, or a (k-1) th -layer neighbor to a k th -layer neighbor is called a k th -zone flow (Definition II.7).

Definition II.7 (k th -zone flow)

av au f P is a k th -zone flow of a i iff ∃ av au f P : (a u , a v ∈ N k-1 P (a i )) ∨ (a u ∈ N k-1 P (a i ) ∧ a v ∈ N k P (a i )) ∨ (a v ∈ N k-1 P (a i ) ∧ a u ∈ N k P (a i )).
The set of all k th -zone flows of a service a i ∈ P is denoted by Z k P (a i ). Z 0 P (a i ) = ∅ and |Z k P (a i )| is the number of connection flows in the k th connection zone of a i .

For example in Fig. 3, the connection from a 2 to a 7 is a 2 ndzone flow of a 5 while the connection from a 7 to a 3 is one of its 3 rd -zone flows. |Z 2 P2 (a 5 )| = 3 as in the 2 nd -zone of a 5 , there are three connection flows, which are from a 2 to e 3 , a 7 and a 6 .

B. Service composition context

Intuitively, the connection paths between two services in a service-based process present their relation in term of closeness. The longer the connection path is, the weaker their relation is and the shortest connection path between two services presents their best relation. To illustrate the best relations of a service to other services in a service-based process, we define the composition context graph (formally defined in Definition II.8) which presents all the shortest paths from a service to others.

Each service in a service-based process has a composition context graph. Each vertex in this graph is associated to a number which indicates the shortest path length of the connection path to the associated service. The vertices that have the same distance to the associated service are located on the same layer around the associated service. We name the number associated to each service the layer number. The area limited between two adjacent layers is called zone. The edge connecting two vertexes in a composition context graph belongs to a zone. We assign to each edge in the composition context graph a number, so-called zone number, which determines the zone that the edge belongs to. l 1m =ml 2m =ml 5m =ml 6m =ml 7m =ml 7 m=ml 8 m=ml 9 m=ml 15 m=ml 16 m'flowGtransition' l 3m =ml 4m =ml 10m =m'eventGbasedGgateway''messageGcatching' l 11m =ml 12m =m'eventGbasedGgateway''messageGcatching''parallel' l 13m =ml 14m =m'synchronization' a 1m :mSearchmtrains a 2m :mPresentmalternatives Fig. 4: Composition context graphs of a x (in Fig. 2) and a 6 (in Fig. 3)

Definition II.8 (Composition context graph)

The composition context graph of a service a x ∈ P , denoted by G ax P = (V ax P , E ax P , L ax P ), is a labeled directed graph. V ax P is a set of vertexes associated to their layer numbers; E ax P is a set of edges associated to their zone numbers; and L ax P is a set of edge labels in G ax P . V ax P , E ax P , and L ax P are defined as: ) where V ax P1 = {(a x , 0), (a 2 , 1), (a 3 , 1), (a 1 , 2), (e 1 , 2), (a 4 , 2), (s 1 , 3), (e 2 , 3)}; E ax P1 ={((a 2 , a x ), 1), ((a x , a 3 ), 1), ((a 2 , e 1 ), 2), ((a 1 , a 2 ), 2), ((a 3 , a 4 ), 2), ((s 1 , a 1 ), 3), ((a 4 , e 2 ), 3)}; L ax P1 = L P1 = {((s 1 , a 1 ), 'flow-transition'), ((a 1 , a 2 ), 'flow-transition'), ((a 2 , e 1 ),'event-based-gateway''message-catching'), ((a 2 , a x ), 'event-based-gateway''message-catching'), ((a x , a 3 ), 'flowtransition'), ((a 3 , a 4 ), 'flow-transition'), ((a 4 , e 2 ), 'flowtransition')}. This composition context graph and the composition context graph a 6 in Fig. 3 are depicted in Fig. 4.

• V ax P = {(a i , L( ax ai S P )) : a i ∈ V P } • E ax P = {((a i ,

C. Composition context graph matching

In this section, we present our approach to compute the matching between two composition contexts. Concretely, we match all connection flows that belong to the same connection zone and have the same ending services. Particularly, for the first zone, we match the connection flows connecting the associated services to the same services in the first layer.

1) Connection flow matching:

We propose to apply Levenshtein distance (LD for short) [START_REF] Levenshtein | Binary Codes Capable of Correcting Deletions, Insertions and Reversals[END_REF] to compute the matching between connection flows. In information theory, the LD is a metric for measuring the difference between two sequences of characters. The LD is defined as the minimum number of edits needed to transform one sequence of characters into the other, with the allowable edit operations being insertion, deletion, or substitution of a single element.In our approach, we consider each connection element as a character and present a connection flow as a sequence of characters. Then, the similarity between two connection flows are inferred by the similarity between corresponding sequences of characters.

Concretely, given two connection flows

aj ai f P1 = c 1 c 2 . . . c n and ay ax f P2 = c ′ 1 c ′ 2 .
. . c ′ m , the pattern matching between them is computed by Equation 1.

M ( aj ai f P1 , ay ax f P2 ) = 1 - LD( aj ai f P1 , ay ax f P2 ) M ax(n, m) (1)
In our example, we have

M ( a2 a1 f P1 , a2 a5 f P2 ) = M ('flow- transition', 'flow-transition') =1; M p ( ax a2 f P1 , a6 a2 f P2 ) = M ('event-based-gateway''message-caching',
'event-basedgateway' 'message-caching''parallel') = 0.67 and so on.

2) Context matching:

To compute the composition context matching between two services, we propose to sum up the matching of the connection flows in the two contexts. There are two cases to consider: matching in the first zone and matching in other zones. In the first zone, we match the connection flows that connect the two associated services and same services in the first layer. In other zones, we match the connection flows that connect the same services. For example, to compute the context matching between a x and a 6 (Figure 4), we will match

( ax a2 f P1 , a6 a2 f P2 ), ( a3 ax f P1 , a3 a6 f P2 ), ( e1 a2 f P1 , e3 a2 f P2 ), ( a4 a3 f P1 , a4 a3 f P2 ) and ( e2 a4 f P1 , e4 a4 f P2 ).
Besides, the consumption context of a service is strongly reflected by the connection flows to its closest neighbors while the interactions with other neighbors in the further layers do not heavily reflect its consumption context. Therefore, we propose to assign a weight (w t ) for each t th connection zone, so called zone-weight and integrate this weight into the similarity computation. Since the zone-weight has to have greater values in smaller t th connection zone, we propose the zone-weight a value computed by a polynomial function which

is w t = k + 1 -t k
, where t is the zone number (1 ≤ t ≤ k) and k is the number of considered zones around the service. Then, the composition contexts matching between G ai P1 and G aj P2 within k zones, denoted by MW k (G ai P1 , G aj P2 ), is given by Equation 2.

MW k (G a i P 1 , G a j P 2 ) = 2 k + 1 × k t=1 k + 1 -t k × av au f P 1 ∈Z t P 1 an am f P 2 ∈Z t P 2
MF t ( av au fP 1 , an am fP 2 )

|Z t P 1 (ai)| (2)
where:

MF t ( av au fP 1 , an am fP 2 ) =              M ( av au fP 1 , an am fP 2 ) if        t = 1, (au = am) ∨ (av = an) ∨(au = av ∧ am = an) t = 1, (au = am ∧ av = an) 0 other cases
For example, the service context matching between a x and a 6 (Figure . 4) computed by Equation 2 is:

MW 3 (G ax P 1 , G a 6 P 2 ) = 2 3 + 1 × ( 3 3 × M ( ax a 2 fP 1 , a 6 a 2 fP 2 ) + M ( a 3 ax fP 1 , a 3 a 6 fP 2 ) 2 + 2 3 × M ( e 1 a 2 fP 1 , e 3 a 2 fP 2 ) + M ( a 4 a 3 fP 1 , a 4 a 3 fP 2 ) 3 + 1 3 × Mp( e 2 a 4 fP 1 , e 4 a 4 fP 2 ) 2 ) = 2 4 × ( 0.66 + 0 2 + 2 3 × 1 + 1 3 + 1 3 × 1 2 ) = 0.47
Similarity between services is inferred by their composition context matching. Based on this similarity, we build a query which assist process designer to search for similar services. This query is presented in the next section.

III. QUERYING SERVICES IN SERVICE-BASED PROCESSES

In this section, we present a query language that is used to find similar services for a selected position in a servicebased process based on the composition context matching. We present the query language in section III-A and its execution in section III-B.

A. Query's grammar

The query language in our approach consists of three parameters, which are: an associated service, connection constraints, and a radius. The associated service is the service whose composition context is taken into account to match with other contexts. Connection constrains are services or connection flows to be included/excluded to filter the query's results. The radius is the number of connection layers taken into account for the composition context matching. It specifies the largeness of the considered composition contexts.

We present our proposed query's grammar using the Extended Backus-Naur Form 1 . We use ';' to separate the input parameters; '(' and ')' to separate query's constrains; '<' and '>' to group services or connection flows; '[' and ']' to separate a connection flow and its ending services. We use '+' and '-' signs to include/exclude constraints; and '|' sign for multiple choice operator. Details of the grammar are presented in Table I The query grammar is explained as follows:

= 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z'; 11. DigitNotZero ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';
• The query is defined in line 1 with three parameters separated by ':'. The constraint is optional. It can be defined to filter the query result. It can also be eliminated if we want to execute only the composition context matching without filtering. • In line 2, the service identifier is defined as a string of characters or digits. It has to start by a character. • In line 3, we define constraints. A constraint can be an included/excluded service or connection flow. It can also include different items and operators. Operators in a constraint can be OR, INCLUDE, EXCLUDE. We use '|', '+' and '-' to specify these operators. Consequently, we define a constraint as a 'Term' or another constraint with '|' operator. • In line 4 we define a 'Term' as an 'Item' or another constraint with the '+' and '-' operators. • The 'Item' is defined in line 5. It can be a service or a connection flow that is included/excluded in the query. It can also be another constraint which is grouped by '(' and ')'. Definitions in line 3, 4 and 5 allow specifying a constraint with multiple services, connection flows, operations and grouped conditions. • In line 6, we define a connection flow which is presented within '<' and '>' signs. It includes a string of connection elements that connects two services. 1 the EBNF is originally developed by Niklaus Wirth [START_REF] Wirth | What can we do about the unnecessary diversity of notation for syntactic definitions?[END_REF] and the EBNF standard is adopted by ISO, no. ISO/IEC 14977

• The string of connection elements is defined in line 7. It includes at least a connection element which is defined in line 8. • In line 9, we define the radius as a natural number greater than 0. • Finally, lines 10, 11, 12 define literal characters and digits.

For example, during the design of train reservation process (Fig. 2), if the process designer wants to find services that have similar context to 'Search trains' (a 1 ) within the first zone, he can make a query as: a 1 ::1. If he wants to find services that are similar to 'Search trains' but not followed by 'Present alternatives', he will exclude the connection flow connecting 'Search trains' to 'Present alternatives' in its first layer. The query will be: a 1 :-(<a 1 [sequence]a 2 >):1. In the case that he wants to know possible payment methods, he may select 'Process payment' service (a 3 ) and add a constraint which does not include a 'sequence' that connects to 'Send confirmation' service (a 4 ). He may also widen the considered composition contexts in two layers to get more results. Consequently, his query is as follows: a 3 :-(<['sequence']a 4 >):2. In another context, if he wants to know existing services that are similar to 'Search trains' (a 1 ), and include the services 'Request payment Info.' (a 8 ) and 'Process payment' (a 3 ) but exclude the AND-join connection between them, his query is as follows: a 1 :+a 8 +a 3 -(<a 8 ['AND-join']a 3 >):5.

B. Query's execution

In general, the procedure of getting results by using our query is as follows:

1) We capture the composition context of the associated service. The largeness of the composition context is specified by the radius parameter. 2) We match the composition context of the associated service to others in other service-based processes. 3) We refine the matching result by selecting only services whose composition contexts satisfy the query's constraints. 4) We sort the selected services based on the matching values and pick up top-N services2 for the response.

IV. IMPLEMENTATION & EXPERIMENTS

A. Implementation

To validate our approach as a proof of concept, we develop an application that can assist the process designer to find services using our query language. The application is developed and integrated into the Signavio3 , which is a business process modeling platform. Users are invited to use our application at http://www-inf.it-sudparis.eu/SIMBAD/tools/WebRec/4 . The screen shot of the application is shown in Fig. 5. The areas 1, 2 and 3 show the BPMN elements for design, canvas and property of the selected element. They are provided by The composition context matching is executed beforehand. Then, query constraints are applied on the matching result to filter unrelated services.

B. Experiments

We performed experiments on a large public collection of business processes. Our goal is two fold: (i) to evaluate the feasibility of our proposed query and (ii) to measure its efficiency of our algorithm. Details of the dataset and experiments are given as following.

1) Dataset:

The dataset used in our approach is shared by the Business Integration Technologies (BIT) research group 5 at the IBM Zurich Research Laboratory. It was presented in [START_REF] Fahland | Instantaneous soundness checking of industrial business process models[END_REF]. It contains business process models designed for financial services, telecommunications, and other domains. It is presented in XML format following BPMN 2.0 standard. Each XML file stores the data of a business process, including elements' IDs, service names, and the sequence flows between elements. The dataset consists of 560 business processes with 6363 services. There are 3781 different services in which 1196 services appear in more than one process. In average, there are 11.36 services, 2.59 'start' elements, 3.42 'end' elements, 18.96 gateways (including parallel, exclusive and inclusive gateways) and 46.81 sequence flows in a process .

2) Results:

In the first experiment, we target to evaluate the feasibility of our service querying approach. To do so, we evaluate the number of services in the dataset that can be retrieved by querying the composition contexts within a given radius. We set radius = 1 and match the composition context graphs of all services in the repository using the proposed computation. We obtain 2938 (77.7%) services that match at least one service with a matching value greater than 0. It means that our approach can provide queried results for a majority services as we can retrieve similar composition contexts for more than 3/4 number of services.

In the second experiment, we evaluate the efficiency of our approach based on Precision values. We also compare our approach with an approach that query services randomly. As our approach takes into account composition contexts

Precision values

Number of recommended activities

Ourr approach Random approach Fig. 6: Precision values with radius = 1 instead of service identifiers, we consider service identifiers as data in computing Precision. Concretely, consider a selected service a in a process P . Assume that a appears in n processes. Also assume that the query of services that are relevant to this selected position returns a list of l services, in which t(t ≤ l) services are a. Precision of this query is given by Equation 3.

P recision = t l ; (3)
In our experiment, we tune the number of queried services for each position from 5 to 1. We take into account only the first zone in our queries. To ignore the noise of the irrelevant processes, we compute Precision for only the services that appear in at least 10 processes. Consequently, 29 services and 267 processes are considered for our experiment.

Figure 6 shows the average Precision values obtained in our experiment. It shows that our queries achieved good Precision values. The Precision values increase when the number of queried services decreases. This means that the relevant services mostly appear at the top of the returned list. In other words, when we reduce the number of services in the returned list, the result shows that our approach are more focused and precise. It also shows that our approach is much more efficient than a random approach.

V. RELATED WORK

Recently, there are many efforts on finding advanced solutions for process querying. Authors in [START_REF] Awad | Semantic querying of business process models[END_REF], [START_REF] Sakr | A framework for querying graph-based business process models[END_REF] proposed and developed a business process querying language, named BPMN-Q. The BPMN-Q helps to retrieve partial process fragments that start from a given activity (corresponding to service in our approach) and end by another given activity. Their query, however, always requires two activities as input and they have not yet dealt with the structural constrains, i.e. included/excluded activities and connection flows.

Momotko et. al. [START_REF] Momotko | Process query language: A way to make workflow processes more flexible[END_REF] proposed a query language to retrieve the status of service instance during the process execution time. Meanwhile, Beeri et. al. [START_REF] Beeri | Querying business processes[END_REF], [START_REF] Beeri | Monitoring business processes with queries[END_REF], [START_REF] Beheshti | A query language for analyzing business processes execution[END_REF] proposed a query language for business process monitoring. Different from them, our approach can be applied in both design and execution phases. In addition, we exploit the relations between services in the design instead of the attributes of a service instance. Deutch et. al. [START_REF] Deutch | Querying structural and behavioral properties of business processes[END_REF] were inspired by [START_REF] Beeri | Querying business processes[END_REF] and proposed a model for querying the structural and behavioral properties of business processes. While [START_REF] Deutch | A structural/temporal query language for business processes[END_REF] proposed a query language for process specifications and Markovic et. al [START_REF] Markovic | Serviceoriented computing -icsoc 2007 workshops[END_REF] proposed an ontoloty-based framework for process querying. In our approach, we focus on the service's 'behavior', i.e. relations between services, instead of the process 'behavior', and we match the service (composition context) graphs instead of the process graphs.

Other approaches that aim at facilitating the process design without building a query language includes business process searching [START_REF] Yan | Fast business process similarity search with feature-based similarity estimation[END_REF], [START_REF] Dijkman | Graph matching algorithms for business process model similarity search[END_REF] and process similarity measuring [START_REF] Van Der Aalst | Process equivalence: Comparing two process models based on observed behavior[END_REF], [START_REF] Dijkman | A classification of differences between similar business processes[END_REF], [START_REF] Li | On measuring process model similarity based on high-level change operations[END_REF], [START_REF] Dongen | Measuring similarity between business process models[END_REF], [START_REF] Ehrig | Measuring similarity between semantic business process models[END_REF]. Their target is to help process designers find similar processes to the one they are designing. Related to them, our work also helps to facilitate process design. However, instead of comparing process models, we focus on comparing services in process models.

In a recent work [START_REF] Chan | Assisting business process design by activity neighborhood context matching[END_REF], [START_REF] Chan | Context-based service recommendation for assisting business process design[END_REF], [START_REF] Chan | Composition context matching for web service recommendation[END_REF], we recommended a list of services having a similar context graph in a process/service composition. Whereas in this work, we provide a graphical user interface and a context free grammar language to the process designer to specify his queries. Compared to our previous work, the process designer is able now to specify new constraints over the composition context using a defined query, and to view the corresponding results. This querying mechanism is richer and more useful than recommending simple services.

VI. CONCLUSION

In this paper, we present an original approach that can assist process designers during the design time and execution time. We introduce the service composition context and propose an algorithm to compute the similarity between services based on the composition context matching. We also propose a query language that can help to find services that are similar to selected services in a process. Experimental results show that our approach is feasible and efficient in querying services.

Due to the general limitation of public business process datasets, which provide only elements' identifier and services' names without any further information such as the one we used in our experiment, the validation of our approach so far is done with only the perfect match of services' names. However, our approach can be easily improved to deal with other comparison metrics and the validation can be extended for the imperfect matching. For example, we can take into account neighbors if their similarities on another comparison metric are greater than a certain threshold.

In our future work, we intend take into account the other service properties such as service description and pre-/postconditions to refine the matching algorithm. We also aim at extending our approach to extract the hidden knowledge existing in business processes logs for another quality input.

Fig. 3 :

 3 Fig. 2: Incomplete train reservation process

  aj ai P P , denoted by L( aj ai P P ) is the number of connection flows in the path. Definition II.5 (shortest connection path)

Fig. 5 :

 5 Fig. 5: Application's screen-shot

  5 http://www.zurich.ibm.com/csc/bit/

  .

	1.	Query	::=	ServiceID,':',[Constraint],':',Radius;
	2.	ServiceID	::=	Character,{Character|Digit};
	3.	Constraint	::=	('+'|'-')Term | Constraint,'|',Term;
	4.	Term	::=	Item | Term,'+',Item | Term,'-',Item;
	5.	Item	::=	ServiceID| ConFlow | '(',Constraint,')';
	6.	ConFlow	::=	'<',[ServiceID],'[',FlowString,']',[ServiceID]'>';
	7.	FlowString	::=	ConElement,{ConElement};
	8.	ConElement	::=
				based-
				gateway'| 'message-catching';
	9.	Radius	::=	DigitNotZero,{Digit};
	10.	Character	::

'sequence' | 'AND-split' | 'AND-join' | 'OR-split' | 'OR-join' | 'XOR-split' | 'XOR-join' | 'event-

TABLE I :

 I Query grammar

N can be flexibly tuned by the process designer

Academic version at: http://www.signavio.com/en/academic.html and the open source at: http://code.google.com/p/signavio-core-components/

Tutorial at: http://www-inf.it-sudparis.eu/SIMBAD/tools/WebRec/tutorial. html and video demo at: http://www-inf.it-sudparis.eu/SIMBAD/tools/ WebRec/demo.html