Source Code for Module QSTK.qstklearn.fastknn

  1  """ 
  2  This package is an implementation of a novel improvement to KNN which 
  3  speeds up query times 
  4  """ 
  5  import math,random,sys,bisect,time 
  6  import numpy,scipy.spatial.distance,scipy.spatial.kdtree 
  7  import cProfile,pstats,gendata 
  8   
  9 -def adistfun(u,v): 
 10          #assuming 1xN ndarrays 
 11          #return math.sqrt(((u-v)**2).sum()) 
 12          #return ((u-v)**2).sum() 
 13          tmp = (u-v) 
 14          return math.sqrt(numpy.dot(tmp,tmp)) 
 15   
 16 -class FastKNN: 
 17          """ 
 18          A class which implements the KNN learning algorithm with sped up 
 19          query times. 
 20   
 21          This class follows the conventions of other classes in the qstklearn 
 22          module, with a constructor that initializes basic parameters and 
 23          bookkeeping variables, an 'addEvidence' method for adding labeled 
 24          training data individually or as a batch, and a 'query' method 
 25          that returns an estimated class for an unlabled point.  Training 
 26          and testing data are in the form of numpy arrays, and classes are 
 27          discrete. 
 28           
 29          In order to speed up query times, this class keeps a number of lists which 
 30          sort the training data by distance to 'anchor' points.  The lists aren't 
 31          sorted until the first call to the 'query' method, after which, the lists 
 32          are kept in sorted order. Initial sort is done using pythons 'sort' 
 33          (samplesort), and sorted insertions with 'insort' from the bisect module. 
 34          """ 
 35 -        def __init__(self, num_anchors, k): 
 36                  """ 
 37                  Creates a new FastKNN object that will use the given number of  
 38                  anchors. 
 39                  """ 
 40                  self.num_anchors = num_anchors 
 41                  self.training_data = list() 
 42                  self.anchors = list() 
 43                  self.data_by_anchors = dict() 
 44                  self.data_classes = dict() 
 45                  self.is_sorted = False 
 46                  #self.distfun = scipy.spatial.distance.euclidean 
 47                  self.distfun = adistfun 
 48                  self.num_checks = 0 
 49                  self.kdt = None 
 50                  self.k = k 
 51           
 52 -        def resetAnchors(self,selection_type='random'): 
 53                  """ 
 54                  Picks a new set of anchors.  The anchor lists will be re-sorted upon 
 55                  the next call to 'query'. 
 56                   
 57                  selection_type - the method to use when selecting new anchor points. 
 58                  'random' performs a random permutation of the training points and 
 59                  picks the first 'num_anchors' as new anchors. 
 60                  """ 
 61                  if selection_type == 'random': 
 62                          self.anchors = range(len(self.training_data)) 
 63                          random.shuffle(self.anchors) 
 64                          self.anchors = self.anchors[0:self.num_anchors] 
 65                          self.kdt = scipy.spatial.kdtree.KDTree(numpy.array(self.training_data)[self.anchors,:]) 
 66                  self.is_sorted = False 
 67                                   
 68           
 69 -        def addEvidence(self,data,label): 
 70                  """ 
 71                  Adds to the set of training data. If the anchor lists were sorted 
 72                  before the call to this method, the new data will be inserted into 
 73                  the anchor lists using 'bisect.insort' 
 74                   
 75                  data - a numpy array, either a single point (1D) or a set of 
 76                  points (2D) 
 77                   
 78                  label - the label for data. A single value, or a list of values 
 79                  in the same order as the points in data. 
 80                  """ 
 81                  if len(data.shape)==1: 
 82                          new_idx = len(self.training_data) 
 83                          self.training_data.append(data) 
 84                          self.data_classes[new_idx] = label 
 85                          if self.is_sorted: 
 86                                  for a in self.anchors: 
 87                                          dist = self.distfun(data,self.training_data[a]) 
 88                                          bisect.insort(self.data_by_anchors[a],(dist,new_idx)) 
 89                  elif len(data.shape)>1: 
 90                          for i in xrange(len(data)): 
 91                                  thing = data[i] 
 92                                  new_idx = len(self.training_data) 
 93                                  self.training_data.append(thing) 
 94                                  self.data_classes[new_idx] = label[i] 
 95                                  if self.is_sorted: 
 96                                          for a in self.anchors: 
 97                                                  dist = self.distfun(thing,self.training_data[a]) 
 98                                                  bisect.insort(self.data_by_anchors[a],(dist,new_idx)) 
 99           
100 -        def query(self,point,k=None,method='mode',slow=False,dumdumcheck=False): 
101                  """ 
102                  Returns class value for an unlabled point by examining its k nearest 
103                  neighbors. 'method' determines how the class of the unlabled point is 
104                  determined. 
105                  """ 
106                  if k is None: 
107                          k = self.k 
108                  #stime = time.time() 
109                  if len(self.anchors) < self.num_anchors: 
110                          self.resetAnchors() 
111                  if not self.is_sorted: 
112                          for a in self.anchors: 
113                                  self.data_by_anchors[a] = [ ( self.distfun(self.training_data[datai],self.training_data[a]), datai) for datai in range(len(self.training_data))] 
114                                  self.data_by_anchors[a].sort(key=lambda pnt: pnt[0]) 
115                  #select the anchor to search from 
116                  #right now pick the anchor closest to the query point 
117                   
118                  #anchor = self.anchors[0] 
119                  #anchor_dist = self.distfun(point,self.training_data[anchor])  
120                  #for i in xrange(1,len(self.anchors)): 
121                  #       new_anchor = self.anchors[i] 
122                  #       new_anchor_dist = self.distfun(point,self.training_data[new_anchor]) 
123                  #       if new_anchor_dist < anchor_dist: 
124                  #               anchor = new_anchor 
125                  #               anchor_dist = new_anchor_dist 
126                  res = self.kdt.query(numpy.array([point,])) 
127                  anchor = self.anchors[res[1][0]] 
128                  anchor_dist = res[0][0] 
129                  #print "Found the anchor",anchor,anchor_dist 
130                   
131                  #now search through the list 
132                  anchor_list = self.data_by_anchors[anchor] 
133                  neighbors = list() 
134                  maxd = None 
135                  maxd_idx = 0 
136                  for i in xrange(0,len(anchor_list)): 
137                          nextpnt_dist = self.distfun(point,self.training_data[anchor_list[i][1]]) 
138                          self.num_checks += 1 
139                          nextthing = (nextpnt_dist,anchor_list[i][1]) 
140                           
141                          #ins_idx = bisect.bisect(neighbors,nextthing) 
142                          #if ins_idx <= k: 
143                          #       neighbors.insert(ins_idx,nextthing) 
144                          #       neighbors = neighbors[:k] 
145                          #if not(slow) and len(neighbors) >= k: 
146                          #       if anchor_dist + neighbors[k-1][0] < anchor_list[i][0]: 
147                          #               break 
148                           
149                          if len(neighbors)<k: 
150                                  if (maxd is None) or (maxd < nextpnt_dist): 
151                                          maxd = nextpnt_dist 
152                                          maxd_idx = len(neighbors) 
153                                  neighbors.append(nextthing) 
154                          elif nextpnt_dist < maxd: 
155                                  neighbors[maxd_idx] = nextthing 
156                                  maxthing = max(neighbors) 
157                                  maxd_idx = neighbors.index(maxthing) 
158                                  maxd = maxthing[0] 
159                          if not(slow) and len(neighbors) >= k: 
160                                  if anchor_dist + maxd < anchor_list[i][0]: 
161                                          break 
162   
163                  #we have the k neighbors, report the class 
164                  #of the query point via method 
165                  if method == 'mode': 
166                          class_count = dict() 
167                          for n in neighbors: 
168                                  nid = n[1] 
169                                  clss = self.data_classes[nid] 
170                                  if clss in class_count: 
171                                          tmp = class_count[clss] 
172                                  else: 
173                                          tmp = 0 
174                                  class_count[clss] = tmp+1 
175                          bleh = max(class_count.iteritems(),key=lambda item:item[1]) 
176                          if dumdumcheck and bleh[1] == 1: 
177                                  print "aHAH!" 
178                                  print point 
179                          rv = bleh[0] 
180                  elif method == 'mean': 
181                          return sum([self.data_classes[n[1]] for n in neighbors])/float(k) 
182                  #etime = time.time() 
183                  #print "Query time:", etime-stime 
184                  return rv 
185   
186 -def dataifywine(fname): 
187          foo = open(fname) 
188          bar = [line for line in foo] 
189          foo.close() 
190          #first line is the name of the attributes, strip it off 
191          bar = bar[1:] 
192          #trim, split, and cast the data. seperator is ';' 
193          return [map(float,thing.strip().split(';')) for thing in bar] 
194   
195 -def testwine(): 
196          wqred = dataifywine('wine/winequality-red.csv') + dataifywine('wine/winequality-white.csv') 
197          leftoutperc = 0.1 
198          leftout = int(len(wqred)*leftoutperc) 
199          testing = wqred[:leftout] 
200          training = wqred[leftout:] 
201          print "Training:",len(training) 
202          print "Testing:",len(testing) 
203          foo = FastKNN(10) 
204          foo.addEvidence(numpy.array([thing[:-1] for thing in training]), [thing[-1] for thing in training]) 
205          knn.addEvidence(numpy.array(training)) 
206          total = 0 
207          correct = 0 
208          for x in xrange(len(testing)): 
209                  thing = testing[x] 
210                  guess = foo.query(numpy.array(thing[:-1]),3) 
211                  #realknn = knn.query(numpy.array([thing[:-1],]),3,method='mean') 
212                  #guess = realknn[0] 
213                  #print realknn 
214                  #print guess, thing[-1] 
215                  if guess == thing[-1]: 
216                          correct += 1 
217                  total += 1 
218                  if total % 50 == 0: 
219                          print total,'/',len(testing) 
220          print correct,"/",total,":",float(correct)/float(total) 
221          print "Average checks per query:", float(foo.num_checks)/float(total) 
222           
223 -def testspiral(): 
224          for leftout in xrange(1,11): 
225                  print "Fold",leftout 
226                  foo = FastKNN(10) 
227                  for x in xrange(1,11): 
228                          if x != leftout: 
229                                  somedata = open("spiral/spiralfold%d.txt" % x) 
230                                  pnts = list() 
231                                  clss = list() 
232                                  for line in somedata: 
233                                          pbbbt,x,y = line.split() 
234                                          x,y = float(x),float(y) 
235                                          pnts.append((x,y)) 
236                                          clss.append(line.split()[0]) 
237                                  somedata.close() 
238                                  pnts = numpy.array(pnts) 
239                                  foo.addEvidence(pnts,clss) 
240                  somedata = open("spiral/spiralfold%d.txt" % leftout) 
241                  correct = total = 0 
242                  for line in somedata: 
243                          pbbbt,x,y = line.split() 
244                          x,y = float(x),float(y) 
245                          guess=foo.query((x,y),10) 
246                          #guess2 = foo.query((x,y),10,slow=True) 
247                          #if guess != guess2: 
248                          #       print "Crap!" 
249                          #       print guess,guess2,(x,y,pbbbt) 
250                          #print guess, pbbbt 
251                          if guess == pbbbt: 
252                                  correct += 1 
253                          total += 1 
254                  print correct,"/",total,":",float(correct)/float(total) 
255                  print "Average number of checks per query:",  
256                  print float(foo.num_checks)/float(total) 
257   
258 -def getflatcsv(fname): 
259          inf = open(fname) 
260          return numpy.array([map(float,s.strip().split(',')) for s in inf.readlines()]) 
261   
262 -def testgendata(): 
263          anchors = 200 
264          fname = 'test2.dat' 
265          querys = 1000 
266          d = 2 
267          k = 3 
268          bnds = ((-10,10),)*d 
269          clsses = (0,1) 
270          foo = FastKNN(anchors,k) 
271          data = getflatcsv(fname) 
272          foo.addEvidence(data[:,:-1],data[:,-1]) 
273          foo.num_checks = 0 
274          for x in xrange(querys): 
275                  pnt = numpy.array(gendata.gensingle(d,bnds,clsses)) 
276                  foo.query(pnt[:-1]) 
277                  if x % 50 == 0: 
278                          print float(foo.num_checks)/float(x+1), 
279                          print x,"/",querys 
280          print "Average # queries:", float(foo.num_checks)/float(querys) 
281           
282           
283   
284 -def test(): 
285          testgendata() 
286   
287  if __name__=="__main__": 
288          test() 
289          #prof= cProfile.Profile() 
290          #prof.run('test()') 
291          #stats = pstats.Stats(prof) 
292          #stats.sort_stats("cumulative").print_stats() 
293