Проверяемый текст
Демидова, Лилия Анатольевна. Развитие методов теории нечётких множеств и генетических алгоритмов для задач поддержки принятия решений в условиях неопределённости (Диссертация 2009)
[стр. 74]

2.1 Алгоритм нечетких с-средних иа основе нечетких множеств первого типа Задача нечеткой кластеризации заключается в нахождении нечеткого разбиения или нечеткого покрытия исходного множества объектов, которые образуют структуру нечетких кластеров, присутствующих в анализируемых данных.
Эта задача сводится к нахождению степеней принадлежности объектов искомым нечетким кластерам, определяющим в совокупности нечеткое разбиение или нечеткое покрытие исходного множества объектов
[39, 76, 104, 130].
В основе наиболее известного алгоритма, реализующего нечеткую кластеризацию, алгоритма нечетких с*-средних (FCM-алгоритма), предложенного Дж.
К.
Данном (J.C.
Dunn) в 1976 г., лежит метод неопределенных множителей Лагранжа [150, 151].
В 1980 г.
Дж.
К.
Беждек (J.C.
Bezdek) теоретически доказал сходимость этого алгоритма, а в 1981 г .
обобщил
его на случай произвольных нечетких многообразий [136, 137].
Классический FCMалгоритм основан иа использовании нечетких множеств первого типа (или просто нечетких множеств) Н М ТI.
Пусть X = {х[9х29...,хп} множество объектов кластеризации, а P = {Pl9P2,...9Pq) множество признаков, каждый из которых количественно представляет некоторое свойство или характеристику объектов конкретной проблемной области (например, элемент мониторинга), где п —натуральное число, определяющее общее количество объектов кластеризации; q натуральное число, определяющее общее количество элементов мониторинга.
Пусть, кроме того, для каждого объекта xt (i = \,п) с использованием некоторой количественной шкалы определены все оценки по элементам мониторинга из множества Р .
Каждому объекту xi можно поставить в соответствие вектор значений оценок объекта по элементам мониторинга: xt ={х]9х*,..,9х ?), где xj количественное значение оценки, представленное действительным числом (xj e R ) , по элементу мониторинга р, е Р (/ = 1,д) 74
[стр. 100]

меративные) алгоритмы, в,которых объекты объединяются во всё более и более крупные кластеры [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

[стр.,250]

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

[стр.,251]

Пусть для каждого объекта xj (/ = 1,/г) с использованием некоторой количественной шкалы определены все оценки по критериям из множества Р .
Тогда каждому объекту х( можно поставить в соответствие вектор значений оценок объекта по критериям: xt = (х],х: ,...,х?), где xj количественное значение оценки, представленное действительным числом (xj е Л ), по критерию Pi е Р (l = l,q) для объекта данных xt е X .
Для того чтобы результаты нечеткой кластеризации имели содержательную интерпретацию, адекватную проблеме нахождения нечетких кластеров, множество критериев должно выбираться так, чтобы все xj измерялись в шкале интервалов или отношений [117, 202].
В дальнейшем множество объектов кластеризации X будет отождествляться с НМ объектов кластеризации X , элементам которого сопоставлены некоторые ФП объектов нечетким-кластерам.
В общем виде задача нечеткой кластеризации имеет вид: определить такое нечеткое разбиение R {x) = { X , 1X .
с= X ) или нечеткое покрытие /(Л ')= {X.
\Х у.
<^Х) множества объектов кластеризации X на заданное число с нечетких кластеров X , (у е {2,..., с}), которое обеспечивает экстремум некоторой целевой функции f( R ( x ) ) среди всех нечетких разбиений или экстремум некоторой целевой функции f ( l ( X ) ) всех нечетких покрытий [117, 284, 305, 309].
Нечетким покрытием НМ X называется система нечетких подмножеств Г{Х)={Х.
\ Х , ^ Х ) , если выполняется условие: и А ', = X ( Xj е /) .
Нечетким разбиением НМ X называется система нечетких подмножеств R(X)= {XJ X j с X } , если выполняются условия: и Х , = Х ( X J e R ) i hc < 1, С = Х 1г \ Х я 9 (ЧХп Х ше Я ) 9 j где hc высота НМ С .
Пусть искомые нечеткие кластеры представляют собой НМ X 9 образующие нечеткое покрытие множества объектов кластеризации X .
251

[Back]