Слюсарь В.В., аспирант, старший преподаватель Московского государственного института электронной техники
ФОРМАЛИЗАЦИЯ ЗАДАЧИ ПОИСКА ДОКУМЕНТИРОВАННОЙ ИНФОРМАЦИИ
Любую систему можно представить в виде конечной совокупности некоторого множества элементов Е = (еЛ и управляющего механизма М, устанавливающего связи между элементами системы и управляющего ими, образуя единую функционирующую систему.
Множество элементов системы можно разделить на информационные и управляющие элементы, отличающиеся набором выполняемых функций: Информационные элементы выполняют исключительно функции преобразования информации и не влияют непосредственно на другие элементы системы. Управляющие элементы воздействуют на информационные, но не подверженные влиянию других элементов.
Система характеризуется наличием множества входных значений М=(ш;}, операторов входа Б=(Б;}, выходных значений К=(и|} и выходных операторов у=(т]} (также называемых воздействиями).
Т :{Т ^ М;Т ^ Щ 0)
Функционирование системы можно определить как распределенное во времени Т преобразование информации из входного значения М в выходное значение К:
Преобразование информации в каждой системе реализуется через заданный алгоритм, который для системы называется функцией выхода Б:
На систему, т.е. ее алгоритм Б, могут воздействовать некоторые управляющие воздействия С. Характеристика саморегулирующейся системы выражается через параметр К
Таким образом систему можно представить как упорядоченную совокупность элементов
Р :{М ^ Ж} (2)
вида
£ =< Т, Е, М, у, Ж, Н, Я > (3)
Математическая модель поисковой системы включает в себя представление поискового образа документа, представление запроса пользователя и метод вычисления релевантности поискового образа запросу пользователя.
Поисковый образ документа представляется в виде неориентированного нечеткого графа второго рода:
где Ха. - нечеткое множество вершин, - носитель нечеткого множества Хё.
Элементы множества Хё соответствуют термам, содержащимся в документе. Функция
Ой = (X й , Z й )
(4)
Дха(^)принадлежности определяет степень принадлежности терма документу (его вес при описании документа списком термов).
Хй = (<^х(х)/ х >},х е Хй (5)
Нечеткое множество = {<мщ (х У)/(х у) >} х у е ха описывает множество ребер, соответствующих отношению «ассоциативной связности» термов документа. Функция принадлежности Иг„ (x, У) определяет степень связанности термов х и у в пределах документа и зависит от частоты совместной встречаемости термов в документе, близости их положения в тексте. Все степени принадлежности являются вещественными величинами со значениями, лежащими в диапазоне от 0 до 1.
Следующей задачей является представление поискового запроса. Запрос является формализованной информационной потребностью пользователя.
Запрос Я определяется как
Я = (Хг, вг ,иг, ¥г) (6)
Где:
Хг - нечеткое множество термов запроса;
Хг = {< ПХг (х)/ X >} (7)
хеХг,
и X г ( X ) определяет вес терма в запросе (степень его важности для результатов поиска);
вг нечеткое неориентированное отношение ассоциативной связанности термов запроса, заданное на множестве Хг ;
вг = {< Мв (х, У) /(х, У) >}, х, У е Хг (8)
иг = {< Миг (х, У) /(х, У) >}, х, У е Хг (9)
иг - нечеткое неориентированное отношение термов запроса и предметной области: М ог - желаемое значение связности термов х и у в искомом документе. Бг - нечеткое ориентированное отношение термов запроса и термов языка.
¥г = {< Мег (х, У) /(х, у) >}, х, у е Хг * Т (10)
Пояснение: М ^ - степень принадлежности термов данному отношению. Для алгоритма вычисления релевантности запроса и, на основании отношений иг и Бг, строится объединенное отношение и г. В простейшем случае, оно может быть построено путем объединения этих отношений с использованием операции максимума:
Миг (х t) = тах(Миг (х I X М Рг (х ^)) (11)
В этом случае, запрос может быть записан в следующем виде:
Я = (Хг,вг,и Г) (12)
Пусть МегшБ - количество термов предметной области, а Кг - число термов в запросе (мощность множества Хг). Тогда аналогично модели ПОД, модель запроса может быть представлена в виде совокупности матриц:
XI = 0, если 1-й терм не присутствует в запросе и весу терма в противном случае.
При поиске информации САП ДИ опирается на некоторую модель знаний, заложенную при ее построении или полученную в процессе функционирования. Для обеспечения возможности использования априорно заданных и более точных, по сравнению с получаемыми в процессе функционирования, знаний экспертов о предметной области, необходимо определить форму представления таких знаний, не выходящую за рамки используемого в САП ДИ математического аппарата. В рамках данной работы, для описания семантических сетей (а именно они чаще всего используются для описания знаний экспертов) используются нечеткие графы второго рода. Ввиду того, что знания экспертов могут описываться несколькими отношениями, в качестве модели знаний экспертов используется неоднородная семантическая сеть, заданная на множестве термов предметной области.
Неоднородная семантическая сеть - это ориентированный граф, вершины которого связаны отношениями нескольких типов. Предлагаемая модель содержит два типа отношений: неориентированное синонимическое и ориентированное гипонимическое (общее-частное). Данные типы отношений наиболее часто используются при построении различных систем анализа текстовых документов, входя в состав большинства составленных тезаурусов и частично пересекаются с уже составленными для многих областей знаний каталогами и рубрикаторами (гипонимическое отношение является в некотором роде рубрикатором предметной области). БЗ экспертов описывается как:
Где Хе - множество вершин;
Цб - множество неориентированных дуг, отражающих синонимические связи между терминами;
Цс - множество ориентированных дуг, отражающих связи типа «общее-частное» между термами.
Первое отношение позволяет выделять на семантическом поле предметной области синонимические группы, которые в последствии могут быть использованы для повышения релевантности ответа.
Второе отношение, описывающее гипонимические связи, содержит иерархию тем и терминов предметной области, и также может быть использовано для расширения запроса, для учета контекста и для повышения релевантности при ранжировании найденных документов.
БЗ экспертов и БД документов используется на этапе формирования расширенного запроса. Так как формирование запроса - процедура интерактивная, после ввода пользователем запроса, следует операция выбора множества тех термов, которые связаны с указанными в запросе термами.
Полученное множество синонимов может использоваться для расширения запроса путем предъявления пользователю в качестве предполагаемого варианта расширения.
1. Гагарина Л.Г., Слюсарь В.В. Методология оценки эффективности работы автоматизированной информационно-поисковой системы на основе интегральных критериев уровня ка-
(13)
(14)
СПИСОК ЛИТЕРАТУРЫ
чества поиска. Научно-технический журнал «Известия высших учебных заведений. Электроника» № 2, 2006. - М., МИЭТ, 2006.
2. Гагарина Л.Г., Слюсарь В.В. Критерии оценки эффективности работы автоматизированных информационно-поисковых систем. // тезисы докладов Х11-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика-2005». - М.: МИЭТ, 2005.
3. Прохоров Н.Л., ред. Управляющие вычислительные комплексы: учебное пособие. - М., Финансы и статистика, 2003.
4. Гасанов Э.Э., Кудрявцев В.Б. Теория Хранения и поиска информации. - М., Физмат-лит, 2002.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.