Aluode/PerceptionLabPortable
0
1"""
2This module gathers tree-based methods, including decision, regression and
3randomized trees. Single and multi-output problems are both handled.
4"""
5
6# Authors: The scikit-learn developers
7# SPDX-License-Identifier: BSD-3-Clause
8
9import copy
10import numbers
11from abc import ABCMeta, abstractmethod
12from math import ceil
13from numbers import Integral, Real
14
15import numpy as np
16from scipy.sparse import issparse
17
18from sklearn.utils import metadata_routing
19
20from ..base import (
21 BaseEstimator,
22 ClassifierMixin,
23 MultiOutputMixin,
24 RegressorMixin,
25 _fit_context,
26 clone,
27 is_classifier,
28)
29from ..utils import Bunch, check_random_state, compute_sample_weight
30from ..utils._param_validation import Hidden, Interval, RealNotInt, StrOptions
31from ..utils.multiclass import check_classification_targets
32from ..utils.validation import (
33 _assert_all_finite_element_wise,
34 _check_n_features,
35 _check_sample_weight,
36 assert_all_finite,
37 check_is_fitted,
38 validate_data,
39)
40from . import _criterion, _splitter, _tree
41from ._criterion import Criterion
42from ._splitter import Splitter
43from ._tree import (
44 BestFirstTreeBuilder,
45 DepthFirstTreeBuilder,
46 Tree,
47 _build_pruned_tree_ccp,
48 ccp_pruning_path,
49)
50from ._utils import _any_isnan_axis0
51
52__all__ = [
53 "DecisionTreeClassifier",
54 "DecisionTreeRegressor",
55 "ExtraTreeClassifier",
56 "ExtraTreeRegressor",
57]
58
59
60# =============================================================================
61# Types and constants
62# =============================================================================
63
64DTYPE = _tree.DTYPE
65DOUBLE = _tree.DOUBLE
66
67CRITERIA_CLF = {
68 "gini": _criterion.Gini,
69 "log_loss": _criterion.Entropy,
70 "entropy": _criterion.Entropy,
71}
72CRITERIA_REG = {
73 "squared_error": _criterion.MSE,
74 "friedman_mse": _criterion.FriedmanMSE,
75 "absolute_error": _criterion.MAE,
76 "poisson": _criterion.Poisson,
77}
78
79DENSE_SPLITTERS = {"best": _splitter.BestSplitter, "random": _splitter.RandomSplitter}
80
81SPARSE_SPLITTERS = {
82 "best": _splitter.BestSparseSplitter,
83 "random": _splitter.RandomSparseSplitter,
84}
85
86# =============================================================================
87# Base decision tree
88# =============================================================================
89
90
91class BaseDecisionTree(MultiOutputMixin, BaseEstimator, metaclass=ABCMeta):
92 """Base class for decision trees.
93
94 Warning: This class should not be used directly.
95 Use derived classes instead.
96 """
97
98 # "check_input" is used for optimisation and isn't something to be passed
99 # around in a pipeline.
100 __metadata_request__predict = {"check_input": metadata_routing.UNUSED}
101
102 _parameter_constraints: dict = {
103 "splitter": [StrOptions({"best", "random"})],
104 "max_depth": [Interval(Integral, 1, None, closed="left"), None],
105 "min_samples_split": [
106 Interval(Integral, 2, None, closed="left"),
107 Interval(RealNotInt, 0.0, 1.0, closed="right"),
108 ],
109 "min_samples_leaf": [
110 Interval(Integral, 1, None, closed="left"),
111 Interval(RealNotInt, 0.0, 1.0, closed="neither"),
112 ],
113 "min_weight_fraction_leaf": [Interval(Real, 0.0, 0.5, closed="both")],
114 "max_features": [
115 Interval(Integral, 1, None, closed="left"),
116 Interval(RealNotInt, 0.0, 1.0, closed="right"),
117 StrOptions({"sqrt", "log2"}),
118 None,
119 ],
120 "random_state": ["random_state"],
121 "max_leaf_nodes": [Interval(Integral, 2, None, closed="left"), None],
122 "min_impurity_decrease": [Interval(Real, 0.0, None, closed="left")],
123 "ccp_alpha": [Interval(Real, 0.0, None, closed="left")],
124 "monotonic_cst": ["array-like", None],
125 }
126
127 @abstractmethod
128 def __init__(
129 self,
130 *,
131 criterion,
132 splitter,
133 max_depth,
134 min_samples_split,
135 min_samples_leaf,
136 min_weight_fraction_leaf,
137 max_features,
138 max_leaf_nodes,
139 random_state,
140 min_impurity_decrease,
141 class_weight=None,
142 ccp_alpha=0.0,
143 monotonic_cst=None,
144 ):
145 self.criterion = criterion
146 self.splitter = splitter
147 self.max_depth = max_depth
148 self.min_samples_split = min_samples_split
149 self.min_samples_leaf = min_samples_leaf
150 self.min_weight_fraction_leaf = min_weight_fraction_leaf
151 self.max_features = max_features
152 self.max_leaf_nodes = max_leaf_nodes
153 self.random_state = random_state
154 self.min_impurity_decrease = min_impurity_decrease
155 self.class_weight = class_weight
156 self.ccp_alpha = ccp_alpha
157 self.monotonic_cst = monotonic_cst
158
159 def get_depth(self):
160 """Return the depth of the decision tree.
161
162 The depth of a tree is the maximum distance between the root
163 and any leaf.
164
165 Returns
166 -------
167 self.tree_.max_depth : int
168 The maximum depth of the tree.
169 """
170 check_is_fitted(self)
171 return self.tree_.max_depth
172
173 def get_n_leaves(self):
174 """Return the number of leaves of the decision tree.
175
176 Returns
177 -------
178 self.tree_.n_leaves : int
179 Number of leaves.
180 """
181 check_is_fitted(self)
182 return self.tree_.n_leaves
183
184 def _support_missing_values(self, X):
185 return (
186 not issparse(X)
187 and self.__sklearn_tags__().input_tags.allow_nan
188 and self.monotonic_cst is None
189 )
190
191 def _compute_missing_values_in_feature_mask(self, X, estimator_name=None):
192 """Return boolean mask denoting if there are missing values for each feature.
193
194 This method also ensures that X is finite.
195
196 Parameter
197 ---------
198 X : array-like of shape (n_samples, n_features), dtype=DOUBLE
199 Input data.
200
201 estimator_name : str or None, default=None
202 Name to use when raising an error. Defaults to the class name.
203
204 Returns
205 -------
206 missing_values_in_feature_mask : ndarray of shape (n_features,), or None
207 Missing value mask. If missing values are not supported or there
208 are no missing values, return None.
209 """
210 estimator_name = estimator_name or self.__class__.__name__
211 common_kwargs = dict(estimator_name=estimator_name, input_name="X")
212
213 if not self._support_missing_values(X):
214 assert_all_finite(X, **common_kwargs)
215 return None
216
217 with np.errstate(over="ignore"):
218 overall_sum = np.sum(X)
219
220 if not np.isfinite(overall_sum):
221 # Raise a ValueError in case of the presence of an infinite element.
222 _assert_all_finite_element_wise(X, xp=np, allow_nan=True, **common_kwargs)
223
224 # If the sum is not nan, then there are no missing values
225 if not np.isnan(overall_sum):
226 return None
227
228 missing_values_in_feature_mask = _any_isnan_axis0(X)
229 return missing_values_in_feature_mask
230
231 def _fit(
232 self,
233 X,
234 y,
235 sample_weight=None,
236 check_input=True,
237 missing_values_in_feature_mask=None,
238 ):
239 random_state = check_random_state(self.random_state)
240
241 if check_input:
242 # Need to validate separately here.
243 # We can't pass multi_output=True because that would allow y to be
244 # csr.
245
246 # _compute_missing_values_in_feature_mask will check for finite values and
247 # compute the missing mask if the tree supports missing values
248 check_X_params = dict(
249 dtype=DTYPE, accept_sparse="csc", ensure_all_finite=False
250 )
251 check_y_params = dict(ensure_2d=False, dtype=None)
252 X, y = validate_data(
253 self, X, y, validate_separately=(check_X_params, check_y_params)
254 )
255
256 missing_values_in_feature_mask = (
257 self._compute_missing_values_in_feature_mask(X)
258 )
259 if issparse(X):
260 X.sort_indices()
261
262 if X.indices.dtype != np.intc or X.indptr.dtype != np.intc:
263 raise ValueError(
264 "No support for np.int64 index based sparse matrices"
265 )
266
267 if self.criterion == "poisson":
268 if np.any(y < 0):
269 raise ValueError(
270 "Some value(s) of y are negative which is"
271 " not allowed for Poisson regression."
272 )
273 if np.sum(y) <= 0:
274 raise ValueError(
275 "Sum of y is not positive which is "
276 "necessary for Poisson regression."
277 )
278
279 # Determine output settings
280 n_samples, self.n_features_in_ = X.shape
281 is_classification = is_classifier(self)
282
283 y = np.atleast_1d(y)
284 expanded_class_weight = None
285
286 if y.ndim == 1:
287 # reshape is necessary to preserve the data contiguity against vs
288 # [:, np.newaxis] that does not.
289 y = np.reshape(y, (-1, 1))
290
291 self.n_outputs_ = y.shape[1]
292
293 if is_classification:
294 check_classification_targets(y)
295 y = np.copy(y)
296
297 self.classes_ = []
298 self.n_classes_ = []
299
300 if self.class_weight is not None:
301 y_original = np.copy(y)
302
303 y_encoded = np.zeros(y.shape, dtype=int)
304 for k in range(self.n_outputs_):
305 classes_k, y_encoded[:, k] = np.unique(y[:, k], return_inverse=True)
306 self.classes_.append(classes_k)
307 self.n_classes_.append(classes_k.shape[0])
308 y = y_encoded
309
310 if self.class_weight is not None:
311 expanded_class_weight = compute_sample_weight(
312 self.class_weight, y_original
313 )
314
315 self.n_classes_ = np.array(self.n_classes_, dtype=np.intp)
316
317 if getattr(y, "dtype", None) != DOUBLE or not y.flags.contiguous:
318 y = np.ascontiguousarray(y, dtype=DOUBLE)
319
320 max_depth = np.iinfo(np.int32).max if self.max_depth is None else self.max_depth
321
322 if isinstance(self.min_samples_leaf, numbers.Integral):
323 min_samples_leaf = self.min_samples_leaf
324 else: # float
325 min_samples_leaf = ceil(self.min_samples_leaf * n_samples)
326
327 if isinstance(self.min_samples_split, numbers.Integral):
328 min_samples_split = self.min_samples_split
329 else: # float
330 min_samples_split = ceil(self.min_samples_split * n_samples)
331 min_samples_split = max(2, min_samples_split)
332
333 min_samples_split = max(min_samples_split, 2 * min_samples_leaf)
334
335 if isinstance(self.max_features, str):
336 if self.max_features == "sqrt":
337 max_features = max(1, int(np.sqrt(self.n_features_in_)))
338 elif self.max_features == "log2":
339 max_features = max(1, int(np.log2(self.n_features_in_)))
340 elif self.max_features is None:
341 max_features = self.n_features_in_
342 elif isinstance(self.max_features, numbers.Integral):
343 max_features = self.max_features
344 else: # float
345 if self.max_features > 0.0:
346 max_features = max(1, int(self.max_features * self.n_features_in_))
347 else:
348 max_features = 0
349
350 self.max_features_ = max_features
351
352 max_leaf_nodes = -1 if self.max_leaf_nodes is None else self.max_leaf_nodes
353
354 if len(y) != n_samples:
355 raise ValueError(
356 "Number of labels=%d does not match number of samples=%d"
357 % (len(y), n_samples)
358 )
359
360 if sample_weight is not None:
361 sample_weight = _check_sample_weight(sample_weight, X, dtype=DOUBLE)
362
363 if expanded_class_weight is not None:
364 if sample_weight is not None:
365 sample_weight = sample_weight * expanded_class_weight
366 else:
367 sample_weight = expanded_class_weight
368
369 # Set min_weight_leaf from min_weight_fraction_leaf
370 if sample_weight is None:
371 min_weight_leaf = self.min_weight_fraction_leaf * n_samples
372 else:
373 min_weight_leaf = self.min_weight_fraction_leaf * np.sum(sample_weight)
374
375 # Build tree
376 criterion = self.criterion
377 if not isinstance(criterion, Criterion):
378 if is_classification:
379 criterion = CRITERIA_CLF[self.criterion](
380 self.n_outputs_, self.n_classes_
381 )
382 else:
383 criterion = CRITERIA_REG[self.criterion](self.n_outputs_, n_samples)
384 else:
385 # Make a deepcopy in case the criterion has mutable attributes that
386 # might be shared and modified concurrently during parallel fitting
387 criterion = copy.deepcopy(criterion)
388
389 SPLITTERS = SPARSE_SPLITTERS if issparse(X) else DENSE_SPLITTERS
390
391 splitter = self.splitter
392 if self.monotonic_cst is None:
393 monotonic_cst = None
394 else:
395 if self.n_outputs_ > 1:
396 raise ValueError(
397 "Monotonicity constraints are not supported with multiple outputs."
398 )
399 # Check to correct monotonicity constraint' specification,
400 # by applying element-wise logical conjunction
401 # Note: we do not cast `np.asarray(self.monotonic_cst, dtype=np.int8)`
402 # straight away here so as to generate error messages for invalid
403 # values using the original values prior to any dtype related conversion.
404 monotonic_cst = np.asarray(self.monotonic_cst)
405 if monotonic_cst.shape[0] != X.shape[1]:
406 raise ValueError(
407 "monotonic_cst has shape {} but the input data "
408 "X has {} features.".format(monotonic_cst.shape[0], X.shape[1])
409 )
410 valid_constraints = np.isin(monotonic_cst, (-1, 0, 1))
411 if not np.all(valid_constraints):
412 unique_constaints_value = np.unique(monotonic_cst)
413 raise ValueError(
414 "monotonic_cst must be None or an array-like of -1, 0 or 1, but"
415 f" got {unique_constaints_value}"
416 )
417 monotonic_cst = np.asarray(monotonic_cst, dtype=np.int8)
418 if is_classifier(self):
419 if self.n_classes_[0] > 2:
420 raise ValueError(
421 "Monotonicity constraints are not supported with multiclass "
422 "classification"
423 )
424 # Binary classification trees are built by constraining probabilities
425 # of the *negative class* in order to make the implementation similar
426 # to regression trees.
427 # Since self.monotonic_cst encodes constraints on probabilities of the
428 # *positive class*, all signs must be flipped.
429 monotonic_cst *= -1
430
431 if not isinstance(self.splitter, Splitter):
432 splitter = SPLITTERS[self.splitter](
433 criterion,
434 self.max_features_,
435 min_samples_leaf,
436 min_weight_leaf,
437 random_state,
438 monotonic_cst,
439 )
440
441 if is_classifier(self):
442 self.tree_ = Tree(self.n_features_in_, self.n_classes_, self.n_outputs_)
443 else:
444 self.tree_ = Tree(
445 self.n_features_in_,
446 # TODO: tree shouldn't need this in this case
447 np.array([1] * self.n_outputs_, dtype=np.intp),
448 self.n_outputs_,
449 )
450
451 # Use BestFirst if max_leaf_nodes given; use DepthFirst otherwise
452 if max_leaf_nodes < 0:
453 builder = DepthFirstTreeBuilder(
454 splitter,
455 min_samples_split,
456 min_samples_leaf,
457 min_weight_leaf,
458 max_depth,
459 self.min_impurity_decrease,
460 )
461 else:
462 builder = BestFirstTreeBuilder(
463 splitter,
464 min_samples_split,
465 min_samples_leaf,
466 min_weight_leaf,
467 max_depth,
468 max_leaf_nodes,
469 self.min_impurity_decrease,
470 )
471
472 builder.build(self.tree_, X, y, sample_weight, missing_values_in_feature_mask)
473
474 if self.n_outputs_ == 1 and is_classifier(self):
475 self.n_classes_ = self.n_classes_[0]
476 self.classes_ = self.classes_[0]
477
478 self._prune_tree()
479
480 return self
481
482 def _validate_X_predict(self, X, check_input):
483 """Validate the training data on predict (probabilities)."""
484 if check_input:
485 if self._support_missing_values(X):
486 ensure_all_finite = "allow-nan"
487 else:
488 ensure_all_finite = True
489 X = validate_data(
490 self,
491 X,
492 dtype=DTYPE,
493 accept_sparse="csr",
494 reset=False,
495 ensure_all_finite=ensure_all_finite,
496 )
497 if issparse(X) and (
498 X.indices.dtype != np.intc or X.indptr.dtype != np.intc
499 ):
500 raise ValueError("No support for np.int64 index based sparse matrices")
501 else:
502 # The number of features is checked regardless of `check_input`
503 _check_n_features(self, X, reset=False)
504 return X
505
506 def predict(self, X, check_input=True):
507 """Predict class or regression value for X.
508
509 For a classification model, the predicted class for each sample in X is
510 returned. For a regression model, the predicted value based on X is
511 returned.
512
513 Parameters
514 ----------
515 X : {array-like, sparse matrix} of shape (n_samples, n_features)
516 The input samples. Internally, it will be converted to
517 ``dtype=np.float32`` and if a sparse matrix is provided
518 to a sparse ``csr_matrix``.
519
520 check_input : bool, default=True
521 Allow to bypass several input checking.
522 Don't use this parameter unless you know what you're doing.
523
524 Returns
525 -------
526 y : array-like of shape (n_samples,) or (n_samples, n_outputs)
527 The predicted classes, or the predict values.
528 """
529 check_is_fitted(self)
530 X = self._validate_X_predict(X, check_input)
531 proba = self.tree_.predict(X)
532 n_samples = X.shape[0]
533
534 # Classification
535 if is_classifier(self):
536 if self.n_outputs_ == 1:
537 return self.classes_.take(np.argmax(proba, axis=1), axis=0)
538
539 else:
540 class_type = self.classes_[0].dtype
541 predictions = np.zeros((n_samples, self.n_outputs_), dtype=class_type)
542 for k in range(self.n_outputs_):
543 predictions[:, k] = self.classes_[k].take(
544 np.argmax(proba[:, k], axis=1), axis=0
545 )
546
547 return predictions
548
549 # Regression
550 else:
551 if self.n_outputs_ == 1:
552 return proba[:, 0]
553
554 else:
555 return proba[:, :, 0]
556
557 def apply(self, X, check_input=True):
558 """Return the index of the leaf that each sample is predicted as.
559
560 .. versionadded:: 0.17
561
562 Parameters
563 ----------
564 X : {array-like, sparse matrix} of shape (n_samples, n_features)
565 The input samples. Internally, it will be converted to
566 ``dtype=np.float32`` and if a sparse matrix is provided
567 to a sparse ``csr_matrix``.
568
569 check_input : bool, default=True
570 Allow to bypass several input checking.
571 Don't use this parameter unless you know what you're doing.
572
573 Returns
574 -------
575 X_leaves : array-like of shape (n_samples,)
576 For each datapoint x in X, return the index of the leaf x
577 ends up in. Leaves are numbered within
578 ``[0; self.tree_.node_count)``, possibly with gaps in the
579 numbering.
580 """
581 check_is_fitted(self)
582 X = self._validate_X_predict(X, check_input)
583 return self.tree_.apply(X)
584
585 def decision_path(self, X, check_input=True):
586 """Return the decision path in the tree.
587
588 .. versionadded:: 0.18
589
590 Parameters
591 ----------
592 X : {array-like, sparse matrix} of shape (n_samples, n_features)
593 The input samples. Internally, it will be converted to
594 ``dtype=np.float32`` and if a sparse matrix is provided
595 to a sparse ``csr_matrix``.
596
597 check_input : bool, default=True
598 Allow to bypass several input checking.
599 Don't use this parameter unless you know what you're doing.
600
601 Returns
602 -------
603 indicator : sparse matrix of shape (n_samples, n_nodes)
604 Return a node indicator CSR matrix where non zero elements
605 indicates that the samples goes through the nodes.
606 """
607 X = self._validate_X_predict(X, check_input)
608 return self.tree_.decision_path(X)
609
610 def _prune_tree(self):
611 """Prune tree using Minimal Cost-Complexity Pruning."""
612 check_is_fitted(self)
613
614 if self.ccp_alpha == 0.0:
615 return
616
617 # build pruned tree
618 if is_classifier(self):
619 n_classes = np.atleast_1d(self.n_classes_)
620 pruned_tree = Tree(self.n_features_in_, n_classes, self.n_outputs_)
621 else:
622 pruned_tree = Tree(
623 self.n_features_in_,
624 # TODO: the tree shouldn't need this param
625 np.array([1] * self.n_outputs_, dtype=np.intp),
626 self.n_outputs_,
627 )
628 _build_pruned_tree_ccp(pruned_tree, self.tree_, self.ccp_alpha)
629
630 self.tree_ = pruned_tree
631
632 def cost_complexity_pruning_path(self, X, y, sample_weight=None):
633 """Compute the pruning path during Minimal Cost-Complexity Pruning.
634
635 See :ref:`minimal_cost_complexity_pruning` for details on the pruning
636 process.
637
638 Parameters
639 ----------
640 X : {array-like, sparse matrix} of shape (n_samples, n_features)
641 The training input samples. Internally, it will be converted to
642 ``dtype=np.float32`` and if a sparse matrix is provided
643 to a sparse ``csc_matrix``.
644
645 y : array-like of shape (n_samples,) or (n_samples, n_outputs)
646 The target values (class labels) as integers or strings.
647
648 sample_weight : array-like of shape (n_samples,), default=None
649 Sample weights. If None, then samples are equally weighted. Splits
650 that would create child nodes with net zero or negative weight are
651 ignored while searching for a split in each node. Splits are also
652 ignored if they would result in any single class carrying a
653 negative weight in either child node.
654
655 Returns
656 -------
657 ccp_path : :class:`~sklearn.utils.Bunch`
658 Dictionary-like object, with the following attributes.
659
660 ccp_alphas : ndarray
661 Effective alphas of subtree during pruning.
662
663 impurities : ndarray
664 Sum of the impurities of the subtree leaves for the
665 corresponding alpha value in ``ccp_alphas``.
666 """
667 est = clone(self).set_params(ccp_alpha=0.0)
668 est.fit(X, y, sample_weight=sample_weight)
669 return Bunch(**ccp_pruning_path(est.tree_))
670
671 @property
672 def feature_importances_(self):
673 """Return the feature importances.
674
675 The importance of a feature is computed as the (normalized) total
676 reduction of the criterion brought by that feature.
677 It is also known as the Gini importance.
678
679 Warning: impurity-based feature importances can be misleading for
680 high cardinality features (many unique values). See
681 :func:`sklearn.inspection.permutation_importance` as an alternative.
682
683 Returns
684 -------
685 feature_importances_ : ndarray of shape (n_features,)
686 Normalized total reduction of criteria by feature
687 (Gini importance).
688 """
689 check_is_fitted(self)
690
691 return self.tree_.compute_feature_importances()
692
693 def __sklearn_tags__(self):
694 tags = super().__sklearn_tags__()
695 tags.input_tags.sparse = True
696 return tags
697
698
699# =============================================================================
700# Public estimators
701# =============================================================================
702
703
704class DecisionTreeClassifier(ClassifierMixin, BaseDecisionTree):
705 """A decision tree classifier.
706
707 Read more in the :ref:`User Guide <tree>`.
708
709 Parameters
710 ----------
711 criterion : {"gini", "entropy", "log_loss"}, default="gini"
712 The function to measure the quality of a split. Supported criteria are
713 "gini" for the Gini impurity and "log_loss" and "entropy" both for the
714 Shannon information gain, see :ref:`tree_mathematical_formulation`.
715
716 splitter : {"best", "random"}, default="best"
717 The strategy used to choose the split at each node. Supported
718 strategies are "best" to choose the best split and "random" to choose
719 the best random split.
720
721 max_depth : int, default=None
722 The maximum depth of the tree. If None, then nodes are expanded until
723 all leaves are pure or until all leaves contain less than
724 min_samples_split samples.
725
726 min_samples_split : int or float, default=2
727 The minimum number of samples required to split an internal node:
728
729 - If int, then consider `min_samples_split` as the minimum number.
730 - If float, then `min_samples_split` is a fraction and
731 `ceil(min_samples_split * n_samples)` are the minimum
732 number of samples for each split.
733
734 .. versionchanged:: 0.18
735 Added float values for fractions.
736
737 min_samples_leaf : int or float, default=1
738 The minimum number of samples required to be at a leaf node.
739 A split point at any depth will only be considered if it leaves at
740 least ``min_samples_leaf`` training samples in each of the left and
741 right branches. This may have the effect of smoothing the model,
742 especially in regression.
743
744 - If int, then consider `min_samples_leaf` as the minimum number.
745 - If float, then `min_samples_leaf` is a fraction and
746 `ceil(min_samples_leaf * n_samples)` are the minimum
747 number of samples for each node.
748
749 .. versionchanged:: 0.18
750 Added float values for fractions.
751
752 min_weight_fraction_leaf : float, default=0.0
753 The minimum weighted fraction of the sum total of weights (of all
754 the input samples) required to be at a leaf node. Samples have
755 equal weight when sample_weight is not provided.
756
757 max_features : int, float or {"sqrt", "log2"}, default=None
758 The number of features to consider when looking for the best split:
759
760 - If int, then consider `max_features` features at each split.
761 - If float, then `max_features` is a fraction and
762 `max(1, int(max_features * n_features_in_))` features are considered at
763 each split.
764 - If "sqrt", then `max_features=sqrt(n_features)`.
765 - If "log2", then `max_features=log2(n_features)`.
766 - If None, then `max_features=n_features`.
767
768 .. note::
769
770 The search for a split does not stop until at least one
771 valid partition of the node samples is found, even if it requires to
772 effectively inspect more than ``max_features`` features.
773
774 random_state : int, RandomState instance or None, default=None
775 Controls the randomness of the estimator. The features are always
776 randomly permuted at each split, even if ``splitter`` is set to
777 ``"best"``. When ``max_features < n_features``, the algorithm will
778 select ``max_features`` at random at each split before finding the best
779 split among them. But the best found split may vary across different
780 runs, even if ``max_features=n_features``. That is the case, if the
781 improvement of the criterion is identical for several splits and one
782 split has to be selected at random. To obtain a deterministic behaviour
783 during fitting, ``random_state`` has to be fixed to an integer.
784 See :term:`Glossary <random_state>` for details.
785
786 max_leaf_nodes : int, default=None
787 Grow a tree with ``max_leaf_nodes`` in best-first fashion.
788 Best nodes are defined as relative reduction in impurity.
789 If None then unlimited number of leaf nodes.
790
791 min_impurity_decrease : float, default=0.0
792 A node will be split if this split induces a decrease of the impurity
793 greater than or equal to this value.
794
795 The weighted impurity decrease equation is the following::
796
797 N_t / N * (impurity - N_t_R / N_t * right_impurity
798 - N_t_L / N_t * left_impurity)
799
800 where ``N`` is the total number of samples, ``N_t`` is the number of
801 samples at the current node, ``N_t_L`` is the number of samples in the
802 left child, and ``N_t_R`` is the number of samples in the right child.
803
804 ``N``, ``N_t``, ``N_t_R`` and ``N_t_L`` all refer to the weighted sum,
805 if ``sample_weight`` is passed.
806
807 .. versionadded:: 0.19
808
809 class_weight : dict, list of dict or "balanced", default=None
810 Weights associated with classes in the form ``{class_label: weight}``.
811 If None, all classes are supposed to have weight one. For
812 multi-output problems, a list of dicts can be provided in the same
813 order as the columns of y.
814
815 Note that for multioutput (including multilabel) weights should be
816 defined for each class of every column in its own dict. For example,
817 for four-class multilabel classification weights should be
818 [{0: 1, 1: 1}, {0: 1, 1: 5}, {0: 1, 1: 1}, {0: 1, 1: 1}] instead of
819 [{1:1}, {2:5}, {3:1}, {4:1}].
820
821 The "balanced" mode uses the values of y to automatically adjust
822 weights inversely proportional to class frequencies in the input data
823 as ``n_samples / (n_classes * np.bincount(y))``
824
825 For multi-output, the weights of each column of y will be multiplied.
826
827 Note that these weights will be multiplied with sample_weight (passed
828 through the fit method) if sample_weight is specified.
829
830 ccp_alpha : non-negative float, default=0.0
831 Complexity parameter used for Minimal Cost-Complexity Pruning. The
832 subtree with the largest cost complexity that is smaller than
833 ``ccp_alpha`` will be chosen. By default, no pruning is performed. See
834 :ref:`minimal_cost_complexity_pruning` for details. See
835 :ref:`sphx_glr_auto_examples_tree_plot_cost_complexity_pruning.py`
836 for an example of such pruning.
837
838 .. versionadded:: 0.22
839
840 monotonic_cst : array-like of int of shape (n_features), default=None
841 Indicates the monotonicity constraint to enforce on each feature.
842 - 1: monotonic increase
843 - 0: no constraint
844 - -1: monotonic decrease
845
846 If monotonic_cst is None, no constraints are applied.
847
848 Monotonicity constraints are not supported for:
849 - multiclass classifications (i.e. when `n_classes > 2`),
850 - multioutput classifications (i.e. when `n_outputs_ > 1`),
851 - classifications trained on data with missing values.
852
853 The constraints hold over the probability of the positive class.
854
855 Read more in the :ref:`User Guide <monotonic_cst_gbdt>`.
856
857 .. versionadded:: 1.4
858
859 Attributes
860 ----------
861 classes_ : ndarray of shape (n_classes,) or list of ndarray
862 The classes labels (single output problem),
863 or a list of arrays of class labels (multi-output problem).
864
865 feature_importances_ : ndarray of shape (n_features,)
866 The impurity-based feature importances.
867 The higher, the more important the feature.
868 The importance of a feature is computed as the (normalized)
869 total reduction of the criterion brought by that feature. It is also
870 known as the Gini importance [4]_.
871
872 Warning: impurity-based feature importances can be misleading for
873 high cardinality features (many unique values). See
874 :func:`sklearn.inspection.permutation_importance` as an alternative.
875
876 max_features_ : int
877 The inferred value of max_features.
878
879 n_classes_ : int or list of int
880 The number of classes (for single output problems),
881 or a list containing the number of classes for each
882 output (for multi-output problems).
883
884 n_features_in_ : int
885 Number of features seen during :term:`fit`.
886
887 .. versionadded:: 0.24
888
889 feature_names_in_ : ndarray of shape (`n_features_in_`,)
890 Names of features seen during :term:`fit`. Defined only when `X`
891 has feature names that are all strings.
892
893 .. versionadded:: 1.0
894
895 n_outputs_ : int
896 The number of outputs when ``fit`` is performed.
897
898 tree_ : Tree instance
899 The underlying Tree object. Please refer to
900 ``help(sklearn.tree._tree.Tree)`` for attributes of Tree object and
901 :ref:`sphx_glr_auto_examples_tree_plot_unveil_tree_structure.py`
902 for basic usage of these attributes.
903
904 See Also
905 --------
906 DecisionTreeRegressor : A decision tree regressor.
907
908 Notes
909 -----
910 The default values for the parameters controlling the size of the trees
911 (e.g. ``max_depth``, ``min_samples_leaf``, etc.) lead to fully grown and
912 unpruned trees which can potentially be very large on some data sets. To
913 reduce memory consumption, the complexity and size of the trees should be
914 controlled by setting those parameter values.
915
916 The :meth:`predict` method operates using the :func:`numpy.argmax`
917 function on the outputs of :meth:`predict_proba`. This means that in
918 case the highest predicted probabilities are tied, the classifier will
919 predict the tied class with the lowest index in :term:`classes_`.
920
921 References
922 ----------
923
924 .. [1] https://en.wikipedia.org/wiki/Decision_tree_learning
925
926 .. [2] L. Breiman, J. Friedman, R. Olshen, and C. Stone, "Classification
927 and Regression Trees", Wadsworth, Belmont, CA, 1984.
928
929 .. [3] T. Hastie, R. Tibshirani and J. Friedman. "Elements of Statistical
930 Learning", Springer, 2009.
931
932 .. [4] L. Breiman, and A. Cutler, "Random Forests",
933 https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm
934
935 Examples
936 --------
937 >>> from sklearn.datasets import load_iris
938 >>> from sklearn.model_selection import cross_val_score
939 >>> from sklearn.tree import DecisionTreeClassifier
940 >>> clf = DecisionTreeClassifier(random_state=0)
941 >>> iris = load_iris()
942 >>> cross_val_score(clf, iris.data, iris.target, cv=10)
943 ... # doctest: +SKIP
944 ...
945 array([ 1. , 0.93, 0.86, 0.93, 0.93,
946 0.93, 0.93, 1. , 0.93, 1. ])
947 """
948
949 # "check_input" is used for optimisation and isn't something to be passed
950 # around in a pipeline.
951 __metadata_request__predict_proba = {"check_input": metadata_routing.UNUSED}
952 __metadata_request__fit = {"check_input": metadata_routing.UNUSED}
953
954 _parameter_constraints: dict = {
955 **BaseDecisionTree._parameter_constraints,
956 "criterion": [StrOptions({"gini", "entropy", "log_loss"}), Hidden(Criterion)],
957 "class_weight": [dict, list, StrOptions({"balanced"}), None],
958 }
959
960 def __init__(
961 self,
962 *,
963 criterion="gini",
964 splitter="best",
965 max_depth=None,
966 min_samples_split=2,
967 min_samples_leaf=1,
968 min_weight_fraction_leaf=0.0,
969 max_features=None,
970 random_state=None,
971 max_leaf_nodes=None,
972 min_impurity_decrease=0.0,
973 class_weight=None,
974 ccp_alpha=0.0,
975 monotonic_cst=None,
976 ):
977 super().__init__(
978 criterion=criterion,
979 splitter=splitter,
980 max_depth=max_depth,
981 min_samples_split=min_samples_split,
982 min_samples_leaf=min_samples_leaf,
983 min_weight_fraction_leaf=min_weight_fraction_leaf,
984 max_features=max_features,
985 max_leaf_nodes=max_leaf_nodes,
986 class_weight=class_weight,
987 random_state=random_state,
988 min_impurity_decrease=min_impurity_decrease,
989 monotonic_cst=monotonic_cst,
990 ccp_alpha=ccp_alpha,
991 )
992
993 @_fit_context(prefer_skip_nested_validation=True)
994 def fit(self, X, y, sample_weight=None, check_input=True):
995 """Build a decision tree classifier from the training set (X, y).
996
997 Parameters
998 ----------
999 X : {array-like, sparse matrix} of shape (n_samples, n_features)
1000 The training input samples. Internally, it will be converted to
1001 ``dtype=np.float32`` and if a sparse matrix is provided
1002 to a sparse ``csc_matrix``.
1003
1004 y : array-like of shape (n_samples,) or (n_samples, n_outputs)
1005 The target values (class labels) as integers or strings.
1006
1007 sample_weight : array-like of shape (n_samples,), default=None
1008 Sample weights. If None, then samples are equally weighted. Splits
1009 that would create child nodes with net zero or negative weight are
1010 ignored while searching for a split in each node. Splits are also
1011 ignored if they would result in any single class carrying a
1012 negative weight in either child node.
1013
1014 check_input : bool, default=True
1015 Allow to bypass several input checking.
1016 Don't use this parameter unless you know what you're doing.
1017
1018 Returns
1019 -------
1020 self : DecisionTreeClassifier
1021 Fitted estimator.
1022 """
1023
1024 super()._fit(
1025 X,
1026 y,
1027 sample_weight=sample_weight,
1028 check_input=check_input,
1029 )
1030 return self
1031
1032 def predict_proba(self, X, check_input=True):
1033 """Predict class probabilities of the input samples X.
1034
1035 The predicted class probability is the fraction of samples of the same
1036 class in a leaf.
1037
1038 Parameters
1039 ----------
1040 X : {array-like, sparse matrix} of shape (n_samples, n_features)
1041 The input samples. Internally, it will be converted to
1042 ``dtype=np.float32`` and if a sparse matrix is provided
1043 to a sparse ``csr_matrix``.
1044
1045 check_input : bool, default=True
1046 Allow to bypass several input checking.
1047 Don't use this parameter unless you know what you're doing.
1048
1049 Returns
1050 -------
1051 proba : ndarray of shape (n_samples, n_classes) or list of n_outputs \
1052 such arrays if n_outputs > 1
1053 The class probabilities of the input samples. The order of the
1054 classes corresponds to that in the attribute :term:`classes_`.
1055 """
1056 check_is_fitted(self)
1057 X = self._validate_X_predict(X, check_input)
1058 proba = self.tree_.predict(X)
1059
1060 if self.n_outputs_ == 1:
1061 return proba[:, : self.n_classes_]
1062 else:
1063 all_proba = []
1064 for k in range(self.n_outputs_):
1065 proba_k = proba[:, k, : self.n_classes_[k]]
1066 all_proba.append(proba_k)
1067 return all_proba
1068
1069 def predict_log_proba(self, X):
1070 """Predict class log-probabilities of the input samples X.
1071
1072 Parameters
1073 ----------
1074 X : {array-like, sparse matrix} of shape (n_samples, n_features)
1075 The input samples. Internally, it will be converted to
1076 ``dtype=np.float32`` and if a sparse matrix is provided
1077 to a sparse ``csr_matrix``.
1078
1079 Returns
1080 -------
1081 proba : ndarray of shape (n_samples, n_classes) or list of n_outputs \
1082 such arrays if n_outputs > 1
1083 The class log-probabilities of the input samples. The order of the
1084 classes corresponds to that in the attribute :term:`classes_`.
1085 """
1086 proba = self.predict_proba(X)
1087
1088 if self.n_outputs_ == 1:
1089 return np.log(proba)
1090
1091 else:
1092 for k in range(self.n_outputs_):
1093 proba[k] = np.log(proba[k])
1094
1095 return proba
1096
1097 def __sklearn_tags__(self):
1098 tags = super().__sklearn_tags__()
1099 # XXX: nan is only support for dense arrays, but we set this for common test to
1100 # pass, specifically: check_estimators_nan_inf
1101 allow_nan = self.splitter in ("best", "random") and self.criterion in {
1102 "gini",
1103 "log_loss",
1104 "entropy",
1105 }
1106 tags.classifier_tags.multi_label = True
1107 tags.input_tags.allow_nan = allow_nan
1108 return tags
1109
1110
1111class DecisionTreeRegressor(RegressorMixin, BaseDecisionTree):
1112 """A decision tree regressor.
1113
1114 Read more in the :ref:`User Guide <tree>`.
1115
1116 Parameters
1117 ----------
1118 criterion : {"squared_error", "friedman_mse", "absolute_error", \
1119 "poisson"}, default="squared_error"
1120 The function to measure the quality of a split. Supported criteria
1121 are "squared_error" for the mean squared error, which is equal to
1122 variance reduction as feature selection criterion and minimizes the L2
1123 loss using the mean of each terminal node, "friedman_mse", which uses
1124 mean squared error with Friedman's improvement score for potential
1125 splits, "absolute_error" for the mean absolute error, which minimizes
1126 the L1 loss using the median of each terminal node, and "poisson" which
1127 uses reduction in the half mean Poisson deviance to find splits.
1128
1129 .. versionadded:: 0.18
1130 Mean Absolute Error (MAE) criterion.
1131
1132 .. versionadded:: 0.24
1133 Poisson deviance criterion.
1134
1135 splitter : {"best", "random"}, default="best"
1136 The strategy used to choose the split at each node. Supported
1137 strategies are "best" to choose the best split and "random" to choose
1138 the best random split.
1139
1140 max_depth : int, default=None
1141 The maximum depth of the tree. If None, then nodes are expanded until
1142 all leaves are pure or until all leaves contain less than
1143 min_samples_split samples.
1144
1145 For an example of how ``max_depth`` influences the model, see
1146 :ref:`sphx_glr_auto_examples_tree_plot_tree_regression.py`.
1147
1148 min_samples_split : int or float, default=2
1149 The minimum number of samples required to split an internal node:
1150
1151 - If int, then consider `min_samples_split` as the minimum number.
1152 - If float, then `min_samples_split` is a fraction and
1153 `ceil(min_samples_split * n_samples)` are the minimum
1154 number of samples for each split.
1155
1156 .. versionchanged:: 0.18
1157 Added float values for fractions.
1158
1159 min_samples_leaf : int or float, default=1
1160 The minimum number of samples required to be at a leaf node.
1161 A split point at any depth will only be considered if it leaves at
1162 least ``min_samples_leaf`` training samples in each of the left and
1163 right branches. This may have the effect of smoothing the model,
1164 especially in regression.
1165
1166 - If int, then consider `min_samples_leaf` as the minimum number.
1167 - If float, then `min_samples_leaf` is a fraction and
1168 `ceil(min_samples_leaf * n_samples)` are the minimum
1169 number of samples for each node.
1170
1171 .. versionchanged:: 0.18
1172 Added float values for fractions.
1173
1174 min_weight_fraction_leaf : float, default=0.0
1175 The minimum weighted fraction of the sum total of weights (of all
1176 the input samples) required to be at a leaf node. Samples have
1177 equal weight when sample_weight is not provided.
1178
1179 max_features : int, float or {"sqrt", "log2"}, default=None
1180 The number of features to consider when looking for the best split:
1181
1182 - If int, then consider `max_features` features at each split.
1183 - If float, then `max_features` is a fraction and
1184 `max(1, int(max_features * n_features_in_))` features are considered at each
1185 split.
1186 - If "sqrt", then `max_features=sqrt(n_features)`.
1187 - If "log2", then `max_features=log2(n_features)`.
1188 - If None, then `max_features=n_features`.
1189
1190 Note: the search for a split does not stop until at least one
1191 valid partition of the node samples is found, even if it requires to
1192 effectively inspect more than ``max_features`` features.
1193
1194 random_state : int, RandomState instance or None, default=None
1195 Controls the randomness of the estimator. The features are always
1196 randomly permuted at each split, even if ``splitter`` is set to
1197 ``"best"``. When ``max_features < n_features``, the algorithm will
1198 select ``max_features`` at random at each split before finding the best
1199 split among them. But the best found split may vary across different
1200 runs, even if ``max_features=n_features``. That is the case, if the