Source Code for Module mvpa.clfs.knn

  1  """This module provides a k-Nearest-Neighbour classifier.""" 
  2  # emacs: -*- mode: python; py-indent-offset: 4; indent-tabs-mode: nil -*- 
  3  # vi: set ft=python sts=4 ts=4 sw=4 et: 
  4  ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ## 
  5  # 
  6  #   See COPYING file distributed along with the PyMVPA package for the 
  7  #   copyright and license terms. 
  8  # 
  9  ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ### ## 
 10  """k-Nearest-Neighbour classifier.""" 
 11   
 12  __docformat__ = 'restructuredtext' 
 13   
 14   
 15  import numpy as N 
 16   
 17  from mvpa.base import warning 
 18  from mvpa.misc.support import indentDoc 
 19  from mvpa.clfs.base import Classifier 
 20  from mvpa.base.dochelpers import enhancedDocString 
 21  from mvpa.clfs.distance import squared_euclidean_distance 
 22   
 23  if __debug__: 
 24      from mvpa.base import debug 
 25   
 26   
 27 -class kNN(Classifier): 
 28      """ 
 29      k-Nearest-Neighbour classifier. 
 30   
 31      This is a simple classifier that bases its decision on the distances 
 32      between the training dataset samples and the test sample(s). Distances 
 33      are computed using a customizable distance function. A certain number 
 34      (`k`)of nearest neighbors is selected based on the smallest distances 
 35      and the labels of this neighboring samples are fed into a voting 
 36      function to determine the labels of the test sample. 
 37   
 38      Training a kNN classifier is extremely quick, as no actuall training 
 39      is performed as the training dataset is simply stored in the 
 40      classifier. All computations are done during classifier prediction. 
 41   
 42      .. note:: 
 43        If enabled, kNN stores the votes per class in the 'values' state after 
 44        calling predict(). 
 45   
 46      """ 
 47   
 48      _clf_internals = ['knn', 'non-linear', 'binary', 'multiclass', 
 49                        'notrain2predict' ] 
 50   
 51 -    def __init__(self, k=2, dfx=squared_euclidean_distance, 
 52                   voting='weighted', **kwargs): 
 53          """ 
 54          :Parameters: 
 55            k: unsigned integer 
 56              Number of nearest neighbours to be used for voting. 
 57            dfx: functor 
 58              Function to compute the distances between training and test samples. 
 59              Default: squared euclidean distance 
 60            voting: str 
 61              Voting method used to derive predictions from the nearest neighbors. 
 62              Possible values are 'majority' (simple majority of classes 
 63              determines vote) and 'weighted' (votes are weighted according to the 
 64              relative frequencies of each class in the training data). 
 65            **kwargs: 
 66              Additonal arguments are passed to the base class. 
 67          """ 
 68   
 69          # init base class first 
 70          Classifier.__init__(self, **kwargs) 
 71   
 72          self.__k = k 
 73          self.__dfx = dfx 
 74          self.__voting = voting 
 75          self.__data = None 
 76   
 77   
 78 -    def __repr__(self): 
 79          """Representation of the object 
 80          """ 
 81          return "kNN(k=%d, dfx=%s enable_states=%s)" % \ 
 82              (self.__k, self.__dfx, str(self.states.enabled)) 
 83   
 84   
 85 -    def __str__(self): 
 86          return "%s\n data: %s" % \ 
 87              (Classifier.__str__(self), indentDoc(self.__data)) 
 88   
 89   
 90 -    def _train(self, data): 
 91          """Train the classifier. 
 92   
 93          For kNN it is degenerate -- just stores the data. 
 94          """ 
 95          self.__data = data 
 96          if __debug__: 
 97              if str(data.samples.dtype).startswith('uint') \ 
 98                  or str(data.samples.dtype).startswith('int'): 
 99                  warning("kNN: input data is in integers. " + \ 
100                          "Overflow on arithmetic operations might result in"+\ 
101                          " errors. Please convert dataset's samples into" +\ 
102                          " floating datatype if any error is reported.") 
103          self.__weights = None 
104   
105          # create dictionary with an item for each condition 
106          uniquelabels = data.uniquelabels 
107          self.__votes_init = dict(zip(uniquelabels, 
108                                       [0] * len(uniquelabels))) 
109   
110   
111 -    def _predict(self, data): 
112          """Predict the class labels for the provided data. 
113   
114          Returns a list of class labels (one for each data sample). 
115          """ 
116          # make sure we're talking about arrays 
117          data = N.asarray(data) 
118   
119          # checks only in debug mode 
120          if __debug__: 
121              if not data.ndim == 2: 
122                  raise ValueError, "Data array must be two-dimensional." 
123   
124              if not data.shape[1] == self.__data.nfeatures: 
125                  raise ValueError, "Length of data samples (features) does " \ 
126                                    "not match the classifier." 
127   
128          # compute the distance matrix between training and test data with 
129          # distances stored row-wise, ie. distances between test sample [0] 
130          # and all training samples will end up in row 0 
131          dists = self.__dfx(self.__data.samples, data).T 
132   
133          # determine the k nearest neighbors per test sample 
134          knns = dists.argsort(axis=1)[:, :self.__k] 
135   
136          # predicted class labels will go here 
137          predicted = [] 
138          votes = [] 
139   
140          if self.__voting == 'majority': 
141              vfx = self.getMajorityVote 
142          elif self.__voting == 'weighted': 
143              vfx = self.getWeightedVote 
144          else: 
145              raise ValueError, "kNN told to perform unknown voting '%s'." % self.__voting 
146   
147          # perform voting 
148          results = [vfx(knn) for knn in knns] 
149   
150          # extract predictions 
151          predicted = [r[0] for r in results] 
152   
153          # store the predictions in the state. Relies on State._setitem to do 
154          # nothing if the relevant state member is not enabled 
155          self.predictions = predicted 
156          self.values = [r[1] for r in results] 
157   
158          return predicted 
159   
160   
161 -    def getMajorityVote(self, knn_ids): 
162          """Simple voting by choosing the majority of class neighbours. 
163          """ 
164   
165          uniquelabels = self.__data.uniquelabels 
166   
167          # translate knn ids into class labels 
168          knn_labels = N.array([ self.__data.labels[nn] for nn in knn_ids ]) 
169   
170          # number of occerences for each unique class in kNNs 
171          votes = self.__votes_init.copy() 
172          for nn in knn_ids: 
173              votes[self.__labels[nn]] += 1 
174   
175          # find the class with most votes 
176          # return votes as well to store them in the state 
177          return uniquelabels[N.asarray(votes).argmax()], \ 
178                 votes 
179   
180   
181 -    def getWeightedVote(self, knn_ids): 
182          """Vote with classes weighted by the number of samples per class. 
183          """ 
184          uniquelabels = self.__data.uniquelabels 
185   
186          # Lazy evaluation 
187          if self.__weights is None: 
188              # 
189              # It seemed to Yarik that this has to be evaluated just once per 
190              # training dataset. 
191              # 
192              self.__labels = self.__data.labels 
193              Nlabels = len(self.__labels) 
194              Nuniquelabels = len(uniquelabels) 
195   
196              # TODO: To get proper speed up for the next line only, 
197              #       histogram should be computed 
198              #       via sorting + counting "same" elements while reducing. 
199              #       Guaranteed complexity is NlogN whenever now it is N^2 
200              # compute the relative proportion of samples belonging to each 
201              # class (do it in one loop to improve speed and reduce readability 
202              self.__weights = \ 
203                  [ 1.0 - ((self.__labels == label).sum() / Nlabels) \ 
204                      for label in uniquelabels ] 
205              self.__weights = dict(zip(uniquelabels, self.__weights)) 
206   
207   
208          # number of occerences for each unique class in kNNs 
209          votes = self.__votes_init.copy() 
210          for nn in knn_ids: 
211              votes[self.__labels[nn]] += 1 
212   
213          # weight votes 
214          votes = [ self.__weights[ul] * votes[ul] for ul in uniquelabels] 
215   
216          # find the class with most votes 
217          # return votes as well to store them in the state 
218          return uniquelabels[N.asarray(votes).argmax()], \ 
219                 votes 
220   
221   
222 -    def untrain(self): 
223          """Reset trained state""" 
224          self.__data = None 
225          super(kNN, self).untrain() 
226