На правах рукописи

ЧЕКИНА Александра Валерьевна

ГЕНЕТИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ ТЕХНИЧЕСКОЙ

ДОКУМЕНТАЦИИ В ПРОЕКТНЫХ РЕПОЗИТОРИЯХ САПР

05.13.12 – Системы автоматизации проектирования (промышленность)

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

Ульяновск – 2012

Работа выполнена на кафедре «Информационные системы» в Ульяновском государственном техническом университете.

Научный руководитель: доктор технических наук, профессор Ярушкина Надежда Глебовна

Официальные оппоненты: доктор технических наук, профессор Соснин Петр Иванович кандидат технических наук Черкашин Сергей Витальевич

Ведущая организация: ФГБОУ ВПО ВолгГТУ

Защита диссертации состоится « » _ 2012 г. в 12 часов на заседании диссертационного совета Д212.277.01 при Ульяновском государственном техническом университете по адресу: 432027, г. Ульяновск, ул. Северный Венец, 32 (ауд. 211, Главный корпус).

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного технического университета.

Автореферат разослан « » _ 2012 г.

Ученый секретарь диссертационного совета, доктор технических наук, профессор Смирнов В.И.

Актуальность работы Большинство крупных проектных организаций обладает значительным архивом успешных проектов. Новые проекты должны использовать ранее разработанные решения, так как повторность использования позволяет сократить сроки проектирования. Однако для решения задачи поиска проектного прототипа при хранении больших объемов информации необходима содержательная классификация проектных документов, которая позволит реализовать поиск похожих проектных документов. Следовательно, возникает задача создания проектного репозитория, автоматизирующего процессы классификации имеющихся и вновь поступающих в архив документов. Причем построение системы классов можно выполнить с помощью методов кластеризации.

В настоящее время существующие методы классификации проектных документов в архивах конструкторско-технической документации основаны на ручной процедуре присвоения кода проектному документу на основе справочника-классификатора. Поэтому существует проблема формирования автоматизированного метода кластеризации технической документации на основе лексики документа. Следовательно, для реализации поиска прототипов проектного решения в интеллектуальном проектном репозитории САПР требуется содержательная классификация проектных документов.

Решение научно-технической задачи создания проектного репозитария, автоматизирующего процессы классификации имеющихся и вновь поступающих в архив документов, в полном объеме не достижимо существующими методами и средствами.

Современный проектный репозитарий должен представлять собой интеллектуальное хранилище проектных документов, чтобы обеспечить поиск необходимого проектного решения. Единицей обработки и хранения в репозитарии является проектный документ, понимаемый как информационный ресурс. Информационный ресурс – это файл или совокупность файлов, объединенных общей семантикой и имеющих текстовую аннотацию. Основу индексирования проектных документов традиционно составляет лексический портрет текстового дескриптора информационного ресурса.

Задача кластеризации относится к классу задач оптимизации. Наиболее распространенный алгоритм кластеризации – алгоритм k-средних – является итерационным, достаточно медленным и слабо учитывает особенности пространства поиска.

Одним из методов решения задачи кластеризации могут служить генетические алгоритмы (ГА), так как стандартный генетический алгоритм сходится к глобальному оптимуму (по теореме схем Холланда). Кроме сходимости, ГА позволяет учесть особенности пространства поиска за счет настройки параметров и тем самым улучшить скорость сходимости. Поэтому целесообразно адаптировать ГА к решению задачи кластеризации проектных документов.

Существует много способов реализации идеи биологической эволюции в рамках генетических алгоритмов. Сегодня термином «генетический алгоритм» называют не одну модель, а широкий класс алгоритмов, подчас мало похожих друг на друга. Они различаются в первую очередь типами представления хромосом, операторами скрещивания (кроссинговера), мутации, различными подходами к воспроизводству и отбору. Гибкость структуры генетических алгоритмов, возможность настройки параметров позволяют получить проектные решения, отличающиеся высокой эффективностью.

Так как ГА является стохастическим, то зависимости скорости сходимости от его параметров необходимо исследовать. Результаты исследования должны позволить разработать ГА с управляемой сходимостью.

Основы современной теории кластеризации созданы трудами таких ученых, как С. Макнаотон, Гюстафсон, Кессель, Т. Кохонен, Г. Болл, Д. Холл, Дж. Мак-Кин, Г. Ланс, У. Уильямс, М. Жамбю, Г. Миллиган, М. Брюинош, Р. Дженсен, Х. Фридман, Дж. Рубин, Н.Г. Загоруйко, В.Н. Елкина и других. Основы построения интеллектуальных САПР, в том числе вопросы построения проектного репозитория проектов в САПР, рассмотрены в трудах Хилла П., Дж. Джонса, Норенкова И.П., Борисова А.Н. и др.. Значительный вклад в развитие методов генетической оптимизации в САПР внесли следующие ученые: Голберг Д., Холланд Дж., Курейчик В.М., Растригин Л.А., Курейчик В.В., Редько, Зинченко Л.А., Букатова И.Л. и др.

Цель диссертационной работы Целью диссертационной работы является разработка новых и эффективных методов и алгоритмов решения задачи кластеризации технической документации проектного репозитория САПР.

Задачи исследования Для достижения поставленной цели необходимо решить следующие задачи:

1. Выполнить сравнительный анализ существующих методов и систем кластеризации проектных документов;

2. Адаптировать схему генетической оптимизации к прикладной задаче кластеризации проектных документов как информационных ресурсов, для чего построить меру содержательного сходства проектных документов как расстояние между ними;

3. Разработать основные генетические операторы (селекция, кроссовер, мутация, формирование начальной популяции) применительно к задаче кластеризации проектных документов;

4. Разработать адаптивный алгоритм генетической кластеризации проектных документов, обеспечивающий быструю сходимость 5. Предложить методику настройки параметров генетической кластеризации, обеспечивающую быструю сходимость и высокое качество решения на основе вычислительных экспериментов;

6. Разработать и реализовать программную систему генетической кластеризации проектных документов как базовую часть интеллектуального архива проектной документации;

7. Исследовать результативность и сходимость генетической оптимизации кластеризации проектных документов с помощью вычислительных экспериментов и внедрения в практику проектной организации.

Методы исследования Для решения поставленных задач использовались следующие методы исследования: теория кластеризации, теория генетической оптимизации, методы математической статистики, методы концептуального и лексикографического анализов, метод экспертной оценки специалистов, объектно-ориентированный подход при создании комплекса программ.

Научная новизна Адаптация схемы генетического алгоритма к прикладной задаче кластеризации проектных документов на основе построенной меры лексического сходства документов.

1. Разработка модифицированных генетических операторов: селекции, мутации и кроссинговера.

2. Разработка адаптивного управляемого генетического алгоритма обеспечивающего быструю сходимость.

3. Разработка методики управления адаптивным параметризованным генетическим алгоритмом.

4. Разработка структурно-функционального решения программной системы генетической кластеризации проектных документов для проектного репозитория САПР.

Все перечисленные положения являются новыми.

Достоверность результатов диссертационной работы Достоверность научных положений, выводов и рекомендаций подтверждена результатами вычислительных экспериментов, корректным использованием формализованных методов, а также результатами использования материалов диссертации и разработанной системы в проектной организации в соответствии с актами внедрения.

Практическая значимость На основе разработанных методов и алгоритмов создан программноалгоритмический комплекс для решения задачи кластеризации информационных ресурсов. При построении программного комплекса использовался объектно-ориентированный язык Java и СУБД MS SQL Server.

Программная система генетической кластеризации прошла апробацию в ФНПЦ ОАО «НПО МАРС», МУП «Ульяновская городская электросеть», что подтверждено соответствующими актами внедрения.

Апробация результатов исследования Основные положения и результаты диссертации докладывались, и обсуждались на: «Interactive Systems and Technologies» (Ульяновск, 2007, 2009), на всероссийской конференции «Проведение научных исследований в области обработки, хранения, передачи и защиты информации ОИ-2009»

(Ульяновск, 2009), на одиннадцатой и двенадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2008 (Дубна, 2008), КИИ-2010 (Тверь, 2010), на научных сессиях МИФИ-2007, 2008 (Москва, 2008), на второй всероссийской научной конференции с международным участием «Нечеткие системы и мягкие вычисления» НСМВ-2008 (Ульяновск, 2008), на семинаре с международным участием «Интеллектуальный анализ временных рядов» по результатам НИР, поддержанной ФЦП, проект № 02.740.11.5021 (Ульяновск, 2010), на международных «Конференции по логике, информатике, науковедению»

(Ульяновск 2004 - 2007) Основные положения неоднократно докладывались и обсуждались на научно-технических конференциях УлГТУ «Вузовская наука в современных условиях».

Основания для выполнения работы Данная научная работа выполнялась в рамках тематического плана научных исследований Федерального агентства по образованию в 2005, 2006, 2007, 2008 г., была поддержана грантами РФФИ № 06-01-02012 и 06в 2006 г., № 08-01-97006 в 2008 г.; ряд задач исследования решался в рамках х/д НИР № 100/05 УлГТУ по заказу ФНПЦ ОАО НПО МАРС.

Публикация результатов работы По теме диссертации опубликовано 23 работы, в том числе 5 тезисов докладов, 18 статей.

Шесть статей опубликованы в изданиях, входящих в перечень ВАК.

Личный вклад Все результаты, составляющие содержание диссертации, получены автором самостоятельно.

Структура и объем диссертационного исследования Работа изложена на 215 страницах машинописного текста, содержит рисунков и 43 таблицы, состоит из введения, четырех глав, заключения, списка использованной литературы и 4 приложений.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационного исследования, сформулированы цели, приведены сведения о полученных научных и практических результатах, реализации и внедрении работы, апробации, дано общее описание выполненной работы.

В первой главе содержится обзор состояния исследований в области кластеризации.

В параграфе 1.1 приведены определения информационного поиска и информационного ресурса.

последовательность операций, выполняемых с целью отыскания и выдачи фактических данных, удовлетворяющих сформулированному запросу.

В настоящее время, в связи с геометрическим ростом информации, информационных ресурсов является актуальной задачей, имеющей существенную научную и практическую ценность. Для решения задач ИП электронных информационных ресурсов (ЭИР) применяют специальный класс автоматизированных систем: информационно-поисковые системы (ИПС).

Единицей обработки и хранения в репозитарии является информационный ресурс. В диссертации принято следующее определение информационного ресурса (ИР): файл или совокупность файлов, объединенных общей семантикой и имеющих текстовую аннотацию. В частном случае, информационный ресурс – это один или несколько текстовых файлов. Текст аннотации (или текст самого ресурса) однозначно отражает смысловое содержание данного ресурса. При кластеризации мы полагаемся на гипотезу о том, что смысловое содержание текста кодируется статистическим распределением слов. То есть, по частотному распределению слов, составляющих текст ресурса (или аннотации), мы можем определить его категорию.

В параграфе 1.2 приводится формализованная задача кластеризации ИР.

Поясняется структура задачи. Рассматриваются традиционно используемые в кластерном анализе меры близости между объектами.

Меру близости (сходства) объектов удобно представить как обратную величину от расстояния между объектами. Было выбрано Евклидово расстояние d(x,y) = { i (xi - yi)2 }1/2, которое является частным случаем Обобщенного степенного расстояния Минковского для р= Параграф 1.2 первой главы включает классификацию и анализ алгоритмов и методов кластеризации. В таблице 1 представлены краткие характеристики каждого вида.

Таблица 1. Обзор алгоритмов кластеризации кластеризации кластеров Иерархический Произвольная расстояния для усечения k-средних c-средних покрывающее Произвольная расстояния для удаления На данный момент существует множество методов, осуществляющих кластеризацию или классификацию документов. Некоторые методы могут использовать несколько альтернативных алгоритмов. В таблице представлена сводка основных характеристик методов.

В параграфе 1.2.4 сформулированы основные подходы к решению задачи сравнения работы автоматических классификаций, приведены характеристики оценки работы систем автоматической кластеризации ИР.

Определены некоторые основные свойства идеального алгоритма автоматической классификации.

Также в параграфе приведены методики оценки качества автоматической кластеризации, статистические формулы функционалов качества.

Во второй главе описываются методы, методики и алгоритмы решения задачи классификации ИР на основе эволюционных вычислений.

В параграфе 2.1 рассматривается индекс ИР на основе его лексического портрета, как основа входных данных для алгоритма генетической кластеризации.

Классическое описание процесса индексация представляется в виде одной или нескольких операций:

1. Отбор индексационных терминов или ключевых слов (используемых для описания содержания документа), 2. Приписывание терминам некоторого веса (отражающего предполагаемую важность термина), 3. Отнесение терминов к определенному типу («к классу действий, свойств или объектов»), 4. Определение отношений между терминами (синонимических, иерархических, ассоциативных).

Взвешивание терминов Взвешивание терминов подразумевает, что каждому дескриптору xi в документе D ставится в соответствие некоторый неотрицательный вес w..

Вес представляет собой количественную характеристику, которая, как правило, варьируется в интервале [0,1] или [0,100] (интервал выбирается в зависимости от условий анализа и для него могут задаваться другие границы).

Метод сигнал-шум Для оценки значимости слов используется методы определения частот слов каждого документа и частот, рассчитанных по формуле Шеннона (сигнал-шум):

Таблица 2. Обзор методов кластеризации текстов e Link, Average вариант Сформулированы особенности кластеризации ИР:

1. ИР представляется его лексическим портретом. В результате процесса индексации получены частоты встречаемости в ИР всех термов из составленного ранее словаря. Словарь может быть очень большим, так как чем он больше, тем наиболее полный лексический портрет ИР будет получен. Это значит, что объект кластеризации (ИР) будет иметь множество атрибутов, в качестве которых выступают частоты 2. В лексическом портрете ИР могут иметь место нулевые частотности или частотности с очень малыми числовыми значениями встречаемости терминов. Это означает, что данный термин в документе либо не встретился, либо встретился малое (по сравнению с другими терминами из словаря) число раз. Но, несмотря на малые или нулевые значения, они играют большую роль для определения индекса документа. Алгоритм должен работать и с малозначимыми терминами.

3. Проектная организация, как правило, имеет широкий спектр деятельности. Выпускается много продуктов, разработка каждого из которых сопровождается существенным объемом документации. Вся документация, в свою очередь, подразделяется на тематики, рубрики.

Как следствие, число кластеров, на которые разбивается документация очень велико.

В параграфе 2.2 приведена адаптация стандартного генетического алгоритма к решению задачи кластеризации.

Адаптация заключается в уточнении параметров стандартного генетического алгоритма для решения прикладной задачи.

В случае кластеризации ИР необходимо определить следующие параметры ГА:

1. Способ кодировки решения (хромосомы) 2. Содержание операторов отбора (селекции), рекомбинации и мутации 3. Функция оптимальности (оценки) каждой хромосомы 4. Условие завершения эволюции 5. Вероятностные параметры управления сходимостью эволюции Хромосома представляет собой массив пар (документ, кластер).

Каждая хромосома оценивается мерой ее «приспособленности»

(fitness–function). Фитнесс – функция для каждой хромосомы определяется суммой евклидовых расстояний от каждого ИР до центра соответствующего кластера, т.е.

где x – координата центра i-го кластера, xир – координата i-го информационного ресурса, m – количество информационных ресурсов, которое одновременно определяет и длину хромосомы.

n – количество координатных осей, по которым формируется общая координата информационного ресурса.

Наиболее приспособленные особи получают большую возможность участвовать в воспроизводстве потомства.

Пропорциональный отбор назначает каждой i-й хромосоме вероятность P(i), равную отношению ее приспособленности к суммарной приспособленности популяции.

В алгоритме используется равномерный многоточечный кроссовер, в результате которого все биты хромосом обмениваются с некоторой вероятностью. Значение каждого бита в хромосоме потомка определяется случайным образом из соответствующих битов родителей. Для этого