Теоретический обзор одного из простейших методов машинного обучения
Эта статья является продолжением серии статей, посвященных ключевым теоретическим концепциям машинного обучения. Помимо введения в ML, я написал статьи по классификации и регрессии, которые доступны на моей странице.
Вступление
Наиболее распространенные методы машинного обучения, такие как классические линейные регрессии, классификации, K-ближайшие соседи, используют метрическую функцию стоимости для оценки производительности. В качестве примера мы используем евклидово расстояние в алгоритме kNN, чтобы найти k ближайших точек данных к нашей невидимой точке и использовать классы этих наблюдаемых точек для присвоения значения.
Есть некоторые наборы данных или проблемные вопросы, которые не полностью соответствуют этому методу анализа. Классификация фруктов на основе их описания не выигрывает от вычисления евклидовых расстояний или расстояний l1 на любом этапе процесса, поэтому нам нужен альтернативный метод, который может решить эти конкретные проблемы.
Что мы можем заметить в задачах, которые не поддаются вычислению расстояний, так это то, что они могут извлечь выгоду из модели, которая направлена на их лучшую «категоризацию». По сути, модель, которая является менее математически сложной (на первый взгляд) и направлена на поиск общих точек данных путем разделения набора данных на все более и более все меньшие и меньшие группы на каждой итерации. Идея состоит в том, что, когда мы дойдем до конца нашей модели, у нас будет ряд групп, которые можно будет однозначно идентифицировать как принадлежащие к определенному классу.
По сути, это процесс дерева решений. Решение Деревья применяют последовательность решений или правил, которые часто зависят от одной переменной за раз. Эти деревья разделяют наш ввод на регионы, уточняя уровень детализации на каждой итерации / уровне, пока мы не дойдем до конца нашего дерева, также называемого листовым узлом, который обеспечивает окончательную предсказанную метку.
Компоненты дерева
Дерево решений состоит из следующих компонентов:
Узел - точка в дереве между двумя ветвями, в которой объявляется правило.
Корневой узел - первый узел в дереве
Ветви - стрелка, соединяющая один узел с другим, направление движения зависит от того, как точка данных соотносится с правилом в исходном узле
Узел листа - последний узел в дерево, точка, в которой метка назначается точке данных
Уровень - номер, присвоенный каждому набору узлов, начиная с 0, который обозначает, сколько уровней эти узлы находятся от корня
Коэффициент ветвления - коэффициент ветвления B на уровне l равен количеству ветвей, имеющихся у узлов на уровне l + 1.
Итак, как экземпляр проходит через дерево решений? Начнем с корневого узла. У этого узла будет какое-то объявление, например «Животное имеет более двух футов» или в математической нотации, передавая массив, в котором первое значение определяет количество футов указанного животного, мы получаем x [0] ›2. Мы оцениваем наш экземпляр относительно этой функции и решите, в какую ветку мы должны спуститься, чтобы перейти на следующий уровень. Важно отметить, что решения о ветвлении должны быть взаимоисключающими, а это означает, что не может быть никакой неопределенности относительно того, в каком направлении будет двигаться вход (он должен быть чисто объективным). Узел, на который мы переместились, теперь считается корневым узлом этого нового поддерева, и мы снова запускаем процесс. Это продолжается итеративно, пока мы не дойдем до листового узла и не назначим связанный класс нашему экземпляру.
Классификация деревьев считается чрезвычайно интерпретируемой и очень быстрой для выполнения, поскольку простые решения принимаются на каждом этапе, и нет необходимости обходить все дерево, чтобы найти правильный класс. Наши деревья также будут вычислять посредством обучения, какие переменные функции наиболее важны, поэтому нам может даже не потребоваться оценивать все переменные функции, чтобы принять решение по классу.
Бинарные деревья
Самый простой тип дерева - это бинарное дерево. Двоичное дерево содержит максимальный коэффициент ветвления 2 на каждом уровне. Таким образом, каждый родительский узел может иметь максимум 2 дочерних узла. В большинстве случаев это могут быть решения «да» / «нет».
Каждое дерево с коэффициентом ветвления больше двух может быть преобразовано в эквивалентное двоичное дерево. Иногда это полезная функция из-за простоты. В большинстве языков программирования вы можете указать, хотите ли вы ограничить любую модель дерева решений только структурой двоичного дерева.
Математика
Математика в деревьях решений происходит в процессе обучения. Сначала мы начинаем с набора данных D = {X, y}, из которого нам нужно найти древовидную структуру и правила принятия решений для каждого узла. Каждый узел разделит набор данных на два или более непересекающихся подмножества D_ (l, i) *, где l - номер слоя, а i обозначает каждое отдельное подмножество. Если все наши метки в этом подмножестве принадлежат к одному классу, подмножество называется чистым, и этот узел будет объявлен листовым узлом, и этот раздел дерева достиг завершения. Если это не так, критерии разделения будут продолжены.
В некоторых более сложных наборах данных для перехода к этапу, на котором каждый листовой узел является чистым, могут потребоваться чрезвычайно глубокие деревья решений, что приведет к переобучению набора данных. Из-за этого мы часто останавливаемся, прежде чем дойдем до чистых узлов, и вместо этого должны разработать более сложные стратегии завершения, в которых узлы могут быть нечистыми, но ошибка учитывается и измеряется.
Деревья называются монотетическими, если один атрибут учитывается в каждом узле, и политетическими в противном случае. Обычно мы предпочитаем более простые деревья, потому что их легче интерпретировать и выполнять. В большинстве языков программирования можно ограничить дерево решений для создания монотетических или политетических деревьев, но почти всегда рекомендуется сначала попробовать первое и усложнить его только в случае крайней необходимости. Чтобы создать эти деревья, мы минимизируем меру, которую мы называем нечистотой.
Меры по содержанию примесей
Энтропия примеси или информации примеси рассчитывается по следующей формуле
Эта формула, по сути, сообщает нам уровень предсказуемости в каждом узле нашего дерева. В конечном итоге мы хотим, чтобы наши заметки были предсказуемыми, и мы достигаем этого, гарантируя, что в узле присутствует большая часть определенного класса. Чтобы показать разницу между разными уровнями предсказуемости и подчеркнуть влияние этого на нашу меру примесей, я привел несколько примеров ниже.
Поскольку мы хотим, чтобы значение нашей информационной примеси было как можно ближе к 0, у нас возникает проблема минимизации. Наша модель будет проходить через каждую переменную и ее возможные значения, чтобы найти оператор (например, x [0] ›2 или x [3] = 1), который приведет к наименьшим значениям примеси для дочерних узлов.
Критерий остановки
Мы знаем, что не всегда можем ожидать, что наша прядь будет формировать идеально чистые листовые узлы, и из-за этого мы должны установить некоторую форму критерия остановки. Мы можем сделать это несколькими способами.
Для метода проверки набора мы объединяем наши обучающие данные в набор для обучения и набор для проверки. Типичное разделение составляет 66% -34% или 70% -30%, но это остается на усмотрение пользователя. Наша модель продолжит разделять наши подмножества, создавая больше ветвей и узлов на каждом уровне, и пока она это делает, она измеряет ошибку в наборе проверки. Пока ошибка на проверочном наборе продолжает падать, мы продолжаем разбивать наши подмножества. Когда ошибка перестает падать, мы останавливаем генерацию новых уровней в нашем дереве решений, и это наша окончательная модель.
Обрезка - это метод, используемый для упрощения обучения работе с деревом. Мы начинаем с запуска нашей модели дерева решений и обучения полного дерева без каких-либо критериев остановки. После этого мы измеряем примесь в каждом узле. Затем мы проходим через каждую пару листовых узлов и удаляем те, которые не стоят нам большого штрафа за чистоту, по сути удаляя набор ветвей из нашего дерева. Мы продолжаем делать это либо заранее определенное количество раз, либо столько раз, сколько наше наказание за нечистоту ниже определенного порога.
Деревья регрессии
Технически деревья решений можно использовать в регрессионном анализе. В этом случае конечные узлы становятся непрерывными значениями. Метка листового узла - это среднее значение точек данных, назначенных этому узлу.
Обычно деревья решений не используются в регрессии. Их структурированный характер, особенно то, как они принимают трудные решения на каждом этапе, гораздо больше поддаются классификации. Чаще всего другие модели, более применимые к регрессионному анализу, оказываются более эффективными, чем деревья решений.
Это ваше резюме деревьев решений. В следующих статьях я хочу более подробно остановиться на гораздо большем количестве концепций, так что следите за ними! На очереди нейронные сети. Если вас интересует какая-либо из моих предыдущих статей, подпишите и мою страницу. А пока.
* D_ (l, i) представляет собой индекс D (l, i)
