Repository: scikit-learn/scikit-learn
Pull request: [MRG+2] Tree MAE fix to ensure sample_weights are used during impurity calculation
Tree MAE is not considering sample_weights when calculating impurity!

In the proposed fix, you will see I have multiplied by the sample weight after applying the absolute to the difference (not before). This is in line with the consensus / discussion found here, where negative sample weights are considered: #3774 (and also because during initialisation, self.weighted_n_node_samples is a summation of the sample weights with no "absolute" applied (this is used in the impurity division calc)).

#### Reference Issues/PRs
<!--
Example: Fixes #1234. See also #3456.
Please use keywords (e.g., Fixes) to create link to the issues or pull requests
you resolved, so that they will automatically be closed when your pull request
is merged. See https://github.com/blog/1506-closing-issues-via-pull-requests
-->
Fixes: #11460 (Tree MAE is not considering sample_weights when calculating impurity!)


Problem statement:
Tree MAE is not considering sample_weights when calculating impurity!
This is clearly visible by looking at the code in _criterion.pyx -> class MAE -> children_impurity and node_impurity.

I will shortly provide a pull request link with a fix for the above... I have created this issue so that impacts of negative sample weights can be discussed (if necessary)?

Hints from issue discussion:
In the proposed fix, you will see I have multiplied by the sample weight *after* applying the absolute to the difference (not before).  This is in line with the consensus / discussion found here, where negative sample weights are considered: https://github.com/scikit-learn/scikit-learn/issues/3774 (and also because during initialisation, self.weighted_n_node_samples is a summation of the sample weights with no "absolute" applied (this is used in the impurity division calc)).

Commit message: Removed unnecessary explicits

Patch to review:
diff --git a/doc/whats_new/v0.20.rst b/doc/whats_new/v0.20.rst
index 27c9641dec3de..0f248c810e4fd 100644
--- a/doc/whats_new/v0.20.rst
+++ b/doc/whats_new/v0.20.rst
@@ -513,6 +513,12 @@ Classifiers and regressors
   per-tree basis. The previous behavior over-weighted the Gini importance of
   features that appear in later stages. This issue only affected feature
   importances. :issue:`11176` by :user:`Gil Forsyth <gforsyth>`.
+  
+- Fixed a bug in :class:`tree.MAE` to ensure sample_weights are being used 
+  during the calculation of tree MAE impurity. Previous behaviour could 
+  cause suboptimal splits to be chosen since the impurity calculation 
+  considered all samples to be of equal weight importance.
+  :issue:`11464` by :user:`John Stott <JohnStott>`.  
 
 Decomposition, manifold learning and clustering
 
diff --git a/sklearn/tree/_criterion.pyx b/sklearn/tree/_criterion.pyx
index f47aa73e6e792..e64df8159056b 100644
--- a/sklearn/tree/_criterion.pyx
+++ b/sklearn/tree/_criterion.pyx
@@ -1238,9 +1238,8 @@ cdef class MAE(RegressionCriterion):
         cdef SIZE_t* samples = self.samples
         cdef SIZE_t i, p, k
         cdef DOUBLE_t y_ik
-        cdef DOUBLE_t w_y_ik
-
-        cdef double impurity = 0.0
+        cdef DOUBLE_t w = 1.0
+        cdef DOUBLE_t impurity = 0.0
 
         for k in range(self.n_outputs):
             for p in range(self.start, self.end):
@@ -1248,7 +1247,11 @@ cdef class MAE(RegressionCriterion):
 
                 y_ik = y[i * self.y_stride + k]
 
-                impurity += <double> fabs((<double> y_ik) - <double> self.node_medians[k])
+                if sample_weight != NULL:
+                    w = sample_weight[i]
+
+                impurity += fabs(y_ik - self.node_medians[k]) * w
+
         return impurity / (self.weighted_n_node_samples * self.n_outputs)
 
     cdef void children_impurity(self, double* impurity_left,
@@ -1269,6 +1272,9 @@ cdef class MAE(RegressionCriterion):
         cdef SIZE_t i, p, k
         cdef DOUBLE_t y_ik
         cdef DOUBLE_t median
+        cdef DOUBLE_t w = 1.0
+        cdef DOUBLE_t imp_left = 0.0
+        cdef DOUBLE_t imp_right = 0.0
 
         cdef void** left_child = <void**> self.left_child.data
         cdef void** right_child = <void**> self.right_child.data
@@ -1283,9 +1289,11 @@ cdef class MAE(RegressionCriterion):
 
                 y_ik = y[i * self.y_stride + k]
 
-                impurity_left[0] += <double>fabs((<double> y_ik) -
-                                                 <double> median)
-        impurity_left[0] /= <double>((self.weighted_n_left) * self.n_outputs)
+                if sample_weight != NULL:
+                    w = sample_weight[i]
+
+                imp_left += fabs(y_ik - median) * w
+        impurity_left[0] = imp_left / (self.weighted_n_left * self.n_outputs)
 
         for k in range(self.n_outputs):
             median = (<WeightedMedianCalculator> right_child[k]).get_median()
@@ -1294,10 +1302,11 @@ cdef class MAE(RegressionCriterion):
 
                 y_ik = y[i * self.y_stride + k]
 
-                impurity_right[0] += <double>fabs((<double> y_ik) -
-                                                  <double> median)
-        impurity_right[0] /= <double>((self.weighted_n_right) *
-                                      self.n_outputs)
+                if sample_weight != NULL:
+                    w = sample_weight[i]
+
+                imp_right += fabs(y_ik - median) * w
+        impurity_right[0] = imp_right / (self.weighted_n_right * self.n_outputs)
 
 
 cdef class FriedmanMSE(MSE):
diff --git a/sklearn/tree/tests/test_tree.py b/sklearn/tree/tests/test_tree.py
index bb117d8a29863..835892731db01 100644
--- a/sklearn/tree/tests/test_tree.py
+++ b/sklearn/tree/tests/test_tree.py
@@ -1698,12 +1698,13 @@ def test_mae():
     dt_mae = DecisionTreeRegressor(random_state=0, criterion="mae",
                                    max_leaf_nodes=2)
     dt_mae.fit([[3], [5], [3], [8], [5]], [6, 7, 3, 4, 3])
-    assert_array_equal(dt_mae.tree_.impurity, [1.4, 1.5, 4.0/3.0])
+    assert_array_equal(dt_mae.tree_.impurity, [1.4, 1.5, 4.0 / 3.0])
     assert_array_equal(dt_mae.tree_.value.flat, [4, 4.5, 4.0])
 
     dt_mae.fit([[3], [5], [3], [8], [5]], [6, 7, 3, 4, 3],
                [0.6, 0.3, 0.1, 1.0, 0.3])
-    assert_array_equal(dt_mae.tree_.impurity, [7.0/2.3, 3.0/0.7, 4.0/1.6])
+    assert_array_almost_equal(dt_mae.tree_.impurity,
+                              [2.5 / 2.3, 0.3 / 0.7, 1.2 / 1.6])
     assert_array_equal(dt_mae.tree_.value.flat, [4.0, 6.0, 4.0])
 
 


Code review comments:
diff_hunk: @@ -513,6 +513,12 @@ Classifiers and regressors
   per-tree basis. The previous behavior over-weighted the Gini importance of
   features that appear in later stages. This issue only affected feature
   importances. :issue:`11176` by :user:`Gil Forsyth <gforsyth>`.
+  
+- Fixed a bug in :class:`tree.MAE` to ensure sample_weights are being used 
path: doc/whats_new/v0.20.rst
text: @user1:
use backticks around sample_weights

@author:
English wise, it didn't quite look right `sample_weight`s (with plurality) so changed to plain English (no parameter reference).

diff_hunk: @@ -1269,6 +1272,9 @@ cdef class MAE(RegressionCriterion):
         cdef SIZE_t i, p, k
         cdef DOUBLE_t y_ik
         cdef DOUBLE_t median
+        cdef DOUBLE_t w = 1.0
+        cdef DOUBLE_t imp_left = 0.0
path: sklearn/tree/_criterion.pyx
text: @user1:
can you call `imp_left` to `impurity_left` and `impurity_left` to `p_impurity_left` to differentiate which one is the pointer and like this both name will be explicit.
The same thing should be done for the `right`.

@author:
Done 👍

diff_hunk: @@ -1698,12 +1698,13 @@ def test_mae():
     dt_mae = DecisionTreeRegressor(random_state=0, criterion="mae",
                                    max_leaf_nodes=2)
     dt_mae.fit([[3], [5], [3], [8], [5]], [6, 7, 3, 4, 3])
-    assert_array_equal(dt_mae.tree_.impurity, [1.4, 1.5, 4.0/3.0])
+    assert_array_equal(dt_mae.tree_.impurity, [1.4, 1.5, 4.0 / 3.0])
     assert_array_equal(dt_mae.tree_.value.flat, [4, 4.5, 4.0])
 
     dt_mae.fit([[3], [5], [3], [8], [5]], [6, 7, 3, 4, 3],
                [0.6, 0.3, 0.1, 1.0, 0.3])
-    assert_array_equal(dt_mae.tree_.impurity, [7.0/2.3, 3.0/0.7, 4.0/1.6])
+    assert_array_almost_equal(dt_mae.tree_.impurity,
path: sklearn/tree/tests/test_tree.py
text: @user1:
we should probably add the case where we have the same sample_weight (array of one) which should give the previous results as well.

@author:
Good point, added (with additional comments too)