V Международная студенческая научная конференция Студенческий научный форум - 2013

Введение

В настоящее время для решения задачи поиска применяются математическо-статистические (латентный семантический поиск), графовые (набор документов представляется в виде ориентированного графа) и онтологические (поиск по готовым онтологиям) методы []. Каждый из них имеет недостатки:

• Неприменимость на локальном компьютере и в локальной сети (графовые – из-за отсутствия явных ссылок между документами).

• Неприемлемые затраты на построение индексов и поддержание их актуального состояния (онтологические – из-за отсутствия автоматических методов построения онтологий).

• Ведение поиска без учета семантики слов и выражений, и, как следствие, снижение релевантности результатов поиска (латентный семантический поиск и поиск на графовых структурах).

Несмотря на перечисленные недостатки, тандем латентного семантического поиска и поиска на графовых структурах дает хорошие результаты: большинство поисковых систем в сети Internet использует эту совокупность []. Однако, как говорилось, графовые методы неприменимы для персонального и корпоративного поиска и оба подхода не учитывают семантику запроса и документов, не имеют компонент объяснения. Как следствие, задача поиска «по смыслу» остается нерешенной, а новейшие алгоритмы поисковых систем в сети Internet, дающие хорошие результаты, остаются неприменимыми на локальном компьютере и в локальной сети.

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

Основные понятия

Для описания предлагаемого алгоритма введем и раскроем некоторые понятия.

Онтология

Под онтологией будем понимать пару , где

X – конечное непустое множество концептов (понятий, терминов) предметной области, которую представляет онтология О;

– конечное множество отношений между концептами (понятиями, терминами) заданной предметной области.

Минимальный набор концептов, допустимых в онтологии:

1. Именованная вершина. Именоваться может только листовая вершина.

2. Неименованная вершина. Такой вершиной будет являться любая не листовая вершина. Частным случаем неименованной вершины является вершина типа «Документ», служащей точкой входа в онтологию документа.

Минимальный набор отношений, которые будут допустимы и будут поддерживаться:

1. «Синоним». Данное отношение будет указывать на синонимичность понятий в определенном контексте.

2. «Ссылается на». Данное отношение призвано отражать связи между документами. На основе связей этого типа возможно построение ориентированного графа документов. Данное отношение допустимо только между концептами типа «Документ».

3. «Это есть». Отношение служит для построения таксономии понятий. При помощи этого отношения будет возможно указания стиля документа или его принадлежности к определенным категориям.

4. «Является автором». Специальное, предметное отношение для явного выделения авторов и соавторов документов. Данное отношение должно вести к вершине типа «Документ».

5. «Наименование» Отношение, необходимое для именования нелистовых вершин онтологии.

Документ

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

Таким образом, документ представляется тройкой:

,

где: R – множество реквизитов документа. Множество реквизитов может быть описано стандартом метаданных «Дублинское ядро» []. В примерах будут использоваться такие реквизиты как A – автор и T – название;

C – контент, т.е. содержимое физического документа;

O– онтология документа.

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

1. Наличие одной и только одной вершины типа «Документ».

2. Из вершины «Документ» должна исходить одна дуга типа «Наименование». Наименование может быть как единственным, так и иметь несколько синонимов (к примеру, название документа на другом языке).

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

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

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

Описание алгоритма

Теперь перейдем к описанию непосредственно метода поиска документов. Предлагаемый нами алгоритм состоит из пяти шагов:

1. Первым шагом поиска является построение онтологии O по имеющимся документам.

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

3. Третий шаг – выделение набора документов , содержащих все ,или его часть; обозначим этот набор за .

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

Последний шаг работы – выдача результатов пользователю.

Далее опишем каждый шаг подробно.

Построение онтологии

Шаг является подготовительным для поиска. На нем решается задача автоматического построения онтологий документов O, выделения реквизитов документа, таких, как авторы A и названия T, из неструктурированного документа на естественном языке (ЕЯ).

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

После построения онтологий документов происходит определение связей «ссылается на» между документами. Целесообразно данные связи вынести в отдельную онтологию. При анализе связей между документами могут быть обнаружены «висячие» ссылки, т.е. исходящие ссылки на документы, которые отсутствуют в общем репозитории документов. Такие «висячие» ссылки все равно должны быть помещены в онтологию связей. За счет этого поиск будет возможен даже по тем документов, которые отсутствуют физически в репозитории. Получив результат, пользователь сможет найти предложенный документ в другом месте (например, в сети Internet).

Иными словами, мы получаем онтологии двух уровней:

1.  

   1. обозначим онтологии документов , где n – количество документов;

   2. онтология связей между документами – .

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

1. .

Дополнительно, может быть построена онтология предметного уровня . Данная онтология не относится к документам D – она содержит знания о предметной области, к которой относятся документы. Ее построение может быть как автоматическим, так и ручным. Следует отметить, что при отсутствии единой предметной области между документами, над которыми будет осуществлен поиск, построение большого числа может ухудшить результаты поиска за счет появления аномалий, противоречий, неоднозначностей в знаниях.

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

1. Предметная онтология , описывающая общие сведения из предметной области. Ее наличие необязательно.

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

3. Онтологии , являющиеся детализацией вершин в и содержащие онтологическое представление документов в документном репозитории.

Как, так и могут ссылаться на онтологию .

Ввод запроса пользователем

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

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

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

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

Выбор первичного множества документов

Задачей данного этапа является первичный отбор множества документов , удовлетворяющих запросу пользователя Q. Множество, полученное на данном этапе, не является окончательным и может быть изменено на следующем этапе.

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

Таким образом, первоначальный набор документов вычислим по формуле:

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

На этом же этапе, отобранным документам присваиваются веса – степень семантической близости к запросу пользователя. Вес документа можно вычислить по формуле:

,

где

,

где – оценка близости между предикатами, а и – триплеты (триплет представляет собой тройку , где и – концепты онтологии, а P – предикат, отношение между.

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

Следует отметить, что вес документа не нормирован. Это вызвано тем, что мы измеряем семантическое расстояние между документом и запросом, а не относительную их близость. Требование отсутствия нормированных весов предъявляется алгоритмом HITS, выбранным в качестве алгоритма ранжирования для более качественного вычисления «авторитетных документов».

Таким образом, после выполнения этого этапа мы имеем:

1. Запрос пользователя Q.

2. Онтологию запроса пользователя .

3. Предметную онтологию .

4. Онтологию связей .

5. Онтологии документов .

6. Первоначальный набор документов .

7. Веса документов, вошедших в – .

Совмещая вместе и, мы получаем взвешенный ориентированный граф , где V – множество документов , некоторым из которых поставлено в соответствие число – вес. При отсутствии числа, вес документа будем считать за 0. Множество E – множество ориентированных дуг, символизирующих связи между документами. Дуги из E не имеют весов за счет того, что на сегодняшний день невозможно автоматически определить силу связи между документами с достаточной точностью.

Выполнение алгоритма ранжирования

Для ранжирования результатов нами был выбран алгоритм HITS []. В качестве идеальных для него выдвигаются требования:

1.  

   1. должно быть относительно небольшим;

1.  

   1. должно содержать большое число релевантных документов;

   2. содержит большинство (или много) сильных «авторитетов»;

(здесь– коллекция документов, участвующих в ранжировании).

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

«Корневой» набор документов увеличивается за счет добавления документов, на которые ссылаются или которые ссылаются на любой документ из множества. В алгоритме вводится параметр d – количество документов, которые может добавить документ из . Документы, добавляемые во множество, должны выбираться как d документов с наибольшими весами (наибольшей семантической близостью). При этом их веса должны превышать. Такой отбор будет повышать полноту поиска и его релевантность.

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

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

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

Таким образом, результатом работы данного алгоритма станет набор пар , где:

1.  

   1. – найденный документ;

   2. – ранг документа, полученный в результате работы алгоритма.

Выдача результатов поиска

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

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

Заключение

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

На данном этапе выполняется построение онтологии ссылок документов и частичное построение онтологии документа O, реализуется механизм ранжирования HITS. Ошибка составления онтологий составляет 27%. Наиболее частой причиной ошибки является несоблюдение правил оформления и ГОСТов.

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

Библиографический список

1. Signorini A. A survey of Ranking Algorithms // Department of Computer Science University of Iowa – 2005. – № 11 – С: 36-39.

2. Гасанов Э.Э. Теория Хранения и поиска информации / Э.Э. Гасанов, В.Б. Кудрявцев // М.: Физматлит, 2002.

3. ГОСТ Р 7.0.10 – 2010. Система стандартов по информации, библиотечному и издательскому делу. Набор элементов метаданных «Дублинское ядро». – Москва: Изд-во стандартов, 2010. – 74 с.

4. Губин М.Ю. Методы создания семантических метаописаний документов с применением семантических сетей, фреймовых моделей и частотных характеристик / М.Ю. Губин, В.В. Разин, А. Ф. Тузовский // Доклады Томского государственного университета систем управления и радиоэлектроники. – 2010. – Т. 2, № 2. – С. 227–229.

5. Никоненко А.А. Обзор знаний онтологического типа / А.А. Никоненко // научно–теоретический журнал «Искусственный интеллект». – 2009.–№4. – С. 208 219.

Научный руководитель: старший преподаватель кафедры МОВС ПГНИУ В.В. Ланин

Код для цитирования: Скопировать