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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Увеличение параметра 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.

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

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

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

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

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

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

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