Восстановление отсутствующих данных в символьных последовательностях

• Автор: Рубцов, Антон Геннадьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Красноярск
• Количество страниц: 110 с. : ил.

Содержание
Введение
1. Обзор методов заполнения пропусков в данных
1.1. Статистические методы
1.2. Методы, основанные на моделировании
1.3. Коды обнаружения ошибок и корректирующие коды
1.4. Выводы
2. Постановка задачи и критерий качества заполнения
2.1. Постановка задачи
2.2. Критерий качества заполнения
2.3. Выводы
3. Кинетическая машина Кирдина, матричное представление частотного словаря и генетические алгоритмы в задаче восстановления отсутствующих данных в символьных последовательностях
3.1. Кинетическая машина Кирдина
3.2. Кинетическая машина Кирдина в задаче восстановления утерянных данных
3.3. Последовательный имитатор
3.4. Отличие КМК от случайных процессов и классических
параллельных систем вычислений
3.5. Матричное представление частотных словарей
3.6. Построение заполнений с помощью матричного представления частотного словаря
3.7. Генетические алгоритмы в задаче восстановления
отсутствующих данных
3.8. Выводы
4. Программная реализация и вычислительные эксперименты
4.1. Эксперименты
4.2. Выводы
Заключение

Введение
Актуальность темы
Подавляющее большинство методов обработки и анализа данных работают только с полными данными. На практике очень часто встречаются ситуации, когда какая-либо часть данных отсутствует. Для того чтобы иметь возможность обрабатывать такие данные, необходимо восстановить отсутствующие. Существуют различные подходы к решению этой задачи. Большинство методов позволяют получить значения пропущенных данных исходя из принципа их максимальной похожести на полные имеющиеся данные.
При проведении статистического анализа [21, 23] на практике ограничиваются анализом не всей генеральной совокупности в целом, а лишь некоторого выборочного числа наблюдений. Анализируемая выборка должна отвечать критериям качественности и полноты. Но в ситуациях, когда некоторые свойства у исследуемых объектов отсутствуют, происходит смещение основных статистических характеристик. Например, смещения математического ожидания и дисперсии возрастают прямо пропорционально числу пропусков. То есть, ошибка напрямую зависит от количества отсутствующих данных. Причинами таких пропусков могут послужить, например, отсутствие значений вследствие каких-то мелких поломок оборудования, не связанных с экспериментальным процессом, или нежелание респондента при проведении статистического опроса отвечать на вопросы о своих доходах. Знание механизма, приводящего к отсутствию значений, является ключевым при выборе методов анализа и интерпретации результатов. Неполные данные несут в себе новую информацию для исследования, важность которой может быть велика. Поэтому ее следует включать в анализ.
Практически все методы восстановления данных используют аппарат теории вероятности и математической статистики. Как правило, подобные методы восстанавливают пропущенные данные, представленные в какой-нибудь специальной форме, например, в виде таблиц. К тому же, как говорилось ранее, эти данные должны удовлетворять критериям качественно-
сти и полноты; это достаточно жесткое ограничение для практического применения. Работы, посвященные восстановлению пропущенных данных, в основной своей массе рассматривают многомерные данные [8, 16, 17, 20, 21, 23]. В этих работах данные (объекты) представляются точкой в многомерном пространстве, а параметры объекта являются координатами этой точки. При этом для восстановления пропущенных координат зачастую требуется некоторая априорная информация.
Символьные последовательности - это классические объекты математики. Они встречаются как предмет изучения во многих прикладных задачах, от теоретического программирования и теории управления до биологии и лингвистики. Изучение символьных последовательностей позволяет ответить на множество вопросов различных областей науки, связанных с чистой или прикладной математикой.
Как объект прикладного исследования, символьные последовательности встречаются во всех областях, где рассматриваются те или иные объекты, состоящие из большого числа одинаковых фрагментов. При этом схожесть или подобие могут носить искусственный характер. Исследователь вправе по своему усмотрению рассматривать некоторые фрагменты исследуемого объекта, например, нуклеотиды в молекуле нуклеиновой кислоты или символы в текстах какого-либо естественного языка, записанные в алфавитной системе записи, как тождественные друг другу, не отличающиеся ничем, кроме своего положения в рассматриваемом объекте - символьной последовательности.
Рассмотрим биологические макромолекулы, например нуклеиновые кислоты. Они играют ключевую роль во многих процессах, протекающих в живых организмах. Изучение структуры, а также функциональных, химических, физико-химических и прочих свойств нуклеиновых кислот активно ведется специалистами различных областей науки. Одним из важных направлений является изучение нуклеиновых кислот как символьных последовательностей (нуклеотидных последовательностей). Существующие в настоя-
К+ однозначно задаются правилами или командами, которые объединяются в программу. Команды могут быть только трёх видов:
а) Распад гачу—>и/ + , где, г/, гг - произвольные, у,/,£ - фикси-
рованы. Распад однозначно задается тройкой цепочек (у,/,#) Обозначим Рх множество таких троек.
При применении этой команды функция Ри изменит свои значения следующим образом:
- Рм (и™) = Рм(иую)-1;
-Рм.(цГ) = Рм(и/) +1;
- /(я) = /;;/(щу)+1.
Команда распада применима, если Рм (ит>) > 0;
б) Синтез ик + дч/тьм?, где, и,м> - произвольные, — фикси-
рованы. Синтез однозначно задается тройкой цепочек (,5,5) . Обозначим Р2 множество таких троек.
При применении этой команды функция Рм изменит свои значения следующим образом:
- Рм (ик) = Рм(ик)-1;
- Ри-(я™) = ри(<Р»)-1',
- РК .(и™) = Рм{и™) +1-
Команда синтеза применима, если Рм (ик) > 0, Рм {с}М>) > 0 ;
в) Прямая замена тлу—мтг, где, — произвольные, у,5 - фиксированы. Прямая замена однозначно задается парой цепочек (у, л). Обозначим Р3 множество таких пар.
При применении этой команды функция Рм изменит свои значения следующим образом:
- 7. (иууу) = Рм (музу) -1;
- Рм (и™) = рм(шм;) + 1-