Содержание к диссертации
Введение
ГЛАВА 1 Задача кластерного анализа 22
1.1 Задача кластеризации. Меры подобия 22
1.2 Алгоритмы кластеризации, основанные на иерархической группировке 25
1.3 Алгоритмы кластеризации, использующие функции-критерии качества 27
1.4 Алгоритмы кластеризации, основанные на выборе центральных элементов классов 30
ГЛАВА 2 Алгоритмы кластеризации, основанные на построении покрытий целочисленных матриц 32
2.1 Понятие (7 -покрытия целочисленной матрицы и его геометрическая интерпретация 33
2.2 Алгоритмы кластеризации, основанные на построении О" -покрытий целочисленных матриц 34
2.3 Тестирование на модельных задачах 39
2.4 Тестирование на реальных задачах 42
2.4.1 Анализ данных социологических исследований. Классификация анкет опроса (выделение однородных групп респондентов) 43
2.4.2 Медицинское прогнозирование. Классификация пациентов по истории болезни (выделение однородных групп пациентов) 44
ГЛАВА 3 Алгоритмы поиска покрытий булевой и целочисленной матриц 46
3.1 Основные определения. Об одном подходе к оценке вычислительной сложности алгоритмов поиска неприводимых покрытий булевой матрицы 48
3.2 Наиболее известные алгоритмы поиска неприводимых покрытий булевой матрицы и теоретические оценки их вычислительной сложности 51
3.2.1 Алгоритм, основанный на идее расшифровки монотонной булевой функции 51
3.2.2 Асимптотически оптимальные алгоритмы, основанные на поиске единичных подматриц булевой матрицы 52
3.3 Новые алгоритмы поиска неприводимых покрытий булевой матрицы и
теоретические оценки их вычислительной сложности 53
3.3.1 Алгоритм спуска с пошаговым удалением охватывающих столбцов 53
3.3.2 Алгоритм спуска с пошаговым удалением охватывающих строк и столбцов 57
3.3.3 Алгоритм, использующий «дополнительную матрицу» 58
3.4 Экспериментальные оценки вычислительной сложности алгоритмов построения множества всех неприводимых покрытий булевой матрицы 60
3.5 Модификация алгоритмов построения неприводимых покрытий булевой матрицы для поиска минимальных покрытий 66
3.6 Экспериментальные оценки вычислительной сложности алгоритмов построения множества всех минимальных покрытий булевой матрицы 78
3.7 Решение задачи построения (тупиковых) покрытий целочисленной матрицы на основе построения (неприводимых) покрытий булевой матрицы 89
ГЛАВА 4 Метрические свойства множества покрытий целочисленной матрицы 93
4.1 О числе «коротких» тупиковых покрытий целочисленной матрицы 95
4.2 Асимптотики числа совместимых наборов столбцов булевой матрицы 101
ГЛАВА 5 Метрические свойства дизъюнктивных нормальных форм двузначных логических функций, определенных на к -ичных п -мерных наборах 109
Заключение 112
Литература
- Алгоритмы кластеризации, основанные на иерархической группировке
- Алгоритмы кластеризации, основанные на построении О" -покрытий целочисленных матриц
- Наиболее известные алгоритмы поиска неприводимых покрытий булевой матрицы и теоретические оценки их вычислительной сложности
- Асимптотики числа совместимых наборов столбцов булевой матрицы
Введение к работе
В стандартной постановке задача кластеризации или, как ее еще называют, задача распознавания без обучения, формулируется следующим образом. Исследуется некоторое конечное множество объектов М. Объекты из М описаны в системе признаков {х1,х2,...,хп}. Требуется разбить множество М на «однородные» группы (классы). Число групп может быть задано заранее, а может быть и неизвестным.
Рассматриваются алгоритмы кластеризации, использующие понятия близости объектов из М друг к другу, близости объекта S, SeM, к группе объектов М , М с А/, близости групп объектов М и М", М сМ, М" с М, друг к другу. Традиционно для этого используются функции расстояния. К недостаткам таких алгоритмов можно отнести трудности при выборе содержательно интерпретируемой функции расстояния, при применении которой получалась бы интересная кластерная структура. Особенно затруднителен подбор функции расстояния в задачах кластеризации с целочисленной информацией невысокой значности (т.е. информацией, представленной качественными или номинальными признаками). Такие задачи возникают при обработке данных социологических исследований, в медицинской диагностике, при классификации геологических объектов и др. Для решения указанных задач могут быть применены алгоритмы кластеризации, использующие расстояние Хэмминга и его обобщение на целочисленный случай (алгоритмы типа «ближайший сосед», «дальний сосед», «к средних» и т.п.). Эти алгоритмы не всегда показывают хороший результат в случае, когда информация представлена признаками, принимающими более двух значений.
Известно, что при решении задач распознавания с обучением в случае, когда информация представлена целочисленными признаками, хорошо зарекомендовали себя логические или как их еще называют дискретные алгоритмы. При их конструировании используется аппарат дискретной математики, в частности, булевой алгебры, теории
дизъюнктивных нормальных форм и теории покрытий булевых и целочисленных матриц. Основополагающими работами являются работы Ю.И. Журавлева, СВ. Яблонского и М.Н. Вайнцвайга [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,...,-1}, к 2;
Е[, к 2, г п,-множество всех А ичных наборов вида (crj,..., jr), jt є{0,1,...,А:-і},
/ = 1, г. Пусть а є Егк, (т = {аь...,аг).
Определение. Набор Н из г различных столбцов матрицы L называется а-покрытием, если подматрица L матрицы L, образованная столбцами набора Н, не содержит строку (crj,..., ar ).
Определение. Набор столбцов Н матрицы L, являющийся а-покрытием,
її
называется тупиковым а-покрытием, если подматрица L с точностью до перестановки строк содержит а-подматрицу, т.е. подматрицу вида
Р\ °г °ъ •" аг-\ аг ах р2 аъ ••• аг_х аг
crj а2 ст3 ••• тг_х рг
где Д ФСГ(, i = \,r.
В случае к = 2 тупиковое (0,...,0)-покрытие называется неприводимым
покрытием. В этом случае а -подматрица является единичной подматрицей. Покрытие минимальной длины называется минимальным покрытиям.
Обозначим через C(L, сг), B(L, сг) и S(L, сг) соответственно множество сг-покрытий матрицы L, множество тупиковых сг-покрытий матрицы L и множество сг -подматриц матрицы L. Положим
C(L) = (j U C(L,a),B(L) = (j U B(L,cf),S(L) = \J (J S(L,а). г=\оєЕгк r=laeEk r=\aeErk
Приведем геометрическую интерпретацию понятия сг-покрытия целочисленной матрицы L [45, 59].
Множество El является -значным «-мерным кубом. Обозначим через ML -множество точек куба Е%, задаваемых строками матрицы L. Положим ML =Е%\ML. Набору столбцов Н с номерами (j\,-..,jr), являющемуся сг-покрытием матрицы L, поставим в соответствие множество Е а всех точек « = («),...,«„) из ЕІ таких, что a,- =07,/ = 1, г. Очевидно, Е является (п-г)-мерным подкубом (гранью) куба
Е% и целиком принадлежит ML. В случае г = п, множество точек Е а является 0-мерным подкубом, состоящим из одной точки сг. Таким образом, множеству C(L) взаимнооднозначно соответствует множество всех подкубов, содержащихся в ML.
Отметим, что является подкубом тогда и только тогда, когда сг2 с 07, Я 2 с Я,. Пусть Е - некоторое подмножество El. Будем говорить, что подкуб Е cz Е является максимальным в Е, если не существует другого подкуба Е" cz Е такого, что Е а Е". Множество всех максимальных подкубов в Е будем обозначать &max (Е). Нетрудно видеть, что множеству B(L) взаимнооднозначно соответствует множество &maK(ML). Таким образом, задача построения множества B(L) может быть сформулирована как задача построения множества всех максимальных подкубов в ML. Задачи построения покрытий целочисленной матрицы могут быть также сформулированы как задачи построения дизъюнктивной нормальной формы (ДНФ) двузначной логической функции специального вида, заданной на -ичных «-мерных наборах [34,35,39, 86]. Действительно, пусть на наборах из Е% задана всюду определенная логическая функция F, принимающая значения из {0,1}; BF - множество наборов, на которых функция F принимает значение 0. Множество всех таких функций обозначим через % п. Определение. Элементарной конъюнкцией (э.к.) называется выражение вида ха} ...ха.г, где переменная хг принимает значения из {0,1,...Д-1}, сг,. е{0,1,...Д-1}, i = \,r, X. = { 1, если Xi = а,-; 0, иначе, и все j), і = \,г, различны.
Число г называется рангом э.к. Интервал истинности э.к. 53 обозначается через N Q .
Определение. Э. к. 33 называется допустимой для F, если N SQ f\BF =0.
Определение. Э.к. © называется максимальной для F, если 33 допустимая конъюнкция для F и не существует допустимой для F конъюнкции S3 такой, что N Q =э JV 8.
Определение. Сокращенной ДНФ функции F называется ДНФ, состоящая из всех максимальных конъюнкций функции F.
Пусть BF состоит из наборов вида (р\ир\2,...,р п), ..., (РтХ,Рт2,...,Ртп). Из наборов BF составим матрицу L вида Ai Pa - A» /?21 Pl2 •• / .Аяі Дя2 • Hmn_ Справедливы приведенные ниже утверждения 5.1 и 5.2. Утверждение 5.1. Э.к. ха.х ...ха.г является допустимой для F тогда и только J\ Jr тогда, когда набор столбцов с номерами j\,...,jr является (crj,...,crr)-покрытием матрицы L. Утверждение 5.2. Э.к. ха.х ...ха.г является максимальной для F тогда и только h Jr тогда, когда набор столбцов с номерами j\,...,jr является тупиковым (o"i,...,crr) . V покрытием матрицы L.
Из утверждений 5.1 и 5.2 следует, что алгоритмы поиска покрытий целочисленной матрицы могут быть применены при построении допустимой ДНФ двузначной логической функции, алгоритмы поиска тупиковых покрытий целочисленной матрицы могут быть применены при построении сокращенной ДНФ двузначной логической функции и наоборот.
Традиционно вопросы построения эффективных реализаций логических процедур распознавания связаны с изучением метрических (количественных) свойств множества покрытий и построением эффективных алгоритмов поиска покрытий булевых и целочисленных матриц. В частности, такая информация как типичная длина (тупикового) покрытия, типичное число (тупиковых) покрытий важна для получения оценок вычислительной сложности алгоритмов поиска тупиковых покрытий, и позволяет оценить требуемые вычислительные ресурсы, лучше организовать память компьютера и тем самым понизить необходимые требования к вычислительной технике при реализации распознающих процедур Технические основы получения указанных оценок были заложены в работах Н.В. Носкова, В.А. Слепян, Е.В. Дюковой и А.Е. Андреева [1 - 3, 29 - 33, 65, 66, 72 - 74] при изучении метрических свойств множеств тупиковых и минимальных тестов.
В [34, 35, 39, 86] были получены асимптотики числа покрытий из В(Ь) И ДЛИНЫ покрытия из В(Ь) для почти всех матриц L размера тхп с элементами из {0,1,...,к-\},к 2, при условиях /?-»оо и та п кт , а \, В 1. Аналогичные оценки получены для числа подматриц из S(L) И порядка подматрицы из S(L). Показано, что в данном случае число покрытий из В(Ь) ПОЧТИ всегда асимптотически совпадает с числом всех подматриц из 5(1.) и по порядку меньше числа покрытий из C(L). В [49] был рассмотрен прямо противоположный случай, а именно, р когда па тйкп , а \, В \. Получены асимптотики типичных значений числа подматриц из S(L) и порядка подматрицы из S(L). Установлено, что в случае, когда па т кп , а \, /? 1/2, почти всегда число подматриц из S(L) ПО порядку больше числа покрытий из В(Ь). Кроме того, для практически общего случая в [49] получены асимптотики типичных значений числа покрытий из C(L) И длины покрытия из С (і) и показано, что при r \ogkm-logk(logkmxkiri) и и- » у почти всех матриц L размера тхп отсутствуют покрытия длины г. Оставался не изученным интересный с практической точки зрения вопрос, а именно: при каких условиях (в частности, при каких ограничениях на длину рассматриваемых покрытий) почти всегда число покрытий матрицы L асимптотически совпадает с числом ее тупиковых покрытий. Ответ на этот вопрос, во первых, давал бы возможность использовать для построения тупиковых покрытий алгоритмы нахождения покрытий, не обязательно являющихся тупиковыми. Во вторых, выявление указанных условий напрямую связано с тем, что при решении прикладных задач распознавания обычно ограничивают сверху длину рассматриваемых покрытий. Дело в том, что короткие покрытия порождают более информативные элементарные классификаторы и при этом сокращается объем вычислений.
Основное внимание исследователей уделялось алгоритмам поиска неприводимых покрытий булевой матрицы и к настоящему моменту разработан целый ряд таких алгоритмов, каждый из которых ориентирован на определенный тип матриц. При этом выделяют три типа матриц: «вертикальная» (число строк матрицы существенно превосходит число ее столбцов); «горизонтальная» (число столбцов матрицы существенно превосходит число ее строк); «квадратная» или «близкая к квадратной» (число строк в матрице совпадает или незначительно отличается от числа ее столбцов).
Случай вертикальной матрицы является достаточно простым. В данном случае из-за сравнительно небольшого числа столбцов в матрице задачу построения множества неприводимых покрытий можно решить полным (или почти полным) перебором. Одним из первых алгоритмов, предназначенных для поиска неприводимых покрытий в вертикальной матрице, является алгоритм, разработанный Т.П. Слуцкой и З.Е. Королевой. Этот алгоритм основан на идее расшифровки монотонной булевой функции [62, 75].
Для оценки эффективности алгоритмов построения неприводимых покрытий булевой матрицы, в [33, 35, 37, 79] Е.В. Дюковой было введено понятие асимптотически оптимального алгоритма и построены асимптотически оптимальные алгоритмы поиска неприводимых покрытий булевой матрицы для горизонтальной матрицы. Алгоритмы основаны на поиске единичных подматриц.
Оставался не изученным технически более сложный случай, когда матрица квадратная или близка к квадратной.
Следует отметить, что не всякий алгоритм поиска неприводимых покрытий может быть легко модифицирован для случая поиска тупиковых покрытий общего вида (тупиковых т -покрытий). Поэтому, с появлением новых моделей процедур распознавания и классификации актуальной является задача построения эффективной и универсальной схемы для поиска (тупиковых) покрытий целочисленной матрицы на основе поиска (неприводимых) покрытий булевой матрицы.
Основной целью диссертационной работы является, во-первых, исследование возможности использования комбинаторных методов при решении задач кластерного анализа с целочисленной информацией, в частности, применение алгоритмов поиска покрытий булевых и целочисленных матриц, и, во вторых, построение эффективных в теоретическом и практическом плане алгоритмов поиска тупиковых, минимальных и близких к минимальным покрытий. В данном направлении получены следующие результаты.
Для решения задач кластеризации с целочисленной информацией в диссертационной работе разработан подход, основанный на принципе «невстречаемости» наборов из допустимых значений признаков в описаниях объектов класса. В данном случае близость объекта S к группе объектов М оценивается числом справедливых высказываний типа «если объект S и все объекты из группы М не содержат некоторого подописания (набора допустимых значений признаков), то объект S близок к группе М ». По сути, решение задачи кластеризации ведется непосредственно в терминах той предметной области, в которой решается задача. Подописания, используемые при оценке близости объекта S к группе объектов М, порождаются покрытиями матрицы, образованной признаковыми описаниями объектов из М.
Алгоритмы кластеризации, разработанные на базе предлагаемого подхода, являются очень гибкими в настройке. К настраиваемым параметрам здесь относятся длины рассматриваемых покрытий, веса покрытий и т.п. В случае бинарной информации можно указать значения параметров, позволяющие получать аналоги алгоритмов, основанных на расстоянии Хемминга и работающих по принципам «дальний сосед» и «ближайший сосед».
Результаты экспериментов на модельных и реальных задачах с целочисленной информацией показали в ряде случаев, например в случае, когда признаки, описывающие классифицируемые объекты, принимают более двух значений, преимущество алгоритмов, основанных на построении покрытий, над алгоритмами, использующими расстояние Хемминга в качестве меры близости. При этом в алгоритме кластеризации использовалась процедура построения тупиковых покрытий целочисленной матрицы, основанная на поиске неприводимых покрытий булевой матрицы.
В диссертационной работе построены эффективные в практическом теоретическом плане алгоритмы поиска неприводимых покрытий булевой матрицы (алгоритмы УОС1, УОС2 и ДМ).
Алгоритм УОС1 (алгоритм спуска с пошаговым удалением охватывающих столбцов) основан на использовании следующего очевидного утверждения: в неприводимом покрытии не существует пары столбцов такой, что один столбец охватывает другой. На каждом шаге работы алгоритма строится набор столбцов, не содержащий охватывающих столбцов. Построение таких наборов является простой в выислительном плане задачей и в тоже время позволяет существенно сократить перебор. Алгоритм является «универсальным», т.е. эффективным при любых соотношениях числа строк и столбцов исходной матрицы (эксперементы проводились на случайных матрицах с числом строк меньшим или равным 1000 и числом столбцов меньшим или равным 200). Применение алгоритма УОС1 позволило существенно (в ряде случаев на порядок и более) сократить время построения множества неприводимых покрытий по сравнению с другими алгоритмами.
Алгоритм УОС2 (алгоритм спуска с пошаговым удалением охватывающих столбцов и строк) является модификацией алгоритма УОС1, позволяющей еще более сократить время построения множества неприводимых покрытий в случае «вертикальных» матриц и матриц с большим числом нулевых элементов. На каждом шаге алгоритма УОС2 строится покрытие, не содержащее охватывающих столбцов.
Алгоритм ДМ основан на поиске и удалении охватывающих строк в исходной матрице и в матрице, являющейся «дополнительной» к исходной. Алгоритм ДМ эффективен при небольшом числе столбцов исходной матрицы и практически нечувствителен к числу строк в ней.
Проведено теоретическое исследование алгоритмов поиска коротких покрытий. Показано, что указанные алгоритмы являются асимптотически эффективными при условии, что осуществляется поиск неприводимых покрытий по длине близких к минимальному покрытию. Ниже приведена более точная формулировка результата.
Пусть LeMmn; В(L,б) -множество неприводимых покрытий матрицы L; G(L) -конечная совокупность наборов столбцов матрицы L, содержащая B(L,0J. Предполагается, что каждый набор в G(L) не содержит одинаковых столбцов и некоторые наборы столбцов в G[L) могут встречаться более одного раза. Обозначим через 1 (- )1 число наборов в G(L) С учетом их повторений.
Пусть алгоритм А строит покрытия из B(L,Q) путем последовательного просмотра всех наборов из G[L). При этом каждый набор из G(L) просматривается столько раз, сколько раз он встречается в G(L). Таким образом, на каждом шаге алгоритма А строится некоторый набор столбцов Н из G(L) И проверяется принадлежность Н к B(L,0J. Совокупность G(L) назовем погружением алгоритма А.
Число шагов алгоритма А равно к/().
Нас будет интересовать вычислительная сложность алгоритма А в типичном случае (для почти всех булевых матриц размера тхп). Из оценок следует, что число неприводимых покрытий почти всегда растет экспоненциально с ростом размера матрицы. Эффективность алгоритма А имеет смысл оценивать в терминах полиномиальной задержки [87].
Будем говорить, что алгоритм А строит погружение G(L) С полиномиальной задержкой, если на каждом шаге выполняется не более d[m,n) элементарных операций и d{m,n) ограничено сверху полиномом от размера матрицы. Под элементарной операцией понимается просмотр одного элемента матрицы L.
Определение. Алгоритм А является асимптотически эффективным, если алгоритм А строит погружение G{V) с полиномиальной задержкой и для почти всех матриц L из Мтп выполнено \G(L)\ і Ч limy1-— -, тІт,п).. "- 10 Я (і, 0) где х(т,п) ограничено сверху полиномом от размера матрицы L, \ВуЬ,Ь\ множества B\L,by. Если г{т,п) = \, то алгоритм А называется асимтотически оптимальным [25, 76]. Под вычислительной сложностью алгоритма А будем понимать величину d(m,n)p(i) .
Аналогичным образом может быть введено понятие эффективного алгоритма построения тупиковых покрытий целочисленной матрицы. - мощность
Здесь и далее через \Q\ обозначается мощность множества Q.
Следует отметить, что построенные в [35, 79] алгоритмы являются асимтотически а тР оптимальными при т nS2 , а \, /? 1. В [35] в качестве погружения используются наборы столбцов, содержащие единичные подматрицы исходной матрицы, а в [79] - наборы столбцов, являющиеся неприводимыми покрытиями. При этом каждый набор столбцов встречается в погружении столько раз, сколько единичных подматриц он содержит.
Определение. Набор Н из г различных столбцов матрицы называется совместимым, если выполнено одно из двух условий: 1) г = 1; 2) г 2 и любые два столбца набора Н содержат единичную подматрицу порядка 2.
Определение. Совместимый набор столбцов матрицы L, являющийся покрытием, называется совместимым покрытием.
Погружением алгоритма УОС1 является некоторое подмножество из множества совместимых наборов. Погружением алгоритма УОС2 является некоторое подмножество из множества совместимых покрытий.
Справедливы теоремы 3.1 и 3.2, приведенные ниже. Теорема 3.1. Алгоритм УОС1 строит погружение с полиномиальной задержкой, не превосходящей 2т п. Теорема 3.2. Алгоритм УОС2 строит погружение с полиномиальной задержкой, 2 1 1 не превосходящей 2т п + 2т п . Пусть rx = [log т - \ogk In logA т -1]l.
Асимптотическая эффективность алгоритмов поиска неприводимых покрытий, длины которых принадлежат отрезку [1, Г] ], обосновывается изучением метрических свойств множества покрытий, множества совместимых наборов столбцов и множества совместимых покрытий. Выше было отмечено, что при r logkm-\ogk(logkmx]nn) и п —»оо у почти всех матриц размера тхп отсутствуют покрытия длины г. В данной работе получены асимптотики типичных значений для числа покрытий и числа тупиковых покрытий, длины которых не превосходят Г]. Результат формулируется следующим образом.
Пусть; р -интервал (log m-\ogk(}ogk mx]nn),ri]; MJ n, к 2, - множество всех матриц размера тхп с элементами из {0,1,..., -1}; С„() и ДД)-соответственно совокупность покрытий из С(), L є Мтп, длины которых принадлежат интервалу р, и совокупность покрытий из B(L), длины которых принадлежат интервалу р; Cr(L) и Br(L) - соответственно совокупность покрытий из C(Z) длины Tj, и совокупность
ПОКРЫТИЙ ИЗ B[L) ДЛИНЫ Aj.
Имеет место следующая Теорема 4.1. Если т кп , /3 \/2, то для почти всех матриц L из Мтп при л-»со справедливо \В9 (1)«\cf (L)\«\СП (L)\«\Bn (L)\ к Q (1 - Г" Г Следствием из теоремы 4.1 является верхняя оценка длины минимального покрытия в типичном случае.
Пусть 5r (1,,6)- множество тупиковых (0,...,0)-покрытий длины г Cr \L,b\ -множество (0,...,0)-покрытий покрытий длины г; Ur(L) - множество совместимых наборов столбцов матрицы L длины г; у/ отрезок вида \q\,qj\, где #i 1, Чг - п 1 U(L) = f,Ur(L); Ur{L)= Ur(L); (і,б)= J Br (l,6); c(L,o) = {JCr(L,o); r=\ rey/ ГЩІ r=\ Cw(L,0)=[jCr(L,0);V(L) = U{L)f]c(L,0);Vl//{L) = U(L)r\Cvr(L,0). rey/
Справедливы теоремы 4.4 и 4.5, приведенные ниже. Пусть (р2 -интервал [1,/j];
Теорема 4.4. Если т 2" , р \12, то для почти всех матриц L из Мтп при п— сс справедливо c {L °) К(ьЬЫ1 °) сз(і-2- )т.
Теорема 4.5. Если log2 п - о {пі) и т 2п , р \12, то для почти всех матриц L из Мтп при и-»°о справедливо
Из теорем 4.4 и 4.5 сразу следует, что при поиске неприводимых покрытий, длины которых не превосходят /j, эффективны алгоритмы спуска (У0С1, У0С2), эффективен также алгоритм, основанный, на переборе всех наборов столбцов длины, не превосходящей 7j, и для последнего г(т,п) не превосходит log2 т.
Пусть q\ - интервал [log2 тп,п\. Справедливы следующие теоремы 4.2 и 4.3.
Теорема 4.2. Если па т 2" , а \, Р \, то для почти всех матриц L из М п при п — со справедливо «с, «M-l wl-z \V{L)\ \C(
Теорема 4.3. Если па т 2п , а \, р \, то для почти всех матриц L из Mmn при и-» со справедливо \U(L}»V. Полученные в теоремах 4.2 и 4.3 асимптотики важны для оценки вычислительной сложности алгоритмов спуска (алгоритмы УОС1, УОС2). На основе результатов теоремы 4.1 в диссертационной работе получены новые оценки, касающиеся изучения метрических свойств допустимых и максимальных конъюнкций логических функций, заданных множеством нулей.
Пусть ((F,r) -множество всех допустимых конъюнкций функции F, F ef wj, ранга г; S(F,r) -множество всех максимальных конъюнкций функции F ранга г; G{F, p) = j6(F,r); в( )« (J «( )• retp ГЄ(р
Из теоремы 4.1 и утверждений 5.1, 5.2 сразу следует
Теорема 5.1. Если т к" , /3 \/2, то для почти всех функций F из tnn при п- оо справедливо
В настоящей работе разработан подход, позволяющий решать задачу построения (тупиковых) с -покрытий целочисленной матрицы на основе построения (неприводимых) покрытий булевой матрицы. По исходной целочисленной матрице L, LeMmn, специальным образом строится бинарная матрица L размера тхп где п - kn. Показано, что существует взаимнооднозначное соответствие между (тупиковыми) а -покрытиями матрицы L и специального вида (неприводимыми) покрытиями матрицы L. Проведено экспериментальное исследование указанного подхода на случайных матрицах и при решении прикладных задач. Позднее, данный подход был использован в [27] при построении нормальных форм бинарных функций &-значной логики по перечню их нулей.
Построены модификации рассмотренных в работе алгоритмов поиска неприводимых покрытий булевой матрицы на случай поиска минимальных покрытий.
Диссертационная работа состоит из введения, пяти глав и заключения.
В главе 1 рассматривается классическая постановка задачи кластеризации и описаны наиболее известные и часто применяемые на практике алгоритмы ее решения.
В главе 2 предлагается подход к решению задачи кластеризации с целочисленной информацией, основанный на построении а -покрытий классов. Приведены результаты тестирования на модельных множествах данных и реальных задачах из области медицинской диагнотики и обработки данных социологиских исследований.
В главе 3 рассматривается задача построения множества всех неприводимых покрытий булевой матрицы и задача построения множества всех минимальных покрытий булевой матрицы. Вводится понятие асимтотически эффективного алгоритма построения неприводимых покрытий булевой матрицы. Описаны известные алгоритмы поиска неприводимых покрытий. Предложены новые алгоритмы поиска неприводимых покрытий. Построены модификации новых алгоритмов на случай поиска минимальных покрытий. Приведены результаты теоретического и экспериментального исследования • сложности предложенных в работе алгоритмов поиска неприводимых и минимальных покрытий, показывающие их эффективность. Описан способ построения (тупиковых) покрытий целочисленной матрицы на основе построения (неприводимых) покрытий булевой матрицы.
В главе 4 изучаются метрические свойства множества а -покрытий целочисленной р матрицы. Для случая, т кп , (5 1/2, указаны ограничения на длину а -покрытий, при которых при п — оо почти всегда (для почти всех матриц размера тхп) почти все а покрытия являются тупиковыми. Получена асимптотика типичного числа таких покрытий. Как следствие получена асимптотическая верхняя оценка длины минимального а -покрытия в типичном случае. Изучаются метрические свойства множества совместимых наборов столбцов и множества совместимых покрытий булевой матрицы. Получены асимптотики типичных значений для числа совместимых наборов столбцов и числа совместимых покрытий в случае па т 2п , а \, /? 1. Получены асимптотики типичных значений для числа совместимых наборов столбцов и числа совместимых покрытий, длины которых принадлежат интервалу [1,log2 w-log2lnlog2 w —і], в случае Р \og2n = o(m) и т 2" ,р \12.
В главе 5 изучаются метрические свойства специального вида дизъюнктивных нормальных форм двузначных логических функций, определенных на &-ичных п -мерных наборах. Для случая, т кп , J3 1/2, где т - число нулей логической функции, указаны ограничения на ранг конъюнкций, при которых при п- х почти всегда (для почти всех функций указанного вида) почти все допустимые конъюнкции являются максимальными. Получена асимптотика типичного числа таких конъюнкций.
Алгоритмы кластеризации, основанные на иерархической группировке
Благодаря своей простоте, иерархические процедуры кластеризации находятся среди наиболее известных методов. Процедуры можно разделить на два различных класса: агломеративные процедуры и делимые процедуры. Агломеративные (объединяющие) процедуры начинают с одиночных классов и образуют последовательность постепенно объединяемых классов. Делимые, напротив, начинают с одного класса, содержащего все объекты, и образуют последовательность постепенно расщепляемых классов. Дальнейшее рассмотрение ограничим агломеративными процедурами.
Рассмотрим последовательность разделений т объектов на группы. Первый шаг последовательности - разделение на m групп, каждая из т групп содержит в точности по одному объекту. Следующий шаг - разделение на т-\ группу, затем на. т-2 групп и так далее до т -ого шага в котором все объекты образуют одну группу. Таким образом к -тому шагу соответствует разделение на т + \-к групп, где к = ],...,т. Если для любых двух объектов Si и S2 справедливо, что если они объединены в одну группу на к -том шаге, они будут содержаться в одной группе и на последующих шагах, то такая последовательность разделений называется иерархической группировкой.
Пусть требуется разделить т объектов на / классов. Основные этапы агломеративной группировки описываются следующей процедурой: Процедура: Базовая Агломеративная Группировка Шаг 1. Пусть І =т иМ( = {/}, = !,» т Шаг 2. Если / /, выход из процедуры. ШагЗ. Найти такую пару групп Mt, М= для которой справедливо: p(Mj,MA = min р(Мг,Мр), где /?(А/Г,М_] расстояние между группами Мг и Л/„ в введенном выше смысле. Шаг 4. Обединить Mt и М,-, уничтожить М, уменьшить / на единицу. Шаг 5. Перейти к шагу 2.
Процедура заканчивает работу, когда достигнуто заданное число групп. Заметим, что результат работы процедуры зависит от выбора расстояния между группами. Например, процедура, использующая расстояние pmin, будет лучше работать чем процедура, использующая расстояние pmax, в случае, когда группы компактны и хорошо разделены (при этом группы могут быть вытянуты или иметь отростки), но хуже, если между компактными группами существует некоторый мост из небольшого числа объектов. Демонстрирует эти различия следующий рисунок.
Пусть, как и ранее, имеется выборка М из т обектов S\,S2,...,Sm которые мы хотим разделить на / непересекающихся классов М\, М2, ..., Mi . Объекты из одного класса должны быть более схожи между собой, чем объекты из разных классов. Для хорошей постановки задачи необходимо определить критерий, который измеряет качество группировки. Тогда задача сводится к нахождению такого разделения, которое минимизирует (максимизирует) критерий.
В качестве таких критериев могут быть использованы приводимые ниже. Критерий суммы квадратов ошибок Пусть л,- - число объектов в Mi и пусть S; - среднее арифметическое векторов признаков всех объектов, входящих в /-тый класс: S; =— V S. Тогда сумма квадратов ni SeMj і _ ошибок определяется функцией Je = р2 (5 - SA. /=1 SeM, Данная функция минимизирует сумму квадратов длин векторов ошибок. То есть Je измеряет общую квадратичную ошибку при представлении т выборок Si,S2,.-.,Sm центрами / групп ,...,5/. Повышение качества группировки влечет уменьшение значения Je .
Критерий суммы квадратов ошибок - хорошая функция критерия в случае, когда выборки образуют достаточно хорошо разделенные облака, и число таких облаков не очень велико. Критерий рассеяния Введем сначала несколько определений. Средний вектор /-той группы Sj = — Г 5. Пі SeMj - 1 1 l Общий средний вектор 5 - — ] 5 = - /5, mSeM ni=\ Матрица рассеяния для /-той группы М( = (5-5,)(5-5,) . SBM, I Матрица рассеяния внутри группы Mw = М,-. i=i і _ _ _ _ Матрица рассеяния между группами Мв = ,(5,- -S)(S; -S)T . Общая матрица рассеяния Мт = ] (5 - S)(S - S)T . SeM
Из этих определений следует, что общая матрица рассеяния есть сумма матрицы рассеяния внутри группы и матрицы рассеяния между группами: MT=MW+MB.
Заметим, что общая матрица рассеяния не зависит от разделения множества выборок на группы, а зависит только от общего множества объектов. Матрицы рассеяния между группами и внутри группы зависят от разделения, при этом если внутригрупповое рассеяние уменьшается, то межгрупповое увеличивается.
В качестве критериев могут быть использованы следующие функции: 1. След матрицы - одна из самых простых скалярных мер матрицы. След матрицы Mw, это ни что иное, как критерий суммы квадратов ошибок:
Алгоритмы кластеризации, основанные на построении О" -покрытий целочисленных матриц
Пусть L - матрица размера тхп с элементами из {0,1,...,к-\}, к 2; Е[, к 2, г п,- множество всех к-ичных наборов вида (crj,...,crr), сг,- є{0,1,...Д-і}, i = r. Рассмотрим теЕгк, сг = (сгі,...,аг). Определение. Набор Н из г различных столбцов матрицы L называется а її покрытием, если подматрица L матрицы L, образованная столбцами набора Н, не содержит строку (crj,..., ar).
Определение. Набор столбцов Н матрицы L, являющийся а-покрытием, называется тупиковым а-покрытием, если подматрица LH с точностью до перестановки строк содержит а-подматрицу, т.е. подматрицу вида Р\ 2 з " ar-\ V сг, р2 т3 ег_х схг т, а2 сг3 аг_х рг_ где Д (jt, i = \,r. Понятие сг-покрытия впервые введено в [34,35].
В случае к = 2 тупиковое (0,...,0)-покрытие называется неприводимым покрытием. В этом случае сг -подматрица является единичной подматрицей. Покрытие минимальной длины называется минимальным покрытием. Обозначим через C(L, а) и B(L,a) соответственно множество сг-покрытий матрицы L и множество тупиковых сг -покрытий матрицы L. Положим C(I) = U (J C(L,a), B(L) = [j [J B(L,a). r=\ aeErk г=\ аєЕгк Приведем геометрическую интерпретацию понятия т-покрытия целочисленной матрицы L [45, 59].
Множество Е% является -значным n-мерным кубом. Обозначим через ML -множество точек куба Е%, задаваемых строками матрицы L. Положим ML =Е%\ML. Набору столбцов Н с номерами (У),...,уЛ), являющемуся сг-покрытием матрицы L, поставим в соответствие множество Е а всех точек а = (ссі,...,а„) из Е таких, что «, =о-,-,/ = 1, г. Очевидно, Е а является (л-г)-мерным подкубом (гранью) куба Е% и целиком принадлежит ML. В случае г = п, множество точек Е а является 0-мерным подкубом, состоящим из одной точки ст. Таким образом, множеству C(L) взаимнооднозначно соответствует множество всех подкубов, содержащихся в ML. Отметим, что Е а{ н является подкубом тогда и только тогда, когда ст2 = o-j, Я2сЯ,.
Пусть Е - некоторое подмножество Е%. Будем говорить, что подкуб E czE является максимальным в Е, если не существует другого подкуба Е" с: Е такого, что Е с Е". Множество всех максимальных подкубов в Е будем обозначать ётах (Е). Нетрудно видеть, что множеству B(L) взаимнооднозначно соответствует множество ёшах (ML). Таким образом, задача построения множества B(L) может быть сформулирована как задача построения множества всех максимальных подкубов в ML. Пусть задача кластеризации решается для множества объектов М = {Sb...,Sm}, МсЕ.
Основная идея описываемых в данной главе алгоритмов состоит в следующем. Рассмотрим ситуацию, когда определяется степень принадлежности объекта S, S є М, к группе объектов М , М с:М. Наличие в описании S и некоторых объектов из М одинакового набора значений признаков не даёт справедливого суждения о принадлежности исследуемого объекта к множеству М . И в то же время, если описание S содержит набор значений признаков, который не присутствует в описании ни у одного объекта из М , то можно сказать, что объединение S и М нарушает внутреннюю структуру множества М . Таким образом, рассматривая различные комбинации значений признаков, не содержащихся в описаниях объектов из М , можно оценить близость объекта S к множеству М .
Через Ьц обозначим матрицу, строками которой являются признаковые описания объектов из U, U с.М.
Введем меру близости множества М", М"сМ, к множеству М , М сі/, как отношение числа покрытий матрицы LM , являющихся также покрытиями матрицы -д/»ил/ » к числу покрытий матрицы LM . Отметим, что при оценке близости М"
к М вместо множества покрытий может быть использовано множество тупиковых покрытий, множество минимальных покрытий, множество покрытий ограниченной длины и т.п. В качестве иллюстрации предложенного подхода более подробно рассмотрим алгоритм кластеризации, основанный на построении тупиковых а -покрытий.
Введем следующие обозначения: сгг(М ) - множество покрытий из B(LM ); о-г(М М") - множество покрытий из (/, -)0 С(Хд/ ид/») (множество тупиковых сг покрытий матрицы, образованной признаковыми описаниями объектов из М , которые также являются тупиковыми а -покрытиями матрицы, образованной признаковыми описаниями объектов из М [}Мп).
Наиболее известные алгоритмы поиска неприводимых покрытий булевой матрицы и теоретические оценки их вычислительной сложности
Пусть L - произвольная матрица из Мтп. Каждому набору (Т = (сгі,...,сгЛ) из Е% может быть взаимно однозначно сопоставлен набор єд ={j\,...,jr} всех таких чисел jt из {1,2,...,«}, для которых а =1.
Работа алгоритма СК сводится к следующему. Просматриваются всевозможные наборы из . Для каждого набора устанавливается, является ли он правильным относительно L. Набор j = ( jj,...,crw) является правильным тогда и только тогда, когда набор столбцов с номерами из ед является покрытием матрицы L. Если набор & является правильным, то осуществляется проверка: является ли набор столбцов с номерами из є6 неприводимым покрытием.
При просмотре наборов из ЕІ движение происходит по такой шкале: набор (а[,...,ег п) следует за набором (сг1,...,сгя),если За счет монотонности удается сократить число просматриваемых наборов из Е%.
В [33, 35] был построен алгоритм А01, основанный на перечислении с полиномиальной задержкой 0[тп) всех единичных подматриц булевой матрицы L. Вычислительная сложность алгоритма А01 не превосходит 0(mn)S(L), где S(L) - число единичных подматриц булевой матрицы L, В [33, 35] получены результаты, свидетельствующие о том, что алгоритм А01 асимптотически оптимален в случае, р па т 2" (а 1, /3 1), п—»оо, и не является асимптотически оптимальным в случае, когда число строк матрицы по порядку превосходит число столбцов, так как в указанном случае число единичных подматриц по порядку больше числа неприводимых покрытий.
В [37, 79] построен алгоритм А02, основанный на перечислении с полиномиальной задержкой 0\т п\ таких единичных подматриц, которые порождают неприводимые покрытия. В данном алгоритме некоторые неприводимые покрытия строятся неоднократно, т.е. некоторые шаги повторяются. Вычислительная сложность алгоритма А02 не превосходит Оуп n\S (L), где S (L) - число единичных подматриц, порождающих неприводимые покрытия.
В [33, 35] было показано, что в случае т па, а \, п— со, почти всегда (для почти всех матриц размера тхп) величина S(Z,) асимптотически совпадает с величиной 5(,б) . Отсюда следует, что в указанном случае алгоритмы А01 и А02 являются асимптотически оптимальными. В качестве погружения в алгоритме А01 выступают наборы столбцов содержащие единичные подматрицы. В алгоритме А02 - наборы столбцов, содержащие только те единичные подматрицы, которые порождают неприводимые покрытия.
В следующем разделе предложены новые алгоритмы построения неприводимых покрытий (УОС1 и УОС2), основанные на удалении охватывающих строк и столбцов.
Пусть Ь = {аЛ, i = \,2,...,m, j = 1,2,...,п, - булева матрица. Столбец матрицы L будем называть единичным, если все его элементы равны единице, и нулевыми, если все его элементы равны нулю. Остальные столбцы будем называть смешанными. Будем говорить, что столбец с номером д охватывает столбец с номером j2, если а у ау при / = 1,2,...,т. Будем говорить, что столбец с номером j покрывает строку с номером / (строка с номером / покрывает столбец с номером j), если ау = 1.
Суть описываемого алгоритма поиска неприводимых покрытий, обозначаемого далее алгоритм УОС1, состоит в следующем. В процессе решения задачи алгоритмом осуществляется односторонний обход дерева, вершинам которого соответствуют пары (Я, LH), где Я - некоторый TJ упорядоченный набор номеров столбцов и L - некоторая подматрица матрицы L, которая строится по набору Я. Обход дерева начинается с корневой вершины, которой соответствует пара (0,L).
Асимптотики числа совместимых наборов столбцов булевой матрицы
В данной главе рассмотрена связь между задачей нахождения т-покрытий целочисленной матрицы с элементами из множества {0,1,...,-1} и задачей построения сокращенной дизъюнктивной нормальной формы двузначной логической функции, заданной на &-ичных наборах [39, 86]. На основе теоремы 4.1. получены новые оценки, касающиеся изучения метрических свойств допустимых и максимальных конъюнкций р логических функций, заданных множеством нулей. А именно, для случая, m kn , Р 1/2, где т - число нулей логической функции, указаны ограничения на ранг конъюнкций, при которых при п — оо почти всегда (для почти всех функций указанного вида) почти все допустимые конъюнкции являются максимальными. Получена асимптотика типичного числа таких конъюнкций.
Задача построения покрытий целочисленной матрицы может быть сформулирована как задача построения ДНФ двузначной логической функции специального вида, заданной на к -ичных п -мерных наборах. Поясним сказанное.
Пусть на наборах из Е% задана всюду определенная логическая функция F, принимающая значения из {0,1}, BF - множество наборов, на которых функция F принимает значение 0, /? = т. Множество всех таких функций обозначим через f L Определение. Элементарной конъюнкцией (э.к.) называется выражение вида ха.х ...ха.г, где переменная х,-. принимает значения из {0,1,...,к-\\, Л Jr -Ч 1 а, є{0,1,...Д-і}, i = \,r, Ji [0, иначе, и все Ji, i = \,r, различны. Число г называется рангом э.к. Интервал истинности э.к. 33 обозначается через N Q . Определение. Э.к. 33 называется допустимой для F, если N% f]BF =0. Определение. Э.к. 33 называется максимальной для F, если 33 допустимая конъюнкция для F и не существует допустимой для F конъюнкции 33 такой, что Определение. Сокращенной ДНФ функции F называется ДНФ, состоящая из всех максимальных конъюнкций функции F. ПуСТЬ Вр СОСТОИТ ИЗ Наборов ВИДа (Pu Pl2 --- Pln) » (Рт\ Рт2 - Ртп)- Из наборов BF составим матрицу L вида Рп Рп - Ры Рг\ Ріг Ріп _Рт\ Pml Ртп_ Справедливы следующие утверждения. Утверждение 5.1. Э.к. ха.х ...ха.г является допустимой для F тогда и только тогда, когда набор столбцов с номерами j\,...,jr является ( 7j,...,ОГ)-покрытием матрицы L. Утверждение 5.2. Э.к. х7} ...ха.г является максимальной для F тогда и только тогда, когда набор столбцов с номерами j\,...,Jr является тупиковым ( jj,...,crr)-покрытием матрицы L. Пусть (S {F,r) -множество всех допустимых конъюнкций функции F, F .%тп, ранга г;- (F,r) -множество всех максимальных конъюнкций функции F ранга г; 1 = [1о8 т - loBk h 1оВ ю -1]; Р - интервал (log т - log (log т х In л), г, ]; e(F, )= j6(F,r); в( »= Ue(M
В работе получены следующие результаты:
Разработан подход к решению задачи кластеризации с целочисленной информацией, основанный на построении а -покрытий целочисленной матрицы. Исследованы свойства алгоритмов, построенных на базе этого подхода.
Введено понятие асимптотически эффективного алгоритма поиска неприводимых покрытий булевой матрицы, которое является расширением понятия асимптотически оптимального алгоритма, введенного в работах Е.В. Дюковой. Указаны достаточные условия, при которых алгоритм построения неприводимых покрытий является асимптотически эффективным.
Разработаны эффективные в практическом плане алгоритмы построения неприводимых покрытий булевой матрицы, основаные на поиске так называемых совместимых наборов столбцов матрицы и совместимых покрытий. Приведены модификации разработанных алгоритмов на случай поиска минимальных покрытий булевой матрицы. Предложен подход к построению (тупиковых) покрытий целочисленной матрицы, основанный на построении (неприводимых) покрытий булевой матрицы.
Получены новые результаты, касающиеся изучения метрических свойств множества а -покрытий целочисленной матрицы. Для случая, т<кп , /3 < 1/2, указаны ограничения на длину а -покрытий, при которых при п —> оо почти всегда (для почти всех матриц размера тхп) почти все а -покрытия являются тупиковыми. Получена асимптотика типичного числа таких покрытий. Как следствие получена асимптотическая верхняя оценка длины минимального а -покрытия в типичном случае.
