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

СЛЮСАРЬ Валентин Викторович

РАЗРАБОТКА МОДЕЛЕЙ И АЛГОРИТМОВ

АВТОМАТИЗАЦИИ ПОЛНОТЕКСТОВОГО ПОИСКА

ДОКУМЕНТИРОВАННОЙ ИНФОРМАЦИИ ПОВЫШЕННОЙ

РЕЛЕВАНТНОСТИ В РАСПРЕДЕЛЕННЫХ

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

Специальность: 05.13.06 — Автоматизация и управление технологическими процессами и производствами в приборо- и машиностроении

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва, 2007 2

Работа выполнена в Московском государственном институте электронной техники (техническом университете)

Научный руководитель Д. т. н., профессор Л. Г. Гагарина Официальные Д.т.н., профессор оппоненты Н. Н. Герасименко К.т.н., доцент С. А. Каратыгин

Ведущая организация ОАО “Институт электронных управляющих машин”, г. Москва

Защита состоится «»2007 года в _: на заседании диссертационного совета _ при Московском государственном институте электронной техники (техническом университете) по адресу:

124498, Москва, Зеленоград, проезд 4806, МИЭТ

С диссертацией можно ознакомиться в библиотеке МИЭТ.

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

Ученый секретарь Д.т.н., профессор Диссертационного совета А. И. Погалов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

4. Создание экспертной модели поиска документированной 5. Разработка комплексного алгоритма нахождения релевантной полнотекстового поиска документированной информации в распределенных производственных структурах на основе предложенных моделей и алгоритмов.

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

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

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

2. Разработано формализованное представление полнотекстового документа в терминологии семантических сетей.

3. Разработана математическая модель полнотекстового запроса на основе теории графов, коррелирующая с моделью поискового образа документа (ПОД).

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

5. Создана концептуальная модель функционирования САП ДИ как составляющая автоматизированной системы управления производством, на базе разработанных математических моделей 6. Создана и верифицирована имитационная модель поиска релевантной документации в информационном пространстве электронного хранилища документов обеспечивающая традиционными методами поиска документированной информации и ее верификация.

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

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

Достоверность полученных результатов подтверждается результатами имитационного моделирования, доказавшими преимущества предложенных в работе методов и алгоритмов полнотекстового поиска документированной информации, выразившиеся в повышении релевантности находимых документов, а также успешным внедрением и эксплуатацией моделей и алгоритмов на предприятии «ООО ДУЭТ Ко».

Личный вклад автора. Все основные результаты получены автором лично. Главными из них являются:

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

формализация представления полнотекстового документа в терминологии семантических сетей;

разработка на основе теории графов математической модели полнотекстового запроса, коррелирующей с математической алгоритмическая реализация построения расширенного поискового образа документа, базирующегося на простом ПОД;

выведение комплексного алгоритма нахождения релевантной информации на основе обратной связи с пользователем;

создание концептуальной модели функционирования САП ДИ как составляющей автоматизированной системы управления производством на базе разработанных математических моделей и алгоритмов;

полнотекстового поиска документированной информации в распределенных производственных структурах;

внедрение разработанных моделей, алгоритмов и программной реализации модели поиска документированной информации в технологический процесс ООО “Дуэт Ко”;

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

Реализация полученных результатов.

Все работы по реализации и внедрению проводились под руководством или при непосредственном участии автора. Результаты диссертационной работы используются в технологическом процессе фирмы “Дуэт Ко” в рамках опытной эксплуатации автоматизированной системы поиска архивной документации (благодаря использованию разработанных моделей и алгоритмов затраты рабочего времени специалистов на поиск документации снизились более чем в два раза, и на 25% уменьшилось количество нерелевантных документов, ошибочно получаемых пользователями)., а также в учебном процессе кафедры ИПОВС Московского Государственного института электронной техники при чтении дисциплин “Автоматизированные информационные системы”, “Проектирование информационных систем”, “Имитационное моделирование”.

На защиту выносятся следующие основные научные результаты:

1. Формализованное представление полнотекстового документа в терминологии семантических сетей.

2. Математическая модель полнотекстового запроса на основе теории графов, коррелирующая с моделью ПОД.

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

4. Комплексный алгоритм нахождения релевантной информации на основе обратной связи с пользователем.

5. Концептуальная модель функционирования САП ДИ как составляющая автоматизированной системы управления производством, на базе разработанных математических моделей 6. Имитационная модель поиска релевантной документации в информационном пространстве электронного хранилища документов обеспечивающая увеличение эффективности поиска документированной информации.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях.

1. V Всероссийская международная конференция «Антикризисное управление в России в современных условиях», МГТУ им.

2. 11 Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информтика-2004», МИЭТ, 2004.

«Антикризисное управление в России в современных условиях», МГТУ им. Баумана, 2004.

4. Двенадцатая Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информтика-2005», МИЭТ, 2005.

5. V Международная научно-техническая конференция “Электроника и информатика - 2005”, МИЭТ, 2005.

6. Тринадцатая Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информтика-2006», МИЭТ, 2006.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из наименований и приложения, содержит 180 страниц текста, включая 117 страниц основного текста, 27 рисунков, 3 таблицы, 10 страниц списка используемой литературы из 119 наименований и 26 страниц приложений.

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

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

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

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

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

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

сложность сочетания простого и расширенного поисковых запросов в рамках одного обращения пользователя;

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

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

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

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

преобразование потоков сообщений – информационный поиск, отбор из поискового массива множества сообщений, подчиняющихся определенным формальным сообщениям;

преобразование сообщений или документов – составление поисковых образов индексов (индексирование) документов.

Принимая во внимание требования, предъявляемые к эффективности поиска информации, в работе предложена обобщенная схема САП ДИ, представленная на рис. 1. Для автоматической индексации документов в структуре САП ДИ выделен контур документов и контур запросов. Контур документов включает процессы получения множества документов L0 и преобразования каждого документа.

документ представляется в виде вектор-столбца:

Любую систему, в частности САП ДИ, можно рассматривать как конечную совокупность некоторого множества элементов Е = {ej} и управляющего механизма M, устанавливающего связи между элементами системы и управляющего ими, образуя единую функционирующую систему.

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

Аналогично связи системы подразделяются на информационные Рис. 1. Обобщенная структура подсистемы поиска (для передачи преобразуемой информации) и управляющие. Поскольку каждая система формируется в определенной среде, то говорят, что система формируется множеством внутренних состояний (ресурсов) Z={Zk}. Использование множества этих ресурсов, т.е. переход из одного внутреннего состояния в другое, происходит под воздействием определенной стратегии (плана). Таким планом (стратегией) является функция перехода Н из одного внутреннего состояния системы в другое:

Предложенная структура характеризуется наличием множества входных значений Х={Xi}, операторов входа K={Ki}, выходных значений Y={yj} и выходных операторов Q={Qj} (также называемых воздействиями).

Функционирование системы определим как распределенное во времени Т преобразование информации из входного значения Х в выходное значение Y:

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

Характеристика саморегулирующейся системы выражается через параметр F. Таким образом, систему можно представить как упорядоченную совокупность элементов вида Функционирование САП ДИ, как и любой системы, основано на математической модели, включающей в себя представление поискового образа документа, представление запроса пользователя и метод вычисления релевантности поискового образа запросу пользователя.

С целью унификации процедуры анализа документов различных форматов построена модель полнотекстового документа в терминах семантических сетей. При разработке моделей используются не символы, составляющие содержание текстовых блоков, а более высокоуровневые объекты — термы. Предложенная модель позволяет представить текст документа в виде сети взаимосвязанных фреймов, взаимодействующих с помощью горизонтальных и вертикальных связей. Горизонтальные связи соединяют элементы на одном уровне в иерархии документа. Это, как правило, фреймы одного и того же типа.

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

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

Полученная модель шаблона имеет вид:

где Fr - фрейм шаблон, Id - уникальный идентификатор фрейма, lF вертикальный уровень фрейма, Trm - текстовое содержимое фрейма (список термов), Fnext - указатель на фрейм того же уровня или пустой указатель, Fup - указатель на фрейм более низкого уровня или пустой указатель. Attr — указатель на дополнительные атрибуты или 0 в случае их отсутствия.

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

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

Разработаны модели полнотекстового запроса и поиска документа в распределенной производственной структуре. Документ хранится в базе данных САП ДИ в виде своего образа, заменяющего текст документа при выполнении операции вычисления релевантности.

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

где Xd - нечеткое множество вершин, – носитель нечеткого множества Хd:

Элементы множества Хd соответствуют термам, содержащимся в документе. Функция Xd(x)принадлежности определяет степень принадлежности терма документу (его вес при описании документа списком термов).

принадлежности Ud ( x, y ) определяет степень связанности термов х и у в пределах документа и зависит от частоты совместной встречаемости термов в документе, близости их положения в тексте Поисковый запрос определяется как где Xr – нечеткое множество термов запроса, xXr, Gr – нечеткое неориентированное отношение ассоциативной связанности термов запроса, определяемое через желаемую связность термов x и у в искомом документе, представляющую из себя число от 0 до 1, Ur – нечеткое множество, описывающее связность термов запроса аналогично множеству Ud. Для вычисления релевантности запроса и, на основании отношений Ur и Fr, строится объединенное отношение U’r.

В простейшем случае, оно может быть построено путем объединения этих отношений с использованием операции максимума:

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

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

Алгоритм создания ПОД (рис.2), соответствующего модели, построенной во второй главе, разбивается на две независимые части:

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

Исходными данными алгоритма являются количество документов;

модель документа в виде сети фреймов, содержащая иерархическое описание текста; количество термов в документе; номер документа;

количество термов в базе данных. Выходные данные: количество термов в поисковом образе документа; документ, представленный в виде списка термов; степени принадлежности термов документу;

модифицированные частоты встречаемости термов в документах.

Все термы используются Сортировка списк Установка макси мальных nj значе Выбор i-го терма,