Монотетические и политетические методы

Большинство алгоритмов являются политетическими, в которых схожесть объектов определяется при одновременном рассмотрении всех их характеристик. При сравнении.

'Jain A., Murty М., Flynn Р. Op. cit.

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

Методы четкой и нечеткой кластеризации.

Четкие методы кластеризации разбивают исходное множество объектов на несколько ненересекающихся подмножеств. При этом любой объект принадлежит только одному кластеру. Нечеткие методы кластеризации позволяют одному и тому же объекту принадлежать одновременно нескольким (или даже всем) кластерам, но с различной степенью принадлежности. Нечеткая кластеризация во многих ситуациях более «естественна», чем четкая, например для объектов, расположенных на границе кластеров^[1].

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

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

Рис. 18.1.2. Таксономия методов кластеризации.

Далее приведем краткое описание основных особенностей методов кластеризации^[2].

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

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

Современным масштабируемым агломеративным методом является CURE — Clustering Using REpresentatives, который выполняет иерархическую кластеризацию с использованием выделенного набора репрезентативных точек кластера.

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

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

Алгоритм MST (.Algorithm based on Minimal Spanning Tree) опирается на использование теории графов, его целью является построение минимального остовного дерева, характеризующегося минимальной суммой весов входящих в него ребер, где веса ребер соответствуют расстоянию между объектами, подлежащими кластеризации. В построенном дереве удаляются ребра, имеющие наибольший вес (соединяющие самые несхожие объекты), в результате чего происходит формирование кластеров. На рис. 18.1.3 приведен пример кластеризации девяти точек в двумерном пространстве на три группы с помощью метода MST.

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

Одним из наиболее распространенных среди неиерархических методов за счет простоты понимания и удовлетворительного уровня результатов является метод k-means (k-средних).

Рис. 18.1.3. Использование метода MST для формирования кластеров Основная идея: объект относится к тому кластеру, расстояние до центра которого является наименьшим. Алгоритм выглядит следующим образом:

• 1) стандартизация данных;
• 2) выбираются k объектов, которые рассматриваются как центры кластеров;
• 3) итерация: объекты распределяются по кластерам (каждый объект относится к кластеру с ближайшим к этому объекту центром), производится перерасчет центров полученных кластеров. Итерации повторяются до момента стабилизации центров либо до достижения заранее установленного количества.

Достоинства: быстрота работы алгоритма, возможность анализа большого объема данных, простота использования, понятность и прозрачность алгоритма.

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

Среди неиерархических алгоритмов также популярен ЕМ-алгоритм (Expectation-Maximization). В нем вместо центров кластеров предполагается наличие функции плотности вероятности для каждого кластера с соответствующим значением математического ожидания и дисперсией. В рамках? А/-алгоритма ведется поиск параметров распределений (средние и стандартные отклонения) по принципу максимума правдоподобия^[3].

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

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

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

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

Достоинства: используется универсальный аппроксиматор — нейронная сеть, обучение сети без учителя, самоорганизация сети, простота реализации.

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

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

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

Важно!

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

Обратите внимание!

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

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

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

Обратите внимание!

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

• [1] Штовба С. Д.

  Введение

  в теорию нечетких множеств и нечеткую логику [Электронныйресурс] URL: http://matlab.exponenta.rU/fuzzylogic/bookl/l.php (дата обращения: 19.05.2014).

• [2] Более детально с особенностями методов можно ознакомиться в работах: Jain A., Muity М., Flynn Р. Op. cit. Р. 264—323; KoganJ., Nicholas СИ., Teboullc Л/. Grouping Multidimensional Data: Recent Advances in Clustering. Springer. 2006; Паклин H. Алгоритмы кластеризации на службеData Mining [Электронный ресурс] URL: http://www.basegroup.ru/library/analysis/clustcri-zation/datamining/ (дата обращения: 21.06.2014).
• [3] Паклин Н. Указ. сом.