Метод ближайших соседей активно используется в машинном обучении для решения задач классификации в различных бизнес-приложениях. Познакомимся поближе с этим алгоритмом Machine Learning, а также разберем, почему NoSQL-хранилище Apache HBase отлично подходит для работы с ним.
Что такое метод ближайших соседей: ликбез по Machine Learning
В проектах Machine Learning и приложениях интеллектуального анализа данных, а также в пространственных и мультимедийных системах часто используется метод ближайших соседей (kNN, k-Nearest Neighbor). Он представляет собой простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки. Этот метод очень чувствителен к диапазону изменений входных переменных. Поэтому перед его применением входные данные следует нормализовать, приведя числовые значения признаков к одинаковой области изменения.
Можно сказать, что метод ближайших соседей является одним из простейших алгоритмов контролируемого машинного обучения, который сохраняет все доступные данные и классифицирует новую точку данных на основе сходства. Будучи непараметрическим алгоритмом, он не делает никаких предположений относительно базовых данных и не обучается сразу на обучающем наборе, а сохраняет его и во время классификации выполняет действие над набором данных.
С математической точки зрения kNN представляет собой классификацию новой точки данных на основании имеющихся k точек, расположенных ближе всего к ней. Благодаря тому, что kNN-модель не выводит дискриминационную функцию из обучающих данных, а только хранит их и учится на этом датасете только во время прогнозирования в реальном времени, метод ближайших соседей работает очень быстро. Он намного быстрее, чем другие алгоритмы Machine Learning, такие как метод опорных векторов (SVM) или линейная регрессия.
Еще одним преимуществом kNN является простота добавления новых данных, поскольку алгоритм не требует обучения перед тем, как делать прогнозы. Наконец, он очень прост в реализации, для которой нужны только 2 параметра: значение k и мера расстояния, например, евклидова или манхэттенская.
Однако, метод ближайших соседей не очень хорошо работает с большими наборами данных из-за высокой стоимости вычислений расстояния между новой точкой и каждой существующей и снижения производительности алгоритма. Также kNN плохо работает с данными большого размера, потому что при большом количестве измерений становится сложно вычислить расстояние в каждом из них. Как уже было отмечено ранее, kNN чувствителен к шуму в наборе данных, пропускам и выбросам. Необходимо провести предварительную подготовку, в частности, заполнить пропуски, удалить выбросы и нормализовать обучающий датасет.
Из наиболее понятных примеров реального применения метода ближайших соседей в практических приложениях можно отметить обнаружение мошеннических транзакций по кредитным картам и разработку рекомендательных систем, чтобы советовать пользователям товары на основе их предпочтений. Поскольку в этих случаях идет обработка огромного количества данных, целесообразно применять kNN-метод с технологиями Big Data, например, Apache HBase, что мы и рассмотрим далее.
Плюсы Apache HBase для kNN-алгоритмов
Напомним, Apache HBase является колоночно-ориентированной мультиверсионной NoSQL-СУБД типа key-value. Она работает поверх HDFS и обеспечивает возможности Google BigTable для Hadoop. Благодаря колоночно-ориентированной структуре хранения данных, Apache HBase работает очень быстро. А возможности этой СУБД эффективно обрабатывать огромные объемы данных смягчают недостатки kNN-метода, который изначально не предназначен для работы с большими выборками.
Запуск kNN-алгоритмов на данных в HBase поможет найти наиболее похожие элементы, что пригодится в рекомендательных и AML-системах (Anti-Money Laundering), а также в задачах обработки естественного языка, распознавания изображений, классификации текстов и анализе временных рядов.
Благодаря распределенному характеру HBase, запускаемые на ней kNN-алгоритмы становятся высокопроизводительными и выгодными с экономической точки зрения. Также эти аналитические приложения отлично масштабируются, могут работать с огромными объемами данных и сложными запросами, которые в Apache HBase выражаются не через SQL-инструкции, а в виде кода MapReduce. Примеры этого мы рассматривали здесь. Повысить эффективность работы kNN-алгоритмов в Apache HBase помогут следующие рекомендации:
- использовать оптимизированные структуры данных, такие как деревья, чтобы улучшить точность вычислений;
- добавить предварительное вычисление расстояний, чтобы сократить время выполнения программы;
- распараллелить вычисления между несколькими ядрами ЦП или узлами кластера;
- выбор наилучшую метрику расстояния, релевантную вычисляемому типу данных;
- настроить гиперпараметры алгоритма, задав оптимальное значение k. Если количество соседей для алгоритма kNN слишком велико, может случиться переобучение модели и рост вычислительных затрат. Если количество соседей слишком мало, точность алгоритма будет слишком мала из-за зашумления данных.
- включить кэширование промежуточных результатов, чтобы повторно использовать их в сложных вычислениях, сокращая время пересчета расстояний между точками данных.
Читайте в нашей новой статье, как kNN-алгоритмы используются в векторных базах данных для ИИ-приложений.
Узнайте больше подробностей про администрирование и эксплуатацию Apache Hive и других компонентов экосистемы Hadoop для хранения и аналитики больших данных на специализированных курсах в нашем лицензированном учебном центре обучения и повышения квалификации для разработчиков, менеджеров, архитекторов, инженеров, администраторов, Data Scientist’ов и аналитиков Big Data в Москве:
Источники
