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

Сегодня я постараюсь объяснить простыми словами принципы работы 10 самых эффективных data mining-алгоритмов, которые описаны в этом докладе.

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

1. С4.5

Что он делает? Алгоритм C4.5 строит классификатор в форме дерева решений. Чтобы сделать это, ему нужно передать набор уже классифицированных данных.

Подождите, а что такое классификатор? Классификатор – это инструмент, применяемый в data mining, который использует классифицированные данные и на их основании пытается предсказать, к какому классу стоит отнести новые данные.

Как выглядит пример использования алгоритма? Предположим, что у нас есть набор данных – это данные о группе пациентов. Мы знаем различные параметры каждого пациента: возраст, пульс, кровяное давление, максимальное потребление кислорода, историю семьи и так далее. Эти параметры называются атрибутами.

Теперь:

На основании этих атрибутов мы хотим предсказать, может ли пациент заболеть раком. Пациент может попасть в один из 2 классов: будет болеть раком или не будет болеть раком. Алгоритму C4.5 сообщают класс каждого пациента.

Вот в чем суть:

Используя набор атрибутов пациента и соответствующий класс, C4.5 строит дерево решений, способное предсказать класс для новых пациентов на основании их атрибутов.

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

• у пациента в истории семьи есть заболевания раком;
• у пациента есть ген, который присутствует у пациентов, больных раком;
• у пациента опухоль;
• размер опухоли больше 5 см.

Таким образом:

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

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

Вот отличия C4.5 от других систем, использующих деревья решений:

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

Почему стоит использовать C4.5? Вероятно, самым большим достоинством деревьев решений является их простая интерпретация. Также они имеют довольно высокую скорость работы, а выходные данные легко понимаются человеком.

Где он используется? На OpenTox можно найти реализацию на Java, которая является инструментом для визуализации и анализа в методах data mining. Orange, набор open-source-инструментов для анализа и визуализации результатов дата майнинга, использует C4.5 в своем классификаторе дерева решений.
Классификаторы – отличная вещь, но вот вам еще один алгоритм, который имеет непосредственное отношение к кластеризации….

2. Метод к-средних

Что он делает? Метод к-средних создает к-групп из набора объектов таким образом, чтобы члены группы были наиболее однородными. Это популярная техника кластерного анализа для исследования набора данных.

Погодите-ка, что такое кластерный анализ? Кластерный анализ – это семейство алгоритмов, разработанных для формирования групп таким образом, чтобы члены группы были наиболее похожими друг на друга и не похожими на элементы, не выходящие в группу. Кластер и группа – это синонимы в мире кластерного анализа.

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

Смотрите:

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

Может возникнуть вопрос:

Как нам сгруппировать вместе пациентов по возрасту, пульсу, давлению с помощью этих векторов?
Хотите узнать хорошую новость?

Вы говорите методу к-средних, сколько кластеров вам нужно, а он сделает все остальное.

Как это происходит? Метод к-средних имеет множество вариантов работы для различных типов данных.

В общем случае все они делают примерно следующее:

1. Метод к-средних выбирает точки многомерного пространства, которые будут представлять к-кластеры. Эти точки называются центрами тяжести.
2. Каждый пациент будет располагаться наиболее близко к одной из точек. Надеемся, что не все они будут стремиться к одному центру тяжести, поэтому образуется несколько кластеров.
3. Теперь у нас есть к-кластеров, и каждый пациент – это член какого-то из них.
4. Метод к-средних, учитывая положение членов кластера, находит центр каждого из к-кластеров (именно здесь используются векторы пациентов!).
5. Вычисленный центр становится новым центром тяжести кластера.
6. Поскольку центр тяжести переместился, пациенты могли оказаться ближе к другим центрам тяжести. Другими словами, они могли сменить членство.
7. Шаги 2-6 повторяются до тех пор, пока центр тяжести не перестанут изменяться и членство не стабилизируется. Это называется сходимостью.

Требует ли этот метод обучения или он самообучающийся? Бывает по-разному. Но большинство расценивает метод к-средних как самообучающийся. Вместо того, чтобы уточнять количество кластеров, метод к-средних «изучает» кластеры самостоятельно, не требуя информации о том, к какому кластеру относятся данные наблюдения. Метод к-средних может быть полуобучаемым.

Почему стоит использовать метод к-средних? Не думаю, что многие возьмутся спорить:

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

Дальше – лучше:

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

Но не все так гладко:

Два основных недостатка метода к-средних заключаются в чувствительности к «выбросам» и начальному выбору центров тяжести. Также нужно помнить, что метод к-средних создан для работы с непрерывными значениями, поэтому придется проделать пару фокусов, чтобы заставить алгоритм работать с дискретными данными.

Где он используется? Огромное количество реализаций метода к-средних доступны онлайн:

• Apache Mahout
• Julia
• R
• SciPy
• Weka
• MATLAB
• SAS

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

3. Метод опорных векторов

Что он делает? Метод опорных векторов (SVM – Support vector machine) использует гиперплоскость, чтобы классифицировать данные по 2 классам. На верхнем уровне SVM выполняет те же операции, что и C4.5, но с одним отличием – SVM не использует деревья решений.

Стоп-стоп, гипер-что? Гиперплоскость – это функция, например, уравнение для линии y = mx + b. На самом деле, для простой классификационной задачи с 2 параметрами гиперплоскость может быть линией.

Как оказалось…

SVM позволяет спроецировать ваши данные в пространство большей размерности. Когда данные спроецированы…

…SVM определяет лучшую гиперплоскость, которая делит данные на 2 класса.

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

Вы видите:

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

Что представляют собой шары, стол и палочка? Шары представляют собой данные, а красный и синий цвета – два класса. Палка представляет собой самую простую гиперплоскость, то есть линию.

А как же самая крутая часть?

SVM самостоятельно определяет функцию гиперплоскости.

Что, если все гораздо сложнее? Верно, часто так и происходит. Если шары перемешаны друг с другом, то простая палка тут не поможет.

Вот что нужно сделать:

Быстро поднимите стол – шары взлетят в воздух. Пока шары находятся в воздухе и в правильных положениях, вы можете разделить красные и синие большим куском бумаги.

Вы можете подумать, что это жульничество:

Нет. Поднятие стола в воздух – это эквивалент отражению данных в пространство с более высокой размерностью. В этом случае мы переходим от плоской поверхности стола к трехмерному положению шаров в воздухе.

Как SVM это делает? Использование нуль-пространства (ядра) матрицы дает нам отличный инструмент для работы в пространствах более высокой размерности. Большой лист бумаги по-прежнему называется гиперплоскостью, но теперь это функция плоскости, а не линии. Как заметил Ювал Мерхав (Yuval Merhav) – раз мы перешли в третье измерение, то гиперплоскость должна стать плоскостью.

Я считаю, что эта визуализация неплохо помогает понять принцип работы SVM:



На Reddit есть 2 отличных треда по этой теме, на подфорумах ELI5 и ML.

Как шары на столе или в воздухе соотносятся с реальными данными? Шар на столе имеет местоположение, которое можно определить по координатам. Например, шар может отстоять на 20 см от левой грани стола и на 50 – от нижней. Другими словами, координаты (x,y) шара имеют значения (20,50) [правильнее было бы сказать: (50,20)]. Координаты x и y формируют двумерное измерение.

Вот что получается:

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

В результате:

SVM отображает эти параметры в высшее измерение, а затем находит гиперплоскость, чтобы разделить классы.

Термин «отступ» (margin) часто ассоциируется с SVM. Что это? Маржа гиперплоскости – это расстояние между гиперплоскостью и 2 ближайшими точками данных каждого класса. В примере с шарами и столом маржей называется расстояние между палкой и ближайшим красным и синим шариком.

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

Откуда SVM получил свое название? Гиперплоскость равноудалена от красного и синего шаров. Эти шары – точки данных, которые называются опорными векторами (support vectors), потому что они поддерживают гиперплоскость.

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

Почему именно SVM? SVM, наряду с C4.5 – это два метода, которые нужно попробовать в первую очередь. Но, согласно теореме No Free Lunch («бесплатных завтраков не бывает»), не существует универсального метода для решения задач классификации. Должен добавить, что слабыми сторонами этого метода являются необходимость выбора ядра и плохая интерпретируемость.

Где он используется? Есть множество реализаций SVM. Самые популярные – это scikit-learn, MATLAB и разумеется libsvm.

Следующий алгоритм – один из моих самых любимых…

4. Алгоритм Apriori

Что он делает? Алгоритм Apriori ищет ассоциативные правила и применяется по отношению к базам данных, содержащим огромное количество транзакций.

Что такое ассоциативные правила? Изучение ассоциативных правил – это техника, применяемая в data mining для изучения соотношений и отношений между переменными базы данных.

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



Хорошие новости:

Применяя алгоритм Apriori, мы можем определить товары, купленные вместе – то есть установить ассоциативные правила.

Что это дает нам:

Вы можете определить товары, которые часто покупают вместе. Основная задача маркетинга – заставить клиентов покупать больше. Связанные товары называются наборами.

Например:

Вы можете заметить, что чипсы, чипсы с соусом и газировка часто стоят на прилавках рядом. Это называется двухэлементным набором. Когда база данных достаточно большая, будет гораздо сложнее «увидеть» взаимосвязи, в особенности, когда вы имеете дело с трёхэлементными или более крупными наборами. Как раз для этого и создан алгоритм Apriori.

Как же работает алгоритм Apriori? Перед тем, как перейти к сути алгоритма, вам нужно определить 3 параметра:

1. Во-первых, нужно установить размер набора. Вы хотите определить двухэлементный, трёхэлементный набор или какой-нибудь еще?
2. Во-вторых, определить поддержку – это число транзакций, входящих в набор, разделенное на общее количество транзакций. Набор, который равен поддержке, является самым часто встречаемым набором.
3. В-третьих, определить достоверность, то есть условную вероятность определенного товара оказаться в корзине с другими товарами. Пример: чипсы в вашем наборе имеют 67%-ную вероятность оказаться в одной корзине с газировкой.

Простой алгоритм Apriori состоит из трех шагов:

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

Требует ли этот метод обучения или он самообучающийся? Apriori обычно рассматривается как самообучающийся алгоритм, поэтому его часто применяют для поиска интересных шаблонов и отношений.

Еще кое-что…

Существует модификация алгоритма Apriori, способная проводить классификацию маркированных данных

Почему именно Apriori? Он прост, понятен, легкореализуем и имеет множество модификаций.

С другой стороны…

В процессе работы алгоритм может быть довольно ресурсоемким; вычисления могут занять достаточно много времени.

Где он используется? Существует огромное количество реализаций Apriori. Одни из самых популярных – это ARtool, Weka и Orange.

Следующий алгоритм был самым сложным в понимании для меня, давайте взглянем на него…

5. EM-алгоритм

Что он делает? В data mining алгоритм максимизации ожидания (expectation-maximization (EM) обычно используется как кластерный алгоритм (наподобие алгоритма к-средних) для обнаружения знаний.

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

Давайте я объясню…

Я не статистик, поэтому надеюсь, что мое упрощение будет корректным и поможет вам во всем разобраться.

Вот несколько концепций, которые сделают все проще…

Что такое статистическая модель? Я вижу модель как что-то, описывающее известные данные. Например, оценки за экзамен могут соответствовать нормальному распределению, поэтому предположение, что оценки генерируются в соответствии с нормальным распределением, является моделью.

Секундочку, а что такое распределение? Распределение представляет вероятности появления всех измеримых результатов. Например, оценки за экзамен могут соответствовать нормальному распределению. Это нормальное распределение представляет все вероятности получения той или иной оценки.

Другими словами, распределение помогает понять, сколько человек, сдающих экзамен, получат ту или иную оценку.

Круто, а что такое параметры модели? Параметр описывает распределение, которое является частью модели. Например, нормальное распределение описывается средним арифметическим и дисперсией.

В примере с экзаменом распределение оценок (измеримые исходы) вписывается в нормальное распределение. Среднее арифметическое равняется 85, а дисперсия – 100.

Для того, чтобы описать нормальное распределение, вам нужны всего два параметра:

1. Среднее арифметическое
2. Дисперсия

А правдоподобие? Возвращаясь к примеру с нормальным распределением.… Предположим, что у нас есть множество оценок. Однако мы знаем не все, а только часть из них.

Вот в чем суть:

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

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

Вы вероятно думаете, что же такое вероятность?

Предположим, что мы знаем среднее арифметическое и дисперсию. Вероятность появления той или иной оценки соответствует нормальному распределению. Шанс, что мы пронаблюдаем определенные оценки с определенной частотой, называется вероятностью.

Если сказать простыми словами, то мы оцениваем возможные исходы на основании параметров.

Отлично! А в чем отличие между данными наблюдений и скрытыми данными? Данные наблюдений – это данные, которые вы пронаблюдали или зафиксировали. Скрытые данные – это отсутствующие данные. Есть множество причин, почему они могут отсутствовать (не зафиксированы, проигнорированы и так далее).

Вот в чем загвоздка:

В ходе дата майнинга и кластеризации важно оценивать класс точки данных, как отсутствующие данные. Мы не знаем, что это за класс, поэтому интерпретация недостающих данных очень важна в случае применения EM-алгоритма к задаче кластеризации.

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

А теперь хорошие новости:

Оценивая максимальное правдоподобие, EM-алгоритм создает отличную модель, которая назначает метки класса точкам данных – прямо как в кластеризации.

Как EM помогает в кластеризации? EM-алгоритм начинает с того, что пытается сделать вывод на основании параметров модели.

Затем следует итерационный трехшаговый процесс:

1. E-шаг: На этом шаге на основании параметров модели вычисляются вероятность принадлежности каждой точки данных к кластеру.
2. М-шаг: Обновляет параметры модели в соответствии с кластерным распределением, проведенным на шаге E.
3. Предыдущие два шага повторяются до тех пор, пока параметры модели и кластерное распределение не уравняются.

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

Почему именно EM? Главным достоинством EM-алгоритма является простота исполнения. Вдобавок ко всему, он может оптимизировать не только параметры модели, но и делать предположения относительно значений отсутствующих данных.

Это делает EM отличным методом для кластеризации и создания моделей с параметрами. Зная кластеры и параметры модели можно предполагать, что содержит кластер и куда стоит отнести новые данные.

Хотя и у EM-алгоритма есть свои недостатки:

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

Где он используется? EM-алгоритм реализован в Weka. R имеет реализацию в пакете mclust. В scikit-learn есть реализация EM в модуле gmm.

Какой метод data mining использует Google? Давайте взглянем.

6. PageRank

Что он делает? PageRank – это алгоритм ссылочного ранжирования, разработанный для определения относительной важности объекта, связанного с сетью объектов.

Что-что? Ссылочное ранжирование? Это тип сетевого анализа, определяющий ассоциации (читай, связи) между объектами.

Вот пример: Наиболее известный пример PageRank – это поисковая система Google. Хотя их поисковик не полностью полагается на PageRank, все же это один из методов, который использует Google, чтобы определить важность веб-страницы.

Позвольте мне объяснить:

Веб-страницы в интернете связаны друг с другом. Если rayli.net дает ссылку на CNN, то CNN получает очко в копилку, так как rayli.net посчитал сайт CNN релевантным.

Но это еще не все…

Вес балла от rayli.net оценивается важностью и релевантностью самого сайта.
Другими словами, любая веб-страница, дающая ссылку на rayli.net, повышает его релевантность.

Резюме?

Эта концепция голосов и релевантности представляет собой PageRank. Голос rayli.net за CNN увеличивает PageRank CNN, и величина, на которую он увеличится, зависит от влияния и значимости rayli.net.

Что означают PageRank равные 0,1,2,3 и так далее? Хотя точное значение числа PageRank компания Google не раскрывает, мы можем получить об этом представление.

И вот как:



Видите?

Все это выглядит как соревнование по популярности. Мы все имеем представление о том, какие сайты релевантные и популярные. PageRank просто переводит наше представление в цифры.

Как еще применяется PageRank? PageRank был специально разработан для всемирной сети.

Только подумайте:

По своему содержанию PageRank – это просто суперэффективный способ проведения ссылочного ранжирования. Однако соединяемые объекты необязательно должны быть веб-страницами.

Вот 3 инновационных применения PageRank:

1. Доктор Стефано Аллесина (Stefano Allesina) из Чикагского университета применил PageRank в сфере экологии, чтобы определить, какие из особей являются жизненно важными для поддержания экосистемы.
2. Twitter разработал WTF (Who-to-Follow) – персонализированный вариант рекомендательного движка, основанного на PageRank, показывающий список людей, на которых стоит подписаться.
3. Бин Жэнь (Bin Jiang) из Гонконгского политехнического университета использовал вариант PageRank для предсказания перемещения людей на основании топологических метрик в Лондоне.

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

Почему именно PageRank? Главным достоинством PageRank является надежность, несмотря на сложность получения релевантной входящей ссылки.

Простое замечание:

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

Где он используется? Торговая марка PageRank принадлежит компании Google. Однако алгоритм PageRank запатентован Стэндфордским университетом.

Если у вас возник вопрос по поводу того, можете ли вы использовать PageRank:
Я не адвокат, так что лучше посоветоваться со знающими людьми, но, вероятно, вы можете использовать алгоритм сколько вам угодно, пока он не начнет приносить вам финансовую выгоду.

Вот 3 примера реализации PageRank:

• Реализация C++ OpenSource PageRank.
• Реализация Python PageRank.
• Пакет сетевого анализа igraph в R.

Далее перейдем к…

7. AdaBoost

Что он делает? AdaBoost – это алгоритм усиления классификаторов.

Как вы помните, классификатор пытается предсказать по уже известным ему данным, к какому классу будут относиться новые данные.

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

В чем разница между сильным и слабым классификатором? Слабый классификатор производит классификацию с точностью чуть выше шанса. Популярный пример слабого классификатора – это так называемый «решающий пень» – одноуровневое дерево решений.

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

Какие есть примеры AdaBoost? Давайте начнем с трех слабых классификаторов. Мы обучим их за 10 итераций на тренировочном наборе данных о пациентах. Набор данных содержит детали медицинских записей пациента.

Вопрос в том…

Как нам предсказать, заболеет ли человек раком?

Вот как AdaBoost отвечает на этот вопрос:

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

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

Раунд 2: AdaBoost повторно пытается выявить лучший классификатор.
И здесь возникает загвоздка:

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

Почему?

Это – словно переходить на следующий уровень в видеоигре и не начинать все заново, если персонаж погибает. Вместо этого вы начинаете с уровня 2, и всеми силами стараетесь перейти на третий уровень.

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

Лучший классификатор снова взвешен и включен в ансамбль – неверно классифицированные пациенты также взвешены и получают больший шанс быть выбранными повторно.

После 10 раундов: Мы получаем ансамбль взвешенных классификаторов, натренированных и перетренированных на неправильно классифицированных данных из предыдущих итераций.

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

Почему именно AdaBoost? AdaBoost – это просто. Алгоритм относительно легок в программировании.

Кроме того он очень быстрый! Слабые классификаторы обычно проще, чем сильные. Простота означает высокую скорость исполнения.

Еще кое-что…

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

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

Где он используется? AdaBoost имеет тонну вариаций и реализаций. Вот некоторые из них:

• scikit-learn
• ICSIBoost
• Обобщенная усиленная регрессионная модель gbm (Generalized Boosted Regression Models)

Если вам нравится шоу мистера Роджерса, то вам понравится следующий алгоритм…

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

Что он делает? kNN (k-Nearest Neighbors) – это алгоритм классификации, однако он отличается от предыдущих, описанных в этой статье, потому что это – ленивый классификатор.

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

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

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

Вот почему:

• C4.5 строит дерево решений в процессе обучения;
• SVM строит гиперплоскость;
• AdaBoost строит ансамблевую классификацию.

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

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

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

Возможно, вы думаете…

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

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

• Использование расстояния Хэмминга как метрики для определения «близости» двух текстовых строк;
• Преобразование дискретных данных в бинарные числа.

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

• kNN классификация категорийных данных
• Использование kNN в R с категорийными величинами

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

Я готов поспорить, что вы догадываетесь, в каком случае все становится чуть-чуть сложнее.

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

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

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

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

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

Но это только часть истории…

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

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

Где он используется? Существуют несколько реализаций:

• MATLAB kNN классификация
• scikit-learn KNeighborsClassifier
• kNN классификация в R

Спам? Забудьте о нем! В этом поможет наш следующий алгоритм…

9. Наивный байесовский классификатор

Что он делает? Наивный байесовский классификатор – это семейство алгоритмов классификации, которые принимают одно допущение:
Каждый параметр классифицируемых данных рассматривается независимо от других параметров класса.

Что означает слово «независимо»? 2 параметра называются независимыми, когда значение одного параметра не оказывает влияния на второй.

Например:

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

Но давайте посмотрим дальше, все ли параметры независимы?

К сожалению, ответ – нет. Есть 3 соотношения, которые зависимы:

• если рост увеличился, вероятно, увеличился вес;
• если увеличился уровень холестерина, вероятно, увеличился вес;
• если увеличился уровень холестерина, вероятно, увеличился пульс.

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

Это подводит нас к другому вопросу…

Почему метод называется наивным? Предположение, что все параметры набора данных независимы – это довольно наивное предположение. Обычно так не бывает.

Кто такой Байес? Томас Байес был английским математиком-статистиком, в честь которого была названа теорема Байеса.

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

Упрощенное уравнение для классификации выглядит так:



Давайте взглянем на него поподробнее.

Что означает это уравнение? Уравнение находит вероятность класса А, на основании параметров 1 и 2. Другими словами, если вы видите параметры 1 и 2, то, вероятно, это данные класса А.

Уравнение читается следующим образом: Вероятность [выявления] класса А на основании параметров 1 и 2 – это дробь.

1. Числитель дроби – это вероятность параметра 1, принадлежащего классу А, умноженная на вероятность параметра 2, принадлежащего классу А, умноженная на вероятность класса А.
2. Знаменатель – это вероятность параметра 1 умноженная на вероятность параметра 2.

Есть какой-нибудь пример реализации наивного байесовского классификатора? Ниже представлен отличный пример, взятый из треда Stack Overflow.

Вот условия:

1. У нас есть тренировочный набор данных о 1000 фруктах.
2. Фрукт может быть бананом, апельсином или каким-нибудь другим (это классы).
3. Фрукт может быть длинным, сладким или желтым (это параметры).

Что мы видим в этом тренировочном наборе данных?

• Из 500 бананов 400 длинные, 350 сладкие и 450 желтые;
• Среди 300 апельсинов нет ни одного длинного, но оказалось 150 сладких и 300 желтых.
• Из оставшихся 200 фруктов 100 оказались длинными, 150 сладкими и 50 желтыми.

Если мы получим только параметры – длину, сладость и цвет фрукта (не зная его класса), то сможем вычислить вероятность того, что фрукт окажется бананом, апельсином или чем-то другим.

Предположим, что неизвестный фрукт длинный, сладкий и желтый.

Для вычисления вероятности нужно проделать 4 простых шага:

Шаг 1: Чтобы вычислить вероятность того, что неизвестный фрукт – это банан, давайте сначала решим, похож ли этот фрукт на банан. Вот как вычисляется вероятность класса «Банан» на основании параметров «длинный», «сладкий», «желтый»:

P(Banana|Long, Sweet, Yellow)

Выглядит точно так же как уравнение, описанное выше.

Шаг 2: Начнем с числителя и подставим все значения в уравнение:

• P(Long|Banana) = 400/500 = 0.8
• P(Sweet|Banana) = 350/500 = 0.7
• P(Yellow|Banana) = 450/500 = 0.9
• P(Banana) = 500/1000 = 0.5

Перемножив значения (согласно уравнению), мы получим:

0.8 x 0.7 x 0.9 x 0.5 = 0.252

Шаг 3: Проигнорируем знаменатель, поскольку он будет одинаковым для всех последующих вычислений.

Шаг 4: Проделаем те же вычисления для других классов:

• P(Orange|Long, Sweet, Yellow) = 0
• P(Other|Long, Sweet, Yellow) = 0.01875

Поскольку 0,252 больше, чем 0,01875, то наивный байесовский алгоритм классифицирует этот длинный, сладкий и желтый фрукт как банан.

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

Почему стоит использовать наивный байесовский классификатор? Как вы можете заметить в примере выше, алгоритм состоит из простой арифметики. Это простые вычисления: умножение и деление.

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

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

Где он используется? Реализации алгоритма могут быть найдены в Orange, scikit-learn, Weka и R.

И наконец, давайте посмотрим на 10 алгоритм…

10. Алгоритм CART

Что он делает? CART (classification and regression trees) – это аббревиатура, обозначающая методы классификации и регрессии с использованием дерева решений. Это методика обучения, основанная на деревьях решений, которая возвращает классификационные или регрессионные деревья. Как было в случае с C4.5, CART – это классификатор.

Дерево классификации выглядит так же как дерево решений? Дерево классификаций – это подвид дерева решений. Результатом работы дерева классификаций является класс.

Например, снова возьмем набор данных о пациенте. Вы можете попытаться предсказать, будет ли у пациента рак. Здесь возможно использование двух классов: «заболеет раком» и «не заболеет раком».

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

Довольно просто запомнить …

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

Как CART соотносится с C4.5?

C4.5	Cart
Использует приток информации к сегменту данных в процессе создания дерева решений	Здесь используется неопределенность Джини (не путать с коэффициентом Джини). На Stack Overflow можно почитать о различиях между ними.
Использует однопроходной метод прореживания, чтобы уменьшить переобучение.	Использует механизм отсечения дерева при прореживании. Начиная с низа дерева, CART оценивает ошибку классификации в узле и вне узла. Если погрешность превышает граничную, то ветка отбрасывается
Узлы дерева решений могут иметь две или более ветвей	Узлы решения имеют две ветки
На основе вероятностей распределяет отсутствующие значения между «детьми»	Использует суррогатные переменные, чтобы передать отсутствующие данные «детям»

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

Почему именно CART? Причины, по которым вы бы использовали C4.5, применимы и к CART, поскольку оба метода – это техники обучения на основании дерева решений. Также к достоинствам CART можно отнести легкую интерпретируемость.

Как и C4.5, CART довольно быстрый, пользуется популярностью и обладает удобно читаемым выводом.

Где он используется? Реализации CART встречаются в scikit-learn. R использует CART в своем пакете работы с деревьями. CART есть в Weka и MATLAB.

Наконец, Salford Systems имеют единственную запатентованную реализацию CART, код которой основан на теории, представленной общеизвестными статистиками из Стэндфордского университета и Калифорнийского университета в Беркли.