<s> from numpy import * <EOL> from itertools import combinations <EOL> class ClusterNode ( object ) : <EOL> def __init__ ( self , vec , left , right , distance = <NUM_LIT:0.0> , count = <NUM_LIT:1> ) : <EOL> self . left = left <EOL> self . right = right <EOL> self . vec = vec <EOL> self . distance = distance <EOL> self . count = count <EOL> def extract_clusters ( self , dist ) : <EOL> """<STR_LIT>""" <EOL> if self . distance < dist : <EOL> return [ self ] <EOL> return self . left . extract_clusters ( dist ) + self . right . extract_clusters ( dist ) <EOL> def get_cluster_elements ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . left . get_cluster_elements ( ) + self . right . get_cluster_elements ( ) <EOL> def get_height ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . left . get_height ( ) + self . right . get_height ( ) <EOL> def get_depth ( self ) : <EOL> """<STR_LIT>""" <EOL> return max ( self . left . get_depth ( ) , self . right . get_depth ( ) ) + self . distance <EOL> def draw ( self , draw , x , y , s , imlist , im ) : <EOL> """<STR_LIT>""" <EOL> h1 = int ( self . left . get_height ( ) * <NUM_LIT:20> / <NUM_LIT:2> ) <EOL> h2 = int ( self . right . get_height ( ) * <NUM_LIT:20> / <NUM_LIT:2> ) <EOL> top = y - ( h1 + h2 ) <EOL> bottom = y + ( h1 + h2 ) <EOL> draw . line ( ( x , top + h1 , x , bottom - h2 ) , fill = ( <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ) ) <EOL> ll = self . distance * s <EOL> draw . line ( ( x , top + h1 , x + ll , top + h1 ) , fill = ( <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ) ) <EOL> draw . line ( ( x , bottom - h2 , x + ll , bottom - h2 ) , fill = ( <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ) ) <EOL> self . left . draw ( draw , x + ll , top + h1 , s , imlist , im ) <EOL> self . right . draw ( draw , x + ll , bottom - h2 , s , imlist , im ) <EOL> class ClusterLeafNode ( object ) : <EOL> def __init__ ( self , vec , id ) : <EOL> self . vec = vec <EOL> self . id = id <EOL> def extract_clusters ( self , dist ) : <EOL> return [ self ] <EOL> def get_cluster_elements ( self ) : <EOL> return [ self . id ] <EOL> def get_height ( self ) : <EOL> return <NUM_LIT:1> <EOL> def get_depth ( self ) : <EOL> return <NUM_LIT:0> <EOL> def draw ( self , draw , x , y , s , imlist , im ) : <EOL> nodeim = Image . open ( imlist [ self . id ] ) <EOL> nodeim . thumbnail ( [ <NUM_LIT:20> , <NUM_LIT:20> ] ) <EOL> ns = nodeim . size <EOL> im . paste ( nodeim , [ int ( x ) , int ( y - ns [ <NUM_LIT:1> ] // <NUM_LIT:2> ) , int ( x + ns [ <NUM_LIT:0> ] ) , int ( y + ns [ <NUM_LIT:1> ] - ns [ <NUM_LIT:1> ] // <NUM_LIT:2> ) ] ) <EOL> def L2dist ( v1 , v2 ) : <EOL> return sqrt ( sum ( ( v1 - v2 ) ** <NUM_LIT:2> ) ) <EOL> def L1dist ( v1 , v2 ) : <EOL> return sum ( abs ( v1 - v2 ) ) <EOL> def hcluster ( features , distfcn = L2dist ) : <EOL> """<STR_LIT>""" <EOL> distances = { } <EOL> node = [ ClusterLeafNode ( array ( f ) , id = i ) for i , f in enumerate ( features ) ] <EOL> while len ( node ) > <NUM_LIT:1> : <EOL> closest = float ( '<STR_LIT>' ) <EOL> for ni , nj in combinations ( node , <NUM_LIT:2> ) : <EOL> if ( ni , nj ) not in distances : <EOL> distances [ ni , nj ] = distfcn ( ni . vec , nj . vec ) <EOL> d = distances [ ni , nj ] <EOL> if d < closest : <EOL> closest = d <EOL> lowestpair = ( ni , nj ) <EOL> ni , nj = lowestpair <EOL> new_vec = ( ni . vec + nj . vec ) / <NUM_LIT> <EOL> new_node = ClusterNode ( new_vec , left = ni , right = nj , distance = closest ) <EOL> node . remove ( ni ) <EOL> node . remove ( nj ) <EOL> node . append ( new_node ) <EOL> return node [ <NUM_LIT:0> ] <EOL> from PIL import Image , ImageDraw <EOL> def draw_dendrogram ( node , imlist , filename = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> rows = node . get_height ( ) * <NUM_LIT:20> <EOL> cols = <NUM_LIT> <EOL> s = float ( cols - <NUM_LIT> ) / node . get_depth ( ) <EOL> im = Image . new ( '<STR_LIT>' , ( cols , rows ) , ( <NUM_LIT:255> , <NUM_LIT:255> , <NUM_LIT:255> ) ) <EOL> draw = ImageDraw . Draw ( im ) <EOL> draw . line ( ( <NUM_LIT:0> , rows / <NUM_LIT:2> , <NUM_LIT:20> , rows / <NUM_LIT:2> ) , fill = ( <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ) ) <EOL> node . draw ( draw , <NUM_LIT:20> , ( rows / <NUM_LIT:2> ) , s , imlist , im ) <EOL> im . save ( filename ) <EOL> im . show ( ) </s>
