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

Размещено на http://www.allbest.ru/

ОПРЕДЕЛЕНИЕ ТЕМАТИКИ ЗАПРОСА, ИСПОЛЬЗУЯ ГРАФОВЫЕ МОДЕЛИ ДАННЫХ

Довбенко Алексей Викторович - аспирант,

кафедра теоретических основ информатики, факультет прикладной математики, информатики и механики,

Воронежский государственный университет, г. Воронеж

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

DETERMINE THE SUBJECT OF THE QUERY USING GRAPH DATA MODELS

Dovbenko Alexey Victorovich - Post-Graduate Student,

DEPARTMENT OF THEORETICAL BASES OF COMPUTER SCIENCE, FACULTY OF APPLIED MATHEMATICS, COMPUTER SCIENCE AND MECHANICS, VORONEZH STATE UNIVERSITY, VORONEZH

Abstract: in the article examples of determining the subject of a query using graph data models are considered. The main problem of determining the subject matter of the text, as well as completely unobvious problems with which the developer may encounter, is considered. The main examples of queries, the use of 'stop words', an example of storing data in an oriented and undirected graph are presented, and the method of constructing both an oriented and undirected graph is described. Also given is an example of learning the system, based on word repetition in various documents. Various ways of solving the definition of the text are proposed. Keywords: search query, query topics, graph data model, search engine.

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

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

- реагировать на стоп слова, например «стрелы лука» относятся к теме охоты, а «жаренные стрелы лука» - к кулинарии.

Самой адекватной моделью для представления текста является граф, который определяется как конечное множество объектов (вершин) и множество пар различных вершин (ребер) [1, стр. 22]. Такая структура хорошо изучена с точки зрения математики и часто служит удобным средством представления структурированной информации для дальнейшего анализа. Графы используются в гуманитарных областях знаний для автоматической обработки текстов [2, 3], информационного поиска [4], реферирования и индексирования текстов [5, 6], автоматического перевода [7], стилистической диагностики [8, 9], в задачах атрибуции анонимных текстов [10] и т.д. Обучение системы

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

Fword = n/m, (1),

где Fword - частота встречи слова в тексте; n - количество встреч слова и его словообразований; m - общее количество преобразованных в инфинитив слов.

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

Рис. 1. Пример связи слов в графовой модели данных

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

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

Определение тематики поискового запроса с помощью неориентированного графа.

Поиск тематики поискового запроса осуществляется поиском кратчайшего пути между вершинами неориентированного графа (поисковый запрос аналогично разбивается на слова в инфинитиве), причем путь должен проходить хотя бы через одну не искомую вершину. На примере рисунка 1 поисковый запрос «Брандо актер». путь имеет следующий вид: Брандо - фильм - актер, находя непрямой кратчайший путь из вершины «Брандо» в вершину «Фильм» и убирая искомые вершины получаем тематику запроса - «фильм». Имея взвешенный граф, в котором длина ребра равна 1/n, где n - число общих упоминаний вершин в одном тексте (т.е. максимальное значение n - количество обработанных страниц). Можно воспользоваться алгоритмом кратчайшего поиска пути из одной вершин в другую для взвешенного, неориентированного графа, таким как RBFS или SMA* [4].

Рассмотрим пример «стоп слов», т.е. слова которые полностью меняют тематику запроса, несмотря на присутствие других слов относящихся к одной тематике (Рисунок 2). При поисковом запросе «стрелы лука», тематика запроса будет «охота», но при запросе «жаренные стрелы лука», тематика становится равна кулинарии, т.к. кратчайший путь от вершин «лук - стрела» всё ещё проходит через тематику охоты, а вот пути от «жарить - лук» и «жарить - стрела», уже проходят через тематику «Кулинария».

Рис. 2. Пример работы «стоп слов»

Основные проблемы определения тематики поискового запроса с помощью графовой модели данных проявляются, если поисковый запрос уже содержит тематику (например «фильмы про охоту»), тогда использование неориентированного графа теряет смысл, т.к. связь между темами слабая и поиск общего узла среди множества ребер мало того, что затратен по времени и ресурсам [7], так и бессмыслен, потому что мы уходим от основных тем к подтемам. Также возникает проблема, когда связь между графами одна и она линейна, вычисления общих узлов займут много времени и в итоге ничего не вернут. Определение тематики поискового запроса с помощью ориентированного графа.

Итак хранение данных в неориентированном графе и поиск тематики по кратчайшему пути не удовлетворяет большинству условий, несмотря на отличную работу в «идеальной среде», такая модель ломается при запросе, включающем в себя тематику, при единственной линейной связи между узлами, при неимении связей. Исходя из этого рассмотрим пример модели хранения в ориентированном графе. Ориентированный граф должен перестраиваться в зависимости от количества новых документов и как следствие обучения исходной системы. Исходя из этого следует предположить, что в момент времени t0 или при n0 обработанных документов, систему стоит считать обученной. Направленность связей графа должна исходить из узлов с наименьшем общем количеством веса к наибольшему, т.е. главные темы не должны иметь исходящих связей (Рисунок 3). Определение темы идет от узлов поиска к конечным узлам, далее определяются общие узлы путей, так при запросе «Брандо актер», исходя из рисунка 3, тематика слова «Брандо» будет «Фильм», а слова «актер» - «Театр» и «Фильм».

Рис. 3. Пример ориентированного графа

Такая модель данных, поиска от частного к общему имеет ряд достоинств, алгоритм расчета довольно линеен, и не захватывает множество узлов, при имении темы изначально система не будет делать лишних вычислений (При запросе «Фильм Антракт», исходя из рисунка 3, выберутся два ключевых слова «Фильм» и «Антракт»). Стоит отметить, что в конечной модели данных вес ребер не имеет значимости, поэтому граф можно считать ненагруженным. Основной сложностью этой системы является построение ориентированного графа и его изменение при времени t (n+1) или количестве обработанных документов m (n+1), но исходя из того что построение такого графа делается незаметным для конечного пользователя, то быстродействие и расход ресурсов не играют большой роли.

Вывод

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

запрос данные граф

Список литературы / References

1. Bunke H., Jiang X., Kandel A. On the minimum common supergraph of two graphs // Computing. 2000. Vol. 65. № 1. P. 13-25. [Электронный ресурс]. Режим доступа: http://wotan.liu.edu/docis/dbl/comput/2000 65 1 13 QTMCSQ.html/ (дата обращения: 15.01.2018).

2. Апресян Ю.Д. Идеи и методы современной структурной лингвистики. М.: Просвещение, 1966. 302 с.

3. Тарланов З.К. Методы и принципы лингвистического анализа: Учебное пособие для вузов. Петрозаводск: Издательство Петрозаводского университета, 1995. 189 с.

4. Шемакин Ю.И. Начала компьютерной лингвистики: Учебное пособие. М.: Издательство Московского государственного открытого университета, 1992. 113 с.

5. Фаронов В.В. Delphi. Программирование на языке высокого уровня: Учебник для вузов. СПб.: Питер, 2004. 640 с.

6. Химические приложения топологии и теория графов: Материалы симпозиума 18-22 апреля 1983 г.

Афины, шт. Джорджия, США / Под ред. Ю.А. Жданова. М.: Мир, 1987. 560 с.

7. Миркин Б.Г. Анализ качественных признаков и структур. М.: Статистика, 1980. 319 с.

8. Новиков А.И. Семантика текста и ее формализация. М.: Наука, 1983. 215 с.

9. Турыгина Л.А. Моделирование языковых структур средствами вычислительной техники. М.: Высшая школа, 1988. 175 с.

10. Севбо И.П. Графическое представление синтаксических структур и стилистическая диагностика. Киев: Наукова Думка, 1981. 192 с.

Размещено на Allbest.ru