<s> """<STR_LIT>""" <EOL> import math <EOL> from collections import Counter <EOL> import numpy as np <EOL> def mdl ( x , y , ft , accuracy , separate_max ) : <EOL> return mdl_nominal ( x , y , separate_max ) if ft == "<STR_LIT:d>" else mdl_numeric ( x , y , accuracy ) <EOL> def info_gain ( x , y , ft , accuracy , separate_max ) : <EOL> return info_gain_nominal ( x , y , separate_max ) if ft == "<STR_LIT:d>" else info_gain_numeric ( x , y , accuracy ) <EOL> def nominal_splits ( x , y , x_vals , y_dist , separate_max ) : <EOL> """<STR_LIT>""" <EOL> y_val = max ( y_dist , key = y_dist . get ) if separate_max else min ( y_dist , key = y_dist . get ) <EOL> prior = y_dist [ y_val ] / float ( len ( y ) ) <EOL> values , dist , splits = [ ] , [ ] , [ ] <EOL> for x_val in x_vals : <EOL> dist . append ( Counter ( y [ x == x_val ] ) ) <EOL> splits . append ( x_val ) <EOL> suma = sum ( [ prior * dist [ - <NUM_LIT:1> ] [ y_key ] for y_key in y_dist . keys ( ) ] ) <EOL> values . append ( prior * dist [ - <NUM_LIT:1> ] [ y_val ] / float ( suma ) ) <EOL> indices = np . array ( values ) . argsort ( ) [ : : - <NUM_LIT:1> ] <EOL> return np . array ( dist ) [ indices ] , np . array ( splits ) [ indices ] . tolist ( ) <EOL> def h ( values ) : <EOL> """<STR_LIT>""" <EOL> ent = np . true_divide ( values , np . sum ( values ) ) <EOL> return - np . sum ( np . multiply ( ent , np . log2 ( ent ) ) ) <EOL> def info_gain_nominal ( x , y , separate_max ) : <EOL> """<STR_LIT>""" <EOL> x_vals = np . unique ( x ) <EOL> if len ( x_vals ) < <NUM_LIT:3> : <EOL> return None <EOL> y_dist = Counter ( y ) <EOL> h_y = h ( y_dist . values ( ) ) <EOL> dist , splits = nominal_splits ( x , y , x_vals , y_dist , separate_max ) <EOL> indices , repeat = ( range ( <NUM_LIT:1> , len ( dist ) ) , <NUM_LIT:1> ) if len ( dist ) < <NUM_LIT:50> else ( range ( <NUM_LIT:1> , len ( dist ) , len ( dist ) / <NUM_LIT:10> ) , <NUM_LIT:3> ) <EOL> interval = len ( dist ) / <NUM_LIT:10> <EOL> max_ig , max_i , iteration = <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:0> <EOL> while iteration < repeat : <EOL> for i in indices : <EOL> dist0 = np . sum ( [ el for el in dist [ : i ] ] ) <EOL> dist1 = np . sum ( [ el for el in dist [ i : ] ] ) <EOL> coef = np . true_divide ( [ np . sum ( dist0 . values ( ) ) , np . sum ( dist1 . values ( ) ) ] , len ( y ) ) <EOL> ig = h_y - np . dot ( coef , [ h ( dist0 . values ( ) ) , h ( dist1 . values ( ) ) ] ) <EOL> if ig > max_ig : <EOL> max_ig , max_i = ig , i <EOL> iteration += <NUM_LIT:1> <EOL> if repeat > <NUM_LIT:1> : <EOL> interval = int ( interval * <NUM_LIT:0.5> ) <EOL> if max_i in indices and interval > <NUM_LIT:0> : <EOL> middle_index = indices . index ( max_i ) <EOL> else : <EOL> break <EOL> min_index = middle_index if middle_index == <NUM_LIT:0> else middle_index - <NUM_LIT:1> <EOL> max_index = middle_index if middle_index == len ( indices ) - <NUM_LIT:1> else middle_index + <NUM_LIT:1> <EOL> indices = range ( indices [ min_index ] , indices [ max_index ] , interval ) <EOL> return float ( max_ig ) , [ splits [ : max_i ] , splits [ max_i : ] ] <EOL> def info_gain_numeric ( x , y , accuracy ) : <EOL> x_unique = list ( np . unique ( x ) ) <EOL> if len ( x_unique ) == <NUM_LIT:1> : <EOL> return None <EOL> indices = x . argsort ( ) <EOL> x , y = x [ indices ] , y [ indices ] <EOL> right_dist = np . bincount ( y ) <EOL> dummy_class = np . array ( [ len ( right_dist ) ] ) <EOL> class_indices = right_dist . nonzero ( ) [ <NUM_LIT:0> ] <EOL> right_dist = right_dist [ class_indices ] <EOL> left_dist = np . zeros ( len ( class_indices ) ) <EOL> diffs = np . nonzero ( y [ : - <NUM_LIT:1> ] != y [ <NUM_LIT:1> : ] ) [ <NUM_LIT:0> ] + <NUM_LIT:1> <EOL> if accuracy > <NUM_LIT:0> : <EOL> diffs = np . array ( [ diffs [ i ] for i in range ( <NUM_LIT:1> , len ( diffs ) ) if diffs [ i ] - diffs [ i - <NUM_LIT:1> ] > accuracy ] , <EOL> dtype = np . int32 ) if len ( diffs ) > <NUM_LIT:15> else diffs <EOL> intervals = np . array ( ( np . concatenate ( ( [ <NUM_LIT:0> ] , diffs [ : - <NUM_LIT:1> ] ) ) , diffs ) ) . T <EOL> if len ( diffs ) < <NUM_LIT:2> : <EOL> return None <EOL> max_ig , max_i , max_j = <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> <EOL> prior_h = h ( right_dist ) <EOL> for i , j in intervals : <EOL> dist = np . bincount ( np . concatenate ( ( dummy_class , y [ i : j ] ) ) ) [ class_indices ] <EOL> left_dist += dist <EOL> right_dist -= dist <EOL> coef = np . true_divide ( ( np . sum ( left_dist ) , np . sum ( right_dist ) ) , len ( y ) ) <EOL> ig = prior_h - np . dot ( coef , [ h ( left_dist [ left_dist . nonzero ( ) ] ) , h ( right_dist [ right_dist . nonzero ( ) ] ) ] ) <EOL> if ig > max_ig : <EOL> max_ig , max_i , max_j = ig , i , j <EOL> if x [ max_i ] == x [ max_j ] : <EOL> ind = x_unique . index ( x [ max_i ] ) <EOL> mean = np . float32 ( np . mean ( ( x_unique [ <NUM_LIT:1> if ind == <NUM_LIT:0> else ind - <NUM_LIT:1> ] , x_unique [ ind ] ) ) ) <EOL> else : <EOL> mean = np . float32 ( np . mean ( ( x [ max_i ] , x [ max_j ] ) ) ) <EOL> return float ( max_ig ) , [ mean , mean ] <EOL> def multinomLog2 ( selectors ) : <EOL> """<STR_LIT>""" <EOL> ln2 = <NUM_LIT> <EOL> noAll = sum ( selectors ) <EOL> lgNf = math . lgamma ( noAll + <NUM_LIT:1.0> ) / ln2 <EOL> lgnFac = [ ] <EOL> for selector in selectors : <EOL> if selector == <NUM_LIT:0> or selector == <NUM_LIT:1> : <EOL> lgnFac . append ( <NUM_LIT:0.0> ) <EOL> elif selector == <NUM_LIT:2> : <EOL> lgnFac . append ( <NUM_LIT:1.0> ) <EOL> elif selector == noAll : <EOL> lgnFac . append ( lgNf ) <EOL> else : <EOL> lgnFac . append ( math . lgamma ( selector + <NUM_LIT:1.0> ) / ln2 ) <EOL> return lgNf - sum ( lgnFac ) <EOL> def calc_mdl ( yx_dist , y_dist ) : <EOL> """<STR_LIT>""" <EOL> prior = multinomLog2 ( y_dist . values ( ) ) <EOL> prior += multinomLog2 ( [ len ( y_dist . keys ( ) ) - <NUM_LIT:1> , sum ( y_dist . values ( ) ) ] ) <EOL> post = <NUM_LIT:0> <EOL> for x_val in yx_dist : <EOL> post += multinomLog2 ( [ x_val . get ( c , <NUM_LIT:0> ) for c in y_dist . keys ( ) ] ) <EOL> post += multinomLog2 ( [ len ( y_dist . keys ( ) ) - <NUM_LIT:1> , sum ( x_val . values ( ) ) ] ) <EOL> return ( prior - post ) / float ( sum ( y_dist . values ( ) ) ) <EOL> def mdl_nominal ( x , y , separate_max ) : <EOL> """<STR_LIT>""" <EOL> x_vals = np . unique ( x ) <EOL> if len ( x_vals ) == <NUM_LIT:1> : <EOL> return None <EOL> y_dist = Counter ( y ) <EOL> dist , splits = nominal_splits ( x , y , x_vals , y_dist , separate_max ) <EOL> prior_mdl = calc_mdl ( dist , y_dist ) <EOL> max_mdl , max_i = <NUM_LIT:0> , <NUM_LIT:1> <EOL> for i in range ( <NUM_LIT:1> , len ( dist ) ) : <EOL> dist0_x = [ el for el in dist [ : i ] ] <EOL> dist0_y = np . sum ( dist0_x ) <EOL> post_mdl0 = calc_mdl ( dist0_x , dist0_y ) <EOL> dist1_x = [ el for el in dist [ i : ] ] <EOL> dist1_y = np . sum ( dist1_x ) <EOL> post_mdl1 = calc_mdl ( dist1_x , dist1_y ) <EOL> coef = np . true_divide ( [ sum ( dist0_y . values ( ) ) , sum ( dist1_y . values ( ) ) ] , len ( x ) ) <EOL> mdl_val = prior_mdl - np . dot ( coef , [ post_mdl0 , post_mdl1 ] ) <EOL> if mdl_val > max_mdl : <EOL> max_mdl , max_i = mdl_val , i <EOL> split = [ splits [ : max_i ] , splits [ max_i : ] ] <EOL> return ( max_mdl , split ) <EOL> def mdl_numeric ( x , y , accuracy ) : <EOL> x_unique = list ( np . unique ( x ) ) <EOL> if len ( x_unique ) == <NUM_LIT:1> : <EOL> return None <EOL> indices = x . argsort ( ) <EOL> x , y = x [ indices ] , y [ indices ] <EOL> right_dist = np . bincount ( y ) <EOL> dummy_class = np . array ( [ len ( right_dist ) ] ) <EOL> class_indices = right_dist . nonzero ( ) [ <NUM_LIT:0> ] <EOL> right_dist = right_dist [ class_indices ] <EOL> left_dist = np . zeros ( len ( class_indices ) ) <EOL> y_dist = Counter ( dict ( zip ( class_indices , right_dist ) ) ) <EOL> diffs = np . nonzero ( y [ : - <NUM_LIT:1> ] != y [ <NUM_LIT:1> : ] ) [ <NUM_LIT:0> ] + <NUM_LIT:1> <EOL> if accuracy > <NUM_LIT:0> : <EOL> diffs = np . array ( [ diffs [ i ] for i in range ( <NUM_LIT:1> , len ( diffs ) ) if diffs [ i ] - diffs [ i - <NUM_LIT:1> ] > accuracy ] , <EOL> dtype = np . int32 ) if len ( diffs ) > <NUM_LIT:15> else diffs <EOL> intervals = np . array ( ( np . concatenate ( ( [ <NUM_LIT:0> ] , diffs [ : - <NUM_LIT:1> ] ) ) , diffs ) ) . T <EOL> dist = [ Counter ( dict ( zip ( class_indices , np . bincount ( np . concatenate ( ( dummy_class , y [ i : j ] ) ) ) [ class_indices ] ) ) ) for <EOL> i , j in intervals ] <EOL> prior_mdl = calc_mdl ( dist , y_dist ) <EOL> max_mdl , max_i = <NUM_LIT:0> , <NUM_LIT:0> <EOL> for i in range ( <NUM_LIT:1> , len ( dist ) ) : <EOL> dist0_x = dist [ : i ] <EOL> dist0_y = np . sum ( dist0_x ) <EOL> post_mdl0 = calc_mdl ( dist0_x , dist0_y ) <EOL> dist1_x = dist [ i : ] <EOL> dist1_y = np . sum ( dist1_x ) <EOL> post_mdl1 = calc_mdl ( dist1_x , dist1_y ) <EOL> coef = np . true_divide ( [ sum ( dist0_y . values ( ) ) , sum ( dist1_y . values ( ) ) ] , len ( x ) ) <EOL> mdl_val = prior_mdl - np . dot ( coef , [ post_mdl0 , post_mdl1 ] ) <EOL> if mdl_val > max_mdl : <EOL> max_mdl , max_i = mdl_val , i <EOL> max_i , max_j = intervals [ max_i ] <EOL> if x [ max_i ] == x [ max_j ] : <EOL> ind = x_unique . index ( x [ max_i ] ) <EOL> mean = np . mean ( ( x [ <NUM_LIT:1> if ind == <NUM_LIT:0> else ind - <NUM_LIT:1> ] , x [ ind ] ) ) <EOL> else : <EOL> mean = np . mean ( ( x [ max_i ] , x [ max_j ] ) ) <EOL> return ( max_mdl , [ mean , mean ] ) </s>
