интересно
Предыдущая | Содержание | Следующая

Модификация метода нечётких концептов для повышения эффективности информационного поиска

Введение

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

При решении задачи каталогизации на первое место выходит проблема описания (представления) документа. Обычно задача формального представления документа решается в два этапа [1]. Первая задача решается на основе булевой модели или так называемой частотной [2]. В любом случае на этом этапе происходит выделение большого числа ключевых слов, что весьма затрудняет обработку данных. На втором этапе тысячи слов, отобранных на первом этапе, подвергаются дополнительному анализу и сокращению. Так, например, удаляются различные служебные слова, связки и т.д., которые имеют высокую степень включённости в любой текст или документ. После исключения этих слов составляется словарь и (или) тезаурус, который будет использоваться для дальнейшей обработки.

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

Формальное описание документа с помощью нечётких концептов

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

В данной работе предлагается развитие концепции нечёткой каталогизации, предложенной в работе [4]. Допустим, база данных состоит из п документов:

Предлагаемая концепция состоит из трёх этапов.

Определение базовых концептов.

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

задаётся

следующим образом:

— функция принадлежности терма к. к концепту t.. Степень принад-

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

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

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

- функция

. Функция агрегирования может быть выбрана на

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

Таким образом, каждый документ может быть представлен на основе множества концептов в следующем виде:

Построение нечёткого тезауруса запросов.

Запрос пользователя также может быть представлен в виде, аналогичном (1). Это достигается построением нечёткого тезауруса, в котором устанавливаются соответствия между термами концептами запроса. Метод построения нечёткого тезауруса подробно рассмотрен в работе [6], в соответствии с этим методом по базе данных документов строится такой тезаурус. Причём при построении тезауруса используются те же концепты, что и для представления (1). В результате соотнесения запроса тезаурусу возможно представление запроса также в виде множества концептов:

Оценка релевантности запроса

Классификация документов в БД может осуществляться теми методами, которые, например, предлагаются в работах [6]. Здесь необходимо отметить, что классификация документа и отработка запроса к каталогизированной базе данных не может иметь однозначную оценку, в связи с этим предполагается, что множество документов, возвращённых по запросу, имеет нечёткий коэффициент релевантности.

Будем считать, что в результате выполненного запроса имеется множество предъявленных к анализу документов R, и пусть С - множество документов, имеющих отношение к запросу.

Тогда множество документов С определяется следующим образом:

- коэффициент релевантности документа запросу, а обобщённый коэффициент релевантности документа вычисляется следующим образом:

Классификация результата запроса по группам релевантности

  . Используя эти параметры, можно задать множество

С следующим образом:

является частью множества С и формирует некоторое количество групп релевантности результата.

то энтропия как критерий определяется следующим образом:

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

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

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

Треугольная:

- среднеквадратичное отклонение.

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

как нечёткое число, задаваемое соответствующей функцией

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

определяем по Заде с функцией принадлежности:

равно 2 (рис. 1), на интервале

  - 3 и т.д. Таким образом, мы можем определить не только интервалы, но

и отсортировать их. Интервал, на котором величина I принимает максимальное значение, является интервалом с максимальным уровнем релевантности.

Для проверки верности данного подхода проведём оценку функции плотности распределения коэффициента релевантности на интервалах, полученных ранее. Сделаем допущение о том, что мы имеем достаточный объём выборки. В качестве метода оценивания функции плотности распределения воспользуемся методом операторных оценок [8], который обеспечивает несмещённость и состоятельность оценки. В этом методе используется операторная аппроксимация. Действительно, функция распределения F(x) связана с плотностью вероятностей известным соотношением:

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

, при этом действия приводят к другому вполне определённому аналитическому выражению. Более подробно теоретическое обоснование этого метода можно найти в [8]. Плотность распределения оценок степени релевантности запроса wR(a) оценивается в два этапа. На первом из них по обучающей выборке

строится эмпирическая функция FR(а). На втором этапе производится выбор постоянных в формулах операторной аппроксимации; по имеющимся значениям FR (a)

поочерёдно вычисляются все значения плотности wR (а) в выбранных интервалах

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

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

Определение эмпирической функции распределения:

- упорядоченные по возрастанию элементы обучающей

выборки.

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

При отработке запроса к базе данных количество результативных документов колебалось от нескольких документов до нескольких десятков. Для уверенной работы метода операторных оценок требуется выборка более 35-40 значений [8]. Была проведена серия экспериментов с объёмом выборки от 20 элементов. Порядок следования групп релевантности совпадает в большинстве случаев, при увеличении выборки > 100 элементов результаты практически идентичны. Дальнейшие исследования направлены на выявление наиболее эффективных видов функции принадлежности для работы с малым числом элементов выборки.