Покрытие целочисленной матрицы и задача кластерного анализа тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Инякин, Андрей Сергеевич

• Инякин, Андрей Сергеевич
• кандидат физико-математических наук
• 2006

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

ВВЕДЕНИЕ.

ГЛАВА 1 ЗАДАЧА КЛАСТЕРНОГО АНАЛИЗА.

1.1 Задача кластеризации. Меры подобия.

1.2 Алгоритмы кластеризации, основанные на иерархической группировке.

1.3 Алгоритмы кластеризации, использующие функции-критерии качества.

1.4 Алгоритмы кластеризации, основанные на выборе центральных элементов классов.

ГЛАВА 2 АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ, ОСНОВАННЫЕ НА ПОСТРОЕНИИ ПОКРЫТИЙ ЦЕЛОЧИСЛЕННЫХ МАТРИЦ.

2.1 Понятие СГ -покрытия целочисленной матрицы и его геометрическая интерпретация.

2.2 Алгоритмы кластеризации, основанные на построении О" -покрытий целочисленных матриц.

2.3 Тестирование на модельных задачах.

2.4 Тестирование на реальных задачах.

2.4.1 Анализ данных социологических исследований. Классификация анкет опроса (выделение однородных групп респондентов).

2.4.2 Медицинское прогнозирование. Классификация пациентов по истории болезни (выделение однородных групп пациентов).

ГЛАВА 3 АЛГОРИТМЫ ПОИСКА ПОКРЫТИЙ БУЛЕВОЙ И ЦЕЛОЧИСЛЕННОЙ МАТРИЦ.

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

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

3.2.1 Алгоритм, основанный на идее расшифровки монотонной булевой функции.

3.2.2 Асимптотически оптимальные алгоритмы, основанные на поиске единичных подматриц булевой матрицы.

3.3 Новые алгоритмы поиска неприводимых покрытий булевой матрицы и теоретические оценки их вычислительной сложности.

3.3.1 Алгоритм спуска с пошаговым удалением охватывающих столбцов.

3.3.2 Алгоритм спуска с пошаговым удалением охватывающих строк и столбцов.

3.3.3 Алгоритм, использующий «дополнительную матрицу».

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

3.5 Модификация алгоритмов построения неприводимых покрытий булевой матрицы для поиска минимальных покрытий.

3.6 Экспериментальные оценки вычислительной сложности алгоритмов построения множества всех минимальных покрытий булевой матрицы.

3.7 Решение задачи построения (тупиковых) покрытий целочисленной матрицы на основе построения (неприводимых) покрытий булевой матрицы.

ГЛАВА 4 МЕТРИЧЕСКИЕ СВОЙСТВА МНОЖЕСТВА ПОКРЫТИЙ ЦЕЛОЧИСЛЕННОЙ МАТРИЦЫ.

4.1 О числе «коротких» тупиковых покрытий целочисленной матрицы.

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

ГЛАВА 5 МЕТРИЧЕСКИЕ СВОЙСТВА ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ ДВУЗНАЧНЫХ ЛОГИЧЕСКИХ ФУНКЦИЙ,

ОПРЕДЕЛЕННЫХ НА &-ИЧНЫХ П -МЕРНЫХ НАБОРАХ.

Введение диссертации (часть автореферата) на тему «Покрытие целочисленной матрицы и задача кластерного анализа»

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

Рассматриваются алгоритмы кластеризации, использующие понятия близости объектов из М друг к другу, близости объекта S, S еМ, к группе объектов М', М' с А/, близости групп объектов М' и М", М' сМ, М" с М, друг к другу. Традиционно для этого используются функции расстояния. К недостаткам таких алгоритмов можно отнести трудности при выборе содержательно интерпретируемой функции расстояния, при применении которой получалась бы интересная кластерная структура. Особенно затруднителен подбор функции расстояния в задачах кластеризации с целочисленной информацией невысокой значности (т.е. информацией, представленной качественными или номинальными признаками). Такие задачи возникают при обработке данных социологических исследований, в медицинской диагностике, при классификации геологических объектов и др. Для решения указанных задач могут быть применены алгоритмы кластеризации, использующие расстояние Хэмминга и его обобщение на целочисленный случай (алгоритмы типа «ближайший сосед», «дальний сосед», «к средних» и т.п.). Эти алгоритмы не всегда показывают хороший результат в случае, когда информация представлена признаками, принимающими более двух значений.

Известно, что при решении задач распознавания с обучением в случае, когда информация представлена целочисленными признаками, хорошо зарекомендовали себя логические или как их еще называют дискретные алгоритмы. При их конструировании используется аппарат дискретной математики, в частности, булевой алгебры, теории дизъюнктивных нормальных форм и теории покрытий булевых и целочисленных матриц. Основополагающими работами являются работы Ю.И. Журавлева, С.В. Яблонского и М.Н. Вайнцвайга [6,9,22,23, 51, 52,65].

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

В классических процедурах распознавания дискретного характера роль элементарных классификаторов играют фрагменты описаний обучающих объектов, позволяющие различать объекты из разных классов. В этих процедурах информативные фрагменты порождаются тестами, представительными и антипредставительными наборами, конъюнкциями специального вида [4-10, 33, 35, 39 - 41,46,47,49 - 53, 56, 62, 63,68, 79-86].

В последнее время построены модели логических процедур распознавания, основанные на принципе «невстречаемости» элементарных классификаторов в описаниях обучающих объектов [42-47, 49, 68, 80-84]. Роль элементарных классификаторов в таких моделях играют наборы из допустимых значений признаков, отсутствующие в описаниях всех обучающих объектов класса (покрытия класса). Техническая основа решения в рассматриваемых логических процедурах базируется на методах поиска так называемых а -покрытий и тупиковых а -покрытий булевых и целочисленных матриц, а также методах построения нормальных форм логических функций [19,29 - 38,42 -45,54, 58, 59, 61].

Пусть L - матрица размера тхп с элементами из {0,1,.,к-\), к >2;

Е[, к> 2, г < пмножество всех А>ичных наборов вида (crj,.,^), сг; е {0,1,.Д-l}, = 1, г. Пусть а е Егк, а = (ст1,.,сг/.).

Определение. Набор Н из г различных столбцов матрицы L называется а

TJ покрытием, если подматрица L матрицы L, образованная столбцами набора Н, не содержит строку (ctj ,., аг ).

Определение. Набор столбцов Н матрицы L, являющийся а-покрытием,

JT называется тупиковым а-покрытием, если подматрица L с точностью до перестановки строк содержит а-подматрицу, т.е. подматрицу вида

Р\ °ъ ar-1 аг сг, /?2 аъ ••• агх аг ctj сг2 £73 ••• <тг j рг где Д *crt,i = \,r.

В случае к = 2 тупиковое (0,., 0)-покрытие называется неприводимым покрытием. В этом случае а -подматрица является единичной подматрицей. Покрытие минимальной длины называется минимальным покрытиям.

Обозначим через C(L, сг), B(L, сг) и S(L, сг) соответственно множество сг-покрытий матрицы L, множество тупиковых сг-покрытий матрицы L и множество а -подматриц матрицы L. Положим

C(L) = (j U C(L,a),B(L) = \J JJ B(L, сг), S(L) = \J jj S(L,a). r=\oeErk r=\azErk r=\aeErk

Приведем геометрическую интерпретацию понятия сг-покрытия целочисленной матрицы L [45, 59].

Множество является £-значным «-мерным кубом. Обозначим через ML -множество точек куба Е£, задаваемых строками матрицы L. Положим ML = Е%\ МL. Набору столбцов Н с номерами (j\,.,jr), являющемуся сг-покрытием матрицы L, поставим в соответствие множество всех точек а = (aJfап) из Е£ таких, что a j. = <7j,i = 1, г. Очевидно, является («-г)-мерным подкубом (гранью) куба и целиком принадлежит ML. В случае г = п, множество точек является 0мерным подкубом, состоящим из одной точки сг. Таким образом, множеству C(L) взаимнооднозначно соответствует множество всех подкубов, содержащихся в ML.

Отметим, что является подкубом тогда и только тогда, когда сг2 с 0\,

Н 2 с Я,.

Пусть Е - некоторое подмножество Е%. Будем говорить, что подкуб Е' cz Е является максимальным в Е, если не существует другого подкуба Е" с: Е такого, что

Е' с Е". Множество всех максимальных подкубов в Е будем обозначать &max (Е). Нетрудно видеть, что множеству B(L) взаимнооднозначно соответствует множество &mWi(ML). Таким образом, задача построения множества B{L) может быть сформулирована как задача построения множества всех максимальных подкубов в ML.

Задачи построения покрытий целочисленной матрицы могут быть также сформулированы как задачи построения дизъюнктивной нормальной формы (ДНФ) двузначной логической функции специального вида, заданной на £-ичных «-мерных наборах [34,35,39, 86].

Действительно, пусть на наборах из задана всюду определенная логическая функция F, принимающая значения из {0,1}; BF - множество наборов, на которых функция F принимает значение 0. Множество всех таких функций обозначим через .

Определение. Элементарной конъюнкцией (э.к.) называется выражение вида л\'.ха.г, где переменная х,- принимает значения из {0,1,. Д-l}, J г Ji * и все j), i = 1, г, различны.

Число г называется рангом э.к. Интервал истинности э.к. 33 обозначается через Мд.

Определение. Э. к. 33 называется допустимой для F, если N<q f\BF =0.

Определение. Э.к. © называется максимальной для F, если 33 допустимая конъюнкция для F и не существует допустимой для F конъюнкции 33' такой, что N<q> =5 iV<g .

Определение. Сокращенной ДНФ функции F называется ДНФ, состоящая из всех максимальных конъюнкций функции F.

Пусть Bp состоит из наборов вида (Д,,Д2>-">АИ), •••> (Рт\>Рт2>~->Ртп)- Из

СГ,. е {О,!,.,£-!}, i = \,r,

1, если Xj. = <jj,; 0, иначе,

Ji наборов BF составим матрицу L вида

Ai Pa Pin

Pl\ P22 . Pin

Pm\ Pml Pmn J

Справедливы приведенные ниже утверждения 5.1 и 5.2.

Утверждение 5.1. Э.к. х^1 .ха.г является допустимой для F тогда и только

J1 Jr тогда, когда набор столбцов с номерами j\,.,jr является (crj,.,crr)-покрытием матрицы L.

Утверждение 5.2. Э.к. х^'. х°г является максимальной для F тогда и только тогда, когда набор столбцов с номерами jr является тупиковым (crj,.,сгг)покрытием матрицы L.

Из утверждений 5.1 и 5.2 следует, что алгоритмы поиска покрытий целочисленной матрицы могут быть применены при построении допустимой ДНФ двузначной логической функции, алгоритмы поиска тупиковых покрытий целочисленной матрицы могут быть применены при построении сокращенной ДНФ двузначной логической функции и наоборот.

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

Технические основы получения указанных оценок были заложены в работах Н.В. Носкова, В .А. Слепян, Е.В. Дюковой и А.Е. Андреева [1 - 3, 29 - 33, 65, 66, 72 - 74] при изучении метрических свойств множеств тупиковых и минимальных тестов.

В [34, 35, 39, 86] были получены асимптотики числа покрытий из B(L) и длины покрытия из В(Ь) для почти всех матриц L размера тхп с элементами из {0,1,.Д-1}Д>2, при условиях п-> оо и та <п<ктР, а> 1, J3 < 1. Аналогичные оценки получены для числа подматриц из S(L) и порядка подматрицы из S(L). Показано, что в данном случае число покрытий из В(Ь) почти всегда асимптотически совпадает с числом всех подматриц из S(L) и по порядку меньше числа покрытий из C(L).

В [49] был рассмотрен прямо противоположный случай, а именно, р когда па <тйкп , а> 1, /?< 1. Получены асимптотики типичных значений числа подматриц из S(L) и порядка подматрицы из S(L). Установлено, что в случае, когда па <т<кпР, а> 1, /3 < 1/2, почти всегда число подматриц из S(L) по порядку больше числа покрытий из B(L). Кроме того, для практически общего случая в [49] получены асимптотики типичных значений числа покрытий из C(Z-) и длины покрытия из C(i) и показано, что при r<\ogkm-logk(logkmxlnri) и п—»°о у почти всех матриц L размера тхп отсутствуют покрытия длины г.

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

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

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

Случай вертикальной матрицы является достаточно простым. В данном случае из-за сравнительно небольшого числа столбцов в матрице задачу построения множества неприводимых покрытий можно решить полным (или почти полным) перебором. Одним из первых алгоритмов, предназначенных для поиска неприводимых покрытий в вертикальной матрице, является алгоритм, разработанный Т.П. Слуцкой и З.Е. Королевой. Этот алгоритм основан на идее расшифровки монотонной булевой функции [62, 75].

Для оценки эффективности алгоритмов построения неприводимых покрытий булевой матрицы, в [33, 35, 37, 79] Е.В. Дюковой было введено понятие асимптотически оптимального алгоритма и построены асимптотически оптимальные алгоритмы поиска неприводимых покрытий булевой матрицы для горизонтальной матрицы. Алгоритмы основаны на поиске единичных подматриц.

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

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

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

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

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

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

В диссертационной работе построены эффективные в практическом теоретическом плане алгоритмы поиска неприводимых покрытий булевой матрицы (алгоритмы УОС1, УОС2 и ДМ).

Алгоритм УОС1 (алгоритм спуска с пошаговым удалением охватывающих столбцов) основан на использовании следующего очевидного утверждения: в неприводимом покрытии не существует пары столбцов такой, что один столбец охватывает другой. На каждом шаге работы алгоритма строится набор столбцов, не содержащий охватывающих столбцов. Построение таких наборов является простой в выислительном плане задачей и в тоже время позволяет существенно сократить перебор. Алгоритм является «универсальным», т.е. эффективным при любых соотношениях числа строк и столбцов исходной матрицы (эксперементы проводились на случайных матрицах с числом строк меньшим или равным 1000 и числом столбцов меньшим или равным 200). Применение алгоритма УОС1 позволило существенно (в ряде случаев на порядок и более) сократить время построения множества неприводимых покрытий по сравнению с другими алгоритмами.

Алгоритм УОС2 (алгоритм спуска с пошаговым удалением охватывающих столбцов и строк) является модификацией алгоритма УОС1, позволяющей еще более сократить время построения множества неприводимых покрытий в случае «вертикальных» матриц и матриц с большим числом нулевых элементов. На каждом шаге алгоритма УОС2 строится покрытие, не содержащее охватывающих столбцов.

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

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

Пусть LeM^n; В {ь,б) - множество неприводимых покрытий матрицы L; G(Z,) - конечная совокупность наборов столбцов матрицы L, содержащая B^L,б). Предполагается, что каждый набор в G(L) не содержит одинаковых столбцов и некоторые наборы столбцов в G[L) могут встречаться более одного раза. Обозначим через 1^(^)1 число наборов в G(Z,) с учетом их повторений.

Пусть алгоритм А строит покрытия из B^L, б) путем последовательного просмотра всех наборов из G[L). При этом каждый набор из G(L) просматривается столько раз, сколько раз он встречается в G(Z-). Таким образом, на каждом шаге алгоритма А строится некоторый набор столбцов Н из G(L) и проверяется принадлежность Н к b(l,6). Совокупность G(L) назовем погружением алгоритма А. Число шагов алгоритма А равно |С7(£)|.

Нас будет интересовать вычислительная сложность алгоритма А в типичном случае (для почти всех булевых матриц размера тхп). Из оценок следует, что число неприводимых покрытий почти всегда растет экспоненциально с ростом размера матрицы. Эффективность алгоритма А имеет смысл оценивать в терминах полиномиальной задержки [87].

Будем говорить, что алгоритм А строит погружение G(L) с полиномиальной задержкой, если на каждом шаге выполняется не более d(m,ri) элементарных операций и d{m,n) ограничено сверху полиномом от размера матрицы. Под элементарной операцией понимается просмотр одного элемента матрицы L.

Определение. Алгоритм А является асимптотически эффективным, если алгоритм А строит погружение G^L) с полиномиальной задержкой и для почти всех матриц L из М*п выполнено lGWl / ч

Inn,' / :\,<г(т,п), мощность где т(т,п) ограничено сверху полиномом от размера матрицы L, множества B[L,by.

Если z(m,n) -1, то алгоритм А называется асимтотически оптимальным [25, 76]. Под вычислительной сложностью алгоритма А будем понимать величину c/(m,«)|G(Z)|.

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

1 Здесь и далее через ||Q| обозначается мощность множества Q.

Следует отметить, что построенные в [35, 79] алгоритмы являются асимтотически а щр оптимальными при т <п< 2 , а> 1, /? < 1. В [35] в качестве погружения используются наборы столбцов, содержащие единичные подматрицы исходной матрицы, а в [79] - наборы столбцов, являющиеся неприводимыми покрытиями. При этом каждый набор столбцов встречается в погружении столько раз, сколько единичных подматриц он содержит.

Определение. Набор Н из г различных столбцов матрицы называется совместимым, если выполнено одно из двух условий: 1) г = 1; 2) г > 2 и любые два столбца набора Н содержат единичную подматрицу порядка 2.

Определение. Совместимый набор столбцов матрицы L, являющийся покрытием, называется совместимым покрытием.

Погружением алгоритма УОС1 является некоторое подмножество из множества совместимых наборов. Погружением алгоритма УОС2 является некоторое подмножество из множества совместимых покрытий.

Справедливы теоремы 3.1 и 3.2, приведенные ниже.

Теорема 3.1. Алгоритм УОС1 строит погружение с полиномиальной задержкой, не превосходящей 2т п.

Теорема 3.2. Алгоритм УОС2 строит погружение с полиномиальной задержкой, 2 2 2 не превосходящей 2т п + 2т п .

Пусть rj = [log^ т - log^ In \ogk m -1]1.

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

1 Здесь [х] - целая часть X. совместимых покрытий. Выше было отмечено, что при г < logд. m-\ogk(\ogk mx\nri) и п —» оо у почти всех матриц размера тхп отсутствуют покрытия длины г. В данной работе получены асимптотики типичных значений для числа покрытий и числа тупиковых покрытий, длины которых не превосходят Г\. Результат формулируется следующим образом.

Пусть; (р - интервал (log^ m-log^log^ /я х In и), rj ]; к > 2,- множество всех матриц размера тхп с элементами из {0,1,.,&-1}; и ^(^-соответственно совокупность покрытий из С (Z), L е , длины которых принадлежат интервалу (р, и совокупность покрытий из длины которых принадлежат интервалу ср; СГ) (L) и Bri(L) - соответственно совокупность покрытий из C[L) длины ц, и совокупность покрытий из B[L) длины i\. Имеет место следующая

Теорема 4.1. Если т<кп^, /?<1/2, то для почти всех матриц L из при п ->оо справедливо в, (I)|*|С, (I)|«\cri (L)|*|Вп (Z)|* к* Cj? (1 - IT* г.

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

Пусть Br^L,б) - множество тупиковых (О,.,0)-покрытий длины г Сг (-£>6) -множество (О,.,0)-покрытий покрытий длины г; Ur(L) - множество совместимых наборов столбцов матрицы L длины г; у/ отрезок вида \q\ ,qj\, где q^ > 1, q2<n\

U(L) = ^Ur(L); Ur{L)=1£Uf.(L); В, (L,o) = |J Br (l,6); c(z,6) = Qc, (l,6); r=1 re^- геу/ r=1 z,6) = (J Cr (46); V(L) = C/(Z)nc(x,5); Vw (Z,) = (z,6). геу/

Справедливы теоремы 4.4 и 4.5, приведенные ниже.

Пусть (р2 - интервал [l,r, ];

Р 2

Теорема 4.4. Если т<2" , р<М2, то для почти всех матриц L из Мтп при п—>сс справедливо

К *К w|* К Mlж I1 -2п Г •

Теорема 4.5. Если log2 п = о(т) и т< 2пР, р < 1 / 2, то для почти всех матриц L из М^п при «->оо справедливо

Из теорем 4.4 и 4.5 сразу следует, что при поиске неприводимых покрытий, длины которых не превосходят гх, эффективны алгоритмы спуска (У0С1, У0С2), эффективен также алгоритм, основанный, на переборе всех наборов столбцов длины, не превосходящей и для последнего г{т,п) не превосходит log\ т. Пусть - интервал [log2 тп,п]. Справедливы следующие теоремы 4.2 и 4.3.

Теорема 4.2. Если па <т< 2"^, а> 1, Р< 1, то для почти всех матриц L из при п —> оо справедливо

V{L)\*|C(Z,6)|*|СЯ (Z,6)|«(1)| - X Сгп

Теорема 4.3. Если па <т< 2п , а> 1, Р<\, то для почти всех матриц L из Мтп при «->оо справедливо

Полученные в теоремах 4.2 и 4.3 асимптотики важны для оценки вычислительной сложности алгоритмов спуска (алгоритмы У0С1, У0С2).

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

Пусть (S(F,r) - множество всех допустимых конъюнкций функции F, F ранга г; <S(F,r) - множество всех максимальных конъюнкций функции F ранга г; «(*»= |j6(F,r); ®(F,<p)= re<p re<p

Из теоремы 4.1 и утверждений 5.1, 5.2 сразу следует

Теорема 5.1. Если т<к"Р, /?<1/2, то для почти всех функций F из f^L при п ->оо справедливо

B(F,<p)\ «|6(*>)| - )|«I®(F,r{ )| * (1 - Г.

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

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

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

Заключение диссертации по теме «Теоретические основы информатики», Инякин, Андрей Сергеевич

Заключение

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

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

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

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

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

Получены новые результаты, касающиеся изучения метрических свойств множества совместимых наборов столбцов и множества совместимых покрытий булевой матрицы размера т х п. Получены асимптотики типичных значений числа совместимых наборов столбцов и числа совместимых покрытий в случае па <т< 2"Р, а >1, /? < 1. Получены асимптотики типичных значений для числа совместимых наборов столбцов и числа совместимых покрытий, длины которых принадлежат интервалу l,log2 m-log2 lnlog2 m-l], в случае \og2n = o(m) и т< 2"^, /?<1/2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания : Некоторые аспекты // «Радио и Связь» Москва 1985.

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

18. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М:. Мир 1982.416 с.

19. Демьянов Е.А., Дюкова Е.В., Инякин А.С. Экспериментальное исследование алгоритмов построения неприводимых покрытий булевых матриц // Докл. Всеросс. Конф. «Матем. методы распознавания образов 11». М.: Регион-Холдинг, 2003, С. 61-65.

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

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

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

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

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

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

26. Дьяконов А.Г. Построение дизъюнктивных нормальных форм в логических алгоритмах распознавания // Ж. вычисл. матем: и матем. физ. 2002. Т. 42. № 12. -С. 1899-1907.

27. Дьяконов А.Г. Кодировки и их использование при ДНФ-реализации бинарных функций // ДАН, 2003, Т. 391, № 2, С. 162-165.

28. Дьяконов А.Г. Методы построения ДНФ бинарных функций с малым числом нулей. Применение к распознаванию // Искусственный интеллект, 2004, №2, С.75-79.

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

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

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

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

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

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

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

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

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

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

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

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

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

42. Дюкова Е.В., Инякин А.С. Решение задачи таксономии на основе построения сигма покрытий // Докл. Всеросс. конф. «Математические методы распознавания образов 9», М.: АЛЕВ-В, 1999. С. 45-47.

43. Дюкова Е.В., Инякин А.С. Задача таксономии и тупиковые покрытия целочисленной матрицы // Докл. Всеросс. конф. «Математические методы распознавания образов 10», М.: АЛЕВ-В, 2001. С. 44-47.

44. Дюкова Е.В., Инякин А.С. Задача таксономии и тупиковые покрытия целочисленной матрицы // Сообщения по прикладной математике. М.: ВЦ РАН, 2002.28с.

45. Дюкова Е.В., Инякин А.С. О процедурах классификации, основанных на построении покрытий классов // Ж. вычисл. матем. и матем. физ. 2003. Т. 43, № 12. С. 1910-1921.

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

47. Дюкова Е.В., Инякин А.С., Песков Н.В. Программный комплекс логических алгоритмов распознавания «ЛоРА» // Тезисы докладов международной научной конференции «ИОИ-2004» Симферополь: Крымский научный центр НАН Укранины, 2004 С. 67-68.

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

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

50. Журавлев Ю.И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации // ДАН СССР. 1976. Т. 231, № 3. С. 532-535.

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

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

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

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

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

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

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

58. Инякин А.С. Об одном алгоритме поиска тупиковых сг-покрытий // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2002. С. 47-48.

59. Инякин А.С. Алгоритмы поиска неприводимых покрытий булевых матриц // Сообщения по прикладной математике. М.: ВЦ РАН, 2004. 25с.

60. Исаев И.В. Задача синтеза корректного алгоритма распознавания как задача построения минимального покрытия // Ж. вычиел. матем. и матем. физ. 1983. Т. 23, № 2. 467-476.

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

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

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

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

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

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

67. Пападимитриу X., Стайглиц X. Комбинаторная оптимизация. Алгоритмы и сложность // М:. Мир, 1985. 512 с.

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

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

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

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

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

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

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

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

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

77. Demyanov E.A., Djukova E.V., Injakin A.S., Peskov N.V. Analysis of the polls results with a view to classify regions of Russian Federation// J. Pattern Recognition and Image Analysis. 2005, (принята в печать).

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

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

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

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

82. Djukova E.V., Inyakin A.S., Peskov N.V., Sakharov A.A. Combinatorial (Logical) Data Analysis in Pattern Recognition Problems // J. Pattern Recognition and Image Analysis. 2005, Vol. 15, № l.,pp. 46-48.

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

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

85. Jonson D.S., Yannakakis M., Papadimitriou C.H. On general all maximal independent sets // Information Processing Letts. 1988. V. 27. P. 119-123.