Способы представления результирующих наборов
В соответствии с принципом вероятностного ранжирования должен быть получен результирующий набор и представлен пользователю в виде списка, отсортированного с учетом вероятности релевантности. Такой способ представления имеет смысл, если пользователь заинтересован в поиске всех релевантных документов, проведенном настолько быстро, насколько это возможно. Но он оказывается не совсем приемлемым, поскольку в нем не учитывается полезность. Например, если в коллекции имеются две копии наиболее релевантного документа, то после просмотра первой копии полезность второй, имеющей такую же релевантность, становится равной нулю. Во многих системах информационного поиска имеются механизмы, позволяющие исключать результаты, которые слишком подобны ранее полученным результатам.
Один из наиболее мощных способов повышения производительности системы информационного поиска состоит в обеспечении возможности использовать отзывы, касающиеся релевантности. В этих отзывах пользователь указывает, какие документы из первоначального результирующего набора являются релевантными. После этого система может представить второй результирующий набор документов с документами, подобными указанным.
Еще один подход состоит в том, что результирующий набор представляется в виде размеченного дерева, а не упорядоченного списка. С помощью средств классификации документов эти результаты оформляются в виде заранее определенной таксономии тем. Например, коллекция новостных сообщений может классифицироваться на "World News" (Зарубежные новости), "Local News" (Местные новости), "Business" (Новости экономики), "Entertainment" (Новости культуры) и "Sports" (Новости спорта). А при использовании средств кластеризации документов дерево категорий создается для каждого результирующего набора с нуля. Методы классификации являются приемлемыми, если количество тем в коллекции невелико, а методы кластеризации в большей степени подходят для более широких коллекций, таких как World Wide Web. И в том и в другом случае после выполнения запроса пользователя результирующий набор предъявляется ему в виде папок, составленных по категориям.
Классификация — это задача контролируемого обучения, поэтому для ее решения может применяться любой из методов, описанных в главе 18. Один из широко используемых подходов состоит в формировании деревьев решений. После подготовки обучающего множества документов, обозначенных правильными категориями, может быть сформировано единственное дерево решений, листьям которого поставлены в соответствие документы, принадлежащие к той или иной категории. Такой подход полностью себя оправдывает, если имеется лишь несколько категорий, но при наличии более крупных множеств категорий приходится формировать по одному дереву решений для каждой категории, притом что листья этого дерева обозначают документ как принадлежащий или не принадлежащий к данной категории. Обычно характеристиками, проверяемыми в каждом узле, являются отдельные слова. Например, в одном из узлов дерева решений для категории "Sports" может быть предусмотрена проверка наличия слова "basketball". Для классификации текстов были опробованы такие средства, как усиленные деревья решений, наивные байесовские модели и машины поддерживающих векторов; во многих случаях точность при использовании булевой классификации находилась в пределах 90-98%.
Кластеризация относится к типу задач неконтролируемого обучения. В разделе 20.3 было показано, как может использоваться алгоритм ЕМ для улучшения начальной оценки кластеризации на основе сочетания гауссовых моделей. Задача кластеризации документов является более сложной, поскольку неизвестно, было ли выполнено формирование данных с помощью правильной гауссовой модели, а также в связи с тем, что приходится действовать в условиях пространства поиска, имеющего намного больше размерностей. Для решения этой задачи был разработан целый ряд подходов.
В методе агломеративной кластеризации создается дерево кластеров путем выполнения полной обработки совокупности вплоть до отдельных документов. Отсечение ветвей этого дерева для получения меньшего количества категорий может быть выполнено на любом уровне, но такая операция рассматривается как выходящая за рамки самого алгоритма. На первом этапе каждый документ рассматривается как отдельный кластер. После этого отыскиваются два кластера, наиболее близкие друг к другу согласно определенному критерию расстояния, и эти два кластера сливаются в один. Такой процесс повторяется до тех пор, пока не остается только один кластер. Критерием расстояния между двумя документами является некоторый критерий, измеряющий совпадение слов в этих документах. Например, документ может быть представлен как вектор количества слов, а само расстояние определено как евклидово расстояние между двумя векторами. Критерием расстояния между двумя кластерами может служить расстояние до середины кластера или может учитываться среднее расстояние между элементами кластеров. Метод агломеративной кластеризации требует затрат времени, пропорциональных О (п2), где п — количество документов.
В методе кластеризации по к средним создается плоское множество, состоящее точно из к категорий. Этот метод действует, как описано ниже.
1. Случайным образом осуществляется выборка к документов для представления к категорий.
2. Каждый документ обозначается как принадлежащий к ближайшей категории.
3. Вычисляется среднее каждого кластера и используются к средних для представления новых значений к категорий.
4. Этапы 2) и 3) повторяются до тех пор, пока алгоритм не сходится.
Для метода кластеризации по к средним требуются затраты времени, пропорциональные О (л), в чем состоит одно из его преимуществ над агломеративной кластеризацией. Но в литературе часто приходится встречать сообщение о том, что этот метод является менее точным по сравнению с агломеративной кластеризацией, хотя некоторые исследователи сообщают, что он позволяет добиться почти таких же высоких показателей [1460].
Но независимо от применяемого алгоритма кластеризации требуется решить еще одну задачу, прежде чем результаты кластеризации можно будет использовать для представления результирующего набора, — найти удобный способ описания кластера. При использовании метода классификации имена категорий уже определены (например, "Earnings" — доходы), но при кластеризации имена категорий приходится изобретать заново. Один из способов выполнения этой задачи состоит в подборе списка слов, которые являются представительными для этого кластера. Еще один вариант состоит в применении названий одного или нескольких документов, близких к центру кластера.