RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 2019, том 161, книга 3, страницы 423–437 (Mi uzku1528)  

Решение задачи кластеризации методами оптимизации на графах

И. В. Коннов, О. А. Кашина, Э. И. Гильманова

Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия

Аннотация: Быстрый рост объёмов обрабатываемой информации, наблюдаемый в последнее время, увеличение размерности решаемых задач обусловливают актуальность разработки и применения методов снижения размерности. Одним из подходов к снижению размерности данных является их кластеризация, то есть объединение в максимально однородные группы. При этом желательно, чтобы представители разных кластеров были бы максимально «непохожими» друг на друга. Помимо снижения размерности, задачи кластеризации имеют и самостоятельное значение, например, в экономике это связано с сегментированием рынка, в социологии — с типологизацией признаков, в геологии — с фациальной диагностикой пород и т. д.
Несмотря на большое число известных методов решения задачи кластеризации, проблема разработки и исследования новых алгоритмов не теряет актуальности. Дело в том, что не существует алгоритма, который превосходил бы все остальные по всем критериям (быстродействие, нечувствительнсть к размерам и форме кластеров, количество параметров и т. д.).
В статье представлен алгоритм кластеризации, основанный на применении теории графов (теоремы о максимальном потоке и минимальном разрезе) и проведён сравнительный анализ его с четырьмя другими алгоритмами — представителями различных классов методов кластеризации.

Ключевые слова: кластеризация, максимальный поток, минимальный разрез, теорема Форда–Фалкерсона, метод расстановки пометок, метод $k$-средних, иерархическая кластеризация, метод Варда, метод DBSCAN, алгоритм MaxFlow.

Финансовая поддержка Номер гранта
Министерство образования и науки Российской Федерации 1.12878.2018/12.1
1.460.2016/1.4
Российский фонд фундаментальных исследований 16-01-00109_a
Работа выполнена за счет средств субсидии, выделенной Казанскому федеральному университету для выполнения государственного задания в сфере научной деятельности, проект № 1.12878.2018/12.1.
Работа первого и второго авторов выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект № 16-01-00109a.
Работа первого автора выполнена в рамках государственного задания Минобрнауки России, номер задания 1.460.2016/1.4.


DOI: https://doi.org/10.26907/2541-7746.2019.3.423-437

Полный текст: PDF файл (729 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.179.2
Поступила в редакцию: 17.10.2018

Образец цитирования: И. В. Коннов, О. А. Кашина, Э. И. Гильманова, “Решение задачи кластеризации методами оптимизации на графах”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 161, № 3, Изд-во Казанского ун-та, Казань, 2019, 423–437

Цитирование в формате AMSBIB
\RBibitem{KonKasGil19}
\by И.~В.~Коннов, О.~А.~Кашина, Э.~И.~Гильманова
\paper Решение задачи кластеризации методами оптимизации на графах
\serial Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки
\yr 2019
\vol 161
\issue 3
\pages 423--437
\publ Изд-во Казанского ун-та
\publaddr Казань
\mathnet{http://mi.mathnet.ru/uzku1528}
\crossref{https://doi.org/10.26907/2541-7746.2019.3.423-437}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/uzku1528
  • http://mi.mathnet.ru/rus/uzku/v161/i3/p423

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Ученые записки Казанского университета. Серия Физико-математические науки
    Просмотров:
    Эта страница:22
    Полный текст:12
    Литература:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020