Частотный метод маркирования

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

Метод c²

Этот метод [13] применяется для кластерного разбиения, подразумевающего иерархию кластеров. Основная идея его состоит в том, что бы использовать критерий c² для каждого слова, для каждого узла, начиная от корня иерархии и продвигаясь рекурсивно к листьям. Если гипотеза о том, что термин повторяется примерно равное количество раз во всех потомках данного узла подтверждается, этот термин помечается как основной для текущего поддерева и считается удаленным из всех остальных его узлов. Обычно мера значимости для данного критерия выбирается от 0.95 и выше. Чем выше критерий значимости, тем меньшее количество терминов остается для каждого узла по завершении алгоритма [13].

Краткое описание алгоритма.

Шаг 1. Для каждого узла составить список терминов, употребляющихся в документах относящегося к нему кластера (каждый кластер объединяет все предыдущие вниз по дереву).

Шаг 2. Начиная с вершины дерева, для каждого термина проверить гипотезу c² о независимости (данный термин имеет разную вероятность появления в потомках данного узла):

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

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

Шаг 3. Повторять шаг 2 рекурсивно, двигаясь по дереву вниз.

Список оставшихся не удаленными для каждого узла слов можно использовать для именования соответствующего кластера документов.