Алгоритм FDET для построения пространства признаков классификации сложных объектов в рамках графовой модели

Вестник ТюмГУ. Физико-математическое моделирование. Нефть, газ, энергетика.


Выпуск:

2017. Том 3. №3

Название: 
Алгоритм FDET для построения пространства признаков классификации сложных объектов в рамках графовой модели


Для цитирования: Егоров Ю. А. Алгоритм FDET для построения пространства признаков классификации сложных объектов в рамках графовой модели / Ю. А. Егоров, М. С. Воробьёва, А. М. Воробьёв // Вестник Тюменского государственного университета. Физико-математическое моделирование. Нефть, газ, энергетика. 2017. Том 3. № 3. С. 125-134. DOI: 10.21684/2411-7978-2017-3-3-125-134

Об авторах:

Егоров Юрий Алексеевич, аспирант, Тюменский государственный университет; y.a.egorov@utmn.ru

Воробьева Марина Сергеевна, кандидат технических наук, доцент кафедры программного обеспечения, Тюменский государственный университет; m.s.vorobeva@utmn.ru

Воробьёв Артём Максимович, старший преподаватель кафедры программного обеспечения, Тюменский государственный университет; a.m.vorobev@utmn.ru

Аннотация:

В статье рассматривается графовая модель для классификации объектов сложной структуры. В рамках данной модели рассматривается алгоритм gBoost, осуществляющий решение задачи классификации. Решением задачи классификации является множество признаков, значимых для классификации объектов заданной обучающей выборки. Каждый признак представляет собой подграф, входящий хотя бы в один граф обучающей выборки, наличие или отсутствие которого позволяет отнести объект к тому или иному классу.

Для построения пространства признаков классификации предложен алгоритм FDET. Входными данными алгоритма являются графы обучающей выборки, выходными — дерево подграфов, в каждом узле которого находится уникальный элемент пространства признаков классификации. В статье приводятся ограничения, накладываемые на входные данные, описание алгоритма и его вычислительная сложность.

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

Список литературы:

  1. Воробьева М. С. Построение распределенного алгоритма поиска структурных различий в категориях изоморфизма / М. С. Воробьева, А. М. Воробьев, Ю. А. Егоров // Международный научно-исследовательский журнал. 2017. № 4 (58). Часть 4. С. 24-28.
  2. Егоров Ю. А. Модификация алгоритма Ульмана для многопроцессорных систем / Ю. А. Егоров // Материалы XVII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям, г. Новосибирск / Новосибирск: ИВТ СО РАН, 2016. С. 86-87.
  3. Захарова И. Г. Алгоритм поиска минимального пути в графе с динамически изменяющимися весами / И. Г. Захарова, И. А. Муравьев // Математическое и информационное моделирование. Издательство ТюмГУ, 2015. С. 173-179.
  4. Demiriz A. Linear Programming Boosting via Column Generation / A. Demiriz, K. P. Bennett, J. Shawe-Taylor // Machine Learning. 2002. Vol. 46. Pp. 225-254. DOI: 10.1023/A:1012470815092
  5. Saigo H. gBoost: A Mathematical Programming Approach to Graph Classification and Regression / H. Saigo, S. Nowozin, T. Kadowaki // Machine Learning. 2009. Vol. 75. Pp. 69-89. DOI: 10.1007/s10994-008-5089-z