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

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

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

Поисковый запрос в большинстве информационных систем представляется в виде набора слов, которыми пользователь пытается описать искомый документ, в этом случае работает предположение, что смысл документа можно выразить через смысл употребляемых в нем слов. Основываясь на этих данных можно предположить, что в распоряжении поисковой системы имеется только набор документов и словарь терминов. В этом случае данные, которыми оперирует поисковая система, представляются в виде матрицы, где документы представлены в виде строк, а слова, то есть признаки или термы, образующие словарь представлены в виде столбцов. Элементы матрицы это веса термов, часто вычисляемые с использованием меры TF-IDF [4]. Запрос представляется вектором, большая часть компонент которого равна нулю, отличны от нуля только те компоненты, термы которых участвуют в запросе. Документ также описывается вектором, компоненты которого соответствуют строкам матрицы. Однако основная задача, выполняемая поисковой, системой заключается не столько в поиске документов, сколько в ранжировании найденных документов с помощью какой-либо функции меры определяющей релевантность документа поисковому запросу.

К моделям информационного поиска, оперирующим подобным набором исходных данных относятся расширенные булевские модели [6]. Расширенные булевские модели, в своих самых простых вариантах реализации, вычисляют функцию меры, определяющую релевантность документа поисковому запросу, как скалярное произведение двух векторов представляющих документ и запрос.

Однако наиболее часто используемыми являются векторные модели. Эти модели в качестве меры релевантности документа поисковому запросу используют меру, определяемую как косинус угла между вектором документа и запроса. Такой подход к представлению и поиску документов с помощью векторных пространств был реализован в VSM методе [3]. Идея VSM метода, представления документов как объектов в многомерном пространстве признаков, подверглась критике, заключавшейся в том, что в качестве ортогонального базиса векторного пространства используются термы, часть которых может быть семантически зависима, что стало учитываться в GVSM [5] методе. Более того, в LSI [2] методе, также являющемся развитием VSM метода, сделана попытка выявления контекстно-зависимых термов, что позволяет понизить размер используемой матрицы, но оставляет открытым вопрос выбора наилучшей размерности этой матрицы.

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

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

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

Методика вычисления меры. Для определения расстояний нам потребуется построить структуру  являющейся семантической сетью. В данной структуре будут присутствовать два вида объектов, объекты являющиеся признаками (термами или мнимыми документами) и объекты, являющиеся обычными документами. Данная структура является смешанным связанным графом, в котором вершинами выступают как документы, так и признаки. Связи между документами и признаками не ориентированны, а связи между самими документами, то есть цитирование, могут быть ориентированными. Также могут быть установлены прямые связи между самими признаками, но в нашей модели эту задачу в значительной степени выполняют документы.

Каждая связь должна обладать весом или длиной, если говорить о ребрах графа. При этом, чем меньше длина, тем сильнее связаны между собой объекты. Например, вес связи между документом и признаком можно вычислять, используя меру TF-IDF, а между документами использовать некоторый аналог меры TF-IDF.

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

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

a1

где qi объекты из множества термов, j объекты из множества документов, а rij минимальное расстояние между объектами i и j на графе. Набор термов поискового запроса q1,…,qk по возможности должен присутствовать в документе, а набор термов qk+1,…,qp по возможности должен в нем отсутствовать. Таким образом, искомый документ должен быть ближе к термам q1,…,qk и дальше от термов qk+1,…,qp. В итоге искомым документом будет тот, для которого значение функции R будет наименьшим.

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

a2

где i объект, значимость которого мы вычисляем, a6, а n число объектов в нашем множестве. Чем больше значение функции F, тем выше значимость объекта i. Так как выражение, стоящее под знаком суммы быстро убывает с ростом расстояний между объектами, то основной вклад в значения функции F, вносят те объекты, которые расположены ближе к объекту i.

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

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

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

a3

Функция S позволяет связать степень значимости объектов с расстоянием между ними. Для объектов, относящихся к одной предметной области, основной вклад в значения функции S вносит значимость, а для объектов из разных предметных областей основной вклад в значения функции S вносит расстояние. С помощью функция S мы можем определить наиболее связанные документы и признаки. Чем терминологически ближе объекты, тем большие значения принимает функция S. Даже если объект i, принадлежит некоторой предметной области, но при этом не относится к объектам, которые лучше других описывают данную предметную область, то все равно максимум функции S для объекта i будет достигаться на объекте j, который также принадлежит этой предметной области и при этом будет ближе или одним из тех объектов, которые лучше других описывают данную предметную область.

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

a4

где C равно модулю минимального значения функции S на всем множестве исследуемых объектов. Искомым документом будет тот, для которого значение функции RD будет максимальным, при этом мы также получим релевантную оценку для каждого документа из нашего множества. С помощью функции RD ищется документ, который будет не просто ближе к термам q1,…,qk и дальше от термов qk+1,…,qp, он также будет являться одним из наилучших описаний предметной области, к которой также принадлежат термы q1,…,qk и по возможности не принадлежат термы qk+1,…,qp.

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

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

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

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

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

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

  1. Заякин Д.И. Параметрическая чувствительность метода кластеризации, основанного на анализе плотности распределения объектов // Проблемы управления и моделирования в сложных системах: Труды XI международной конференции. Самара, 2009. – С. ххх-ххх.
  2. Deerwester S., Dumais S. T., Furnas G. W., Landauer T. K., Harshman R. A. Indexing by Latent Semantic Analysis // Journal of the American Society for Information Science. – 1990. – № 1(6). – P. 391–407.
  3. Salton G., Wang A., Yang C. S. A vector space model for information retrieval // Journal of the American Society for Information Science. – 1975. – № 18(11). – P. 613–620.
  4. Salton G., Buckley C. Term-weighting approaches in automatic text retrieval // Information Processing & Management. – 1988. – № 24(5). – P. 513–523.
  5. Wong S. K. M., Ziarko W., Wong P. C. N. Generalized vector space model in information retrieval // Proceedings of the 8th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval. (Montreal, Canada, 1985). – P. 18–25.
  6. Lee J. H. Properties of extended Boolean models in information retrieval // Proceedings of the 17th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval. (Dublin, Ireland, 1994). – P. 182–190.

А вот одна из картинок к презентации к статье.

a5

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

2 идей о “Кластерная модель информационного поиска

  1. akkaynt-magaz.ru

    Если быть точным, то информационно-поисковые системы в Internet — это признание того, что ни иерархическая модель Gopher, ни гипертекстовая модель World Wide Web не решают проблему поиска информации в больших объемах разнородных документов.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *