Привет, Хабр!

ИТ-проекты – это далеко не только создание новых систем с нуля. Существенная часть специалистов занята поддержкой и сопровождением действующих систем. А когда в состав ИТ-системы добавляется новое ПО (или заменяется какой-то из её компонентов), актуальной задачей является перенос архивных данных и настройка взаимодействия нового софта с окружающим ландшафтом. При этом задачей-максимум является добавление новых свойств для системы, улучшающих пользовательский опыт или процессы администрирования и сопровождения. Ниже я расскажу, как мы провели классификацию объектов информационной модели при интеграции действующей системы расчета производственных показателей с внешней, вновь создаваемой системой управления НСИ.

Информационная модель обслуживаемой нами ИТ-системы расчета производственных показателей (название которой приводить не будем из-за NDA) состоит из порядка 10 тыс. объектов. Каждый объект используется для хранения данных – временных рядов суточных, месячных и т.п. значений. Структура объектов различается из-за различного состава настроенных в каждом из них атрибутов (т.е. различного состава временных рядов). Объект при этом или соответствует оборудованию реального мира, или введен в модель как группирующий элемент. Назначение ИТ-системы – периодическое (ежесуточное, ежемесячное) формирование множества сводных отчетов, при сохранении архива всех исходных и промежуточных рассчитанных данных.

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

На горизонте очередного обновления системы, встал вопрос о настройке взаимодействия с системой управления нормативно-справочной информацией (НСИ), для «наведения порядка» в информационной модели за счет введения в НСИ классов, и создания нового объекта только как экземпляра какого-либо класса.

Подготовка – выделение классов

Соответственно, нам необходимо классифицировать существующее множество объектов. Первый шаг – выяснить:

На сколько классов можно разбить множество объектов, по классифицирующему признаку – составу атрибутов у объекта?
Сколько объектов входят в каждый из классов?

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

В результате, получаем список классов, который для удобства вывода на экран (и иллюстрирования данной статьи) можно представить в виде таблицы и отобразить со скрытием строк в середине. Выделен 401 класс из 10 тысяч объектов. Максимальное число атрибутов в классе (колонка attsNum) – 35, минимальное – 1.

*Таблица (DataFrame), составленная из сформированных классов*

Для каждого класса приведен список атрибутов объектов данного класса, количество атрибутов и количество объектов, относящихся к данному классу (т.е. имеющих определенный в классе перечень атрибутов).

Далее – наиболее интересный вопрос: как можно организовать иерархию наследования из полученных классов?

Кластеризация. Зависимость результатов от алгоритма расчета «сходства»

Если рассматривать одиночное наследование, то это задача иерархической кластеризации. Применим агломеративный метод (объединение «снизу вверх»):

Сформируем матрицу сходства как отношение числа совпадающих атрибутов двух классов к максимальному количеству атрибутов у рассматриваемой пары классов. Полученная матрица будет выглядеть так:
Матрица сходства классов
Сформируем на её основе «матрицу различия» (иначе – матрицу расстояний) и далее «сжатую матрицу расстояний» (condensed distance matrix).
Используя Python-пакет scipy.cluster.hierarchy, сформируем матрицу связи (linkage matrix), для которой во всех примерах по иерархической классификации (и в коде для данной статьи) принято имя Z.
Построим и отобразим иерархию (дендрограмму), используя пакет matplotlib.pyplot.

*Полная иерархия классов в виде дендрограммы*

Для всех 401 классов дендрограмма выглядит как на рисунке выше – красиво! Но не информативно для человека, задача которого – настроить данную иерархию в системе управления НСИ.

Даже если отобразить дендрограмму на большей «подложке», так, чтобы номера (индексы) исходных классов на нижней оси были читаемыми – все равно, остается непонятным: какой набор атрибутов предлагается для каждого из создаваемых базовых классов?

Для того, чтобы ответить на данный вопрос, сначала необходимо уточнить принцип объединения классов в кластеры – или принцип «обрезки» дендрограммы.

Исходя из того, что мы строим иерархию классов, примем, что:

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

В этом случае приходим к тому, что первоначальная примененная нами формула расчета сходства («похожести») классов была неверной – т.к. по ней классы, например, с 29 и 30 атрибутами (из которых совпадают 25) более похожи друг на друга, чем классы с 2 и 3 атрибутами, у которых совпадают 2. Но при построении иерархии с наследованием важен минимальный абсолютный «шаг» добавления атрибутов, а не относительная доля совпадения.

Изменим формулу и будем рассчитывать сразу «степень несходства» как разность максимального числа атрибутов у пары классов и числа их совпадающих атрибутов.

В этом случае, дендрограмма выглядит следующим образом:

Дендрограмма, полученная при проведении кластеризации при изменении алгоритма формирования матрицы различия классов

Построение иерархии с одиночным наследованием классов

Чтобы лучше разобраться во взаимосвязях и отладить алгоритм построения иерархии, повторим построение матрицы различия и дендрограммы для меньшего набора исходных объектов (73 объекта, на основе которых сформировано 13 классов).Новая дендрограмма выглядит следующим образом:

*Дендрограмма для меньшего набора исходных данных*

Вся информация о взаимосвязях и последовательности выделения кластеров хранится в Z (матрице связи). На её основе, можно сформировать древовидную структуру, дополнив каждый элемент дерева (класс) информацией о его атрибутах (attrs):

*Бинарное дерево иерархической кластеризации*

Это бинарное дерево. Его листья – исходные элементы (выделенные при анализе массива объектов классы), узлы – полученные кластеры (предлагаемые базовые классы). Листья имеют исходный перечень атрибутов, выделенных при анализе информационной модели и формировании первоначального списка классов. Для каждого узла при построении этого дерева перечень атрибутов определен как пересечение множеств атрибутов группируемых им элементов.

Для того, чтобы данное дерево стало похоже на «обычную» иерархию классов, нам необходимо выполнить его дальнейшее преобразование:

Уйти от бинарности – если несколько последовательных шагов кластеризации было с одинаковым значением distance и прирастанием size по единице, то оставляем только кластер с наибольшим size, и включаем в него непосредственно исходные элементы, обработанные на данных шагах. (На дендрограмме такая ситуация видна как несколько (больше двух) элементов под общей горизонтальной линией).
Соответственно: делаем дерево не бинарным – переходим от left, right к children и в цикле по строкам Z, в последовательностях кластеров с одинаковыми distance и наборами атрибутов, и прирастанием size по единице, переносим все элементы непосредственно в наивысший кластер последовательности, а вложенные кластеры – удаляем.
Удалить элементы, перечень атрибутов которых совпадает с перечнем атрибутов группирующего их элемента (базового класса). (Такая ситуация возможна, когда у одного из двух классов, объединяемых в кластер на некотором шаге алгоритма кластеризации, перечень атрибутов является подмножеством перечня атрибутов второго класса).
В результате шагов 1 и 2, получим дерево:
Переформированное дерево иерархии классов
Для того, чтобы явно выделить добавляемые в производном классе атрибуты: добавим атрибут attrs_added, скроем attrs, size и distance, переименуем все узлы и листья (Cluster, Element) в классы.
Дерево иерархии классов

Можно даже автоматически сформировать UML-диаграмму наследования классов, используя инструмент генерации диаграмм, принимающий на вход описание на некотором структурированном языке разметки, например D2 ( https://d2lang.com/ ).

Результаты. Что дальше?

Мы получили:

Иерархию классов, которую можно использовать для настройки классификации объектов информационной модели в системах, которые поддерживают такую возможность, или при разработке собственной системы управления НСИ. (При этом, отметили важность использования наиболее адекватного для предметной области алгоритма расчета степени сходства/отличия классифицируемых эл��ментов).
Таблицу, где для каждого исходного объекта информационной модели указан определенный для него класс.

Вопрос к сообществу: а для каких еще ИТ-задач вы видите возможность / целесообразность применить подобный алгоритм формирования иерархии классов?

Для подготовки статьи использовался Google Colab. Исходный python-код (в основном, сформированный с помощью DeepSeek) и тестовый набор данных выложен на github.

Построение иерархии классов для множества объектов информационной модели