|
Следовательно, байесовский критерий, минимизирующий ошибку, будет иметь вид (N, / N)pNi (X/ и,) £(N2 / N)pMj (X / <о2) -> X 0). (4.П) или, подставляя (4.9) в (4.10) получим k,^k2-> X еС1. (4.12) [со 2 Таким образом, решение о принадлежности объекта X к тому или другому классу можно принять непосредственно после нахождения к ближайших соседей и сравнения к, и к2. Данное решающее правило легко обобщается для задачи классификации М классов. Аналогично, как и для двух классов, выбираются из обучающих выборок к ближайших к точке X точек. Пусть k,,k2,...,kM число наблюдений из соответственно. Наблюдение X относится к тому классу i, из которого в числе к ближайших точек присутствует больше точек, чем из любого другого класса j * i (j = 1,2,...,М). Решающее правило для классификации М совокупностей имеет вид [96] kj =max{k,,k2,...,kM}->X etOj. (4.13) Процедура классификации по правилу к ближайших соседей не требует знания плотностей вероятности и является достаточно простой. Недостатком данного метода классификации является необходимость хранить в памяти машины все объекты и сравнивать каждый из них с неизвестным объектом. В общем случае непараметрические методы классификации требуют большего объема вычислений при классификации новых наблюдений, чем параметрические методы при наличии обучения. В упомянутой литературе приводятся алгоритмы работы непараметрических классификаторов по методу к ближайших соседей. Однако производить сравнение показателей эффективности и сложности этих алгоритмов и разработанных алгоритмов нельзя, так как в структуру алгоритмов, представленных в приложении 4 ( Рис.П 4.1 и Рис.П 4.2) заложены процедуры формирования классификационных признаков, разработанные в главе 3. Поэтому необходимо сравнивать алгоритмы работы 115 |
124 2г жn_n/2 A(k,N,X) = у (4.9) v ; пГ(п/ 2) Величина А является случайной величиной, зависящей от выбранного множества N объектов. Оценка (4.8) может использоваться для классификации следующим образом. Когда требуется классифицировать неизвестный объект X, среди имеющихся N объектов, из которых N, объектов принадлежит классу ю,, а N2 объектов классу со2, находят к ближайших к точке X объектов. / Пусть к, и к2 соответственно числа объектов из класса со, и со2 среди I • , этих к ближайших соседей. Тогда оценка (4.8) принимает вид pNl(X/ffi1) = ^ 2 2 > i = i,2. (4.10) N А Так как к, и к2 объектов извлечены из одного и того же гипершара, то объем А один и тот же как для класса со,, так и для класса со2. Следовательно, байесовский критерий, минимизирующий ошибку, будет иметь вид гсо (N1/N )pNi(X /® ,)i(N 2/N )pNi(X/co2)-4.X e \ (4.11) I®2 или, подставляя (4.9) в (4.10) получим k, 1ю2' (4.12) Таким образом, решение о принадлежности объекта X к тому или другому классу можно принять непосредственно после нахождения к ближайших соседей и сравнения к, и к2. Данное решающее правило легко обобщается для задачи классификации Мs I классов. Аналогично, как и для двух классов, выбираются из обучающих выборок к ближайших к точке X точек. Пусть к,,к2,...,км число наблюдений из ®,,со2,...,сом соответственно. Наблюдение X относится к тому классу i, из которого в числе к ближайших точек присутствует больше точек, чем из любого другого класса j Фi (j = 1,2,...,М). Решающее правило для классификации М совокупностей имеет вид [96] к, = max{k,,k2,...,kM}-» X ею ,. (4.13) Процедура классификации по правилу к ближайших соседей не требует знания плотностей вероятности и является достаточно простой. Недостатком данного метода классификации является необходимость хранить в памяти машины все объекты и сравнивать каждый из них с неизвестным объектом. В общем случае непараметрические методы классификации требуют большего объема вычислений при классификации новых наблюдений, чем параметрические методы при наличии обучения. В упомянутой литературе приводятся алгоритмы работы непараметрических классификаторов по методу к ближайших соседей. Однако производить I 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 |