粒关系演算：关系计算与数据的桥梁

PEDRYCZ Witold

（阿尔伯塔大学电气与计算机工程系，埃德蒙顿 T6R 2V4）

Relational computing[1-2］has been one of the focal points of fundamental research in fuzzy sets and interval analysis.The well-known concepts，such as projection，Cartesian product，and composition operators，are prescriptive，viz. they provide universal concepts and a way of generic computing that navigate processing sets and fuzzy sets.A number of them can be regarded as certain aggregation procedures involving many arguments so it could be beneficial to have them endowed with abilities to capture the nature of data they operate on.For instance，the projection operation returns the maximal value of the characteristic function or membership function.Adding a descriptive facet to the constructs and making them have a prescriptivedescriptive character could be a desirable property.Having this in mind，in the present study，it is advocated that the results of such aggregation can be conveniently described as information granules reflecting the diversity of the partial results.In other words，the ultimate objective is to revise and augment the mechanisms and results of relational computing by engaging the mechanisms of granular computing[3-7］.It is shown that the principle of justifiable granularity serves as a sound conceptual vehicle to accommodate the characteristics of data by producing a granular format of the results.Interestingly，this avenue of developments of relational constructs has not been fully investigated.There have been some initial studies pointing at the statistical properties of logic operators that impact the resulting operator；however the idea of information granules as a result of such logic operations has not been studied.

In this paper，some generic definitions are presented concerning Cartesian products，projections and the following reconstruction mechanism，composition operators.In the sequel，fuzzy relational equations are covered along with a topic of a reconstruction of fuzzy relations.In addition，the principle of justifiable granularity，which is central to the ensuing granular constructs is introduced.Moreover，both a one-dimensional and multivariable case is studied. Furthermore，G-operations are presented 4 along with a variety of architectures（such asG-Cartesian products，G-relational composition operations， granular relational equations， and granular logic networks）.

1 Generic definitions

LetAandBbe two sets or fuzzy sets defined in finite spacesXandY，respectively，dim（X）=n，anddim（Y）=m. They are described by characteristic functions（sets） or membership functions（fuzzy sets）. In what follows，the fundamental definitions and constructs forming a backbone of relational calculus is briefly recalled.Interestingly，these entities are the same for sets and fuzzy sets meaning that the definitions put forward apply to the same extent to sets and fuzzy sets.

1.1 Cartesian product and projection operations

Relations and fuzzy relations are cornerstones when describing and processing relationships existing among real-world objects.

Cartesian product

A Cartesian product ofAandB，A×B，is a relation （fuzzy relation） described by their characteristic or membership functions[2，8-9］

For fuzzy sets，the minimum operation is replaced by anyt-norm（A×B）（x，y）=A（x）tB（y）.Of course，ifAandBare sets，allt-norms return the same result.

To focus attention，relations defined over two spaces are considered.However，the constructs are readily extended to multidimensional situations.A two-dimensional fuzzy relationRis defined over the Cartesian productX×Y.The well-known definition of projection is presented as

Projection of fuzzy relation

The projections ofRonXandY，respectively，are defined as

The result of projection is a fuzzy set.From the computational perspective，it is worth noting that the result of projection is determined by the maximal value of the relation across one argument for the second one being fixed.In this way，this is an optimistic view：the membership values ofRdepend upon the extreme value of the slice ofRreported along thexorycoordinate.

Reconstruction

The results of projection ofRcan be used to reconstruct the original fuzzy relation.This is a typical example in image processing when an original 3D object has to be reconstructed in an efficient way based on their projections.

The common way of realizing reconstruction is to take a Cartesian product of the projection results，sayAandBand compute their Cartesian product.IfRis an image，it is apparent that the projection operation returns a result based on the maximal value ofRfor a value of one argument fixed，see Fig.1.

Fig.1 Projection of relation on x and y coordinates along with the reconstruction result

There is no guarantee thatA×Balways returnsR.This problem will be expounded later on.

1.2 Composition operators

The composition operators that commonly discussed in relational calculus involve a sup-min（max-min）and inf-max（min-max）operations.Given a fuzzy setAinXand a fuzzy relationR，these compositions return another fuzzy setBinYwith thefollowing membership function sup-min composition

It is worth noting that ifAis an overall space，A（x）=1，then the composition operator returns the projection ofR.

1.3 Logic aggregation of many fuzzy sets

t-norms and t-conorms are commonly used in the realization of logic aggregation.Theoroperation of fuzzy sets defined in the same spaceA1，A2，...，Acis applied to the individual membership gradesA1（x）A2（x）...An（x）returningA1（x）sA2（x）s...sAn（x）.For the operation，one considers anyt-norm and the results becomesA1（x）tA2（x）t...tAn（x）.One could note that depending on thet-norm being used，the largest and smallest membership grades of the results are bounded

If the number of arguments increases，the result tends to zero（andoperation）or 1（oroperation）.

1.4 Fuzzy relational equations

Fuzzy relational equations have been studied from the seventies[1-2，10-11］with a significant progress reported over the decades[12-13］.These equations are directly based on the composition operators studied in Section 2.2.The two expressions（4）and（5）could be sought as equations with regard toAandRbeing streated as unknown.More specifically，there are two key types of equations

-estimation problem：GivenAandB，determineR

-inverse problem：GivenRandB，determineA

For the sup-min and inf-min composition operators，the solutions are well-known[1-2］.Equations with sup-tand inf-tcompositions are also discussed in the context of their analytical solutions[11］.It is also shown that if the solution set is nonempty，the largest（smallest）solutions can be determined. Likewise，the solutions could be determined for the sup-tand inf-scompositions.However，the equations with thes-tandt-scompositions cannot be processed in a general way.Likewise，if the solution sets are empty，one has to resort to approximate solutions obtained by invoking optimization methods，say gradient-based techniques.

The estimation problem can be generalized by considering a system of fuzzy relational equations

A1◦R=B1，A2◦R=B2，...，Ac◦R=Bc

1.5 Reconstruction of fuzzy relations -a parametric augmentation

The previous way of carrying out projection is generalized in the form of the procedure where thes-tcomposition is introduced and some parametric flexibility are brought in to the calculations

In case of finite spacesXandY，wandvare vectors of weights assuming values in[0，1］.Their objective is to calibrate an impact of individual elements ofXandYwhen determining the respective contributions to the generated results.

As to the reconstruction，it is augmented by weightsfandgwhich yield

The overall scheme of projection and reconstruction is visualized in Fig.2.

Fig.2 Realization of reconstruction of fuzzy relation

As a matter of fact，the expressions（10）-（12）are examples of logic neurons：the projection is completed in terms of the two OR neurons whereas the reconstruction is conducted with the aid of the AND neuron.

The selection of the values of the weightsw，v，f，andgis completed by solving the following optimization problem，

where||.||is a certain distance function.

2 Principle of justifiable granularity

Building information granules on a basis of experimental data constitutes a pivotal item on the agenda of granular computing with far-reaching implications on the design methodology of granular models and ensuing applications. Clustering and fuzzy clustering[14］are often used as a vehicle to produce information granules. The principle of justifiable granularity rooted in the compelling intuitively appealing arguments guides a construction of an information granule[15-17］.In a nutshell，a resulting information granule becomes a summarization of data （viz. the available experimental evidence）. The underlying intuitive rationale behind the principle is to deliver a concise and abstract characterization of the data such that the two requirements are addressed，i.e.，the produced granule isjustifiedin light of the available experimental data，and the granule comes with a welldefined semantics meaning that it can be easily interpreted and becomes distinguishable from the others.

Formally speaking， these two intuitively appealing criteria are expressed by the criterion of coverage and the criterion of specificity.Coverage states how much data are positioned behind the constructed information granule. Rephrase it differently，coverage quantifies an extent to which information granule is supported by available experimental evidence.Specificity，on the other hand，is concerned with the semantics of information granule stressing the semantics（meaning）of the granule.

In what follows，the developments of the principle of justifiable granularity is elaborated on by starting with a generic version. The main assumptions and the features of the environment in which information granules are being formed are also summarized in a concise manner. Information granules are formalized in an interval format so that an interval[a，b］is constructed.The interval type of information granule is explored for illustrative purposes；however the method is far more general and the principle can be applied to different granular and numeric experimental data and produce information granules formalized in terms fuzzy sets，rough sets and others.

2.1 One-dimensional data

One-dimensional real datax1，x2，…，xNare considered.The bounds of the data arexminandxmax；xmin=arg mink xk，xmax=arg maxk xk.

The coverage measure is associated with a count of the number of data embraced byA，namely

Wherecard（.）denotes the cardinality ofA，viz.the number（count）of elementsxkbelonging（covered）toA.In essence，coverage has a visible probabilistic flavor.The specificity ofA，sp（A），is regarded as a decreasing functiongof the size（length）of information granule.If the granule is composed of a single element，sp（A）attains the highest value and returns 1.IfAis included in some other information granuleB，thensp（A）＞sp（B）.In a limit case，ifAis an entire space，sp（A）returns zero.For an interval-valued information granuleA=[a，b］，a simple implementation of specificity withgbeing a linearly decreasing function comes as

whererangeis defined asrange=xmax-xmin.

The criteria of coverage and specificity are in an obvious conflicting relationship.The increase in the values of coverage implies lower values of specificity and vice versa.If it is wished to maximize both criteria，a sound compromise has to be reached.Let us introduce the following product of the criteria

The maximization of the performance indexVgives rise to information granule where some tradeoffs between coverage and specificity are reached.The design of information granule is accomplished by maximizing the above product of coverage and specificity. Formally speaking，consider that an information granule is described by a vector of parametersp，V（p），the principle of justifiable granularity yields an information granule that maximizesV，popt=argp V（p）.

To maximize the indexVthrough the adjusting the parameters of the information granule，two different strategies are encountered：

（1）A two-phase development is considered.First a numeric representative（mean，median，mode，etc.）of the available data is determined.It can be regarded as their initial representation.Next，the parameters of the information granule are optimized by maximizingV.For instance，in case of an interval，one has two bounds（aandb）to be determined.These two parameters are determined separately，viz.aandbare formed by maximizingV（a）andV（b）.The data used in the maximization ofV（b）involves the data larger than the numeric representative.Likewise，V（a）is optimized on a basis of the data lower than this representative.

（2）A single-phase procedure in which all parameters of information granule are determined at the same time.In the above case，the values ofaandbare simultaneously optimized.In comparison with the previous method，here the location of the interval is not biased towards one of the“anchor”points such as the mean or median.This approach yields more flexibility and finally results in possibly higher values ofV（p）.

As an example，let us consider 500 data governed by a normal distributionN（0，1）.The range is[-3.43，3.00］.

The use of the principle of justifiable granularity where both bounds are optimized at the same time leads to the interval information granule[-0.896，1.261］.The obtained product of the coverage and specificity criteria is 0.730.

Proceeding with the separate optimization of the bounds and assuming a numeric representative to be the mean value（0.047），the optimal interval[-0.983，0.846］is obtained and the optimized performance index is 0.654.If the numeric representative is taken as the median（0.654），the numeric representative is practically the same as before，[-0.987，0.847］resulting in the same value of the performance index.

Considering the 500 data generated by the Laplace distributionL（0，1），the obtained results are

-simultaneous optimization of the bounds：[-1.876，1.497］，performance is 0.822

-separate optimization of the bounds，mean as the representative：[-1.493，1.498］，performance 0.774

-separate optimization of the bounds，median as the representative：[-1.480，1.473］，performance 0.768

For the Cauchy distribution（again 500 data），the obtained results are

-simultaneous optimization of the bounds：[-10.123，14.808］，performance is 0.970

-separate optimization of the bounds，mean as the representative：[-5.639，21.847］

performance 0.958

-separate optimization of the bounds，median as the representative：[-5.943，14.794］，performance 0.952

If fuzzy sets are considered as information granules，the definitions of coverage and specificity are reformulated to take into account the notion of partial membership. Here the fundamental representation theorem is invoked，stating that any fuzzy set can be represented as a family of itsα-cuts[8，15］，namely

The supremum（sup）operation is taken over all values ofα.In virtue of the representation theorem，any fuzzy set represented as a collection of sets is obtained.

Having this family ofα-cuts in mind and considering Eqs.（14）and（15）as a point of departure for constructs of sets（intervals），the following relationships are obtained.

-coverage

whereXis a space over whichAis defined.Moreover，one assumes thatAcan be integrated.The discrete version of the coverage expression comes in the form of the sum of membership degrees.If each data point is associated with some weightw（x），the calculations of the coverage involve these values

2.2 Multivariable data

Let us consider multivariable dataX=｛x1，x2，...，xN｝wherexk∈Rn.It is assumed that the data are normalized to the unit hypercube.The process is carried out in the same way as described in the first option. It is assumed that some numeric representative prototype ofXassociated with the data is given.Denote it byv.It could be also produced by running some clustering or fuzzy clustering technique.

Around the numeric prototypev，one spans an information granuleG，G=（v，ρ）whose optimal size（radius）is obtained as the result of the maximization of the already introduced criterion，namely

The geometry of information granule depends upon the form of the distance function.For instance，the Tchebyshev distance implies a hyperbox shape of the granules.

When using the fuzzy clustering method，the dataXcome with their weights associated with the individual elements ofX，say（x1，w1），（x2，w2），...，（xN，wN），wherewk∈[0，1］serves as a degree of membership of thekth data point.The coverage criterion is modified to reflect the existing weights.Introduce the following set

The specificity measure is defined as presented before.

3 G-operations

Projections and composition operators are examples of multi-argument aggregation operators.Many input variables give rise to a single result.In this paper，it is advocated that the result of aggregation of numeric input arguments is an information granule which helps incorporate the diversity of input arguments and copes with the descriptive aspect of the result.

The classic definition of projection，although conceptually sound，is quite limited when it comes to the incorporation of data distribution.Both in Eq.（2）and（3），the result hinges upon the maximal value of the characteristic or membership function.For Boolean relations，the result is only either 0 or 1 irrespective of the distribution of values of the input variables. For fuzzy relation，the result is the maximal membership grade.It is a bit counterintuitive as the projections of very different rows ofRyields the same result.The use of anyt-conorm gives a better insight as the result captures the membership values of the fuzzy relation for some fixedx，yet it does not reflect the nature（distribution）of the data.

In sum，it could be intuitive to anticipate that the result of projection has to accommodate the diversity of the entries ofRforming any row or column and become an information granule of type-2.The result of any operation on fuzzy sets involving many arguments should reflect the existing diversity and return an information granule whose localization and specificity is impacted by the existing data.This gives rise to a slew of constructs such as projection（and the associated reconstruction process），granular composition operators，and granular relational equations.It is also shown that this leads to a new class of granular logic networks built on a basis ofGANDandG-ORneurons.

Conceptually， the results of processing individual inputs，sayf（x1），f（x2），...，f（xn）wherefis a certain operator，saymax，min，t-norm，tconorm，etc.are considereden blockand regarded as a certain information granule.In a concise way，the process is described asT=G（f（｛x1，x2，...，xN｝）withGdenoting a procedure of the principle of justifiable granularity returning an interval information granuleT=[t-，t+］on a basis off（x1），f（x2），...，f（xn）.

3.1 G-Cartesian product and a reconstruction problem

G-Cartesian product

Recall thatA（y）=projxR=supxR（x，y）.TheG-projxRreturns an information granuleA～with the bounds[a-（x），a+（x）］where these bounds are produced by the principle of justifiable granularity being applied to the collection of membership grades｛R（x1，y），R（x2，y），...，R（xn，y）｝so someyfixed.

LikewiseB～is an information granule[b-（y），b+（y）］arising through the formation of information granule which emerges after processing｛R（x，y1），R（x，y2），...，R（x，ym）｝

Reconstruction

The reconstruction，as in case of type-1 information granules（see Section 4），is realized by taking a Cartesian product ofAandB.Here，however，AandBare type-2 information granules.ThusRitself is a type-2 fuzzy relationR～with the entries[a-（x）tb-（y），a+（x）tb+（y）］.An interesting question arises as to the quality of the obtained reconstruction.AsRandR～are of two different types，the performance of reconstruction is evaluated by using the measures of coverage and specificity.Those are the same which were studied with regard to the principle of justifiable granularity.The coverage is expressed in the form

The coverage operator，cov（a，[b，c］）returns 1 onceais included in the interval[b，c］.The performance of reconstruction is expressed as the product-----cov-sp，the higher the value of this index，the better the performance of the reconstructed fuzzy relation.

3.2 Granular relational composition operators

The composition operators discussed in Section 2.2 are examples of multi-argument aggregation operations.the operation ofG-min，G-max，G-t，andG-sare introduced as analogous to the discussed compositions in the following way

G-min andG-tcompositions

The principle of justifiable granularity is applied to sets｛min（A（x1），R（x1，y）），min（A（x2），R（x2，y）），...，min（A（xn），R（xn，y））｝and｛A（x1）tR（x1，y），A（x2）tR（x2，y），...，A（xn）tR（xn，y）｝，respectively.

For the inf-min and inf-s，one has

With the principle of justifiable granularity applied to sets

3.3 Granular fuzzy relational equations

The composition operations discussed above，both in terms of their numeric and granular versions，are considered in the generalized versions of relational equations，G-relational equations.As before，there are two types of problems

Estimation problem.Given are fuzzy setsAandB，determineR.In virtue of theG-max orG-tcomposition，the result of the composition ofAandRisB～，B～（y）=G-min（A（x），R（x，y））orB～（y）=G-t（A（x），R（x，y））.The unknown fuzzy relationRis optimized in a way the product of coverage and specificity ofB～，-----cov-spare maximized where

The solution（optimal fuzzy relation）Roptis the one that maximizes the product of the average coverage and specificity，Ropt=arg maxR（-----cov-sp)

For the system of equations where pairs of data（Ak，Bk），k=1，2，...，Nare provided，the formulation of the problem is the same as shown above with the coverage and specificity expressed over all data meaning that

In the estimation problem，the data in the form（Ak，B*k）could be encountered whereB*kis a type-2 information granule.In this case，the performance index quantifies how closelyB*kandB～kare.A certain performance measurePis expressed in the form

wherecard（.）denotes the cardinality of the information granules.

Inverse problem

Here given areRandBandAhas to be determined.The formulation of the optimization problem in whichAis searched for whereG-min or Gtapplied toAandRreturnsB～for which the coverage and specificity are calculated in the form given by Eqs.（35）and（36）.

The solutions to the estimation and inverse problems cannot be obtained analytically.A sound alternative is to involve some population-based optimization methods such as PSO（Particle Swarm Optimization），GA（genetic algorithms），DE（differential evolution）or alike and regard the product of coverage and specificity as a suitable fitness function.

3.4 Granular logic neurons and granular neural networks

The composition operators form the computing setting of granular neurons.The G-tcomposition gives rise to aG-OR neurons and G-scomposition produces aG-AND neuron；refer to Fig.3.

Fig.3 Granular logic neurons

In essence，the granular neurons are realized byG-torG-scomposition operators returning a type-2 information granuleY. The weights play an important role by endowing the neurons by some parametric flexibility which is central to the realization of the learning capabilities of the neurons.

G-s composition：if all weights are equal to 1，the original data are used in the principle of justifiable granularity.If the weights are getting lower then the population of inputs is shifted towards lower values and the resulting information granule is moved towards the lower end of the unit interval.For the GAND neuron，if all weights are set to zero，the obtained information granule is built on a basis of the original data.If the weights are getting larger，the obtained information granule migrates towards higher end of the space.Note that in both classes of neurons，the numeric inputs produce a granular outputY.

The generalization of the logic processor discussed in Refs.[9，15］is a two-layer architecture where the first layer is composed ofG-AND followed by the output layer composed ofG-OR units.A multiple input-single output topology is illustrated in Fig.4.

Fig.4 Architecture of G logic processor

The outputs of G-AND neurons are information granules.Denote them byZ1，Z2，...，Zm.They are processed by the G-OR neuron.The lower and upper bounds ofZis are processed separately，which at the end gives rise to information granule of type-2（the level of type of information granule has been elevated）.For the purpose of learning，one can treat them as information granule of type-1 use in the performance index the bounds of the granule as depicted in Fig.5.

Fig.5 Processing in G logic processor(Stressed is an elevated level of information granules obtained when moving along successive layers of the architecture)

To realize learning of the network，two components have to be clearly identified，namely a suitable performance index and a learning algorithm.To focus on this discussion，consider that the learning data are given as a family of input-output pairs（xk，targetk），k=1，2，...，Nwithninput variables and a single output.With regard to the first one，because numeric data are confronted with the information granule，the optimization process has to be guided by a suitable performance index that takes into account the diverse nature of data and results of the model.

As we encounter type-2 information granules，two optimization performance indexes are considered.There areA+=[y--ky++k]andA-=[y-+k，y+-k]whereA-⊂A+.

The optimization problem is formulated forA+andA-in the following form

The solution iswopt=arg maxw V1orwopt=arg maxw V2wherewis a collection of weights of the G-neurons forming the network.

Given the complexity of the optimized performance index whose gradient with respect to the parameters of the network is difficult to determine，a feasible optimization vehicle comes from a family of population-based optimization techniques.

4 Conclusions

This study develops a new perspective and provides algorithmic environment of data augmented constructs of relational computing.This enhanced the current consideration from a purely prescriptive ground to embrace the descriptive aspect involving data content and data characteristics.It has been shown that multivariable constructs（projections，compositions，etc.）give rise to results of elevated aspect of information granularity.In particular，the arguments that are membership grades lead to the granular result，say，an interval of possible membership grades.It can be stated that there is an interesting effect of elevation of type of information granules：an aggregation（composition）of type-pinformation granules produces a single type（p+1）information granule.Granular architectures have been introduced，referred to asG-constructs，sayGprojection，G-composition，among others.The idea of fuzzy relational equations is generalized toGrelational equations.As a follow-up of weighted composition operations，a family of granular neurons and neural networks has been established that focuses on numeric processing producing granular results.

While the study opens up a new avenue of research in fuzzy sets，relational calculus，there are a number of promising directions worth pursuing.First，all investigations have been conducted for interval information granules. However， the framework proposed here is for more general and as such deserves more studies.The solutions to theGrelational equations are demanding given the underlying processing thus a way of their determination calls for more thorough investigations as to efficiency of optimization methods.