mvpa.clfs.knn

30 """ 31 k-Nearest-Neighbour classifier. 32 33 This is a simple classifier that bases its decision on the distances 34 between the training dataset samples and the test sample(s). Distances 35 are computed using a customizable distance function. A certain number 36 (`k`)of nearest neighbors is selected based on the smallest distances 37 and the labels of this neighboring samples are fed into a voting 38 function to determine the labels of the test sample. 39 40 Training a kNN classifier is extremely quick, as no actuall training 41 is performed as the training dataset is simply stored in the 42 classifier. All computations are done during classifier prediction. 43 44 .. note:: 45 If enabled, kNN stores the votes per class in the 'values' state after 46 calling predict(). 47 48 """ 49 50 _clf_internals = ['knn', 'non-linear', 'binary', 'multiclass', 51 'notrain2predict' ] 52

53 - def __init__(self, k=2, dfx=squared_euclidean_distance, 54 voting='weighted', **kwargs):

55 """ 56 :Parameters: 57 k: unsigned integer 58 Number of nearest neighbours to be used for voting. 59 dfx: functor 60 Function to compute the distances between training and test samples. 61 Default: squared euclidean distance 62 voting: str 63 Voting method used to derive predictions from the nearest neighbors. 64 Possible values are 'majority' (simple majority of classes 65 determines vote) and 'weighted' (votes are weighted according to the 66 relative frequencies of each class in the training data). 67 **kwargs: 68 Additonal arguments are passed to the base class. 69 """ 70 71 # init base class first 72 Classifier.__init__(self, **kwargs) 73 74 self.__k = k 75 self.__dfx = dfx 76 self.__voting = voting 77 self.__data = None

78 79

80 - def __repr__(self, prefixes=[]):

81 """Representation of the object 82 """ 83 return super(kNN, self).__repr__( 84 ["k=%d" % self.__k, "dfx=%s" % self.__dfx, 85 "voting=%s" % repr(self.__voting)] 86 + prefixes)

87 88

89 - def __str__(self):

90 return "%s\n data: %s" % \ 91 (Classifier.__str__(self), indentDoc(self.__data))

92 93

94 - def _train(self, data):

95 """Train the classifier. 96 97 For kNN it is degenerate -- just stores the data. 98 """ 99 self.__data = data 100 if __debug__: 101 if str(data.samples.dtype).startswith('uint') \ 102 or str(data.samples.dtype).startswith('int'): 103 warning("kNN: input data is in integers. " + \ 104 "Overflow on arithmetic operations might result in"+\ 105 " errors. Please convert dataset's samples into" +\ 106 " floating datatype if any error is reported.") 107 self.__weights = None 108 109 # create dictionary with an item for each condition 110 uniquelabels = data.uniquelabels 111 self.__votes_init = dict(zip(uniquelabels, 112 [0] * len(uniquelabels)))

113 114

115 - def _predict(self, data):

116 """Predict the class labels for the provided data. 117 118 Returns a list of class labels (one for each data sample). 119 """ 120 # make sure we're talking about arrays 121 data = N.asarray(data) 122 123 # checks only in debug mode 124 if __debug__: 125 if not data.ndim == 2: 126 raise ValueError, "Data array must be two-dimensional." 127 128 if not data.shape[1] == self.__data.nfeatures: 129 raise ValueError, "Length of data samples (features) does " \ 130 "not match the classifier." 131 132 # compute the distance matrix between training and test data with 133 # distances stored row-wise, ie. distances between test sample [0] 134 # and all training samples will end up in row 0 135 dists = self.__dfx(self.__data.samples, data).T 136 137 # determine the k nearest neighbors per test sample 138 knns = dists.argsort(axis=1)[:, :self.__k] 139 140 # predicted class labels will go here 141 predicted = [] 142 143 if self.__voting == 'majority': 144 vfx = self.getMajorityVote 145 elif self.__voting == 'weighted': 146 vfx = self.getWeightedVote 147 else: 148 raise ValueError, "kNN told to perform unknown voting '%s'." \ 149 % self.__voting 150 151 # perform voting 152 results = [vfx(knn) for knn in knns] 153 154 # extract predictions 155 predicted = [r[0] for r in results] 156 157 # store the predictions in the state. Relies on State._setitem to do 158 # nothing if the relevant state member is not enabled 159 self.predictions = predicted 160 self.values = [r[1] for r in results] 161 162 return predicted

163 164

165 - def getMajorityVote(self, knn_ids):

166 """Simple voting by choosing the majority of class neighbors. 167 """ 168 # local bindings 169 _data = self.__data 170 labels = _data.labels 171 172 # number of occerences for each unique class in kNNs 173 votes = self.__votes_init.copy() 174 for nn in knn_ids: 175 votes[labels[nn]] += 1 176 177 # find the class with most votes 178 # return votes as well to store them in the state 179 if _dict_has_key: 180 # approx 5% faster implementation than below 181 maxvotes = max(votes.iteritems(), key=lambda x:x[1])[0] 182 else: 183 # no key keyword for max in elderly versions 184 maxvotes = max([(v, k) for k, v in votes.iteritems()])[1] 185 186 return maxvotes, \ 187 [votes[ul] for ul in _data.uniquelabels] # transform into lists

188 189

190 - def getWeightedVote(self, knn_ids):

191 """Vote with classes weighted by the number of samples per class. 192 """ 193 # local bindings 194 _data = self.__data 195 uniquelabels = _data.uniquelabels 196 197 # Lazy evaluation 198 if self.__weights is None: 199 # 200 # It seemed to Yarik that this has to be evaluated just once per 201 # training dataset. 202 # 203 self.__labels = labels = self.__data.labels 204 Nlabels = len(labels) 205 Nuniquelabels = len(uniquelabels) 206 207 # TODO: To get proper speed up for the next line only, 208 # histogram should be computed 209 # via sorting + counting "same" elements while reducing. 210 # Guaranteed complexity is NlogN whenever now it is N^2 211 # compute the relative proportion of samples belonging to each 212 # class (do it in one loop to improve speed and reduce readability 213 self.__weights = \ 214 [ 1.0 - ((labels == label).sum() / Nlabels) \ 215 for label in uniquelabels ] 216 self.__weights = dict(zip(uniquelabels, self.__weights)) 217 218 labels = self.__labels 219 # number of occerences for each unique class in kNNs 220 votes = self.__votes_init.copy() 221 for nn in knn_ids: 222 votes[labels[nn]] += 1 223 224 # weight votes 225 votes = [ self.__weights[ul] * votes[ul] for ul in uniquelabels] 226 227 # find the class with most votes 228 # return votes as well to store them in the state 229 return uniquelabels[N.asarray(votes).argmax()], \ 230 votes

231 232

233 - def untrain(self):

234 """Reset trained state""" 235 self.__data = None 236 super(kNN, self).untrain()

Source Code for Module mvpa.clfs.knn