Кластеризация

- Методы кластеризации 
- Алгоритм кластеризации на основе суффиксных деревьев 

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

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

K-means . Относится к не-иерархическим алгоритмам. Кластеры представлены в виде центроидов, являющихся "центром массы" всех документов, входящих в кластер. 

STC - Suffix Tree Clustering . Кластеры образуются в узлах специального вида дерева - суффиксного дерева, которое строится из слов и фраз входных документов 
На основе проведенного исследования было принято решение использовать в качестве метода кластеризации модифицированный алгоритм на основе суффиксных деревьев. 

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

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

• важен порядок слов в документе для определения названий кластеров, состоящих из нескольких слов

Общая схема формирования тематических групп документов с использованием алгоритма STC:

• Очистка

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

Затем для набора документов строится дерево, но единицей, находящейся на рёбрах дерева является слово или словосочетание
• Группировка базовых кластеров

Пусть Bm и Bn - базовые кластеры, |Bm|, |Bn| - их размеры. |Bn Bm|- количество общих документов для этих кластеров. Если: |Bn Bm|/ |Bm| > 0.5 и |Bn Bm| / |Bn| > 0.5, то базовые кластеры объединяются в один общий, иначе не объединяются

• Удаление стоп-слов
Удаление слов, не имеющих смыслового значения слов (частицы, междометия и т. д.)
• Морфологический разбор
Приведение слова к нормальной форме (перевод в единственное число, удаление суффиксов)
• Синтаксический разбор
Выделение связанных компонент (существительное + прилагательное)

• Строится суффиксное дерево для очищенных документов
  




Рис 1. Пример суффиксного дерева для строк
1. «кошка ест сыр»
2. «мышь тоже ест сыр»
3. «кошка тоже ест мышь»

• Определяются базовые кластеры

На основе построенного дерева формируются базовые кластеры:
1. кошка
2. сыр
3. мышь
4. тоже ест

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