You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by smurching <gi...@git.apache.org> on 2017/11/15 20:06:38 UTC
[GitHub] spark pull request #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Ref...
GitHub user smurching opened a pull request:
https://github.com/apache/spark/pull/19758
[SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor RandomForest.scala into utility classes
## What changes were proposed in this pull request?
Breaks up #19433 to help unblock #19666; after this PR is merged, #19666 can be merged.
This PR contains the changes made to migrate functionality from RandomForest.scala into the following utility classes:
* AggUpdateUtils
* ImpurityUtils
* SplitUtils
The PR also adds tests for split selection logic in TreeSplitUtilsSuite.
A follow-up PR will include the other changes from #19433:
* Local decision tree data structures & tests
* Local tree training logic & tests
## How was this patch tested?
Adds unit tests for split selection logic in TreeSplitUtilsSuite
(Please explain how this patch was tested. E.g. unit tests, integration tests, manual tests)
(If this patch involves UI changes, please attach a screenshot; otherwise, remove this)
Please review http://spark.apache.org/contributing.html before opening a pull request.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/smurching/spark refactor-random-forest
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/19758.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #19758
----
commit f2e3fbd40eea2919d249710eae5b5789d97543b7
Author: Sid Murching <si...@databricks.com>
Date: 2017-11-15T17:52:01Z
Local tree training part 1 (refactor RandomForest.scala into utility classes)
commit a2357c95672e94a148051d00e26b89245eb8e204
Author: Sid Murching <si...@databricks.com>
Date: 2017-11-15T17:57:55Z
WIP adding TreeSplitUtilsSuite
commit 320c32ee8d0ac9bde457b0286d064470648c73af
Author: Sid Murching <si...@databricks.com>
Date: 2017-11-15T19:37:56Z
WIP
commit b93f9f3da9cca0887c0264162f5b032f14fa87d7
Author: Sid Murching <si...@databricks.com>
Date: 2017-11-15T19:57:25Z
Add TreeSplitUtilsSuite, refactor it to not depend on any local tree training code
----
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Ref...
Posted by smurching <gi...@git.apache.org>.
Github user smurching commented on a diff in the pull request:
https://github.com/apache/spark/pull/19758#discussion_r154284858
--- Diff: mllib/src/test/scala/org/apache/spark/ml/tree/impl/TreeSplitUtilsSuite.scala ---
@@ -0,0 +1,280 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.ml.tree.impl
+
+import org.apache.spark.SparkFunSuite
+import org.apache.spark.ml.tree.{CategoricalSplit, ContinuousSplit, Split}
+import org.apache.spark.ml.util.DefaultReadWriteTest
+import org.apache.spark.mllib.tree.impurity.{Entropy, Impurity}
+import org.apache.spark.mllib.tree.model.ImpurityStats
+import org.apache.spark.mllib.util.MLlibTestSparkContext
+
+/** Suite exercising helper methods for making split decisions during decision tree training. */
+class TreeSplitUtilsSuite
+ extends SparkFunSuite with MLlibTestSparkContext with DefaultReadWriteTest {
+
+ /**
+ * Get a DTStatsAggregator for sufficient stat collection/impurity calculation populated
+ * with the data from the specified training points. Assumes a feature index of 0 and that
+ * all training points have the same weights (1.0).
+ */
+ private def getAggregator(
+ metadata: DecisionTreeMetadata,
+ values: Array[Int],
+ labels: Array[Double],
+ featureSplits: Array[Split]): DTStatsAggregator = {
+ // Create stats aggregator
+ val statsAggregator = new DTStatsAggregator(metadata, featureSubset = None)
+ // Update parent impurity stats
+ val featureIndex = 0
+ val instanceWeights = Array.fill[Double](values.length)(1.0)
+ AggUpdateUtils.updateParentImpurity(statsAggregator, indices = values.indices.toArray,
+ from = 0, to = values.length, instanceWeights, labels)
+ // Update current aggregator's impurity stats
+ values.zip(labels).foreach { case (value: Int, label: Double) =>
+ if (metadata.isUnordered(featureIndex)) {
+ AggUpdateUtils.updateUnorderedFeature(statsAggregator, value, label,
+ featureIndex = featureIndex, featureIndexIdx = 0, featureSplits, instanceWeight = 1.0)
+ } else {
+ AggUpdateUtils.updateOrderedFeature(statsAggregator, value, label, featureIndexIdx = 0,
+ instanceWeight = 1.0)
+ }
+ }
+ statsAggregator
+ }
+
+ /**
+ * Check that left/right impurities match what we'd expect for a split.
+ * @param labels Labels whose impurity information should be reflected in stats
+ * @param stats ImpurityStats object containing impurity info for the left/right sides of a split
+ */
+ private def validateImpurityStats(
+ impurity: Impurity,
+ labels: Array[Double],
+ stats: ImpurityStats,
+ expectedLeftStats: Array[Double],
+ expectedRightStats: Array[Double]): Unit = {
+ // Compute impurity for our data points manually
+ val numClasses = (labels.max + 1).toInt
+ val fullImpurityStatsArray
+ = Array.tabulate[Double](numClasses)((label: Int) => labels.count(_ == label).toDouble)
+ val fullImpurity = Entropy.calculate(fullImpurityStatsArray, labels.length)
+ // Verify that impurity stats were computed correctly for split
+ assert(stats.impurityCalculator.stats === fullImpurityStatsArray)
+ assert(stats.impurity === fullImpurity)
+ assert(stats.leftImpurityCalculator.stats === expectedLeftStats)
+ assert(stats.rightImpurityCalculator.stats === expectedRightStats)
+ assert(stats.valid)
+ }
+
+ /* * * * * * * * * * * Choosing Splits * * * * * * * * * * */
+
+ test("chooseSplit: choose correct type of split (continuous split)") {
+ // Construct (binned) continuous data
+ val labels = Array(0.0, 0.0, 1.0)
+ val values = Array(1, 2, 3)
+ val featureIndex = 0
+ // Get an array of continuous splits corresponding to values in our binned data
+ val splits = TreeTests.getContinuousSplits(thresholds = values.distinct.sorted,
+ featureIndex = 0)
+ // Construct DTStatsAggregator, compute sufficient stats
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, Map.empty)
+ val statsAggregator = getAggregator(metadata, values, labels, splits)
+ // Choose split, check that it's a valid ContinuousSplit
+ val (split, stats) = SplitUtils.chooseSplit(statsAggregator, featureIndex, featureIndex,
+ splits)
+ assert(stats.valid && split.isInstanceOf[ContinuousSplit])
+ }
+
+ test("chooseSplit: choose correct type of split (categorical split)") {
+ // Construct categorical data
+ val labels = Array(0.0, 0.0, 1.0, 1.0, 1.0)
+ val featureArity = 3
+ val values = Array(0, 0, 1, 2, 2)
+ val featureIndex = 0
+ // Construct DTStatsAggregator, compute sufficient stats
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, Map(featureIndex -> featureArity))
+ val splits = RandomForest.findUnorderedSplits(metadata, featureIndex)
+ val statsAggregator = getAggregator(metadata, values, labels, splits)
+ // Choose split, check that it's a valid categorical split
+ val (split, stats) = SplitUtils.chooseSplit(statsAggregator = statsAggregator,
+ featureIndex = featureIndex, featureIndexIdx = featureIndex, featureSplits = splits)
+ assert(stats.valid && split.isInstanceOf[CategoricalSplit])
+ }
+
+ test("chooseOrderedCategoricalSplit: basic case") {
+ // Helper method for testing ordered categorical split
+ def testHelper(
+ values: Array[Int],
+ labels: Array[Double],
+ expectedLeftCategories: Array[Double],
+ expectedLeftStats: Array[Double],
+ expectedRightStats: Array[Double]): Unit = {
+ // Set up metadata for ordered categorical feature
+ val featureIndex = 0
+ val featureArity = values.max + 1
+ val arityMap = Map[Int, Int](featureIndex -> featureArity)
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, arityMap, unorderedFeatures = Some(Set.empty))
+ // Construct DTStatsAggregator, compute sufficient stats
+ val statsAggregator = getAggregator(metadata, values, labels, featureSplits = Array.empty)
+ // Choose split
+ val (split, stats) =
+ SplitUtils.chooseOrderedCategoricalSplit(statsAggregator, featureIndex, featureIndex)
+ // Verify that split has the expected left-side/right-side categories
+ val expectedRightCategories = Range(0, featureArity)
+ .filter(c => !expectedLeftCategories.contains(c)).map(_.toDouble).toArray
+ split match {
+ case s: CategoricalSplit =>
+ assert(s.featureIndex === featureIndex)
+ assert(s.leftCategories === expectedLeftCategories)
+ assert(s.rightCategories === expectedRightCategories)
+ case _ =>
+ throw new AssertionError(
+ s"Expected CategoricalSplit but got ${split.getClass.getSimpleName}")
+ }
+ validateImpurityStats(Entropy, labels, stats, expectedLeftStats, expectedRightStats)
+ }
+
+ // Test a single split: The left side of our split should contain the two points with label 0,
+ // the left side of our split should contain the five points with label 1
+ val values = Array(0, 0, 1, 2, 2, 2, 2)
+ val labels1 = Array(0, 0, 1, 1, 1, 1, 1).map(_.toDouble)
+ testHelper(values, labels1, expectedLeftCategories = Array(0.0),
+ expectedLeftStats = Array(2.0, 0.0), expectedRightStats = Array(0.0, 5.0))
+
+ // Test a single split: The left side of our split should contain the three points with label 0,
+ // the left side of our split should contain the four points with label 1
+ val labels2 = Array(0, 0, 0, 1, 1, 1, 1).map(_.toDouble)
+ testHelper(values, labels2, expectedLeftCategories = Array(0.0, 1.0),
+ expectedLeftStats = Array(3.0, 0.0), expectedRightStats = Array(0.0, 4.0))
+ }
+
+ test("chooseOrderedCategoricalSplit: return bad stats if we should not split") {
+ // Construct categorical data
+ val featureIndex = 0
+ val values = Array(0, 0, 1, 2, 2, 2, 2)
+ val featureArity = values.max + 1
+ val labels = Array(1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0)
+ // Construct DTStatsAggregator, compute sufficient stats
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, Map(featureIndex -> featureArity), unorderedFeatures = Some(Set.empty))
+ val statsAggregator = getAggregator(metadata, values, labels, featureSplits = Array.empty)
+ // Choose split, verify that it's invalid
+ val (_, stats) = SplitUtils.chooseOrderedCategoricalSplit(statsAggregator, featureIndex,
+ featureIndex)
+ assert(!stats.valid)
+ }
+
+ test("chooseUnorderedCategoricalSplit: basic case") {
+ val featureIndex = 0
+ // Construct data for unordered categorical feature
+ // label: 0 --> values: 1
+ // label: 1 --> values: 0, 2
+ // label: 2 --> values: 2
+ // Expected split: feature value 1 on the left, values (0, 2) on the right
+ val values = Array(1, 1, 0, 2, 2)
+ val featureArity = values.max + 1
--- End diff --
@WeichenXu123 thanks for the feedback! Definitely agree that the test is a little weak right now.
IMO it's mainly weak due to the low feature arity (there only three possible splits, so the right one could be picked by chance). I think increasing the number of classes/examples substantially might make the test harder to reason about, but not opposed to that either - let me know what you think.
What about something like:
```
val values = Array(0, 1, 2, 3, 2, 2, 4)
val labels = Array(0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 2.0)
// label: 0 --> values: 0, 1
// label: 1 --> values: 2, 3
// label: 2 --> values: 2, 2, 4
// Expected split: feature values (0, 1) on the left, values (2, 3, 4) on the right
```
This way we still test multiclass classification & test the split-selection logic more rigorously.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Ref...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on a diff in the pull request:
https://github.com/apache/spark/pull/19758#discussion_r154302624
--- Diff: mllib/src/test/scala/org/apache/spark/ml/tree/impl/TreeSplitUtilsSuite.scala ---
@@ -0,0 +1,280 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.ml.tree.impl
+
+import org.apache.spark.SparkFunSuite
+import org.apache.spark.ml.tree.{CategoricalSplit, ContinuousSplit, Split}
+import org.apache.spark.ml.util.DefaultReadWriteTest
+import org.apache.spark.mllib.tree.impurity.{Entropy, Impurity}
+import org.apache.spark.mllib.tree.model.ImpurityStats
+import org.apache.spark.mllib.util.MLlibTestSparkContext
+
+/** Suite exercising helper methods for making split decisions during decision tree training. */
+class TreeSplitUtilsSuite
+ extends SparkFunSuite with MLlibTestSparkContext with DefaultReadWriteTest {
+
+ /**
+ * Get a DTStatsAggregator for sufficient stat collection/impurity calculation populated
+ * with the data from the specified training points. Assumes a feature index of 0 and that
+ * all training points have the same weights (1.0).
+ */
+ private def getAggregator(
+ metadata: DecisionTreeMetadata,
+ values: Array[Int],
+ labels: Array[Double],
+ featureSplits: Array[Split]): DTStatsAggregator = {
+ // Create stats aggregator
+ val statsAggregator = new DTStatsAggregator(metadata, featureSubset = None)
+ // Update parent impurity stats
+ val featureIndex = 0
+ val instanceWeights = Array.fill[Double](values.length)(1.0)
+ AggUpdateUtils.updateParentImpurity(statsAggregator, indices = values.indices.toArray,
+ from = 0, to = values.length, instanceWeights, labels)
+ // Update current aggregator's impurity stats
+ values.zip(labels).foreach { case (value: Int, label: Double) =>
+ if (metadata.isUnordered(featureIndex)) {
+ AggUpdateUtils.updateUnorderedFeature(statsAggregator, value, label,
+ featureIndex = featureIndex, featureIndexIdx = 0, featureSplits, instanceWeight = 1.0)
+ } else {
+ AggUpdateUtils.updateOrderedFeature(statsAggregator, value, label, featureIndexIdx = 0,
+ instanceWeight = 1.0)
+ }
+ }
+ statsAggregator
+ }
+
+ /**
+ * Check that left/right impurities match what we'd expect for a split.
+ * @param labels Labels whose impurity information should be reflected in stats
+ * @param stats ImpurityStats object containing impurity info for the left/right sides of a split
+ */
+ private def validateImpurityStats(
+ impurity: Impurity,
+ labels: Array[Double],
+ stats: ImpurityStats,
+ expectedLeftStats: Array[Double],
+ expectedRightStats: Array[Double]): Unit = {
+ // Compute impurity for our data points manually
+ val numClasses = (labels.max + 1).toInt
+ val fullImpurityStatsArray
+ = Array.tabulate[Double](numClasses)((label: Int) => labels.count(_ == label).toDouble)
+ val fullImpurity = Entropy.calculate(fullImpurityStatsArray, labels.length)
+ // Verify that impurity stats were computed correctly for split
+ assert(stats.impurityCalculator.stats === fullImpurityStatsArray)
+ assert(stats.impurity === fullImpurity)
+ assert(stats.leftImpurityCalculator.stats === expectedLeftStats)
+ assert(stats.rightImpurityCalculator.stats === expectedRightStats)
+ assert(stats.valid)
+ }
+
+ /* * * * * * * * * * * Choosing Splits * * * * * * * * * * */
+
+ test("chooseSplit: choose correct type of split (continuous split)") {
+ // Construct (binned) continuous data
+ val labels = Array(0.0, 0.0, 1.0)
+ val values = Array(1, 2, 3)
+ val featureIndex = 0
+ // Get an array of continuous splits corresponding to values in our binned data
+ val splits = TreeTests.getContinuousSplits(thresholds = values.distinct.sorted,
+ featureIndex = 0)
+ // Construct DTStatsAggregator, compute sufficient stats
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, Map.empty)
+ val statsAggregator = getAggregator(metadata, values, labels, splits)
+ // Choose split, check that it's a valid ContinuousSplit
+ val (split, stats) = SplitUtils.chooseSplit(statsAggregator, featureIndex, featureIndex,
+ splits)
+ assert(stats.valid && split.isInstanceOf[ContinuousSplit])
+ }
+
+ test("chooseSplit: choose correct type of split (categorical split)") {
+ // Construct categorical data
+ val labels = Array(0.0, 0.0, 1.0, 1.0, 1.0)
+ val featureArity = 3
+ val values = Array(0, 0, 1, 2, 2)
+ val featureIndex = 0
+ // Construct DTStatsAggregator, compute sufficient stats
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, Map(featureIndex -> featureArity))
+ val splits = RandomForest.findUnorderedSplits(metadata, featureIndex)
+ val statsAggregator = getAggregator(metadata, values, labels, splits)
+ // Choose split, check that it's a valid categorical split
+ val (split, stats) = SplitUtils.chooseSplit(statsAggregator = statsAggregator,
+ featureIndex = featureIndex, featureIndexIdx = featureIndex, featureSplits = splits)
+ assert(stats.valid && split.isInstanceOf[CategoricalSplit])
+ }
+
+ test("chooseOrderedCategoricalSplit: basic case") {
+ // Helper method for testing ordered categorical split
+ def testHelper(
+ values: Array[Int],
+ labels: Array[Double],
+ expectedLeftCategories: Array[Double],
+ expectedLeftStats: Array[Double],
+ expectedRightStats: Array[Double]): Unit = {
+ // Set up metadata for ordered categorical feature
+ val featureIndex = 0
+ val featureArity = values.max + 1
+ val arityMap = Map[Int, Int](featureIndex -> featureArity)
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, arityMap, unorderedFeatures = Some(Set.empty))
+ // Construct DTStatsAggregator, compute sufficient stats
+ val statsAggregator = getAggregator(metadata, values, labels, featureSplits = Array.empty)
+ // Choose split
+ val (split, stats) =
+ SplitUtils.chooseOrderedCategoricalSplit(statsAggregator, featureIndex, featureIndex)
+ // Verify that split has the expected left-side/right-side categories
+ val expectedRightCategories = Range(0, featureArity)
+ .filter(c => !expectedLeftCategories.contains(c)).map(_.toDouble).toArray
+ split match {
+ case s: CategoricalSplit =>
+ assert(s.featureIndex === featureIndex)
+ assert(s.leftCategories === expectedLeftCategories)
+ assert(s.rightCategories === expectedRightCategories)
+ case _ =>
+ throw new AssertionError(
+ s"Expected CategoricalSplit but got ${split.getClass.getSimpleName}")
+ }
+ validateImpurityStats(Entropy, labels, stats, expectedLeftStats, expectedRightStats)
+ }
+
+ // Test a single split: The left side of our split should contain the two points with label 0,
+ // the left side of our split should contain the five points with label 1
+ val values = Array(0, 0, 1, 2, 2, 2, 2)
+ val labels1 = Array(0, 0, 1, 1, 1, 1, 1).map(_.toDouble)
+ testHelper(values, labels1, expectedLeftCategories = Array(0.0),
+ expectedLeftStats = Array(2.0, 0.0), expectedRightStats = Array(0.0, 5.0))
+
+ // Test a single split: The left side of our split should contain the three points with label 0,
+ // the left side of our split should contain the four points with label 1
+ val labels2 = Array(0, 0, 0, 1, 1, 1, 1).map(_.toDouble)
+ testHelper(values, labels2, expectedLeftCategories = Array(0.0, 1.0),
+ expectedLeftStats = Array(3.0, 0.0), expectedRightStats = Array(0.0, 4.0))
+ }
+
+ test("chooseOrderedCategoricalSplit: return bad stats if we should not split") {
+ // Construct categorical data
+ val featureIndex = 0
+ val values = Array(0, 0, 1, 2, 2, 2, 2)
+ val featureArity = values.max + 1
+ val labels = Array(1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0)
+ // Construct DTStatsAggregator, compute sufficient stats
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, Map(featureIndex -> featureArity), unorderedFeatures = Some(Set.empty))
+ val statsAggregator = getAggregator(metadata, values, labels, featureSplits = Array.empty)
+ // Choose split, verify that it's invalid
+ val (_, stats) = SplitUtils.chooseOrderedCategoricalSplit(statsAggregator, featureIndex,
+ featureIndex)
+ assert(!stats.valid)
+ }
+
+ test("chooseUnorderedCategoricalSplit: basic case") {
+ val featureIndex = 0
+ // Construct data for unordered categorical feature
+ // label: 0 --> values: 1
+ // label: 1 --> values: 0, 2
+ // label: 2 --> values: 2
+ // Expected split: feature value 1 on the left, values (0, 2) on the right
+ val values = Array(1, 1, 0, 2, 2)
+ val featureArity = values.max + 1
--- End diff --
I think it is OK. thanks!
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19758
Merged build finished. Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19758
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/83911/
Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19758
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/83914/
Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Ref...
Posted by WeichenXu123 <gi...@git.apache.org>.
Github user WeichenXu123 commented on a diff in the pull request:
https://github.com/apache/spark/pull/19758#discussion_r152749515
--- Diff: mllib/src/test/scala/org/apache/spark/ml/tree/impl/TreeSplitUtilsSuite.scala ---
@@ -0,0 +1,280 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.ml.tree.impl
+
+import org.apache.spark.SparkFunSuite
+import org.apache.spark.ml.tree.{CategoricalSplit, ContinuousSplit, Split}
+import org.apache.spark.ml.util.DefaultReadWriteTest
+import org.apache.spark.mllib.tree.impurity.{Entropy, Impurity}
+import org.apache.spark.mllib.tree.model.ImpurityStats
+import org.apache.spark.mllib.util.MLlibTestSparkContext
+
+/** Suite exercising helper methods for making split decisions during decision tree training. */
+class TreeSplitUtilsSuite
+ extends SparkFunSuite with MLlibTestSparkContext with DefaultReadWriteTest {
+
+ /**
+ * Get a DTStatsAggregator for sufficient stat collection/impurity calculation populated
+ * with the data from the specified training points. Assumes a feature index of 0 and that
+ * all training points have the same weights (1.0).
+ */
+ private def getAggregator(
+ metadata: DecisionTreeMetadata,
+ values: Array[Int],
+ labels: Array[Double],
+ featureSplits: Array[Split]): DTStatsAggregator = {
+ // Create stats aggregator
+ val statsAggregator = new DTStatsAggregator(metadata, featureSubset = None)
+ // Update parent impurity stats
+ val featureIndex = 0
+ val instanceWeights = Array.fill[Double](values.length)(1.0)
+ AggUpdateUtils.updateParentImpurity(statsAggregator, indices = values.indices.toArray,
+ from = 0, to = values.length, instanceWeights, labels)
+ // Update current aggregator's impurity stats
+ values.zip(labels).foreach { case (value: Int, label: Double) =>
+ if (metadata.isUnordered(featureIndex)) {
+ AggUpdateUtils.updateUnorderedFeature(statsAggregator, value, label,
+ featureIndex = featureIndex, featureIndexIdx = 0, featureSplits, instanceWeight = 1.0)
+ } else {
+ AggUpdateUtils.updateOrderedFeature(statsAggregator, value, label, featureIndexIdx = 0,
+ instanceWeight = 1.0)
+ }
+ }
+ statsAggregator
+ }
+
+ /**
+ * Check that left/right impurities match what we'd expect for a split.
+ * @param labels Labels whose impurity information should be reflected in stats
+ * @param stats ImpurityStats object containing impurity info for the left/right sides of a split
+ */
+ private def validateImpurityStats(
+ impurity: Impurity,
+ labels: Array[Double],
+ stats: ImpurityStats,
+ expectedLeftStats: Array[Double],
+ expectedRightStats: Array[Double]): Unit = {
+ // Compute impurity for our data points manually
+ val numClasses = (labels.max + 1).toInt
+ val fullImpurityStatsArray
+ = Array.tabulate[Double](numClasses)((label: Int) => labels.count(_ == label).toDouble)
+ val fullImpurity = Entropy.calculate(fullImpurityStatsArray, labels.length)
+ // Verify that impurity stats were computed correctly for split
+ assert(stats.impurityCalculator.stats === fullImpurityStatsArray)
+ assert(stats.impurity === fullImpurity)
+ assert(stats.leftImpurityCalculator.stats === expectedLeftStats)
+ assert(stats.rightImpurityCalculator.stats === expectedRightStats)
+ assert(stats.valid)
+ }
+
+ /* * * * * * * * * * * Choosing Splits * * * * * * * * * * */
+
+ test("chooseSplit: choose correct type of split (continuous split)") {
+ // Construct (binned) continuous data
+ val labels = Array(0.0, 0.0, 1.0)
+ val values = Array(1, 2, 3)
+ val featureIndex = 0
+ // Get an array of continuous splits corresponding to values in our binned data
+ val splits = TreeTests.getContinuousSplits(thresholds = values.distinct.sorted,
+ featureIndex = 0)
+ // Construct DTStatsAggregator, compute sufficient stats
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, Map.empty)
+ val statsAggregator = getAggregator(metadata, values, labels, splits)
+ // Choose split, check that it's a valid ContinuousSplit
+ val (split, stats) = SplitUtils.chooseSplit(statsAggregator, featureIndex, featureIndex,
+ splits)
+ assert(stats.valid && split.isInstanceOf[ContinuousSplit])
+ }
+
+ test("chooseSplit: choose correct type of split (categorical split)") {
+ // Construct categorical data
+ val labels = Array(0.0, 0.0, 1.0, 1.0, 1.0)
+ val featureArity = 3
+ val values = Array(0, 0, 1, 2, 2)
+ val featureIndex = 0
+ // Construct DTStatsAggregator, compute sufficient stats
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, Map(featureIndex -> featureArity))
+ val splits = RandomForest.findUnorderedSplits(metadata, featureIndex)
+ val statsAggregator = getAggregator(metadata, values, labels, splits)
+ // Choose split, check that it's a valid categorical split
+ val (split, stats) = SplitUtils.chooseSplit(statsAggregator = statsAggregator,
+ featureIndex = featureIndex, featureIndexIdx = featureIndex, featureSplits = splits)
+ assert(stats.valid && split.isInstanceOf[CategoricalSplit])
+ }
+
+ test("chooseOrderedCategoricalSplit: basic case") {
+ // Helper method for testing ordered categorical split
+ def testHelper(
+ values: Array[Int],
+ labels: Array[Double],
+ expectedLeftCategories: Array[Double],
+ expectedLeftStats: Array[Double],
+ expectedRightStats: Array[Double]): Unit = {
+ // Set up metadata for ordered categorical feature
+ val featureIndex = 0
+ val featureArity = values.max + 1
+ val arityMap = Map[Int, Int](featureIndex -> featureArity)
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, arityMap, unorderedFeatures = Some(Set.empty))
+ // Construct DTStatsAggregator, compute sufficient stats
+ val statsAggregator = getAggregator(metadata, values, labels, featureSplits = Array.empty)
+ // Choose split
+ val (split, stats) =
+ SplitUtils.chooseOrderedCategoricalSplit(statsAggregator, featureIndex, featureIndex)
+ // Verify that split has the expected left-side/right-side categories
+ val expectedRightCategories = Range(0, featureArity)
+ .filter(c => !expectedLeftCategories.contains(c)).map(_.toDouble).toArray
+ split match {
+ case s: CategoricalSplit =>
+ assert(s.featureIndex === featureIndex)
+ assert(s.leftCategories === expectedLeftCategories)
+ assert(s.rightCategories === expectedRightCategories)
+ case _ =>
+ throw new AssertionError(
+ s"Expected CategoricalSplit but got ${split.getClass.getSimpleName}")
+ }
+ validateImpurityStats(Entropy, labels, stats, expectedLeftStats, expectedRightStats)
+ }
+
+ // Test a single split: The left side of our split should contain the two points with label 0,
+ // the left side of our split should contain the five points with label 1
+ val values = Array(0, 0, 1, 2, 2, 2, 2)
+ val labels1 = Array(0, 0, 1, 1, 1, 1, 1).map(_.toDouble)
+ testHelper(values, labels1, expectedLeftCategories = Array(0.0),
+ expectedLeftStats = Array(2.0, 0.0), expectedRightStats = Array(0.0, 5.0))
+
+ // Test a single split: The left side of our split should contain the three points with label 0,
+ // the left side of our split should contain the four points with label 1
+ val labels2 = Array(0, 0, 0, 1, 1, 1, 1).map(_.toDouble)
+ testHelper(values, labels2, expectedLeftCategories = Array(0.0, 1.0),
+ expectedLeftStats = Array(3.0, 0.0), expectedRightStats = Array(0.0, 4.0))
+ }
+
+ test("chooseOrderedCategoricalSplit: return bad stats if we should not split") {
+ // Construct categorical data
+ val featureIndex = 0
+ val values = Array(0, 0, 1, 2, 2, 2, 2)
+ val featureArity = values.max + 1
+ val labels = Array(1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0)
+ // Construct DTStatsAggregator, compute sufficient stats
+ val metadata = TreeTests.getMetadata(numExamples = values.length, numFeatures = 1,
+ numClasses = 2, Map(featureIndex -> featureArity), unorderedFeatures = Some(Set.empty))
+ val statsAggregator = getAggregator(metadata, values, labels, featureSplits = Array.empty)
+ // Choose split, verify that it's invalid
+ val (_, stats) = SplitUtils.chooseOrderedCategoricalSplit(statsAggregator, featureIndex,
+ featureIndex)
+ assert(!stats.valid)
+ }
+
+ test("chooseUnorderedCategoricalSplit: basic case") {
+ val featureIndex = 0
+ // Construct data for unordered categorical feature
+ // label: 0 --> values: 1
+ // label: 1 --> values: 0, 2
+ // label: 2 --> values: 2
+ // Expected split: feature value 1 on the left, values (0, 2) on the right
+ val values = Array(1, 1, 0, 2, 2)
+ val featureArity = values.max + 1
--- End diff --
In order to make the test more strict, can you increase the `featureArity`, `numExamples` and `numClasses` ? e.g., featureArity = 6 and numExamples = 10 and numClasses = 5
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19758
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/84379/
Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19758
**[Test build #83914 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/83914/testReport)** for PR 19758 at commit [`b6291e1`](https://github.com/apache/spark/commit/b6291e1dd9670b74f3643c5bdc10b5bc7d79e66c).
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19758
**[Test build #83911 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/83911/testReport)** for PR 19758 at commit [`b4a5f3b`](https://github.com/apache/spark/commit/b4a5f3b2204e8ab957864103424c269cbb1da81b).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by wenbochang <gi...@git.apache.org>.
Github user wenbochang commented on the issue:
https://github.com/apache/spark/pull/19758
Any updates? this PR seems to address critical issue: https://issues.apache.org/jira/browse/SPARK-3162
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19758
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/83910/
Test FAILed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19758
**[Test build #84379 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/84379/testReport)** for PR 19758 at commit [`5bcccda`](https://github.com/apache/spark/commit/5bcccda6a599f60d2d084ecf871649675a792d5d).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19758
**[Test build #83911 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/83911/testReport)** for PR 19758 at commit [`b4a5f3b`](https://github.com/apache/spark/commit/b4a5f3b2204e8ab957864103424c269cbb1da81b).
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by felixcheung <gi...@git.apache.org>.
Github user felixcheung commented on the issue:
https://github.com/apache/spark/pull/19758
ping?
I'm mostly interested in SPARK-3162
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19758
**[Test build #83910 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/83910/testReport)** for PR 19758 at commit [`b93f9f3`](https://github.com/apache/spark/commit/b93f9f3da9cca0887c0264162f5b032f14fa87d7).
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19758
**[Test build #84379 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/84379/testReport)** for PR 19758 at commit [`5bcccda`](https://github.com/apache/spark/commit/5bcccda6a599f60d2d084ecf871649675a792d5d).
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19758
**[Test build #83914 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/83914/testReport)** for PR 19758 at commit [`b6291e1`](https://github.com/apache/spark/commit/b6291e1dd9670b74f3643c5bdc10b5bc7d79e66c).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19758
Merged build finished. Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19758
Merged build finished. Test PASSed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Ref...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/spark/pull/19758
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/19758
Merged build finished. Test FAILed.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #19758: [SPARK-3162][MLlib] Local Tree Training Pt 1: Refactor R...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/19758
**[Test build #83910 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/83910/testReport)** for PR 19758 at commit [`b93f9f3`](https://github.com/apache/spark/commit/b93f9f3da9cca0887c0264162f5b032f14fa87d7).
* This patch **fails to generate documentation**.
* This patch merges cleanly.
* This patch adds no public classes.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org