|
147 Рош 0.5 0.4 0.3 0.2 0.1 0 2 3 4 5 6 7 8 9 10 11 12 13 14 п Рисунок 4.8 Зависимость оценок суммарных вероятностей ошибки классификации от числа объектов обучения по классам по методу k-ближайших соседей Произведем оценку вычислительной сложности программы моделирования работы классификатора по методу к ближайших соседей в соответствии с методикой, использованной в п. 4.4. Определим порядок сложности алгоритма. Для структурной схемы на рисунке 4.6 расчет порядка сложности начина4 ем с внутренних циклов. Порядок сложности внутреннего цикла по I составляет: 20(1НМ ), (4.14) где НМ = М/2 половина длины интервала наблюдения. Порядок сложности второго цикла (по L): 0(1 •НМ2 •L + N ■log. N), (4.15) где N общая длина обучающей выборки.4 Порядок сложности цикла по J o (l•НМ2 •L + N •log2n )-J, (4.16) |
125 сравнение показателей эффективности и сложности этих алгоритмов и разработанных алгоритмов нельзя, так как в структуру алгоритмов, представленных на рис. 4.1 и 4.2 заложены процедуры формирования классификационных признаков, разработанные в главе 3. Поэтому необходимо сравнивать алгоритмы работы НКСП в целом, то есть, включая модули формирования признаковых про-s. странств, обучения и принятия решений. Для того чтобы избежать необходимости анализа эффективности признаков, используемых "эталонным" классификатором, остановимся на наиболее часто используемом врачами-элеКтроэнцефалографистами преобразовании исходных сигналов спектральном [42, 43]. Большинство диагностических аппаратнопрограммных комплексов использует спектральное преобразование исходных сигналов для получения набора классификационных признаков. Методы вычисления таких признаков давно известны, хорошо разработаны и апробированы вI ■ практически используемых устройствах [77]. Поэтому представляется целесообразным воспользоваться готовыми алгоритмами формирования признаковых пространств, например, на основе вычисления спектральной плотности мощности сигнала в полосах частот, приведенными в [77, VI.2]. С целью получения количественных соотношений, устанавливающих зависимость эффективности непараметрического классификатора, работающего по методу к ближайших соседей, от временных параметров системы было поведено цифровое моделирование. Методом статистических испытаний были получены зависимости вероятности ошибки классификации от количества объектов обучения при фиксированном общем объеме обучающей выборки и с использованием тех же обучающих и контрольных статистик, которые были задействованы в статистическом эксперименте с разработанной моделью НКСП. Структурная схема алгоритма классификации представлена на рис. 4.8, 4.9, графики зависимости Рош(п) нарис. 4.10 [21]. Произведем оценку вычислительной сложности программы моделирования работы классификатора по методу к ближайших соседей в соответствии с методикой, использованной в п. 4.3. Определим порядок сложности алгоритма. Для структурной схемы на рис.4.8 расчет порядка сложности начинаем с внутренних циклов. Порядок сложности внутреннего цикла по i составляет: (4.14) где НМ = М / 2 половина длины интервала наблюдения. Порядок сложности второго цикла (по 1): 0(lH M 2 L+ N log2N), (4.15) где N общая длина обучающей выборки. I |