You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by jkbradley <gi...@git.apache.org> on 2014/08/16 00:37:21 UTC
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
GitHub user jkbradley opened a pull request:
https://github.com/apache/spark/pull/1975
[SPARK-3042] [mllib] DecisionTree Filter top-down instead of bottom-up
DecisionTree needs to match each example to a node at each iteration. It currently does this with a set of filters very inefficiently: For each example, it examines each node at the current level and traces up to the root to see if that example should be handled by that node.
Fix: Filter top-down using the partly built tree itself.
Major changes:
* Eliminated Filter class, findBinsForLevel() method.
* Set up node parent links in main loop over levels in train().
* Added predictNodeIndex() for filtering top-down.
Other changes:
* Pre-compute set of unorderedFeatures.
Notes for following expected PR based on [https://issues.apache.org/jira/browse/SPARK-3043]:
* The unorderedFeatures set will next be stored in a metadata structure to simplify function calls (to store other items such as the data in strategy).
I've done initial tests indicating that this speeds things up, but am only now running large-scale ones.
CC: @mengxr @manishamde @chouqin Any comments are welcome---thanks!
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/jkbradley/spark dt-opt2
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/1975.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 #1975
----
commit a95bc22e648d01158d3a4fd597059135e1302266
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-05T18:17:28Z
timing for DecisionTree internals
commit 511ec85fbe4c4463d8e600fabc5d54c5b2bd8417
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-06T01:16:19Z
Merge remote-tracking branch 'upstream/master' into dt-timing
commit bcf874a7444303ac7dc14cc5a36890cec45a8359
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-07T21:53:22Z
Merge remote-tracking branch 'upstream/master' into dt-timing
Conflicts:
mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala
commit f61e9d227233679ab826e38210376e7050da9b6b
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-08T07:35:06Z
Merge remote-tracking branch 'upstream/master' into dt-timing
commit 3211f027c1a41f8eaa4eea4e90073216a8474c4e
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-08T16:46:12Z
Optimizing DecisionTree
* Added TreePoint representation to avoid calling findBin multiple times.
* (not working yet, but debugging)
commit 0f676e2e0ae02e54387a255ac9f64d3c7265d152
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-08T21:12:52Z
Optimizations + Bug fix for DecisionTree
Optimization: Added TreePoint representation so we only call findBin once for each example, feature.
Also, calculateGainsForAllNodeSplits now only searches over actual splits, not empty/unused ones.
BUG FIX: isSampleValid
* isSampleValid used to treat unordered categorical features incorrectly: It treated the bins as if indexed by featured values, rather than by subsets of values/categories.
* exhibited for unordered features (multi-class classification with categorical features of low arity)
* Fix: Index bins correctly for unordered categorical features.
Also: some commented-out debugging println calls in DecisionTree, to be removed later
commit b2ed1f39ecc967a663a88241b46e5786eb66be22
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-08T21:15:44Z
Merge remote-tracking branch 'upstream/master' into dt-opt
commit b914f3b7ed94e897b55f28c772f48a7d6fba7f06
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-09T19:01:45Z
DecisionTree optimization: eliminated filters + small changes
DecisionTree.scala
* Eliminated filters, replaced by building tree on the fly and filtering top-down.
** Aggregation over examples now skips examples which do not reach the current level.
* Only calculate unorderedFeatures once (in findSplitsBins)
Node: Renamed predictIfLeaf to predict
Bin, Split: Updated doc
commit c1565a5248e5d0ccc2293315799281030a74c217
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-11T18:09:32Z
Small DecisionTree updates:
* Simplification: Updated calculateGainForSplit to take aggregates for a single (feature, split) pair.
* Internal doc: findAggForOrderedFeatureClassification
commit a87e08f1e5999c31b956a34617f88ff9a50775ae
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-14T18:34:12Z
Merge remote-tracking branch 'upstream/master' into dt-opt1
commit 8464a6efd644daf9954ba43c9790ec304f94e029
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-14T19:26:57Z
Moved TimeTracker to tree/impl/ in its own file, and cleaned it up. Removed debugging println calls from DecisionTree. Made TreePoint extend Serialiable
commit e66f1b1cb2252dab1f847f2c24623baab40627fc
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-14T19:58:22Z
TreePoint
* Updated doc
* Made some methods private
Changed timer to report time in seconds.
commit d03608949e19c53596b4f6cc09d9f68011184d68
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-14T20:07:14Z
Print timing info to logDebug.
commit 430d782294a08f63535e2ecce167703021e1fe44
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-14T23:09:14Z
Added more debug info on binning error. Added some docs.
commit 356dabac6bad8b2e2a9f7b90aaae80d987c113dc
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-14T23:57:13Z
Merge branch 'dt-opt1' into dt-opt2
Conflicts:
mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala
mllib/src/test/scala/org/apache/spark/mllib/tree/DecisionTreeSuite.scala
commit 26d10dd58ee218102bd205c1e6d68fda5a45cf4b
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-15T00:44:08Z
Removed tree/model/Filter.scala since no longer used. Removed debugging println calls in DecisionTree.scala.
commit 2d2aaaffd630e5a9376a321ac5b7d2a64bcd13e2
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-15T16:46:16Z
Merge remote-tracking branch 'upstream/master' into dt-opt1
commit 6b5651e7671315f78aef42344ab514e3cf8052df
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-15T19:28:47Z
Updates based on code review. 1 major change: persisting to memory + disk, not just memory.
Details:
DecisionTree
* Changed: .cache() -> .persist(StorageLevel.MEMORY_AND_DISK)
** This gave major performance improvements on small tests. E.g., 500K examples, 500 features, depth 5, on MacBook, took 292 sec with cache() and 112 when using disk as well.
* Change for to while loops
* Small cleanups
TimeTracker
* Removed useless timing in DecisionTree
TreePoint
* Renamed features to binnedFeatures
commit 5f2dec2e3c5e17ce79cef119ef039323dbd73942
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-15T19:43:50Z
Fixed scalastyle issue in TreePoint
commit f40381c0ecf76506f7b727d1d6ca715fe7716065
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-15T21:28:07Z
Merge branch 'dt-opt1' into dt-opt2
Conflicts:
mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala
mllib/src/test/scala/org/apache/spark/mllib/tree/DecisionTreeSuite.scala
Merge is OK except one DT Suite test to fix.
commit 797f68a13323bbebac099ea1a98654fb7b2984a0
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-15T22:19:01Z
Fixed DecisionTreeSuite bug for training second level. Needed to update treePointToNodeIndex with groupShift.
commit 931a3a714e44ab1138dac18bc3b497892d36e3e5
Author: Joseph K. Bradley <jo...@gmail.com>
Date: 2014-08-15T22:22:26Z
Merge remote-tracking branch 'upstream/master' into dt-opt2
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52384369
Jenkins, test this please.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52378626
[QA tests have started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18653/consoleFull) for PR 1975 at commit [`db0d773`](https://github.com/apache/spark/commit/db0d7732a8cece3dc0188923e6c2939c09ee686a).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by manishamde <gi...@git.apache.org>.
Github user manishamde commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16328177
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -531,160 +526,121 @@ object DecisionTree extends Serializable with Logging {
// numNodes: Number of nodes in this (level of tree, group),
// where nodes at deeper (larger) levels may be divided into groups.
- val numNodes = math.pow(2, level).toInt / numGroups
+ val numNodes = (1 << level) / numGroups
logDebug("numNodes = " + numNodes)
// Find the number of features by looking at the first sample.
- val numFeatures = input.first().binnedFeatures.size
+ val numFeatures = metadata.numFeatures
logDebug("numFeatures = " + numFeatures)
// numBins: Number of bins = 1 + number of possible splits
val numBins = bins(0).length
logDebug("numBins = " + numBins)
- val numClasses = strategy.numClassesForClassification
+ val numClasses = metadata.numClasses
logDebug("numClasses = " + numClasses)
- val isMulticlassClassification = strategy.isMulticlassClassification
- logDebug("isMulticlassClassification = " + isMulticlassClassification)
+ val isMulticlass = metadata.isMulticlass
+ logDebug("isMulticlass = " + isMulticlass)
- val isMulticlassClassificationWithCategoricalFeatures
- = strategy.isMulticlassWithCategoricalFeatures
- logDebug("isMultiClassWithCategoricalFeatures = " +
- isMulticlassClassificationWithCategoricalFeatures)
+ val isMulticlassWithCategoricalFeatures = metadata.isMulticlassWithCategoricalFeatures
+ logDebug("isMultiClassWithCategoricalFeatures = " + isMulticlassWithCategoricalFeatures)
// shift when more than one group is used at deep tree level
val groupShift = numNodes * groupIndex
- /** Find the filters used before reaching the current code. */
- def findParentFilters(nodeIndex: Int): List[Filter] = {
- if (level == 0) {
- List[Filter]()
- } else {
- val nodeFilterIndex = math.pow(2, level).toInt - 1 + nodeIndex + groupShift
- filters(nodeFilterIndex)
- }
- }
-
/**
- * Find whether the sample is valid input for the current node, i.e., whether it passes through
- * all the filters for the current node.
+ * Get the node index corresponding to this data point.
+ * This is used during training, mimicking prediction.
--- End diff --
A little more explanation of this method or strategy in general in the code will help in future code maintenance.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52414362
[QA tests have started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18697/consoleFull) for PR 1975 at commit [`a0ed0da`](https://github.com/apache/spark/commit/a0ed0daa4c3622e19626de7aa3b29e07c6015ff2).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52414976
[QA tests have finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18697/consoleFull) for PR 1975 at commit [`a0ed0da`](https://github.com/apache/spark/commit/a0ed0daa4c3622e19626de7aa3b29e07c6015ff2).
* This patch **passes** unit tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by manishamde <gi...@git.apache.org>.
Github user manishamde commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16328201
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/impl/DTMetadata.scala ---
@@ -0,0 +1,101 @@
+/*
+ * 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.mllib.tree.impl
+
+import scala.collection.mutable
+
+import org.apache.spark.mllib.regression.LabeledPoint
+import org.apache.spark.mllib.tree.configuration.Algo._
+import org.apache.spark.mllib.tree.configuration.QuantileStrategy._
+import org.apache.spark.mllib.tree.configuration.Strategy
+import org.apache.spark.mllib.tree.impurity.Impurity
+import org.apache.spark.rdd.RDD
+
+
+/**
+ * Learning and dataset metadata for DecisionTree.
+ *
+ * @param numClasses For classification: labels can take values {0, ..., numClasses - 1}.
+ * For regression: fixed at 0 (no meaning).
+ * @param featureArity Map: categorical feature index --> arity.
+ * I.e., the feature takes values in {0, ..., arity - 1}.
+ */
+private[tree] class DTMetadata(
--- End diff --
Suggestion: DecisionTreeMetadata, TreeMetadata or Metadata as class name alternatives.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52413151
LGTM. Waiting for Jenkins ...
Btw, I created a JIRA for using 1-indexing: https://issues.apache.org/jira/browse/SPARK-3086 .
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by manishamde <gi...@git.apache.org>.
Github user manishamde commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16328186
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -531,160 +526,121 @@ object DecisionTree extends Serializable with Logging {
// numNodes: Number of nodes in this (level of tree, group),
// where nodes at deeper (larger) levels may be divided into groups.
- val numNodes = math.pow(2, level).toInt / numGroups
+ val numNodes = (1 << level) / numGroups
logDebug("numNodes = " + numNodes)
// Find the number of features by looking at the first sample.
- val numFeatures = input.first().binnedFeatures.size
+ val numFeatures = metadata.numFeatures
logDebug("numFeatures = " + numFeatures)
// numBins: Number of bins = 1 + number of possible splits
val numBins = bins(0).length
logDebug("numBins = " + numBins)
- val numClasses = strategy.numClassesForClassification
+ val numClasses = metadata.numClasses
logDebug("numClasses = " + numClasses)
- val isMulticlassClassification = strategy.isMulticlassClassification
- logDebug("isMulticlassClassification = " + isMulticlassClassification)
+ val isMulticlass = metadata.isMulticlass
+ logDebug("isMulticlass = " + isMulticlass)
- val isMulticlassClassificationWithCategoricalFeatures
- = strategy.isMulticlassWithCategoricalFeatures
- logDebug("isMultiClassWithCategoricalFeatures = " +
- isMulticlassClassificationWithCategoricalFeatures)
+ val isMulticlassWithCategoricalFeatures = metadata.isMulticlassWithCategoricalFeatures
+ logDebug("isMultiClassWithCategoricalFeatures = " + isMulticlassWithCategoricalFeatures)
// shift when more than one group is used at deep tree level
val groupShift = numNodes * groupIndex
- /** Find the filters used before reaching the current code. */
- def findParentFilters(nodeIndex: Int): List[Filter] = {
- if (level == 0) {
- List[Filter]()
- } else {
- val nodeFilterIndex = math.pow(2, level).toInt - 1 + nodeIndex + groupShift
- filters(nodeFilterIndex)
- }
- }
-
/**
- * Find whether the sample is valid input for the current node, i.e., whether it passes through
- * all the filters for the current node.
+ * Get the node index corresponding to this data point.
+ * This is used during training, mimicking prediction.
+ * @return Leaf index if the data point reaches a leaf.
+ * Otherwise, last node reachable in tree matching this example.
*/
- def isSampleValid(parentFilters: List[Filter], treePoint: TreePoint): Boolean = {
- // leaf
- if ((level > 0) && (parentFilters.length == 0)) {
- return false
- }
-
- // Apply each filter and check sample validity. Return false when invalid condition found.
- parentFilters.foreach { filter =>
- val featureIndex = filter.split.feature
- val comparison = filter.comparison
- val isFeatureContinuous = filter.split.featureType == Continuous
- if (isFeatureContinuous) {
- val binId = treePoint.binnedFeatures(featureIndex)
- val bin = bins(featureIndex)(binId)
- val featureValue = bin.highSplit.threshold
- val threshold = filter.split.threshold
- comparison match {
- case -1 => if (featureValue > threshold) return false
- case 1 => if (featureValue <= threshold) return false
+ def predictNodeIndex(node: Node, binnedFeatures: Array[Int]): Int = {
+ if (node.isLeaf) {
+ node.id
+ } else {
+ val featureIndex = node.split.get.feature
+ val splitLeft = node.split.get.featureType match {
+ case Continuous => {
+ val binIndex = binnedFeatures(featureIndex)
+ val featureValueUpperBound = bins(featureIndex)(binIndex).highSplit.threshold
+ // bin binIndex has range (bin.lowSplit.threshold, bin.highSplit.threshold]
+ // We do not need to check lowSplit since bins are separated by splits.
+ featureValueUpperBound <= node.split.get.threshold
}
- } else {
- val numFeatureCategories = strategy.categoricalFeaturesInfo(featureIndex)
- val isSpaceSufficientForAllCategoricalSplits =
- numBins > math.pow(2, numFeatureCategories.toInt - 1) - 1
- val isUnorderedFeature =
- isMulticlassClassification && isSpaceSufficientForAllCategoricalSplits
- val featureValue = if (isUnorderedFeature) {
- treePoint.binnedFeatures(featureIndex)
+ case Categorical => {
+ val featureValue = if (metadata.isUnordered(featureIndex)) {
+ binnedFeatures(featureIndex)
+ } else {
+ val binIndex = binnedFeatures(featureIndex)
+ bins(featureIndex)(binIndex).category
+ }
+ node.split.get.categories.contains(featureValue)
+ }
+ case _ => throw new RuntimeException(s"predictNodeIndex failed for unknown reason.")
+ }
+ if (node.leftNode.isEmpty || node.rightNode.isEmpty) {
+ // Return index from next layer of nodes to train
+ if (splitLeft) {
+ node.id * 2 + 1 // left
} else {
- val binId = treePoint.binnedFeatures(featureIndex)
- bins(featureIndex)(binId).category
+ node.id * 2 + 2 // right
}
- val containsFeature = filter.split.categories.contains(featureValue)
- comparison match {
- case -1 => if (!containsFeature) return false
- case 1 => if (containsFeature) return false
+ } else {
+ if (splitLeft) {
+ predictNodeIndex(node.leftNode.get, binnedFeatures)
+ } else {
+ predictNodeIndex(node.rightNode.get, binnedFeatures)
}
}
}
+ }
- // Return true when the sample is valid for all filters.
- true
+ def nodeIndexToLevel(idx: Int): Int = {
+ if (idx == 0) {
+ 0
+ } else {
+ math.floor(math.log(idx) / math.log(2)).toInt
+ }
}
+ // Used for treePointToNodeIndex
+ val levelOffset = (1 << level) - 1
+
/**
- * Finds bins for all nodes (and all features) at a given level.
- * For l nodes, k features the storage is as follows:
- * label, b_11, b_12, .. , b_1k, b_21, b_22, .. , b_2k, b_l1, b_l2, .. , b_lk,
- * where b_ij is an integer between 0 and numBins - 1 for regressions and binary
- * classification and the categorical feature value in multiclass classification.
- * Invalid sample is denoted by noting bin for feature 1 as -1.
- *
- * For unordered features, the "bin index" returned is actually the feature value (category).
- *
- * @return Array of size 1 + numFeatures * numNodes, where
- * arr(0) = label for labeledPoint, and
- * arr(1 + numFeatures * nodeIndex + featureIndex) =
- * bin index for this labeledPoint
- * (or InvalidBinIndex if labeledPoint is not handled by this node)
+ * Find the node (indexed from 0 at the start of this level) for the given example.
--- End diff --
May be the comment should reflect that the indexing from the start of the groupShift at a given level.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52413057
Jenkins, test this please.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52414342
@mengxr @manishamde Thanks for the feedback! I pushed my last updates, and everything should be ready, Jenkins agreeing.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by manishamde <gi...@git.apache.org>.
Github user manishamde commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52413760
Thanks @mengxr for the review as well.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52368214
[QA tests have started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18630/consoleFull) for PR 1975 at commit [`931a3a7`](https://github.com/apache/spark/commit/931a3a714e44ab1138dac18bc3b497892d36e3e5).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52385147
[QA tests have finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18660/consoleFull) for PR 1975 at commit [`ac0b9f8`](https://github.com/apache/spark/commit/ac0b9f84ededb9aaee477f439f711d9be8e890bd).
* This patch **passes** unit tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16322132
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -556,135 +568,98 @@ object DecisionTree extends Serializable with Logging {
// shift when more than one group is used at deep tree level
val groupShift = numNodes * groupIndex
- /** Find the filters used before reaching the current code. */
- def findParentFilters(nodeIndex: Int): List[Filter] = {
- if (level == 0) {
- List[Filter]()
- } else {
- val nodeFilterIndex = math.pow(2, level).toInt - 1 + nodeIndex + groupShift
- filters(nodeFilterIndex)
- }
- }
-
/**
- * Find whether the sample is valid input for the current node, i.e., whether it passes through
- * all the filters for the current node.
+ * Get the node index corresponding to this data point.
+ * This is used during training, mimicking prediction.
+ * @return Leaf index if the data point reaches a leaf.
+ * Otherwise, last node reachable in tree matching this example.
*/
- def isSampleValid(parentFilters: List[Filter], treePoint: TreePoint): Boolean = {
- // leaf
- if ((level > 0) && (parentFilters.length == 0)) {
- return false
- }
-
- // Apply each filter and check sample validity. Return false when invalid condition found.
- parentFilters.foreach { filter =>
- val featureIndex = filter.split.feature
- val comparison = filter.comparison
- val isFeatureContinuous = filter.split.featureType == Continuous
- if (isFeatureContinuous) {
- val binId = treePoint.binnedFeatures(featureIndex)
- val bin = bins(featureIndex)(binId)
- val featureValue = bin.highSplit.threshold
- val threshold = filter.split.threshold
- comparison match {
- case -1 => if (featureValue > threshold) return false
- case 1 => if (featureValue <= threshold) return false
+ def predictNodeIndex(node: Node, features: Array[Int]): Int = {
--- End diff --
`features` -> `binnedFeatures`?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52413104
[QA tests have started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18692/consoleFull) for PR 1975 at commit [`3726d20`](https://github.com/apache/spark/commit/3726d2003e681e569a6d1fbf4af65909500f1b80).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16323075
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -198,29 +214,22 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
index: Int,
maxDepth: Int,
nodeSplitStats: (Split, InformationGainStats),
- parentImpurities: Array[Double],
- filters: Array[List[Filter]]): Unit = {
+ parentImpurities: Array[Double]): Unit = {
+ if (level >= maxDepth)
+ return
// 0 corresponds to the left child node and 1 corresponds to the right child node.
var i = 0
while (i <= 1) {
- // Calculate the index of the node from the node level and the index at the current level.
+ // Calculate the index of the node from the node level and the index at the current level.
val nodeIndex = math.pow(2, level + 1).toInt - 1 + 2 * index + i
- if (level < maxDepth) {
- val impurity = if (i == 0) {
- nodeSplitStats._2.leftImpurity
- } else {
- nodeSplitStats._2.rightImpurity
- }
- logDebug("nodeIndex = " + nodeIndex + ", impurity = " + impurity)
- // noting the parent impurities
- parentImpurities(nodeIndex) = impurity
- // noting the parents filters for the child nodes
- val childFilter = new Filter(nodeSplitStats._1, if (i == 0) -1 else 1)
- filters(nodeIndex) = childFilter :: filters((nodeIndex - 1) / 2)
- for (filter <- filters(nodeIndex)) {
- logDebug("Filter = " + filter)
- }
+ val impurity = if (i == 0) {
+ nodeSplitStats._2.leftImpurity
+ } else {
+ nodeSplitStats._2.rightImpurity
}
+ logDebug("nodeIndex = " + nodeIndex + ", impurity = " + impurity)
+ // noting the parent impurities
+ parentImpurities(nodeIndex) = impurity
--- End diff --
I'm not sure that would help here, but at some point down the line (not this PR), I do want to include this impurity info in the growing tree structure itself. I will make a JIRA for it.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16322156
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -80,14 +82,12 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
val maxDepth = strategy.maxDepth
// the max number of nodes possible given the depth of the tree
val maxNumNodes = math.pow(2, maxDepth + 1).toInt - 1
- // Initialize an array to hold filters applied to points for each node.
- val filters = new Array[List[Filter]](maxNumNodes)
- // The filter at the top node is an empty list.
- filters(0) = List()
// Initialize an array to hold parent impurity calculations for each node.
val parentImpurities = new Array[Double](maxNumNodes)
// dummy value for top node (updated during first split calculation)
val nodes = new Array[Node](maxNumNodes)
+ val nodesInTree = Array.fill[Boolean](maxNumNodes)(false) // put into nodes array later?
+ nodesInTree(0) = true
--- End diff --
Is it used anywhere else?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16327981
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -531,7 +526,7 @@ object DecisionTree extends Serializable with Logging {
// numNodes: Number of nodes in this (level of tree, group),
// where nodes at deeper (larger) levels may be divided into groups.
- val numNodes = math.pow(2, level).toInt / numGroups
+ val numNodes = (1 << level) / numGroups
logDebug("numNodes = " + numNodes)
// Find the number of features by looking at the first sample.
--- End diff --
Thanks! I forgot to port that change from my next PR.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52378539
Passes scala style checks on my laptop now. Hopefully good to go. Note: The DTMetadata class becomes more useful in the next planned PR, where it stores the variable number of bins per feature.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16322128
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -130,18 +129,35 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
// Find best split for all nodes at a level.
timer.start("findBestSplits")
val splitsStatsForLevel = DecisionTree.findBestSplits(treeInput, parentImpurities,
- strategy, level, filters, splits, bins, maxLevelForSingleGroup, timer)
+ strategy, level, nodes, splits, bins, maxLevelForSingleGroup, unorderedFeatures, timer)
timer.stop("findBestSplits")
+ val levelNodeIndexOffset = math.pow(2, level).toInt - 1
for ((nodeSplitStats, index) <- splitsStatsForLevel.view.zipWithIndex) {
+ val nodeIndex = levelNodeIndexOffset + index
+ val isLeftChild = level != 0 && nodeIndex % 2 == 1
+ val parentNodeIndex = if (isLeftChild) { // -1 for root node
--- End diff --
minor: Is it cleaner if we offset node index by 1? So the root node has index 1 instead of 0, and then `parentNodeIndex = nodeIndex >> 1`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52384395
[QA tests have started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18660/consoleFull) for PR 1975 at commit [`ac0b9f8`](https://github.com/apache/spark/commit/ac0b9f84ededb9aaee477f439f711d9be8e890bd).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16327149
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -531,7 +526,7 @@ object DecisionTree extends Serializable with Logging {
// numNodes: Number of nodes in this (level of tree, group),
// where nodes at deeper (larger) levels may be divided into groups.
- val numNodes = math.pow(2, level).toInt / numGroups
+ val numNodes = (1 << level) / numGroups
logDebug("numNodes = " + numNodes)
// Find the number of features by looking at the first sample.
--- End diff --
Should get `numFeatures` from metadata. Calling `first()` triggers at least one job.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52415104
Merged into master and branch-1.1. Thanks!!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by manishamde <gi...@git.apache.org>.
Github user manishamde commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16328225
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -130,22 +124,37 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
// Find best split for all nodes at a level.
timer.start("findBestSplits")
val splitsStatsForLevel = DecisionTree.findBestSplits(treeInput, parentImpurities,
- strategy, level, filters, splits, bins, maxLevelForSingleGroup, timer)
+ metadata, level, nodes, splits, bins, maxLevelForSingleGroup, timer)
timer.stop("findBestSplits")
+ val levelNodeIndexOffset = (1 << level) - 1
for ((nodeSplitStats, index) <- splitsStatsForLevel.view.zipWithIndex) {
+ val nodeIndex = levelNodeIndexOffset + index
+ val isLeftChild = level != 0 && nodeIndex % 2 == 1
+ val parentNodeIndex = if (isLeftChild) { // -1 for root node
+ (nodeIndex - 1) / 2
+ } else {
+ (nodeIndex - 2) / 2
+ }
+ // Extract info for this node (index) at the current level.
timer.start("extractNodeInfo")
- // Extract info for nodes at the current level.
extractNodeInfo(nodeSplitStats, level, index, nodes)
timer.stop("extractNodeInfo")
- timer.start("extractInfoForLowerLevels")
+ if (level != 0) {
+ // Set parent.
+ if (isLeftChild) {
+ nodes(parentNodeIndex).leftNode = Some(nodes(nodeIndex))
+ } else {
+ nodes(parentNodeIndex).rightNode = Some(nodes(nodeIndex))
+ }
+ }
// Extract info for nodes at the next lower level.
- extractInfoForLowerLevels(level, index, maxDepth, nodeSplitStats, parentImpurities,
- filters)
+ timer.start("extractInfoForLowerLevels")
+ extractInfoForLowerLevels(level, index, maxDepth, nodeSplitStats, parentImpurities)
timer.stop("extractInfoForLowerLevels")
logDebug("final best split = " + nodeSplitStats._1)
}
- require(math.pow(2, level) == splitsStatsForLevel.length)
+ require((1 << level) == splitsStatsForLevel.length)
--- End diff --
Sounds good.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16322130
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -198,29 +214,22 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
index: Int,
maxDepth: Int,
nodeSplitStats: (Split, InformationGainStats),
- parentImpurities: Array[Double],
- filters: Array[List[Filter]]): Unit = {
+ parentImpurities: Array[Double]): Unit = {
+ if (level >= maxDepth)
+ return
// 0 corresponds to the left child node and 1 corresponds to the right child node.
var i = 0
while (i <= 1) {
- // Calculate the index of the node from the node level and the index at the current level.
+ // Calculate the index of the node from the node level and the index at the current level.
val nodeIndex = math.pow(2, level + 1).toInt - 1 + 2 * index + i
- if (level < maxDepth) {
- val impurity = if (i == 0) {
- nodeSplitStats._2.leftImpurity
- } else {
- nodeSplitStats._2.rightImpurity
- }
- logDebug("nodeIndex = " + nodeIndex + ", impurity = " + impurity)
- // noting the parent impurities
- parentImpurities(nodeIndex) = impurity
- // noting the parents filters for the child nodes
- val childFilter = new Filter(nodeSplitStats._1, if (i == 0) -1 else 1)
- filters(nodeIndex) = childFilter :: filters((nodeIndex - 1) / 2)
- for (filter <- filters(nodeIndex)) {
- logDebug("Filter = " + filter)
- }
+ val impurity = if (i == 0) {
+ nodeSplitStats._2.leftImpurity
+ } else {
+ nodeSplitStats._2.rightImpurity
}
+ logDebug("nodeIndex = " + nodeIndex + ", impurity = " + impurity)
+ // noting the parent impurities
+ parentImpurities(nodeIndex) = impurity
--- End diff --
Since most of the code is removed, maybe we can unfold the while loop:
~~~
val leftNodeIndex = math.pow(2, level + 1).toInt - 1 + 2 * index
parentImpurities(leftNodeIndex) = nodeSplitStats._2.leftImpurity
val rightNodeIndex = leftNodeIndex + 1
parentImpurities(rightNodeIndex) = nodeSplitStats._2.rightImpurity
~~~
Btw, could the code be simplified if we don't use `leftNode` and `rightNode` but `childNodes: Array[Node]`?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16328077
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/impl/DTMetadata.scala ---
@@ -0,0 +1,97 @@
+/*
+ * 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.mllib.tree.impl
+
+import scala.collection.mutable
+
+import org.apache.spark.mllib.regression.LabeledPoint
+import org.apache.spark.mllib.tree.configuration.Algo._
+import org.apache.spark.mllib.tree.configuration.QuantileStrategy._
+import org.apache.spark.mllib.tree.configuration.Strategy
+import org.apache.spark.mllib.tree.impurity.Impurity
+import org.apache.spark.rdd.RDD
+
+
+/**
+ * Learning and dataset metadata for DecisionTree.
+ *
+ * @param featureArity Map: categorical feature index --> arity.
+ * I.e., the feature takes values in {0, ..., arity - 1}.
+ */
+private[tree] class DTMetadata(
+ val numFeatures: Int,
+ val numExamples: Long,
+ val numClasses: Int,
+ val maxBins: Int,
+ val featureArity: Map[Int, Int],
+ val unorderedFeatures: Set[Int],
+ val impurity: Impurity,
+ val quantileStrategy: QuantileStrategy) extends Serializable {
+
+ def isUnordered(featureIndex: Int): Boolean = unorderedFeatures.contains(featureIndex)
+
+ def isClassification: Boolean = numClasses >= 2
+
+ def isMulticlass: Boolean = numClasses > 2
+
+ def isMulticlassWithCategoricalFeatures: Boolean = isMulticlass && (featureArity.size > 0)
+
+ def isCategorical(featureIndex: Int): Boolean = featureArity.contains(featureIndex)
+
+ def isContinuous(featureIndex: Int): Boolean = !featureArity.contains(featureIndex)
+
+}
+
+private[tree] object DTMetadata {
+
+ def buildMetadata(input: RDD[LabeledPoint], strategy: Strategy): DTMetadata = {
+
+ val numFeatures = input.take(1)(0).features.size
+ val numExamples = input.count()
+ val numClasses = strategy.algo match {
+ case Classification => strategy.numClassesForClassification
+ case Regression => 0
+ }
+
+ val maxBins = math.min(strategy.maxBins, numExamples).toInt
+
+ val unorderedFeatures = new mutable.HashSet[Int]()
+ if (numClasses > 2) {
+ strategy.categoricalFeaturesInfo.foreach { case (f, k) =>
+ val numUnorderedBins = (1 << k - 1) - 1
+ if (numUnorderedBins < maxBins) {
+ unorderedFeatures.add(f)
+ } else {
+ // TODO: Allow this case, where we simply will know nothing about some categories?
+ require(k < maxBins, "maxBins should be greater than max categories " +
+ "in categorical features")
+ }
+ }
+ } else {
+ strategy.categoricalFeaturesInfo.foreach { case (f, k) =>
--- End diff --
The code actually relies on this since it uses one more bin than it needs to. The correction is in my next code update, sorry.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by manishamde <gi...@git.apache.org>.
Github user manishamde commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16328124
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -62,43 +62,38 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
timer.start("init")
val retaggedInput = input.retag(classOf[LabeledPoint])
+ val metadata = DTMetadata.buildMetadata(retaggedInput, strategy)
logDebug("algo = " + strategy.algo)
// Find the splits and the corresponding bins (interval between the splits) using a sample
// of the input data.
timer.start("findSplitsBins")
- val (splits, bins) = DecisionTree.findSplitsBins(retaggedInput, strategy)
+ val (splits, bins) = DecisionTree.findSplitsBins(retaggedInput, metadata)
val numBins = bins(0).length
timer.stop("findSplitsBins")
logDebug("numBins = " + numBins)
+ // Bin feature values (TreePoint representation).
// Cache input RDD for speedup during multiple passes.
- val treeInput = TreePoint.convertToTreeRDD(retaggedInput, strategy, bins)
+ val treeInput = TreePoint.convertToTreeRDD(retaggedInput, bins, metadata)
.persist(StorageLevel.MEMORY_AND_DISK)
+ val numFeatures = metadata.numFeatures
// depth of the decision tree
val maxDepth = strategy.maxDepth
// the max number of nodes possible given the depth of the tree
- val maxNumNodes = math.pow(2, maxDepth + 1).toInt - 1
- // Initialize an array to hold filters applied to points for each node.
- val filters = new Array[List[Filter]](maxNumNodes)
- // The filter at the top node is an empty list.
- filters(0) = List()
+ val maxNumNodes = (2 << maxDepth) - 1
--- End diff --
May be a comment explaining this calculation will help. Even the previous code might be a good comment. :-)
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16327382
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/impl/DTMetadata.scala ---
@@ -0,0 +1,97 @@
+/*
+ * 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.mllib.tree.impl
+
+import scala.collection.mutable
+
+import org.apache.spark.mllib.regression.LabeledPoint
+import org.apache.spark.mllib.tree.configuration.Algo._
+import org.apache.spark.mllib.tree.configuration.QuantileStrategy._
+import org.apache.spark.mllib.tree.configuration.Strategy
+import org.apache.spark.mllib.tree.impurity.Impurity
+import org.apache.spark.rdd.RDD
+
+
+/**
+ * Learning and dataset metadata for DecisionTree.
+ *
+ * @param featureArity Map: categorical feature index --> arity.
+ * I.e., the feature takes values in {0, ..., arity - 1}.
+ */
+private[tree] class DTMetadata(
+ val numFeatures: Int,
+ val numExamples: Long,
+ val numClasses: Int,
+ val maxBins: Int,
+ val featureArity: Map[Int, Int],
+ val unorderedFeatures: Set[Int],
+ val impurity: Impurity,
+ val quantileStrategy: QuantileStrategy) extends Serializable {
+
+ def isUnordered(featureIndex: Int): Boolean = unorderedFeatures.contains(featureIndex)
+
+ def isClassification: Boolean = numClasses >= 2
+
+ def isMulticlass: Boolean = numClasses > 2
+
+ def isMulticlassWithCategoricalFeatures: Boolean = isMulticlass && (featureArity.size > 0)
+
+ def isCategorical(featureIndex: Int): Boolean = featureArity.contains(featureIndex)
+
+ def isContinuous(featureIndex: Int): Boolean = !featureArity.contains(featureIndex)
+
+}
+
+private[tree] object DTMetadata {
+
+ def buildMetadata(input: RDD[LabeledPoint], strategy: Strategy): DTMetadata = {
+
+ val numFeatures = input.take(1)(0).features.size
+ val numExamples = input.count()
+ val numClasses = strategy.algo match {
+ case Classification => strategy.numClassesForClassification
+ case Regression => 0
+ }
+
+ val maxBins = math.min(strategy.maxBins, numExamples).toInt
+
+ val unorderedFeatures = new mutable.HashSet[Int]()
+ if (numClasses > 2) {
+ strategy.categoricalFeaturesInfo.foreach { case (f, k) =>
+ val numUnorderedBins = (1 << k - 1) - 1
--- End diff --
Need to check the value of `k` first. If `k > 30`, the result will be unexpected. Using `1L` instead of `1` may help.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52379941
[QA tests have finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18653/consoleFull) for PR 1975 at commit [`db0d773`](https://github.com/apache/spark/commit/db0d7732a8cece3dc0188923e6c2939c09ee686a).
* This patch **passes** unit tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16323074
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -130,18 +129,35 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
// Find best split for all nodes at a level.
timer.start("findBestSplits")
val splitsStatsForLevel = DecisionTree.findBestSplits(treeInput, parentImpurities,
- strategy, level, filters, splits, bins, maxLevelForSingleGroup, timer)
+ strategy, level, nodes, splits, bins, maxLevelForSingleGroup, unorderedFeatures, timer)
timer.stop("findBestSplits")
+ val levelNodeIndexOffset = math.pow(2, level).toInt - 1
for ((nodeSplitStats, index) <- splitsStatsForLevel.view.zipWithIndex) {
+ val nodeIndex = levelNodeIndexOffset + index
+ val isLeftChild = level != 0 && nodeIndex % 2 == 1
+ val parentNodeIndex = if (isLeftChild) { // -1 for root node
--- End diff --
Sounds good, but I will save that for the next PR so that there are fewer changes to propagate.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16322133
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -556,135 +568,98 @@ object DecisionTree extends Serializable with Logging {
// shift when more than one group is used at deep tree level
val groupShift = numNodes * groupIndex
- /** Find the filters used before reaching the current code. */
- def findParentFilters(nodeIndex: Int): List[Filter] = {
- if (level == 0) {
- List[Filter]()
- } else {
- val nodeFilterIndex = math.pow(2, level).toInt - 1 + nodeIndex + groupShift
- filters(nodeFilterIndex)
- }
- }
-
/**
- * Find whether the sample is valid input for the current node, i.e., whether it passes through
- * all the filters for the current node.
+ * Get the node index corresponding to this data point.
+ * This is used during training, mimicking prediction.
+ * @return Leaf index if the data point reaches a leaf.
+ * Otherwise, last node reachable in tree matching this example.
*/
- def isSampleValid(parentFilters: List[Filter], treePoint: TreePoint): Boolean = {
- // leaf
- if ((level > 0) && (parentFilters.length == 0)) {
- return false
- }
-
- // Apply each filter and check sample validity. Return false when invalid condition found.
- parentFilters.foreach { filter =>
- val featureIndex = filter.split.feature
- val comparison = filter.comparison
- val isFeatureContinuous = filter.split.featureType == Continuous
- if (isFeatureContinuous) {
- val binId = treePoint.binnedFeatures(featureIndex)
- val bin = bins(featureIndex)(binId)
- val featureValue = bin.highSplit.threshold
- val threshold = filter.split.threshold
- comparison match {
- case -1 => if (featureValue > threshold) return false
- case 1 => if (featureValue <= threshold) return false
+ def predictNodeIndex(node: Node, features: Array[Int]): Int = {
+ if (node.isLeaf) {
+ node.id
+ } else {
+ val featureIndex = node.split.get.feature
+ val splitLeft = node.split.get.featureType match {
+ case Continuous => {
+ val binIndex = features(featureIndex)
+ val featureValueUpperBound = bins(featureIndex)(binIndex).highSplit.threshold
+ // bin binIndex has range (bin.lowSplit.threshold, bin.highSplit.threshold]
+ // We do not need to check lowSplit since bins are separated by splits.
+ featureValueUpperBound <= node.split.get.threshold
}
- } else {
- val numFeatureCategories = strategy.categoricalFeaturesInfo(featureIndex)
- val isSpaceSufficientForAllCategoricalSplits =
- numBins > math.pow(2, numFeatureCategories.toInt - 1) - 1
- val isUnorderedFeature =
- isMulticlassClassification && isSpaceSufficientForAllCategoricalSplits
- val featureValue = if (isUnorderedFeature) {
- treePoint.binnedFeatures(featureIndex)
+ case Categorical => {
+ val featureValue = if (unorderedFeatures.contains(featureIndex)) {
+ features(featureIndex)
+ } else {
+ val binIndex = features(featureIndex)
+ bins(featureIndex)(binIndex).category
+ }
+ node.split.get.categories.contains(featureValue)
+ }
+ case _ => throw new RuntimeException(s"predictNodeIndex failed for unknown reason.")
+ }
+ if (node.leftNode.isEmpty || node.rightNode.isEmpty) {
+ // Return index from next layer of nodes to train
+ if (splitLeft) {
+ node.id * 2 + 1 // left
} else {
- val binId = treePoint.binnedFeatures(featureIndex)
- bins(featureIndex)(binId).category
+ node.id * 2 + 2 // right
}
- val containsFeature = filter.split.categories.contains(featureValue)
- comparison match {
- case -1 => if (!containsFeature) return false
- case 1 => if (containsFeature) return false
+ } else {
+ if (splitLeft) {
+ predictNodeIndex(node.leftNode.get, features)
+ } else {
+ predictNodeIndex(node.rightNode.get, features)
}
}
}
+ }
- // Return true when the sample is valid for all filters.
- true
+ def nodeIndexToLevel(idx: Int): Int = {
+ if (idx == 0) {
+ 0
+ } else {
+ math.floor(math.log(idx) / math.log(2)).toInt
--- End diff --
If we use 1-indexing, this is `java.lang.Integer.highestOneBit(idx) - 1`, which is much faster than `math.log`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16322135
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -818,36 +760,25 @@ object DecisionTree extends Serializable with Logging {
*
* @param agg Array storing aggregate calculation, updated by this function.
* Size: 3 * numBins * numFeatures * numNodes
- * @param arr Bin mapping from findBinsForLevel.
- * Array of size 1 + (numFeatures * numNodes).
+ * @param treePoint Data point being aggregated.
+ * @param nodeIndex Node corresponding to treePoint. Indexed from 0 at start of (level, group).
* @return agg
*/
- def regressionBinSeqOp(arr: Array[Double], agg: Array[Double]): Unit = {
- // Iterate over all nodes.
- var nodeIndex = 0
- while (nodeIndex < numNodes) {
- // Check whether the instance was valid for this nodeIndex.
- val validSignalIndex = 1 + numFeatures * nodeIndex
- val isSampleValidForNode = arr(validSignalIndex) != InvalidBinIndex
- if (isSampleValidForNode) {
- // actual class label
- val label = arr(0)
- // Iterate over all features.
- var featureIndex = 0
- while (featureIndex < numFeatures) {
- // Find the bin index for this feature.
- val arrShift = 1 + numFeatures * nodeIndex
- val arrIndex = arrShift + featureIndex
- // Update count, sum, and sum^2 for one bin.
- val aggShift = 3 * numBins * numFeatures * nodeIndex
- val aggIndex = aggShift + 3 * featureIndex * numBins + arr(arrIndex).toInt * 3
- agg(aggIndex) = agg(aggIndex) + 1
- agg(aggIndex + 1) = agg(aggIndex + 1) + label
- agg(aggIndex + 2) = agg(aggIndex + 2) + label * label
- featureIndex += 1
- }
- }
- nodeIndex += 1
+ def regressionBinSeqOp(agg: Array[Double], treePoint: TreePoint, nodeIndex: Int): Unit = {
+ val label = treePoint.label
+ // Iterate over all features.
+ var featureIndex = 0
+ while (featureIndex < numFeatures) {
+ // Update count, sum, and sum^2 for one bin.
+ val binIndex = treePoint.binnedFeatures(featureIndex)
+ val aggIndex =
+ 3 * numBins * numFeatures * nodeIndex +
+ 3 * numBins * featureIndex +
+ 3 * binIndex
+ agg(aggIndex) = agg(aggIndex) + 1
--- End diff --
use `agg(aggIndex) += 1`?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16327359
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -905,144 +821,140 @@ object DecisionTree extends Serializable with Logging {
}
// Calculate bin aggregates.
+ timer.start("aggregation")
val binAggregates = {
- binMappedRDD.aggregate(Array.fill[Double](binAggregateLength)(0))(binSeqOp,binCombOp)
+ input.aggregate(Array.fill[Double](binAggregateLength)(0))(binSeqOp, binCombOp)
}
timer.stop("aggregation")
logDebug("binAggregates.length = " + binAggregates.length)
/**
- * Calculates the information gain for all splits based upon left/right split aggregates.
- * @param leftNodeAgg left node aggregates
- * @param featureIndex feature index
- * @param splitIndex split index
- * @param rightNodeAgg right node aggregate
+ * Calculate the information gain for a given (feature, split) based upon left/right aggregates.
+ * @param leftNodeAgg left node aggregates for this (feature, split)
+ * @param rightNodeAgg right node aggregate for this (feature, split)
* @param topImpurity impurity of the parent node
* @return information gain and statistics for all splits
*/
def calculateGainForSplit(
- leftNodeAgg: Array[Array[Array[Double]]],
- featureIndex: Int,
- splitIndex: Int,
- rightNodeAgg: Array[Array[Array[Double]]],
+ leftNodeAgg: Array[Double],
+ rightNodeAgg: Array[Double],
topImpurity: Double): InformationGainStats = {
- strategy.algo match {
- case Classification =>
- val leftCounts: Array[Double] = leftNodeAgg(featureIndex)(splitIndex)
- val rightCounts: Array[Double] = rightNodeAgg(featureIndex)(splitIndex)
- val leftTotalCount = leftCounts.sum
- val rightTotalCount = rightCounts.sum
-
- val impurity = {
- if (level > 0) {
- topImpurity
- } else {
- // Calculate impurity for root node.
- val rootNodeCounts = new Array[Double](numClasses)
- var classIndex = 0
- while (classIndex < numClasses) {
- rootNodeCounts(classIndex) = leftCounts(classIndex) + rightCounts(classIndex)
- classIndex += 1
- }
- strategy.impurity.calculate(rootNodeCounts, leftTotalCount + rightTotalCount)
- }
- }
+ if (metadata.isClassification) {
+ val leftTotalCount = leftNodeAgg.sum
+ val rightTotalCount = rightNodeAgg.sum
- val totalCount = leftTotalCount + rightTotalCount
- if (totalCount == 0) {
- // Return arbitrary prediction.
- return new InformationGainStats(0, topImpurity, topImpurity, topImpurity, 0)
+ val impurity = {
+ if (level > 0) {
+ topImpurity
+ } else {
+ // Calculate impurity for root node.
+ val rootNodeCounts = new Array[Double](numClasses)
+ var classIndex = 0
+ while (classIndex < numClasses) {
+ rootNodeCounts(classIndex) = leftNodeAgg(classIndex) + rightNodeAgg(classIndex)
+ classIndex += 1
+ }
+ metadata.impurity.calculate(rootNodeCounts, leftTotalCount + rightTotalCount)
}
+ }
- // Sum of count for each label
- val leftRightCounts: Array[Double] =
- leftCounts.zip(rightCounts).map { case (leftCount, rightCount) =>
- leftCount + rightCount
- }
+ val totalCount = leftTotalCount + rightTotalCount
+ if (totalCount == 0) {
+ // Return arbitrary prediction.
+ return new InformationGainStats(0, topImpurity, topImpurity, topImpurity, 0)
+ }
- def indexOfLargestArrayElement(array: Array[Double]): Int = {
- val result = array.foldLeft(-1, Double.MinValue, 0) {
- case ((maxIndex, maxValue, currentIndex), currentValue) =>
- if (currentValue > maxValue) {
- (currentIndex, currentValue, currentIndex + 1)
- } else {
- (maxIndex, maxValue, currentIndex + 1)
- }
- }
- if (result._1 < 0) {
- throw new RuntimeException("DecisionTree internal error:" +
- " calculateGainForSplit failed in indexOfLargestArrayElement")
- }
- result._1
+ // Sum of count for each label
+ val leftrightNodeAgg: Array[Double] =
+ leftNodeAgg.zip(rightNodeAgg).map { case (leftCount, rightCount) =>
+ leftCount + rightCount
}
- val predict = indexOfLargestArrayElement(leftRightCounts)
- val prob = leftRightCounts(predict) / totalCount
-
- val leftImpurity = if (leftTotalCount == 0) {
- topImpurity
- } else {
- strategy.impurity.calculate(leftCounts, leftTotalCount)
+ def indexOfLargestArrayElement(array: Array[Double]): Int = {
+ val result = array.foldLeft(-1, Double.MinValue, 0) {
+ case ((maxIndex, maxValue, currentIndex), currentValue) =>
+ if (currentValue > maxValue) {
+ (currentIndex, currentValue, currentIndex + 1)
+ } else {
+ (maxIndex, maxValue, currentIndex + 1)
+ }
}
- val rightImpurity = if (rightTotalCount == 0) {
- topImpurity
- } else {
- strategy.impurity.calculate(rightCounts, rightTotalCount)
+ if (result._1 < 0) {
+ throw new RuntimeException("DecisionTree internal error:" +
+ " calculateGainForSplit failed in indexOfLargestArrayElement")
}
+ result._1
+ }
- val leftWeight = leftTotalCount / totalCount
- val rightWeight = rightTotalCount / totalCount
+ val predict = indexOfLargestArrayElement(leftrightNodeAgg)
+ val prob = leftrightNodeAgg(predict) / totalCount
- val gain = impurity - leftWeight * leftImpurity - rightWeight * rightImpurity
+ val leftImpurity = if (leftTotalCount == 0) {
+ topImpurity
+ } else {
+ metadata.impurity.calculate(leftNodeAgg, leftTotalCount)
+ }
+ val rightImpurity = if (rightTotalCount == 0) {
+ topImpurity
+ } else {
+ metadata.impurity.calculate(rightNodeAgg, rightTotalCount)
+ }
- new InformationGainStats(gain, impurity, leftImpurity, rightImpurity, predict, prob)
+ val leftWeight = leftTotalCount / totalCount
+ val rightWeight = rightTotalCount / totalCount
- case Regression =>
- val leftCount = leftNodeAgg(featureIndex)(splitIndex)(0)
- val leftSum = leftNodeAgg(featureIndex)(splitIndex)(1)
- val leftSumSquares = leftNodeAgg(featureIndex)(splitIndex)(2)
+ val gain = impurity - leftWeight * leftImpurity - rightWeight * rightImpurity
- val rightCount = rightNodeAgg(featureIndex)(splitIndex)(0)
- val rightSum = rightNodeAgg(featureIndex)(splitIndex)(1)
- val rightSumSquares = rightNodeAgg(featureIndex)(splitIndex)(2)
+ new InformationGainStats(gain, impurity, leftImpurity, rightImpurity, predict, prob)
- val impurity = {
- if (level > 0) {
- topImpurity
- } else {
- // Calculate impurity for root node.
- val count = leftCount + rightCount
- val sum = leftSum + rightSum
- val sumSquares = leftSumSquares + rightSumSquares
- strategy.impurity.calculate(count, sum, sumSquares)
- }
- }
+ } else {
+ // Regression
- if (leftCount == 0) {
- return new InformationGainStats(0, topImpurity, Double.MinValue, topImpurity,
- rightSum / rightCount)
- }
- if (rightCount == 0) {
- return new InformationGainStats(0, topImpurity ,topImpurity,
- Double.MinValue, leftSum / leftCount)
+ val leftCount = leftNodeAgg(0)
+ val leftSum = leftNodeAgg(1)
+ val leftSumSquares = leftNodeAgg(2)
+
+ val rightCount = rightNodeAgg(0)
+ val rightSum = rightNodeAgg(1)
+ val rightSumSquares = rightNodeAgg(2)
+
+ val impurity = {
+ if (level > 0) {
+ topImpurity
+ } else {
+ // Calculate impurity for root node.
+ val count = leftCount + rightCount
+ val sum = leftSum + rightSum
+ val sumSquares = leftSumSquares + rightSumSquares
+ metadata.impurity.calculate(count, sum, sumSquares)
}
+ }
- val leftImpurity = strategy.impurity.calculate(leftCount, leftSum, leftSumSquares)
- val rightImpurity = strategy.impurity.calculate(rightCount, rightSum, rightSumSquares)
+ if (leftCount == 0) {
+ return new InformationGainStats(0, topImpurity, Double.MinValue, topImpurity,
+ rightSum / rightCount)
+ }
+ if (rightCount == 0) {
+ return new InformationGainStats(0, topImpurity, topImpurity,
+ Double.MinValue, leftSum / leftCount)
+ }
- val leftWeight = leftCount.toDouble / (leftCount + rightCount)
- val rightWeight = rightCount.toDouble / (leftCount + rightCount)
+ val leftImpurity = metadata.impurity.calculate(leftCount, leftSum, leftSumSquares)
+ val rightImpurity = metadata.impurity.calculate(rightCount, rightSum, rightSumSquares)
- val gain = {
- if (level > 0) {
- impurity - leftWeight * leftImpurity - rightWeight * rightImpurity
- } else {
- impurity - leftWeight * leftImpurity - rightWeight * rightImpurity
- }
+ val leftWeight = leftCount.toDouble / (leftCount + rightCount)
+ val rightWeight = rightCount.toDouble / (leftCount + rightCount)
+
+ val gain = {
+ if (level > 0) {
+ impurity - leftWeight * leftImpurity - rightWeight * rightImpurity
+ } else {
+ impurity - leftWeight * leftImpurity - rightWeight * rightImpurity
--- End diff --
There is no difference between if and else.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52369173
I will fix the scala style QA failure by bringing the metadata class from my next planned PR into this one. Updating soon...
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/spark/pull/1975
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52413762
[QA tests have finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18692/consoleFull) for PR 1975 at commit [`3726d20`](https://github.com/apache/spark/commit/3726d2003e681e569a6d1fbf4af65909500f1b80).
* This patch **passes** unit tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16327365
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/impl/DTMetadata.scala ---
@@ -0,0 +1,97 @@
+/*
+ * 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.mllib.tree.impl
+
+import scala.collection.mutable
+
+import org.apache.spark.mllib.regression.LabeledPoint
+import org.apache.spark.mllib.tree.configuration.Algo._
+import org.apache.spark.mllib.tree.configuration.QuantileStrategy._
+import org.apache.spark.mllib.tree.configuration.Strategy
+import org.apache.spark.mllib.tree.impurity.Impurity
+import org.apache.spark.rdd.RDD
+
+
+/**
+ * Learning and dataset metadata for DecisionTree.
+ *
+ * @param featureArity Map: categorical feature index --> arity.
+ * I.e., the feature takes values in {0, ..., arity - 1}.
+ */
+private[tree] class DTMetadata(
+ val numFeatures: Int,
+ val numExamples: Long,
+ val numClasses: Int,
--- End diff --
It would be helpful if we add doc for `numClasses` mentioning its value for regression problems.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16323073
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -80,14 +82,12 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
val maxDepth = strategy.maxDepth
// the max number of nodes possible given the depth of the tree
val maxNumNodes = math.pow(2, maxDepth + 1).toInt - 1
- // Initialize an array to hold filters applied to points for each node.
- val filters = new Array[List[Filter]](maxNumNodes)
- // The filter at the top node is an empty list.
- filters(0) = List()
// Initialize an array to hold parent impurity calculations for each node.
val parentImpurities = new Array[Double](maxNumNodes)
// dummy value for top node (updated during first split calculation)
val nodes = new Array[Node](maxNumNodes)
+ val nodesInTree = Array.fill[Boolean](maxNumNodes)(false) // put into nodes array later?
+ nodesInTree(0) = true
--- End diff --
Nope; I intended to use it for another optimization (ignoring unused branches of the tree) but will postpone that. Will remove it for now.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by manishamde <gi...@git.apache.org>.
Github user manishamde commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16328129
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -130,22 +124,37 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
// Find best split for all nodes at a level.
timer.start("findBestSplits")
val splitsStatsForLevel = DecisionTree.findBestSplits(treeInput, parentImpurities,
- strategy, level, filters, splits, bins, maxLevelForSingleGroup, timer)
+ metadata, level, nodes, splits, bins, maxLevelForSingleGroup, timer)
timer.stop("findBestSplits")
+ val levelNodeIndexOffset = (1 << level) - 1
for ((nodeSplitStats, index) <- splitsStatsForLevel.view.zipWithIndex) {
+ val nodeIndex = levelNodeIndexOffset + index
+ val isLeftChild = level != 0 && nodeIndex % 2 == 1
+ val parentNodeIndex = if (isLeftChild) { // -1 for root node
+ (nodeIndex - 1) / 2
+ } else {
+ (nodeIndex - 2) / 2
+ }
+ // Extract info for this node (index) at the current level.
timer.start("extractNodeInfo")
- // Extract info for nodes at the current level.
extractNodeInfo(nodeSplitStats, level, index, nodes)
timer.stop("extractNodeInfo")
- timer.start("extractInfoForLowerLevels")
+ if (level != 0) {
+ // Set parent.
+ if (isLeftChild) {
+ nodes(parentNodeIndex).leftNode = Some(nodes(nodeIndex))
+ } else {
+ nodes(parentNodeIndex).rightNode = Some(nodes(nodeIndex))
+ }
+ }
// Extract info for nodes at the next lower level.
- extractInfoForLowerLevels(level, index, maxDepth, nodeSplitStats, parentImpurities,
- filters)
+ timer.start("extractInfoForLowerLevels")
+ extractInfoForLowerLevels(level, index, maxDepth, nodeSplitStats, parentImpurities)
timer.stop("extractInfoForLowerLevels")
logDebug("final best split = " + nodeSplitStats._1)
}
- require(math.pow(2, level) == splitsStatsForLevel.length)
+ require((1 << level) == splitsStatsForLevel.length)
--- End diff --
Ditto: comment will help to maintain code.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52368269
[QA tests have finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/18630/consoleFull) for PR 1975 at commit [`931a3a7`](https://github.com/apache/spark/commit/931a3a714e44ab1138dac18bc3b497892d36e3e5).
* This patch **fails** unit tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52378348
@jkbradley There are couple `math.pow(2, ..)` calls in the implementation. We can use `<<` instead, which is faster than `math.pow`. As mentioned in the comments, if we use 1-indexing for nodes, the index calculation will be much simpler. But I'm not sure about whether this is an easy change.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16327409
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/impl/DTMetadata.scala ---
@@ -0,0 +1,97 @@
+/*
+ * 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.mllib.tree.impl
+
+import scala.collection.mutable
+
+import org.apache.spark.mllib.regression.LabeledPoint
+import org.apache.spark.mllib.tree.configuration.Algo._
+import org.apache.spark.mllib.tree.configuration.QuantileStrategy._
+import org.apache.spark.mllib.tree.configuration.Strategy
+import org.apache.spark.mllib.tree.impurity.Impurity
+import org.apache.spark.rdd.RDD
+
+
+/**
+ * Learning and dataset metadata for DecisionTree.
+ *
+ * @param featureArity Map: categorical feature index --> arity.
+ * I.e., the feature takes values in {0, ..., arity - 1}.
+ */
+private[tree] class DTMetadata(
+ val numFeatures: Int,
+ val numExamples: Long,
+ val numClasses: Int,
+ val maxBins: Int,
+ val featureArity: Map[Int, Int],
+ val unorderedFeatures: Set[Int],
+ val impurity: Impurity,
+ val quantileStrategy: QuantileStrategy) extends Serializable {
+
+ def isUnordered(featureIndex: Int): Boolean = unorderedFeatures.contains(featureIndex)
+
+ def isClassification: Boolean = numClasses >= 2
+
+ def isMulticlass: Boolean = numClasses > 2
+
+ def isMulticlassWithCategoricalFeatures: Boolean = isMulticlass && (featureArity.size > 0)
+
+ def isCategorical(featureIndex: Int): Boolean = featureArity.contains(featureIndex)
+
+ def isContinuous(featureIndex: Int): Boolean = !featureArity.contains(featureIndex)
+
+}
+
+private[tree] object DTMetadata {
+
+ def buildMetadata(input: RDD[LabeledPoint], strategy: Strategy): DTMetadata = {
+
+ val numFeatures = input.take(1)(0).features.size
+ val numExamples = input.count()
+ val numClasses = strategy.algo match {
+ case Classification => strategy.numClassesForClassification
+ case Regression => 0
+ }
+
+ val maxBins = math.min(strategy.maxBins, numExamples).toInt
+
+ val unorderedFeatures = new mutable.HashSet[Int]()
+ if (numClasses > 2) {
+ strategy.categoricalFeaturesInfo.foreach { case (f, k) =>
+ val numUnorderedBins = (1 << k - 1) - 1
+ if (numUnorderedBins < maxBins) {
+ unorderedFeatures.add(f)
+ } else {
+ // TODO: Allow this case, where we simply will know nothing about some categories?
+ require(k < maxBins, "maxBins should be greater than max categories " +
+ "in categorical features")
+ }
+ }
+ } else {
+ strategy.categoricalFeaturesInfo.foreach { case (f, k) =>
--- End diff --
Do we allow `maxBins >= k` in binary classification?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by manishamde <gi...@git.apache.org>.
Github user manishamde commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52413757
Apart from minor comments, LGTM!
This is an awesome PR. The Filter class had to go for a long time -- thanks for doing it. :-) And the predictNodeIndex is an awesome non-obvious optimization.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the pull request:
https://github.com/apache/spark/pull/1975#issuecomment-52412973
@mengxr Thanks for the comments; updates made!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16328188
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -130,22 +124,37 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
// Find best split for all nodes at a level.
timer.start("findBestSplits")
val splitsStatsForLevel = DecisionTree.findBestSplits(treeInput, parentImpurities,
- strategy, level, filters, splits, bins, maxLevelForSingleGroup, timer)
+ metadata, level, nodes, splits, bins, maxLevelForSingleGroup, timer)
timer.stop("findBestSplits")
+ val levelNodeIndexOffset = (1 << level) - 1
for ((nodeSplitStats, index) <- splitsStatsForLevel.view.zipWithIndex) {
+ val nodeIndex = levelNodeIndexOffset + index
+ val isLeftChild = level != 0 && nodeIndex % 2 == 1
+ val parentNodeIndex = if (isLeftChild) { // -1 for root node
+ (nodeIndex - 1) / 2
+ } else {
+ (nodeIndex - 2) / 2
+ }
+ // Extract info for this node (index) at the current level.
timer.start("extractNodeInfo")
- // Extract info for nodes at the current level.
extractNodeInfo(nodeSplitStats, level, index, nodes)
timer.stop("extractNodeInfo")
- timer.start("extractInfoForLowerLevels")
+ if (level != 0) {
+ // Set parent.
+ if (isLeftChild) {
+ nodes(parentNodeIndex).leftNode = Some(nodes(nodeIndex))
+ } else {
+ nodes(parentNodeIndex).rightNode = Some(nodes(nodeIndex))
+ }
+ }
// Extract info for nodes at the next lower level.
- extractInfoForLowerLevels(level, index, maxDepth, nodeSplitStats, parentImpurities,
- filters)
+ timer.start("extractInfoForLowerLevels")
+ extractInfoForLowerLevels(level, index, maxDepth, nodeSplitStats, parentImpurities)
timer.stop("extractInfoForLowerLevels")
logDebug("final best split = " + nodeSplitStats._1)
}
- require(math.pow(2, level) == splitsStatsForLevel.length)
+ require((1 << level) == splitsStatsForLevel.length)
--- End diff --
In my next update, I actually moved all of these to intuitively named functions such as numNodesInLevel(). I'd like to stick with that, but leave that in the next update if that's OK. That will also help to consolidate the indexing code and make the 1-indexing change easier to make.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-3042] [mllib] DecisionTree Filter top-d...
Posted by manishamde <gi...@git.apache.org>.
Github user manishamde commented on a diff in the pull request:
https://github.com/apache/spark/pull/1975#discussion_r16328127
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/tree/DecisionTree.scala ---
@@ -130,22 +124,37 @@ class DecisionTree (private val strategy: Strategy) extends Serializable with Lo
// Find best split for all nodes at a level.
timer.start("findBestSplits")
val splitsStatsForLevel = DecisionTree.findBestSplits(treeInput, parentImpurities,
- strategy, level, filters, splits, bins, maxLevelForSingleGroup, timer)
+ metadata, level, nodes, splits, bins, maxLevelForSingleGroup, timer)
timer.stop("findBestSplits")
+ val levelNodeIndexOffset = (1 << level) - 1
--- End diff --
Ditto: comment might help to understand the calculation using bit shift.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org