<s> """<STR_LIT>""" <EOL> from collections import defaultdict <EOL> import numpy as np <EOL> from scipy import sparse <EOL> from sklearn . base import BaseEstimator , ClusterMixin <EOL> from sklearn . utils . validation import check_array <EOL> def get_max_value_key ( dic ) : <EOL> """<STR_LIT>""" <EOL> v = list ( dic . values ( ) ) <EOL> k = list ( dic . keys ( ) ) <EOL> return k [ v . index ( max ( v ) ) ] <EOL> def matching_dissim ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return np . sum ( a != b , axis = <NUM_LIT:1> ) <EOL> def init_huang ( X , n_clusters ) : <EOL> """<STR_LIT>""" <EOL> nattrs = X . shape [ <NUM_LIT:1> ] <EOL> centroids = np . empty ( ( n_clusters , nattrs ) , dtype = '<STR_LIT:object>' ) <EOL> for iattr in range ( nattrs ) : <EOL> freq = defaultdict ( int ) <EOL> for curattr in X [ : , iattr ] : <EOL> freq [ curattr ] += <NUM_LIT:1> <EOL> choices = [ chc for chc , wght in freq . items ( ) for _ in range ( wght ) ] <EOL> centroids [ : , iattr ] = np . random . choice ( choices , n_clusters ) <EOL> for ik in range ( n_clusters ) : <EOL> ndx = np . argsort ( matching_dissim ( X , centroids [ ik ] ) ) <EOL> while np . all ( X [ ndx [ <NUM_LIT:0> ] ] == centroids , axis = <NUM_LIT:1> ) . any ( ) : <EOL> ndx = np . delete ( ndx , <NUM_LIT:0> ) <EOL> centroids [ ik ] = X [ ndx [ <NUM_LIT:0> ] ] <EOL> return centroids <EOL> def init_cao ( X , n_clusters ) : <EOL> """<STR_LIT>""" <EOL> npoints , nattrs = X . shape <EOL> centroids = np . empty ( ( n_clusters , nattrs ) , dtype = '<STR_LIT:object>' ) <EOL> dens = np . zeros ( npoints ) <EOL> for iattr in range ( nattrs ) : <EOL> freq = defaultdict ( int ) <EOL> for val in X [ : , iattr ] : <EOL> freq [ val ] += <NUM_LIT:1> <EOL> for ipoint in range ( npoints ) : <EOL> dens [ ipoint ] += freq [ X [ ipoint , iattr ] ] / float ( nattrs ) <EOL> dens /= npoints <EOL> centroids [ <NUM_LIT:0> ] = X [ np . argmax ( dens ) ] <EOL> if n_clusters > <NUM_LIT:1> : <EOL> for ik in range ( <NUM_LIT:1> , n_clusters ) : <EOL> dd = np . empty ( ( ik , npoints ) ) <EOL> for ikk in range ( ik ) : <EOL> dd [ ikk ] = matching_dissim ( X , centroids [ ikk ] ) * dens <EOL> centroids [ ik ] = X [ np . argmax ( np . min ( dd , axis = <NUM_LIT:0> ) ) ] <EOL> return centroids <EOL> def move_point_cat ( point , ipoint , to_clust , from_clust , cl_attr_freq , membship ) : <EOL> """<STR_LIT>""" <EOL> membship [ to_clust , ipoint ] = <NUM_LIT:1> <EOL> membship [ from_clust , ipoint ] = <NUM_LIT:0> <EOL> for iattr , curattr in enumerate ( point ) : <EOL> cl_attr_freq [ to_clust ] [ iattr ] [ curattr ] += <NUM_LIT:1> <EOL> cl_attr_freq [ from_clust ] [ iattr ] [ curattr ] -= <NUM_LIT:1> <EOL> return cl_attr_freq , membship <EOL> def encode_features ( X , enc_map = None ) : <EOL> """<STR_LIT>""" <EOL> if np . issubdtype ( X . dtype , np . integer ) : <EOL> return X , enc_map <EOL> if enc_map is None : <EOL> fit = True <EOL> enc_map = [ ] <EOL> else : <EOL> fit = False <EOL> Xenc = np . zeros ( X . shape ) . astype ( '<STR_LIT:int>' ) <EOL> for ii in range ( X . shape [ <NUM_LIT:1> ] ) : <EOL> if fit : <EOL> enc_map . append ( { val : jj for jj , val in enumerate ( np . unique ( X [ : , ii ] ) ) } ) <EOL> Xenc [ : , ii ] = np . array ( [ enc_map [ ii ] . get ( x , - <NUM_LIT:1> ) for x in X [ : , ii ] ] ) <EOL> return Xenc , enc_map <EOL> def _labels_cost ( X , centroids ) : <EOL> """<STR_LIT>""" <EOL> X = check_array ( X ) <EOL> npoints = X . shape [ <NUM_LIT:0> ] <EOL> cost = <NUM_LIT:0.> <EOL> labels = np . empty ( npoints , dtype = np . uint8 ) <EOL> for ipoint , curpoint in enumerate ( X ) : <EOL> diss = matching_dissim ( centroids , curpoint ) <EOL> clust = np . argmin ( diss ) <EOL> labels [ ipoint ] = clust <EOL> cost += diss [ clust ] <EOL> return labels , cost <EOL> def _k_modes_iter ( X , centroids , cl_attr_freq , membship ) : <EOL> """<STR_LIT>""" <EOL> moves = <NUM_LIT:0> <EOL> for ipoint , curpoint in enumerate ( X ) : <EOL> clust = np . argmin ( matching_dissim ( centroids , curpoint ) ) <EOL> if membship [ clust , ipoint ] : <EOL> continue <EOL> moves += <NUM_LIT:1> <EOL> old_clust = np . argwhere ( membship [ : , ipoint ] ) [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] <EOL> cl_attr_freq , membship = move_point_cat ( <EOL> curpoint , ipoint , clust , old_clust , cl_attr_freq , membship <EOL> ) <EOL> for iattr in range ( len ( curpoint ) ) : <EOL> for curc in ( clust , old_clust ) : <EOL> centroids [ curc , iattr ] = get_max_value_key ( cl_attr_freq [ curc ] [ iattr ] ) <EOL> if sum ( membship [ old_clust , : ] ) == <NUM_LIT:0> : <EOL> from_clust = membship . sum ( axis = <NUM_LIT:1> ) . argmax ( ) <EOL> choices = [ ii for ii , ch in enumerate ( membship [ from_clust , : ] ) if ch ] <EOL> rindx = np . random . choice ( choices ) <EOL> cl_attr_freq , membship = move_point_cat ( <EOL> X [ rindx ] , rindx , old_clust , from_clust , cl_attr_freq , membship <EOL> ) <EOL> return centroids , moves <EOL> def k_modes ( X , n_clusters , init , n_init , max_iter , verbose ) : <EOL> """<STR_LIT>""" <EOL> if sparse . issparse ( X ) : <EOL> raise TypeError ( "<STR_LIT>" ) <EOL> X = check_array ( X , dtype = None ) <EOL> X , enc_map = encode_features ( X ) <EOL> npoints , nattrs = X . shape <EOL> assert n_clusters < npoints , "<STR_LIT>" <EOL> all_centroids = [ ] <EOL> all_labels = [ ] <EOL> all_costs = [ ] <EOL> all_n_iters = [ ] <EOL> for init_no in range ( n_init ) : <EOL> if verbose : <EOL> print ( "<STR_LIT>" ) <EOL> if isinstance ( init , str ) and init == '<STR_LIT>' : <EOL> centroids = init_huang ( X , n_clusters ) <EOL> elif isinstance ( init , str ) and init == '<STR_LIT>' : <EOL> centroids = init_cao ( X , n_clusters ) <EOL> elif isinstance ( init , str ) and init == '<STR_LIT>' : <EOL> seeds = np . random . choice ( range ( npoints ) , n_clusters ) <EOL> centroids = X [ seeds ] <EOL> elif hasattr ( init , '<STR_LIT>' ) : <EOL> assert init . shape [ <NUM_LIT:0> ] == n_clusters , "<STR_LIT>" <EOL> assert init . shape [ <NUM_LIT:1> ] == nattrs , "<STR_LIT>" <EOL> centroids = np . asarray ( init , dtype = np . uint8 ) <EOL> else : <EOL> raise NotImplementedError <EOL> if verbose : <EOL> print ( "<STR_LIT>" ) <EOL> membship = np . zeros ( ( n_clusters , npoints ) , dtype = np . uint8 ) <EOL> cl_attr_freq = [ [ defaultdict ( int ) for _ in range ( nattrs ) ] <EOL> for _ in range ( n_clusters ) ] <EOL> for ipoint , curpoint in enumerate ( X ) : <EOL> clust = np . argmin ( matching_dissim ( centroids , curpoint ) ) <EOL> membship [ clust , ipoint ] = <NUM_LIT:1> <EOL> for iattr , curattr in enumerate ( curpoint ) : <EOL> cl_attr_freq [ clust ] [ iattr ] [ curattr ] += <NUM_LIT:1> <EOL> for ik in range ( n_clusters ) : <EOL> for iattr in range ( nattrs ) : <EOL> if sum ( membship [ ik ] ) == <NUM_LIT:0> : <EOL> centroids [ ik , iattr ] = np . random . choice ( X [ : , iattr ] ) <EOL> else : <EOL> centroids [ ik , iattr ] = get_max_value_key ( cl_attr_freq [ ik ] [ iattr ] ) <EOL> if verbose : <EOL> print ( "<STR_LIT>" ) <EOL> itr = <NUM_LIT:0> <EOL> converged = False <EOL> cost = np . Inf <EOL> while itr <= max_iter and not converged : <EOL> itr += <NUM_LIT:1> <EOL> centroids , moves = _k_modes_iter ( X , centroids , cl_attr_freq , membship ) <EOL> labels , ncost = _labels_cost ( X , centroids ) <EOL> converged = ( moves == <NUM_LIT:0> ) or ( ncost >= cost ) <EOL> cost = ncost <EOL> if verbose : <EOL> print ( "<STR_LIT>" <EOL> . format ( init_no + <NUM_LIT:1> , itr , max_iter , moves , cost ) ) <EOL> all_centroids . append ( centroids ) <EOL> all_labels . append ( labels ) <EOL> all_costs . append ( cost ) <EOL> all_n_iters . append ( itr ) <EOL> best = np . argmin ( all_costs ) <EOL> if n_init > <NUM_LIT:1> and verbose : <EOL> print ( "<STR_LIT>" . format ( best + <NUM_LIT:1> ) ) <EOL> return all_centroids [ best ] , all_labels [ best ] , all_costs [ best ] , all_n_iters [ best ] , enc_map <EOL> class KModes ( BaseEstimator , ClusterMixin ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , n_clusters = <NUM_LIT:8> , init = '<STR_LIT>' , n_init = <NUM_LIT:1> , max_iter = <NUM_LIT:100> , verbose = <NUM_LIT:0> ) : <EOL> self . n_clusters = n_clusters <EOL> self . init = init <EOL> self . n_init = n_init <EOL> self . verbose = verbose <EOL> if ( ( isinstance ( self . init , str ) and self . init == '<STR_LIT>' ) or <EOL> hasattr ( self . init , '<STR_LIT>' ) ) and self . n_init > <NUM_LIT:1> : <EOL> if self . verbose : <EOL> print ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> self . n_init = <NUM_LIT:1> <EOL> self . max_iter = max_iter <EOL> def fit ( self , X , y = None , ** kwargs ) : <EOL> """<STR_LIT>""" <EOL> self . cluster_centroids_ , self . labels_ , self . cost_ , self . n_iter_ , self . enc_map_ = k_modes ( X , <EOL> self . n_clusters , <EOL> self . init , <EOL> self . n_init , <EOL> self . max_iter , <EOL> self . verbose ) <EOL> return self <EOL> def fit_predict ( self , X , y = None , ** kwargs ) : <EOL> """<STR_LIT>""" <EOL> return self . fit ( X , ** kwargs ) . labels_ <EOL> def predict ( self , X , ** kwargs ) : <EOL> """<STR_LIT>""" <EOL> assert hasattr ( self , '<STR_LIT>' ) , "<STR_LIT>" <EOL> X = check_array ( X , dtype = None ) <EOL> X , _ = encode_features ( X , enc_map = self . enc_map_ ) <EOL> return _labels_cost ( X , self . cluster_centroids_ ) [ <NUM_LIT:0> ] </s>
