Allocation of information granularity in optimization and
- 格式：pdf
- 大小：1.14 MB
- 文档页数：9
Computational Intelligence and Information ManagementAllocation of information granularity in optimization and decision-making models:Towards building the foundations of GranularComputingWitold Pedrycz ⇑Department of Electrical &Computer Engineering,University of Alberta,Edmonton,AB,Canada T6R 2V4Warsaw School of Information Technology,Newelska 6,Warsaw,Polanda r t i c l e i n f o Article history:Received 21November 2011Accepted 23March 2012Available online 30March 2012Keywords:Granular Computing Fuzzy setsAllocation of information granularitya b s t r a c tThe highly diversified conceptual and algorithmic landscape of Granular Computing calls for the forma-tion of sound fundamentals of the discipline,which cut across the diversity of formal frameworks (fuzzy sets,sets,rough sets)in which information granules are formed and processed.The study addresses this quest by introducing an idea of granular models –generalizations of numeric models that are formed as a result of an optimal allocation (distribution)of information rmation granularity is regarded as a crucial design asset,which helps establish a better rapport of the resulting granular model with the system under modeling.A suite of modeling situations is elaborated on;they offer convincing examples behind the emergence of granular models.Pertinent problems showing how information gran-ularity is distributed throughout the parameters of numeric functions (and resulting in granular map-pings)are formulated as optimization tasks.A set of associated information granularity distribution protocols is discussed.We also provide a number of illustrative examples.Ó2012Elsevier B.V.All rights reserved.1.Introductory notesGranular Computing [1–4,8,9,22]has emerged as a unified and coherent platform of constructing,describing,and processing information granules.The underlying concept of information gran-ules has far reaching implications by giving rise to generic,seman-tically meaningful entities that are crucial to the perception of real world,modeling its phenomena and supporting decision-making processes.What has been said so far touched a qualitative aspect of the problem.The ongoing challenge is to develop a computing framework within which all these representation and processing endeavors could be formally realized.Granular Computing be-comes innovative and intellectually proactive endeavor that man-ifests in several fundamental ways.It identifies the essential commonalities between the surprisingly diversified problems and technologies used there,which could be cast into a unified frame-work known as a granular world.This is a fully operational pro-cessing entity that interacts with the external world (that could be another granular or numeric world)by collecting necessary granular information and returning the outcomes of the Granular Computing.With the emergence of the unified framework of gran-ular processing,we accomplish a better grasp as to the role of interaction between various formalisms and visualize a way in which they communicate.Granular Computing brings together the existing plethora of formalisms of set theory (interval analysis)[17],fuzzy sets [11,23–25],probabilistic sets [12,13]rough sets [6,16,18–20],shadowed sets [21]under the same roof by clearly visualizing that in spite of their visibly distinct underpinnings (and ensuing processing),they exhibit some fundamental com-monalities.In this sense,Granular Computing establishes a stimu-lating environment of synergy among the individual approaches.By building upon the commonalities of the existing formal ap-proaches,Granular Computing helps build heterogeneous and multifaceted models of processing of information granules by clearly recognizing the orthogonal nature of some of the existing and well established frameworks (say,probability theory coming with its probability density functions and fuzzy sets with their membership functions).Granular Computing fully acknowledges a notion of variable granularity whose range could cover detailed numeric entities and very abstract and general information gran-ules.It looks at the aspects of compatibility of such information granules and ensuing communication mechanisms of the granular worlds.Granular Computing gives rise to processing that is less time demanding than the one required when dealing with detailed numeric processing [1].Interestingly,the inception of information granules is highly motivated.We do not form information granules without rmation granules arise as an evident realiza-tion of the fundamental paradigm of abstraction.0377-2217/$-see front matter Ó2012Elsevier B.V.All rights reserved./10.1016/j.ejor.2012.03.038⇑Address:Department of Electrical &Computer Engineering,University ofAlberta,Edmonton,AB,Canada T6R 2V4.Tel.:+17804398731.E-mail address:wpedrycz@ualberta.caAs underlined,the objective of Granular Computing is to create a unified view at all of the theoretical models of information granules and build on some essential similarities and subsequently arrive at fundamentals that help view this way of computing in broader context.These fundamentals are needed so that Granular Computing can effectively engage various formal frameworks it has been embracing for some time.One has to look at some general ways of forming information granules,irrespectively of a way they are formalized–a necessary prerequisite to start with their pro-cessing.The principle of justifiable granularity offers a certain viable rmation granularity helps achieve better rapport with reality by bringing into a picture an issue of non-nu-meric data or results and quantifying its nature via information granules.This aspect is especially clearly visible in system model-ing.There are no ideal models.The numeric,precise outcomes pro-duced by models are not rmation granularity has been engaged in one way or another in quantifying the lack of numeric precision.One admits a certain level of information granularity to make the model reflective of reality,quantify a limited knowledge about a phenomenon the model deals with,and capture the diver-sity of sources of knowledge and viewpoints articulated by individ-ual decision-makers in processes of group decision-making[5,11]. The studies reported in[7,11,12]and carried out in the setting of rough sets offer an important and timely perspective at Granular Computing and dominance-based rough sets.Overall,information granularity can be then regarded as an essential design asset whose prudent usage becomes crucial to make models more real-istic.This position gives rise to another fundamental principle of Granular Computing–an allocation of information granularity along with an optimization of the allocation process.In system modeling,an allocation of granularity elevates the existing models, no matter what their origin is,to a new level that could be referred to as granular models.As it will be discussed in the study,there are a number of convincing arguments that offer compelling evidence behind the emergence of granular models.The objective of this study is to establish a concept of allocation of information granularity regarded as an important design asset in sys-tem modeling by giving rise to granular models.Along with the con-cept,discussed are protocols of allocation of information granularity throughout the system and the ensuing optimization.While there have been some discussions on granular models,especially those coming from the studies on fuzzy sets such as type-2fuzzy models, controllers,and classifiers their design methodology has not been fully developed and in several cases there is a lack of motivation and con-vincing justification behind the constructs being introduced.The material is organized in the following way.Inhighlight a transition from models to granular models anda number of compelling reasons behind the emergence of models.A formal problem statement is presented infollowed by a detailed discussion on formal models ofgranules and their characterization in terms oflarity(specificity),Section4.The design of granularcovered in Section5in which both a collection ofan allocation of granularity as well as the underlying (optimization indexes)are studied.Fuzzy neural networksas a useful modeling example where we discuss thebuilding granular fuzzy neural networks(Sections6and7 formulations of allocation of information granularity arein Sections8and9.A number of illustrative examplesthe main points of the constructs are distributedoverall study.In this study,a point of departure is a numeric mappingR n to R of the form f(x,a)where a is a p-dimensionalmeric parameters.The mapping itself could be realizeddifferent ways such as e.g.,neural network,neurofuzzyrule-based system,and linear regression model.In this way our considerations exhibit a significant level of generality and are of relevance to a broad class of constructs.2.From models to granular modelsThere are a number of interesting and practically legitimate de-sign and application scenarios where the inherent granularity of the models becomes visible and plays an important role.We briefly highlight the main features of these modeling environments.2.1.Granular characterization of modelsIt is needless to say that there are no ideal models which can capture the data without any modeling error meaning that the out-put of the model is equal to the output data for all inputs forming the training data.To quantify this lack of accuracy,we give up on the precise numeric model(no matter what particular format it could assume)and make the model granular by admitting granular parameters and allocating a predetermined level of granularity to the respective parameters so that the granular model obtained in this way‘‘cover’’as many training data as possible.2.2.Emergence of granular models as a manifestation of transfer knowledgeLet us consider that for a current problem at hand we are pro-vided with a very limited data set–some experimental evidence (data)D expressed in terms of input–output pairs.Given this small data,two possible scenarios could be envisioned:(a)We can attempt to construct a model based on the data.Asthe current data set is very limited,designing a new model does not look quite feasible:it is very likely that the model cannot be constructed at all,or even if formed,the resulting construct could be of low quality.(b)We would like to rely on the existing model(which althoughdeals with not the same situation but has been formed on a large and quite representative body of experimental evi-dence.We may take advantage of the experience accumu-lated so far and augment it in a certain sense so that it becomes adjusted to the current quite limited albeit current data.In doing this,we fully acknowledge that the existing source of knowledge has to be taken with a big grain of salt and the outcomes of the model have to be reflective of par-1.Emergence of a granular model as a result of knowledge transfer.138W.Pedrycz/European Journal of Operational Research232(2014)137–145knowledge transfer(which,in essence,issome model)manifests in the formation of aversion of the original model.2.3.Granular models as a result of model reductionModels,especially those with a modularto their granular counterparts.This could be a reduction:the reduced structure of the model is using which we compensate for this reduction.This quite vividly in case of rule-based models or fuzzy els.Let us recall that those are the models composed the form-if condition is A i then conclusion is B ii=1,2,...,P now if we choose only a subset of‘‘T’’rules out of the entire collection,these rules are made granular by making the con-dition part A i granular,schematically denoted as G(A i).In other words,we compensate for the reduction of the number of rules by making the remaining ones granular.These rules take on the fol-lowing form-if GðA iÞthen B ið2Þi=1,2,...,T,T(P.The essence of the reduction process is illus-trated in Fig.2.The choice of the subset of the rules along with an allocation of information granularity is subject to optimization.The objective of this optimization is to make the outputs of the granular model (rule-based system)as close as possible to the outputs produced by the complete model(all rules).For the predetermined subset of rules,we are concerned with a suitable distribution of information granularity among the condition parts of the already selected rules.2.4.Granular model in modeling of non-stationary phenomenaA model of a non-stationary system is affected by the temporal changes of the system.Instead of making continuous updates to the model,which may result in a significant development over-head,one could admit a granular model with granular parameters. The granular form of the parameters is used here to account for the temporal variations of the system.In a nutshell,one constructs a model over a certain limited time window and generalizes its nu-meric parameters to the granular counterparts based upon the data available outside the window,see Fig.3.In some sense this concept of information granularity e2[0,1]being viewed as an important asset.It transforms the vector of numeric parameters a into a vec-tor whose coordinates are information granules A=[A1,A2,...,A p] such that the level of admissible granularity e is allocated to A i s in such a way a balance of levels of information granularity with e1,e2,...,e p being the levels of information granularity is satisfied that isP pi¼1e i¼p e i.e.,e¼P pi¼1e i=p.Concisely,we can articulate this process of information granularity allocation as follows fðx;aÞnumeric mapping!granularity allocationðeÞ!fðx;AÞ¼fðx;GðaÞÞgranular mappingð3Þthat is A i=G(a i)with G(Á)denoting a transformation of the numeric parameter a i to a certain granular counterpart A i.Note that this expression is general and we are not confined to any particular for-malism of information granules used here.The mapping itself can be realized in various ways depending upon its original realization and a way in which information gran-ules are represented,we come up with a plethora of modeling con-structs with some representative examples listed in Table1.rmation granules:formal models and characterization of granularityThe information granules of the parameters of the mapping can be realized as intervals,fuzzy sets,or probability density functions (pdfs),to recall some commonly encountered alternatives.All of them are well documented in the literature.Hybrid constructs such as fuzzy probabilities,rough-fuzzy or fuzzy-rough constructs are also quite visible.An information granule can be characterized by its specificity.In a descriptive way,one can think of specificity as a measure quantifying how detailed(specific)a piece of knowl-edge–information granule is.If one regards information granule as a certain constraint expressed over a certain variable,the more specific this constraint is,the more useful the piece of knowledge (information granule)becomes.Granularity of information granule relates with the number of elements associated with the granule. The highest granularity characterizes an information granule com-posed of a single element,{x}.When the number of such elements (or some related characterization of the entities associated with the information granule)increases,the granularity decreases.In other words,the granularity is a non-increasing or decreasing con-tinuous function of this number of elements.Formally speaking, consider an information granule A and denote by/the functional operating on A,/(A)and returning a nonnegative value character-izing the number of elements,dispersion or related measure of dis-persion of A over the universe of discourse X,/:A?R+[{0}.The granularity of A,g(A)is any continuous non-increasing(decreasing) mapping defined over/(A),g(/(A)).Let us consider some illustra-tive examples.For sets defined over a certain discrete space X,a cardinality of A,card(A),can be viewed as the number of elementsFig.2.From rule-based model to its reduced granular rule-based structure.Fig.3.Granular model as a manifestation of modeling of non-stationary system.W.Pedrycz/in X belonging to A .When X =R ,where A =[a ,b ],/(A )can be ex-pressed as the length of this interval,namely /(A )=j b Àa j .In the sequel the granularity can be taken as e.g.,g (A )=exp(À/(A ))=ex-p(Àj b Àa j ).If A collapses to a single point,{a },then g (A )=1.For fuzzy sets,as we are concerned with elements associated with information granule at some levels of belongingness (mem-bership),the notion of cardinality is generalized in the form of a so-called r -count where one computes the overall membership degrees.For the discrete space,we /ðA Þ¼PA x 2X ðx Þwith A (x )being a degree of membership of For X =R ,one has /ðA Þ¼R AX ðx Þdx (assuming that the exist).For probabilistic information granules described by density function,pA (x )a measure of dispersion,say a deviation or variance,var(A ),of the density function sought as a suitable representative of /,/(A )=var(A ).As g (A )is a non-increasing function of /(A ).5.From numeric to granular mapping:a rationale granular generalizationThere are two essential aspects with regard to the granular pings that is (a)a way of allocating information granularity vidual parameters of the mapping,which is expressed in of protocols of management of information granules,and optimization of the process of allocation of granularity presence of a certain optimization criterion.5.1.Protocols of allocation of information granularityAn allocation of the available information granularity realized in several different ways depending on how much sity one would like to consider in the allocation process.In follows,we discuss several main protocols of allocation of tion granularity,refer also to Fig.4:P 1:uniform allocation of information granularity.This protocolis the simplest one.It does not call for any optimization.All numeric values of the parameters are treated in the same way and become replaced by intervals of the same length.Furthermore the intervals are distributed symmetrically around the original values of the parameters,see Fig.4a.P 2:Uniform allocation of information granularity with asym-metric position of intervals around the numeric parameter,Fig.4b.Here we encounter some level of flexibility:even though the intervals are of the same length,their asymmet-ric localization brings a certain level of flexibility,which could be taken advantage of during the optimization pro-cess.More specifically,we allocate the intervals of lengths ec and e (1Àc )to the left and to the right from the numeric parameter where c 2[0,1]controls asymmetry of localiza-tion of the interval whose overall length is e .Another variant of the method increases an available level of flexibility by allowing for different asymmetric localizations of the inter-vals that can vary from one parameter to another.Instead of a single parameter of asymmetry (c )we admit individual c i for various numeric parameters.P 3:Non-uniform allocation of information granularity withsymmetrically distributed intervals of information granules,Fig.4c.P 4:Non-uniform allocation of information granularity withasymmetrically distributed intervals of information gran-ules,Fig.4d.Among all the protocols discussed so far,this one exhibits the highest level of flexibility.P 5:An interesting point of reference,which is helpful in assess-ing a relative performance of the above methods,is to con-sider a random allocation of granularity.By doing this,one can quantify how the optimized and carefully thought out process of granularity allocation is superior over a purely random allocation process.In all these protocols,we assure that the allocated information granularity meets the constraint of the total granularity available Table 1A collection of selected examples of granular mappings developed on a basis of well-known numeric modeling constructs.Model Granular model Examples of granular models LinearregressionGranular linear regressionFuzzy linear regression Rough linear regression Interval-valued linear regressionProbabilistic linear regressionRule-based modelGranular rule-based modelFuzzy rule-based model Rough rule-based model Interval-valued rule-based modelProbabilistic rule-based modelFuzzy modelGranular fuzzy modelFuzzy fuzzy model =fuzzy 2modelRough fuzzy modelInterval-valued fuzzy model Probabilistic fuzzy model Neural networkGranular neural networkFuzzy neural network Rough neural network Interval-valued neural networkProbabilistic neural networkPolynomialGranular polynomialFuzzy polynomial Rough polynomialInterval-valued polynomial Probabilistic polynomialProtocols of allocation of information granularity P 1–P 4and realization of the fuzzy sets of condition.140W.Pedrycz /European Journal of Operational Research 232(2014)137–145upon the protocol,which becomes longer with the increased spe-cialization of granularity allocation.Having considered all components that in essence constitute the environment of allocation of information granularity,we can bring them together to articulate a formal optimization process.5.2.Design criteria in the realization of the protocols of allocation of information granularityConsidering possible ways of allocating granularity and in order to arrive at its optimization throughout the mapping,we have to translate the allocation problem to a certain optimization task with a well-defined performance index and the ensuing optimization framework.In the evaluation,we use a collection of input–output data {(x 1,target 1),(x 2,target 2),...,(x N ,target N )}.For x k ,the granu-lar mapping return Y k ,Y k =f (x k ,A ).There are two criteria of interest which are afterwards used to guide the optimization of the alloca-tion of information granularity:(a)coverage criterion.We count the number of cases when Y k‘‘covers’’target k .In other words,one can engage a certain inclusion measure,say,incl(target k ,Y k )quantifying an extent to which target k is included in Y k .The computing details depend upon the nature of the information granule Y k .If Y k is an interval then the measure returns 1if target k &Y k .In case Y k is a fuzzy set,the inclusion measure returns Y k (target k ),which is a membership degree of target k in Y k .The overall coverage criterion is taken as a sum of degrees of inclusions for all data relative to all data,namelyQ ¼1N X N k ¼1incl ðtarget k ;Y k Þð4Þ(b)specificity criterion.Here our interest is in quantifying thespecificity of the information granules Y 1,Y 2,...,Y N .A simple alternative could be an average length of the intervalsV ¼1=N P N k ¼1j y þk Ày Àk j in case of interval-valued formalism of information granules,Y k =[y k À,y k +]or a weighted length of fuzzy sets when this formalism is used.Two optimization problems are formulated:Maximization of the coverage criterion ,Maximize Q realized with respect to allocation of information granularity e that isMax e 1;e 2;...;e p Qsubject to constraintse i >0and the overall level of information granularityrequirementP p i ¼1e i ¼p eMinimize average length of intervals V ,Min e 1;e 2;...;e p Vsubject to constraintse i >0and the overall level of information granularityrequirementP p i ¼1e i ¼p eThis optimization is about the maximization of specificity granular mapping (quantified by the specificity of the output mapping).Note that both Q and V depends upon the mined value of e .Evidently Q is a nondecreasing function of the maximization of Q is sought,the problem can be each prespecified value of e and an overall performance granular mapping can be quantified by aggregation over all of information granularity,namelyAUC ¼Z1Q ðe Þd eð7Þwhich is nothing but an area under curve (AUC),see Fig.5.The high-er the AUC value,the higher the overall performance of the granular mapping.The criteria of coverage and specificity of the granular outputs are in conflict.One can also consider a two-objective optimization problem and as a result develop a Pareto front of non-dominated solutions.6.Fuzzy neural networksFuzzy neural networks are constructs formed at the junction of the technologies of fuzzy sets and neurocomputing [10,15].The functional components of the network –logic neurons belong to two main categories of so-called AND and OR neurons,see Fig.6.The OR neuron realizes an and logic aggregation of inputs x =[x 1,x 2,...,x n ]with the corresponding connections (weights)w =[w 1,w 2,...,w n ]and then summarizes the partial results in an or -wise manner (hence the name of the neuron).The concise nota-tion underlines this flow of computing,y =OR(x ;w )while the real-ization of the logic operations gives rise to the expression (commonly referring to it as an s–t combination or more generally,an s–t aggregation of the inputs and the corresponding connections)y ¼S n i ¼1ðw i tx i Þð8Þt-norms and t-conorms (s-norms)are the generic models of logic operators used in fuzzy sets,cf [14].Lower values of w i discount the impact of the corresponding inputs;higher values of the con-nections (especially those being positioned close to 1)do not affect the original truth values of the inputs resulting in the logic formula.In limit,if all connections w i ,i =1,2,...,n are set to 1then the neu-ron produces a plain or -combination of the inputs,y =x 1or x 2or ...or x n .The values of the connections set to zero eliminate the corre-sponding putationally,the OR neuron exhibits nonlin-ear characteristics (that is inherently implied by the use of the t-and t-conorms (that are evidently nonlinear mappings).The con-nections of the neuron contribute to its adaptive character;the changes in their values form the crux of the parametric learning.AND neurons are described as y =AND (x ;w )with x and w being de-fined as in case of the OR neuron,are governed by the expressiony ¼T n i ¼1ðw i sx i Þð9ÞHere the or and and connectives are used in a reversed order:first the inputs are combined with the use of the t-conorm (s-norm)and the partial results produced in this way are aggregated Performance index as a function of the level of granularity e with curve (AUC)regarded as a global descriptor of the quality of the W.Pedrycz /European Journal of Operational Research 232(2014)137–145141By making the connections granular and admitting a certain for-malism of information granularity,we end up with granular fuzzy neural networks such as interval-valued,fuzzy,and probabilistic fuzzy neural networks,see Fig.7.development of granular fuzzy neural networksconsider the detailed example shown in Fig.8wherenetwork exhibits a hidden layer comprising twoThe connections of the network are also indicatedThe data set D consists of100inputs x k distributed uniformly in the[0,1]4hypercube.The corresponding outputs by noise and these input–output data are used in mization of allocation of information granularity.Thefor thefive protocols are visualized in Fig.9.plots of the coverage versus the levels of information granularity e show the increased level of sophistication erage of outputs of the data.As expected,the random allocation performs quite poorly.The uniform distribution where each con-nection is affected to the same degree,no matter whether symmet-ric or asymmetric location of the interval is considered is not very beneficial.The improvement happens when the allocation of gran-ularity has been optimized;the advantages of the PSO are clearly evident.Likewise asymmetric position of intervals of the connec-tions results in further improvements of the coverage.The AUC val-ues quantify the obtained performance.We have obtained the following results:random:0:719;uniform-symmetric allocation:0:731uniform;asymmetric allocation:0:747;PSO;symmetric allocation:0:801;PSO;asymmetric allocation:0:842:It is apparent and not surprising that the two protocols in which PSO has been used produce the best results.With the two optimization criteria considered(that is coverageexample fuzzy neural network formed with the use of logic ANDFrom fuzzy neural networks to granular fuzzy neural networks;shown are selected realizations of information granularity.Research232(2014)137–145。
