Алгоритмы с оценками для решения задач анализа данных

• Автор: Долгушев, Алексей Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Новосибирск
• Количество страниц: 82 с.

Оглавление
Введение

1 Труднорешаемые задачи кластеризации данных

1.1 Задачи поиска подмножеств и кластеризации векторов в евклидовом

пространстве

1.2 Об алгоритмической сложности задачи МЗБС

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

1.2.2 Известные факты о задаче

1.2.3 ИР-полнота задачи в случае, когда размерность пространства

является, а число кластеров не является частью входа задачи

1.3 Задача УЭ поиска подмножества «похожих» векторов

1.3.1 Постановка задачи
1.3.2 2-приближённый алгоритм
1.3.3 Апроксимационая схема
1.4 Заключение
2 Задачи помехоустойчивого оГГ-Ппе анализа и распознавания векторных последовательностей
2.1 Сущность и особенности ой'-Пне подхода к анализу и распознаванию
векторных последовательностей
2.2 Задача обнаружения повторяющегося вектора при наличии «посторонних» векторов-вставок
2.2.1 Модель анализируемых далпых
2.2.2 Редуцированная экстремальная задача
2.2.3 Базовая экстремальная задача
2.2.4 Алгоритм решения задачи
2.3 Задачи распознавания векторной последовательности, как структуры,
включающей повторяющийся вектор при наличии «посторонних» векторов-
вставок
2.3.1 Модель анализируемых данных
2.3.2 Редуцированные экстремальные задачи
2.3.3 Алгоритмы решения
2.4 Заключение
Заключение
Литература
Введение
Фундаментальной проблемой математической кибернетики и дискретной математики является анализ данных и распознавание образов. Эта проблема представляет значительный интерес как в практическом плане — в связи с прикладными проблемами обработки информации, так и в теоретическом плане — стимулируя поиск и изучение новых техник, принципов и алгоритмов во множестве предметных областей (математической статистике, исследовании операций, компьютерной геометрии и др.).
Основы анализа данных были заложены классическими работами Фишера (основы дискриминантного анализа), Колмогорова, Хинчниа (задача о разделении двух смесей распределения) и в дальнейшем развиты в теории статистических решений и активно изучавшимися с середины прошлого века задачами сопоставления нового объекта одному из заданных классов, разделения множества объектов на несколько непересекающихся классов и др. В России это направление интенсивно развивается в ВЦ РАН (Журавлев, Рудаков, Рязанов, Дюкова), ИММ Уро РАН (Еремин, Мазуров, Хачай), а также ИМ СО РАН (Кельманов, Гимади, Пяткип).
Задачи анализа и распознавания данных, как правило, связаны с содержательными проблемами, в которых требуется по результатам измерения или вычисления характеристик объектов принять решение о взаимосвязи объектов между собой и с новыми объектами.
Следующий за формулированием содержательной проблемы шаг — построение конструктивной модели анализируемых данных. Эта модель содержательной проблемы анализа данных практически всегда формулируется в форме задачи оптимизации критерия или функционала (минимума суммы квадратов уклонений, максимума правдоподобия, максимума апостериорной вероятности и др.), адекватно отражающего проблему. Многообразие критериев в комбинации с многообразием моделей (структур) анализируемых данных порождает широкий спектр редуцированных экстремальных задач, к которым сводится поиск оптимального решения. При этом сходные в содержательном плане проблемы сводятся к отличающимся экстремальным задачам. Зачастую простейшие и давно известные проблемы анализа данных сводятся к решению экстремальных задач, для которых эффективные алгоритмы с оценками точности решения неизвестны.

Глава
Задачи помехоустойчивого off-line анализа и распознавания векторных последовательностей
В данной главе рассматриваются дискретные экстремальные задачи, к которым сводятся некоторые проблемы помехоустойчивого off-line анализа и распознавания структурированных векторных последовательностей с случае аддитивной помехи. Для этих задач обосновываются эффективные алгоритмы, гарантирующие оптимальность решения. Результаты третьей главы опубликованы в работах [22-24,27-31).
2.1 Сущность и особенности off-line подхода к анализу и распознаванию векторных последовательностей
Важной проблемой анализа и классификации данных является анализ структурированных векторных последовательностей. Интерес к этой проблеме вызван тем, что векторные последовательности, имеющие заданную или неизвестную структуру, часто используются для описания результатов измерения (или вычисления) наборов характеристик совокупности изучаемых объектов, взаимосвязь между ними и изменение их свойств или состояний во времени.
Существует две важные проблемы анализа векторных последовательностей: 1) обнаружения и идентификации векторов в векторной последовательности; 2) распознавания векторных последовательностей.
Задача обнаружения и идентификации, в общем случае формулируется в следующем виде: требуется найти в последовательности векторы, соответствующие векторам из заданной совокупности, и для каждого найденного вектора установить, какому именно вектору этой совокупности он соответствует.
Задача распознавания векторных последовательностей состоит в том, чтобы определить, какому набору векторов соответствует вся последовательность, как единое целое. Множества наборов возможных векторов, как правило, имеет экспоненциальную мощность, что в большинстве случаев делает практически нереализуемым полный перебор всех вариантов. Подобные задачи могут возникать, например, при