<s> """<STR_LIT>""" <EOL> import warnings <EOL> from abc import ABCMeta , abstractmethod <EOL> import numpy as np <EOL> from scipy . sparse import csr_matrix , issparse <EOL> from . ball_tree import BallTree <EOL> from . kd_tree import KDTree <EOL> from . . base import BaseEstimator <EOL> from . . metrics import pairwise_distances <EOL> from . . metrics . pairwise import PAIRWISE_DISTANCE_FUNCTIONS <EOL> from . . utils import check_X_y , check_array , _get_n_jobs , gen_even_slices <EOL> from . . utils . fixes import argpartition <EOL> from . . utils . multiclass import check_classification_targets <EOL> from . . externals import six <EOL> from . . externals . joblib import Parallel , delayed <EOL> from . . exceptions import NotFittedError <EOL> from . . exceptions import DataConversionWarning <EOL> VALID_METRICS = dict ( ball_tree = BallTree . valid_metrics , <EOL> kd_tree = KDTree . valid_metrics , <EOL> brute = ( list ( PAIRWISE_DISTANCE_FUNCTIONS . keys ( ) ) + <EOL> [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' ] ) ) <EOL> VALID_METRICS_SPARSE = dict ( ball_tree = [ ] , <EOL> kd_tree = [ ] , <EOL> brute = PAIRWISE_DISTANCE_FUNCTIONS . keys ( ) ) <EOL> def _check_weights ( weights ) : <EOL> """<STR_LIT>""" <EOL> if weights in ( None , '<STR_LIT>' , '<STR_LIT>' ) : <EOL> return weights <EOL> elif callable ( weights ) : <EOL> return weights <EOL> else : <EOL> raise ValueError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> def _get_weights ( dist , weights ) : <EOL> """<STR_LIT>""" <EOL> if weights in ( None , '<STR_LIT>' ) : <EOL> return None <EOL> elif weights == '<STR_LIT>' : <EOL> if dist . dtype is np . dtype ( object ) : <EOL> for point_dist_i , point_dist in enumerate ( dist ) : <EOL> if hasattr ( point_dist , '<STR_LIT>' ) and <NUM_LIT:0.> in point_dist : <EOL> dist [ point_dist_i ] = point_dist == <NUM_LIT:0.> <EOL> else : <EOL> dist [ point_dist_i ] = <NUM_LIT:1.> / point_dist <EOL> else : <EOL> with np . errstate ( divide = '<STR_LIT:ignore>' ) : <EOL> dist = <NUM_LIT:1.> / dist <EOL> inf_mask = np . isinf ( dist ) <EOL> inf_row = np . any ( inf_mask , axis = <NUM_LIT:1> ) <EOL> dist [ inf_row ] = inf_mask [ inf_row ] <EOL> return dist <EOL> elif callable ( weights ) : <EOL> return weights ( dist ) <EOL> else : <EOL> raise ValueError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> class NeighborsBase ( six . with_metaclass ( ABCMeta , BaseEstimator ) ) : <EOL> """<STR_LIT>""" <EOL> @ abstractmethod <EOL> def __init__ ( self ) : <EOL> pass <EOL> def _init_params ( self , n_neighbors = None , radius = None , <EOL> algorithm = '<STR_LIT>' , leaf_size = <NUM_LIT:30> , metric = '<STR_LIT>' , <EOL> p = <NUM_LIT:2> , metric_params = None , n_jobs = <NUM_LIT:1> ) : <EOL> self . n_neighbors = n_neighbors <EOL> self . radius = radius <EOL> self . algorithm = algorithm <EOL> self . leaf_size = leaf_size <EOL> self . metric = metric <EOL> self . metric_params = metric_params <EOL> self . p = p <EOL> self . n_jobs = n_jobs <EOL> if algorithm not in [ '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' ] : <EOL> raise ValueError ( "<STR_LIT>" % algorithm ) <EOL> if algorithm == '<STR_LIT>' : <EOL> if metric == '<STR_LIT>' : <EOL> alg_check = '<STR_LIT>' <EOL> else : <EOL> alg_check = '<STR_LIT>' <EOL> else : <EOL> alg_check = algorithm <EOL> if callable ( metric ) : <EOL> if algorithm == '<STR_LIT>' : <EOL> raise ValueError ( <EOL> "<STR_LIT>" <EOL> % metric ) <EOL> elif metric not in VALID_METRICS [ alg_check ] : <EOL> raise ValueError ( "<STR_LIT>" <EOL> % ( metric , algorithm ) ) <EOL> if self . metric_params is not None and '<STR_LIT:p>' in self . metric_params : <EOL> warnings . warn ( "<STR_LIT>" <EOL> "<STR_LIT>" <EOL> "<STR_LIT>" , SyntaxWarning , stacklevel = <NUM_LIT:3> ) <EOL> effective_p = metric_params [ '<STR_LIT:p>' ] <EOL> else : <EOL> effective_p = self . p <EOL> if self . metric in [ '<STR_LIT>' , '<STR_LIT>' ] and effective_p < <NUM_LIT:1> : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> self . _fit_X = None <EOL> self . _tree = None <EOL> self . _fit_method = None <EOL> def _fit ( self , X ) : <EOL> if self . metric_params is None : <EOL> self . effective_metric_params_ = { } <EOL> else : <EOL> self . effective_metric_params_ = self . metric_params . copy ( ) <EOL> effective_p = self . effective_metric_params_ . get ( '<STR_LIT:p>' , self . p ) <EOL> if self . metric in [ '<STR_LIT>' , '<STR_LIT>' ] : <EOL> self . effective_metric_params_ [ '<STR_LIT:p>' ] = effective_p <EOL> self . effective_metric_ = self . metric <EOL> if self . metric == '<STR_LIT>' : <EOL> p = self . effective_metric_params_ . pop ( '<STR_LIT:p>' , <NUM_LIT:2> ) <EOL> if p < <NUM_LIT:1> : <EOL> raise ValueError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> elif p == <NUM_LIT:1> : <EOL> self . effective_metric_ = '<STR_LIT>' <EOL> elif p == <NUM_LIT:2> : <EOL> self . effective_metric_ = '<STR_LIT>' <EOL> elif p == np . inf : <EOL> self . effective_metric_ = '<STR_LIT>' <EOL> else : <EOL> self . effective_metric_params_ [ '<STR_LIT:p>' ] = p <EOL> if isinstance ( X , NeighborsBase ) : <EOL> self . _fit_X = X . _fit_X <EOL> self . _tree = X . _tree <EOL> self . _fit_method = X . _fit_method <EOL> return self <EOL> elif isinstance ( X , BallTree ) : <EOL> self . _fit_X = X . data <EOL> self . _tree = X <EOL> self . _fit_method = '<STR_LIT>' <EOL> return self <EOL> elif isinstance ( X , KDTree ) : <EOL> self . _fit_X = X . data <EOL> self . _tree = X <EOL> self . _fit_method = '<STR_LIT>' <EOL> return self <EOL> X = check_array ( X , accept_sparse = '<STR_LIT>' ) <EOL> n_samples = X . shape [ <NUM_LIT:0> ] <EOL> if n_samples == <NUM_LIT:0> : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> if issparse ( X ) : <EOL> if self . algorithm not in ( '<STR_LIT>' , '<STR_LIT>' ) : <EOL> warnings . warn ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> if self . effective_metric_ not in VALID_METRICS_SPARSE [ '<STR_LIT>' ] : <EOL> raise ValueError ( "<STR_LIT>" <EOL> % self . effective_metric_ ) <EOL> self . _fit_X = X . copy ( ) <EOL> self . _tree = None <EOL> self . _fit_method = '<STR_LIT>' <EOL> return self <EOL> self . _fit_method = self . algorithm <EOL> self . _fit_X = X <EOL> if self . _fit_method == '<STR_LIT>' : <EOL> if ( ( self . n_neighbors is None or <EOL> self . n_neighbors < self . _fit_X . shape [ <NUM_LIT:0> ] // <NUM_LIT:2> ) and <EOL> self . metric != '<STR_LIT>' ) : <EOL> if self . effective_metric_ in VALID_METRICS [ '<STR_LIT>' ] : <EOL> self . _fit_method = '<STR_LIT>' <EOL> else : <EOL> self . _fit_method = '<STR_LIT>' <EOL> else : <EOL> self . _fit_method = '<STR_LIT>' <EOL> if self . _fit_method == '<STR_LIT>' : <EOL> self . _tree = BallTree ( X , self . leaf_size , <EOL> metric = self . effective_metric_ , <EOL> ** self . effective_metric_params_ ) <EOL> elif self . _fit_method == '<STR_LIT>' : <EOL> self . _tree = KDTree ( X , self . leaf_size , <EOL> metric = self . effective_metric_ , <EOL> ** self . effective_metric_params_ ) <EOL> elif self . _fit_method == '<STR_LIT>' : <EOL> self . _tree = None <EOL> else : <EOL> raise ValueError ( "<STR_LIT>" <EOL> % self . algorithm ) <EOL> if self . n_neighbors is not None : <EOL> if self . n_neighbors <= <NUM_LIT:0> : <EOL> raise ValueError ( <EOL> "<STR_LIT>" % <EOL> self . n_neighbors <EOL> ) <EOL> return self <EOL> @ property <EOL> def _pairwise ( self ) : <EOL> return self . metric == '<STR_LIT>' <EOL> class KNeighborsMixin ( object ) : <EOL> """<STR_LIT>""" <EOL> def kneighbors ( self , X = None , n_neighbors = None , return_distance = True ) : <EOL> """<STR_LIT>""" <EOL> if self . _fit_method is None : <EOL> raise NotFittedError ( "<STR_LIT>" ) <EOL> if n_neighbors is None : <EOL> n_neighbors = self . n_neighbors <EOL> if X is not None : <EOL> query_is_train = False <EOL> X = check_array ( X , accept_sparse = '<STR_LIT>' ) <EOL> else : <EOL> query_is_train = True <EOL> X = self . _fit_X <EOL> n_neighbors += <NUM_LIT:1> <EOL> train_size = self . _fit_X . shape [ <NUM_LIT:0> ] <EOL> if n_neighbors > train_size : <EOL> raise ValueError ( <EOL> "<STR_LIT>" <EOL> "<STR_LIT>" % <EOL> ( train_size , n_neighbors ) <EOL> ) <EOL> n_samples , _ = X . shape <EOL> sample_range = np . arange ( n_samples ) [ : , None ] <EOL> n_jobs = _get_n_jobs ( self . n_jobs ) <EOL> if self . _fit_method == '<STR_LIT>' : <EOL> if self . effective_metric_ == '<STR_LIT>' : <EOL> dist = pairwise_distances ( X , self . _fit_X , '<STR_LIT>' , <EOL> n_jobs = n_jobs , squared = True ) <EOL> else : <EOL> dist = pairwise_distances ( <EOL> X , self . _fit_X , self . effective_metric_ , n_jobs = n_jobs , <EOL> ** self . effective_metric_params_ ) <EOL> neigh_ind = argpartition ( dist , n_neighbors - <NUM_LIT:1> , axis = <NUM_LIT:1> ) <EOL> neigh_ind = neigh_ind [ : , : n_neighbors ] <EOL> neigh_ind = neigh_ind [ <EOL> sample_range , np . argsort ( dist [ sample_range , neigh_ind ] ) ] <EOL> if return_distance : <EOL> if self . effective_metric_ == '<STR_LIT>' : <EOL> result = np . sqrt ( dist [ sample_range , neigh_ind ] ) , neigh_ind <EOL> else : <EOL> result = dist [ sample_range , neigh_ind ] , neigh_ind <EOL> else : <EOL> result = neigh_ind <EOL> elif self . _fit_method in [ '<STR_LIT>' , '<STR_LIT>' ] : <EOL> if issparse ( X ) : <EOL> raise ValueError ( <EOL> "<STR_LIT>" <EOL> "<STR_LIT>" % self . _fit_method ) <EOL> result = Parallel ( n_jobs , backend = '<STR_LIT>' ) ( <EOL> delayed ( self . _tree . query , check_pickle = False ) ( <EOL> X [ s ] , n_neighbors , return_distance ) <EOL> for s in gen_even_slices ( X . shape [ <NUM_LIT:0> ] , n_jobs ) <EOL> ) <EOL> if return_distance : <EOL> dist , neigh_ind = tuple ( zip ( * result ) ) <EOL> result = np . vstack ( dist ) , np . vstack ( neigh_ind ) <EOL> else : <EOL> result = np . vstack ( result ) <EOL> else : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> if not query_is_train : <EOL> return result <EOL> else : <EOL> if return_distance : <EOL> dist , neigh_ind = result <EOL> else : <EOL> neigh_ind = result <EOL> sample_mask = neigh_ind != sample_range <EOL> dup_gr_nbrs = np . all ( sample_mask , axis = <NUM_LIT:1> ) <EOL> sample_mask [ : , <NUM_LIT:0> ] [ dup_gr_nbrs ] = False <EOL> neigh_ind = np . reshape ( <EOL> neigh_ind [ sample_mask ] , ( n_samples , n_neighbors - <NUM_LIT:1> ) ) <EOL> if return_distance : <EOL> dist = np . reshape ( <EOL> dist [ sample_mask ] , ( n_samples , n_neighbors - <NUM_LIT:1> ) ) <EOL> return dist , neigh_ind <EOL> return neigh_ind <EOL> def kneighbors_graph ( self , X = None , n_neighbors = None , <EOL> mode = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> if n_neighbors is None : <EOL> n_neighbors = self . n_neighbors <EOL> if X is not None : <EOL> X = check_array ( X , accept_sparse = '<STR_LIT>' ) <EOL> n_samples1 = X . shape [ <NUM_LIT:0> ] <EOL> else : <EOL> n_samples1 = self . _fit_X . shape [ <NUM_LIT:0> ] <EOL> n_samples2 = self . _fit_X . shape [ <NUM_LIT:0> ] <EOL> n_nonzero = n_samples1 * n_neighbors <EOL> A_indptr = np . arange ( <NUM_LIT:0> , n_nonzero + <NUM_LIT:1> , n_neighbors ) <EOL> if mode == '<STR_LIT>' : <EOL> A_data = np . ones ( n_samples1 * n_neighbors ) <EOL> A_ind = self . kneighbors ( X , n_neighbors , return_distance = False ) <EOL> elif mode == '<STR_LIT>' : <EOL> A_data , A_ind = self . kneighbors ( <EOL> X , n_neighbors , return_distance = True ) <EOL> A_data = np . ravel ( A_data ) <EOL> else : <EOL> raise ValueError ( <EOL> '<STR_LIT>' <EOL> '<STR_LIT>' % mode ) <EOL> kneighbors_graph = csr_matrix ( ( A_data , A_ind . ravel ( ) , A_indptr ) , <EOL> shape = ( n_samples1 , n_samples2 ) ) <EOL> return kneighbors_graph <EOL> class RadiusNeighborsMixin ( object ) : <EOL> """<STR_LIT>""" <EOL> def radius_neighbors ( self , X = None , radius = None , return_distance = True ) : <EOL> """<STR_LIT>""" <EOL> if self . _fit_method is None : <EOL> raise NotFittedError ( "<STR_LIT>" ) <EOL> if X is not None : <EOL> query_is_train = False <EOL> X = check_array ( X , accept_sparse = '<STR_LIT>' ) <EOL> else : <EOL> query_is_train = True <EOL> X = self . _fit_X <EOL> if radius is None : <EOL> radius = self . radius <EOL> n_samples = X . shape [ <NUM_LIT:0> ] <EOL> if self . _fit_method == '<STR_LIT>' : <EOL> if self . effective_metric_ == '<STR_LIT>' : <EOL> dist = pairwise_distances ( X , self . _fit_X , '<STR_LIT>' , <EOL> squared = True ) <EOL> radius *= radius <EOL> else : <EOL> dist = pairwise_distances ( X , self . _fit_X , <EOL> self . effective_metric_ , <EOL> ** self . effective_metric_params_ ) <EOL> neigh_ind_list = [ np . where ( d <= radius ) [ <NUM_LIT:0> ] for d in dist ] <EOL> neigh_ind = np . empty ( n_samples , dtype = '<STR_LIT:object>' ) <EOL> neigh_ind [ : ] = neigh_ind_list <EOL> if return_distance : <EOL> dist_array = np . empty ( n_samples , dtype = '<STR_LIT:object>' ) <EOL> if self . effective_metric_ == '<STR_LIT>' : <EOL> dist_list = [ np . sqrt ( d [ neigh_ind [ i ] ] ) <EOL> for i , d in enumerate ( dist ) ] <EOL> else : <EOL> dist_list = [ d [ neigh_ind [ i ] ] <EOL> for i , d in enumerate ( dist ) ] <EOL> dist_array [ : ] = dist_list <EOL> results = dist_array , neigh_ind <EOL> else : <EOL> results = neigh_ind <EOL> elif self . _fit_method in [ '<STR_LIT>' , '<STR_LIT>' ] : <EOL> if issparse ( X ) : <EOL> raise ValueError ( <EOL> "<STR_LIT>" <EOL> "<STR_LIT>" % self . _fit_method ) <EOL> results = self . _tree . query_radius ( X , radius , <EOL> return_distance = return_distance ) <EOL> if return_distance : <EOL> results = results [ : : - <NUM_LIT:1> ] <EOL> else : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> if not query_is_train : <EOL> return results <EOL> else : <EOL> if return_distance : <EOL> dist , neigh_ind = results <EOL> else : <EOL> neigh_ind = results <EOL> for ind , ind_neighbor in enumerate ( neigh_ind ) : <EOL> mask = ind_neighbor != ind <EOL> neigh_ind [ ind ] = ind_neighbor [ mask ] <EOL> if return_distance : <EOL> dist [ ind ] = dist [ ind ] [ mask ] <EOL> if return_distance : <EOL> return dist , neigh_ind <EOL> return neigh_ind <EOL> def radius_neighbors_graph ( self , X = None , radius = None , mode = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> if X is not None : <EOL> X = check_array ( X , accept_sparse = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] ) <EOL> n_samples2 = self . _fit_X . shape [ <NUM_LIT:0> ] <EOL> if radius is None : <EOL> radius = self . radius <EOL> if mode == '<STR_LIT>' : <EOL> A_ind = self . radius_neighbors ( X , radius , <EOL> return_distance = False ) <EOL> A_data = None <EOL> elif mode == '<STR_LIT>' : <EOL> dist , A_ind = self . radius_neighbors ( X , radius , <EOL> return_distance = True ) <EOL> A_data = np . concatenate ( list ( dist ) ) <EOL> else : <EOL> raise ValueError ( <EOL> '<STR_LIT>' <EOL> '<STR_LIT>' % mode ) <EOL> n_samples1 = A_ind . shape [ <NUM_LIT:0> ] <EOL> n_neighbors = np . array ( [ len ( a ) for a in A_ind ] ) <EOL> A_ind = np . concatenate ( list ( A_ind ) ) <EOL> if A_data is None : <EOL> A_data = np . ones ( len ( A_ind ) ) <EOL> A_indptr = np . concatenate ( ( np . zeros ( <NUM_LIT:1> , dtype = int ) , <EOL> np . cumsum ( n_neighbors ) ) ) <EOL> return csr_matrix ( ( A_data , A_ind , A_indptr ) , <EOL> shape = ( n_samples1 , n_samples2 ) ) <EOL> class SupervisedFloatMixin ( object ) : <EOL> def fit ( self , X , y ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( X , ( KDTree , BallTree ) ) : <EOL> X , y = check_X_y ( X , y , "<STR_LIT>" , multi_output = True ) <EOL> self . _y = y <EOL> return self . _fit ( X ) <EOL> class SupervisedIntegerMixin ( object ) : <EOL> def fit ( self , X , y ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( X , ( KDTree , BallTree ) ) : <EOL> X , y = check_X_y ( X , y , "<STR_LIT>" , multi_output = True ) <EOL> if y . ndim == <NUM_LIT:1> or y . ndim == <NUM_LIT:2> and y . shape [ <NUM_LIT:1> ] == <NUM_LIT:1> : <EOL> if y . ndim != <NUM_LIT:1> : <EOL> warnings . warn ( "<STR_LIT>" <EOL> "<STR_LIT>" <EOL> "<STR_LIT>" , <EOL> DataConversionWarning , stacklevel = <NUM_LIT:2> ) <EOL> self . outputs_2d_ = False <EOL> y = y . reshape ( ( - <NUM_LIT:1> , <NUM_LIT:1> ) ) <EOL> else : <EOL> self . outputs_2d_ = True <EOL> check_classification_targets ( y ) <EOL> self . classes_ = [ ] <EOL> self . _y = np . empty ( y . shape , dtype = np . int ) <EOL> for k in range ( self . _y . shape [ <NUM_LIT:1> ] ) : <EOL> classes , self . _y [ : , k ] = np . unique ( y [ : , k ] , return_inverse = True ) <EOL> self . classes_ . append ( classes ) <EOL> if not self . outputs_2d_ : <EOL> self . classes_ = self . classes_ [ <NUM_LIT:0> ] <EOL> self . _y = self . _y . ravel ( ) <EOL> return self . _fit ( X ) <EOL> class UnsupervisedMixin ( object ) : <EOL> def fit ( self , X , y = None ) : <EOL> """<STR_LIT>""" <EOL> return self . _fit ( X ) </s>
