Подход к анализу и построению алгоритмов решения одной задачи кластеризации на знаковых графах

doi:10.17223/20710410/64/9

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Семенова, Дарья Владиславовна | Ибрагимова, Эллада Ибрагимовна

Add to "Quick Collection"

Description	Size	Format
Подход к анализу и построению алгоритмов решения одной задачи кластеризации на знаковых графах	727 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/64/9

#знаковые графы

#корреляционная кластеризация

#систематизация алгоритмов

#потенциальные функции

Title: Подход к анализу и построению алгоритмов решения одной задачи кластеризации на знаковых графах
Title: Approach to analysis and construction of algorithms for solving one clustering problem on signed graphs
Creator: Солдатенко, Александр Александрович
|
Семенова, Дарья Владиславовна
|
Ибрагимова, Эллада Ибрагимовна
Date: 2024
DOI: 10.17223/20710410/64/9
Description: Рассматривается NP-трудная оптимизационная задача корреляционной кластеризации для неориентированных и невзвешенных знаковых графов без кратных рёбер и петель, где функционал ошибки представляет собой линейную комбинацию межкластерной и внутрикластерной ошибок. Предложен системный подход построения и анализа алгоритмов, основанных на структуре графа, для решения этой задачи. Подход представлен в виде общей схемы, состоящей из шести взаимосвязанных блоков, отражающих основные этапы решения задачи корреляционной кластеризации. С использованием данной схемы проанализированы шесть существующих алгоритмов. Согласно общей схеме построен новый алгоритм CarVeR, который является модификацией алгоритма SGClusta с помощью потенциальных функций. Топология общей схемы открывает возможности для анализа и доказательства вычислительной сложности алгоритмов, что продемонстрировано в теореме о вычислительной сложности алгоритма CarVeR. Представлены вычислительные эксперименты на синтетических данных для сравнения пяти алгоритмов. Результаты экспериментов показали конкурентную способность алгоритма CarVeR как по времени выполнения, так и по минимизации значения функционала ошибки.