key: cord-0047108-ix3wpv7x
authors: Suraj, Zbigniew; Hassanien, Aboul Ella; Bandyopadhyay, Sibasis
title: Weighted Generalized Fuzzy Petri Nets and Rough Sets for Knowledge Representation and Reasoning
date: 2020-06-10
journal: Rough Sets
DOI: 10.1007/978-3-030-52705-1_5
sha: 5551caf6a2e6f433ba979e2b3644d0f22b2494a3
doc_id: 47108
cord_uid: ix3wpv7x

In this paper, we consider the decision tables provided by experts in the field. We construct an algorithm for executing a highly parallel program represented by a fuzzy Petri net from a given decision table. The constructed net allows objects to be identified in decision tables to the extent that appropriate decisions can be made. Conditional attribute values given by experts are propagated by the net at maximum speed. This is done by properly organizing the net’s work. Our approach is based on rough set theory and weighted generalized fuzzy Petri nets.

Rough set theory, proposed by Pawlak in 1982 [18] , is a mathematical tool for dealing with unclear, imprecise, incoherent and uncertain knowledge. It has been observed for many years that both research and applications of rough set theory are attracting more and more attention of researchers. It can be successfully used in many areas of application alone or in combination with other approaches. Here, we use this theory to support modeling of decision-making systems using weighted generalized fuzzy Petri nets.

In this paper, we assume that a decision table S representing experimental knowledge is given [17] . It consists of a number of rows labeled by elements from a set of objects U , which contain the results of measurements, observations, reviews etc. represented by a value vector of conditional attributes (conditions) from A together with a decision d corresponding to this vector. Values of conditions are provided by experts in the field. In some applications the values of conditional attributes can be interpreted as states of local processes in a complex system and the decision value is related to the global state of that system [13, 16, 24] . Sometimes it is necessary to transform a given experimental decision table by taking into account other relevant features (new conditional attributes) instead of the original ones. This step is necessary when the decision algorithm constructed directly from the original decision table yields an inadequate classification of unseen objects or when the complexity of decision algorithm synthesis from the original decision table is too high. In this case some additional time is necessary to compute the values of new features after the original values are given. The input for our algorithm consists of a decision table (if necessary, pre-processed as described above).

We shall construct a fuzzy Petri net allowing to make a decision as soon as a sufficient number of conditional attribute values is known and conclusions drawn from the knowledge encoded in S (cf. [22] ). In the paper we formulate this problem and present its solution.

First, we assume that knowledge encoded in S is represented by rules automatically extracted from S. We consider acceptable rules in S, i.e. rules for which the accuracy factor need not necessarily be equal to 1 [23] . We assume that the knowledge encoded in S is complete in the sense that invisible objects have attribute value vectors consistent with rules extracted from S. This assumption may be too restrictive, because the rules for the classification of new objects should be generated only from appropriate features (attributes). The rule is active if the values of all attributes on its left side are given. Our algorithm should propagate information from attributes to other attributes as soon as possible. This is the reason for generating true decision rules corresponding to relative reducts with respect to the decision in S [22] . The last step of our algorithm is the implementation of the set of generated rules using fuzzy Petri nets. Each step of a computation of the constructed fuzzy Petri net consists of two phases. In the first phase, it is checked that all condition values are known, and if so, in the second phase, new information about the values is sent through the net at maximum speed. The whole computation process is carried out by proper organization of the net's work.

In the paper, we use fuzzy Petri nets [3, 5, 10, 12, 30] as a model of the target decision-making system. Net properties can be verified using tools for the analysis of Petri nets (see e.g. [28] ).

Over the past few decades, there has been a series of modifications to the classic fuzzy Petri nets (FPNs) [12] to deal with complex decision-making systems. Chen [4] introduced weight factors into FPNs and proposed a weighted FPN (WFPN) model. Ha et al. [7] extended his work by adding input and output weight factors into WFPNs. Then the intuitionistic fuzzy sets were integrated into FPNs, and an intuitionistic FPN was presented in [11, 26] . Skowron and Suraj [23] developed a parallel algorithm for real-time decision-making based on rough set theory and classic Petri nets. Peters et al. [20] combined the theory of FPNs, rough sets, and colored Petri nets to develop a rough fuzzy Petri net model. Suraj and Fryc [27] introduced time factor to approximate Petri nets, which plays a vital role in developing real-time decision-making systems. Bandyopadhyay et al. [1] proposed to link Petri nets and soft sets and introduced a soft Petri net model. Suraj and Hassanien [29] combined the theory of FPN and sets of fuzzy intervals to avoid the problem of determining the exact membership or truth value. This paper establishes some relationships between rough set theory and fuzzy Petri nets. Parameter values such as rule certainty coefficients, input and output weights of arcs in the net model are calculated automatically from a given decision table. The empirical example provided here shows the effectiveness of the proposed model.

The rest of this paper is organized in the following way. Section 2 contains some background knowledge regarding rough set theory. In Sect. 3, the weighted generalized fuzzy Petri net formalism is given. Section 4 describes three structural forms of decision rules and a method for transformation of decision tables into weighted generalized fuzzy Petri nets. An example illustrating the approach presented in this paper is provided in Sect. 5. Finally, Sect. 6 suggests some directions for further research related to our approach.

In this section we recall basic notions of rough set theory. Among them are those of information systems, indiscernibility relations, dependencies of attributes, relative reducts, significance of attributes and rules [14, 15] .

An information system is a pair S = (U, A), where U is a non-empty finite set of objects called the universe and A is a non-empty finite set of attributes such that a : U → V a for every a ∈ A. The set V a is called the value set of a, and V = a∈A V a is said to be the domain of A.

Let Let us observe that the decision d determines a partition {X 1 , ..., X r(d) } of the universe U , where X k = {u ∈ U : d(u) = k} for 1 ≤ k ≤ r(d). The set X i is called the i-th decision class of S. If X 1 , ..., X r(d) are the decision classes of S, then the set BX 1 ∪...∪BX r(d) is called the B-positive region of S and is denoted by P OS B (d).

Any decision system S = (U, A ∪ {d}) can be represented by a data table with the number of rows equal to the cardinality of the universe U and the number of columns equal to the cardinality of the set A ∪ {d}. On the position corresponding to the row u and column a the value a(u) appears. Table 1 

Each row of the table can be seen as information about specific patient. 

An important issue in data analysis is discovering of dependencies between attributes. Intuitively, a set of attributes C depends totally on a set of attributes B, denoted by B ⇒ C, if there exists a functional dependency between values of C and B. Let S = (U, A) be an information system and let B,

|X| denotes the cardinality of X = ∅. The set P OS B (C) is called a positive region of the partition U/C with respect to B. In fact, it is the set of all elements of U that can be uniquely classified to blocks of the partition U/C by means of B.

Let

Consider once again the decision system presented in Table 1 

Significance of an attribute a in a decision system S = (U, A ∪ {d}) can be evaluated by measuring the effect of removing of an attribute a ∈ A from the attribute set A on the positive region defined by the table S.

Let B ⊆ A. Significance of an attribute a ∈ A is defined as follows: Note that the following relationship is also met: 0 ≤ σ(B, d, a) ≤ 1.

Using the above formula for the decision system from Example 1, we obtain the following results for Table 1: 1. 

Rules express some of the relationships between values of the attributes described in decision tables. In this subsection we recall the definition of rules as well as other related concepts.

Atomic formulae over B and V are expressions of the form a = v. They are called descriptors over B and V , where a ∈ B and v ∈ V a . The set DESC(B, V ) of formulae over B and V is the least set containing all atomic formulae over B and V and closed with respect to the propositional connectives OR (disjunction), AND (conjunction) and NOT (negation).

Let τ ∈ DESC(B, V ). τ S denotes the meaning of τ in the decision system S which is the set of all objects in U with the property τ . These sets are defined as follows:

Formulae τ and d = v are called the predecessor and the successor of the decision rule r. τ S is the non-empty set of objects matching the decision rule and τ S ∩ (d = v) S is the set of objects supporting the rule. With every decision rule r we can associate several numerical factors. The accuracy factor of the decision rule r is the number

It is also easy to see that 0 ≤ str(r) ≤ acc(r) ≤ 1 for every the decision rule r in S.

Let us consider the decision system table S from Example 1 presented in Table 1 . Using the method for generating decision rules in S [22] , we get the following rules, corresponding to the relative reduct R 1 = {H, T} along with the numerical factors defined above:

-r 1 : IF H=no AND T=very high THEN F=yes; str(r 1 ) = 1/6, acc(r 1 ) = 1 -r 2 : IF H=yes AND T=very high THEN F=yes; str(r 2 ) = 1/6, acc(r 2 ) = 1 -r 3 : IF H=no AND T=high THEN F=yes; str(r 3 ) = 1/6, acc(r 3 ) = 1 -r 4 : IF H=yes AND T=high THEN F=yes; str(r 4 ) = 1/6, acc(r 4 ) = 1/2 -r 5 : IF H=yes AND T=high THEN F=no; str(r 5 ) = 1/6, acc(r 5 ) = 1/2 -r 6 : IF H=no AND T=normal THEN F=no; str(r 6 ) = 1/6, acc(r 6 ) = 1

Note that the rules r 1 , r 2 , r 3 , r 6 are true in Table 1, while the other rules are  acceptable in this table. For a systematic overview of rule synthesis, see e.g. [9, 15, 21] .

Fuzzy Petri nets are a modification of classic Petri nets to deal with imprecise, unclear or incomplete information in knowledge-based systems that are widely used to model fuzzy production rules and rule-based reasoning.

In this section, we define weighted generalized fuzzy Petri nets (WGFP-net). The new model is a modification of generalized fuzzy Petri nets, proposed in [25] . The main difference between the current net model and the previous one concerns the weights of arcs. Weights are now added to the input and output arcs. They are any numbers from 0 to 1, automatically calculated from the data table and interpreted in the concepts of rough set theory (see Sect. 4) (cf. [2, 10] ).

In this paper WGFP-nets are used as a tool for computing a parallel program from a given decision table. After modeling a decision table by a WGFP-net the states are identified in the net to an extent allowing to take the appropriate decisions.

We also assume that the reader knows the basic concepts of classic Petri nets [6] and triangular norms [8] .

Let We also accept that if I(p, t) = 0 (O(p, t) = 0) then the directed arc from input (output) place p to transition t does not exist in the net drawing. Similarly, if M 0 (p) = 0 then the token does not exist in the place p. In addition, if I(p, t) = 1 (O(t, p) = 1), then the weight of the arc equal to 1 is also disregarded in the net drawing. The numbers β(t) and γ(t) are placed in a net picture under the transition t. The first number is interpreted as the truth degree of an implication corresponding to a given transition t. The role of the second one is to limit the possibility of transition firings, i.e., if the input operator In value for all values corresponding to input places of the transition t is less than a threshold value γ(t) then this transition cannot be fired (activated). The operator binding function δ connects transitions with triples of operators (In, Out 1 , Out 2 ). The first operator in the triple is called the input operator, and two remaining ones are the output operators. The input operator In concerns the way in which all input places are connected with a given transition t (more precisely, statements corresponding to those places). However, the output operators Out 1 and Out 2 concern the way in which the next marking is computed after firing the transition t. In the case of the input operator we assume that it can belong to one of two classes, i.e., t-or s-norm, whereas the second one belongs to the class of t-norms and the third to the class of s-norms.

Let N be a WGFP-net. A marking of N is a function M : P → [0, 1]. The dynamic behavior of the system is represented by the firing of the corresponding transition, and the evolution of the system is represented by a firing sequence of transitions. We assume that the networks built in the form presented in this paper operate according to the firing rule consisting of the following three steps:

In for all input places of the transition t by M multiplied by the relevant weights of arcs is positive and greater than, or equal to the number being a value of threshold function γ corresponding to the transition t. Formally, the following condition for γ(t) should be satisfied:

where In is an input operator of the transition t, iw ij is an input weight of t and M (p ij ) is a marking of a place p ij for j = 1, 2, ..., k. Formally, for each p ∈ P

We also assume that if several transitions are simultaneously enabled in the same marking (i.e. transitions are concurrent) then they can be fired by an application of the firing rule described above in one and the same step and the resulting marking is computed according to this rule. (ZtN, GtN, ZsN) , where ZtN(a, b) = min(a, b) GtN(a, b) = a · b (algebraic product, Goguen t-Norm), and ZsN(a, b) = max(a, b) (maximum, Zadeh s-Norm). The transition t 1 is enabled by the initial marking M 0 , since ZtN(I(p 1 , t 1 ) · M 0 (p 1 ), I(p 2 , t 1 ) · M 0 (p 2 )) = min(1/5, 1/5) = 1/5 ≥ 0.1 = γ(t 1 ). Firing transition t 1 by the marking M 0 transforms M 0 to the resulting marking M = (1/2, 2/5, 1/5), because ow 3 · GtN(1/5, β(t 1 )) = 1· GtN(1/5, 1.0) = 1/5 and ZsN(1/5, M 0 (p 3 )) = max(1/5, 0) = 1/5. Note that in this case the transition t 1 is still enabled by M , but when it is fired at this marking, the result marking is the same as M . We omit the detailed description of the relevant calculations illustrating the transformation from the marking M to M after firing t 1 . They run similarly to these above.

Now we present a method for transforming decision rules representing a given decision system into a WGFP-net.

We assume that a decision system is represented by decision rules of the form

Let S = (U, A ∪ {d}) be a decision system, and DESC(A, V a ) be the set of the set of conditional formulae of S.

In the paper, we consider three structural forms of decision rules with a list of numerical factors enclosed in square brackets '[' and ']' characterizing these rules (cf. [4, 7, 10] ).

where a = v and d = v denote descriptors such that a = v ∈ DESC(A, V a ) and v ∈ V d , b is the truth degree value of a = v, σ(a) is significance of the attribute a, while str(r 1 ) and acc(r 1 ) are the strength factor and the accuracy factor of the rule r 1 , respectively.

A WGFP-net structure of the decision rule r 1 is shown in Fig. 2 , where iw is the input weight of the transition r 1 and interpreted as σ(a), while ow is the output weight of r 1 and interpreted as str(r 1 ) (see Subsect. 2.3 and 2.4). A larger value of i w or ow means a stronger corresponding connection. However, the value β(r 1 ) = c is interpreted as acc(r 1 ). Similarly as before, the larger value of β the more credible the rule is. The value of γ represents the threshold value. Larger value b requires greater truth degree of the rule precedence, i.e., a = v. The operator In and the operators Out 1 , Out 2 represent the input operator and the output operators, respectively. According to Fig. 3 the token value in an output place p of a transition t corresponding to the decision rule r 1 is calculated as

where d = γ(r 1 ) and γ(r 1 ) is the threshold value associated to the transition r 1 and it is given by an expert in the field during the simulation process of the network.

If the predecessor or the successor of a decision rule contains AND or OR (propositional connectives), it is called a composite decision rule. Below, two types of composite decision rules are presented together with their WGFP-net representation (see Fig. 3 and Fig. 4 ). σ 2 (a) , . . . , σ k (a), str(r 2 ); acc(r 2 )]

where a 1 = v 1 , a 2 = v 2 , . . ., a k = v k , d = v denotes descriptors, and b 1 , b 2 , . . ., b k , b their truth degree values, respectively. The meaning of all numerical factors characterizing this rule is similar to the meanings of the relevant factors described for the rule of type 1. The token value b is calculated in the output place as follows (Fig. 3) σ 2 (a ) , . . . , σ n (a ), str 1 (r 3 ), str 2 (r 3 ), . . . , str n (r 3 ); acc 1 (r 3 ), acc 2 (r 3 ), . . . , acc n (r 3 

. . , d = v n denotes descriptors, and b is the truth degree value of a = v . The token value for the type 3 is calculated in each output place as follows (Fig. 4) 

1. It is easy to see that the rule of type 1 is a particular case of the rule of type 2, as in the case of the rule of type 1, there is only one descriptor in the predecessor. Type 3 can also be easily converted to type 1. Therefore, without losing generality, we can only consider the rules of type 1 and 2. 2. As the rules of type 1 and 3 have only one descriptor in their predecessors, we may omit the input operator In in Fig. 2 and 4 . Nevertheless, for better readability of these figures we leave the operator where it is. What's more, the rule of type 3 can be generalized in the case when in the predecessor of the rule instead of one descriptor we have a conjunction of descriptors (as in the rule of type 2). Then the net modeling of such a rule in relation to its predecessor is similar to the one done for the rule of type 2. 3. We assume that the initial markings of output places are equal to 0 in all net models corresponding to the considered rule types. Therefore, in the descriptions of the token values in output places we do not regard the output operator Out 2 . In the opposite case, i.e., for non-zero markings of output places, we should take into account this output operator. Thus, in each formula presented above the final token value a should be computed as follows: b = Out 2 (b , M(p )), where b denotes the token values computed for suitable rule types by means of formulas presented above, and M (p ) is a marking of output place p . Intuitively, a final token value corresponding to M (p ) for each output place p of a transition representing a decision rule r is obtained as a result of Out 2 operation for the computed Out 1 operation value and the current marking M (p ).

Using the method described above, we can formulate a simple algorithm that constructs a WGFP-net based on a given set of rules extracted from a decision system S. This algorithm transforms the rule into a WGFP-net depending on the form of the transformed rule. Let S = (U, A ∪ {d}) be a decision system.

Input : A finite set R of decision rules in with a list of parameters Output: A WGFP-net NS F ← ∅; (* The empty set. *) for each r ∈ R if r is a rule of type 1 then construct a subnet Nr as shown in Fig. 2 ; if r is a rule of type 2 then construct a subnet Nr as shown in Fig. 3 ; if r is a rule of type 3 then construct a subnet Nr as shown in Fig. 4 ; F ← F ∪ {Nr}; integrate all subnets from a family F on joint places and create a result net NS; return NS;

To illustrate our methodology, let's reconsider the decision rules corresponding to the relative reduct R 1 from Example 4 along with a full list of parameters needed to build a structure of WGFP net model: Assessing the statements (descriptors) attached to places p 2 and p 4 , we observe that transitions t 4 and t 5 are enabled in the initial marking (see Fig. 5 ). After firing these transitions in any order we obtain the same values for the decisions F=yes, F=no equal to 1/48 (see Fig. 6 ). This means that an unambiguous decision does not exist in this case. In the net model with parameters (and this is the model presented in the paper) the problem of ambiguity of decisions is easier to solve than in the model without parameters. In a situation like this, the ambiguity of decisions could be relatively easily resolved if the weights of the output arcs for t 4 and t 5 were different. This situation is possible with a different interpretation of the weights of the input and/or output arcs in this net model. We intend to address this problem in more detail in our future research work.

It is also visible in this figure that in the current marking the transitions t 4 and t 5 are still enabled. Firing these two transitions in the current marking does not change this marking, therefore the simulation of the net operation is already completed. We omit the particular calculation in this case, because it runs similarly as in Example 5 (Sect. 3).

Trying to make fuzzy Petri nets more realistic with regard to the perception of physical reality, in this paper we established the relationship between fuzzy Petri nets and rough set theory. This link is of a methodological nature and shows the possible application of rough set methodology to transform the WGFP-net into a more realistic net model. In the proposed model, the weights of arcs and the function β are interpreted using appropriate concepts from the rough set theory, thanks to which their values are calculated from data tables. Decision rules are also automatically generated from these tables, which are the basis for building the net model of the decision algorithm. In addition, the considered net model allows the use of any triangular norms to describe the behavior of the WGFPnets. The approach developed seems promising and one could try to apply it to problems that can be solved in a similar way.

It is worth noting that the presented net model allows relatively quickly identify the objects specified in a given decision table. However, the algorithm described does not propagate information from attributes to other attributes as soon as possible. If such an algorithm did this, we would achieve even faster decision making in the net model. It is well known that this aspect is extremely important in real-time systems. This is the reason to consider in the next study the rules in minimal form, i.e. with a minimal number of descriptors on its left hand side. Another interesting problem arises when we are unable to determine the exact membership or value of truth, then we should focus our attention on e.g. interval fuzzy sets [19] to indicate their scope instead of exact values. Therefore, it seems useful to examine the WGFP-net in the context of interval t-norms. This should make the model proposed here even more flexible, general and practical. These are just some examples of problems that we would like to examine using the approach presented in the paper.

Soft Petri net

Modified generalized weighted fuzzy Petri net in intuitionistic fuzzy environment

Fuzziness in Petri Nets

Weighted fuzzy reasoning using weighted fuzzy Petri nets

Knowledge representation using fuzzy Petri nets

Petri Nets and Grafcet: Tools for Modelling Discrete Event Systems

Fuzzy knowledge representation and reasoning using a generalized fuzzy Petri net and a similarity measure

Triangular Norms. Kluwer

Rough sets: a tutorial

Fuzzy Petri nets for knowledge representation and reasoning: a literature review

Fuzzy Petri nets using intuitionistic fuzzy sets and ordered weighted averaging operators

Fuzzy Petri nets for rule-based decision-making

Rough sets for discovering concurrent systems models from data tables

Rudiments of rough sets

Rough sets and boolean reasoning

Concurrent versus sequential the rough sets perspective

Rough Sets -Theoretical Aspects of Reasoning about Data

Rough sets

Fuzzy Control and Fuzzy Systems, 2nd extended edn

Approximate realtime decision making: concepts and rough fuzzy Petri net models

Synthesis of adaptive decision systems from experimental data

A synthesis of decision rules: applications of discernibility matrices

A parallel algorithm for real-time decision making: a rough set approach

Rough sets and concurrency

A new class of fuzzy Petri nets for knowledge representation and reasoning

Generalized weighted fuzzy Petri net in intuitionistic fuzzy environment

Timed approximate Petri net

Petri nets and PNeS in modeling and analysis of concurrent systems

Fuzzy Petri nets and interval analysis working together

Fuzzy Petri nets and industrial applications: a review

Acknowledgement. This work was partially supported by the Center for Innovation and Transfer of Natural Sciences and Engineering Knowledge at the University of Rzeszów. We would like to thank the anonymous referees for critical remarks and useful suggestions to improve the quality of the paper.