кластеров, для чего требуется выполнить (Зg l) арифметических операций с { с l)/2 раз, так как С 2 = с!/(2!-(с 2) i)= с •{с 1)/2. Тогда для вычисления всех сумм следует выполнить с •(с 1)/2 •(3 •q 1) арифметических операций. Для определения минимальной суммы требуется выполнить c * (c -l)/2 операций сравнения. Для завершения вычислений знаменателя формулы требуется еще одна операция умножения. Следовательно, для вычисления знаменателя формулы количество необходимых арифметических операций равно: При вычислении числителя требуется выполнение 2 •с •// операций умопераций. Кроме того, необходимо выполнение еще одной операции деления для вычисления индекса Се —Бени. Таким образом, количество арифметических операций для вычисления индекса С е-Бени по формуле (2.16) равно: Выполним оценку сложности вычисления нечеткого общего гиперобъема F H . Количество арифметических операций, необходимое для вычисления всех ковариационных матриц RJ равно: (((д •п + (q —1+ q) •п) + ((/? 1)+ 2 •п) + (п —1+ /?)) + 1) •с . Вычисление определителя матрицы размера с х е в системе MATLAB 7.0 реализуется через LU -разложение, где L нормированная нижняя треугольная с х с -матрица, а С/ — верхняя треугольная с х с -матрица [24, 46]. Следовательно, вычисление определителя матрицы размера с х с требует вывычисления квадратного корпя оценивается сверху константой Т2. Тогда сложность вычисления нечеткого общего гиперобъема FH можно оценить как: ножения и (с/7-1) операций сложения, то есть ( З С ' П 1) арифметических + З'С /2+ 1= (2.32) полнения операций [7]. Пусть, кроме того, сложность |
Бени необходимо дополнительные расчеты для вычисления числителя и знаменателя формулы. При расчете знаменателя сначала необходимо для расчета одной суммы выполнить (q 1) операцию сложения, q операций вычитания и q операций умножения, то есть (3 •q l ) арифметических операций. Такие суммы необходимо вычислить для каждой пары центров кластеров и г. ( j * t ) из с кластеров, для чего требуется выполнить (3 ■q — \) арифметических операций с ( с 1) „ 2 с! c ( c l ) — 1----раз. так как С,. = — г = — -----. Iаким образом, для вычисле2 г 2 ! ( с 2 ) 2 ния всех сумм следует выполнить ——■(3 ■<7 1) арифметических операций. Для определения минимальной суммы требуется выполнить ° ——— операцию сравнения. Для завершения вычислений знаменателя формулы требуется еще одна операция умножения. В результате для вычисления знаменателя формулы требуется: : ( с 1) /, с •(с —1) , , c ( c l ) , — •(3 •q -1) + — ----+ 1= 3q --------+1 с 2 2 арифметических операций. При вычислении числителя требуется выполнение 2-сп операций умножения и (с •?г—l) операций сложения, то есть ( З с п l) арифметических операций. Кроме того, необходимо выполнение еще одной операции деления для вычисления индекса Се Бени. Таким образом, вычисление индекса Се Бени по формуле (4.36) требует выполнения: 3 •q •— ———+1 + (З -с -п l)+ 1= 3q •— ———+ 3 -с -п + 1= г 2Л \ х2( П А 4 — —---+ « + 1 = -^-с2 q ----с -q + 3 •с •п + 1 2 ) 2 2 = 3 •с арифметических операций. 382 Для оценки слож ности вычисления нечеткого общ его гиперобъема 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 |