<s> import math <EOL> def lg ( x ) : <EOL> return math . log ( x ) / math . log ( <NUM_LIT:2> ) <EOL> def entropy ( labels ) : <EOL> label_set = set ( labels ) <EOL> sums = { } <EOL> count = <NUM_LIT:0.0> <EOL> for each in label_set : <EOL> sums [ each ] = <NUM_LIT:0.0> <EOL> for each in labels : <EOL> sums [ each ] += <NUM_LIT:1.0> <EOL> count += <NUM_LIT:1.0> <EOL> ent = <NUM_LIT:0.0> <EOL> for each in sums . values ( ) : <EOL> p_i = each / count <EOL> ent -= p_i * lg ( p_i ) <EOL> return ent <EOL> def maxValue ( labels ) : <EOL> label_set = set ( labels ) <EOL> sums = { } <EOL> count = <NUM_LIT:0.0> <EOL> for each in label_set : <EOL> sums [ each ] = <NUM_LIT:0.0> <EOL> for each in labels : <EOL> sums [ each ] += <NUM_LIT:1.0> <EOL> count += <NUM_LIT:1.0> <EOL> highVal = <NUM_LIT:0.0> <EOL> highLab = labels [ <NUM_LIT:0> ] <EOL> for key , value in sums . iteritems ( ) : <EOL> if value > highVal : <EOL> highVal = value <EOL> highLab = key <EOL> return highLab <EOL> def getLabels ( features ) : <EOL> labels = [ each [ <NUM_LIT:0> ] for each in features ] <EOL> return labels <EOL> def splitFeatures ( feature , features ) : <EOL> split = { } <EOL> for label , values in features : <EOL> key = values [ feature ] <EOL> if not split . has_key ( key ) : <EOL> split [ key ] = [ ] <EOL> split [ key ] . append ( [ label , values ] ) <EOL> return split <EOL> class ID3 : <EOL> def __init__ ( self ) : <EOL> self . training_data = [ ] <EOL> self . testing_data = [ ] <EOL> self . labels = set ( ) <EOL> self . top = None <EOL> def addTraining ( self , label , feature ) : <EOL> '''<STR_LIT>''' <EOL> self . training_data . append ( ( label , feature ) ) <EOL> self . labels |= self . labels | set ( [ label ] ) <EOL> def addTesting ( self , label , feature ) : <EOL> '''<STR_LIT>''' <EOL> self . testing_data . append ( ( label , feature ) ) <EOL> def train ( self ) : <EOL> '''<STR_LIT>''' <EOL> self . top = Node ( self . training_data ) <EOL> def classify ( self , feature ) : <EOL> '''<STR_LIT>''' <EOL> return self . top . classify ( feature ) <EOL> def test ( self , data = None ) : <EOL> if data == None : <EOL> data = self . testing_data <EOL> correct = <NUM_LIT:0> <EOL> wrong = <NUM_LIT:0> <EOL> for label , feature in data : <EOL> c , _ = self . classify ( feature ) <EOL> if c == label : <EOL> correct += <NUM_LIT:1> <EOL> else : <EOL> wrong += <NUM_LIT:1> <EOL> print "<STR_LIT>" % ( correct , correct + wrong ) <EOL> return float ( correct ) / float ( correct + wrong ) <EOL> class Node : <EOL> def __init__ ( self , features ) : <EOL> self . cutoff = <NUM_LIT:2> <EOL> self . min_entropy = <NUM_LIT> <EOL> self . feature = None <EOL> self . entropy = None <EOL> self . label = None <EOL> self . children = None <EOL> self . train ( features ) <EOL> def train ( self , features ) : <EOL> labels = getLabels ( features ) <EOL> print "<STR_LIT>" , entropy ( labels ) <EOL> print "<STR_LIT>" , maxValue ( labels ) <EOL> self . label = maxValue ( labels ) <EOL> self . entropy = entropy ( labels ) <EOL> if len ( features ) < self . cutoff or self . entropy < self . min_entropy : <EOL> return <EOL> no_feature = len ( features [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] ) <EOL> max_gain = <NUM_LIT:0.0> <EOL> max_feature = <NUM_LIT:0> <EOL> max_children = { } <EOL> for i in range ( no_feature ) : <EOL> gain = self . entropy <EOL> s = splitFeatures ( i , features ) <EOL> for _ , vals in s . iteritems ( ) : <EOL> scale = float ( len ( vals ) ) / float ( len ( features ) ) <EOL> e = entropy ( getLabels ( vals ) ) <EOL> gain -= scale * e <EOL> if max_gain < gain : <EOL> max_gain = gain <EOL> max_feature = i <EOL> max_children = s <EOL> print "<STR_LIT>" , max_gain , max_feature <EOL> self . feature = max_feature <EOL> self . gain = max_gain <EOL> self . children = { } <EOL> for label , features in max_children . iteritems ( ) : <EOL> self . children [ label ] = Node ( features ) <EOL> def classify ( self , feature ) : <EOL> '''<STR_LIT>''' <EOL> if self . feature : <EOL> val = feature [ self . feature ] <EOL> if self . children . has_key ( val ) : <EOL> return self . children [ val ] . classify ( feature ) <EOL> return self . label , None <EOL> def toBits ( val , bits = <NUM_LIT:4> ) : <EOL> result = [ ] <EOL> for _ in range ( bits ) : <EOL> result . append ( val & <NUM_LIT:1> ) <EOL> val = val >> <NUM_LIT:1> <EOL> result . reverse ( ) <EOL> return result </s>
