Разработка ансамбля алгоритмов кластеризации на основе изменяющихся метрик расстояний © П. В. Бочкарёв © В. С. Киреев Национальный исследовательский ядерный университет «МИФИ», Москва, Российская Федерация pvbochkarev@mephi.ru vskireev@mephi.ru Аннотация Под критерием качества кластеризации обычно понимается некоторый функционал, зависящий от В настоящее время происходит активное накопление разброса объектов внутри группы и расстояний данных большого объёма в различных между ними [9]. информационных средах, таких как социальные, Кластеризация отличается от классификации тем, корпоративные, научные и другие. Интенсивное что изначально неизвестны ни количество, ни использование больших данных в различных свойства классов (кластеров). К особенностям областях стимулирует повышенный интерес кластеризации можно отнести следующее: исследователей к развитию методов и средств  возможность определения заранее обработки и анализа массивных данных огромных неизвестного класса объектов по начальным объёмов и значительного многообразия. Одним из характеристикам; перспективных направлений в аналитике  возможность обработки сколь угодно интенсивных данных является кластерный анализ, большого количества объектов в достаточно который позволяет решить такие задачи как, короткие сроки. сокращение размерности исходного набора данных, Устойчивость решений в задачах кластеризации выявление паттернов и т.д. В данной статье авторами может быть повышена благодаря формированию предлагается ансамбль алгоритмов кластеризации, ансамбля алгоритмов [13] и построению с его состоящий из базовых алгоритмов K-means, помощью коллективного решения на основе мнений отличающихся по одному параметру - метрике участников ансамбля, где под мнением алгоритма расстояния между объектами. Для оценки работы подразумевается его вариант разбиения данных на разработанного ансамбля использованы открытые кластеры. данные архива UCI. Данные свойства кластерного анализа особо актуальны при работе в областях с интенсивным 1 Введение использованием данных, когда предметная область слабо формализована, например, для анализа Данные большого объёма (BigData), текстовых документов, изображений и т.д. используются в различных процессах, таких как Основное внимание в данной работе уделяется извлечение информации из веб-ресурсов, выявления построению ансамбля алгоритмов кластеризации на общих закономерностей в областях с интенсивным использованием данных и т.д. Эти данные основе изменяющихся метрик расстояний для анализа данных большого объема. необходимо структурировать, классифицировать, подвергать тщательному анализу. В этом случае кластерный анализ является основой многих 2 Современные подходы к решению научных исследований [14]. Кластеризация (от англ. проблемы cluster – скопление), это сегментация через Выбор метода кластеризации зависит от выделение определённых объединений однородных количества данных и от того, требуется ли элементов, которые рассматриваются как обрабатывать и анализировать несколько типов самостоятельные единицы, обладающие данных одновременно [6, 10]. определёнными свойствами [15]. На практике чаще всего используются гибридные В результате процедуры кластеризации подходы, в которых шлифование кластеров образуются «кластеры», то есть группы очень выполняется методом K-средних (см. форм.1), а похожих объектов [16]. начальное разбиение – одним из более Труды XVIII Международной конференции универсальных и мощных методов. DAMDID/RCDL’2016 «Аналитика и управление ∑ ∑ , (1) данными в областях с интенсивным использованием данных», Ершово, 11-14 октября где k – число кластеров, – полученные 2016 кластеры, i=1, 2,…, k и – центры масс векторов. 32 Данные о сравнении алгоритмов представлены в получить более устойчивое решение даже при таб.1 [7]. большом количестве шумов и выбросов в данных [9]. Таблица 1 Сравнительная таблица алгоритмов Существуют следующие основные методики Алгоритм Входные Результаты получения ансамбля алгоритмов (см. Рис. 1)[8]: кластеризации данные 1. нахождение консенсусного разбиения, т.е. иерархическая число бинарное древо согласованного разбиения при имеющихся кластеров кластеров нескольких решениях, оптимального по или порог некоторому критерию; расстояния 2. вычисление согласованной матрицы для сходства/различий (co-occurrence matrix). усечения иерархии Ансамбль K-средних число центры алгоритмов кластеров кластеров C-средних число центры кластеров, кластеров, степень матрица Нахождение Вычисление нечеткости принадлежности консенсусного согласованной выделение порог древовидная разбиения матрицы связных расстояния структура сходства компонент R кластеров Для определения расстояния между объектами в Рисунок 1 Ансамбли алгоритмов кластеризации кластерном анализе используются различные метрики расстояний между объектами x и x’. При формировании окончательного решения Наиболее востребованными в кластерном анализе используются результаты, полученные различными являются следующие метрики: алгоритмами, либо одним алгоритмом с различными 1. Евклидово расстояние значениями параметров, по разным подсистемам переменных и т.д. В настоящее время ансамблевый , ∑ ; (2) подход является одним из наиболее перспективных 2. Манхэттенское расстояние направлений в кластерном анализе. , ∑ | |; (3) Примерами использования ансамбля алгоритмов 3. Расстояние Чебышева кластеризации могут служить следующие. Созданный на основе непараметрического алгоритма , | | ; (4) MeanSC, ансамбль позволил улучшить показатели 4. Коэффициент Жаккара кластеризации многоканальных изображений [13]. А ∑ также, используя ансамбль алгоритмов , ∑ ∑ ∑ ; (5) кластеризации на основе K-средних и алгоритма 5. Динамическая трансформация временной SVM (Support Vector Machines), удалось повысить шкалы (dynamic time wrapping, DTW) точность обнаружения сердечных аномалий, что позволило сократить время установления диагноза ∑ , ′ , (6) [2]. Таким образом, применяя ансамбль с различными где K – длина пути между x и x’, который наборами алгоритмов, в соответствии с их вычисляется по специальной матрице преимуществами и особенностями, можно создать трансформаций [11]. наиболее подходящую схему кластеризации для определённой предметной области. Ранее также Выбор метрики существенно влияет на качество указывалось, что важным фактором, влияющим на кластеризации. результат кластеризации, является выбор В настоящее время в кластерном анализе конкретной метрики расстояний между объектами. проявляется тенденция к применению коллективных Объединяя эти два подхода, можно существенно методов [1]. Ранее было отмечено, что алгоритмы повысить эффективность кластерного анализа. кластерного анализа не являются универсальными: каждый алгоритм имеет свою особую область применения (таблица 1). В том случае, если 3 Предлагаемый подход рассматриваемая область содержит различные типы 3.1 Ансамбль алгоритмов кластеризации данных, для выделения кластеров необходимо применять не один определённый алгоритм, а набор Предлагаемый авторами ансамбль алгоритмов различных алгоритмов. представляет собой сочетание последовательных Ансамблевый (коллективный) подход позволяет алгоритмов K-средних, каждый из которых снизить зависимость конечного решения от предлагает свое разбиение, и иерархического выбранных параметров исходных алгоритмов и агломеративного алгоритма, объединяющего 33 полученные решения с помощью особого механизма. 3.2 Алгоритмы кластеризации В отличие от ансамбля, использующего алгоритм В данном ансамбле алгоритмов кластеризации MeansSC [13], предложенный ансамбль опирается на были использованы пять К-средних (см. форм.1), как результаты предварительного исследования один из наиболее востребованных алгоритмов исходных данных, которые представляют собой кластеризации больших данных [12]. Для данных небольшой набор размеченных экспертами объектов. алгоритмов были использованы такие метрики, как: Минимально необходимый процент объема исходной выборки, гарантирующий заданную  Евклидово расстояние (см. форм. 2) точность, подлежит дальнейшему изучению. Для  Манхэттенское расстояние (см. форм. 3) определенности, в данной работе используется 0.5%,  Расстояние Чебышева (см. форм. 4) что в случае увеличения объема данных, очевидно,  Коэффициент Жаккара (см. форм. 5) должно подлежать пересмотру. На первом шаге каждый алгоритм K-средних,  DTW расстояние (см. форм. 6) разбивает данные на кластеры, используя свою метрику расстояния. Затем, рассчитывается точность 3.3 Наилучшее разбиение на кластеры и вес мнения алгоритма в ансамбле по формуле 7: Для получения наилучшего разбиения на кластеры необходимо, как было упомянуто выше, , (7) ∑ составить бинарную матрицу сходства\различий на где – точность алгоритма l, т.е. отношение каждое L разбиение в ансамбле: количество правильно кластеризованных объектов к , , (8) объему всей выборки, а L – количество алгоритмов в где hi(i, j) равен нулю, если элемент i и элемент j ансамбле. попали в один кластер, и 1 если нет. Для каждого полученного разбиения Следующим шагом в составлении ансамбля составляется предварительная бинарная матрица алгоритмов кластеризации является составление различий размера n x n, где n-количество объектов, согласованной матрицы бинарных разбиений. ∗ ∗ необходимая для определения, занесены ли объекты , , (9) ∗ ∑ разбиения в один класс. Затем рассчитывается , , , (10) согласованная матрица различий, каждый элемент где wl – вес алгоритма. которой представляет собой взвешенную (с использованием веса из формулы 7) сумму Для формирования наилучшего разбиения по элементов предварительных матриц. Полученная согласованной матрице был выбран алгоритм матрица используется в качестве входных данных ближайшего соседа. для алгоритма иерархической агломеративной кластеризации. Затем с помощью обычных приемов, таких как определение скачка расстояния 4 Валидация предлагаемого ансамбля агломерации, можно выбрать наиболее подходящее кластерное решение. Процедура создания ансамбля Для тестирования и оценки ансамбля алгоритмов алгоритмов представлена на рисунке 2. кластеризации использовалось программное средство RapidMiner [3]. С помощью RapidMiner можно решать, как исследовательские (модельные), Алгоритм 1 Алгоритм 5 так и прикладные (реальные) задачи интеллектуального анализа данных, включая анализ Проверка Проверка текста, анализ мультимедиа, анализ потоков данных, точности точности что подходит для тестирования ансамбля алгоритмов кластеризации. В качестве данных для Расчёт веса Расчёт веса кластеризации использовались открытые данные с разбиения разбиения web-сайта UCI [4]. Данный пример содержит информацию о платежах клиентов с помощью пластиковых карт, всего 30 тыс. записей и 24 Составление Составление бинарной бинарной атрибута. Данные были размечены экспертным матрицы матрицы способом на 2 кластера, и эти результаты были взяты в качестве корректного решения. Ниже представлены элементы схемы Составление согласованной эксперимента, разработанной в RapidMiner. Для матрицы различий, учитывая вес разбиения снижения размерности исходных данных был выбран метод главных компонентов (Principal Применение метода ближайшего component analysis, PCA) (см. Рис. 3). В качестве соседа к согласованной матрице критерия выбора количества компонент был выбран различий критерий Кайзера (собственное значение Рисунок 2 Ансамбль алгоритмов кластеризации компоненты больше единицы). 34 Рисунок 3 Снижение размерности данных На следующем шаге была выявлена точность каждого алгоритма путём сравнения полученного разбиения на два кластера каждым алгоритмом с кластерами, размеченными экспертным способом. После получения значения точности каждого Рисунок 5 Работа алгоритма иерархической алгоритма, по формуле 7 был рассчитан вес мнения кластеризации алгоритма (см. Рис. 4). Так, из графика видно, что наибольшим весом обладает алгоритм, В результате применения предложенного использовавший расстояние Чебышева, а подхода было получено окончательное решение, наименьшим весом - алгоритм с метрикой Жаккара. состоящее из двух кластеров, характеризующих поведение клиентов при осуществлении платежей, обладающее достаточно высокой точностью, Вес мнения алгоритма согласующееся с экспертным мнением (см. Рис. 6). 20,40% Из рисунка видно, что точность предложенного 20,50% ансамбля превышает точность стандартного 20,35% алгоритма К-средних, с различными метриками. 20,00% 20,35% 20,20% 19,50% Точность алгоритмов, % 19,00% 92 90,61 89,31 89,44 18,70% 90 88,4 18,50% 88 89,31 18,00% 86 84 82,03 82 80 Рисунок 4 Диаграмма веса алгоритмов Далее была проведена кластеризация данных каждым алгоритмом. На следующем шаге, используя возможности RapidMiner, по формуле 8 были Рисунок 6 Сравнение точности алгоритмов получены бинарные матрицы разбиения На основе полученных результатов можно 5 Заключение определить значение индекса качества группировки (вес разбиения). Используя вес каждого разбиения и Задача интеллектуального анализа и обработки сумму значений бинарных матриц Больших Данных последние несколько лет является сходства\различий (см. форм. 9), была составлена предметом изучения множества специалистов и согласованная матрица различий для ансамбля важной составляющей этого анализа указывается алгоритмов кластеризации (см. форм. 10). кластеризация этих данных, позволяющая Применяя алгоритм ближайшего соседа к приблизиться к решению проблемы трех V (объема рассчитанной матрице, с помощью возможностей данных для хранения - Volume, скорости обработки - Rapidminer, было определено наилучшее разбиение. Velocity и разнообразия исходных типов данных - На рисунке 5 представлена часть результатов Variety) [5]. Таким образом, кластерный анализ работы алгоритма – дендрограммы, полученной на становится одним из ключевых в сферах обработки последнем этапе его работы. интенсивных данных, так как это один из 35 эффективных методов, который существует на вычислительная техника и информатика, 2013, сегодняшний день. Применяя ансамбль алгоритмов №2 (23), с 22-31. кластеризации, можно повысить достоверность [10] В.С. Киреев. Оценка результатов кластеризации разбиения данных на группы. Существенным при использовании различных критериев является то, что данный метод может применяться в качества// Программные продукты и системы, различных областях. Рассмотренный в данной статье 2009, №3, С. 36-39. ансамбль алгоритмов кластеризации нивелирует [11] Д.Е. Мозохин, В.А. Калягин. Сравнительный недостатки метрик расстояний для алгоритмов K- анализ алгоритмов кластеризации в сетях средних, тем самым повышая достоверность фондовых рынков // Алгоритмы, методы и разбиения. Дальнейшее исследование системы обработки данных. 2015, 4(33), С. 73-90 предложенного ансамбля алгоритмов на основе [12] И. Демин. Концепция кластера в технологиях меняющейся метрики расстояний планируется в интеллектуального анализа данных// Риск: рамках гранта РФФИ № 15-07-08742. Ресурсы, Информация, Снабжение, Конкуренция, 2012, 1, C. 260-263. [13] И. А. Пестунов, В. Б. Бериков, Ю. Н. Синявский. Литература Сегментация многоспектральных изображений на основе ансамбля непараметрических [1] J. Ghosh, A. Acharya Cluster ensembles. Wiley алгоритмов кластеризации // Вестник СибГАУ, Interdisciplinary Reviews: Data Mining and 2010, №5(31), С. 56-64. Knowledge Discovery. 2011. V. 1(4). P.305−315. [14] С. А. Суслов. Кластерный анализ: сущность, [2] Kausar Noreen;Abdullah Azween; Samir Brahim преимущества и недостатки // Вестник НГИЭИ. Belhaouari;Palaniappan Sellapan;AlGhamdi Bandar 2010. №1, С. 51-57. Saeed;Dey Nilanjan. Ensemble Clustering [15] С.А. Батуркин, Е.Ю. Батуркина, В.А. Зименко, Algorithm with Supervised Classification of И.В. Сигинов. Статистические алгоритмы Clinical Data for Early Diagnosis of Coronary кластеризации данных в адаптивных обучающих Artery Disease.// Journal of Medical Imaging and системах // Вестник РГРТУ, 2010, № 1 (31), С. 82- Health Informatics, V. 6, Number 1, February 2016, 85. P. 78-87. [16] С. Л. Подвальный, А. В. Плотников, А. М. [3] Predictive Analytics Platform | RapidMiner Белянин. Сравнение алгоритмов кластерного https://rapidminer.com/ анализа на случайном наборе данных // Вестник [4] UCI Machine Learning Repository ВГТУ, 2012, Т.8 №5, С. 4-6. https://archive.ics.uci.edu/ml/datasets/default+of+cr edit+card+clients (26.06.2016) [5] А. К. Горшенин, С.Я. Шоргин. Разработка информационной технологии Development of Ensemble of Clustering интеллектуального анализа больших данных // Algorithms Based on Varying Distances Metrics Современные проблемы прикладной математики, информатики, автоматизации, Pyotr V. Bochkaryov, Vasiliy S. Kireev управления: Материалы 3-го Международного Currently there is an active accumulation of big data научно-технического семинара (Севастополь, 9– in various information environments, such as social, 13 сентября 2013). –М.:ИПИ РАН, 2013. С. 104– corporate, scientific and other domains. Intensive use of 114. big data in various fields stimulates the increased interest [6] А.П. Кулаичев. Методы и средства of researchers to the development of methods and means комплексного анализа данных. – М.: Форум — Инфра-М, 2006. — 512 с. of processing and analyzing massive data volumes with [7] Б.О. Лялька, Антонова-Рафи Ю.В. Оценка significant variety. One of the promising areas in data эффективности кластеризационных алгоритмов. intensive analytics is cluster analysis, which allows to // Научные труды SWORLD, 2015, №2 (39), С. solve such problems as: reducing the dimension of the 25-29. original dataset, identifying patterns, etc. In this article, [8] В.Б. Бериков. Классификация данных с the authors propose an ensemble of clustering применением коллектива алгоритмов algorithms, consisting of the basic algorithm K-means, кластерного анализа // Знания-Онтологии- Теории (ЗОНТ-2015), 2015, С. 29-38 characterized by one parameter - the distance metric [9] В. Б. Бериков. Коллектив алгоритмов с весами в between objects. For the evaluation of performance of кластерном анализе разнородных данных // the designed ensemble the open data archive of UCI was Вестн. Том. гос. ун-та. Управление, used. 36