Source code for gplearn.genetic

"""Genetic Programming in Python, with a scikit-learn inspired API

The :mod:`gplearn.genetic` module implements Genetic Programming. These
are supervised learning methods based on applying evolutionary operations on
computer programs.
"""

# Author: Trevor Stephens <trevorstephens.com>
#
# License: BSD 3 clause

import itertools
from abc import ABCMeta, abstractmethod
from time import time
from warnings import warn

import numpy as np
from joblib import Parallel, delayed
from scipy.stats import rankdata
from sklearn.base import BaseEstimator
from sklearn.base import RegressorMixin, TransformerMixin, ClassifierMixin
from sklearn.exceptions import NotFittedError
from sklearn.utils.validation import check_X_y, check_array
from sklearn.utils.multiclass import check_classification_targets

from ._program import _Program
from .fitness import _fitness_map, _Fitness
from .functions import _function_map, _Function, sig1 as sigmoid
from .utils import _partition_estimators
from .utils import check_random_state

__all__ = ['SymbolicRegressor', 'SymbolicClassifier', 'SymbolicTransformer']

MAX_INT = np.iinfo(np.int32).max


def _parallel_evolve(n_programs, parents, X, y, sample_weight, seeds, params):
    """Private function used to build a batch of programs within a job."""
    n_samples, n_features = X.shape
    # Unpack parameters
    tournament_size = params['tournament_size']
    function_set = params['function_set']
    arities = params['arities']
    init_depth = params['init_depth']
    init_method = params['init_method']
    const_range = params['const_range']
    metric = params['_metric']
    transformer = params['_transformer']
    parsimony_coefficient = params['parsimony_coefficient']
    method_probs = params['method_probs']
    p_point_replace = params['p_point_replace']
    max_samples = params['max_samples']
    feature_names = params['feature_names']

    max_samples = int(max_samples * n_samples)

    def _tournament():
        """Find the fittest individual from a sub-population."""
        contenders = random_state.randint(0, len(parents), tournament_size)
        fitness = [parents[p].fitness_ for p in contenders]
        if metric.greater_is_better:
            parent_index = contenders[np.argmax(fitness)]
        else:
            parent_index = contenders[np.argmin(fitness)]
        return parents[parent_index], parent_index

    # Build programs
    programs = []

    for i in range(n_programs):

        random_state = check_random_state(seeds[i])

        if parents is None:
            program = None
            genome = None
        else:
            method = random_state.uniform()
            parent, parent_index = _tournament()

            if method < method_probs[0]:
                # crossover
                donor, donor_index = _tournament()
                program, removed, remains = parent.crossover(donor.program,
                                                             random_state)
                genome = {'method': 'Crossover',
                          'parent_idx': parent_index,
                          'parent_nodes': removed,
                          'donor_idx': donor_index,
                          'donor_nodes': remains}
            elif method < method_probs[1]:
                # subtree_mutation
                program, removed, _ = parent.subtree_mutation(random_state)
                genome = {'method': 'Subtree Mutation',
                          'parent_idx': parent_index,
                          'parent_nodes': removed}
            elif method < method_probs[2]:
                # hoist_mutation
                program, removed = parent.hoist_mutation(random_state)
                genome = {'method': 'Hoist Mutation',
                          'parent_idx': parent_index,
                          'parent_nodes': removed}
            elif method < method_probs[3]:
                # point_mutation
                program, mutated = parent.point_mutation(random_state)
                genome = {'method': 'Point Mutation',
                          'parent_idx': parent_index,
                          'parent_nodes': mutated}
            else:
                # reproduction
                program = parent.reproduce()
                genome = {'method': 'Reproduction',
                          'parent_idx': parent_index,
                          'parent_nodes': []}

        program = _Program(function_set=function_set,
                           arities=arities,
                           init_depth=init_depth,
                           init_method=init_method,
                           n_features=n_features,
                           metric=metric,
                           transformer=transformer,
                           const_range=const_range,
                           p_point_replace=p_point_replace,
                           parsimony_coefficient=parsimony_coefficient,
                           feature_names=feature_names,
                           random_state=random_state,
                           program=program)

        program.parents = genome

        # Draw samples, using sample weights, and then fit
        if sample_weight is None:
            curr_sample_weight = np.ones((n_samples,))
        else:
            curr_sample_weight = sample_weight.copy()
        oob_sample_weight = curr_sample_weight.copy()

        indices, not_indices = program.get_all_indices(n_samples,
                                                       max_samples,
                                                       random_state)

        curr_sample_weight[not_indices] = 0
        oob_sample_weight[indices] = 0

        program.raw_fitness_ = program.raw_fitness(X, y, curr_sample_weight)
        if max_samples < n_samples:
            # Calculate OOB fitness
            program.oob_fitness_ = program.raw_fitness(X, y, oob_sample_weight)

        programs.append(program)

    return programs


class BaseSymbolic(BaseEstimator, metaclass=ABCMeta):

    """Base class for symbolic regression / classification estimators.

    Warning: This class should not be used directly.
    Use derived classes instead.

    """

    @abstractmethod
    def __init__(self,
                 population_size=1000,
                 hall_of_fame=None,
                 n_components=None,
                 generations=20,
                 tournament_size=20,
                 stopping_criteria=0.0,
                 const_range=(-1., 1.),
                 init_depth=(2, 6),
                 init_method='half and half',
                 function_set=('add', 'sub', 'mul', 'div'),
                 transformer=None,
                 metric='mean absolute error',
                 parsimony_coefficient=0.001,
                 p_crossover=0.9,
                 p_subtree_mutation=0.01,
                 p_hoist_mutation=0.01,
                 p_point_mutation=0.01,
                 p_point_replace=0.05,
                 max_samples=1.0,
                 feature_names=None,
                 warm_start=False,
                 low_memory=False,
                 n_jobs=1,
                 verbose=0,
                 random_state=None):

        self.population_size = population_size
        self.hall_of_fame = hall_of_fame
        self.n_components = n_components
        self.generations = generations
        self.tournament_size = tournament_size
        self.stopping_criteria = stopping_criteria
        self.const_range = const_range
        self.init_depth = init_depth
        self.init_method = init_method
        self.function_set = function_set
        self.transformer = transformer
        self.metric = metric
        self.parsimony_coefficient = parsimony_coefficient
        self.p_crossover = p_crossover
        self.p_subtree_mutation = p_subtree_mutation
        self.p_hoist_mutation = p_hoist_mutation
        self.p_point_mutation = p_point_mutation
        self.p_point_replace = p_point_replace
        self.max_samples = max_samples
        self.feature_names = feature_names
        self.warm_start = warm_start
        self.low_memory = low_memory
        self.n_jobs = n_jobs
        self.verbose = verbose
        self.random_state = random_state

    def _verbose_reporter(self, run_details=None):
        """A report of the progress of the evolution process.

        Parameters
        ----------
        run_details : dict
            Information about the evolution.

        """
        if run_details is None:
            print('    |{:^25}|{:^42}|'.format('Population Average',
                                               'Best Individual'))
            print('-' * 4 + ' ' + '-' * 25 + ' ' + '-' * 42 + ' ' + '-' * 10)
            line_format = '{:>4} {:>8} {:>16} {:>8} {:>16} {:>16} {:>10}'
            print(line_format.format('Gen', 'Length', 'Fitness', 'Length',
                                     'Fitness', 'OOB Fitness', 'Time Left'))

        else:
            # Estimate remaining time for run
            gen = run_details['generation'][-1]
            generation_time = run_details['generation_time'][-1]
            remaining_time = (self.generations - gen - 1) * generation_time
            if remaining_time > 60:
                remaining_time = '{0:.2f}m'.format(remaining_time / 60.0)
            else:
                remaining_time = '{0:.2f}s'.format(remaining_time)

            oob_fitness = 'N/A'
            line_format = '{:4d} {:8.2f} {:16g} {:8d} {:16g} {:>16} {:>10}'
            if self.max_samples < 1.0:
                oob_fitness = run_details['best_oob_fitness'][-1]
                line_format = '{:4d} {:8.2f} {:16g} {:8d} {:16g} {:16g} {:>10}'

            print(line_format.format(run_details['generation'][-1],
                                     run_details['average_length'][-1],
                                     run_details['average_fitness'][-1],
                                     run_details['best_length'][-1],
                                     run_details['best_fitness'][-1],
                                     oob_fitness,
                                     remaining_time))

    def fit(self, X, y, sample_weight=None):
        """Fit the Genetic Program according to X, y.

        Parameters
        ----------
        X : array-like, shape = [n_samples, n_features]
            Training vectors, where n_samples is the number of samples and
            n_features is the number of features.

        y : array-like, shape = [n_samples]
            Target values.

        sample_weight : array-like, shape = [n_samples], optional
            Weights applied to individual samples.

        Returns
        -------
        self : object
            Returns self.

        """
        random_state = check_random_state(self.random_state)

        # Check arrays
        if isinstance(self, ClassifierMixin):
            X, y = check_X_y(X, y, y_numeric=False)
            check_classification_targets(y)
            self.classes_, y = np.unique(y, return_inverse=True)
            n_trim_classes = np.count_nonzero(np.bincount(y, sample_weight))
            if n_trim_classes != 2:
                raise ValueError("y contains %d class after sample_weight "
                                 "trimmed classes with zero weights, while 2 "
                                 "classes are required."
                                 % n_trim_classes)
            self.n_classes_ = len(self.classes_)
        else:
            X, y = check_X_y(X, y, y_numeric=True)
        if sample_weight is not None:
            sample_weight = check_array(sample_weight, ensure_2d=False)
        _, self.n_features_ = X.shape

        hall_of_fame = self.hall_of_fame
        if hall_of_fame is None:
            hall_of_fame = self.population_size
        if hall_of_fame > self.population_size or hall_of_fame < 1:
            raise ValueError('hall_of_fame (%d) must be less than or equal to '
                             'population_size (%d).' % (self.hall_of_fame,
                                                        self.population_size))
        n_components = self.n_components
        if n_components is None:
            n_components = hall_of_fame
        if n_components > hall_of_fame or n_components < 1:
            raise ValueError('n_components (%d) must be less than or equal to '
                             'hall_of_fame (%d).' % (self.n_components,
                                                     self.hall_of_fame))

        self._function_set = []
        for function in self.function_set:
            if isinstance(function, str):
                if function not in _function_map:
                    raise ValueError('invalid function name %s found in '
                                     '`function_set`.' % function)
                self._function_set.append(_function_map[function])
            elif isinstance(function, _Function):
                self._function_set.append(function)
            else:
                raise ValueError('invalid type %s found in `function_set`.'
                                 % type(function))
        if not self._function_set:
            raise ValueError('No valid functions found in `function_set`.')

        # For point-mutation to find a compatible replacement node
        self._arities = {}
        for function in self._function_set:
            arity = function.arity
            self._arities[arity] = self._arities.get(arity, [])
            self._arities[arity].append(function)

        if isinstance(self.metric, _Fitness):
            self._metric = self.metric
        elif isinstance(self, RegressorMixin):
            if self.metric not in ('mean absolute error', 'mse', 'rmse',
                                   'pearson', 'spearman'):
                raise ValueError('Unsupported metric: %s' % self.metric)
            self._metric = _fitness_map[self.metric]
        elif isinstance(self, ClassifierMixin):
            if self.metric != 'log loss':
                raise ValueError('Unsupported metric: %s' % self.metric)
            self._metric = _fitness_map[self.metric]
        elif isinstance(self, TransformerMixin):
            if self.metric not in ('pearson', 'spearman'):
                raise ValueError('Unsupported metric: %s' % self.metric)
            self._metric = _fitness_map[self.metric]

        self._method_probs = np.array([self.p_crossover,
                                       self.p_subtree_mutation,
                                       self.p_hoist_mutation,
                                       self.p_point_mutation])
        self._method_probs = np.cumsum(self._method_probs)

        if self._method_probs[-1] > 1:
            raise ValueError('The sum of p_crossover, p_subtree_mutation, '
                             'p_hoist_mutation and p_point_mutation should '
                             'total to 1.0 or less.')

        if self.init_method not in ('half and half', 'grow', 'full'):
            raise ValueError('Valid program initializations methods include '
                             '"grow", "full" and "half and half". Given %s.'
                             % self.init_method)

        if not((isinstance(self.const_range, tuple) and
                len(self.const_range) == 2) or self.const_range is None):
            raise ValueError('const_range should be a tuple with length two, '
                             'or None.')

        if (not isinstance(self.init_depth, tuple) or
                len(self.init_depth) != 2):
            raise ValueError('init_depth should be a tuple with length two.')
        if self.init_depth[0] > self.init_depth[1]:
            raise ValueError('init_depth should be in increasing numerical '
                             'order: (min_depth, max_depth).')

        if self.feature_names is not None:
            if self.n_features_ != len(self.feature_names):
                raise ValueError('The supplied `feature_names` has different '
                                 'length to n_features. Expected %d, got %d.'
                                 % (self.n_features_, len(self.feature_names)))
            for feature_name in self.feature_names:
                if not isinstance(feature_name, str):
                    raise ValueError('invalid type %s found in '
                                     '`feature_names`.' % type(feature_name))

        if self.transformer is not None:
            if isinstance(self.transformer, _Function):
                self._transformer = self.transformer
            elif self.transformer == 'sigmoid':
                self._transformer = sigmoid
            else:
                raise ValueError('Invalid `transformer`. Expected either '
                                 '"sigmoid" or _Function object, got %s' %
                                 type(self.transformer))
            if self._transformer.arity != 1:
                raise ValueError('Invalid arity for `transformer`. Expected 1, '
                                 'got %d.' % (self._transformer.arity))

        params = self.get_params()
        params['_metric'] = self._metric
        if hasattr(self, '_transformer'):
            params['_transformer'] = self._transformer
        else:
            params['_transformer'] = None
        params['function_set'] = self._function_set
        params['arities'] = self._arities
        params['method_probs'] = self._method_probs

        if not self.warm_start or not hasattr(self, '_programs'):
            # Free allocated memory, if any
            self._programs = []
            self.run_details_ = {'generation': [],
                                 'average_length': [],
                                 'average_fitness': [],
                                 'best_length': [],
                                 'best_fitness': [],
                                 'best_oob_fitness': [],
                                 'generation_time': []}

        prior_generations = len(self._programs)
        n_more_generations = self.generations - prior_generations

        if n_more_generations < 0:
            raise ValueError('generations=%d must be larger or equal to '
                             'len(_programs)=%d when warm_start==True'
                             % (self.generations, len(self._programs)))
        elif n_more_generations == 0:
            fitness = [program.raw_fitness_ for program in self._programs[-1]]
            warn('Warm-start fitting without increasing n_estimators does not '
                 'fit new programs.')

        if self.warm_start:
            # Generate and discard seeds that would have been produced on the
            # initial fit call.
            for i in range(len(self._programs)):
                _ = random_state.randint(MAX_INT, size=self.population_size)

        if self.verbose:
            # Print header fields
            self._verbose_reporter()

        for gen in range(prior_generations, self.generations):

            start_time = time()

            if gen == 0:
                parents = None
            else:
                parents = self._programs[gen - 1]

            # Parallel loop
            n_jobs, n_programs, starts = _partition_estimators(
                self.population_size, self.n_jobs)
            seeds = random_state.randint(MAX_INT, size=self.population_size)

            population = Parallel(n_jobs=n_jobs,
                                  verbose=int(self.verbose > 1))(
                delayed(_parallel_evolve)(n_programs[i],
                                          parents,
                                          X,
                                          y,
                                          sample_weight,
                                          seeds[starts[i]:starts[i + 1]],
                                          params)
                for i in range(n_jobs))

            # Reduce, maintaining order across different n_jobs
            population = list(itertools.chain.from_iterable(population))

            fitness = [program.raw_fitness_ for program in population]
            length = [program.length_ for program in population]

            parsimony_coefficient = None
            if self.parsimony_coefficient == 'auto':
                parsimony_coefficient = (np.cov(length, fitness)[1, 0] /
                                         np.var(length))
            for program in population:
                program.fitness_ = program.fitness(parsimony_coefficient)

            self._programs.append(population)

            # Remove old programs that didn't make it into the new population.
            if not self.low_memory:
                for old_gen in np.arange(gen, 0, -1):
                    indices = []
                    for program in self._programs[old_gen]:
                        if program is not None:
                            for idx in program.parents:
                                if 'idx' in idx:
                                    indices.append(program.parents[idx])
                    indices = set(indices)
                    for idx in range(self.population_size):
                        if idx not in indices:
                            self._programs[old_gen - 1][idx] = None
            elif gen > 0:
                # Remove old generations
                self._programs[gen - 1] = None

            # Record run details
            if self._metric.greater_is_better:
                best_program = population[np.argmax(fitness)]
            else:
                best_program = population[np.argmin(fitness)]

            self.run_details_['generation'].append(gen)
            self.run_details_['average_length'].append(np.mean(length))
            self.run_details_['average_fitness'].append(np.mean(fitness))
            self.run_details_['best_length'].append(best_program.length_)
            self.run_details_['best_fitness'].append(best_program.raw_fitness_)
            oob_fitness = np.nan
            if self.max_samples < 1.0:
                oob_fitness = best_program.oob_fitness_
            self.run_details_['best_oob_fitness'].append(oob_fitness)
            generation_time = time() - start_time
            self.run_details_['generation_time'].append(generation_time)

            if self.verbose:
                self._verbose_reporter(self.run_details_)

            # Check for early stopping
            if self._metric.greater_is_better:
                best_fitness = fitness[np.argmax(fitness)]
                if best_fitness >= self.stopping_criteria:
                    break
            else:
                best_fitness = fitness[np.argmin(fitness)]
                if best_fitness <= self.stopping_criteria:
                    break

        if isinstance(self, TransformerMixin):
            # Find the best individuals in the final generation
            fitness = np.array(fitness)
            if self._metric.greater_is_better:
                hall_of_fame = fitness.argsort()[::-1][:self.hall_of_fame]
            else:
                hall_of_fame = fitness.argsort()[:self.hall_of_fame]
            evaluation = np.array([gp.execute(X) for gp in
                                   [self._programs[-1][i] for
                                    i in hall_of_fame]])
            if self.metric == 'spearman':
                evaluation = np.apply_along_axis(rankdata, 1, evaluation)

            with np.errstate(divide='ignore', invalid='ignore'):
                correlations = np.abs(np.corrcoef(evaluation))
            np.fill_diagonal(correlations, 0.)
            components = list(range(self.hall_of_fame))
            indices = list(range(self.hall_of_fame))
            # Iteratively remove least fit individual of most correlated pair
            while len(components) > self.n_components:
                most_correlated = np.unravel_index(np.argmax(correlations),
                                                   correlations.shape)
                # The correlation matrix is sorted by fitness, so identifying
                # the least fit of the pair is simply getting the higher index
                worst = max(most_correlated)
                components.pop(worst)
                indices.remove(worst)
                correlations = correlations[:, indices][indices, :]
                indices = list(range(len(components)))
            self._best_programs = [self._programs[-1][i] for i in
                                   hall_of_fame[components]]

        else:
            # Find the best individual in the final generation
            if self._metric.greater_is_better:
                self._program = self._programs[-1][np.argmax(fitness)]
            else:
                self._program = self._programs[-1][np.argmin(fitness)]

        return self


[docs]class SymbolicRegressor(BaseSymbolic, RegressorMixin): """A Genetic Programming symbolic regressor. A symbolic regressor is an estimator that begins by building a population of naive random formulas to represent a relationship. The formulas are represented as tree-like structures with mathematical functions being recursively applied to variables and constants. Each successive generation of programs is then evolved from the one that came before it by selecting the fittest individuals from the population to undergo genetic operations such as crossover, mutation or reproduction. Parameters ---------- population_size : integer, optional (default=1000) The number of programs in each generation. generations : integer, optional (default=20) The number of generations to evolve. tournament_size : integer, optional (default=20) The number of programs that will compete to become part of the next generation. stopping_criteria : float, optional (default=0.0) The required metric value required in order to stop evolution early. const_range : tuple of two floats, or None, optional (default=(-1., 1.)) The range of constants to include in the formulas. If None then no constants will be included in the candidate programs. init_depth : tuple of two ints, optional (default=(2, 6)) The range of tree depths for the initial population of naive formulas. Individual trees will randomly choose a maximum depth from this range. When combined with `init_method='half and half'` this yields the well- known 'ramped half and half' initialization method. init_method : str, optional (default='half and half') - 'grow' : Nodes are chosen at random from both functions and terminals, allowing for smaller trees than `init_depth` allows. Tends to grow asymmetrical trees. - 'full' : Functions are chosen until the `init_depth` is reached, and then terminals are selected. Tends to grow 'bushy' trees. - 'half and half' : Trees are grown through a 50/50 mix of 'full' and 'grow', making for a mix of tree shapes in the initial population. function_set : iterable, optional (default=('add', 'sub', 'mul', 'div')) The functions to use when building and evolving programs. This iterable can include strings to indicate either individual functions as outlined below, or you can also include your own functions as built using the ``make_function`` factory from the ``functions`` module. Available individual functions are: - 'add' : addition, arity=2. - 'sub' : subtraction, arity=2. - 'mul' : multiplication, arity=2. - 'div' : protected division where a denominator near-zero returns 1., arity=2. - 'sqrt' : protected square root where the absolute value of the argument is used, arity=1. - 'log' : protected log where the absolute value of the argument is used and a near-zero argument returns 0., arity=1. - 'abs' : absolute value, arity=1. - 'neg' : negative, arity=1. - 'inv' : protected inverse where a near-zero argument returns 0., arity=1. - 'max' : maximum, arity=2. - 'min' : minimum, arity=2. - 'sin' : sine (radians), arity=1. - 'cos' : cosine (radians), arity=1. - 'tan' : tangent (radians), arity=1. metric : str, optional (default='mean absolute error') The name of the raw fitness metric. Available options include: - 'mean absolute error'. - 'mse' for mean squared error. - 'rmse' for root mean squared error. - 'pearson', for Pearson's product-moment correlation coefficient. - 'spearman' for Spearman's rank-order correlation coefficient. Note that 'pearson' and 'spearman' will not directly predict the target but could be useful as value-added features in a second-step estimator. This would allow the user to generate one engineered feature at a time, using the SymbolicTransformer would allow creation of multiple features at once. parsimony_coefficient : float or "auto", optional (default=0.001) This constant penalizes large programs by adjusting their fitness to be less favorable for selection. Larger values penalize the program more which can control the phenomenon known as 'bloat'. Bloat is when evolution is increasing the size of programs without a significant increase in fitness, which is costly for computation time and makes for a less understandable final result. This parameter may need to be tuned over successive runs. If "auto" the parsimony coefficient is recalculated for each generation using c = Cov(l,f)/Var( l), where Cov(l,f) is the covariance between program size l and program fitness f in the population, and Var(l) is the variance of program sizes. p_crossover : float, optional (default=0.9) The probability of performing crossover on a tournament winner. Crossover takes the winner of a tournament and selects a random subtree from it to be replaced. A second tournament is performed to find a donor. The donor also has a subtree selected at random and this is inserted into the original parent to form an offspring in the next generation. p_subtree_mutation : float, optional (default=0.01) The probability of performing subtree mutation on a tournament winner. Subtree mutation takes the winner of a tournament and selects a random subtree from it to be replaced. A donor subtree is generated at random and this is inserted into the original parent to form an offspring in the next generation. p_hoist_mutation : float, optional (default=0.01) The probability of performing hoist mutation on a tournament winner. Hoist mutation takes the winner of a tournament and selects a random subtree from it. A random subtree of that subtree is then selected and this is 'hoisted' into the original subtrees location to form an offspring in the next generation. This method helps to control bloat. p_point_mutation : float, optional (default=0.01) The probability of performing point mutation on a tournament winner. Point mutation takes the winner of a tournament and selects random nodes from it to be replaced. Terminals are replaced by other terminals and functions are replaced by other functions that require the same number of arguments as the original node. The resulting tree forms an offspring in the next generation. Note : The above genetic operation probabilities must sum to less than one. The balance of probability is assigned to 'reproduction', where a tournament winner is cloned and enters the next generation unmodified. p_point_replace : float, optional (default=0.05) For point mutation only, the probability that any given node will be mutated. max_samples : float, optional (default=1.0) The fraction of samples to draw from X to evaluate each program on. feature_names : list, optional (default=None) Optional list of feature names, used purely for representations in the `print` operation or `export_graphviz`. If None, then X0, X1, etc will be used for representations. warm_start : bool, optional (default=False) When set to ``True``, reuse the solution of the previous call to fit and add more generations to the evolution, otherwise, just fit a new evolution. low_memory : bool, optional (default=False) When set to ``True``, only the current generation is retained. Parent information is discarded. For very large populations or runs with many generations, this can result in substantial memory use reduction. n_jobs : integer, optional (default=1) The number of jobs to run in parallel for `fit`. If -1, then the number of jobs is set to the number of cores. verbose : int, optional (default=0) Controls the verbosity of the evolution building process. random_state : int, RandomState instance or None, optional (default=None) If int, random_state is the seed used by the random number generator; If RandomState instance, random_state is the random number generator; If None, the random number generator is the RandomState instance used by `np.random`. Attributes ---------- run_details_ : dict Details of the evolution process. Includes the following elements: - 'generation' : The generation index. - 'average_length' : The average program length of the generation. - 'average_fitness' : The average program fitness of the generation. - 'best_length' : The length of the best program in the generation. - 'best_fitness' : The fitness of the best program in the generation. - 'best_oob_fitness' : The out of bag fitness of the best program in the generation (requires `max_samples` < 1.0). - 'generation_time' : The time it took for the generation to evolve. See Also -------- SymbolicTransformer References ---------- .. [1] J. Koza, "Genetic Programming", 1992. .. [2] R. Poli, et al. "A Field Guide to Genetic Programming", 2008. """ def __init__(self, population_size=1000, generations=20, tournament_size=20, stopping_criteria=0.0, const_range=(-1., 1.), init_depth=(2, 6), init_method='half and half', function_set=('add', 'sub', 'mul', 'div'), metric='mean absolute error', parsimony_coefficient=0.001, p_crossover=0.9, p_subtree_mutation=0.01, p_hoist_mutation=0.01, p_point_mutation=0.01, p_point_replace=0.05, max_samples=1.0, feature_names=None, warm_start=False, low_memory=False, n_jobs=1, verbose=0, random_state=None): super(SymbolicRegressor, self).__init__( population_size=population_size, generations=generations, tournament_size=tournament_size, stopping_criteria=stopping_criteria, const_range=const_range, init_depth=init_depth, init_method=init_method, function_set=function_set, metric=metric, parsimony_coefficient=parsimony_coefficient, p_crossover=p_crossover, p_subtree_mutation=p_subtree_mutation, p_hoist_mutation=p_hoist_mutation, p_point_mutation=p_point_mutation, p_point_replace=p_point_replace, max_samples=max_samples, feature_names=feature_names, warm_start=warm_start, low_memory=low_memory, n_jobs=n_jobs, verbose=verbose, random_state=random_state) def __str__(self): """Overloads `print` output of the object to resemble a LISP tree.""" if not hasattr(self, '_program'): return self.__repr__() return self._program.__str__()
[docs] def predict(self, X): """Perform regression on test vectors X. Parameters ---------- X : array-like, shape = [n_samples, n_features] Input vectors, where n_samples is the number of samples and n_features is the number of features. Returns ------- y : array, shape = [n_samples] Predicted values for X. """ if not hasattr(self, '_program'): raise NotFittedError('SymbolicRegressor not fitted.') X = check_array(X) _, n_features = X.shape if self.n_features_ != n_features: raise ValueError('Number of features of the model must match the ' 'input. Model n_features is %s and input ' 'n_features is %s.' % (self.n_features_, n_features)) y = self._program.execute(X) return y
[docs]class SymbolicClassifier(BaseSymbolic, ClassifierMixin): """A Genetic Programming symbolic classifier. A symbolic classifier is an estimator that begins by building a population of naive random formulas to represent a relationship. The formulas are represented as tree-like structures with mathematical functions being recursively applied to variables and constants. Each successive generation of programs is then evolved from the one that came before it by selecting the fittest individuals from the population to undergo genetic operations such as crossover, mutation or reproduction. Parameters ---------- population_size : integer, optional (default=500) The number of programs in each generation. generations : integer, optional (default=10) The number of generations to evolve. tournament_size : integer, optional (default=20) The number of programs that will compete to become part of the next generation. stopping_criteria : float, optional (default=0.0) The required metric value required in order to stop evolution early. const_range : tuple of two floats, or None, optional (default=(-1., 1.)) The range of constants to include in the formulas. If None then no constants will be included in the candidate programs. init_depth : tuple of two ints, optional (default=(2, 6)) The range of tree depths for the initial population of naive formulas. Individual trees will randomly choose a maximum depth from this range. When combined with `init_method='half and half'` this yields the well- known 'ramped half and half' initialization method. init_method : str, optional (default='half and half') - 'grow' : Nodes are chosen at random from both functions and terminals, allowing for smaller trees than `init_depth` allows. Tends to grow asymmetrical trees. - 'full' : Functions are chosen until the `init_depth` is reached, and then terminals are selected. Tends to grow 'bushy' trees. - 'half and half' : Trees are grown through a 50/50 mix of 'full' and 'grow', making for a mix of tree shapes in the initial population. function_set : iterable, optional (default=('add', 'sub', 'mul', 'div')) The functions to use when building and evolving programs. This iterable can include strings to indicate either individual functions as outlined below, or you can also include your own functions as built using the ``make_function`` factory from the ``functions`` module. Available individual functions are: - 'add' : addition, arity=2. - 'sub' : subtraction, arity=2. - 'mul' : multiplication, arity=2. - 'div' : protected division where a denominator near-zero returns 1., arity=2. - 'sqrt' : protected square root where the absolute value of the argument is used, arity=1. - 'log' : protected log where the absolute value of the argument is used and a near-zero argument returns 0., arity=1. - 'abs' : absolute value, arity=1. - 'neg' : negative, arity=1. - 'inv' : protected inverse where a near-zero argument returns 0., arity=1. - 'max' : maximum, arity=2. - 'min' : minimum, arity=2. - 'sin' : sine (radians), arity=1. - 'cos' : cosine (radians), arity=1. - 'tan' : tangent (radians), arity=1. transformer : str, optional (default='sigmoid') The name of the function through which the raw decision function is passed. This function will transform the raw decision function into probabilities of each class. This can also be replaced by your own functions as built using the ``make_function`` factory from the ``functions`` module. metric : str, optional (default='log loss') The name of the raw fitness metric. Available options include: - 'log loss' aka binary cross-entropy loss. parsimony_coefficient : float or "auto", optional (default=0.001) This constant penalizes large programs by adjusting their fitness to be less favorable for selection. Larger values penalize the program more which can control the phenomenon known as 'bloat'. Bloat is when evolution is increasing the size of programs without a significant increase in fitness, which is costly for computation time and makes for a less understandable final result. This parameter may need to be tuned over successive runs. If "auto" the parsimony coefficient is recalculated for each generation using c = Cov(l,f)/Var( l), where Cov(l,f) is the covariance between program size l and program fitness f in the population, and Var(l) is the variance of program sizes. p_crossover : float, optional (default=0.9) The probability of performing crossover on a tournament winner. Crossover takes the winner of a tournament and selects a random subtree from it to be replaced. A second tournament is performed to find a donor. The donor also has a subtree selected at random and this is inserted into the original parent to form an offspring in the next generation. p_subtree_mutation : float, optional (default=0.01) The probability of performing subtree mutation on a tournament winner. Subtree mutation takes the winner of a tournament and selects a random subtree from it to be replaced. A donor subtree is generated at random and this is inserted into the original parent to form an offspring in the next generation. p_hoist_mutation : float, optional (default=0.01) The probability of performing hoist mutation on a tournament winner. Hoist mutation takes the winner of a tournament and selects a random subtree from it. A random subtree of that subtree is then selected and this is 'hoisted' into the original subtrees location to form an offspring in the next generation. This method helps to control bloat. p_point_mutation : float, optional (default=0.01) The probability of performing point mutation on a tournament winner. Point mutation takes the winner of a tournament and selects random nodes from it to be replaced. Terminals are replaced by other terminals and functions are replaced by other functions that require the same number of arguments as the original node. The resulting tree forms an offspring in the next generation. Note : The above genetic operation probabilities must sum to less than one. The balance of probability is assigned to 'reproduction', where a tournament winner is cloned and enters the next generation unmodified. p_point_replace : float, optional (default=0.05) For point mutation only, the probability that any given node will be mutated. max_samples : float, optional (default=1.0) The fraction of samples to draw from X to evaluate each program on. feature_names : list, optional (default=None) Optional list of feature names, used purely for representations in the `print` operation or `export_graphviz`. If None, then X0, X1, etc will be used for representations. warm_start : bool, optional (default=False) When set to ``True``, reuse the solution of the previous call to fit and add more generations to the evolution, otherwise, just fit a new evolution. low_memory : bool, optional (default=False) When set to ``True``, only the current generation is retained. Parent information is discarded. For very large populations or runs with many generations, this can result in substantial memory use reduction. n_jobs : integer, optional (default=1) The number of jobs to run in parallel for `fit`. If -1, then the number of jobs is set to the number of cores. verbose : int, optional (default=0) Controls the verbosity of the evolution building process. random_state : int, RandomState instance or None, optional (default=None) If int, random_state is the seed used by the random number generator; If RandomState instance, random_state is the random number generator; If None, the random number generator is the RandomState instance used by `np.random`. Attributes ---------- run_details_ : dict Details of the evolution process. Includes the following elements: - 'generation' : The generation index. - 'average_length' : The average program length of the generation. - 'average_fitness' : The average program fitness of the generation. - 'best_length' : The length of the best program in the generation. - 'best_fitness' : The fitness of the best program in the generation. - 'best_oob_fitness' : The out of bag fitness of the best program in the generation (requires `max_samples` < 1.0). - 'generation_time' : The time it took for the generation to evolve. See Also -------- SymbolicTransformer References ---------- .. [1] J. Koza, "Genetic Programming", 1992. .. [2] R. Poli, et al. "A Field Guide to Genetic Programming", 2008. """ def __init__(self, population_size=1000, generations=20, tournament_size=20, stopping_criteria=0.0, const_range=(-1., 1.), init_depth=(2, 6), init_method='half and half', function_set=('add', 'sub', 'mul', 'div'), transformer='sigmoid', metric='log loss', parsimony_coefficient=0.001, p_crossover=0.9, p_subtree_mutation=0.01, p_hoist_mutation=0.01, p_point_mutation=0.01, p_point_replace=0.05, max_samples=1.0, feature_names=None, warm_start=False, low_memory=False, n_jobs=1, verbose=0, random_state=None): super(SymbolicClassifier, self).__init__( population_size=population_size, generations=generations, tournament_size=tournament_size, stopping_criteria=stopping_criteria, const_range=const_range, init_depth=init_depth, init_method=init_method, function_set=function_set, transformer=transformer, metric=metric, parsimony_coefficient=parsimony_coefficient, p_crossover=p_crossover, p_subtree_mutation=p_subtree_mutation, p_hoist_mutation=p_hoist_mutation, p_point_mutation=p_point_mutation, p_point_replace=p_point_replace, max_samples=max_samples, feature_names=feature_names, warm_start=warm_start, low_memory=low_memory, n_jobs=n_jobs, verbose=verbose, random_state=random_state) def __str__(self): """Overloads `print` output of the object to resemble a LISP tree.""" if not hasattr(self, '_program'): return self.__repr__() return self._program.__str__()
[docs] def predict_proba(self, X): """Predict probabilities on test vectors X. Parameters ---------- X : array-like, shape = [n_samples, n_features] Input vectors, where n_samples is the number of samples and n_features is the number of features. Returns ------- proba : array, shape = [n_samples, n_classes] The class probabilities of the input samples. The order of the classes corresponds to that in the attribute `classes_`. """ if not hasattr(self, '_program'): raise NotFittedError('SymbolicClassifier not fitted.') X = check_array(X) _, n_features = X.shape if self.n_features_ != n_features: raise ValueError('Number of features of the model must match the ' 'input. Model n_features is %s and input ' 'n_features is %s.' % (self.n_features_, n_features)) scores = self._program.execute(X) proba = self._transformer(scores) proba = np.vstack([1 - proba, proba]).T return proba
[docs] def predict(self, X): """Predict classes on test vectors X. Parameters ---------- X : array-like, shape = [n_samples, n_features] Input vectors, where n_samples is the number of samples and n_features is the number of features. Returns ------- y : array, shape = [n_samples,] The predicted classes of the input samples. """ proba = self.predict_proba(X) return self.classes_.take(np.argmax(proba, axis=1), axis=0)
[docs]class SymbolicTransformer(BaseSymbolic, TransformerMixin): """A Genetic Programming symbolic transformer. A symbolic transformer is a supervised transformer that begins by building a population of naive random formulas to represent a relationship. The formulas are represented as tree-like structures with mathematical functions being recursively applied to variables and constants. Each successive generation of programs is then evolved from the one that came before it by selecting the fittest individuals from the population to undergo genetic operations such as crossover, mutation or reproduction. The final population is searched for the fittest individuals with the least correlation to one another. Parameters ---------- population_size : integer, optional (default=1000) The number of programs in each generation. hall_of_fame : integer, or None, optional (default=100) The number of fittest programs to compare from when finding the least-correlated individuals for the n_components. If `None`, the entire final generation will be used. n_components : integer, or None, optional (default=10) The number of best programs to return after searching the hall_of_fame for the least-correlated individuals. If `None`, the entire hall_of_fame will be used. generations : integer, optional (default=20) The number of generations to evolve. tournament_size : integer, optional (default=20) The number of programs that will compete to become part of the next generation. stopping_criteria : float, optional (default=1.0) The required metric value required in order to stop evolution early. const_range : tuple of two floats, or None, optional (default=(-1., 1.)) The range of constants to include in the formulas. If None then no constants will be included in the candidate programs. init_depth : tuple of two ints, optional (default=(2, 6)) The range of tree depths for the initial population of naive formulas. Individual trees will randomly choose a maximum depth from this range. When combined with `init_method='half and half'` this yields the well- known 'ramped half and half' initialization method. init_method : str, optional (default='half and half') - 'grow' : Nodes are chosen at random from both functions and terminals, allowing for smaller trees than `init_depth` allows. Tends to grow asymmetrical trees. - 'full' : Functions are chosen until the `init_depth` is reached, and then terminals are selected. Tends to grow 'bushy' trees. - 'half and half' : Trees are grown through a 50/50 mix of 'full' and 'grow', making for a mix of tree shapes in the initial population. function_set : iterable, optional (default=('add', 'sub', 'mul', 'div')) The functions to use when building and evolving programs. This iterable can include strings to indicate either individual functions as outlined below, or you can also include your own functions as built using the ``make_function`` factory from the ``functions`` module. Available individual functions are: - 'add' : addition, arity=2. - 'sub' : subtraction, arity=2. - 'mul' : multiplication, arity=2. - 'div' : protected division where a denominator near-zero returns 1., arity=2. - 'sqrt' : protected square root where the absolute value of the argument is used, arity=1. - 'log' : protected log where the absolute value of the argument is used and a near-zero argument returns 0., arity=1. - 'abs' : absolute value, arity=1. - 'neg' : negative, arity=1. - 'inv' : protected inverse where a near-zero argument returns 0., arity=1. - 'max' : maximum, arity=2. - 'min' : minimum, arity=2. - 'sin' : sine (radians), arity=1. - 'cos' : cosine (radians), arity=1. - 'tan' : tangent (radians), arity=1. metric : str, optional (default='pearson') The name of the raw fitness metric. Available options include: - 'pearson', for Pearson's product-moment correlation coefficient. - 'spearman' for Spearman's rank-order correlation coefficient. parsimony_coefficient : float or "auto", optional (default=0.001) This constant penalizes large programs by adjusting their fitness to be less favorable for selection. Larger values penalize the program more which can control the phenomenon known as 'bloat'. Bloat is when evolution is increasing the size of programs without a significant increase in fitness, which is costly for computation time and makes for a less understandable final result. This parameter may need to be tuned over successive runs. If "auto" the parsimony coefficient is recalculated for each generation using c = Cov(l,f)/Var( l), where Cov(l,f) is the covariance between program size l and program fitness f in the population, and Var(l) is the variance of program sizes. p_crossover : float, optional (default=0.9) The probability of performing crossover on a tournament winner. Crossover takes the winner of a tournament and selects a random subtree from it to be replaced. A second tournament is performed to find a donor. The donor also has a subtree selected at random and this is inserted into the original parent to form an offspring in the next generation. p_subtree_mutation : float, optional (default=0.01) The probability of performing subtree mutation on a tournament winner. Subtree mutation takes the winner of a tournament and selects a random subtree from it to be replaced. A donor subtree is generated at random and this is inserted into the original parent to form an offspring in the next generation. p_hoist_mutation : float, optional (default=0.01) The probability of performing hoist mutation on a tournament winner. Hoist mutation takes the winner of a tournament and selects a random subtree from it. A random subtree of that subtree is then selected and this is 'hoisted' into the original subtrees location to form an offspring in the next generation. This method helps to control bloat. p_point_mutation : float, optional (default=0.01) The probability of performing point mutation on a tournament winner. Point mutation takes the winner of a tournament and selects random nodes from it to be replaced. Terminals are replaced by other terminals and functions are replaced by other functions that require the same number of arguments as the original node. The resulting tree forms an offspring in the next generation. Note : The above genetic operation probabilities must sum to less than one. The balance of probability is assigned to 'reproduction', where a tournament winner is cloned and enters the next generation unmodified. p_point_replace : float, optional (default=0.05) For point mutation only, the probability that any given node will be mutated. max_samples : float, optional (default=1.0) The fraction of samples to draw from X to evaluate each program on. feature_names : list, optional (default=None) Optional list of feature names, used purely for representations in the `print` operation or `export_graphviz`. If None, then X0, X1, etc will be used for representations. warm_start : bool, optional (default=False) When set to ``True``, reuse the solution of the previous call to fit and add more generations to the evolution, otherwise, just fit a new evolution. low_memory : bool, optional (default=False) When set to ``True``, only the current generation is retained. Parent information is discarded. For very large populations or runs with many generations, this can result in substantial memory use reduction. n_jobs : integer, optional (default=1) The number of jobs to run in parallel for `fit`. If -1, then the number of jobs is set to the number of cores. verbose : int, optional (default=0) Controls the verbosity of the evolution building process. random_state : int, RandomState instance or None, optional (default=None) If int, random_state is the seed used by the random number generator; If RandomState instance, random_state is the random number generator; If None, the random number generator is the RandomState instance used by `np.random`. Attributes ---------- run_details_ : dict Details of the evolution process. Includes the following elements: - 'generation' : The generation index. - 'average_length' : The average program length of the generation. - 'average_fitness' : The average program fitness of the generation. - 'best_length' : The length of the best program in the generation. - 'best_fitness' : The fitness of the best program in the generation. - 'best_oob_fitness' : The out of bag fitness of the best program in the generation (requires `max_samples` < 1.0). - 'generation_time' : The time it took for the generation to evolve. See Also -------- SymbolicRegressor References ---------- .. [1] J. Koza, "Genetic Programming", 1992. .. [2] R. Poli, et al. "A Field Guide to Genetic Programming", 2008. """ def __init__(self, population_size=1000, hall_of_fame=100, n_components=10, generations=20, tournament_size=20, stopping_criteria=1.0, const_range=(-1., 1.), init_depth=(2, 6), init_method='half and half', function_set=('add', 'sub', 'mul', 'div'), metric='pearson', parsimony_coefficient=0.001, p_crossover=0.9, p_subtree_mutation=0.01, p_hoist_mutation=0.01, p_point_mutation=0.01, p_point_replace=0.05, max_samples=1.0, feature_names=None, warm_start=False, low_memory=False, n_jobs=1, verbose=0, random_state=None): super(SymbolicTransformer, self).__init__( population_size=population_size, hall_of_fame=hall_of_fame, n_components=n_components, generations=generations, tournament_size=tournament_size, stopping_criteria=stopping_criteria, const_range=const_range, init_depth=init_depth, init_method=init_method, function_set=function_set, metric=metric, parsimony_coefficient=parsimony_coefficient, p_crossover=p_crossover, p_subtree_mutation=p_subtree_mutation, p_hoist_mutation=p_hoist_mutation, p_point_mutation=p_point_mutation, p_point_replace=p_point_replace, max_samples=max_samples, feature_names=feature_names, warm_start=warm_start, low_memory=low_memory, n_jobs=n_jobs, verbose=verbose, random_state=random_state) def __len__(self): """Overloads `len` output to be the number of fitted components.""" if not hasattr(self, '_best_programs'): return 0 return self.n_components def __getitem__(self, item): """Return the ith item of the fitted components.""" if item >= len(self): raise IndexError return self._best_programs[item] def __str__(self): """Overloads `print` output of the object to resemble LISP trees.""" if not hasattr(self, '_best_programs'): return self.__repr__() output = str([gp.__str__() for gp in self]) return output.replace("',", ",\n").replace("'", "")
[docs] def transform(self, X): """Transform X according to the fitted transformer. Parameters ---------- X : array-like, shape = [n_samples, n_features] Input vectors, where n_samples is the number of samples and n_features is the number of features. Returns ------- X_new : array-like, shape = [n_samples, n_components] Transformed array. """ if not hasattr(self, '_best_programs'): raise NotFittedError('SymbolicTransformer not fitted.') X = check_array(X) _, n_features = X.shape if self.n_features_ != n_features: raise ValueError('Number of features of the model must match the ' 'input. Model n_features is %s and input ' 'n_features is %s.' % (self.n_features_, n_features)) X_new = np.array([gp.execute(X) for gp in self._best_programs]).T return X_new
[docs] def fit_transform(self, X, y, sample_weight=None): """Fit to data, then transform it. Parameters ---------- X : array-like, shape = [n_samples, n_features] Training vectors, where n_samples is the number of samples and n_features is the number of features. y : array-like, shape = [n_samples] Target values. sample_weight : array-like, shape = [n_samples], optional Weights applied to individual samples. Returns ------- X_new : array-like, shape = [n_samples, n_components] Transformed array. """ return self.fit(X, y, sample_weight).transform(X)