Finding dependencies in data based on methods of satisfying table con-straints

Full Text

Введение

В статье для решения задач машинного обучения (МО), связанных с извлечением паттернов, предлагается новый подход на основе парадигмы программирования в ограничениях. Данную парадигму предлагается применять для генерации кандидатов в искомые паттерны. Любой метод удовлетворения ограничений содержит две обязательные компоненты: одна из них реализует рассуждения на ограничениях, а другая служит для разбиения пространства поиска на меньшие подпространства для их дальнейшего исследования [1]. Рассуждения на ограничениях носят дедуктивный характер и сводятся к последовательному усечению исходных областей определения переменных путём исключения из них «лишних» значений, т.е. значений, которые не способны образовывать ни одного решения.

Статья посвящена разработке авторских методов поиска в данных особого типа закономерностей (причинно-следственных отношений), называемых частыми паттернами. Под частым паттерном понимается совокупность признаков, которая характеризует большое количество объектов обучающей выборки. Существующие методы выявления паттернов не позволяют гибко учитывать дополнительные требования к их виду [2]. Учёт новых условий, которым должны удовлетворять искомые закономерности, приводит к трудоёмкой модификации ранее используемых алгоритмов. Анализ подобных дополнительных условий влечёт снижение производительности вычислений.

В отличие от исследований, посвящённых использованию технологии программирования в ограничениях для выявления зависимостей в данных [3–6], предлагаемый подход основан на оригинальном способе представления обучающей выборки с помощью специализированных табличных ограничений – сжатых таблиц D-типа [7], а не на основе представления в виде объектно-признаковой таблицы (бинарной матрицы). Особое внимание уделяется решению задачи поиска замкнутых паттернов, которые являются своеобразным базисом в пространстве рассматриваемых закономерностей. Решение задачи поиска замкнутых паттернов входит как часть в решение рассматриваемых в работе задач МО, включающих учёт и анализ дополнительных требований к виду искомых паттернов. В качестве дополнительных требований к виду паттерна рассмотрены ограничения на частоту встречаемости замкнутого паттерна, а также условия на вхождение некоторого элемента (признака) в паттерн. В работе применяется авторский метод поиска с возвратами, а также специализированные правила редукции для табличных ограничений. Предлагаемый подход позволяет легко адаптироваться к дополнительным требованиям, накладываемым на паттерны. Для этого к основным правилам редукции сжатых таблиц D-типа, используемым при поиске замкнутых паттернов, добавляются новые правила, учитывающие интересующие особенности анализируемых закономерностей.

1. Задача удовлетворения табличных ограничений

При использовании парадигмы программирования в ограничениях решаемая задача представляется, как задача удовлетворения ограничений [8]. Задача удовлетворения ограничений заключается в поиске решений для сети ограничений [9]. Сеть ограничений задаётся тремя компонентами <X,D,C>: X – множество переменных {X₁, X₂, …, X_n}, D – множество доменов переменных {D₁, D₂, …, D_n}, C – множество ограничений {C₁, C₂, ….C_m}, которые регламентируют допустимые сочетания значений переменных. Каждый домен D_i описывает множество допустимых значений {v₁,…,v_k} для переменной X_i.

В работе [7] выполнен обзор табличных ограничений, к которым, в частности, относятся сжатые таблицы (компактные таблицы) и смарт-таблицы [10–13].

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

Пример 1. Пусть дано отношение в виде бинарной матрицы (см. таблицу 1). В рамках МО данная бинарная матрица может рассматриваться как обучающая выборка. Строки матрицы соответствуют объектам, а столбцы – атрибутам. Можно предположить, например, что объекты - это какие-то транзакции покупок, а атрибуты - определённые товары.

 

Таблица 1 – Пример бинарной матрицы

	a	b	c	d
1	1	1
2	1	1	1	1
3	1			1
4		1	1
5			1

 

Данная бинарная матрица может быть записана как сжатая таблица C-типа:

$R\left[XY\right]=\left[\begin{array}{l}\begin{array}{cc}\left\{\mathrm{1,2,3}\right\}& \left\{a\right\}\\ \left\{\mathrm{1,2,4}\right\}& \left\{b\right\}\end{array}\\ \begin{array}{cc}\left\{\mathrm{2,4,5}\right\}& \left\{c\right\}\\ \left\{\mathrm{2,3}\right\}& \left\{d\right\}\end{array}\end{array}\right].$

Домен переменной X - это множество объектов {1, 2, 3, 4, 5}, домен переменной Y - это множество атрибутов {a, b, c, d}. Каждый кортеж данной сжатой таблицы C-типа компактно описывает множество ячеек бинарной матрицы, где стоят единицы (т.е. определённое множество элементарных кортежей). Например, первый кортеж компактно описывает множество ячеек первого столбца бинарной матрицы: (1, a), (2, a), (3, a). Вся таблица C-типа интерпретируется как объединение множеств элементарных кортежей, описываемых её отдельными строками. Обучающая выборка также может быть представлена в виде сжатой таблицы D-типа:

$K\left[XY\right]=\left]\begin{array}{l}\begin{array}{cc}\left\{\mathrm{1,2,3}\right\}& \{b,c,d\}\\ \left\{\mathrm{1,2,4}\right\}& \{a,c,d\}\end{array}\\ \begin{array}{cc}\left\{\mathrm{2,4,5}\right\}& \{a,b,d\}\\ \left\{\mathrm{2,3}\right\}& \{a,b,c\}\end{array}\end{array}\right[.$

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

Каждая строка таблицы K[XY] соответствует столбцу исходной бинарной матрицы. Например, первая строка K[XY] соответствует первому столбцу бинарной матрицы и компактно описывает следующее логическое выражение:

(Y ∈ {a}) → (X ∈ {1, 2, 3}).

Эта формула после замены операции импликации может быть записана следующим образом:

(Y ∈/ {a}) ∨ (X ∈ {1, 2, 3}).

Последнее выражение эквивалентно следующей записи:

(Y ∈ {b, c, d}) ∨ (X ∈ {1, 2, 3}).

Сжатая таблица D-типа целиком компактно описывает множество истинности конъюнкции импликаций, соответствующих каждой её строке.

При определении рассматриваемых табличных ограничений могут использоваться два типа фиктивных компонент: пустая компонента (“∅”), которая не содержит значений, и полная компонента (“∗”), которая содержит все значения из соответствующего домена.

Стоит отметить, что исходное отношение (бинарная матрица) может быть представлено в виде сжатых таблиц C- и D-типа не единственным способом. Например, каждый кортеж сжатой таблицы может отображаться не в столбец, а в строку исходной бинарной матрицы.

Как и к обычным таблицам, к сжатым таблицам также можно применять операции реляционной алгебры. Эти операции проводятся с использованием специализированных теорем без разложения сжатых таблиц на обычные таблицы [14].

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

Задача поиска замкнутых паттернов состоит в том, чтобы на основе исходного представления обучающей выборки в виде бинарной матрицы (объектно-признаковой таблицы), найти все замкнутые паттерны.

Пусть I ={1, ..., n} – множество идентификаторов элементов или атрибутов, а T ={1, ..., m} – множество идентификаторов транзакций или объектов. Паттерн p (элементный набор) – это любое подмножество множества I. Транзакционная база данных - это множество D⊆I×T. Множество элементов, соответствующих транзакции t, обозначается D[t]={i | (i, t)∈D}. Транзакция t содержит паттерн p тогда и только тогда, когда множество D[t] содержит p (т.е. p⊆D[t]). Покрытие паттерна p, обозначается T_D(p), - это множество транзакций, содержащих p (т.е. T_D(p)={t∈T|p⊆D[t]}). Пусть дано подмножество транзакций S⊆T, тогда I_D(S)=∩_t∈SD[t] описывает множество общих элементов S. Замыкание паттерна p в D, обозначается Close(p)=I_D(T_D(p)), - это множество общих элементов его покрытия T_D(p). Паттерн p является замкнутым тогда и только тогда, когда Close(p)=p.

Для решения задач, связанных с выявлением паттернов, используются различные алгоритмы, например алгоритм Apriori [15]. Выявление замкнутых паттернов — операция, требующая много вычислительных ресурсов и времени, особенно если кроме свойства замкнутости паттерна приходится анализировать дополнительные требования к виду искомых закономерностей. Наиболее популярным требованием к виду паттерна является ограничение на частоту его встречаемости в обучающей выборке.

Абсолютная частота паттерна (абсолютная поддержка паттерна) p – это мощность его покрытия, т.е. freq_D(p) = |T_D(p)|. Пусть дана константа θ ∈ N, называемая минимальной абсолютной поддержкой паттерна (порогом абсолютной поддержки паттерна), тогда паттерн p является частым, если freq_D(p)≥θ. Задача нахождения частых замкнутых паттернов заключается в нахождении всех паттернов p, таких что freq_D(p) ≥ θ и Close(p) = p. Большинство алгоритмов, в том числе модификации алгоритма Apriori, используют при поиске паттернов с ограничением на частоту встречаемости свойство антимонотонности: c ростом мощности множества элементов паттерна его покрытие уменьшается либо остаётся тем же. Из данной формулировки следует, что любое k-элементное множество будет часто встречающимся тогда и только тогда, когда все его (k−1)-элементные подмножества будут часто встречающимися.

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

• ограничения на наличие/отсутствие элемента в паттерне;
• ограничения на подпаттерн и суперпаттерн;
• ограничения на количество элементов в паттерне;
• агрегатные ограничения, представляющее собой количественные ограничения на совокупности элементов в паттерне, где агрегатной функцией может быть сумма, среднее значение, максимум, минимум и т.д.

Например, если в качестве элементов транзакций выступают покупки в некотором магазине, то в качестве агрегатного ограничения может рассматриваться сумма счёта (по чеку), превышающая какую-либо сумму (например, 2000 рублей).

Для демонстрации возможностей предлагаемого подхода в работе рассматривается два типа дополнительных ограничений: ограничения на наличие/отсутствие элемента в паттерне и ограничения на частоту встречаемости паттерна в обучающей выборке.

3. Метод решения задачи выявления замкнутых паттернов

Разработанный метод состоит из двух этапов: на первом этапе генерируются кандидаты в замкнутые паттерны, на втором выполняется проверка, удовлетворяют ли кандидаты требованиям к замкнутым паттернам. В терминах табличных ограничений (см. раздел 1) обучающая выборка представляется как сжатая таблица D-типа, а каждый кандидат в замкнутые паттерны и искомый паттерн представляется, как сжатая таблица C-типа [A, B], которая состоит из одной строки, где A Í T, B Í I. B – это собственно паттерн, а A – его покрытие.

В примере 1 показано, как кортеж сжатой таблицы D-типа может быть соотнесён с каждым столбцом исходной бинарной матрицы, которая моделирует обучающую выборку. Для этого примера задача нахождения замкнутых паттернов может быть интерпретирована как нахождение значимых комбинаций одновременно приобретаемых товаров. Замкнутые паттерны обеспечивают минимальное представление всех паттернов, т.е можно получить все паттерны из замкнутых.

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

Первый этап. На этом этапе важно исключить как можно больше явно неперспективных случаев. Для этого необходимо: 1) представить обучающую выборку в виде сжатой таблицы D-типа; 2) преобразовать сжатую таблицу D-типа в эквивалентную сжатую таблицу C-типа с помощью методов ветвления и отсечения неперспективных ветвей дерева поиска. Каждый из полученных кортежей является кандидатом в паттерны.

Разработанный метод нахождения замкнутых паттернов включает систематическое исследование пространства поиска и построение дерева поиска следующим образом. Каждый уровень дерева поиска отображается в одну из строк сжатой таблицы D-типа, а узел отображается в определённую компоненту этой строки. Каждое решение задачи удовлетворения ограничений формируется путём выбора одной компоненты из каждой строки сжатой таблицы D-типа. Фрагмент дерева поиска для примера 1, построенного на основе сжатой таблицы K[XY], показан на рисунке 1.

 

Рисунок 1 – Фрагмент дерева поиска для задачи нахождения замкнутых паттернов

 

Второй этап. Для каждого кандидата в замкнутые паттерны, описанного сжатым кортежем [A, B], выполняется следующая проверка.

1)    для объектов A вычисляется I_D(A). Это вычисление выполняется путём перемножения булевых векторов, соответствующих объектам из множества A.

2)    I_D(A) сравнивается с множеством B, в случае несовпадения - вывод отрицательный. Иначе проверка прошла успешно.

На рисунке 1 серым фоном обозначены кандидаты в паттерны, не прошедшие проверку.

Все замкнутые паттерны, найденные в примере 1 и прошедшие проверку, - это сжатые кортежи, которые можно объединить в одну сжатую таблицу C-типа:

$\left[\begin{array}{cc}\left\{\mathrm{1,2,3}\right\}& \left\{a\right\}\\ \left\{\mathrm{1,2,4}\right\}& \left\{b\right\}\\ \left\{\mathrm{2,4,5}\right\}& \left\{c\right\}\\ \left\{\mathrm{1,2}\right\}& \{a,b\}\\ \left\{\mathrm{2,4}\right\}& \{b,c\}\\ \left\{\mathrm{2,3}\right\}& \{a,d\}\\ \left\{2\right\}& \{a,b,c,d\}\end{array}\right].$

Общая алгоритмическая сложность двух стадий предложенного метода может быть вычислена как: O((|T||I|+2∗|I|+2∗|T|-min(|T|,|I|))∗2^min(|T|,|I|)). Более подробно описанные этапы изложены в [16].

Ускорение базового метода поиска. Известны три способа ускорения базового метода поиска: 1) использование отношений частичного порядка на множестве объектов и признаков; 2) сужение пространства поиска за счёт распространения ограничений; 3) использование дополнительных ограничений. Первый способ разобран в [16]. В данной работе рассматриваются 2-й и 3-й способы.

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

Утверждение 1 (У1). Если в сжатой таблице D-типа имеется пустой столбец (столбец, содержащий все пустые компоненты), то этот столбец удаляется из таблицы.

Утверждение 2 (У2). Если в сжатой таблице D-типа имеется пустая строка (строка, содержащая все пустые компоненты), то таблица пуста (задача удовлетворения ограничений не имеет решения).

Утверждение 3 (У3). Если в сжатой таблице D-типа имеется строка, содержащая только одну непустую компоненту, то элементы, не принадлежащие этой компоненте, удаляются из соответствующего домена.

Утверждение 4 (У4). Если в сжатой таблице D-типа имеется строка, содержащая хотя бы одну полную компоненту, то эта строка удаляется из сжатой таблицы D-типа.

Утверждение 5 (У5). Если компонента сжатой таблицы D-типа содержит элемент, не принадлежащий соответствующему домену, то этот элемент удаляется из компоненты.

 

Таблица 2 – Пример применения правил редукции

	a	b	c	d
1	1	1
2	1	1
3			1	1
4			1	1

 

$\begin{array}{l}\text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}XY\\ \left\{\mathrm{1,2,3,4}\right\}\{a,b,c,d\}\\ \begin{array}{c}1\\ 2\\ 3\\ 4\end{array}\left]\begin{array}{cc}\left\{\mathrm{1,2}\right\}& \{b,c,d\}\\ \left\{\mathrm{1,2}\right\}& \{a,c,d\}\\ \left\{\mathrm{3,4}\right\}& \{a,b,d\}\\ \left\{\mathrm{3,4}\right\}& \{a,b,c\}\end{array}\right[\end{array}$

Здесь в заголовках столбцов перечислены имена соответствующих переменных и доменов этих переменных.

Пусть на первом шаге поиска выбрана первая компонента первой строки (компонента {1, 2}), т.е. домен переменной X равен множеству {1, 2}. Тогда согласно утверждению У4, первая и вторая строки удаляются из сжатой таблицы. Первые компоненты третьей и четвёртой строк становятся равны пустому множеству на основании утверждения У5. Тогда:

$\begin{array}{l}\text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}XY\\ \left\{\mathrm{1,2}\right\}\{a,b,c\}\\ \begin{array}{c}3\\ 4\end{array}\left]\begin{array}{cc}\varnothing & \{a,b,d\}\\ \varnothing & \{a,b,c\}\end{array}\right[\end{array}$

Согласно утверждению У3, домен переменной Y сокращается до множества {a, b}, а оставшиеся строки удаляются на основании У4. Таким образом, все строки удаляются без формирования пустых строк, что означает нахождение решения. Получившееся решение описывается следующим сжатым кортежем в пространстве X, Y: [{1,2}, {a, b}]. Это решение является одним из замкнутых паттернов.

4. Ограничения на частоту встречаемости замкнутых паттернов

При нахождении частых паттернов сжатые таблицы сокращаются более активно по сравнения с нахождением просто замкнутых паттернов. Это происходит вследствие того, что к базовым правилам редукции У1-У5 добавляются два дополнительных правила.

Утверждение 6 (У6). Компоненты сжатой таблицы D-типа, соответствующие переменной X и имеющие мощность меньше определённой границы θ, заменяются пустыми компонентами.

Утверждение 7 (У7). Если мощность домена переменной X меньше определённой границы θ, то задача удовлетворения ограничений не имеет решения.

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

 

Рисунок 2 – Пример дерева поиска для задачи нахождения частых замкнутых паттернов

 

Условия задачи формулируются на основе исходных данных из примера 1, но налагается дополнительное ограничение θ = 2 на частоту встречаемости паттерна. Во время вывода используются приведённые правила редукции. Данное дерево содержит существенно меньше узлов, нежели дерево на рисунке 1, которое не удаётся полностью поместить на рисунок.

5. Ограничения на наличие/отсутствие элемента в замкнутом паттерне

5.1 Ограничение на наличие элемента в паттерне

Требуется найти все паттерны, содержащие некоторый заданный элемент y из домена переменной Y, т.е. требуется найти такие p, что .

Пусть обучающая выборка представлена с помощью сжатой таблицы D-типа. В этом случае в процессе вывода, помимо базовых утверждений У1-У5, применяются следующие утверждения.

Утверждение 8 (У8). В кортеже, где в компоненте Y отсутствует значение y, которое должно содержаться в искомых паттернах, данная компонента заменяется на пустую.

Утверждение 9 (У9). Если в домене атрибута Y отсутствует значение y, которое должно содержаться в искомом паттерне, то задача удовлетворения ограничений не имеет решения.

Пусть в качестве обучающей выборки выступает бинарная матрица из примера 1, представленная в виде сжатой таблицы D-типа K[XY]. Необходимо, чтобы искомые паттерны содержали элемент “c”. При этом ограничение на частоту встречаемости искомых паттернов имеет вид freq_D(p) ≥ 2.

Третий кортеж исходной сжатой таблицы D-типа K[XY] отличается от других кортежей таблицы тем, что его компонента Y не содержит значения “c”. Эту компоненту следует заменить на пустую, поскольку при генерации искомых паттернов данная компонента никогда не может быть выбрана, а следовательно всегда выбирается компонента X рассматриваемого кортежа. Тогда текущие домены переменных станут: XÎ{2, 4, 5}, YÎ{a, b, c, d}, а исходная таблица K[XY] с учётом новых доменов преобразуется на основе утверждений У1-У5 к следующему виду:

$\begin{array}{l}\begin{array}{cc}X& Y\end{array}\\ \begin{array}{cc}\left\{\mathrm{2,4,5}\right\}& \{a,b,c,d\}\end{array}\\ \begin{array}{c}1\\ 2\\ 4\end{array}\left]\begin{array}{l}\begin{array}{cc}\left\{2\right\}& \{b,c,d\}\\ \left\{\mathrm{2,4}\right\}& \{a,c,d\}\end{array}\\ \begin{array}{cc}\left\{2\right\}& \{a,b,c\}\end{array}\end{array}\right[.\end{array}$

Из анализа требования к частоте встречаемости паттерна получается:

$\begin{array}{l}\begin{array}{cc}X& Y\end{array}\\ \begin{array}{cc}\left\{\mathrm{2,4,5}\right\}& \{a,b,c,d\}\end{array}\\ \begin{array}{c}1\\ 2\\ 4\end{array}\left]\begin{array}{l}\begin{array}{cc}\varnothing & \{b,c,d\}\\ \left\{\mathrm{2,4}\right\}& \{a,c,d\}\end{array}\\ \begin{array}{cc}\varnothing & \{a,b,c\}\end{array}\end{array}\right[.\end{array}$

По сравнению с предыдущей сжатой таблицей D-типа в кортежах все компоненты X, мощность которых меньше заданного порога встречаемости (q = 2), заменяются пустыми компонентами (согласно У6). Тогда, применяя утверждения У1-У5, получаются следующие новые домены переменных: X Î {2, 4, 5}, Y Î {b, c}, а «остаток» сжатой таблицы D-типа будет иметь вид:

$\begin{array}{l}\begin{array}{cc}X& Y\end{array}\\ \begin{array}{cc}\left\{\mathrm{2,4,5}\right\}& \{b,c\}\end{array}\\ \left]\begin{array}{cc}\left\{\mathrm{2,4}\right\}& \left\{c\right\}\end{array}\right[.\end{array}$

Дерево поиска для рассмотренного примера представлено на рисунке 3. Таким образом, в качестве решения имеются следующие паттерны: [{2,4} {b,c}] и . Видно, что они удовлетворяют как требованию на вхождение в паттерн элемента “с”, так и требованию к частоте встречаемости искомых паттернов. Анализируя рисунок 3, можно сделать вывод, что других замкнутых паттернов с заданным набором ограничений не существует.

 

Рисунок 3 – Дерево поиска для задачи нахождения паттернов с заданным элементом (пример)

 

5.2 Ограничение на отсутствие элемента в паттерне

Пусть требуется найти все паттерны, не содержащие некоторый заданный элемент y из домена переменной Y, т.е. требуется найти такие p, что $y\notin p,y\in I$. В этом случае к базовым утверждениям У1-У5 добавляются следующие утверждения.

Утверждение 10 (У10). В кортеже, где в компоненте Y отсутствует значение y, которое не должно содержаться в искомых паттернах, компонента X заменяется на пустую.

Утверждение 11 (У11). Если в сжатой таблице отсутствует кортеж, компонента Y которого не содержит значение y, то задача удовлетворения ограничений не имеет решения.

Пример 3. Пусть имеется обучающая выборка из примера 1 и требуется найти замкнутые паттерны, которые не должны содержать элемент “a” (т.е. $a\notin p$), при этом паттерны должны удовлетворять требованию freq_D(p)≥2.

В качестве исходной берётся сжатая таблица D-типа K[XY] из примера 1. Поскольку получаемые паттерны не должны содержать элемент “a”, то всегда должна выбираться компонента Y, не содержащая данный элемент, – это компонента Y первого кортежа таблицы K[XY]. Это означает, что компоненту X первого кортежа таблицы K[XY], следует заменить на пустую компоненту. В результате, согласно У1-У5, получается:

$\begin{array}{l}\begin{array}{cc}X& Y\end{array}\\ \begin{array}{cc}\left\{\mathrm{1,2,3,4,5}\right\}& \{b,c,d\}\end{array}\\ \begin{array}{c}2\\ 3\\ 4\end{array}\left]\begin{array}{l}\begin{array}{cc}\left\{\mathrm{1,2,4}\right\}& \{c,d\}\end{array}\\ \begin{array}{cc}\left\{\mathrm{2,4,5}\right\}& \{b,d\}\\ \left\{\mathrm{2,3}\right\}& \{b,c\}\end{array}\end{array}\right[.\end{array}$

Дерево поиска представлено на рисунке 4. Пусть в полученной сжатой таблице выбирается компонента X первой строки. Тогда текущие домены переменных описываются следующим образом: X Î {1, 2, 4}, Y Î {b, c, d}. После «настройки» упрощённой сжатой таблицы на новый домен переменной X, получается:

$\begin{array}{l}\begin{array}{cc}X& Y\end{array}\\ \begin{array}{cc}\left\{\mathrm{1,2,4}\right\}& \{b,c,d\}\end{array}\\ \begin{array}{c}3\\ 4\end{array}\left]\begin{array}{l}\begin{array}{cc}\left\{\mathrm{2,4}\right\}& \{b,d\}\end{array}\\ \begin{array}{cc}\left\{2\right\}& \{b,c\}\end{array}\end{array}\right[.\end{array}$

В процессе вывода используется тот факт, что искомый паттерн должен иметь порог абсолютной частоты встречаемости θ=2. Следовательно, к полученной сжатой таблице можно применить утверждение У6. Тогда новые домены переменных: X ∈ {1, 2, 4}, Y ∈ {b, c}. Применяя У1-У5, получается сжатая таблица D-типа, состоящая из одной строки:

$\begin{array}{l}\begin{array}{cc}X& Y\end{array}\\ \begin{array}{cc}\left\{\mathrm{1,2,4}\right\}& \{b,c\}\end{array}\\ \left]\begin{array}{cc}\left\{\mathrm{2,4}\right\}& \left\{b\right\}\end{array}\right[.\end{array}$

В результате прохода по данной ветке листовые вершины дерева поиска получаются путём выбора одной из компонент сжатой таблицы (см. рисунок 4). Всего в данном дереве поиска получаются три паттерна с заданной частотой встречаемости и не содержащие элемент “a”: $\left[\begin{array}{cc}\left\{\mathrm{2,4}\right\}& \{b,c\}\end{array}\right]$, $\left[\begin{array}{cc}\left\{\mathrm{1,2,4}\right\}& \left\{b\right\}\end{array}\right]$, $\left[\begin{array}{cc}\left\{\mathrm{2,4,5}\right\}& \left\{c\right\}\end{array}\right]$.

 

Рисунок 4 – Дерево поиска для задачи нахождения паттернов, не содержащих заданный элемент (пример)

 

Заключение

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

Новизной исследований является то, что обучающую выборку предложено представлять в виде специального типа табличных ограничений - сжатых таблиц D-типа. Такое представление информации и предложенный способ построения дерева поиска позволяют ускорить процесс вычислений: для некоторых типов входных данных приведённая оценка вычислительной сложности авторского метода нахождения замкнутых паттернов оказывается лучше, чем оценка большинства методов-прототипов [16]. Дополнительное сокращение количества узлов дерева поиска достигается за счёт применения разработанных процедур распространения табличных ограничений, основанных на эквивалентных преобразованиях сжатых таблиц D-типа с использованием специализированных правил редукции.

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

About the authors

Alexander A. Zuenko

Putilov Institute for Informatics and Mathematical Modeling, Subdivision of the Federal Research Centre «Kola Science Centre of the Russian Academy of Sciences»

Author for correspondence.
Email: zuenko@iimm.ru
ORCID iD: 0000-0002-7165-6651
Scopus Author ID: 26536974000
ResearcherId: E-7944-2017

PhD, Senior Researcher 

Russian Federation, Apatity

Olga N. Zuenko

Putilov Institute for Informatics and Mathematical Modeling, Subdivision of the Federal Research Centre «Kola Science Centre of the Russian Academy of Sciences

Email: ozuenko@iimm.ru
ORCID iD: 0000-0001-5431-7538
Scopus Author ID: 57222359556
ResearcherId: HKN-6360-2023

Junior Researcher 

Russian Federation, Apatity

References

Supplementary files