Диалоговый метод автоматизации поиска семантически похожих документов

УДК 004

ДИАЛОГОВЫЙ МЕТОД АВТОМАТИЗАЦИИ ПОИСКА СЕМАНТИЧЕСКИ ПОХОЖИХ

ДОКУМЕНТОВ

А.В. Калиниченко

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

Ключевые слова: информационный поиск, поиск похожих документов, пертинентность

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

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

Модифицированной формой представления информационных интересов пользователя является поиск похожих документов (similar document search). Целью поиска является обнаружение документов, тематически близких документу-образцу. Под тематической близостью понимается близость по содержанию, смыслу. [2]

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

Калиниченко Алла Викторовна - СКГМИ (ГТУ), соискатель, e-mail: kalinichenkoalla@mail.ru

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

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

ОПИСАНИЕ МЕТОДА

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

D = d ,...,d^} - множество документов в текстовой коллекции.

N = DI - общее количество документов.

T = {t1,...fm} - множество терминов в коллекции документов. Термин t может быть одним словом или фразой, состоящей из нескольких слов, например, «автоматизированная система».

M = IT - общее количество терминов.

Документ d можно представить в виде последовательности элементов множества Т, обозначим ее d = j/i,...,ir j , где r - общее количество слов в документе. Очевидно, элементы в данной последовательности могут повторяться.

S ^ d, t i, radius j = jt j : |i — j\ < radius, t j e d j -

множество слов, находящихся в заданном окне от слова t i , то есть его контекст.

K = {kj,...km} , где kt = S^d, ti, radius^ -множество контекстов терминов, k содержит

контекст ti .

Тогда документ dt, dt e D может быть представлен множеством W = {w1,...,wm}, где w j

- вес термина t в документе d , а коллекция текстовых документов - в виде матрицы:

( Di D2 . . Dn '

t1 wii w12 . Wi tv1n

12 w21 2 2 £ n 2 w

vt m Wm1 Wm2 . .. w mn J

(W, К) - расширенный поисковый образ документа.

Для присваивания веса терминам используем меру tf _ idf . Схема взвешивания tf _ idf присваивает каждому термину t его вес в документе d на основе формулы:

tf _ idft,d = tft,d х idft, где

tftd - количество вхождений термина t в документ d;

N

idf = log— - обратная документная частота

dft (inverse document frequency) термина t;

dft - документная частота (document frequency), определяемая как количество документов в коллекции, содержащих термин t.

Вес tf _ idf термина t обладает следующими свойствами:

- Он достигает максимального значения, если термин встречается много раз в небольшом количестве документов (тем самым усиливая их отличие от других документов).

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

- Он достигает минимального значения, если термин встречается практически во всех документах [4].

Dv = {dv1,...ftv1} - множество документов, выданных поисковой системой в ответ на запрос - поисковая выдача.

P - документ-образец.

Ra ={n(P, d, X а) - критерий смыслового соответствия [3], где /U(P, d) - функция вычисления меры релевантности, а - пороговое значение релевантности, такое что

IX при u(P, dj) > а, документ выдается а [О, при u(p, dj) < а, документ не выдается

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

1. Ввод документа-образца P.

2. Предварительная обработка документа

образца Р: лексический, морфологический

анализ, нормализация терминов, удаление стоп-

слов, выявление значимых двухсловных терминов.

3. На основе частоты появления слов и

значимых двухсловных терминов

(словосочетаний) в документе и их дискриминационной силы формируется множество W для документа-образца Р.

4. Для каждого ключевого термина ti, i = I, M формируется контекст К Получим расширенный поисковый образ документа образца ^, К).

5. Выполняется контекстная кластеризация ключевых терминов. В один кластер попадают термины с наиболее схожими контекстами. Пусть С = ^сI,fiq } - множество кластеров, ^ -

подмножество Т, принадлежащее ^тому кластеру. Для наглядности кластеры изображаем графически.

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

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

8. Для формирования более точного запроса Ъ пользователь может откорректировать (добавить, удалить, отметить наиболее важные) оставшиеся ключевые термины и их контекст.

9. Выполняется поиск документов по сформированному запросу Ъ.

10. Для каждого документа е Бу ,

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

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

12. Завершение поиска.

Описанный алгоритм графически представлен на рисунке.

ЗАКЛЮЧЕНИЕ

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

Литература

1. Ландэ Д.В. Поисковые системы: поле боя - семантика. "Телеком" № 4, 2004 г.

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

3. Максимович Г.Ю., Романенко А.Г., Самойлюк О.Ф. Информационные системы: Учеб. пособие: 2 изд., испр. и доп. М.: Российск. гос. гуманит. ун-т, 2007. 289с.

4. Маннинг К. Д., Рагхаван П., Шютце Х. Введение в информационный поиск. : Пер. с англ. - М.: ООО «И.Д. Вильямс», 2011. 528с.

Алгоритм поиска семантически похожих документов Северо-Кавказский горно-металлургический институт

А DIALOGUE TECHNIQUEFOR AUTOMATION SEMANTICALLY SIMILAR DOCUMENTS SEARCH

A.V. Kalinichenko

We propose a method for searching semantically similar text documents, which increases the search pertinence. Dialogue with the user, used in the method allows to specify the information need and build a more exact search query

Key words: information retrieval, similar document search, pertinence