|
На шаге 1 сложность вычислений для типичного алгоритма полной* сортировки оценивается как /7*(л-1). Так как сложность упорядочения по возрастанию оценивается по каждому элементу мониторинга, то она равна q 'П'{п —l). При п » q сложность вычислений можно оценить как о(п2). На шаге 2 сложность вычислений при оценке центра кластера такая же, как и в FCM-алгоритме на основе НМТ1 —о(п2). На шаге 3 выполняется сравнение различий между центром кластера и каждым объектом для поиска размещения центра кластера в множестве объектов, выполняемое в пределе п раз. При n » q сложность вычислений можно оценить как о(п2\ Следовательно, общая сложность трех шагов для одной итерации оценивается как о(п2). Если число требуемых итераций алгоритма Карника Менделя равно г, то сложность может быть оценена как г •о{п2\ Как известно, алгоритм Карника Менделя требует не более п итераций [165]. В этом случае общая сложность FCM-алгоритма на основе ИНМТ2 может быть оценена как п-о[п2У) 0 { п 2\ Поскольку при применении алгоритма Карника Менделя к типичным множествам объектов обычно достаточно выполнения 3-4 итераций итерационного алгоритма, то сложность FCM-алгоритма на основе ИНМТ2 обычно значительно меньше, чем о{пъ\ так как г « п [163]. Таким образом, сложность вычислений для FCMалгоритма на основе ИНМТ2 в общем случае иа порядок выше, чем в FCMалгоритме на основе НМТ1. 3,2 Проблема выбора показателя качества кластеризации на основе интервальных нечетких множеств второго типа Как показал анализ, при оценке качества кластеризации с использованием FCM-алгоритма иа основе ИНМТ2 применение в качестве показателей 161 |
Порядок вычислений для итерационного алгоритма Карлика Менделя может быть представлен следующими тремя шагами: 1. Упорядочение /-х индексов (/ = !,«) множества объектов по возрастанию значений оценок по каждому критерию / (/ = 1,q). 2. Оценка центра кластера на основе нижних и верхних ФГ( объектов. 3. Позиционирование центра кластера в множестве объектов. Fla шаге 1 сложность вычислений для типичного алгоритма полной сортировки оценивается как п ■(п 1). Сложность упорядочения по возрастанию также оценивается по каждому критерию. Следовательно, сложность равна q ■п ■(п 1). При n » q сложность вычислений можно оценить как о(п2). FTa шаге 2 сложность вычислений при оценке центра кластера такая же, как и в FCM-алгоритме на основе FIMT1 о(п2). На шаге 3 требуется сравнение различий между центром кластера и каждым объектом для поиска размещения центра кластера в множестве объектов, которое в пределе выполняется п раз. При n » q сложность вычислений можно оценить как о(п2). Таким образом, общая сложность трех шагов для одной итерации оценивается как о(п2). Если число требуемых итераций алгоритма Карника Менделя равно г , то сложность может быть оценена как г ■0(п2). Известно, что алгоритм Карника Менделя требует не более и итераций [338]. Тогда общая сложность FCM-алгоритма на основе ИНМТ2 может быть оценена как п ■о (л 2)= о(«3). Однако, при применении алгоритма Карника Менделя к типичным множествам объектов обычно достаточно выполнения 3-4 итераций итерационного алгоритма. Сложность FCMалгоритма на основе ИНМТ2 обычно значительно меньше, чем о(п'), так как г « а 1336]. Таким образом, сложность вычислений для FCM-алгоритма на основе 11FIMT2 в общем случае на порядок выше, чем в FCM-алгоритме на основе HMTJ. Однако это может рассматриваться как малая цена за получение более лучших результатов кластеризации. 350 |