Применение генетических алгоритмов для решения задачи нечеткой кластеризации в неевклидовых метриках

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

Рассмотрим разработанный на основе теории нечутких множеств FCM- алгоритм (Fuzzy Classifier Means).

Fuzzy Classifier Means-алгоритм. Пусть X — метрическое пространство, d X —* R — определенная на нем метрика. Х! = {х, х{, ..., xJm),j = 1, N — набор из Аг /«-мерных входных векторов признаков, сопоставляемых каждому объекту.

Реализация алгоритма приводит к необходимости вычисления расстояний между векторами. Если признаки х,х{, ...,xJm имеют различную размерность и/или измерены в различных шкалах, то расстояние между векторами станет абсолютно неинформативным. К примеру, х показывает возраст у'-ого покупателя в выборке, a х{ — величину его среднего дохода. Тогда при вычислении возраста, скажем, в секундах, доход покупателя, измеренный в долларах в месяц, не будет вносить практически никакого вклада в расстояние (меру различия) между покупателями как субъектами исследования. Если же возраст измерять в годах, то, напротив, именно этот показатель станет незначимым, так как в этом случае абсолютные значения, характеризующие возраст чаще всего не будут превосходить 100. Для решения подобной проблемы необходимо изначально провести процедуру стандартизации входных векторов. Сделать это можно, например, путем нормировки признаков следующим образом

среднеквадратическое отклонение.

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

Алгоритм требует, чтобы аналитик из каких-либо своих предположений предложил число кластеров К, на которое требуется разбить исходную выборку. На практике, как правило, разбиение выборки проводится на разное количество кластеров, а также на основе двух- или трехмерных проекций. В последующем из интуитивных соображений выбирают то разбиение, которое лучше всего удается интерпретировать с точки зрения специалиста в данной предметной области. Существуют также эвристические алгоритмы, помогающие определить наилучшее количество кластеров. Один из таких алгоритмов, реализованных в пакете MATLAB, представлен в монографии А. В. Леоненкова[3].

Будем предполагать, что искомые нечеткие кластеры представляют собой нечеткие множества, образующие нечеткое покрытие исходного множества объектов кластеризации. Обозначим через р. k € [0; 1] степень принадлежности вектора X' кластеру k. Тогда, чтобы кластеры образовывали нечеткое покрытие, необходимо потребовать выполнение условия:

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

В качестве центра каждого кластера, т.е. его типичного представителя, естественно выбрать средневзвешенное по степеням принадлежности, взятым с неким экспоненциальным весом q > 1, значение всех векторов Х т.е.

которое имеет смысл центра масс.

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

В качестве целевой функции, которую необходимо минимизировать, выберем сумму взвешенных расстояний от всех векторов XJ до всех центров кластеров с* где dj k = || Xj - Ск || — расстояние по некоторой метрике от ]-го вектора наблюдений до центра /е-ого кластера. Если в качестве метрики выбрать квадрат евклидова расстояния, т.е.

то получим следующую задачу математического программирования в которой на переменные ци,pv /c наложены следующие условия

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

Историческая справка

В 1980 г. Дж. К. Бсждек теоретически доказал сходимость итеративного алгоритма, позволяющего получить приближенное решение задачи (19.12). В 1981 г. он обобщил алгоритм на случай произвольных нечетких многообразий и предложил для этого алгоритма название нечетких С-средних1.

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

Составим функцию Лагранжа

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

  • 1 Леоненков А. В. Указ. соч.
  • 2 Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. Т. 1. М. : Физматлит, 2001. 680 с.

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

Заметим, что может возникнуть проблема — если центр какого-нибудь из кластеров совпадет с одним из наблюдений Х тогда для него djk = 0 и мы получим 0 в знаменателе. Обойти такую проблему очень легко — достаточно считать, что степень принадлежности этого объекта к данному кластеру равна 1, тогда степени принадлежности всех других объектов к данному кластеру будут равны 0. На самом деле метрика d- к зависит от центров кластеров cf, которые, в свою очередь зависят от р^, следовательно, найденные степени принадлежности в общем случае далеко не оптимальны и мы можем говорить лишь об итеративной сходимости алгоритма.

Формально данный алгоритм можно записать в следующей форме.

  • 1. Инициируем случайным образом степени принадлежности ij k так, чтобы они удовлетворяли всем ограничениям.
  • 2. Рассчитываем на их основе центры кластеров с?.
  • 3. Определяем расстояния dj k между всеми наблюдениями и центрами кластеров.
  • 4. По полученной формуле рассчитываем новые степени принадлежности с учетом сделанного замечания.
  • 5. Рассчитываем /(р^},..., р^), где р — номер текущей итерации.
  • 6. Возвращаемся к и. 2 и итеративно повторяем процесс до тех пор, пока не выполнено хотя бы одно из условий окончания вычислений:
    • а) |/(р^,..., Цд’к) -/(Ц|^,Рд/тс^)! < ?, где ? называется параметром сходимости алгоритма и задается аналитиком перед его началом;
    • б) число итераций превысило М — этот параметр также задается аналитиком перед запуском алгоритма.

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

  • [1] Штовба С. Д. Указ. соч.
  • [2] Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988. 176 с.
  • [3] Леоненков А. В. Нечеткое моделирование в среде Matlab и fuzzyTECH. СПб.: БХВ-Пе-тербург, 2003. 719 с.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >