Технический справочник по алгоритму деревьев принятия решений Майкрософт

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

В этом разделе объясняется реализация алгоритма, описывается настройка поведения алгоритма для различных задач и ссылки на дополнительные сведения о запросах моделей дерева принятия решений.

Реализация алгоритма деревьев принятия решений

Алгоритм деревьев решений Майкрософт применяет байесовский подход к изучению моделей причинного взаимодействия, получая приблизительные апостериорные распределения для этих моделей. Подробное описание этого подхода см. в документе на сайте Microsoft Research по структуре и обучению параметров.

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

Алгоритм с использованием этих предыдущих сетей вычисляет относительные апостериорные вероятности структур сетей на основе текущих данных обучения и определяет структуры сетей с самыми высокими апостериорными вероятностями.

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

Создание дерева

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

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

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

Дискретные и непрерывные входные данные

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

Однако, если прогнозируемый атрибут дискретен и входные данные непрерывны, входные данные непрерывных столбцов автоматически дискретизированы. Вы можете принять значение по умолчанию, чтобы Analysis Services нашла оптимальное количество ячеек, или управлять способом дискретизации непрерывных входных данных, задавая свойства DiscretizationMethod и DiscretizationBucketCount. Дополнительные сведения см. в разделе "Изменение дискретизации столбца в модели интеллектуального анализа данных".

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

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

Дополнительные сведения о том, как алгоритм деревьев принятия решений Майкрософт работает с дискретными прогнозируемыми столбцами, см. в статье Learning Bayesian Networks: Сочетание знаний и статистических данных. Дополнительные сведения о том, как алгоритм деревьев решений Microsoft работает с непрерывным прогнозируемым столбцом, см. в приложении авторегрессивных моделей дерева для Time-Series Analysis.

Методы оценивания и выбор признаков

Алгоритм Microsoft Decision Trees предлагает три формулы для оценки прироста информации: энтропия Шеннона, байесианская сеть с априорной вероятностью K2 и байесианская сеть с равномерным распределением априорных вероятностей Дирихле. Все три метода хорошо зарекомендовали себя в области интеллектуального анализа данных. Мы рекомендуем поэкспериментировать с различными параметрами и методами оценки, чтобы определить, какие результаты обеспечивают наилучшие результаты. Дополнительные сведения об этих методах оценки см. в разделе "Выбор компонентов".

Все алгоритмы интеллектуального анализа данных служб Analysis Services автоматически используют выбор компонентов для улучшения анализа и уменьшения нагрузки на обработку. Метод, используемый для выбора признаков, зависит от алгоритма, используемого для сборки модели. Параметры алгоритма, управляющие выбором компонентов для модели дерева принятия решений, MAXIMUM_INPUT_ATTRIBUTES и MAXIMUM_OUTPUT.

Алгоритм	Метод анализа	Комментарии
Деревья принятия решений	Оценка интересности Энтропия Шеннона Байесовский с априорным распределением K2 Байесовский Дирихлеев с равномерным априорным распределением (по умолчанию)	Если для всех столбцов содержатся не двоичные непрерывные значения, оценка интересности используется для всех столбцов, чтобы обеспечить согласованность. В противном случае используется используемый по умолчанию или указанный метод.
Линейная регрессия	Оценка интересности	Линейная регрессия использует только интересность, так как она поддерживает только непрерывные столбцы.

Масштабируемость и производительность

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

• Выбор компонентов для оптимизации выбора атрибутов.

• Байесовская оценка для контроля роста деревьев.

• Оптимизация бинирования для непрерывных атрибутов.

• Динамическое группирование входных значений для определения наиболее важных значений.

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

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

• Увеличьте значение параметра COMPLEXITY_PENALTY, чтобы ограничить рост дерева.

• Ограничьте количество элементов в моделях ассоциаций, чтобы ограничить количество созданных деревьев.

• Увеличьте значение параметра MINIMUM_SUPPORT, чтобы избежать переполнения.

• Ограничить число дискретных значений для любого атрибута до 10 или меньше. Можно попробовать группировать значения по-разному в разных моделях.

  Замечание

  Инструменты исследования данных, доступные в средах SQL Server 2014 Integration Services (SSIS), можно использовать для визуализации распределения значений в данных и соответствующего группирования значений перед началом интеллектуального анализа данных. Дополнительные сведения см. в разделе "Задача профилирования данных" и "Средство просмотра". Надстройки интеллектуального анализа данных для Excel 2007 также можно использовать для изучения, группирования и повторной маркировки данных в Microsoft Excel.

Настройка алгоритма дерева принятия решений

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

Замечание

Алгоритм деревьев принятия решений Майкрософт доступен во всех выпусках SQL Server; Однако некоторые расширенные параметры для настройки поведения алгоритма дерева принятия решений Майкрософт доступны только в определенных выпусках SQL Server. Список функций, поддерживаемых выпусками SQL Server, см. в разделе "Функции, поддерживаемые выпусками SQL Server 2012 ( (https://go.microsoft.com/fwlink/?linkid=232473).

Настройка параметров алгоритма

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

ШТРАФ ЗА СЛОЖНОСТЬ
Управляет ростом дерева принятия решений. Низкое значение увеличивает количество разбиений, а большое значение уменьшает количество разбиений. Значение по умолчанию основано на количестве атрибутов для конкретной модели, как описано в следующем списке:

• Для 1–9 атрибутов по умолчанию используется значение 0,5.

• Для 10–99 атрибутов значение по умолчанию — 0,9.

• Для 100 или более атрибутов значение по умолчанию — 0,99.

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

Замечание

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

[Доступно только в некоторых выпусках SQL Server ]

МАКСИМАЛЬНОЕ_КОЛИЧЕСТВО_ВХОДНЫХ_АТРИБУТОВ
Определяет количество входных атрибутов, которые алгоритм может обрабатывать перед вызовом выбора компонентов.

Значение по умолчанию — 255.

Задайте для этого значения значение 0, чтобы отключить выбор компонентов.

[Доступно только в некоторых выпусках SQL Server]

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

Значение по умолчанию — 255.

Задайте для этого значения значение 0, чтобы отключить выбор компонентов.

[Доступно только в некоторых выпусках SQL Server]

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

Значение по умолчанию равно 10.

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

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

Идентификатор	Имя
1	Энтропия
3	Байесовский с априорным распределением K2
4	Байесовский эквивалент Дирихле (BDE) с равномерным априорным распределением (по умолчанию)

Значение по умолчанию — 4 или BDE.

Описание этих методов оценки см. в разделе "Выбор компонентов".

Метод_Разделения
Определяет метод, используемый для разделения узла. Имеются следующие варианты:

Идентификатор	Имя
1	Двоичный: Указывает, что независимо от фактического количества значений для атрибута дерево должно быть разделено на две ветви.
2	Полный: Указывает, что дерево может создавать столько разбиений, сколько есть значения атрибутов.
3	Оба: Указывает, что службы Analysis Services могут определить, следует ли использовать двоичное или полное разделение для получения наилучших результатов.

Значение по умолчанию — 3.

Флаги моделирования

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

Флаг моделирования	Описание
Только_наличие_модели	Означает, что столбец будет рассматриваться как наличие двух возможных состояний: Missing и Existing. Значение NULL — это отсутствующее значение. Применяется к столбцам модели интеллектуального анализа данных.
НЕ ПУСТОЙ	Указывает, что столбец не может содержать значение NULL. Ошибка возникнет, если службы Analysis Services столкнутся с null'ом во время обучения модели. Применяется к столбцам структуры данных.

Регрессоры в моделях дерева принятия решений

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

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

Однако можно использовать параметр FORCE_REGRESSOR, чтобы гарантировать, что алгоритм будет использовать конкретный регрессор. Этот параметр можно использовать только с деревьями принятия решений Майкрософт и алгоритмами линейной регрессии Майкрософт. При установке флага моделирования алгоритм попытается найти уравнения регрессии формы a*C1 + b*C2 + ... для соответствия шаблонов в узлах дерева. Сумма остатков вычисляется, и если отклонение слишком велико, в дереве принудительно производится разделение.

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

Требования

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

Входные и предсказуемые столбцы

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

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

Замечание

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

См. также

Алгоритм деревьев принятия решений Майкрософт
Примеры запросов модели дерева принятия решений
Содержимое модели интеллектуального анализа данных для моделей дерева принятия решений (службы Analysis Services — интеллектуальный анализ данных)