Кластерная гипотеза (cluster hypothesis)

16.1. Кластеризация в информационном поиске
Кластерная гипотеза (cluster hypothesis) — это основное предположение, позволяющее применять кластеризацию для информационного поиска. Кластерная гипотеза. Документы, принадлежащие одному и тому же кластеру, являются примерно одинаково релевантными по отношению
к информационным потребностям.
Эта гипотеза утверждает, что если документ принадлежит кластеру
и является релевантным по отношению к запросу, то вполне вероятно, что
и другие документы этого кластера релевантны. Это объясняется тем, что кластеризация объединяет документы, содержащие много общих терминов. Кластерная гипотеза по существу является гипотезой о смежности, сформулированной в главе 14. В обоих случаях мы постулируем, что
похожие документы обладают примерно одинаковыми свойствами релевантности.
В табл. 16.1 перечислены основные приложения кластеризации в области информационного поиска. Они отличаются по множествам документов, которые подвергаются кластеризации (результаты поиска, коллекция или подмножества коллекции), и по аспектам информационно-поисковой системы, которые при этом улучшаются (качество или производительность поиска). При этом все они опираются на основную гипотезу о кластерах.

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

в информационно-поисковых системах представляются в виде простого списка. Пользователи просматривают этот список сверху вниз, пока не
найдут нужную им информацию. В то же время после кластеризации результатов поиска похожие документы будут указаны в списке недалеко друг от друга. Иногда легче просматривать группы однородных документов, а не множество отдельных документов. Это особенно полезно, если термин запроса имеет несколько значений. Например, на рис. 16.2 показан запрос jaguar. Три наиболее распространенных значения этого слова — автомобиль, животное и операционная система компьютера Apple. Панель Clustered Results в поисковой системе Vivisimo (http://vivisimo.com) представляет собой более рациональный пользовательский интерфейс, позволяющий лучше понять содержание результатов поиска по сравнению с обычным списком документов.
Более удобный пользовательский интерфейс можно также создать с помощью разбиения и объединения (scatter-gather). Это приложение указано в табл. 16.1 вторым. Метод разбиения и объединения разбивает (scatter) всю коллекцию на кластеры, чтобы получить группы документов, которые пользователь может выбрать или объединить (gather). Выбранные группы объединяются, а совокупность результатов вновь разделяется на кластеры. Этот процесс повторяется до тех пор, пока не будет найден искомый
кластер. Пример показан на рис. 16.3.
Автоматически сгенерированные кластеры, такие как на рис. 16.3, не так аккуратно организованы, как вручную сконструированное иерархическое дерево, подобное каталогу Open Directory (http://dmoz.org). Кроме того, автоматический поиск меток, описывающих кластеры, представляет собой сложную проблему (раздел 17.7). Однако навигация по кластерам является интересной альтернативой стандартному поиску по ключевым словам. Это особенно верно в ситуациях, когда пользователь предпочитает запросам
переходы по ссылкам, поскольку не уверен в выборе терминов запроса.
В качестве альтернативы итеративной кластеризации, управляемой пользователем, в методе разбиения и объединения можно осуществить статическую иерархическую кластеризацию коллекции без участия пользователя (в табл. 16.1 это приложение называется “Кластеризация коллекции”). Примерами такого подхода являются новостная поисковая
система Google News и ее предшественница — система Columbia NewsBlaster. В случае новостей мы должны проводить кластеризацию часто, чтобы пользователь имел доступ к самым свежим новостям. Кластеризация хорошо подходит работы с коллекциями новостей, поскольку чтение новостей на самом деле является не поиском, а процессом выбора подмножества сообщений о недавних событиях.
Четвертое приложение кластеризации использует гипотезу о кластерах напрямую для лучшения результатов поиска за счет кластеризации всей коллекции. Для идентификации начального множества документов, соответствующих запросу, используется стандартный инвертированный индекс. Затем к этому множеству добавляются другие документы из того
же кластера, даже если они слабо связаны с запросом. Например, если поступил запрос car, то будет извлечено несколько документов из кластера, посвященного автомобилям, а затем к ним будут добавлены документы из этого кластера, в которых используются другие термины (automobile, vehicle и т.д.). Это повышает полноту поиска; группа документов с высокой взаимной схожестью часто образует группу релевантных документов.

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

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

невозможно использовать эффективно, например, при латентном семантическом индексировании (глава 18). В таких ситуациях можно было бы оценить сходство запроса с каждым документом, но это слишком медленный процесс. Кластерная гипотеза предлагает альтернативу: найти кластер, ближайший к запросу, и рассматривать только документы
из данного кластера. Для этого (намного меньшего) множества можно вычислить сходство запроса с каждым документом и ранжировать документы обычным образом. Поскольку кластеров намного меньше, чем документов, поиск ближайшего кластера выполняется быстро, а поскольку документы, соответствующие запросу, похожи друг на друга, они, как правило, принадлежат одному и тому же кластеру. Хотя этот алгоритм
неточен, ожидаемое снижение качества поиска незначительно. Это использование кластеризации описано в разделе 7.1.6.