((( *Г2 -1 . |
Для оценки слож ности вычисления нечеткого общ его гиперобъема F H по формуле (4.29) запиш ем нечеткую ковариационную матрицу j -го кластера при т = 2 : Z ( » , t O )2 ( * , v j R -------------------------------. I» , ) 2 .■-I Для вычисления всех ковариационных м атриц Ry следу ет выполнить: (((су -я + ( q 1+ q )п ) + ((« 1) + 2л )+ (и 1 + /г)) + !)• с арифметических операций. Вычиелетгие определителя матрицы разм ера с х с в системе M A TLA B 7.0 реализуется через L U -разлож ение, где L нормированная нижняя треугольная с х с -матрица, a U верхняя треугольная с х с -матрица [155]. Следовательно, вычисление определителя матрицы размера с х с требует выполнения Тх = о (с,,0"-’ 7)=<9(с2’31) операций [16]. П усть, кроме того, слож ность вычисления квадратного корня оценивается сверху константой Т2. Тогда сложность вычисления нечеткого общ его гиперобьем а F H можно оценить как: (((? 'ft G /—^ “? ) ' ^ 0 (О* —l) + 2• и) + ((w —l ) + / ? ) ) + l + 7j + Т2)с + + (с 0 = (3 •q п + 4 •п -I'J] + Т2) с 1 = (П.4.5) = 3 •q ■и ■с + 4 -п с + с -Ту + с -Т, 1 . Сравнивая формулы (П.4.4) и (П.4.5), мож но сделать вывод о больш ей вычислительной сложности расчета нечеткого общ его гиперобъема F H по сравнению со сложностью расчета индекса Се Бени Х В . П.4.6.5 Оценка сложности реализации генетического алгоритма Выполним оценку затрат памяти VBH через количество используемых О переменных [158] при реализации КМ НК при кодировании хромосом координатами центров кластеров с дополнительным пересчетом функций принадлежности и при кодировании хромосом степенями принадлеж ности объектов центрам кластеров. 383 Таблица П .4 .15 Оценки затрат памяти Переменная задачи Кодирование хромосом координатами центров кластеров с ДПФП Кодирование хромосом степенями принадлежности объектов центрам кластеров Массив оценок объектов n q n q Массив знамений функции соответствия попчляции хромосом Р Р -Массив значений функции соответствия расширенной популяции хромосом . 2 P + Rc P 2 P + Rc P > Массив вероятностей ' при оценке здоровья популяции Р Р Массив степеней принадлежности объектов центрам кластеров С *77*Рх \ с п Р Расширенный массив степеней принадлежности объектов центрам кластеров c n ( 2 P + Rc -Р) < с п (2 • Р + Rc -Р) Массив популяции хромосом с д -Р С П Р Массив расширенной' популяция хромосом c q ( 2 P + R c P) с ■п • (2 • Р + Rc ■Р) Массив для двух хромосом-роднтелей 2 c q 2 с п Массив родителей.» Rc • Р ■сq RC P -сп Массив отпрысков Rc ■P -с -q Rc -Р сп Массив сортировки значений функций принадлежности 2 ■P + R c P 2 P + Rc P Массив разбиений на кластеры n п Массив центров кластеров * для текущей хромосомы c q c q Массив степеней принадлежности объектов центрам кластеров для текущей хромосомы с •n с пt Массив центров кластеров для лучшей хромосомы c q c q Массив степеней принадлежности объектов центрам кластеров для лучшей хромосомы с -n с -п При оценке затрат памяти для КМНК для этих способов кодирования хромосом можно выделить общую «составляющую» затрат памяти V и «составляющие» затрат памяти V, и V2> определяемые способами кодирования хромосом: координатами центров кластеров с дополнительным пересчетом 384 функций принадлежности и при кодировании хромосомстепенями принадлежности объектов центрам кластеров соответственно. В таблице П.4.15 приведены оценки основных затрат памяти при реализации КМ Н К при кодировании хромосом координатами центров кластеров с дополнительным пересчетом функций принадлеж ности и при кодировании хромосом степенями принадлежности объектов центрам кластеров («жирным» шрифтом выделены переменные, для которы х затраты памяти различны). Общая «составляющ ая» затрат памяти V мож ет бы ть оценена как: V = // + «• q 42 •с ■q.+ 2 c n + 5 P + 3 R c P + 3 c n P + c n R c P , где п количество объектов кластеризации; q количество критериев; с количествокпастеров; Р размер популяции; R c коэф ф ициент скрещ ивания. П усть L n q . Т огда затраты памяти при кодировании степенями принадлеж ности объектов центрам, кластеров‘Превышают затраты памяти прикодировании координатами центров кластеров на следую щ ую величину: A V = V2 V t L -(2+ 3 •R c P + 3 P ) = ( n q ) ( 2 + 3 R ^ P + 3 P ) . Таким образом, чем больш е величина L = n q , тем больш е затраты памяти при кодировании степенями принадлеж ности объектов центрам кластеров; Следует отметить, что реализация классического FC M -алгоритма на основе НМТ1 требует значительно меньш их затрат памяти VFCM: основные затраты памяти связаны с созданием массива оценок объектов (n-q), массива центров кластеров (с ■q ), массива степеней принадлеж ности объектов центрам кластеров (с •п ) и массива разбиений на кластеры (и ), что соответствует первой и трем последним строкам таблицы П .4.15. Vгем ~ n q + c t i + cq + n. О днако, как уж е было отмечено в ГЛ А В Е 4, для получения адекватных результатов кластеризации требуется многократное выполнение классического FCM -алгоритма на основе НМ Т1. 385 |