Известия РАН. Теория и системы управления, 2023, № 3, стр. 14-37

Введение. Многоаспектные данные могут дать больше информации, чем данные с одним аспектом, во многих практических задачах. Многоаспектная кластеризация (МАК) стала актуальной в связи с получением большого количества таких данных [1]. Большинство существующих методов хорошо работают в предположении, что данные являются полными, т.е. для каждого образца есть его представление в каждом аспекте. Однако это предположение не всегда справедливо на практике. Например, при диагностике болезни Альцгеймера [2] по разным причинам не все виды обследований пациента доступны, что приводит к неполным многоаспектным данным. Соответственно кластеризация таких данных в последнее время привлекает все больше внимания.

В последние годы были разработаны некоторые методы многоаспектной кластеризации неполных данных (также неполная многоаспектная кластеризация, НМАК) (incomplete multi-view clustering, IMVC), некоторые из них кратко описаны в разд. 1. НМАК на основе графов привлекла внимание многих исследователей благодаря тому, что граф является мощным инструментом для анализа взаимосвязей [3]. Неполная многоаспектная спектральная кластеризация с адаптивным обучением графов (incomplete multi-view spectral clustering with adaptive graph learning, IMSC_AGL) [4] использует графы, построенные из низкорангового подпространства каждого аспекта для формирования согласованного низкоразмерного представления каждого образца. Обобщенная НМАК с гибким распространением структуры локальности (generalized incomplete multi-view clustering with flexible locality structure diffusion, GIMC_FLSD) [5] комбинирует обучение графов и факторизацию матриц для получения унифицированного представления, которое сохраняет информацию графа. Неполное обучение неотрицательного представления с несколькими графами (incomplete multi-view non-negative representation learning, IMNRL) [6] выполняет факторизацию матриц нескольких неполных графов для получения согласованного неотрицательного представления с ограничениями на графы. Адаптивная кластеризация неполных графов на основе пополнения графов (adaptive graph completion based incomplete multi-view clustering, AGC_IMC) [7] выполняет последовательное обучение на представлениях, используя представление графа каждого аспекта в качестве регуляризации неполных данных других аспектов, и далее получает согласованное низкоразмерное представление. Эти методы применяют обучение графов для фиксации локальной топологии представления. Однако при этом учитывается только внутриаспектное сходство представленных образцов и игнорируется межаспектное сходство. Поэтому эта группа методов не может эффективно найти дополнительную информацию, скрытую в различных аспектах.

Корреляция – классическая мера, которую можно применить для получения дополнительной информации из многоаспектных данных. Для работы с неполными многоаспектными данными, содержащими информацию о корреляции между аспектами, предложено несколько тензорных методов. В работе [8] используются представления подпространства с тензорными ограничениями низкого ранга, чтобы исследовать внутри- и межаспектные связи между образцами и одновременно улавливать корреляции высокого порядка между несколькими аспектами. Неполная многоаспектная тензорная спектральная кластеризация с выводом отсутствующих представлений (incomplete multi-view tensor spectral clustering with missing view inferring, IMVTSC-MVI) [9] объединяет в единую структуру пространство признаков, пополненное отсутствующими представлениями, и пространство многообразий, основанное на обучении графов сходства. Стоит отметить, что IMVTSC-MVI рассматривает каждый аспект одинаково, т.е. с одинаковым весом. В [10] предлагается получать полный граф для каждого аспекта, учитывая сходство графов между аспектами и применяя метод дополнения тензоров. Хотя вышеупомянутые методы на основе тензоров достигли хороших результатов, все еще существуют некоторые проблемы. В большинстве известных работ ограничение низкого ранга действует для преобразованного графа, что значительно увеличивает вычислительные затраты. Это связано с тем, что необходимо выполнение сингулярного разложения на каждом фронтальном срезе тензора $n \times m \times n$, где n и m – количество образцов и аспектов соответственно. С этой целью в данной работе для уменьшения вычислительной сложности определяется ядерная норма тензора, использующая полуортогональную матрицу.

Предлагаемый метод называется улучшение неполной многоаспектной кластеризации пополнением тензорного графа (enhancing incomplete multi-view clustering via tensor graph completion, EIMC_TGC). Метод объединяет пополнение тензорного графа, адаптивное взвешивание аспектов и последовательную кластеризацию подпространств в единую структуру. Отличительная особенность метода – переопределение ядерной нормы тензора на основе полуортогональной матрицы для сокращения вычислений и определение оператора сжатия для получения аналитических решений подзадач. Вклад данной работы сводится к следующим выводам.

1. Предлагается метод НМАК, использующий тензорное пополнение. В отличие от существующего метода МАК на основе тензорной нормы, мы переопределяем тензорную ядерную норму через полуортогональную, что снижает вычислительные затраты, и адаптивно назначаем веса каждому аспекту.

2. Для получения аналитического решения подзадачи с переопределенной ядерной нормой предусмотрен оператор сжатия. Предлагается алгоритм оптимизации на основе расширенного метода множителей Лагранжа (augmented Lagrange multiplier, ALM).

3. Эксперименты на четырех наборах данных подтверждают, что этот метод эффективен в задачах кластеризации.

Структура данной работы следующая. В разд. 1 кратко представлены известные аналогичные работы. В разд. 2 изложен предлагаемый метод и дан алгоритм решения. В разд. 3 описана проверка эффективности метода численными экспериментами. В разд. 3.4 подводятся итоги работы.

1. Известные аналоги. В этом разделе представлены известные из литературы последних лет методы обработки неполных многоаспектных данных, а также некоторые обозначения и базовые определения. Методы НМАК можно разделить на пять категорий по основному используемому подходу: кластеризация подпространств, факторизация неотрицательных матриц, обучение графов, глубокие нейронные сети, вероятностный подход.

Методы кластеризации подпространства [11–16] проецируют все существующие аспекты в общее низкоразмерное подпространство и выравнивают все представления в этом подпространстве для получения согласованного низкоразмерного представления. Например, в [15] используется разреженное низкоранговое представление подпространства для совместного измерения внутриаспектных и межаспектных отношений. В [12] предложен полупарный обобщенный корреляционный анализ с частичным обучением (semi-paired and semi-supervised generalized correlation analysis, S²GCA) на основе канонического корреляционного анализа (canonical correlation analysis, CCA), который обрабатывает неполные данные и применим к сценарию с частичным привлечением учителя.

Методы на базе неотрицательной матричной факторизации (non-negative matrix factorization, NMF) [17–22] направлены на разложение матрицы данных каждого аспекта на произведение одной общей (базисной) матрицы и матрицы, соответствующей каждому из аспектов. Например, в [17] предложена частичная МАК на основе NMF для изучения общего представления для полных выборок и частного скрытого представления с той же матрицей базиса. Многоаспектное обучение с неполными аспектами (multi-view learning with incomplete views, MVL-IV) [18] факторизует матрицу неполных данных каждого аспекта как произведение общей матрицы и базисной матрицы соответствующего аспекта, имеющей низкий ранг.

Методы на основе обучения графа [23–27] строят общую матрицу графа связности (или матрицу ядра), так чтобы сохранить геометрическую структуру. Эти методы используют спектральную кластеризацию и многоядерное обучение. Например, НМАК адаптивным пополнением графа (adaptive graph completion based incomplete multi-view clustering, AGC_IMC) [7] получает общий граф с помощью специальной регуляризации и далее добивается согласованного низкоразмерного представления образцов. Метод неполных многоядерных k-средних с взаимным дополнением ядер (incomplete multiple kernel k-means with mutual kernel completion, MKKM-IK-MKC) [23] получает неполные матрицы ядер и осуществляет интерполяцию.

Методы на основе глубоких нейронных сетей [28–32] используют мощную способность нейронной сети к выделению признаков. Например, в [29] разработан новый метод НМАК, который проецирует все данные нескольких видов на полное и единое представление с ограничением присущей геометрической структуры. В [31, 32] предложена НМАК с применением генеративной состязательной сети [33], которая порождает недостающие данные на основе имеющихся. В [34] единое представление получается путем максимизации взаимной информации между различными аспектами посредством контрастного обучения, недостающие данные восстанавливаются путем минимизации условной энтропии различных аспектов.

Методы, основанные на вероятностном подходе [35–38], обычно используют байесовскую статистику, гауссовские модели, вариационный вывод и другие инструменты для моделирования многоаспектных данных с вероятностной точки зрения. Например, в [37] применяется модель латентных переменных общего гауссовского процесса для моделирования неполных многоаспектных данных для кластеризации. В [36] для обработки неполных многоаспектных данных предложено объединение байесовского канонического корреляционного анализа [39] и обучения с учителем [40].

Существует два подхода к использованию тензоров в многоаспектном обучении. Первый заключается в том, чтобы рассматривать различные аспекты как подпространства пространства высокой размерности и обрабатывать их соответственно. Представителем первого подхода является тензорный канонический корреляционный анализ (tensor canonical correlation analysis, TCCA) [41]. TCCA определяет ковариационный тензор для обработки многоаспектных данных с произвольным количеством аспектов, расширяя матрицу взаимной ковариации в каноническом корреляционном анализе. Глубокий TCCA (deep TCCA, DTCCA) [42] объединяет TCCA с глубоким обучением нейросетей. DTCCA может не только обрабатывать данные с произвольным количеством аспектов, но и не требует хранения всего тензора, что означает, что он может обрабатывать большое количество данных. В [43] рассматривались многоаспектные данные как тензор размерности 3, для вычисления низкоразмерного представления образцов использовано разложение Такера.

Второй подход предполагает, что графы различных представлений похожи, т.е. тензор данных имеет низкий ранг. Низкоранговая тензорная многоаспектная кластеризация подпространств (low-rank tensor constrained multi-view subspace clustering, LT-MSC) [44] рассматривает совокупность матриц данных различных аспектов как тензор, ранг которого должен быть ограничен, что уменьшает избыточность данных и повышает качество кластеризации. В [45] применен известный своей устойчивостью метод анализа главных компонент, сохраняющий низкий ранг тензора, построенного на основе вероятностых переходных матриц.

1.1. Обозначения. Матрицы обозначаются курсивными прописными буквами, например $X \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}}}}}$. Элемент матрицы задается двумя индексами (номерами строки и столбца), таким образом матрица имеет размерность 2. Несколько матриц размерности 2 одного размера можно объединить в матрицу размерности 3, далее называемую тензором²². Матрицы, составляющие тензор, называются слоями. Тензоры обозначаются заглавными каллиграфическими буквами, например $\mathcal{X} \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}} \times {{n}_{3}}}}}$ – тензор из ${{n}_{1}}$ строк, ${{n}_{2}}$ столбцов и ${{n}_{3}}$ слоев. Некоторые основные обозначения приведены в табл. 1.

Определение 1. Рассмотрим тензор $\mathcal{X} \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}} \times {{n}_{3}}}}}$. Слой с номером k представляет собой матрицу, составленную из элементов тензора $\mathcal{X}$, с третьим индексом, равным k: ${{\mathcal{X}}_{{(:,:,k)}}} \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}}}}}$, $k = \overline {1,{{n}_{3}}} $. Для краткости будем обозначать ${{X}^{{(k)}}} \equiv {{\mathcal{X}}_{{(:,:,k)}}}$. Также можно называть слой фронтальным срезом.

Определение 2. Аналогично j-м боковым срезом назовем матрицу, составленную из элементов тензора с фиксированным вторым индексом (номером столбца): ${{\mathcal{X}}_{{(:,j,:)}}} \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{3}}}}}$, $j = \overline {1,{{n}_{2}}} $.

Определение 3. Трубкой тензора $\mathcal{X}$ назовем вектор, составленный из элементов тензора с двумя фиксированными индексами. Здесь используются трубки с фиксированными первыми двумя индексами: $x = {{\mathcal{X}}_{{(i,j,:)}}} \in {{\mathbb{R}}^{{{{n}_{3}}}}}$.

Определение 4. Для тензора $\mathcal{X} \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}} \times {{n}_{3}}}}}$ введем операцию разворачивания:

которая переводит его в матрицу.

Определение 5. Обратная операция сворачивания переводит матрицу в тензор:

Определение 6. Для тензора $\mathcal{X} \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}} \times {{n}_{3}}}}}$ и матрицы $\Phi \in {{\mathbb{R}}^{{{{n}_{3}} \times {{n}_{3}}}}}$ определим трансформированный тензор ${{\mathcal{X}}_{\Phi }} \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}} \times {{n}_{3}}}}}$, составленный из боковых срезов исходного тензора, умноженных на матрицу Φ, так что ${{\mathcal{X}}_{\Phi }}_{{(:,i,:)}} = {{\mathcal{X}}_{{(:,i,:)}}}\Phi $.

2. Предлагаемый метод. Канонический корреляционный анализ (ККА) является классическим и эффективным методом для многоаспектного обучения. ККА может обрабатывать только два аспекта. По этой причине для обработки данных с большим числом аспектов предлагается обобщенный ККА (generalized CCA, GCCA) [46]. В частности, дается выборка из $n$ образцов в $m$ аспектах $\left\{ {{{X}_{i}} \in {{\mathbb{R}}^{{{{d}_{i}} \times n}}}} \right\}_{{i = 1}}^{m}$, где d_i – размерность $i$-го аспекта. Тогда модель GCCA представляется как

где запись s.t. обозначает “при условии”, I – единичная матрица, ${{\left\| A \right\|}_{F}}$ – норма Фробениуса матрицы A: Норма Фробениуса для тензора определяет аналогично:

Символы A и $\left\{ {{{W}_{i}}} \right\}_{{i = 1}}^{m}$ в уравнении (2.1) – это последовательное низкоразмерное представление образцов и матрица проекции каждого аспекта соответственно. Геометрическая структура среди образцов является достоверной априорной информацией, которая может быть эффективно закодирована графом. Следовательно, для получения согласованного низкоразмерного представления с сохранением структуры предлагается графовый многоаспектный ККА (graph multi-view CCA, GMCCA) [47], целевая функция приобретает следующий вид:

где ${{L}_{G}}$ – матрица лапласиана предварительно построенного графа G, а $\lambda > 0$ – параметр регуляризации.

К сожалению, вышеупомянутый метод применим только к полным многоаспектным данным. Здесь на основе GMCCA и восстановления тензоров разработан новый метод для неполных многоаспектных данных. Для заданного неполного набора данных $\{ {{X}_{i}} \in {{\mathbb{R}}^{{{{d}_{i}}}}} \times n\} _{{i = 1}}^{m}$ с $m$ аспектами и $n$ образцами, недостающие экземпляры которых заполняются нулевыми векторами, т.е. если j-й экземпляр i-го представления отсутствует, то ${{X}_{{i(:,j)}}} = \vec {0}$. Недостающая информация каждого представления записывается в диагональную матрицу $\left\{ {{{P}_{i}} \in {{\mathbb{R}}^{{n \times n}}}} \right\}_{{i = 1}}^{m}$. ${{P}_{i}}$ определяется следующим образом:

Символ ${{d}_{i}}$ обозначает размерность признака $i$-го представления. Наивная модель для обработки неполных многоаспектных данных, основанная на (2.4), выглядит следующим образом:

где ${{L}_{{{{G}_{i}}}}}$ – матрица лапласиана предварительно построенного графа ${{G}_{i}}$ $i$-го представления. Стоит отметить, что модель (2.6) рассматривает каждое представление одинаково, что обычно нереалистично. По этой причине аналогично [48] вводятся веса $\left\{ {{{{\bar {\delta }}}_{i}}} \right\}_{{i = 1}}^{m}$ для взвешивания важности различных представлений:

Интуитивно понятно, что если i-й аспект может предоставить больше полезной информации, то $\left\| {\left( {A - W_{i}^{ \top }{{X}_{i}}} \right){{P}_{i}}} \right\|_{F}^{2}$ и ${\text{tr}}\left( {A{{L}_{{{{G}_{i}}}}}{{A}^{ \top }}} \right)$ должны быть малы, и поэтому вес ${{\bar {\delta }}_{i}}$ для этого аспекта будет большим в соответствии с уравнением (2.7) и наоборот. Однако если представление имеет высокий процент пропусков, то вес этого представления также будет больше. Это происходит потому, что высокий процент пропусков приводит к тому, что ${{P}_{i}}$ содержит больше нулей, что в свою очередь делает ${{\bar {\delta }}_{i}}$ больше. Чтобы избежать этого явления, вес изменен на

где ${{n}_{i}}$ – количество доступных экземпляров i-го аспекта.

Невозможно напрямую построить полный граф ${{G}_{i}}$ для каждого аспекта из-за неполноты данных. Поэтому его необходимо дополнить [7, 23]. Согласованность между аспектами является важным свойством реальных данных. Соответственно графы различных аспектов должны быть очень похожими. Это свойство хорошо отражается низким рангом тензора, составленного из этих графов (матриц смежности). Следовательно, исходя из восстановления тензора, целевая функция для восстановления графов выражается следующим образом:

где $\mathcal{G} \in {{\mathbb{R}}^{{n \times m \times n}}}$ и ${{\mathcal{G}}_{{\left( {:,i,:} \right)}}} = {{G}_{i}}$, 1 – вектор соответствующей размерности со всеми единичными компонентами, $\mathcal{M} \in {{\mathbb{R}}^{{n \times m \times n}}}$ – тензор предварительно построенного неполного графа с недостающими позициями, заполненными нулями, где ${{\mathcal{M}}_{{\left( {:,i,:} \right)}}} = {{M}_{i}}$ – предварительно построенный граф i-го аспекта, ${{P}_{\Omega }}\left( \cdot \right)$ – ортогональная проекция на линейное подпространство тензора, определенного на $\Omega = \left\{ {\left( {i,j,k} \right)|{{\mathcal{M}}_{{\left( {i,j,k} \right)}}}{\text{не}}\,\,{\text{пропущено}}} \right\}$:

Тензорная норма ${{\left\| \cdot \right\|}_{{\Phi ,w,{{S}_{p}}}}}$ определена следующим образом.

Определение 7. Пусть задан тензор $\mathcal{X} \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}} \times {{n}_{3}}}}}$, $h = {\text{min}}\left( {{{n}_{1}},{{n}_{3}}} \right)$, вектор весов $w \in {{\mathbb{R}}^{h}}$, при этом ${{w}_{1}} \geqslant {{w}_{2}} \geqslant \; \cdots \; \geqslant {{w}_{l}} \geqslant 0$, $0 < p \leqslant 1$, и матрица преобразования $\Phi \in {{\mathbb{R}}^{{{{n}_{3}} \times r}}}$, тогда

где $X_{\Phi }^{{(i)}}$ – i-й фронтальный срез тензора $\mathcal{X}$, трансформированного матрицей $\Phi $.

Примечание 1. Заметим, что в литературе [9, 10] матрица преобразования обычно является ортогональной квадратной матрицей, т.е. ${{\Phi }^{ \top }}\Phi = I$ и $r = {{n}_{3}}$. Наше эмпирическое исследование показывает, что в этом нет необходимости. Поэтому в данной работе в качестве матрицы преобразования используется полуортогональная матрица, т.е. ${{\Phi }^{ \top }}\Phi = I$ и $r < {{n}_{3}}$. Это позволит сократить вычислительные затраты, т.е. если раньше требовалось ${{n}_{3}}$ разложения по сингулярным значениям, то теперь требуется только r. Экспериментальное исследование в разд. 3.4 показывает, что $r = {{n}_{3}}$ может быть не оптимальным.

Объединив модель восстановления графов (2.9) с (2.6) и введя веса $\left\{ {{{\delta }_{i}}} \right\}_{{i = 1}}^{m}$ согласно (2.7) и (2.8), получаем следующую модель:

где $\mu > 0$ – параметр регуляризации. Схема предложенного метода дана на рис. 1.

Примечание 2. Известно [49], что количество нулевых собственных значений матрицы Лапласиана ${{L}_{G}}$ должно быть равно количеству связных компонент графа G. Другими словами, для графа с $c$ компонент связности

Имеет место следующее уравнение:

Поскольку правая часть (2.14) формально идентична члену ${\text{tr}}(A{{L}_{{{{G}_{i}}}}}{{A}^{ \top }})$ в целевой функции (2.12), можно ожидать, что решение задачи (2.12) породит разбиение на малое число компонент, т.е. хорошую кластеризацию. Примечательно, что наш метод может работать с неполными выборками с выученными $\left\{ {{{W}_{i}}} \right\}_{{i = 1}}^{m}$.

2.1. Решение. Для эффективного решения задачи (2.12) нам необходимо ввести вспомогательную переменную $\mathcal{Y}$, чтобы разделить взаимозависимые члены так, чтобы они могли быть решены независимо. Таким образом, можно переформулировать задачу (2.12) в следующую эквивалентную форму:

где ${{\delta }_{i}}$ задается (2.7). Воспользовавшись недавними достижениями в области методов переменных направлений, предложим эффективный алгоритм, основанный на методе неопределенных множителей Лагранжа (inexact augmented Lagrange multipliers, IALM) для решения (2.15). Расширенная функция Лагранжа задается следующим образом: где $\rho > 0$ – штрафной параметр, $\mathcal{C} \in {{\mathbb{R}}^{{n \times m \times n}}}$ – множители Лагранжа. В этом разделе используются надстрочные знаки для обозначения количества итераций, т.е. A^k или ${{A}^{{k + 1}}}$ и т.д.

2.1.1. Пересчет ${{A}^{{k + 1}}}$ и $\left\{ {W_{i}^{{k + 1}}} \right\}_{{i = 1}}^{m}$ с фиксированными ${{\mathcal{G}}^{k}}$ и $\left\{ {\delta _{i}^{k}} \right\}_{{i = 1}}^{m}$. Для обновления ${{A}^{{k + 1}}}$ и $\left\{ {W_{i}^{{k + 1}}} \right\}_{{i = 1}}^{m}$ рассмотрим следующие задачи оптимизации:

После простых алгебраических операций задача (2.17) может быть преобразована в следующую задачу на собственные значения:

где $\Sigma $ – диагональная матрица собственных значений. Тогда ${{A}^{ \top }}$ можно получить из собственного вектора, соответствующего первым d наибольшим собственным значениям, где d – размерность последовательного низкоразмерного представления (т.е. $A \in {{\mathbb{R}}^{{d \times n}}}$). Имея ${{A}^{{k + 1}}}$, можно получить $W_{i}^{{k + 1}} = {{\left( {{{X}_{i}}{{P}_{i}}X_{i}^{ \top }} \right)}^{{ - 1}}}{{X}_{i}}{{P}_{i}}{{A}^{{k + 1}}}^{ \top }$ для $i = \overline {1,m} $. После получения ${{A}^{{k + 1}}}$ и $\left\{ {W_{i}^{{k + 1}}} \right\}_{{i = 1}}^{m}$ веса $\left\{ {\delta _{i}^{{k + 1}}} \right\}_{{i = 1}}^{m}$ могут быть обновлены в соответствии с определением (2.7).

2.1.2. Пересчет ${{\mathcal{G}}^{{k + 1}}}$ с фиксированными ${{A}^{{k + 1}}}$, $\left\{ {\delta _{i}^{{k + 1}}} \right\}_{{i = 1}}^{m}$, ${{\mathcal{Y}}^{k}}$, ${{\mathcal{C}}^{k}}$ и ${{\rho }^{k}}$. Чтобы получить ${{\mathcal{G}}^{{k + 1}}}$, фиксируем другую переменную и решаем следующую задачу оптимизации:

Задача (2.19) – это задача наименьших квадратов с ограничениями. Заметим, что каждая трубка тензора задачи (2.19) независима, поэтому она может быть преобразована в $nm$ независимых подзадач. Без потери общности пусть $g \in {{\mathbb{R}}^{n}}$, $s \in {{\mathbb{R}}^{n}}$, $y \in {{\mathbb{R}}^{n}}$, $\omega \in {{\mathbb{R}}^{n}}$, $c \in {{\mathbb{R}}^{n}}$ и $t \in {{\mathbb{R}}^{n}}$ – определенные трубки тензоров $\mathcal{G}$, $\mathcal{M}$, $\mathcal{Y}$, $\Omega $, $\mathcal{C}$ и $\mathcal{T}$ соответственно, где $\mathcal{T}_{{\left( {i,j,l} \right)}}^{k} = \lambda \delta _{l}^{{k + 1}}{{\left\| {A_{{\left( {:,i} \right)}}^{{k + 1}} - A_{{\left( {:,j} \right)}}^{{k + 1}}} \right\|_{F}^{2}} \mathord{\left/ {\vphantom {{\left\| {A_{{\left( {:,i} \right)}}^{{k + 1}} - A_{{\left( {:,j} \right)}}^{{k + 1}}} \right\|_{F}^{2}} 2}} \right. \kern-0em} 2}$. Таким образом, можно получить следующую оптимизационную задачу:

Функцию Лагранжа для (2.20) запишем как

где $\alpha \in \mathbb{R}$ и $\beta \in {{\mathbb{R}}^{n}}$ являются множителями. Если взять производную функции Лагранжа по $g$ и положить ее равной нулю, то получится уравнение

Согласно условию KKT, т.е. ${{1}^{ \top }}g = 1$, имеем

Сочетая (2.22) и (2.23), получим

Далее, согласно дополнительной релаксации в условии KKT, имеем

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

Поскольку ${{{\mathbf{1}}}^{ \top }}{{g}^{{k + 1}}} = 1$, значение ${{{v}}^{k}}$ можно найти как корни следующей функции:

Уравнение (2.28) может быть решено методом Ньютона. Производная первого порядка от $f\left( {v} \right)$ имеет вид

где

Решение задачи (2.20) (получение $\mathcal{G}$) представим алгоритмом 1.

Алгоритм 1.

Вход: ${{t}^{k}}$, ${{\rho }^{k}}$, $\omega $, $z$, ${{c}^{k}}$, ${{t}^{k}}$.

Выход: Тензор ${{\mathcal{G}}^{{k + 1}}}$.

Шаг 1. Инициализация: Номер шага $q = 0$, ${{{v}}^{0}} = 0$.

Шаг 2. Вычислить u^k, согласно (2.26).

Шаг 3. Вычислить $f({{{v}}^{q}})$, согласно (2.28).

Шаг 4. Если $\left| {f({{{v}}^{q}})} \right| \leqslant {{10}^{{ - 10}}}$, то перейти к шагу 8.

Шаг 5. Вычислить градиент $f\left( {v} \right)$ в точке ${{{v}}^{q}}$, согласно (2.29).

Шаг 6. Пересчитать ${{{v}}^{{q + 1}}} = {{{{{v}}^{q}} - f({{{v}}^{q}})} \mathord{\left/ {\vphantom {{{{{v}}^{q}} - f({{{v}}^{q}})} {\nabla f({{{v}}^{q}})}}} \right. \kern-0em} {\nabla f({{{v}}^{q}})}}$.

Шаг 7. $q \leftarrow q + 1$ и перейти к шагу 3.

Шаг 8. Вычислить ${{g}^{{k + 1}}}$, согласно (2.27).

Шаг 9. Составить тензор ${{\mathcal{G}}^{{k + 1}}}$ из трубок ${{g}^{{k + 1}}}$.

2.1.3. Пересчет ${{\mathcal{Y}}^{{k + 1}}}$ с фиксированными ${{\mathcal{G}}^{{k + 1}}}$, ${{\mathcal{C}}^{k}}$ и ${{\rho }^{k}}$. При сохранении всех остальных переменных ${{\mathcal{G}}^{{k + 1}}}$ может быть получено путем решения следующей оптимизационной задачи:

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

Теорема 1. Пусть $\mathcal{A} \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}} \times {{n}_{3}}}}}$, $l = \min \{ {{n}_{1}},{{n}_{2}}\} $, ${{w}_{1}} \geqslant {{w}_{2}} \geqslant \; \cdots \; \geqslant {{w}_{l}} \geqslant 0$. Для модели

оптимальным решением является где ${{\mathcal{S}}_{{\tau ,w,p}}}\left( {{{\mathcal{A}}_{\Phi }}} \right)$ – тензор, $i$-й фронтальный срез которого ${{S}_{{\tau ,w,p}}}\left( {A_{\Phi }^{{(i)}}} \right)$.

Поэтому оптимальным решением (2.31) будет

где ${{\mathcal{B}}^{k}} = {{\mathcal{G}}^{{k + 1}}} + \frac{{{{\mathcal{C}}^{k}}}}{{{{\rho }^{k}}}}$, ${{\mathcal{S}}_{{\frac{\mu }{\rho },w,p}}}(\mathcal{B}_{\Phi }^{k})$, как показано в доказательстве теоремы 1 в Приложении. На основе вышеприведенного описания псевдокод сведен в алгоритм 2 решения задачи (2.12).

Алгоритм 2.

Вход: $\left\{ {{{X}_{i}}} \right\}_{{i = 1}}^{m}$, $\left\{ {{{P}_{i}}} \right\}_{{i = 1}}^{m}$, $w$, $\mathcal{M}$, $\lambda $, $\mu $, $\gamma $.

Выход: $A$, $\left\{ {{{W}_{i}}} \right\}_{{i = 1}}^{m}$.

Шаг 1. Инициализация: Номер шага $k = 0$, $\eta = 1.1$, ${{\rho }^{0}} = {{10}^{{ - 4}}}$, $\left\{ {\delta _{i}^{0} = \frac{1}{m}} \right\}_{{i = 1}}^{m}$, ${{\mathcal{C}}^{0}} = 0$, ${{\mathcal{G}}^{0}} = {{\mathcal{Y}}^{0}} = \mathcal{M}$.

Шаг 2. Расчитать ${{A}^{{k + 1}}}$, согласно (2.18).

Шаг 3. Расчитать $W_{i}^{{k + 1}}$ как ${{\left( {{{X}_{i}}{{P}_{i}}X_{i}^{ \top }} \right)}^{{ - 1}}}{{X}_{i}}{{P}_{i}}{{A}^{{k + 1}}}^{ \top }$ для всех i.

Шаг 4. Расчитать $\delta _{i}^{{k + 1}}$, согласно определению для всех i.

Шаг 5. Расчитать ${{\mathcal{G}}^{{k + 1}}}$ алгоритмом 1.

Шаг 6. Расчитать ${{\mathcal{Y}}^{{k + 1}}}$, согласно (2.34).

Шаг 7. Расчитать ${{\mathcal{C}}^{{k + 1}}} = {{\mathcal{C}}^{k}} + {{\rho }^{k}}\left( {{{\mathcal{G}}^{{k + 1}}} - {{\mathcal{Y}}^{{k + 1}}}} \right)$.

Шаг 8. Расчитать ${{\rho }^{{k + 1}}} = \eta {{\rho }^{k}}$.

Шаг 9. Если алгоритм сошелся, то выдать $A = {{A}^{{k + 1}}}$, ${{W}_{i}} = W_{i}^{{k + 1}}$ для всех i.

Шаг 10. $k \leftarrow k + 1$ и перейти к шагу 2.

2.2. Анализ сходимости. Проанализируем сходимость алгоритма 2. Сначала покажем ограниченность последовательностей в лемме 1, которая доказана в Приложении. Затем сходимость будет исследована в теореме 2, которая также доказана в Приложении.

Лемма 1. Последовательности $\left\{ {{{\mathcal{C}}^{k}}} \right\}$, $\left\{ {{{\mathcal{Y}}^{k}}} \right\}$, $\left\{ {{{A}^{k}}} \right\}$, $\left\{ {\left\{ {W_{i}^{k}} \right\}_{{i = 1}}^{m}} \right\}$, $\left\{ {{{\mathcal{G}}^{k}}} \right\}$ и расширенная функция Лагранжа (2.16), которые генерируются алгоритмом 2, ограничены.

Теорема 2. Последовательности $\left\{ {{{\mathcal{G}}^{k}}} \right\}$ и $\left\{ {{{\mathcal{Y}}^{k}}} \right\}$, порожденные алгоритмом 2, удовлетворяют следующим требованиям:

1) $\mathop {\lim }\limits_{k \to \infty } {{\left\| {{{\mathcal{G}}^{k}} - {{\mathcal{Y}}^{k}}} \right\|}_{F}} = 0,$

2) $\mathop {\lim }\limits_{k \to \infty } {{\left\| {{{\mathcal{G}}^{{k + 1}}} - {{\mathcal{G}}^{k}}} \right\|}_{F}} = 0,$

3) $\mathop {\lim }\limits_{k \to \infty } {{\left\| {{{\mathcal{Y}}^{{k + 1}}} - {{\mathcal{Y}}^{k}}} \right\|}_{F}} = 0.$

3. Вычислительные эксперименты. Наборы данных. Четыре набора данных, использованные в эксперименте, показаны в табл. 2 и описаны ниже.

1. Цифры [50]. Набор данных содержит $10$ классов объектов, т.е. изображения рукописных цифр 0–9. В каждом классе есть $200$ образцов. Известны шесть аспектов: средние значения пикселей, коэффициенты Фурье, корреляции профилей, момент Цернике, коэффициенты Карунена–Лоэва и морфологические. В данном эксперименте задействованы только первые пять.

2. 3_Sources [51]. Набор данных содержит 948 историй из трех онлайн-ресурсов – BBC, Reuters и Guardian. В данном эксперименте для сравнения с другими методами используется подмножество, содержащее 169 историй, о которых сообщалось на всех ресурсах. Эти 169 историй разделены на шесть классов: бизнес, развлечения, здоровье, политика, спорт и технологии.

3. BBC Sport [52]. Набор данных содержит 737 документов о новостях спорта, которые выражены 2–4 мнениями и разделены на пять категорий. Для наших экспериментов мы выбрали подмножество образцов, описанных по 4 раза, в нем 116 элементов.

4. Orl [53]. Очень популярный набор данных лиц, содержащий 400 изображений лиц, предоставленных 40 лицами, каждое из которых состоит из $10$ фотографий. Поскольку Orl – это набор данных с одним аспектом, мы извлекли LBP, GIST и пирамиду гистограммы ориентированных градиентов и объединили их с пиксельными характеристиками, чтобы сформировать набор данных с четырьмя аспектами.

Построение неполных многоаспектных данных. Для каждого из вышеперечисленных наборов данных случайным образом выбираем p% ($p \in \left\{ {90,70,50,30} \right\}$) образцов и превращаем их в неполные путем удаления данных из случайно выбранного аспекта.

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

1. BSV [54]. BSV выполняет кластеризацию k-средних и классификацию ближайших соседей на всех аспектах и сообщает оптимальные результаты кластеризации и классификации, где недостающие экземпляры дополняются средним экземпляром соответствующего аспекта.

2. Concat [54]. Объединение всех аспектов в один и применение k-средних и ближайших соседей для получения окончательных результатов кластеризации и классификации, где недостающие экземпляры также заполняются средним экземпляром, как BSV.

3. DAIMC [20]. Метод использует два способа для согласованного представления всех аспектов: матричное разложение на основе выравнивания информации об экземплярах и разреженную регрессию на основе базисных матриц.

4. IMSC_AGL [4]. Метод получает консенсусное низкоразмерное представление при помощи спектральной кластеризации и строит графы низкорангового представления.

5. TCIMC [10]. Метод получает полный граф путем тензорного восстановления для каждого вида и отличается от представленного здесь метода тензорной нормой.

Наш метод сначала получает низкоразмерное представление $A$ всех образцов, а затем применяет метод k-средних для $A$. Поскольку метод чувствителен к начальному значению, вычисления производятся несколько раз и результат усредняется. Найденные центры служат для построения графа каждого представления:

где $k = 10$, $\sigma = 1$. Недостающие позиции в ${{M}_{i}}$ заполняются нулями. Значения $p$, $w$ и $\Phi $ в тензорной норме ${{\left\| \cdot \right\|}_{{\Phi ,w,{{S}_{p}}}}}$ задаются 0.6, 1 и дискретным косинусным преобразованием соответственно.

Меры качества. Оценка качества производится тремя известными мерами: точностью (accuracy, ACC), нормализованной взаимной информацией (normalized mutual information, NMI), чистотой (purity).

3.1. Результаты. Таблица 3 показывает результаты кластеризации шести методов на четырех наборах данных. Из нее можно сделать следующие выводы.

1. Представленный метод имеет лучшие результаты в большинстве случаев по сравнению с другими пятью методами. В задаче кластеризации предложенный метод примерно на 5 и 10% лучше, чем другие, на данных Orl и Handwritten, соответственно. Неизбежны некоторые данные, для которых та или иная мера не является оптимальной, например задача кластеризации наборов данных Handwritten, 3Sources и BBC Sport.

2. Таблица 3 демонстрирует, что IMSC_AGL, TCIMC и наш метод имеют лучшее качество кластеризации, чем DAIMC на всех наборах данных. Это указывает на то, что графовые инструменты могут улучшить качество кластеризации. TCIMC и наш метод основаны на тензорном заполнении графа, в них отличается тензорная норма. Эксперименты показывают, что наш метод имеет лучшую производительность кластеризации, чем TCIMC, на большинстве наборов данных.

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

3.2. Анализ чувствительности к параметрам. В этом разделе анализируется чувствительность трех параметров $\lambda $, $\mu $ и $\gamma $ на наборах данных Handwritten, 3Sources, BBC Sport и Orl. Проверяются параметры $\lambda $ со значениями {1, 4, 5, 7, 9} и $\mu $ со значениями $\{ 10,\;30,\;50,\;70,\;90\} $. Предложенный метод кластеризации выполняется с различными комбинациями двух параметров ($\lambda \& \mu $). Также выполняется кластеризация с различными $\gamma $ из множества ${{\{ 10}^{p}}$, $p \in \overline { - 2,6} \} $. Рисунки 2 и 3 показывают качество кластеризации в зависимости от параметра масштаба $\lambda \& \mu $ и $\gamma $ на четырех наборах данных с уровнем пропусков $70\% $ соответственно. Согласно этим результатам, наш метод относительно стабилен для гиперпараметров $\lambda $, $\mu $ и $\gamma $, а производительность кластеризации обычно оптимальна для $\lambda = 3$, $\mu = 10$ и $\gamma = 100$.

3.3. Анализ сходимости. В разд. 2.3 показано, что алгоритм 2 сходится. Описаны численные эксперименты для проверки сходимости. Проведены эксперименты на наборах данных Handwritten, 3 Sources, BBC Sport и Orl с уровнем пропусков $70\% $. На рис. 4 показана сходимость алгоритма и качество кластеризации модели при увеличении числа итераций. Из рис. 4 видно, что предложенный метод оптимизации имеет хорошую сходимость, при которой ${{\left\| {{{\mathcal{G}}^{{k + 1}}} - {{\mathcal{G}}^{k}}} \right\|}_{F}}$, ${{\left\| {{{\mathcal{Y}}^{{k + 1}}} - {{\mathcal{Y}}^{k}}} \right\|}_{F}}$, и ${{\left\| {{{\mathcal{G}}^{k}} - {{\mathcal{Y}}^{k}}} \right\|}_{F}}$ может быстро уменьшаться и стремиться к нулю во всех четырех наборах данных. Результаты кластеризации также стабилизируются с увеличением числа итераций.

3.4. Влияние параметра $r$. Исследуем влияние параметра $r$ на результат эксперимента. Вводим $r$ от $n \times 10$ до $n \times 100\% $ для каждого эксперимента на наборах данных Handwritten, 3 Sources, BBC Sport и Orl с уровнем пропусков $70\% $, т.е. $r \in \left\{ {n \times 10\% ,n \times 20\% ,\; \ldots ,\;n \times 100\% } \right\}$. Производительность кластеризации нашего метода на наборах данных Handwritten и Orl уменьшается при увеличении $r{\text{/}}n$ (рис. 5). На наборах данных 3 Sources и BBC Sport производительность предложенной модели существенно не меняется при увеличении $r{\text{/}}n$. Рисунок 6 показывает, что время работы для решения $\mathcal{Y}$ становится больше с увеличением значения $r{\text{/}}n$ на четырех наборах данных. Отметим, что $r = n$ не является оптимальным выбором, в данном методе имеет смысл использовать $r < n$.

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