WWW.DISSERS.RU

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

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


Pages:     || 2 | 3 | 4 | 5 |   ...   | 43 |
РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР при поддержке РОССИЙСКОГО ФОНДА ФУНДАМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ МАТЕМАТИЧЕСКИЕ МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ (ММРО-10) Доклады 10-й Всероссийской конференции Москва 2001 Оргкомитет Председатель: академик РАН Журавлев Ю.И.

Зам. председателя: чл.-корр. РАН Рудаков К.В.

Члены:

Матросов В.Л., чл.-корр. РАН Дюкова Е.В., д.ф.-м.н.

Воронцов К.В., к.ф.-м.н Горелик А.Л., д.т.н.

Жданов С.А., к.ф.-м.н.

Донской В.И., д.ф.-м.н., проф.

Кондратьев В.В., чл.-корр. РАН Ларичев О.И., академик РАН Местецкий Л.М., д.т.н., проф.

Устинин М.А., к.ф.-м.н.

Технический оргкомитет Председатель: Громов А.Н.

Члены:

Инякин А.С.

Майсурадзе А.И.

Песков Н.В.

Чехович Ю.В.

2 I. Математическая теория распознавания О групповых нечетких классификациях М.Б. Айдарханов, Л.Л. Ла (Алматы) Нечеткие классификации и отношения эквивалентности Классификацией К конечного множеств а M ={S1,..., Sn} называется его разбиение на непересекающ иеся подмножества (классы). Данные разбиения определяют отношения эквивалентности множеств а М и наоборот, любое отнош ение эквивалентности на М задает некоторую классификацию этого множества. Покажем выполнение соответствующих свойств для нечетких классификаций.

Определение 1. [1] Нечеткая классификация К n-элементного множеств а l М на l классов задается матрицей A = (ai, j )nl, где =1, ai, j j=1 n i = 1,...,n, 0 < < n, j =1,...,l.

ai, j i =1 Нечеткой классификации, заданной матрицей A = (ai, j )nl поставим в соответствие нечеткое отношение эквивалентности R, относительно операций [2]: a b = max(0, a + b -1), a b = min(1, a + b), с функцией принадлежности R(Si,Sk ) = 1- max ak, j - ai, j. Данному j отношению эквивалентности R с матрицей (ri, j )nn соответствует множество нечетких классификаций с матрицами (ai, j )nl, где l =1, max ak, j - ai, j =1- ri,k.

ai, j j j=Устойчивость алгоритмов групповой нечеткой классификации Рассмотрен один подход к определению групповой, нечеткой классификации и дана оценка устойчивости алгоритмов групповой нечеткой классификации. Аналогичная задача для четких классификаций была рассмотрена в [3].

Определение 4.[4] Пусть K1,..., Km - классификации множества M.

* K назовем групповой, если на ней достигается минимум функционала m m (K) = (K, Ki)2, т.е. (K *) = min ) (K, Ki )2, где K(M i=i =(M ) - пространство классификаций M.

Пусть - метрика Евклида. K1,..., Km - нечеткие классификации M на l классов заданные матрицами (ai(,p) )nl, p =1,..., m Определим j нечеткую классификацию заданную матрицей G = (gi, j )nxl, где m gi, j = ( a( p) ) / m. Она будет являться групповой классификацией.

i, j p=Обозначим через (M ) матрицу нечеткой классификации, полученную в результате работы алгоритма на M.

Определение 5. Пусть I M. Алгоритм классификации назовем (, ) - устойчивым на M, если ((M ) M \ I, (M \ I)) для всех I, I, где A(M ) M \ I - ограничение A(M ) на M \ I.

Теорема. Пусть, M = {S1,...,Sn} I M, I, 1,..., m - (i, ) -устойчивые алгоритмы классификации, G - матрица групповой нечеткой классификации для классификаций 1(M ),...,m (M ), - соответствующий алгоритм вычисления групповой нечеткой классификации. Тогда * * (G M \ I, (M \ I )), где = max{1,...,m}.

Литература 1. Заде Л.А. Размытые множества и их применение в распознавании образов и кластер анализе. – В кн.: Классификация и кластер. М.: Мир, 1980, с.208-2. Аверкин А.Н., Батыршин И.З., Блишун А.Ф., Силов В.Б., Тарасов В.Б.

Нечеткие множеств а в моделях управления и искусственного интелектаМ.: Наука. 1986.-312с.

3. M.B. Aidarkhanov, L.L. La Some Properties of Group Classi fications // Pattern Recognition and Image Analysis. Vol. 9, N 1, 1999. pp. 7-9.

4. Айвазян С.А., Бежаева З.И., Староверов О.В. Классификация многомерных наблюдений.- М.: Статистика, 1974. –240 с.

Дискретные ортогональные преобразования c мультиэкспоненциальным базисом М.В. Алиев, В.М.Чернов, М.А.Чичева Самара Среди многочисленных дискретных ортогональных преобразований, ДОП, (Фурье, Адамара, Хартли и т.д.), применя емых в цифровой обработке сигналов, важную роль играет дискретное косинусное преобразов ание (ДКП):

N - x n =m x n hm n, (1) ( ) ( ) ( ) n= 2im n+) ( 2im n+) ( где hm n =exp, ( ) + exp 2N 2N (2) m - нормирующие коэффициенты, - оператор комплексного сопряжения, - рациональный параметр, гарантирующий ортогональность базисных функций hm n. Преимущ еств а ДКП перед другими ДОП ( ) заключаются в отсутствии краевых ("гиббсов ских") искажений при использовании алгоритмов блочного кодирования сигналов, хороших аппроксимационных свойствах по отношению к (оптимальному) преобразованию Карунена-Лоэва, наличии эффективных (быстрых) алгоритмов и т.д.

В основе обобщения ДКП, рассматриваемого в работе, лежит следующая идея. Оператор комплексного сопряжения является единственным нетривиальным R-автоморфизмом второго порядка, действующим (глобально) в комплексном поле С. С другой стороны, при естественном "пользовательском" допущении о рациональности значений x n, все ( ) слагаемые в сумме (1) являются элементами некоторого (кругового) подполя, для которого существуют (локальные) автоморфизмы, отличные от комплексного сопряжения.

В работе рассматривается новый класс ДОП, аналогичный (1)-(2), для случая произвольного автоморфизма второго порядка. Описывается связь между параметрами p и, приводятся алгоритмы их нахождения, синтезируются быстрые алгоритмы вычисления преобразований.



Доказывается, в частности, что несмотря на невещественность базисных функций (2) в общем случае, существуют быстры е алгоритмы преобразований (1)-(2) с вычислительной сложностью, сравнимой со сложность ю быстрых алгоритмов ДКП, для которого значения базисных функции (2) – вещественные числа.

Подробно исследован случай автоморфизма, являющегося Qлинейным продолжением отображения 2i : g, где =exp, g – целое.

2N В этом случае базисные функции (2) преобразов ания (1) имеют :

(n+) (n+)g hm n =m +m, (=a b - несократимая дробь).

( ) Доказываются теоремы существования преобразования с параметрами g, a,b, при заданной длине N. Синтезируются быстрые алгоритмы вычисления преобразований.

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

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

L- 2im n+) ( hm n = l exp, ( ) 2N l=где - автоморфизм порядка L подходящего кругового поля.

Байесовский подход к определению качества распознавания В.Б. Бериков (Новосибирск) При изучении статистических свойств решающих прав ил распознавания образов в случае обучающей выборки ограниченного объема, одной из основных проблем является оценка качества решающих правил распознавания в зависимости от объема выборки, размерности пространства характеристик, класса распределений и вида решающих правил.

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

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

Рассматрив аются дискретные характеристики или непрерывные, область значений которых предварительно разбита на «ячейки». В последнем случае разбиение может задаваться, например, некоторым деревом решений. При этом структура дерев а фиксирована, а решения приписываются концевым вершинам на основании выборки.

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

Хотя дискретная задача распознавания является лишь частью более общей задачи распознавания образов, она достаточно важна.

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

С другой стороны, можно прив ести много примеров прикладных задач, в которых используются дискретные (булевы, номинальные) характеристики.

Рассмотрим, например, задачу классификации «горячих точек» мутации в генетических последовательностях [2,3]. «Горячей точкой» мутации называется определенный участок ДНК, в котором возникновение мутации более вероятно, чем в других участках. Предполагается, что вероятность мутации в некоторой позиции последовательности зависит от 2r ближайших соседних элементов («контекста»). Поскольку элементы кодируются символами 4-х буквенного алфавита {A,C,T,G}, рассматрив ается дискретное пространство характеристик размерности 2r. Задача заключается в построении решающего правила для распознавания «горячих точек» по характеристикам контекста. Важно также определить оценки качества распознавания в зависимости от длины контекста, числа экспериментов над последовательностью и т.д.

Предположим, нам известна частота ошибок на обучающей выборке для некоторого решающего правила распознавания f (обучающая выборка известна), число M значений дискретной характеристики и объем N обучающей выборки. Число образов равно двум. Предположим, что на множестве задач распознавания задано равномерное априорное распределение.

Теорема. Апостериорная вероятность ошибки Perr для решающего правила f подчиняется распределению с характеристической функцией (t ) =( N + M,N +2M ;it ), a( j ) j x где (a,c;x ) = - ряд Куммера (вырожденная c( j ) j ! j =гипергеометрическая функция), через a( j ) обозначено:

a( j ) = a( a +1)...( a + j -1), (причем a( 0 ) =1), i – мнимая единица.

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

Следствие. Произвольный l-й момент (относительно нуля) вероятности ошибки равен E(Perr )l =( N + M )( l ) /(N +2M )( l ) Отсюда можно показать, что математическое ожидание и дисперсия вероятности ошибки для f равны соответственно: EP=( N+M)/(N+2M), VP=EP(1-EP)/(N+2M+1).





Полученны е формулы позволяют оценить доверительный интервал для вероятности ошибки с помощью неравенств Чебышевского типа, а также оценить объем обучающей выборки, достаточный для достижения заданной точности распознавания. Стандартный подход, связанный с вычислением статистики хи-квадрат, не позволяет решить данную задачу.

Альтернативный подход Вапника-Червоненкиса [5], как правило, дает слишком пессимистичные оценки качества распознавания, как это было показано в [4].

Рассмотрим следующий пример, взятый из [2]. Пусть эксперт сформулировал решающее правило распознавания «горячих точек» мутации по контексту при r=2, изображенное в виде дерева решений на рис.1.

Xx3{T,C,G} x3{A} горячая точка холодная точка мутации мутации Рис. Для проверки этого правила используется выборка, состоящая из N=наблюдений. Частота ошибки =0. Тогда математическое ожидание вероятности ошибки EP0.07, дисперсия VP0.0027.

Работа выполнена при поддержке РРФИ 01-01-Литература 1. Лбов Г.С., Старцева Н.Г. Логические решающие функции и вопросы статистической устойчивости решений // Новосибирск: Изд-во Ин-та математики. 1999.

2. Berikov V.B., Rogozin I.B. Regression trees for analysis of mutational spectra in nucleotide sequences // Bioinformatics. 1999. V. 15. P. 553-562.

3. Glazko, G.V., Milanesi L., Rogozin I.B. The subclass approach for mutational spectrum analysis: application of the SEM algorithm // J. Theor. Biol. 1998.

V. 192. P. 475-487.

4. Бериков В.Б. Об устойчивости алгоритмов распознавания в дискретной постановке // Искусственный интеллект. 2000. T. 2. С. 5-8.

5. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. М.:

Наука. 1974.

Решение задачи таксономии, основанное на анализе одномерных признаковых покрытий А.С. Бирюков (Долгопрудный) В работе [1] рассмотрена следующая задача. Дана выборка {S} из m чисел. Предполагается, что {S} является смесью l кластеров, при этом функции плотностей распределений кластеров известны с точностью до параметров. Требуется по выборке {S} найти данные параметры.

Для случаев равномерного и нормального распределений в работе [2] предложены соответствующие практические алгоритмы нахождения параметров одномерного распределения. Решив необходимые одномерные задачи кластерного анализа, можно далее найти реш ения задачи классификации для векторных описаний объектов путем построения коллективного реш ения [3]. При реализации данного метода возникают трудности, связанные с тем, что методы [2] дают наборы решений, равноценных по функционалу качества. Ниже предлагается алгоритм построения на базе набора решений нового решения, состоящего из «фрагментов» исходных решений. При этом оптимизируется соответствие кластеризации полученной для различных признаков.

Будем считать, что распределение значений признака по классам – равномерное. На первом этапе находим какими-либо методами, например [2], для каждого признака некоторый набор решений одномерной задачи кластеризации. То есть для i -ого признака имеем следующие наборы интервалов покрытий:

i i i Решение 1: [a11;b11],[ai1; b21],...,[ali1; bli1] i i i Решение 2: [a12 ;b1i2],[a22 ; b22],...,[ali 2; bli 2]...

ik ik ik Решение k : [a1 ; b1 ],[aik ; b2 ],...,[alik ;blik] Обозначим каждый интервал Aik, где i - номер признака, k - номер j решения для этого признака, j - номер интервала разбиения в этом решении.

Теперь попарно срав ним все интервалы Aik всех пар признаков. Введем j функционал, характеризующ ий относительное пересечение двух интервалов:

Ai1k1 Aij2kj1 F1 Ai1k1, Aij2k2 =, i1 i2, j1 Ai1k1 Ai2kjjа также функционал, характеризующий абсолютное пересечение:

F1 Ai1k1, Aij2k2 = Ai1k1 Aij2k2, i1 i2.

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

= F1F2.

Теперь мы можем вычислить вес для каждого интервала Aik :

j (Aik)= (Aik, Atpq).

j j p,q,t pi Затем для каждого признака i строим набор интервалов i B1, Bi,..., Bi, образующий покрытие, имеющее максимальный вес. Это Ni можно сделать, например, решив следующую задачу:

n x min c =, n a xµ µ µ =где c = f(Aik) 0, aµ {0,1}, x {0,1}.

j Таким образом, для каждого признака мы получим решение задачи классификации. Теперь решим задачу поиска коллективного решения относительно полученных решений [3] и мы найдем решение исходной задачи.

Реализация данного алгоритма показала, что он дает стабильное улучшение исходного набора решений одномерных задач кластеризации.

Работа выполнена при поддержке Российского Фонда фундаментальных исследований (проекты №99-07-90120, 99-07-90390, 00-01-00650) и ИНТАС №00-397, 00-626.

Литература 1. В.В. Рязанов. О решении задачи кластерного анализа на базе склеивания решений по признаковым подпространствам. Труды конференции «РОАИ – 5 - 2000», том 1, стр. 118.

2. А.С. Бирюков, А.П. Виноградов, В.В. Рязанов, И.В. Рязанов. О восстановлении некоторых плотностей кластеров по эмпирическим плотностям смеси. Труды конференции «РОАИ – 5 - 2000», том 1, стр. 16.

3. В.В. Рязанов. Оптимальные коллективны е решения в задачах распознавания и классификации //Диссертация на соискание ученой степени доктора физико-математических наук, Москва, 1994.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 43 |










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

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