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

Д.И. ИГНАТОВ, канд. техн. наук (dignatov@hse.ru)

(Национальный исследовательский университет

”Высшая школа экономики”, Москва)

ТРИКЛАСТЕРЫ БЛИЗКИХ ЗНАЧЕНИЙ

ДЛЯ АНАЛИЗА ТРЕХМЕРНЫХ ДАННЫХ¹

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

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

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

плотных подтензоров в трехмерных тензорах над полем действительных

чисел. Предлагаются два метода решения этой задачи: NOAC — вариант

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

операторов и триадическая версия метода k-средних с уточненной метри-

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

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

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

метода NOAC в смысле критериев качества найденных трикластеров.

Ключевые слова: трикластеризация, анализ формальных понятий, трех-

мерные тензоры, многозначные контексты.

DOI: 10.31857/S0005231022060071, EDN: ACVQYG

1. Введение

В современном мире характерно наличие насыщенной информационной

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

тет с каждым годом. Часто главной проблемой, препятствующей успешному

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

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

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

ной прикладной математике и информатике [1]. Кластерный анализ предо-

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

структуры данных и классификации объектов. Основная идея заключается

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

ваемые кластерами.

Существуют методы, решающие задачи кластеризации объектов или при-

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

¹ Статья подготовлена в результате проведения исследования в рамках Программы

фундаментальных исследований Национального исследовательского университета “Выс-

шая школа экономики” (НИУ ВШЭ).

объектно-признаковое описание сходства (бикластеризация) [2]. Тем не менее

триклаcтеризация и n-мерная кластеризация как дальнейшее ее расширение

не были столь же тщательно изучены (см., например, обзор [3]). В данной

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

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

основываясь на методах ОАС-трикластеризации (OAC от Object, Attribute,

Condition) [4], сравнение эффективности работы этих алгоритмов, а также

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

В ходе разработки новых алгоритмов были рассмотрены существующие

методы, решающие близкие задачи, а именно: ОАС-трикластеризация, осно-

ванная на штрих-операторах [4], метод шкалирования формальных понятий

(Conceptual Scaling) [5] и его реализация TriMax [5], а также метод меж-

порядкового шкалирования (Interordinal Scaling) [5]. По различным причи-

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

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

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

метод NOAC (Numerical OAC), являющийся расширением на многозначный

случай ОАС-трикластеризации, основанной на штрих-операторах, и класси-

ческий алгоритм кластеризации k-средних (k-means), использующий автор-

скую метрику для вычисления расстояний (Tri-k-means).

Данная работа состоит из четырех частей. Первая часть содержит некото-

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

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

дований. В ней также содержатся все общие формулировки, необходимые для

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

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

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

ложены два алгоритма, решающие поставленную выше задачу. В четвертой

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

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

2. Базовые определения

2.1. Диадический случай

Для полноценного погружения в предметную область следует начать с

формулировки базовых определений анализа формальных понятий (Formal

Concept Analysis — FCA) [6].

Пусть даны два множества: G и M. Элементы множества G называют объ-

ектами (от нем. Gegenständ - объект), а элементы множества M - признаками

(от нем. Merkmal - признак). Пусть также дано бинарное отношение I, являю-

щееся подмножеством декартового произведения этих множеств: I ⊆ G × M.

Формальным контекстом называется тройка K = (G, M, I). Если пара (g, m),

где g ∈ G и m ∈ M, принадлежит отношению инцидентности I, говорят, что

“объект g обладает признаком m”. Это обозначается как (g, m) ∈ I или gIm.

Обычно формальные контексты представляются в виде матриц или таблиц с

булевыми значениями.

Теперь рассмотрим два отображения φ : 2^G → 2^M и ψ : 2^M → 2^G. Пусть

φ(A) = {m | ∀g ∈ A : gIm}, ψ(B) = {g | ∀m ∈ B : gIm}. Для них выполняют-

ся следующие условия: (для A₁, A₂ ⊆ G; B₁, B₂ ⊆ M)

A₁ ⊆ A₂ ⇒ φ(A₂) ⊆ φ(A₁),

B₁ ⊆ B₂ ⇒ ψ(B₂) ⊆ ψ(B₁).

Эти отображения задают операторы Галуа для множеств объектов и при-

знаков. Так как по составу множества можно однозначно определить, ка-

кой из операторов применяется, обычно используется единое обозначение (·)^′.

Верны следующие свойства (для A, A₁, A₂ ⊆ G, B ⊆ M):

1) A₁ ⊆ A₂ ⇒ A′2 ⊆ A′1,

2) A₁ ⊆ A₂ ⇒ A′′1 ⊆ A′′2,

3) A ⊆ A^′′,

4) A^′ = A^′′′ (также A^′′ = A^′′′′),

5) (A₁ ∪ A₂)^′ ⇔ A′1 ∩ A′2,

6) A ⊆ B^′ ⇔ B ⊆ A^′ ⇔ A × B ∈ I.

Повторное применение этого же оператора дает оператор (·)^′′ : 2^G → 2^G,

удовлетворяющий следующим свойствам (для X, Y ⊆ G):

1) X ⊆ Y ⇒ X^′′ ⊆ Y^′′ (монотонность),

2) X ⊆ X^′′ (экстенсивность),

3) (X^′′)^′′ = X^′′ (идемпотентность).

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

жества объектов G на множество признаков M и наоборот, соответственно.

Таким образом, оператор (·)^′′ является оператором замыкания.

Пара (A, B) называется формальным понятием в формальном контексте

(G, M, I), если A ⊆ G, B ⊆ M, A^′ = B, B^′ = A. Множество A называют объ-

емом (extent) формального понятия, а множество B - содержанием (intent)

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

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

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

ной с помощью перестановки строк и столбцов.

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

но отношением частичного порядка

(A₁, B₁) ≥ (A₂, B₂) ⇔ A₂ ⊆ A₁(⇔ B₁ ⊆ B₂)

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

2.2. Многозначные диадические контексты

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

(G, M, W, I), где W является множеством значений контекста, т.е. множе-

ством значений, которые признаки m ∈ M могут принимать на объектах

g ∈ G, a I ⊆ G × M × W. При этом если (g,m,v) ∈ I и (g,m,w) ∈ I, то v = w.

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

ресечении строки, соответствующей объекту g, и столбца, соответствующего

признаку m, записано значение m(g) ∈ W . В самом общем случае бикласте-

ром для таких данных является пара (A, B), где A ⊆ G, B ⊆ M [2, 7].

2.3. Триадический случай и n-адический случай

Расширим приведенные выше определения на случай большей размерно-

сти. В этом разделе рассмотрим определения для общего случая большой

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

ния, необходимые для трикластеризации [8-11].

Во-первых, стоит обобщить понятие формального контекста. Пусть X₁,

X₂,... ,X_n — некоторые множества, а I — n-арное отношение, являющее-

ся подмножеством их декартова произведения: I ⊆ X₁ × X₂ × . . . × X_n. В та-

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

K = (X₁,X₂,...,X_n,I). В триадическом контексте K = (G,M,B,I), по ана-

логии с диадическим случаем, множества G и M называются соответствен-

но множествами объектов и признаков, а множество B называется множе-

ством условий (от нем. Bedingungen — условия). Тогда тройка (g, m, b) ∈ I,

где g ∈ G, m ∈ M, b ∈ B может интерпретироваться как “объект g обладает

признаком m при условии b”.

Расширение оператора Галуа (·)^′ приобретает следующие разновидности:

2X¹ → 2X2 × . . . × 2Xn , . . . , 2Xn → 2X1 × . . . × 2Xn-1 , . . . , 2X1 × . . . × 2Xn-1 →

→ 2Xn,...,2X2 × ... × 2Xn → 2X1. Таким образом, в триадическом случае

оператор производит переход из любого из трех множеств в декартово

произведение оставшихся двух либо обратно.

Кортеж (A₁, A₂, . . . , A_n) называется n-адическим формальным понятием,

если выполняется условие: (A₁ × . . . × An-1)^′ = A_n, . . . , (A₂ × . . . × A_n)^′ = A₁.

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

как и в диадическом случае, объемом и содержанием соответственно. Тре-

тье множество называется модусом (от лат. Modus — мера, образ, способ).

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

максимальным кубоидом.

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

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

2.4. Многозначные триадические контексты

Дополним определение триадического контекста для многозначного слу-

чая. Пусть G, M, B — множества соответственно объектов, признаков и

условий. Пусть W

— множество допустимых значений контекста. Тогда

4-арное отношение есть I ⊆ G × M × B × W . Если кортеж (g, m, b, w) ∈ I,

говорят, что “признак m принимает значение w на объекте g при усло-

вии b”. K = (G, M, B, W, I) называется многозначным формальным контек-

стом. Стоит заметить, что отношение I определено таким образом, что лю-

бому триплету (g ∈ G, m ∈ M, b ∈ B) соответствует не более одного значе-

ния w ∈ W . Это можно представить в виде (частичной) функции означи-

вания V : Q → W , где Q ⊆ G × M × B. Тогда область определения Q этой

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

ного контекста.

В общем случае трикластером называют тройку (X, Y, Z), где X ⊆ G,

Y ⊆ M, Z ⊆ B [3, 4] .

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

случай, когда W является множеством вещественных чисел R.

2.5. Критерии качества трикластеров

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

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

Пусть T = (X, Y, Z) — трикластер многозначного формального контекста

K = (G,M,B,W,I) с функцией означивания V : Q → W. Определим плот-

ность трикластера T как отношение количества входящих в него троек к его

размеру:

|Q ∩ (X × Y × Z)|

ρ(T ) =

|X||Y ||Z|

Можно заметить, что такая оценка не учитывает значения входящих в три-

кластер троек. Поэтому будем оценивать трикластеры еще и по дисперсии

значений содержащихся в нем триплетов. Пусть S = V (g, m, b) | (g, m, b) ∈

∈ Q ∩ (X × Y × Z) — выборка, состоящая из этих значений. Тогда несмещен-

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

⎛

⎞₂

|S|

∑

S2i - ⎝

S_i⎠ /|S|

i=1

s² =i=1

|S| - 1

Значения трикластера будем считать близкими при некотором параметре δ,

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

т.е. s ≤ δ.

3. Обзор существующих методов многомерной кластеризации

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

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

туры. Это может быть полезно в контекстах без шума, пропущенных значе-

ний и ошибок, однако реальные данные редко соответствуют этим требовани-

ям. Следовательно, при анализе в терминах формальных понятий с большой

вероятностью будет происходить потеря некоторой части значимой инфор-

мации, что приведет к получению нерелевантных результатов. Возможным

решением этой проблемы является ослабление определения формального по-

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

гут входить нули, “пропущенные тройки”). В общем случае такие сущности

называются n-кластерами. В диадическом и триадическом случаях это соот-

ветственно би- и трикластеры.

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

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

чи и порождающего метода [2, 3]. По этой причине в дальнейшем будем срав-

нивать эффективность различных порождающих методов с помощью таких

общих параметров, как плотность, дисперсия и количество трикластеров [8].

3.1. OAC-трикластеризация

Задача ОАС-трикластеризации довольно подробно описана в [4]: рассмат-

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

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

казателям плотности и разнообразия. По этой причине обратим внимание на

последний, который, по сути, является расширением метода OA-бикластери-

зации, описанной в [7] на триадический случай. Для фиксированной тройки

(g, m, b) ∈ I выпишем для удобства штрих-операторы, используемые в мето-

де, явно:

(g, m)^′ = {b | (g, m, b) ∈ I},

(g, b)^′ = {m | (g, b, m) ∈ I},

(m, b)^′ = {g | (g, b, m) ∈ I}.

Тогда ОАС-трикластером, основанным на штрих-операторах, постро-

енным для тройки (g, m, b) ∈ I, будет называться тройка множеств T =

= ((m, b)^′, (g, b)^′, (g, m)^′).

Отличительной особенностью построенных таким образом трикластеров

является наличие в них плотной подструктуры, (m, b)^′ × {m} × {b}, {g} ×

× (g, b)^′ × {b}, {g} × {m} × (g, m)^′, трехмерного креста из “единиц” [4].

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

разом: для каждой тройки (g, m, b) ∈ I пополняются двумерные массивы, со-

держащие результаты выполнения операций штрих, например, P rime[g, m] =

= Prime[g,m] ∪ b, сам трикластер содержит три указателя на соответствую-

щие массивы T = (^∗P rime[m, b],^∗ P rime[g, b],^∗ P rime[g, m]).

Сложность алгоритма по времени (в худшем случае) составляет O(|I|).

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

трикластера, требующая, в худшем случае, сравнения нового трикластера

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

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

сравнения.

3.2. Шкалирование формальных понятий и метод TriMax

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

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

ных контекстах с помощью средств анализа формальных понятий (АФП).

Пусть K = (G, M, W, I) — многозначный диадический формальный кон-

текст. Определим бикластер близких значений с параметром θ как бикластер,

где ∀g_i, g_l ∈ G, ∀m_i, m_k ∈ M

|m_i(g_j ) - m_k(g_l)| ≤ θ, т.е. все значения принад-

лежат одному классу толерантности (m_i(g_j ) ≃_θ m_k(g_l)).

Далее в [4] предлагается выделить из множества W классы толерантно-

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

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

понятий, также являющихся бикластерами близких значений. Эта идея об-

рела воплощение в виде алгоритма TriMax [5] .

В приложении к проблеме, решаемой в данной работе, главным недостат-

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

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

3.3. Межпорядковое шкалирование

Метод, рассмотренный в подразделе 3.2, зависит от параметра θ и ищет

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

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

кового шкалирования (Interordinal Scaling), предложенным в [5] и позволяю-

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

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

за формальных понятий (Triadic Concept Analysis — TCA). Этот подход за-

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

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

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

на объекте.

Пусть (G, M, W, I) — многозначный диадический формальный контекст.

Построим новое интервальное измерение (scale dimension) T из W с помо-

щью процедуры межпорядкового шкалирования (Interordinal Scaling). Шкала

представляет собой бинарное отношение J ⊆ W × T , сопоставляющее каж-

дому исходному значению из W соответствующие элементы из T . Пусть

T = {[min(W),w],∀w ∈ W} ∪ {[w,max(W)],∀w ∈ W}. Тогда (w,t) ∈ J тогда и

только тогда, когда w ∈ t, где t ⊆ T .

Пусть Y ⊆ G × M × T — тернарное отношение. В таком случае (g, m, t) ∈

∈ Y тогда и только тогда, когда m(g) ∈ t. Кортеж (G,M,T,Y ) называется

шкалированным триадическим контекстом многозначного диадического кон-

текста (G, M, W, I).

В [5] доказывается, что кортеж (A, B, U), где A ⊆ G, B ⊆ M, U ⊆ T , яв-

ляется триадическим формальным понятием, только если (A, B) является

бикластером близких значений для некоторого θ ≥ 0.

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

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

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

ветствующие инструменты для тернарного случая исследованы лишь в общем

виде.

4. Предложенные методы

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

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

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

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

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

контекстах. Первый является расширением ОАС-трикластеризации на мно-

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

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

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

4.1. Метод NOAC

Метод NOAC (Numerical OAC) получен модификацией ОАС-трикластери-

зации, основанной на штрих-операторах. Он принимает параметр δ, который

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

триадический контекст K = (G, M, B, W, I) и (частичная) функция означива-

ния V : G × M × B → W , переводящая триплет (g, m, b) в соответствующее

значение w тогда и только тогда, когда (g, m, b, w) ∈ I. Область определе-

ния этой функции обозначим как Q ⊆ G × M × B. Как и в бинарном случае,

будем строить трикластер от фиксированной тройки (g, m,b) ∈ Q. Переопре-

делим операторы, используемые методом:

{

}

(g, m)^δ = b |

(g, m, b) ∈ Q ∧ |V (g, m, b) - V (g, m,b)| < δ ,

{

}

(g,b)^δ = m |

(g, m,b) ∈ Q ∧ |V (g, m,b) - V (g, m,b)| < δ ,

{

}

( m,b)^δ = g

| (g, m,b) ∈ Q ∧ |V (g, m,b) - V (g, m,b)| < δ

Назовем эти операторы δ-операторами. Тогда ОАС-трикластером, осно-

ванным на δ-операторах, построенном на тройке (g, m,b) ∈ Q, будет назы-₍₎

ваться тройка множеств T =

( m,b)^δ,(g,b)^δ,(g, m )^δ

Можно заметить, что построенный таким образом трикластер содержит

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

немногозначным случаем. В силу того что результат применения δ-опера-

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

предподсчет. Для каждой тройки (g, m, b) ∈ Q совершим два шага:

1) Вычислим множества (g, m)^δ , (g, b)^δ и (m, b)^δ.

2) Если трикластер T = ((m, b)^δ, (g, b)^δ , (g, m)^δ ) еще не содержится в мно-

жестве трикластеров, добавим его туда.

Перебор всех троек в худшем случае займет O(|I|). Построение трикласте-

ра производится за O(|G| + |M| + |B|). Следовательно, сложность алгоритма

можно оценить как O(|I| · max(|G|, |M|, |B|)). Отсутствие предподсчета осво-

бождает от необходимости хранить лишние данные, поэтому сложность по

памяти составит O(|I|), что необходимо для хранения всех троек. Проверка

уникальности вычисленного трикластера существенно усложняется с ростом

общего количества трикластеров (в худшем случае O(|I| log(|I|)).

4.2. Метод Tri-k-means

Для сравнения предложенного выше метода с альтернативным вариантом

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

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

контекста. Пусть K = (G, M, B, W, I) — многозначный триадический кон-

текст. Пусть функция V : G × M × B → W переводит тройку (g, m, b) в со-

ответствующее значение w тогда и только тогда, когда (g, m, b, w) ∈ I, а Q ⊆

⊆ G × M × B - ее область определения.

Расстояние между тройками t₁ = (g₁, m₁, b₁) ∈ Q и t₂ = (g₂, m₂, b₂) ∈ Q вы-

числяется по формуле

ρ(t₁, t₂) = |V (t₁) - V (t₂)| + γ([g₁ = g₂] + [m₁ = m₂] + [b₁ = b₂]),

где γ является вещественным параметром, определяющим приоритетность

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

мерениям. Выражение [a₁ = a₂] принимает значение 0, если координаты трой-

ки в соответствующем измерении эквивалентны, и 1 иначе.

В результате работы алгоритма получаем k кластеров, состоящих из тро-

ек. Для сравнения с методом NOAC требуется перевести их в трикластеры.

Пусть H ⊆ Q - множество триплетов, входящих в кластер. Тогда трикласте-

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

T = ({g | ∃(g,m,b) ∈ H},{m | ∃(g,m,b) ∈ H},{b | ∃(g,m,b) ∈ H}).

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

войдут все значения, содержащиеся в тройках исходного кластера. Эту адап-

тацию классического алгоритма k-средних было решено назвать методом

Tri-k-means. Вычислительная сложность одной итерации алгоритма k-сред-

них линейно зависит от параметра k и общего количества трикластеров, по-

этому может быть оценена как O(k · |G||M||B|). Пусть i - количество итера-

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

оценить как O(k · i · |G||M||B|).

5. Эксперименты

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

таты экспериментов доступны по ссылке: https://github.com/EgurnovD/

TriclusteringToolbox.

5.1. Описание данных

Утилитой ContextGenerator был создан эталонный контекст, состоящий

из 1120 троек, сформированных в два кубоида со значениями 3 и 7. Для

него построены наборы контекстов с пропущенными значениями (10-90%) и

размытием значений с различной амплитудой (0,1-2).

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

100k проекта GroupLens [12] (https://grouplens.org/datasets/movielens/

100k/), содержащего информацию о 100 000 оценках по пятибалльной шка-

ле, поставленных 1000 пользователями сайта MovieLens 1700 фильмам при

наличии 19 жанров.

5.2. Результаты экспериментов

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

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

дополнительной обработки при уровне потерь 10%. Метод Tri-k-means спра-

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

количестве трикластеров (параметр k).

Вторая серия экспериментов была посвящена проверке на шумоустойчи-

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

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

ры, вычисленные методом Tri-k-means, в среднем имели большую дисперсию

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

туде размытия.

На реальных данных и метод NOAC, и метод Tri-k-means генерируют три-

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

рождает значительно более плотные трикластеры. Их можно интерпретиро-

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

наково оценивших схожие по жанрам фильмы. Отсутствующие значения в

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

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

отклоняясь от среднего значения.

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

В данной работе были рассмотрены современные методы би- и трикла-

стеризации, а именно OAC-трикластеризация, шкалирование формальных

150 000

Tri-k-means

NOAC

100 000

50 000

10 000 20 000 30 000 40 000 50 000 60 000 70 000 80 000 90 000100 000

Число троек

Зависимость времени работы от объема выборки.

понятий (Conceptual Scaling) и межпорядковое шкалирование (Interordinal

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

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

расширением ОАС-трикластеризации на многозначный случай, назван ме-

тодом NOAC. Другой представляет собой классический алгоритм кластери-

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

ний (метод Tri-k-means). Эксперименты показали, что на синтетических кон-

текстах метод NOAC лучше справляется с размытием значений. Из реальных

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

но тратит на это немного больше времени (см. рисунок). Стоит отметить, что

метод NOAC принимает только один легко интерпретируемый параметр.

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

1. Zaki M.J., Meira Jr W. Data Mining and Machine Learning: Fundamental Concepts

and Algorithms. Cambridge University Press, 2020.

2. Madeira S.C., Oliveira A.L. Biclustering algorithms for biological data analysis: a

survey // IEEE/ACM Trans. on Comp. Biol. and Bioinf., IEEE. 2004. V. 1. No. 1.

P. 24-45.

3. Henriques R., Madeira S.C. Triclustering algorithms for three-dimensional data anal-

ysis: a comprehensive survey // ACM Computing Surveys (CSUR), ACM. 2018.

V. 51. No. 5. P. 1-43.

4. Ignatov D.I., Gnatyshak D.V., Kuznetsov S.O., Mirkin B.G. Triadic formal con-

cept analysis and triclustering: searching for optimal patterns // Machine Learning,

Springer. 2015. V. 101. No. 1. P. 271-302.

5. Kaytoue M., Kuznetsov S.O., Macko J., Napoli A Biclustering meets triadic concept

analysis // Ann. Math. Artif. Intell., Springer. 2014. V. 70. No. 1. P. 55-79.

6. Ganter B., Wille R. Formal Concept Analysis: Mathematical Foundations. Berlin/

Heidelberg: Springer, 1999.

7. Ignatov D.I., Kuznetsov S.O., Poelmans J. Concept-based biclustering for internet

advertisement // In proc. ICDMW, IEEE. 2012. P. 123-130.

8. Lehmann F., Wille R. A triadic approach to formal concept analysis // Conceptual

Structures, LNCS, Springer. 1995. V. 954. P. 32-43.

9. Voutsadakis G. Polyadic Concept Analysis // Order, Springer Verlag. 2002. V. 19.

No. 3. P. 295-304.

10. Ganter B., Obiedkov S. Implications in triadic formal contexts // In proc. Interna-

tional Conference on Conceptual Structures, Springer. 2004. P. 186-195.

11. Ananias K.H.A., Missaoui R., Ruas P.H.B., Zarate L.E., Song M.A.J. Triadic con-

cept approximation // Information Sciences, Elsevier. 2021. V. 572. P. 126-146.

12. Harper F.M., Konstan J.A. The movielens datasets: History and context // ACM

Transact. on Interactive Intell. Syst., ACM. 2015. V. 5. No. 4. P. 1-19.

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

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

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

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