Formalized process models help to handle, design and store processes in a form understandable for the designers and users. As model repositories often contain similar or related models, they should be used when modelling new processes in a form of automated recommendations. It is important, as designers prefer to receive and use suggestions during the modelling process. Recommendations make modelling faster and less error-prone because a set of good models is automatically used to help the designer. In this paper, we describe and evaluate a method that uses Bayesian Networks and configurable models for recommendation purposes in process modelling. The practical integration of the recommendation module with a Activity Modeller tool is also presented.
Processes are one of the most popular methods for modelling flow of information and/or
control within a sequence of activities, actions or tasks. Among many notations that
allow to define and build business process diagrams, the Business Process Modeling
Notation (BPMN) [
Several visual editors were developed to support design of business processes in BPMN, one of which is Activity Modeller 1. It is a web modeller component that is available as part of the Activiti Explorer web application. The Modeller is a fork of the Signavio Core Components project 2. The goal of the Activiti Modeller is to support all the BPMN elements and extension supported by the Activiti Engine – a Java process engine that runs BPMN 2 processes natively.
Although visual editors like Activity provide support for building and executing business processes, this support does not include design recommendations. By recommendation we mean suggestions that the system can give to the designer to improve the design process both in terms of quality and time. ? The paper is supported by the Prosecco project. 1 See http://activiti.org/ 2 See http://www.signavio.com/
Three different types of recommendations can be distinguished depending on the
subject of recommendation process [
In this paper we focus on structural recommendation, that allows for automated generation of suggestions for the next (forward recommendation), previous (backward recommendation) or missing elements (autocompletion) of the designed BP. Such recommendations improves time needed to build new business process and prevents user from making most common mistakes. What is more, such suggestions allow the designer to interactively learn best practices in designing BPMN diagrams as this practices are encoded into the recommendation model.
In this paper we present the implementation and evaluation of the method for
structural recommendation of business processes that uses Bayesian networks and
configurable processes. The work presented in this paper is part of the Prosecco project3. The
objective of the project is to provide tools supporting the management of Small and
Medium Enterprises (SMEs) by the introduction of methods for declarative
specification of business process models and their semantics. The work described in this article
is a continuation of our previous research presented in [
The rest of the paper is organized as follows. In Section 2 related work is presented and motivation for our research was stated. Section 3 describes briefly the recommendation method developed. A prototype implementation of the recommendation module, and its integration with Activity Modeller in Section 4. This section provides also an evaluation of the method on a real-case scenario. Section 5 provides summary of the research and open issues that are planned to be solved in a future work. 2
As empirical studies have proven that users prefer to receive and use suggestions
during modelling processes [
Among attachment recommendations, support with finding appropriate services was
proposed by Born et al. [
In the case of structural recommendations, Kopp et al. [
Start of the
project
marPkeetrfaonrmalysis
[
Divide the
project into
parts
[
[
Refine
information
about project
[
[
Case-based reasoning for workflow adaptation was discussed in [
The work presented in this paper is a continuation of our previous research
presented in [
In the following section we present a short overview of the recommendation method, that uses BN for structural recommendations. It also describes an algorithm for mapping BPMN process elements to random variables of Bayesian network. 3
Bayesian Network [
In the subject of structural recommendations with BN approach, the random variables are BP structural elements (tasks, events, gates, etc). Connections between the random variables are obtained from the configurable process, that captures similarities between two or more BP models and encapsulates them within one meta-model. For the configuration model example, see Figure 1.
The transformation from a configurable model to a BN model is straightforward. Each node in a configurable process has to be modeled as a random variable in BN. Therefore, each node in a configurable process is translated into a node in the network. The flow that is modeled by configurable process represents dependencies between nodes. These dependencies also can be translated directly to the BN model (See Figure 2).
The BN network obtained from the configurable model encodes just the structure
of the process. To allow querying the network for the recommendations it is necessary
to train it. The comprehensive list and comparison of them can be found in [
We defined three different structural recommendation modes that include forward
recommendations, backward recommendation and autocompletion [
The forward recommendation algorithm will scan the Bayesian network starting from the last observed block in a topological order, and return three blocks with the probabilities of presence in the model greater than 50%. The most challenging task in this algorithm was mapping the nodes from BPMN process to nodes in Bayesian network. This was particularly difficult because the BPMN elements are identified by the unique IDs that are different every time a new process is created.
Therefore, we distinguished several possible paths for matching the BN model to the process that is designed: – graph-based metrics, that allows to compare structures of two networks and identify areas that may correspond to the same elements [23], – text-based metrics, that allows to compare elements based on their labels [24], and – semantic-based comparisons, that provides more advanced matching based on the elements labels, taking into consideration semantics of the labels [25].
Because the recommendation module should work in a real-time, we decided to use the second approach which is more efficient comparing to graph-based approaches and requires less implementation effort than the third option. This choice was motivated also by the fact that BPMN elements usually have very informative labels and hence, the text comparison should give good results. As the metric for comparing nodes labels, a Levenshtein distance [26] was used. Mathematically, the Levenshtein distance between two strings a; b is given by the equation 1, where where 1(ai6=bj) is the indicator function equal to 0 when ai = bj and equal to 1 otherwise.
leva;b(i; j) = 8max(i; j) > > > < 8>leva;b(i < >min leva;b(i; j > >: >:leva;b(i 1; j) + 1
1) + 1 1; j 1) + 1(ai6=bj) if min(i; j) = 0; otherwise.
(1) Such text-based matching performs well until two or more nodes have similar or the same labels. For instance in Figure 1 there are four And nodes and two Make settlements nodes. Hence, when the user puts the block with a label And, the recommendation algorithm has to decide to which of the blocks in the Bayesian network it corresponds. This is performed by the neighborhood scanning algorithm.
The algorithm performs a breadth-first search on the currently designed model, and try to match the neighborhood of the node from BPMN diagram to the neighborhoods of the ambiguous nodes in the Bayesian networks. The node from the Bayesian network which neighborhood matches the most of the nodes from BPMN diagram is chosen. For instance in the example from Figure 3, the user choses to include the And gateway in the diagram. The recommendation algorithm has to decide which And node from the Bayesian network presented in the Figure 2 should be treated as a reference point for the next recommendation. Because in the BPMN diagram the neighborhood of the And node is just one element called Start, the neighborhood scanning algorithm will search in the BN for the And node with a Start element as a neighbor. If the ambiguity cannot be resolved by the first level neighborhood scanning, the algorithm continues the process in a breath-search manner.
The following section presents details of the implementation of the recommendation module and presents brief evaluation of the approach.
In [
The first module is the converter, which creates a Bayesian Network file from a BPMN file. The second module generates a training data file based on the information about each block’s occurrence in each of the processes that the configurable process is composed of. The third module takes the untrained Bayesian Network file and the training data file as input and trains the network using the EM algorithm. 6 http://reasoning.cs.ucla.edu/samiam/ – Recommendation plugin – A user interface element, that presents the recommendations to the designer and allows to query the recommendation module. – Shape Menu plugin – A plugin that is a set of icons that surround a selected block providing shortcuts for the most commonly used operations. In this case, a plugin allows to insert the recommended element just after the selected one (see Figure 5).
The Recommendation module and SamIam inference library were encapsulated into a webservice restlet to fit the Activity software architecture. Recommendation plugin and Shape Menu plugin have been implemented as a frontend plugins for Activity modeller. The communication between frontend and backend is based on the JSON exchange format. To better visualize this process of recommendation performed by the Activity recommender, lets assume that the previously trained Bayesian network was deployed into the Activity recommender system. When a designer queries the system for the recommendation, all the BPMN elements labels that were already placed by the designer into the model are treated as an evidence. The currently selected element is tarted as a reference element for which the forward recommendation should be performed. All the evidence are packaged into the JSON format and sent to the backend, where the recommendation module performs a query to the BN and returns the recommended elements back to the frontend. In the frontend the recommendation plugin and shape menu plugin present the recommendations to the designer and the process continues.
The following section describes a brief evaluation of the descried solution on the simple use-case scenario. 4.2
The evaluation of the Activity recommender was performed on the simple model presented in Figure 2. The model was learnt from the configurable process presented in Figure 1 with an auxiliary modules described briefly at the beginning of this section.
The Figure 5 presents the beginning of the design process, when only two elements are inserted into the diagram: the Start of the project element and the And gateway. The Bayesian network representing this state was depicted in the Figure 3. If the user selects the node and presses the button depicted with a question mark icon that is located on the top bar of the modeller, the recommendation query will be send to the recommendation module. The module will then perform forward recommendation starting from the element that was selected by the designer (in this case the And gateway). The results of the query are presented in the sidebar on the left side of the Activity modeller, and are also accessible through shape menu plugin, which is activated when the user hover the mouse over the element.
As presented in Figure 5, the recommendations are consistent with the probabilities calculated from the Bayesian network presented in Figure 3. It is worth noting, that although in the Bayesian network there exist four And gateways, the correct gateway was chosen for the recommendation reference point, thanks to the neighborhood scanning algorithm described in Section 3. 5
In this paper we presented an implementation and evaluation of the structural recommendation module for BPMN diagrams. We integrated one of the most popular BPMN modeller called Ativity with our recommendation module providing practical tool for structural recommendation of BP models. We also presented an approach that supports matching the similar areas of two graphs that is based on the Levenshtein metric and neighbor scanning algorithm. The evaluation was presented on a simple use-case scenario that was part of the Prosecco project.
The future works assumes implementing remaining two recommendation modes that are: backward recommendation and autocompletion. It is also considered to compare the solution based on the Bayesian networks to the other approach that originates from phrase prediction algorithms [27]. 23. Dijkman, R., Dumas, M., García-Bañuelos, L.: Graph matching algorithms for business process model similarity search. In Dayal, U., Eder, J., Koehler, J., Reijers, H., eds.: Business Process Management. Volume 5701 of Lecture Notes in Computer Science. Springer Berlin Heidelberg (2009) 48–63 24. Dijkman, R., Dumas, M., van Dongen, B., Käärik, R., Mendling, J.: Similarity of business process models: Metrics and evaluation. Information Systems 36 (2011) 498 – 516 Special Issue: Semantic Integration of Data, Multimedia, and Services. 25. Sigman, M., Cecchi, G.A.: Global organization of the wordnet lexicon. Proceedings of the
National Academy of Sciences 99 (2002) 1742–1747 26. Levenshtein, V.: Binary Codes Capable of Correcting Deletions, Insertions and Reversals.
Soviet Physics Doklady 10 (1966) 707 27. Nandi, A., Jagadish, H.V.: Effective phrase prediction. In: Proceedings of the 33rd International Conference on Very Large Data Bases. VLDB ’07, VLDB Endowment (2007) 219–230