mvpa.featsel.helpers

1 # emacs: -*- mode: python; py-indent-offset: 4; indent-tabs-mode: nil -*- 2 # vi: set ft=python sts=4 ts=4 sw=4 et: 3 ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ## 4 # 5 # See COPYING file distributed along with the PyMVPA package for the 6 # copyright and license terms. 7 # 8 ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ## 9 """""" 10 11 __docformat__ = 'restructuredtext' 12 13 from math import floor 14 import numpy as N 15 16 from mvpa.misc.state import ClassWithCollections, StateVariable 17 18 if __debug__: 19 from mvpa.base import debug 20 21 # 22 # Functors to be used for FeatureSelection 23 # 24

25 -class BestDetector(object):

26 """Determine whether the last value in a sequence is the best one given 27 some criterion. 28 """

29 - def __init__(self, func=min, lastminimum=False):

30 """Initialize with number of steps 31 32 :Parameters: 33 fun : functor 34 Functor to select the best results. Defaults to min 35 lastminimum : bool 36 Toggle whether the latest or the earliest minimum is used as 37 optimal value to determine the stopping criterion. 38 """ 39 self.__func = func 40 self.__lastminimum = lastminimum 41 self.__bestindex = None 42 """Stores the index of the last detected best value."""

43 44

45 - def __call__(self, errors):

46 """Returns True if the last value in `errors` is the best or False 47 otherwise. 48 """ 49 isbest = False 50 51 # just to prevent ValueError 52 if len(errors)==0: 53 return isbest 54 55 minerror = self.__func(errors) 56 57 if self.__lastminimum: 58 # make sure it is an array 59 errors = N.array(errors) 60 # to find out the location of the minimum but starting from the 61 # end! 62 minindex = N.array((errors == minerror).nonzero()).max() 63 else: 64 minindex = errors.index(minerror) 65 66 self.__bestindex = minindex 67 68 # if minimal is the last one reported -- it is the best 69 if minindex == len(errors)-1: 70 isbest = True 71 72 return isbest

73 74 bestindex = property(fget=lambda self:self.__bestindex)

75 76 77

78 -class StoppingCriterion(object):

79 """Base class for all functors to decide when to stop RFE (or may 80 be general optimization... so it probably will be moved out into 81 some other module 82 """ 83

84 - def __call__(self, errors):

85 """Instruct when to stop. 86 87 Every implementation should return `False` when an empty list is 88 passed as argument. 89 90 Returns tuple `stop`. 91 """ 92 raise NotImplementedError

93 94 95

96 -class MultiStopCrit(StoppingCriterion):

97 """Stop computation if the latest error drops below a certain threshold. 98 """

99 - def __init__(self, crits, mode='or'):

100 """ 101 :Parameters: 102 crits : list of StoppingCriterion instances 103 For each call to MultiStopCrit all of these criterions will 104 be evaluated. 105 mode : any of ('and', 'or') 106 Logical function to determine the multi criterion from the set 107 of base criteria. 108 """ 109 if not mode in ('and', 'or'): 110 raise ValueError, \ 111 "A mode '%s' is not supported." % `mode` 112 113 self.__mode = mode 114 self.__crits = crits

115 116

117 - def __call__(self, errors):

118 """Evaluate all criteria to determine the value of the multi criterion. 119 """ 120 # evaluate all crits 121 crits = [ c(errors) for c in self.__crits ] 122 123 if self.__mode == 'and': 124 return N.all(crits) 125 else: 126 return N.any(crits)

127 128 129

130 -class FixedErrorThresholdStopCrit(StoppingCriterion):

131 """Stop computation if the latest error drops below a certain threshold. 132 """

133 - def __init__(self, threshold):

134 """Initialize with threshold. 135 136 :Parameters: 137 threshold : float [0,1] 138 Error threshold. 139 """ 140 StoppingCriterion.__init__(self) 141 if threshold > 1.0 or threshold < 0.0: 142 raise ValueError, \ 143 "Threshold %f is out of a reasonable range [0,1]." \ 144 % `threshold` 145 self.__threshold = threshold

146 147

148 - def __call__(self, errors):

149 """Nothing special.""" 150 if len(errors)==0: 151 return False 152 if errors[-1] < self.__threshold: 153 return True 154 else: 155 return False

156 157 158 threshold = property(fget=lambda x:x.__threshold)

159 160 161

162 -class NStepsStopCrit(StoppingCriterion):

163 """Stop computation after a certain number of steps. 164 """

165 - def __init__(self, steps):

166 """Initialize with number of steps. 167 168 :Parameters: 169 steps : int 170 Number of steps after which to stop. 171 """ 172 StoppingCriterion.__init__(self) 173 if steps < 0: 174 raise ValueError, \ 175 "Number of steps %i is out of a reasonable range." \ 176 % `steps` 177 self.__steps = steps

178 179

180 - def __call__(self, errors):

181 """Nothing special.""" 182 if len(errors) >= self.__steps: 183 return True 184 else: 185 return False

186 187 188 steps = property(fget=lambda x:x.__steps)

189 190 191

192 -class NBackHistoryStopCrit(StoppingCriterion):

193 """Stop computation if for a number of steps error was increasing 194 """ 195

196 - def __init__(self, bestdetector=BestDetector(), steps=10):

197 """Initialize with number of steps 198 199 :Parameters: 200 bestdetector : BestDetector instance 201 used to determine where the best error is located. 202 steps : int 203 How many steps to check after optimal value. 204 """ 205 StoppingCriterion.__init__(self) 206 if steps < 0: 207 raise ValueError, \ 208 "Number of steps (got %d) should be non-negative" % steps 209 self.__bestdetector = bestdetector 210 self.__steps = steps

211 212

213 - def __call__(self, errors):

214 stop = False 215 216 # just to prevent ValueError 217 if len(errors)==0: 218 return stop 219 220 # charge best detector 221 self.__bestdetector(errors) 222 223 # if number of elements after the min >= len -- stop 224 if len(errors) - self.__bestdetector.bestindex > self.__steps: 225 stop = True 226 227 return stop

228 229 steps = property(fget=lambda x:x.__steps)

230 231 232

233 -class ElementSelector(ClassWithCollections):

234 """Base class to implement functors to select some elements based on a 235 sequence of values. 236 """ 237 238 ndiscarded = StateVariable(True, 239 doc="Store number of discarded elements.") 240

241 - def __init__(self, mode='discard', **kwargs):

242 """Cheap initialization. 243 244 :Parameters: 245 mode : ['discard', 'select'] 246 Decides whether to `select` or to `discard` features. 247 """ 248 ClassWithCollections.__init__(self, **kwargs) 249 250 self._setMode(mode) 251 """Flag whether to select or to discard elements."""

252 253

254 - def _setMode(self, mode):

255 """Choose `select` or `discard` mode.""" 256 257 if not mode in ['discard', 'select']: 258 raise ValueError, "Unkown selection mode [%s]. Can only be one " \ 259 "of 'select' or 'discard'." % mode 260 261 self.__mode = mode

262 263

264 - def __call__(self, seq):

265 """Implementations in derived classed have to return a list of selected 266 element IDs based on the given sequence. 267 """ 268 raise NotImplementedError

269 270 mode = property(fget=lambda self:self.__mode, fset=_setMode)

271 272

273 -class RangeElementSelector(ElementSelector):

274 """Select elements based on specified range of values""" 275

276 - def __init__(self, lower=None, upper=None, inclusive=False, 277 mode='select', **kwargs):

278 """Initialization `RangeElementSelector` 279 280 :Parameters: 281 lower 282 If not None -- select elements which are above of 283 specified value 284 upper 285 If not None -- select elements which are lower of 286 specified value 287 inclusive 288 Either to include end points 289 mode 290 overrides parent's default to be 'select' since it is more 291 native for RangeElementSelector 292 XXX TODO -- unify?? 293 294 `upper` could be lower than `lower` -- then selection is done 295 on values <= lower or >=upper (ie tails). This would produce 296 the same result if called with flipped values for mode and 297 inclusive. 298 299 If no upper no lower is set, assuming upper,lower=0, thus 300 outputing non-0 elements 301 """ 302 303 if lower is None and upper is None: 304 lower, upper = 0, 0 305 """Lets better return non-0 values if none of bounds is set""" 306 307 # init State before registering anything 308 ElementSelector.__init__(self, mode=mode, **kwargs) 309 310 self.__range = (lower, upper) 311 """Values on which to base selection""" 312 313 self.__inclusive = inclusive

314

315 - def __call__(self, seq):

316 """Returns selected IDs. 317 """ 318 lower, upper = self.__range 319 len_seq = len(seq) 320 if not lower is None: 321 if self.__inclusive: 322 selected = seq >= lower 323 else: 324 selected = seq > lower 325 else: 326 selected = N.ones( (len_seq), dtype=N.bool ) 327 328 if not upper is None: 329 if self.__inclusive: 330 selected_upper = seq <= upper 331 else: 332 selected_upper = seq < upper 333 if not lower is None: 334 if lower < upper: 335 # regular range 336 selected = N.logical_and(selected, selected_upper) 337 else: 338 # outside, though that would be similar to exclude 339 selected = N.logical_or(selected, selected_upper) 340 else: 341 selected = selected_upper 342 343 if self.mode == 'discard': 344 selected = N.logical_not(selected) 345 346 result = N.where(selected)[0] 347 348 if __debug__: 349 debug("ES", "Selected %d out of %d elements" % 350 (len(result), len_seq)) 351 return result

352 353

354 -class TailSelector(ElementSelector):

355 """Select elements from a tail of a distribution. 356 357 The default behaviour is to discard the lower tail of a given distribution. 358 """ 359 360 # TODO: 'both' to select from both tails

361 - def __init__(self, tail='lower', sort=True, **kwargs):

362 """Initialize TailSelector 363 364 :Parameters: 365 tail : ['lower', 'upper'] 366 Choose the tail to be processed. 367 sort : bool 368 Flag whether selected IDs will be sorted. Disable if not 369 necessary to save some CPU cycles. 370 371 """ 372 # init State before registering anything 373 ElementSelector.__init__(self, **kwargs) 374 375 self._setTail(tail) 376 """Know which tail to select.""" 377 378 self.__sort = sort

379 380

381 - def _setTail(self, tail):

382 """Set the tail to be processed.""" 383 if not tail in ['lower', 'upper']: 384 raise ValueError, "Unkown tail argument [%s]. Can only be one " \ 385 "of 'lower' or 'upper'." % tail 386 387 self.__tail = tail

388 389

390 - def _getNElements(self, seq):

391 """In derived classes has to return the number of elements to be 392 processed given a sequence values forming the distribution. 393 """ 394 raise NotImplementedError

395 396

397 - def __call__(self, seq):

398 """Returns selected IDs. 399 """ 400 # TODO: Think about selecting features which have equal values but 401 # some are selected and some are not 402 len_seq = len(seq) 403 # how many to select (cannot select more than available) 404 nelements = min(self._getNElements(seq), len_seq) 405 406 # make sure that data is ndarray and compute a sequence rank matrix 407 # lowest value is first 408 seqrank = N.array(seq).argsort() 409 410 if self.mode == 'discard' and self.__tail == 'upper': 411 good_ids = seqrank[:-1*nelements] 412 self.ndiscarded = nelements 413 elif self.mode == 'discard' and self.__tail == 'lower': 414 good_ids = seqrank[nelements:] 415 self.ndiscarded = nelements 416 elif self.mode == 'select' and self.__tail == 'upper': 417 good_ids = seqrank[-1*nelements:] 418 self.ndiscarded = len_seq - nelements 419 else: # select lower tail 420 good_ids = seqrank[:nelements] 421 self.ndiscarded = len_seq - nelements 422 423 # sort ids to keep order 424 # XXX should we do here are leave to other place 425 if self.__sort: 426 good_ids.sort() 427 428 return good_ids

429 430 431

432 -class FixedNElementTailSelector(TailSelector):

433 """Given a sequence, provide set of IDs for a fixed number of to be selected 434 elements. 435 """ 436

437 - def __init__(self, nelements, **kwargs):

438 """Cheap initialization. 439 440 :Parameters: 441 nelements : int 442 Number of elements to select/discard. 443 """ 444 TailSelector.__init__(self, **kwargs) 445 self.__nelements = None 446 self._setNElements(nelements)

447 448

449 - def __repr__(self):

450 return "%s number=%f" % ( 451 TailSelector.__repr__(self), self.nelements)

452 453

454 - def _getNElements(self, seq):

455 return self.__nelements

456 457

458 - def _setNElements(self, nelements):

459 if __debug__: 460 if nelements <= 0: 461 raise ValueError, "Number of elements less or equal to zero " \ 462 "does not make sense." 463 464 self.__nelements = nelements

465 466 467 nelements = property(fget=lambda x:x.__nelements, 468 fset=_setNElements)

469 470 471

472 -class FractionTailSelector(TailSelector):

473 """Given a sequence, provide Ids for a fraction of elements 474 """ 475

476 - def __init__(self, felements, **kwargs):

477 """Cheap initialization. 478 479 :Parameters: 480 felements : float (0,1.0] 481 Fraction of elements to select/discard. Note: Even when 0.0 is 482 specified at least one element will be selected. 483 """ 484 TailSelector.__init__(self, **kwargs) 485 self._setFElements(felements)

486 487

488 - def __repr__(self):

489 return "%s fraction=%f" % ( 490 TailSelector.__repr__(self), self.__felements)

491 492

493 - def _getNElements(self, seq):

494 num = int(floor(self.__felements * len(seq))) 495 num = max(1, num) # remove at least 1 496 # no need for checks as base class will do anyway 497 #return min(num, nselect) 498 return num

499 500

501 - def _setFElements(self, felements):

502 """What fraction to discard""" 503 if felements > 1.0 or felements < 0.0: 504 raise ValueError, \ 505 "Fraction (%f) cannot be outside of [0.0,1.0]" \ 506 % felements 507 508 self.__felements = felements

509 510 511 felements = property(fget=lambda x:x.__felements, 512 fset=_setFElements)

513

Source Code for Module mvpa.featsel.helpers