|
вычисления матрицы расстояний d 2 (j = l , c ; / = 1,и) необходимо выполнить (3 •q 1)*с •и арифметических операций. Следовательно, для вычисления одного значения одной степени принадлежности объекта центру кластера необходимо дополнительно выполнить при расчете знаменателя формулы (2.31): {с —l) операцию сложения, с операций деления и с операций умножения и еще одну операцию деления, то есть 3 •с арифметических операций, а для вычисления всех значений степеней принадлежностей объектов центрам кластел ров следует дополнительно выполнить 3-е •п арифметических операций. Таким образом, расчет всех значений степеней принадлежностей объектов центрам кластеров при выполнении одной итерации классического FCMалгоритма на основе НМТ1 требует выполнения 3 -с2 •п + (3 ■q 1)*с •п арифметических операций. 2.10.3 Анализ сложности вычислений при различных способах кодирования хромосом Сравним вычислительную сложность при расчете одной хромосомы, закодированной координатами центров кластеров и степенями принадлежности объектов центрам кластеров без использования дополнительной переменной для вычисления гг(*,) [63]. Как видно из таблицы 2.13, сложность расчета хромосомы, закодированной степенями принадлежности объектов центрам кластеров, ниже сложности расчета хромосомы, закодированной координатами центров кластеров на (з-с •q *п п *с +3*с2 •п) арифметических операций. 9 Как показывают результаты расчетов при реализации комбинированного метода нечеткой кластеризации с различными способами кодирования, приведенные в п. 2.9.1, кодирование хромосом координатами центров, несмотря на некоторое увеличение вычислительной сложности (и, соответственно, временных затрат), обеспечивает уменьшение количества поколений, необходимого для получения «лучшего» решения, и, самое главное, увеличивает процент генерации лучшего значения функции соответствия. 135 |
вания хромосом координатами центров кластеров с Д11ФГ1 приносит существенный выигрыш по проценту генераций лучшего значения функции соответствия'при некотором увеличении времени реализации ГА. Более подробный анализ оценки эффективности способов кодирования хромосом приведен в ПРИЛОЖЕНИИ 4 (п. П.4.6). В ряде случаев когда количество объектов п невелико по сравнению с количеством критериев q —использование кодирования хромосом нечеткими степенями принадлежности объектов центрам кластеров позволяет сократить затраты времени на получение искомого результата нечеткой кластеризации по сравнению с использованием кодирования хромосом координатами центров кластеров с ДПФП. Это объясняется тем, что при выполнении операции скрещивания хромосомы-родители обмениваются только нечеткими степеням и-принадлежностей объектов центрам кластеров, а не координатами центров кластеров, что позволяет избежать потери возможно полезной информации о расположении центров кластеров. Если количество объектов п невелико по сравнению с количеством критериев q (количеством координат центра кластера), то попытка перевести некоторый г'-й объект (г = 1,и ) из j -го кластера в г'-й за счет изменения его нечетких степеней принадлежности центрам кластеров может оказаться более эффективной, чем попытка изменения координат всего кластера. Кроме того, вычислительная сложность расчета одной хромосомы при использовании кодирования хромосом нечеткими степенями принадлежности объектов центрам кластеров ниже, чем при использовании кодирования хромосом координатами центров кластеров с ДПФП, чго может дать некоторый выигрыш по времени. Кодирование хромосомы координатами центров кластеров без ДПФП Кодирование хромосомы координатами центров кластеров о ДПФП Кодирование хромосомы степенями при!шдлсжности объектов центрам кластеров 11 -c-q-n + +( 3 c n q 2 n ) c 11 -c-q-/i + + ( 6 c n q 2 n ) c 8 -с ■q ■п + + (3 •с ■п q —и) •с 284 П.4.6.2 Оценка сложности вычислений степеней принадлежности объектов центрам кластеров П ри т = 2 ф орм ула (4.6): 1 /=1 dA \^ и у где d p = _ v; )' ] ’ / = 1'>Я:> j = 1, с ; / = 1, « ; п рин и м ает вид: н , (*,) = i f i ,-i V«„• Т аким образом , для вы числен ия зн ачен и й степ ен ей прин адлеж ностей объектов центрам кластеров н еобходи м о п редварительн о вы числи ть м атри цу расстояний d jf , характеризую щ и х расстояни я м еж д у объ ектам и и центрам и кластеров. J (ля вы числен ия одн ой вели чин ы d i н еобходи м о вы п олни ть (q 1) операцию слож ения, q оп ераци й вы читан ия и q оп ераци й ум н ож ен и я, то есть (3 ■q 1) ариф м етических оп ераци й . Т о гд а д л я вы числен ия м атри цы расстояний d j, ( j = 1,с ; / = 1, п ) н еобходи м о вы п олни ть (3• с/ 1)• с • /? ариф м етических операций. Т огда д л я вы ч и слен и я одн ого зн ачен и я степ ени прин адлеж ности объекта центру кластера н еобходи м о д оп олн и тельн о вы п олни ть при расчете знам енателя ф орм улы (4.6) при т = 2 : (с 1) оп ерац и ю слож ен и я, с оп ерац и й деления и с операций у м н ож ен и я и ещ е одн у оп ерац и ю делен и я, то есть 3 •с ариф м етических оп ераци й . С ледовательн о, д л я вы числен ия всех зн ачен и й степеней принадлеж ностей объ ектов центрам кластеров сл едует доп ол н и тел ьно вы полнить 3 е 2 •п ари ф м ети чески х операций. Т аки м образом , расч ет всех зн ачен и й степеней п рин адлеж ностей объ ектов центрам кластеров при вы п олнении одной итерации кл ассического F C M -алгоритм а н а осн ове Н М Т1 требует вы полнения 3 •с 2 •п + (3 • q 1) • с •п ари ф м етически х операций. 378 при различных способах кодирования хромосом Сравним вычислительную сложность при расчете одной хромосомы, закодированной координатами ненаров кластеров без Д П Ф П и с ДП Ф П , а также при расчете одной хромосомы, закодированной степенями принадлеж ности объектов центрам кластеров без использования дополнительной переменной для вычисления (г/; {х, ))* (таблица П .4.14). Как видно из таблицы П .4.14, расчет одной хромосомы, закодированной координатами центров кластеров с ДП Ф П , сложнее расчета одной хромосомы, закодированной координатами центров кластеров без ДП Ф П , на 3 е 2 -п арифметических операций. Сложность расчета хромосомы, закодированной степенями принадлежности объектов центрам кластеров, ниж е сложности расчета хромосом, закодированной координатами центров кластеров без Д П Ф П и с ДПФП, на (3 c q n n c ) и (з-сq -п —п -с + 3 с ‘ -//) арифметических операций соответственно. Как показывают результаты расчетов для реализаций К М Н К с различными способами кодирования, приведенные в П .4.1, кодирование хромосом координатами центров кластеров с ДП Ф П , несмотря на некоторое увеличение вычислительной сложности (и, соответственно, временных затрат), обеспечивает уменьшение количества поколений, необходимого для получения «лучш его» решения, и, самое главное, увеличивает процент генерации лучш его значения функции соответствия. Кодирование хромосом степенями принадлежностей объектов центрам кластеров, хотя и имеет низкую вычислительную сложность, но является эф фективным только в случае небольш ого количества н объектов кластеризации, что на практике встречается довольно редко. Так как обычно с « п и q « n , сложность расчета одной хромосомы при любом способе кодирования можно оценить как o [ i r ). П.4.6.3 Анализ сложности вычислений 379 |