|
Таблица 2.13 Оценка вычислительной сложности расчета одной хромосомы Выполняемые расчеты Кодирование хромосомы координатами центров кластеров Кодирование хромосомы степенями принадлежности объектов центрам кластеров 1. Центры кластеров v; ( 5 n \ ) c q 2. Функции принадлежности и (х,) 3 -е 2 -л + \ ) с-п 3-С2 / 7 + (3-(/-1)-С-П 3. Центры кластеров (5 • п — l) • с • q 4. Функции принадлежности (г,) 3 • с2• п + (3 • q 1)*с • п Итого: 11 •с • q • п + (б • с •п q 2 *п) -с 8 •с •q -п + (3 •с -п q п) с Кодирование хромосом степенями принадлежностей объектов центрам кластеров, хотя и имеет низкую вычислительную сложность, но является эффективным только в случае небольшого количества п объектов кластеризации, что на практике встречается довольно редко. Так как обычно с « п и q « п, сложность расчета одной хромосомы при любом способе кодирования можно оценить как o{t22). 2.10.4 Оценка сложности вычислений некоторых показателей качества кластеризации Выполним оценку сложности расчета наиболее часто используемою показателя качества кластеризации индекса Се Бени ХВ по формуле (2.16) при т 2 и нечеткого общего гиперобъема FH по формуле (2.13) при т 2 . Выполним оценку сложности вычисления индекса Се Бени. Так как значения и}{xt), d \ и vy вычисляются при расчете функций принадлежности и координат центров кластеров, то для расчета индекса Се Бени необходимо дополнительно выполнить расчеты для вычисления числителя и знаменателя формулы. При расчете знаменателя сначала необходимо для расчета одной суммы выполнить (q l) операцию сложения, q операций вычитания и q операций умножения, то есть (3 •q 1) арифметических операций. Такие суммы необходимо вычислить для каждой пары центров кластеров v, и v, (у ^ / ) из с 136 |
при различных способах кодирования хромосом Сравним вычислительную сложность при расчете одной хромосомы, закодированной координатами ненаров кластеров без Д П Ф П и с ДП Ф П , а также при расчете одной хромосомы, закодированной степенями принадлеж ности объектов центрам кластеров без использования дополнительной переменной для вычисления (г/; {х, ))* (таблица П .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 некоторы х п о казател ен кач еств а к л астер и зац и и Выполним оценку сложности расчета наиболее часто используемого показателя качества кластеризации индекса Сс Бени Х В по формуле (4.36): х в = +— ----------^ ---------, n-m inY,(y[ v ' J /-1 где с количество клас теров; п количество объектов; q количество критериев; Uj (.г.) —Ф11 объекта д-( кластеру X -; v ‘j l -я координата центра j го кластера; х[ / -я координата / -го объекта; i = \ , п , j = 1, с ; t = l,c ; а также нечеткого общ его гиперобъема F H по формуле (4.29): F H = f j (dei{Rj ) ) i , j-1 ( a , v J C v , V j f R , ~ --------------------------------------------. i=\ где R , нечеткая ковариационная м атрица j -го кластера; uj {xj ) — Ф П объекта .v, кластеру X j ; vf вектор координат центра j -го кластера; х, вектор координат (оценок по критериям) i -го объекта; det{R j) определитель нечеткой ковариационной матрицы у -г о кластера; п количество объектов; с количество кластеров; / = 1,/г, j = I , с . Выполним оценку сложности вьгчгисления индекса Се Бени. П ерепиш ем формулу (4.36) в виде: tik i* .)? < ХВ = у° ‘ 1=1 -----------------------. v ') 2 1=1 Т ак как значения и (х,), d f; и vI вычисляются при расчете функций принадлежности и координат центров кластеров, то для расчета индекса Се П.4.6.4 Оценка сложности вычислений 381 Бени необходимо дополнительные расчеты для вычисления числителя и знаменателя формулы. При расчете знаменателя сначала необходимо для расчета одной суммы выполнить (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 |