Method and an apparatus for clustering process models

• US 20100004923A1
• Filed: 07/02/2008
• Published: 01/07/2010
• Est. Priority Date: 07/02/2008
• Status: Active Grant

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Gromer, Alexandra, Goller, Mathias, Weber, Norbert, Pomberger, Gustav, Bogl, Andreas
• Granted Patent: US 8,180,627 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

The invention relates to an apparatus for clustering process models each consisting of model elements comprising a text phrase which describes in a natural language a process activity according to a process modeling language grammar and a natural language grammar, wherein said apparatus comprises a process object ontology memory for storing a process object ontology, a distance calculation unit for calculating a distance matrix employing said processing modeling language grammar and said natural language grammar, wherein said distance matrix consists of distances each indicating a dissimilarity of a pair of said process models, and a clustering unit which partitions said process models into a set of clusters based on said calculated distance matrix.

Claims

1. A method for clustering process models each consisting of model elements comprising a text phrase which describes in a natural language a process activity according to a process modeling language grammar and a natural language grammar,

wherein the distance matrix is calculated employing both grammars, each distance of said distance matrix indicating a dissimilarity of a pair of said process models,

wherein said process models are partitioned into a set of clusters based on said calculated distance matrix.

2. The method according to claim 1,

wherein said process model language comprises a UML (Unified Modeling Language)-model, an EPC (Event-driven Process Chain)-model and a petri-network.

3. The method according to claim 2,

wherein each model element is formed by a function model element, an event model element or an operator model element.

4. The method according to claim 1,

wherein said model elements are labeled by text phrases each comprising at least one term, wherein each term within a model element is classified according to said natural language grammar into different word types comprising nouns, verbs, articles, conjunctions, prepositions and adjectives.

5. The method according to claim 4,

wherein stop words of predetermined stop word types are filtered from said terms,

wherein said stop word types comprise prepositions, articles and conjunctions.

6. The method according to claim 1,

wherein on a native calculation model a distance between a first process model (x) and a second process model (y) is calculated depending on the number of model elements (b) which form part only of the second process model (y), the number of model elements (c) which form part only of the first process model (x) and depending on model elements (a) which form part of both process models (x, y).

7. The method according to claim 6,

wherein on said native calculation level, a Jaccard distance between two process models (x, y) is calculated as follows:

${\mathrm{dist}}_{\mathrm{Jaccard}}<br><br>\left(x,y\right)=\frac{b+c}{a+b+c}$

wherein

b is a number of model elements which form only part of the second process model (y),

c is the number of model elements which form only part of the first process model (x), and

a is the number of model elements which form part of both process models (x, y).

8. The method according to claim 1,

wherein on a term calculation level a distance between a first process model and a second process model is calculated on the basis of terms both processed models have in common.

9. The method according to claim 8,

wherein a text vector is generated for each process model indicating a frequency of occurrence of terms in said process model.

10. The method according to claim 9,

wherein on said term calculation level a distance between two process models (x, y) having text vectors v(x)=(x1, . . . , x_n) and v(y)=(y1, . . . , y_n) is calculated as follows:

${\mathrm{dist}}_{\mathrm{Cosinus}}<br><br>\left(x,y\right)=1-\frac{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>x_i·<br><br>y_l}{\sqrt{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>x_i^2}·<br><br>\sqrt{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>y_i^2}}$

wherein x_i, y_i indicate the frequency of occurrence of a term_i.

11. The method according to claim 1,

wherein on an object calculation level a distance between a first process model and a second process model is calculated on the basis of a process object ontology.

12. The method according to claim 11,

wherein on said object calculation level a distance between two process models (x, y) is calculated as follows:

${\mathrm{dist}}_{\mathrm{PO}}<br><br>\left(x,y\right)=\frac{\underset{p_x\in <br><br>M_x}{\sum <br><br>}<br><br>{\mathrm{dist}}_{\min }<br><br>\left(p_x,M_y\right)+\underset{p_y\in <br><br>M_y}{\sum <br><br>}<br><br>{\mathrm{dist}}_{\min }<br><br>\left(p_y,M_x\right)}{<br><br>M_x<br><br>+<br><br>M_y<br><br>}$

wherein

dist_min(p_x, M_y) is the minimum distance between a process object p_x of a model element of a first process model (x) and a set (M_y) of process objects p_y of a second process model (y) in said process object ontology;

dist_min(p_y, M_y)=min {dist_ont(p_x, p_y)}

wherein dist_min(p_y, M_x) is a minimum distance between a process object p_y of a model element of a second process model (y) and a set M_x of process objects p_x of a first process model (x) in said process object ontology;

dist_min(p_y, M_x)=min {dist_ont(p_y, p_x)}

wherein |M_x|+|M_y| is the total number of process objects.

13. The method according to claim 12,

wherein a distance between process objects p_x, p_y in the processed object ontology is calculated as follows:

${\mathrm{dist}}_{\mathrm{Ont}}<br><br>\left(p_x,p_y\right)=1-\underset{p\in <br><br>\mathrm{paths}<br><br>\left(p_x,p_y\right)}{\max }<br><br>\left\{{\mathrm{weight}}_{\mathrm{migr}}^{\mathrm{migr}<br><br>\left(p\right)}·<br><br>{\mathrm{weight}}_{\mathrm{gen}}^{\mathrm{gen}<br><br>\left(p\right)}·<br><br>{\mathrm{weight}}_{\mathrm{sib}}^{\mathrm{sib}<br><br>\left(p\right)}·<br><br>{\mathrm{weight}}_{\mathrm{mer}}^{\mathrm{mer}<br><br>\left(p\right)}\right\}.$

wherein weight_migr is a weight of a migrate-to-relationship and

migr(p) is the number of migrate-to-relationships along a path p;

weight_gen is a weight of a generalization-relationship and

gen(p) is the number of generalization-relationships along a path p;

weight_sib is a weight of a sibling-relationship and

sib(p) is the number of sibling-relationships along a path p; and

weight_mer is a weight of a meronyme- or part-of-relationship and

mer(p) is the number of meronyme- or part-of-relationships within said process object ontology.

14. The method according to claim 1,

wherein on an activity calculation level a distance between a first process model and a second process model is calculated on the basis of a process object ontology and process activities of model elements of said process models,

wherein a process activity is formed by a term of a predetermined word type.

15. The method according to claim 14,

wherein on said activity calculation level a distance between two process models (x, y) is calculated as follows:

${\mathrm{dist}}_{\mathrm{POActivity}}<br><br>\left(x,y\right)=\frac{\underset{a_x\in <br><br>A_x}{\sum <br><br>}<br><br>{\mathrm{dist}}_{\min }<br><br>\left(a_x,A_y\right)+\underset{a_y\in <br><br>A_y}{\sum <br><br>}<br><br>{\mathrm{dist}}_{\min }<br><br>\left(a_y,A_x\right)}{<br><br>A_x<br><br>+<br><br>A_y<br><br>}$

wherein dist_min(a_x, a_y) is the minimum distance between a process activity (a_x) of a model element of a first process model (x) on the set (A_y) of process activities (a_y) of a second process model (y) in said process object ontology;

dist_min(a_x, A_y)=min{dist_activity(a_x, a_y)}

wherein

dist_min(a_y, A_x) is the minimum distance between the process activity (a_y) of a model element of said second process model (y) on the set (A_x) of process activities (a_x) of the first process model (x) in said process object ontology;

dist_min(a_x, A_y)=min{dist_activity(a_x, a_y)}

wherein

|A_x|+|A_y| is the total number of process activities.

16. The method according to claim 15,

wherein the distance between process activities a_x, a_y in said process object ontology is calculated as follows:

if activities a_x, a_y are dissimilar, the distance is calculated as follows;

dist_activity(a_x, a_y)=1

otherwise;

dist_activity(a_x, a_y)=weight_po·

dist_ont(p_x, p_y)

wherein dist_ont(p_x, p_y) is the distance between process objects p_x, p_y in said process object ontology.

17. The method according to claim 1,

wherein said process models are partitioned into a set of clusters by means of a medoid-based clustering algorithm.

18. The method according to claim 1, wherein said method is performed under control of a computer program.

19. The method according to claim 1, wherein the computer program is read from a data carrier.

20. An apparatus for clustering process models each consisting of model elements comprising a text phrase which describes in a natural language a process activity according to a process modeling language grammar and a natural language grammar, wherein said apparatus comprises:

(a) a process object ontology memory for storing a process object ontology;

(b) a distance calculation unit for calculating a distance matrix employing said processing modeling language grammar and said natural language grammar, wherein said distance matrix consists of distances each indicating a dissimilarity of a pair of said process models; and

(c) a clustering unit which partitions said process models into a set of clusters based on said calculated distance matrix.

21. The apparatus according to claim 20,

wherein the distances are calculated by said distance unit according to a selected calculation level, which is selectable between

a native calculation level,

a term calculation level,

an object calculation level,

an activity calculation level.

22. The apparatus according to claim 20,

wherein said clustering unit partitions said process models by means of a menoid-based clustering algorithm.

23. The apparatus according to claim 20,

wherein said process modeling language comprises UML (Unified Model Language)-model, an EPC (Event-driven Process Chain)-model, or a petri-network.

24. The apparatus according to claim 20,

wherein said model elements are labeled by text phrases each comprising at least one term.

25. An apparatus for calculating a dissimilarity between process models each consisting of model elements comprising a text phrase which describes in a natural language a process activity according to a process modeling language grammar and a natural language grammar, said apparatus comprising:

a process object ontology memory for storing a process object ontology; and

a distance calculation unit for calculating a distance matrix consisting of distances each indicating a dissimilarity of a pair of said process models.