автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Поиск информативных фрагментов описаний объектов в задачах распознавания

На правах рукописи

Песков Николай Владимирович

Поиск информативных фрагментов описаний объектов в задачах распознавания

Специальность 05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Москва - 2004

Работа выполнена в Научном совете по комплексной проблеме

"Кибернетика"

Научный руководитель: доктор физико-математических

наук Е. В. Дюкова

Официальные оппоненты: доктор технических наук

Л. М. Местецкий кандидат физико-математических наук М. Н. Вялый

Ведущая организация: Московский педагогический

государственный университет

Защита состоится «_»_200 г. в_часов на заседании диссертационного совета Д002.017.02 Вычислительного центра им. А. А. Дородницына РАН по адресу: 119991, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного Центра им. А. А. Дородницына РАН.

Автореферат разослан «_»_200 г.

Учёный секретарь диссертационного совета д.ф.-м.н.

В. В. Рязанов

2004-4

23914

Общая характеристика работы

Актуальность темы.

Для решения прикладных задач распознавания успешно применяются методы, основанные на комбинаторном анализе признаковых описаний объектов. Эти методы особенно эффективны в случае, когда информация целочисленная и число допустимых значений каждого признака невелико. Основополагающими работами являются работы Ю.И. Журавлева, С.В. Яблонского и М.Н. Вайнцвайга.

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

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

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

Наличие большого перебора, а также первоначально низкая производительность вычислительной техники явились причиной того, что основные усилия в течении многих лет были направлены на разработку общей теории сложности решения задач дискретного анализа информации и синтеза асимптотически оптимальных алгоритмов поиска информативных фрагментов. Полученные в данном направлении результаты позволили в определенной степени преодолеть указанные трудности и значительно усовершенствовать такие классические модели как тестовый алгоритм и алгоритм голосования по представительным наборам. Здесь следует отметить работы В.А. Сле-пян, В.Н. Носкова, Е.В. Дюковой и А.А. Андреева. При этом вопросам качества распознавания не уделялось достаточное внимание. Укажем некоторые проблемы, от решения которых зависит результат распознавания.

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

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

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

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

Необходимость построения эффективных реализаций для

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

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

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

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

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

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

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

Апробация работы. Результаты, изложенные в диссертации, докладывались на Всероссийских конференциях «Математические методы распознавания образов IX, X и ХЬ(Москва, ВЦ РАН, 1999, 2001, 2003 гг.); Международной конференции «Интеллектуализация обработки информации - 2002» (Симферополь, ТНУ); Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии - VI» (Великий Новгород, 2002г.); Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2003» (Москва, МГУ); семинарах отдела «Вычислительных методов прогнозирования» ВЦ РАН и лабораторий «Кибернетических методов информатики» и «Распознавания образов и прогнозирования» НСК РАН.

Публикации. По теме диссертации опубликовано 10 работ [1-10], в том числе 1 в ЖВМиМФ и 3 в журнале Pattern Recognition and Image Analysis. Описания основных результатов, полученных в диссертации, включались в научные отчеты по проектам РФФИ 98-01-00596, 01-01-00575, 00-15-96064.

Структура и объём работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы (91 наименование). Общий объем работы - 102 страницы.

Содержание работы

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

В главе 1 формулируется постановка задачи распознавания, вводится ряд основных определений, рассматривается общая схема конструирования дискретных процедур распознавания. Описывается классический алгоритм голосования по представительным наборам и новые модели: алгоритм голосования по антипредставительным наборам и алгоритм голосования по покрытиям классов.

Задача распознавания формулируется следующим образом. Исследуется некоторое множество объектов М, которые могут быть описаны в системе целочисленных признаков Пусть - конечное множество допустимых значений признака Xj, j € {1,2,... ,п} , и пусть М предста-вимо в виде объединения подмножеств (классов) Ki,...,Ki. Имеется конечный набор объектов из М, о которых известно, каким классам они принадлежат (обучающая выборка). Обучающие объекты представлены своими описаниями. Требуется по описанию некоторого объекта S из М ,

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

В разделе 1.1. приводятся основные определения и обозначения. Одно из основных понятий, используемых при конструировании дискретных процедур распознавания является понятие элементарного классификатора.

Пусть Н = {хуц - некоторый набор признаков, £ —

(ах,..., ап) - объект из обучающей выборки. Набор (о^,..., Оуг) будем называть фрагментом описания объекта £ и обозначать через (Б,И). В классическом варианте элементарными классификаторами является фрагменты описаний обучающих объектов.

В диссертационной работе введено понятие элементарного классификатора более общего вида.

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

Близость объекта £ = (а1,...,ап) из М и элементарного классификатора будем оценивать величиной

Пусть даны два объекта =

из М. Близость объектов по набору при-

знаков Я будем оценивать величиной

1, если а^ = при £ = 1,2,..., г; О, в противном случае.

1, если о^ = а"(, при ¿=1,2,..., г; О, в противном случае.

Каждый распознающий алгоритм дискретного характера А для каждого класса К, К € ... , А^}, строит некоторое подмножество СА(К) из множества всех элементарных классификаторов.. Элементарные классификаторы из СА{К) и только они считаются информативными при использовании алгоритма А. Распознавание объекта 5 осуществляется на основе вычисления величины В(а, 5, Н) для каждого элемента а из СА(К), т.е. для каждого класса К по каждому элементу множества СА(К) осуществляется процедура голосования. В результате вычисляется оценка Г(5, К) принадлежности объекта 5 классу К. Таким образом; каждый распознающий алгоритм А определяется множеством построенных элементарных классификаторов и способом вычисления оценок Г(й', К{),..., Г(5", К{). Объект £ относится к тому классу, для которого оценка максимальна. Если таких оценок несколько, то происходит отказ от распознавания.

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

Набор Я из г различных столбцов матрицы Ь назовем а-покрытием, если подматрица Ьн матрицы L, образованная столбцами из Н, не содержит строки с. Набор Н, являющийся с-покрытием, назовем тупиковым о-покрытием, если содержит подматрицу, составленную ИЗ строк (/?!, 02, аз,..., СГг_1, СГг), (Оь/^СГз, . . . ,СГГ_1,<ТГ), (0"1,СТ2,<7з,...,0г-1,А-), где & ф ар при р = 1,2,...,г. Указанную подматрицу будем называть а-подматрицей.

Пусть Элементарный классификатор

а, порожденный признаками из Н, по отношению к классу К может обладать одним из следующих трех свойств: 1) каждый фрагмент вида (Б',Н), где 5' € К, совпадает с ст; 2) не все, а лишь часть фрагментов вида (5', Я), где Б' Е К, совпадают с ; 3) ни один фрагмент вида не совпадает

с ст. Первая ситуация встречается крайне редко, поэтому работать с наборами значений признаков, для которых выполняется свойство 1, не представляется возможным. Существенное различие в информативности следующих двух свойств заключается в том, что свойство 2 характеризует лишь некоторое подмножество обучающих объектов из К, а свойство 3 все объекты из К . Следовательно, в случае, когда важно рассматривать класс К изолированно от других классов, напрашивается вывод о большей информативности таких наборов значений признаков, для которых выполнено свойство 3. В указанном случае аргументом за отнесение распознаваемого объекта £ в класс К более естественно считать ситуацию, когда набор значений признаков не присутствует у всех объектов из класса К и не присутствует у объекта Б. Классические дискретные процедуры распознавания основаны на поиске элементарных классификаторов, обладающих свойством 2.

В разделе 1.2 описана классическая модель алгоритма А\ голосования по представительным наборам

Фрагмент описания объекта 5' из класса К вида (3',Н) назовем представительным набором для К, если для любого обучающего объекта не принадлежащего классу К, имеет место Представительный набор для класса

К вида (5', Я) назовем тупиковым если для любого набора Н', Н' С Н , найдется обучающий объект 5" из К, для которого 5", Н') = 1. В качес С^^бе р е т с я множество

(тупиковым) представительных наборов для К. В простейшей модификации для оценки принадлежности объекта £ классу К используется величина

(здесь и далее мощность множества Ы).

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

В разделе 1.3. описываются алгоритм Ац голосования по покрытиям классов и алгоритм Аз голосования по антипредставительным наборам.

Множество состоит из элементарных классифика-

торов, обладающих свойством 3. Такие элементарные классификаторы будем назвать покрытиями класса К. Элементарный классификатор, являющийся покрытием класса К и встречающийся в описаниях объектов из К, будем называть антипредставительным набором. Множество состоит

из антипредставительных наборов для К.

Элементарный классификатор или

порожденный набором признаков Н, голосует за принадлежность распознаваемого объекта £ классу К, если а ф (5", Н) Принадлежность объекта £ классу К (в простейшей модификации) оценивается величиной

Гх (5,*) =

1

(а,Н)£САЦК)

Г г(8,К) =

1

(а,Н)еСАЧК)

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

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

В разделе 2.1. предлагается методика оценки информативности (важности для распознавания) признаков, а также отдельных значений признаков.

Традиционно в качестве меры важности признака

рассматривалась величина (впервые предложен-на Ю.И. Журавлевым), равная отношению числа построенных элементарных классификаторов, в которых содержится признак , к общему числу построенных элементарных классификаторов. Такой способ оценки информативности признаков не всегда дает хорошие результаты, например, если признак является шумящим.

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

Пусть £>' = (а[, а'2,..., а'п) - обучающий объект, 5" € К{,

. Положим: - ча-

стота встречаемости а^ в описаниях обучающих объектов из - частота встречаемости а^ в описаниях обучающих объектов из Величины характери-

зуют близость объекта 5' соответственно к своему классу и к другим классам. Величину /-4^(5') = /.¿[^(5") — назо-

вем весом признака Xj для объекта 5'. Будем говорить, что значение признака для является типичным для если где - порог информативности, Например, в случае ц = 0, значение признака будет являться типичным для класса, если в этом классе оно встречается чаще, чем в остальных.

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

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

Пусть описание обучающего объекта £ из К похоже на описания некоторых объектов из К. Тогда объект 5 «лишает» класс К некоторого множества коротких элементарных классификаторов (тестов, представительных наборов и т.д.), что существенно снижает эффективность алгоритма. Для решения указанной проблемы предлагается разбить обучающую выборку на две подвыборки: базовую, состоящую из типичных для своих классов обучающих объектов, и контрольную, состоящую из обучающих объектов, находящиеся на границе между классами. По базовой будем строить множество эле-

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

Предложено два способа выделения типичных объектов: 1) типичными считаются объекты, описания которых состоят в основном из типичных значений признаков; 2) типичными являются объекты, которые правильно распознаются на скользящем контроле. При использовании первого способа вычислительные затраты незначительны. Второй способ довольно трудоемкий.

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

Глава 3 посвящена изучению метрических свойств множества покрытий целочисленной матрицы.

В разделе 3.1 приводятся необходимые определения и обозначения. Пусть - интервал - интервал

togk un~l 1о§* 1о§* ип ~ 1о§к 1оёк 1о8* п> i log* ип-^ logfc logfc ип + logfc logfc log* n);

On ~ bn означает, что lim (an/bn) = 1 при n oo.

Пусть - множество всех матриц размера

элементами из {0,1,..., к—1}; L £ М*п; - множество всех к-ичных наборов длины . Пусть далее

C(L,<j) - множество всех пар вида (Я, сг) , где Я - с-покрытие матрицы L, B(L,a) - множество всех пар вида (Я, а), где Н -

тупиковое а-покрытие матрицы Ь, а) - совокупность всех а-подматриц матрицы L.

Положим

Нас будут интересовать асимптотические оценки чисел \С(Ь)\, \В(Ь)\ и ^(Ь)! для почти всех матриц Ь из М*п при п—> оо. Выявление типичной ситуации будет связано с высказыванием типа «Для почти всех матриц Ь из М*п при п —> оо выполнено свойство /?», причем свойство /3 также может иметь предельный характер. Это означает, что доля тех матриц из М„п для которых с ^-точностью выполнено свойство /?, стремиться к 1 и одновременно € стремиться к 0 при оо.

Ранее в основном изучался случай, когда число строк в матрице по порядку меньше числа столбцов, а именно, когда иа < п < к*0, а > 1, ¡3 < 1. Е.В. Дюковой показано, что в данном случае величина \В(Ь)\ в типичной ситуации асимптотически совпадает с величиной и по порядку меньше числа покрытий. На основании этого факта ею был построен асимптотически оптимальный алгоритм поиска покрытий из

т.

В разделе 3.2 для практически общего случая получены асимптотики типичных значений величины и длины

покрытия из С(Ь), а именно, доказана

Теорема 3.2.1. Если и < кп0, ¡3 < 1, то для почти всех

матриц L из М*п при п —> оо имеет место \C{L)\ » £ CrnV

и длины почти всех покрытий из C(L) принадлежат интервалу Фо>

Пусть Ci(L) - множество всех покрытий из C(L), длины которых не превосходят logfc и—logfc(logfc и In kn) Справедлива

Теорема 3.2.2. Для почти всех матриц L 6 М^|1Пj при имеет место

ß

В разделе 3.3 для случая па < и < кп , а > 1, ß < 1, получены асимптотики типичных значений числа подматриц из S(L) и порядка подматрицы из 5(L), а именно доказана

Теорема 3.3.1. Если па <и< кп$, а > 1, ß < 1, то для почти всех матриц L из М*п при п-Ь оо имеет место

и порядки почти всех подматриц из S(L) принадлежат интервалу

Пусть S\{L) - множество всех ст-подматриц из S(L), ранги которых не меньше logkun. Справедлива

Теорема 3.3.2. Для

почти всех матриц L £ при п —У

имеет место

На основе сравнения оценок, приведенных в теоремах 3.3.1 и 3.2.1, доказана

Теорема 3.3.3. Если па < и < knß, а > 1, ß < 1/2, то для почти всех матриц имеет место

|S(L)|/|2?(L)Hoo.

В главе 4 сформулированы основные принципы конструирования дискретных процедур распознавания с использованием аппарата логических функций. Рассмотрена связь между задачей построения ДНФ двузначной логической функции, заданной на &-ичных «-мерных наборах, и задачей нахождения покрытий матрицы из На основе теорем, доказанных в главе 3, получены асимптотики типичных значений для числа допустимых конъюнкций и ранга допустимой конъюнкции указанной функций, а также верхняя асимптотическая оценка числа максимальных конъюнкций.

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

В заключении приводится краткая формулировка результатов, выносимых на защиту.

Результаты, выносимые на защиту

(1) Введено более общее по сравнению с ранее используемым понятие элементарного классификатора и построены новые модели распознающих процедур дискретного характера, основанные на принципе «невстречаемости» набора из допустимых значений признаков в описаниях объектов класса.

(2) Разработаны подходы к повышению эффективности алгоритмов распознавания, основанные на выделении для каждого класса типичных значений признаков и типичных обуча-

ющих объектов.

(3) Предложен быстрый способ вычисления оценок при голосовании по представительным наборам для процедуры скользящего контроля.

(4) Получены асимптотики типичных значений числа покрытий и длины покрытия целочисленной матрицы для практически общего случая.

(5) Получены асимптотики типичных значений числа подматриц и ранга -подматрицы для случая, когда число строк в матрице значительно превосходит число столбцов. Показано, что в этом случае число -подматриц по порядку больше числа тупиковых <г-покрытий.

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

Публикации по теме диссертации

[1] Дюкова Е. В., Песков Н. В. О некоторых подходах к вычислению информативных характеристик обучающей выборки // Докл. Всеросс. Конф. "Матем. методы распознавания образов - 9". М.: АЛЕВ-В, 1999, С. 181-183.

[2] Дюкова Е. В., Песков Н. В. О дискретных процедурах распознавания, основанных на построении покрытий классов // Докл. Всеросс. Конф. "Матем. методы распознавания образов - 10", М.: АЛЕВ-В, 2001, С. 48-51.

[3] Дюкова Е.В., Песков Н.В. Информативность признаков, отдельных значений признаков и фрагментов описаний объектов // Докл. Всеросс. конф. "Математические ме-

тоды распознавания образов 10", М.: АЛЕВ-В, 2001. С. 44-47.

[4] Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // Ж. вычисл. матем. и матем. физ. 2002. Том 42, № 5, С. 741-753.

[5] Дюкова Е.В., Инякин А.С., Песков Н.В. О некоторых направлениях современных исследований в области дискретного анализа информации в проблеме распознавания // Труды межд. Конф. "Р0АИ-6-2002", Великий Новгород, 2002. Т. 1. С. 203-208.

[6] Песков Н.В. О некоторых подходах к конструированию дискретных процедур распознавания // Сообщения по прикладной математике. М.: ВЦ РАН, 2002. 28с.

[7] Песков Н.В. Об одном подходе к повышению эффективности алгоритмов распознавания // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2002. С. 73-74.

[8] Djukova E.V., Peskov N.V. Selection of Typical Objects in Classes for Recognition Problems // J. Pattern Recognition and Image Analysis. 2002. V. 12. No. 3. P. 243 249.

[9] Djukova E.V., Inyakin A.S., Peskov N.V. Recent Trends in Discrete Analysis of Information in Recognition Problems // J. Pattern Recognition and Image Analysis. 2003. V. 13. No. 3. P. 11-13.

[10] Djukova E.V., Inyakin A.S., Peskov N.V. Methods of Combinatorial Analysis in Synthesis of Efficient Recognition Algorithms // J. Pattern Recognition and Image Analysis. 2003. V. 13. No. 3. P. 426-432.

Издательство ООО "МАКС Пресс". Лицензия ИД № 00510 от 01.12.99 г. Подписано к печати 14.01.2004 г. Формат 60x90 1/16. Усл.печ.л. 1,25. Тираж 100 экз. Заказ 062. Тел. 939-3890,939-3891,928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В.Ломоносова.

i- H5î

РНБ Русский фонд

2004-4 23974

ВВЕДЕНИЕ

1 Модели дискретных (логических) процедур распознавания, основанные на построении покрытий классов

1.1 Основные определения. 1.2 Классическая модель голосования но представительным наборам

1.3 Модели голосования по антипредставительным наборам и по покрытиям класса

2 Методы повышения эффективности дискретных процедур распознавания

2.1 Методы оценки информативных характеристик обучающей выборки.

2.2 Выделение типичных объектов в классе для задач распознавания. Разбиение обучающей выборки на базовую и контрольную.

2.3 Быстрый метод вычисления оценок при голосовании по представительным наборам для процедуры скользящего контроля.

3 Метрические свойства множества сг-покрытий целочисленной матрицы

3.1 Основные определения.

3.2 Асимптотика типичных значений числа сг-покрытий и типичной длины сг-покрытия

3.3 Асимптотика типичных значений числа сг-подматриц и порядка сг-подматрицы в случае большого числа строк

4 Конструирование дискретных процедур распознавания с использованием аппарата логических функций

4.1 Связь задач построения множества элементарных классификаторов, построения нормальных форм логических <■• функций и поиска покрытий целочисленных матриц

4.2 Метрические свойства дизъюнктивных нормальных форм двузначных логических функций, определенных на к-ичпых п-мерных наборах.

5 Апробация предложенных методов на реальных задачах г 5.1 Решение задач прогнозирования результатов лечения онкозаболеваний

5.2 Оценка важности признаков в задаче анализа результатов социологического опроса.

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

Стандартная постановка задачи распознавания заключается в следующем [65]. Исследуется некоторое множество объектов М. Объекты этого множества описываются системой признаков {х\,. ,хп}. Известно, что множество М иредставимо в виде объединения непересекающихся подмножеств (классов) К\,. ,К\. Имеется конечный набор объектов {51,., 5т} из М, о которых известно, каким классам они принадлежат (это прецеденты или обучающие объекты). Требуется по предъявленному набору значений признаков, т.е. описанию некоторого объекта 5 из М , о котором, вообще говоря, неизвестно, какому классу он принадлежит, определить этот класс.

Для решения прикладных задач распознавания успешно применяются методы, основанные на комбинаторном анализе признаковых описаний объектов, которые особенно эффективны в случае, когда информация целочисленная и число допустимых значений каждого признака невелико. При конструировании этих методов используется аппарат дискретной математики, в частности, булевой алгебры, теории дизъюнктивных нормальных форм и теории покрытий булевых и целочисленных матриц. Основополагающими работами являются работы Ю.И. Журавлева, С.В. Яблонского и М.Н. Вайицвайга [8,13,31,85].

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

Основной задачей при построения дискретных процедур распознавания является поиск информативных подописаний (или фрагментов описаний) объектов. Информативными считаются такие фрагменты, которые отражают определенные закономерности в описаниях обучающих объектов, т.е. наличие или, наоборот, отсутствие этих фрагментов в классифицируемом объекте позволяет судить о его принадлежности тому или иному классу. В классических дискретных процедурах распознавания информативными считаются такие фрагменты, которые встречаются в описаниях объектов одного класса, но не встре-* чаются в описаниях объектов остальных классов. Рассматриваемые фрагменты, как правило, имеют содержательное описание в терминах прикладной области, в которой решается задача, и поэтому построенный алгоритм распознавания также легко интерпретируется. Однако выделение информативных подописаний во многих случаях оказывается сложным в силу чисто вычислительных трудностей переборного м характера. Как правило, задача сводится к поиску тупиковых покрытий булевых и целочисленных матриц и может быть также сформулирована как задача построения нормальной формы логической функции [52, 85].

Наличие большого перебора, а также первоначально низкая производительность вычислительной техники явились причиной того, что основные усилия в течении многих лет были направлены на разработку общей теории сложности решения задач дискретного анализа информации и синтеза асимптотически оптимальных алгоритмов поиска информативных фрагментов. Полученные в данном направлении результаты позволили в определенной степени преодолеть указанные трудности и значительно усовершенствовать такие классические модели как тестовый алгоритм и алгоритм голосования по представительным наборам. Здесь следует отметить работы В.А. Слепян, В.Н. Носкова, Е.В. Дюковой и A.A. Андреева [1-3, 36-52, 74, 75, 81-83]. При этом вопросам качества распознавания не уделялось достаточного внимания. Укажем некоторые проблемы, от решения которых зависит результат распознавания.

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

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

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

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

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

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

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

При этом под качеством распознавания понимается качество алгоритма вне обучающей выборки (способность алгоритма к обобщению или экстраполяции), которое в данной работе оценивается по проценту правильно распознанных объектов при проведении процедуры скользящего контроля. На исследованных в работе прикладных задачах предложенные методы позволили повысить качество распознавания на 11-14%.

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

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

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

Простейшим примером корректного алгоритма является следующий. Распознаваемый объект сравнивается с каждым из объектов обучения «$1,.,5т. В случае, если описание объекта 5 совпадает с описанием обучающего объекта 5г-, объект 5 относится к тому классу, которому принадлежит объект в противном случае алгоритм отказывается от распознавания. Нетрудно видеть, что описанный алгоритм является корректным, однако он не сможет распознать ни один объект, описание которого не совпадает с описанием ни одного из обучающих объектов.

Очевидно, что требование полного совпадения описаний расиозпаваемого объекта и одного из обучающих объектов является слишком осторожным. Анализ прикладных задач свидетельствует о том, что вопрос о близости объектов и их принадлежности одному классу можно решать на основе сравнения некоторого множества их подописаний. Поэтому возникает вопрос, как выбирать поднаборы признаков, порождающие такие подописания, по которым будут сравниваться объекты. Один из вариантов ответа на данный вопрос используется в модели алгоритмов вычисления оценок (ABO) [60,65].

Введем следующие обозначения. Пусть Н - некоторый набор из г, г < п, различных целочисленных признаков вида {х^,., xjr}. Близость объектов S' = {а\, а'2,а'п) и S" = (а", ai»,аиз М по набору признаков Н будем оценивать величиной

II, если а'- — а'- ири t = 1,2, .,г: л л

О, в противном случае.

Принципиальная схема построения алгоритмов ABO следующая. В системе признаков ., хп} выделяется совокупность различных подмножеств вида Н = {xjv . г < п не обязательно одинаковой мощности. В дальнейшем выделенные подмножества называются опорными множествами алгоритма, а вся их совокупность обозначается через Cí. Задаются параметры: - параметр, характерезующий представительность объекта S¿, i = 1,2, .,m; Рн - параметр, характерезующий представительность набора (опорного множества) Н, Н £ Г2. Далее проводится процедура голосования или вычисления оценок. Распознаваемый объект S сравнивается с каждым обучающим объектом Si по каждому опорному множеству. Считается, что объект S получает голос за принадлежность классу К, если Si £ К и описания объектов S и Si совпадают по опорному множеству Н ( в этом случае 5г-,Я) = 1). Для каждого класса К, К £ {К\,., К1}, вычисляется оценка принадлежности Г(5, К) объекта 5 классу К, которая имеет вид оценку. Если классов с наибольшей оценкой несколько, то происходит отказ от распознавания. Очевидно, что построенный алгоритм не всегда является корректным. Для корректности этого алгоритма требуется выполнение системы линейных неравенств указанного ниже вида.

Для простоты пусть I = 2, 5г- 6 К\ при 1 < г < т\, 1 < гп\ < т — 1, 5г- € К2 при Ш1 + 1 < г < т. Тогда система неравенств имеет вид

Решение системы сводится к выбору параметров 7г-, г — 1,2,., т, и Рц, Я £ П. В случае, если система несовместна, находится ее максиздссь и далее |С?|- мощность множества (

Г(5т1+х, К2) > Г(5т1+1, К\) мальная совместная подсистемы и из решения этой подсистемы определяются значения параметров 7¿ и Рн

Другой способ добиться корректности алгоритма - выбрать «хорошую» систему опорных множеств. В частности, выбрать ее так, чтобы для любого обучающего объекта S' $ К было выполнено Г(S',K) = 0 и для любого обучающего объекта S" Е К было выполнено Г(5", К) > 0. Это можно сделать следующим образом.

Пусть Н - некоторое опорное множество. Набор признаков Н назовем тестом, если для любых обучающих объектов S' и S", принадлежащих разным классам, выполнено B(SS", Н) = 0. Другими словами, тест - это набор признаков, по которому различаются любые два объекта из разных классов.

Пусть Qt ~ некоторая совокупность тестов. Если совокупность опорных множеств алгоритма состоит из тестов, то очевидно, такой алгоритм является корректным при любых положительных значениях параметров i = 1,2,., m, и Рн, Н G Qт

Если набор признаков Н\ - тест, то любой набор признаков Н2 такой, что Н\ С #2j также является тестом. При этом если объекты близки по #2, то они будут близки и по Hi, если же два объекта близки по по набору столбцов Hi, то они не всегда будут близки по #2. В этом смысле более короткие тесты обладают большей информативностью, и разумно ограничивать длины тестов или строить тупиковые тесты.

Набор признаков Н назовем тупиковым тестом, если выполнены следующие два условия 1) Н - является тестом; 2) любое собственное подмножество набора Н не является тестом. Другими словами тупиковым тестом является неукорачиваемый набор признаков, по которому любые два обучающих объекта из разных классов отличаются друг от друга.

Пусть каждый признак х^ имеет конечное множество допустимых значений Nj.

Пусть Н = {х^,. - некоторый набор признаков, 5 = (а1,.,ап) - объект из обучающей выборки. Фрагмент (а^,., описания объекта 5 обозначим через (5, Н).

Каждый тест Н порождает множество фрагментов описаний объектов вида (5,-, Я), г = 1,2, .,т, где 5г- - обучающий объект, причем каждый из этих фрагментов встречается в некотором классе и не встречается в остальных. При распознавании объектов производится голосование по множеству всех таких фрагментов. Впервые модель тестового алгоритма описана в [31].

Рассмотрим пример. Пусть обучающая выборка состоит из объектов 51 = (0,1,1,0), 52 = (1,2,0,1), 53 = (0,1,0,1), 54 = (1,2,1,0), ¿5 = (1,1,0,1), 5б = (1,171,2), при этом объекты и ¿>3 принадлежат первому классу, а объекты и 5б - второму.

В данном примере тупиковыми тестами являются наборы признаков {х\, Х2, хз}, {х\, Х2, £4} и {х2-,х^х^. Если использовать тестовый алгоритм, то объект 5 = (0,1,2,1) не будет отнесен ни к одному из классов, однако фрагмент (0,1), порождаемый парами (¿>1, {х\, жг}) и (5з, {^1, #2}), содержится в 5 и соответствующих объектах из первого класса и не содержится в объектах из второго класса, что дает нам основание полагать, что распознаваемый объект более близок к первому классу. Таким образом, если при построении алгоритмов распознавания перейти от рассмотрения опорных множеств признаков к анализу фрагментов описаний объектов, можно строить менее осторожные и при этом корректные процедуры. Примерами таких ироцедур являются алгоритмы голосования по представительным наборам или алгоритмы типа "Кора" [8,13].

Фрагмент описания объекта 5' из класса К вида (£", Я) назовем представительным набором для К, если для любого обучающего объекта 5", не принадлежащего классу К, имеет место 5(5', 5", Н) = 0. Фрагмент описания объекта 5' из класса К вида (5', Н) назовем тупиковым представительным набором для К, если выполнены два условия: 1) для любого обучающего объекта 5" £ К имеет место В(Б', 5", Н) = 0; 2) для любого набора Н', Н' С Н , найдется обучающий объект ^ /ЧГ, для которого -¿3(5", 5", Я') = 1.

В классической модели алгоритма голосования по (тупиковым) представительным наборам для каждого класса /С строится множество (тупиковых) представительных наборов, обозначаемое далее через К). Распознавание объекта 5 осуществляется на основе процедуры голосования. В простейшей модификации для оценки принадлежности объекта 5 классу К используется величина

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

Теперь мы можем описать общую схему конструирования дискретных процедур распознавания с использованием понятия элементарно

5',я)еТ(/о го классификатора [56,58,77,87].

Пусть Я - некоторый набор из г различных признаков вида Я = {х^,., xjr}, а = (cti, ., сгг) , Oi - допустимое значение признака Xjn г = 1,2,.,г. Набор а назовем элементарным классификатором, порожденным признаками из Я.

Близость объекта S = (ai,. ,ап) из М и элементарного классификатора а = (ai,., стг), порожденного набором признаков Я, будем оценивать величиной

Множество всех элементарных классификаторов, порожденных наборами признаков из {х\,., хп}, обозначим через С. Таким образом, С = {(¿г, Я)}, где Я С {х1,.,хп}, Я = {хк,., Хуг}, а = (сг1,., оу), с I е А7), при г = 1,2, .,г. Каждый распознающий алгоритм А для каждого класса /С, К Е {К\,., Я/}, строит некоторое подмножество множества С. Обозначим

Распознавание объекта 5 осуществляется на основе вычисления величины В{(7,5, Я) для каждого элемента (сг, Я) множества СА{К), К 6 {.Кь ., К{}, т.е. по каждому элементу множества СА(К) осуществляется процедура голосования. В результате вычисляется оценка Г(5, К) принадлежности объекта 5 классу К. Таким образом, каждый распознающий алгоритм А из рассматриваемого семейства определяется множеством элементарных классификаторов СЛ(К) и способом вычисления оценки Г(5, К), которая получается на основе голосования по элементарным классификаторам из СА(К).

1, если a,jt = crt при t = 1, 2,., г; О, в противном случае. cA = {JcA(Kj).

3 = 1

Например, если А - алгоритм вычисления оценок, то множество состоит из элементарных классификаторов, порождаемых теми фрагментами обучающих объектов, которые порождаются опорными множествами алгоритма А. Если же А - алгоритм голосования по представительным наборам, то СА(К) - некоторое подмножество множества представительных наборов класса К. В обоих случаях оценка Г(S, К) получается на основе суммирования величин B(a,S, Н), где (а,Н)еСА(К).

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

1) каждый фрагмент вида (S',H), где 5' G К, совпадает с (cri,. ,сгг);

2) не все, а лишь некоторые фрагменты вида (SH), где S' G К, совпадают с (cri,., сгг);

3) ни один фрагмент вида (SH), где S' G К, не совпадает с

71,.,СГг).

Первая ситуация встречается крайне редко, поэтому работать с наборами значений признаков, для которых выполняется свойство 1, не представляется возможным. Существенное различие в информативности следующих двух свойств заключается в том, что свойство 2 характеризует лишь некоторое подмножество обучающих объектов из К , а свойство 3 все объекты из К . Следовательно, в случае, когда важно рассматривать класс К изолированно от других классов, напрашивается вывод о большей информативности таких наборов значений признаков, для которых выполнено свойство 3. В указанном случае аргументом за отнесение распознаваемого объекта S в класс

К более естественно считать ситуацию, когда набор значений признаков не присутствует у всех объектов из класса К и не присутствует у объекта 5.

Классические дискретные процедуры распознавания основаны на построении элементарных классификаторов, которые встречаются в описании некоторых объектов рассматриваемого класса (обладают свойством 2). В данной работе предлагаются корректные процедуры, основанные на построении элементарных классификаторов, не встречающихся в описании ии одного объекта рассматриваемого класса (обладающих свойством 3). Этими моделями являются модель голосования по покрытиям класса и модель голосования по антипредставиль-ным наборам [54, 56, 57, 77, 87]. В ряде случаев указанные модели позволяют повысить качество распознавания и требуют меньших вычислительных затрат.

В модели голосования по покрытиям класса множество СЛ(К) состоит из таких элементарных классификаторов, которые не встречаются в описаниях объектов класса К. Такие элементарные классификаторы будем назвать покрытиями класса К. Элементарный классификатор (сг,Н) из СЛ(К) голосует за принадлежность распознаваемого объекта 5 классу К, если а не встречается в описании объекта 5 по набору признаков Н. Принадлежность объекта 5 классу К (в простейшей модификации) оценивается величиной

Г2(5'к) = ШкТ\ £ (1 ~ в(а'н))'

Элементарный классификатор (а, Н) назовем антипредставительным набором класса К, если он не совпадает ни с одним из фрагментов вида (5', Н) , где 5' - обучающий объект из класса К, и совпадает хотя бы с одним фрагментом вида (5", Н) , где 5" - обучающий объект, не принадлежащий классу К. Процедура голосования аналогична процедуре голосования, используемой в алгоритме голосования по покрытиям класса. Принадлежность объекта 5 классу К (в простейшей модификации) оценивается величиной

Гз(5'^)= 1с4ю1 ^ (1 — В(а, 5, #)).

1 ^ П (а,Н)еСА(К)

Нетрудно показать, что представительный набор класса К является антипредствительным для любого другого класса, в случае 1 = 2 антипредставительный набор является представительным для противоположного класса, в случае, когда I > 2 антипредставительный набор для К не всегда является представительным для какого-либо другого класса.

Алгоритмы голосования по покрытиям класса и антипредставительным наборам являются корректными. Здесь корректность достигается за счет того, что для любого обучающего объекта 5' 6 К Г(5', К) = 1 (за принадлежность 5' классу К голосуют все элементарные классификаторы из СА(К)) и Г(5', К') < 1 при К' ф /С, к'е{к

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

В случае, когда I > 2, использование новых процедур дает выигрыш ио времени.

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

Пусть описание обучающего объекта 5, не принадлежащего классу К , похоже на описания некоторых объектов из К. Тогда объект Я «лишает» класс К некоторого множества коротких элементарных классификаторов (тестов, представительных наборов и т.д.), что существенно снижает эффективность алгоритма. Для решения указанной проблемы предлагается разбить обучающую выборку на две подвы-борки, по первой (базовой) построить множество представительных наборов, по второй (контрольной) вычислить их веса. Причем разбить нужно таким образом, чтобы объекты, находящиеся на границе между классами, попали в контрольную нодвыборку, а все остальные (типичные для своих классов) объекты - в базовую подвыборку. Практические эксперименты на прикладных задачах показывают, что такое разбиение увеличивает число коротких элементарных классификаторов из СЛ(К) и тем самым позволяет повысить качество алгоритма распознавания А [53, 55-57, 77, 78, 87].

Для выделения типичных объектов предлагаются два способа. Первый основан на оценке типичности объекта путем вычисления типичности значений признаков [53, 55, 56]. Второй способ использует процедуру скользящего контроля. В данном случае типичными считаются те объекты, которые на скользящем контроле распознаются правильно. Приводится быстрый способ вычисления оценок при голосовании но представительным и тупиковым представительным наборам для процедуры скользящего контроля [77,78,87].

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

Введем следующие обозначения Мт„п, к > 2, - множество всех матриц размера т х п с элементами из {0,1,., к— 1}; Егк - множество всех наборов вида (<7i,., сгг), где сгг- G {0,1,., к — 1}.

Пусть L G а £ ЕНабор Я из г различных столбцов матрицы L назовем тупиковым ст-покрытием, если LH не содержит строку а.

Набор Н из г различных столбцов матрицы L назовем тупиковым сг-покрытием, если выполнены следующие два условия:

1) LH не содержит строку ст;

2) Ьн содержит (с точностью до перестановки строк) подматрицу вида l <?2 Oz . СГГ! <Tr

2 . . £Tr! (JT

2 <?3 . о>i ßr где (Зр ф ор при р = 1,2, .,г . Такую подматрицу будем называть сг-подматрицей. При а = (0,., 0) и к = 2 тупиковое сг-покрытие является неприводимым покрытием, а сг-подматрица - единичной подматрицей.

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

Пусть К 6 {К\,., К{]. Таблицу обучения можно рассматривать как пару матриц Ь\ и ¿2, где Ь\ - матрица, состоящая из описаний обучающих объектов из класса К, а ¿2 - матрица, состоящая из описаний остальных обучающих объектов.

Очевидно, что элементарный классификатор вида (<71,., <7Г), задаваемый парой (Б(,Н), 5г- £ К, Н = {х^,., х^}, является (тупиковым) представительным набором для К тогда и только тогда, когда набор столбцов матрицы Ь\ с номерами не является о-!,., сгг)-покрытием, а набор столбцов Ьч с номерами .71,.,> является (тупиковым) (<71,., сгг)-покрытием.

Элементарный классификатор вида (а\,., <7Г), задаваемый парой (5г-, Я), 5г- £ К, является (тупиковым) аитипредставительным набором для К тогда и только тогда, когда набор столбцов матрицы 1^2 с номерами ] 1,., ]г не является (<71,., сгг)-покрытием, а набор столбцов Ь\ с номерами з 1,., зт является (тупиковым) (<7ь ., о>)-иокрытием.

Элементарный классификатор (<7ь ., сгг), порождаемый набором столбцов Я, является (тупиковым) покрытием класса К тогда и только тогда, когда набор столбцов матрицы Ь\ с номерами jl,.,]г является (тупиковым) (<71,., сгг)-покрытием.

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

Введем обозначения:

- интервал (1од^тпп,п)]

- интервал log* тпп - i logfc logfc mn - logfc logfc logfc n, i logfc mn - i logfc logfc mn + logfc logfc logfc n); an « öri означает, что lim(an/&n) = 1 при n —> oo.

Пусть C(L,a) - множество всех пар вида (Н, er) , где Н - <т-покрытие матрицы L, В(Ь,а) - множество всех пар вида (Н,а), где Н - тупиковое сг-иокрытие матрицы L, S(L,a) - совокупность всех сг-подматриц матрицы L.

Положим п

C(L) = U U C(L,<7), г—1 стеЕ^ п U U г=1 эд = 1)и

Нас будут интересовать асимптотические оценки чисел |C(L)|, \B(L)\ и |5(L)| для почти всех матриц L из при п —> оо. Выявление типичной ситуации будет связано с высказываниями типа «Для почти всех матриц L из М£п при п —> со выполнено свойство ß», причем свойство ß также может иметь предельный характер. Это означает, что доля тех матриц из М!Цп для которых с ^-точностью выполнено свойство (3, стремиться к 1 и одновременно е стремиться к О при п —> оо.

Ранее в [37-40, 42, 44, 45, 47, 48, 50, 52, 86] изучался случай, когда число строк в матрице но порядку меньше числа столбцов, а именно случай, когда та < п < к™0, а > 1, /3 < 1. Показано, что в данном случае величина \В{Ь)\ почти всегда (для почти всех матриц Ь из при п —> оо асимптотически совпадает с величиной ^(Ь)! и по порядку меньше числа покрытий. На основании этого факта был построен асимптотически оптимальный алгоритм поиска покрытий из В(Ь).

На его основе в [90,91] построен точный алгоритм с полиномиальной временной задержкой (при наличии незначительного числа повторяющихся шагов).

В данной работе рассмотрен прямо противоположный случай, а именно, когда па < т < кпв, а > 1, < 1 [54,56,57,87].

Получены асимптотики типичных значений числа подматриц из Б{Ь) и порядка подматрицы из £(£), а именно доказана

Теорема 3.3.1. Если па < т < кпв, а > 1, ¡3 < 1, то для почти всех матриц Ь из при тг —» оо справедливо и порядки почти всех подматриц из 5(Ь) принадлеэ/сат интервалу п

Пусть тп

Тогда справедлива

Теорема 3.3.2. Для почти всех матриц L £ при п —V оо имеет место

Si(L)\ = 0.

Из теоремы 3.3.2 следует, что почти все матрицы в не имеют ст-подматриц, порядок которых больше logfc тп.

Для практически общего случая в [54,56,57,87] получены асимптотики типичных значений величины \C(L)\ и длины покрытия из C(L), а именно, доказана

Теорема 3.2.1. Если т < кп, ß < 1, то для почти всех матриц L из при п —> оо имеет место

C{L)\ » £ Crnkr и длины почти всех покрытий из C(L) принадлежат интервалу Ф®. Пусть го = log^m — log^logj-mlnfcn) и пусть

Ci(£)= U U

Г<г0 о£Е1

Тогда справедлива

Теорема 3.2.2. Для почти всех матриц L 6 при п —> оо имеет место

Сг(Ь)\ = 0.

Из теоремы 3.2.2 следует, что при г < log^m — \ogk(\ogkm\nkn) почти все матрицы не имеют сг-покрытий длины г.

На основе сравнения оценок, приведенных в теоремах 3.3.1 и 3.2.1, доказана

Теорема 3.3.3. Если па < т < кп°, а > 1, ß < 1/2, то для почти всех матриц L из Mfnn при п —> оо справедливо \S(L)\/\B(L)\ оо.

Покажем, что задачу нахождения покрытий целочисленной матрицы с элементами из множества {0,1,., к — 1} можно сформулировать как задачу построения сокращенной ДНФ двузначной логической функции, заданной на &-ичных п-мерных наборах [45, 47, 48, 52, 86].

Пусть на наборах из задана всюду или частично определенная логическая функция /, принимающая значения из множества {0,1}, А/ - множество единиц этой функции, В/ - множество ее нулей. Введем ряд определений. Пусть переменная х принимает значения из множества а е Положим

II, если х = а: О, если х ф о.

Элементарной конъюнкцией (э.к.) называется выражение вида х. где все хразличны. Число г называется рангом конъюнкции. Интервал истинности э.к. 03 будем обозначать через Л^.

Введем понятия допустимой, неприводимой и максимальной конъюнкции для функции /.

Э.к. 03 называется допустимой для /, если Л^ПЛу ф 0 и Л^П-В/ =

0.

Э.к. 03 называется неприводимой для /, если не существует элементарной конъюнкции 93' такой, что А/®» Э Л/© и N<8>Г\В/ = N<8ПВ/.

Э.к. 03 называется максимальной для К, если 03 допустимая конъюнкция и не существует допустимой конъюнкции 03' такой, что Л^/ Э

Я».

Пусть А/ состоит из наборов (скц, оси,., <*!„),., (аиь аи2,., аип В/ - из наборов (/?111 012,., 01„), .(0«1, 0„2, • • . , 0ип).

Из наборов А/ составим матрицу Ь\ вида с*п с*12 . осы

С*21 ОС22 . ОС2п и1 аи2 • • • ОСип

Из наборов Bf составим матрицу Ь2 вида

011 012 01п

021 022 ••. 02п

0«1 Ри2 • - • Ат

Утверждение 4.1.1. Э.к. является допустимой для

Р тогда и только тогда, когда набор столбцов с номерами . является ., аг)-покрытием матрицы Ь2

Утверждение 4.1.2. Э.к. х. является неприводимой для Р тогда и только тогда, когда в наборе столбцов с номерами . ,]г содержится (<71,., аг)-подматрица матрицы ¿2.

Утверждение 4.1.3. Э.к. . является максимальной для Р тогда и только тогда, когда набор столбцов с номерами jl,.,зг является тупиковым (о-!,., аг)-покрытием матрицы Ь2.

Утверждение 4.1.4. Э.к. является максимальной для / тогда и только тогда, когда набор столбцов с номерами Л» • • •»Зг является тупиковым (<Т1,., аг)-покрытием матрицы 1,2 и подматрица матрицы Ь\, образованная столбцами с номерами Л > • • • содержит хотя бы одну из строк вида ., аг).

В силу утверждений 4.1.1 - 4.1.3 для числа и ранга допустимых конъюнкций двузначной логической функции, заданной на А>ичных пмерных наборах можно сформулировать утверждения, аналогичные теоремам 3.2.1 - 3.2.2, а также получить верхнюю ассимптотическую оценку числа максимальных конъюнкций.

Настоящая работа состоит из введения пяти глав и заключения.

В главе 1 описан классический алгоритм голосования по представительным наборам и предлагаются модели алгоритмов голосования по антипредставительным наборам и покрытиям классов.

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

Глава 3 посвящена получению асимптотических оценок типичных значений числа покрытий и длины покрытия, а также числа о-подматриц и размера сг-подматриц.

В главе 4 сформулированы основные принципы конструирования ^ дискретных процедур распознавания с использованием аппарата логических функций. Рассмотрена связь между задачей нахождения покрытий целочисленной матрицы и задачей построения совершенной ДНФ двузначной логической функции заданной на &-ичных наборах. Получены асимптотики типичных значений для числа допустимых конъюнкций для указанных функций и ранга допустимой конъюнкции, а также верхние асимптотические оценки числа максимальных конъюнкций.

В главе 5 приведены результаты тестирования предложенных в работе подходов на реальных задачах. Исследованы задачи прогнозирования результатов лечения онкобольных и анализа результатов социологического опроса. Проведено сравнение новых моделей с классическим алгоритмом голосования по представительным наборам.

Т'

ЗАКЛЮЧЕНИЕ

Работа посвящена исследованию дискретных процедур распознавания. При построении этих процедур важнейшим этапом является поиск информативных фрагментов признаковых описаний объектов. В работе предложены новые подходы к поиску таких фрагментов.

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

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

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

4) Получены асимптотики типичных значений числа покрытий и длины покрытия целочисленной матрицы для практически общего случая.

5) Получены асимптотики типичных значений числа сг-подматриц и ранга <7-подматрицы для случая, когда число строк в матрице значительно превосходит число столбцов. Показано, что в этом случае число сг-подматриц по порядку больше числа тупиковых ст-покрытий.

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

1. Андреев А. Е. Некоторые вопросы тестового распознавания образов // ДАН СССР. 1981, Т. 255, № 4. С. 781-734.

2. Андреев А. Е. О тупиковых и минимальных тестах // ДАН СССР. 1981, Т. 256, № 3. С. 521-524.

3. Андреев А. Е. Об асимптотическом поведении числа тупиковых тестов и минимальной длины теста для почти всех таблиц // Проблемы кибернетики. Вып. 41. М.: Наука, 1984. С. 117-141.

4. Айзенберг H.H., Журавлев Ю.И., Пилюгин C.B. Применение сверточных алгебр для построения корректных распознающих алгоритмов //Ж. вычжсл. матем. и матем. физ. 1987. Т. 27, № 6. С. 912-923.

5. Асланян А., Журавлев Ю. И. Об одном подходе к построению эффективных алгоритмов распознавания // Ж. вычисл. матем. и матем. физ. 1985. Т. 25, № 2. С. 283-291.

6. Асланян JI. А. Об одном методе распознаваний, основанном на разделении классов дизъюнктивными нормальными формами // Кибернетика. 1975. JV* 5. С. 103-110.

7. Асланян Л. А. Алгоритмы распознавания с логическими отделителями // Сб. работ по матем. кибернетике. Вып. 1. М.: ВЦ АН СССР, 1976. С. 116-131.

8. Баскакова Л. В., Журавлев Ю. И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств // Ж. вычисл. матем. и матем. физ. 1981. Т. 21, № 5. С. 1264-1275.

9. Бушманов О. Н. Класс алгоритмов распознавания, основанный на поиске эмпирических закономерностей // М: ВЦ РАН. 1992. 21 с.

10. Бушманов 0. Н., Дюкова Е. В., Журавлев Ю. И., Кочетков Д. В., Рязанов В. В. Система анализа и распознавания образов // Распознавание, классификация, прогноз (математические методы и ИХ применение). М.: Наука, 1989. Вып. 2. С. 250-273.

11. Бушманов 0. Н., Дюкова Е. В., Рязанов В. В. Система распознавания, таксономии и анализа стандартных данных // Тез. III Всесоюзной конф. "Мат. методы распознавания образов".

12. Валев В., Беликов М., Дюкова Е. В, Программный комплекс для решения задач распознавания на основе построения эмпирических закономерностей . М.: ВЦ АН СССР, 1988. 20 с.

13. Вайнцвайг М. Н. Алгоритм обучения распознаванию образов «Кора» // Алгоритмы обучения распознаванию образов. М.: Сов. радио, 1973. С. 82-91.

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

15. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979. 448 с.

16. Вапник В. Н. Индуктивные принципы поиска эмпирических закономерностей // Распознавание, классификация, прогноз (математические методы и их применение). М.: Наука, 1988. Вып. 1.С. 17-81 .

17. Васильев В, И. Распознающие системы. .Киев: Наукова думка,1983. 466 С.

18. Вентцель Н. С. Теория вероятностей // М.: Наука, 1964.

19. Вешторт А. М., Зуев Ю. А., Краснопрошин В. В. Двухуровневая схема распознавания с логическим корректором // Распознавание, классификация, прогноз (математические методы и их применение). М.: Наука, 1989. Вып. 2. С. 73-98.

20. Волжков Ю, К., Дюкова Е. В., Левашов Е. А., Рязанов В. В. Применение методов распознавания образов для прогнозирования свойств твердых сплавов группы СТИМ, М: МИСИС, 1988. С. 40-43.

21. Гельфанд И. М., Губермаи Ш. А., Шифрин М, А. Прогнозирование и распознавание в медицинских задачах // Распознавание, классификация, прогноз, М.: Наука, 1989, С, 201-228,

22. Глаголев В, В. Некоторые оценки дизъюнктивных нормальных форм функции алгебры логики // Проблемы кибернетики. М.

23. Наука,1967. ВЫП. 19, С. 75-94. Глаз А. Б. Параметрическая и структурная адаптация правил в задачах распознавания, Рига: Зинатне, 1988. 172 с.

24. Гольдберг С. И. Об одном методе распознавания образов "Совокупный антисиндром"// Вычисл. системы, Новосибирск. 1978. Вып. 76. С. 83-90,

25. Горелик A. JL, Гуревич И. В., Скрипник В. А. Современное состояние проблемы распознавания. М.: Радио и связь, 1984. 160 с,

26. Горелик A. JL, Скрипник В. А, Методы распознавания. М.: Высшая школа, 1984. 208 с,

27. Гренандер У. Лекции но теории образов. М.: Мир, Т. 1. 1979. 384 е.; Т, 2. 1981. 448 е.; Т. 3. 1983, 432 с.

28. Гуревич И. В., Журавлев Ю. И. Минимизация булевых функций и эффективные алгоритмы распознавания // Кибернетика. 1974,, № 3. С. 16-20.

29. Денисова P.A. Метод синтеза тупиковых представительных наборов для fc-значных таблиц, М.: ВЦ АН СССР, 1984. 29 с.

30. Дискретная математика и математические вопросы кибернетики / Под ред. С.Б. Яблонского, О.Б. Лупанова, М.: Наука"1974. 312 с.

31. Дмитриев А. И., Журавлев Ю. И., Кренделев Ф. П. О математических принципах классификации предметов или явлений //

32. Дискретный анализ. Новосибирск: ИМ СО АН СССР, Вып. 7. 1966. С. 1-17

33. Дмитриев А. И., Журавлев Ю. И., Кренделев Ф. П. Об одном принципе классификации и прогноза геологических объектов и явлений // Известия Сиб. отд. АН СССР, Геология и геофизика. 1968. Т. 5, С. 50-64,

34. Долгоруков А. Ю., Дюкова Е. В. Об одном способе вычисления информационных характеристик обучающей // Тезисы Всероссийской конференции "Математические методы распознавания образов (ММРО-6)". г. Москва, 1993. С. 22-23.

35. Донской В. И. Алгоритмы обучения, основанные на построении решающих деревьев // Ж. вычисл. матем. и матем. физ. 1982. Т. 22, № 4. С. 963-974.

36. Донской В. И. Слабоопределениые задачи линейного булева программирования с частично заданным множеством допустимых решений // Ж. вычисл. матем. и матем. физ. 1988. Т. 28, № 9, С. 1379-1385.

37. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир. 1976. 511 с.

38. Дюкова Е. В. Об одном алгоритме построения тупиковых тестов для бинарных таблиц // Сборник работ по дискретной математике. М.: ВЦ АН СССРб 1976. Вып. 1. С. 167-185

39. Дюкова Е. В. Об асимптотически оптимальном алгоритме построения тупиковых тестов // ДАН СССР. 1977. Т. 233, К« 4. С. 527-530

40. Дюкова Е. В. Об асимптотически оптимальном алгоритме построения тупиковых тестов для одного класса Ахзначных таблиц // Тез. докл. IV Всесоюз. конф. но проблемам теоретический кибернетики. Новосибирск: Изд-во СО АК СССР, 1977. С. 197-199.

41. Дюкова Е. В. Об асимптотически оптимальном алгоритме построения тупиковых, тестов для бинарных таблиц // Проблемы кибернетики. М.: Наука, 1978. Вып. 34. С. 169-186.

42. Дюкова Е. В. Построение тупиковых тестов для &-значных таблиц // ДАН СССР. 1978. Т.238. № 6. С. 1279-1282

43. Дюкова Е.В., Журавлев Ю.И., Зенкин A.A. и др. Пакет прикладных программ для решения задач распознавания и классификации (ПАРК). М.: ВЦ АН СССР, 1981. 23 с.

44. Дюкова Е. В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания // Проблемы кибернетики. Вып. 39, М.: Наука, 1982, С. 165-199.

45. Дюкова Е. В., Рязанов В. В. 0 решении прикладных задач алгоритмами распознавания, основанными на принципе голосования. М.: ВЦ АН СССР, 1986. 26 с.

46. Дюкова Е. В. 0 метрических свойствах алгоритмов типа «Кора» для одного класса бинарных таблиц. М.: ВЦ АН СССР, 1986, 17 с.

47. Дюкова Е. В. О сложности реализации некоторых процедур распознавания // Ж. вычисл. матем. и матем. физ. 1987. Т. 27, № 1. С. 114-127.4б. Дюкова Е. В. Об одной параметрической модели алгоритмов распознавания типа "Кора". М.: ВЦ АН СССР, 1988, 23 с.

48. Дюкова Е. В. Алгоритмы распознавания типа "Кора": сложность реализации и метрические свойства // Распознавание, классификация, прогноз (математические методы и их применение). М.: Наука" 1989. Вып. 2. С. 99-125.

49. Дюкова Е. В. О решении систем булевых квазинельсоновского типа // Вопросы кибернетики / Дискретная математика. Методы и применение / М.: АН СССР, Научный Совет но комплексной проблеме "Кибернетика", 1983. с. 5-19.

50. Дюкова Е. В., Карнеева М. J1. Модели алгоритмов, основанные на различных способах перекодировки исходной информации // Матем. методы в распознавании образов и дискретной оптимизации. М.: ВЦ АН СССР, 1990. С. 43-56.

51. Дюкова Е. В. Асимптотические оценки некоторых характеристик множества представительных наборов и задача об устойчивости // Ж. вычисл. матем. и матем. физ. 1995. Т. 35, № 1. С. 122-184.

52. Дюкова Е.В., Журавлев Ю.М., Рудаков К.В. Об алгебро-логическом синтезе корректных процедур распознавания на базе элементарных алгоритмов // Ж. вычисл. матем. и матем. физ. 1996. Т. 36, 1 8. С. 217-225.

53. Дюкова Е. В., Журавлев Ю. И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. №8. С.1264-1278.

54. Дюкова Е. В., Песков Н. В. О некоторых подходах к вычислению информативных характеристик обучающей выборки // Докл. Всеросс. Конф. "Матем. методы распознавания образов -9м. М.: АЛЕВ-В, 1999, С. 181-183.

55. Дюкова Е. В., Песков Н. В. О дискретных процедурах распознавания, основанных на построении покрытий классов // Докл. Всеросс. Конф. "Матем. методы распознавания образов 10", М.: АЛЕВ-В, 2001, С. 48-51.

56. Дюкова Е.В., Песков Н.В. Информативность признаков, отдельных значений признаков и фрагментов описаний объектов // Докл. Всеросс. конф. "Математические методы распознавания образов 10", М.: АЛЕВ-В, 2001. С. 44 47.

57. Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // Ж. вычисл. матем. и матем. физ. 2002. Том 42, № 5, С. 741-753.

58. Дюкова Е.В., Инякин А.С., Песков Н.В. О некоторых направлениях современных исследований в области дискретного анализа информации в проблеме распознавания // Труды межд. Конф. "РОАИ-6-2002", Великий Новгород, 2002. Т. 1. С. 203-208.

59. Дюкова Е.В. Дискрентиые (логические) процедуры распознавания: принципы конструирования, сложность реализации иосновные модели //Учебное пособие для студентов Математических факультетов педвузов. М: МПГУ 2003 г. 30 с.

60. Журавлев Ю. И. Об одном классе не всюду определенных функций алгебры логики // Дискретиый анализ. Новосибирск: ИМ СО АН СССР, Вып. 2, 1964. С. 23-27.

61. Журавлев Ю. И., Никифоров В. В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. Л 3. С. 1-11.

62. Журавлев Ю. И., Мирошник С. Н., Швартин С. М. Об одном подходе к оптимизации в классе параметрических алгоритмов распознавания // Ж. вычисл. матем. и матем. физ. 1975. Т. 16, № 1, С, 209-218.

63. Журавлев Ю. И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации // ДАН СССР.

64. Журавлев Ю. И. Непараметрические задачи распознавания образов // Кибернетика. 1976. № 6. С. 93-103.

65. Журавлев Ю. И., Зенкин А. А., Зенкин А. И., Исаев И. В., Кольцов П. П., Кочетков Д, В., Рязанов В. В. Задачи распознавания или классификации со стандартной обучающей информацией // Ж. вычисл. матем. и матем. физ. 1980, Т. 20, № 5. С. 1294-1309.

66. Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Пробл. кибернетики. М.: Наука, 1978. Вып. 33. С. 5-68.

67. Журавлев Ю. И., Платоненко И. М. Об экономном умножении булевых уравнений: // Ж. вычиел. матем. и матем. физ. 1984. Т. 20, № 5. С. 1294-1309.

68. Журавлев Ю. И., Коган А. Ю. Реализация булевых функций с малым числом нулей дизъюнктивными нормальными формами и смежные задачи // ДАН СССР. 1985. Т. 285, № 4. С. 795-799.

69. Журавлев Ю.И. Об алгоритмах распознавания с представительными наборами (о логических алгоритмах). Ж. вычисл. матем. и матем. физ. 2002. Том 42, № 5, С. 1425-1435.

70. Катериночкина Н. Н. Поиск максимального верхнего нуля монотонной функции алгебры логики // ДАН СССР. 1975, Т. 224, № 3. С. 557-560,

71. Коган Ю. А. О дизъюнктивных нормальных формах булевых функций, с малым числом нулей // Ж. вычисл. матем. и матем. физ. 1987. Т, 27. 16, С. 924-931.

72. Константинов Р. М., Королева 3. Е., Кудрявцев В. Б. О комбинаторно-логическом подходе к задачам прогноза рудо-носности // Проблемы кибернетики. Вып.30. М.: Наука, 1975. С. 5-33.

73. Кузнецов В. Е. Об одном стохастическом алгоритме вычисления информативных характеристик таблиц по методу тестов // Дискретный анализ. Новосибирск: ИМ СО АН СССР, 1973. Вып. 23. С. 8-23.

74. Мадатян X. А. Оценка числа представительных наборов дляодного класса бинарных таблиц // Math. Problems In Compiit, Theory. Banach Center Pitbls, Warsaw, 1988. V. 21. P. 513-522.

75. Носков В. Н. О тупиковых и минимальных тестах для одного класса таблиц // Дискретный анализ. Новосибирск: ИМ СО АН СССР, 1968. вып. 12. С. 27-49.

76. Носков В. Н., Слепян В. А. О числе тупиковых тестов для одного класса таблиц // Кибернетика. 1972. № 1. С. 60-65.

77. Платоненко И. М. О реализации алгоритмов типа "Кора"с помощью решения систем булевых уравнений специального вида. М.: ВЦ АН. СССР, 1983. 21 с.

78. Песков Н.В. О некоторых подходах к конструированию дискретных процедур распознавания // Сообщения по прикладной математике. М.: ВЦ РАН, 2002. 28с.

79. Песков Н.В. Об одном подходе к повышению эффективности алгоритмов распознавания // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2002. С. 73-74.

80. Рудаков К. В. О числе гиперплоскостей, разделяющих конечные множества в эвклидовом пространстве // ДАН СССР, 1976. Т. 231, № 6. С. 1296-1299.

81. Сапоженко А. А. Оценка длины и числа тупиковых д.н.ф. для почти всех не всюду определенных булевых функций // Матем. заметки. 1980. Т. 28. № 2. С. 279-300.

82. Слепян В.А. Параметры распределения, тупиковых тестов и веса столбцов в бинарных таблицах // Дискретный анализ. Новосибирск: ИМ СО АН' СССР, 1969. Вып. 14. С. 28-43.

83. Слепян В. А. О числе тупиковых тестов и о мерах информативности столбца для почти всех бинарных таблиц // ДАН СССР. 1987. Т. 297, № 1, С. 43-46.

84. Слепян В. А. Длина минимального теста для некоторого класса таблиц // Дискретный анализ. Новосибирск: ММ СО АН СССР, 1973. Вып. 23. С. 59-71.

85. Слуцкая T.JI. Алгоритмы вычисления информационных весов // Дискретный анализ. Новосибирск: ИМ СО АН СССР, 1966, Вып. 12. С. 75-90.

86. Чегис И.А., Яблонский С.В. Логические способы контроля электрических схем // Труды Матем. ин-та им. В.А.Стеклова АН СССР. 1958, Т. 51. С. 270-360.

87. Djukova Е. V., Zhuravlev Yu. 1. Diskrete methods of information analysis and algorithm synthesis //J. Pattern Recognition and Image Analys., 1997. V. 7. № 2. P. 192-207.

88. Djukova E.V., Peskov N.V. Selection of Typical Objects in Classes for Recognition Problems //J. Pattern Recognition and Image Analysis. 2002. V. 12. No. 3. P. 243 249.

89. Djukova E.V., Inyakin A.S., Peskov N.V. Recent Trends in Discrete Analysis of Information in Recognition Problems // J. Pattern Recognition and Image Analysis. 2003. V. 13. No. 3. P. 11-13.

90. Djukova E.V., Inyakin A.S., Peskov N.V. Methods of Combinatorial Analysis in Synthesis of Efficient Recognition Algorithms // J. Pattern Recognition and Image Analysis. 2003. V. 13. No. 3. P. 426-432.

91. Djukova E.V. Discrete Recognition Procedures: The Complexity of Realization //J. Pattern Recognition and Image Analysis. 2003. V. 13. No. 1. P. 8-10.

92. Djukova E.V. Discrete (Logical) Recognition Procedures: Principles of Construction, Complexity of Realization and Basic Modeles // J. Pattern Recognition and Image Analysis. 2003. V. 13. No. 3. P. 417-425.