Поделиться через

  • Статья

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

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

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

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

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

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

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

Построение дерева

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

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

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

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

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

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

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

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

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

Методы количественной оценки и выбор компонентов

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

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

Алгоритм

Метод анализа

Комментарии

Деревья решений

Оценка интересности

Энтропия Шеннона

Алгоритм Байеса с априорной оценкой K2

Эквивалент Дирихле метода Байеса с однородной априорной оценкой (выбор по умолчанию)

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

Линейная регрессия

Оценка интересности

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

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

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

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

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

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

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

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

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

  • Увеличение параметра COMPLEXITY_PENALTY для ограничения роста дерева.

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

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

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

    ПримечаниеПримечание

    Можно использовать средства просмотра данных, доступные в службах SQL Server 2008 Integration Services, для визуализации распределения значений в данных и соответствующего группирования этих значений до начала интеллектуального анализа данных. Дополнительные сведения см. в разделе Профилирование данных с помощью задачи «Профилирование данных» и средства просмотра. Можно также исследовать, группировать и переразмечать данные в программе Microsoft Excel с помощью надстройки интеллектуального анализа данных для Excel 2007.

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

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

Задание параметров алгоритма

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

  • COMPLEXITY_PENALTY
    Управляет ростом дерева решений. Низкое значение увеличивает количество разбиений, а высокое количество — уменьшает. Значение по умолчанию основано на количестве атрибутов для конкретной модели, как описано в следующем списке.

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

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

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

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

    ПримечаниеПримечание

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

    [SQL Server Enterprise]

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

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

    Установите значение 0, чтобы отключить выбор компонентов.

    [SQL Server Enterprise]

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

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

    Установите значение 0, чтобы отключить выбор компонентов.

    [SQL Server Enterprise]

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

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

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

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

    Идентификатор

    Название

    1

    Энтропия

    2

    Алгоритм Байеса с априорной оценкой K2

    3

    Эквивалент Дирихле метода Байеса (BDE) с априорной оценкой

    (по умолчанию)

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

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

  • SPLIT_METHOD
    Определяет метод, используемый для разбиения узла. Доступны следующие параметры.

    Идентификатор

    Название

    1

    Binary: указывает, что независимо от реального числа значений атрибута дерево следует разбить на две ветви.

    2

    Complete: указывает, что в дереве можно создавать столько разбиений, сколько существует значений атрибута.

    3

    Both: указывает, что службы Analysis Services могут определять, какое разбиение лучше использовать — бинарное или полное.

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

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

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

Флаг модели

Описание

MODEL_EXISTENCE_ONLY

Столбец будет обрабатываться так, как будто у него два возможных состояния: Missing и Existing. NULL означает отсутствие значения.

Применяется к столбцам модели интеллектуального анализа данных.

NOT NULL

Указывает, что столбец не может принимать значение NULL. Если службы Analysis Services в ходе обучения модели обнаружат столбец со значением NULL, возникает ошибка.

Применяется к столбцам структуры интеллектуального анализа данных.

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

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

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

Можно, однако, применить параметр FORCED_REGRESSOR, чтобы гарантировать использование конкретного регрессора в алгоритме. Этот параметр может применяться только с алгоритмом дерева принятия решений (Майкрософт) и алгоритмом линейной регрессии (Майкрософт). Если пользователем задан флаг модели, алгоритм попытается найти уравнения регрессии в форме a*C1 + b*C2 + ... для подгонки шаблонов к узлам дерева. Вычисляется сумма остатков, и, если отклонение слишком велико, принудительно выполняется разбиение дерева.

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

Требования

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

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

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

Столбец

Типы содержимого

Входной атрибут

Continuous, Cyclical, Discrete, Discretized, Key, Ordered, Table

Прогнозируемый атрибут

Continuous, Cyclical, Discrete, Discretized, Ordered, Table
ПримечаниеПримечание

Типы содержимого Cyclical и Ordered поддерживаются, но алгоритм обрабатывает их как дискретные величины и не производит их особой обработки.