Исследование в области сложности алгебро-логического анализа данных и синтеза распознающих процедур тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Сотнезов, Роман Михайлович

• Сотнезов, Роман Михайлович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Сотнезов, Роман Михайлович

Оглавление

Введение

Глава 1. Синтез процедур распознавания с использованием алгебро-логического подхода

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

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

1.3. Построение корректных наборов эл.кл. класса

1.4. Модели голосования по монотонным и антимонотонным корректным наборам эл.кл. класса

1.5. Связь алгебро-логического подхода с классическими логическими процедурами распознавания

1.6. Обобщение алгебро-логического подхода на случай произвольного набора распознающих алгоритмов

1.7. Сложность задачи перечисления корректных наборов эл.кл

1.8. Тестирование моделей голосования по (монотонным) корректным наборам эл.кл. классов

Глава 2.Корректное понижение значности информации в задачах распознавания

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

2.2. Алгоритмы поиска оптимальной корректной перекодировки КОД1

2.3. Однокритериальные генетические алгоритмы поиска оптимальной корректной перекодировки КОД2, КОДЗ, КОД4

2.4. Двухкритериальный генетический алгоритм поиска оптимальной корректной перекодировки КОД5

2.5. Результаты тестирования

Глава 3.Генетические алгоритмы в задачах дискретной оптимизации

3.1. Постановка задачи

3.2. Представление особей в генетическом алгоритме

3.3. Формирование начальной популяции

3.4. Функция приспособленности и выбор родительских особей

3.5. Операторы скрещивания и мутации

3.6. Восстановление допустимости решения

3.7. Обновление популяции

3.8. Описание алгоритмов ОАВтагу и ОА1ЧопВтагу

3.9. Результаты вычислений на тестовых задачах

3.10. Адаптация алгоритмов ОаВтагу и ОаМопВтагу для многопроцессорных комплексов

Глава 4. Метрические свойства множества тупиковых покрытий булевых и целочисленных матриц

4.1. Основные понятия и результаты, полученные ранее

4.2. Метрические свойства множества покрытий булевых и целочисленных матриц в случае п <т

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

4.4.0 сложности алгоритмов построения тупиковых покрытий булевых и целочисленных матриц, основанных на перечислении совместимых наборов столбцов

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Исследование в области сложности алгебро-логического анализа данных и синтеза распознающих процедур»

Введение

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

Постановка задачи распознавания по прецедентам заключается в следующем. Исследуется некоторое множество объектов М, про которое известно, что оно может быть разбито на непересекающиеся подмножества (классы) Кг,...,К1,1 > 2. Под прецедентной (обучающей) информацией понимается совокупность примеров описаний изучаемых объектов, полученная на основе измерения или наблюдения ряда характеристик этих объектов, а также те «ответы», которые должен был бы дать «идеальный» алгоритм, решая задачу классификации для заданной совокупности описаний. Подлежащие измерению или наблюдению характеристики называются признаками. Требуется уметь классифицировать объекты, не вошедшие в обучающую выборку, т.е. по признаковому описанию каждого такого объекта определять, какому классу он принадлежит. Фактически нужно сравнить вновь предъявленное описание с материалом обучения. Существуют разные мнения о том, как проводить подобное сравнение.

Развиваемый в данной работе подход к задаче распознавания по прецедентам базируется на применении аппарата дискретной математики с использованием логических и алгебро-логических методов анализа данных. Основы проблематики были заложены в работах C.B. Яблонского, Ю.И.

Журавлёва, М.Н. Вайнцвайга и М.М. Бонгарда [4, 6, 7, 9, 42] и развиты в [3, 8, 10-27, 33, 50-62].

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

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

Пусть {х1,...,хп} - совокупность целочисленных признаков, используемая для описания объектов из М и пусть Я = ...,Х]г}- набор из г различных признаков, г < п, а = (аг>... ,аг), а^- допустимое значение признака х^ при I = 1,2,..., г (предполагается, что число допустимых значений каждого признака ограничено). Пара (Я, о) называется элементарным классификатором (эл.кл.).

Пусть 5 = (а1; ...,ап), Б ЕМ. Набор признаков Н = {х;1,... ,х)г} выделяет в описании объекта 5 фрагмент (а;1,..., а^), который обозначается через (5, Я).

Близость объекта 5 из М и эл.кл. (Я, <т) оценивается величиной Д(ад(5) равной 1, если (5, Я) = о, и равной 0, в противном случае.

Построение распознающего алгоритма А основано на конструировании для каждого класса К, К Е {Къ ..., К¿}, множества эл.кл. СА(К) и проведении процедуры голосования по каждому эл.кл. из СА(К{) и СА(К2) и ... и С^К^).

В зависимости от значения функции 5(Яо.)(5), (Я;<т) £ СА(К), распознаваемый объект 51 либо получает голос за принадлежность классу К, либо не получает этого голоса. Оценка Г(5, К) принадлежности объекта 5 классу К вычисляется на основе суммирования голосов, полученных при голосовании по всем эл.кл. из СА(К). Анализ оценок Г (б1, Кг),..., Г (5, К{) позволяет классифицировать объект Я.

Особое внимание уделяется понятию корректного эл.кл. класса К.

Пусть Т - обучающая выборка, К £ {Кг,..., Кг], К = {Кх и ... и К^К. Предполагается, что любые два обучающих объекта из Г, принадлежащие разным классам, имеют разные описания.

Эл.кл. (Я, сг) не является корректным для класса К, если выполнены два условия: 1) (5', Я) = а хотя бы для одного обучающего объекта 5' из К; 2) (5", Я) = о хотя бы для одного обучающего объекта 5" из К. Во всех остальных случаях эл.кл. (Я, сг) считается корректным для К. В существующих алгоритмах используются корректные эл.кл. трех типов, перечисленных ниже.

Эл.кл. типа 1. Выполнено условие 1), но не выполнено условие 2).

Эл.кл. типа 2. Не выполнено условие 1), но выполнено условие 2).

Эл.кл. типа 3. Не выполнено условие 2).

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

Рассмотрим примеры таких алгоритмов.

В алгоритмах голосования по представительным наборам [4, 15, 17, 23, 24, 51, 52, 54, 57, 58] множество СА(К) состоит из корректных эл.кл. типа 1. Пусть (Я, сг) - корректный эл.кл. для класса К типа 1. Тогда существует обучающий объект Б' Е К такой, что (£', Я) = а и для любого обучающего объекта 5" е К выполнено (5", Я) ^ ст. Фрагмент (5"', Я) называется представительным набором для класса К.

В простейшей модификации модели алгоритма голосования по представительным наборам оценка принадлежности К) объекта 5 к классу К имеет вид

где СА (К) - используемое подмножество эл.кл. для К, Я (Т, К) - множество обучающих объектов из К. Очевидно, алгоритм голосования по представительным наборам является корректным.

Другим примером корректного алгоритма является модель алгоритма голосования по антипредставительным наборам [23, 24], в которой используются корректные эл.кл. типа 2. Антипредставителъный набор - это фрагмент (5", Я), где 5" - обучающий объект из К, при этом для любого обучающего объекта Б' из К выполнено (З^Я) Ф (5Я). В простейшей модификации данной модели оценка принадлежности Г2(5', К) объекта 5 к классу К имеет вид

где СА(К) - используемое подмножество корректных эл.кл. для К типа 2, Я (Г, К) - множество обучающих объектов из К.

(.н,сг)есА(к) 5'е/?(гд), (5',Я)=(Т

В тестовых алгоритмах осуществляется поиск специальных наборов признаков - тестов. Набор признаков Я = {хд, ...,Xjr), Я Q {х1> ...,хп} называется тестом, если для любого класса К Е {Къ ...,К{] и любого обучающего объекта SEK фрагмент (S, Я) является представительным набором класса К. Таким образом, тестом является набор признаков, позволяющий различать любые два обучающих объекта из разных классов.

В алгоритмах голосования по покрытиям классов строятся эл.кл. типа 3 [23, 24]. Оценка за класс К аналогична оценке Г2(5, К).

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

Пусть L - булева матрица размера тхп, Н - набор столбцов матрицы L. Набор столбцов Я называется покрытием матрицы L, если каждая строка матрицы L в пересечении, хотя бы с одним столбцом из Я дает 1. Покрытие называется неприводимым, если никакое его подмножество не является покрытием. Покрытие называется минимальным, если не существует покрытия меньшей мощности. Очевидно, что неприводимое покрытие содержит каждую из строк (1,0, ...,0), (ОД, ...,0),(ОД ...,1), то есть содержит единичную подматрицу.

Для нахождения (тупиковых) тестов, а также (тупиковых) представительных наборов строится специальная булева матрица L* (матрица сравнения). Каждая строка этой матрицы образуется в результате сравнения двух обучающих объектов из разных классов. При этом в столбце с номером j ставится 1, если сравниваемые объекты различаются по признаку Xj, и ставится 0 в противном случае.

Пусть S1,...,Sm - обучающие объекты и пусть L*, i Е {1, ...,т} -подматрица матрицы L*, которая образована сравнением обучающего объекта

со всеми обучающими объектами, не принадлежащими тому же классу, что и объект

Очевидно, что набор признаков (хд,..., х^] является тупиковым тестом тогда и только тогда, когда набор столбцов матрицы I* с номерами ]г>... ,]г является неприводимым покрытием.

Очевидно также, что фрагмент Я), - обучающий объект класса К, К Е {К1, ...,К{\, является (тупиковым) представительным набором для класса К тогда и только тогда, когда набор столбцов матрицы Ь\ с номерами из Я является (неприводимым) покрытием.

Задача построения неприводимых покрытий булевой матрицы может быть сформулирована как задача преобразования конъюнктивной нормальной формы монотонной булевой функции в сокращённую дизъюнктивную нормальную форму (как задача построения максимальных конъюнкций монотонной булевой функции) [43]. Данная задача, называемая также дуализацией, относится к числу труднорешаемых задач перечисления решений.

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

Важный результат получен в работе Фридмана М. и Хачияна Л. [63], в которой для дуализации построен инкрементальный квазиполиномиальный алгоритм. В данном случае инкрементальность означает, что алгоритму разрешено на каждом шаге просматривать множество решений, построенных на предыдущих шагах, и на этот просмотр тратить время, ограниченное

квазиполиномом не только от размера задачи, но и от числа найденных решений.

В России вопросы снижения вычислительной сложности задачи дуализации исследуются с середины 20-го столетия [42, 43]. В конце 1970-х годов были разработаны первые эффективные алгоритмы для практически важных случаев этой задачи. В частности, в работах [10, 11] были предложены и теоретически обоснованы модели тестовых алгоритмов распознавания, основанных на асимптотически оптимальном перечислении множества неприводимых покрытий булевой матрицы.

Пусть В(Ь, 0) - множество неприводимых покрытий булевой матрицы Ь и пусть - конечная последовательность наборов столбцов матрицы Ь, содержащая множество В(Ь, 0). Предполагается, что некоторые элементы в (2(1) могут повторяться. Пусть алгоритм А строит с полиномиальной задержкой последовательность (¿(Ь), А1А(Ь) - число шагов алгоритма А (число элементов в ()(Ь)). При построении очередного элемента из (¿(Ь) алгоритм А проверяет его на принадлежность В (1,0). Очевидно, что такая проверка может быть осуществлена за полиномиальное от размеров матрицы время. Если построенный элемент принадлежит В(Ь, 0), то дополнительно проверяется, что этот элемент не был ранее построен алгоритмом А. Требуется, чтобы данная проверка осуществлялась за полиномиальное от размера матрицы время.

Алгоритм А является асимптотически оптимальным, если ЫА(Ь) « | В{1,0) | при п -» оо для почти всех булевых матриц Ь размера тх п.

К настоящему моменту построен ряд асимптотически оптимальных алгоритмов (в основном для случая, когда матрица вытянута по горизонтали [3, 10-13], то есть число строк матрицы меньше числа ее столбцов). Эти алгоритмы основаны на перечислении с полиномиальной задержкой

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

При анализе целочисленных данных в задачах распознавания наравне с методами преобразования нормальных форм монотонной булевой функции применяются методы синтеза нормальных форм логических функций, являющихся характеристическими функциями классов. В [14, 15, 17-20, 24, 25, 53, 59, 60] построены асимптотически оптимальные алгоритмы для задач перечисления максимальных конъюнкций двузначных логических функций, которые сформулированы как задачи построения тупиковых покрытий целочисленной матрицы. Эти алгоритмы успешно протестированы на большом числе практических и модельных задач.

Теоретическое обоснование асимптотически оптимальных методов поиска тупиковых покрытий булевых и целочисленных матриц базируется на изучении метрических (количественных) свойств множества покрытий. К настоящему времени наиболее полно исследован случай, когда число столбцов п в матрице по порядку роста больше при п -> оо числа строк т. Для этого случая в [2, 10 - 15, 17-20, 60] получены асимптотики типичного числа тупиковых покрытий и типичной длины тупикового покрытия как булевой, так и целочисленной матрицы. В частности показано, что число неприводимых покрытий булевой матрицы почти всегда асимптотически равно числу единичных подматриц этой матрицы. Технически более сложным оказалось получение аналогичных оценок в случае, когда число столбцов в матрице не превосходит числа её строк. Для этого случая в [8, 19] была получена лишь асимптотика логарифма типичного числа тупиковых покрытий. Таким образом, оставался открытым вопрос, касающийся получения точных асимптотических оценок важных количественных характеристик множества покрытий булевых и целочисленных матрицы в случае квадратных и вытянутых по вертикали матриц.

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

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

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

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

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

Ю.И. Журавлевым показано, что задача построения корректной перекодировки может быть сведена к построению специального вида покрытия булевой матрицы, которая строится по обучающей выборке. В [21, 56] предложен подход, позволяющий выбирать наилучшую в смысле качества распознавания корректную перекодировку. Недостаток подхода -большая вычислительная сложность.

Основными целями диссертационной работы являются: 1. Разработка новых подходов к повышению эффективности решения задачи распознавания по прецедентам методами логического и алгебро-логического анализа данных.

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

1.2. Развитие методов корректного понижения значности целочисленных данных в задачах распознавания. Использование новых критериев качества перекодирования.

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

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

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

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

В диссертационной работе получены следующие результаты.

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

В этом случае функция приспособленности - оценка распознающей способности корректного набора эл.кл.

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

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

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

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

Диссертационная работа состоит из введения, четырех глав и заключения.

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

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

Пусть и = {(Н^а^,..., (НС[,аС})} - набор эл.кл, 5еМ. Положим

= (Яся^оЮ.....

Определение 1.1.1. Набор эл.кл. и называется корректным для класса К, К Е {К^...,^}, если существует функция алгебры логики к такая, что для любых двух объектов 5' и 5" из обучающей выборки, таких что 5' е К, 5" £ К выполняется неравенство

(0)^(5')) Ф ^(6)^(5"))

Определение 1.4.1. Корректный набор эл.кл. и с корректирующей функцией называется монотонным корректным для класса К, если Ри,к~ монотонная функция и Рик(а)и(5')) = 1 для любого обучающего объекта 5' класса К.

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

Далее рассматриваются распознающие алгоритмы, работающие по следующей схеме. Для каждого класса К, К Е {Кг,..., /Сг}, распознающий алгоритм А конструирует некоторое подмножество И^(Ю множества корректных наборов эл.кл. класса К. Распознавание объекта Я производится на основе вычисления оценок принадлежности этого объекта к классам

Пусть И (Т, К) - множество обучающих объектов из Т принадлежащих К, Я(Т, К) - множество обучающих объектов из Т не принадлежащих К.

Случай 1. Множество ША(К) состоит из корректных наборов эл.кл. класса К, не обязательно являющихся монотонными. Пусть и е У/А(К). Положим

_ [1, если 0)^(5) = ¿0^(5'), иначе.

Тогда оценка принадлежности объекта 5" к классу К имеет вид

где суммирование проводится по всем (и,Б') из И'А(К) X Я(Т,К).

Случай 2. Множество У\/А(К) состоит только из монотонных корректных наборов эл.кл. класса К. Пусть и Е У\/А(К\ \ и\ = ц. Положим

82 Я = (1'если °>и№ > ши и ' (0, иначе,

где (о и (Б) > 0)и($')> <^(5) = (с-1. Ши(Б') = (а'±> ...,а'ч), означает, что

щ > а[ при I = 1,2,..., q.

Оценка принадлежности объекта £ к классу К имеет вид

ГЛ5'к) = тт,кшд(ю\

где суммирование проводится по всем ([/, 5") из И?А(К) х Я(Т, К).

Разработаны и реализованы распознающие алгоритмы А1, А2, АЗ, А4, работающие по описанной выше схеме. В качестве базисных алгоритмов используются одноэлементные эл.кл., то есть эл.кл. вида (ху,а), где а -допустимое значение признака х^. Для построения корректных наборов эл.кл. используются генетические алгоритмы, каждый из которых запускается несколько раз для получения наилучшего результата. Особями популяции в генетических алгоритмах являются корректные наборы эл.кл.

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

Для построения требуемого коллектива корректных наборов эл.кл., исходная выборка разбивается случайным образом на две подвыборки Т0 и Т± таких, что |710|/|Г1|=4. Подвыборка Т0 используется для построения корректных наборов эл.кл., а подвыборка Т± для оценки качества распознавания построенных корректных наборов эл.кл. Пусть — К (То, К),

(}1 = К(Т1,К), <21 = К(Т1,Ку Оценка распознающей способности корректного набора эл.кл. имеет следующий вид

где 5^(5,5') = для А1 и = 5^(5,5') для А2.

Алгоритмы АЗ и А4 решают задачу построения одного корректного набора эл.кл. по мощности близкого к минимальному соответственно в случаях 2 и 1. Функция приспособленности особи в генетическом алгоритме - мощность корректного набора эл.кл.

Тестирование разработанных алгоритмов проводилось на реальных задачах. Наилучшие результаты показаны алгоритмом А1.

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

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

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

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

Л(Я)= X с,; МН)=щ X

;'ек2(я) ;ей1(я) 1

здесь Я - кодирующее покрытие, £ {1,2, ...,п], - число единиц в У—ом столбце матрицы Ьт, (Я) - множество номеров столбцов Ьт, входящих в Я, Я2(Щ ~ множество номеров столбцов матрицы Ьт, не входящих в Я. Ставится задача минимизации используемых функционалов.

Проведено тестирование разработанных алгоритмов на реальных данных и сравнение с алгоритмами корректного перекодирования данных из [21, 56]. Показано, что данная методика позволяет повысить качество распознавания алгоритма голосования по представительным наборам, сконструированного по перекодированным данным, существенно не увеличивая вычислительных затрат.

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

Для задачи поиска минимального покрытия булевой матрицы разработаны два генетических алгоритма: алгоритм с бинарным представлением задачи и алгоритм с целочисленным представлением задачи. В первом случае для описания покрытия матрицы (особи популяции) используется бинарный вектор, во втором - целочисленный. Оба алгоритма осуществляют поиск минимального покрытия среди неприводимых покрытий. В качестве оценки пригодности решения (функции приспособленности) использован вес соответствующего покрытия. Предложены нестандартные операторы скрещивания, учитывающие веса используемых столбцов и значения функций приспособленности особей-родителей, а также операторы мутации с переменным числом мутируемых генов. Число мутируемых генов к(€) на шаге £, возрастает с развитием популяции и определяется по формуле

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

Эффективность построенных алгоритмов оценена на тестовых задачах, содержащихся в электронной библиотеке OR Library. Эти задачи состоят из 65 разреженных по числу единиц матриц, разбитых на 11 классов. Результаты тестирования показали, что хотя бы один из алгоритмов находит оптимальное решение в 61 задаче. В четырех оставшихся задачах лучшее найденное покрытие отличается по весу от оптимального на единицу.

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

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

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

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

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

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

Пусть МтП - множество всех матриц размера тхп с элементами из {ОД,..., к - 1}, к > 2; к > 2, г<п, - множество всех наборов вида (<71(.., <гг), где сг£ £ {ОД,..., к - 1}, Ь = 1,2,..., п.

Пусть Ь Е Н - набор столбцов матрицы Ь, а Е о = (о-!,.., <тг). Набор столбцов Я называется тупиковым о - покрытием, если выполнены следующие два условия: 1) подматрица ЬИ матрицы Ь, образованная столбцами набора Я, не содержит строку сг, 2) для каждого р Е {1,2, ...,г} подматрица Ьн содержит по крайней мере одну из строк вида (/?1(.., /?г) е где /?р Ф ар и /?; = су при; Е {1,2, ...,г}\{р}, т.е. Ьнсодержит а - подматрицу.

Если выполнено только условие 1), то набор столбцов Н называется а — покрытием матрицы Ь.

Если выполнено только условие 2), то набор столбцов Н называется а — совместимым набором столбцов матрицы Ь.

Нетрудно видеть, что понятие (тупикового) (0,0, ...,0)-покрытия булевой матрицы совпадает с понятием (неприводимого) покрытия булевой матрицы. Отметим, что (0,0, ...,0)-подматрица булевой матрицы является единичной подматрицей.

Пусть Ь е МтП. Положим 5(Ь, <т), (т 6 - множество всех -подматриц матрицы Ь, С(Ь, о), о е Е£ - множество всех сг-покрытий матрицы Ь, В{Ь,о),о £ - множество всех тупиковых сг-покрытий матрицы I, V(Ь, сг), о е - множество всех а — совместимых наборов столбцов матрицы Ь.

Пусть далее

5Г(1) = , Сг{1) = а) ,

адО = иащВ{1,&) , В{Ь) = и им = Усщиа.ег), и а) = и

гх(/с) = [к^кт - \ogy- 1п 1оgkm- 1],

г2(/0 = ]к^кт + с[, с = + к^кк^кп,

рг(к) = ехр(-тк~г) (1 - ехр{-т(к - 1)/Гг))г,

/п ~ 00 > означает, что /п = дп{ 1 + 8п), где 8п 0 при п -> оо;

/п < п оо, означает, что /п < $п(1 + 8п), где 5П -> 0 при п -> оо;

|7| - мощность множества 7.

В разделе 4.2 доказаны следующие теоремы

Теорема 4.2.1. Если п<т< кп<3, р < 1/2, то для почти всех матриц I из при п -> оо справедливо

Г2(Ю г2(к)

Л |ЯГ(1)|* ^ С^кгрг(к);

г=п(к) г=г1(/с)

2)1^)1« £ 1^)1« ^ — ехр(—ш(/с — 1)/с_г))г;

Г=Г!(/С) Г=Г!(к)

3) ]Г \ВГ(Ь)\ ~ \ВГ2(к)(Ь)\~ \5Г2{к)(Ь)\ ~

г>г2(к)

г>г2(к)

« - ехр(—ш(/с - 1)к-г^))Г2(Ю.

Теорема 4.2.2. Если т < кп>3, /? < 1/2, то при п оо для почти всех матриц I из МтП справедливо

Г<Г!(к)

~ С^(к)кг^рГ1(к) « ехр{-тк-г^к))]

г<гг(к)

Замечание. Оценки, приведенные в утверждении 1 теоремы 4.2.2 впервые получены в работе Дюковой Е.В. [16]. В диссертационной работе удалось получить более простое доказательство этого утверждения.

Приведены аналоги теорем 4.2.1 и 4.2.2 для количественных характеристик неприводимых покрытий булевой матрицы и (0Д...,0) — совместимых наборов столбцов булевой матрицы.

Таким образом, показано, что при п <т < кп^, /? < 1/2 для почти всех матриц Ь из число тупиковых покрытий из В(Ь) длины г > г2(к) асимптотически равно при п оо числу а - совместимых наборов длины г > г2(/с) и числу о - подматриц из 5(1) ранга г2(/с). Также показано, что

при п <т < кп\ р < 1/2 для почти всех матриц Ь из при п -> с»

длины почти всех тупиковых покрытий из В(Ц) и наборов столбцов из и(Ь) принадлежат интервалу [гг (к), г2 (/с)].

В [24] было показано, что при п <т < кпР, /? < 1/2, число тупиковых покрытий из В(Ь) длины г <гг {к) для почти всех матриц Ь из асимптотически равно при п -» оо числу покрытий из С(Ь) длины гг (к). При доказательстве теоремы 4.2.4 получено более простое доказательство этого утверждения. Также показано, что число о - совместимых наборов столбцов из и (I) длины г <гг (к) асимптотически равно числу о - совместимых наборов столбцов длины г = гг (/с).

Оценки, полученные в разделе 4.2, использованы в разделе 4.3 для получения асимптотик типичного числа максимальных конъюнкций и типичного ранга максимальной конъюнкции двузначной логической функции от п переменных с т нулями. Показано, что ранги почти всех максимальных конъюнкций для почти всех двузначных логических функций F от п переменных с т нулями принадлежат интервалу [г1(к),г2(к)]. Число максимальных конъюнкций длины г > г2(/с) функции асимптотически равно при п оо числу неприводимых конъюнкций ранга г > г2 (к). Число максимальных конъюнкций длины г < гх(/с) функции Т7 асимптотически равно при п оо числу допустимых конъюнкций ранга гг(к).

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

Пусть алгоритм А строит множество тупиковых покрытий В(Ь) матрицы Ь £ путем перечисления с полиномиальной задержкой

множества наборов столбцов этой матрицы, которое содержит B(L), NA(L) -число шагов алгоритма А.

Алгоритм А является асимптотически эффективным, если NA(L) ^^ р(т,п) х \B(L)\ при п -> оо для почти всех матриц L из где р(т,п) -

полином от т и п.

Показана асимптотическая эффективность алгоритмов поиска покрытий из 5(L), L € основанных на переборе (перечислении)

некоторого подмножества U'(L) U (L) множества совместимых наборов столбцов матрицы L.

Пусть алгоритм А строит множество тупиковых покрытий B(V) матрицы L е М£п путем перечисления с полиномиальной задержкой о — совместимых наборов столбцов этой матрицы, NA(L) - число шагов алгоритма А. Доказана следующая теорема.

Теорема 4.4.4. Если п<т< , /3 < 1/2, то для почти всех матриц L из при 71 оо справедливо

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Сотнезов, Роман Михайлович

Заключение

В работе получены следующие результаты.

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

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

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

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

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

6. Показано, что при п < т, для почти всех матриц Ь из при п оо число всех тупиковых покрытий и число всех совместимых наборов столбцов матрицы Ь асимптотически равно соответственно числу тупиковых покрытий и числу совместимых наборов столбцов, длина которых принадлежит интервалу [^(/с),?^^)]. Аналогичный результат получен для задач преобразования нормальных форм двузначной логической функции.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Сотнезов, Роман Михайлович, 2012 год

Список литературы

1. Агеев A.A. Алгоритмы с улучшенными оценками точности для задачи о покрытии множествами // Дискретный анализ и исследование операций, январь-июнь 2004, серия 2, т.11, стр. 3-10.

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

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

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

5. Батищев Д.И., Костюков В.Е, Старостин Н.В., Смирнов А.И. Популяционно-генетический подход к решению задачи о покрытии. Учебное пособие. - Нижний Новгород: Изд-во ННГУ, 2004, 152 с.

6. Бонгард М.М., М. Н. Вайнцвайг. Об оценках ожидаемого качества признаков // Проблемы кибернетики, 1968, вып. 20.

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

8. Демьянов Е.А., Дюкова Е.В. О построении тупиковых покрытий целочисленной матрицы // Ж. вычисл. матем. и матем. физ. 2007. Т. 47. № 3. С. 539-547.

9. Дмитриев А.И., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов или явлений // Дискретный анализ. Новосибирск: ИМ СО АН СССР, 1966. Вып. 7. С. 3-17.

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

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

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

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

М.Дюкова Е.В. О сложности реализации некоторых процедур распознавания // Ж. вычисл. матем. и матем. физ. 1987. Т. 27. № 1. С. 114-127.

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

16.Дюкова Е.В. Метрические свойства близких к минимальным покрытий целочисленных матриц // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2002. С. 37-38.

П.Дюкова Е.В. О сложности реализации дискретных (логических) процедур распознавания // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. № 3. С. 550-572.

18.Дюкова Е.В. О числе тупиковых покрытий целочисленной матрицы // Ж. вычисл. матем. и матем. физ. 2005. Т . 45 № 5. С. 938-943.

19. Дюкова Е.В. О построении тупиковых покрытий булевой матрицы // ДАН. 2007. Т. 412. №1. С. 15-17.

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

21.Дюкова Е.В., Журавлев Ю.И., Песков Н.В., Сахаров A.A. Обработка вещественнозначной информации логическими процедурами распознавания // Искусственный интеллект. HAH Украины, 2004. №2. С.80-85.

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

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

24.Дюкова Е.В., Песков Н.В. Построение распознающих процедур на базе элементарных классификаторов // Математические вопросы кибернетики. 2005. № 14. С.57-92.

25.Дюкова Е.В., Инякин A.C. Асимптотически оптимальное построение тупиковых покрытий целочисленной матрицы // Математические вопросы кибернетики. М: Наука, 2008. №17. С.235-246.

26.Дюкова Е.В., Сизов A.B., Сотнезов P.M. Об одном методе построения приближённого решения для задачи о покрытии // Доклады 14-й Всероссийской конференции «Математические методы распознавания образов». М.: МАКС Пресс, 2009. С. 241-243.

27.Дюкова Е.В., Сизов A.B., Сотнезов P.M. О корректном понижении значности данных в задачах распознавания // Доклады Международной конференции «Математические методы

распознавания образов» (ММРО-15), г. Петрозаводск, 17-23 сентября 2011 г. С. 80-83.

28.Дюкова Е.В., Сотнезов P.M. О сложности дискретных задач перечисления//Докл. Акад. Наук. 2010. Т. 143. №1. С. 11-13.

29.Дюкова Е.В., Сотнезов P.M. О сложности перечисления элементарных классификаторов в логических процедурах распознавания // Интеллектуализация обработки информации: 8-я международная конференция. Кипр, г. Пафос, 17-23 октября 2010 г.: Сборник докладов. - М.: МАКС Пресс, 2010. - С. 43-46.

30.Дюкова Е.В., Сотнезов P.M. Асимптотические оценки числа решений задачи дуализации и ее обобщений // Ж. вычисл. матем. и матем. физ. 2011. Том 51, № 8. С. 1531-1540.

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

32.Журавлев Ю.И., Рязанов В.В., Сенько О.В. «Распознавание». Математические методы. Программная Система. Практические применения // М. ФАЗИС, 2006. 176 с.

33.Кудрявцев В.Б., Андреев А.Е., Гасанов Э.Э. Теория тестового распознавания, М.: Физматлит, 2007. - 320 с.

34.Матросов B.JI. Синтез оптимальных алгоритмов в алгебраических замыканиях моделей алгоритмов распознавания // Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука. 1988. Вып. 1.С. 149-176.

35.Нгуен М.Х. Применение генетического алгоритма для решения одной задачи планирования производства. Динамика неоднородных систем. Выпуск 11. -М.:КомКнига, 2007. -С.162-169.

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

37.Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука. 1988. Вып. 1. С. 176-200

38.Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач // Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука. 1988. Вып. 1. С. 229-279

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

40.Сотнезов P.M. Генетические алгоритмы в задаче о покрытии. Сборник тезисов лучших дипломных работ 2008 года. М. Издательский отдел факультета ВМиК МГУ, 2008, с. 73-74.

41.Сотнезов P.M. Генетические алгоритмы в задаче о покрытии // Восьмая международная конференция «Дискретные модели в теории управляющих систем». Москва, 2009 г. Электронный сборник материалов конференции. С. 179-183. (http://dmconf.ru/dm8/proceedings.pdf)

42.Чегис И.А., Яблонский C.B. Логические способы контроля электрических схем // Тр. МИАН СССР, М., 1958.

43.Яблонский C.B. Введение в дискретную математику // М.: Наука, 1986.384 с

44.Asuncion A., Newman DJ. UCI Machine Learning Repository, University of California, Irvine. - 2007. www.ics.uci.edu/~mlearn/MLRepository.html

45.J.E. Beasley. OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41: 1069-1072, 1990.

46.J.E. Beasley and K. Jornsten. Enhancing an algorithm for set covering problems. European Journal of Operational Research, 58:293-300, 1992.

47.A. Capara et all. Algorithms for Railway Crew Management. Mathematical Programming 79 (1997) pp. 125-141

48.Alberto Caprara, Matteo Fischetti, Paolo Toth. Algorithms for the set covering problem. Working Paper, DEIS, University of Bologna, 1998.

49.Alberto Caprara, Matteo Fischetti, Paolo Toth. A heuristic Method for the Set Covering Problem. Operation Research, Vol. 47 (1999). pp. 730-743

50.Demyanov E.A., Djukova E.V., Inyakin A.S., Peskov N.V. Classifying the Subjects of the Russian Federationon the Basis of Analysis of Results of Gallup Polling // Pattern Recognition and Image Analysis, 2007, Vol. 17, No. 4, pp. 578-583.

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

52.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.

53.Djukova E.V., Inyakin A.S. Constructing Irreducible Coverings of a Boolean Matrix // J. Pattern Recognition and Image Analysis, 2007. Vol. 17, No. 3, pp. 357-362.

54.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.

55.Djukova E., Inyakin A., Peskov N., Sakharov A. Combinatorial (Logical) Data Analysis in Pattern Recognition Problems// Pattern Recognition and Image Analysis. 2005. Vol.15, №1. P. 46-48

56.Djukova E.V., Inyakin A.S., Peskov N.V., Saharov A.A. Increasing the Efficiency of Combinatorial Logical Data Analysis in Recognition and Classification Problems // Pattern Recognition and Image Analysis. 2006. Vol. 16, No. 4. P. 695-699.

57.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.

58.Djukova E.V., Peskov N.V. A Classification Algorithm Based on the Complete Decision Tree // J. Pattern Recognition and Image Analysis, 2007. Vol. 17. No. 3, pp. 363-367.

59.Djukova E. V., Nefedov V. Yu. The Complexity of Transformation of Normal Forms for Characteristic Functions of Classes // Pattern Recognition and Image Analysis, 2009, Vol. 19, No. 3, pp. 435-440.

60.Djukova E.V., Yu.I. Zhuravlev. Discrete Methods of Information Analysis in Recognition and Algorithm Synthesis // Pattern Recognition and Image Analysis. 1997. Vol.7. No.2. P. 192-207.

61.Djukova E.V., Zhuravlev Yu.I., Sotnezov R.M. Synthesis of Corrector Family with High Recognition Ability // New Trends in Classification and Data Mining. Sofia, 2010. - P. 32-39.

62.Djukova E.V., Zhuravlev Yu.I., Sotnezov R.M. Construction of an Ensemble of Logical Correctors on the Basis of Elementary Classifiers // Pattern Recognition and Image Analysis, 2011, Vol. 21, No. 4, pp. 599-605.

63.Fredman M., Khachiyan L. On the Complexity of Dualization of Monotone Disjunctive Normal Forms // J. of Algorithms. 1996. Vol. 21. No. 3. P. 618628.

64.Philippe Galinier and Alain Heztz. Solution techniques for the large set covering problem. Discrete applied Mathematics, Vol. 155, Issue 3, 2007.

65.M.R. Garey and D.S. Johnson. Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.

66.L.W. Jacobs and M.J. Brusco. A simulated annealing-based heuristic for the set covering problem. Working paper, Operations Management and Infprmation Systems Department, Northern Illinois University, Dekalb, IL 60115, USA, 1993.

67.Sotnezov R.M. Genetic Algorithms in problems of discrete optimization and recognition, International Conference on "Pattern Recognition and Image Analisys: new Information Technologies", Nizhni Novgorod, Russian Federation, 2008. V.2, P 173-175.

68.Sotnezov R.M. Genetic Algorithms for Problems of Logical Data Analysis in Discrete Optimization and Image Recognition // Pattern Recognition and Image Analysis, 2009, Vol. 19, No 3, pp. 469-477.