XIV Российская конференция с международным участием
"Распределенные информационные и вычислительные ресурсы" (DICR-2012)

№ гос. регистрации 0321300118
26 ноября - 30 ноября 2012, Новосибирск

Васильев И.Л.   Ушаков А.В.  

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

Докладчик: Ушаков А.В.

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

Файл с полным текстом: VasilyevUshakov.pdf


К списку докладов