WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 82 |

n количество классов; s размер класса; t размер доверительного интервала. Модель классификатора fx в общем виде представляется как fx = f([k], Lxy, hx), (2) где [k] фрагменты функций признаков; Lxy метрика в пространстве признаков; hx решающая функция или правило.

Если для оптимизации модели классификатора использовать последовательный анализ, а в качестве параметра оптимизации средний размер класса в виде s = f([k], Lxy, hx), то задача оптимизации представляется следующим образом:

arg min f([k], Lxy, hx) = min(s). (3) [k],Lxy,hx Модель СР включает модель классификатора с параметрами, а также компоненты, влияющие на достоверность результатов распознавания.

При оптимизации модели СР важно отдельно учесть влияние на достоверность распознавания таких факторов, как мера расстояний между образами и размеры доверительного интервала и класса, связанные между собой. Основная трудность при исследовании указанных зависимостей состоит в том, что существуют влияния компонент СР как одной на другую, так и совместно на функционал (1). Всё это усложняет построение моделей различного назначения.

38 (TF) Капустий Б. Е., Русын Б. П., Таянов В. А.

Рассмотрим выражение мер расстояний между векторами признаков x и y, используемых в теории распознавания [5], через меру Манхеттена простую линейную меру с весовыми коэффициентами ai:

n d(x, y) = ai|xi - yi|, (4) i=где d(x, y) произвольная мера расстояний между векторами x и y.

Меру расстояний Минковского, как наиболее обобщённую меру, используемую в теории распознавания образов, можно представить в виде 1 n n n p p d(x, y) = |xi - yi|p = ai|xi - yi| = C(p) ai|xi - yi|, (5) i=1 i=1 i= n 1-p p где C(p) = ai|xi - yi|) ; ai = |xi - yi|)p-1; p > 0.

i=Из приведенного выше следует, что произвольная метрика это фильтр в пространстве признаков, т. е. она устанавливает веса признаков при использовании решающих правил. Вес определённого признака должен быть пропорционален приращению одного из показателей при его добавлении в общее признаковое множество, используемое для дискриминации классов: вероятности правильного распознавания, среднего размера класса, дивергенции между классами или дискриминанта Фишера [1, 4, 5]. Можно использовать и другие показатели, однако способ их применения должен быть одинаковым. Если признак не даёт приращения соответствующего показателя или ухудшает его, то значение веса соответствующего признака следует принять равным нулю. Таким образом, путём дополнительного уменьшения количества признаков можно ускорить процесс распознавания, не ухудшая его качественных характеристик. Проблема оптимизации набора признаков и выбора вида метрики решена однозначно с помощью взвешенных признаков и простой линейной меры подобия между образами с весовыми коэффициентами.

Задача селекции признаков в этом случае решается частично. Определяется субмножество признаков из генеральной совокупности, выбираемой при помощи того или иного алгоритма (например, ряда ортогональных преобразований). Этот алгоритм в свою очередь должен удовлетворять определённым требованиям относительно селекции признаков таким, как минимизация энтропии образов класса или максимум дивергенции между классами. Указанным требованиям удовлетворяет метод главных компонент [5].

Последним параметром, используемым в модели, является решающая функция или правило. Условно все решающие функции можно разделить на те, что работают в признаковом пространстве и те, которые Построение оптимальной вероятностной модели систем распознавания (TF) строятся на основании функции расстояний. В признаковом пространстве, например, применяют байесовский классификатор, линейный дискриминант Фишера, метод опорных векторов, и др. В многомерном признаковом пространстве значительно усложняется процедура принятия решения при использовании этих решающих правил. Это особенно нежелательно в случаях, когда распознавание проводится непрерывно для серии образов, поступающих в блок распознавания соответствующей системы. Поэтому при практической реализации СР, работающих с достаточно большиим сериями изображений, используют решающие правила, построенные на основании функции расстояний. Принято использовать два решающих правила: по минимуму расстояния от ближайшего (1NN) и k ближайших соседей (kNN). Хотя 1NN правило наиболее простое, оно характеризуется наименьшими показателями вероятности при принятии решений. Поэтому целесообразно использовать kNN правило. При этом задача сводится к выбору значения k, оптимального для принятия решения в пределах доверительного интервала, соответствующего списку возможных претендентов. От размера класса также зависит размер доверительного интервала, в котором принимается решение. Определение условий, при которых результаты принятия решения на основании оптимального байесовского решающего правила с одной стороны, и 1NN или kNN правил с другой, совпадают или близки, даёт возможность использовать наиболее простое решающее правило при сохранении качественных свойств процедуры принятия решения.

Литература [1] Журавлев Ю. И., Рязанов В. В., Сенько О. В. Распознавание. Математические методы. Программная система. Практические применения Москва:

Фазис, 2005. 159 с.

[2] Капустий Б. Е., Русын Б. П., Таянов В. А. Новый подход к определению вероятности правильного распознавания объектов множеств // УСиМ.

2005. № 2. С. 8–13.

[3] Kapustiy B. O., Rusyn B. P., Tayanov V. A. Tayanov Comparative analysis of different estimates of Recognition Probability // Journal of Automation and Information Sciences. 2006. Issue 8. P. 8–16.



[4] Kapustiy B. O., Rusyn B. P., Tayanov V. A. Сlassifier optimization in small sample size condition // Avtomatika i vychislitel’naya tekhnika. 2006. vol.

40, Issue 5. P.25–32.

[5] Webb R. A. Statistical Pattern recognition. John Wiley & Sons Inc, 2nd ed., 2002.

40 (TF) Климова О. Н.

Учет двух наборов взаимно зависимой информации об относительной важности критериев в задачах многокритериального выбора Климова О. Н.

Klimova_O@rambler.ru Санкт-Петербург, Санкт-Петербургский Государственный Университет Одной из значимых проблем в области многокритериального выбора является проблема сужения множества Парето, поскольку оно зачастую оказывается достаточно широким. Как правило, дальнейшее сужение области поиска наилучшего решения происходит на основе дополнительной информации, получаемой от лица, принимающего решения (ЛПР).

В данной работе рассматривается задача, в которой дополнительная информация представляет собой количественную информацию об относительной важности критериев [2]. Она заключается в том, что выделяются группы критериев и определяется важность первой группы относительно второй. Количественно важность выражается парой наборов числовых параметров. Первый набор содержит максимальные величины выигрышей по каждому из критериев более важной группы, в том случае, если ЛПР сделает уступки по каждому из критериев менее важной группы (второй набор параметров содержит величины уступок). Более того, оказывается, что вторая группа критериев, в свою очередь, важнее первой. В данной ситуации ЛПР идет на взаимные уступки по нескольким критериям, ради прибыли по каждому из них.

Информация подобного рода, т. е. когда группа критериев A важнее группы B, а группа критериев B, в свою очередь, важнее A (причем A и B непустые и взаимно непересекающиеся группы) является взаимно зависимой [2].

Пусть X множество возможных решений. Предпочтения ЛПР выражаются при помощи набора критериев f1,..., fm, m 2, образующих векторный критерий f(x) = (f1(x),..., fm(x)), и бинарного отношения строгого предпочтения X, заданного на X. Множество выбираемых решений обозначим через Sel(X).

Наряду с множествами X и Sel(X) будем использовать множества возможных Y = f(X) Rm и выбираемых Sel(Y ) = f(Sel(X)) векторов.

Дополнительная информация состоит из следующих двух сообщений:

1) группа критериев A важнее группы критериев B с заданными положи тельными параметрами wi (i A), wj (j B) и группа критериев B важнее группы критериев A с заданными положительными параметрами j (j B), i (i A); 2) группа A важнее группы критериев C с по ложительными параметрами wi (i A), wk (k C) и группа C важ нее группы критериев A с положительными параметрами k (k C), Учет взаимно зависимой информации при многокритериальном выборе (TF) i (i A). Группы критериев A, B, C непустые и взаимно непересекающиеся. Представленный набор информации обозначим через (И). Таким образом, в рассматриваемой задаче имеются два набора взаимно зависимой информации.

Будем предполагать, что отношение предпочтения удовлетворяет четырем аксиомам, определяющим разумный выбор [2].

Аксиома 1 (об исключении доминируемых векторов). Для любой пары векторов y, y Y, удовлетворяющих соотношению y Y y, выполнено y Sel(Y ).

/ Аксиома 2. Для отношения Y существует иррефлексивное и транзитивное продолжение на все пространство Rm. Тем самым, отношение Y является сужением на Y.

Аксиома 3. Каждый из критериев f1,..., fm согласован с отношением предпочтения.

Аксиома 4. Для любых векторов y, y Rm таких, что y y, для любого числа > 0 и произвольного вектора c Rm выполняется y + + c y + c.

Учет дополнительной информации происходит в два этапа. Сначала необходимо убедиться в непротиворечивости [1] предоставленной информации, а затем по определенным формулам произвести сужение исходного множества Парето.

Критерий непротиворечивости был получен в следующем виде.

Теорема 1. Набор информации (И) непротиворечив тогда и только тогда, когда существуют номера i1 A и j B, для которых выполняется неравенство wi i 1 > (1) wj j и существуют номера i2 A и k C, для которых выполняется неравенство wi i 2 >. (2) wk k Учет двух наборов взаимно зависимой информации описанного вида, осуществляется по формулам, полученным в следующей теореме.

Теорема 2. Пусть отношение предпочтения удовлетворяет аксиомам 1–4 и задана непротиворечивая информация об относительной важности (И), причем неравенства вида (1), (2) выполняются для всех i A, j B, k C. Тогда для множества выбираемых решений Sel(X) имеют место включения Sel(X) Pg(X) Pf (X), 42 (TF) Леухин А. Н., Бахтин С. А.

где Pg(X) множество Парето в новой задаче многокритериального выбора с векторным критерием g размерности q = m - (|A| + |B| + |C|) + + 4 · |A| · |B| · |C| и компонентами gijk = wjwkfi(x) + wiwkfj(x) + wjwi fk(x), i A, j B, k C;

gikj = jk fi(x) + ik fj(x) + ji fk(x), i A, j B, k C;

gjki = wjk fi(x) + wik fj(x) + wji fk(x), i A, j B, k C;

gkji = jwkfi(x) + iwkfj(x) + jwi fk(x), i A, j B, k C;

gs = fs, s I \ (A B C).

Таким образом, согласно теореме 2, множество Парето Pg(X), полученное относительно нового векторного критерия g, уже множества Pf (X) и является оценкой для искомого множества Sel(X).

Наконец, отметим, что теорема 2 сводится к частному случаю, если дополнительная информация (И) состоит только из одного набора взаимно зависимой информации (группа критериев A важнее группы критериев B, а группа критериев B важнее группы A) [1].





Литература [1] Климова О. Н., Ногин В. Д. Учет взаимно зависимой информации об относительной важности критериев в процессе принятия решений // ЖВМиМФ. 2006. Т. 46, № 12. С. 2178–2190.

[2] Ногин В. Д. Принятие решений в многокритериальной среде: количественный подход. 2-е издание. Москва: Физматлит, 2005. 176 с.

Новый алгоритм синтеза всех неприводимых многочленов над заданным конечным полем Леухин А. Н., Бахтин С. А.

inf@marstu.mari.ru Йошкар-Ола, ГОУ ВПО Марийский гос. тех. университет Проведен обзор проблемы синтеза неприводимых и примитивных многочленов над заданным конечным полем. Предложен новый быстрый детерминированный алгоритм синтеза всех неприводимых многочленов над конечным полем Fp заданной степени n, основанный на модифицированном быстром методе Крылова для вычисления характеристического многочлена матрицы Фробениуса, сопровождающей неприводимый многочлен над заданным конечным полем.

Теория многочленов степени n от одной переменной, неприводимых над конечными полями Fp, представляет существенный интерес как n для исследования алгебраической структуры конечных полей Fq=p, Синтез всех неприводимых многочленов над заданным конечным полем (TF) так и для многочисленных приложений в современной теории передачи информации. Такие многочлены имеют большое значение при синтезе шумоподобных кодовых последовательностей, в теории помехоустойчивого кодирования, в криптографии при решении задачи дискретного логарифмирования (к которой сводится задача логарифмирования на эллиптической кривой), в теории кольцевых счетчиков, и т. д.

Первое крупное исследование о неприводимых многочленах от одной переменной над полем Fq проведено в работе [1]. Фундаментальный обзор результатов по теории конечных полей, включающий и теорию неприводимых многочленов, приводится в работе [2]. Однако, несмотря на достигнутые успехи в теории синтеза неприводимых многочленов, имеется ряд важнейших проблем, которые до сих пор не поддаются решению.

Одной из них является проблема построения неприводимых многочленов заданной степени в явном виде, а также определения периодов элементов поля корней этих многочленов.

По существу, все подходы к синтезу неприводимых многочленов можно разделить на три большие группы. К первой группе можно отнести аналитические методы построения, позволяющие в явном виде сразу записать выражения для неприводимых многочленов. В роли таких многочленов чаще всего выступают полиномы с малым числом слагаемых двучлены, трехчлены и четырехчлены.

В работе [2] приводятся теоремы для неприводимых двучленов и трехчленов. Конкретные примеры аналитических выражений для неприводимых многочленов, удовлетворяющие приведенным теоремам, приводятся в работе [3]. Конструкции неприводимых многочленов над полем F2 степени 4·3k ·5l, над полем F3 степени 4·2k ·5l, над полем Fp (p > 3) степени 2 · 2k · 3l можно найти в работе [4]. Другие аналитические конструкции неприводимых многочленов над конечными полями в явном виде приведены в работах [5, 6].

К сожалению, в явном виде не удается получить выражения для неприводимых многочленов произвольной степени n над полем Fq. Кроме того, в явном виде невозможно записать все неприводимые многочлены заданной степени n.

Следующая группа методов синтеза основана на идее факторизации многочлена произвольно заданной степени n в конечном поле Fq. Неприводимость многочлена устанавливается по результатам факторизации.

Первые существенны результаты получены в работе [7], опираясь на которые, в работе [8] синтезирован улучшенный и эффективный в вычислительном плане метод. В дальнейшем на основе методов факторизации появились вероятностные [9] и детерминированные [10] алгоритмы-тесты 44 (TF) Леухин А. Н., Бахтин С. А.

на неприводимость многочлена произвольной степени n над полем Fq, позволяющие решать задачу за полиномиальное время.

В третью группу методов синтеза неприводимых полиномов входят алгоритмы построения неприводимых и примитивных многочленов, использующих алгебраическую структуру и внутреннее строение полей Галуа. В отличии от двух предыдущих случаев, данные методы позволяют синтезировать сразу все возможные неприводимые или примитивные многочлены степени n над Fq. Первый алгоритм алгоритм решета является прямым методом синтеза неприводимых многочленов [2], и для его реализации нет необходимости в использовании начального неприводимого многочлена. Однако этот алгоритм имеет низкую вычислительную производительность и может использоваться для малых размерностей степени многочлена n и характеристики p поля. Второй алгоритм [2] основан на свойствах минимальных многочленов степени n поля Fq. Для его реализации требуется один начальный неприводимый полином степени n над Fq для задания внутренней структуры поля.

В работе [11] описан метод построения новых неприводимых многочленов над полем, исходя из данного неприводимого многочлена.

В ходе исследовательской работы нами был получен алгоритм синтеза всех возможных примитивных многочленов степени n над полем Fp.

На первом шаге формируется матрица Фробениуса, сопровождающая начальный примитивный многочлен. На втором шаге определяютn ся подмножества коэффициентов p-сопряженных элементов поля Fp, и на их основе формируются множество кооффициентов, содержащее любой из элементов каждого подмножества. На третьем шаге исходная матрица возводится в степень коэффициента множества. На четверттом шаге с использованием метода Крылова формируется матрица, по которой будет вычисляться характеристический многочлен в конечном поле.

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 82 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.