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

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

Смысл метрических методов очень хорошо раскрывает фраза «Скажи мне, кто твой друг, и я скажу, кто ты». Алгоритмы этого класса почти не имеют фазы обучения. Вместо этого они просто запоминают всю обучающую выборку, а на этапе предсказания просто ищут похожие на целевой объекты. Такой процесс называют lazy learning , потому что никакого обучения, по сути, не происходит. Также метрические модели являются непараметрическими, потому что они не делают явных допущений о глобальных законах, которым подчиняются данные. Так, линейная регрессия основывается на предположении о том, что изучаемая закономерность линейная (с неизвестными коэффициентами, которые восстанавливаются по выборке), а линейная бинарная классификация – что существует гиперплоскость, неплохо разделяющая классы. Метрические методы по сути своей локальны: они исходят из допущения, что свойства объекта можно узнать, имея представление о его соседях.

Указанные выше свойства могут быть полезными, особенно в случае сложно устроенных данных, для которых мы не можем придумать глобальную модель, однако, с другой стороны, из-за lazy learning алгоритм становится абсолютно неприменимым при большом количестве данных. Несмотря на то, что эти алгоритмы очень просты для понимания, они являются довольно точными и хорошо интерпретируемыми и часто используются как минимум в качестве бейзлайнов в разных задачах.

Обзору одного из самых известных метрических алгоритмов — методу k-ближайших соседей , или k-nearest neighbors (KNN) , будет посвящена первая часть главы. Этот подход в основном чисто инженерный из-за отсутствия фазы обучения и в настоящее время уже почти нигде не применяется, однако многие техники, на которых основан алгоритм, используются и в других методах. Например, алгоритмы поиска ближайших соседей, являющиеся неотъемлемой частью метода, имеют намного более широкую область применения. Плюс ко всему KNN — очень простой и легко интерпретируемый алгоритм, поэтому изучить его всё равно полезно. Мы обсудим подробнее его преимущества, недостатки, область его применения, а также возможные обобщения.

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

Метод ближайших соседей пример.

Сводная таблица для метрических методов классификации

Метрические алгоритмы классификации

Метрические алгоритмы классификации - алгоритмы, основанные на вычислении оценок сходства между объектами на основе весовых функций.

Один из наиболее простых метрических алгоритмов классификации. Работает следующим образом: дан классифицируемый объект и обучающая выборка . Требуется определить класс объекта на основе данных из обучающей выборки. Для этого:

сортируется по возрастанию расстояния от объекта z до каждого объекта выборки.
1. Проверяются классы k ближайших соседей объекта z . Класс, встречаемый наиболее часто среди k соседей, присваивается объекту z .

Исходными данными для алгоритма являются: классифицируемый объект, обучающая выборка и параметр k - число рассматриваемых ближайших соседей. Результатом работы метода является класс классифицируемого объекта.

При k = 1 алгоритм превращается в частный случай 1NN . В таком слачае, рассматриваемый объект z присваивается к классу его первого ближайшего соседа. В свою очередь, остальные объекты не рассматриваются.

Пример работы 1NN при использовании в качестве обучающей выборки Ирисы Фишера:

Для проверки оптимальности k используется Критерий Скользящего Контроля LOO (Leave One Out). Данный критерий проверяет оптимальность значения k следующим образом:

1. Из обучающей выборки удаляется i -й объект .
2. Запоминаем "старый" класс i -го объекта.
3. Запускаем алгоритм для оставшейся выборки. В результате работы i -му элементу присваивается "новый" класс на основе имеющейся выборки. Если значения "нового" и "старого" класса совпали, то i -ый элемент классифицировало верно. При их же несовпадении сумма ошибки увеличивается на 1.
4. Шаги 1-3 повторяются для каждого объекта выборки при фиксированном k . По окончании работы алгоритма полученная сумма ошибки sum делится на размер выборки l : . Потом значение k меняется, и алгоритм повторяется для нового значения. k с наименьшим значением суммы ошибки будет оптимальным.

Реализация kNN

При реализации алгоритма, в качестве обучающей выборки использовалась выборка ирисов Фишера. В качестве признаков объектов использовались значения длины и ширины лепестка. Значение k подбиралось по LOO .

Алгоритм:

kNN classes counts

где xl - обучающая выборка.

Пример работы метода kNN при k = 10 даёт следующий результат.

Применив критерий LOO для получения оптимального k мы получаем следующий ответ:

Достоинства алгоритма:

1. Простота реализации (относительно)
2. Хорошее качество, при правильно подобранной метрике и параметре k

Недостатки алгоритма:

1. Необходимость хранить выборку целиком, как следствие - неэффективное использование памяти
2. Малый набор параметров
3. Качество классификации сильно зависит от выбранной метрики
4. "Выбросы" могут значительно ухудшить точность

Метод kwNN отличается от kNN тем, что вес ближайших соседей зависит не от ранга соседа, а от расстояния до объекта z. В методе kNN считается, что вес каждого k -соседа равен 1. По сути, мы считали частоту появления классов среди ближайших k соседей. Применяя же метод kwNN в качестве весовой функции мы используем w =, что соответствует методуэкспоненциально взвешенных ближайших соседей. Предполагается, чтопринадлежит и рассматриваем с шагом 0.1.

Реализация kwNN

Алгоритм:

kwNN # размерность выборки по столбцам classes # берём k ближайших соседей classes == i) classes = classes + q^j # суммируем веса для всех объектов одного класса } } class

Для выборки Ирисы Фишера получаем следующий результат:

В результате работы мы получили, что наиболее оптимальными явлеются значения k = 6 .

Метод ближайших соседей достоинства и недостатки. K-Ближайшие соседи и их оптимизация

Есть известная поговорка:

«Ты - тот, кем ты себя окружаешь»

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

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

Глубина дерева решений. Дерево решений

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

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

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

В этом случае можно сказать, что решается задача бинарной классификации (целевой класс имеет два значения: "Выдать кредит" и "Отказать") по признакам "Возраст", "Наличие дома", "Доход" и "Образование".

Дерево решений как алгоритм машинного обучения – по сути то же самое: объединение логических правил вида "Значение признакаменьшеИ Значение признакаменьше… => Класс 1" в структуру данных "Дерево". Огромное преимущество деревьев решений в том, что они легко интерпретируемы, понятны человеку. Например, по схеме на рисунке выше можно объяснить заемщику, почему ему было отказано в кредите. Скажем, потому, что у него нет дома и доход меньше 5000. Как мы увидим дальше, многие другие, хоть и более точные, модели не обладают этим свойством и могут рассматриваться скорее как "черный ящик", в который загрузили данные и получили ответ. В связи с этой "понятностью" деревьев решений и их сходством с моделью принятия решений человеком (можно легко объяснять боссу свою модель), деревья решений получили огромную популярность, а один из представителей этой группы методов классификации, С4.5, рассматривается первым в списке 10 лучших алгоритмов интеллектуального анализа данных ("Top 10 algorithms in data mining", Knowledge and Information Systems, 2008. PDF ).

Ансамбль деревьев решений. Random Forest

В предыдущем разделе мы сделали предположение, что базовые алгоритмы некоррелированы, и за счёт этого получили очень сильное уменьшение дисперсии у ансамбля относительно входящих в него базовых алгоритмов. Однако в реальной жизни добиться этого сложно: ведь базовые алгоритмы учили одну и ту же зависимость на пересекающихся выборках. Поэтому будет странно, если корреляция на самом деле нулевая. Но на практике оказывается, что строгое выполнение этого предположения не обязательно . Достаточно, чтобы алгоритмы были в некоторой степени не похожи друг на друга. На этом строится развитие идеи бэггинга для решающих деревьев — случайный лес.

Построим ансамбль алгоритмов, где базовый алгоритм — это решающее дерево. Будем строить по следующей схеме:

1. Для построения $i$-го дерева: а. Сначала, как в обычном бэггинге, из обучающей выборки $X$ выбирается с возвращением случайная подвыборка $X^i$ того же размера. б. Затем случайно выбираются $n
2. Чтобы получить предсказание ансамбля на тестовом объекте, усредняем отдельные ответы деревьев (для регрессии) или берём самый популярный класс (для классификации).
3. Profit. Мы построили Random Forest (случайный лес) – комбинацию бэггинга и метода случайных подпространств над решающими деревьями.

Построение леса:

Применение леса:

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

Какая должна быть глубина деревьев в случайном лесе?

Ошибка модели (на которую мы можем повлиять) состоит из смещения и разброса. Разброс мы уменьшаем с помощью процедуры бэггинга. На смещение бэггинг не влияет, а хочется, чтобы у леса оно было небольшим. Поэтому смещение должно быть небольшим у самих деревьев, из которых строится ансамбль. У неглубоких деревьев малое число параметров, то есть дерево способно запомнить только верхнеуровневые статистики обучающей подвыборки. Они во всех подвыборках будут похожи, но будут не очень подробно описывать целевую зависимость. Поэтому при изменении обучающей подвыборки предсказание на тестовом объекте будет стабильным, но не точным (низкая дисперсия, высокое смещение). Наоборот, у глубоких деревьев нет проблем запомнить подвыборку подробно. Поэтому предсказание на тестовом объекте будет сильнее меняться в зависимости от обучающей подвыборки, зато в среднем будет близко к истине (высокая дисперсия, низкое смещение). Вывод: используем глубокие деревья.

Метод дерево решений. Дерево решений и задача, требующая многошагового принятия решений

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

Например, может существовать неопределенность как в отношении объема продаж, так и величины затрат. Более того, значение некоторых переменных может зависеть от значения других переменных: например, если будет продано 100,000 единиц продукта, себестоимость единицы продукта составит $4, но если будет продано 120,000 единиц, себестоимость единицы снизится до $3.80. Таким образом, возможны различные исходы ситуации, при этом некоторые из них будут зависеть от предыдущих исходов. Дерево решений представляет собой полезный метод разделения сложной задачи на более мелкие и более управляемые подзадачи.

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

Метод k-ближайших соседей алгоритм. Алгоритм k-ближайших соседей

Алгоритм k-ближайших соседей продолжает серию статей о.

kNN ( k-Nearest Neighbors ) – это алгоритм классификации, однако это – ленивый классификатор.

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

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

Какими классификаторами являются C4.5, SVM и AdaBoost? В отличие от kNN, они все – активные классификаторы.

Вот почему:

Что делает kNN? kNN не строит никакую классификационную модель. Вместо этого он просто сохраняет размеченные тренировочные данные.

Когда появляется новые неразмеченные данные, kNN проходит по 2 базовым шагам:

Сначала он ищет k ближайших размеченных точек данных – другими словами, k ближайших соседей.

Затем, используя классы соседей, kNN решает, как лучше классифицировать новые данные.

Как kNN понимает, какие точки находятся ближе всего? Для непрерывных данных kNN использует дистанционную метрику, например, Евклидову дистанцию (метрику). Выбор метрики зависит от типа данных. Некоторые советуют даже выбирать дистанционную метрику на основании тренировочных данных. Есть очень много, описанных во многих работах по дистанционным метрикам kNN.

При работе с дискретными данными, они сначала преобразуются в непрерывные. Вот 2 примера:

2 треда со Stack Overflow предлагают еще несколько решений:

Как kNN классифицирует новые данные, если соседи «не согласны»? kNN легко решает, к какому классу отнести данные, если все соседи принадлежат одному классу. Логика проста – если все соседи «согласны», то новые данные отводятся в их класс.

Как kNN решает, к какому классу отнести данные, если соседи не принадлежат одному классу?

Для решения этой проблемы используются 2 классические техники:

1. Принять за правильное решение простое большинство. К какому классу относится наиболее количество соседей, туда и определяют точку данных.

2. Проделать то же самое, но дать ближайшим соседям больший вес. Самый простой способ сделать это – использовать квантиль расстояния. Если сосед отстоит на 5 единиц, то его вес будет 1/5. При увеличении дистанции вес становится все меньше и меньше. Это как раз то, что нам нужно.

Требует ли этот метод обучения или он самообучающийся? Этот метод требует обучения, поскольку kNN необходим размеченный набор данных.

Почему именно kNN? kNN легок в понимании и легко реализуем – это две главные причины. В зависимости от выбора дистанционной метрики, kNN может показывать достаточно точные результаты.

Вот 5 вещей, за которыми нужно следить:

1. kNN может быть очень ресурсозатратным, если пытаться определить ближайших соседей на большом наборе данных.2. Зашумленные данные могут испортить kNN-классификацию.3. Нужно учитывать количество значений. Характеристики с большим количеством значений могут оказывать влияние на дистанционную метрику, по отношению к характеристикам с меньшим количеством значений.4. Поскольку обработка данных «откладывается», kNN обычно требует больше места, чем активные классификаторы.5. Выбор правильной дистанционной метрики очень важен для точности kNN.

Деревья решений. Как растут деревья решений: базовые основы

Начнем с определения: дерево решений – это математическая модель в виде графа, которая отображает точки принятия решений, предшествующие им события и последствия. Этот метод Data Mining широко используется в машинном обучении, позволяя решать задачи классификации и регрессии .

Аналитические модели в виде деревьев решений более вербализуемы, интерпретируемы и понятны человеку, чем другие методы Machine Learning , например, нейронные сети. Дополнительное достоинство Decision Tree – это быстрота за счет отсутствия этапа подготовки данных ( Data Preparation ), поскольку не нужно очищать и нормализовать датасет .

В бизнес-анализе , менеджменте и экономике Decision Tree – это отличный инструмент для наглядного отображения всех возможных альтернатив (сценариев), прогнозирования будущих событий, а также оценки их потенциальной выгоды и рисков. Для этого дерево решений представляют в виде графической схемы, чтобы его проще воспринимать и анализировать. Данный граф состоит из следующих элементов :

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

Пример дерева решений

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

Дерево решений пример. Деревья решений ¶

Деревья решений (DT) — это непараметрический контролируемый метод обучения, используемый дляи. Цель состоит в том, чтобы создать модель, которая предсказывает значение целевой переменной, изучая простые правила принятия решений, выведенные из характеристик данных. Дерево можно рассматривать как кусочно-постоянное приближение.

Например, в приведенном ниже примере деревья решений обучаются на основе данных, чтобы аппроксимировать синусоидальную кривую с набором правил принятия решений «если-то-еще». Чем глубже дерево, тем сложнее правила принятия решений и тем лучше модель.

Некоторые преимущества деревьев решений:

• Просто понять и интерпретировать. Деревья можно визуализировать.
• Требуется небольшая подготовка данных. Другие методы часто требуют нормализации данных, создания фиктивных переменных и удаления пустых значений. Однако обратите внимание, что этот модуль не поддерживает отсутствующие значения.
• Стоимость использования дерева (т. Е. Прогнозирования данных) является логарифмической по количеству точек данных, используемых для обучения дерева.
• Может обрабатывать как числовые, так и категориальные данные. Однако реализация scikit-learn пока не поддерживает категориальные переменные. Другие методы обычно специализируются на анализе наборов данных, содержащих только один тип переменных. См.для получения дополнительной информации.
• Способен обрабатывать проблемы с несколькими выходами.
• Использует модель белого ящика. Если данная ситуация наблюдаема в модели, объяснение условия легко объяснить с помощью булевой логики. Напротив, в модели черного ящика (например, в искусственной нейронной сети) результаты могут быть труднее интерпретировать.
• Возможна проверка модели с помощью статистических тестов. Это позволяет учитывать надежность модели.
• Работает хорошо, даже если его предположения несколько нарушаются истинной моделью, на основе которой были сгенерированы данные.