|
меративные) алгоритмы, в которых объекты объединяются во всё более и более крупные кластеры. Наиболее распространены восходящие алгоритмы кластеризации, работающие следующим образом. Сначала каждый объект считается отдельным кластером. Для одноэлементных кластеров с использованием какой-либо метрики (например, евклидовой метрики) определяется некоторая функция расстояния р[хп х X гДе и х . некоторые объекты. Затем выполняется процесс слияний. На каждой итерации вместо пары самых близких кластеров U и V образуется новый кластер W U u V . Расстояние от нового кластера W до любого другого кластера S вычисляется по расстояниям p(U,V)9 p(U9S) и p(V,S), которые к этому моменту уже должны быть известны. При вычислении расстояний p(U,V) обычно используются: алгоритм «ближнего соседа»; алгоритм «дальнего соседа»; алгоритм «средней связи» и др., приводящие, вообще говоря, к различным результатам кластеризации [46]. Известны алгоритмы иерархической кластеризации, в которых для представления объектов, оцениваемых по ряду критериев (элементов мониторинга) группой экспертов, используются мультимножества [30]. 1*6.5 Алгоритм четких с-средних Алгоритм четких с -средних предполагает, что кластеризация выполняется для объектов с количественными признаками [138, 150]. При этом считается, что количество кластеров с { с е {2,...,и 1}) задано заранее. Пусть Х = {х19х29...9х„} множество объектов кластеризации, а Р = {Р{,Р2,...9РЯ} множество критериев (элементов мониторинга), каждый из которых количественно представляет некоторое свойство или характеристику объектов конкретной проблемной области, где п натуральное число, определяющее общее количество объектов, q натуральное число, определяющее общее количество критериев (элементов мониторинга) [29, 39, 76]. Пусть, кроме того, с использованием некоторой количественной шкалы определены все 61 |
меративные) алгоритмы, в,которых объекты объединяются во всё более и более крупные кластеры [119]. При этом наиболее распространены восходящие алгоритмы кластеризации; работающие следующим образом. Сначала каждый объект считается отдельным кластером. Для одноэлементных кластеров с использованием какой-либо метрики, (например, Евклидовой) определяется некоторая функция расстояния p{xn xj), где х, и х} —некоторые объекты..Затем выполняется процесс-слияний. На каждой итерации вместо пары самых близких кластеров U и V образуется, новый кластер IV U и У . Расстояние от нового кластера W. до любого другого кластера S вычисляется по расстояниям p(U ,V), p(U ,S) и p(V,S), которые к-этому моменту уже должны быть известны; При вычислении расстояний p(i/,V ) обычно используются: алгоритм «блиЖнего соседа»; алгоритм «дальнего соседа»; алгоритм «средней связи»-и др., приводящие, вообще говоря, к различным результатам кластеризации [153]. 1.8.6 Алгоритм четких с -средних Алгоритм четких с-средних предполагает, что кластеризация выполняется для объектов с количественными признаками [116, 136, 202]. При этом считается, что число кластеров с (с е ( 2 l}) задано заранее. Пусть X { х 1,х2,...,хп} множество объектов кластеризации, а Р = {Р1,Р2,...,Р11} множество критериев, каждый из которых количественно представляет некоторое свойство или характеристику объектов конкретной проблемной области, где п натуральное число, определяющее общее количество объектов, q натуральное число, определяющее общее количество критериев [116]. Пусть для каждого объекта ( / —1,я) с использованием некоторой количественной шкалы определены все оценки по критериям из множества Р. Тогда каждому объекту xt можно поставить в соответствие вектор значений 100 3.5 Упорядочение объектов, представленных мультимножествами с использованием нечеткого метода Дельфы Метод упорядочения объектов с помощью мультимножеств основан на оценке их близости, по отношению к некоторому «идеальному» («антиидеальному») объекту в пространстве критериев. Этот метод допускает использование различных, в том числе и противоречивых, оценок по критериям для описания объектов [225, 228]. Рассмотрим задачу принятия, решения об упорядочении некоторого множества объектов X = {х,,.т,,...,л*п}. Отметим, что данное множество объектов может быть исходным или полученным в результате классификации исходного множества объектов, представленных мультимножествами, с использованием обобщающих решающих правил классификации, построение которых описано в п. 3.5. В простейшем случае эту задачу можно решить голосованием —рейтинг объекта (место в списке упорядочения) определяется количеством поданных за него голосов. Но в этом случае получается обобщенная оценка объекта «в целом» без какой-либо детализации по отдельным критериям. Более сложной является задача принятия решения об упорядочении объектов X = {хих2,...,х„} по ряду критериев Р = {Р1,Р2,...,Р1/} на основе каких-либо фактических показателей или экспертных оценок [264]. Данная задача является задачей многокритериального анализа. Пусть X = {.v,,.v2,...,x„} множество объектов; Р = {Р1,Р2,...,Р1)} множество количественных и качественных критериев, по которым оцениваются объекты, где п натуральное число, определяющее общее количество объектов, q натуральное число, определяющее общее количество критериев. Пусть, кроме того, каждый объект из множества X = {х,,х,,...,х„} оценивается т экспертами по всем критериям, то есть каждый г -й эксперт 231 4.1 Кластеризация объектов с использованием FCM-алгоритма иа основе нечетких множеств первого типа Обычно под задачей нечеткой кластеризации понимают нахождение нечеткого разбиения или нечеткого покрытия исходного множества объектов, которые образуют структуру нечетких кластеров, присутствующих в анализируемых данных. Эта задача сводится к нахождению степеней принадлежности объектов искомым нечетким кластерам, определяющим в совокупности нечеткое разбиение или нечеткое покрытие исходного множества объектов [117, 202, 273, 276, 282. 336]. Среди алгоритмов, реализующих нечеткую; кластеризацию, наиболее известен FCM-алгоритм (алгоритм нечетких с-средних), в основе которого лежит метод неопределенных множителей Лагранжа [273, 276]. Классический FCM-алгоритм основан на использовании нечетких множеств первого типа (или просто нечетких множеств) НМ Т1. Основные идеи классического FCM-алгоритма были сформулированы Дж. К. Данном (J.C. Dunn) в 1976 г. Первоначально FCM-алгори гм назывался нечетким алгоритмом ISODATA (fuzzy ISODATA) [315, 324]. В 1980 г. Дж. К. Беждек (J.C. Bezdek) теоретически доказал сходимость этого алгоритма, а в 1981 г. обобщил нечеткий алгоритм ISODATA на случай произвольных нечетких многообразий и предложил для этого алгоритма принятое в настоящее время название FCM-алгоритм (fuzzy с -means algorithm) [284, 286]. Пусть X (jfj,jc2,...,.vH} множество объектов кластеризации, а Р-{Р],Р2,...,Р(1} множество критериев, каждый из которых количественно представляет некоторое свойство или характеристику объектов конкретной проблемной области, где п натуральное число, определяющее общее количество объектов кластеризации (мощность множества объектов кластеризации), q —натуральное число, определяющее общее количество критериев. 250 |