Что такое дерево и как оно применяется в строительстве

Статья познакомит вас с понятием дерева как структуры данных, пояснит в каких случаях и для чего можно их применять:

• рассмотрены достоинства и недостатки деревьев относительно списков и массивов, исходя из которых вы сможете выбрать наиболее подходящую структуру данных для своей задачи;
• показаны основные проблемы реализации деревьев поиска, которые должны подтолкнуть вас использовать готовые библиотеки, а не пытаться сделать все самостоятельно;
• описаны Kd-деревья — решаемые проблемы и предлагаемые подходы.

1 Что такое деревья (в программировании)?

Математическое определение дерева — «граф без петель и циклов» вряд-ли пояснит рядовому человеку какие выгоды можно извлечь из такой структуры данных.

В некоторых книгах, посвященным разработке алгоритмов, деревья определяются рекурсивно. Дерево является либо пустым, либо состоит из узла (корня), являющегося родительским узлом для некоторого количества деревьев (это количество определяет арность дерева) [1, 2].

САМОЕ ДОРОГОЕ ДЕРЕВО В МИРЕ ! И ЧЕМ ЖЕ ОНО ТАК ЦЕНИТСЯ? УДОВОЕ ДЕРЕВО!

Рабочее определение (в рамках этой статьи): дерево — это способ организации данных в виде иерархической структуры.

Когда применяются древовидные структуры:

1. иногда такая иерархия существует в предметной области вашей программы, например, она должна обрабатывать гениалогическое дерево или работать со структурой каталогов на жестком диске. В таких случаях инода имеет смысл сохранить между объектами вашей программы существующие отношения иерархии:
   Дерево каталогов операционной системы UNIX
2. в других случаях между объектами, которые обрабатывает ваша программа отношения иерархии явно не заданы, однако, их можно задать и это сделает обработку данных в программе более удобной. Например, при разработке парсеров или трансляторов полезным может оказаться дерево синтаксического разбора (синтаксическое дерево) [4], хотя в выражениях типа «1+7*3» иерархия операций не так очевидна;
3. не секрет, что поиск объектов наиболее эффективен если они упорядочены. В частности, поиск значения в неупорядоченном наборе из 1000 элементов в худшем случае потребует 1000 операций, а в упорядоченном — можно обойтись всего 10.

Двоичный поиск [3] выполняется над отсортированным массивом. На каждом шаге искомый элемент сравнивается со значением, находящимся посередине массива. В зависимости от результатов сравнения — либо левая, либо правая части могут быть «отброшены».

2 Деревья и другие структуры данных

Итак, у нас есть много данных — возможно это информация о температуре за несколько лет, а может быть — данные о фирмах в вашем городе. Как хранить их внутри вашего приложения? — Правильный ответ зависит от того, как именно вы будете пользоваться этими данными.

В таблице приведены асимптотические оценки часто используемых операций над некоторыми структурами данных. На случай если вы еще не освоили асимптотический анализ, в таблице показано примерное значение количества действий, необходимых для выполнения операции над контейнером из 10 тысяч элементов.

Сколько простоит каркасный дом? / Реальный срок службы каркасного дома

удаление элемента по указателю (итератору)

поиск элемента с заданным значением

вставка элемента (значения)

O(1)
~ 1 O(1)
~ 1 O(n)
~ 10000

(вернет i-тый по значению элемент)

Особенностью массивов является хранение данных в непрерывной области памяти. За счет этого обеспечивается максимальная эффективность операции произвольного доступа, однако:

1. при удалении элемента нужно «сдвинуть» все значения, размещенные «справа»;
2. при вставке может потребоваться создание массива большего размера и копирование туда всех данных из старого массива;

При поиске значения в массиве мы в худшем случае переберем все элементы, то есть выполним O(n) операций. Однако, если массив упорядочен — мы можем применить двоичный поиск, который значительно эффективнее.

Связные списки хранят значения в узлах, разбросанных по памяти и связанных между собой указателями. За счет этого, вставка и удаление работает очень быстро, однако для обращения к N -ному элементу списка придется пройти по указателям N раз.

Деревья поиска, как и связные списки состоят из узлов, связанных указателями. Однако узлы эти упорядочены определенным образом — за счет этого увеличивается эффективность поиска, но осложняется операция вставки элемента. Эта структура данных, в ряде случаев,может иметь преимущества над массивами и связными списками — посмотрим за счет чего это обеспечивается…

3 Деревья поиска

Двоичное дерево состоит из узлов, каждый из которых хранит свое значение, а также две ссылки — на правое и левое поддерево. Если справа или слева нет узлов — соответствующая ссылка равна нулю (в С++ — нулевой указатель). Дерево представляется корнем (ссылкой на самый верхний узел).

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

При обходе такого дерева, начиная с левого поддерева, значения будут просмотрены в порядке неубывания, начиная с правого – невозрастания, т.е. дерево поиска хранит отсортированные данные:

В процессе поиска элемента в дереве, мы сравниваем его со значением корня, если корень оказался больше — то нам нет смысла рассматривать правое поддерево (ведь там все значения еще больше). За счет этого на каждом сравнении «отсекается» узлов дерева, а значит — мы получаем поиск с оценкой сложности O(log(n)) .

Операция вставки выполняет добавление листа в дерево, то справа и слева от нового узла будет пусто ( null ). При вставке мы выполняем поиск подходящей свободной позиции, с учетом требования «значения вершин левого поддерева должны всегда оказываться меньше или равны значению корневого узла, а правого – больше». Алгоритм вставки значения E в дерево может выглядеть так:

1. если дерево является пустым – то E помещается в корневую вершину;
2. если значение E больше значения корневой вершины – осуществляется вставка E в правое поддерево (рекурсивно), иначе – в левое.

Пример использования такого алгоритма приведен в таблице:

Шаг 0: исходное дерево
Шаг 1: определям, что вставлять нужно в левое поддерево
Шаг 2: 6 > 4 , поэтому вставляем в правое поддерево
Шаг 3: 6 < 7 , вставка в левое поддеррево
Шаг 4: 6 > 5 , вставляем справа, но там пусто.

В качестве упражнения полезно попробовать вставить в дерево узел со значением 8.5 , а также, взять пустое дерево (без элементов) и добавить в него последовательно узлы [1, 11, 32, 46, 48] . Если в результате у вас получится дерево, как на приведенной ниже картинке — вы все поняли и сделали правильно:

Этот пример иллюстрирует основную проблему описанного тут алгоритма вставки узлов — если подать ему на вход упорядоченные данные — то дерево «вытянется» в обыкновенный двусвязный список. В частности, для выполнения поиска в таком «дереве» из N элементов нам придется перейти по укзателям N раз.

Удаление элемента из дерева поиска, несколько запутаннее, поэтому алгоритм тут не приведен, зато приведены поясняющие иллюстрации:

Такие алгоритмы добавления элемента и удаления элемента не гарантируют сбалансированности полученного дерева, то есть дерево может «вырождаться» в список, как показано на рисунке выше. Существуют самобалансирующиеся деревья поиска, например, красно-черные деревья, АВЛ-деревья или расширяющиеся деревья, но их рассмотрение выходит за рамки статьи [2, 5, 6]. Нужно знать, что аналогичные операции для, таких деревьев реализуются несколько труднее, но их вычислительная сложность можно оценить как O(log(N)) . Эти алгоритмы уже реализованы во множестве библиотек и обычно их не требуется писать самостоятельно. Например, в стандартной библиотеке С++ они представлены классами std::map и std::set .

4 Kd-деревья

Во многих программах появляется необходимость хранения и эффективной обработки объектов на плоскости. Это не только картографические приложения, но и все двумерные игры. Задумывались ли вы о том, как эту задачу решают игровые движки?

Игровой уровень обычно значительно больше, чем видимая в данный момент область экрана, а отрисовывать необходимо только видимые объекты. Значит движок должен уметь быстро получать объекты, входящие в заданную прямоугольную область. Кроме того, объекты умеют перемещаться и сталкиваться друг с другом — когда Марио собирает монетку, она исчезает, а счет увеличивается. Игровой движок должен эффективно реализовывать обработку столкновения объектов — подумайте почему эта задача сводится к первой. Примитивная реализация поиска столкнувшихся объектов может заключаться в переборе всех пар, то есть имеет вычислительную сложность O(n^2) . Даже в Марио (которой более 20 лет) уровни содержали тысячи объектов, а значит такой алгоритм не подойдет.

Мы уже разобрались с тем, что для эффективной реализации поиска объекты нужно хранить упорядоченными. Однако, как хранить точки? — ведь у них есть две (или три) координаты, а сортировка по одной из них не обеспечит приемлемую скорость поиска. Именно эти проблемы решают Kd-деревья.

Общая идея kd-деревьев заключается в разделении плоскости, содержащей объекты на части (прямоугольные области) таким образом, что в каждой области содержится один объект. При этом, между областями можно выстроить иерархические зависимости, за счет которых можно существенно повысить эффективность поиска. Существуют различные типы kd-деревьев, отличающиеся выбором секущей плоскости.

Задача: есть множество точек, находящихся на плоскости, нужно выстроить объекты в иерархическую структуру, исходя из их координат для обеспечения эффективного поиска. Описанные ниже подходы можно обобщить до более сложных геометрических объектов (не точек) и пространств больших размерностей.

Первый вариант решения:

1. выберем произвольную точку на плоскости (желательно ближе к центру), поместим ее в корень дерева. Плоскость разобьем на 2 части — левую и правую (относительно точки);
2. выделим в каждой области по точке, которую поместим в корень поддерева, разобьем каждое подпространство на два — нижнее и верхнее;
3. описанный процесс повторяется до тех пор, пока в каждой области плоскости не окажется по одной точке. При разбиении чередуются измерения, на основе которых выполняется разделение пространства (верхнее-нижнее, левое-правое).

Пример построения такого дерева приведен на рисунке. Тут плоскость сначала разбита относительно точки А на левую и правую, правая в свою очередь разбита на нижнюю и верхнюю относительно точки С. Нижняя опять разбивается на левую и правую относительно точки D .

С такой структурой данных, алгоритм вывода всех точек, входящих в Прямоугольник может выглядеть так:

Цветом на приведенной выше схеме обозначена область поиска. Она не пересекается с областью B (расположенной левее А ). Даже если бы в этой области были миллионы точек — мы «отсекли» бы их за одну итерацию алгоритма — то есть мы получили полноценный двоичный поиск на плоскости. Визуализация алгоритма:

При перемещении объектов может возникать необходимость перестроения дерева — если объект переместился из одной области «родительского» объекта в другую.

Описанный подход называется Kd-деревья с циклическим проходом по измерениям. Возможны и другие варианты выбора секущей плоскости — например каждый узел квадрадерева делит свою часть плоскости на 4 части (левая верхняя, левая нижняя, правая верхняя, права нижняя). Если в какой-то части оказывается более 1 объекта — то она делится дальше. Октадеревья адаптируют эту идею к трехмерному пространству.

Источник: pro-prof.com

Что такое дерево решений и где его используют?

Ребята, привет! Сегодня команда ProductStar подготовила для вас статью, в которой мы рассмотрели общие принципы работы и области применения дерева решений. Материал подготовлен на основе работы Акобира Шахиди «Деревья решений: общие принципы».

Дерево решений — эффективный инструмент интеллектуального анализа данных и предсказательной аналитики. Он помогает в решении задач по классификации и регрессии.

Дерево решений представляет собой иерархическую древовидную структуру, состоящую из правила вида «Если …, то . ». За счет обучающего множества правила генерируются автоматически в процессе обучения.

В отличие от нейронных сетей, деревья как аналитические модели проще, потому что правила генерируются на естественном языке: например, «Если реклама привела 1000 клиентов, то она настроена хорошо».

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

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

• дерево классификации — когда целевая переменная дискретная;
• дерево регрессии — когда целевая переменная непрерывная.

Развитие инструмента началось в 1950-х годах. Тогда были предложены основные идеи в области исследований моделирования человеческого поведения с помощью компьютерных систем.

Дальнейшее развитие деревьев решений как самообучающихся моделей для анализа данных связано с Джоном Р. Куинленом (автором алгоритма ID3 и последующих модификаций С4.5 и С5.0) и Лео Брейманом, предложившим алгоритм CART и метод случайного леса.

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

Простой случай: примеры попадают в узел, проходят проверку и разбиваются на два подмножества:

• первое — те, которые удовлетворяют установленное правило;
• второе — те, которые не удовлетворяют установленное правило.

Далее к каждому подмножеству снова применяется правило, процедура повторяется. Это продолжается, пока не будет достигнуто условие остановки алгоритма. Последний узел, когда не осуществляется проверка и разбиение, становится листом.

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

Пример попадает в лист, если соответствует всем правилам на пути к нему. К каждому листу есть только один путь. Таким образом, пример может попасть только в один лист, что обеспечивает единственность решения.

Изучите основные понятия, которые используются в теории деревьев решений, чтобы в дальнейшем было проще усваивать новый материал.

Его применяют для поддержки процессов принятия управленческих решений, используемых в статистистике, анализе данных и машинном обучении. Инструмент помогает решать следующие задачи:

• Классификация. Отнесение объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные задачи.
• Регрессия (численное предсказание). Предсказание числового значения независимой переменной для заданного входного вектора.
• Описание объектов. Набор правил в дереве решений позволяет компактно описывать объекты. Поэтому вместо сложных структур, используемых для описания объектов, можно хранить деревья решений.

Основная задача при построении дерева решений — последовательно и рекурсивно разбить обучающее множество на подмножества с применением решающих правил в узлах. Но как долго надо разбивать? Этот процесс продолжают до того, пока все узлы в конце ветвей не станут листами.

Узел становится листом в двух случаях:

• естественным образом — когда он содержит единственный объект или объект только одного класса;
• после достижения заданного условия остановки алгоритм — например, минимально допустимое число примеров в узле или максимальная глубина дерева.

В основе построения лежат «жадные» алгоритмы, допускающие локально-оптимальные решения на каждом шаге (разбиения в узлах), которые приводят к оптимальному итоговому решению. То есть при выборе одного атрибута и произведении разбиения по нему на подмножества, алгоритм не может вернуться назад и выбрать другой атрибут, даже если это даст лучшее итоговое разбиение. Следовательно, на этапе построения дерева решений нельзя точно утверждать, что удастся добиться оптимального разбиения.

Популярные алгоритмы, используемых для обучения деревьев решений, строятся на базе принципа «разделяй и властвуй». Задают общее множество S, содержащее:

• n примеров, для каждого из которых задана метка класса Ci(i = 1..k);
• m атрибутов Aj(j = 1..m), которые определяют принадлежность объекта к тому или иному классу.

Тогда возможно три случая:

1. Примеры множества S имеют одинаковую метку Ci, следовательно, все обучающие примеры относятся к одному классу. В таком случае обучение не имеет смысла, потому что все примеры в модели будут одного класса, который и «научится» распознавать модель. Само дерево будет похоже на один большой лист, ассоциированный с классом Ci. Тогда его использование не будет иметь смысла, потому что все новые объекты будут относиться к одному классу.
2. Множество S — пустое множество без примеров. Для него сформируется лист, класс которого выберется из другого множества. Например, самый распространенный из родительского множества класс.
3. Множество S состоит из обучающих примеров всех классов Ck. В таком случае множество разбивается на подмножества в соответствии с классами. Для этого выбирают один из атрибутов Aj множества S, состоящий из двух и более уникальных значений: a1, a2, …, ap), где p — число уникальных значений признака. Множество S разбивают на p подмножеств (S1, S2, …, Sp), состоящих из примеров с соответствующим значением атрибута. Процесс разбиения продолжается, но уже со следующим атрибутом. Он будет повторяться, пока все примеры в результирующих подмножества не окажутся одного класса.

Третья применяется в большинстве алгоритмов, используемых для построения деревьев решений. Эта методика формирует дерево сверху вниз, то есть от корневого узла к листьям.

Сегодня существует много алгоритмов обучения: ID3, CART, C4.5, C5.0, NewId, ITrule, CHAID, CN2 и другие. Самыми популярными считаются:

• ID3 (Iterative Dichotomizer 3). Алгоритм позволяет работать только с дискретной целевой переменной. Деревья решений, построенные на основе ID3, получаются квалифицирующими. Число потомков в узле неограниченно. Алгоритм не работает с пропущенными данными.
• C4.5. «Продвинутая» версия ID3, дополненная возможностью работы с пропущенными значениями атрибутов. В 2008 году издание Spring Science провело исследование и выявило, что C4.5 — самый популярный алгоритм Data Mining.
• CART (Classification and Regression Tree). Алгоритм решает задачи классификации и регрессии, так как позволяет использовать дискретную и непрерывную целевые переменные. CART строит деревья, в каждом узле которых только два потомка.

Построение осуществляется в 4 этапа:

1. Выбрать атрибут для осуществления разбиения в данном узле.
2. Определить критерий остановки обучения.
3. Выбрать метод отсечения ветвей.
4. Оценить точность построенного дерева.

Далее рассмотрим каждый подробнее.

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

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

В основе критерия лежит информационная энтропия:

где n — число классов в исходном подмножестве, Ni — число примеров i-го класса, N — общее число примеров в подмножестве.

Энтропия рассматривается как мера неоднородности подмножества по представленным в нем классам. И даже если классы представлены в равных долях, а неопределенность классификации наибольшая, то энтропия тоже максимальная. Логарифм от единицы будет обращать энтропию в ноль, если все примеры узла относятся к одному классу.

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

Но на деле об энтропии говорят редко. Специалисты уделяют внимание обратной величине — информации. В таком случае лучшим атрибутом будет тот, который обеспечит максимальный прирост информации результирующего узла относительно исходного:

где Info(S) — информация, связанная с подмножеством S до разбиения, Info(Sa) — информация, связанная с подмножеством, полученным при разбиении атрибута A.

Задача выбора атрибута в такой ситуации заключается в максимизации величины Gain(A), которую называют приростом информации. Поэтому теоретико-информационный подход также известен под название «критерий прироста информации.

В основе этого метода лежит использования индекса Джини. Он показывает, как часто случайно выбранный пример обучающего множества будет распознан неправильно. Важное условие — целевые значения должны браться из определенного статистического распределения.

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

Индекс Джини рассчитывается по формуле:

где Q — результирующее множество, n — число классов в нем, pi — вероятность i-го класса (выраженная как относительная частота примеров соответствующего класса).

Значение показателя меняется от 0 до 1. Если индекс равен 0, значит, все примеры результирующего множества относятся к одному классу. Если равен 1, значит, классы представлены в равных пропорциях и равновероятны. Оптимальным считают то разбиение, для которого значение индекса Джини минимально.

Алгоритм обучения может работать до получения «чистых» подмножеств с примерами одного класса. В таком случае высока вероятность получить дерево, в котором для каждого примера будет создан отдельный лист. Такое дерево не получится применять на практике из-за переобученности. Каждому примеру будет соответствовать свой уникальный путь в дереве. Получится набор правил, актуальный только для данного примера.

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

Специалисты решили принудительно останавливать строительство дерева, чтобы оно не становилось «переобученным».

Для этого используют несколько подходов:

• Ранняя остановка. Алгоритм останавливается после достижения заданного значения критерия (например, процентной доли правильно распознанных примеров). Преимущество метода — сокращение временных затрат на обучение. Главный недостаток — ранняя остановка негативно сказывается на точности дерева. Из-за этого многие специалисты советуют отдавать предпочтение отсечению ветей.
• Ограничение глубины дерева. Алгоритм останавливается после достижения установленного числа разбиений в ветвях. Этот подход также негативно сказывается на точности дерева.
• Задание минимально допустимого числа примеров в узле. Устанавливается ограничение на создание узлов с числом примером меньше заданного (например, 7). В таком случае не будут создаваться тривиальные разбиения и малозначимые правила.

Этими подходами пользуются редко, потому что они не гарантируют лучшего результата. Чаще всего, они работают только в каких-то определенных случаях. Рекомендаций по использованию какого-либо метода нет, поэтому аналитикам приходится набирать практический опыт путем проб и ошибок.

Без ограничения «роста» дерево решений станет слишком большим и сложным, что сделает невозможной дальнейшую интерпретацию. А если делать решающие правила для создания узлов, в которые будут попадать по 2-3 примера, они не лишатся практической ценности.

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

Но и тут есть проблема: такая задача относится к классу NP-полных задач, а они, как известно, эффективных решений не имеют. Поэтому прибегают к методу отсечения ветвей, который реализуется в 3 шага:

1. Строительство полного дерева, в котором листья содержат примеры одного класса.
2. Определение двух показателей: относительную точность модели (отношение числа правильно распознанных примеров к общему числу примеров) и абсолютную ошибку (число неправильно классифицированных примеров).
3. Удаление листов и узлов, потеря которых минимально скажется на точности модели и увеличении ошибки.

Отсечение ветвей проводят противоположно росту дерева, то есть снизу вверх, путем последовательного преобразования узлов в листья.

Главное отличие метода «отсечение ветвей» от преждевременной остановки — получается найти оптимальное соотношение между точностью и понятностью. При этом уходит больше времени на обучение, потому что в рамках этого подхода изначально строится полное дерево.

Иногда упрощения дерева недостаточно, чтобы оно легко воспринималось и интерпретировалось. Тогда специалисты извлекают из дерева решающие правила и составляют из них наборы, описывающие классы.

Для извлечения правил нужно отслеживать все пути от корневого узла к листьям дерева. Каждый путь дает правило с множеством условий, представляющих собой проверку в каждом узле пути.

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

Преимущества:

• Формируют четкие и понятные правила классификации. Например, «если возраст < 40 и нет имущества для залога, то отказать в кредите». То есть деревья решений хорошо и быстро интерпретируются.
• Способны генерировать правила в областях, где специалисту трудно формализовать свои знания.
• Легко визуализируются, то есть могут «интерпретироваться» не только как модель в целом, но и как прогноз для отдельного тестового субъекта (путь в дереве).
• Быстро обучаются и прогнозируют.
• Не требуется много параметров модели.
• Поддерживают как числовые, так и категориальные признаки.

• Деревья решений чувствительны к шумам во входных данных. Небольшие изменения обучающей выборки могут привести к глобальным корректировкам модели, что скажется на смене правил классификации и интерпретируемости модели.
• Разделяющая граница имеет определенные ограничения, из-за чего дерево решений по качеству классификации уступает другим методам.
• Возможно переобучение дерева решений, из-за чего приходится прибегать к методу «отсечения ветвей», установке минимального числа элементов в листьях дерева или максимальной глубины дерева.
• Сложный поиск оптимального дерева решений: это приводит к необходимости использования эвристики типа жадного поиска признака с максимальным приростом информации, которые в конечном итоге не дают 100-процентной гарантии нахождения оптимального дерева.
• Дерево решений делает константный прогноз для объектов, находящихся в признаковом пространстве вне параллелепипеда, который охватывает не все объекты обучающей выборки.

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

Успешнее всего деревья применяют в следующих областях:

• Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.
• Промышленность. Контроль качества продукции (обнаружение дефектов в готовых товарах), испытания без нарушений (например, проверка качества сварки) и т.п.
• Медицина. Диагностика заболеваний разной сложности.
• Молекулярная биология. Анализ строения аминокислот.
• Торговля. Классификация клиентов и товар.

Это не исчерпывающий список областей применения дерева решений. Круг использования постоянно расширяется, а деревья решений постепенно становятся важным инструментом управления бизнес-процессами и поддержки принятия решений.

Надеемся, наша статья оказалась для вас полезной. Больше интересного контента от ProductStar вы найдёте в нашем блоге на vc и в аналитическом тг-канале.

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

Источник: vc.ru