# Дерево решений CDecisionTree

<!-- TOC -->

- [Дерево решений CDecisionTree](#дерево-решений-cdecisionTree)
	- [Параметры построения модели](#параметры-построения-модели)
	- [Модель](#модель)
	- [Пример](#пример)

<!-- /TOC -->

Метод дерева решений представляет собой классификацию на основе последовательного сравнения признаков данного объекта с некоторыми пороговыми значениями. На основе результата сравнения можно попасть в одну из дочерних вершин и так до тех пор, пока не будет достигнута листовая вершина, в которой производится окончательная классификация.

В **NeoML** алгоритм реализован классом `CDecisionTree`. Он предоставляет метод `Train` для обучения модели, выполняющей многоклассовую классификацию.

## Параметры построения модели

Параметры реализованы структурой `CDecisionTree::CParams`.

- *MinContinuousSubsetSize* — [для непрерывного признака] минимальное количество векторов в подмножестве вершины;
- *MinDiscreteSubsetSize* — [для дискретного признака] минимальное количество векторов в подмножестве вершины;
- *MinDiscreteSubsetPart* — [для дискретного признака] минимальный вес векторов в подмножестве вершины относительно веса родителя (может принимать значения от 0 до 1);
- *MinContinuousSubsetPart* — [для непрерывного признака] минимальный вес векторов в подмножестве вершины относительно веса родителя (может принимать значения от 0 до 1);
- *MinSplitSize* — минимальное количество векторов в подмножестве вершины, при котором она будет делиться дальше;
- *MaxTreeDepth* — максимальная глубина дерева;
- *MaxNodesCount* — максимальное количество вершин в дереве;
- *SplitCriterion* — критерий деления подмножеств при построении дерева;
- *ConstNodeThreshold* — доля одинаковых элементов в подмножестве, при превышении которой будет создана константная вершина (может принимать значения от 0 до 1);
- *RandomSelectedFeaturesCount* — при построении каждого узла используется не больше этого количества случайно выбранных признаков. Задайте значение `-1`, чтобы использовать все признаки;
- *AvailableMemory* — ограничение памяти, используемой алгоритмом (в байтах); если обучение завершается с ошибкой, попробуйте увеличить этот параметр (по умолчанию запрашивается 1Гб);
- *MulticlassMode* - подход, используемый при многоклассовой классификации: SingleClassifier (по умолчанию), OneVsAll или OneVsOne.

## Модель

Построенная модель представляет собой дерево, каждой внутренней вершине которого соответствует пара (индекс разделяющего признака, набор его значений), а листам — вероятности отнесения к различным классам.

Классификация заданного вектора выполняется путем поиска подходящего для него листа. Поиск листа начинается в корне дерева, при этом следующая вершина выбирается исходя из значения разделяющего признака текущей вершины.

Построенная модель описывается интерфейсом `IDecisionTreeModel`:

```c++
// Интерфейс модели классификатора.
class NEOML_API IDecisionTreeModel : public IModel {
public:
	virtual ~IDecisionTreeModel() = 0;

	// Получить количество детей узла.
	virtual int GetChildrenCount() const = 0;

	// Получить дочерний узел.
	virtual CPtr<IDecisionTreeModel> GetChild( int index ) const = 0;

	// Получить информацию об узле.
	virtual void GetNodeInfo( CDecisionTreeNodeInfo& info ) const = 0;

	// Сериализация.
	virtual void Serialize( CArchive& ) = 0;
};
```

## Пример

Ниже представлен простой пример обучения древесного классификатора на данных, содержащих только непрерывные признаки. Входные данные подаются в виде объекта, реализующего интерфейс [`IProblem`](Problems.md).

```c++
CPtr<IDecisionTreeModel> buildModel( IProblem* data )
{
	CDecisionTree::CParams param;
	param.MinContinuousSubsetPart = 0.10; // В поддерево попадает не меньше 10% вершин.
	param.MinContinuousSubsetSize = 128; // Считаем, что в датасетах только непрерывные признаки.
	param.MinSplitSize = 16; // В поддереве не меньше 16 вершин.
	param.MaxTreeDepth = 10; // Дерево не глубже 10 уровней.
	param.SplitCriterion = CDecisionTree::SC_InformationGain;

	CDecisionTree builder( param );

	return dynamic_cast<IDecisionTreeModel*>( builder.Train( data ).Ptr() );
}
```