fuzzy.set.operations

1 # -*- coding: utf-8 -*- 2 # 3 # Copyright (C) 2009 Rene Liebscher 4 # 5 # This program is free software; you can redistribute it and/or modify it under 6 # the terms of the GNU Lesser General Public License as published by the Free 7 # Software Foundation; either version 3 of the License, or (at your option) any 8 # later version. 9 # 10 # This program is distributed in the hope that it will be useful, but WITHOUT 11 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 12 # FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more 13 # details. 14 # 15 # You should have received a copy of the GNU Lesser General Public License 16 # along with this program; if not, see <http://www.gnu.org/licenses/>. 17 # 18 """ 19 Helper functions for calculation with fuzzy sets. 20 21 Examples can be found here U{http://pyfuzzy.sourceforge.net/demo/merge/} 22 23 * Intersection of set1 and set2 can be done by 24 25 C{set = merge(T_NORM,set1,set2)} 26 27 where T_NORM is a t-norm eg. Min. 28 (or a function which accepts two parameters as min().) 29 30 * Union of set1 and set2 can be done by 31 32 C{set = merge(S_NORM,set1,set2)} 33 34 where S_NORM is a s-norm eg. Max. 35 (or a function which accepts two parameters as max().) 36 37 * Complement of set1 can be done by 38 39 C{set = norm(lambda a,b:1.0-a ,set1,0.0)} 40 41 using a user defined function for it. 42 (The second parameter is ignored or better said 43 it doesn't influence the value, it only influences 44 maybe where the points of the resulting polygon are 45 set.) 46 47 * Activation function can be done by 48 49 C{set = norm(act_norm,set,act_value)} 50 51 where act_norm is any L{fuzzy.norm} or two params function (eg. min) 52 and act_value is the result of a rule calculation. 53 """ 54 55 __revision__ = "$Id: operations.py,v 1.13 2013-01-09 20:10:19 rliebscher Exp $" 56 57 from fuzzy.Exception import FuzzyException 58 59 # helper functions

60 -def _find_root(f, x1, x2, f1=None, f2=None, epsilon=None):

61 """Find root of function f between x1,x2 by using the regula falsi method 62 with the pegasus modification. 63 See also U{http://de.wikipedia.org/wiki/Regula_Falsi}. (The english 64 version lacks the description of pegasus modification.) 65 The algorithm stops if the error estimation is smaller than epsilon 66 or there is an ZeroDivisionError, which means both values f1 and f2 are 67 identical (should be 0 then). 68 69 @param f: function for which to find M{f(x)=0} 70 @type f: M{f(x)} 71 @param x1: left border of range 72 @type x1: float 73 @param x2: right border of range 74 @type x2: float 75 @param f1: value for x1, if available 76 @type f1: float 77 @param f2: value for x2, if available 78 @type f2: float 79 @param epsilon: break condition for algorithm (value < epsilon) 80 @type epsilon: float/None 81 @return: M{x} where M{f(x)=0} 82 @rtype: float 83 """ 84 if f1 is None: 85 f1 = f(x1) 86 if f2 is None: 87 f2 = f(x2) 88 if f1 * f2 > 0.: 89 raise FuzzyException("need interval with root") 90 if epsilon is None: 91 epsilon = 1.e-10 92 epsx = epsz = epsilon 93 z = (x1+x2)/2. 94 try: 95 i = 0 96 while i < 1000: 97 i += 1 98 z = x1 - f1 * (x2 - x1) / (f2 - f1) # approximation for root 99 fz = f(z) 100 101 #print x1,z,x2,f1,fz,f2 102 # smaller than epsilon: return z as approximation 103 if abs(x2 - x1) <= epsx or abs(fz) <= epsz: 104 return z 105 106 # root in [f(xz), f(x2)]?: 107 if fz * f2 < 0.: 108 # check [z, x2], but exchange borders 109 x1,x2,f1,f2 = x2,z,f2,fz 110 else: 111 # check [x1, z], and modify the value f1, 112 # so next steps x1 will move 113 x1,x2,f1,f2 = x1,z,f1*f2/(f2+fz),fz 114 raise FuzzyException("Too much iterations: %d" % i) 115 except ZeroDivisionError: 116 #print "ZeroDivisionError" 117 return z

118

119 -def _find_root_linear(x1,x2,f1,f2):

120 """Find root x1,x2 by using interpolation. 121 122 @param x1: left border of range 123 @type x1: float 124 @param x2: right border of range 125 @type x2: float 126 @param f1: value for x1 127 @type f1: float 128 @param f2: value for x2 129 @type f2: float 130 @return: M{x} where M{f(x)=0} 131 @rtype: float 132 """ 133 m = f1 / (f2 - f1) 134 return x1 - m * (x2 - x1)

135

136 -def _find_intersection(x1,x2,fa1,fa2,fb1,fb2):

137 """Find intersection of two linear functions fa/fb between x1,x2 138 with values there fa1/fb1 and fa2/fb2. 139 140 @param x1: left border of range 141 @type x1: float 142 @param x2: right border of range 143 @type x2: float 144 @param fa1: value for x1 145 @type fa1: float 146 @param fa2: value for x2 147 @type fa2: float 148 @param fb1: value for x1 149 @type fb1: float 150 @param fb2: value for x2 151 @type fb2: float 152 @return: M{x} where M{fa(x)-fb(x)=0} 153 @rtype: float 154 """ 155 return _find_root_linear(x1,x2,fa1-fb1,fa2-fb2)

156

157 -def check(x,y1,y2):

158 if isinstance(y1,list) and len(y1)==1: 159 y1 = y1[0] 160 if isinstance(y1,float) and isinstance(y2,float): 161 return [(x,y1,y2)] 162 elif isinstance(y1,float) and isinstance(y2,list): 163 return [(x,y1,y2_) for y2_ in y2] 164 elif isinstance(y1,list) and isinstance(y2,float): 165 return [(x,y2_,y1_) for x,y1_,y2_ in check(x,y2,y1)] 166 else: 167 if len(y1) == len(y2): 168 # intersection 169 # for all x,y1,y2 170 return [(x,y1_,y2_) for y1_,y2_ in zip(y1,y2)] 171 elif len(y1) < len(y2): 172 if len(y2)>3: 173 raise FuzzyException() 174 # only case 2-3 is left 175 return [(x,y1[0],y2[0]),(x,y1[1],y2[1]),(x,y1[1],y2[2])] 176 else: 177 return [(x,y2,y1) for x,y1,y2 in check(x,y2_,y1_)]

178 179

180 -def _merge_generator1(set1, set2):

181 """Returns a new fuzzy set which is the merger of set1 and set2, 182 where the membership of the result set is equal to C{NORM(set1(x),set2(x))}. 183 184 @param set1: fuzzy set 185 @type set1: L{fuzzy.set.Set} 186 @param set2: fuzzy set 187 @type set2: L{fuzzy.set.Set} 188 @return: resulting fuzzy set 189 @rtype: L{fuzzy.set.Polygon.Polygon} 190 """ 191 192 g1 = set1.getValuesXY() 193 g2 = set2.getValuesXY() 194 195 def next_(g,x,y): 196 try: 197 x,y = next(g) 198 return x,y,False 199 except StopIteration: 200 return x,y,True

201 202 UPDATE_1 = 1 203 UPDATE_2 = 2 204 UPDATE_BOTH = 3 205 206 x1,y1,end1 = next_(g1,None,None) 207 x2,y2,end2 = next_(g2,None,None) 208 while not (end1 and end2): 209 if end1: 210 update = UPDATE_2 211 elif end2: 212 update = UPDATE_1 213 elif x1 < x2: 214 update = UPDATE_1 215 elif x1 > x2: 216 update = UPDATE_2 217 else: 218 update = UPDATE_BOTH 219 220 if update == UPDATE_1: 221 x = x1 222 y1_ = y1 223 y2_ = set2(x) 224 elif update == UPDATE_2: 225 x = x2 226 y1_ = set1(x) 227 y2_ = y2 228 else: 229 x = x1 # x1 == x2 ! 230 y1_ = y1 231 y2_ = y2 232 233 #check 234 for _,_y1,_y2 in check(x,y1_,y2_): 235 # add this point 236 yield (x, _y1, _y2) 237 238 if update == UPDATE_1: 239 x1,y1,end1 = next_(g1,x1,y1) 240 elif update == UPDATE_2: 241 x2,y2,end2 = next_(g2,x2,y2) 242 else: 243 x1,y1,end1 = next_(g1,x1,y1) 244 x2,y2,end2 = next_(g2,x2,y2) 245 246

247 -def _merge_generator(NORM, set1, set2):

248 """Returns a new fuzzy set which is the merger of set1 and set2, 249 where the membership of the result set is equal to C{NORM(set1(x),set2(x))}. 250 251 @param NORM: fuzzy norm to calculate both sets values. For example Min(), Max(), ... 252 Also possible as two params function, eg. C{lambda a,b: (a+b)/2.}. 253 @type NORM: L{fuzzy.norm.Norm.Norm} 254 @param set1: fuzzy set 255 @type set1: L{fuzzy.set.Set} 256 @param set2: fuzzy set 257 @type set2: L{fuzzy.set.Set} 258 @return: resulting fuzzy set 259 @rtype: L{fuzzy.set.Polygon.Polygon} 260 """ 261 262 from fuzzy.set.Polygon import Polygon 263 use_find_root = not (isinstance(set1, Polygon) and isinstance(set2, Polygon)) 264 265 g = _merge_generator1(set1,set2) 266 x,y1,y2 = next(g) 267 yield (x, NORM(y1, y2)) 268 prev_x, prev_y1, prev_y2 = x, y1, y2 269 for x,y1,y2 in g: 270 # test if intersection => split interval 271 if (x != prev_x) and ((y1>y2 and prev_y1<prev_y2) or (y1<y2 and prev_y1>prev_y2)): 272 # calculate intersection 273 if use_find_root: 274 f = lambda x, set1=set1, set2=set2: set1(x)-set2(x) 275 x_ = _find_root(f, prev_x, x, prev_y1-prev_y2, y1-y2) 276 else: 277 x_ = _find_intersection(prev_x,x,prev_y1,y1,prev_y2,y2) 278 y1_ = set1(x_) 279 y2_ = set2(x_) 280 # add this point 281 yield (x_, NORM(y1_, y2_)) 282 # set saved point to intermediate 283 prev_x, prev_y1, prev_y2 = x_, y1_, y2_ 284 # add this point 285 yield (x, NORM(y1, y2)) 286 prev_x, prev_y1, prev_y2 = x, y1, y2

287

288 -def merge(NORM, set1, set2, segment_size=None):

289 """Returns a new fuzzy set which is the merger of set1 and set2, 290 where the membership of the result set is equal to C{NORM(set1(x),set2(x))}. 291 292 For nonlinear operations you might want set the segment size to a value 293 which controls how large a linear segment of the result can be. 294 See also the following examples: 295 - U{http://pyfuzzy.sourceforge.net/demo/merge/AlgebraicProduct_d_d.png} - The algebraic product is M{x*y}, so using it on the same set, it calculates the square of it. 296 - U{http://pyfuzzy.sourceforge.net/demo/merge/AlgebraicSum_d_d.png} - The algebraic sum is M{x+y-x*y}. 297 298 @param NORM: fuzzy norm to calculate both sets values. For example Min(), Max(), ... 299 Also possible as two params function, eg. C{lambda a,b: (a+b)/2.}. 300 @type NORM: L{fuzzy.norm.Norm.Norm} 301 @param set1: fuzzy set 302 @type set1: L{fuzzy.set.Set} 303 @param set2: fuzzy set 304 @type set2: L{fuzzy.set.Set} 305 @param segment_size: maximum size of a segment 306 @type segment_size: float/None 307 @return: resulting fuzzy set 308 @rtype: L{fuzzy.set.Polygon.Polygon} 309 """ 310 from fuzzy.set.Polygon import Polygon 311 ret = Polygon() 312 313 prev_x, prev_y = None, None 314 for x, y in _merge_generator(NORM, set1, set2): 315 if (segment_size is not None) and (prev_x is not None) and (abs(y-prev_y)>0.01): 316 diff = x-prev_x 317 if diff > 2.*segment_size: 318 n = int(diff/segment_size) 319 dx = diff/n 320 for i in range(1, n): 321 x_ = prev_x+i*dx 322 ret.add(x_, NORM(set1(x_), set2(x_))) 323 ret.add(x, y) 324 prev_x, prev_y = x, y 325 326 return ret

327 328

329 -def _norm_generator(NORM, set, value):

330 """Returns a new fuzzy set which is this set normed with value. 331 where the membership of the result set is equal to C{NORM(set(x),value)}. 332 333 @param NORM: fuzzy norm to calculate set's values with value. For example Min(), Max(), ... 334 Also possible as two params function, eg. C{lambda a,b: (a+b)/2.}. 335 @type NORM: L{fuzzy.norm.Norm.Norm} 336 @param set: fuzzy set 337 @type set: L{fuzzy.set.Set} 338 @param value: value 339 @type value: float 340 """ 341 342 from fuzzy.set.Polygon import Polygon 343 use_find_root = not isinstance(set, Polygon) 344 345 prev_x = None 346 prev_y = None 347 for x,y in set.getValuesXY(flat=True): 348 if prev_x is None: 349 pass 350 else: 351 # test if intersection => split interval 352 if (x != prev_x) and ((y>value and prev_y<value) or (y<value and prev_y>value)): 353 # calculate intersection 354 if use_find_root: 355 f = lambda x, set=set: set(x)-value 356 x_ = _find_root(f, prev_x, x, prev_y-value, y-value) 357 else: 358 x_ = _find_intersection(prev_x,x,prev_y,y,value,value) 359 y_ = set(x_) 360 # add this point 361 yield (x_, NORM(y_, value)) 362 # set saved point to intermediate 363 prev_x, prev_y = x_, y_ 364 # add this point 365 prev_x,prev_y = x,y 366 yield (x, NORM(y, value))

367

368 -def norm(NORM, set, value, segment_size=None):

369 """Returns a new fuzzy set which ist this set normed with value. 370 where the membership of the result set is equal to C{NORM(set(x),value)}. 371 372 For meaning of segment_size see also L{fuzzy.set.operations.merge}. 373 374 @param NORM: fuzzy norm to calculate set's values with value. For example Min(), Max(), ... 375 Also possible as two params function, eg. C{lambda a,b: (a+b)/2.}. 376 @type NORM: L{fuzzy.norm.Norm.Norm} 377 @param set: fuzzy set 378 @type set: L{fuzzy.set.Set} 379 @param value: value 380 @type value: float 381 @param segment_size: maximum size of a segment 382 @type segment_size: float/None 383 @return: resulting fuzzy set 384 @rtype: L{fuzzy.set.Polygon.Polygon} 385 """ 386 from fuzzy.set.Polygon import Polygon 387 ret = Polygon() 388 389 prev_x, prev_y = None, None 390 for x, y in _norm_generator(NORM, set, value): 391 if (segment_size is not None) and (prev_x is not None) and (abs(y-prev_y)>0.01): 392 diff = x-prev_x 393 if diff > 2.*segment_size: 394 n = int(diff/segment_size) 395 dx = diff/n 396 for i in range(1, n): 397 x_ = prev_x+i*dx 398 ret.add(x_, NORM(set(x_), value)) 399 ret.add(x, y) 400 prev_x, prev_y = x, y 401 402 return ret

403

404 -def _complement_generator(COMPLEMENT, set):

405 """Returns a new fuzzy set which is this complement of the given set. 406 (Where the membership of the result set is equal to C{COMPLEMENT(set(x))}. 407 408 @param COMPLEMENT: fuzzy complement to use. For example Zadeh(), ... 409 Also possible as one param function, eg. C{lambda x: 1.-x}. 410 @type COMPLEMENT: L{fuzzy.complement.Base.Base} 411 @param set: fuzzy set 412 @type set: L{fuzzy.set.Set} 413 @return: resulting fuzzy set 414 @rtype: L{fuzzy.set.Polygon.Polygon} 415 """ 416 for x,y in set.getValuesXY(flat=True): 417 yield (x, COMPLEMENT(y))

418

419 -def complement(COMPLEMENT, set, segment_size=None):

420 """Returns a new fuzzy set which is this complement of the given set. 421 (Where the membership of the result set is equal to C{COMPLEMENT(set(x))}. 422 423 For meaning of segment_size see also L{fuzzy.set.operations.merge}. 424 425 @param COMPLEMENT: fuzzy complement to use. For example Zadeh(), ... 426 Also possible as one param function, eg. C{lambda x: 1.-x}. 427 @type COMPLEMENT: L{fuzzy.complement.Base.Base} 428 @param set: fuzzy set 429 @type set: L{fuzzy.set.Set} 430 @param segment_size: maximum size of a segment 431 @type segment_size: float/None 432 @return: resulting fuzzy set 433 @rtype: L{fuzzy.set.Polygon.Polygon} 434 """ 435 from fuzzy.set.Polygon import Polygon 436 ret = Polygon() 437 438 prev_x, prev_y = None, None 439 for x, y in _complement_generator(COMPLEMENT, set): 440 if (segment_size is not None) and (prev_x is not None) and (abs(y-prev_y)>0.01): 441 diff = x-prev_x 442 if diff > 2.*segment_size: 443 n = int(diff/segment_size) 444 dx = diff/n 445 for i in range(1, n): 446 x_ = prev_x+i*dx 447 ret.add(x_, COMPLEMENT(set(x_))) 448 ret.add(x, y) 449 prev_x, prev_y = x, y 450 451 return ret

452

Source Code for Module fuzzy.set.operations