class_docstr: iSOUP-Tree's Extended Binary Search Tree (E-BST).
  
  This class implements the Extended Binary Search Tree[^1] (E-BST)
  structure, using the variant employed by Osojnik et al.[^2] in the
  iSOUP-Tree algorithm. This structure is employed to observe the target
  space distribution.
  
  Proposed along with Fast Incremental Model Tree with Drift Detection[^1] (FIMT-DD), E-BST was
  the first attribute observer (AO) proposed for incremental Hoeffding Tree regressors. This
  AO works by storing all observations between splits in an extended binary search tree
  structure. E-BST stores the input feature realizations and statistics of the target(s) that
  enable calculating the split heuristic at any time. To alleviate time and memory costs, E-BST
  implements a memory management routine, where the worst split candidates are pruned from the
  binary tree.
  
  In this variant, only the left branch statistics are stored and the complete split-enabling
  statistics are calculated with an in-order traversal of the binary search tree.
  
  References
  ----------
  [^1]: Ikonomovska, E., Gama, J., & Džeroski, S. (2011). Learning model trees from evolving
      data streams. Data mining and knowledge discovery, 23(1), 128-168.
  [^2]: [Osojnik, Aljaž. 2017. Structured output prediction on Data Streams
  (Doctoral Dissertation)](http://kt.ijs.si/theses/phd_aljaz_osojnik.pdf)
class_docstr_tok: ["iSOUP-Tree","'s","Extended","Binary","Search","Tree","(","E-BST",")",".","This","class","implements","the","Extended","Binary","Search","Tree","[","^1","]","(","E-BST",")","structure",",","using","the","variant","employed","by","Osojnik","et","al",".","[","^2","]","in","the","iSOUP-Tree","algorithm",".","This","structure","is","employed","to","observe","the","target","space","distribution",".","Proposed","along","with","Fast","Incremental","Model","Tree","with","Drift","Detection","[","^1","]","(","FIMT-DD",")",",","E-BST","was","the","first","attribute","observer","(","AO",")","proposed","for","incremental","Hoeffding","Tree","regressors",".","This","AO","works","by","storing","all","observations","between","splits","in","an","extended","binary","search","tree","structure",".","E-BST","stores","the","input","feature","realizations","and","statistics","of","the","target","(","s",")","that","enable","calculating","the","split","heuristic","at","any","time",".","To","alleviate","time","and","memory","costs",",","E-BST","implements","a","memory","management","routine",",","where","the","worst","split","candidates","are","pruned","from","the","binary","tree",".","In","this","variant",",","only","the","left","branch","statistics","are","stored","and","the","complete","split-enabling","statistics","are","calculated","with","an","in-order","traversal","of","the","binary","search","tree",".","References","--","--","--","--","--","[","^1","]",":","Ikonomovska",",","E.",",","Gama",",","J.",",","&","D\u017eeroski",",","S.","(","2011",")",".","Learning","model","trees","from","evolving","data","streams",".","Data","mining","and","knowledge","discovery",",","23","(","1",")",",","128-168",".","[","^2","]",":","[","Osojnik",",","Alja\u017e",".","2017",".","Structured","output","prediction","on","Data","Streams","(","Doctoral","Dissertation",")","]","(","http",":","\/\/kt.ijs.si\/theses\/phd_aljaz_osojnik.pdf",")"]
docstr: Remove bad splits.
  
  Based on FIMT-DD's [^1] procedure to remove bad split candidates from the E-BST. This
  mechanism is triggered every time a split attempt fails. The rationale is to remove
  points whose split merit is much worse than the best candidate overall (for which the
  growth decision already failed).
  
  Let $m_1$ be the merit of the best split point and $m_2$ be the merit of the
  second best split candidate. The ratio $r = m_2/m_1$ along with the Hoeffding bound
  ($\epsilon$) are used to decide upon creating a split. A split occurs when
  $r < 1 - \epsilon$. A split candidate, with merit $m_i$, is considered badr
  if $m_i / m_1 < r - 2\epsilon$. The rationale is the following: if the merit ratio
  for this point is smaller than the lower bound of $r$, then the true merit of that
  split relative to the best one is small. Hence, this candidate can be safely removed.
  
  To avoid excessive and costly manipulations of the E-BST to update the stored statistics,
  only the nodes whose children are all bad split points are pruned, as defined in [^1].
  
  Parameters
  ----------
  criterion
      The split criterion used by the regression tree.
  last_check_ratio
      The ratio between the merit of the second best split candidate and the merit of the
      best split candidate observed in the last failed split attempt.
  last_check_vr
      The merit (variance reduction) of the best split candidate observed in the last
      failed split attempt.
  last_check_e
      The Hoeffding bound value calculated in the last failed split attempt.
  pre_split_dist
      The complete statistics of the target observed in the leaf node.
  
  References
  ----------
  [^1]: Ikonomovska, E., Gama, J., & Džeroski, S. (2011). Learning model trees from evolving
  data streams. Data mining and knowledge discovery, 23(1), 128-168.
docstr_tok: ["Remove","bad","splits",".","Based","on","FIMT-DD","'s","[","^1","]","procedure","to","remove","bad","split","candidates","from","the","E-BST",".","This","mechanism","is","triggered","every","time","a","split","attempt","fails",".","The","rationale","is","to","remove","points","whose","split","merit","is","much","worse","than","the","best","candidate","overall","(","for","which","the","growth","decision","already","failed",")",".","Let","$","m_1","$","be","the","merit","of","the","best","split","point","and","$","m_2","$","be","the","merit","of","the","second","best","split","candidate",".","The","ratio","$","r","=","m_2\/m_1","$","along","with","the","Hoeffding","bound","(","$","\\epsilon","$",")","are","used","to","decide","upon","creating","a","split",".","A","split","occurs","when","$","r","<","1","-","\\epsilon","$",".","A","split","candidate",",","with","merit","$","m_i","$",",","is","considered","badr","if","$","m_i","\/","m_1","<","r","-","2\\epsilon","$",".","The","rationale","is","the","following",":","if","the","merit","ratio","for","this","point","is","smaller","than","the","lower","bound","of","$","r","$",",","then","the","true","merit","of","that","split","relative","to","the","best","one","is","small",".","Hence",",","this","candidate","can","be","safely","removed",".","To","avoid","excessive","and","costly","manipulations","of","the","E-BST","to","update","the","stored","statistics",",","only","the","nodes","whose","children","are","all","bad","split","points","are","pruned",",","as","defined","in","[","^1","]",".","Parameters","--","--","--","--","--","criterion","The","split","criterion","used","by","the","regression","tree",".","last_check_ratio","The","ratio","between","the","merit","of","the","second","best","split","candidate","and","the","merit","of","the","best","split","candidate","observed","in","the","last","failed","split","attempt",".","last_check_vr","The","merit","(","variance","reduction",")","of","the","best","split","candidate","observed","in","the","last","failed","split","attempt",".","last_check_e","The","Hoeffding","bound","value","calculated","in","the","last","failed","split","attempt",".","pre_split_dist","The","complete","statistics","of","the","target","observed","in","the","leaf","node",".","References","--","--","--","--","--","[","^1","]",":","Ikonomovska",",","E.",",","Gama",",","J.",",","&","D\u017eeroski",",","S.","(","2011",")",".","Learning","model","trees","from","evolving","data","streams",".","Data","mining","and","knowledge","discovery",",","23","(","1",")",",","128-168","."]
code: def remove_bad_splits(
      self,
      criterion,
      last_check_ratio: float,
      last_check_vr: float,
      last_check_e: float,
      pre_split_dist: list | dict,
  ):
      """Remove bad splits.
  
      Based on FIMT-DD's [^1] procedure to remove bad split candidates from the E-BST. This
      mechanism is triggered every time a split attempt fails. The rationale is to remove
      points whose split merit is much worse than the best candidate overall (for which the
      growth decision already failed).
  
      Let $m_1$ be the merit of the best split point and $m_2$ be the merit of the
      second best split candidate. The ratio $r = m_2/m_1$ along with the Hoeffding bound
      ($\\epsilon$) are used to decide upon creating a split. A split occurs when
      $r < 1 - \\epsilon$. A split candidate, with merit $m_i$, is considered badr
      if $m_i / m_1 < r - 2\\epsilon$. The rationale is the following: if the merit ratio
      for this point is smaller than the lower bound of $r$, then the true merit of that
      split relative to the best one is small. Hence, this candidate can be safely removed.
  
      To avoid excessive and costly manipulations of the E-BST to update the stored statistics,
      only the nodes whose children are all bad split points are pruned, as defined in [^1].
  
      Parameters
      ----------
      criterion
          The split criterion used by the regression tree.
      last_check_ratio
          The ratio between the merit of the second best split candidate and the merit of the
          best split candidate observed in the last failed split attempt.
      last_check_vr
          The merit (variance reduction) of the best split candidate observed in the last
          failed split attempt.
      last_check_e
          The Hoeffding bound value calculated in the last failed split attempt.
      pre_split_dist
          The complete statistics of the target observed in the leaf node.
  
      References
      ----------
      [^1]: Ikonomovska, E., Gama, J., & Džeroski, S. (2011). Learning model trees from evolving
      data streams. Data mining and knowledge discovery, 23(1), 128-168.
      """
  
      if self._root is None:
          return
  
      # Auxiliary variables
      self._criterion = criterion
      self._pre_split_dist = pre_split_dist
      self._last_check_ratio = last_check_ratio
      self._last_check_vr = last_check_vr
      self._last_check_e = last_check_e
  
      # Import VectorDict here to prevent circular import of river.utils
      from river.utils import VectorDict
  
      # Handles both single-target and multi-target tasks
      if isinstance(pre_split_dist, VectorDict):
          self._aux_estimator = VectorDict(
              default_factory=functools.partial(Var)
          )
      else:
          self._aux_estimator = Var()
  
      self._remove_bad_split_nodes(self._root)
  
      # Delete auxiliary variables
      del self._criterion
      del self._pre_split_dist
      del self._last_check_ratio
      del self._last_check_vr
      del self._last_check_e
      del self._aux_estimator
  
file_path: river/river/tree/splitter/ebst_splitter.py
imports: from __future__ import annotations
  import functools
  from river.stats import Var
  from ..utils import BranchFactory
  from .base import Splitter
label_desc: Use image node_id 7 for calling the EBSTSplitter obj's underlying member method code with example usage: obj.remove_bad_splits(criterion, last_check_ratio, last_check_vr, last_check_e, pre_split_dist) without return types