Data Mining: что внутри
Уровни информации
Я не думаю, что открою Америку, если скажу, что не вся информация одинаково полезна. Иногда для объяснения какого-то понятия необходимо написать много текста, а иногда для объяснения сложнейших вопросов достаточно посмотреть на простую диаграмму. Для сокращения избыточности информации были придуманы математические формулы, чертежи, условные обозначения, программный код и т.д. Кроме того, важным является не только сама информация, но и ее представление. Понятно, что котировки акций более наглядно можно продемонстрировать с помощью графика, а математические формулы опишут законы Ньютона в более компактном виде.
В процессе развития информационных технологий, а также систем сбора и хранения данных — баз данных (databases), хранилищ данных (data warehousing), и с недавних пор, облачных репозиториев, возникла проблема анализа больших объемов данных, когда аналитик или управленец не в состоянии вручную обработать большие массивы данных и принять решение. Понятно, что аналитику необходимо каким-то образом представить исходную информацию в более компактном виде, с которой может справится человеческий мозг за приемлемое время.
Между уровнями нет четких граней, но такая классификация позволит нам в дальнейшем не запутаться с терминологией.
Data Mining
Осмелюсь ввести еще один термин для первого пункта — Data Extracting, который буду использовать в дальнейшем.
Information retrieval
Information retrieval используется для получения структурированных данных или репрезентативной выборки меньшего размера. По нашей классификации information retrieval оперирует данными первого уровня, а в результате выдает информацию второго уровня.
Самым простым примером information retrieval является поисковая система, которая на основании неких алгоритмов выводит часть информации из полного набора документов. Кроме того, любая система, которая работает с тестовыми данными, метаинформаций или базами данных тем или иным способом использует инструменты information retrieval. Инструментами могут выступать методы индексации, фильтрации, сортировки данных, парсеры и т.д.
Text Mining
Другие названия: text data mining, text analysis, очень близкое понятие – concern mining.
Text mining может работать как с сырыми данными, так и с частично обработанными, но в отличие от information retrieval, text mining анализирует текстовую информацию с помощью математических методов, что позволяет получать результат с элементами знания.
Задачи, которые решает text mining: нахождение шаблонов данных, получение структурированной информации, построение иерархий объектов, классификация и кластеризация данных, определение тематики или области знаний, автоматическое реферирование документов, задачи автоматической фильтрации контента, определение семантических связей и другие.
Для решения задач text mining используют статистические методы, методы интерполяции, аппроксимации и экстраполяции, нечеткие методы, методы контент-анализа.
Web Mining
Ну и наконец мы добрались к web mining – наборе подходов и техник для извлечения данных из веб-ресурсов.
Так как веб-источники, ка правило, не являются текстовыми данными, то и подходы к процессу извлечения данных отличаются в этом случае. В первую очередь необходимо помнить, что информация в вебе хранится в виде специального языка разметки HTML (хотя есть и другие форматы – RSS, Atom, SOAP, но об этом поговорим позже), веб-страницы могут иметь дополнительную метаинформацию, а также информацию о структуре (семантике) документа, каждый веб-документ находится внутри некого домена и к нему могут применяться правила поисковой оптимизации (SEO).
Это первая статья из цикла, посвященного data mining / extracting / web mining. Пожелания и аргументированная критика принимаются.
Применение Data mining в продажах
Выберите показатели клиентов для анализа
Очевидно, что компания, задумавшаяся об автоматизации подобной аналитики, должна иметь хорошую информационную систему (ИС), в которой будет храниться множество данных по клиентам, например, сколько сотрудников в компании, какой вид деятельности, есть ли бухгалтерия, юристы и т.п. В целом ИС может хранить десятки, сотни таких показателей, но для конкретного анализа может оказаться достаточным 15-20 показателей.
Выберите показатели, которые присутствуют одновременно у обслуживаемых и потенциальных клиентов.
Выбранные показатели должны быть актуальны, т.е. должна быть возможность регулярно обновлять данные по этим показателям. Если вы не можете собрать информацию по какому-то показателю, не используйте его в анализе. Перед началом анализа соберите актуальную информацию, даже если этот этап займет 1-2 месяца, это того стоит.
Выберите целевые показатели обслуживаемых клиентов
Определите несколько целевых показателей обслуживаемых клиентов, которые будут однозначно определять, привлекателен для вас клиент или нет, например, период обслуживания клиента, доходность клиента, обслуживаемые продукты и т.п. Очевидно, что эти показатели будут характерны только для обслуживаемых клиентов. Таких показателей может быть немного (2-3), главное чтобы этот показатель характеризовал нужный сегмент в зависимости от ваших целей, например, привлекательный клиент для бизнеса с точки зрения долгосрочной прибыльности.
Произведите группировку значений показателей
В ИС значения выбранных показателей могут храниться в виде числовых данных или набора различных полей. Для анализа оптимальнее объединить эти значения в группы, например, количество бухгалтеров: 1, 2-5, 6-9, 10 и более.
Выберите клиентов для создания модели
Сначала работа ведется только с массивом обслуживаемых клиентов. Оптимальнее выбрать историю взаимоотношений с клиентами за несколько лет, например, за 5 или более лет. Чем больше клиентов будет в выборке, тем более точным будет результат.
Выбранных клиентов с их характеристиками необходимо поместить в базу данных, например в MS SQL Server. В простейшем случае это будет одна таблица фактов, где одна строка это один клиент, а каждое поле таблицы это выбранные на предыдущем этапе показатели.
При заливке данных, скорее всего их надо будет подготовить для анализа, преобразовать в соответствии с проведенной ранее группировкой значений показателей.
Причем в таблице вы можете хранить эти значения в виде текста, но более правильно в виде кодов — ссылок на справочник. В таблицу фактов можно заливать данные скриптами на T-sql, с помощью SQL Server Integration Services (SSIS) или другими способами.
Создайте модель для анализа
Далее необходимо создать модель для анализа Data mining, например, с помощью SQL Server Business Intelligence Development Studio (BIDS). Подробное описание создания моделей в BIDS выходит за рамки данной статьи, отмечу лишь, что мной используется стандартный микрософтовский алгоритм кластеризации.
На выходе получаем определенное количество кластеров, каждый из которых характеризуется выбранными показателями клиентов.
Выделите характерные значения для полученных кластеров
Каждый кластер необходимо описать характерными значениями по всем используемым в анализе показателям, характерным для потенциальных и обслуживаемых клиентов. Например, для кластера 1 характерно количество бухгалтеров 2-5, бюджетный тип налогообложения и вид деятельности здравоохранение. Важно, чтобы в описании кластера присутствовали значения по всем показателям. Возможно, что один показатель будет содержать несколько значений, например, в одном кластере с близкой вероятностью будут находиться клиенты с видом деятельности здравоохранение и образование. Это нормально, берите оба значения.
Объедините кластеры в сегменты
Далее анализируем полученные кластеры в разрезе тех самых 2-3 целевых показателей обслуживаемых клиентов, которые были выбраны ранее. Фактически можно составить таблицу, в которой каждый кластер будет описан понятным для продавцов языком. Например, кластер 1 — с клиентами, живущими средний срок жизни и приносящими ежемесячный доход выше среднего, кластер 2 – с клиентами, живущими больше среднего, и приносящими доход ниже среднего уровня. Все эти описания и формулировки лежат в компетентной области маркетингового аналитика. Какие-то кластеры можно сгруппировать, если они по целевым показателям относятся к одной группе. Полученные группы кластеров будем называть сегментами.
Выберите потенциальных клиентов
Необходимо выбрать массив всех потенциальных клиентов, которых мы хотим сегментировать. В общем случае это все клиенты, которые могут поступить в работу сотрудникам для продажи.
Распределите потенциальных клиентов по кластерам
Топ-10 data mining-алгоритмов простым языком
Примечание переводчика: Мы довольно часто пишем об алгоритмической торговле (вот, например, список литературы по этой теме и соответствующие аналитические материалы) и API для создания торговых роботов, сегодня же речь пойдет непосредственно об алгоритмах, которые можно использовать для анализа различных данных (в том числе на финансовом рынке). Материал является адаптированным переводом статьи американского раработчика и аналитика Рэя Ли.
Сегодня я постараюсь объяснить простыми словами принципы работы 10 самых эффективных data mining-алгоритмов, которые описаны в этом докладе.
Когда вы узнаете, что они собой представляют, как работают, что делают и где применяются, я надеюсь, что вы используете эту статью в качестве отправной точки для дальнейшего изучения принципов data mining.
1. С4.5
Что он делает? Алгоритм C4.5 строит классификатор в форме дерева решений. Чтобы сделать это, ему нужно передать набор уже классифицированных данных.
Подождите, а что такое классификатор? Классификатор – это инструмент, применяемый в data mining, который использует классифицированные данные и на их основании пытается предсказать, к какому классу стоит отнести новые данные.
Как выглядит пример использования алгоритма? Предположим, что у нас есть набор данных – это данные о группе пациентов. Мы знаем различные параметры каждого пациента: возраст, пульс, кровяное давление, максимальное потребление кислорода, историю семьи и так далее. Эти параметры называются атрибутами.
На основании этих атрибутов мы хотим предсказать, может ли пациент заболеть раком. Пациент может попасть в один из 2 классов: будет болеть раком или не будет болеть раком. Алгоритму C4.5 сообщают класс каждого пациента.
Используя набор атрибутов пациента и соответствующий класс, C4.5 строит дерево решений, способное предсказать класс для новых пациентов на основании их атрибутов.
Круто, но что такое дерево решений? Классификация методом дерева решений создает некое подобие блок-схемы для распределения новых данных. Если вернуться к примеру с пациентом, то ветка блок-схемы может выглядеть так:
В каждой точке блок-схемы задается вопрос о значимости того или иного атрибута, и в зависимости от этих атрибутов он или она [пациенты] попадают в определенный класс. Вы можете найти множество примеров построения дерева решений здесь.
Требует ли этот метод обучения или он самообучающийся? Этот метод требует обучения, здесь тренировочный набор данных размечается классами. Снова возвращаясь к примеру с пациентами, отмечу, что C4.5 не решает самостоятельно, заболеет пациент раком или нет. Как мы уже говорили, он создает дерево решений, которое используется для принятия решений.
Вот отличия C4.5 от других систем, использующих деревья решений:
Где он используется? На OpenTox можно найти реализацию на Java, которая является инструментом для визуализации и анализа в методах data mining. Orange, набор open-source-инструментов для анализа и визуализации результатов дата майнинга, использует C4.5 в своем классификаторе дерева решений.
Классификаторы – отличная вещь, но вот вам еще один алгоритм, который имеет непосредственное отношение к кластеризации….
2. Метод к-средних
Что он делает? Метод к-средних создает к-групп из набора объектов таким образом, чтобы члены группы были наиболее однородными. Это популярная техника кластерного анализа для исследования набора данных.
Погодите-ка, что такое кластерный анализ? Кластерный анализ – это семейство алгоритмов, разработанных для формирования групп таким образом, чтобы члены группы были наиболее похожими друг на друга и не похожими на элементы, не выходящие в группу. Кластер и группа – это синонимы в мире кластерного анализа.
Есть какой-нибудь пример? Определенно. Предположим, что у нас есть данные о пациентах. В кластерном анализе это называется наблюдениями. Мы кое-что знаем о каждом пациенте, например, его возраст, пульс, кровяное давление, максимальное потребление кислорода, холестерин и так далее. Это вектор, представляющий пациента.
Вы можете думать об этом векторе как о списке чисел, который может быть интерпретирован в виде координатов многомерного пространства. Пульс в одном измерении, кровяное давление – в другом и так далее.
Может возникнуть вопрос:
Как нам сгруппировать вместе пациентов по возрасту, пульсу, давлению с помощью этих векторов?
Хотите узнать хорошую новость?
Вы говорите методу к-средних, сколько кластеров вам нужно, а он сделает все остальное.
Как это происходит? Метод к-средних имеет множество вариантов работы для различных типов данных.
В общем случае все они делают примерно следующее:
Почему стоит использовать метод к-средних? Не думаю, что многие возьмутся спорить:
Основным достоинством алгоритма является его простота. Простота обычно означает высокую скорость выполнения и эффективность по сравнению с другими алгоритмами, в особенности при работе с крупными наборами данных.
Метод к-средних может использоваться для предварительного разбиения на группы большого набора данных, после которого проводится более мощный кластерный анализ подкластеров. Метод к-средних может использоваться, чтобы «прикинуть» количество кластеров и проверить наличие неучтенных данных и связей в наборах.
Но не все так гладко:
Два основных недостатка метода к-средних заключаются в чувствительности к «выбросам» и начальному выбору центров тяжести. Также нужно помнить, что метод к-средних создан для работы с непрерывными значениями, поэтому придется проделать пару фокусов, чтобы заставить алгоритм работать с дискретными данными.
Где он используется? Огромное количество реализаций метода к-средних доступны онлайн:
3. Метод опорных векторов
Что он делает? Метод опорных векторов (SVM – Support vector machine) использует гиперплоскость, чтобы классифицировать данные по 2 классам. На верхнем уровне SVM выполняет те же операции, что и C4.5, но с одним отличием – SVM не использует деревья решений.
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 параметра:
Существует модификация алгоритма Apriori, способная проводить классификацию маркированных данных
Почему именно Apriori? Он прост, понятен, легкореализуем и имеет множество модификаций.
В процессе работы алгоритм может быть довольно ресурсоемким; вычисления могут занять достаточно много времени.
Где он используется? Существует огромное количество реализаций Apriori. Одни из самых популярных – это ARtool, Weka и Orange.
Следующий алгоритм был самым сложным в понимании для меня, давайте взглянем на него…
5. EM-алгоритм
Что он делает? В data mining алгоритм максимизации ожидания (expectation-maximization (EM) обычно используется как кластерный алгоритм (наподобие алгоритма к-средних) для обнаружения знаний.
В математической статистике EM-алгоритм считается итерационным и используется для оценки максимального правдоподобия при вычислении параметров статистической модели со скрытыми переменными.
Я не статистик, поэтому надеюсь, что мое упрощение будет корректным и поможет вам во всем разобраться.
Вот несколько концепций, которые сделают все проще…
Что такое статистическая модель? Я вижу модель как что-то, описывающее известные данные. Например, оценки за экзамен могут соответствовать нормальному распределению, поэтому предположение, что оценки генерируются в соответствии с нормальным распределением, является моделью.
Секундочку, а что такое распределение? Распределение представляет вероятности появления всех измеримых результатов. Например, оценки за экзамен могут соответствовать нормальному распределению. Это нормальное распределение представляет все вероятности получения той или иной оценки.
Другими словами, распределение помогает понять, сколько человек, сдающих экзамен, получат ту или иную оценку.
Круто, а что такое параметры модели? Параметр описывает распределение, которое является частью модели. Например, нормальное распределение описывается средним арифметическим и дисперсией.
В примере с экзаменом распределение оценок (измеримые исходы) вписывается в нормальное распределение. Среднее арифметическое равняется 85, а дисперсия – 100.
Для того, чтобы описать нормальное распределение, вам нужны всего два параметра:
Мы не знаем среднее арифметическое или дисперсию всех оценок, но мы можем оценить их, используя данные из примера. Правдоподобие – это вероятность того, что кривая нормального распределения с оцененными значениями среднего арифметического и дисперсии будет достаточно точно описывать полученные результаты экзаменов.
Другими словами, имея набор исчисляемых исходов, давайте оценим параметры модели. На основании этих оцененных параметров считается гипотетическая вероятность появления того или иного исхода, называемая правдоподобием.
Запомните, что это гипотетическая вероятность для существующих оценок, а на вероятность получения оценки в будущем.
Вы вероятно думаете, что же такое вероятность?
Предположим, что мы знаем среднее арифметическое и дисперсию. Вероятность появления той или иной оценки соответствует нормальному распределению. Шанс, что мы пронаблюдаем определенные оценки с определенной частотой, называется вероятностью.
Если сказать простыми словами, то мы оцениваем возможные исходы на основании параметров.
Отлично! А в чем отличие между данными наблюдений и скрытыми данными? Данные наблюдений – это данные, которые вы пронаблюдали или зафиксировали. Скрытые данные – это отсутствующие данные. Есть множество причин, почему они могут отсутствовать (не зафиксированы, проигнорированы и так далее).
Вот в чем загвоздка:
В ходе дата майнинга и кластеризации важно оценивать класс точки данных, как отсутствующие данные. Мы не знаем, что это за класс, поэтому интерпретация недостающих данных очень важна в случае применения EM-алгоритма к задаче кластеризации.
Повторюсь: EM-алгоритм является итерационным и используется для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Надеюсь, что теперь вам стало понятнее.
А теперь хорошие новости:
Оценивая максимальное правдоподобие, EM-алгоритм создает отличную модель, которая назначает метки класса точкам данных – прямо как в кластеризации.
Как EM помогает в кластеризации? EM-алгоритм начинает с того, что пытается сделать вывод на основании параметров модели.
Затем следует итерационный трехшаговый процесс:
Требует ли этот метод обучения или он самообучающийся? Поскольку мы не предоставляли алгоритму маркированные данные, то это самообучающийся метод.
Почему именно EM? Главным достоинством EM-алгоритма является простота исполнения. Вдобавок ко всему, он может оптимизировать не только параметры модели, но и делать предположения относительно значений отсутствующих данных.
Это делает EM отличным методом для кластеризации и создания моделей с параметрами. Зная кластеры и параметры модели можно предполагать, что содержит кластер и куда стоит отнести новые данные.
Хотя и у EM-алгоритма есть свои недостатки:
Какой метод 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:
Почему именно PageRank? Главным достоинством PageRank является надежность, несмотря на сложность получения релевантной входящей ссылки.
Если у вас есть график или схема, и вы хотите определить ее относительную важность, приоритет, ранжирование или релевантность, дайте PageRank показать себя.
Где он используется? Торговая марка PageRank принадлежит компании Google. Однако алгоритм PageRank запатентован Стэндфордским университетом.
Если у вас возник вопрос по поводу того, можете ли вы использовать PageRank:
Я не адвокат, так что лучше посоветоваться со знающими людьми, но, вероятно, вы можете использовать алгоритм сколько вам угодно, пока он не начнет приносить вам финансовую выгоду.
Вот 3 примера реализации PageRank:
7. AdaBoost
Что он делает? AdaBoost – это алгоритм усиления классификаторов.
Как вы помните, классификатор пытается предсказать по уже известным ему данным, к какому классу будут относиться новые данные.
Что такое усиление? Усиление – это ансамблевый алгоритм обучения, который берет множество алгоритмов обучения, например, деревья решений, и объединяет их. Целью является взять набор или группу слабых классификаторов и объединить их в один сильный.
В чем разница между сильным и слабым классификатором? Слабый классификатор производит классификацию с точностью чуть выше шанса. Популярный пример слабого классификатора – это так называемый «решающий пень» – одноуровневое дерево решений.
Сильный классификатор, наоборот, имеет гораздо большую точность. Самым распространенным примером сильного классификатора является SVM.
Какие есть примеры AdaBoost? Давайте начнем с трех слабых классификаторов. Мы обучим их за 10 итераций на тренировочном наборе данных о пациентах. Набор данных содержит детали медицинских записей пациента.
Как нам предсказать, заболеет ли человек раком?
Вот как AdaBoost отвечает на этот вопрос:
Раунд 1: AdaBoost берет часть данных тренировочного набора и проверяет, насколько точен каждый классификатор. В результате выбирается наилучший из них.
Дополнительно те примеры, которые были классифицированы неверно, приобретают больший вес в следующей итерации.
Еще одна вещь – лучшему классификатору также присваивается вес в зависимости от его точности, а сам классификатор включается в ансамбль (на первом шаге ансамбль состоит из одного классификатора).
Раунд 2: AdaBoost повторно пытается выявить лучший классификатор.
И здесь возникает загвоздка:
Выборка тренировочных данных о пациентах теперь включает в себя ранее неверно классифицированные примеры, которые имеют больший вес. Другими словами, те пациенты, которые были неправильно классифицированы в прошлой итерации, получают больший шанс попасть в новую выборку.
Это – словно переходить на следующий уровень в видеоигре и не начинать все заново, если персонаж погибает. Вместо этого вы начинаете с уровня 2, и всеми силами стараетесь перейти на третий уровень.
Точно так же первый классификатор, вероятно, классифицировал некоторых пациентов верно. Вместо того, чтобы пытаться классифицировать их повторно, давайте сфокусируемся на тех, кого классифицировать не удалось.
Лучший классификатор снова взвешен и включен в ансамбль – неверно классифицированные пациенты также взвешены и получают больший шанс быть выбранными повторно.
После 10 раундов: Мы получаем ансамбль взвешенных классификаторов, натренированных и перетренированных на неправильно классифицированных данных из предыдущих итераций.
Требует ли этот метод обучения или он самообучающийся? Этот метод требует обучения, поскольку на каждой итерации по размеченному набору данных тренируются более слабые классификаторы.
Почему именно AdaBoost? AdaBoost – это просто. Алгоритм относительно легок в программировании.
Кроме того он очень быстрый! Слабые классификаторы обычно проще, чем сильные. Простота означает высокую скорость исполнения.
Это супер-элегантный способ автоматической настройки классификатора, поскольку каждая успешная итерация AdaBoost корректирует вес лучшего классификатора. Вам нужно только указать количество итераций.
И наконец, AdaBoost очень гибкий и легко приспосабливающийся к условиям задачи алгоритм. AdaBoost может работать с любыми обучающимися алгоритмами и с большим количеством разнообразных данных.
Где он используется? AdaBoost имеет тонну вариаций и реализаций. Вот некоторые из них:
8. Алгоритм k-ближайших соседей (kNN)
Что он делает? kNN (k-Nearest Neighbors) – это алгоритм классификации, однако он отличается от предыдущих, описанных в этой статье, потому что это – ленивый классификатор.
Что значит ленивый классификатор? Это означает, что в процессе обучения он не делает ничего, а только хранит тренировочные данные. Он начинает классификацию только тогда, когда появляются новые немаркированные данные.
Активный же классификатор создает классификационную модель в процессе обучения. Когда вводятся новые данные, такой классификатор «скармливает» данные классификационной модели.
Какими классификаторами являются C4.5, SVM и AdaBoost? В отличие от kNN, они все – активные классификаторы.
Когда появляется новые неразмеченные данные, kNN проходит по 2 базовым шагам:
Сначала он ищет k ближайших размеченных точек данных – другими словами, k ближайших соседей.
Затем, используя классы соседей, kNN решает, как лучше классифицировать новые данные.
Возможно, вы думаете…
Как kNN понимает, какие точки находятся ближе всего? Для непрерывных данных kNN использует дистанционную метрику, например, Евклидову дистанцию (метрику). Выбор метрики зависит от типа данных. Некоторые советуют даже выбирать дистанционную метрику на основании тренировочных данных. Есть очень много нюансов, описанных во многих работах по дистанционным метрикам kNN.
При работе с дискретными данными, они сначала преобразуются в непрерывные. Вот 2 примера:
Я готов поспорить, что вы догадываетесь, в каком случае все становится чуть-чуть сложнее.
Как kNN решает, к какому классу отнести данные, если соседи не принадлежат одному классу?
Для решения этой проблемы используются 2 классические техники:
Почему именно kNN? kNN легок в понимании и легко реализуем – это две главные причины. В зависимости от выбора дистанционной метрики, kNN может показывать достаточно точные результаты.
Но это только часть истории…
Вот 5 вещей, за которыми нужно следить:
9. Наивный байесовский классификатор
Что он делает? Наивный байесовский классификатор – это семейство алгоритмов классификации, которые принимают одно допущение:
Каждый параметр классифицируемых данных рассматривается независимо от других параметров класса.
Что означает слово «независимо»? 2 параметра называются независимыми, когда значение одного параметра не оказывает влияния на второй.
Скажем, у вас есть набор данных о пациенте: пульс, уровень холестерина, вес, рост и почтовый индекс. Все параметры будут независимыми, если значения всех параметров не оказывают эффекта друг на друга. Для этого набора данных разумно предположить, что рост пациента и почтовый индекс независимы, поскольку рост человека и его почтовый индекс никак не связаны.
Но давайте посмотрим дальше, все ли параметры независимы?
К сожалению, ответ – нет. Есть 3 соотношения, которые зависимы:
Это подводит нас к другому вопросу…
Почему метод называется наивным? Предположение, что все параметры набора данных независимы – это довольно наивное предположение. Обычно так не бывает.
Кто такой Байес? Томас Байес был английским математиком-статистиком, в честь которого была названа теорема Байеса.
По сути, теорема позволяет нам предсказать класс на основании набора параметров, используя вероятность.
Упрощенное уравнение для классификации выглядит так:
Давайте взглянем на него поподробнее.
Что означает это уравнение? Уравнение находит вероятность класса А, на основании параметров 1 и 2. Другими словами, если вы видите параметры 1 и 2, то, вероятно, это данные класса А.
Уравнение читается следующим образом: Вероятность [выявления] класса А на основании параметров 1 и 2 – это дробь.
Что мы видим в этом тренировочном наборе данных?
Предположим, что неизвестный фрукт длинный, сладкий и желтый.
Для вычисления вероятности нужно проделать 4 простых шага:
Шаг 1: Чтобы вычислить вероятность того, что неизвестный фрукт – это банан, давайте сначала решим, похож ли этот фрукт на банан. Вот как вычисляется вероятность класса «Банан» на основании параметров «длинный», «сладкий», «желтый»:
P(Banana|Long, Sweet, Yellow)
Выглядит точно так же как уравнение, описанное выше.
Шаг 2: Начнем с числителя и подставим все значения в уравнение:
0.8 x 0.7 x 0.9 x 0.5 = 0.252
Шаг 3: Проигнорируем знаменатель, поскольку он будет одинаковым для всех последующих вычислений.
Шаг 4: Проделаем те же вычисления для других классов:
Поскольку 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, код которой основан на теории, представленной общеизвестными статистиками из Стэндфордского университета и Калифорнийского университета в Беркли.
