Разделение категориальных предикторов в деревьях классификации
Проблемы разделения многоуровневых предикторов
Когда вы выращиваете классификационное дерево, найти оптимальное двоичное разделение для категориального предиктора со многими уровнями сложнее в вычислительном отношении, чем найти разделение для непрерывного предиктора. Для непрерывного предиктора дерево может разделиться на половины между любыми двумя смежными уникальными значениями предиктора. В отличие от этого, чтобы найти точное, оптимальное двоичное разделение для категориального предиктора с L уровнями, дерево классификации должно учитывать 2L–1-1 разделение. Для получения этой формулы:
Подсчитайте количество способов присвоения L разных значений левому и правому узлам. Всего 2.L способы.
Разделите 2L на 2, потому что слева и справа могут быть заменены.
Отменить случай с пустым узлом.
Для регрессионных задач и двоичных задач классификации программное обеспечение использует точный алгоритм поиска через вычислительный ярлык [1]. Дерево может упорядочить категории по среднему отклику (для регрессии) или вероятности класса для одного из классов (для классификации). Затем оптимальным разделением является один из L - 1 разделений для упорядоченного списка. Поэтому вычислительные проблемы возникают только тогда, когда вы выращиваете деревья классификации для данных с K ≥ 3 классами.
Алгоритмы категориального разделения предиктора
Чтобы уменьшить расчеты, программное обеспечение предлагает несколько эвристических алгоритмов для нахождения хорошего разделения. Можно выбрать алгоритм для разделения категориальных предикторов с помощью 'AlgorithmForCategorical' аргумент пары "имя-значение", когда вы растете дерево классификации используя fitctree или когда вы создаете классификатора, используя templateTree для классификационного ансамбля (fitcensemble) или многоклассовую модель ECOC (fitcecoc).
Если вы не задаете алгоритм, программное обеспечение выбирает оптимальный алгоритм для каждого разделения, используя известное количество классов и уровней категориального предиктора. Если предиктор имеет самое большее MaxNumCategories уровни, программное обеспечение разделяет категориальные предикторы, используя точный алгоритм поиска. В противном случае программное обеспечение выбирает эвристический алгоритм поиска на основе количества классов и уровней. Значение по умолчанию MaxNumCategories уровень равен 10. В зависимости от вашей платформы программное обеспечение не может выполнить точный поиск по категориальным предикторам с более чем 32 или 64 уровнями.
Доступные эвристические алгоритмы: тяните влево по чистоте, основанном на основных компонентах разбиении и один от всех по классам.
Тяните налево от чистоты
Тяга слева от алгоритма очистки начинается со всех L категориальных уровней на правой ветви. Затем алгоритм принимает следующие действия:
Просмотрите категории K, которые имеют наибольшие вероятности классов для каждого класса.
Переместите категорию с максимальным значением критерия разделения в левую ветвь.
Продолжайте перемещать категории справа налево, записывая критерий разделения при каждом перемещении, пока у правого дочернего элемента не останется только одна категория.
Из этой последовательности выбранное разделение является тем, которое максимизирует критерий разделения.
Выберите этот алгоритм путем определения 'AlgorithmForCategorical','PullLeft' в fitctree или templateTree.
Основанное на основных компонентах разбиение
Алгоритм разбиения на основные компоненты [2] находит близкое к оптимальному двоичное разбиение уровней предиктора L путем поиска разделяющей гиперплоскости. Гиперплоскость перпендикулярна первому главному компоненту взвешенной ковариационной матрицы центрированной матрицы вероятностей класса.
Алгоритм присваивает счет каждой из категорий L, вычисленную как скалярное произведение между найденным основным компонентом и вектором вероятностей классов для этой категории. Затем выбранное разделение является одним из L - 1 разделений, которое максимизирует критерий разделения.
Выберите этот алгоритм путем определения 'AlgorithmForCategorical','PCA' в fitctree или templateTree.
Один-Против-Все по классам
Алгоритм один от всех по классам начинается со всех L категориальных уровней в правой ветви. Для каждого из классов K алгоритм заказывает категории на основе их вероятности для этого класса.
Для первого класса алгоритм перемещает каждую категорию в левую ветвь по порядку, записывая критерий разделения при каждом перемещении. Затем алгоритм повторяет этот процесс для остальных классов. Из этой последовательности выбранное разделение является тем, которое максимизирует критерий разделения.
Выберите этот алгоритм путем определения 'AlgorithmForCategorical','OVAbyClass' в fitctree или templateTree.
Смотрите данные с многоуровневыми категориальными предикторами
В этом примере показано, как просмотреть набор данных, который включает категориальные предикторы со многими уровнями (категориями) и как обучить двоичное дерево решений для классификации.
Загрузка выборочных данных
Загрузите 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. The 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] Breiman, L., J. H. Friedman, R. A. Olshen, and C. J. Stone. Деревья классификации и регрессии. Бока Ратон, FL: Chapman & Hall, 1984.
[2] Coppersmith, D., S. J. Хонг и Дж. Р. М. Хоскинг. «Разбиение номинальных атрибутов на разделы в деревьях решений». Data Mining and Knowledge Discovery, Vol. 3, 1999, pp. 197-217.
См. также
fitcensemble | fitctree | fitrtree | templateTree