Приведенные коэффициенты, по сути, представляют

Таблица 4.5.14.2

Коэффициент	Название
	Коэффициент Дайса (dice)
	Коэффициент Джаккарда (jaccard)
	Косинусный коэффициент
	Коэффициент перекрытия

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

. Надо сказать, что обратное утверждение, вообще говоря, не верно.
Если P – множество объектов, предназначенных для кластеризации, то функция D определения степени различия документов – это функция, ставящая в соответствие

неотрицательное рациональное число. Функция определения степени различия d удовлетворяет следующим условиям:

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

, где

представляет собой разность множеств x и y. Она связана, например, с коэффициентами Дайса соотношением

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

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

двух векторов

для косинусного коэффициента соответствия

получаем следующую формулу:

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

она может быть определена как:

.
Если xi и xj - независимы, тогда

(и

). Дополнительно выполняется условие, что

, показывающее, что функция является симметричной.
Функция

интерпретируется как статистическая мера информации, содержащейся в документе

о документе

(и наоборот). Когда данная функция применяется для определения степени связи между двумя индексными терминами, например, i и j, тогда xi и xj являются бинарными переменными. Таким образом,

является вероятностью присутствия индексного термина i и, соответственно P(xi=0) является вероятностью его отсутствия.
Та степень взаимосвязи, которая существует между индексными терминами i и j вычисляется затем функцией

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

для определения степени соответствия (см. Jardine, N. and Sibson, R., Mathematical Taxonomy, Wiley, London and New York (1971)) между парами документов.
Как и в случае автоматической классификации документов, использование вероятностных методов при формировании кластеров содержит в себе достаточно высокий потенциал и представляет крайне интересную область для исследований.
Итак, для формирования кластеров необходимо использовать некую функцию соответствия для определения степени связи между парами документов из коллекции.
Постулируем теперь основную идею, на которой, собственно говоря, и построена вся теория кластерного представления коллекции документов. Гипотеза, приведшая к появлению кластерных методов, называется Гипотезой Кластеров и может быть сформулирована следующим образом: “Связанные между собой документы имеют тенденцию быть релевантными одним и тем же запросам”.
Базисом, на котором построены все системы автоматического поиска информации, является то, что документы, релевантные запросу, отличаются от нерелевантных документов.

Гипотеза кластеров указывает на целесообразность разделения документов на группы до обработки поисковых запросов. Естественно, она ничего не говорит о том, каким образом должно проводиться это разделение.
Проводился ряд исследований по поводу применения кластерных методов в поисковых системах. Некоторые отчеты приведены в работах Б. Литофски, Д. Крауча, Н. Привеса и Д. Смита, а также М. Фритше.
Кластерные методы, выбираемые для использования в экспериментальных поисковых системах должны удовлетворять некоторым определенным требованиям. Это:

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

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

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

Основной вывод из вышесказанного состоит в том, что любой кластерный метод, не удовлетворяющий приведенным условиям, не может производить сколько-нибудь значащие экспериментальные результаты. Надо сказать что, к сожалению, далеко не все работающие кластерные методы удовлетворяют приведенным требованиям. В основном, это происходит из-за значительных различий между реализованными методами кластеризации от теоретически разработанных ад-хок алгоритмов.
Другим критерием выбора является эффективность процесса создания кластеров с точки зрения производительности и требований к объему необходимого дискового пространства.
Необходимость учета данного критерия находится, естественно, в сильной зависимости от конкретных условий и требований.
Возможно, использование процедур фильтрации базы данных таким образом, что из базы данных будет удаляться информация об индексных терминах, встречающихся в более чем, скажем 80% проиндексированных документов. Таким образом, список стоп-слов будет динамически изменяющимся. Как уже говорилось, использование списка стоп-слов может приводить к 30% уменьшению размеров индексных файлов.

Для построения кластеров обычно используется два основных подхода:

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

кластерные методы применяются не к объектам непосредственно, а к их описаниям.

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

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

1	Salton, G., “Automatic Text Analysis”, Science, 168, 335-343 (1970)
2	Luhn, H. P. “The automatic creation of literature abstracts”, IBM Journal of Research and Development, 2, 159-165 (1958)
3	Gerard Salton, Chris Buckley and Edward A. Fox, “Automatic Query Formulations in Information Retrieval”, Cornell University, http://cs-tr.cs.cornell.edu/
4	Tandem Computers Inc. “Three Query Parsers”, http://oss2.tandem.com /search97/doc/srchscr/tpappc1.htm
5	Object Design Inc., “Persistent Storage Engine PSE-Pro documentation”, http://www.odi.com/
6	Roger Whitney, “CS 660: Combinatorial Algorithms. Splay Tree”, San Diego State University. http://saturn.sdsu.edu:8080/~whitney/

Содержание раздела

Главная сайта