TY - JOUR

T1 - Бинарные метрические деревья и иерархия вложенных кластеров

AU - Орехов, Андрей Владимирович

AU - Васильев, Егор Владимирович

PY - 2024

Y1 - 2024

N2 - Методы машинного обучения используют деревья данных для организации и хранения информации. Каждая из таких структур обладает определенными преимуществами и позволяет улучшить качество конкретного алгоритма. Если у всех узлов дерева не более двух потомков, то оно называется бинарным; главное его преимущество — высокая эффективность реализации алгоритмов поиска и сортировки. В связи с этим важно отметить, что дендрограммы иерархических агломеративных методов кластеризации также относятся к бинарным деревьям и отражают таксономию элементов множества данных. Любой кластер, не являющийся синглетоном, можно разделить на подкластеры, что позволяет сформировать иерархическую структуру в метрическом пространстве (метрическое дерево) с дополнительными свойствами, например, автоматически задать высоту дерева, считая, по определению, что число уровней, на которых располагаются его узлы, совпадает с количеством вариантов разбиения выборочного множества на кластеры, подкластеры, подкластеры подкластеров и т. д. Такую задачу можно решить, используя аппроксимационно-оценочные критерии, изменение чувствительности которых при помощи коэффициента тренда дает возможность получить различные варианты кластеризации. При проведении вычислительных экспериментов использовалось синтетическое множество точек на евклидовой плоскости и изучались результаты его разбиения на кластеры центроидным методом. Марковские моменты остановки процесса кластеризации определялись посредством параболического аппроксимационно-оценочного критерия, построенного по четырем точкам. Верификация результатов, полученных при численном моделировании, производилась за счет изменения величины шага коэффициента тренда.

AB - Методы машинного обучения используют деревья данных для организации и хранения информации. Каждая из таких структур обладает определенными преимуществами и позволяет улучшить качество конкретного алгоритма. Если у всех узлов дерева не более двух потомков, то оно называется бинарным; главное его преимущество — высокая эффективность реализации алгоритмов поиска и сортировки. В связи с этим важно отметить, что дендрограммы иерархических агломеративных методов кластеризации также относятся к бинарным деревьям и отражают таксономию элементов множества данных. Любой кластер, не являющийся синглетоном, можно разделить на подкластеры, что позволяет сформировать иерархическую структуру в метрическом пространстве (метрическое дерево) с дополнительными свойствами, например, автоматически задать высоту дерева, считая, по определению, что число уровней, на которых располагаются его узлы, совпадает с количеством вариантов разбиения выборочного множества на кластеры, подкластеры, подкластеры подкластеров и т. д. Такую задачу можно решить, используя аппроксимационно-оценочные критерии, изменение чувствительности которых при помощи коэффициента тренда дает возможность получить различные варианты кластеризации. При проведении вычислительных экспериментов использовалось синтетическое множество точек на евклидовой плоскости и изучались результаты его разбиения на кластеры центроидным методом. Марковские моменты остановки процесса кластеризации определялись посредством параболического аппроксимационно-оценочного критерия, построенного по четырем точкам. Верификация результатов, полученных при численном моделировании, производилась за счет изменения величины шага коэффициента тренда.

KW - метрическое дерево

KW - агломеративная кластеризация

KW - марковский момент

KW - метод наименьших квадратов

UR - http://www.scopus.com/inward/record.url?partnerID=HzOxMe3b&scp=85215975933&origin=inward

U2 - 10.21638/spbu10.2024.405

DO - 10.21638/spbu10.2024.405

M3 - статья

VL - 20

SP - 487

EP - 499

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

SN - 1811-9905

IS - 4

ER -