You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ch...@apache.org on 2018/08/30 16:29:05 UTC
[2/3] ignite git commit: IGNITE-9237: [ML] Random forest optimization
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/RandomForestTrainer.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/RandomForestTrainer.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/RandomForestTrainer.java
index 8608f09..cb25aa3 100644
--- a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/RandomForestTrainer.java
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/RandomForestTrainer.java
@@ -17,45 +17,359 @@
package org.apache.ignite.ml.tree.randomforest;
-import org.apache.ignite.ml.composition.BaggingModelTrainer;
-import org.apache.ignite.ml.composition.predictionsaggregator.PredictionsAggregator;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Queue;
+import java.util.Random;
+import java.util.Set;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+import org.apache.ignite.ml.composition.ModelsComposition;
+import org.apache.ignite.ml.dataset.Dataset;
+import org.apache.ignite.ml.dataset.DatasetBuilder;
+import org.apache.ignite.ml.dataset.feature.BucketMeta;
+import org.apache.ignite.ml.dataset.feature.FeatureMeta;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedDatasetBuilder;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedDatasetPartition;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedVector;
+import org.apache.ignite.ml.dataset.primitive.builder.context.EmptyContextBuilder;
+import org.apache.ignite.ml.dataset.primitive.context.EmptyContext;
+import org.apache.ignite.ml.math.functions.IgniteBiFunction;
+import org.apache.ignite.ml.math.primitives.vector.Vector;
+import org.apache.ignite.ml.trainers.DatasetTrainer;
+import org.apache.ignite.ml.tree.randomforest.data.FeaturesCountSelectionStrategies;
+import org.apache.ignite.ml.tree.randomforest.data.NodeId;
+import org.apache.ignite.ml.tree.randomforest.data.NodeSplit;
+import org.apache.ignite.ml.tree.randomforest.data.TreeNode;
+import org.apache.ignite.ml.tree.randomforest.data.TreeRoot;
+import org.apache.ignite.ml.tree.randomforest.data.impurity.ImpurityComputer;
+import org.apache.ignite.ml.tree.randomforest.data.impurity.ImpurityHistogramsComputer;
+import org.apache.ignite.ml.tree.randomforest.data.statistics.LeafValuesComputer;
+import org.apache.ignite.ml.tree.randomforest.data.statistics.NormalDistributionStatistics;
+import org.apache.ignite.ml.tree.randomforest.data.statistics.NormalDistributionStatisticsComputer;
/**
- * Abstract random forest trainer.
+ * Class represents a realization of Random Forest algorithm. Main idea of this realization is that at each learning
+ * iteration it tries to aggregate statistics on impurity for each corner nodes (leaves that may be splitted on a new
+ * iteration) in each trees in random forest. It requires one map-reduce operation over learning dataset. After such
+ * aggregation the algorithm selects split points for each corner nodes of create leaf nodes. The algorithm stops when
+ * there is no splitting for nodes in trees. At last stage the algorithm aggregates statistics on labels for leaf nodes
+ * in one map-reduce step and sets values to leafs based these statistics.
+ *
+ * @param <L> Type of statistics aggregator for leaf values computing.
+ * @param <S> Type of impurity computer specific for algorithm.
+ * @param <T> Type of child of RandomForestTrainer using in with-methods.
*/
-public abstract class RandomForestTrainer extends BaggingModelTrainer {
- /** Max decision tree deep. */
- protected final int maxDeep;
+public abstract class RandomForestTrainer<L, S extends ImpurityComputer<BootstrappedVector, S>,
+ T extends RandomForestTrainer<L, S, T>> extends DatasetTrainer<ModelsComposition, Double> {
+ /** Bucket size factor. */
+ private static final double BUCKET_SIZE_FACTOR = (1 / 10.0);
+
+ /** Count of trees. */
+ private int cntOfTrees = 1;
+
+ /** Subsample size. */
+ private double subsampleSize = 1.0;
+
+ /** Max depth. */
+ private int maxDepth = 5;
+
+ /** Min impurity delta. */
+ private double minImpurityDelta = 0.0;
+
+ /** Features Meta. */
+ private List<FeatureMeta> meta;
+
+ /** Features per tree. */
+ private int featuresPerTree;
+
+ /** Seed. */
+ private long seed = System.currentTimeMillis();
+
+ /** Random generator. */
+ private Random random = new Random(seed);
+
+ /** Nodes to learn selection strategy. */
+ private Function<Queue<TreeNode>, List<TreeNode>> nodesToLearnSelectionStrgy = this::defaultNodesToLearnSelectionStrgy;
+
+ /**
+ * Create an instance of RandomForestTrainer.
+ *
+ * @param meta Features Meta.
+ */
+ public RandomForestTrainer(List<FeatureMeta> meta) {
+ this.meta = meta;
+ this.featuresPerTree = FeaturesCountSelectionStrategies.ALL.apply(meta);
+ }
+
+ /** {@inheritDoc} */
+ @Override public <K, V> ModelsComposition fit(DatasetBuilder<K, V> datasetBuilder,
+ IgniteBiFunction<K, V, Vector> featureExtractor, IgniteBiFunction<K, V, Double> lbExtractor) {
+ List<TreeRoot> models = null;
+ try (Dataset<EmptyContext, BootstrappedDatasetPartition> dataset = datasetBuilder.build(
+ new EmptyContextBuilder<>(),
+ new BootstrappedDatasetBuilder<>(featureExtractor, lbExtractor, cntOfTrees, subsampleSize))) {
+
+ init(dataset);
+ models = fit(dataset);
+ }
+ catch (Exception e) {
+ throw new RuntimeException(e);
+ }
+
+ assert models != null;
+ return buildComposition(models);
+ }
+
+ /**
+ * @return an instance of current object with valid type in according to inheritance.
+ */
+ protected abstract T instance();
+
+ /**
+ * @param cntOfTrees Count of trees.
+ * @return an instance of current object with valid type in according to inheritance.
+ */
+ public T withCountOfTrees(int cntOfTrees) {
+ this.cntOfTrees = cntOfTrees;
+ return instance();
+ }
+
+ /**
+ * @param subsampleSize Subsample size.
+ * @return an instance of current object with valid type in according to inheritance.
+ */
+ public T withSubsampleSize(double subsampleSize) {
+ this.subsampleSize = subsampleSize;
+ return instance();
+ }
+
+ /**
+ * @param maxDepth Max depth.
+ * @return an instance of current object with valid type in according to inheritance.
+ */
+ public T withMaxDepth(int maxDepth) {
+ this.maxDepth = maxDepth;
+ return instance();
+ }
- /** Min impurity decrease. */
- protected final double minImpurityDecrease;
+ /**
+ * @param minImpurityDelta Min impurity delta.
+ * @return an instance of current object with valid type in according to inheritance.
+ */
+ public T withMinImpurityDelta(double minImpurityDelta) {
+ this.minImpurityDelta = minImpurityDelta;
+ return instance();
+ }
- /** Use index structure instead of using sorting while decision tree learning. */
- protected boolean useIndex = false;
+ /**
+ * @param strgy Strgy.
+ * @return an instance of current object with valid type in according to inheritance.
+ */
+ public T withFeaturesCountSelectionStrgy(Function<List<FeatureMeta>, Integer> strgy) {
+ this.featuresPerTree = strgy.apply(meta);
+ return instance();
+ }
/**
- * Constructs new instance of BaggingModelTrainer.
+ * Sets strategy for selection nodes from learning queue in each iteration.
*
- * @param predictionsAggregator Predictions aggregator.
- * @param featureVectorSize Feature vector size.
- * @param maximumFeaturesCntPerMdl Number of features to draw from original features vector to train each model.
- * @param ensembleSize Ensemble size.
- * @param samplePartSizePerMdl Size of sample part in percent to train one model.
- * @param maxDeep Max decision tree deep.
- * @param minImpurityDecrease Min impurity decrease.
+ * @param strgy Strgy.
*/
- public RandomForestTrainer(PredictionsAggregator predictionsAggregator,
- int featureVectorSize,
- int maximumFeaturesCntPerMdl,
- int ensembleSize,
- double samplePartSizePerMdl,
- int maxDeep,
- double minImpurityDecrease) {
+ public T withNodesToLearnSelectionStrgy(Function<Queue<TreeNode>, List<TreeNode>> strgy) {
+ this.nodesToLearnSelectionStrgy = strgy;
+ return instance();
+ }
- super(predictionsAggregator, featureVectorSize, maximumFeaturesCntPerMdl,
- ensembleSize, samplePartSizePerMdl);
+ /**
+ * @param seed Seed.
+ * @return an instance of current object with valid type in according to inheritance.
+ */
+ public T withSeed(long seed) {
+ this.seed = seed;
+ this.random = new Random(seed);
+ return instance();
+ }
- this.maxDeep = maxDeep;
- this.minImpurityDecrease = minImpurityDecrease;
+ /**
+ * Init-step before learning. It may be useful collecting labels statistics step for classification.
+ *
+ * @param dataset Dataset.
+ */
+ protected void init(Dataset<EmptyContext, BootstrappedDatasetPartition> dataset) {
}
+
+ /**
+ * Trains model based on the specified data.
+ *
+ * @param dataset Dataset.
+ * @return list of decision trees.
+ */
+ private List<TreeRoot> fit(Dataset<EmptyContext, BootstrappedDatasetPartition> dataset) {
+ Queue<TreeNode> treesQueue = createRootsQueue();
+ ArrayList<TreeRoot> roots = initTrees(treesQueue);
+ Map<Integer, BucketMeta> histMeta = computeHistogramMeta(meta, dataset);
+
+ ImpurityHistogramsComputer<S> histogramsComputer = createImpurityHistogramsComputer();
+ while (!treesQueue.isEmpty()) {
+ Map<NodeId, TreeNode> nodesToLearn = getNodesToLearn(treesQueue);
+ Map<NodeId, ImpurityHistogramsComputer.NodeImpurityHistograms<S>> nodesImpHists = histogramsComputer
+ .aggregateImpurityStatistics(roots, histMeta, nodesToLearn, dataset);
+ if (nodesToLearn.size() != nodesImpHists.size())
+ throw new IllegalStateException();
+
+ for (NodeId nodeId : nodesImpHists.keySet())
+ split(treesQueue, nodesToLearn, nodesImpHists.get(nodeId));
+ }
+
+ createLeafStatisticsAggregator().setValuesForLeaves(roots, dataset);
+ return roots;
+ }
+
+ /**
+ * Split node with NodeId if need.
+ *
+ * @param learningQueue Learning queue.
+ * @param nodesToLearn Nodes to learn at current iteration.
+ * @param nodeImpurityHistograms Impurity histograms on current iteration.
+ */
+ private void split(Queue<TreeNode> learningQueue, Map<NodeId, TreeNode> nodesToLearn,
+ ImpurityHistogramsComputer.NodeImpurityHistograms<S> nodeImpurityHistograms) {
+
+ TreeNode cornerNode = nodesToLearn.get(nodeImpurityHistograms.getNodeId());
+ Optional<NodeSplit> bestSplit = nodeImpurityHistograms.findBestSplit();
+
+ if (needSplit(cornerNode, bestSplit)) {
+ List<TreeNode> children = bestSplit.get().split(cornerNode);
+ learningQueue.addAll(children);
+ }
+ else {
+ if (bestSplit.isPresent())
+ bestSplit.get().createLeaf(cornerNode);
+ else {
+ cornerNode.setImpurity(Double.NEGATIVE_INFINITY);
+ cornerNode.toLeaf(0.0);
+ }
+ }
+ }
+
+ /**
+ * Creates an instance of Histograms Computer corresponding to RF implementation.
+ */
+ protected abstract ImpurityHistogramsComputer<S> createImpurityHistogramsComputer();
+
+ /**
+ * Creates an instance of Leaf Statistics Aggregator corresponding to RF implementation.
+ */
+ protected abstract LeafValuesComputer<L> createLeafStatisticsAggregator();
+
+ /**
+ * Creates list of trees.
+ *
+ * @param treesQueue Trees queue.
+ * @return List of trees.
+ */
+ protected ArrayList<TreeRoot> initTrees(Queue<TreeNode> treesQueue) {
+ assert featuresPerTree > 0;
+ ArrayList<TreeRoot> roots = new ArrayList<>();
+
+ List<Integer> allFeatureIds = IntStream.range(0, meta.size()).boxed().collect(Collectors.toList());
+ for (TreeNode node : treesQueue) {
+ Collections.shuffle(allFeatureIds, random);
+ Set<Integer> featuresSubspace = allFeatureIds.stream()
+ .limit(featuresPerTree).collect(Collectors.toSet());
+ roots.add(new TreeRoot(node, featuresSubspace));
+ }
+
+ return roots;
+ }
+
+ /**
+ * Compute bucket metas based on feature metas and learning dataset.
+ *
+ * @param meta Features meta.
+ * @param dataset Dataset.
+ * @return bucket metas.
+ */
+ private Map<Integer, BucketMeta> computeHistogramMeta(List<FeatureMeta> meta,
+ Dataset<EmptyContext, BootstrappedDatasetPartition> dataset) {
+
+ List<NormalDistributionStatistics> stats = new NormalDistributionStatisticsComputer()
+ .computeStatistics(meta, dataset);
+
+ Map<Integer, BucketMeta> bucketsMeta = new HashMap<>();
+ for (int i = 0; i < stats.size(); i++) {
+ BucketMeta bucketMeta = new BucketMeta(meta.get(i));
+ if (!bucketMeta.getFeatureMeta().isCategoricalFeature()) {
+ NormalDistributionStatistics stat = stats.get(i);
+ bucketMeta.setMinVal(stat.min());
+ bucketMeta.setBucketSize(stat.std() * BUCKET_SIZE_FACTOR);
+ }
+ bucketsMeta.put(i, bucketMeta);
+ }
+ return bucketsMeta;
+ }
+
+ /**
+ * Creates an initial nodes queue for learning based on countOfTrees. Each of these nodes represents a root decision
+ * trees in random forest.
+ *
+ * @return initial nodes queue.
+ */
+ private Queue<TreeNode> createRootsQueue() {
+ Queue<TreeNode> roots = new LinkedList<>();
+ for (int i = 0; i < cntOfTrees; i++)
+ roots.add(new TreeNode(1, i));
+ return roots;
+ }
+
+ /**
+ * Select set of nodes for leaning from queue based in nodesToLearnSelectionStrategy.
+ *
+ * @param queue Learning queue.
+ * @return collection of nodes for learning iterations.
+ */
+ private Map<NodeId, TreeNode> getNodesToLearn(Queue<TreeNode> queue) {
+ return nodesToLearnSelectionStrgy.apply(queue).stream()
+ .collect(Collectors.toMap(TreeNode::getId, node -> node));
+ }
+
+ /**
+ * Default nodesToLearnSelectionStrategy that returns all nodes from queue.
+ *
+ * @param queue Queue.
+ * @return List of nodes to learn.
+ */
+ private List<TreeNode> defaultNodesToLearnSelectionStrgy(Queue<TreeNode> queue) {
+ List<TreeNode> res = new ArrayList<>(queue);
+ queue.clear();
+ return res;
+ }
+
+ /**
+ * Check current note for the need for splitting.
+ *
+ * @param parentNode Parent node.
+ * @param split Best node split.
+ * @return true if split is needed.
+ */
+ boolean needSplit(TreeNode parentNode, Optional<NodeSplit> split) {
+ return split.isPresent() && parentNode.getImpurity() - split.get().getImpurity() > minImpurityDelta &&
+ parentNode.getDepth() < (maxDepth + 1);
+ }
+
+ /**
+ * Returns composition of built trees.
+ *
+ * @param models Models.
+ * @return composition of built trees.
+ */
+ protected abstract ModelsComposition buildComposition(List<TreeRoot> models);
+
}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/FeaturesCountSelectionStrategies.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/FeaturesCountSelectionStrategies.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/FeaturesCountSelectionStrategies.java
new file mode 100644
index 0000000..a246277
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/FeaturesCountSelectionStrategies.java
@@ -0,0 +1,47 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data;
+
+import java.util.List;
+import org.apache.ignite.ml.dataset.feature.FeatureMeta;
+import org.apache.ignite.ml.math.functions.IgniteFunction;
+
+/**
+ * Class contains a default implementations of some features count selection strategies for random forest.
+ */
+public class FeaturesCountSelectionStrategies {
+ /** */
+ public static IgniteFunction<List<FeatureMeta>, Integer> SQRT = (List<FeatureMeta> meta) -> {
+ return (int)Math.sqrt(meta.size());
+ };
+
+ /** */
+ public static IgniteFunction<List<FeatureMeta>, Integer> ALL = (List<FeatureMeta> meta) -> {
+ return meta.size();
+ };
+
+ /** */
+ public static IgniteFunction<List<FeatureMeta>, Integer> LOG2 = (List<FeatureMeta> meta) -> {
+ return (int)(Math.log(meta.size()) / Math.log(2));
+ };
+
+ /** */
+ public static IgniteFunction<List<FeatureMeta>, Integer> ONE_THIRD = (List<FeatureMeta> meta) -> {
+ return (int)(meta.size() / 3);
+ };
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/NodeId.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/NodeId.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/NodeId.java
new file mode 100644
index 0000000..2f40af3
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/NodeId.java
@@ -0,0 +1,55 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data;
+
+import org.apache.ignite.lang.IgniteBiTuple;
+
+/**
+ * Class represents Node id in Random Forest consisting of tree id and node id in tree in according to
+ * breadth-first search in tree.
+ */
+public class NodeId extends IgniteBiTuple<Integer, Long> {
+ /** Serial version uid. */
+ private static final long serialVersionUID = 4400852013136423333L;
+
+ /**
+ * Create an instance of NodeId.
+ *
+ * @param treeId Tree id.
+ * @param nodeId Node id.
+ */
+ public NodeId(Integer treeId, Long nodeId) {
+ super(treeId, nodeId);
+ }
+
+ /**
+ *
+ * @return Tree id.
+ */
+ public int treeId() {
+ return get1();
+ }
+
+ /**
+ *
+ * @return Node id.
+ */
+ public long nodeId() {
+ return get2();
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/NodeSplit.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/NodeSplit.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/NodeSplit.java
new file mode 100644
index 0000000..52d0b74
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/NodeSplit.java
@@ -0,0 +1,79 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data;
+
+import java.util.List;
+
+/**
+ * Class represents a split point for decision tree.
+ */
+public class NodeSplit {
+ /** Feature id in feature vector. */
+ private final int featureId;
+
+ /** Feature split value. */
+ private final double value;
+
+ /** Impurity at this split point. */
+ private final double impurity;
+
+ /**
+ * Creates an instance of NodeSplit.
+ *
+ * @param featureId Feature id.
+ * @param value Feature split value.
+ * @param impurity Impurity value.
+ */
+ public NodeSplit(int featureId, double value, double impurity) {
+ this.featureId = featureId;
+ this.value = value;
+ this.impurity = impurity;
+ }
+
+ /**
+ * Split node from parameter onto two children nodes.
+ *
+ * @param node Node.
+ * @return list of children.
+ */
+ public List<TreeNode> split(TreeNode node) {
+ List<TreeNode> children = node.toConditional(featureId, value);
+ node.setImpurity(impurity);
+ return children;
+ }
+
+ /**
+ * Convert node to leaf.
+ *
+ * @param node Node.
+ */
+ public void createLeaf(TreeNode node) {
+ node.setImpurity(impurity);
+ node.toLeaf(0.0); //values will be set in last stage if training
+ }
+
+ /** */
+ public double getImpurity() {
+ return impurity;
+ }
+
+ /** */
+ public double getValue() {
+ return value;
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/TreeNode.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/TreeNode.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/TreeNode.java
new file mode 100644
index 0000000..eb06143
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/TreeNode.java
@@ -0,0 +1,200 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data;
+
+import java.io.Serializable;
+import java.util.Arrays;
+import java.util.List;
+import org.apache.ignite.ml.Model;
+import org.apache.ignite.ml.math.primitives.vector.Vector;
+
+/**
+ * Decision tree node class.
+ */
+public class TreeNode implements Model<Vector, Double>, Serializable {
+ /** Serial version uid. */
+ private static final long serialVersionUID = -8546263332508653661L;
+
+ /**
+ * Type of node.
+ */
+ public enum Type {
+ /** Unknown. */
+ UNKNOWN,
+
+ /** Leaf node. */
+ LEAF,
+
+ /** Conditional node. */
+ CONDITIONAL
+ }
+
+ /** Id. */
+ private final NodeId id;
+
+ /** Feature id. */
+ private int featureId;
+
+ /** Value. */
+ private double value;
+
+ /** Type. */
+ private Type type;
+
+ /** Impurity. */
+ private double impurity;
+
+ /** Depth. */
+ private int depth;
+
+ /** Left branch. */
+ private TreeNode left;
+
+ /** Right branch. */
+ private TreeNode right;
+
+ /**
+ * Create an instance of TreeNode.
+ *
+ * @param id Id in according to breadth-first search ordering.
+ * @param treeId Tree id.
+ */
+ public TreeNode(long id, int treeId) {
+ this.id = new NodeId(treeId, id);
+ this.value = -1;
+ this.type = Type.UNKNOWN;
+ this.impurity = Double.POSITIVE_INFINITY;
+ this.depth = 1;
+ }
+
+ /** {@inheritDoc} */
+ public Double apply(Vector features) {
+ assert type != Type.UNKNOWN;
+
+ if (type == Type.LEAF)
+ return value;
+ else {
+ if (features.get(featureId) <= value)
+ return left.apply(features);
+ else
+ return right.apply(features);
+ }
+ }
+
+ /**
+ * Returns leaf node for feature vector in according to decision tree.
+ *
+ * @param features Features.
+ * @return Node.
+ */
+ public NodeId predictNextNodeKey(Vector features) {
+ switch (type) {
+ case UNKNOWN:
+ return id;
+ case LEAF:
+ return id;
+ default:
+ if (features.get(featureId) <= value)
+ return left.predictNextNodeKey(features);
+ else
+ return right.predictNextNodeKey(features);
+ }
+ }
+
+ /**
+ * Convert node to conditional node.
+ *
+ * @param featureId Feature id.
+ * @param value Value.
+ */
+ public List<TreeNode> toConditional(int featureId, double value) {
+ assert type == Type.UNKNOWN;
+
+ toLeaf(value);
+ left = new TreeNode(2 * id.nodeId(), id.treeId());
+ right = new TreeNode(2 * id.nodeId() + 1, id.treeId());
+ this.type = Type.CONDITIONAL;
+ this.featureId = featureId;
+
+ left.depth = right.depth = depth + 1;
+ return Arrays.asList(left, right);
+ }
+
+ /**
+ * Convert node to leaf.
+ *
+ * @param value Value.
+ */
+ public void toLeaf(double value) {
+ assert type == Type.UNKNOWN;
+
+ this.value = value;
+ this.type = Type.LEAF;
+
+ this.left = null;
+ this.right = null;
+ }
+
+ /** */
+ public NodeId getId() {
+ return id;
+ }
+
+ /** */
+ public void setValue(double value) {
+ this.value = value;
+ }
+
+ /** */
+ public Type getType() {
+ return type;
+ }
+
+ /** */
+ public void setImpurity(double impurity) {
+ this.impurity = impurity;
+ }
+
+ /**
+ * @return impurity in current node.
+ */
+ public double getImpurity() {
+ return impurity;
+ }
+
+ /**
+ * @return depth of current node.
+ */
+ public int getDepth() {
+ return depth;
+ }
+
+ /**
+ * @return right subtree.
+ */
+ public TreeNode getLeft() {
+ return left;
+ }
+
+ /**
+ * @return left subtree.
+ */
+ public TreeNode getRight() {
+ return right;
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/TreeRoot.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/TreeRoot.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/TreeRoot.java
new file mode 100644
index 0000000..e47868d
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/TreeRoot.java
@@ -0,0 +1,86 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Set;
+import org.apache.ignite.ml.Model;
+import org.apache.ignite.ml.math.primitives.vector.Vector;
+
+/**
+ * Tree root class.
+ */
+public class TreeRoot implements Model<Vector, Double> {
+ /** Serial version uid. */
+ private static final long serialVersionUID = 531797299171329057L;
+
+ /** Root node. */
+ private TreeNode node;
+
+ /** Used features. */
+ private Set<Integer> usedFeatures;
+
+ /**
+ * Create an instance of TreeRoot.
+ *
+ * @param root Root.
+ * @param usedFeatures Used features.
+ */
+ public TreeRoot(TreeNode root, Set<Integer> usedFeatures) {
+ this.node = root;
+ this.usedFeatures = usedFeatures;
+ }
+
+ /** {@inheritDoc} */
+ @Override public Double apply(Vector vector) {
+ return node.apply(vector);
+ }
+
+ /** */
+ public Set<Integer> getUsedFeatures() {
+ return usedFeatures;
+ }
+
+ /** */
+ public TreeNode getRootNode() {
+ return node;
+ }
+
+ /**
+ * @return all leafs in tree.
+ */
+ public List<TreeNode> getLeafs() {
+ List<TreeNode> res = new ArrayList<>();
+ getLeafs(node, res);
+ return res;
+ }
+
+ /**
+ * @param root Root.
+ * @param res Result list.
+ */
+ private void getLeafs(TreeNode root, List<TreeNode> res) {
+ if (root.getType() == TreeNode.Type.LEAF)
+ res.add(root);
+ else {
+ getLeafs(root.getLeft(), res);
+ getLeafs(root.getRight(), res);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/GiniHistogram.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/GiniHistogram.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/GiniHistogram.java
new file mode 100644
index 0000000..80a07a7
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/GiniHistogram.java
@@ -0,0 +1,225 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.impurity;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.TreeSet;
+import java.util.stream.Collectors;
+import org.apache.ignite.ml.dataset.feature.BucketMeta;
+import org.apache.ignite.ml.dataset.feature.ObjectHistogram;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedVector;
+import org.apache.ignite.ml.tree.randomforest.data.NodeSplit;
+import sun.reflect.generics.reflectiveObjects.NotImplementedException;
+
+/**
+ * Class contains implementation of splitting point finding algorithm based on Gini metric (see
+ * https://en.wikipedia.org/wiki/Gini_coefficient) and represents a set of histograms in according to this metric.
+ */
+public class GiniHistogram extends ImpurityHistogram implements ImpurityComputer<BootstrappedVector, GiniHistogram> {
+ /** Serial version uid. */
+ private static final long serialVersionUID = 5780670356098827667L;
+
+ /** Bucket meta. */
+ private final BucketMeta bucketMeta;
+
+ /** Sample id. */
+ private final int sampleId;
+
+ /** Hists of counters for each labels. */
+ private final ArrayList<ObjectHistogram<BootstrappedVector>> hists;
+
+ /** Label mapping to internal representation. */
+ private final Map<Double, Integer> lblMapping;
+
+ /** Bucket ids. */
+ private final Set<Integer> bucketIds;
+
+ /**
+ * Creates an instance of GiniHistogram.
+ *
+ * @param sampleId Sample id.
+ * @param lblMapping Label mapping.
+ * @param bucketMeta Bucket meta.
+ */
+ public GiniHistogram(int sampleId, Map<Double, Integer> lblMapping, BucketMeta bucketMeta) {
+ super(bucketMeta.getFeatureMeta().getFeatureId());
+ this.hists = new ArrayList<>(lblMapping.size());
+ this.sampleId = sampleId;
+ this.bucketMeta = bucketMeta;
+ this.lblMapping = lblMapping;
+
+ for (int i = 0; i < lblMapping.size(); i++)
+ hists.add(new ObjectHistogram<>(this::bucketMap, this::counterMap));
+
+ this.bucketIds = new TreeSet<>();
+ }
+
+ /** {@inheritDoc} */
+ @Override public void addElement(BootstrappedVector vector) {
+ Integer lblId = lblMapping.get(vector.label());
+ hists.get(lblId).addElement(vector);
+ }
+
+ /** {@inheritDoc} */
+ @Override public Optional<Double> getValue(Integer bucketId) {
+ throw new NotImplementedException();
+ }
+
+ /** {@inheritDoc} */
+ @Override public GiniHistogram plus(GiniHistogram other) {
+ GiniHistogram res = new GiniHistogram(sampleId, lblMapping, bucketMeta);
+ res.bucketIds.addAll(this.bucketIds);
+ res.bucketIds.addAll(other.bucketIds);
+ for (int i = 0; i < hists.size(); i++)
+ res.hists.set(i, this.hists.get(i).plus(other.hists.get(i)));
+ return res;
+ }
+
+ /** {@inheritDoc} */
+ @Override public Optional<NodeSplit> findBestSplit() {
+ if (bucketIds.size() < 2)
+ return Optional.empty();
+
+ double bestImpurity = Double.POSITIVE_INFINITY;
+ double bestSplitVal = Double.NEGATIVE_INFINITY;
+ int bestBucketId = -1;
+
+ List<TreeMap<Integer, Double>> countersDistribPerCls = hists.stream()
+ .map(ObjectHistogram::computeDistributionFunction)
+ .collect(Collectors.toList());
+
+ double[] totalSampleCntPerLb = countersDistribPerCls.stream()
+ .mapToDouble(x -> x.isEmpty() ? 0.0 : x.lastEntry().getValue())
+ .toArray();
+
+ Map<Integer, Double> lastLeftValues = new HashMap<>();
+ for (int i = 0; i < lblMapping.size(); i++)
+ lastLeftValues.put(i, 0.0);
+
+ for (Integer bucketId : bucketIds) {
+ double totalToleftCnt = 0;
+ double totalToRightCnt = 0;
+
+ double leftImpurity = 0;
+ double rightImpurity = 0;
+
+ //Compute number of samples left and right in according to split by bucketId
+ for (int lbId = 0; lbId < lblMapping.size(); lbId++) {
+ Double left = countersDistribPerCls.get(lbId).get(bucketId);
+ if (left == null)
+ left = lastLeftValues.get(lbId);
+
+ totalToleftCnt += left;
+ totalToRightCnt += totalSampleCntPerLb[lbId] - left;
+
+ lastLeftValues.put(lbId, left);
+ }
+
+ for (int lbId = 0; lbId < lblMapping.size(); lbId++) {
+ //count of samples with label [corresponding lblId] to the left of bucket
+ Double toLeftCnt = countersDistribPerCls.get(lbId).getOrDefault(bucketId, lastLeftValues.get(lbId));
+
+ if (toLeftCnt > 0)
+ leftImpurity += Math.pow(toLeftCnt, 2) / totalToleftCnt;
+
+ //number of samples to the right of bucket = total samples count - toLeftCnt
+ double toRightCnt = totalSampleCntPerLb[lbId] - toLeftCnt;
+ if (toRightCnt > 0)
+ rightImpurity += (Math.pow(toRightCnt, 2)) / totalToRightCnt;
+ }
+
+ double impurityInBucket = -(leftImpurity + rightImpurity);
+ if (impurityInBucket <= bestImpurity) {
+ bestImpurity = impurityInBucket;
+ bestSplitVal = bucketMeta.bucketIdToValue(bucketId);
+ bestBucketId = bucketId;
+ }
+ }
+
+ return checkAndReturnSplitValue(bestBucketId, bestSplitVal, bestImpurity);
+ }
+
+ /** {@inheritDoc} */
+ @Override public Set<Integer> buckets() {
+ return bucketIds;
+ }
+
+ /**
+ * Returns counters histogram for class-label.
+ *
+ * @param lbl Label.
+ * @return counters histogram for class-label.
+ */
+ ObjectHistogram<BootstrappedVector> getHistForLabel(Double lbl) {
+ return hists.get(lblMapping.get(lbl));
+ }
+
+ /**
+ * Maps vector to counter value.
+ *
+ * @param vec Vector.
+ * @return Counter value.
+ */
+ private Double counterMap(BootstrappedVector vec) {
+ return (double)vec.counters()[sampleId];
+ }
+
+ /**
+ * Maps vector to bucket id.
+ *
+ * @param vec Vector.
+ * @return Bucket id.
+ */
+ private Integer bucketMap(BootstrappedVector vec) {
+ int bucketId = bucketMeta.getBucketId(vec.features().get(featureId));
+ this.bucketIds.add(bucketId);
+ return bucketId;
+ }
+
+ /** {@inheritDoc} */
+ @Override public boolean isEqualTo(GiniHistogram other) {
+ HashSet<Integer> unionBuckets = new HashSet<>(buckets());
+ unionBuckets.addAll(other.bucketIds);
+ if (unionBuckets.size() != bucketIds.size())
+ return false;
+
+ HashSet<Double> unionMappings = new HashSet<>(lblMapping.keySet());
+ unionMappings.addAll(other.lblMapping.keySet());
+ if (unionMappings.size() != lblMapping.size())
+ return false;
+
+ for (Double lbl : unionMappings) {
+ if (lblMapping.get(lbl) != other.lblMapping.get(lbl))
+ return false;
+
+ ObjectHistogram<BootstrappedVector> thisHist = getHistForLabel(lbl);
+ ObjectHistogram<BootstrappedVector> otherHist = other.getHistForLabel(lbl);
+ if (!thisHist.isEqualTo(otherHist))
+ return false;
+ }
+
+ return true;
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/GiniHistogramsComputer.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/GiniHistogramsComputer.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/GiniHistogramsComputer.java
new file mode 100644
index 0000000..8c9dc95
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/GiniHistogramsComputer.java
@@ -0,0 +1,46 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.impurity;
+
+import java.util.Map;
+import org.apache.ignite.ml.dataset.feature.BucketMeta;
+
+/**
+ * Implementation of {@link ImpurityHistogramsComputer} for classification task.
+ */
+public class GiniHistogramsComputer extends ImpurityHistogramsComputer<GiniHistogram> {
+ /** Serial version uid. */
+ private static final long serialVersionUID = 3672921182944932748L;
+
+ /** Label mapping. */
+ private final Map<Double, Integer> lblMapping;
+
+ /**
+ * Creates an instance of GiniHistogramsComputer.
+ *
+ * @param lblMapping Lbl mapping.
+ */
+ public GiniHistogramsComputer(Map<Double, Integer> lblMapping) {
+ this.lblMapping = lblMapping;
+ }
+
+ /** {@inheritDoc} */
+ @Override protected GiniHistogram createImpurityComputerForFeature(int sampleId, BucketMeta meta) {
+ return new GiniHistogram(sampleId, lblMapping, meta);
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityComputer.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityComputer.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityComputer.java
new file mode 100644
index 0000000..0684415
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityComputer.java
@@ -0,0 +1,38 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.impurity;
+
+import java.util.Optional;
+import org.apache.ignite.ml.dataset.feature.Histogram;
+import org.apache.ignite.ml.tree.randomforest.data.NodeSplit;
+
+/**
+ * Interface represents an object that can compute best splitting point using features histograms.
+ *
+ * @param <T> Base object type for histogram.
+ * @param <H> Type of histogram that can be used in math operations with this object.
+ */
+public interface ImpurityComputer<T, H extends Histogram<T, H>> extends Histogram<T, H> {
+ /**
+ * Returns best split point computed on histogram if it exists.
+ * Split point may be absent when there is no data in histograms or split point lay in last bucket in histogram.
+ *
+ * @return Splitting point for decision tree.
+ */
+ public Optional<NodeSplit> findBestSplit();
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityHistogram.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityHistogram.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityHistogram.java
new file mode 100644
index 0000000..296d862
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityHistogram.java
@@ -0,0 +1,74 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.impurity;
+
+import java.util.Optional;
+import java.util.Set;
+import java.util.TreeSet;
+import org.apache.ignite.ml.tree.randomforest.data.NodeSplit;
+
+/**
+ * Helper class for ImpurityHistograms.
+ */
+public abstract class ImpurityHistogram {
+ /** Bucket ids. */
+ protected final Set<Integer> bucketIds = new TreeSet<>();
+
+ /** Feature id. */
+ protected final int featureId;
+
+ /**
+ * Creates an instance of ImpurityHistogram.
+ *
+ * @param featureId Feature id.
+ */
+ public ImpurityHistogram(int featureId) {
+ this.featureId = featureId;
+ }
+
+ /**
+ * Checks split value validity and return Optional-wrap of it.
+ * In other case returns Optional.empty
+ *
+ * @param bestBucketId Best bucket id.
+ * @param bestSplitVal Best split value.
+ * @param bestImpurity Best impurity.
+ * @return best split value.
+ */
+ protected Optional<NodeSplit> checkAndReturnSplitValue(int bestBucketId, double bestSplitVal, double bestImpurity) {
+ if (isLastBucket(bestBucketId))
+ return Optional.empty();
+ else
+ return Optional.of(new NodeSplit(featureId, bestSplitVal, bestImpurity));
+ }
+
+ /**
+ * @param bestBucketId Best bucket id.
+ * @return true if best found bucket is last within all bucketIds.
+ */
+ private boolean isLastBucket(int bestBucketId) {
+ int minBucketId = Integer.MAX_VALUE;
+ int maxBucketId = Integer.MIN_VALUE;
+ for (Integer bucketId : bucketIds) {
+ minBucketId = Math.min(minBucketId, bucketId);
+ maxBucketId = Math.max(maxBucketId, bucketId);
+ }
+
+ return bestBucketId == maxBucketId;
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityHistogramsComputer.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityHistogramsComputer.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityHistogramsComputer.java
new file mode 100644
index 0000000..d1ed87f
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/ImpurityHistogramsComputer.java
@@ -0,0 +1,211 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.impurity;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Optional;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+import org.apache.ignite.ml.dataset.Dataset;
+import org.apache.ignite.ml.dataset.feature.BucketMeta;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedDatasetPartition;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedVector;
+import org.apache.ignite.ml.dataset.primitive.context.EmptyContext;
+import org.apache.ignite.ml.tree.randomforest.data.NodeId;
+import org.apache.ignite.ml.tree.randomforest.data.NodeSplit;
+import org.apache.ignite.ml.tree.randomforest.data.TreeNode;
+import org.apache.ignite.ml.tree.randomforest.data.TreeRoot;
+
+/**
+ * Class containing logic of aggregation impurity statistics within learning dataset.
+ *
+ * @param <S> Type of basic impurity computer for feature.
+ */
+public abstract class ImpurityHistogramsComputer<S extends ImpurityComputer<BootstrappedVector, S>> implements Serializable {
+ /** Serial version uid. */
+ private static final long serialVersionUID = -4984067145908187508L;
+
+ /**
+ * Computes histograms for each features.
+ *
+ * @param roots Random forest roots.
+ * @param histMeta Histograms meta.
+ * @param nodesToLearn Nodes to learn.
+ * @param dataset Dataset.
+ */
+ public Map<NodeId, NodeImpurityHistograms<S>> aggregateImpurityStatistics(ArrayList<TreeRoot> roots,
+ Map<Integer, BucketMeta> histMeta, Map<NodeId, TreeNode> nodesToLearn,
+ Dataset<EmptyContext, BootstrappedDatasetPartition> dataset) {
+
+ return dataset.compute(
+ x -> aggregateImpurityStatisticsOnPartition(x, roots, histMeta, nodesToLearn),
+ this::reduceImpurityStatistics
+ );
+ }
+
+ /**
+ * Aggregates statistics for impurity computing for each corner nodes for each trees in random forest. This
+ * algorithm predict corner node in decision tree for learning vector and stocks it to correspond histogram.
+ *
+ * @param dataset Dataset.
+ * @param roots Trees.
+ * @param histMeta Histogram buckets meta.
+ * @param part Partition.
+ * @return Leaf statistics for impurity computing.
+ */
+ private Map<NodeId, NodeImpurityHistograms<S>> aggregateImpurityStatisticsOnPartition(
+ BootstrappedDatasetPartition dataset, ArrayList<TreeRoot> roots,
+ Map<Integer, BucketMeta> histMeta,
+ Map<NodeId, TreeNode> part) {
+
+ Map<NodeId, NodeImpurityHistograms<S>> res = part.keySet().stream()
+ .collect(Collectors.toMap(n -> n, NodeImpurityHistograms::new));
+
+ dataset.forEach(vector -> {
+ for (int sampleId = 0; sampleId < vector.counters().length; sampleId++) {
+ if (vector.counters()[sampleId] == 0)
+ continue;
+
+ TreeRoot root = roots.get(sampleId);
+ NodeId key = root.getRootNode().predictNextNodeKey(vector.features());
+ if (!part.containsKey(key)) //if we didn't take all nodes from learning queue
+ continue;
+
+ NodeImpurityHistograms<S> statistics = res.get(key);
+ for (Integer featureId : root.getUsedFeatures()) {
+ BucketMeta meta = histMeta.get(featureId);
+ if (!statistics.perFeatureStatistics.containsKey(featureId))
+ statistics.perFeatureStatistics.put(featureId, createImpurityComputerForFeature(sampleId, meta));
+ S impurityComputer = statistics.perFeatureStatistics.get(featureId);
+ impurityComputer.addElement(vector);
+ }
+ }
+ });
+ return res;
+ }
+
+ /**
+ * Merge leaf statistics from several data partitions.
+ *
+ * @param left Left.
+ * @param right Right.
+ * @return merged leaf impurity statistics.
+ */
+ private Map<NodeId, NodeImpurityHistograms<S>> reduceImpurityStatistics(Map<NodeId, NodeImpurityHistograms<S>> left,
+ Map<NodeId, NodeImpurityHistograms<S>> right) {
+
+ if (left == null)
+ return right;
+ if (right == null)
+ return left;
+
+ Map<NodeId, NodeImpurityHistograms<S>> res = new HashMap<>(left);
+ for (NodeId key : right.keySet()) {
+ NodeImpurityHistograms<S> rightVal = right.get(key);
+ if (!res.containsKey(key))
+ res.put(key, rightVal);
+ else
+ res.put(key, left.get(key).plus(rightVal));
+ }
+
+ return res;
+ }
+
+ /**
+ * Creates impurity computer in according to specific algorithm based on random forest (for example {@link
+ * GiniHistogram} for classification).
+ *
+ * @param sampleId Sample id.
+ * @param meta Bucket Meta.
+ * @return impurity computer
+ */
+ protected abstract S createImpurityComputerForFeature(int sampleId, BucketMeta meta);
+
+ /**
+ * Class represents per feature statistics for impurity computing.
+ */
+ public static class NodeImpurityHistograms<S extends ImpurityComputer<BootstrappedVector, S>> implements Serializable {
+ /** Serial version uid. */
+ private static final long serialVersionUID = 2700045747590421768L;
+
+ /** Node id. */
+ private final NodeId nodeId;
+
+ /** Per feature statistics. */
+ private final Map<Integer, S> perFeatureStatistics = new HashMap<>();
+
+ /**
+ * Create an instance of NodeImpurityHistograms.
+ *
+ * @param nodeId Node id.
+ */
+ public NodeImpurityHistograms(NodeId nodeId) {
+ this.nodeId = nodeId;
+ }
+
+ /**
+ * Store features statistics from other instance.
+ *
+ * @param other Other instance.
+ */
+ public NodeImpurityHistograms<S> plus(NodeImpurityHistograms<S> other) {
+ assert nodeId == other.nodeId;
+ NodeImpurityHistograms<S> res = new NodeImpurityHistograms<>(nodeId);
+ addTo(this.perFeatureStatistics, res.perFeatureStatistics);
+ addTo(other.perFeatureStatistics, res.perFeatureStatistics);
+ return res;
+ }
+
+ /**
+ * Adds all statistics to target.
+ *
+ * @param from From.
+ * @param to To.
+ */
+ private void addTo(Map<Integer, S> from, Map<Integer, S> to) {
+ from.forEach((key, hist) -> {
+ if(!to.containsKey(key)) {
+ to.put(key, hist);
+ } else {
+ S sumOfHists = to.get(key).plus(hist);
+ to.put(key, sumOfHists);
+ }
+ });
+ }
+
+ /** */
+ public NodeId getNodeId() {
+ return nodeId;
+ }
+
+ /**
+ * Find best split point, based on feature statistics.
+ *
+ * @return Best split point if it exists.
+ */
+ public Optional<NodeSplit> findBestSplit() {
+ return perFeatureStatistics.values().stream()
+ .flatMap(x -> x.findBestSplit().map(Stream::of).orElse(Stream.empty()))
+ .min(Comparator.comparingDouble(NodeSplit::getImpurity));
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/MSEHistogram.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/MSEHistogram.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/MSEHistogram.java
new file mode 100644
index 0000000..e015e3f
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/MSEHistogram.java
@@ -0,0 +1,235 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.impurity;
+
+import java.util.HashSet;
+import java.util.Optional;
+import java.util.Set;
+import java.util.TreeMap;
+import org.apache.ignite.ml.dataset.feature.BucketMeta;
+import org.apache.ignite.ml.dataset.feature.ObjectHistogram;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedVector;
+import org.apache.ignite.ml.tree.randomforest.data.NodeSplit;
+import sun.reflect.generics.reflectiveObjects.NotImplementedException;
+
+/**
+ * Class contains implementation of splitting point finding algorithm based on MSE metric (see https://en.wikipedia.org/wiki/Mean_squared_error)
+ * and represents a set of histograms in according to this metric.
+ */
+public class MSEHistogram extends ImpurityHistogram implements ImpurityComputer<BootstrappedVector, MSEHistogram> {
+ /** Serial version uid. */
+ private static final long serialVersionUID = 9175485616887867623L;
+
+ /** Bucket meta. */
+ private final BucketMeta bucketMeta;
+
+ /** Sample id. */
+ private final int sampleId;
+
+ /** Counters. */
+ private ObjectHistogram<BootstrappedVector> counters;
+
+ /** Sums of label values. */
+ private ObjectHistogram<BootstrappedVector> sumOfLabels;
+
+ /** Sums of squared label values. */
+ private ObjectHistogram<BootstrappedVector> sumOfSquaredLabels;
+
+ /**
+ * Creates an instance of MSEHistogram.
+ *
+ * @param sampleId Sample id.
+ * @param bucketMeta Bucket meta.
+ */
+ public MSEHistogram(int sampleId, BucketMeta bucketMeta) {
+ super(bucketMeta.getFeatureMeta().getFeatureId());
+ this.bucketMeta = bucketMeta;
+ this.sampleId = sampleId;
+
+ counters = new ObjectHistogram<>(this::bucketMap, this::counterMap);
+ sumOfLabels = new ObjectHistogram<>(this::bucketMap, this::ysMap);
+ sumOfSquaredLabels = new ObjectHistogram<>(this::bucketMap, this::y2sMap);
+ }
+
+ /** {@inheritDoc} */
+ @Override public void addElement(BootstrappedVector vector) {
+ counters.addElement(vector);
+ sumOfLabels.addElement(vector);
+ sumOfSquaredLabels.addElement(vector);
+ }
+
+ /** {@inheritDoc} */
+ @Override public MSEHistogram plus(MSEHistogram other) {
+ MSEHistogram res = new MSEHistogram(sampleId, bucketMeta);
+ res.counters = this.counters.plus(other.counters);
+ res.sumOfLabels = this.sumOfLabels.plus(other.sumOfLabels);
+ res.sumOfSquaredLabels = this.sumOfSquaredLabels.plus(other.sumOfSquaredLabels);
+ res.bucketIds.addAll(this.bucketIds);
+ res.bucketIds.addAll(bucketIds);
+ return res;
+ }
+
+ /** {@inheritDoc} */
+ @Override public Set<Integer> buckets() {
+ return bucketIds;
+ }
+
+ /** {@inheritDoc} */
+ @Override public Optional<Double> getValue(Integer bucketId) {
+ throw new NotImplementedException();
+ }
+
+ /** {@inheritDoc} */
+ @Override public Optional<NodeSplit> findBestSplit() {
+ double bestImpurity = Double.POSITIVE_INFINITY;
+ double bestSplitVal = Double.NEGATIVE_INFINITY;
+ int bestBucketId = -1;
+
+ //counter corresponds to number of samples
+ //ys corresponds to sumOfLabels
+ //y2s corresponds to sumOfSquaredLabels
+ TreeMap<Integer, Double> cntrDistrib = counters.computeDistributionFunction();
+ TreeMap<Integer, Double> ysDistrib = sumOfLabels.computeDistributionFunction();
+ TreeMap<Integer, Double> y2sDistrib = sumOfSquaredLabels.computeDistributionFunction();
+
+ double cntrMax = cntrDistrib.lastEntry().getValue();
+ double ysMax = ysDistrib.lastEntry().getValue();
+ double y2sMax = y2sDistrib.lastEntry().getValue();
+
+ double lastLeftCntrVal = 0.0;
+ double lastLeftYVal = 0.0;
+ double lastLeftY2Val = 0.0;
+
+ for (Integer bucketId : bucketIds) {
+ //values for impurity computing to the left of bucket value
+ double leftCnt = cntrDistrib.getOrDefault(bucketId, lastLeftCntrVal);
+ double leftY = ysDistrib.getOrDefault(bucketId, lastLeftYVal);
+ double leftY2 = y2sDistrib.getOrDefault(bucketId, lastLeftY2Val);
+
+ //values for impurity computing to the right of bucket value
+ double rightCnt = cntrMax - leftCnt;
+ double rightY = ysMax - leftY;
+ double rightY2 = y2sMax - leftY2;
+
+ double impurity = 0.0;
+
+ if (leftCnt > 0)
+ impurity += impurity(leftCnt, leftY, leftY2);
+ if (rightCnt > 0)
+ impurity += impurity(rightCnt, rightY, rightY2);
+
+ if (impurity < bestImpurity) {
+ bestImpurity = impurity;
+ bestSplitVal = bucketMeta.bucketIdToValue(bucketId);
+ bestBucketId = bucketId;
+ }
+ }
+
+ return checkAndReturnSplitValue(bestBucketId, bestSplitVal, bestImpurity);
+ }
+
+ /**
+ * Computes impurity function value.
+ *
+ * @param cnt Counter value.
+ * @param ys plus of Ys.
+ * @param y2s plus of Y^2 s.
+ * @return impurity value.
+ */
+ private double impurity(double cnt, double ys, double y2s) {
+ return y2s - 2.0 * ys / cnt * ys + Math.pow(ys / cnt, 2) * cnt;
+ }
+
+ /**
+ * Maps vector to bucket id.
+ *
+ * @param vec Vector.
+ * @return Bucket id.
+ */
+ private Integer bucketMap(BootstrappedVector vec) {
+ int bucketId = bucketMeta.getBucketId(vec.features().get(featureId));
+ this.bucketIds.add(bucketId);
+ return bucketId;
+ }
+
+ /**
+ * Maps vector to counter value.
+ *
+ * @param vec Vector.
+ * @return Counter value.
+ */
+ private Double counterMap(BootstrappedVector vec) {
+ return (double)vec.counters()[sampleId];
+ }
+
+ /**
+ * Maps vector to Y-value.
+ *
+ * @param vec Vector.
+ * @return Y value.
+ */
+ private Double ysMap(BootstrappedVector vec) {
+ return vec.counters()[sampleId] * vec.label();
+ }
+
+ /**
+ * Maps vector to Y^2 value.
+ *
+ * @param vec Vec.
+ * @return Y^2 value.
+ */
+ private Double y2sMap(BootstrappedVector vec) {
+ return vec.counters()[sampleId] * Math.pow(vec.label(), 2);
+ }
+
+ /**
+ * @return Counters histogram.
+ */
+ ObjectHistogram<BootstrappedVector> getCounters() {
+ return counters;
+ }
+
+ /**
+ * @return Ys histogram.
+ */
+ ObjectHistogram<BootstrappedVector> getSumOfLabels() {
+ return sumOfLabels;
+ }
+
+ /**
+ * @return Y^2s histogram.
+ */
+ ObjectHistogram<BootstrappedVector> getSumOfSquaredLabels() {
+ return sumOfSquaredLabels;
+ }
+
+ /** {@inheritDoc} */
+ @Override public boolean isEqualTo(MSEHistogram other) {
+ HashSet<Integer> unionBuckets = new HashSet<>(buckets());
+ unionBuckets.addAll(other.bucketIds);
+ if(unionBuckets.size() != bucketIds.size())
+ return false;
+
+ if(!this.counters.isEqualTo(other.counters))
+ return false;
+ if(!this.sumOfLabels.isEqualTo(other.sumOfLabels))
+ return false;
+
+ return this.sumOfSquaredLabels.isEqualTo(other.sumOfSquaredLabels);
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/MSEHistogramComputer.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/MSEHistogramComputer.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/MSEHistogramComputer.java
new file mode 100644
index 0000000..412cfc9
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/MSEHistogramComputer.java
@@ -0,0 +1,33 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.impurity;
+
+import org.apache.ignite.ml.dataset.feature.BucketMeta;
+
+/**
+ * Histogram computer realization for MSE impurity metric.
+ */
+public class MSEHistogramComputer extends ImpurityHistogramsComputer<MSEHistogram> {
+ /** Serial version uid. */
+ private static final long serialVersionUID = -1544823437437088334L;
+
+ /** {@inheritDoc} */
+ @Override protected MSEHistogram createImpurityComputerForFeature(int sampleId, BucketMeta meta) {
+ return new MSEHistogram(sampleId, meta);
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/package-info.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/package-info.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/package-info.java
new file mode 100644
index 0000000..62e2259
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/impurity/package-info.java
@@ -0,0 +1,22 @@
+/*
+ * 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 description. -->
+ * Contains implementation of impurity computers based on histograms.
+ */
+package org.apache.ignite.ml.tree.randomforest.data.impurity;
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/package-info.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/package-info.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/package-info.java
new file mode 100644
index 0000000..0311845
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/package-info.java
@@ -0,0 +1,22 @@
+/*
+ * 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 description. -->
+ * Package contains helper data structures for random forest implementation.
+ */
+package org.apache.ignite.ml.tree.randomforest.data;
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/ClassifierLeafValuesComputer.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/ClassifierLeafValuesComputer.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/ClassifierLeafValuesComputer.java
new file mode 100644
index 0000000..64297ff
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/ClassifierLeafValuesComputer.java
@@ -0,0 +1,82 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.statistics;
+
+import java.util.Comparator;
+import java.util.Map;
+import org.apache.ignite.ml.dataset.feature.ObjectHistogram;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedVector;
+
+/**
+ * Implementation of {@link LeafValuesComputer} for classification task.
+ */
+public class ClassifierLeafValuesComputer extends LeafValuesComputer<ObjectHistogram<BootstrappedVector>> {
+ /** Serial version uid. */
+ private static final long serialVersionUID = 420416095877577599L;
+
+ /** Label mapping. */
+ private final Map<Double, Integer> lblMapping;
+
+ /**
+ * Creates an instance of ClassifierLeafValuesComputer.
+ *
+ * @param lblMapping Label mapping.
+ */
+ public ClassifierLeafValuesComputer(Map<Double, Integer> lblMapping) {
+ this.lblMapping = lblMapping;
+ }
+
+ /** {@inheritDoc} */
+ @Override protected void addElementToLeafStatistic(ObjectHistogram<BootstrappedVector> leafStatAggr, BootstrappedVector vec, int sampleId) {
+ leafStatAggr.addElement(vec);
+ }
+
+ /** {@inheritDoc} */
+ @Override protected ObjectHistogram<BootstrappedVector> mergeLeafStats(ObjectHistogram<BootstrappedVector> leftStats,
+ ObjectHistogram<BootstrappedVector> rightStats) {
+
+ return leftStats.plus(rightStats);
+ }
+
+ /** {@inheritDoc} */
+ @Override protected ObjectHistogram<BootstrappedVector> createLeafStatsAggregator(int sampleId) {
+ return new ObjectHistogram<>(
+ x -> lblMapping.get(x.label()),
+ x -> (double)x.counters()[sampleId]
+ );
+ }
+
+ /**
+ * Returns the most frequent value in according to statistic.
+ *
+ * @param stat Leaf statistics.
+ */
+ @Override protected double computeLeafValue(ObjectHistogram<BootstrappedVector> stat) {
+ Integer bucketId = stat.buckets().stream()
+ .max(Comparator.comparing(b -> stat.getValue(b).orElse(0.0)))
+ .orElse(-1);
+
+ if(bucketId == -1)
+ return Double.NaN;
+
+ return lblMapping.entrySet().stream()
+ .filter(x -> x.getValue().equals(bucketId))
+ .findFirst()
+ .get().getKey();
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/LeafValuesComputer.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/LeafValuesComputer.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/LeafValuesComputer.java
new file mode 100644
index 0000000..056eece
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/LeafValuesComputer.java
@@ -0,0 +1,158 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.statistics;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+import org.apache.ignite.ml.dataset.Dataset;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedDatasetPartition;
+import org.apache.ignite.ml.dataset.impl.bootstrapping.BootstrappedVector;
+import org.apache.ignite.ml.dataset.primitive.context.EmptyContext;
+import org.apache.ignite.ml.tree.randomforest.data.NodeId;
+import org.apache.ignite.ml.tree.randomforest.data.TreeNode;
+import org.apache.ignite.ml.tree.randomforest.data.TreeRoot;
+
+/**
+ * Class containing logic of leaf values computing after building of all trees in random forest.
+ *
+ * @param <T> Type of leaf statistic.
+ */
+public abstract class LeafValuesComputer<T> implements Serializable {
+ /** Serial version uid. */
+ private static final long serialVersionUID = -429848953091775832L;
+
+ /**
+ * Takes a list of all built trees and in one map-reduceImpurityStatistics step collect statistics for evaluating
+ * leaf-values for each tree and sets values for leaves.
+ *
+ * @param roots Learned trees.
+ * @param dataset Dataset.
+ */
+ public void setValuesForLeaves(ArrayList<TreeRoot> roots,
+ Dataset<EmptyContext, BootstrappedDatasetPartition> dataset) {
+
+ Map<NodeId, TreeNode> leafs = roots.stream()
+ .flatMap(r -> r.getLeafs().stream())
+ .collect(Collectors.toMap(TreeNode::getId, Function.identity()));
+
+ Map<NodeId, T> stats = dataset.compute(
+ data -> computeLeafsStatisticsInPartition(roots, leafs, data),
+ this::mergeLeafStatistics
+ );
+
+ leafs.forEach((id, leaf) -> {
+ T stat = stats.get(id);
+ if(stat != null) {
+ double leafVal = computeLeafValue(stat);
+ leaf.setValue(leafVal);
+ }
+ });
+ }
+
+ /**
+ * Aggregates statistics on labels from learning dataset for each leaf nodes.
+ *
+ * @param roots Learned trees.
+ * @param leafs List of all leafs.
+ * @param data Data.
+ * @return statistics on labels for each leaf nodes.
+ */
+ private Map<NodeId, T> computeLeafsStatisticsInPartition(ArrayList<TreeRoot> roots,
+ Map<NodeId, TreeNode> leafs, BootstrappedDatasetPartition data) {
+
+ Map<NodeId, T> res = new HashMap<>();
+ for (int sampleId = 0; sampleId < roots.size(); sampleId++) {
+ final int sampleIdConst = sampleId;
+
+ data.forEach(vec -> {
+ NodeId leafId = roots.get(sampleIdConst).getRootNode().predictNextNodeKey(vec.features());
+ if (!leafs.containsKey(leafId))
+ throw new IllegalStateException();
+
+ if (!res.containsKey(leafId))
+ res.put(leafId, createLeafStatsAggregator(sampleIdConst));
+
+ addElementToLeafStatistic(res.get(leafId), vec, sampleIdConst);
+ });
+ }
+
+ return res;
+ }
+
+ /**
+ * Merges statistics on labels from several partitions.
+ *
+ * @param left first partition.
+ * @param right second partition.
+ * @return merged statistics.
+ */
+ private Map<NodeId, T> mergeLeafStatistics(Map<NodeId, T> left, Map<NodeId, T> right) {
+ if (left == null)
+ return right;
+ if (right == null)
+ return left;
+
+ Set<NodeId> keys = new HashSet<>(left.keySet());
+ keys.addAll(right.keySet());
+ for (NodeId key : keys) {
+ if (!left.containsKey(key))
+ left.put(key, right.get(key));
+ else if (right.containsKey(key))
+ left.put(key, mergeLeafStats(left.get(key), right.get(key)));
+ }
+
+ return left;
+ }
+
+ /**
+ * Save vector to leaf statistic.
+ *
+ * @param leafStatAggr Leaf statistics aggregator.
+ * @param vec Vector.
+ * @param sampleId Sample id.
+ */
+ protected abstract void addElementToLeafStatistic(T leafStatAggr, BootstrappedVector vec, int sampleId);
+
+ /**
+ * Merge statistics for same leafs.
+ *
+ * @param leftStats First leaf stat aggregator.
+ * @param rightStats Second leaf stat aggregator.
+ */
+ protected abstract T mergeLeafStats(T leftStats, T rightStats);
+
+ /**
+ * Creates an instance of leaf statistics aggregator in according to concrete algorithm based on RandomForest.
+ *
+ * @param sampleId Sample id.
+ */
+ protected abstract T createLeafStatsAggregator(int sampleId);
+
+ /**
+ * Compute value from leaf based on statistics on labels corresponds to leaf.
+ *
+ * @param stat Leaf statistics.
+ */
+ protected abstract double computeLeafValue(T stat);
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/MeanValueStatistic.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/MeanValueStatistic.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/MeanValueStatistic.java
new file mode 100644
index 0000000..c2c61d7
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/MeanValueStatistic.java
@@ -0,0 +1,72 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.statistics;
+
+import java.io.Serializable;
+
+/**
+ * Statistics for mean value computing container.
+ */
+public class MeanValueStatistic implements Serializable {
+ /** Serial version uid. */
+ private static final long serialVersionUID = -6265792209142062174L;
+
+ /** Sum of values. */
+ private double sumOfValues;
+
+ /** Count of values. */
+ private long cntOfValues;
+
+ /**
+ * Creates an instance of MeanValueStatistic.
+ *
+ * @param sumOfValues Sum of values.
+ * @param cntOfValues Count of values.
+ */
+ public MeanValueStatistic(double sumOfValues, long cntOfValues) {
+ this.sumOfValues = sumOfValues;
+ this.cntOfValues = cntOfValues;
+ }
+
+ /**
+ * @return mean value.
+ */
+ public double mean() {
+ return sumOfValues / cntOfValues;
+ }
+
+ /** */
+ public double getSumOfValues() {
+ return sumOfValues;
+ }
+
+ /** */
+ public void setSumOfValues(double sumOfValues) {
+ this.sumOfValues = sumOfValues;
+ }
+
+ /** */
+ public long getCntOfValues() {
+ return cntOfValues;
+ }
+
+ /** */
+ public void setCntOfValues(long cntOfValues) {
+ this.cntOfValues = cntOfValues;
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/78328fe4/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/NormalDistributionStatistics.java
----------------------------------------------------------------------
diff --git a/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/NormalDistributionStatistics.java b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/NormalDistributionStatistics.java
new file mode 100644
index 0000000..8341204
--- /dev/null
+++ b/modules/ml/src/main/java/org/apache/ignite/ml/tree/randomforest/data/statistics/NormalDistributionStatistics.java
@@ -0,0 +1,112 @@
+/*
+ * 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.ignite.ml.tree.randomforest.data.statistics;
+
+import java.io.Serializable;
+
+/**
+ * Aggregator of normal distribution statistics for continual features.
+ */
+public class NormalDistributionStatistics implements Serializable {
+ /** Serial version uid. */
+ private static final long serialVersionUID = -5422805289301484436L;
+
+ /** Min value. */
+ private final double min;
+
+ /** Max value. */
+ private final double max;
+
+ /** Sum of value squares. */
+ private final double sumOfSquares;
+
+ /** Sum of values. */
+ private final double sumOfValues;
+
+ /** Count of objects. */
+ private final long n;
+
+ /**
+ * Creates an instance of NormalDistributionStatistics.
+ *
+ * @param min Min.
+ * @param max Max.
+ * @param sumOfSquares Sum of squares.
+ * @param sumOfValues Sum of values.
+ * @param n N.
+ */
+ public NormalDistributionStatistics(double min, double max, double sumOfSquares, double sumOfValues, long n) {
+ this.min = min;
+ this.max = max;
+ this.sumOfSquares = sumOfSquares;
+ this.sumOfValues = sumOfValues;
+ this.n = n;
+ }
+
+ /**
+ * Returns plus of normal distribution statistics.
+ *
+ * @param stats Stats.
+ * @return plus of normal distribution statistics.
+ */
+ public NormalDistributionStatistics plus(NormalDistributionStatistics stats) {
+ return new NormalDistributionStatistics(
+ Math.min(this.min, stats.min),
+ Math.max(this.max, stats.max),
+ this.sumOfSquares + stats.sumOfSquares,
+ this.sumOfValues + stats.sumOfValues,
+ this.n + stats.n
+ );
+ }
+
+ /**
+ * @return mean value.
+ */
+ public double mean() {
+ return sumOfValues / n;
+ }
+
+ /**
+ * @return variance value.
+ */
+ public double variance() {
+ double mean = mean();
+ return (sumOfSquares / n) - mean * mean;
+ }
+
+ /**
+ * @return standard deviation value.
+ */
+ public double std() {
+ return Math.sqrt(variance());
+ }
+
+ /**
+ * @return min value.
+ */
+ public double min() {
+ return min;
+ }
+
+ /**
+ * @return max value.
+ */
+ public double max() {
+ return max;
+ }
+}