class_docstr: FIGS (sum of trees) classifier.
  Fast Interpretable Greedy-Tree Sums (FIGS) is an algorithm for fitting concise rule-based models.
  Specifically, FIGS generalizes CART to simultaneously grow a flexible number of trees in a summation.
  The total number of splits across all the trees can be restricted by a pre-specified threshold, keeping the model interpretable.
  Experiments across real-world datasets show that FIGS achieves state-of-the-art prediction performance when restricted to just a few splits (e.g. less than 20).
  https://arxiv.org/abs/2201.11931
class_docstr_tok: ["FIGS","(","sum","of","trees",")","classifier",".","Fast","Interpretable","Greedy-Tree","Sums","(","FIGS",")","is","an","algorithm","for","fitting","concise","rule-based","models",".","Specifically",",","FIGS","generalizes","CART","to","simultaneously","grow","a","flexible","number","of","trees","in","a","summation",".","The","total","number","of","splits","across","all","the","trees","can","be","restricted","by","a","pre-specified","threshold",",","keeping","the","model","interpretable",".","Experiments","across","real-world","datasets","show","that","FIGS","achieves","state-of-the-art","prediction","performance","when","restricted","to","just","a","few","splits","(","e.g",".","less","than","20",")",".","https",":","\/\/arxiv.org\/abs\/2201.11931"]
docstr: Params
  ------
  _sample_weight: array-like of shape (n_samples,), default=None
      Sample weights. If None, then samples are equally weighted.
      Splits that would create child nodes with net zero or negative weight
      are ignored while searching for a split in each node.
docstr_tok: ["Params","--","--","--","_sample_weight",":","array-like","of","shape","(","n_samples",",",")",",","default=None","Sample","weights",".","If","None",",","then","samples","are","equally","weighted",".","Splits","that","would","create","child","nodes","with","net","zero","or","negative","weight","are","ignored","while","searching","for","a","split","in","each","node","."]
code: def fit(
      self,
      X,
      y=None,
      feature_names=None,
      verbose=False,
      sample_weight=None,
      categorical_features=None,
  ):
      """
      Params
      ------
      _sample_weight: array-like of shape (n_samples,), default=None
          Sample weights. If None, then samples are equally weighted.
          Splits that would create child nodes with net zero or negative weight
          are ignored while searching for a split in each node.
      """
      if categorical_features is not None:
          X, self._encoder = self._encode_categories(
              X, categorical_features
          )
      X, y, feature_names = check_fit_arguments(
          self, X, y, feature_names
      )
      if sample_weight is not None:
          sample_weight = _check_sample_weight(sample_weight, X)
  
      self.trees_ = []  # list of the root nodes of added trees
      self.complexity_ = 0  # tracks the number of rules in the model
      y_predictions_per_tree = {}  # predictions for each tree
      y_residuals_per_tree = {}  # based on predictions above
  
      # set up initial potential_splits
      # everything in potential_splits either is_root (so it can be added directly to self.trees_)
      # or it is a child of a root node that has already been added
      idxs = np.ones(X.shape[0], dtype=bool)
      node_init = self._construct_node_with_stump(
          X=X,
          y=y,
          idxs=idxs,
          tree_num=-1,
          sample_weight=sample_weight,
          max_features=self.max_features,
      )
      potential_splits = [node_init]
      for node in potential_splits:
          node.setattrs(is_root=True)
      potential_splits = sorted(
          potential_splits, key=lambda x: x.impurity_reduction
      )
  
      # start the greedy fitting algorithm
      finished = False
      while len(potential_splits) > 0 and not finished:
          # print('potential_splits', [str(s) for s in potential_splits])
          # get node with max impurity_reduction (since it's sorted)
          split_node = potential_splits.pop()
  
          # don't split on node
          if split_node.impurity_reduction < self.min_impurity_decrease:
              finished = True
              break
          elif (
              split_node.is_root
              and self.max_trees is not None
              and len(self.trees_) >= self.max_trees
          ):
              # If the node is the root of a new tree and we have reached self.max_trees,
              # don't split on it, but allow later splits to continue growing existing trees
              continue
  
          # split on node
          if verbose:
              print("\nadding " + str(split_node))
          self.complexity_ += 1
  
          # if added a tree root
          if split_node.is_root:
              # start a new tree
              self.trees_.append(split_node)
  
              # update tree_num
              for node_ in [
                  split_node,
                  split_node.left_temp,
                  split_node.right_temp,
              ]:
                  if node_ is not None:
                      node_.tree_num = len(self.trees_) - 1
  
              # add new root potential node
              node_new_root = Node(
                  is_root=True,
                  idxs=np.ones(X.shape[0], dtype=bool),
                  tree_num=-1,
              )
              potential_splits.append(node_new_root)
  
          # add children to potential splits
          # assign left_temp, right_temp to be proper children
          # (basically adds them to tree in predict method)
          split_node.setattrs(
              left=split_node.left_temp, right=split_node.right_temp
          )
  
          # add children to potential_splits
          potential_splits.append(split_node.left)
          potential_splits.append(split_node.right)
  
          # update predictions for altered tree
          for tree_num_ in range(len(self.trees_)):
              y_predictions_per_tree[tree_num_] = self._predict_tree(
                  self.trees_[tree_num_], X
              )
          # dummy 0 preds for possible new trees
          y_predictions_per_tree[-1] = np.zeros(X.shape[0])
  
          # update residuals for each tree
          # -1 is key for potential new tree
          for tree_num_ in list(range(len(self.trees_))) + [-1]:
              y_residuals_per_tree[tree_num_] = deepcopy(y)
  
              # subtract predictions of all other trees
              # Since the current tree makes a constant prediction over the node being split,
              # one may ignore its contributions to the residuals without affecting the impurity decrease.
              for tree_num_other_ in range(len(self.trees_)):
                  if not tree_num_other_ == tree_num_:
                      y_residuals_per_tree[
                          tree_num_
                      ] -= y_predictions_per_tree[tree_num_other_]
  
          # recompute all impurities + update potential_split children
          potential_splits_new = []
          for potential_split in potential_splits:
              y_target = y_residuals_per_tree[potential_split.tree_num]
  
              # re-calculate the best split
              potential_split_updated = self._construct_node_with_stump(
                  X=X,
                  y=y_target,
                  idxs=potential_split.idxs,
                  tree_num=potential_split.tree_num,
                  sample_weight=sample_weight,
                  max_features=self.max_features,
              )
  
              # need to preserve certain attributes from before (value at this split + is_root)
              # value may change because residuals may have changed, but we want it to store the value from before
              potential_split.setattrs(
                  feature=potential_split_updated.feature,
                  threshold=potential_split_updated.threshold,
                  impurity_reduction=potential_split_updated.impurity_reduction,
                  impurity=potential_split_updated.impurity,
                  left_temp=potential_split_updated.left_temp,
                  right_temp=potential_split_updated.right_temp,
              )
  
              # this is a valid split
              if potential_split.impurity_reduction is not None:
                  potential_splits_new.append(potential_split)
  
          # sort so largest impurity reduction comes last (should probs make this a heap later)
          potential_splits = sorted(
              potential_splits_new, key=lambda x: x.impurity_reduction
          )
          if verbose:
              print(self)
          if (
              self.max_rules is not None
              and self.complexity_ >= self.max_rules
          ):
              finished = True
              break
  
      # annotate final tree with node_id and value_sklearn, and prepare importance_data_
      importance_data = []
      for tree_ in self.trees_:
          node_counter = iter(range(0, int(1e06)))
  
          def _annotate_node(node: Node, X, y):
              if node is None:
                  return
  
              # TODO does not incorporate sample weights
              value_counts = pd.Series(y).value_counts()
              try:
                  neg_count = value_counts[0.0]
              except KeyError:
                  neg_count = 0
  
              try:
                  pos_count = value_counts[1.0]
              except KeyError:
                  pos_count = 0
  
              value_sklearn = np.array(
                  [neg_count, pos_count], dtype=float
              )
  
              node.setattrs(
                  node_id=next(node_counter),
                  value_sklearn=value_sklearn,
              )
  
              idxs_left = X[:, node.feature] <= node.threshold
              _annotate_node(node.left, X[idxs_left], y[idxs_left])
              _annotate_node(node.right, X[~idxs_left], y[~idxs_left])
  
          _annotate_node(tree_, X, y)
  
          # now that the samples per node are known, we can start to compute the importances
          importance_data_tree = np.zeros(len(self.feature_names_))
  
          def _importances(node: Node):
              if node is None or node.left is None:
                  return 0.0
  
              # TODO does not incorporate sample weights, but will if added to value_sklearn
              importance_data_tree[node.feature] += (
                  np.sum(node.value_sklearn) * node.impurity
                  - np.sum(node.left.value_sklearn) * node.left.impurity
                  - np.sum(node.right.value_sklearn)
                  * node.right.impurity
              )
  
              return (
                  np.sum(node.value_sklearn)
                  + _importances(node.left)
                  + _importances(node.right)
              )
  
          # require the tree to have more than 1 node, otherwise just leave importance_data_tree as zeros
          if 1 < next(node_counter):
              tree_samples = _importances(tree_)
              if tree_samples != 0:
                  importance_data_tree /= tree_samples
              else:
                  importance_data_tree = 0
  
          importance_data.append(importance_data_tree)
  
      self.importance_data_ = importance_data
  
      return self
  
imports: from copy import deepcopy
  from typing import List
  import matplotlib.pyplot
  import numpy
  import pandas
  from scipy.special import expit
  from sklearn import datasets
  from sklearn import tree
  from sklearn.base import BaseEstimator, ClassifierMixin, RegressorMixin
  from sklearn.model_selection import train_test_split, cross_val_score
  from sklearn.tree import plot_tree, DecisionTreeClassifier
  from sklearn.utils import check_X_y, check_array
  from sklearn.utils.validation import _check_sample_weight, check_is_fitted
  from imodels.tree.viz_utils import extract_sklearn_tree_from_figs
  from imodels.util.arguments import check_fit_arguments
  from imodels.util.data_util import encode_categories
label_desc: Use image node_id 5 for calling the FIGS obj's underlying member method code with example usage: obj.fit(X, y, feature_names, verbose, sample_weight, categorical_features) and returns: self, unknown, int