The problem of separability verification of fuzzy binary relations is considered. A necessary and sufficient condition for separability is given and an efficient algorithm for checking separability that can be easily applied in practice is suggested. The paper is supplemented by a simple test that sometimes might be helpful in detecting non-separability just at one glance.
Fuzzy relation generalize the concept of the classical relation by admitting a partial association between elements of universes of discourse [1, 2]. Hence fuzzy relations can be used for modeling more or less vague relationships between objects. They can formally be treated like fuzzy sets. The notion of fuzzy relation seems to be very natural and useful in various applications. In many cases fuzzy relations describe the actual situation more adequately than the classical ones. For instance, an association between different diseases and possible symptoms, documents and keywords, expected gain and possible states of nature, etc., are rarely of binary nature. Hence, by admitting there different intensity of association we obtain much more adequate mathematical model of the discussed problem (see, e.g., [3–5]).
Some types of relations are of special importance like fuzzy equivalence relations, fuzzy ordering relations, similarity relations, etc. (for the review and basic mathematical properties see, e.g., [10]). Separable (noninteractive) fuzzy relations are of interest in the case that one looks at a fuzzy relation R ⊆ X × Y as a fuzzy relationship between two variables or decision rules and with X and Y treated as corresponding sets of all possible values or possible alternatives, respectively. If variables and are disconnected then the choice of the particular value x ∈ X of variable does not depend on the choice of the particular value y ∈ Y of variable and conversely. For some recent applications of separable fuzzy relations and noninteractive variables in different fields one can mention: fuzzy optimization [7], prediction models [8], fuzzy differential equation [9], fuzzy numbers [10], fuzzy weighting [
Requirements to be met for concluding that a given fuzzy binary relation is separable are not complicated. However, checking all necessary conditions might be tedious, especially if the corresponding relation matrix is large enough. Therefore, an efficient algorithm that simplifies the separability verification would be desirable. Such algorithm is suggested in this contribution.
The paper is organized as follows. In Section 2 we introduce basic notation and concepts connected with fuzzy relations. Section 3 is devoted to separable fuzzy binary relations. A simple sufficient condition showing that variables under study are connected is given in Section 4. By this result in some situations one glance might be enough to detect non-separability. Unfortunately, since this separability test is based on the sufficient condition, it cannot be conclusive generally. Therefore, in Section 5, we prove a necessary and sufficient condition for separability which gives a strong basis for the decisive criterion. The theorem is supplemented by the desired efficient algorithm for checking separability that can be easily applied in practice. The aforementioned considerations and results are illustrated by numerical examples.
A fuzzy binary relation R between crisp sets X and Y is a fuzzy subset of the Cartesian product X × Y, i.e. R ⊆ X × Y = {(x, y) : x ∈ X, y ∈ Y }. Thus a fuzzy binary relation is a set of ordered pairs {((x, y), R(x, y)) : x ∈ X, y ∈ Y }, where R : X × Y → [0, 1] is the membership function of R. The membership grade R(x, y) ∈ [0, 1] reflects the intensity of relation between x and y. If for some pair (x, y) we have R(x, y) = 1, it denotes that elements x and y are fully related. On the other hand, if R(x, y) = 0 then it means that these elements are unrelated. Finally, intermediate values, i.e. 0 < R(x, y) < 1, indicate a partial association.
From now on we make the assumption that both sets X and Y are finite, i.e. X = {x_{1}, …, x_{n}} and Y = {y_{1}, …, y_{m}}. Under this assumption a convenient representation of a fuzzy binary relation R ⊆ X × Y is, the so called, relation matrix [R] = [r_{ij} ], where
The
Thus the height is the largest intensity of the relation obtained by any pair (x, y) ∈ R.
We say that fuzzy binary relations R and Q are
The intersection P ∩ Q of two fuzzy binary relations P and Q in X × Y is a fuzzy binary relation R ⊆ X × Y defined as
where T denotes a t-norm, while the union R = P ∪ Q of two fuzzy binary relations P and Q in X × Y is defined as follows
where S is a t-conorm. Further on we restrict our considerations to classical triangular norms, i.e. T(x, y) = min{x, y} = x ∧ y and S(x, y) = max{x, y} = x ∨ y in (
A Cartesian product of two fuzzy sets A and B defined in the universes of discourse X and Y, respectively, is a fuzzy relation A×B in the product space X×Y with the membership function given by (A × B)(x, y) = T(A(x), B(y)),
where x ∈ X, y ∈ Y and T is a t-norm. As it was mentioned above, in the present contribution we assume that T is a classical t-norm.
Given a fuzzy binary relation R ⊆ X × Y, its
while its
It is easily seen that domR(x) and codR(y) are equal to the hight of the corresponding row and column of matrix [R], respectively (see [1, 2]). Consequently, each element of X belongs to domR to the degree equal to the strength of its strongest relation to any member of set Y, while each element of Y belongs to codR to the degree equal to the strength of its strongest relation to any member of set X.
The domain and codomain are also called the first projection Proj_{X}R and the second projection Proj_{Y}R of a fuzzy binary relation, respectively, i.e. domR = Proj_{X}R and codR = Proj_{Y}R.
An operation, which is in some sense an inverse to the projection, is called a cylindric extension. The cylindric extension of domR is a fuzzy relation cyl(domR) ⊆ X × Y with membership function cyl(domR)(x, y) = domR(x) for all x ∈ X, y ∈ Y
while the cylindric extension of codR is a fuzzy relation cyl(codR) ⊆ X × Y with membership function cyl(codR)(x, y) = codR(y) for all x ∈ X, y ∈ Y.
Obviously,
Moreover, it can be shown that the cylindric extensions produce the largest fuzzy relation (in the sense of inclusion) with given projection.
As it is seen from (
However, in the special case, we can uniquely reconstruct a fuzzy binary relation from its projections. It happens so if the relation is separable (see [15, 16]), noninteractive [3, 4] or orthogonal [5].
A fuzzy binary relation R ⊆ X ×Y is
The proof of the following lemma is obvious.
The following conditions are equivalent:
i) R is separable,
ii) R(x, y) = domR(x) ∧ codR(y) ∀x ∈ X, ∀y ∈ Y,
iii)R = cyl(domR) ∩ cyl(codR).
Separable fuzzy relations are of special interest in the case that one looks at fuzzy relation as a relationship between two variables, attributes or decision rules and with X and Y treated as corresponding sets of all possible values or possible alternatives, respectively.
If the relation R ⊂ X × Y is separable then variablesandare called
If variables and are disconnected then the choice of the particular value x ∈ X of variable does not depend on the choice of the particular value y ∈ Y of variable and conversely. One may notice that the notion of disconnected variables can be thought of as being analogous to independent random variables in probability theory.
LetX = {x_{1}, x_{2}, x_{3}, x_{4}} and Y = {y_{1}, y_{2}, y_{3}, y_{4}, y_{5}}. It is easily seen that the fuzzy binary relation R_{1} ⊆ X×Y described by the relation matrix [R_{1}] given below is separable.
Indeed, domR_{1} = 0.4/x_{1} + 0.7/x_{2} + 1/x_{3} + 0.1/x_{4}and codR_{1} = 0.3/y_{1} +1/y_{2} +0.5/y_{3} +0/y_{4} +0.9/y_{5}, hence R_{1}is separable.
Now let us consider a fuzzy binary relation R_{2} ⊆ X×Y described by the relation matrix [R_{2}] given below
Although the projections of these two matrices are identical, i.e. domR_{2} = domR_{1}and codR_{2} = codR_{1}, the fuzzy relation R_{2}is not separable, since R_{2}(x_{2}, y_{3}) = 0.2 ≠ domR_{2}(x_{2}) ∧codR_{2}(y_{3}) = 0.5.
To prove that a given fuzzy binary relation R ⊆ X × Y is separable, where X = {x_{1}, …, x_{n}} and Y = {y_{1}, …, y_{m}}, one has to check m · n conditions (see condition ii in Lemma 2). Although the conditions to be checked are not difficult, their number might be large (and hence a time necessary for calculations may be long) if the relation matrix is too big. However, let us firstly consider two trivial cases where we get separability immediately.
A fuzzy binary relation R ⊆ X×Y such that R = ∅︀ is separable.
If R = ∅︀ then R(x, y) = 0 for each x ∈ X and y ∈ Y. Hence domR = ∅︀ and codR = ∅︀ and therefore R = domR × codR which is our claim.
A fuzzy binary relation R ⊆ X×Y such that R(x, y) = 1 for each x ∈ X and y ∈ Y is separable.
If R(x, y) = 1 for each x ∈ X and y ∈ Y then R = X × Y. Moreover domR = X, codR = Y and thus R = domR × codR which proves the lemma.
The interpretation of Lemma 4 and 5 is also straightforward since if there is no association between two variables or if all their outcomes are fully related, an information about a particular outcome of one of these variables bring no new information on the other variable.
Unfortunately, in all other cases, except of these two trivial situations, we need some time to check all necessary conditions. Therefore, an algorithm which enables to reduce the number of conditions to be checked to solve the problem of possible separability would be desirable. In next section we propose a very simple sufficient condition showing that variables under study are connected which may be used to conclude the lack of separability without any calculations, just at a glance. Then, in Section 5 we prove the necessary and sufficient condition for separability which gives us an efficient algorithm for checking separability of fuzzy binary decisions.
Let us recall that the support of a fuzzy set A with a membership function A : X → [0, 1] is a crisp subset supp(A) of the universe of discourse X given as follows
Suppose, sets X = {x_{1}, …, x_{n}} and Y = {y_{1}, …, y_{m}} describe all possible values of variables and , respectively. Further on following definition will be useful.
Thus, the significant part of a fuzzy binary relation R is just the reduction of this relation to the Cartesian product supp(domR) × supp(codR). It is easily seen that for a given fuzzy relation R ⊆ X × Y described by the relation matrix [R] one gets a relation matrix [&R̃] corresponding to R̃ by deleting all zero rows and columns in [R]. Therefore [&R̃] is a minor of [R].
Going back to Example 1 one can see that R̃_{1}is described by the following matrix
In the example given above the significant part of a fuzzy relation under study is equivalent to the support of that relation but it is not a rule. For every binary fuzzy relation R we have supp(R) ⊆ supp(domR) × supp(codR).
Below we state a theorem that provides an easy condition to show that given a fuzzy binary relation is not separable and therefore two variables under study are connected.
Let R ⊆ X×Y be a fuzzy binary relation with membership function R : X×Y → [0, 1] and R ≠ ∅︀. If R is separable then
Suppose the relation R is separable and, contrary to our claim, that
i.e. there exist (x_{0}, y_{0}) ∈ supp(domR) × supp(codR) such that R̃(x_{0}, y_{0}) = 0. By Definition 6 and by condition ii) in Lemma 2 we get
Hence domR(x_{0}) = 0 or codR(y_{0}) = 0 and therefore either x_{0} /∈ supp(domR) or y_{0} /∈ supp(codR) which contradicts our assumption and completes the proof.
Theorem 7 provides a quick test for the lack of separability. Below we give its equivalent version expressed in a more useful matrix representation.
If a matrix [ &R̃] corresponding to a fuzzy binary relation R contains a zero element then R is not separable and variablesandare connected.
LetX = {x_{1}, x_{2}, x_{3}, x_{4}} and Y = {y_{1}, y_{2}, y_{3}, y_{4}, y_{5}}. Suppose a fuzzy binary relation R_{3} ⊆ X×Y is described by the following relation matrix [R_{3}]
Since
contains zero element the fuzzy binary relation R_{3}is not separable.
The criterion given in Corollary 8 works, of course, in one direction only: if there are no zeros in the matrix [&R̃], the relation R may be separable or not, and further checking is necessary.
Going back to Example 1 we find that although there is no zero element in [&R̃_{2}] the relation R_{2}is not separable.
Although Theorem 7 specifies only the sufficient condition for separability of fuzzy binary relations, Corollary 8 could be helpful in some situations in concluding that some variables are connected. In the next section we prove the necessary and sufficient condition for separability requires more operations but solves the problem of separability definitely.
Let us start from recalling that the
It is clear that the support is simply zero α-cut, i.e.
Let R ⊆ X × Y denote a fuzzy binary relation such that R ≠ ∅︀. Then R is separable if and only if
Firstly, let’s note that for any two nonempty fuzzy sets A in X and B in Y and for any α ∈ [0, 1) the following equality holds
Let us also recall the well-known fact that any two fuzzy sets C and D in the same universe of discourse are equal if and only if their strong α-cut are equal for any α ∈ [0, 1), i.e.
Now suppose that a fuzzy binary relation R is separable. Then, by Definition 9 we have R = domR × codR, so by (
Now, substituting domR and codR into (
and combining (
Conversely, if (
One can easily notice that Theorem 7 implies from the above Theorem 9. Actually, if R is separable then
Below we propose a practical and efficient algorithm for checking whether a given fuzzy binary relation is separable, based on Theorem 9. We begin from generalizing the notion of the significant part of a fuzzy relation given in Definition 6.
Letα ∈ [0, 1). Theα
It is clear that zero α-significant part of a fuzzy relation is usual significant part of a fuzzy relation defined in (
Now, combining Theorem 9 and the notion of the α-significant part of a fuzzy relation we are ready for suggesting the desired algorithm testing whether a given fuzzy binary relation is separable. The general idea can be specified by the following corollary.
A fuzzy binary relation R is separable if and only if for anyα ∈ [0, 1) the corresponding matrix [&R̃^{α}] contains no element which is smaller than or equal toα.
In practice there is no need to check all α ∈ [0, 1) but only those occurring in the relation domain and codomain. Indeed, they are the only ones that can result in omitting one or more rows or columns from the original matrix. Moreover, since their number is no greater than the total number of rows and columns in the matrix, the proposed necessary and sufficient criterion for separability seems to work efficiently in practice. Actually, if X = {x_{1}, …, x_{n}} and Y = {y_{1}, …, y_{m}} then the cardinality card(W) = l ⩽ n + m.
Although it is not necessary for performing the algorithm given above, it is advisable to order values in W before moving to Step 3. Indeed, if we arrange these values in the increasing order, i.e. if W = {α_{1}, …, α_{l}} so that α_{1} < α_{2} < … < α_{l}, then in each next iteration of the loop in Step 3 we would operate with a smaller matrix than in the previous iteration.
We present the way in which our algorithm works in two examples.
Let us consider once more the relation R_{2}given in Example 1, i.e.
for which we have domR_{2} = 0.4/x_{1}+0.7/x_{2}+1/x_{3}+0.1/x_{4} and codR_{2} = 0.3/y_{1} +1/y_{2} +0.5/y_{3} +0/y_{4} +0.9/y_{5}. Thus, the potential values to be checked are only those that appear in the domain or codomain and are smaller than 1, i.e. W = {0, 0.1, 0.3, 0.4, 0.5, 07, 0.9}. So our criteria reduces to check whether [
Forα = 0 we have to omit the fourth column in [R_{2}] and we obtain
Since [
Sine there is no element smaller or equal to 0.1 in [
However, it is seen that [
Let us consider once more the relation R_{1}given in Example 1, i.e.
Here we have identical domain and codomain as in the previous example, so the set W of values to be checked is also the same as before. Thus we can find the followingα-significant parts of the fuzzy relation R_{1}:
Since none of [
In various problems of approximate reasoning and broadly perceived decision making the information whether variables (attributes) under study are connected/noninteractive and whether the corresponding fuzzy relations are separable is of importance. Therefore, a simple test for separability of fuzzy relations is desirable. In this contribution we have suggested an efficient algorithm for checking separability based on the necessary and sufficient condition. We have also indicated a simple test for detecting interactivity based on the sufficient condition. The suggested methods could be easily applied in practice.
However, some problems in the field remain open. Firstly, in the paper we have restricted our attention to fuzzy binary relations. Therefore, a generalization of the proposed methods for more dimensions would be interesting. Secondly, in this contribution we have adopted the common assumption that the Cartesian product of fuzzy sets is defined with respect to the classical t-norm (i.e. minimum) and, consequently, the minimum operator appears in the definition of separability. However, one may consider there some other t-norms and hence discuss the notion of t-separability.
No potential conflict of interest relevant to this article was reported.