Fuzzy multisets represent a particularly challenging generalization of the concept of fuzzy sets. The membership degrees of fuzzy multisets are given by multisets in 0,1 rather than single values. Mathematically, they can be also seen as a generalization of the hesitant fuzzy sets. But in this general setting, the information about repetition is not lost with fuzzy multisets; and so, the opinions given by the experts are more reliably accounted for. The definitions of the complement, union, and intersection operations for these sets and their relation with other extensions of fuzzy sets, however, is not straightforward. Aggregate unions and intersections have been shown to be equivalent to the standard definitions of union and intersection for the typical hesitant fuzzy sets. But computing them is not simple because the definitions of the aggregate operations as multiset unions of sequences based on permutations can potentially result in a huge number of operations. In this paper, we propose a new formulation for the aggregate union and intersection of fuzzy multisets that is computationally less intensive, thereby providing two algorithms amenable to computer-based calculations.
The theory of fuzzy sets, originally introduced by L. A. Zadeh [1], has been amply studied over the last few decades. Alongside the original formulation, there have appeared a number of extensions of the theory where the role of numbers in the real unit interval 0,1 as membership values is taken over by more sophisticated mathematical objects such as intervals (interval-based fuzzy sets [2]) and functions (type-2 fuzzy sets [2]). Most of these generalizations seek to account for the imprecision in determining membership by representing a tolerance around an ideal central value. But there are also some generalizations that rely on a set of possible values, even widely differing ones, as the fuzzy membership of an element. The fuzzy multisets [3] and the hesitant fuzzy sets [4] are two such approaches. Both are very similar in terms of their semantics, a fact already acknowledged in the original article where the hesitant fuzzy sets were introduced [4]. The difference between these two concepts is that hesitant fuzzy sets use crisp sets as their membership grades whereas fuzzy multisets rely on crisp multisets for this. A crisp multiset is an extension of the idea of a set where elements may appear repeated. So, a crisp set like 0.1,0.2 is a valid membership grade for a hesitant fuzzy set and a crisp multiset like 〈0.1,0.2,0.2〉 can be a membership grade for a fuzzy multiset. Both fuzzy multisets and hesitant fuzzy sets have garnered widespread recognition and further extensions of these concepts are being actively researched at present [5,6].
But the basic operations of intersection and union were defined differently for either type of fuzzy sets and the two theories are consequently different. In a recent article [7], we have argued that by using definitions of intersection and union for the fuzzy multisets that differ from the conventional ones due to S. Miyamoto [3], the gap between the two theories can be bridged. We have called these operations the aggregate intersection and aggregate union and they are also suitable as definitions for multiset-based hesitant fuzzy sets, which were already brought up in the original article about hesitant fuzzy sets, where the idea is discussed. But all the subsequent research in hesitant fuzzy sets, which has been summarized in detail by Z. Xu in a recent book [8], has focused on the set-based concept. Oddly enough, the multiset extension has mostly been neglected in the related literature. Nevertheless, the formal definition of the aggregate intersection and union does not lead to an optimal workable algorithm as it depends on a cumbersome operation. In this operation, all the possible permutations of ordered sequences of membership values for each one of the two operands must be joined through a multiset-style union. The number of steps involved explodes with large cardinalities as such an algorithm has a time complexity On!. In this paper, we work out two computationally simpler algorithms, with time complexity On, for the aggregate intersection and union.
This paper is organized as follows: Section 2 introduces the fundamental results of the fuzzy multisets and hesitant fuzzy sets, including the aggregate intersection and union which generalize the hesitant operations for the fuzzy multisets. In Section 3, explicit formulas for the aggregate intersection and union are given, followed by an analysis of an important particular case in Section 4. In Section 5, we present the algorithmic flowcharts for both operations. In Section 6, we check that the improved algorithmic performance matches our expectations. Finally, in Section 7, we sum up the conclusions of our research.
2. PRELIMINARY CONCEPTS
2.1. Fuzzy Sets and Multisets
In this paper, we will assume that the basic definitions and results of ordinary fuzzy sets are known and understood by the reader. Given a reference set (the universe) X, an ordinary fuzzy set is a function A:X→0,1 and the family of all the ordinary fuzzy sets over X, FX, is called the ordinary fuzzy power set over X [2]. For an element x∈X, its image by A is called its membership value.
Given a fuzzy set A over a finite universe X, its cardinality |A| is the real number defined as A:=∑x∈XAx and its support, SuppA, is the set x∈X|Ax>0. Inclusion of fuzzy sets is defined as a partial order relation ⊆ such that if A and B are fuzzy sets, then A⊆B when Ax⩽Bx for all x∈X. Given two fuzzy sets A and B, their standard intersection A∩B is the fuzzy set defined by A∩Bx=minAx,Bx and their standard union A∪B is the fuzzy set defined by A∪Bx=maxAx,Bx.
Similarly, we assume a basic knowledge of multisets. Given a reference set U, a multiset is a function M:U→ℕ (including zero) and the family of all the multisets over U, ℕU, is called the power multiset over U. For an element u∈U, its image by M is called its multiplicity value.
Given a multiset M over a finite universe U, its cardinality |M| is the natural number defined as |M|:=∑u∈UMu and its support, SuppM, is the set u∈U|Mu>0. Inclusion of multisets is defined as a partial order relation ⊆ such that if M and N are multisets, then M⊆N when Mu⩽Nu for all u∈U. Given two multisets M and N, their intersection M∩N is the multiset defined by M∩Nu=minMu,Nu and their union M∪N is the multiset defined by M∪Nu=maxMu,Nu [3,9].
In terms of notational convention, just as a set S can be represented by listing its members S=a,b,…, a set-like notation M=〈a,b,b,…〉, with the elements repeated as many times as their multiplicity value, is commonly used when the multiset M over a universe U=a,b,… has a finite support for any u∈U. In order to avoid confusion with sets, we will use angular brackets 〈〉 for multisets.
2.2. Fuzzy Multisets
The two concepts of fuzzy sets and multisets can be combined into the concept of a fuzzy multiset as a function X→ℕ0,1, where the membership values are multisets over 0,1 rather than single real numbers [3]. The family of all the fuzzy multisets over X, FMX, is called the fuzzy power multiset over X.
The first definitions of intersection and union were given by R. R. Yager [10], but they did not work as an extension of the fuzzy set operations. This was corrected by the definitions later proposed by S. Miyamoto [3] and which have become the standard ones. In Subsection 2.6 below, we review these definitions.
2.3. Hesitant Fuzzy Sets
Hesitant fuzzy sets were proposed by V. Torra in [4] as yet another generalization of the ordinary fuzzy sets [4]. A hesitant fuzzy set A˜ is a function A˜:X→P0,1, where P0,1 is the family of all the subsets of the real closed interval 0,1 [4]. For an element x∈X, its image by A˜ is called its hesitant element [8]. The family of all the hesitant fuzzy sets over X, FHX, is called the hesitant fuzzy power set over X. Those hesitant fuzzy sets such that their hesitant elements are all finite are referred to as typical hesitant fuzzy sets [4] and are the only ones that we will discuss.
Finding good definitions for the operations on hesitant fuzzy sets is tricky. They should be defined in such a way that they generalize those of the ordinary fuzzy sets and also those of other fuzzy set extensions, such as the interval-valued fuzzy sets, that appear as special cases within the hesitant framework. In Subsection 2.7, we sum up the definitions for the hesitant intersection and union.
2.4. Difference Between Fuzzy Multisets and Hesitant Fuzzy Sets
Based on their definitions as functions, fuzzy multisets and hesitant fuzzy sets differ in that the former support repeated membership values. This is a limitation of hesitant fuzzy sets. In a common situation, the values come from a fixed number of criteria applied to each element of the universe. For example, if three criteria are used, the membership of an element may be evaluated as either a hesitant element 0.1,0.2,0.3 or a multiset 〈0.1,0.2,0.3〉, with the same information content. But if two of the criteria lead to the same value, a multiset 〈0.1,0.2,0.2〉 would be matched by a hesitant element 0.1,0.2, where the information that the second value was twice as popular is lost. This limitation was mentioned in the original article about hesitant fuzzy sets [4], and the alternative multiset-based hesitant fuzzy sets were also proposed.
But what is the difference between Yager and Miyamoto’s fuzzy multisets and Torra’s multiset-based hesitant fuzzy sets? If P0,1 is replaced with ℕ0,1 then the definition becomes the same. The difference lies in the fact that both theories have evolved using different definitions for some of the common operations. Most importantly, the intersection and union as conventionally defined for fuzzy multisets are not equivalent to the accepted definitions for hesitant fuzzy sets. It is this difference in the operations that sets the two theories apart. In our recent paper [7], we introduced some general definitions of intersection and union where Miyamoto’s definitions appear as particular cases, as well as the additional multiset-based definitions that generalize the hesitant ones, which are the focus of this paper. In Subsection 2.7 below, we review these definitions.
2.5. Sequences
Another basic concept that we will need is that of a finite sequence of length n∈ℕ or n-tuple, which for a universe U can be defined as an element of Un. The elements in a set or a multiset of cardinality n can always be arranged as a sequence. Given a finite subset S⊆U or a multiset M∈ℕU, a function s:S⊆U||S|=n→Un or s:M∈ℕU||M|=n→Un is called an ordering strategy, with the family of all such functions being denoted by OSS and OSM, respectively. The number of possible ordering strategies is the number of permutations of n elements (with repetition in the multiset case) and, when U is totally ordered, two common sorting strategies are the ascending sort s↑ and the descending sort s↓, where the elements are sorted in ascending or descending order, respectively. We will use parentheses () for sequences; for example, s↓1,2,3=3,2,1, s↓〈1,2,2〉=2,2,1.
2.6. Miyamoto’s Intersection and Union for Fuzzy Multisets
Defining binary operations between fuzzy multisets is simpler when the membership values have the same cardinality. To handle this case, we will define subfamilies of the fuzzy multisets where the cardinality is fixed for each member of the universe X.
Definition 1.
Let X be a universe. Given a function m:X→ℕ, an m-regular fuzzy multiset A^ over the universe X is a fuzzy multiset such that, for each element of the universe x∈X, |A^x|=mx. We call m a cardinality map. The family of all the m-regular fuzzy multisets over X, FM|⋅|=mX, is called the m-regular fuzzy power multiset [7].
Miyamoto’s definitions of intersection and union are based on operating in a coordinate wise fashion on the ordered sequences that result from picking the descending sort s↓ as the ordering strategy.
Definition 2.
Let X be a universe and let m:X→ℕ be a cardinality map. Given two m-regular fuzzy multisets A^ and B^, for each x∈X, s↓A^x and s↓B^x are the two ordered sequences of the crisp multisets A^x and B^x with the values sorted in descending order. For each element x∈X, two new ordered sequences μA^∩B^x and μA^∪B^x can be built with the pairwise minima and maxima, respectively with i∈1,…,mx [3]:
The m-regular intersection (or Miyamoto’s intersection) A^∩B^ and the m-regular union (Miyamoto’s union) A^∪B^ are the m-regular fuzzy multisets defined by
When the two fuzzy multisets A^ and B^ have different cardinalities for an element x∈X, an additional step that equalizes the length of the ordered sequences to the maximum of the two will be required in order to apply Definition 2. We will refer to that operation as regularization [7]. The most common regularization strategies consist in increasing the count of either the maximum or the minimum membership value, which can be called the optimistic and pessimistic strategies [8,11]. Note that the regularization step involves the ordered sequences used in the calculation and not the hesitant elements themselves which, being crisp sets, cannot have repeated elements. Adding repeated values is the only option that preserves the underlying hesitant element for the ordered sequence (unlike the alternative of adding average values) and the pessimistic and optimistic approaches behave like a lower and an upper bound for all the possible repetitions of values. This mechanism extends the validity of Definition 2 to those cases where the cardinalities do not match.
2.7. Aggregate Intersection and Union for Fuzzy Multisets
Miyamoto’s definitions of intersection and union are based on the pairwise minima and maxima after sorting the values in descending order. As the same approach can be replicated with any sorting strategy, it is possible to establish a more general definition parametrized with the sorting strategy as follows:
Definition 3.
Let X be a universe and let m:X→ℕ be a cardinality map. Given two m-regular fuzzy multisets A^ and B^ and two ordering strategies sA and sB, for each element x∈X, two new sequences μA^∩sA,sBB^x and μA^∪sA,sBB^x can be built with the pairwise minima and maxima with i∈1,…,mx
μA^∩sA,sBB^xi:=minsAA^xi,sBB^xi
μA^∪sA,sBB^xi:=maxsAA^xi,sBB^xi.
The m-regular sA,sB-ordered intersection A^∩sA,sBB^ and the m-regular sA,sB-ordered union A^∪sA,sBB^ are the two m-regular fuzzy multisets defined by
For example, in a single-element universe X=x, we can define two 3-regular fuzzy multisets A^ and B^ as A^x=〈0.1,0.6,0.6〉 and B^x=〈0.2,0.2,0.4〉. If we use a common ascending sorting strategy s↑ such that s↑〈0.1,0.6,0.6〉=0.1,0.6,0.6 and s↑〈0.2,0.2,0.4〉=0.2,0.2,0.4, then their s↑-ordered intersection is the fuzzy multiset given by the membership function A^∩s↑,s↑B^x=〈0.1,0.2,0.4〉 and the union is given by A^∩s↑,s↑B^x=〈0.2,0.6,0.6〉.
These definitions can be extended to fuzzy multisets with mismatched cardinalities through an initial regularization step [7].
Miyamoto’s definitions are now the particular case when both sorting strategies are chosen as sA=sB=s↓. It can easily be proved that choosing sA=sB=s↑ yields the same results for the operations, so sorting in either descending or ascending order is just a matter of convention. But other sorting strategies lead to different results, so the choice of sA and sB does affect the behavior of the operations.
As we argued in our recent work [7], since we are working with finite sets we can make a definition that is independent of any particular sorting strategy by taking the multiset union of the ordered intersections and unions (see Definition 3) resulting from all the combinations of possible sorting strategies sA,sB. This idea leads to the following definitions:
Definition 4.
Let X be a universe and let A^,B^∈FMX be two fuzzy multisets. The aggregate intersection and the aggregate union of A^ and B^ are the two fuzzy multisets A^∩aB^ and A^∪aB^ such that, for any element x∈X, A^∩aB^x is the multiset union of the sA,sB-ordered intersections and A∪aBx is the multiset union of the sA,sB-ordered unions for all the possible pairs of ordering strategies sA,sB:
Using the same example as for the ordered operations above, the fact that all permutations must be taken into account means that now we can get not only 〈0.1,0.2,0.4〉 for the intersection at x, but also 〈0.1,0.2,0.2〉 if we pair the values 0.4 and 0.6 together, so the aggregate intersection will be A^∩aB^x=〈0.1,0.2,0.2,0.4〉. Similarly, the aggregate union is given by A^∩aB^x=〈0.2,0.4,0.6,0.6〉.
All these forms of intersection and union that we have defined are consistent with the definitions for the ordinary fuzzy sets. But this aggregate form of intersection and union is in addition also consistent with the definitions for the typical hesitant fuzzy sets, which we review now.
Definition 5.
Let X be the universe and let A˜ and B˜∈FHX be two hesitant fuzzy sets. The hesitant intersection and the hesitant union of A˜ and B˜ are the two hesitant fuzzy sets A˜∩hB˜ and A˜∪hB˜ defined, respectively, as follows [4, p. 534]:
A˜∩hB˜x=α∈A˜x∪B˜x,
with α⩽minmaxA˜x,maxB˜x.
A˜∪hB˜x=α∈A˜x∪B˜x,
with α⩾maxminA˜x,minB˜x.
These definitions for the intersection and the union are consistent with the requirement that they should reduce to the ordinary fuzzy definitions with single-valued hesitant elements and, when hesitant fuzzy sets are regarded as a form of type-2 fuzzy sets (in their general form, without any convexity assumptions), can also be shown to be consistent with the type-2 definitions [12]. As we show in the next proposition, they are also consistent with the aggregate operations for multisets. But we need an additional formal definition first:
Definition 6.
Let X be the universe and let A^∈FMX be a fuzzy multiset. Its hesitant fuzzy set support SupphA^ is the hesitant fuzzy set such that, for any element x∈X, SupphA^x=SuppA^x, where Supp is the support in the multiset sense, the set of values with nonzero multiplicity.
The function Supph that maps a fuzzy multiset to its hesitant fuzzy set support is obviously injective. If we restrict the fuzzy multisets to those that only have multiplicity values of 0 or 1, then it is a bijection and we can similarly define an equivalent fuzzy multiset for any given hesitant fuzzy set. It is this equivalence that allows us to identify the aggregate intersection and union for fuzzy multisets with the hesitant intersection and union, an intuitive result that can be formalized through the next proposition.
Proposition 1.
LetXbe the universe and letA^andB^∈FMXbe two fuzzy multisets. Then the following relations hold:
In order to prove the first equality, given an element x∈X, we need to prove that
SupphA^∩aB^x=SupphA^∩hSupphB^x.
Let t∈0,1 and let us consider three possible cases.
Case 1. If A^xt=0 and B^xt=0, t is not in the support of either fuzzy multiset and, by definition, t∉SupphA^x and t∉SupphB^x and, since the hesitant intersection is defined as a subset of the union of the hesitant elements then
t∉SupphA^∩hSupphB^x.
On the other hand, t cannot appear in either of the sequences sAA^x and sBB^x used for the ordered intersection in Definition 3 for any ordering strategy whatsoever, and so A^∩aB^xt=0 or, equivalently,
t∉SuppA^∩aB^x,
and then
t∉SupphA^∩aB^x.
Case 2. Let us consider A^xt>0 such that there is no t′∈0,1 with t⩽t′ such that B^xt′>0; i.e. t>maxu∈0,1|B^xu>0.
As t is part of the support of A^x, t∈SupphA^x and it will be in the union SupphA^x∪SupphB^x but, as t is larger than the maximum of the hesitant element SupphB^x then
t∉SupphA^∩hSupphB^x.
On the other hand, t will appear in the sequences sAA^x but all the values in sBB^x are smaller, so it will not make it into the aggregate intersection,
t∉SuppA^∩aB^x.
Consequently,
t∉SupphA^∩aB^x.
Case 3. Let us consider A^xt>0 such that there is t′∈0,1 with t⩽t′ and B^xt′>0; i.e. t⩽maxu∈0,1|B^xu>0. As t is part of the support of A^x, t∈SupphA^x whereas t' is in the support of B^x, so t'∈SupphB^x and then,
t∈SupphA^∩hSupphB^x.
On the other hand, t will appear in the sequences sAA^x and t′ will appear in the sequences sBB^x in the ordered intersections. As we need to take a multiset union of all the possible combinations of the ordered intersections, there will be at least a combination where t gets paired with t′ and, as t is the minimum of the two, A^∩aB^xt>0. This,
t∈SuppA^∩aB^x.
Consequently,
t∈SupphA^∩aB^x.
For the union, the proof is completely analogous, with Case 2 using a t value that is less than the minimum of all the values in the support of B^x and Case 3 using a t value not less than that minimum.
We have thus proved that the aggregate intersection and union are more general operations that reduce to the hesitant intersection and union as particular cases. However, unlike the elegant definitions of the latter (see Definition 5), the way we have defined the aggregate operations is unwieldy for actual use as it involves taking all the possible combinations of all the permuted sequences made up of the membership values in each multiset, an operation with time complexity On!. In the next section, we work out an expression for the aggregate operations that generalizes Definition 5 through a simple formula with time complexity On.
3. THE EXPLICIT FORM OF THE AGGREGATE OPERATIONS
In order to write an explicit form for the aggregate intersection and union, we will need the concept of α-cuts for multisets first. Besides the normal “upper” version that zeroes out those membership values below α [3], we will also define a custom lower version that zeroes out the values above α.
Definition 7.
Let X be the universe. For a fuzzy multiset A^∈FMX and a real number α∈0,1, the strong (upper) α-cut of A^ is the crisp multiset A^>α∈ℕX where the multiplicity values for each element x∈X are given by the cardinality of the submultiset of A^x restricted to those values strictly greater than α:
[A^]>α(x):=∑∈Supp(A^(x))r>αA^(x)(t).
And, similarly, the lower version of the α-cut:
Definition 8.
Let X be the universe. For a fuzzy multiset A^∈FMX and a real number α∈0,1, the strong lower α-cut of A^ is the crisp multiset A^<α∈ℕX, where the multiplicity values for each element x∈X are given by the cardinality of the submultiset of A^x restricted to the values strictly less than α:
[A^]<α(x):=∑∈Supp(A^(x))t<αA^(x)(t).
We need these definitions of the strong α-cuts for the next pair of propositions, which are the most important contributions of this paper:
Proposition 2.
The aggregate intersection of two fuzzy multisetsA^andB^over a universeXcan be expressed explicitly as a function as follows:
In order to prove this equality, we will consider a fixed x∈X and analyze the different possible cases for the fuzzy membership parameter t∈0,1 separately.
Case 1. Let t be such that both A^xt=0 and B^xt=0. As t does not appear in either fuzzy multiset, the result of A^∩aB^xt according to Definition 4 must be 0. And the above formula yields 0 as a result too.
Case 2. Let t be such that A^xt>0 and B^xt=0. Now t appears in one of the fuzzy multisets, and the result of A^∩aB^xt according to Definition 4 will be the maximum number of possible pairings between the A^xt occurrences of t in the sequences sAA^x and those values in B^x that are greater than t. That number is obviously minA^xt,B^>tx. As we have B^xt=0, the other two terms evaluate to zero and the equality holds in this case too.
Case 3. Let t be such that A^xt=0 and B^xt>0. This is the same as Case 2, with the roles of the two operands swapped, so the aggregate intersection will be given by the second term minB^xt,A^>tx, with the other terms being zero.
Case 4. Let t be such that A^xt>0 and B^xt>0. This is the nontrivial case where the three terms contribute to the result. As the aggregate definition is based on taking the maximum possible multiplicity among all the permutations of sequences, we have to identify the most favorable situations. The A^xt occurrences of t in the sequences sAA^x will make it into the aggregate intersection if they can be paired with values in sBB^x that are greater than t and the maximum number of such pairings is obviously B^>tx. We have thus accounted for minA^xt,B^>tx contributions.
Now if A^xt⩽B^>tx we have exhausted the t values in A^x, but if that is not the case there will be a positive number A^xt−B^>tx of occurrences of t that can still be paired with the t values in B^x in the final step. Before that, we repeat the same reasoning for the B^xt occurrences of t in the sequences sBB^x and, again, a maximum of A^>tx will find their way into the aggregate intersection, independently of the ones in A^x, which results in the minB^xt,A^>tx contribution. Finally, if both A^xt>B^>tx and B^xt>A^>tx, there remains a number of t values, the minimum of the two subtractions, that have not been paired with any greater values but which can, in the most favorable sequence combination, be paired with each other, leading to the third term in the equality.
And similarly, for the union.
Proposition 3.
The aggregate union of two fuzzy multisetsA^andB^over a universeXcan be expressed explicitly as a function as follows:
The proof is completely analogous to the one for the aggregate intersection (see proof of Proposition 2).
4. THE EFFECT OF OVERLAPPING RANGES
It should be remarked that the aggregate operations do not preserve the cardinality of the operands, unlike the ordered operations. For example, if we have two fuzzy multisets A^x=〈0.1,0.4〉 and B^x=〈0.2,0.4〉 in a single-element universe X=x, their aggregate intersection is A^∩aB^x=〈0.1,0.2,0.4〉. But it can be proved that this behavior only occurs when the involved multisets have overlapping ranges of values. In the most usual cases when using fuzzy multisets, we may have membership multisets like 〈0.1,0.2,0.2〉 or 〈0.8,0.8,0.9〉 but a membership multiset like 〈0.1,0.5,0.9〉 would be hard to justify. This means that the operational differences between the ordered and the aggregate operations are more theoretical than practical in nature. The following proposition formalizes this observation.
Proposition 4.
LetXbe the universe and letA^andB^∈FMXbe two fuzzy multisets. For an elementx∈X, ifA^xandB^xspan ranges of values that do not overlap; that is,max SuppA^x⩽min SuppB^xormax SuppB^x⩽min SuppA^x, then the result of thesA,sB-ordered intersection andsA,sB-ordered union is independent of the choice ofsAandsB:
Let us assume, without loss of generality, that A^x is the fuzzy multiset with the lower values, max SuppA^x⩽min SuppB^x. Then for any pair of ordering strategies sA and sB, if A^=〈a1,a2,…〉 and B^=〈b1,b2,…〉 we will get the sequences aσA1,aσA2,… and bσB1,bσB2,…, σA and σB being the permutations on the index space caused by the ordering strategies sA and sB.
As none of the ai values are greater than any of the bj values for any pair of indices i, j, we have
A^∩sA,sBB^x=A^x
and
A^∪sA,sBB^x=B^x,
regardless of the ordering strategies.
We have proved this for a fixed element x∈X. If the condition of nonoverlapping ranges holds for any element, then the independence of the sorting strategy applies to the whole fuzzy multisets, and not just to the particular multisets evaluated at x. We conclude with the following corollary:
Corollary 5.
LetXbe the universe and letA^andB^∈FMXbe two fuzzy multisets such that they span ranges of values that do not overlap for any element, that is, eithermaxSuppA^x⩽min SuppB^xormax SuppB^x⩽min SuppA^xfor allx∈X, then the aggregate intersection is the same as Miyamoto’s intersection (or any othersA,sB-ordered intersection) and the aggregate union is the same as Miyamoto’s union (or any othersA,sB-ordered union).
5. THE ALGORITHMS
The computation of aggregate intersection and union for a fixed element x∈X is not straightforward. Thus, in this section we propose an algorithm to compute them in an effcient way. It is assumed that there is a data structure that represents a multiset together with related operations for element insertion and look-up (like, e.g., the std::multiset class in the C++ standard library) and a similar data structure for sets (a std::set in C++). As the algorithm (see Algorithm 1) involves an iteration over the elements of the multisets, its time complexity is On in terms of the size of the input multisets.
In both algorithms (see Algorithms 2 and 3), we can improve the efficiency by handling some special cases separately. If the value ranges do not overlap, we can rely on Proposition 4 to skip formulas defined in Propositions 2 and 3 and assign the result directly in an O1 operation. This optimization is handled by the first two if statements in the algorithm. When that is not the case, the pseudocode in the second nested else block implements the hesitant definitions (see Definition 5).
6. NUMERICAL RESULTS
With the aim of checking that the improved algorithmic performance matches our expectations, we have run a test in C++ consisting in carrying out some aggregate intersections of pairs of input multisets with a growing length.
Algorithm 1: Algorithm for computing aggregate intersection and union based on Definition 4
1: function Intersection a,b ⊳ Input arguments: two multisets a and b
2: result ←create_multiset() ⊳ Empty initialization of a new multiset
3: b_array←multiset_to_sorted_arrayb
4: size←sizea ⊳ Must equal size(b) and size(b_array)
5: first_permutation←true
6: permutations_remain←true
7: whilepermutations_remaindo
8: current_iteration←create_multiset()
9: fori=0,i<size,i++do
10: multiset_insertcurrent_iteration,minai,b_arrayi ⊳ For Intersection
11: multiset_insertcurrent_iteration,maxai,b_arrayi ⊳ For Union
34: multiset_insertresult,t,t_count⊳ Inserts tt_count times
35: end for
36: end if
37: end if
38: returnresult
39: end function
For our timing test, and considering that the optimized algorithm is trivial in the case of nonoverlapping ranges, we will require the input multisets to have overlapping ranges. This is something that can be done by starting off with two multisets a=〈0.1,0.2〉 and b=〈0.2,0.3〉 for the first iteration and then inserting additional overlapped values between 0.2 and 0.3. We will add the n values 0.2+i/n+1×0.1 with i=1,…,n to the first multiset and the n values 0.2+2i−1/2n+2×0.1 with i=1,…,n to the second multiset. This will give the multisets 〈0.1,0.2,0.25〉 and 〈0.2,0.225,0.3〉 for n=1, 〈0.1,0.2,0.233,0.266〉 and 〈0.2,0.2166,0.25,0.3〉 for n=2, and so on.
In a loop for growing values of n=0,1,2,…, the test builds the two input multisets of length n+2 and measures the elapsed time. These timing results, in microseconds, are finally dumped to a text file and are displayed here in Table 1. The test has been compiled and run using Microsoft Visual Studio 2017 and it leaves no doubt that there is an enormous gap in performance between the two algorithms.
The difference between the two algorithms, even for relatively small input lengths, is so glaring that it has not been deemed necessary to attempt repeated tests. With an input length of 10, the permutation-based algorithm for one single intersection takes a whopping 20 seconds to complete in release mode, whereas the new and more efficient algorithm for the same input length stays in the vicinity of 20 μs, a million times faster. Further optimizations may be worth exploring if the concept of these aggregate operations on fuzzy multisets turns out to be useful. At this time, the only existing definitions for the aggregate operations are those of the original article [7] and the formulas we have presented in the previous section, so only these two approaches can be compared.
Algorithm 3: Algorithm for computing the aggregate union based on Proposition 3
1: function Union a,b⊳ Input arguments: two multisets a and b
2: result←create_multiset()⊳ Empty initialization of a new multiset
Graph plotting the results of the timing test for the aggregate intersection.
7. CONCLUSION
In this paper, we have reviewed the properties of the aggregate intersection and union for fuzzy multisets and their relation with the equivalent operations for hesitant fuzzy sets and we have proposed formulas for their efficient calculation. Furthermore, we have also proved that the discrepancies between these operations vanish in the typical situations where the multiple membership values for an element remain in close proximity to one another and the membership ranges for two elements do not overlap. We have also presented the explicit algorithms for these operations. Finally, we have carried out a test in C++ to verify that the new algorithms do indeed execute much faster.
The basic operations of intersection and union are essential to any extension of fuzzy sets. In this case, the proposed algorithm can be used as an alternative to the sorted Miyamoto-style operations with fuzzy multisets and also as a multiset-based extension of the hesitant fuzzy set operations. Further work will be needed to test the merits of the aggregate operations in real use cases involving fuzzy multisets and also with nonstandard t-norms and t-conorms and with general membership grades other than 0,1.
CONFLICT OF INTEREST
The authors confirm that all commercial affiliations, stock ownership, equity interests, or patent licensing arrangements that could be considered to pose a financial conflict of interest in connection with the work have been disclosed.
Funding Statement
The authors confirm that all funding sources supporting the work and all institutions or people who contributed to the work, but who do not meet the criteria for authorship, are acknowledged.
ACKNOWLEDGMENTS
This work was supported by project TIN2017-87600-P from the Ministry of Economy, Industry and Competitiveness of Spain, project PGC2018-098623-B-I00 from the Ministry of Science, Innovation and Universities of Spain and project IDI/2018/000176 from the Department of Employment, Industry and Tourism of Asturias.
TY - JOUR
AU - Ángel Riesgo
AU - Pedro Alonso
AU - Irene Díaz
AU - Susana Montes
PY - 2019
DA - 2019/08/05
TI - An Algorithmic Approach for Computing Unions and Intersections Between Fuzzy Multisets
JO - International Journal of Computational Intelligence Systems
SP - 833
EP - 841
VL - 12
IS - 2
SN - 1875-6883
UR - https://doi.org/10.2991/ijcis.d.190724.001
DO - 10.2991/ijcis.d.190724.001
ID - Riesgo2019
ER -
