Автоматика и телемеханика, № 11, 2019

Интеллектуальные системы управления,

анализ данных

(Институт проблем управления им. В.А. Трапезникова РАН, Москва)

ПРОЦЕДУРА КЛАССИФИКАЦИИ ОБЪЕКТОВ

С СЕМАНТИЧЕСКОЙ ИЕРАРХИЕЙ ПРИЗНАКОВ

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

структурой взаимоотношений (семантикой) признаков с учетом их мо-

дальностей. Понятия семантики признаков и их модальности объясня-

ются перед описанием самой процедуры. Рассматривается трехуровневая

модель с семантической иерархией признаков: «классифицируемые объ-

екты - метапризнаки - признаки объектов». Метапризнаки интерпрети-

руются как семантические обобщения относящихся к ним признаков объ-

ектов. Важным этапом предлагаемой процедуры является агрегирование

признаков нижнего уровня с учетом их семантической связи с метапри-

знаками. Агрегирование приводит к существенному уменьшению размер-

ности исходной задачи классификации, решаемой теперь в терминах зна-

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

ка Dermatology из известного репозитория UCI Machine Learning. На этом

примере показано, что несмотря на существенную несбалансированность

выборки Dermatology результаты применения предлагаемой процедуры

вполне сравнимы с лучшими результатами ряда известных алгоритмов

классификации, полученными на этой выборке.

Ключевые слова: субпризнак, метапризнак, семантическая иерархия при-

знаков, модальность признака, агрегирование, классификация.

DOI: 10.1134/S0005231019110084

1. Введение

Варианты постановок и решений задач классификации¹ существенным об-

разом зависят от структуры множества признаков классифицируемых объек-

тов² и иерархии классов, априори введенных на объектах исходной выборки.

Структура множества признаков (как и сами признаки) может быть раз-

ной для разных постановок задачи классификации. Так, при допущении, что

все признаки независимы и измеримы (в соответствующих шкалах), в каче-

стве модели исходных данных может быть выбрана так называемая «плос-

кая» (flat) модель [1]. Альтернативами «плоской» модели являются различ-

¹ В данной работе рассматривается только классификация «с учителем» (supervised

classification), предусматривающая наличие обучающей выборки, объекты которой одно-

значно принадлежат тому или иному классу введенного на выборке разбиения.

² Под объектом может пониматься некая сущность (физический объект, наблюдение и

т.п.), описываемая соответствующей совокупностью признаков из выбранного множества

признаков. В зарубежных работах «носители» признаков называются по-разному: object,

entity, instance и т.п. Далее для единообразия будет использоваться слово «объект».

140

ные иерархические модели, в которых каждый уровень иерархии характери-

зуется соответствующим распределением «признаков-классов» [1]. В данной

статье предполагается, что каждый объект описывается соответствующей со-

вокупностью признаков (которые могут принадлежать и другим объектам),

а классов - небольшое число и они независимы.

В последние десятилетия в работах по искусственному интеллекту (особен-

но в работах по классификации документов, изображений и т.п.) стало ши-

роко употребляться понятие семантики данных [2], семантики признаков [3]

и семантической иерархии признаков (СИП) [4]. Предпосылками для уче-

та СИП при классификации объектов с признаками различной физической

природы явились многочисленные примеры иерархии признаков от «простей-

ших» понятий (например, желтый, красный и т.д.) до более сложных (напри-

мер, цвет), которые «встраиваются» как промежуточные уровни в соответ-

ствующие иерархии [5, 6]. Как показано в работах [4, 7], при классификации

объектов, допускающих построение СИП, учет СИП улучшает результаты

классификации таких объектов по сравнению с использованием для их клас-

сификации «плоской» модели.

Следующим важным понятием в данной работе является понятие модаль-

ности признаков. Считается [8], что модальность признака определяется кон-

текстом исследуемой ситуации, в которой под модальностью признаков мо-

жет пониматься различие в смысловом раскрытии понятия того или ино-

го признака. Так, основными модальностями при классификации изображе-

ний [5] являются такие модальности как текстура, цвет, наличие геометриче-

ских особенностей в изображении (углов, прямых линий и т.п.). В медицине,

например, широко применяются так называемые мультимодальные исследо-

вания [6], в которых одновременно анализируются признаки с различными

модальностями (изображения, видео, текст). При этом согласно [6] качество

классификации состояния пациента намного лучше, чем в случае использо-

вания признаков только одной модальности.

В данной статье рассматривается процедура построения алгоритма клас-

сификации в случае, когда признаки объектов имеют разные модальности

и допускают построение СИП. Верхний уровень модели с СИП составляют

объекты - «носители» признаков, а нижний - сами «простейшие» признаки

с теми или иными значениями. На промежуточном уровне модели распола-

гаются так называемые метапризнаки, содержание каждого из них опреде-

ляется соответствующим множеством относящихся к данному метапризна-

ку «простейших» признаков нижнего уровня. Суть предлагаемого подхода к

классификации - обоснование перехода от большой совокупности «простей-

ших» признаков к гораздо меньшей совокупности метапризнаков путем соот-

ветствующих агрегирований признаков нижнего уровня с учетом семантики

взаимоотношений признаков среднего и нижнего уровней. Как указано в ра-

ботах [1, 9, 10], специфика агрегирования признаков при переходе к метапри-

знакам в структурах с СИП состоит в том, чтобы при агрегировании сохраня-

лась структура семантических связей между признаками нижнего и среднего

уровней. В [11, 12] описываются требования, которым должна удовлетворять

выбираемая функция агрегирования и сама процедура выбора. В частности,

в такой функции должны учитываться совокупные эффекты, обусловленные

141

«горизонтальными» взаимовлияниями признаков на одном и том же уровне, и

такие совокупности признаков должны входить в область определения функ-

ции агрегирования. Известные методы уменьшения размерности, такие как

LLE (метод локального линейного вложения, local linear embedding), ISOMAP

и другие методы, анализируемые в [13], широко используются в различных

задачах. Однако, как указывается в [14], в подобных методах не учитыва-

ются семантические зависимости между переменными различных уровней и

различных модальностей, все такие переменные «сливаются» в переменные

пространств меньшей размерности.

Цель настоящей работы состоит в том, чтобы на примере простейшей трех-

уровневой структуры с СИП продемонстрировать основные этапы процедуры

классификации объектов:

— обоснование вводимых элементов промежуточного слоя;

— формирование модели с СИП для каждого объекта;

— выбор функций агрегирования признаков нижнего уровня;

— решение исходной задачи классификации в терминах значений исполь-

зуемых функций агрегирования с учетом указанных выше требований на

взаимоотношения переменных разных уровней.

В качестве иллюстративного примера рассматривается выборка

Dermatology из известного репозитория UCI Machine Learning [15], опи-

сывающая диагностику 6 видов кожных заболеваний у 343 пациентов на

основе 34 клинических и гистопатологических анализов. Показано, как по

этой выборке строится модель с СИП и как вводимое в модель агрегирование

уменьшает размерность исходной задачи классификации.

Работа построена следующим образом. Во введении приводятся необхо-

димые определения, связанные с СИП, и кратко представлен круг работ по

вопросам семантической иерархии и агрегирования. В разделе 2 подробнее

раскрываются формальные понятия, входящие в описание модели с СИП.

В разделе 3 обсуждается тип функций агрегирования, используемых для аг-

регирования признаков нижнего уровня. В разделе 4 представлена упрощен-

ная версия алгоритма классификации из работы [16], адаптированная для

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

ций агрегирования, а в разделе 5 оценивается вычислительная сложность

предложенной процедуры. В разделе 6 описывается применение этой проце-

дуры к выборке Dermatology. Особенности данной процедуры, важные при

рассмотрении практических задач, обсуждаются в разделе 7. В заключение

делаются выводы о возможных применениях предложенного подхода.

2. Определение модели с СИП

Прежде всего, подробнее определим понятие модели с СИП. Пусть задана

совокупность S из n объектов, которые необходимо классифицировать. Каж-

дый из объектов описывется соответствующей совокупностью признаков, воз-

можно, разных модальностей, называемой описанием объекта. Обозначим че-

рез N₀ мощность объединения X₀ всех признаков. Иерархическая модель H_i

с СИП строится для каждого объекта O_i, i ≤ n. На верхнем уровне модели H_i

располагается сам объект O_i. Второй уровень модели содержит m метапри-

142

знаков M₁, . . . , M_m, где m зависит от специфики рассматриваемой задачи

(так, например, в приводимой ниже выборке Dermatology метапризнаками

являются возможные виды заболеваний). Будем считать, что множество ме-

тапризнаков {M₁, . . . , M_m} сопоставляется каждому объекту из S. При этом

если описание объекта O_i, i ≤ n не содержит некоторого метапризнака M_u,

u ≤ m, полагаем M_u = 0 в модели H_i. Каждому ненулевому метапризнаку M_j

в модели H_i однозначно сопоставляется множество G_ij «простейших» призна-

ков нижнего уровня (для простоты называемых субпризнаками). Все элемен-

ты множества G_ij суть значения признаков из описании объекта O_i. При этом

каждый субпризнак из G_ij может входить в описания других объектов из S,

и соответственно - в другие множества³ G_is, . . . , G_ik. Однозначность отнесе-

ния множества G_ij к метапризнаку M_j говорит о том, что все субпризнаки

из G_ij имеют семантические связи с M_j , а некоторые субпризнаки из G_ij -

и с другими метапризнаками.

Переменные разных уровней в модели H_i могут анализироваться «сверху-

вниз» или «снизу-вверх». Для наглядности направление исследуемого соот-

ношения указывается направлением соответствующей стрелки ↓ или ↑. Мо-

дель H_i может быть представлена следующим образом:

{

O_i ↓ {M_j}mj=1 ↓ {G_ij}mj=1 ↓

{x_ijk}Nj

}^m ,

k=1

j=1

где x_ijk - элементы множества G_ij с мощностью N_j.

В плане дальнейшего перехода к классификации объектов из S рассмот-

рим, как распределяются метки (labels) классов на уровнях модели H_i. До-

пустим, что на исходной совокупности объектов S введено некоторое раз-

биение π на K (K ≤ m) блоков (классов), и пусть объект O_i принадлежит

ν-му классу C_ν (т.е. имеет метку ν). Эта метка переносится и на субпризнаки

из G_ij , входящие в описание объекта O_i. Заметим, что поскольку субпризнаки

из G_ij могут входить в описания и других объектов из S, скажем, объекта O_r,

входящего в блок C_μ разбиения π, таким субпризнакам кроме метки ν при-

писывается и метка μ, так что каждый субпризнак из G_ij может иметь, в

принципе, несколько меток (такая совокупность меток называется в лите-

ратуре bag of labels). Метки каждого субпризнака из G_ij переносятся и на

те метапризнаки M_j , . . . , M_k, с которыми данный субпризнак семантически

связан. Этот факт учтем в виде соотношения

(1)

↑ {O_p}rp=1

↑ {ν}.

Здесь {O_p}rp=1 - совокупность объектов, в описания которых входят призна-

ки, семантически связанные с M_j , . . . , M_k, а {ν} - множество меток таких

объектов, включающее метку ν объекта O_i. Аналогично строятся модели H_r

для остальных объектов H_r, r = 1, . . . , n из S. Далее считаем выполненными

следующие условия:

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

симптом (субпризнак) может относиться к разным заболеваниям - см. приведенный ни-

же пример. На этапе классификации такие неоднозначности учитываются и усложняют

выработку диагноза.

143

1. Все модели H_r, r = 1, . . . , n изначально отличаются только значениями

субпризнаков нижнего уровня и структурой семантических связей субпри-

знаков с соответствующими метапризнаками (нулевые значения на втором и

третьем уровнях допустимы).

2. Субпризнаки с неопределенными или неизвестными значениями не до-

пустимы.

3. Каждый объект исходной совокупности S принадлежит однозначно к

тому или иному классу разбиения π = (C₁, . . . , C_K ), классы взаимно незави-

симы и K ≤ m⁴.

Ключевой момент предлагаемого подхода к классификации структур с

СИП состоит в агрегировании субпризнаков в каждом из множеств G_ij ,

i = 1,...,n, j = 1,...,m и переходе от пространства исходных признаков

большой размерности N₀ к пространству значений функций агрегирования

гораздо меньшей размерности m. Предварительная подготовка исходных дан-

ных к запуску процедуры классификации состоит в прохождении следующих

этапов: а) нормализация субпризнаков в каждом множестве G_ij , i = 1, . . . , n,

1 ≤ j ≤ m и выбор функций агрегирования; б) нахождение значений функ-

ций агрегирования для каждого множества G_ij ; в) определение каждой мо-

дели P_i, i = 1, . . . , n, являющейся модификацией соответствующей модели H_i

в терминах найденных значений функций агрегирования.

3. Выбор функций агрегирования для субпризнаков

Этапы выбора функций агрегирования для субпризнаков:

а. Поскольку значения субпризнаков в каждом множестве G_ij могут из-

начально выбираться из разных шкал, перед агрегированием субпризна-

ки необходимо их нормализовать. Нормализация проводится по правилу

y_ijk

∑_n

, где каждая нормализованная величина y_ijk есть доля ис-

x_sjk

s=1

ходного значения субпризнака x_ijk из G_ij в сумме (по всем объектам сово-

купности S) значений этого субпризнака. Подчеркнем, что нормализующий

множитель

∑n

для каждого признака X_k ∈ X₀, входящего (с разными

s=1

x_sjk

значениями) в множества G_ij , 1 ≤ j ≤ m, i = 1, . . . , n, один и тот же. Распре-

деление нормализованных значений {y_ijk}, k = 1, . . . , N на множестве G_ij не

является вероятностным, поскольку сумма (по k) переменных {y_ijk} в общем

случае не равна единице.

б. Выбираемая функция агрегирования должна быть чувствительной к

распределению и значениям ненулевых агрегируемых переменных. В случае

вероятностного распределения таких значений можно использовать инверс-

ную энтропию [17] (энтропию со знаком плюс). По аналогии с [17] функцию

агрегирования переменных_ijk y_ijk в множествах G_ij определим как

⎛

⎞

N_j

∑

(2)

Fij (yij1, . . . , yijN_j ) =^⎝-

y_ijk log₂(y_ijk)|y_ijk > 0^⎠ .

k=1

⁴ Случай K > m имеет особенности, требующие отдельного рассмотрения.

144

Для удобства отображение

(2) назовем псевдоэнтропией. Отображение

Fij : [0, 1]Nj → R является нелинейным монотонным неубывающим отобра-

жением. Функция F_ij переводит вектор (yij1, . . . , yijNj ) в соответствующее

положительное число w_ij ∈ R, которое назовем весом метапризнака M_j в объ-

екте O_i выборки S. Аналогичным образом найдем веса w_ij для всех метапри-

знаков M_j , j = 1, . . . , m, i = 1, . . . , n. Отличие модели P_r от модели H_i лишь

в том, что элементы {M₁, . . . , M_m} второго уровня заменяются значениями

соответствующих весов w_rj. Строку весов, сопоставляемых объекту O_i, обо-

значим как W_i = {w_ij }, j = 1, . . . , m.

4. Процедура классификации объектов

с использованием весов метапризнаков

4.1. Разбиение исходной совокупности S

на обучающую и тестовую выборки

Классификация (supervised) объектов предусматривает разбиение исход-

ной совокупности S на обучающую выборку (ОВ) и тестовую выборку (ТВ),

которые содержат n_ОВ и n_ТВ объектов соответственно. При этом все объек-

ты сохраняют те же метки, что и ранее в совокупности S. Другими словами,

разбиение π разделяется на два подразбиения π_ОВ и π_ТВ с выполнением сле-

дующих важных требований:

Требования к формированию ОВ и ТВ.

а. Каждый класс подразбиения π_ТВ должен иметь непустое пересечение с

каким-либо классом подразбиения π_ОВ.

б. Модели для объектов O_i из ОВ и ТВ являются теми же, что и ранее

построенные модели H_i для этих объектов из S. в. Метки объектов из ТВ не

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

ся лишь при определении точности классификации построенного алгоритма.

Задача классификации объектов с СИП формулируется следующим обра-

зом. Метки объектов из ОВ априори считаются известными. Метка ν объек-

та O_i из ОВ переносится на компоненты соответствующего этому объекту O_i

вектора весов W_i = {w_ij }, j = 1, . . . , m, так что соотношение (1) для объек-

та O_i выглядит так:

O_i ↓ {w_j}mj=1 ↓ ν.

Метки для объектов из ТВ определяются вхождением этих объектов в тот

или иной блок подразбиения π_ТВ. Для удобства при рассмотрении моделей из

ТВ все элементы снабжаются штрихами. При этом функция агрегирования

субпризнаков в G^′pj определяется по аналогии с (2) как

⎛

⎞

N^′j

∑



F^′ij(y′ij1,... ,y^′ijN′ ) =^⎝-

y^′ijt log₂(y^′ijt)y′

>0^⎠.

ijt

t=1

Поскольку значения субпризнаков в моделях объектов из ОВ и ТВ могут не

совпадать, для корректного сравнения значений весов w_ij и w^′ij, получаемых с

применением функций агрегирования F_ij и F^′ij , нормализующий множитель

145

∑n

для субпризнаков из G^′ij должен быть тем же самым, что и при

x_sjk

s=1

нормализации субпризнаков в G_ij .

4.2. Классификация объектов ТВ с использованием весов метапризнаков

Ниже с краткими комментариями приводятся основные этапы алгоритма

из [16] с адаптацией к классификации объектов в терминах весов метапри-

знаков.

Пусть Z - тестовый объект, модель H_Z для которого характеризуется век-

тором весов метапризнаков W^′Z = (w′Z1, . . . , w^′Zm). Перечислим основные эта-

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

сти как ААК.

А. Определение понятия “допустимой близости” для весов метапризна-

ков. Для каждого метапризнака M_j определяются его максимальный mmaxj

и минимальный mminj веса по всем объектам из S. Разность этих значений

делится на некоторое выбираемое число h (о выборе значения h будет сказано

далее в п. Д). Обозначим d_j =wmaxj -wminjh.Двазначенияwrjиwsj^{назовем}

d_j-близкими, если модуль их разности не больше d_j. Для простоты будем

считать, что h не зависит от j.

Б. Построение матрицы весов для тестового объекта Z. Пусть w^′Zj —

вес метапризнака M_j в объекте Z. Совокупность весов метапризнака M_j

в объектах из ОВ, таких что эти веса d_j -близки к значению w^′Zj, назовем

d_Zj-окрестностью значения w^′Zj. Множество объектов из ОВ, образующих

d_Zj-окрестность значения w^′Zj, обозначим как U(w^′Zj,d_j), совокупность ве-

сов метапризнаков объектов из множества U(w^′Zj , d_j ) — как V (w^′Zj , d_j ), а со-

вокупность меток объектов из U(w^′Zj , d_j ) — как L(w^′Zj, d_j ). Пусть N_Zjν —

число объектов из U(w^′Zj, d_j ), входящих в блок C_ν разбиения π_ОВ. Сопоста-

N_Zjν

вим значению w^′Zj число⁵ g_Zjν =

, где | ∗ | обозначает мощность

|U(w^′Zj,dj)||C∇|

соответствующего множества. Найденное число g_Zjν будем рассматривать

как вес метки ν в множестве L(w^′Zj , d_j ) . Подобным образом найдем мно-

жество N_Zjμ объектов из U(w^′Zj, d_j ), принадлежащих классу C_μ, μ = ν, и вы-

числим вес g_Zjμ каждой метки μ (μ = 1, . . . , K). Сформируем столбец весов

меток G_Zj = (gZj1, . . . , g_ZjK )^T для веса w^′Zj метапризнака M_j в объекте Z.

Заметим, что все координаты в G_Zj — неотрицательные и не большие еди-

ницы. Столбец весов G_Zj можно интерпретировать как локальный (по мета-

признаку M_j ) классификатор для объекта Z. Аналогичным образом найдем

векторы-столбцы весов для ненулевых значений всех m метапризнаков объ-

екта Z и сгруппируем эти столбцы в матрицу Q_Z размера K × m, которую

назовем матрицей весов меток метапризнаков в объекте Z.

В. Определение метки для тестового объекта Z. Интерпретируем мат-

рицу Q_Z как совокупность локальных классификаторов (по метапризнакам

объекта Z). В [18] говорится о том, что классифицирующая способность объ-

единения локальных классификаторов может быть усилена путем их взве-

шивания (combining) с использованием какой-либо нелинейной монотонной

⁵ В [16] объясняется структура коэффициента gZ_j.

146

функции. В качестве такой функции взвешивания Φ_Zμ по каждой стро-

ке G_Zμ с номером μ в матрице Q_Z возьмем функцию того же типа, что и

Fij (см. (2)), и применим еe к каждой строке GZμ матрицы QZ . Сформируем

вектор R_Z = E(G_ZK ), который назовем классифицирующим вектором для

объекта Z. Номер координаты вектора R_Z с наибольшим значением считаем

меткой, приписываемой тестовому объекту Z. Аналогичным образом произ-

водится классификация остальных объектов ТВ.

Г. Параметры классификации. Тестовый объект Z считается правильно

классифицированным, если его метка, найденная в п. В, совпадает с мет-

кой этого объекта в подразбиении π_ТВ. Точность классификации определя-

ется как отношение правильно классифицированных объектов ТВ к общему

количеству объектов ТВ. При анализе алгоритма классификации в первую

очередь обращается внимание на значение точности классификации. Однако

точность классификации является лишь одним из качеств алгоритма клас-

сификации. При наличии более двух классов с сильно различающейся мощ-

ностью основную “нагрузку” при классификации может брать на себя класс

с наибольшей мощностью, и высокий процент правильной классификации

может не означать хорошей классификации объектов в классах с неболь-

шой мощностью, хотя во многих практических задачах именно такие классы

представляют особый интерес. Подобный случай рассматривается в приво-

димом ниже примере (см. раздел 7). Классификация в случае сильно несба-

лансированных выборок представляет отдельное направление в классифика-

ции, в рамках этого направления известно много публикаций. В ААК пред-

лагается использовать следующую меру ρ_ТВ наполняемости блоков разбие-

∑_K′

|C′0ν|

ния π_TB = (C′1, . . . , C′K′ ): ρ_TB =

, где |C′0ν | - количество правиль-

ν=1 |C^′ν|

но классифицированных объектов в классе C^′ν . Значения показателя ρ_ТВ

определены в интервале [0, K^′]. Чувствительность меры ρ_ТВ к наполнению

того или иного класса обратно пропорциональна мощности наполняемого

класса.

Д. Выбор значения параметра h существенным образом влияет на точ-

ность классификации в ААК, поэтому достижение «приемлемого» значения

точности классификации определяет окончательное значение h. Это - типич-

ный подход «с обратной связью» (wrapper approach). При условии, что вы-

бор значения h не зависит от метапризнаков объектов, процедура выбора h

может быть сведена к простейшему одномерному поиску [16]. При переходе

к использованию весов метапризнаков исходная задача превращается в стан-

дартную задачу классификации, которую можно решать в рамках «плоской»

модели «объекты - метапризнаки» с применением любого алгоритма класси-

фикации. Однако в данной работе используется алгоритм из [16], поскольку

он обладает рядом практически важных особенностей, обсуждаемых в раз-

деле 7.

5. Оценка вычислительной сложности предложенного алгоритма

Описанная выше процедура классификации объектов с СИП состоит из

двух последовательных частей: а) агрегирование входной информации на ОВ

147

и ТВ; б) решение задачи классификации с использованием весов метапри-

знаков. Пусть, как и ранее, N₀ - размерность пространства всех субпризна-

ков. При агрегировании рассматриваются значения каждого субпризнака по

всем объектам ОВ и ТВ. Для простоты положим, что ОВ и ТВ имеют по

n объектов, тогда вычислительная сложность этапа агрегирования оценива-

ется как O(2nN₀). ААК представляет собой сложный цикл, в котором для

каждого объекта ТВ рассматриваются все объекты ОВ и для каждой па-

ры объектов производится сравнение значений каждого из m соответствую-

щих весов метапризнаков на предмет их «допустимой близости». Положим,

что для определения «приемлемого» значения параметра h, определяющего

значение d(h)-близости, полный цикл ААК повторяется q раз, q ≤ m. Тогда

вычислительная сложность этапа б) оценивается как O(n²mq) или, с уче-

том того, что q ≤ m, - как O(n²m²). Для оценки всей процедуры необходимо

рассмотреть асимптотическое поведение функции nN₀ + n²m². При выполне-

нии условия N₀ < nm² с учетом замечаний, сделанных в [19], вычислительная

сложность всей процедуры оценивается как O(n²m²). Если же рассматривать

задачу классификации в рамках «плоской» модели (без агрегирования) с ис-

пользованием алгоритма из [16] , то вычислительная сложность алгоритма

классификации оценивается как O(n²N²⁰) при условии, что N₀ > qm. Таким

образом, агрегирование уменьшает вычислительную сложность задачи клас-

(_N

)₂

сификации в отношении порядка

6. Пример

В качестве примера, на котором демонстрируется эффективность предло-

женной процедуры классификации, использовалась выборка Dermatology из

репозитория UCI Machine Learning [15]. В этой выборке представлены резуль-

таты 34 клинических анализов (наличие сыпи или покраснений на коже, тем-

пература тела и т.п.) и гистопатологических анализов (шелушение, соскаб-

ливания, биохимия и т.п.), проведенных над 343 пациентами с целью опреде-

ления (классификации) у них тех или иных кожных заболеваний из 6 видов

возможных заболеваний. Более подробная информация о связи тех или иных

результатов анализов с конкретным видом заболевания, представляющая ин-

терес для читателя, содержится в [20, 21]⁶. Значения каждого из анализов у

каждого пациента определялись в единой качественной шкале (0, 1, 2, 3), где

0 означает отсутствие данного анализа у исследуемого пациента. Поскольку

тот или иной анализ в общем случае не достаточен для однозначного ука-

зания вида заболевания, предварительно исследовалась «неоднозначность»

каждого из анализов, и для каждого вида заболевания формировалось мно-

жество соответствующих анализов (без учета их значений), возможно связан-

ных с этим заболеванием. Гистограмма количества таких связей для каждого

из анализов представлена в [21]. По причинам, не относящимся к тематике

данной статьи, из исходного множества анализов были удалены анализы с

номерами 1, 2, 11, 13, 17, 18, 32, 34. Из оставшихся 26 анализов были вы-

делены 6 совокупностей анализов, каждая из которых, возможно, связана

⁶ В частности, в [20] более подробно указано, какие признаки и каких кожных заболе-

ваний являются клиническими, а какие - гистопатологическими.

148

Таблица 1. Совокупности упорядоченных по «важности» анализов

для соответствующих видов заболеваний

Номер вида

Номера анализов

заболевания

20, 22, 21, 28, 16, 10, 9, 19, 24, 3, 26, 29, 6, 33, 12, 27

28, 20, 22, 5, 26, 21, 9, 24, 27, 16, 29, 6, 12, 25, 8, 33

33, 27, 29, 6, 12, 25, 8, 21, 14, 20, 22, 16, 9, 10, 4, 23

21, 9, 20, 22, 10, 28, 33, 27, 6, 12, 25, 8, 23, 29, 24, 4

15, 5, 14, 20, 10, 9, 22, 26, 28, 24, 27, 29, 6, 12, 25, 33

7, 31, 5, 22, 26, 21, 24, 30, 27, 29, 6, 12, 8, 15, 33,19

Таблица 2. Мощности классов разбиений π_ОВ и π_ТВ

π_ОВ

π_ТВ

{C′0ν}

с соответствующим видом заболевания (см. табл. 1). Анализы в каждой из

этих совокупностей упорядочивались по «важности» при отнесении их к ука-

занному виду заболевания⁷.

В терминах моделей с СИП все входящие в выборку Dermatology анализы

интерпретируются как субпризнаки с разными значениями для разных па-

циентов, а виды заболеваний - как метапризнаки. При этом согласно табл. 1.

тот или иной субпризнак может соответствовать нескольким метапризнакам.

Множество пациентов в выборке Dermatology можно рассматривать как вы-

борку S, в которой каждому пациенту соответствует определенная строка в

выборке S. Состояние каждого пациента характеризуется конкретной сово-

купностью ненулевых анализов. По этой совокупности с привлечением кон-

силиума врачей для каждого пациента был указан диагноз, т.е. конкретный

вид заболевания из 6 возможных видов. В терминах задачи классификации

такой диагноз интерпретируется как приписывание соответствующей метки

каждому пациенту, а совокупность таких меток на множестве пациентов -

как введение разбиения π на выборке S. При этом каждый пациент одно-

значно относится к некоторому классу C_ν разбиения π, т.е. характеризуется

меткой ν. Таким образом, исходная информация вполне достаточна для при-

менения описанной выше процедуры классификации.

По исходной выборке S сформируем ОВ и ТВ путем попеременного отне-

сения очередного пациента к ОВ или ТВ и определим разбиения π_ОВ и π_ТВ

с соблюдением указанных в разделе 4.1 требований. Мощности классов этих

разбиений приведены в первых двух строках табл. 2. Видим, что ОВ и ТВ яв-

ляются несбалансированными выборками, поскольку число элементов самого

крупного блока разбиения π_ОВ и π_ТВ превышает число элементов самого мел-

кого блока более чем в 9 раз. Точность классификации ААК, описанного в

разделе 4.2 и примененного к объектам ТВ, составляет 94,7%. При этом чис-

ло правильно классифицированных объектов в каждом блоке разбиения π_ТВ

⁷ В силу агрегирования субпризнаков в моделях с СИП подобная упорядоченность далее

не используется (см. раздел 7).

149

Таблица 3. Сравнительные оценки точности классификации некоторых алгорит-

мов на выборке Dermatology

Алгоритм

«Наивный

Дерево

kNN

ЛДА

VFI5

ААК

классификации

Байес»

решений

Точность классификации (%)

97,2

98,3

96,1

98,3

96,2

94,7

представлено в третьей строке табл. 2, а определенный в разделе 4.2 коэф-

фициент ρ_ТВ заполнения блоков разбиения π_ТВ равен 5,47, что говорит о

хорошем качестве заполнения блоков разной мощности⁸. В табл. 3 приведе-

ны заимствованные из [21] данные о точности классификации на ТВ⁹ ря-

да известных алгоритмов (в том числе алгоритма VFI5, описанного в [20],

и ААК), в которых использовались 6 множеств признаков, приведенных в

табл. 1. Сокращенные названия алгоритмов в табл. 3: kNN - некоторый алго-

ритм из семейства kNN-алгоритмов, базирующихся на понятии «ближайшей

окрестности», а ЛДА - линейный дискриминантный анализ. Согласно табл. 3

точность классификации ААК несколько меньше, чем в приведенных алго-

ритмах, однако ААК обладает рядом положительных качеств при решении

практических задач, эти качества обсуждаются в разделе 7.

7. Практически важные особенности ААК

Обсуждаемые ниже особенности ААК включают: 1) качество классифика-

ции на существенно несбалансированных выборках; 2) уменьшение размерно-

сти множества данных на этапе классификации; 3) ослабление контекстной

зависимости модальностей субпризнаков в ААК.

1. Качество классификации ААК на существенно несбалансированных вы-

борках. Если исходная выборка является существенно несбалансированной

выборкой (как в приводимом выше примере), то высокая точность классифи-

кации в целом может не означать хорошей классификации объектов в классах

с небольшой мощностью. Поясним эту мысль на приведенном выше примере.

Здесь ААК обеспечил неплохое качество заполнения наименьшего блока C₆

разбиения π_ТВ, классифицировав правильно три объекта из четырех. Непло-

хое качество заполнения мелких блоков показал и исходный алгоритм ав-

тора [16] на ряде существенно несбалансированных выборок из репозитория

UCI Machine Learning. Это свойство исходного алгоритма и ААК допускает

следующее объяснение.

Общий подход к построению алгоритмов классификации (supervised) со-

стоит в том, что каждому объекту из ОВ «навешивается» метка класса задан-

ного разбиения π_ОВ, и далее этим меткам приписываются веса, вычисляемые

тем или иным образом. Поскольку при каждом разбиении исходной выбор-

ки на ОВ и ТВ в каждой из них - конечное число объектов, каждой метке

класса при каждом разбиении соответствует некоторое конечное множество

⁸ Это же свойство алгоритма, описанного в [16], проявлялось и при рассмотрении ряда

сильно несбалансированных выборок из репозитория UCI Machine Learning.

⁹ Как сказано в [21], ОВ и ТВ составляли по 50% исходной выборки Dermatology.

150

объектов исходной выборки с точечными значениями признаков¹⁰. Посколь-

ку точность классификации на конкретной выборке зависит от количества

объектов в ОВ и ТВ, для обоснования результирующей точности классифи-

кации используют разные процедуры разбиений (butstrap, boosting и т.п.).

Однако в таких процедурах каждой метке будет соответствовать другое, но

конечное множество признаков с точечными значениями. Отличие алгорит-

ма из работы

[16] и ААК от известных алгоритмов состоит в том, что для

всякого значения количественного или качественного признака из ТВ зада-

ется непрерывная окрестность «допустимо близких» к нему значений этого

же признака из ОВ. (см. раздел 4.2, п. Д). При этом каждой метке будет

соответствовать результирующее конечное множество интервалов значений

этого признака. Поскольку проблема построения алгоритма с оптимальным

значением точности классификации в классе обычно используемых выборок

является, как известно, NP -полной, о превосходстве того или иного подхода

к построению алгоритма можно судить лишь по полученным результатам на

используемом множестве выборок.

В приводимом выше примере ААК позволяет вместо значений 26 каче-

ственных признаков рассматривать 6 весов метапризнаков как значений ис-

пользуемых функций агрегирования. Совокупность классов на ТВ, содер-

жащей 171 объект, имеет вид (см. табл. 2): C₁ = 52, . . . , C₆ = 4, т.е. число

элементов в максимальном блоке превышает число элементов в минималь-

ном блоке более чем в 13 раз). Точность классификации ААК на ТВ равна

94,7%. Заметим, что правильная классификация каждого из трех объектов

блока C6 «забирает» 100(3 : 171 ) ≈ 1,7% от полной точности классификации.

Согласно табл. 3 максимальная точность классификации двух известных ал-

горитмов классификации («Наивный Байес» и Дерево решений) на той же

ТВ равна 98,3%. Отсюда следует, что такая точность классификации каж-

дого из этих алгоритмов может быть достигнута и при полном «игнорирова-

нии» блока C₆ вместе с правильной классификацией объектов в остальных

блоках ТВ, поскольку 100% - 1,7% ≈ 98,3% (это тем более справедливо для

остальных алгоритмов из табл. 3). При этом согласно табл. 2 ААК правильно

классифицирует 3 из 4 элементов в блоке C₆.

2. Уменьшение размерности множества данных на этапе классификации.

В силу агрегирования субпризнаков в каждом из множеств, семантически

связанных с соответствующими метапризнаками, размерность множества

(_N

)₂

значений m функций агрегирования уменьшается в

раз по сравнению

с размерностью N₀ множества субпризнаков.

3. Ослабление контекстной зависимости модальностей субпризнаков в

ААК. Во многих практических задачах (особенно в медицине) значения суб-

признаков на ОВ и ТВ определяются приближенно (в качественных шкалах),

что имеет место и в рассмотренном выше примере. В то же время известно,

что такой популярный подход как построение дерева решений крайне чув-

ствителен к возмущениям значений признаков из ОВ. Теоретический анализ

качества алгоритмов классификации (supervised) в рамках статистического

¹⁰ Особняком здесь стоит алгоритм VFI5, описанный в [20], в котором для каждой метки

вычисляются интервалы значений каждого признака объектов из ОВ.

151

подхода представлен в работе [22] в предположении, что вероятностные рас-

пределения значений признаков статистически эквивалентны на ОВ и ТВ.

Однако это предположение, как правило, не выполняется в практических за-

дачах (в частности, в приводимом выше примере). В устройствах обработки

информации с помехами для повышения помехоустойчивости давно применя-

ется агрегирование, реализуемое на сумматорах различных видов. При этом,

как правило, не обращается внимание на модальности агрегируемых сигна-

лов.

Во многих практических задачах модальность признака зависит от его

значений, при этом понятие модальности становится контекстно зависимым

(context sensitive). Нормализация субпризнаков и их последующее агрегиро-

вание в каждом из множеств G_ij позволяет несколько уменьшить взаимо-

влияния субпризнаков в множествах G_ij . Поскольку и нормализация, и аг-

регирование проводятся для тех же субпризнаков в ТВ, распределения мо-

дальностей субпризнаков в соответствующих множествах G_ij и G^′ij могут не

совпадать, как и значения соответствующих весов w_ij и w^′ij. Наличие меток

разбиения π_ОВ на субпризнаках из ОВ «удаляет» эту проблему, так как всем

субпризнакам из множества G_ij , относящегося к объекту O_i с меткой ν, при-

писывается метка ν (как и всему вектору весов W_i = {w_ij }, j = 1, . . . , m, и

приписывание другой метки μ весу w^′ij зависит лишь от «допустимой бли-

зости» веса w^′ij к w_ij. Таким образом, наличие известного разбиения на ОВ

является очень важной «подсказкой» при построении алгоритмов классифи-

кации для моделей с СИП.

И еще одно важное замечание относительно упорядочения анализов по

«важности» в строках табл. 1. Можно заметить, что и в [20], где подробно

описывается алгоритм VFI5, и тем более в ААК не используется такое упо-

рядочение. Оно крайне важно лишь на этапе выработки исходного диагноза

для каждого пациента, и становится ненужным на этапе классификации, ко-

гда метка для каждого пациента уже определена. Подобный процесс упоря-

дочения анализов по «важности» довольно сложный и ответственный, тогда

как наличие исходных меток на объектах выборки существенно упрощает

применение алгоритмов классификации.

8. Заключение

Описанная в настоящей статье процедура классификации объектов с СИП

предусматривает выполнение двух необходимых условий:

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

субпризнаков с метапризнаками, к которым они относятся;

- нормализующие множители для субпризнаков из соответствующих мно-

жеств G_ij и G^′ij в ОВ и ТВ совпадают.

Несмотря на простоту иерархии моделей с СИП, практические особенности

процедуры классификации объектов с СИП, приведенные в разделе 7, поз-

воляют применять эту процедуру для проведения классификации во многих

многомерных задачах, в которых понятия семантической связи и модально-

сти переменных имеют существенное значение (в частности, в медицинских,

финансовых и социальных задачах).

152

СПИСОК ЛИТЕРАТУРЫ

Borges H.B., Silla C.N., Nievola J.C. An evaluation of global-model hierarchical

classification algorithms for hierarchical classification problems with single path of

labels // Comp. Math. Appl. 2013. V. 66. P. 1991-2002.

https://www.sciencedirect.com/science/. . . /S08981221130043.

Liu H. Towards Semantic Data Mining // www.ceur-ws.org/Vol-660/paper6.pdf

Motik B., Maedche A., Volz R. A Conceptual Modeling Approach for Semantics-

Driven Enterprise Applications // Proc. Meaningful Internet Syst. 2002. P. 1082-

1099. www.citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.10

Albaradei S., Wang Y. Object Classification Using a Semantic Hierarchy //

www.cs.umanitoba.ca/˜ywang/papers/isvc14_hierarchy.

Fatimaezzahra M., Abdelaziz E., Mohamed S., Loubna B. Towards Domain Ontology

Creation Based on a Taxonomy Structure in Computer Vision // Int. J. Adv.

Comput. Sci. Appl. (IJACSA). 2016. V. 7. No. 2. P. 28-43.

https://thesai.org/Downloads/Volume7No2/Paper_38-Towards. . .

Wang Y., Halper M., D. Wei D., Perl Y., Geller J. Abstraction of complex concepts

with a refined partial-area taxonomy of SNOMED // J. Biomed. Inform. 2012. V. 45.

P. 15-42. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3313654

Ciaramita M., Hofmann T., Johnson. M. Hierarchical Semantic Classification: Word

Sense Disambiguation with World Knowledge // https://pdfs.semanticscholar.org/

faa4/a19f4edd1d97a09

Deng W.-Y., Liu D., Dong Y.-Y. Feature Selection and Classification for High-

Dimensional Incomplete Multimodal Data // Math. Probl. Eng. 2018. V. 2018.

Article ID 1583969. 9 pages. https://doi.org/10.1155/2018/1583969

Fernandez M.J., Eastman C.M. Basic Taxonomic Structures and Levels of

Abstraction // Proc. 1st ASIS SIG/CR Classif. Res. Workshop. 1990. P. 59-70.

https://journals.lib.washington.edu/index.php/acro/. . .

10.

Verma N., Mahajan D., Sellamanickam D., Nair V. Learning Hierarchical Similarity

Metrics // www.cs.toronto.edu/˜vnair/cvpr12.pdf

11.

Bettencourt L.M.A. The Rules of Information Aggregation and Emergence

of Collective Intelligent Behavior // onlinelibrary.wiley.com/doi/10.1111/j.1756-

8765. . . /full

12.

Marichal J.-L. Aggregation functions for decision making // https://arxiv.org>math

13.

Bengio Y., Paiement J.-F., Vincent P., Delalleau O., Le Roux N., Ouimet M. Out-

of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering.

https://papers.nips.cc/. . . /2461-out-of-sample-extensions-for-l

14.

Hua Y. Cross-Modal Correlation Learning by Adaptive Hierarchical Semantic //

www.ieeexplore.ieee.org/document/7422147/

15.

Machine Learning Repository // archive.ics.uci.edu/ml/datasets.html

16.

Корноушенко Е.К. Алгоритм классификации путем парного сравнения призна-

ков // АиТ. 2017. № 11. С. 151-166.

Kornoushenko E.K. Classification Algorithm Based on Pairwise Comparison of

Features // Autom. Remote Control. 2017. V. 78. No. 11. P. 2062-2074.

17.

Magimai.-Doss M., Hakkani-Tür D., Cetin O., Shriberg E., Fung J., Mirghafori N.

Entropy-based C;assifier Combimation for Sentence Segmentation //

www.citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1

153

18. Воронцов К.В. Комбинаторный подход к оценке качества обучаемых алгорит-

мов / Математические вопросы кибернетики. Под ред. О.Б. Лупанова. Т. 13. М.:

Физматлит, 2004. С. 5-36.

19. Zindros D. A Gentle Introduction to Algorithm Complexity Analysis //

www.discrete.gr/complexity/

20. Govenir H.A., Demiroz G., Ilter N. Learning differential diagnosis of erythemato-

squamous diseases using voting feature intervals // Artif. Intelligence Medicin. 1998.

V. 13. P. 147-165.

21. El-Baz A.H. Filter Based Feature Selection for Automatic Detection of Erythemato-

squamous Diseases // British J. Math. Comput. Sci. 2015. V. 9. No. 5. P. 394-406.

www.journalrepository.org/. . . /El-Baz952015BJMCS17618.p. . .

22. Schain M. Machine Learning Algorithms and Robustness // Diss. Phd. Tel-Aviv.

Univ. 2015. https://m.tau.ac.il/˜mansour/students/Mariano_Schain_Phd.pdf

Статья представлена к публикации членом редколлегии О.П. Кузнецовым.

Поступила в редакцию 04.04.2018

После доработки 20.12.2018

Принята к публикации 07.02.2019

154