Source Code for Module mvpa.featsel.ifs

  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  """Incremental feature search (IFS). 
 10   
 11  Very similar to Recursive feature elimination (RFE), but instead of begining 
 12  with all features and stripping some sequentially, start with an empty feature 
 13  set and include important features successively. 
 14  """ 
 15   
 16  __docformat__ = 'restructuredtext' 
 17   
 18  import numpy as N 
 19  from mvpa.support.copy import copy 
 20   
 21  from mvpa.featsel.base import FeatureSelection 
 22  from mvpa.featsel.helpers import NBackHistoryStopCrit, \ 
 23                                   FixedNElementTailSelector, \ 
 24                                   BestDetector 
 25   
 26  from mvpa.misc.state import StateVariable 
 27   
 28  if __debug__: 
 29      from mvpa.base import debug 
 30   
 31   
 32 -class IFS(FeatureSelection): 
 33      """Incremental feature search. 
 34   
 35      A scalar `DatasetMeasure` is computed multiple times on variations of a 
 36      certain dataset. These measures are in turn used to incrementally select 
 37      important features. Starting with an empty feature set the dataset measure 
 38      is first computed for each single feature. A number of features is selected 
 39      based on the resulting data measure map (using an `ElementSelector`). 
 40   
 41      Next the dataset measure is computed again using each feature in addition 
 42      to the already selected feature set. Again the `ElementSelector` is used to 
 43      select more features. 
 44   
 45      For each feature selection the transfer error on some testdatset is 
 46      computed. This procedure is repeated until a given `StoppingCriterion` 
 47      is reached. 
 48      """ 
 49   
 50      errors = StateVariable() 
 51   
 52 -    def __init__(self, 
 53                   data_measure, 
 54                   transfer_error, 
 55                   bestdetector=BestDetector(), 
 56                   stopping_criterion=NBackHistoryStopCrit(BestDetector()), 
 57                   feature_selector=FixedNElementTailSelector(1, 
 58                                                              tail='upper', 
 59                                                              mode='select'), 
 60                   **kwargs 
 61                   ): 
 62          """Initialize incremental feature search 
 63   
 64          :Parameters: 
 65              data_measure : DatasetMeasure 
 66                  Computed for each candidate feature selection. 
 67              transfer_error : TransferError 
 68                  Compute against a test dataset for each incremental feature 
 69                  set. 
 70              bestdetector : Functor 
 71                  Given a list of error values it has to return a boolean that 
 72                  signals whether the latest error value is the total minimum. 
 73              stopping_criterion : Functor 
 74                  Given a list of error values it has to return whether the 
 75                  criterion is fulfilled. 
 76           """ 
 77          # bases init first 
 78          FeatureSelection.__init__(self, **kwargs) 
 79   
 80          self.__data_measure = data_measure 
 81          self.__transfer_error = transfer_error 
 82          self.__feature_selector = feature_selector 
 83          self.__bestdetector = bestdetector 
 84          self.__stopping_criterion = stopping_criterion 
 85   
 86   
 87 -    def __call__(self, dataset, testdataset): 
 88          """Proceed and select the features recursively eliminating less 
 89          important ones. 
 90   
 91          :Parameters: 
 92              `dataset`: `Dataset` 
 93                  used to select features and train classifiers to determine the 
 94                  transfer error. 
 95              `testdataset`: `Dataset` 
 96                  used to test the trained classifer on a certain feature set 
 97                  to determine the transfer error. 
 98   
 99          Returns a tuple with the dataset containing the feature subset of 
100          `dataset` that had the lowest transfer error of all tested sets until 
101          the stopping criterion was reached. The tuple also contains a dataset 
102          with the corrsponding features from the `testdataset`. 
103          """ 
104          errors = [] 
105          """Computed error for each tested features set.""" 
106   
107          # feature candidate are all features in the pattern object 
108          candidates = range( dataset.nfeatures ) 
109   
110          # initially empty list of selected features 
111          selected = [] 
112   
113          # results in here please 
114          results = None 
115   
116          # as long as there are candidates left 
117          # the loop will most likely get broken earlier if the stopping 
118          # criterion is reached 
119          while len( candidates ): 
120              # measures for all candidates 
121              measures = [] 
122   
123              # for all possible candidates 
124              for i, candidate in enumerate(candidates): 
125                  if __debug__: 
126                      debug('IFSC', "Tested %i" % i, cr=True) 
127   
128                  # take the new candidate and all already selected features 
129                  # select a new temporay feature subset from the dataset 
130                  # XXX assume MappedDataset and issue plain=True ?? 
131                  tmp_dataset = \ 
132                      dataset.selectFeatures(selected + [candidate]) 
133   
134                  # compute data measure on this feature set 
135                  measures.append(self.__data_measure(tmp_dataset)) 
136   
137              measures = [N.asscalar(m) for m in measures] 
138              # Select promissing feature candidates (staging) 
139              # IDs are only applicable to the current set of feature candidates 
140              tmp_staging_ids = self.__feature_selector(measures) 
141   
142              # translate into real candidate ids 
143              staging_ids = [ candidates[i] for i in tmp_staging_ids ] 
144   
145              # mark them as selected and remove from candidates 
146              selected += staging_ids 
147              for i in staging_ids: 
148                  candidates.remove(i) 
149   
150              # compute transfer error for the new set 
151              # XXX assume MappedDataset and issue plain=True ?? 
152              error = self.__transfer_error(testdataset.selectFeatures(selected), 
153                                            dataset.selectFeatures(selected)) 
154              errors.append(error) 
155   
156              # Check if it is time to stop and if we got 
157              # the best result 
158              stop = self.__stopping_criterion(errors) 
159              isthebest = self.__bestdetector(errors) 
160   
161              if __debug__: 
162                  debug('IFSC', 
163                        "nselected %i; error: %.4f " \ 
164                        "best/stop=%d/%d\n" \ 
165                        % (len(selected), errors[-1], isthebest, stop), 
166                        cr=True, lf=True) 
167   
168              if isthebest: 
169                  # do copy to survive later selections 
170                  results = copy(selected) 
171   
172              # leave the loop when the criterion is reached 
173              if stop: 
174                  break 
175   
176          # charge state 
177          self.errors = errors 
178   
179          # best dataset ever is returned 
180          return dataset.selectFeatures(results), \ 
181                 testdataset.selectFeatures(results) 
182