Известия РАН. Теория и системы управления, 2019, № 4, стр. 83-98

Введение. Данные в практических задачах могут состоять из различных представлений или аспектов. Например, одна и та же фотография может быть дана в высоком или низком разрешении, веб-страницы могут быть классифицированы на основе содержимого и текста гиперссылок и т.п. Можно предположить, что использование информации из нескольких представлений обеспечивает лучшую производительность кластеризации, чем из одного [1]. Многоаспектная кластеризация, МАК (multi-view clustering, MVC) [2] стала актуальной темой исследований в прошлом десятилетии, было предложено большое число алгоритмов. Неотрицательное матричное разложение (НМР) [3, 4] является распространенным приемом МАК. Алгоритм НМР был впервые предложен для обучения классификаторов частей объектов, таких, как человеческие лица и текстовые документы [5–7]. Суть НМР состоит в том, чтобы найти две неотрицательные матрицы, произведение которых обеспечивает хорошее приближение к исходной матрице.

В последнее время НМР стал популярным методом кластеризации данных с несколькими представлениями, и, согласно литературе, он обеспечивает качество, сравнимое с большинством современных самообучаемых алгоритмов [8]. Один из способов (назовем его здесь объединенным НМР, или ОНМР) заключается в конкатенации (объединении) признаков из всех представлений и последующем запуске НМР непосредственно для этого объединенного набора. Простая конкатенация данных из разных представлений может привести к потере специфики некоторых представлений, что влияет на качество работы алгоритма. В методе мульти-НМР (МНМР) [9, 10] предложено разложение объединенной матрицы с ограничением, которое подталкивает решение задачи кластеризации каждого представления к общему консенсусу. Алгоритмы, основанные на МНМР, широко используются в различных приложениях, таких, как медицинская диагностика [11, 12], аннотация изображений [13–15], распознавание объектов [16], динамическая кластеризация по многим представлениям (online multi-view clustering) [17, 18].

Однако эти алгоритмы учитывают только ограничения, накладываемые парами представлений. Если же некоторые объекты отображены не во всех представлениях, кластеризация не гарантируется. При сопоставлении только пар представлений теряется информация о структуре исходного многообразия, породившего эти представления. Для того, чтобы восстановить эту структуру, предложены такие алгоритмы извлечения многообразий (manifold learning) и нелинейного снижения размерности, как локально-линейное встраивание (local linear embedding, LLE) [19], локальное изометрическое отображение (ISOMAP) [20], вычисление собственных векторов лапласиана матрицы связности (laplacian eigenmaps) [21]. Множественные нелинейные ограничения могут также хорошо приближать данные [22]. Все эти алгоритмы используют так называемую инвариантную идею [23], состоящую в том, что соседние точки многообразия с большой вероятностью имеют похожие вложения. Было показано, что эффективность обучения может быть значительно улучшена, если использовать геометрическую структуру и учитывать локальную инвариантность во время процедуры НМР [24, 25].

Следует отметить, что большинство существующих алгоритмов кластеризации основаны на идеальном предположении, что для каждого объекта известен его образец в каждом представлении, иначе говоря, для каждого образца в одном представлении можно найти его пару в другом представлении [9, 26–28]. Более общий случай состоит в том, что в некоторых представлениях отсутствуют образцы некоторых объектов, что приводит к получению неполных многоаспектных данных (semi-paired multi-view data). Отбрасывание не полностью представленных объектов приводит к переобучению на оставшихся данных и плохому обобщению для отброшенных. Разработаны методы, такие, как кластеризация с несколькими неполными представлениями (multiple incomplete views clustering, MIC) [29], которые пополняют недостающие образцы в каждом представлении, но в этом случае все зависит от качества пополнения. В [30] предложен метод частичной многоаспектной кластеризации, ЧМК (partial multi-view clustering, PVC) для неполных данных с двумя представлениями. Он работает путем создания скрытого подпространства, в котором образцы, соответствующие одному и тому же объекту в разных представлениях, находятся близко друг к другу. Регуляризованная графом частичная многоаспектная кластеризация, ГЧМК (graph-regularized partial multi-view clustering, GPMVC) [31] расширяет ЧМК для нескольких сценариев и использует регуляризацию лапласиана при помощи графа, настраиваемого для конкретного представления, что повышает качество работы. ЧМК работает только с парами представлений, при этом нельзя ввести ограничения на скрытую информацию для отдельного представления. ГЧМК ограничивает структуру скрытого представления глобально путем введения условий, ограничивающих многообразие, но эти глобальные ограничения могут быть недостаточно хорошими для выявления локальной геометрической структуры в каждом отдельном представлении. Метод неполного мультимодального группирования визуальных данных, НМГ (incomplete multi-modal visual data grouping, IMG) [32] также сочетает ЧМК с ограничением многообразия, но поскольку он работает только с двумя представлениями, его применение во многих практических задачах затруднено. Дважды выровненная неполная кластеризация с несколькими представлениями, ДВНК (doubly aligned incomplete multi-view clustering, DAIMC) [33] решает проблему неполных представлений путем введения соответствующей задачи на веса и обеспечения соответствия базовых матриц отдельных представлений. Разнесенное неотрицательное матричное разложение, РНМР (diverse nonnegative matrix factorization, DiNMF) [34] уменьшает избыточность, вводя штраф за корреляцию векторов базиса, что обеспечивает процесс обучения за линейное время.

В статье предложен новый алгоритм полупарной многоаспектной кластеризации, ПМАК (semi-paired multi-view clustering, SMC) путем объединения НМР с регуляризацией многообразия в каждом представлении, которое явно учитывает парную информацию между различными представлениями и геометрическую информацию в каждом конкретном представлении. Кроме того, благодаря введению матрицы отсутствующих образцов алгоритм может работать как с полностью, так и с частично представленными данными.

Здесь стоит выделить несколько преимуществ предложенного подхода.

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

2. В то время как МНМР и ЧМК учитывают только парную информацию, предложенный алгоритм использует внутреннюю геометрию данных и включает ее в качестве дополнительного слагаемого регуляризации. Следовательно, аналогично регуляризованной графом неотрицательной матричной факторизации ГНМР, (graph regularized non-negative matrix factorization) [24], алгоритм в особенности хорош в пространствах вложения большой размерности. По сравнению с ГЧМК алгоритм имеет более строгие ограничения матрицы индикаторов и более сжатую формулировку.

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

Остальная часть статьи организована следующим образом: в разд. 1 дается краткий обзор известных работ по многоаспектной кластеризации на основе НМР. В разд. 2 представлен алгоритм и доказательство сходимости оптимизационного процесса. Экспериментальные результаты по кластеризации данных с несколькими представлениями приведены в разд. 3.

1. Обзор известных методов. Рассмотрим развитие методов кластеризации, основанных на НМР, и способы использования при этом данных нескольких представлений.

1.1. Неотрицательное матричное разложение. Пусть $X = [{{\vec {x}}_{1}},{{\vec {x}}_{2}},\; \cdots \;,{{\vec {x}}_{N}}] \in {{\mathbb{R}}^{{d \times N}}}$ – матрица, столбцы которой ${{\vec {x}}_{i}}$ являются векторами исходных данных. В терминах рассматриваемых далее методов кластеризации d – размерность пространства представления (пока единственного), N – число известных для него образцов. Это неотрицательная матрица, т.е. в ней содержатся лишь неотрицательные элементы: ${{x}_{{ij}}} \geqslant 0$, $X \geqslant 0$. НМР [3] стремится найти две неотрицательные матрицы U и V, такие, что

где $U = [{{u}_{{ik}}}] \in {{\mathbb{R}}^{{d \times K}}}$ – базисная матрица, а $V = [{{v}_{{jk}}}] \in {{\mathbb{R}}^{{N \times K}}}$ – индикаторная матрица, K – размерность скрытого пространства. Поиск НМР можно сформулировать как следующую оптимизационную задачу [4]:

Здесь и далее нижний индекс матричной нормы обозначает ее тип. В работе используются три типа норм (1-норма, 2-норма и F-норма (норма Фробениуса)), определяемые для матрицы $A \in {{\mathbb{R}}^{{m \times n}}}$ соответственно как

1.2. Регуляризованная графом неотрицательная матричная факторизация. В методе регуляризованной графом НМР (ГНМР) вводится весовая матрица W для отражения внутренней геометрической структуры данных в каждом представлении [24], матрица $W$ может быть определена следующим образом:

1) 0–1 взвешивание

2) взвешивание тепловым ядром

ГНМР сводится к следующей оптимизационной задаче [24]:

где ${\text{Tr}}( \cdot )$ – след матрицы, $\lambda $ – параметр регуляризации, $L = D - W$ – матрица лапласина, $D$ – диагональная матрица с элементами, равными построчным суммам W:

1.3. Мульти-НМР. Этот метод требует, чтобы матрицы коэффициентов, извлеченные из разных представлений, были регуляризованы для достижения общего консенсуса [9]. Обозначим через $\{ {{X}^{{(1)}}},{{X}^{{(2)}}}, \cdots ,{{X}^{{(m)}}}\} $ данные всех представлений, где для каждого представления ${{X}^{{(v)}}} \approx {{U}^{{(v)}}}{{({{V}^{{(v)}}})}^{T}}$. Для МНМР получается следующая задача оптимизации:

1.4. Частичная многоаспектная кластеризация. Метод ЧМК может работать с кластеризацией двух представлений, где в каждом представлении могут отсутствовать образцы [30]. Для объектов, имеющих образцы в обоих представлениях, ЧМК требует, чтобы представления этих образцов в низкоразмерном пространстве совпадали. Формально ЧМК приводит к следующей задаче минимизации:

где матрица ${{X}^{{(1)}}} \in {{\mathbb{R}}^{{(c + \mathop {\bar {n}}\nolimits_1 ) \times {{d}_{1}}}}}$ составлена из двух: первые $c$ строк обозначаются $X_{c}^{{(1)}}$ и соответствуют образцам, имеющим пары во втором представлении, остаток обозначен ${{\bar {X}}^{{(1)}}}$ и содержит образцы, заданные только первым представлением. Аналогично записывается матрица ${{X}^{{(2)}}} \in {{\mathbb{R}}^{{(c + {{{\bar {n}}}_{2}}) \times {{d}_{2}}}}}$. Через ${{U}^{{(1)}}} \in {{\mathbb{R}}^{{K \times {{d}_{1}}}}}$, ${{U}^{{(2)}}} \in {{\mathbb{R}}^{{K \times {{d}_{2}}}}}$ обозначены базисные матрицы двух представлений; ${{V}^{{(1)}}} \in {{\mathbb{R}}^{{(c + {{{\bar {n}}}_{1}}) \times K}}}$, ${{V}^{{(2)}}} \in {{\mathbb{R}}^{{(c + {{{\bar {n}}}_{2}}) \times K}}}$ – матрицы индикаторов каждого представления в скрытом пространстве, ${{V}_{c}} \in {{\mathbb{R}}^{{c \times K}}}$ – индикаторная (под)матрица парных данных, K – размерность скрытого пространства, $\lambda $ – параметр регуляризации, ${{d}_{1}}$ и ${{d}_{2}}$ – размерности первого и второго представлений соответственно. ЧМК обеспечивает, чтобы парные образцы имели одинаковый индикатор в скрытом пространстве, т.е. первые $c$ строк матриц ${{V}^{{(1)}}}$ и ${{V}^{{(2)}}}$ совпадают, оставшиеся ${{\bar {n}}_{1}}$ и ${{\bar {n}}_{2}}$ строк могут различаться.

2. Полупарная многоаспектная кластеризация. Пусть набор данных содержит $N$ объектов, каждый из которых может быть представлен несколькими образцами в не более чем $m$ представлениях. Обозначим через $\{ {{X}^{{(1)}}},{{X}^{{(2)}}}, \cdots ,{{X}^{{(m)}}}\} $ данные всех представлений, где ${{X}^{{(v)}}}$ = = $[\vec {x}_{1}^{{(v)}},\vec {x}_{2}^{{(v)}}, \cdots ,\vec {x}_{{{{n}^{{(v)}}}}}^{{(v)}}] \in {{\mathbb{R}}^{{{{d}^{{(v)}}} \times {{n}^{{(v)}}}}}}$, $v = 1,2,\; \cdots ,\;m$, и ${{n}^{{(v)}}}$ – число образцов в представлении с номером $v$. Соответственно ${{n}^{{(v)}}} \leqslant N$, поскольку некоторых образцов в представлениях недостает. Цель алгоритма ПМАК, как и обычного алгоритма кластеризации, состоит в том, чтобы объединить объекты в группы (кластеры).

Во-первых, для полностью спаренного набора данных с несколькими представлениями важно установить взаимосвязь каждого представления. Следуя идее МНМР, можно ограничить вектор индикатора парных экземпляров, используя парную информацию. В частности, естественно предположить, что образцы одного и того же объекта в разных представлениях близки. Как упоминалось ранее, МНМР ищет матрицу индикатора для каждого представления и общую матрицу консенсуса. Необходимо вычислить m + 1 матриц, которые близки друг к другу в F-норме. Согласно МНМР, $m$ матриц индикаторов объединяются в одну, таким образом парные образцы имеют один и тот же вектор индикатора после неотрицательного разложения матрицы. Таким образом, можно получить общую матрицу индикаторов неотрицательного консенсуса $V* \in {{\mathbb{R}}^{{N \times K}}}$ для каждого представления, где K – число базисных векторов. Эту идею можно сформулировать как минимизацию целевой функции:

по ${{U}^{{(v)}}}$ и $V{\text{*}}$. Далее, для учета неполноты данных вводится матрица пар ${{C}^{{(v)}}} \in {{\mathbb{R}}^{{{{n}^{{(v)}}} \times N}}}$:

Объединяя матрицы пар с (2.1), можно получить следующую целевую функцию:

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

где ${{W}^{{(v)}}}$ – весовая матрица, та же, которая используется в ГНМР для измерения близости точек, например (1.3), (1.4). Воспользовавшись (2.3) и (2.4), получим задачу минимизации: где $\lambda > 0$ – параметр регуляризации, балансирующий невязки ${{E}_{1}}$ и ${{E}_{2}}$. В задаче (2.5) можно видеть, что первое слагаемое обеспечивает максимально возможное приближение для парных данных, а второе пытается максимально сохранить отношение соседей. Что еще более важно, формулировка (2.5) подходит для обработки как полных, так и неполных данных.

2.1. Решение. Подобно оригинальному НМР с одним представлением, используется итеративная процедура решения задачи (2.5).

2.2. Фиксируем $V{\text{*}}$, обновляем ${{U}^{{(v)}}}$. Если $V{\text{*}}$ фиксировано для каждого представления, вычисление ${{U}^{{(v)}}}$ не зависит от ${{U}^{{(v')}}}$, $v' \ne v$. Для данных каждого представления можно найти ${{U}^{{(v)}}}$ независимо и целевая функция сводится к $E = mi{{n}_{{{{U}^{{(v)}}}}}}{\text{||}}{{X}^{{(v)}}} - {{U}^{{(v)}}}{{V}^{{ * {\text{T}}}}}{{C}^{{(v){\text{T}}}}}{\text{||}}_{F}^{2}$, что совпадает с оригинальной постановкой НМР. Таким образом, запишем правило обновления:

Нетрудно убедиться, что $u_{{ik}}^{{(v)}}$ остается неотрицательным после каждого шага.

2.3. Фиксируем ${{U}^{{(v)}}}$, обновляем $V{\text{*}}$. Пусть теперь ${{U}^{{(v)}}}$ зафиксировано. Обозначим через $\Psi $ матрицу лагранжевых множителей для ограничения $V* \geqslant 0$. Функция Лагранжа записывается как

Дифференцируем целевую функцию $L$ по $V{\text{*}}$:

Используя условия Каруша–Куна–Такера ${{\psi }_{{jk}}}v_{{jk}}^{ * } = 0$, получим

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

В матричной форме (2.6) и (2.7) представляются как следующие мультипликативные правила:

где знаки $ \odot $ и $ \div $ соответствуют операциям поэлементного умножения и деления. Псевдокод ПМАК представлен в алгоритме.

Алгоритм.

Дано: Набор данных $\{ {{X}^{{(1)}}},{{X}^{{(2)}}},\; \cdots ,\;{{X}^{{(m)}}}\} $; матрицы пар $\{ {{C}^{{(1)}}},{{C}^{{(2)}}},\; \cdots ,\;{{C}^{{(m)}}}\} $; параметр $\lambda $.

Найти: Базисные матрицы $\{ {{U}^{{(1)}}},{{U}^{{(2)}}},\; \cdots ,\;{{U}^{{(m)}}}\} $; индикаторную матрицу V*.

Шаг 1. Инициализация ${{U}^{{(v)}}},{{V}^{{(v)}}}$ для всех представлений $v = \overline {1,m} $.

Шаг 2. Фиксируем V*. Для всех $v = \overline {1,m} $ обновляем ${{U}^{{(v)}}}$, согласно (2.8).

Шаг 3. Фиксируем все ${{U}^{{(v)}}}$. Обновляем V*, согласно (2.9).

Шаг 4. Если минимум (2.5) достигнут, то конец, иначе переходим к шагу 2.

Использование следующих традиционных методов градиентного спуска также решает эту задачу:

где $\eta _{{ik}}^{{(v)}}$ и ${{\delta }_{{jk}}}$ – параметры величин шагов. Если задать то получаются также правила обновления (2.8) и (2.9). По сравнению с методом градиентного спуска предложенные итерационные процедуры обеспечивают неотрицательность ${{U}^{{(v)}}}$ и V*. Может быть доказано, что правила обновления сходятся к локальному оптимуму целевой функции.

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

Теорема. Целевая функция задачи (2.5) не увеличивается в соответствии с правилами обновления (2.8) и (2.9).

Очевидно, что целевая функция задачи (2.5) неотрицательна. Подобно процессу доказательства в [4], можно дать следующее определение и лемму.

Определение. Назовем $G(h,h')$ вспомогательной функцией для F(h), если для всех $h$, $h'$ из области определения F(h) удовлетворяются условия $G(h,h') \geqslant F(h)$, $G(h,h) = F(h)$ [4].

Лемма. Если G является вспомогательной функцией для F, то F не увеличивается при следующем обновлении [4]:

Если V* фиксировано, можно определить

как вспомогательную функцию для $F_{{ik}}^{{(v)}}(u_{{ik}}^{{(v)}})$. Аналогично можно определить как вспомогательную функцию для ${{F}_{{jk}}}(v_{{jk}}^{ * })(v_{{jk}}^{ * })$. Подставляя данные выше вспомогательные функции в (18), получим правила (15) и (16).

2.5. Анализ сложности. В алгоритме ПМАК сложность обновления ${{U}^{{(v)}}}$ в (2.8) равна $O({{d}^{{(v)}}}{{n}^{{(v)}}}K)$, что совпадает с оригинальным НМР. Сложность обновления V* в (2.9) равна

Если предположить, что целевая функция в (2.5) сходится после t шагов обновления, то общая сложность алгоритма ПМАК будет $O\left( {t{{O}_{1}}} \right)$. Кроме того, алгоритм ПМАК требует дополнительно

операций для построения матрицы ближайших соседей ${{W}^{v}}$. В общем случае для каждого представления $K \ll {{n}^{{(v)}}}$ и $K \ll {{d}^{{(v)}}}$. Обозначив наибольшую размерность представлений ${{d}_{{max}}}$, получим, что сложность ПМАК составляет не более $O(tmd_{{max}}^{3})$.

3. Численные эксперименты. Проведена серия экспериментов над следующими четырьмя наборами данных с несколькими представлениями, статистика которых приведена в табл. 1.

Набор данных Йельского университета (Yale dataset) содержит 11 различных изображений каждого из 15 различных объектов. Здесь использованы изображения, обрезанные до размера 64 × 64 пикселя в качестве представления высокого разрешения, обрезанные до 50 × 50 пикселей как представления со средним разрешением и 32 × 32 пикселя в качестве представления с низким разрешением.

Набор данных ORL (ORL dataset) содержит 10 различных изображений каждого из 40 различных лиц. Изображения сделаны в разное время, с различным освещением и мимикой. Здесь изображения обрезаны до 64 × 64 пикселя для представления с высоким разрешением и до 56 × 46 пикселя как представление с низким разрешением.

MFD dataset. Этот набор данных состоит из различных признаков (в терминологии статьи – представлений), вычисленных для отсканированных изображений рукописных цифр (‘0’ ~ ‘9’). Набор данных содержит 2000 экземпляров, каждый экземпляр дан в шести представлениях. Здесь использованы следующие три представления: коэффициенты Фурье формы символов, корреляции профилей и средние значения пикселей в окнах 2 × 3.

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

3.1. Сравнение с аналогами. Чтобы оценить предлагаемый алгоритм ПМАК, для нескольких наборов данных было проведено его сравнение со следующими аналогами.

1. ОНМР. Этот метод работает путем объединения признаков для всех представлений и последующего запуска НМР на таком объединенном представлении.

2. МНМР [9]. Метод формулирует совместный процесс факторизации матрицы с ограничением, которое подталкивает решение кластеризации каждого представления к общему консенсусу.

3. ЧМК [30]. Метод работает путем создания скрытого подпространства, в котором парные образцы имеют общее представление, а непарные – индивидуальное.

4. НМГ [32].

Следует отметить, что ОНМР и МНМР не могут обрабатывать случаи неполных данных, отсутствующие экземпляры в каждом представлении заполняются средними значениями признаков. Такой подход используется в [33]. Для ЧМК и НМГ, которые работают только с данными двух представлений, модели обучались всем возможным комбинациям двух представлений, приведены наилучшие достигнутые результаты. Чтобы построить сценарий с неполными данными, удаляются некоторые случайно выбранные образцы в каждом представлении, так, что доля полученных непарных образцов варьируется от 0 до 50%. Для кластеризации применен алгоритм k-средних на базовой матрице и, так же как в [9], для измерения качества кластеризации использованы точность (AC) и нормализованная взаимная информация (NMI).

3.2. Результаты кластеризации. Каждый метод запускался 20 раз, чтобы уменьшить случайность. На рис. 1 показана усредненная величина NMI для четырех наборов данных, на рис. 2 – усредненная величина AC. По горизонтальной оси всех графиков отложена доля непарных данных. Можно видеть, что ПМАК почти всегда превосходит другие методы по показателям NMI и AC. На наборах данных Yale и ORL алгоритм ПМАК превосходит все остальные базовые алгоритмы с большим отрывом. И даже когда непарный уровень относительно велик, ПМАК все равно может получить стабильную производительность. Это связано с тем, что метод ПМАК объединяет не только информацию о парных экземплярах, но также и скрытую структуру многообразия в каждом представлении. Отметим, что МНМР и ОНМР на некоторых данных работают неудовлетворительно. Это свидетельствует о том, что использование лишь парных экземпляров не может приводить к хорошей кластеризации.

На рис. 1, в, 2, в представлены результаты расчетов по набору данных Википедии. Можно видеть, что все качество работы всех методов падает при увеличении доли непарных образцов. Это связано с тем, что в наборе данных Википедии есть два представления: изображения и текста. Размерность представления изображения составляет 128, а представления текста – 10, благодаря чему представление текста имеет относительно низкое измерение, которое даже меньше, чем число базисных векторов, использованное в экспериментах. Таким образом, некоторые алгоритмы кластеризации с несколькими представлениями не могут построить матрицы индикаторов, в то время как некоторые методы кластеризации с одним представлением, которые рассматривают парные данные как данные с одним представлением, могут достигать лучшей производительности. В наборе данных Википедии методы ПМАК, ЧМК и НМГ имеют близкое качество кластеризации. Однако ЧМК и НМГ могут работать только с наборами данных с двумя представлениями, что в значительной степени ограничивает область их применения.

На рис. 1, г, 2, г показаны результаты экспериментов на базе данных MFD. В отличие от наборов данных Yale и ORL, все представления которых являются растровыми изображениями (т.е. признаки во всех представлениях – это пиксели), в MFD представления более разнообразны. Видно, что ПМАК получает небольшое превосходство по сравнению с ЧМК и НМГ, когда нет пропущенных образцов, при появлении пропусков и увеличении их доли в данных преимущество продолжает расти, что выявляет большую устойчивость предложенного метода по сравнению с аналогами. Предложенный метод опережает ОНМР и МНМР на базе MFD для данных с пропусками, поскольку качество пополнения не гарантировано, а также эти методы игнорируют скрытую структуру в каждом представлении.

3.3. Исследование параметров. Проведены эксперименты с различными значениями $K$, чтобы показать влияние размерности скрытого пространства. В табл. 2–5 дано качество кластеризации по наборам данных Yale, ORL, Википедия и MFD соответственно. Каждый метод исполнялся 20 раз чтобы уменьшить случайность, в таблицах показаны среднее и стандартное отклонения (в единицах $( \times {{10}^{{ - 4}}})$) каждого метода. Эти результаты демонстрируют, что ПМАК превосходит другие алгоритмы, основанные на НМР, когда скрытый коэффициент $K$ постоянно изменяется, что важно, потому что меньший K также означает меньшую сложность вычислений.

Целевая функция в (2.5) имеет два гиперпараметра: параметр регуляризации $\lambda $ и число соседей в слагаемом, ограничивающем многообразие. Параметр $lambda$ меняется в диапазоне ${{10}^{{ - 3}}} \sim {{10}^{3}}$, а число соседей – в диапазоне 2 ~ 20. Рисунок 3 показывает, что при доле парных 60% в наборе данных ORL предложенный алгоритм ПМАК получает относительно лучшую производительность при $\lambda = \{ 1{{e}^{{ - 1}}},1{{e}^{0}}\} $ и количестве соседей, равном 10. Число базисных векторов V* установлено равным 35.

3.4. Исследование числа представлений. Чтобы продемонстрировать, что метод ПМАК может использовать дополнительную информацию на множественных представлениях, проведены эксперименты с различным количеством представлений на наборах данных MFD и Yale. Рисунок 4 показывает качество кластеризации в зависимости от числа представлений. Процент пропуска в каждом представлении составляет 0.1, а результаты для одного представления получены методом ГНМР. Очевидно, что с увеличением количества представлений можно повысить качество кластеризации, что свидетельствует о том, что большее количество представлений может помочь нам найти больше дополнительной информации.

3.5. Исследование сходимости. Теорема из разд. 2 гарантирует сходимость алгоритма ПМАК. Поэтому в этом разделе исследуется только скорость сходимости. На рис. 5 показаны результаты для ORL с 60% парных экземпляров, Википедии – с 80% парных экземпляров и MFD – с 80% парных экземпляров. Горизонтальная ось графиков соответствует числу итераций. Видно, что ПМАК сходится примерно за 50 итераций.

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