This is an automated email from the ASF dual-hosted git repository.
zhengruifeng pushed a commit to branch branch-4.x
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/branch-4.x by this push:
new 192d5cfa97c6 [SPARK-58896][4.X][ML] Compute decision tree model stats
in one traversal
192d5cfa97c6 is described below
commit 192d5cfa97c684e9fbe9eb891c44f25782fce8ce
Author: Ruifeng Zheng <[email protected]>
AuthorDate: Fri Aug 21 15:53:45 2026 +0800
[SPARK-58896][4.X][ML] Compute decision tree model stats in one traversal
### What changes were proposed in this pull request?
This PR backports #58147 to `branch-4.x`.
It computes decision tree model stats in a single traversal of the root
node. It adds
`Node.computeStats`, which returns a `NodeStats` value containing the
subtree depth, number of
descendants, and number of leaves. Decision tree classification and
regression models compute
these stats once and `DecisionTreeModel` reuses them for `numNodes`,
`depth`, and leaf metadata.
This also renames the package-private `numLeave` helper to `numLeaves`. In
this backport, the
MiMa exclusions are placed in the 4.4 compatibility section.
### Why are the changes needed?
Before this change, decision tree model metadata could traverse the tree
separately for depth,
node count, and leaf count. Computing these values together avoids
redundant tree walks.
### Does this PR introduce _any_ user-facing change?
No.
### How was this patch tested?
Manually tested with:
```
git diff --check upstream/branch-4.x...HEAD
git diff -U0 upstream/branch-4.x...HEAD -- '*.scala' | awk '/^\+[^+]/ {
line=substr($0, 2); if (length(line)>100 && line !~
/^[[:space:]]*(import|package) / && line !~ /https?:\/\//) print
FILENAME":"NR": "length(line)" chars: "line }'
git diff -U0 upstream/branch-4.x...HEAD -- '*.scala' | awk '/^\+[^+]/ &&
/[^\x00-\x7F]/ { print }'
```
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: OpenAI Codex
Closes #58184 from zhengruifeng/backport-58147-4x.
Authored-by: Ruifeng Zheng <[email protected]>
Signed-off-by: Ruifeng Zheng <[email protected]>
---
.../ml/classification/DecisionTreeClassifier.scala | 2 ++
.../ml/regression/DecisionTreeRegressor.scala | 2 ++
.../main/scala/org/apache/spark/ml/tree/Node.scala | 28 ++++++++++++++++++++++
.../org/apache/spark/ml/tree/treeModels.scala | 18 +++++---------
.../DecisionTreeClassifierSuite.scala | 2 +-
project/MimaExcludes.scala | 9 ++++++-
6 files changed, 47 insertions(+), 14 deletions(-)
diff --git
a/mllib/src/main/scala/org/apache/spark/ml/classification/DecisionTreeClassifier.scala
b/mllib/src/main/scala/org/apache/spark/ml/classification/DecisionTreeClassifier.scala
index 2a4abda7d9ef..78b747f65f2f 100644
---
a/mllib/src/main/scala/org/apache/spark/ml/classification/DecisionTreeClassifier.scala
+++
b/mllib/src/main/scala/org/apache/spark/ml/classification/DecisionTreeClassifier.scala
@@ -201,6 +201,8 @@ class DecisionTreeClassificationModel private[ml] (
// For ml connect only
private[ml] def this() = this("", Node.dummyNode, -1, -1)
+ override private[ml] val treeStats: NodeStats = rootNode.computeStats
+
private[spark] override def estimatedSize: Long = estimateMatadataSize +
getEstimatedSize()
override def predict(features: Vector): Double = {
diff --git
a/mllib/src/main/scala/org/apache/spark/ml/regression/DecisionTreeRegressor.scala
b/mllib/src/main/scala/org/apache/spark/ml/regression/DecisionTreeRegressor.scala
index 6a9da904b9c0..dc2377166e17 100644
---
a/mllib/src/main/scala/org/apache/spark/ml/regression/DecisionTreeRegressor.scala
+++
b/mllib/src/main/scala/org/apache/spark/ml/regression/DecisionTreeRegressor.scala
@@ -190,6 +190,8 @@ class DecisionTreeRegressionModel private[ml] (
// For ml connect only
private[ml] def this() = this("", Node.dummyNode, -1)
+ override private[ml] val treeStats: NodeStats = rootNode.computeStats
+
private[spark] override def estimatedSize: Long = estimateMatadataSize +
getEstimatedSize()
override def predict(features: Vector): Double = {
diff --git a/mllib/src/main/scala/org/apache/spark/ml/tree/Node.scala
b/mllib/src/main/scala/org/apache/spark/ml/tree/Node.scala
index 50978d2e6515..72da973b5c0d 100644
--- a/mllib/src/main/scala/org/apache/spark/ml/tree/Node.scala
+++ b/mllib/src/main/scala/org/apache/spark/ml/tree/Node.scala
@@ -77,8 +77,36 @@ sealed abstract class Node extends Serializable {
* @return Max feature index used in a split, or -1 if there are no splits
(single leaf node).
*/
private[ml] def maxSplitFeatureIndex(): Int
+
+ private[ml] def computeStats: NodeStats = {
+ var numDescendants = 0
+ var subtreeDepth = 0
+ var numLeaves = 0
+
+ def visit(node: Node, depth: Int): Unit = {
+ if (depth > 0) {
+ numDescendants += 1
+ }
+ subtreeDepth = math.max(subtreeDepth, depth)
+ node match {
+ case _: LeafNode =>
+ numLeaves += 1
+ case internal: InternalNode =>
+ visit(internal.leftChild, depth + 1)
+ visit(internal.rightChild, depth + 1)
+ }
+ }
+
+ visit(this, 0)
+ NodeStats(subtreeDepth, numDescendants, numLeaves)
+ }
}
+private[ml] case class NodeStats(
+ subtreeDepth: Int,
+ numDescendants: Int,
+ numLeaves: Int)
+
private[ml] object Node {
/**
diff --git a/mllib/src/main/scala/org/apache/spark/ml/tree/treeModels.scala
b/mllib/src/main/scala/org/apache/spark/ml/tree/treeModels.scala
index 0a3d379ddda2..ca923a1f751f 100644
--- a/mllib/src/main/scala/org/apache/spark/ml/tree/treeModels.scala
+++ b/mllib/src/main/scala/org/apache/spark/ml/tree/treeModels.scala
@@ -49,17 +49,13 @@ private[spark] trait DecisionTreeModel {
def rootNode: Node
/** Number of nodes in tree, including leaf nodes. */
- def numNodes: Int = {
- 1 + rootNode.numDescendants
- }
+ def numNodes: Int = treeStats.numDescendants + 1
/**
* Depth of the tree.
* E.g.: Depth 0 means 1 leaf node. Depth 1 means 1 internal node and 2
leaf nodes.
*/
- lazy val depth: Int = {
- rootNode.subtreeDepth
- }
+ def depth: Int = treeStats.subtreeDepth
/** Summary of the model */
override def toString: String = {
@@ -95,13 +91,11 @@ private[spark] trait DecisionTreeModel {
}
}
- private[ml] lazy val numLeave: Int =
- leafIterator(rootNode).size
+ private[ml] def treeStats: NodeStats
- private[ml] def leafAttr = {
- NominalAttribute.defaultAttr
- .withNumValues(numLeave)
- }
+ private[ml] def numLeaves: Int = treeStats.numLeaves
+
+ private[ml] def leafAttr =
NominalAttribute.defaultAttr.withNumValues(numLeaves)
private[ml] def getLeafField(leafCol: String) = {
leafAttr.withName(leafCol).toStructField()
diff --git
a/mllib/src/test/scala/org/apache/spark/ml/classification/DecisionTreeClassifierSuite.scala
b/mllib/src/test/scala/org/apache/spark/ml/classification/DecisionTreeClassifierSuite.scala
index 3b778a01416c..e248d0f51b6e 100644
---
a/mllib/src/test/scala/org/apache/spark/ml/classification/DecisionTreeClassifierSuite.scala
+++
b/mllib/src/test/scala/org/apache/spark/ml/classification/DecisionTreeClassifierSuite.scala
@@ -270,7 +270,7 @@ class DecisionTreeClassifierSuite extends MLTest with
DefaultReadWriteTest {
val transformed = newTree.transform(newData)
checkNominalOnDF(transformed, "prediction", newTree.numClasses)
- checkNominalOnDF(transformed, "predictedLeafId", newTree.numLeave)
+ checkNominalOnDF(transformed, "predictedLeafId", newTree.numLeaves)
checkVectorSizeOnDF(transformed, "rawPrediction", newTree.numClasses)
checkVectorSizeOnDF(transformed, "probability", newTree.numClasses)
diff --git a/project/MimaExcludes.scala b/project/MimaExcludes.scala
index 7fd569ad3222..ffc2470b748a 100644
--- a/project/MimaExcludes.scala
+++ b/project/MimaExcludes.scala
@@ -34,7 +34,14 @@ import com.typesafe.tools.mima.core.*
object MimaExcludes {
// Exclude rules for 4.4.x from 4.3.0 (add 4.4-specific filters below as
needed).
- lazy val v44excludes: Seq[Problem => Boolean] = v43excludes
+ lazy val v44excludes: Seq[Problem => Boolean] = v43excludes ++ Seq(
+ // [SPARK-58896] Decision tree leaf counts moved behind NodeStats. The old
package-private
+ // numLeave accessors are removed from concrete models.
+ ProblemFilters.exclude[DirectMissingMethodProblem](
+
"org.apache.spark.ml.classification.DecisionTreeClassificationModel.numLeave"),
+ ProblemFilters.exclude[DirectMissingMethodProblem](
+ "org.apache.spark.ml.regression.DecisionTreeRegressionModel.numLeave")
+ )
// Exclude rules for 4.3.x from 4.2.0 (add 4.3-specific filters below as
needed).
lazy val v43excludes: Seq[Problem => Boolean] = v42excludes ++ Seq(
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
