ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
3
поисковых выдач ИПС требует дополнительных исследований. Так, в
ИПС, распространяющихся как специальное программное обеспче-
ние (СПО), в частности в ядре ИПС ApacheSolr (и соответственно в
библиотеке Lucene) отсутствуют собственные инструменты класте-
ризации результатов поиска. В ряде крупных коммерческих проек-
тов, например в продуктах фирмы Oracle, данная возможность суще-
ствует, однако закрытость исходных кодов ограничивает их
применение в собственных разработках.
Для расширения функциональности реализованной на базе
ApacheSolr специализированной ИПС была поставлена задача срав-
нительного анализа методов кластеризации с последующей инте-
грацией наиболее подходящего из методов. Проанализировав пуб-
ликации с точки зрения перспектив алгоритмической реализации и
возможности интеграции в специализированную ИПС выбраны два
алгоритма: STC (suffix tree clustering) — алгоритм, в котором класте-
ры образуются в узлах специального вида дерева (суффиксное дере-
во, строящееся из слов и фраз входных документов [6]), и Lingo —
алгоритм, основанный на интеграции метода сингулярного разло-
жения и
k
-средних [7].
На рис. 2 приведен пример, заимствованный из работы [6], по-
строения суффиксного дерева и принципа метода кластеризации для
строк: «кошка ест сыр», «мышь тоже ест сыр», «кошка тоже ест
мышь». На основе построенного дерева формируются базовые кла-
стеры: кошка, сыр, мышь, тоже ест. Если базовые кластеры пересе-
каются более чем по половине содержащихся в них слов, то происхо-
дит объединение кластеров.
В отличие от STC, алгоритм Lingo основан на сингулярном раз-
ложении терм-документной матрицы [7].
Рис. 2. Алгоритм [6] построения суффиксного дерева
1,2 4,5,6,7