Инструментальные средства Эффективные алгоритмы № 2 (44) 2013 ПРИКЛАДНАЯ ИНФОРМАТИКА М. А. <...> Баранов, аспирант Московского института электроники и математики НИУ ВШЭ Модификация жадного алгоритма кластеризации Задача создания эффективных по времени и релевантности результата алгоритмов документального поиска сохраняет свою актуальность. <...> Возможности для усовершенствования предоставляют жадные алгоритмы кластеризации. введение эффективных алгоритмов информационного поиска, одной из составляющей которых является кластеризация — разбиение исходного множества документов на группы, состоящие из схожих документов. <...> Из факта принадлежности документа кластеру и его релевантности по отношению к некоторому информационному запросу с высокой вероятностью следует, что и остальные документы данного кластера также релевантны этому запросу [13]. <...> В настоящее время разработано множеН ство алгоритмов кластеризации, использующих различные подходы к решению задачи кластерного анализа. <...> Стоит отметить, что жадные алгоритмы часто используются при решении задач кластеризации (см., например, [1, 2, 9, 12, 18]). <...> Предварительно строится матрица схожести документов 78 Инструментальные средства Эффективные алгоритмы аблюдаемый рост количества создаваемых документов делает все более актуальной задачу создания размером N Ч N, где N — число документов в коллекции, а документу с номером k соответствуют k-й столбец и k-я строка. <...> В матрице в каждой ячейке (i, j) задается мера схожести между i-м и j-м документами. <...> Предлагается подбирать меру схожести таким образом, чтобы ее значение лежало в диапазоне от 0 до 1, где 0 соответствует полному различию документов, а 1 — полному сходству. <...> На первом шаге в матрице схожести находится строка, сумма элементов которой является максимальной. <...> Документ, соответствующий ей, объявляется центром очередного кластера, а сама строка содержит коэффициенты схожести этого документа со всеми остальными <...>