<s> """<STR_LIT>""" <EOL> import math , random , sys , bisect , time <EOL> import numpy , scipy . spatial . distance , scipy . spatial . kdtree <EOL> import cProfile , pstats , gendata <EOL> def adistfun ( u , v ) : <EOL> tmp = ( u - v ) <EOL> return math . sqrt ( numpy . dot ( tmp , tmp ) ) <EOL> class FastKNN : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , num_anchors , k ) : <EOL> """<STR_LIT>""" <EOL> self . num_anchors = num_anchors <EOL> self . training_data = list ( ) <EOL> self . anchors = list ( ) <EOL> self . data_by_anchors = dict ( ) <EOL> self . data_classes = dict ( ) <EOL> self . is_sorted = False <EOL> self . distfun = adistfun <EOL> self . num_checks = <NUM_LIT:0> <EOL> self . kdt = None <EOL> self . k = k <EOL> def resetAnchors ( self , selection_type = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> if selection_type == '<STR_LIT>' : <EOL> self . anchors = range ( len ( self . training_data ) ) <EOL> random . shuffle ( self . anchors ) <EOL> self . anchors = self . anchors [ <NUM_LIT:0> : self . num_anchors ] <EOL> self . kdt = scipy . spatial . kdtree . KDTree ( numpy . array ( self . training_data ) [ self . anchors , : ] ) <EOL> self . is_sorted = False <EOL> def addEvidence ( self , data , label ) : <EOL> """<STR_LIT>""" <EOL> if len ( data . shape ) == <NUM_LIT:1> : <EOL> new_idx = len ( self . training_data ) <EOL> self . training_data . append ( data ) <EOL> self . data_classes [ new_idx ] = label <EOL> if self . is_sorted : <EOL> for a in self . anchors : <EOL> dist = self . distfun ( data , self . training_data [ a ] ) <EOL> bisect . insort ( self . data_by_anchors [ a ] , ( dist , new_idx ) ) <EOL> elif len ( data . shape ) > <NUM_LIT:1> : <EOL> for i in xrange ( len ( data ) ) : <EOL> thing = data [ i ] <EOL> new_idx = len ( self . training_data ) <EOL> self . training_data . append ( thing ) <EOL> self . data_classes [ new_idx ] = label [ i ] <EOL> if self . is_sorted : <EOL> for a in self . anchors : <EOL> dist = self . distfun ( thing , self . training_data [ a ] ) <EOL> bisect . insort ( self . data_by_anchors [ a ] , ( dist , new_idx ) ) <EOL> def query ( self , point , k = None , method = '<STR_LIT>' , slow = False , dumdumcheck = False ) : <EOL> """<STR_LIT>""" <EOL> if k is None : <EOL> k = self . k <EOL> if len ( self . anchors ) < self . num_anchors : <EOL> self . resetAnchors ( ) <EOL> if not self . is_sorted : <EOL> for a in self . anchors : <EOL> self . data_by_anchors [ a ] = [ ( self . distfun ( self . training_data [ datai ] , self . training_data [ a ] ) , datai ) for datai in range ( len ( self . training_data ) ) ] <EOL> self . data_by_anchors [ a ] . sort ( key = lambda pnt : pnt [ <NUM_LIT:0> ] ) <EOL> res = self . kdt . query ( numpy . array ( [ point , ] ) ) <EOL> anchor = self . anchors [ res [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] ] <EOL> anchor_dist = res [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] <EOL> anchor_list = self . data_by_anchors [ anchor ] <EOL> neighbors = list ( ) <EOL> maxd = None <EOL> maxd_idx = <NUM_LIT:0> <EOL> for i in xrange ( <NUM_LIT:0> , len ( anchor_list ) ) : <EOL> nextpnt_dist = self . distfun ( point , self . training_data [ anchor_list [ i ] [ <NUM_LIT:1> ] ] ) <EOL> self . num_checks += <NUM_LIT:1> <EOL> nextthing = ( nextpnt_dist , anchor_list [ i ] [ <NUM_LIT:1> ] ) <EOL> if len ( neighbors ) < k : <EOL> if ( maxd is None ) or ( maxd < nextpnt_dist ) : <EOL> maxd = nextpnt_dist <EOL> maxd_idx = len ( neighbors ) <EOL> neighbors . append ( nextthing ) <EOL> elif nextpnt_dist < maxd : <EOL> neighbors [ maxd_idx ] = nextthing <EOL> maxthing = max ( neighbors ) <EOL> maxd_idx = neighbors . index ( maxthing ) <EOL> maxd = maxthing [ <NUM_LIT:0> ] <EOL> if not ( slow ) and len ( neighbors ) >= k : <EOL> if anchor_dist + maxd < anchor_list [ i ] [ <NUM_LIT:0> ] : <EOL> break <EOL> if method == '<STR_LIT>' : <EOL> class_count = dict ( ) <EOL> for n in neighbors : <EOL> nid = n [ <NUM_LIT:1> ] <EOL> clss = self . data_classes [ nid ] <EOL> if clss in class_count : <EOL> tmp = class_count [ clss ] <EOL> else : <EOL> tmp = <NUM_LIT:0> <EOL> class_count [ clss ] = tmp + <NUM_LIT:1> <EOL> bleh = max ( class_count . iteritems ( ) , key = lambda item : item [ <NUM_LIT:1> ] ) <EOL> if dumdumcheck and bleh [ <NUM_LIT:1> ] == <NUM_LIT:1> : <EOL> print "<STR_LIT>" <EOL> print point <EOL> rv = bleh [ <NUM_LIT:0> ] <EOL> elif method == '<STR_LIT>' : <EOL> return sum ( [ self . data_classes [ n [ <NUM_LIT:1> ] ] for n in neighbors ] ) / float ( k ) <EOL> return rv <EOL> def dataifywine ( fname ) : <EOL> foo = open ( fname ) <EOL> bar = [ line for line in foo ] <EOL> foo . close ( ) <EOL> bar = bar [ <NUM_LIT:1> : ] <EOL> return [ map ( float , thing . strip ( ) . split ( '<STR_LIT:;>' ) ) for thing in bar ] <EOL> def testwine ( ) : <EOL> wqred = dataifywine ( '<STR_LIT>' ) + dataifywine ( '<STR_LIT>' ) <EOL> leftoutperc = <NUM_LIT:0.1> <EOL> leftout = int ( len ( wqred ) * leftoutperc ) <EOL> testing = wqred [ : leftout ] <EOL> training = wqred [ leftout : ] <EOL> print "<STR_LIT>" , len ( training ) <EOL> print "<STR_LIT>" , len ( testing ) <EOL> foo = FastKNN ( <NUM_LIT:10> ) <EOL> foo . addEvidence ( numpy . array ( [ thing [ : - <NUM_LIT:1> ] for thing in training ] ) , [ thing [ - <NUM_LIT:1> ] for thing in training ] ) <EOL> knn . addEvidence ( numpy . array ( training ) ) <EOL> total = <NUM_LIT:0> <EOL> correct = <NUM_LIT:0> <EOL> for x in xrange ( len ( testing ) ) : <EOL> thing = testing [ x ] <EOL> guess = foo . query ( numpy . array ( thing [ : - <NUM_LIT:1> ] ) , <NUM_LIT:3> ) <EOL> if guess == thing [ - <NUM_LIT:1> ] : <EOL> correct += <NUM_LIT:1> <EOL> total += <NUM_LIT:1> <EOL> if total % <NUM_LIT:50> == <NUM_LIT:0> : <EOL> print total , '<STR_LIT:/>' , len ( testing ) <EOL> print correct , "<STR_LIT:/>" , total , "<STR_LIT::>" , float ( correct ) / float ( total ) <EOL> print "<STR_LIT>" , float ( foo . num_checks ) / float ( total ) <EOL> def testspiral ( ) : <EOL> for leftout in xrange ( <NUM_LIT:1> , <NUM_LIT:11> ) : <EOL> print "<STR_LIT>" , leftout <EOL> foo = FastKNN ( <NUM_LIT:10> ) <EOL> for x in xrange ( <NUM_LIT:1> , <NUM_LIT:11> ) : <EOL> if x != leftout : <EOL> somedata = open ( "<STR_LIT>" % x ) <EOL> pnts = list ( ) <EOL> clss = list ( ) <EOL> for line in somedata : <EOL> pbbbt , x , y = line . split ( ) <EOL> x , y = float ( x ) , float ( y ) <EOL> pnts . append ( ( x , y ) ) <EOL> clss . append ( line . split ( ) [ <NUM_LIT:0> ] ) <EOL> somedata . close ( ) <EOL> pnts = numpy . array ( pnts ) <EOL> foo . addEvidence ( pnts , clss ) <EOL> somedata = open ( "<STR_LIT>" % leftout ) <EOL> correct = total = <NUM_LIT:0> <EOL> for line in somedata : <EOL> pbbbt , x , y = line . split ( ) <EOL> x , y = float ( x ) , float ( y ) <EOL> guess = foo . query ( ( x , y ) , <NUM_LIT:10> ) <EOL> if guess == pbbbt : <EOL> correct += <NUM_LIT:1> <EOL> total += <NUM_LIT:1> <EOL> print correct , "<STR_LIT:/>" , total , "<STR_LIT::>" , float ( correct ) / float ( total ) <EOL> print "<STR_LIT>" , <EOL> print float ( foo . num_checks ) / float ( total ) <EOL> def getflatcsv ( fname ) : <EOL> inf = open ( fname ) <EOL> return numpy . array ( [ map ( float , s . strip ( ) . split ( '<STR_LIT:U+002C>' ) ) for s in inf . readlines ( ) ] ) <EOL> def testgendata ( ) : <EOL> anchors = <NUM_LIT:200> <EOL> fname = '<STR_LIT>' <EOL> querys = <NUM_LIT:1000> <EOL> d = <NUM_LIT:2> <EOL> k = <NUM_LIT:3> <EOL> bnds = ( ( - <NUM_LIT:10> , <NUM_LIT:10> ) , ) * d <EOL> clsses = ( <NUM_LIT:0> , <NUM_LIT:1> ) <EOL> foo = FastKNN ( anchors , k ) <EOL> data = getflatcsv ( fname ) <EOL> foo . addEvidence ( data [ : , : - <NUM_LIT:1> ] , data [ : , - <NUM_LIT:1> ] ) <EOL> foo . num_checks = <NUM_LIT:0> <EOL> for x in xrange ( querys ) : <EOL> pnt = numpy . array ( gendata . gensingle ( d , bnds , clsses ) ) <EOL> foo . query ( pnt [ : - <NUM_LIT:1> ] ) <EOL> if x % <NUM_LIT:50> == <NUM_LIT:0> : <EOL> print float ( foo . num_checks ) / float ( x + <NUM_LIT:1> ) , <EOL> print x , "<STR_LIT:/>" , querys <EOL> print "<STR_LIT>" , float ( foo . num_checks ) / float ( querys ) <EOL> def test ( ) : <EOL> testgendata ( ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> test ( ) </s>
