УДК 004

Дерево решений и его применение в анализе больших данных

Уланов Марат Зуфарович – магистрант Московского технического университета связи и информатики.

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

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

Введение

Современный мир характеризуется огромным объемом данных, накапливающихся в различных сферах деятельности, начиная от социальных сетей и интернет-коммерции до медицинских исследований и финансовых операций. Этот взрывной рост данных создает потребность в эффективных методах анализа и извлечения ценной информации из этого огромного объема информации. В этом контексте машинное обучение становится незаменимым инструментом для автоматизации и оптимизации процессов анализа данных, как подчеркивают многие исследователи [5, 8]. Одним из ключевых алгоритмов машинного обучения, широко применяемых в анализе больших данных, является дерево решений. Дерево решений представляет собой модель, которая использует иерархическую структуру для представления принятия решений. Оно является простым и гибким инструментом, который может быть использован для классификации и регрессии, а также для выполнения задач фильтрации и прогнозирования.

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

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

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

Понятие машинного обучения и типы алгоритмов машинного обучения

Машинное обучение представляет собой широкую область искусственного интеллекта, которая изучает разработку алгоритмов и моделей, позволяющих компьютерным системам обучаться и делать предсказания (прогнозы) или принимать решения на основе опыта и данных, а не явно заданных правил [1].

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

1. Логистическая регрессия – используется для предсказания вероятности принадлежности объекта к определенному классу. Она моделирует логистическую функцию, которая принимает входные значения и возвращает вероятность принадлежности к классу.
2. Метод k-ближайших соседей (k-NN) – относит новый объект к классу, который является наиболее распространенным среди его k ближайших соседей в пространстве признаков. Значение k определяет количество соседей, учитываемых при классификации [9].
3. Метод опорных векторов (SVM) – строит оптимальную гиперплоскость или набор гиперплоскостей, которые разделяют объекты разных классов в пространстве признаков. SVM может использовать ядерные функции для работы с нелинейными данными [2].
4. Нейронные сети – это модели, состоящие из взаимосвязанных узлов, называемых нейронами, которые передают и обрабатывают информацию. Нейронные сети могут иметь различные архитектуры, включая многослойные персептроны, сверточные нейронные сети и рекуррентные нейронные сети.
5. Градиентный бустинг (Gradient Boosting) – является ансамблевым методом машинного обучения, который комбинирует слабые модели в последовательной форме. Каждая новая модель строится таким образом, чтобы исправлять ошибки предыдущих моделей [4].

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

Понятие и суть алгоритма «Дерево решений»

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

Суть дерева решений можно описать математически следующим образом:

Пусть у нас есть обучающий набор данных, состоящий из N объектов, каждый из которых имеет M признаков. Обозначим этот набор данных как X = {(x₁,y₁),(x₂,y₂),...,(x^N,y^N)}, где x_i = (x_i1,x_i2,...,x_im) – вектор признаков для i-го объекта, а yᵢ – соответствующее значение целевой переменной (класс или числовое значение).

Для построения дерева решений, мы используем функции принятия решений (decision functions), которые основаны на значениях признаков и пороговых значениях. Каждый узел дерева представляет собой пару (j, t), где j – индекс признака, а t – пороговое значение.

Дерево решений строится по принципу рекурсивного разбиения данных. На каждом узле дерева выбирается наилучший признак и пороговое значение, по которому объекты разделяются на две или более подгруппы. Этот процесс продолжается до достижения критерия остановки, такого как достижение определенной глубины дерева или недостаточное количество объектов в узле [7].

Процесс построения дерева решений включает выбор оптимальных признаков и пороговых значений для разделения данных. Один из популярных критериев разделения – это индекс Джини (Gini index) или критерий энтропии (entropy criterion) [3].

Индекс Джини для узла t определяется следующей формулой:

Gini(t) = 1 – Σ(p_i)²,

где pᵢ – доля объектов класса i в узле t.

Критерий энтропии для узла t определяется следующей формулой:

H(t) = –Σ(pᵢ * log₂(p_i)),

где pᵢ – вероятность объекта принадлежать классу i в узле t.

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

Пусть Q – функционал качества разделения, который определяется в зависимости от критерия разделения (например, индекса Джини или энтропии). При разделении узла t на два дочерних узла t₁ и t₂, функционал качества разделения Q(t, t₁, t₂) вычисляется как взвешенная сумма индексов Джини или энтропий дочерних узлов, где веса определяются долей объектов в каждом узле.

Таким образом, при построении дерева решений мы ищем оптимальное разделение, которое минимизирует функционал качества разделения Q(t, t₁, t₂). Этот процесс рекурсивно повторяется для каждого узла до достижения критерия остановки, например, максимальной глубины дерева или недостаточного количества объектов в узле.

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

Применение алгоритма дерева решений в анализе больших данных

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

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

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

1. Признаки:

• Сумма покупки (в долларах) – X₁
• Категория товара (1 – электроника, 2 – одежда, 3 – бытовая техника) – X₂
• Возраст покупателя – X₃
• Пол покупателя (0 – мужской, 1 – женский) – X₄

2. Целевая переменная:

• Тип покупки (0 – низкая ценовая категория, 1 – высокая ценовая категория) – Y

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

Шаги решения задачи:

1. Загрузка данных. Мы загружаем большой объем данных, содержащих информацию о покупках. Предположим, что нам доступно 1 миллион записей.
2. Предобработка данных. Перед использованием данных мы выполняем предобработку, включающую удаление пропущенных значений и выбросов, а также масштабирование признаков при необходимости.
3. Разделение данных. Мы разделяем данные на обучающую выборку и тестовую выборку. Например, мы можем использовать 80% данных для обучения модели и 20% данных для оценки ее производительности.
4. Обучение модели дерева решений. Мы строим модель дерева решений на обучающей выборке. Для разделения узлов используем индекс Джини.
5. Подбор гиперпараметров. Мы проводим поиск по сетке для определения оптимальных гиперпараметров модели, таких как глубина дерева, минимальное количество объектов в листе, чтобы достичь наилучшей производительности модели.
6. Оценка производительности модели. Мы оцениваем производительность модели на тестовой выборке с использованием метрик, таких как точность (accuracy), полнота (recall), F-мера (F1-score), чтобы оценить ее способность предсказывать тип покупки.
7. Построение таблицы результатов. Мы создаем таблицу, в которой будут отображены результаты модели дерева решений.

Пример таблицы результатов может выглядеть следующим образом (табл. 1).

Таблица 1. Результаты применения алгоритма дерева решений для решения поставленной задачи

Показатель	Значение
Точность	0.85
Полнота	0.78
F-мера	0.81
AUC-ROC	0.87
Глубина дерева	10
Мин. кол-во объектов в листе	50

В данной таблице представлены основные метрики производительности модели дерева решений на тестовой выборке. Например, точность указывает на долю правильно предсказанных типов покупки, полнота отражает долю правильно обнаруженных высоких ценовых категорий, F-мера объединяет точность и полноту в одну метрику, а AUC-ROC (площадь под ROC-кривой) отражает общую производительность модели.

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

Заключение

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

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

Список литературы

1. Алханов Асет Адылович Машинное обучение и его применение в современном мире // Проблемы науки. 2021. №7 (66). URL: https://cyberleninka.ru/article/n/mashinnoe-obuchenie-i-ego-primenenie-v-sovremennom-mire (дата обращения: 18.07.2023).
2. Владимир Вьюгин.Математические основы теории машинного обучения и прогнозирования. — МЦМНО, 2013. — 390 с.
3. Гофман Евгений Александрович, Олейник Алексей Александрович, Субботин Сергей Александрович Кластер-анализ с использованием деревьев решений // Радиоэлектроника и информатика. 2011. №2. URL: https://cyberleninka.ru/article/n/klaster-analiz-s-ispolzovaniem-dereviev-resheniy (дата обращения: 18.07.2023).
4. Дружков Павел Николаевич, Золотых Николай Юрьевич, Половинкин Алексей Николаевич Программная реализация алгоритма градиентного бустинга деревьев решений // Вестник ННГУ. 2011. №1. URL: https://cyberleninka.ru/article/n/programmnaya-realizatsiya-algoritma-gradientnogo-bustinga-dereviev-resheniy (дата обращения: 18.07.2023).
5. Кравченко Влада Олеговна, Крюкова Анастасия Александровна "большие данные" – практические аспекты и особенности // Academy. 2016. №6 (9). URL: https://cyberleninka.ru/article/n/bolshie-dannye-prakticheskie-aspekty-i-osobennosti (дата обращения: 18.07.2023).
6. Алгоритмы машинного обучения и их использование. Мифтахов Р.И.Моя профессиональная карьера. 2020. Т. 3. № 11. С. 53-58.
7. Анализ алгоритма машинного обучения “дерево решений”. Никитина Г.М., Павлов Е.М., Рыжов А.В., Тарасенко А.Д. В сборнике: Студенческая наука: актуальные вопросы, достижения и инновации.сборник статей X Международной научно-практической конференции в 2 частях. Пенза, 2022. С. 77-79.
8. Тихонов Алексей Анатольевич Большие данные и глубокое машинное обучение в искусственных нейронных сетях // Наука и образование сегодня. 2018. №6 (29). URL: https://cyberleninka.ru/article/n/bolshie-dannye-i-glubokoe-mashinnoe-obuchenie-v-iskusstvennyh-neyronnyh-setyah (дата обращения: 18.07.2023).
9. Madeh Piryonesi, Tamer E. El-Diraby. Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems(англ.) // Journal of Transportation Engineering, Part B: Pavements. — 2020-06. — Vol. 146, iss. 2.
10. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard and L. D. Jackel: Backpropagation Applied to Handwritten Zip Code Recognition, Neural Computation, 1(4):541-551, Winter 1989.