人工智能英文版课件：Design of information granules

1、Design of information granulesThe principle of justifiable granularityConstruction of information granules via fuzzy clusteringKnowledge-based clusteringSuccessive refinements of information granulesOutlineThe principle of justifiable granularityGivencollection of a one-dimensional (scalar) numeric

2、data, D = x1, x2, , xN. form a meaningful (legitimate) information granule based which adheres to two intuitively compelling requirements: experimental evidence (legitimacy) (ii) sound semantic (meaning) The principle of justifiable granularity experimental evidenceexperimental evidence (legitimacy)

3、: The numeric evidence accumulated within the bounds of W has to be as high as possible. The principle of justifiable granularity semantic soundness(ii) sound semantic (meaning)information granule should be as specific as possible. This request implies that the resulting information granule comes wi

4、th a well-defined semantics (meaning). We would like to have W highly detailed, which makes the information granule semantically meaningful (sound). This implies that the smaller (more compact) the information granule (lower information granule) is, the better. This point of view is in agreement wit

5、h our general perception of knowledge being articulated through constraints (information granules) “x is in 1,3” is more specific (semantically sound, more supportive of any further action, etc.) than “x is in 0, 10”. The principle of justifiable granularity conflicting requirementsPrinciple of just

6、ifiable granularityGroup of recordings of age of individuals in a certain communityinformation granule = piece of knowledge, constraints (restriction) overspace of ageInformation granule 1, 110 high experimental evidence, missing semantics Information granule 47.55 no experimental evidence, visible

7、semantics The principle of justifiable granularity optimization aspects Construction of interval information granuleOptimization of upper bound (optimization done separately for each bound)f1- increasing function, f2 decreasing functionMax coverage Max specificityThe principle of justifiable granula

8、rity optimization aspects f1- increasing function, f2 decreasing functionMax coverage Max specificityThe principle of justifiable granularity - optimizationExamples of functions (f1 and f2)Illustrative examplesData governed by some prob density function (pdf) Illustrative examplesIllustrative exampl

9、esIllustrative examplesf1(u) = u2Illustrative examplesf1(u) = u0.5f1-f2 plotsIllustrative examplesNumeric data Intervals for selected values of aSelection of values of a We can look at these inequalities one by one and solve them for the maximal values of a. Choosing maximal value of aSelection of v

10、alues of a Formation of intervals indexed by a positioned in the unit intervalShadowed sets and rough sets conceptual similarity in the sense that these information granules identify three regions in the universe of discourse: (a) full membership (complete belongingness), (b) full exclusion (lack of

11、 belongingness), and (c) ignorance about membership (no knowledge about membership of elements located in this region is available). Shadowed sets and rough sets:formation through the principle of justifiable granularity Shadowed set- performance index V= 0.2 optimal values b = 0.368, db = 0.66 = 0.

12、5 optimal values b = 0.205, db = 0.59 Weighted data in the construction of Information granulewk weights associated ith datanumeric representative weighted median:Optimized performance indexPrinciple of justifiable granularity- ”inhibitory” data(z1,w1), (z2, w2) , (zn, wn) weights wi in 0,1(y1, g1),

13、 (y2, g2), (ym, gm) weights gi in 0,1“inhibitory” data Modified performance indexMaxFormation of fuzzy sets through a collection of a-cutsTwo observations:-normalization of values of a to the unit interval -monotonicity of the interval granules with regard to the values of a, For different values of

14、 a, a collection of the corresponding W(a)s forms a nested family of intervals The intervals can be regarded as a family of a-cuts of a certain fuzzy set W with the membership function resulting from the representation theorem.Development of type-2 fuzzy setsFuzzy sets - numeric membership functions

15、Granular fuzzy sets granular membership functionsfamily of fuzzy sets described by type-2 fuzzy sets constructed with the use of the principle of justifiable granularity membership degrees granular membershipDevelopment of type-2 fuzzy sets:exampleDesign of multivariable information granulesConstruc

16、tion of information granules for individual variables formation of their Cartesian productDiversity of information granules in the principle of justifiable granularity Examples of granular dataJustifiable granularity: expressing coverage criterion in presence ofInformation granulesintervalsfuzzy set

17、sprobabilitiesDiversity of information granules and the principle of justifiable granularitySaatys priority method of pairwise comparison (AHP)Collection of elements x1, x2, , xnMembership degrees are given as A(x1), A(x2). A(xn)Reciprocal matrix RSaatys priority method of pairwise comparisonRecipro

18、cal matrix R main properties:reflexivityreciprocalitytransitivity Saatys priority method of pairwise comparison: computingi-th row of R RA = nA n-the largest eigenvalue of R Saatys priority method of pairwise comparisonEstimation of reciprocal matrix:Scale (typically 1-7 range, could be larger, 1-9)

19、 strong preference: high values on the scale (7-9) preference: 4-7 weak preference or no preference 1-3Solving the eigenvalue problem for R, max eigenvalue, lmax Saatys priority method :quantifying consistency of resultsn = (lmax n)/(n-1)lack of consistency n 0.1Saatys priority method :Examplehigh t

20、emperatureuniverse of discourse: 10, 20, 30, 40scale 1-5max eigenvalue = 4.114 eigenvector 0.122 0.195 0.438 0.869 after normalization 0.14 0.22 0.50 1.00. Fuzzy clustering and design of information granulesGiven a collection of n-dimensional data set xk, k=1,2,N, Determine its structure a collectio

21、n of “c” clusters,Minimization of objective function (performance index) Q v1, v2, , vc prototypesU = uik partition matrix expressing a way of allocation of the data to the corresponding clusters; uik membership degree of data xk in the i-th cluster.|. | distance between the data xk and prototype vi

22、m fuzzification coefficientFuzzy partition matrix- propertiesDistribution of membershipBoundary conditionsFuzzy C-Means (FCM):Optimization problemTwo optimization tasksDetermine partition matrixDetermine prototypesOptimization of partition matrix (1)Constraint-based optimization; use of Lagrange mul

23、tiplierOptimization of partition matrix (2)Optimization of prototypesAssumption use of Euclidean distanceFuzzy C-Means- an overall processIterative optimization processstart from some random allocation of data (a certain randomly initialized partition matrix) iterate update partition matrix update p

24、rototypesuntil termination criterion satisfied termination criterionFuzzification coefficientm=1.2m=2.0m=3.0Fuzzy partition- two related viewsU=uik i=2, 2, , c, k=1, 2, , NRelationships between pairs of data proximity matrixP =pkl k,=1,2 , NDependency between clusters linkage matrix L = lij, i, j=1,

25、 2,., cFuzzy C-Means for granular data- two approaches (1)Parametric approach information granules to be clustered are represented in a certain parametric format ( triangular fuzzy sets, intervals, Gaussian membership functions, etc.) There are several parameters associated with the membership funct

26、ions and the clustering is carried out in the space of these parameters. The resulting prototypes are also described by information granules having the same parametric form as the information granules being clustered. dimensionality of the space of the parameters in which the clustering takes place

27、is higher than the original space. Example triangular membership functions - new space is R3n (given the original space is Rn). Fuzzy C-Means for granular data- two approaches (2)non-parametric approach no particular form of the information granules - some characteristic descriptors of information g

28、ranules used to capture the nature of these granules are formed and used to carry out clustering. Interpretation of information granulesOrder one-dim projected prototypes in the increasing orderassign some labels (information granules) with a clear semantics, say negative large, negative medium, neg

29、ative small, positive large. Proceed with the same projection for the remaining variables, Translate the prototypes into a Cartesian product of one-dimensional information granules. Fuzzy clusters formed in multivariable spaceTo facilitate interpretation project prototypes on individual variablesInt

30、erpretation of information granules projected prototypesRefinement of information granulesSuccessive refinement of information granulesSuccessive refinements of information granulesHighest level of hierarchyLinking data with clustersassociating with the i-th cluster all data that belong to it to the

31、 highest extent (higher than to the remaining clusters) Quantifying a content of information granules (1)Class membership content. This information content is of interest when the elements in the input space are associated with some classes viz. each xk belongs to one of the classes w1, w2, ., wp. T

32、he information content of this nature is of interest in case of classification problems. Determine the class with the maximal number of data contained in Xi. Quantifying a content of information granules (1)Output variable content xk is associated with some output yk (regression type of problems) ev

33、aluate the content of the cluster from this perspective. Compute the numeric representative y* of yks for all xk which belong to Xi,Refinement of information granules conditional fuzzy clustering context (expressed at higher level)Conditioanl fuzzy clustering - examplefuzzy sets (highest level of hi

34、erarchy)refinementReconstruction problem(2)Use of fundamental results of fuzzy relational equationspossibility and necessity formulas are treated as equations with regard to XReconstruction problem(3)Upper boundLower boundReconstruction problem- relational operatorsReconstruction problem- boundsReco

35、nstruction is not unique (as could have been expected)Calculations for interval Ai - upper boundReconstruction problem- lower boundCalculations for interval Ai - lower boundReconstruction process - illustrationReconstruction process and shadowed setsReconstruction process multivariable caseAi and X

36、defined in p-dimensional spaceDegree of overlapConstruction of vocabulary-optimization problems (1)Optimization of the vocabulary of granular terms For the predetermined number of terms (c), distribute them in such a way that the reconstruction bounds are made as tight as possible (the distance betw

37、een the bounds |.| is the lowest one). For given information granules coming from F, determine (optimize) AConstruction of vocabulary-optimization problems (2)Optimization of the dimensionality of the vocabulary of granular termsallocate different numbers of information granules (vocabulary) across

38、individual coordinates of the multivariable space. Formation of hierarchical granulation structure While the number of information granules of A could be limited, a hierarchical structure in which some of these granules is further “expanded” by forming a collection of more detailed granulesReconstru

39、ction (granulation- degranulation) in presence of numeric dataReconstruction (granulation- degranulation) in presence of numeric datagranulationdegranulationGranulation of numeric data-optimizationgranulationGranulation of numeric data-solutionDegranulation of numeric datagiven ui(x) and the prototy

40、pes vi, the reconstructed vector of x is considered as a solution to the minimization problem In which we reconstruct (degranulate) original x If |.| treated as Euclidean distanceQuality of granulation- degranulationFuzzy C-MeansFCM selection of essential parametersChoice of fuzzification coefficien

41、t (m)Choice of number of clusters (c)Fuzzy C-Means- example reconstruction errorGranulation- degranulation for triangular fuzzy setsOne dimensional caseCodebook composed of triangular fuzzy sets with overlapbetween successive fuzzy setsZero reconstruction errorIf the following conditions holdZero re

42、construction errorThenThe codebook composed of triangular membership functions in the formleads the zero decoding (lossless compression, granulation-degranulation) errorFuzzy Rule-Based ModelsFuzzy rules as a vehicle of knowledge representationRule conditional statement with information granules If

43、input variable is A then output variable is B A and B: descriptors of pieces of knowledge rule: expresses a relationship between inputs and outputs Example If the temperature is high then the electricity demand is high If and then parts . formed by information granules sets rough sets fuzzy setsRule

44、-based system/model (FRBS) FRBS is a family of rules of the formIf input variable is Ai then output variable is Bi i = 1, 2,., cAi and Bi are information granules More complex rulesIf input variable1 is Ai and input variable2 is Bi and . then output variable is Zi multidimensional input space (Carte

45、sian product of inputs) individual inputs aggregated by the and connective highly parallel, modular granular modelGeneral categories of fuzzy rules and their semanticsMulti-input multi-output fuzzy rules If X1 is A1 and X2 is A2 and . and Xn is An then Y1 is B1 and Y2 is B2 and . and Ym is Bm Xi = v

46、ariables whose values are fuzzy sets Ai Yj = variables whose values are fuzzy sets Bj Ai on Xi, i = 1, 2,.,n Bj on Yj, j = 1, 2,.,m Without any loss of generality if we assume rules of the form If X is A and Y is B then Z is CCertainty-qualified rules If X is A and Y is B then Z is C with certainty

47、0,1 : degree of certainty of the rule = 1 rule is certainGradual rules the more X is A the more Y is B relationships between changes in X and Y captures tendency between information granules Examples:the higher the income, the higher the taxesthe lower the temperature, the higher energy consumptionF

48、unctional fuzzy rules If X is Ai then y = f (x,ai) f : X Y xRn Rule: confines the function to the support of granule Ai f : linear or nonlinear (neural nets, etc.) Highly modular modelsConstruction of computable representationsMain steps:1. specification of the fuzzy variables to be used2. associati

49、on of the fuzzy variables using fuzzy sets3. computational formalization of each rule using fuzzy relations and definition of aggregation operator to combine rules togetherBasic functional modules of FRBSGeneral architecture of FRBSFuzzy if-then rules(input-output relationship)Parametersof the FRBSP

50、rocess inputs and rules(approximate reasoning)Input interface (attribute) of (input) is (value)the temperature of the motor is high Canonical (atomic) formp: X is A temperature (motor) is highfuzzy setLowMediumHighx (C)Multiple fuzzy inputs: conjunctive canonical formp : X1 is A1 and X2 is A2 and .

51、and Xn is An conjunctive canonical formXi are fuzzy (linguistic) variablesAi : fuzzy sets on Xii = 1, 2, ., nCompound proposition induces a fuzzy relation P on X1X1. Xn p : (X1, X2 , ., Xn) is Pt (T) = t-normExample Fuzzy relation associated with (X,Y) is P Triangular fuzzy sets A1(x,4,5,6) = A, A2(

52、y,8,10,12) = B t-norm: algebraic product Choose a t-norm t and define: R(x,y) ft (x,y) = A(x) t B(y) (x,y) XYExamples: t = min Rc(x,y) fc (x,y) = minA(x) t B(y) (Mamdani) t = algebraic product Rp(x,y) fp (x,y) = A(x)B(y) (Larsen)Fuzzy conjunctionRc(x,y) = min a, b (a, b)0,12Rc(x,y) = min A(x), B(y)

53、(A(x), B(y)0,12Example: t = minA(x) = A(x,4,5,6), B(y) = B(y,4,5,6)Rp(x,y) =ab (a, b)0,12Rp(x,y) = A(x)B(y) (a, b)0,12Example: t = algebraic productA(x) = A(x,4,5,6), B(y) = B(y,4,5,6)Main types of rule bases Fuzzy rule base R1, R2,.,RN finite family of fuzzy rules Fuzzy rule base can assume various

54、 formats:. fuzzy graph Ri: If X is Ai then Y is Bi is a fuzzy granule in XY, i = 1,.,N. fuzzy implication rule base Ri: If X is Ai then Y is Bi is fuzzy implication, i = 1,.,N . functional fuzzy rule base Ri: If X is Ai then y = fi(x) is a functional fuzzy rule, i = 1,.,NFuzzy graph Fuzzy rule base

55、R collection of rules R1, R2,.,RN Each fuzzy rule Ri is a fuzzy granule (point) Fuzzy graph R is a collection of fuzzy granules granular approximation of a function R = R1 or R2 or.or RN general formPointPoint P in XYP = ABA is a singleton in XB is a singleton in YGranuleGranule G in XYG = ABA is an

56、 interval in XB is an interval in YFuzzy granules fuzzy pointsfuzzy granule R in XYR = ABA is a fuzzy set on XB is a fuzzy set on YFuzzy rule base as a set fuzzy granulesRi = AiBiGraph of a function f and its granular approximation RfRRi = AiBiFuzzy rule base and fuzzy graphExample 1Ri = AiBi Ri(x,y

57、) = min Ai(x), Bi(y)R = Ri R(x,y) = max Ri(x,y), i = 1,., N Fuzzy rule base and fuzzy graphExample 2Ri = Ai t Bi Ri(x,y) = Ai(x) Bi(y)R = Ri R(x,y) = max Ri(x,y), i = 1,., N Fuzzy inference Compositional rule of inference X is A (X,Y) is R Y is BX is A(X,Y) is R Y is AoRTypes of rule-based systems a

58、nd architecturesLinguistic fuzzy modelsP:X is A and Y is BinputR1:If X is A1 and Y is B1 then Z is C1 .Ri:If X is Ai and Y is Bi then Z is Cirule base .RN:If X is AN and Y is BN then Z is CNZ:Z is Coutput all fuzzy sets A, B, Ai,s and Bi,s are given rule and connectives (and, or) with known semantic

59、s membership function of fuzzy set C = ?min-max modelsAssumeP: X is A and Y is BP(x,y) = minA(x), B(y)Ri: If X is Ai and Y is Bi then Z is CiRi(x,y,z) = minAi(x), Bi(y), Ci(z) i = 1,., NUsing the compositional rule of inference (t = min)Example: min-max fuzzy model processingmin-max fuzzy model arch

60、itecture Special case: numeric inputs Numeric outputDesign issues of FRBS:Consistency and completenessGiven input/output data: (x1, y1), (x2, y2),.,(xM, yM)dataconsistencycompletenessaccuracyrulesIssue: quality of the rulesCompleteness of rules All data points represented through some fuzzy setmaxi