Другие журналы
|
научное издание МГТУ им. Н.Э. БауманаНАУКА и ОБРАЗОВАНИЕИздатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408![]()
Многокритериальная оценка релевантности документов корпоративной онтологической базы знаний на основе их ролевой кластеризации
# 11, ноябрь 2013 DOI: 10.7463/1113.0637857
Файл статьи:
![]() УДК 519.6 Россия, МГТУ им. Н.Э. Баумана
Введение Корпоративная база знаний представляет собой совокупность большого числа разного рода слабоструктурированных документов, в которых с той или иной степенью подробности описаны прецеденты – некоторые ситуации и решения, которые были приняты в этих ситуациях. В системах поддержки принятия решений (СППР), которые используют такие базы знаний, поиск решения заключается в поиске в них наиболее подходящих прецедентов и соответствующих им документов [1]. Современные поисковые системы основаны, преимущественно, на применении полнотекстового поиска. При этом учитывается частота встречаемости терминов в документе, их средняя языковая частотность и так далее [2]. Альтернативой полнотекстовому поиску является поиск по метаданным, то есть поиск по атрибутам документов, содержащимся в их метаданных. Классический атрибутивный поиск основывается на использовании в качестве метаданных документа преимущественно его регистрационных атрибутов (авторы документа, название документа, дата создания, тема и т.п.) [3]. Эффективность поиска решений в базах знаний прецедентов можно повысить, основываясь не на регистрационных атрибутах документов, а на параметрах, характеризующих ситуацию принятия решения и само решение. Работа продолжает серию работ, использующих подход к поиску решений в базах знаний прецедентов, в котором метаданные формируются на основе онтологии соответствующей предметной области, заданной в виде семантической сети. Релевантность документов при этом может быть оценена с помощью значительного числа метрик, формализующих близость концептов, входящих в метаданные документа, и концептов поискового запроса [4 - 8]. О задаче поиска информации в общей постановке говорят в терминах модели поиска, которая включает в себя способ представления документов, способ представления поисковых запросов, вид критерия релевантности документов [9]. В данной работе документы в базе знаний, а также поисковые запросы представляются в виде фреймов, которые называются паттерном проектирования и паттерном запроса соответственно. Слоты этих паттернов соответствуют ролям концептов используемой онтологии (предметная область, объект, свойство, действие, задача и т.д.) [1]. Указанные роли разбивают концепты онтологии, документа и запроса к базе знаний на кластеры. Предполагается, что по методике построения семантической сети документа, построены семантические сети указанных кластеров. Таким образом, поисковые образы документа и запроса представляются в виде совокупности семантических сетей, соответствующих слотам паттерна проектирования и паттерна запроса. В пером разделе работы приводим постановку задачи многокритериальной оценки релевантности документов корпоративной онтологической базы знаний. Во втором разделе даем определения множества и фронта Парето поставленной задачи. Третий раздел содержит обзор известных классов методов многокритериальной оптимизации и обоснование выбора класса адаптивных методов многокритериальной оптимизации. В четвертом разделе представляем предлагаемый адаптивный метод многокритериальной оценки релевантности. В заключении формулируем основные результаты работы и перспективы ее развития.
1. Постановка задачи Положим, что, например, по методике, предложенной в работе [10], семантическая сеть Тем или иным способом, произведена ролевая кластеризация семантических сетей Пусть паттерн проектирования Введем следующие обозначения: Обозначим Ставим следующую дискретную задачу многокритериальной оптимизации (МКО). Среди всех документов
Поскольку речь идет о фиксированном запросе
2. Множество и фронт Парето задачи многокритериальной оценки релевантности Критерии Критериальная вектор-функция Вектор Документ Выделим из множества Множество Парето и фронт Парето занимают в теории многокритериальной оптимизации исключительное место. Это обусловлено тем обстоятельством, что согласно известному принципу Эджворта-Парето, при «разумном» поведении ЛПР выбор решения следует производить на множестве Парето. Роль множества Парето при решении задач МКО определяет также следующая теорема [11]. Теорема. Если для некоторых весовых множителей
то вектор Теорема показывает, что выбор определенной точки из множества Парето эквивалентен указанию весов каждого из частных критериев оптимальности. На этом факте основано большое число приближенных алгоритмов решения задач МКО. Заметим, что теорема задает лишь необходимое условие оптимальности по Парето вектора Постановка МКО-задачи (1) фиксирует лишь множество допустимых значений
3. Обзор методов многокритериальной оптимизации Методы решения задачи МКО чрезвычайно разнообразны. Существует несколько способов классификации этих методов. Используем в качестве основы классификацию, предложенную в работе [11], и выделим следующие классы методов решения МКО-задачи: ‑ априорные методы; ‑ апостериорные методы; ‑ адаптивные методы; ‑ методы Парето-аппроксимации. Методы каждого из указанных классов имеет свои достоинства и ни один из них не свободен от недостатков, наличие которых не позволяет признать методы этого класса универсальными. Эти же классы методов в значительной мере переплетаются друг с другом так, что не всегда МКО-метод удается однозначно отнести к тому или иному классу. Так, в настоящее время развивается класс адаптивных эволюционных методов, которые основаны на многократном построении некоторых фрагментов множества Парето. Примером алгоритмов этого класса служит алгоритм MOEA/D (MultiobjectiveEvolutionaryAlgorithmbasedonDecomposition) [12]. Общей идеей методов решения МКО-задачи является сужение множества Априорные методы предполагают формализацию дополнительной информации о предпочтениях ЛПР до начала решения задачи, то есть априори. Чаще всего эту информацию представляют в форме, позволяющей свести многокритериальную задачу к однокритериальной задаче оптимизации некоторой скалярной функции. Наиболее известным алгоритмом этого класса является алгоритм скалярной свертки. В данном случае указанную скалярную функцию образует, например, взвешенная сумма частных критериев (аддитивная скалярная свертка) вида (2), где В силу простоты, априорные методы чаще всего использует в вычислительной практике решения МКО-задач. Недостатком этих методов является то обстоятельство, что в общем случае относительная важность частных критериев оптимальности может быть определена только в процессе многократного решения задачи (1), так что, в конечном счете, методы этого класса оказываются апостериорными. Апостериорные методы предполагают внесение ЛПР в МКО-систему (программную систему, реализующую соответствующий апостериорный метод) дополнительной информации о своих предпочтениях в ходе решения задачи, то есть апостериори. При этом обычно дополнительную информацию, как и в априорных алгоритмах, формализуют в виде некоторой скалярной целевой функции. Примером апостериорного метода может служить известный метод последовательных уступок [11]. Адаптивные методы включают в себя некоторую совокупность итераций, каждая из которых содержит фазу анализа, выполняемого ЛПР, и фазу расчетов, выполняемых МКО-системой. По характеру информации, получаемой этой системой от ЛПР на фазе анализа, выделяют три класса адаптивных методов: ‑ методы, в которых ЛПР непосредственно назначает весовые коэффициенты частных критериальных функций; ‑ методы, в которых ЛПР накладывает ограничения на значения этих функций; ‑ методы, которые предполагают только оценку ЛПР альтернатив, предлагаемых ему МКО-системой. В последнем случае может производиться бальная оценка альтернатив (например, в терминах «отлично», «хорошо», «удовлетворительно» и т.д.) либо парное сравнение альтернатив между собой (например, в терминах «лучше», «хуже», «одинаково»). В конечном счете, априорные, апостериорные и адаптивные методы сводят решение МКО-задачи к однокритериальной задаче глобальной (в нашем случае, дискретной) оптимизации. Алгоритмы Парето-аппроксимации не предполагают формализации в той или иной форме дополнительной информации о предпочтениях ЛПР. Алгоритмы этого класса предполагают построение тем или иным способом аппроксимации множества и фронта Парето МКО-задачи и предъявление полученных результатов ЛПР для их неформального анализа и выбора одного из решений. В случае если полученные множества содержат большое число точек, их анализ ЛПР может быть затруднительным.
4. Адаптивный метод многокритериальной оценки релевантности Авторы предлагают модификацию адаптивного метода PREF [13] для решения задачи многокритериальной оценки релевантности документов (1). Метод предполагает бальную оценка ЛПР альтернатив, предлагаемых ему МКО-системой. Положим, что частные критерии оптимальности При каждом фиксированном векторе
В силу счетности множества Если при каждом
В результате МКО-задача (1) сводится к задаче выбора вектора
Если используется аддитивная свертка и множество достижимости Величину
Таблица 1. Допустимые значения функции предпочтений ЛПР, как лингвистической переменной
В результате МКО-задача (1) сводится к задаче отыскания вектора
Общая схема предлагаемого метода решения задачи (1) является итерационной и состоит из следующих основных этапов. Этап «разгона» метода. МКО-система некоторым образом (например, случайно) последовательно генерирует 1) решает задачу дискретной глобальной оптимизации
2) предъявляет ЛПР найденный документ 3) ЛПР оценивает эти данные и вводит в МКО-систему соответствующее значение своей функции предпочтений Первый этап. На основе всех имеющихся в МКО-системе значений 1) Строит функцию 2) Отыскивает максимум функции
3) С найденным вектором Второй этап.На основе всех имеющихся в системе значений В работе [15] для аппроксимации функции предпочтений ЛПР предложено использовать нейронные сети, аппарат нечеткой логики, а также нейро-нечеткие системы. В современной вычислительной практике эти средства широко применяют для решения плохо формализуемых задач, к которым относится задача аппроксимации функции предпочтений. Результаты исследования эффективности указанных методов аппроксимации функции предпочтений ЛПР ожидаемо показывают их близкую эффективность. В силу относительной простоты реализации и сравнительно невысокой вычислительной сложности останавливаемся на аппроксимации функции предпочтений ЛПР с помощью нейронных сетей. По сравнению с классической полиномиальной аппроксимации на основе регрессионных планов, нейросетевая аппроксимация имеет следующие преимущества: ‑ нейронные сети способны моделировать широкий класс функциональных зависимостей, при использовании же полиномов класс функций, как правило, должен быть задан; ‑ для нейронных сетей существует эффективный способ настройки их параметров.
Заключение Задача оценки релевантности документа представляет собой, по сути, задачу многокритериальной оптимизации. До настоящего времени эта задача рассматривалась как однокритериальная или как многокритериальная, но сводящаяся к многокритериальной методом аддитивной скалярной свертки. Этот метод прост в реализации, но далеко не всегда является эффективным. В частности, в общем случае этот метод не гарантирует отыскание всех паретовских точек (если фронт Парето задачи не является выпуклым). На необходимость использования иных методов решения задачи многокритериальной оценки релевантности указывалось еще в работе [10]. В работе предложен адаптивный метод многокритериальной оценки релевантности документов, основанный на ролевой кластеризации документов в корпоративной онтологической базе знаний и аппроксимации функции предпочтений ЛПР. Даже однокритериальный вариант этого метода обладает высокой вычислительной сложностью и требует использования параллельных вычислительных систем.[10]. Тем более использование этих систем необходимо при реализации многокритериального варианта метода. Одной из проблем, которая возникает при использовании рассмотренного подхода к определению релевантности документов (как в однокритериальном, так и в многокритериальном вариантах), является проблема лексической многозначности терминов. Правильное значение многозначного слова может быть установлено только путем анализа контекста, в котором это слово упоминается. Известен ряд методов решения данной задачи, например, методы, основанные на использовании Википедии [16]. В развитие работы планируется экспериментальная проверка эффективности предложенного подхода. Работа выполнена при поддержке гранта РФФИ 10-07-00222-а.
Список литературы 1. Норенков И.П. Интеллектуальные технологии на базе онтологий // Информационные технологии. 2010. № 1. С. 17-23. 2. Толчеев В.О. Методы выявления информационных признаков в задачах классификации текстовых документов // Информационные технологии. 2005. № 8. С. 14-21. 3. The Dublin Core® Metadata Initiative. Режимдоступа: http://dublincore.org/ (датаобращения 01.10.2013). 4. Карпенко А.П., Соколов Н.К. Оценка сложности семантической сети в обучающей системе // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2008. № 11. Режим доступа: http://technomag.edu.ru/doc/106658.html (дата обращения 01.10.2013). 5. Карпенко А.П., Соколов Н.К. Расширенная семантическая сеть обучающей системы и оценка ее сложности // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2008. № 12. Режим доступа: http://technomag.edu.ru/doc/111716.html (дата обращения 01.10.2013). 6. Галямова Е.В., Карпенко А.П., Соколов Н.К. Методика контроля понятийных знаний субъекта обучения в обучающей системе // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 2. Режим доступа: http://technomag.edu.ru/doc/115086.html (дата обращения 01.10.2013). 7. Карпенко А.П., Соколов Н.К. Меры сложности семантической сети в обучающей системе // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2009. № 1 (74). С. 50-66. 8. Галямова Е.В., Карпенко А.П., Соколов Н.К., Ягудаев Г.Г. Контроль понятийных знаний субъекта обучения в обучающей системе // Вестник МАДИ (ГТУ). 2009. № 2 (17). С. 82-86. 9. Когаловский М.Р. Перспективные технологии информационных систем. М.: ДМК Пресс; Компания АйТи, 2003. 288 с. 10. Карпенко А.П. Оценка релевантности документов онтологической базы знаний // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2010. № 9. Режим доступа: http://technomag.edu.ru/doc/157379.html (дата обращения 01.10.2013). 11. Лотов А.В., Поспелова И.И. Многокритериальные задачи принятия решений: учеб. пособие. М.: МАКСПресс, 2008. 197 c. 12. Zhang Q., Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition // IEEE Transactions on Evolutionary Computation. 2007. Vol. 11, no. 6. P. 712-731. DOI: 10.1109/TEVC.2007.892759 13. Карпенко А.П., Мухлисуллина Д.Т., Овчинников В.А. Нейросетевая аппроксимация функции предпочтений лица, принимающего решения, в задаче многокритериальной оптимизации // Информационные технологии. 2010. № 10. С. 2-9. 14. Мухлисуллина Д.Т., Моор Д.А., Карпенко А.П. Многокритериальная оптимизация на основе нечеткой аппроксимации функции предпочтений лица, принимающего решения // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2010. № 1. Режим доступа: http://technomag.edu.ru/doc/135375.html (дата обращения 01.10.2013). 15. Карпенко А.П., Федорук В.Г. Аппроксимация функции предпочтений лица, принимающего решения, в задаче многокритериальной оптимизации. 3. Методы на основе нейронных сетей и нечеткой логики // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2008. № 4. Режим доступа: http://technomag.edu.ru/doc/86335.html (дата обращения 01.10.2013). 16. Mihalcea R. Using Wikipedia for Automatic Word Sense Disambiguation // Proceedings of the North American Chapter of the Association for Computational Linguistics (NAACL 2007). Rochester, NY, USA, April 2007. P. 196-203. Публикации с ключевыми словами: семантическая сеть, фрейм, онтология, поддержка принятия решений Публикации со словами: семантическая сеть, фрейм, онтология, поддержка принятия решений Смотри также: Тематические рубрики: Поделиться:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
|