BC/NW 2006, №1 (8): 13.3

ОСОБЕННОСТИ ИСПОЛЬЗОВАНИЯ МЕТОДОВ НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ ПРИ РЕШЕНИИ ПРАКТИЧЕСКИХ ЗАДАЧ БОЛЬШОЙ РАЗМЕРНОСТИ

М.В. Пряжевский, В.В. Топорков

(Москва, Московский энергетический институт (технический университет), Россия)

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

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

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

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

В итоге, для эффективного решения практических задач большой размерности с использованием методов нечеткой кластеризации, необходимо как минимум соблюдение следующих требований: 1) знание исследователем предметной области и 2) оптимизация и эффективное кодирование алгоритмов нечеткой кластеризации.