Покрытие целочисленной матрицы и задача кластерного анализа

• Автор: Инякин, Андрей Сергеевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 122 с. : ил.

ВВЕДЕНИЕ.

ГЛАВА 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 тупиковое 0,. В этом случае сг подматрица является единичной подматрицей. Покрытие минимальной длины называется минимальным покрытиям. Обозначим через С, сг, , сг и , сг соответственно множество сгпокрытий матрицы , множество тупиковых сгпокрытий матрицы и множество сгподматриц матрицы . Приведем геометрическую интерпретацию понятия сгпокрытия целочисленной матрицы , . Множество является значным п мерным кубом. Обозначим через множество точек куба , задаваемых строками матрицы . Положим Е М. Набору столбцов Н с номерами у ,. Гвсех точек а а,,. Е таких, что , 1, г. Е и целиком принадлежит Лд. В случае г н, множество точек Еа,1 является 0мерным подкубом, состоящим из одной точки сг. Таким образом, множеству С взаимнооднозначно соответствует множество всех нодкубов, содержащихся в . Отмстим, что Еи является подкубом Ега г тогда и только тогда, когда сг2 7, II2. Пусть Е некоторое подмножество . Будем говорить, что подкуб Е а. Е является максимальным в Е, если не существует другого подкуба Е с Е такого, что с. Множество всех максимальных подкубов в будем обозначать 6тах. Нетрудно видеть, что множеству взаимнооднозначно соответствует множество 6тахЛд. Таким образом, задача построения множества может быть сформулирована как задача построения множества всех максимальных подкубов в Лд. Задачи построения покрытий целочисленной матрицы могут быть также сформулированы как задачи построения дизъюнктивной нормальной формы ДНФ двузначной логической функции специального вида, заданной на Аичных п мерных наборах ,, , . Множество всех таких функций обозначим через . Определение. Элементарной конъюнкцией э. Число г называется рангом э. Интервал истинности э. Определение. Э.к. Р, если Му ВГ 0. Определение. Э.к. Р, если допустимая конъюнкция для Р и не существует допустимой для Р конъюнкции такой, что Му и Му. Определение. Сокращенной ДНФ функции Р называется ДНФ, состоящая из всех максимальных конъюнкций функции Р. Пусть Вг состоит из наборов вида . Рт Рт2 Ртп. Справедливы приведенные ниже утверждения 5. Утверждение 5. Э.к. Т,. Утверждение 5. Э.к. Из утверждений 5. ДНФ двузначной логической функции, алгоритмы поиска тупиковых покрытий целочисленной матрицы могут быть применены при построении сокращенной ДНФ двузначной логической функции и наоборот. Традиционно вопросы построения эффективных реализаций логических процедур распознавания связаны с изучением метрических количественных свойств множества покрытий и построением эффективных алгоритмов поиска покрытий булевых и целочисленных матриц. В частности, такая информация как типичная длина тупикового покрытия, типичное число тупиковых покрытий важна для получения оценок вычислительной сложности алгоритмов поиска тупиковых покрытий, и позволяет оценить требуемые вычислительные ресурсы, лучше организовать память компьютера и тем самым понизить необходимые требования к вычислительной технике при реализации распознающих процедур. Н.В. Носкова, В. Л. Слепян, Е. В. Дюковой и А. Е. Андреева 1 3, , , , при изучении метрических свойств множеств тупиковых и минимальных тестов. Д1Д2, при условиях псо и та пктР, а 1, р 1. Аналогичные оценки получены для числа подматриц из и порядка подматрицы из 5. Показано, что в данном случае число покрытий из ВЬ почти всегда асимптотически совпадает с числом всех подматриц из и по порядку меньше числа покрытий из СЬ. В был рассмотрен прямо противоположный случай, а именно,
когда п тк , а 1, р 1. Получены асимптотики типичных значении числа подматриц из 5 и порядка подматрицы из . Р , почти всегда число подматриц из по порядку больше числа покрытий из ВЬ. Ь размера тхп отсутствуют покрытия длины г.