Васильев И.Л. Ушаков А.В.
Параллельный алгоритм поиска нижних оценок оптимального значения в одной из моделей кластерного анализа графов и сетей связей, возникающих в веб-пространстве, биологических и социальных сообществах
Докладчик: Ушаков А.В.
В докладе рассматривается один из подходов к задаче кластерного анализа, основанный на применение модели задачи о p-медиане. Задача кластерного анализа состоит в разбиении множества объектов (наблюдений, событий) на непересекающиеся подмножества, называемые кластерами, таким образом, чтобы объекты внутри каждого кластера были схожи друг с другом и в то же время существенно отличались от объектов из других кластеров. Известно, что решение задачи о p-медиане дает решение задачи кластерного анализа, известное как «сумма звезд», поскольку каждое допустимое решение задачи состоит из p графов-звезд, в центре которых находятся медианы.
В докладе предлагается схема параллельного алгоритма для поиска нижних оценок оптимального значения в задаче о p-медиане. Подход основан на использовании так называемого метода релаксаций Лагранжа, включающим в себя построение релаксаций задачи, а также максимизацию получившейся двойственной функции Лагранжа с помощью методов негладкой оптимизации, обеспечивая в результате нижнюю оценку оптимального значения. Главным новшеством предлагаемого подхода является не только эффективная параллельная схема, но и реализация специальной модели хранения данных, позволяющей оперировать задачами значительно большей размерности, чем известная до сегодняшнего дня из литературы. В докладе приведены результаты вычислительного эксперимента как на известных тестовых примерах большой размерности, так и искусственно сгенерированных задачах кластерного анализа.
| Файл с полным текстом: | VasilyevUshakov.pdf |
К списку докладов
