Известия РАН. Теория и системы управления, 2022, № 1, стр. 41-55

0. Введение. В связи с информатизацией возрастает количество данных с многими представлениями или аспектами, в которых описания объектов взяты из нескольких различных источников или даны различными признаками [1]. Например, веб-страница может быть представлена текстом, изображениями и гиперссылками; изображение может быть описано с помощью гистограмм, спектральных или морфологических характеристик [2], наборами угловых точек и т.д. Данные с несколькими аспектами порождают новый класс методов кластеризации, многоаспектную кластеризацию (МАК) (multi-view clustering, MVC). Методы наиболее полного использования дополнительной и непротиворечивой информации из различных представлений важны во многих приложениях [3]. Разработано множество алгоритмов МАК, которые в соответствии с целью и реализуемой стратегией можно разделить на пять категорий: многоаспектная спектральная кластеризация (multi-view spectral clustering) [4], многоядерная кластеризация (multi-kernel clustering) [5], многоаспектная кластеризация неотрицательным матричным разложением (multi-view nonnegative matrix factorization clustering) [6], многоаспектная кластеризация подпространств (multi-view subspace clustering) [7] и канонический корреляционный анализ (canonical correlation analysis) [8].

В этой статье основное внимание уделяется многоаспектной кластеризации подпространств (МАКП) (multi-view subspace clustering, MVS). Этот класс методов появился при сочетании двух подходов: многоаспектности (использования данных об объектах из различных представлений) и поиска таких разбиения и признаков, что каждый кластер соответствует подпространству объединенного пространства признаков. Известные алгоритмы МАКП работают следующим образом:

1) для каждого аспекта строится матрица смежности;

2) построенные матрицы некоторым образом объединяются в матрицу сродства;

3) для полученной матрицы сродства выполняется алгоритм спектральной кластеризации, дающий окончательный результат.

Очевидно, эффективность МАКП существенно зависит от способа построения матрицы сродства. Сегментация ансамбля подпространств при блочных ограничениях (ensemble subspace segmentation under blockwise constraints, ESSB) [9] сначала строит матрицы смежности для каждого аспекта, а затем получает матрицу сродства как среднее этих матриц. Такой подход не использует взаимосвязь различных аспектов [10]. Система кластеризации на основе графов (graph-based system, GBS) [11] выделяет структуру многообразия при помощи разреженного представления различных аспектов, единая матрица сродства получается как взвешенная комбинация. Многоаспектная кластеризация обучением графа (multiview clustering by graph learning, MVGL) [12] строит начальные матрицы для отдельных аспектов, затем эти матрицы уточняются решением специальной оптимизационной задачи. Матрица сродства получается их комбинацией.

Здесь и далее для отношений смежности и сродства термины граф и матрица используются как взаимозаменяемые, поскольку существует взаимно-однозначное соответствие между полным неориентированным взвешенным графом с N пронумерованными вершинами и симметрической матрицей размером N × N, содержащей веса ребер графа. Граф с несколькими компонентами связности и вершинами, занумерованными так, что номера вершин каждой компоненты идут подряд, соответствует блочно-диагональной матрице. Для приложений смысл имеет граф и его компоненты связности, называемые кластерами, при расчетах используется матричное представление. Матрицей Лапласа (Кирхгофа) для матрицы W называется матрица

где D – диагональная матрица, диагональные элементы которой равны сумме в соответствующих строках W. Доказана следующая теорема.

Теорема. Если матрица Лапласа ${{L}_{W}}$ имеет c нулевых собственных значений, то граф W содержит c компонент связности [13].

Следствие 1. Если ранг ${\text{rank}}\;{{L}_{W}} = N - c$, то граф W содержит c компонент связности.

Следствие 2. Если ранг ${\text{rank}}\;{{L}_{W}} = N - c$, то связанной перестановкой строк и столбцов можно свести матрицу W к блочно-диагональному виду.

Методы [9, 11, 12] объединяют информацию из разных аспектов для создания матрицы сродства. При этом методы GBS и MVGL используют дополнительную информацию о взаимосвязях аспектов. Однако матрицы смежности для каждого аспекта получаются отдельно и далее не меняются. Если многоаспектные данные содержат шум или пропуски, первоначально построенные матрицы смежности не могут точно выразить корреляции объектов в каждом отдельном аспекте, получаемая матрица сродства также не точна и качество кластеризации падает. Имеет смысл улучшать построенные матрицы смежности, используя матрицу сродства, объединяющую все аспекты.

В статье предлагается новый алгоритм МАКП: адаптивное обучение глобального графа сродства (adaptive global affinity graph learning, AGAGL). На рис. 1 показана общая схема работы AGAGL, включающая начальное построение матриц смежности отдельных аспектов, сведение этих матриц к одной глобальной матрице сродства с использованием функции невязки и ограничения на ранг матрицы Лапласа. После получения матрицы сродства пересчитываются матрицы смежности. В конечном счете разбиение на кластеры получается, согласно следствию 1, непосредственно из глобальной матрицы сродства без каких-либо дополнительных алгоритмов кластеризации.

Особенности представленного метода:

1) введена функция невязки между глобальной матрицей сродства и матрицами смежности отдельных аспектов;

2) на каждом шаге итеративно пересчитываются матрица сродства и матрицы смежности;

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

Далее в разд. 1 дана постановка задачи и описаны некоторые применяемые методы, в разд. 2 рассмотрен предлагаемый метод и процедура оптимизации. Экспериментальные результаты и анализ приведены в разд. 3.

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

1.1. Кластеризация подпространств. Пусть в линейном пространстве размерности d задано c попарно не совпадающих подпространств. Из каждого подпространства взято несколько ненулевых объектов (векторов), их общее количество равно N, $N > d$. Эту совокупность назовем обучающей выборкой. Ее можно представить в виде матрицы $X = [{{x}_{1}}, \cdots ,{{x}_{N}}]$, составленной из столбцов-векторов ${{x}_{i}} \in {{\mathbb{R}}^{d}}$. Цель метода кластеризации подпространств – найти разбиение N объектов обучающей выборки на c кластеров, наиболее близкое к истинному, т.е. в каждом полученном кластере должны содержаться объекты одного подпространства. Предполагается, что каждый вектор обучающей выборки может быть представлен как линейная комбинация остальных:

Это можно записать в виде $X = XZ$, $X \in {{\mathbb{R}}^{{d \times N}}}$, $Z \in {{\mathbb{R}}^{{N \times N}}}$, ${\text{diag}}\;Z = 0$. Матрицу Z назовем матрицей смежности, элемент z_ij определяет сходство векторов x_i и x_j, $i \ne j$. Большую роль при обработке реальных данных играет также наличие шума измерения (относительно небольших случайных отклонений многих значений x_ij, как правило, описываемых нормальным распределением) и выбросов (больших отклонений некоторых векторов x_i). В этом случае разложение записывается как $X = XZ + E$, где $E \in {{\mathbb{R}}^{{d \times N}}}$ – матрица невязки. Эти представления неоднозначны, поэтому на матрицы смежности и невязки можно накладывать различные ограничения (регуляризации), получая различные алгоритмы, такие, как регрессия наименьших квадратов (least squares regression, LSR) [14], разреженный граф с ограничениями на блоки (blockwise constrained sparse graph, SGB) [15], низкоранговое представление (low-rank representation, LRR) [16], разреженная кластеризация подпространств (sparse subspace clustering, SSC) [17], и т.д.

LSR минимизирует взвешенную сумму нормы Фробениуса матрицы Z и матрицы невязки $E = X - XZ$. Такой подход хорошо работает на данных с гауссовым шумом. LSR формулируется как следующая оптимизационная задача:

где $\lambda $ – вес невязки. Запись s.t. обозначает “при условии”. Норма Фробениуса матрицы Z равна SGB вводит в целевую функцию слагаемое регуляризации графа и оптимизационная задача записывается как где $W$ – симметрическая весовая матрица, задающая априорные предположения о близости объектов, $\lambda $ – вес невязки разложения, $\mu $ – вес регуляризации графа. Во втором слагаемом целевой функции (1.2) применяется норма ${{l}_{{2,1}}}$. Минимизация этой нормы порождает матрицы невязки с нулевыми столбцами, что отвечает точному разложению соответствующих векторов [18]. Аналогично в SSC для Z используется норма l₁, а в методе LRR – следовая норма (сумма модулей сингулярных значений матрицы).

После нахождения оптимального решения Z окончательное разбиение на кластеры получается спектральной кластеризацией $Z$ [19–22].

1.2. МАКП. Набор данных с несколькими аспектами $X = \{ {{X}^{1}}, \cdots ,{{X}^{v}}\} $ представляет собой матрицу, составленную вертикально из ${v}$ матриц аспектов. Матрица i-го аспекта X ⁱ = = , d ⁱ – размерность аспекта, N – количество объектов выборки, $\sum {{{d}_{i}} = d} $. Есть два способа получить матрицу сродства Z для МАКП.

Первый способ. Сразу строить единую матрицу, общую для всех аспектов. Различные аспекты должны иметь одну и ту же матрицу смежности, поскольку данные каждого из них соответствуют одним и тем же объектам. Такой метод называется ранним слиянием (early fusion). В [23] предложена следующая модель раннего слияния:

где ${{\alpha }^{i}}$ – параметр невязки каждого аспекта, Z – общая матрица сродства. Недостаток методов раннего слияния состоит в том, что матрица сродства игнорирует разнообразие различных аспектов и не может сохранить локальную структуру многообразия каждого аспекта [24].

Второй способ. Получить матрицу смежности ${{Z}^{i}}$ для каждого аспекта, объединить эти отдельные матрицы в матрицу сродства Z [9, 25, 26] и, наконец, провести кластеризацию по Z. Такой метод называется поздним слиянием (late fusion). Например, в ESSB [9] матрица смежности каждого аспекта определяется решением следующей задачи:

Матрица сродства задается усреднением матриц смежности:

2. Метод AGAGL. Составим целевую функцию, сочетая кластеризацию подпространств, МАКП и вводя ограничения на ранг матрицы Лапласа.

2.1. Построение целевой функции. Аналогично регрессии наименьших квадратов (1.1) для матриц смежности ${{Z}^{i}}$ используется норма Фробениуса, для невязок ${{E}^{i}}$ берется норма ${{l}_{{2,1}}}$, порождающая матрицы с немногими ненулевыми столбцами, соответствующими выбросам данных [15]. Чтобы раскрыть внутреннюю локальную структуру данных, добавим к (1.1) слагаемое лапласовской регуляризации, которое обеспечивает то, что два похожих объекта в исходном пространстве близки и в новом пространстве [26]. Регуляризация лапласианом выражается как

где ${{w}_{{ij}}}$ – элемент весовой матрицы W, ${{L}_{W}}$ – ее лапласиан, полученный согласно (0.1). Тогда оптимизационная задача записывается как где $\lambda $ – вес невязки разложения, $\mu $ – вес регуляризации. Матрица смежности для каждого представления получается индивидуально и (2.1) является набором кластеризаций в отдельных аспектах. Следовательно, игнорируется дополнительная информация, скрытая во взаимосвязях различных аспектов, что приводит к снижению качества.

В связи с тем, что данные различных аспектов поступают от одних и тех же исходных объектов, существует общая структура кластера для всех аспектов. Следует найти глобальный граф сродства $S$ для описания общей структуры. Чтобы в полной мере использовать информацию о согласованности, скрытую в нескольких аспектах, определяется функция стоимости несогласия для измерения разницы между матрицей смежности ${{Z}^{i}}$ и общей матрицей сродства $S$:

Объединяя (2.1) и (2.2), можно записать задачу:

В известных из литературы методах МАК после получения матрицы сродства необходимо выполнить окончательную кластеризацию, например, методом k-средних или N-разреза. С ограничением ранга ${\text{rank}}\;{{L}_{S}} = N - c$ можно напрямую получить результат кластеризации из графа сродства S без каких-либо дополнительных шагов кластеризации. Поскольку ${{L}_{S}}$ является полуположительно определенной матрицей [27], все ее собственные значения неотрицательны. Предположим, что $N$ собственных значений ${{L}_{S}}$ упорядочены по возрастанию: $0 \leqslant {{\sigma }_{1}} \leqslant \cdots \leqslant {{\sigma }_{N}}$. Если выполняется rank${{L}_{S}} = N - c$, это означает, что сумма c наименьших собственных значений ${{L}_{S}}$ равна 0, т.е.

Согласно теореме, можно получить [28], что

Когда все элементы S нулевые, для (2.5) существует тривиальное решение. Чтобы избежать тривиального решения, добавляется ограничение $1 \cdot {{s}_{j}} = 1$, где ${{s}_{j}}$ представляет каждый столбец матрицы S, $1 = [1, \ldots ,1]$, точка обозначает операцию скалярного умножения векторов. Тогда (2.5) преобразуется в

Оптимизационную задачу AGAGL можно окончательно записать в виде

где $\alpha $, $\beta $ – масштабирующие константы.

2.2. Процедура оптимизации. Для решения задачи (2.7) применяется расширенный метод множителей Лагранжа. Расширенное уравнение Лагранжа может быть записано как

где $\varepsilon > 0$ – штрафной коэффициент, а ${{Y}^{i}}$ – множитель Лагранжа.

Итеративно решаются несколько подзадач.

Подзадача ${{Z}^{i}}$. Пересчитаем ${{Z}^{i}}$, фиксируя остальные переменные. Взяв частную производную лагранжиана по ${{Z}^{i}}$ и приравнивая ее к нулю, имеем

Подзадача ${{L}^{i}}$. Поскольку исходная выборка содержит шум и выбросы, ${{Z}^{i}}$ можно использовать для получения набора данных с уменьшенным шумом, обозначим его ${{\tilde {X}}^{i}} = {{X}^{i}}{{Z}^{i}}$. В отличие от большинства предыдущих работ, где строится граф k-ближайших соседей на исходном наборе данных, здесь можно построить матрицу весов ${{W}^{i}}$ на наборе данных ${{\tilde {X}}^{i}}$ и вычислить матрицу Лапласа, согласно (0.1).

Подзадача ${{E}^{i}}$. Для каждого ${{E}^{i}}$ отбрасываем другие несвязанные члены и получаем функцию как

Дальнейшее решение осуществляется с помощью оператора сжатия [29].

Подзадача S. Чтобы обновить S, другие переменные фиксируются. Целевая функция (2.7) может быть переформулирована как

Обозначая

получаем

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

где ${{s}_{{ij}}}$ – i-й элемент вектора s_j, и (2.12) переходит в

Обозначим i-й элемент вектора p_j как ${{p}_{{ij}}} = \beta \mathop {\left\| {{{q}_{i}} - {{q}_{j}}} \right\|}\nolimits_2^2 - {{m}_{{ij}}}$. Тогда целевая функция (2.13) записывается следующим образом:

Лагранжиан (2.14)

где $\eta $, $\rho $ – лагранжевы множители, $\rho $ – вектор, $\eta $ – константа. Согласно условию Каруша–Куна–Таккера [30], оптимальным решением (2.14) является

Подзадача Q. Фиксируя S, пересчитываем Q:

В (2.17) оптимальное решение Q составлено из собственных векторов, соответствующих c наименьшим собственным значениям матрицы Лапласа графа ${{L}_{S}}$.

Шаги предлагаемого алгоритма AGAGL даны ниже. Согласно следствию 1, если ${\text{rank}}\,{{L}_{S}}$ = N – c, то выборку можно напрямую разделить на c кластеров – компонент связности глобального графа сродства. Следовательно, условием остановки алгоритма является то, что сумма c наименьших собственных значений ${{L}_{S}}$ равна нулю, т.е. выполняется (2.4).

Алгоритм AGAGL.

Вход: многоаспектный набор данных X, параметры $\lambda $, $\mu $, $\alpha $, $\beta $, количество кластеров $c$, число ближайших соседей $k$ (для вспомогательного метода).

Выход: матрица $S$, содержащая $c$ компонент связности.

Шаг 1. Для каждого ${{X}^{i}}$ построить ${{L}^{i}}$ методом $k$ ближайших соседей.

Шаг 2. Рассчитать ${{Z}^{i}}$, согласно (2.9), при $S = 0$.

Шаг 3. Вычислить $S = \sum\limits_{i = 1}^v \,{{Z}^{i}}$.

Шаг 4. Определить $Q$, согласно (2.17).

Шаг 5. Присвоить ${{\varepsilon }_{0}} = {{10}^{{ - 6}}}$, ${{\varepsilon }_{{max}}} = {{10}^{6}}$, ${{E}^{i}} = 0$, ${{Y}^{i}} = 0$, $p = 1$.

Шаг 6. Для $i = 1,2, \ldots ,{v}$.

Шаг 7. Пересчитать ${{Z}^{i}}$, согласно (2.9).

Шаг 8. Составить матрицу Лапласа набора ${{\tilde {X}}^{i}} = {{X}^{i}}{{Z}^{i}}$.

Шаг 9. Пересчитать ${{E}^{i}}$, согласно (2.10).

Шаг 10. Пересчитать множители Лагранжа: ${{Y}^{i}} = {{Y}^{i}} + \varepsilon ({{X}^{i}} - {{X}^{i}}{{Z}^{i}} - {{E}^{i}})$.

Шаг 11. Пересчитать $\varepsilon = min(p\varepsilon ,{{\varepsilon }_{{max}}})$.

Шаг 12. Конец цикла по i.

Шаг 13. Для $j = 1,2, \ldots ,N$.

Шаг 14. Пересчитать $j$-й столбец $S$, согласно (2.16);

Шаг 15. Конец цикла по $j$.

Шаг 16. Вычислить матрицу сродства $S = \tfrac{1}{2}(S + {{S}^{{\text{T}}}})$.

Шаг 17. Сформировать $Q$ по c наименьшим собственным значениям ${{L}_{S}}$.

Шаг 18. Если $S$ содержит c связных компонент – завершить, иначе перейти к шагу 6.

2.3. Вычислительная сложность. В алгоритме есть пять неизвестных переменных, а именно ${{Z}^{i}}$, ${{L}^{i}}$, ${{E}^{i}}$, $S$ и $Q$. Каждая из них пересчитывается итеративно в указанном порядке. Основная вычислительная сложность складывается из четырех подзадач. При обновлении ${{Z}^{i}}$ сложность в основном связана с обращением и умножением матрицы и составляет $O({v}{{N}^{3}} + d{{N}^{2}})$, где $d = \sum {{{d}_{{v}}}} $ – общая размерность данных всех аспектов. Для пересчета $S$ необходимо рассмотреть каждый столбец ${{s}_{j}}$. Стоимость рассмотрения каждого столбца равна $O(N)$. Таким образом стоимость пересчета $S$ составляет $O({{N}^{2}})$. Чтобы решить $Q$, вычисляются $c$ собственных векторов матрицы Лапласа ${{L}_{S}}$, а сложность составляет $O(c{{N}^{2}})$. Итак, общая вычислительная сложность есть $O({v}{{N}^{3}}$ + dN² + cN²).

3. Эксперименты. В этом разделе описано проведение вычислительных экспериментов: наборы данных, меры, оценка качества, алгоритмы, с которыми сравнивается представленный метод, результаты сравнения. Представлено влияние параметров метода на качество кластеризации, исследована сходимость.

3.1. Наборы данных. Для экспериментов было выбрано пять наборов данных.

Набор BBC [31] содержит тексты 145 документов. Каждый документ разделен на четыре части, поэтому набор данных содержит четыре разных аспекта.

Набор Caltech-101 [32] содержит 8677 изображений из 101 категории. Для экспериментов выбраны наиболее широко представленные семь классов, включая лица, мотоциклы, купюры, Гарфилд, знак “стоп”, кресло; общее количество изображений составляет 1474. Каждое изображение описывается шестью аспектами, такими, как 40-мерные моменты вейвлетов, 48-мерное преобразование Габора, 254-мерные признаки CENTRIST [33], 1984-мерная гистограмма ориентированных градиентов (HOG), 512-мерный GIST [34] и 928-мерные локальные бинарные шаблоны (LBP).

Набор MFD [35] содержит образцы рукописных цифр – 10 классов от 0 до 9, всего 2000 образцов. Образцы представлены шестью различными способами, включая 76-мерные коэффициенты Фурье форм символов, 216-мерные профильные корреляции, 64-мерные коэффициенты Карунена–Лоэва, 240 средних значений пикселей в окнах 2 × 3, 47-мерный момент Цернике и 6-мерный морфологический.

Набор HW2sources также содержит рукописные цифры от 0 до 9. Случайным образом выбрано 2000 образцов из баз MNIST [36] и USPS [37] по 200 каждого класса. Поскольку образцы классов получены из двух разных источников, то набор HW2sources имеет два аспекта.

Набор 3sources содержит 169 текстов новостей, разделенных на шесть классов. Новости взяты из трех источников: BBC, Reuters и Guardian.

В табл. 1 даны характеристики этих наборов.

3.2. Меры качества. Чтобы сравнить предложенный алгоритм с другими, используются три показателя оценки качества кластеризации: точность, нормализованная взаимная информация, чистота.

Точность. Обозначим через ${{U}_{i}}$ истинный номер кластера, куда входит объект ${{x}_{i}}$, ${{V}_{i}}$ – номер кластера, куда попал этот объект при кластеризации, $\nu (x)$ – перенумерация, обладающая свойством $a = b \Leftrightarrow \nu (a) = \nu (b)$, $\delta $ – символ Кронекера. Точность кластеризации ${{Q}_{{Acc}}}$ – доля объектов, правильно отнесенных к кластерам при оптимальной перенумерации (используется венгерский алгоритм [38]):

Нормализованная взаимная информация. Даны два набора кластеров $U$ и $V$, которые обозначаются как $U = \{ {{U}_{1}}, \cdots ,{{U}_{k}}\} $ и $V = \{ {{V}_{1}}, \cdots ,{{V}_{m}}\} $. Если взять в качестве $U$ истинное разбиение, известное из обучающей выборки, то качество кластеризации разбиения $V$ можно определить как нормализованную взаимную информацию наборов кластеров $U$ и $V$:

где $P({{U}_{i}})$ и $P({{V}_{j}})$ представляют вероятность того, что случайная выборка из набора данных принадлежит кластерам ${{U}_{i}}$ и ${{V}_{j}}$ соответственно, $P({{U}_{i}},{{V}_{j}})$ – вероятность того, что случайная выборка принадлежит обоим кластерам. Величина обозначает энтропию набора кластеров.

Чистота. Пусть задан набор $c$ кластеров $\left\{ {{{C}_{1}}, \cdots ,{{C}_{c}}} \right\}$, ${{m}_{i}} = {\text{|}}{{C}_{i}}{\text{|}}$ – число объектов в ${{C}_{i}}$, ${{m}_{{ij}}}$ – число объектов истинного класса  j, попавших в кластер ${{C}_{i}}$, ${{P}_{{ij}}} = {{m}_{i}}{\text{/}}{{m}_{{ij}}}$ – вероятность того, что объект из кластера ${{C}_{i}}$ принадлежит классу  j. Чистотой кластера ${{C}_{i}}$ назовем величину $P({{C}_{i}}) = \mathop {max}\limits_j {{P}_{{ij}}}$, чистотой всего разбиения – величину

где N – общее число объектов выборки.

3.3. Алгоритмы сравнения. Метода сравнивается с шестью классическими алгоритмами:

k-средних: базовый алгоритм кластеризации, применяется к наборам данных с одним аспектом, исполняется для каждого аспекта, в качестве результата берется среднее (1.5);

ESSB [9]: сегментация ансамбля подпространств при блочных ограничениях;

AMGL [39]: взвешенное обучение системы графов (auto-weighted multiple graph learning, AMGL) – алгоритм, автоматически определяющий оптимальный вес для графа каждого аспекта;

GBS [11]: система кластеризации на основе графов;

MVGL [12]: многоаспектная кластеризация обучением графа;

DSS-MSC [40]: многоаспектная кластеризация подпространств с двойным разделением (dual shared-specific multi-view subspace clustering) одновременно извлекает информацию общую для нескольких аспектов и выделяет в каждом из аспектов специфический остаток.

3.4. Результаты эксперимента. Каждый из алгоритмов 30 раз выполнен для каждого набора данных. В табл. 2–4 приведены средние значения и среднеквадратичные отклонения для ${{Q}_{{Acc}}}$, ${{Q}_{{NMI}}}$ и ${{Q}_{{Pur}}}$.

Из таблиц видно, что предлагаемый метод в целом лучше известных из литературы. AGAGL получает лучшие результаты по всем наборам данных, кроме набора данных Caltech-101 с точки зрения ${{Q}_{{NMI}}}$ и ${{Q}_{{Pur}}}$. По сравнению с некоторыми алгоритмами, такими, как ESSB, DSS-MSC и AMGL, предложенный метод не требует дополнительного шага кластеризации на изученном графе.

3.5. Анализ чувствительности параметров. В статье в основном используются четыре параметра: $\lambda $, $\mu $, $\alpha $, $\beta $. Их влияние на показатели кластеризации изучалось на наборе данных MFD.

Влияние $\alpha $, $\beta $ на качество кластеризации. Для фиксированных значений $\lambda = 1$ и $\mu = 1$ проверены значения $\alpha = $ $\{ 0.5,0.6,0.7,0.8,0.9,1.0\} $ и $\beta = $ $\{ 0.001,0.01,0.1,1,10\} $, произведено 15 прогонов. На рис. 2 показаны величины ACC, NMI и Purity.

Как видно из рисунков, значения ${{Q}_{{Acc}}}$, ${{Q}_{{NMI}}}$ и ${{Q}_{{Pur}}}$ максимальны при значении веса рангового ограничения $\beta = 0.1$ и веса невязки $\alpha = 0.7$.

Влияние $\lambda $, $\mu $ на качество кластеризации. При фиксированных значениях $\alpha = 0.5$ и $\beta = 0.1$ значения параметров $\lambda $ и $\mu $ перебираются на множестве $\{ 0.01,\;0.1,\;1,\;10,\;100\} $, производено 15 прогонов. На рис. 3 даны величины ${{Q}_{{Acc}}}$, ${{Q}_{{NMI}}}$ и ${{Q}_{{Pur}}}$.

3.6. Обученный граф сродства. Чтобы отразить качество глобального графа сродства предложенного метода, проведены эксперименты с набором данных MFD и получен глобальный граф сродства с блочно-диагональной структурой. На рис. 4 показаны сгенерированные на разных итерациях граф смежности Z, рассчитанный как среднее значение суммы матриц смежности различных представлений (1.5) (в левой колонке) и глобальный граф сродства S (в правой колонке). Верхний ряд соответствует четвeртой итерации, нижний – десятой. Как видно из рисунка, глобальный граф сродства, построенный предложенным методом, лучше кластеризует данные, чем Z.

3.7. Исследование сходимости. Проверка сходимости метода сделана на наборах MFD и HW2sources, которые содержат большое количество выборок. На рис. 5 приведены графики значения целевой функции по итерациям. Видно, что для обоих наборов данных постоянное значение целевой функции достигается уже в районе 10-й итерации, т.е. граф сродства, содержащий искомые $c$ компонент связности, получается за 10 итераций.

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