# International Journal of Computational Intelligence Systems

Volume 12, Issue 2, 2019, Pages 833 - 841

# An Algorithmic Approach for Computing Unions and Intersections Between Fuzzy Multisets

Authors
Ángel Riesgo1, Pedro Alonso2, Irene Díaz3, Susana Montes1, *
1Department of Statistics and O.R., University of Oviedo, Federico García Lorca, Oviedo, Asturias 33007, Spain
2Department of Mathematics, University of Oviedo, Federico García Lorca, Oviedo, Asturias 33007, Spain
3Computer Science Department, University of Oviedo, Jesús Arias de Velasco, Oviedo, Asturias 33005, Spain
*Corresponding author. E-mail: montes@uniovi.es
Corresponding Author
Susana Montes
Received 5 October 2018, Accepted 20 July 2019, Available Online 5 August 2019.
DOI
10.2991/ijcis.d.190724.001How to use a DOI?
Keywords
Fuzzy sets; Fuzzy multisets; Aggregate union; Aggregate intersection
Abstract

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.

Open Access

## 1. INTRODUCTION

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.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:X0,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 xX, 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:=xXAx and its support, SuppA, is the set xX|Ax>0. Inclusion of fuzzy sets is defined as a partial order relation such that if A and B are fuzzy sets, then AB when AxBx for all xX. Given two fuzzy sets A and B, their standard intersection AB is the fuzzy set defined by ABx=minAx,Bx and their standard union AB is the fuzzy set defined by ABx=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 uU, 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|:=uUMu and its support, SuppM, is the set uU|Mu>0. Inclusion of multisets is defined as a partial order relation such that if M and N are multisets, then MN when MuNu for all uU. Given two multisets M and N, their intersection MN is the multiset defined by MNu=minMu,Nu and their union MN is the multiset defined by MNu=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 uU. 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 X0,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˜:XP0,1, where P0,1 is the family of all the subsets of the real closed interval 0,1 [4]. For an element xX, 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 SU or a multiset MU, a function s:SU||S|=nUn or s:MU||M|=nUn 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, s1,2,3=3,2,1, s1,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 xX, |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 xX, sA^x and sB^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 xX, two new ordered sequences μA^B^x and μA^B^x can be built with the pairwise minima and maxima, respectively with  i1,,mx [3]:

μA^B^xi:=minsA^xi,sB^xiμA^B^xi:=maxsA^xi,sB^xi.

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

A^B^xt=i1imx,μA^B^xi=tA^B^xt=i1imx,μA^B^xi=t.

When the two fuzzy multisets A^ and B^ have different cardinalities for an element xX, 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 xX, two new sequences μA^sA,sBB^x and μA^sA,sBB^x can be built with the pairwise minima and maxima with  i1,,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

A^sA,sBB^xt:=i1imx,μA^sA,sBB^xi=tA^sA,sBB^xt:=i1imx,μA^sA,sBB^xi=t.

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 s0.1,0.6,0.6=0.1,0.6,0.6 and s0.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,sB^x=0.1,0.2,0.4 and the union is given by A^s,sB^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 xX, A^aB^x is the multiset union of the sA,sB-ordered intersections and AaBx is the multiset union of the sA,sB-ordered unions for all the possible pairs of ordering strategies sA,sB:

A^aB^(x)=sAOS(A^)sBOS(B^)A^(sA,sB)B^(x)    xXA^aB^(x)=sAOS(A^)sBOS(B^)A^(sA,sB)B^(x)    xX.

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˜xB˜x,
with αminmaxA˜x,maxB˜x.
A˜hB˜x=αA˜xB˜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 xX, 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.

Let X be the universe and let A^ and B^FMX be two fuzzy multisets. Then the following relations hold:

SupphA^aB^=SupphA^hSupphB^SupphA^aB^=SupphA^hSupphB^.

### Proof.

In order to prove the first equality, given an element xX, we need to prove that

SupphA^aB^x=SupphA^hSupphB^x.

Let t0,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, tSupphA^x and tSupphB^x and, since the hesitant intersection is defined as a subset of the union of the hesitant elements then

tSupphA^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,

tSuppA^aB^x,
and then
tSupphA^aB^x.

Case 2. Let us consider A^xt>0 such that there is no t0,1 with tt such that B^xt>0; i.e. t>maxu0,1|B^xu>0.

As t is part of the support of A^x, tSupphA^x and it will be in the union SupphA^xSupphB^x but, as t is larger than the maximum of the hesitant element SupphB^x then

tSupphA^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,

tSuppA^aB^x.

Consequently,

tSupphA^aB^x.

Case 3. Let us consider A^xt>0 such that there is t0,1 with tt and B^xt>0; i.e. tmaxu0,1|B^xu>0. As t is part of the support of A^x, tSupphA^x whereas t' is in the support of B^x, so t'SupphB^x and then,

tSupphA^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,

tSuppA^aB^x.

Consequently,

tSupphA^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 xX 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 xX 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 multisets A^ and B^ over a universe X can be expressed explicitly as a function as follows:

A^aB^xt=minA^xt,B^>tx+minB^xt,A^>tx+max0,minC^xt,
for t0,1, with
C^xt=A^xtB^>tx,B^xtA^>tx.

### Proof.

In order to prove this equality, we will consider a fixed xX and analyze the different possible cases for the fuzzy membership parameter t0,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^xtB^>tx we have exhausted the t values in A^x, but if that is not the case there will be a positive number A^xtB^>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 multisets A^ and B^ over a universe X can be expressed explicitly as a function as follows:

A^aB^xt=minA^xt,B^<tx+minB^xt,A^<tx+max0,minC^xt,
for t0,1, with
C^xt=A^xtB^<tx,B^xtA^<tx.

### Proof.

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.

Let X be the universe and let A^ and B^FMX be two fuzzy multisets. For an element xX, if A^x and B^x span ranges of values that do not overlap; that is, max SuppA^xmin SuppB^x or max SuppB^xmin SuppA^x, then the result of the sA,sB-ordered intersection and sA,sB-ordered union is independent of the choice of sA and sB:

A^sA,sBB^x=A^sA,sBB^xA^sA,sBB^x=A^sA,sBB^x
sA,sB,sA,sBOSX.

### Proof.

Let us assume, without loss of generality, that A^x is the fuzzy multiset with the lower values, max SuppA^xmin 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 xX. 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.

Let X be the universe and let A^ and B^FMX be two fuzzy multisets such that they span ranges of values that do not overlap for any element, that is, either maxSuppA^xmin SuppB^x or max SuppB^xmin SuppA^x for all xX, then the aggregate intersection is the same as Miyamoto’s intersection (or any other sA,sB-ordered intersection) and the aggregate union is the same as Miyamoto’s union (or any other sA,sB-ordered union).

## 5. THE ALGORITHMS

The computation of aggregate intersection and union for a fixed element xX 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_arraymultiset_to_sorted_arrayb

4: sizesizea ⊳ Must equal size(b) and size(b_array)

5: first_permutationtrue

6: permutations_remaintrue

7: while permutations_remain do

8: current_iterationcreate_multiset()

9: for i=0,i<size,i++ do

10: multiset_insertcurrent_iteration,minai,b_arrayi ⊳ For Intersection

11: multiset_insertcurrent_iteration,maxai,b_arrayi ⊳ For Union

12: end for

13: if first_permutation then

14: resultcurrent_iteration

15: first_permutationfalse

16: else

17: resultcrisp_multiset_unionresult,current_iteration

18: end if

19: permutations_remainnext_permutationb_array

20: end while

21: return result

22: end function

### Algorithm 2: Algorithm for computing the aggregate intersection based on Proposition 2

1: function Intersection a,b ⊳ Input arguments: two multisets a and b

2: resultcreate_multiset() ⊳ Empty initialization of a new multiset

3: a_maxmultiset_maxa

4: b_minmultiset_minb

5: if a_maxb_min then

6: resulta

7: else

8: a_minmultiset_mina

9: b_maxmultiset_maxb

10: if b_maxa_min then

11: resultb

12: else

13: a_supportmultiset_supporta

14: b_supportmultiset_supportb

15: if a_maxb_max then

16: if a_max<b_max then ⊳ Ignore values > min(a_max, b_max)

17: b_supportmultiset_lower_boundb_support,a_max

18: else

19: a_supportmultiset_lower_bounda_support,b_max

20: end if

21: end if

22: supportset_uniona_support,b_support

23: for all tsupport do

24: a_upper_boundmultiset_strict_upper_bounda,t

25: a_up_lengthmultiset_lengtha_upper_bound ⊳ This is [A^]>t

26: b_upper_boundmultiset_strict_upper_boundb,t

27: b_up_lengthmultiset_lengthb_upper_bound ⊳ This is [B^]>t

28: t_a_countmultiset_element_counta,t

29: t_b_countmultiset_element_countb,t

30: t_countmint_a_count,b_up_length+mint_b_count,a_up_length

31: if t_a_countb_up_length AND t_b_counta_up_length then

32: t_count+=mint_a_countb_up_length,t_b_counta_up_length

33: end if

34: multiset_insertresult,t,t_count⊳ Inserts t t_count times

35: end for

36: end if

37: end if

38: return result

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+2i1/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.

Input Length Algorithm 1μs Algorithm 2μs
2 8 0
3 12 4
4 59 6
5 393 9
6 3,455 17
7 22,213 12
8 185,912 16
9 1,896,988 19
10 19,972,942 21
Table 1

Timing test for aggregate intersection.

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: resultcreate_multiset()⊳ Empty initialization of a new multiset

3: a_maxmultiset_maxa

4: b_minmultiset_minb

5: if a_maxb_min then

6: resultb

7: else

8: a_minmultiset_mina

9: b_maxmultiset_maxb

10: if b_maxa_min then

11: resulta

12: else

13: a_supportmultiset_supporta

14: b_supportmultiset_supportb

15: if a_minb_min then

16: if a_min<b_min then⊳ Ignore values < max(a_min, b_min)

17: a_supportmultiset_upper_bounda_support,b_min

18: else

19: b_supportmultiset_upper_boundb_support,a_min

20: end if

21: end if

22: supportset_uniona_support,b_support

23: for all tsupport do

24: a_lower_boundmultiset_strict_lower_bounda,t

25: a_low_lengthmultiset_lengtha_lower_bound⊳ This is [A]<t

26: b_lower_boundmultiset_strict_lower_boundb,t

27: b_low_lengthmultiset_lengthb_lower_bound⊳ This is [B]<t

28: t_a_countmultiset_element_counta,t

29: t_b_countmultiset_element_countb,t

30: t_countmint_a_count,b_low_length+mint_b_count,a_low_length

31: if t_a_countb_low_length AND t_b_counta_low_length then

32: t_count+=mint_a_countb_low_length,t_b_counta_low_length

33: end if

34: multiset_insertresult,t,t_count⊳ Inserts t t_count times

35: end for

36: end if

37: end if

38: return result

39: end function

The results are also plotted in Figure 1.

## 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.

Journal
International Journal of Computational Intelligence Systems
Volume-Issue
12 - 2
Pages
833 - 841
Publication Date
2019/08/05
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.2991/ijcis.d.190724.001How to use a DOI?
Open Access

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  -