25 июля 2020г.
Интеллектуальный анализ данных в настоящее время является одним из наиболее востребованных методов, используемых для анализа данных и извлечения скрытой информации, при невозможности использовать традиционные подходы, что связано со сложностью анализируемых данных и их объемом [1,2]. Основной метод анализа данных, известный как кластеризация данных, группирует данные в кластеры и позволяет легко извлекать информацию из этих кластеров [2].
Кластерный анализ - это задача интеллектуального анализа данных, целью которого является поиск, рекомендации и организация данных. В методах кластеризации наборы данных группируются в несколько кластеров. Кластеризация относится к классу неконтролируемых методов обучения, что отличает ее от классификации, в которой сходные объекты набора данных группируются в определенное количество кластеров. Чаще всего используются следующие два алгоритма кластеризации - это нечеткая кластеризация С-средних и иерархическая кластеризация. Рассмотрим каждый метод чуть подробнее.
Метод нечётких c-средних позволяет разбить имеющееся множество элементов на заданное число нечётких множеств. Метод нечеткой кластеризации c-средних можно рассматривать как усовершенствованный метод k-средних, при котором для каждого элемента из рассматриваемого множества рассчитывается степень его принадлежности каждому из кластеров [3].
Алгоритм данного метода состоит из следующих шагов:
1. Задать случайным образом с центров кластеров cj ,j=1..c.
2. Рассчитать матрицу принадлежности элементов к кластерам r. В случае нормального распределения:
4. Рассчитать функцию потерь (например, исходя из принципа максимального правдоподобия). В случае нормального распределения функция потерь будет равна:
5. Если значение функции потерь уменьшается, то повторить цикл с п.2.
Метод нечетких c-средних имеет ограниченное применение из-за существенного недостатка — невозможность корректного разбиения на кластеры, в случае когда кластеры имеют различную дисперсию по различным размерностям (осям) элементов, например, когда кластер имеет форму эллипса (рис.1).
Иерархическая кластеризация - это подход, в котором один кластер вложен
в другой, образуя тем самым последовательность или иерархия. Иерархическая кластеризация включает в себя два класса методов (рис.2).
Агломерационная кластеризация выполняется снизу вверх. Каждая точка данных обрабатывается как один объект, а затем объединяется с другими объектами, образуя кластер. Затем эти кластеры последовательно объединяются, пока не будет получен один большой кластер. Агломерационный
алгоритм имеет временную сложность O(n2). Если кластеры имеют одинаковый объем, наилучшим вариантом является метод полной связи.
Разделительная кластеризация сначала помещает все объекты в один кластер, а затем выполняется последовательное разбиение на отдельные кластеры. Эти итерации выполняются до тех пор, пока не будет получено нужное количество кластеров.
Иерархическая кластеризация имеет следующие ограничения:
·
невозможно представить отдельные кластеры с такие же шаблоны выражения;
·
по мере того, как
кластеры растут
в
размере, фактическое
выражение модели становятся менее актуальным;
·
сложность квадратична;
·
занимает больше времени, чем нечеткая кластеризация с-среднее.
Предлагается новый подход к кластеризации, который объединяет работу представленных ранее алгоритмов. Он, сочетая в себе функциональность двух вышеупомянутых методов,
устраняет их недостатки, что приводит к лучшим результатам
работы.
Шаги алгоритма гибридного подхода представлены ниже.
1.
Загрузить набор данных.
2.
Применить
нечеткую
кластеризацию
c-средних
и
найти
кластеры
на основе
данных нечетких членов.
3.
Отфильтровать данные.
4. Полученные кластеры не являются адекватными, и многие точки данных все еще не принадлежат ни одному из кластеров, и качество кластеров также низкое. Поэтому проверить сформировано ли необходимое количество кластеров, и все ли точки данных были покрыты.
5.
Если результатом п.4 является ответ «нет», то применить иерархический алгоритм кластеризации.
Пропускаем
данные, которые находятся в сформированных с помощью нечеткого алгоритма c- средних кластерах. Иерархический алгоритм создаст новые кластеры в соответствии со своим алгоритмом.
6.
Сохранить все точки на карте хешей для удаления избыточности в сформированных кластерах.
Извлечь точки данных обоих алгоритмов и организовать объединение кластеров, полученных с помощью обоих алгоритмов.
Предложенный подход гибридной кластеризации
реализован
с использованием технологии MapReduce и программного обеспечения Apache Hadoop. Произведено сравнение алгоритмов кластеризации, для чего были использованы данных о погоде NCDC [5]. Полученный результат позволяет говорить о недостатках и достоинствах применяемых методов. Метод нечеткого c-среднего генерирует только несколько кластеров, а также требует предварительного определения количества кластеров, которые должны быть сформированы. Иерархическая кластеризация является динамической по своей природе и генерирует больше кластеров, чем алгоритм нечетких с-средних, но выполняет много итераций из-за необходимости принятия многих решений о слиянии и разделении. В результате гибридного подхода мы находим максимальное количество кластеров для входных данных, и сформированные кластеры имеют очень хорошее качество, что дает наиболее точные результаты. Предложенный гибридный подход обеспечивает эффективный способ кластеризации, показывающий более высокую точность.
Список литературы
1.
Воронцов К.В. Алгоритмы кластеризации и многомерного шкалирования. Курс лекций. МГУ,2007. [URL: http://www.ccas.ru/voron/download/Clustering.pdf]
2. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН,1999.
3. Тараскина А.С. Нечеткая кластеризация по модифицированному методу c-средних и ее применение для обработки микрочиповых данных // проблемы
интеллектуализации и качества систем информатики. – С. 217-228. [URL: https://www.iis.nsk.su/files/articles/sbor_kas_13_taraskina.pdf]
4. Hierarchical Cluster Analysis [URL: http://uc-r.github.io/hc_clustering]
5. National Climatic Data Center [URL : ftp://ftp.ncdc.noaa.gov/pub/data/ghcn/daily/ ghcnd-all.tar.gz]
