Автоматика и телемеханика, № 12, 2022

(Институт математики им. С.Л. Соболева СО РАН, Новосибирск;

Новосибирский государственный университет)

МОДЕЛЬ И МЕТОД ПОСТРОЕНИЯ РАЗНОРОДНОГО

КЛАСТЕРНОГО АНСАМБЛЯ¹

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

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

ся вероятностная модель, учитывающая коррелированность оценочных

функций, с помощью которой находятся соотношения между характери-

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

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

нимальна верхняя граница оценки вероятности ошибки кластеризации.

Проведено экспериментальное исследование предложенного метода, по-

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

Ключевые слова: кластерный анализ, ансамбль алгоритмов, коассоциа-

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

ритмов.

DOI: 10.31857/S000523102212008X, EDN: KSWKSX

1. Введение

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

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

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

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

случай, когда требуемое число групп задано пользователем. Под критерием

однородности разбиения понимается некоторый функционал, зависящий от

описаний объектов, например показателей внутригруппового и межгруппо-

вого разброса.

Существует большое число методов кластерного анализа [1-4]. На практи-

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

которых управляется с помощью некоторых параметров.

В настоящее время существует необходимость в создании новых методов,

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

устойчивые результаты вне зависимости от начальных инициализаций ал-

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

данных.

¹ Работа проведена при финансовой поддержке РНФ, проект 22-21-00261.

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

ход, основанный на коллективном принятии решений [5-9]. При этом итого-

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

ченных различными алгоритмами либо одним алгоритмом, с разными пара-

метрами работы. Коллективный (ансамблевый) подход позволяет повышать

устойчивость результатов группировки в случае неопределенности в выборе

параметров, проводить обработку больших объемов данных (анализируя по

отдельности сравнительно небольшие их части), а также использовать ¾про-

стые¿ вычислительно эффективные алгоритмы (например, направленные на

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

данных [10].

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

лективных решений кластерного анализа [11]. В данной работе рассматри-

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

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

сти, co-occurrence matrix), устанавливающих, как часто каждая пара объ-

ектов оказывается в одном и том же кластере (или в различных кластерах)

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

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

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

субъективной, любые перестановки меток кластеров эквивалентны (проблема

подробно рассматривается в [6], где предложен один из первых алгоритмов

построения кластерного ансамбля).

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

ного расстояния (сходства) между объектами: чем чаще пара объектов была

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

похожими являются данные объекты. Для получения итогового консенсусно-

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

основанный на попарном сходстве, например, агломеративный алгоритм по-

строения иерархической группировки.

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

ансамблевых решений к ¾истинному¿ разбиению) было сделано в [12]. В [13]

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

воляющая свести задачу кластеризации к задаче попарной классификации с

латентными классами. При этом учитываются веса различных базовых алго-

ритмов ансамбля. Сформулирован критерий оптимальности весов и предло-

жен метод их нахождения. В настоящей работе проводится дальнейшее разви-

тие данного подхода. Проводится исследование влияния коррелированности

базовых решений ансамбля на его качество. Показано, что учет коррелиро-

ванности позволяет объяснить улучшение качества ансамбля при увеличении

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

но установлено в ряде работ (см., например, [14-16]).

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

нятия работы. Во втором разделе вводится вероятностная модель ансамбле-

вого кластерного анализа, в рамках которой исследуются свойства ансамбля.

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

алгоритмов ансамбля. Четвертый раздел посвящен вычислительному экспе-

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

перспективы дальнейших исследований.

2. Основные понятия и обозначения

Пусть информация о множестве объектов исследования A = {a₁, . . . , a_N }

представлена в виде набора X = {x₁, . . . , x_N }, где x_i = X(a_i) = (X₁(a_i), . . . ,

X_d(a_i))

вектор признаков для объекта a_i ∈ A, i = 1, . . . , N, d размер-

ность пространства признаков, x_i ∈ R^d. Требуется разбить множество A на

некоторое заданное число кластеров K.

В ансамблевом кластерном анализе рассматривается набор базовых алго-

ритмов группировки µ₁, . . . , µ_M , которые строят варианты разбиения мно-

жества A. Каждый вариант состоит из K_l,m непересекающихся подмножеств

(кластеров), m = 1, . . . , M, l = 1, . . . , L_m, где L_m - число запусков алгорит-

ма µ_m (величина K_l,m может не совпадать с итоговым числом кластеров K).

Варианты разбиения получены при различных значениях параметров рабо-

ты (или, в более общем смысле, ¾условий обучения¿, таких как подмножество

отобранных переменных или набор начальных центроидов). Обозначим мно-

жество возможных значений параметров алгоритма µ_m через Ω_m.

Определим для каждой пары различных объектов a_i и a_j из множества A

величину

h(Ω_l,m; i, j, X) = I [µ_m (a_i, Ω_l,m, X) = µ_m (a_j , Ω_l,m, X)] ,

где I [·]

индикаторная функция: I [true] = 1; I [false] = 0, µ_m(a, Ω_l,m, X)

номер кластера, приписанного объекту a ∈ A согласно l-му варианту раз-

биения, сформированного алгоритмом µ_m для набора параметров Ω_l,m ∈ Ω_m

по набору данных X. При заданных Ω_l,m, X будем записывать: h_l,m(i, j) =

= h(Ω_l,m; i, j, X). Для каждого l-го варианта разбиения можно определить

коассоциативную матрицу H_l = (h_l(i, j)).

Коллективная кластеризация в рамках рассматриваемого подхода полага-

ется как процесс, включающий несколько основных этапов.

На первом этапе формируются различные варианты разбиения выбор-

ки P_1,1, . . . , P_l,m, . . . , PLM ,M , полученные на основе случайного независимого

выбора параметров алгоритмов из множеств Ω₁, . . . , Ω_M в соответствии с

некоторыми распределениями (например, равномерными).

На втором этапе проводится анализ полученных разбиений: определя-

ются оценочные функции γ_l,m ≥ 0, которые зависят от индексов качества по-

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

ся функциями от разбиений: γ_l,m = γ_l,m(P_1,1, . . . , PLM ,M ). Будем считать, что

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

величина оценочной функции.

Например, при применении процедуры селекции ансамбля [16] проводит-

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

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

оценочной функции. Оставшимся вариантам приписывается некоторое нену-

левое постоянное значение.

На третьем этапе вычисляется усредненная с весами коассоциативная

матрица H = (h(i, j)) с элементами

∑

(1)

h(i, j) =

γ_l,mh_l,m

(i, j),

m=1 l=1

(i, j = 1, . . . , N, i = j). Элементы H рассматриваются как меры близости меж-

ду парами соответствующих объектов. Для формирования окончательного

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

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

ния. В данной работе с этой целью используется алгоритм, основанный на

спектральном кластерном анализе [17]. В итоге получим разбиение множе-

ства A на подмножества C₁, . . . , C_K .

В целях управления качеством ансамбля целесообразно ввести управляе-

мую компоненту в (1) и представить элементы усредненной коассоциативной

матрицы в виде

∑

(2)

h(i, j) =

α_m γ_l,mh_l,m

(i, j),

m=1

l=1

где α₁, . . . , α_M веса базовых алгоритмов µ₁, . . . , µ_M ,

∑α_m = 1, α_m ≥ 0. Ве-

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

самбля. Данная возможность будет рассмотрена ниже в разделе 4.

3. Вероятностная модель ансамблевой классификации

Описывается модель коллективной классификации с латентными класса-

ми, в рамках которой по наблюдаемым характеристикам ансамбля оценива-

ется вероятность непосредственно не наблюдаемой ошибки классификации.

3.1. Модель генерации данных и ансамбля алгоритмов

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

боты [13]. Сформулируем следующую модель генерации данных. Пусть объ-

екты множества A случайным и независимым образом выбираются из некото-

рой генеральной совокупности Γ, разделенной на K классов. Предположим,

что в описании произвольного объекта a ∈ Γ имеется признак Y, который ука-

зывает на его принадлежность к определенному классу: Y (a) ∈ {1, . . . , K}.

1,0

0,8

0,6

0,4

0,2

x_j

x_i

График функции P[Z(i, j) = 1 | x_i, x_j ] в зависимости от значений x_i, x_j .

Этот признак является скрытым (непосредственно не наблюдаемым) для ал-

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

∑

ность P_k = P (Y (a) = k), k = 1, . . . , K, где

P_k = 1. Классу с номером k

k=1

сопоставляется закон условного распределения в пространстве признаков:

p(X(a) = x | Y (a) = k) = p_k(x), k = 1, . . . , K.

Для произвольной пары различных объектов a_i, a_j ∈ A определим случай-

ную величину

Z(i, j) = I [Y (a_i) = Y (a_j )] ,

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

одному классу или к разным классам. Пусть набор данных X фиксирован;

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

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

ние величины Z(i, j) при условии заданных значений X(a_i) = x_i и X(a_j ) = x_j

определяется через условное распределение P [Y | X(a) = x], a ∈ A:

∑

P[Z(i,j) = 1 | x_i,x_j] =

P [Y (a_i) = k | x_i] P [Y (a_j ) = k | x_j ] =

k=1

∑

p_k(x_i)p_k(x_j)P^2k

p(x_i)p(x_j )

k=1

∑

где p(x) =

p_k(x)P_k. На рисунке показан пример графика функции

k=1

P [Z(i, j) = 1 | x_i, x_j ] для случая двух классов, подчиняющихся одномерным

нормальным распределениям: x_i ∼ N(2, 1), x_j ∼ N(8, 1) и равными априор-

ными вероятностями.

Обозначим через Ω_m случайный набор параметров, выбираемый из Ω_m.

Предположим, что алгоритм µ_m проработал некоторое число L_m раз при

независимо выбранных, в соответствии с одним и тем же распределением,

параметрах. Тогда величины Ω_m,1, . . . , Ωm,Lm являются независимыми и оди-

наково распределены с Ω_m.

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

ты базовых алгоритмов (например, относящиеся к свойствам меры близости

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

Результаты работы алгоритма µ_m (т.е. полученные элементы матри-

цы коассоциации) можно рассматривать как детерминированные функции

h_l,m(i,j) = h(i,j,Ω_l,m,X) от независимых многомерных случайных величин

Ω_l,m ∈ Ω_m, l = 1,... ,L_m, которые подчиняются одному и тому же распреде-

лению на Ω_m. Обозначим: Ψ = {Ω_1,1, . . . , ΩLM ,M }.

Рассмотрим условные вероятности правильного решения для каждого ал-

горитма (объединения пары объектов из одного класса в один кластер или

разделения пары из разных классов в различные кластеры):

q^(1)m(i,j,X) = P[h(i,j,Ω_m,X) = 1 | Z(i,j) = 1] ,

q^(0)m(i,j,X) = P[h(i,j,Ω_m,X) = 0 | Z(i,j) = 0] .

В результате работы алгоритма получим набор независимых случайных

величин решений

h(i, j, Ω_1,m, X), . . . , h(i, j, ΩLm ,m, X), m = 1, . . . , M.

Будем также считать, что решения условно независимы:

[

(

)

]

h(i,j,Ωi1,m₁,X) = hr₁ ,... ,h

i, j, Ωij ,m_j , X

= hrj | Z(i,j) = z

= P[h(i,j,Ωi1,m₁,X) = hr₁ | Z(i,j) = z] × ... ×

[

(

)

]

×P

i, j, Ωij ,m_j , X

= hrj | Z(i,j) = z

где Ωi1,m₁ , . . . , Ωi_j ,m_j

произвольные параметры; индексы m₁, . . . , m_j соот-

ветствуют разным сочетаниям алгоритмов, hr1 , . . . , hrj , z ∈ {0, 1}.

Величина оценочной функции γ_l,m, определяемая на втором этапе по-

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

P_1,1,... ,PLM ,M . Необходимость учета других вариантов, помимо текущего,

может быть обоснована, например, тем, что при наличии совпадающих или

очень похожих вариантов их вес было бы разумно уменьшить. Часть дубли-

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

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

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

висит от всего набора параметров: γ_l,m = γ_l,m(Ψ, X). Поскольку функционал

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

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

ной пары объектов. То есть будем считать, что величины γ_l,m = γ_l,m(Ψ, X) и

h_l,m(i,j) = h(i,j,Ω_l,m,X) некоррелированы.

Можно полагать, что для каждого базового алгоритма µ_m, m = 1, . . . , M,

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

гда распределение величин γ_l,m = γ_l,m(Ψ, X), l = 1, . . . , L_m будет одинаково.

3.2. Характеристики ансамбля

Для того чтобы использовать модель ансамблевой классификации для

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

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

телями качества коллективной классификации.

3.2.1. Вероятность ошибки ансамблевой классификации

Введем предварительно следующие понятия. Для фиксированной пары

различных индексов i, j ∈ {1, . . . , N}, ансамблевым решением, полученным

для усредненной матрицы коассоциации с элементами, вычисляемыми со-

гласно (2), назовем величину





∑

D(i, j, Ψ, X) = I

γ_l,m >

γ_l,m .

l,m:h_l,m(i,j)=1

l,m:h_l,m(i,j)=0

Величина D(i, j, Ψ, X) ∈ {0, 1} и показывает, превышает ли суммарный вес

голосов за объединение пары в один кластер (когда D(i, j, Ψ, X) = 1) сумму

голосов за ее разделение (при D(i, j, Ψ, X) = 0). Ансамблевое решение зависит

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

данных.

Вероятность ошибки ансамблевой классификации для пары определяется

как

(3)

P_er (i,j;X) = P_Ψ,Z(i,j)

[D(i, j, Ψ, X) = Z(i, j)] .

Здесь индексы Ψ, Z(i, j) обозначают источник случайности.

3.2.2. Разложение ошибки на составляющие

В данном подразделе, для краткости, будем опускать индексы i, j и обо-

значение X в величинах, определенных выше (подразумевая, что соответ-

ствующие значения i, j, X фиксированы). Пусть D = D(Ψ).

Выражение для вероятности ансамблевой ошибки классификации (3)

можно представить в следующем виде: P_er = E_Ψ,Z [Z - D]² = Var[Z - D] +

+ (E[Z - D])². Так как Var[Z - D] = Var[Z] + Var[D] - 2Cov[Z, D], то

(4)

P_er = Var[Z] + Var[D] + (E[Z - D])²

− 2Cov[Z,D].

Здесь через Var[·] и Cov[·, ·] обозначены соответственно дисперсия и кова-

риация случайных величин. Полученное выражение (4) можно проинтерпре-

тировать следующим образом. Ошибка классификации для пары объектов

имеет несколько источников возникновения:

неустранимая ошибка Var[Z], которая связана с близостью или пересе-

чением истинных непосредственно не наблюдаемых классов;

разброс ансамблевых решений Var[D];

несоответствие между истинным статусом пары объектов и решением

ансамбля, выражаемое через квадрат смещения: (E[Z - D])²;

ковариация с обратным знаком Cov[Z, D] между истинным статусом и

решением ансамбля.

Можно заметить, что в ¾простых¿ задачах кластеризации, т.е. при высо-

кой степени разделимости классов (например, когда дисперсия Var[Z] мала

для всех пар объектов) и достаточно точном соответствии решений ансамбля

истинному статусу, малое значение вероятности ошибки в (4) достигается

при небольшом разнообразии ансамбля (малом разбросе решений, т.е. вели-

чины D для пары).

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

лика, для уменьшения смещения и увеличения ковариации требуется уве-

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

P[Z = D] = 1 (когда алгоритм построения ансамбля точно определяет истин-

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

ной, а дисперсия решений (совпадающая с дисперсией Z) также большой.

Соотношение (4) позволяет на качественном уровне судить об источниках

возникновения ошибки ансамбля. С использованием рассматриваемого ниже

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

относительно поведения ансамбля.

3.2.3. Основные характеристики маржинальной функции

Рассмотрим усредненную коассоциативную матрицу в виде (2). Оценкой

решения (маржинальной функцией кластерного ансамбля [13]) назовем вели-

чину

∑

(5) mg(i, j, Ψ, Z(i, j), X) =

α_mγ_l,m -

α_mγ_l,m,

l,m:h_l,m(i,j)=Z(i,j)

где Z(i, j) ∈ {0, 1}

истинный статус пары. Эта функция показывает, на-

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

шенное число голосов за неправильное решение, и зависит от параметров

алгоритмов, истинного статуса пары и от выборки.

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

вероятность ошибки предсказания величины Z для пары объектов в следую-

щем виде:

P_err(i,j,z) = P[mg(i,j,Ψ,Z(i,j),X) < 0 | Z(i,j) = z].

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

мых выражений. Чтобы определить свойства данной величины, необходимо

знать характеристики маржинальной функции. Найдем ее первые условные

моменты.

Утверждение 1. Условное математическое ожидание маржинальной

функции равно

∑

(

)

(6)

E_Ψ|z [mg (i,j,Ψ,Z(i,j),X)] =

α_mL_mΓ_m 2q^(z)m(i,j,X) - 1

а ее условная дисперсия

∑

[

]

Var_Ψ|z[mg(Ψ, Z)] =

α²

L_m V_m + 4(Γ_m)²q^(z)m(i,j,X)(1 - q^(z)m(i,j,X))

∑

(

)₂

+ α^2mL_m(L_m - 1) 2q^(z)m(i,j,X) - 1

C_m +

(7)

∑

(

)(

)

α_mα_m′ L_mL_m′

2q^(z)m(i, j, X) - 1

2q(z)m′(i, j, X) - 1 C_m,m′ ,

m,m^′:

m=m^′

где оператор E_X|z[·] = E_X [· | Z = z] обозначает условное математическое

ожидание, Γ_m = E_Ψ[γ_l,m] есть математическое ожидание оценочного функ-

ционала на множестве Ω_m, V_m = Var_Ψ[γ_l,m] обозначает дисперсию оценоч-

ной функции, C_m = cov[γ_l,m,γ_l′_,m]

ковариация между оценочными функ-

циями для алгоритма µ_m, C_m,m′ = cov[γ_l,m, γ_l′_,m′ ] ковариация между оце-

ночными функциями для различных алгоритмов µ_m,µ_m′ (m = m^′,m,m^′ =

= 1, . . . , M).

Доказательство утверждения 1 приведено в Приложении.

3.2.4. Влияние характеристик ансамбля на вероятность ошибки

Известно, что для любой случайной величины U с конечным математиче-

ским ожиданием E[U] > 0 и дисперсией Var [U] справедливо

P [U < 0] ≤ P [{U < E[U] - ε}⋃{U > E[U] + ε} = P [| U - E[U] |> ε],

где ε = E[U]. Из неравенства Чебышева вытекает, что

Var[U]

P [U < 0] <

(E[U])²

Следовательно, для условной вероятности ошибки

P_err(i,j,z) = P[mg(i,j,Ψ,Z(i,j),X) < 0 | Z(i,j) = z]

выполняется

Var_Ψ|z [mg(i, j, Ψ, Z(i, j), X)]

(8)

P_err(i,j,z) <

(

)₂

E_Ψ|z [mg(i,j,Ψ,Z(i,j),X)]

в случае, когда E_Ψ|z[mg(i, j, Ψ, Z(i, j), X)] > 0. Из утверждения 1 следует, что

данное условие будет выполнено, в частности, если для всех m = 1, . . . , M

справедливо

(9)

0,5 + ε < q^(z)m

(i, j, X) ≤ 1,

т.е. алгоритм кластеризации принимает решение не наугад (здесь ε неко-

торая малая положительная величина).

Для уменьшения вероятности ошибки можно дополнительно к (8) и (9) по-

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

ной. На основании утверждения 1 можно сделать несколько качественных

выводов о поведении ансамблевых решений.

1) При прочих равных условиях верхняя граница вероятности ошибки сни-

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

горитмов µ_m, µ_m′ , m, m^′ = 1, . . . , M. Заметим, что уменьшение ковариации

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

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

2) Предположим, что L₁ = . . . = L_M = L, все оценочные функции совпа-

дают и равны γ_l,m ≡ 1/L, α_m ≡ 1/M. Значит, ∀m, Γ_m = 1/L, V_m = C_m = 0 и

∀m,m^′ (m = m^′), C_m,m′ = 0. Из (6) получим:

∑(

)

E_Ψ|z [mg(i,j,Ψ,Z(i,j),X)] =

2q^(z)m(i, j, X) - 1 ,

а из (7)

∑

(

)

Var_Ψ|z [mg(i, j, Ψ, Z(i, j), X)] =

q^(z)m(i,j,X) 1 - q(z)m (i,j,X)

M²L

На основании (8), (9) можно сделать вывод о том, что P_err(i, j, z) → 0 при

L → ∞ и M = const. То есть при выполнении условий модели и увеличении

количества элементов ансамбля вероятность ошибки стремится к нулю.

3) Предположим, что ожидаемая оценка качества Γ_m для некоторого зна-

чения m увеличивается при условии максимальной степени устойчивости

q^mz) = 1 и при прочих неизменных характеристиках ансамбля. При этом верх-

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

значениях вероятности правильного решения q^mz) дисперсия маржинальной

функции увеличится за счет первой группы слагаемых в (7). Таким образом,

¾переоценка¿ ансамбля может привести к ухудшению его качества.

4. Выбор оптимальных весов

4.1. Решение оптимизационной задачи

Рассмотрим задачу выбора весов α₁, . . . , α_M базовых алгоритмов так, что-

бы минимизировать верхнюю границу вероятности ошибки. Пусть выбрана

произвольная пара различных объектов a_i, a_j ∈ A, таких что выполняется

условие (9), тогда из (8) получим следующую задачу минимизации (индек-

сы i, j и обозначение X для краткости опущены):

Var_Ψ|z[mg(Ψ, Z)]

(

)₂ → min

α₁,...,α_M

E_Ψ|z[mg(Ψ,Z)]

при ограничениях

∑α_m = 1, α_m ≥ 0, m = 1,...,M.

Приближенное численное решение можно получить, например, с помощью

градиентного метода. В данной работе рассматривается упрощенная задача,

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

Var_Ψ|z[mg(Ψ, Z)] → min

α₁,...,α_M

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

Лагранжа. Пусть функция Лагранжа следующая:

∑

[

(

)]

L= α²

L_m V_m + 4(Γ_m)²q^(z)

1-q^(z)

∑

(

)₂

+ α^2mL_m(L_m - 1) 2q^(z)m - 1

C_m +

∑

(

)(

)

(∑

)

α_mα_m′ L_mL_m′

2q^(z)m - 1

2q(z)m′ - 1 C_m,m′ - λ

α_m - 1 ,

m,m^′:

m=m^′

где λ множитель Лагранжа. Тогда необходимое условие экстремума будет

[

]

(

)

(

)₂

∂L

= 2α_mL_m V_m + 4(Γ_m)²q^(z)

1-q^(z)

+ (L_m - 1)

2q^(z)m - 1

C_m +

∂α_m

∑

(

)(

)

α_m′ L_mL_m′

2q^(z)m - 1

2q(z)m′ - 1 C_m,m′ - λ = 0,

m^′:

m=m^′

m = 1,...,M. Для удобства введем матричные обозначения: пусть A_M×M =

= (A(m^′, m^′′)) матрица с элементами

(10)

A(m^′, m^′′



[

]

(

)

(

)₂



2L_m V_m + 4(Γ_m)²qm)

1-qm)

+ (L_m - 1)

2q^mz) - 1

C_m , m^′ = m^′′,

(

)(

)



L_mL_m′

2q^mz) - 1

2q(z)m′ - 1 C_m,m′ ,

m^′ = m^′′.

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









α₁









A

=



.

α_M

Добавив условие

∑α_m = 1, запишем систему в матричной форме:

Ca = b,

где





-1





 A

a = (α₁,...,α_M,λ)^T, C =



,

b = (0,...,0,1)^T.



-1

Тогда решение определяется как

(11)

a=C^-1

если обратная матрица существует (в случае каких-либо особенностей мат-

рицы условимся назначать алгоритмам одинаковые веса).

Для оценки оптимальных коэффициентов заменим характеристики оце-

ночных функций, входящие в (10), их выборочными аналогами: выборочным

средним, дисперсией и ковариацией. Эти величины определяются по получен-

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

ковариации, рассматриваются различные пары объектов).

Элементы матрицы A зависят от величин q^mz), которые являются непо-

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

ектов. Однако по условию задачи оптимальные коэффициенты должны быть

постоянными для всех пар. Будем считать величину q^mz) параметром, при-

нимающим значение q, близкое к 1, так как полученные выражения спра-

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

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

4.2. Основные шаги алгоритма

Опишем основные шаги предложенного алгоритма построения взвешенно-

го кластерного ансамбля (назовем его CEOW Cluster Ensemble with Opti-

mized Weights).

Алгоритм CEOW.

Входные данные:

X таблица данных ¾объект-свойство¿;

µ₁,... ,µ_M

набор базовых алгоритмов кластерного анализа;

L₁,... ,L_M

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

100

Шаги:

1. Запустить каждый базовый алгоритм заданное число раз со случайны-

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

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

ветствии с которым инициализируются параметры, фиксировано).

2. Для каждого полученного разбиения определить оценку его качества.

3. Найти оценки величин Γ_m, V_m, C_m, для каждого алгоритма µ_m, а так-

же оценки ковариаций C_m,m′ для комбинаций различных алгоритмов

µ_m, µ_m′ .

4. Вычислить оптимальные коэффициенты α₁, . . . , α_M по формуле (11).

5. Вычислить взвешенную коассоциативную матрицу H по формуле (2).

6. Рассматривая матрицу H как матрицу попарного сходства объектов,

найти итоговое разбиение с помощью алгоритма кластерного анали-

за, на вход которого подается полученная матрица сходства (для этого

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

ского разбиения либо спектральный алгоритм).

Конец работы алгоритма.

5. Экспериментальное исследование

Разработанный алгоритм реализован программно на языке Python. Для

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

тестирования была взята из репозитория задач машинного обучения [18]. Она

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

сов.

Эксперимент проводился следующим образом: в качестве базовых алго-

ритмов использовался алгоритм K -means с разным фиксированным числом

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

числом алгоритмов в ансамбле, с шагом один). То, что в качестве базовых

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

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

пускался 20 раз с различной случайной инициализацией центроидов. Оценка

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

ниям Cилуэт-индекса качества [19]. В (10) было взято значение q = q^mz) = 1.

Для построения итогового разбиения использовался спектральный алгоритм

кластерного анализа [17]. Полученное разбиение сравнивалось с истинным

разбиением с помощью исправленного индекса Ранда (ARI) [20]. Более высо-

кое значение индекса свидетельствует о лучшем соответствии разбиений.

В табл. 1 приведены результаты работы алгоритма CEOW, отдельного ал-

горитма K -means, а также кластерного ансамбля, основанного на вычислении

коассоциативной матрицы с равными весами базовых алгоритмов (CEEW

Cluster Ensemble with Equal Weights).

На экспериментальных данных предложенный алгоритм показал более

точные результаты, чем алгоритм K -means и аналогичный ансамблевый алго-

101

Таблица 1. Результаты эксперимента: индекс ARI

Число алгоритмов CEOW K -means CEEW

в ансамбле

0,410

0,351

0,402

0,443

0,351

0,443

0,467

0,351

0,453

ритм с равными весами. Также можно заметить, что результаты улучшаются

с увеличением числа базовых алгоритмов в ансамбле.

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

В работе проведено теоретическое и экспериментальное исследование раз-

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

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

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

ются оценки качества полученных вариантов группировки. Для обоснования

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

сификации, учитывающая коррелированность оценочных функций. В модели

делается предположение о существовании ¾истинных¿ непосредственно не

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

ансамбля. С помощью модели получены аналитические зависимости между

оценками качества решения и характеристиками ансамбля (числом его эле-

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

коррелированности алгоритмов). В рамках модели найдено выражение для

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

ятности ошибки классификации.

Разработан алгоритм, в котором реализован метод построения ансамбля и

вычисления оптимальных весов. Экспериментальное исследование подтвер-

дило эффективность предложенного метода: предложенный алгоритм дал

более высокую точность, чем отдельный алгоритм K -means и аналогичный

ансамблевый алгоритм, не использующий оптимизацию весов.

Проведенное исследование имеет ряд ограничений. Работа направлена в

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

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

ства. При выборе оптимальных весов базовых алгоритмов решалась лишь

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

чить только приближенное численное решение.

В перспективе планируется провести дополнительные экспериментальные

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

интересно сравнить решения общей и упрощенной задач оптимизации. Кро-

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

кластеризации, входящих в ансамбль (DBSCAN, спектральный алгоритм и

102

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

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

сходства.

Автор благодарит магистранта НГУ В.В. Баранова за помощь в проведе-

нии вычислительных экспериментов.

ПРИЛОЖЕНИЕ

Доказательство утверждения 1. При доказательстве для крат-

кости будем опускать обозначения i, j, X. Маржинальная функция (5) может

быть переписана в виде

∑

mg(Ψ,Z) = α_mγ_l,m {I [h(Ω_l,m) = Z] - I [h(Ω_l,m) = Z]} =

l,m

(Π.1)

∑

= α_mγ_l,m(2Z - 1)(2h(Ω_l,m) - 1),

l,m

так как для булевых u, v выполняется I[u = v] - I[u = v] = (2u - 1)(2v - 1).

Отсюда получим

∑

E_Ψ|z[mg(Ψ,Z)] =

E_Ψ|z [α_mγ_l,m(2z - 1)(2h(Ω_l,m) - 1)] =

l,m

∑

(

)

= (2z - 1) α_mE_Ψ[γ_l,m]

2EΩl,m|z [h(Ωl,m)] - 1

l,m

в силу предполагаемой некоррелированности оценочного функционала γ_l,m

и величины h(Ω_l,m), характеризующей данную пару объектов. Так как для

каждого m-го множества параметров величины Ω_m,1, . . . , Ωm,Lm одинаково

распределены с Ω_m, то имеем

∑

∑(

)

E_Ψ|z[mg(Ψ,Z)] = (2z - 1)

α_mΓ_m

2EΩl,m|z [h(Ωl,m)] - 1

l=1

∑

(

)

= (2z - 1) α_mΓ_mL_m

2EΩm|z [h(Ωm)] - 1

При z = 0 выполняется

(

)

1-q⁽⁰⁾

-1 = 1-2q(0)m ,

2EΩm|z[h(Ωm)] - 1 = 2P [hm(Ωm) = 1 | Z = 0] - 1 = 2

а при z = 1

2EΩm|z[h(Ωm)] - 1 = 2P [hm(Ωm) = 1 | Z = 1] - 1 = 2q^m1) - 1.

Значит, для произвольного z ∈ {0, 1} можно записать:

(

)

(Π.2)

2EΩm|z[h(Ωm)] - 1 = (2z - 1)

2q^(z)m - 1

103

Отсюда

∑

(

)

E_Ψ|z

[mg(Ψ, Z)] = (2z - 1)²

α_mΓ_mL_m 2q^(z)m - 1

∑

(

)

= α_mL_mΓ_m 2q^(z)m - 1 .

Рассмотрим теперь условную дисперсию маржинальной функции. Из вы-

ражения (П.1), свойств дисперсии, предположения об условной независимо-

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

функционалом группировки получим:





∑

Var_Ψ|z[mg(Ψ, Z)] = (2z - 1)² Var_Ψ|z  α_mγ_l,m(2h(Ω_l,m) - 1) =

l,m:





∑

= Var_Ψ|z  α_mγ_l,m(2h(Ω_l,m) - 1) =

l,m:

(Π.3)

∑

= Var_Ψ|z [α_mγ_l,m(2h(Ω_l,m) - 1)] +

l,m

∑

[

]

cov

α_mγ_l,m(2h(Ω_l,m) - 1),α_m′ γ_l′_,m′ (2h(Ω_l′_,m′ ) - 1)

l,m,l^′,m^′:

(l,m)=(l^′,m^′)

Рассмотрим группы слагаемых в (П.3) по очереди начиная с первой (обозна-

чив ее через A). В силу предположения о некоррелируемости решений для

пары объектов и оценочным функционалом группировки, получим:

∑

(Π.4)

A = VarΨ|z [α_mγ_l,m(2h(Ω_l,m

) - 1)] =

l,m

∑

{

= α²

Var_Ψ[γ_l,m]Var[2h(Ω_l,m) - 1] + (E_Ψ[γ_l,m])² Var[2h(Ω_l,m) - 1] +

l,m

}

+ (E[2h(Ω_l,m) - 1])² Var_Ψ[γ_l,m]

∑

{

}

= α²

4V_m Var[h(Ω_l,m)] + 4(Γ_m)² Var[h(Ω_l,m)] + (2E[h(Ω_l,m)] - 1)²Vm

l,m

∑

{

= α²

L_m 4V_m Var [h(Ω_m)] + 4(Γ_m)² Var [h(Ω_m)] +

(

)₂

}

+(2z - 1)²

2q^(z)m - 1

V_m

(в последнем выражении было использовано свойство (П.2)). Далее,

[

]

(

)₂

h(Ω_m)²

VarΩm|z [h(Ωm)] = EΩm|z

EΩm|z [h(Ωm)]

(

)

= EΩm|z [h(Ωm)]

1 - EΩm|z [h(Ωm)]

104

(так как h(Ω_m)² = h(Ω_m)). Отсюда для z = 0 получим:

(

)

1-q⁽⁰⁾

q^(0)m;

VarΩm|z=0 [h (Ωm)] =

а для z = 1:

(

)

1-q⁽¹⁾

VarΩm|z=1[h(Ωm)] = q^m1)

Можно записать:

(

)

VarΩm|z [h(Ωm)] = q^mz)

1-q^(z)

Воспользовавшись тождеством

(

)₂

(

)

2q^(z)m - 1

= 1 - 4q^(z)

1-q^(z)

перепишем (П.4):

∑

A = VarΨ|z [α_mγ_l,m(2h(Ω_l,m) - 1)] =

l,m

∑

{

(

)

(

)

(Π.5)

= α²

L_m 4V_mq^(z)

1-q^(z)

+ 4(Γ_m)²q^(z)

1-q^(z)

(

))

}

∑

{

(

)}

+ 1-4q^(z)

1-q^(z)

V_m

= α²

L_m V_m +4(Γ_m)²q^(z)

1-q^(z)

Преобразуем теперь вторую группу слагаемых в (П.3), обозначив ее через B:

∑

[

(

)

)]

cov

α_mγ_l,m (2h(Ω_l,m) - 1) ,α_m′ γ_l′_,m′

Ω_l′,m′

-1

l,m,l^′,m^′:

(l,m)=(l^′,m^′)

∑

{

[

(

)

)]

α_mα_m′ E

γ_l,mγ_l′_,m′ (2h(Ω_l,m) - 1)

Ω_l′,m′

-1

l,m,l^′,m^′:

(l,m)=(l^′,m^′)

}

[

(

)

)]

- E [γl,m (2h(Ω_l,m) - 1)]E

γ_l′,m′

Ω_l′,m′

-1

В силу предположения о некоррелируемости оценочных функций и решений

для пары объектов и так как Ω_l,m, Ω_l′_,m′ независимы для различных сочета-

ний (l, m) = (l^′, m^′), выполняется:

∑

[

(

)

]

α_mα_m′ E [2h(Ω_l,m) - 1] E

Ω_l′,m′

-1

l,m,l^′,m^′:

(l,m)=(l^′,m^′)

{

[

]

[

]}

γ_l,mγ_l′_,m′

- E [γ_l,m]E

γ_l′,m′

105

Так как Ω_l,m, Ω_l′_,m′ одинаково распределены с Ω_m, Ω_m′ соответственно, то,

воспользовавшись (П.2), получим:

∑

(

)(

)

α_mα_m′ (2z - 1)2

2q^(z)m - 1

2q(z)m′ - 1 cov[γ_l,m, γ_l′_,m] =

l,m,l^′,m^′:

(l,m)=(l^′,m^′)

∑

(

)(

)

α_mα_m′

2q^(z)m - 1

2q(z)m′ - 1 cov[γ_l,m, γ_l′_,m].

l,m,l^′,m^′:

(l,m)=(l^′,m^′)

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

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

индексами m, m^′, поэтому

∑ (

∑

[

]

B = α_m 2q^(z)m - 1

cov

γ_l,m,γ_l′_,m

l,l^′=1

l=l^′

∑

(

)(

)∑

[

]

α_mα_m′

2q^(z)m - 1

2q(z)m′ - 1

cov

γ_l,m, γ_l′_,m′

m,m^′:

l,l^′

m=m^′

Так как cov[γ_l,m, γ_l′_,m] = C_m, а cov[γ_l,m, γ_l′_,m′ ] = C_m,m′ , то

∑

(

)₂

B = α^2mLm (L_m - 1) 2q^(z)m - 1

C_m +

∑

(

)(

)

(Π.6)

α_mα_m′ L_mL_m′

2q^(z)m - 1

2q(z)m′ - 1 C_m,m′ .

m,m^′:

m=m^′

Таким образом, подставив (П.5) и (П.6) в (П.3), получим искомое выражение

для дисперсии (7).

Утверждение 1 доказано.

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

1. Миркин Б.Г. Методы кластер-анализа для поддержки принятия решений: обзор.

М.: Изд. дом НИУ ВШЭ, 2011.

2. Duda R.O., Hart P.E., Stork D.G. Pattern Classification. Second Edition. Wiley,

NY. 2000.

3. Jain A.K., Dubes R.C. Algorithms for clustering data. Prentice Hall, NJ, 1988.

4. Jain A.K. Data clustering: 50 years beyond k-means. Pattern Recognition Letters.

2010. Vol. 31, No. 8. P. 651-666.

5. Zhuravlev Yu.I., Nikiforov V.V. Algorithms for recognition based on calculation of

evaluations // Kibernetika. 1971. Vol. 3. P. 1-11.

106

Ryazanov V.V. On the synthesis of classifying algorithms in finite sets of classifica-

tion algorithms (taxonomy). USSR Computational Mathematics and Mathematical

Physics. 1982. Vol. 22, Iss. 2. P. 186-198.

Breiman L. Random Forests // Machine Learning. 2001. Vol. 45(1). P. 5-32.

Kuncheva L. Combining Pattern Classifiers. Methods and Algorithms. Wiley, NJ.

2004.

Schapire R., Freund Y., Bartlett P., Lee W. Boosting the margin: a new explana-

tion for the effectiveness of voting methods. Annals of Statistics. 1998. Vol. 26(5).

P. 1651-1686.

10.

Ghosh J., Acharya A. Cluster ensembles. Wiley Interdisciplinary Reviews: Data Min-

ing and Knowledge Discovery. 2011. Vol. 1(4). P. 305-315.

11.

Vega-Pons S., Ruiz-Shulcloper J.A. Survey of Clustering Ensemble Algorithms. 2011.

IJPRAI 25(3), 337-372.

12.

Topchy A., Law M., Jain A., Fred A. Analysis of Consensus Partition in Cluster

Ensemble // Fourth IEEE International Conference on Data Mining (ICDM’04).

2004. P. 225-232.

13.

Berikov V., Pestunov I. Ensemble clustering based on weighted co-association matri-

ces: Error bound and convergence properties // Pattern Recognition. 2017. Vol. 63.

P. 427-436.

14.

Wu Y., Liu L., Xie Z., Chow K.H., Wei W. Boosting Ensemble Accuracy by Revis-

iting Ensemble Diversity Metrics. In Proceedings of the IEEE/CVF Conference on

Computer Vision and Pattern Recognition. 2021. P. 16469-16477.

15.

Rashidi F., Nejatian S., Parvin H., Rezaie V. Diversity based cluster weighting

in cluster ensemble: an information theory approach. Artificial Intelligence Review.

2019. Vol. 52(2). P. 1341-1368.

16.

Wang Z., Parvin H., Qasem S.N., Tuan B.A., Pho K.H. Cluster ensemble selec-

tion using balanced normalized mutual information. Journal of Intelligent & Fuzzy

Systems, (Preprint). 2020. P. 1-23.

17.

Liu J., Han J. Spectral clustering. Data Clustering. Chapman and Hall/CRC. 2018.

P. 177-200.

18.

http://archive.ics.uci.edu/ml/datasets/image+segmentation.

19.

Rousseeuw P.J. Silhouettes: a graphical aid to the interpretation and validation of

cluster analysis. Journal of computational and applied mathematics. 1987. Vol. 20.

P. 3-65.

20.

Hubert L., Arabie P. Comparing partitions. Journal of Classification. 1985. Vol. 2(1).

P. 193-218.

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

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

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

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

107