|
Порядок сложности цикла по J ( ф •N + М •Z2 •l )I2 •j), (4.5) * а где J количество сигналов в системе. Таким образом, порядок сложности программы моделирования в режиме обучения равен Zo6 = o ((2-N + M -Z2 -l )-I2 *j ) ’ (4.6) Аналогично определяем порядок сложности программы моделирования в режиме классификации: * = О((2 •NK + NK ■Z2)-12 •j), (4.7) где NK длина контрольной выборки, предъявляемой для классификации. Численные значения порядков сложности 2об и 2^, для исходных данных одного из экспериментов, представленного в приложении 3 будут иметь следующие значения: 1= 2, J = 2, N = 104, М = 103, L = 10, NK = 103, Z = 2, Еоб =0.96-10б, 1 ^ = 0.096-106, 2 = 1.056-106. 1 v 4.5 Сравнительный анализ показателей качества и сложности НК МСОК и алгоритма непараметрической классификации по методу к ближайших соседей * Целью данного подраздела является объективное сравнение характеристик предлагаемых алгоритмов и известными алгоритмами непараметрической классификации. Оставляя за рамками данной работы анализ известных алго-Г 141 |
I Анализ полученных результатов приводит к следующим выводам. 1) Минимум вероятности ошибки классификации достигается при росте объема обучающей выборки; 2) Применение алгоритма классификации с коррелированными опорными процессами целесообразно только в случае критически малых объемов обучающих и контрольных выборок. При увеличении времени обучения и распознавания предпочтительно использование алгоритма классификации с некоррелированными опорными процессами, требующего меньших временных затрат на формирование отсчетов признаков при той же вероятности ошибки классификации; 3) Коэффициент сжатия информации о процессе для графиков на рис. 4.4, 4.5 равен к = 1000, количеству точек, по которым строится оценка признака. 122 . 4.3. Оценка вычислительной сложности программы моделирования Оценку вычислительной сложности программы моделирования работы НКСП произведем в соответствии с методикой, предложенной в [73]. Основной задачей будет являться определение порядка сложности алгоритма. Порядок сложности мажоранта функции, определяющей количество арифметических и логических операций, при выполнении программы. Для структурной схемы на рис. 4.1 расчет порядка сложности начинаем с внутренних циклов. Порядок сложности внутреннего цикла по п составляет: 0(2 -N), . (4.2) где o(f(x)) обозначает мажоранту функции f(x) (читается О большое); N длительность обучающей реализации. Порядок сложности второго цикла (по L): o(m -(z2)-l где М длительность интервала, на котором вычисляются оценки признаков; L количество обучающих последовательностей; Z размерность вектора z. Порядок сложности цикла по I: (4.3) o((2-N + M-Z2-Ь)-Г), (4.4) где I размер вектора признаков. Порядок сложности цикла по J: o((2-N + M*Z2-l)■I2-j), (4.5) где J количество сигналов в системе. Таким образом, порядок сложности программы моделирования в режиме обучения равен 2, =0((2-N + M-Z2-L)-I (4.6) Аналогично определяем порядок сложности программы моделирования в режиме классификации: 123 E2 = o ((2-NK + NK-Z2)-I2-JJ, (4.7) где NK длина контрольной выборки, предъявляемой для классификации.■ 1 Численные значения порядков сложности Еv и Е2 для исходных данных1 одного из экспериментов, представленного в прил.З будут иметь следующие значения: 1= 2, J = 4, N = 10% М =103, L = 10, NK = 10J, Z = 2, Ej =0,96-10°, S, = 0,096-106, E = 1,056-106. 4.4. Сравнительный анализ показателей качества и сложности НКСП и а горитма непараметрической классификации по методу к ближайших соседей Целью данного подраздела является объективное сравнение характеристик предлагаемых алгоритмов и известными алгоритмами непараметрической классификации. Оставляя за рамками данной работы анализ известных алгоритмов непараметрического распознавания, остановимся на методах непараметрическойI S оценки плотности вероятности, то есть методах, позволяющих аппроксимировать неизвестную функцию плотности вероятности с целью ее дальнейшего использования для построения оптимальных решающих правил [96]. В литературе [87] достаточно подробно описаны методы оценивания плотности вероятности и их использования для построения оптимальных решающих правил. Среди них: методы оценки Парзена, метод к ближайших соседей, метод гистограмм, методы разложения по базисным функциям. Часто предпочтение отдают методам ядерных оценок Парзена за их высокую точность восстановления функций плотности, однако вычисление ядра для каждого объекта требует значительного времени. Остановимся на модификации оценки Парзена, которая гораздо проще с вычислительной точки зрения. Такая простота вычислений достигается за счет того, что мы ищем не оценки плотностей вероятности сами по себе, а их локальную оценку, то есть нас интересует классификация объектов, порождаемых двумя распределениями, и нам достаточно решить лишь вопрос о том, какая из двух плотностей вероятности больше в данной точке. В методе Парзена каждый объект является центром, вокруг которого строится некоторое фиксированное ядро. Похожую оценку можно получить иначе, следующим образом. Используя выборку, состоящую из N объектов, находят расстояние г от точки X до k-го ближайшего к X объекта (k-го ближайшего соседа). Для измерения "близости" можно воспользоваться любой подходящей метрикой. оценки плотности вероятности в точке X можно принять eN(X)=-k_1 1 N A(k,N,X) (4 t A(k,N,X)объем множества всех точек, расстояния которых до X меньше расстояния используется евклидово представляет собой гипершар радиуса 126 Структурная схема алгоритма программы моделирования работы классификатора (к ближайших соседей) врежиме обучения Ввод отсчетов вх. сигналов х(п).• * Определение величин: 1-размерность вектора признаков; J количество сигналов в системе; N общая длина обучающей выборки; NK общая длина контрольной выборки; М длина интервала наблюдения; L кол-во объектов наблюдения, L=N/M; К кол-во ближайших соседей. П р о ц е д у р а н а х о ж д е н и я спектральных составляющих (алгоритм БПФ) . На выходе массив S^co), HN-N/2. Процедура вычисления ог^енки одного признака энергии сигнала в полосе частот [ccr, coj+1J. нм Ej=£(Sk)2НМ=М/2. Ш=1 К процедуре классификации Рис. 4.8, цикла HM2-L + N) где количество сигналов (4 обучения • • • I • образом, порядок сложности программы моделирования в режиме НМ N) 17) Аналогично определяем порядок сложности программы моделирования классификации НК2 NK 2NK 18) NK длина контрольной выборки, предъявляемой для классификации значения порядков сложности 2! и 22 для исходных данных одного из экспериментов, представленного в прил.З будут иметь следующие значения: 1= 5, J = 4, N = 10% М =103, L= 10, NK= 10% Ej = 50,05-10% I 2 = 5,04-10% E = 55,09-10% |