Генетическая кластеризация технической документации в проектных репозиториях САПР

• Автор: Чекина, Александра Валерьевна
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Ульяновск
• Количество страниц: 212 с. : ил.

СОДЕРЖАНИЕ
СПИСОК СОКРАЩЕНИЙ
ВВЕДЕНИЕ
Глава 1. Сравнительный анализ методов и средств кластеризации информационных ресурсов при автоматизированном проектировании
1.1 Понятие информационного ресурса, проектного репозитария при автоматизированном проектировании. Место задачи кластеризации в автоматизированной обработке информационных ресурсов
1.2 Задача кластеризации. Структура задачи
1.2.1 Задачи классификации
1.2.2 Постановка задачи классификации электронных информационных ресурсов
1.2.3 Формализация задачи кластеризации
1.2.4 Классификация мер
1.3 Классификация и анализ алгоритмов и методов
1.3.1 Алгоритмы иерархической кластеризации
1.3.2 Алгоритмы квадратичной ошибки
1.3.3 Нечеткие алгоритмы
1.3.4 Алгоритмы, основанные на теории графов
1.3.5 Сравнение алгоритмов
1.3.5 Обзор методов кластеризации текстовых документов
1.4 Эффективность и качество автоматической классификации
1.4.1 Подходы к оценке эффективности автоматической классификации
1.4.2 Формула и методика оценки качества
1.4.3 Функционалы качества разбиений
1.5 Анализ применимости схемы генетического алгоритма к задаче кластеризаци54
1.3.1 Схема генетического алгоритма
1.5.2 Классификация генетических алгоритмов
1.5.3 Анализ применимости генетического алгоритма к решению задачи классификации
1.6 Постановка задачи исследования
Выводы по главе
Глава 2. Генетическая кластеризация информационных ресурсов интеллектуального проектного репозитория (ИПР)
2.1 Особенности лингвистического обеспечения ИПР
2.1.1 Понятие информационного ресурса (ИР)
2.1.2 Индекс информационного ресурса на основе его лексического состава
2.1.3 Особенности кластеризации информационных ресурсов
2.2 Адаптация стандартного генетического алгоритма к задаче кластеризации ИР
2.2.1 План адаптации
2.2.2 Структура хромосомы
2.2.3 Селекция
2.2.4 Кроссинговер
2.2.5 Мутация
2.2.6 Оценка приспособленности (РйпеззНипсйоп)
2.3 Алгоритм кластеризации ИР на основе схемы генетической адаптации
2.4 Разработка адаптивного генетического алгоритма
2.5 Методика настройки (параметризации) генетической кластеризации
Выводы по главе

Глава 3. Программная система генетической кластеризации информационных ресурсов
3.1. Информационная структура
3.1.1 Организация электронного архива конструкторской и программной документации
3.1.2 Структурно-функциональная схема интеллектуального хранилища
3.2 Обоснование инструмента реализации
3.3 Структуры данных
3.3.1 Структура входных данных
3.3.2 Структура выходных данных
3.2. Иерархия классов
3.3 Базовая реализация
3.4. Общая архитектура
Выводы по главе
Глава 4. Вычислительные эксперименты
4.1 Объект исследования
4.1.1 Структура архива ФНПЦ НПО ОАО «МАРС»
4.1.2 Виды конструкторской, программной, технической документации
4.1.4 Математическая модель оценки качества кластеризации
4.2 Эксперименты по оценке качества кластеризации
4.2.1 План проведения экспериментов
4.2.2 Результаты экспериментов. Этап№1
4.2.3 Результаты экспериментов. Этап №2
4.2.4 Результаты экспериментов. Этап №3
4.3 Эксперименты по исследованию эффективности предложенного адаптивного генетического алгоритма
4.3.1 Исходное множество документов
4.3.2 Структура экспериментов
4.3.3 Результаты вычислительного эксперимента
4.3.4 Оценка результатов вычислительного эксперимента
Выводы по главе
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ №1. Свидетельство о государственной регистрации программы
для ЭВМ
ПРИЛОЖЕНИЕ №2. Акт внедрения
ПРИЛОЖЕНИЕ №3. Акт внедрения
ПРИЛОЖЕНИЕ №4. Результаты вычислительных экспериментов
П4.1 Эксперименты по оценке качества кластеризации адаптивного генетического
алгоритма. Режим «Управление сходимостью через мутацию»
П4.2 Эксперименты по оценке качества кластеризации адаптивного генетического алгоритма. Режим «Управление сходимостью через плодовитость»
СПИСОК СОКРАЩЕНИЙ
ГА - генетический алгоритм;
МГА - мобильный генетический алгоритм;
ГП - генетическое программирование;
ЭС - эволюционная стратегия;
ИП - информационный поиск;
ИПС - информационно-поисковая система;
ИР - информационный ресурс;
ИСА - интеллектуальный сетевой архив;
ИТ - информационные технологии;
ПД - проектный документ;
ПО - предметная область;
САПР - система автоматизированного проектирования; СУБД - система управления базами данных;
БД - база данных;
ЭД - электронный документ;
ЭИР - электронный информационный ресурс.

Достоинства метода [Кириченко и др., 2006]:
• использует информацию матрицы tf*idf.;
• метод не нуждается в предварительной настройке на специфический набор документов, его не надо обучать;
• лучший метод для выявления латентных зависимостей.
Среди недостатков [Кириченко и др., 2006]:
• огромное количество вычислений может приводить к тому, что на результатах запросов, содержащих сотни тысяч объектов система будет работать очень долго. Как утверждают авторы в [Susan Т. Dumains], скорость вычисления SVD соответствует порядку N2 х к, где N=N(JocS+Nlf,rms, к - размерность пространства факторов;
• отсутствие подходящего названия для полученных факторов. В [L.A Soshnikova, V.N. и др., 1999] описывается один из алгоритмов поиска подходящих названий, но это требует дополнительных вычислительных затрат;
• кластеры не пересекаются;
Suffix Tree Clustering
Изначально суффиксные деревья - suffix tees - были разработаны и применялись для быстрого поиска подстрок. Суффиксное дерево - дерево, содержащее все суффиксы данной строки. Оно состоит из вершин, ветвей и дополнительных указателей, называемых suffix pointers, с помощью которых добиваются линейной скорости построения дерева [Esko Ukkonen]. Ветви дерева обозначаются буквами или буквосочетаниями, которые являются частями суффиксов строки. Суффикс, соответствующий определённой вершине, можно получить путем объединения всех букв, которые находятся на ребрах дерева, начиная от корневой вершины и заканчивая данной.
В [Esko Ukkonen] описан алгоритм построения такого дерева для
строки символов за время 0(п), причем количество используемой памяти
также растёт линейно с ростом длины строки. В диссертации [Oren Eli Zamir]