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

Калиниченко Алла Викторовна

МЕТОДЫ И АЛГОРИТМЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ

ФУНКЦИОНИРОВАНИЯ ИНФОРМАЦИОННО-СПРАВОЧНОЙ

ПОДСИСТЕМЫ АСУП

Специальность: 05.13.06 – «Автоматизация и управление

технологическими процессами и производствами (промышленность)»

АВТОРЕФЕРАТ

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

Владикавказ – 2012 1

Работа выполнена в ФГБОУ ВПО «Северо-Кавказский горнометаллургический институт (государственный технологический университет)»

Научный руководитель: кандидат технических наук, доцент Аликов Алан Юрьевич

Официальные оппоненты: Алексеев Владимир Петрович доктор технических наук, доцент, профессор кафедры «Промышленная электроника» СКГМИ (ГТУ) Салбиев Алан Тасолтанович кандидат технических наук, начальник отдела науки и информационных технологий Министерства образования и науки РСО-Алания

Ведущая организация: ФГУП ГосНИИ Операционных систем, г. Москва

Защита диссертации состоится «22» июня 2012 г. в 1500 часов на заседании диссертационного совета Д212.246.01 при ФГБОУ ВПО «Северо-Кавказский горно-металлургический институт (государственный технологический университет)» по адресу: 362021, г. Владикавказ, ул. Николаева, 44, СКГМИ (ГТУ). Факс: (8672) 407-203. E-mail:

[email protected].

С диссертацией можно ознакомиться в научно-технической библиотеке СКГМИ (ГТУ).

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

Ученый секретарь диссертационного совета Д 212.246.01 к.т.н., доцент А. Ю. Аликов

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

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

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

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

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

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

1. провести анализ требований к современным автоматизированным системам управления предприятием;

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

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

4. разработать метод и алгоритм поиска семантически похожих документов;

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

6. оценить эффективность функционирования предложенных методов и алгоритмов в информационно-справочной подсистеме АСУП.

Объект исследования – информационно-справочные подсистемы АСУП.

Предмет исследования – методы и алгоритмы, обеспечивающие повышение пертинентности и релевантности поиска неструктурированной информации в информационно-справочной подсистеме АСУП.

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

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

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

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

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

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

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

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

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на научно-технических конференциях СКГМИ (ГТУ) 2009-2011г.; а также на следующих международных научно-практических конференциях: X Международная научнопрактическая конференция «ИТ-технологии: Развитие и приложения», г. Владикавказ, 2009г.; V Международная научно-практическая конференция «Современное состояние естественных и технических наук», г. Москва, 2011г.

Публикации. Основные результаты диссертационной работы опубликованы в 7 печатных работах, в т.ч. 2 работы в ведущих рецензируемых научных журналах и изданиях, определенных ВАК РФ для публикации основных научных результатов.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 96 наименований, и содержит 112 страниц машинописного текста, 27 рисунков, 7 таблиц и 1 приложение.

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

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

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

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

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

Во второй главе предложен подход к организации информационно-справочной подсистемы АСУП, включающей в себя диалоговую подсистему уточнения запроса, и выявлены ее особенности. Структурная схема информационно-справочной подсистемы изображена на рисунке 1. В подсистеме предварительной обработки документов/запросов осуществляются следующие операции: определение языка текста, лексический анализ, удаление стоп-слов, нормализация слов, приведение регистра. В подсистеме индексирования происходит выражение содержания документа на информационно-поисковом языке. В подсистеме анализа запроса/документа-образца осуществляется определение информационной потребности пользователя, формирование поискового образа запроса, задание ограничений поиска. Подсистема построения кластеров ассоциативно связанных поисковых терминов документа позволяет построить визуальное представление основного содержания документа в виде графа, вершинами которого являются поисковые термины, а ребра отражают их ассоциативную связь. Для решения задачи корректного отражения информационных потребностей пользователя в информационно-справочной подсистеме АСУП введен диалоговый режим взаимодействия с пользователем, особенностью которого является использование визуализации графа, отражающего взаимосвязи между терминами информационного массива. Данный подход позволит пользователю правильно подобрать набор поисковых терминов. Использование графа для представления взаимосвязей между терминами позволяет применить алгоритмы обхода графа в глубину и в ширину для выявления семантически близких терминов и уточнения запроса. Подсистема «Тезаурус» применяется для уточнения запроса. В подсистеме поиска осуществляется поиск в информационном массиве документов, удовлетворяющих запросу. В подсистеме формирования результатов поиска происходит вычисление меры релевантности документов запросу и выдача результатов.

ПОЛЬЗОВАТЕЛЬ

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

Введем обозначения:

D d1, d2,...,dn – конечное множество документов информационного массива;

n D – общее количество документов;

T t1, t2,...,tm – конечное множество терминов информационного массива;

m T – общее количество терминов;

Q –множество запросов.

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

Текст документа d j, d j D можно представить в виде последовательности элементов множества Т, обозначим ее d t1, t2,...,tr, где r – общее количество слов в документе. Очевидно, элементы в данной последовательности могут повторяться.

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

Поисковый образ документа d j представим в виде пары:

где Ad j ti, Ad (ti ), ti T, i 1,...,m, Ad (ti ) отражает степень принадлежности термина ti документу d j ;

связь терминов документа, Ld (ti, t j ) отражает частоту появления паj ры терминов ti, t j в одном контексте.

Запрос q Q также будем представлять в виде нечеткого множества, то есть Aq ti, Aq (ti ), ti T, i 1,...,m.

Функция принадлежности Ad : Т [0,1] может быть определена на основании функции взвешивания поисковых терминов, например где tfti, d j - количество появлений термина ti в документ dj.

Функцию принадлежности Ld : Т T [0,1] зададим следующим образом:

где tf(ti,t j ),d - количество появлений пары терминов ti, t j в одном контексте в документе d.

При решении задач классификации, кластеризации, поиска семантически похожих документов предложенный поисковый образ документа позволяет учесть контекст терминов. Пусть di, d j D, Ad i, Ld i, нии меры близости документов следует отдельно вычислить меру близости Ad i, Ad j и Ld i, Ld j.

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

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

На шаге 1 выполняется лексический, морфологический анализ, нормализация терминов, удаление стоп-слов.

На шаге 2 осуществляется построение списка терминов, встречающихся в документе, и вычисление частоты их появления.

На шаге 3 выделяется множество значимых поисковых терминов на основе частоты их появления в документе.

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

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

Схема алгоритма формирования кластеров ассоциативно связанных значимых терминов документа пок азана на рисунке 3.

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

Построение графа, отражающего ассоциативную связь значимых поисковых Рисунок 2 – Основные шаги метода формирования кластеров ассоциативно Как правило, трудности при формулировании запроса могут быть вызваны: неспособностью пользователя подобрать набор ключевых слов, наиболее полно отражающий его информационную потребность;

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

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

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

Получить документ D Предварительная Лексический анализ Удаление стоп-слов Инициализировать предложение Получить очередной термин в массиве Для всех элементов массива KeyTerms получить Рисунок 3 - Схема алгоритма формирования кластеров ассоциативно связанных значимых терминов документа.

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

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

Основные шаги метода поиска семантически похожих документов представлены на рисунке 4.

На шаге 1 выполняется предварительна обработка документаобразца Р: лексический, морфологический анализ, нормализация терминов, удаление стоп-слов.

На шаге 2 осуществляется построение списка терминов, встречающихся в документе, и вычисление частоты их появления.

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

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

На шаге 5 строится поисковый образ запроса на основе модели представления информации, предложенной в главе 2.

На шаге 6 выполняется процедура поиска.

На шаге 7 вычисляется релевантность поискового запроса и поисковых образов документов. Вычисляется степень сходства АP, Аd j и L, L. Если противном случае – нет.

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

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

Вычисление степени сходства поискового образа Р и «докумен- Удаление кластеров/терминов, не Рисунок 5 - Схема алгоритма поиска семантически похожих документов.

Разработан алгоритм построения поискового документа на основе математического описания представления информации в информационно-справочной подсистеме АСУП, предложенного в главе 2. Схема алгоритма изображена на рисунке 6.

Предварительная обконтекста S работка документа Рисунок 6 - Схема алгоритма построения поискового образа документа.

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

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

зультатов поиска ботки документов кластеров ски похожих доПостроение ПОД Модуль построеОбратная связь Модуль ния кластеров по- с пользоватеиндексирования исковых терминов Рисунок 7 - Основные модули разработанного программного обеспечения.

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

Таблица 1 - Характеристика тестовой коллекции.

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

точность, полнота, результаты которых отражены в таблице 2.

точность на уровне N документов (precision(N)) – отношение количества релевантных документов среди N первых выданных документов к N. Данная величина характеризует способность системы выдавать релевантные документы в начале списка результатов. На рисунке 8 показан график точности на уровне N документов для предлагаемого метода поиска семантически похожих документов и поиска по ключевым словам при N[1, 20].

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

Таблица 2 – Оценка метода поиска семантически похожих документов.

Предлагаемый метод поиска семантически похожих документов 0,8 0, Рисунок 8 - Точность на уровне N документов.

Рисунок 9 - График зависимости точности от полноты.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

6. Проведена оценка эффективности функционирования предложенных методов и алгоритмов в информационно-справочной подсистеме АСУП.

7. Разработанные методы и алгоритмы внедрены для практического применения в ОАО «Кавдоломит» (г. Владикавказ) в виде информационно-справочной подсистемы предприятия.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО РАБОТЕ

Публикации в ведущих рецензируемых научных журналах, включенных 1. Калиниченко А. В. Диалоговый метод автоматизации поиска семантически похожих документов // Системы управления и информационные технологии. №4.1(46), Воронеж, 2011. С. 191 – 193.

2. Аликов А.Ю., Калиниченко А.В. Математическая модель подсистемы информационного поиска в составе АСУП // Устойчивое развитие горных территорий. №4 (10), Владикавказ, 2011. С.32 – 34.

3. Калиниченко А. В. О методах поиска по документу-образцу в коллекции электронных документов // Материалы X Международной научно-практической конференции «ИТ-технологии: Развитие и приложения» (8-9 декабря 2009 г.). Владикавказ, 2009. С.50 – 59.

4. Калиниченко А. В. Сущность проблемы анализа текста в полнотекстовых поисковых системах. Подходы и пути решения // Журнал научных публикаций аспирантов и докторантов. №5 (47), Курск, 2010.

С. 112 – 114.

5. Калиниченко А. В. Автоматизированная система поиска слабоструктурированной информации в составе интегрированной АСУП // Материалы V Международной научно-практической конференции «Современное состояние естественных и технических наук»

(30.12.2011). – М.: Издательство «Спутник+», 2012. С. 103 – 106.

6. Аликов А.Ю., Калиниченко А.В. Применение нечеткой кластеризации для автоматизации поиска похожих документов // Материалы Международной заочной научно-практической конференции «Вопросы науки и техники». Часть I. (16 января 2012г.) – Новосибирск: Изд.

«ЭКОР-книга», 2012.– С. 80 – 84.

7. Калиниченко А. В. Оценка эффективности полнотекстового поиска в информационного фонде АСУП. // Сборник трудов XII международной конференции «Информатика: проблемы, методология, технологии», Воронеж, 2012. С. 166 – 168.

Подписано в печать 18.05.2012. Формат 60х84 1/16. Бумага офсетная. Гарнитура «Таймс». Печать на ризографе. Усл. п.л. 1,0. Тираж 100. Заказ № 117.

Северо-Кавказский горно-металлургический институт (государственный технологический университет. Издательство «Терек».

Отпечатано в отделе оперативной полиграфии СКГМИ (ГТУ).

362021, г. Владикавказ, ул. Николаева, 44.