|
Когда количество объектов п невелико по сравнению с количеством элементов мониторинга q использование кодирования хромосом нечеткими степенями принадлежности объектов центрам кластеров позволяет сократить затраты времени на получение искомого результата нечеткой кластеризации по сравнению с использованием кодирования хромосом координатами центров кластеров. Это объясняется тем, что при выполнении операции скрещивания хромосомы-родители обмениваются только нечеткими степенями принадлежностей объектов центрам кластеров, а не координатами центров кластеров, что позволяет избежать потери возможно полезной информации о расположении центров кластеров. Если количество объектов п невелико по сравнению с количеством элементов мониторинга q (количеством координат центра кластера), то попытка перевести некоторый i -й объект (/ = \,п) из j -го кластера в / -й за счет изменения его нечетких степеней принадлежности центрам кластеров может оказаться более эффективной, чем попытка изменения координат всего кластера. Кроме того, вычислительная сложность расчета одной хромосомы при использовании кодирования хромосом нечеткими степенями принадлежности объектов центрам кластеров ниже, чем при использовании кодирования хромосом координатами центров кластеров, что может дать некоторый выигрыш по времени (таблица 2.6). В то же время даже когда количество объектов п превышает количество элементов мониторинга q всего в 4 раза (например, при выполнении кластеризации 20 объектов по 5 элементам мониторинга) эффективность использования кодирования хромосом нечеткими степенями принадлежности объектов центрам кластеров по сравнению с использованием кодирования хромосом координатами центров кластеров снижается в 4-5 раз, то есть процент «хороших» генераций составляет всего 10-20%. Таблица 2.6 Оценка вычислительной сложности расчета одной хромосомы Кодирование хромосомы координатами центров кластеров Кодирование хромосомы степенями принадлежности объектов центрам кластеров 11 ■с q •п + (б •с -п —q —2 *п)-с 8' с -q-n + f i c n q n ) -с 121 |
к другому. При этом будет наблюдаться плохая (медленная) сходимость к оптимальному решению (с минимальным значением индекса Се Бени по формуле (4.36)). Это объясняется тем, что при выполнении операции скрещивания и мутации новые хромосомы могут формально описывать разбиение на заданное количество кластеров с = с , а реально на меньшее количество кластеров. В результате такие хромосомы будут признаваться «нежизнеспособными» и будут отбрасываться в процессе отбора. 4.4 Комбинирование FCM-алгоритма на основе нечеткнх множеств первого типа и генетического алгоритма Комбинирование FCM-алгоритма на основе F1MT1 и ГА позволяет значительно уменьшить количество поколений G , необходимое для получения адекватных результатов нечеткой кластеризации, а, следовательно, повысить эффективность применения ГА. Но и в этом случае существенное влияние на результаты кластеризации оказывает то, что в процессе выполнения операций скрещивания и мутации могут быть сгенерированы «нежизнеспособные» хромосомы. Предлагаемый комбинированный метод нечеткой кластеризации (КМНК) предполагает поочередное выполнение FCM-алгоритма на основе НМТ1 и ГА [98, 99, 118, 122]. Комбинированный метод нечеткой кластеризации может быть использован как при кодировании хромосом координатами центров кластеров, так и при кодировании хромосом нечеткими степенями принадлежности объектов центрам кластеров. При этом предлагается новый подход к формированию расширенной популяции. В случае кодирования хромосомы координатами центров кластеров возможны два варианта реализации ГА: без дополнительного пересчета функций принадлежности (ДПФП) и с ДПФП. 277 вания хромосом координатами центров кластеров с Д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 В то;же время даже когда количество объектов п превышает количеством критериев q всегов 4 раза (например, при выполнении кластеризации 20 объектов по 5 критериям)'эффективность использования кодирования хромосом нечеткими степенями принадлежности объектов центрам, кластеров по; равнению с использованием кодирования хромосом координатами центров ■кластеров* с ДПФП снижается в 4-5 раз, го есть процент «хороших» генераций составляет всего 10 -2 0 %. При!увеличении количества объектов п эффективность использования кодирования хромосом степенями принадлежности: объектов центрам кластеровснижаетсяеще больше, так как изменение нечетких степеней'принадлежности одного объекта.мало влияет на результаты кластеризации с использованием. FCM-алгоритма на основе. НМТ1. (в первую очередь на оценку координат центров кластеров). В этом; случае эффективность данного способа кодирования будет целиком зависеть от того, является ли начальная популяция хромосом «хорошей» (то есть.насколько «хорошо» закодированы хромосомы нечеткими степенями, принадлежности центрам кластеров, и, соответственно, насколько хорошо объекты разбиты на кластеры)/ Следует: отметить, что эффективность, применяемого способа кодирования хромосом зависит И от настройки параметров. ГА —выбора*коэффициентов скрещивания,, мутации, количества точек скрещивания-и количества генов, подвергаемых мутации. В классическом ГА обычно: используется-одноточечное скрещивание, а количество мутирующих генов не превышает Ю20% от общей:длины хромосомы. При этом коэффициенты,скрещивания мутации составляют 0,7-0,8 . Однако при решении каждой конкретной задачи нечеткой кластеризации необходимо осуществлять индивидуальный подбор параметров ГА, которые бы могли обеспечить получение адекватных результатов кластеризации за разумное время. Например, если количество объектов кластеризации я , количество критериев q и количество кластеров с равны. 10, 5 й 4 соответственно, а количество мутирующих генов составляет 10 %, то при выполнении операции 285 |