Разделение категориальных предикторов в деревьях классификации

Проблемы в разделении многоуровневых предикторов

Когда вы выращиваете дерево классификации, находя, что оптимальное бинарное разделение для категориального предиктора со многими уровнями более в вычислительном отношении сложно, чем нахождение разделения для непрерывного предиктора. Для непрерывного предиктора дерево может разделить на полпути между любыми двумя смежными, уникальными значениями предиктора. В отличие от этого, чтобы найти точное, оптимальное бинарное разделение для категориального предиктора с уровнями L, дерево классификации должно рассмотреть разделения ^2L–1–1. Получить эту формулу:

Считайте количество способов присвоить L отличные значения левым и правым узлам. Существуют 2^L пути.
Разделитесь 2^L на 2, потому что левый и правый может быть подкачан.
Отбросьте случай, который имеет пустой узел.

Для проблем регрессии и бинарных проблем классификации, программное обеспечение использует точный алгоритм поиска через вычислительный ярлык [1]. Дерево может заказать категории средним ответом (для регрессии) или вероятность класса для одного из классов (для классификации). Затем оптимальное разделение является одним из L – 1 разделение для упорядоченного списка. Поэтому вычислительные проблемы возникают только, когда вы выращиваете деревья классификации для данных с K ≥ 3 класса.

Алгоритмы для категориального разделения предиктора

Чтобы уменьшать расчет, программное обеспечение предлагает несколько эвристических алгоритмов для нахождения хорошего разделения. Можно выбрать алгоритм для разделения категориальных предикторов при помощи 'AlgorithmForCategorical' аргумент пары "имя-значение", когда вы выращиваете использование дерева классификации fitctree или когда вы создаете ученика классификации, использующего templateTree для ансамбля классификации (fitcensemble) или мультикласс модель ECOC (fitcecoc).

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

Доступные эвристические алгоритмы: вытяните оставленный чистотой, основным компонентно-ориентированным разделением и one-all классом.

Вытяните оставленный чистотой

Получение по запросу, оставленное алгоритмом чистоты, начинает со всего L категориальные уровни на правильной ветви. Алгоритм затем принимает эти меры:

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

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

Выберите этот алгоритм путем определения 'AlgorithmForCategorical','PullLeft' \in fitctree или templateTree.

Основное компонентно-ориентированное разделение

Основной компонентно-ориентированный алгоритм разделения [2] находит близко-к-оптимальному бинарный раздел уровней предиктора L путем поиска отделяющейся гиперплоскости. Гиперплоскость перпендикулярна первому основному компоненту взвешенной ковариационной матрицы матрицы вероятности класса в центре.

Алгоритм присваивает счет каждой из категорий L, вычисленных как скалярное произведение между найденным основным компонентом и вектором из вероятностей класса для той категории. Затем выбранное разделение является одним из L – 1 разделение, который максимизирует критерий разделения.

Выберите этот алгоритм путем определения 'AlgorithmForCategorical','PCA' \in fitctree или templateTree.

One-All классом

One-all алгоритмом класса начинает со всего L категориальные уровни на правильной ветви. Для каждого из классов K алгоритм заказывает категории на основе их вероятности для того класса.

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

Выберите этот алгоритм путем определения 'AlgorithmForCategorical','OVAbyClass' \in fitctree или templateTree.

Смотрите данные с многоуровневыми категориальными предикторами

Скрипт Open Live Script

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

Загрузка демонстрационных данных

Загрузите census1994 файл. Этот набор данных состоит из демографических данных Бюро переписи США, чтобы предсказать, передает ли индивидуум 50 000$ в год. Задайте массив ячеек из символьных векторов, содержащий имена переменных.

load census1994
VarNames = adultdata.Properties.VariableNames;

Некоторые имена переменных в adultdata таблица содержит _ символ. Замените экземпляры _ с пробелом.

VarNames = strrep(VarNames,'_',' ');

Задайте данные о предикторе tbl и вектор отклика Y.

tbl = adultdata(:,1:end-1);
Y = categorical(adultdata.salary);

Смотрите категориальные предикторы

Некоторые категориальные переменные имеют много уровней (категории). Считайте количество уровней каждого категориального предиктора.

Найдите индексы категориальных предикторов, которые не являются числовыми в tbl таблица при помощи varfun и isnumeric. varfun функция применяет isnumeric функционируйте к каждой переменной таблицы tbl.

cat = ~varfun(@isnumeric,tbl,'OutputFormat','uniform');

Задайте анонимную функцию, чтобы считать количество категорий в категориальном предикторе с помощью numel и categories.

countNumCats = @(var)numel(categories(categorical(var)));

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

Используйте varfun и countNumCats считать количество категорий для категориальных предикторов в tbl.

numCat = varfun(@(var)countNumCats(var),tbl(:,cat),'OutputFormat','uniform');

Постройте количество категорий для каждого категориального предиктора.

figure
barh(numCat);
h = gca;
h.YTickLabel = VarNames(cat);
ylabel('Predictor')
xlabel('Number of categories')

Обучите модель

Для бинарной классификации программное обеспечение использует вычислительный ярлык, чтобы найти оптимальное разделение для категориальных предикторов со многими категориями. Для классификации больше чем с двумя классами можно выбрать точный алгоритм или эвристический алгоритм, чтобы найти хорошее разделение при помощи 'AlgorithmForCategorical' аргумент пары "имя-значение" fitctree или templateTree. По умолчанию программное обеспечение выбирает оптимальное подмножество алгоритмов для каждого разделения с помощью известного количества классов и уровней категориального предиктора.

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

Mdl = fitctree(tbl,Y)

Mdl = 
  ClassificationTree
           PredictorNames: {1x14 cell}
             ResponseName: 'Y'
    CategoricalPredictors: [2 4 6 7 8 9 10 14]
               ClassNames: [<=50K    >50K]
           ScoreTransform: 'none'
          NumObservations: 32561


  Properties, Methods

Ссылки

[1] Бреимен, L., Дж. Х. Фридман, Р. А. Олшен и К. Дж. Стоун. Классификация и деревья регрессии. Бока-Ратон, FL: Chapman & Hall, 1984.

[2] Котельщик, Д., С. Цз. Хун и Дж. Р. М. Хоскинг. “Деля Номинальные Атрибуты в Деревьях решений”. Анализ данных и Открытие Знаний, Издание 3, 1999, стр 197–217.

Документация