Сборник 2001

ОБЗОР МЕТОДОВ КЛАСТЕРИЗАЦИИ ТЕКСТОВОЙ ИНФОРМАЦИИ

Кириченко К.М, Герасимов М.Б.

STAR SPb (Russia)

 

Огромные объёмы информации в сети Internet зачастую приводят к тому, что количество объектов, выдаваемых по запросу пользователя, очень велико. Это затрудняет процесс обзора результатов и выбора наиболее подходящих материалов (статей, обзоров, отчетов, др.) из множества найденных. Однако, в большинстве случаев огромные объемы информации можно сделать доступными для восприятия, если уметь разбивать источники информации (например, WEB-страницы) на тематические группы. Тогда, пользователь сразу может отбрасывать множества документов из мало-релевантных групп. Такой процесс группировки данных (в нашем случае текстовых) осуществляется с помощью кластеризации или классификации корпуса текстов.

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

ВВЕДЕНИЕ

Обзор проблематики

Нередко случается, когда на введённый пользователем запрос, выдаётся огромное количество материалов, будь то тексты, веб-сайты и т.д. Как правило, результаты запроса представляют собой линейные списки с простым перечислением объектов, отсортированных по релевантности к запросу – некоторой метрике семантической близости документа к запросу. Некоторые поисковые системы позволяют также показать документы, семантически близкие (похожие) выбранному, из всех доступных или только из тех, которые вошли в результат.

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

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

-       они должны содержать семантически близкие по какому-то признаку документы;

-       этот признак должен быть возведён к названию рубрики, которое должно быть читаемым.

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

Критерии оценки исследуемых методов

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

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

Точность системы – в какой степени возвращаемые результаты удовлетворяют запросам пользователей - может определяться экспертами в проблемной области вручную [22], или автоматически с помощью статистических критериев, которые описаны ниже;

-       возможность работы алгоритма в «инкрементном» режиме – осуществлять рубрикацию документов, одновременно с поступлением их из источника, не выполняя каждый раз полный цикл вычислений;

-       «пересекаемость» – возможность попадания одного документа в разные рубрики по смежным темам. Необходимость пересекаемости возникает не всегда. Возможно, пользователю захочется, чтобы документы были строго распределены между рубриками, и каждый из документов входил только в одну из них;

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

С точки зрения реализации метода мы рассмотрим еще несколько критериев:

-       способность использования характеристик о множестве документов, вычисленых зараннее – до основного процесса обработки. К таким характеристикам относятся: матрица близости между документами - similarity matrix, матрица весов документов – tf· idf. (Определение этих понятий см. ниже);

-       необходимость обучения алгоритма.

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

Список рассматриваемых методов

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

-       метод Custom Search Folders – позволяет сузить результаты поиска путём распределения их по «папкам» (folders). Эта система уже реализована в поисковом сервере, находящемся по адресу www.northernlight.com, и имеет название NorthernLight – соответственно;

-       LSA/LSI – Latent Semantic Analysis/Indexing [2]. Путем факторного анализа множества документов выявляются латентные (скрытые) факторы, которые в дальнейшем являются основой для образования кластеров документов;

-       STC – Suffix Tree Clustering [1]. Кластеры образуются в узлах специального вида дерева – суффиксного дерева, которое строится из слов и фраз входных документов;

-       Single Link [3], Complete Link, Group Average – эти методы разбивают множество документов на кластеры, расположенные в древовидной структуре – dendrogramm, получаемой с помощью иерархической аггломеративной кластеризацией;

-       Scatter/Gather [7], [8]. Представляется как итеративный процесс, сначала разбивающий (scatter) множество документов на группы и представлении затем этих групп пользователю (gather) для дальнейшего анализа. Далее процесс повторяется снова над конкретными группами.

-       K-means [23], [24]. Относится к не-иерархическим алгоритмам. Кластеры представлены в виде центроидов (см. ниже), являющихся “центром массы” всех документов, входящих в кластер.

-       CI – Concept Indexing [5]. Разбивает множество документов методом рекурсивной бисекции, т.е. разделяя множество документов на две части на каждом шаге рекурсии. Метод может использовать информацию, полученную на этапе обучения.

-       SOM – Self-Organizing Maps. Производит классификацию документов с использованием самонастраивающейся нейронной сети.

Эти алгоритмы будут подробно описаны в дальнейших разделах.

ОПИСАНИЕ МЕТОДОВ

Прежде чем описывать алгоритмы важно различать следующие свойства, присущие алгоритмам.

Во-первых, необходимо чётко понять разницу между классификацией и кластеризацией документов. Классификация это отнесение каждого документа в определённый класс с заранее известными параметрами, полученными на этапе обучения. Число классов строго ограничено. Кластеризация – разбиение множества документов на кластеры – подмножества, параметры которых заранее неизвестны. Количество кластеров может быть произвольным или фиксированным. Исходя из этих определений, методы SOM иCI осуществляют классификацию документов (последний - в том случае, если используется алгоритм с обучением). Кластеризацию осуществляют остальные алгоритмы. Кластеризация на неопределённое число кластеров производится методом STC, остальные методы требуют задания количества кластеров. Метод LSA/LSI после нахождения скрытых факторов и фиксации их количества фактически превращается в классификацию – ассоциация документов к выбранным факторам.

Во-вторых, все методы можно разделить на числовые и нечисловые. Числовые – это те методы, которые используют числовые характеристики о документах (например, матрицу tf·idf, матрицу близости документов, см. ниже). Нечисловые – методы, которые для работы используют непосредственно слова и фразы, составляющие текст. К нечисловым методам относится STC, остальные методы являются числовыми.

В-третьих, числовым методам кластеризации присущи два способа выполнения кластеризации множества документов: top-down, bottom-up. Top-down – весь имеющийся объем документов изначально рассматривается как единый кластер, и происходит его деление на более мелкие составляющие, до тех пор, пока не сработает остановочный критерий. Как правило, этим критерием является количество кластеров. Bottom-up – изначально рассматривает каждый документ, как отдельный кластер. В процессе работы наиболее близкие документы объединяются в кластеры, содержащие всё больше и больше документов. На остановку метода влияет остановочный критерий. К методам top-down относится CI в его «необучаемой» реализации. Bottom-up - это Single Linkage, Complete Linkage, Group Average и алгоритмы Buckshot и Fractionation применяемые вметоде Scatter/Gather.

ОПРЕДЕЛЕНИЯ

Множество документов в пространстве терминов или множество документов. Oбъекты, с которыми мы оперируем - это документы или части документов, т.е. некоторые фрагменты текстов. Каждый из документов представляется набором слов. В этом наборе могу встречаться конструкции, которые не должны влиять на результаты поиска[1]: некоторые слова общей лексики, предлоги и другие строки. Имеются также слова, которые непосредственно влияют на отнесение документа в какую-либо категорию, - это термины. Каждый термин является элементарным признаком, множество терминов составляет пространство. Множество документов – это множество точек или векторов этого пространства. Координатами точки являются величины значимости каждого термина для данного документа. Величина значимости может считаться по-разному. Ниже приведено несколько метрик, наиболее часто используемых на практике [5]:

-       Бинарная. 0 означает, что термин в данном документе не встречается, 1 – встречается.

-       Количество вхождений термина в документ – TF (term frequency).

-       Интегральная значимость – tf·idf (term frequency, inverse document frequency), которая может вычисляться по-разному, например:

, где

N – количество документов,

n_t – количество документов, в который входит термин t,

m_dt – число вхождений термина t в документ d,

m_d – .

Координаты документов в пространстве терминов записываются в матрицу tf·idf.

Для получения матрицы tf·idf. необходима предварительная обработка текста документа. Следует заметить, что обработка текста для получения матрицы tf·idf не является частью алгоритма кластеризации. Эта матрица формируется для построения матрицы близости (см. ниже), а матрица близости используется для определения множества документов, наиболее схожих с данным.

Все методы, кроме STC, используют готовые данные матрицы tf·idf или матрицы близости.

-       Близость документов (similarity) в пространстве терминов. Эта величина определяет, на сколько один документ семантически похож на другой, и вычисляется, например, как Евклидово расстояние между точками или косинус угла между векторами, представляющими документы в пространстве терминов. Все значения близости документов записываются в треугольную матрицу – матрица близости документов (document similarity martix).

-       Кластер – группа документов со схожими признаками. Все алгоритмы стремятся, чтобы схожесть документов, попадающих в кластер, была именно семантической. Числовые методы связывают понятие кластера и ранее описанных величин, например, следующими способами:

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

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

-       Цетроид кластера – это вектор, который вычисляется как среднее арифметическое векторов всех документов кластера:

,

где S – группа документов, или Кластер. Такое определение центроида кластера еще называют центром масс кластера, подмножества документов.

Custom Search Folders

Эта технология использована в поисковом сервере NorthernLight. Суть её заключается в том, что пользователь может сузить результат поиска, и рассматривать объекты, распределённые по папкам – folders. Выбором одной из предложенных папок пользователь сужает диапазон рассматриваемых объектов.  Объектами в данном случае являются HTML ссылки. Папки имеют иерархическую структуру, что дает возможность всё более и более сужать результат поиска. Распределение по папкам происходит на этапе пост-процессинга (post-processing). По сути дела папки являются центроидами кластеров, к которым затем соотносятся документы (сайты). Процесс распределения по папкам занимает не много времени, потому что матрица близости документов уже есть, она как правило считается в режиме пре-процессинга (подсчёт коэффициентов близости для всего объёма документов – это довольно долгий процесс, который выполняется по мере поступления новых документов в коллекцию.)

Иерархия папок построена вручную и содержит около 20’000 элементов [1]. Благодаря этому названия папок имеют читаемый вид. Таким образом система обладает высокой скоростью работы и хорошей наглядностью. Однако, поскольку набор папок построен вручную, системе обладает следующими недостатками:

-       При построении иерархии папок был использован английский язык, поэтому система работоспособна только на англоязычных запросах и может, соответственно классифицировать документы написаные на этом языке;

-       Иерархия папок имеет довольно общий характер. Опускаясь вниз по иерархии папок, можно заметить, что любая часть иерархии заканчивается уровнем, содержащим одни и те же папки, не зависимо от того из какой точки иерархии мы попали на этот уровень. Однако содержимое папок этого уровня уже зависит от пути следования по иерархии папок. По этой же причине система не применима к узким предметным областям – например, для поиска в специализированных полнотекстовых базах данных;

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

Рис.1. Так выглядит результат запроса по слову “submarine”. В левой колонке перечислены папки, в которые сгруппированы результаты запроса – Custom Search Folders.

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

LSA/LSI

LSA/LSI - как метод обнаружения латентных связей - известен давно [10] и применяется в различных сферах науки. В основе метода лежат принципы факторного анализа, в частности, выявление латентной  структуры изучаемых явлений или объектов.

Пространство терминов – пространство элементарных признаков, в котором изначально располагаются документы. Поскольку термины каким-то семантическим образом связаны между собой, значит они коррелированны[2], поэтому документы, содержащие семантически близкие термины, сгущаются в определённых местах пространства терминов. Фактор - это некая семантическая сущность, которая может не иметь определённого (и читаемого) названия. После определения числа и параметров факторов происходит отображение множества документов на пространство факторов.

 Задачей факторного анализа является выделение главных факторов из пространства элементарных. В большинстве случаев задача нахождения главных факторов решается с помощью Метода Главных Компонент [20]. Количество главных факторов выбирают существенно меньшим, чем количество элементарных, таким образом, редуцируя пространство, на которое происходит отображение объектов исследования (документов). Определение количества главных факторов и конфигурации их в пространстве являются основными проблемами факторного анализа.

Оценка количества выделенных главных факторов может проводиться при помощи критерия Бартлетта – подтверждение или опровержение гипотезы о том, что количества главных факторов достаточно для воспроизведения ковариационной матрицы между объектами (в нашем случае это матрица близости). Проблема конфигурации главных факторов - это проблема выбора положения факторов в пространстве при известном их количестве. Эта проблема чаще всего решается методом варимаксного вращения Фергюсона [20].

Выделенные главные факторы являются координатными осями нового – редуцированного – пространства факторов, и в нашем случае они есть центроиды кластеров.

LSA/LSI - это реализация основных принципов факторного анализа применительно ко множеству документов. Кроме того, метод позволяет успешно преодолевать проблемысинонимии и омонимии, присущие текстовому корпусу. Проблема синонимии возникает тогда, когда одно и то же понятие может быть описано разными словами – синонимами. При омонимии одно слово может иметь разные смыслы (толкования) в разных контекстах. Из-за этих двух проблем простые средства обработки текстов могут выдавать неадекватные ответы на запросы. LSA позволяет преодолевать их основываясь только на статистическую информацию о множестве документов/терминов.

Технически метод заключается в сингулярном разложении (SVD – singular value decomposition) матрицы tf·idf, таким образом, что:

где A – исходная матрица tfidf размера m ´ n, r = rank( A ),

U^TU = V^TV = I_n и S = diag( s₁, … s_n ) – диагональная матрица, такая что s_i > 0 для , s_j = 0 для j³r+1.

Первые r колонок матриц U, V – определяют наборы ортонормированных левых и правых собственных векторов матрицы А, соответственно. S - диагональная матрица, содержащая собственные числа матрицы А. Фактически, значимая часть матрицы не превосходит ранга матрицы, который не превосходит меньшей размерности матрицы. r– это и есть размерность начального факторного пространства. Далее выбираются k£r наибольших собственных чисел из матрицы S, и мы получаем k-размерное факторное пространство, на которое проецируются, как документы посредством матрицы V, так и термины посредством матрицы U [2][21]. В полученном факторном пространстве документы и термины концентрируются областями, имеющими общий семантический, латентный, смысл.

Применительно к кластеризации, получаемые области и есть кластеры. С помощью математических преобразований [21] можно определить центры кластеров. Уже существуют методы инкрементного обновления (incremental update procedures) всех структур, используемых в LSA [21].

Достоинства метода:

-       использует информацию матрицы tf·idf.;

-       метод не нуждается в предварительной настройке на специфический набор документов, его не надо обучать;

-       лучший метод для выявления латентных зависимостей.

Среди недостатков:

-       огромное количество вычислений может приводить к тому, что на результатах запросов, содержащих сотни тысяч объектов система будет работать очень долго. Как утверждают авторы в [2], скорость вычисления SVD соответствует порядку N²  x k, где N=N_docs+N_terms, k – размерность пространства факторов;

-       отсутствие подходящего названия для полученных факторов. В [10] описывается один из алгоритмов поиска подходящих названий, но это требует дополнительных вычислительных затрат;

-       кластеры не пересекаются;

Suffix Tree Clustering

Изначально суффиксные деревья – suffix tees - были разработаны и применялись для быстрого поиска подстрок. Суффиксное дерево – дерево, содержащее все суффиксы данной строки. Оно состоит из вершин, ветвей и дополнительных указателей, называемых suffix pointers, с помощью которых добиваются линейной скорости построения дерева [11]. Ветви дерева обозначаются буквами или буквосочетаниями, которые являются частями суффиксов строки. Суффикс, соответствующий определённой вершине, можно получить путем объединения всех букв, которые находятся на ребрах дерева, начиная от корневой вершины и заканчивая данной.

В [11] и [12] описан алгоритм построения такого дерева для строки символов за время O(n), причем количество используемой памяти также растёт линейно с ростом длины строки. В диссертации [1][3] предложено использовать идею суффиксных деревьев для кластеризации результатов запросов поисковой системы.

Построение дерева осуществляется поэтапно. Сначала получаемые из сети от поискового сервера документы подвергаются предварительно обработке - отчистка от пунктуации, приведение слов в начальную форму (с помощью алгоритмов морфоанализа или стемминга) и т.д. Затем для набора документов строится дерево, но единицей, находящейся на рёбрах дерева является слово или словосочетание, а не буква, как в случае с деревьями для строк. Каждой вершине дерева соответствует фраза. Её можно получить, объединив все слова/словосочетания, находящиеся на рёбрах на пути от корня дерева к данной вершине дерева. В тех вершинах дерева, которые имеют потомков, имеются ссылки на документы, в которых встречается фраза, соответствующая вершине. Множества документов, на которые указывают эти ссылки, образуют базовые кластеры. После этого производится комбинирование базовых кластеров и получение набора кластеров.

Комбинируются кластеры по простой методике:

Пусть B_m и B_n – базовые кластеры, |B_m|, |B_n| - их размеры. |B_nÇB_m| - количество общих документов для этих кластеров.

Тогда, если:     |B_nÇB_m| / |B_m| > 0.5 и  |B_nÇB_m| / |B_n| > 0.5, то базовые кластеры объединяются в один общий, иначе не объединяются.

Достоинства метода:

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

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

-       алгоритм не нуждается в обучении и задании порога срабатывания;

-       алгоритм инкрементен и допускает пересекаемость областей видимости кластеров;

-       если имеется уже построенный индекс по корпусу документов, то можно произвести «арифметизацию» если все тексты документов заменить на некое числовое представление слов, где каждое число ссылается на вход в словаре (или тезаурусе), то сравнивать придётся не слова, а числа, и препроцессинг текстов становится не нужным.

Недостатки метода:

-       необходимость повторной обработки текстов документов.

-       не используется уже имеющаяся информация о значения близости документов или значениях td·idf;

-       не выявляется скрытая семантика среди документов, которая может присутствовать не только на текстовом уровне;

-       проблемы синонимии и омонимии;

Дополнительно: в [18] – приводится сравнение алгоритма с некоторыми другими известными.

Single Link, Complete Link, Group Average

Одни из старейших алгоритмов кластеризации данных. Относятся к методам кластерного анализа ([3], [10], [13]). Особенностью этих методов, является то, что они разбивают документы на кластеры путем разбиения их на иерархичные группы, т.е. получаемое множество кластеров имеет иерархичную структуру. Они называются еще методами иерархической агломеративной кластеризации. Принцип работы иерархических агломеративных процедур состоит в последовательном объединении групп элементов, сначала самых близких, а затем всё более отдалённых друг от друга [20].

Основная суть этих методов заключается в выполнении следующих шагов ([13]):

1. вычисление значений близости между документами и получении матрицы близости;
2. определение каждого документа в свой отдельный кластер;
3. сливание в один кластер наиболее близких пар документов;
4. обновление матрицы близости путем удаления колонок и строк для кластеров, которые были слиты с другими и дальнейшего пересчета матрицы;
5. переход на шаг 3 до тех пор, пока не сработает остановочный критерий.

Эти три метода отличаются между собой в 4-м шаге. И именно благодаря способам обновления матрицы близости разные алгоритмы имеют разную точность. Проверка точности алгоритмов была проведена на специальных тестовых наборах и показала, что алгоритм Single Link имеет наименьшую точность, а остальные два - примерно одинаковую, более высокую, чем у Single Link. Результаты тестирования алгоритмов можно посмотреть в  [13].

В качестве остановочного критерия выбирается максимальное количество документов в кластере.

Скорость работы алгоритмов Single Link и Group Average - O(n²), а в Complete Link – O(n³) [14], где n – количество документов. Количество занимаемой памяти алгоритмомSingle Link – O(n) [3].

Достоинства методов:

-       алгоритмы не нуждаются в обучении;

-       использование матрицы близости между документами;

-       алгоритмы инкрементены.([3]).

Недостатки методов

-       необходимо задавать порог – максимальное количество документов в кластере;

-       для получения хороших результатов кластеризации значения близости между парами документов должны приходить в определённом порядке, т.е. работа алгоритма не детерминированная [3];

-       кластеры не пересекаются.

Scatter/Gather

Scatter/Gather – это метод представления результатов запросов пользователю ([7], [8]). Сначала система разбивает документы на небольшое число групп – фаза scattering. Основываясь на кратких описаниях групп, пользователь выбирает одну или несколько групп для дальнейшего рассмотрения. Документы объединяются – фаза gathering – и рассматриваются, как одна группа, и процесс повторяется уже над ней. Это похоже на последовательность искусственных запросов внутри основного.

На фазе разбиения метод может использовать два алгоритма [7]: Buckshot и Fractionation. Алгоритм Buckshot более быстрый и годится для быстрой рекластеризации при выполнении итераций в Scatter/Gather. Fractionation же является более точным и более медленным алгоритмом и используется в Scatter/Gather для предварительного разбиения на группы множества документов и выполняется в режиме off-line.

Оба алгоритма Buckshot и Fractionation относятся к алгоритмам восходящей (bottom-up) кластеризации.

Идея алгоритма Buckshot заключается в том, что из всего множества документов берётся случайная выборка размером , где k – необходимое количество создаваемых групп, n – количество документов, далее над этой выборкой производится процедура нахождения центров кластеров. Процедура заключается в последовательном «склеивании» документов, находящихся в наибольшей близости друг от друга (используется значение близости между документами). Процедура выполняется до тех пор, пока нужное – заранее заданное количество центров - не будет найдено. Скорость работы алгоритма - O(kn).

Fractionation, – более сложный алгоритм. Сначала все документы разбиваются на группы, число которых больше числа предполагаемых кластеров. Затем группы объединяются, так чтобы их число было равно числу кластеров. Если опустить все математические подробности алгоритма, можно сказать что на j-м шаге объединения число групп равно r^jn, где r - некий фактор редукции, меньший 1. Скорость работы алгоритма O(mn), где m – число начальных групп, на которые бьётся множество документов. Если m = O(k), то алгоритм имеет «прямоугольное» (rectangular) время работы.

Далее производится присвоение документов к центрам. Присвоение происходит по принципу Assign-To-Nearest, –документ присваивается к ближайшему центру. На этом этапе идёт скорее классификация, чем кластеризация. Скорость классификации очень большая по сравнению с кластеризацией, и пропорциональна количеству кластеров.

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

Система Scatter/Gather существует в виде коммерческого продукта и используется для кластеризации различных текстовых ресурсов (например, TIPSTER/TREC [26]).

Рис.2. Результат запроса “bank financial institution failed criminal officer indictment ”, распределённый по кластерам, с использованием системы Scatter/Gather [27].

Достоинства метода:

-       разбиение на кластеры с помощью алгоритма Buckshot обладает высокой скоростью, которая линейна по отношению к числу документов. В то же время Fractionationобладает хорошей точностью определения центроидов кластеров;

-       хорошая наглядность представления данных [7], [8];

-       алгоритм не нуждается в обучении;

-       используется матрица близости документов.

Недостатки метода:

-       высокая скорость и точность не сочетаются в каком-либо одном алгоритме разбиения на кластеры;

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

-       метод не имекрементен;

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

K-means

В основе K-means лежит итеративный процесс стабилизирования центроидов кластеров. Основной характеристикой кластера является его ценроид и вся работа алгоритма направлена на стабилизирование или, в лучшем случае, полное прекращение изменения центроида кластера.

Алгоритм состоит из следующих шагов:

1. Выбираются начальные центроиды для множества документов. Существует несколько методик выбора центроидов:

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

-       на основе Байесовской оценки множества документов [24], нахождения базовых статистик для оценивания и нахождения подходящего для данной выборки числа кластеров и их центроидов. Для Байесовской оценки неизвестных параметров выборки документов необходима априорная информация о природе и распределениях, преимущественно, имеющих место в предметной области [25]. В случае, когда априорной информации нет, можно исходить из того, что распределение нормальное (Гауссовское) или равномерное.

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

2. Все документы множества распределяются среди кластеров. Документ попадает только в один кластер, метрика близости центроида которого и документа имеет наибольшее значение.
3. Пересчитываются центроиды кластеров, исходя из нового множества документов в каждом кластере. Если центроид кластера переместился, то цикл вычислений повторяется с пункта 2. Иначе, если центроид стабилизировался или в некоторой окрестности, или полностью, процесс кластеризации завершается.

Теоретическая скорость работы алгоритма O(n), n – число документов множества.

Достоинства метода:

-       Линейная скорость работы;

-       использует значения матрицы tf·idf;

-       метод не нуждается в обучении и при необходимости может накапливать сведения для дальнейшего увеличения точности работы – использование Байесовских оценок параметров кластеризации;

Недостатки метода:

-       требуется задание количества кластеров, как минимум на начальных этапах – до использования априорной информации;

-       в том случае, когда центроиды кластеров выбираются случайным образом, результаты, получаемые над одной и той же выборкой документов, будут отличаться. Это может происходить по причине неудовлетворительной работы генератора случайных чисел и вследствие равномерного распределения документов в пространстве – без явных областей сгущения;

-       алгоритм не инкрементен;

-       кластеры не пересекаются.

Concept Indexing

Этот метод ([4],[5]) используется для уменьшения размерности пространства признаков (см. LSA/LSI). В пространстве признаков, размерность которого уменьшена, выполняется стандартное отображение множества документов.

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

Необучаемый алгоритм поиска кластеров заключается в непосредственном разбиении на k кластеров (k-way) или методом рекурсивной бисекции. В начале процесса непосредственного разбиения произвольно выбираются k документов, которые являются центрами для кластеров, затем к этим центрам относят документы, которые имеют наивысшее значение коэффициента близости и производят пересчёт центроидов возникших кластеров. Процесс продолжается до исчерпания всех документов или ограничиваются определённым числом итераций.

Метод рекурсивной бисекции подразумевает раэбиение всего объема документов на 2 части, затем эти части тоже подвергаются разбиению, по необходимости. Процесс продолжается рекурсивно до получения k кластеров. Алгоритм рекурсивной бисекции использует значение «суммарного несходства» (aggregate dissimilarity) между документами в кластере, для того чтобы решить какой кластер разбивать дальше. Это значение равно:

где |S_i| - объем кластера. ||C_i||₂ – норма центроида i-го кластера.

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

Достоинства метода:

-       алгоритм рекурсивной бисекции обладает высокой скоростью работы – выше линейной (O(N´logk)), где N – число документов, k – число кластеров;

-       для определения точности алгоритма в [5] использовалась величина:

, RI – retrieval improvement

– количество документов, принадлежащих классу d в «уменьшенном» пространстве признаков размерности r,

– количество документов, принадлежащих классу d в оригинальном пространстве признаков размерности.

В числителе и знаменателе стоят суммы этих величин по всем классам. Значение величины RI, полученное в [5] для методов CI и LSI, очень близки, что говорит о хорошем сходстве алгоритмов (повторим, алгоритм LSI является лучшим для выявления скрытой информации и латетных связей документов);

-       использует значения матрицы tf·idf;

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

Недостатки метода:

-       один из вариантов метода – обучаемый. Для автоматических систем это, безусловно, недостаток, однако обучение заметно улучшает качество работы;

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

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

SOM

По сути своей SOM – это нейронная сеть Кохонена, выполняющая задачу классификации входных данных и обучающаяся без учителя (unsupervised learning) ([9], [17]). SOM– метод, разработанный для отображения многомерных данных на двумерную плоскость – еще один способ визуализации данных.

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

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

Сети Кохонена ещё называют топологическими картами. Как уже отмечалось, количество классов в сети строго ограничено, однако, поскольку сеть обучается без учителя, то параметры классов не известны. Параметры классов формируются в результате специального алгоритма обучения сети, применяемого к множеству документов ([9]) и специальным образом организованных обучающих наборов. Поэтому можно сказать, что алгоритм осуществляет кластеризацию документов.

Достоинства метода:

-       удобство представления результатов кластеризации;

-       метод прост в обучении;

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

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

-       процесс построения сети инкрементен, но имеет значение порядок подачи обучающих сигналов;

-       кластеры пересекаются.

Недостатки метода:

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

-       как правило, процесс обучения длительный и требует фиксирования числа классов и набора обучающих данных.

Рис.3. Внешний вид карты Кохонена с проекта WEBSOM: http://websom.hut.fi/websom

Заключение

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

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

Исходя из приведённых в статье описаний алгоритмов, оценок этих алгоритмов и ориентируясь на сводную таблицу алгоритмов, приведённую ниже, мы можем сделать вывод, что наилучшими являются алгоритмы STC и CI, использующий метод рекурсивной бисекции. У обоих этих алгоритмов хорошее сочетание скорости и точности. Из этих двух, на наш взгляд, лучшим является STC, его преимущество состоит в том, что кластеры, полученные с помощью этого метода, имеют читаемое название и могут быть использованы для описания рубрик.

References

[1]    Oren Eli Zamir. A Phrase-Based Method for Grouping Search Engine Results. University of Washington, Department of Science & Engineering.

[2]    Susan T. Dumains, George W. Furnas, Thomas K.Landauer. Indexing by Latent Semantic Analysis. Bell Communications Research 435 South St. Morristown, NJ 07960. Richard Rashman:University Of Western Ontario.

[3]    R. Sibson. SLINK: An optimally efficient algorithm for the single-link cluster method. King’s College Research Center, King’s College, Cambridge, and Cambridge University Statistical Laboratory.

[4]    Eui-Hong (Sam) Han and George Kapyris. Centroid-Based Document Classification: Analysis & Experimental Results. University of Minnesota, Department of Computer Science / Army HPC Research Center,4-192 EECS Bldg., 200 Union St. SE, Minneapolis, MN 55455 USA.

[5]    Eui-Hong (Sam) Han and George Kapyris. Concept Indexing. A Fast Dimensionality Reduction Algorithm with Application to Document Retrieval & Categorization. University of Minnesota, Department of Computer Science / Army HPC Research Center,4-192 EECS Bldg., 200 Union St. SE, Minneapolis, MN 55455 USA.

[6]    Eui-Hong (Sam) Han, George Kapyris, Vipin Kumar. Text Categorization Using Weight Adjusted k-Nearest Neighbor Classification. University of Minnesota, Department of Computer Science / Army HPC Research Center,4-192 EECS Bldg., 200 Union St. SE, Minneapolis, MN 55455 USA.

[7]    Douglass R.Cutting, David R.Karger, Jan O.Pedersen, John W.Turkey. Scatter/Gather: a Cluster-based Approach to Browsing Large Document Collections.

[8]    Marti A.Hearst, Jan O.Pedersen. Reexaminig the Cluster Hypothesis: Scatter/Gather on Retrieval Results. Xerox Palo Alto Research Center, 3333 Coyote Hill RD, Palo Alto, CA 94304.

[9]    Jouko Lampinen and Erkki Oja. Clustering Properties of Self-Organizing Maps. Lapperanta University of Technology, Department of Information Technology, PO box 20, SF-53851 Lapperanta, Finland.

[10]  L.A Soshnikova, V.N. Tamashevich, G. Uebe, M. Sheffer., 1999. Multidimensional statistical analysis in economics. Uniti:Moscow.

[11]  Sartaj Sahni: http://www-pub.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm

[12]  Esko Ukkonen. On-line construction of suffix trees. Department of Computer Science, University of Helsinki, PO Box 26 (Teollisuuskatu 23), FIN-00014 HUT, Finland.

[13]  Alan Griffiths, H. Claire Luckhurst, and Peter Willett. Using Interdocument Similarity Information in Document Retrieval Systems. Department of Information Studies, University of Sheffield, Western Bank, Sheffield S10 2TN, United Kingdom. Information Retrieval 1997 p.365-373.

[14]  Voorhees E.M., 1986. Implementing agglomerative hierarchical clustering algorithms for use in document retrieval. Information Processing and Management, 22:456-476.

[15]  Bjornar Larsen and Chinatsu Aone. Fast and effective text mining using linear-time document clustering. In the proc. Of the Fifth ACM SIGKDD Int’l Conference on Knowledge Discovery and Data Mining, pages 16-22, 1999.

[16]  http://www.statsoft.com and http://www.statsoft.com/textbook/stneunet.html

[17]  Teuvo Kohonen. Self-Organization of Very Large Document Collections: State of the Art. Helsinki University of Technology, Neural Networks Research Center, PO Box 2200, FIN-02015 HUT, Finland.

[18]  Oren Zamin and Oren Etzioni. Grouper: A Dynamic Clustering Interface to Web Search Results. Department of Computer science and Engineering, University of Wahington, Box 352350 Seattle, WA 98195-2350 USA. http://www.cs.washington.edu/research/clustering

[19]  Oren Zamin and Oren Etzioni. Web Document Clustering: A Feasibility Demonstration. Department of Computer science and Engineering, University of Wahington, Box 352350 Seattle, WA 98195-2350 USA. http://www.cs.washington.edu/research/clustering

[20]  А.М.Дубров, В.С.Мхитарян, Л.И.Трошин., 1998. Многомерные статистические методы. Москва «Финансы и Статистика»

[21]  Michael W. Berry, Todd A. Letsche. Computational Methods for Intelligent Information Access. Department of Computer Science University of Tennessee Knoxville, TN 37996-13031. Susan T. Dumains: Information science Research Group. Bellcore, 445 South Street Room 2L-371, Morristown, NJ 07962-1910.

[22]  S.E.Robertson. K. Spak Jones., 1976. Relevance weighting of search terms. Journal of the American Society for Information Science May-June 1976.

[23]  Christopher D. Manning, Hinrich Schutze. Foundation of Statistical Language Processing. MIT Press.

[24]  Dan Pelleg, Andrew Moore. X-means: Extending K-means with Efficient Estimation of the Number of Clusters. School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 USA.

[25]  С.А. Айвазян, В.С. Мхитарян., 1998. Прикладная статистика и основы эконометрики. Издательское объединение “ЮНИТИ”, Москва.

[26]  http://trec.nist.gov/

[27]  http://www.sims.berkeley.edu/~hearst/sg-example2.html

 

 

 

Сводка основных характеристик алгоритмов

	Вид метода	Ограничения	Пересекаемость кластеров	Инкрементность алгоритма	Используемые числовые характеристики документов	Предварительное обучение	Скорость работы
LSI	Числовой, кластеризующий	Количество кластеров	-	+	tfidf	-	N2 x k, N=terms+docs, k-factors
STC	Нечисловой, кластеризующий	Нет ограничений	+	+	-	-	O(k2 N), N-число документов, k-число кластеров
Single Link, Complete Link, Group Average	Числовой, bottom-up, кластеризующий	Количество документов в кластере	-	+	Similarity matrix	-	Single Link ~ O(N2) Complete Link ~ O(N3) Group Average ~ O(N2)
Scatter/Gather	Числовой, bottom-up, кластеризующий	Количество кластеров	-	-	Similarity matrix	-	Buckshot ~ O(kN) Fractionation ~ O(mN), m=O(k), k-число кластеров
K-means	Числовой, кластеризующий	Количество кластеров, центроиды	-	-	tfidf	-	O(n)
CI – необучаемый вариант	Числовой, top-down, кластеризующий	Количество кластеров	-	В случае кроме рекурсивной бисекции	Similarity matrix	-	O(N*log k), k-числокластеров
CI – обучаемый вариант	Числовой, классифицирующий	Количество кластеров	-	-	Similarity matrix или tfidf	+	?
SOM	Числовой, классифицирующий	Количество кластеров	+	+	Similarity matrixили tfidf	+	?

 

[1] Эти слова называются «стоп-словами», и обычно исключаются, например, на этапе индексации документа в базе данных. В зависимости от конкретного приложения или проблемной области, множество стоп-слов существенно варьируется.

[2] Это положение является одним из основных. Большинство методов базируется на том, что слова и термины в документе распределены независимо друг от друга, что, естественно, неверно.

[3] Орэн Замир, http://www.cs.washington.edu/homes/zamir