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

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

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

Пусть $X = \left\{ {{{x}_{1}},~ \ldots ,~{{x}_{n}}~} \right\}$ – заданное множество атрибутов; H – набор из r атрибутов вида – набор, в котором σ_i – допустимое значение атрибута ${{x}_{{{{j}_{i}}}}},i = \overline {1,{\text{\;}}r} $. Пару (σ, H) назовем элементарным фрагментом (ЭФ) ранга r. Через W(X) обозначим множество всех ЭФ, порождаемых набором атрибутов X.

Пусть $S = \left( {{{a}_{1}},~ \ldots ,~{{a}_{n}}} \right)~$– объект из M (здесь a_j, $j \in \left\{ {1,~2,~ \ldots ,~n~} \right\}$, – значение атрибута x_j для объекта S). Будем говорить, что S содержит ЭФ $\left( {{{\sigma }},~H} \right),H = \left\{ {{{x}_{{{{j}_{1}}}}}, \ldots ,~{{x}_{{{{j}_{r}}}}}} \right\},{{\sigma }} = \left( {{{{{\sigma }}}_{1}},~ \ldots ,{{{{\sigma }}}_{r}}} \right)$, если ${{a}_{{{{j}_{i}}}}} = {{\sigma }_{i}}$ при $i = \overline {1,{\text{\;}}r} $.

Дана некоторая совокупность объектов D из M и задано число p, 1$ \leqslant p \leqslant \left| D \right|$, где $\left| D \right|$ – число объектов в D. Объекты в D не обязательно различны.

ЭФ (σ, H), $\left( {{{\sigma }},~H} \right) \in W\left( X \right)$, называется (p, D)-частым, если для не менее p объектов из D содержат (σ, H). ЭФ $\left( {\sigma ,~H} \right),{\text{\;}}\left( {\sigma ,~H} \right) \in W\left( X \right)$, ранга $r,{\text{\;}}r \leqslant \left| D \right|$, называется правильным в D, если (σ, H) – ‒ (r, D)-частый. ЭФ $\left( {{{\sigma }},~H} \right),{\text{\;}}\left( {{{\sigma }},~H} \right) \in W\left( X \right)$, называется нечастым в D, если ни один объект из D не содержит (σ, H), и минимальным нечастым в D, если из условия ${{\sigma }}' \subset {{\sigma }},{\text{\;}}H' \subset H$ следует, что ЭФ $\left( {{{\sigma '}},~H'} \right)$ не является нечастым в D.

Логическая классификация целочисленных данных предполагает наличие нескольких непересекающихся выборок ${{D}_{{1~}}},~ \ldots ~,~{{D}_{{l~}}}_{~}$, $l \geqslant 2$, объектов из M, каждая из которых представляет некоторый класс объектов. Объекты, содержащиеся в этих выборках, называются прецедентами, а атрибуты из X – признаками. На этапе обучения в каждой выборке ${{D}_{{i~}}},{\text{\;}}i \in \left\{ {1,~2,~ \ldots ,~l} \right\}$, ищутся такие частые ЭФ, которые являются нечастыми в D_j при любом $j \ne i$. Найденные ЭФ позволяют различать прецеденты из разных классов и называются логическими закономерностями или представительными элементарными классификаторами [1–6].

Могут накладываться некоторые дополнительные условия на вид искомых ЭФ (в зависимости от рассматриваемой модели классификатора). Например, ищутся так называемые тупиковые представительные элементарные классификаторы. Элементарный классификатор (σ, H) называется тупиковым представительным для ${{D}_{{i~}}},{\text{\;}}i \in \left\{ {1,~2,~ \ldots ,~l} \right\}$, если выполнены два условия: 1) (σ, H) – $\left( {1,~{{D}_{{i~}}}} \right)$-частый ЭФ; 2) (σ, H) – минимальный нечастый в D_j  при любом $j \ne i$. В этом случае при поиске минимальных нечастых ЭФ возникает необходимость рассматривать труднорешаемую дискретную задачу построения тупиковых покрытий целочисленной матрицы [3], строками которой являются описания прецедентов, не принадлежащих D_i.

В [6] предложена модель логического классификатора, базирующаяся на первоначальном поиске в каждой выборке ${{D}_{{i~}}},{\text{\;}}i \in \left\{ {1,~2,~ \ldots ,~l} \right\}$, правильных ЭФ и последующем отборе среди них тех, которые не содержатся в описаниях прецедентов из других классов. Данная модель демонстрирует существенное преимущество по скорости счета перед классической моделью, основанной на построении тупиковых представительных элементарных классификаторов, не уступая последней в качестве классификации.

Представляет интерес получение асимптотических оценок (при n → ∞) типичного числа правильных ЭФ и оценок типичной длины правильного ЭФ. В [7] требуемые оценки получены для случая, когда число объектов в D существенно меньше числа атрибутов и каждый атрибут принимает значения из множества {$0,1, \ldots ,k - 1\} ,~k \geqslant 2$.

Полученные в работе новые результаты в основном касаются изучения метрических свойств множества правильных ЭФ в случае $n \leqslant \left| D \right|$. Следует отметить, что аналогичные свойства множества минимальных нечастых ЭФ ранее изучались в ряде публикаций (например, [3, 8, 9]), в которых в том числе рассматривался случай $n \leqslant \left| D \right|$. Приводимые в статье оценки числа минимальных нечастых ЭФ имеют вид, позволяющий сравнивать их с соответствующими оценками правильных ЭФ. Результат сравнения свидетельствует о целесообразности (в плане сокращения временных затрат) применения методов поиска частых ЭФ для синтеза логических классификаторов и согласуется с полученными в [6] результатами экспериментов на случайных модельных данных.

В разд. 1 дана постановка задачи. Исходные данные представлены в виде целочисленной матрицы, строками которой являются описания объектов из D. Приведены формулировки двух основных теорем о числе правильных ЭФ. Доказательства этих теорем содержатся в разд. 2. В разд. 3 приведены полученные ранее и новые оценки типичных значений числа минимальных нечастых ЭФ и длины минимального нечастого ЭФ.

1. Постановка задачи и формулировки основных результатов. Пусть L, $L = ({{a}_{{ij}}}),i = \overline {1,~m} ,j = \overline {1,~n} $, – матрица с элементами из {$0,1, \ldots ,k - 1\} ,{\text{\;}}k \geqslant 2;{\text{\;}}E_{k}^{r},{\text{\;}}r \leqslant n,{\text{\;}}k \geqslant 2$, – множество наборов (σ₁, ..., σ_r), ${{\sigma }_{i}} \in \left\{ {0,~1, \ldots ,k - 1} \right\},{\text{\;}}i = \overline {1,{\text{\;}}r} ;{\text{\;}}W_{r}^{n},{\text{\;}}r \leqslant n$, – множество всех наборов вида $\left\{ {{{j}_{1}},~ \ldots ,~{{j}_{r}}} \right\}$, где ${{j}_{t}} \in \left\{ {1,~2,~ \ldots ,n} \right\}$ при $t = \overline {1,{\text{\;}}r} $ и ${{j}_{1}} < \ldots < {{j}_{r}};{\text{\;}}V_{r}^{m},{\text{\;}}r \leqslant m$, – множество всех упорядоченных наборов вида $\left( {{{i}_{1}}, \ldots ,{{i}_{r}}} \right)$, где ${{i}_{t}} \ne {{i}_{l}}$ при $t,~l = \overline {1,{\text{\;}}r} $.

Положим . Число $r$ назовем длиной набора w.

Набор w назовем σ-допустимым для L, если можно указать набор ${v} = \left( {{{i}_{1}}, \ldots ,{{i}_{r}}} \right),{v} \in V_{r}^{m}$, такой, что ${{a}_{{{{i}_{t}}{{j}_{t}}}}}$ $ = {{\sigma }_{t}}$ при $t = \overline {1,{\text{\;}}r} $. Будем говорить, что σ-допустимый набор w порождается набором σ.

Нетрудно видеть, что в случае, когда в качестве строк матрицы L берутся описания объектов из выборки D, то набор $w \in W_{r}^{n},{\text{\;}}w = \left\{ {{{j}_{1}},~ \ldots ,~{{j}_{r}}} \right\}$, является σ-допустимым для L тогда и только тогда, когда ЭФ $\left( {{{\sigma }},~H} \right),{\text{\;}}H = \left\{ {{{x}_{{{{j}_{1}}}}}, \ldots ,~{{x}_{{{{j}_{r}}}}}} \right\}$ – правильный в D.

Введем обозначения: $\mathfrak{M}_{{mn}}^{k}$ – множество всех матриц размера $m \times n$ с элементами из {$0,1, \ldots ,k - 1\} ,{\text{\;}}k \geqslant 2$; $U\left( {L,~\sigma } \right),{\text{\;}}L \in \mathfrak{M}_{{mn}}^{k},{\text{\;}}\sigma \in E_{k}^{r}$, – множество всех σ-допустимых наборов для матрицы L; ${{U}_{r}}\left( {L,~\sigma } \right)$ – множество всех наборов в $U\left( {L,~{{\sigma }}} \right)$ длины r; $U\left( L \right),{\text{\;}}L \in \mathfrak{M}_{{mn}}^{k}$, – совокупность всех допустимых для матрицы L наборов, в которой каждый набор встречается столько раз, сколькими наборами из $E_{k}^{r}$ он порождается; |N| – мощность множества N;

${{r}_{1}} = ~[0.~5{\text{lo}}{{{\text{g}}}_{k}}mn - 0.~5{\text{lo}}{{{\text{g}}}_{k}}{\text{log}}_{k}^{2}mn - {\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}n]$, здесь и далее [q] – целая часть от числа q; ${{r}_{2}} = \left] {0.~5{\text{lo}}{{{\text{g}}}_{k}}mn - 0.~5{\text{lo}}{{{\text{g}}}_{k}}{\text{log}}_{k}^{2}mn + {\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}n} \right[$, здесь и далее $\left] q \right[$ – наименьшее целое, превосходящее $q;{\text{\;}}{{\phi }_{1}}$ – интервал $\left[ {{{r}_{1}},~{{r}_{2}}} \right];{\text{\;}}{{r}_{3}} = \left] {{\text{lo}}{{{\text{g}}}_{k}}m + {\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}m} \right[;{\text{\;}}{{\phi }_{2}}$ – интервал $\left[ {1,~{{r}_{3}}} \right];{{b}_{n}} \approx {{c}_{n}},$ n → ∞, означает, что ${\text{li}}{{{\text{m}}}_{{n \to \infty }}}{{b}_{n}}{\text{/}}{{c}_{n}} = 1;{\text{\;}}{{b}_{n}} \preccurlyeq {{c}_{n}},{\text{\;}}n~ \to ~\infty $, означает, что ${\text{li}}{{{\text{m}}}_{{n \to \infty }}}{{b}_{n}}{\text{/}}{{c}_{n}} \leqslant 1$ .

Ниже приводятся асимптотические оценки типичного значения величины |U(L)| и оценки типичной длины допустимого для $L$ набора при различных значениях $m$ и $n$.

Выявление типичной ситуации связано с высказыванием типа “для почти всех матриц L из $\mathfrak{M}_{{mn}}^{k}$ при n → ∞ выполнено ${{F}_{1}}\left( L \right) \approx {{F}_{2}}\left( L \right)$” (здесь ${{F}_{1}}\left( L \right)$ и ${{F}_{2}}\left( L \right)$ – два функционала, заданные на матрицах из $\mathfrak{M}_{{mn}}^{k}$). Данное высказывание означает, что существуют две положительные бесконечно убывающие функции ${{\alpha }}\left( n \right)$ и ${{\beta }}\left( n \right)$, такие, что для всех достаточно больших $n$ имеет место

где $\mathfrak{M}$ – множество таких матриц L в $\mathfrak{M}_{{mn}}^{k}$, для которых

Справедливы приведенные ниже теоремы 1 и 2.

Теорема 1. Если ${{m}^{a}} \leqslant n \leqslant {{k}^{m}}^{{^{{{\beta }}}}},a > 1,{{\beta }} < 1,k \geqslant 2$, то при n → ∞ для почти всех матриц L из $\mathfrak{M}_{{mn}}^{k}$ имеет место

и длины почти всех наборов из U(L) принадлежат интервалу ϕ₁.

Теорема 2. Если $n \leqslant m \leqslant {{k}^{{{{n}^{\beta }}}}},{{\beta }} < 1{\text{/}}2,~k \geqslant 2$, то при n → ∞ для почти всех матриц L из $\mathfrak{M}_{{mn}}^{k}$ имеет место

и длины почти всех наборов из U(L) принадлежат интервалу ϕ₂.

Доказательства теорем 1 и 2 опираются на ряд лемм, приводимых в разд. 2.

2. Доказательства теорем 1 и 2. Пусть ; $w \in W_{r}^{n}$, $w = \{ {{j}_{1}},~ \ldots ,~{{j}_{r}}\} $. Матрица $L = ({{a}_{{ij}}}),\,\,i = \overline {1,~m} ,j = \overline {1,~n} ,L \in \mathfrak{M}_{{mn}}^{k}$, называется $({v},{{\sigma }},w)$-матрицей, если ${{a}_{{{{i}_{t}}{{j}_{t}}}}}$ = σ_t при $t = \overline {1,r} $. Обозначим через ${{N}_{{({v},{{\sigma }},w)}}}$ совокупность $({v},{{\sigma }},w)$ -матриц в $\mathfrak{M}_{{mn}}^{k}$, через $N_{{({v},{{\sigma }},w)}}^{*}$ – совокупность всех матриц L в ${{N}_{{({v},{{\sigma }},w)}}}$, таких, что $L \notin {{N}_{{({{{v}}_{1}},{{\sigma }},w)}}}$ при ${{{v}}_{1}} \in V_{r}^{m},{{{v}}_{1}} \ne {v}$.

Лемма 1. Если , то

Доказательство. Оценим, сколькими способами можно построить матрицу L из ${{N}_{{({v},{{\sigma }},w)}}}$. Однозначным образом определяются те элементы матрицы L, которые расположены на пересечении строк с номерами из ${v}$ и столбцов с номерами из w. Остальные элементы этой матрицы могут быть выбраны произвольным образом (${{k}^{{mn - {{r}^{2}}}}}$ способов). Отсюда получаем требуемую оценку. Лемма 1 доказана.

Лемма 2. Если ${v} \in V_{r}^{m},~w \in W_{r}^{n},{{\sigma }} \in E_{k}^{r}$, то

Доказательство. Оценим, сколькими способами можно построить матрицу L из $N_{{({v},{{\sigma }},w)}}^{*}$. Элементы этой матрицы, расположенные в столбцах с номерами не входящими в w, могут быть выбраны произвольным образом (${{k}^{{m\left( {n - r} \right)~}}}$ способов). Отсюда, учитывая, что строки в подматрице матрицы L, образованной столбцами с номерами из w, можно выбрать ${{({{k}^{r}} - 1)}^{{m - r}}}$ способами, получаем требуемую оценку. Лемма 2 доказана.

Лемма 3. Пусть и наборы ${{{v}}_{1}}$ и ${{{v}}_{2}}$ пересекаются по $a~\left( {a \geqslant 0} \right)$ элементам, а наборы w₁ и w₂ пересекаются по $b~\left( {b \geqslant 0} \right)$ элементам. Тогда

Доказательство леммы 3 не приводится в силу ее очевидности.

При доказательстве приводимых ниже лемм 4–6 используется выражение ${{b}_{n}}{{ \leqslant }_{n}}{{c}_{n}}$, которое означает, что ${{b}_{n}} \leqslant {{c}_{n}}$ при всех достаточно больших n.

Лемма 4. 1. Если $m \leqslant n \leqslant {{k}^{{{{m}^{\beta }}}}},\beta < 1$, то

2. Имеет место

3. Если $n \leqslant m$, то

Доказательство. Положим ${{a}_{r}} = C_{n}^{r}C_{m}^{r}{{k}^{{r - {{r}^{2}}}}}$, $q\, = \,0.~5{\text{lo}}{{{\text{g}}}_{k}}mn - 0.~5{\text{lo}}{{{\text{g}}}_{k}}{\text{log}}_{k}^{2}mn,\,\,t\, = \,{\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}n$.

1. Пусть $m \leqslant n \leqslant {{k}^{{{{m}^{\beta }}}}},\beta < 1$, и $r \leqslant {{r}_{1}} + 1$. Тогда, пользуясь тем, что $q \leqslant $ 0.5log_kmn, ${{k}^{{2q}}} = mn{\text{/log}}_{k}^{2}mn{\text{\;}}~$ и $\left( {n - q} \right){{ \geqslant }_{n}}0.5n$ при $m \leqslant n,{\text{\;}}\left( {m - q} \right){{ \geqslant }_{n}}0.5m$ при $n \leqslant {{2}^{{{{m}^{\beta }}}}}$, получаем

2. При $r \geqslant {{r}_{2}} - 1~$ получаем

3. При $n \leqslant m,{\text{\;}}r \geqslant {{r}_{3}} - 1$ получаем

Таким образом, ${{a}_{{r - 1}}} = o({{a}_{r}}),{\text{\;}}n \to \infty $, в случае 1 и ${{a}_{{r + 1}}} = o({{a}_{r}}),{\text{\;}}n \to \infty $, в каждом из случаев 2 и 3. Лемма 4 доказана.

Лемма 5. Если $m \leqslant n$ и $r,~l \leqslant {{r}_{2}}$, то имеет место

где δ(n) → 0 при n→ ∞.

Доказательство. Обозначим ${{{{\lambda }}}_{b}} = {{k}^{{lb}}}C_{n}^{r}C_{r}^{b}C_{{n - r}}^{{l - b}}{\text{/}}C_{n}^{r}C_{{n - r}}^{l}$. Так как$~$

и по условию $r,~l{{ \leqslant }_{n}}0.~5{\text{lo}}{{{\text{g}}}_{k}}mn \leqslant {\text{lo}}{{{\text{g}}}_{k}}n,\left( {r + l} \right){\text{/}}n{{ \leqslant }_{n}}$ 0.5, то

Следовательно, оцениваемая сумма не превосходит $C_{n}^{r}C_{{n - r}}^{l}(1 + {{\delta }}(n))$, где δ(n) → 0 при n→ ∞. Отсюда, пользуясь неравенством $C_{{n - r}}^{l} \leqslant C_{n}^{l}$, получаем утверждением леммы. Лемма 5 доказана.

Лемма 6. Если $m \leqslant ~{{k}^{{{{n}^{{{\beta }}}}}}},{{\beta }} < 1{\text{/}}2$, и $r,~l \leqslant $ ${{r}_{3}}$, то имеет место

где δ(n) → 0 при n → ∞.

Доказательство леммы 6 аналогично доказательству леммы 5 (в этом случае $r,{\text{\;}}l \leqslant 2{{n}^{{{\beta }}}}$ и ${{{{\lambda }}}_{b}}{{ \leqslant }_{n}}{{(8{{n}^{{2{{\beta }} - 1}}})}^{b}}$).

Будем считать $\mathfrak{M}_{{mn}}^{k} = \left\{ L \right\}$ пространством элементарных событий, в котором каждое событие L происходит с вероятностью $1{\text{/}}\left| {\mathfrak{M}_{{mn}}^{k}} \right|$. Математическое ожидание случайной величины X(L), определенной на множестве $\mathfrak{M}_{{mn}}^{k}$, будем обозначать через ${\mathbf{M}}X\left( L \right)$, дисперсию – через ${\mathbf{D}}X\left( L \right)$.

Лемма 7 [10]. Пусть для случайных величин ${{X}_{1}}\left( L \right)$ и ${{X}_{2}}\left( L \right)$_, определенных на $\mathfrak{M}_{{mn}}^{k}$_, выполнено ${{X}_{1}}\left( L \right) \geqslant {{X}_{2}}\left( L \right) \geqslant 0$ и при n → ∞ верно ${\mathbf{M}}{{X}_{1}}\left( L \right) \approx {\mathbf{M}}{{X}_{2}}\left( L \right),~{\mathbf{D}}{{X}_{2}}\left( L \right){\text{/}}{{({\mathbf{M}}{{X}_{2}}\left( L \right))}^{2}}$ → 0. Тогда для почти всех матриц L из $\mathfrak{M}_{{mn}}^{k}$ имеет место ${{X}_{1}}\left( L \right) \approx {{X}_{2}}\left( L \right) \approx {\mathbf{M}}{{X}_{2}}\left( L \right),~n \to \infty $.

Пусть ${{\sigma }} \in E_{k}^{r},{\text{\;}}w \in W_{r}^{n}$. На $\mathfrak{M}_{{mn}}^{k} = \left\{ L \right\}$ рассмотрим случайную величину ${{\zeta }_{{({{\sigma }},w)}}}(L),$ равную 1, если w – ${{\sigma }}$-допустимый набор для матрицы L, и равную 0 в противном случае. Положим

Нетрудно видеть, что ${{{{\mu }}}_{r}}\left( L \right) = \left| {{{U}_{r}}\left( L \right)} \right|$ (число наборов в U(L) длины r, ${{\zeta }}\left( L \right) = $ $\left| {U\left( L \right)} \right|$ и ${{\zeta }_{i}}(L),i \in \{ 1,~2\} $, – число тех наборов в U(L), длины которых принадлежат интервалу ϕ_i.

Оценим вероятность события , обозначаемую далее через $P({{\zeta }_{{({{\sigma }},w)}}}(L)\, = \,1)$. Очевидно, в силу леммы 1

С другой стороны, в силу леммы 2 имеем

Из (2.1), а также леммы 4 сразу вытекает следующая лемма.

Лемма 8. Если $m \leqslant n \leqslant ~{{k}^{{{{m}^{{{\beta }}}}}}},{{\beta }} < 1$, то имеет место

Лемма 9. Если ${{m}^{a}} \leqslant n,a > 1$, то

Доказательство. Имеем

Так как $m{{k}^{{ - {{r}_{1}}}}} \to 0,{\text{\;}}n \to \infty $, то ${{(1 - {{k}^{{ - {{r}_{1}}}}})}^{{m - {{r}_{1}}}}} \to 1,{\text{\;}}n \to \infty $. Откуда, пользуясь (2.2), получаем

Лемма 9 доказана.

Из лемм 8 и 9 сразу вытекает следующая лемма.

Лемма10. Если , то

Доказательства представленных ниже лемм 11–13 не приводятся, поскольку они полностью аналогичны доказательству леммы 10.

Лемма11. Если ${{m}^{a}} \leqslant n,a > 1$, то имеет место

Лемма12. Если $n \leqslant m$, то

Лемма13. Если ${{m}^{a}} \leqslant n \leqslant {{k}^{{{{m}^{{{\beta }}}}}}},a > 1,{{\beta }} < 1$, то

Лемма14. Если ${{m}^{a}} \leqslant n \leqslant {{k}^{{{{m}^{{{\beta }}}}}}},a > 1,\beta < 1$, то имеет место

Доказательство. Имеем

Нетрудно видеть, что

где $N = {{N}_{{\left( {{{{v}}_{1}},{{\sigma ;}},{{w}_{1}}} \right)}}} \cap {{N}_{{\left( {{{{v}}_{2}},{{\sigma ''}},~{{w}_{2}}} \right)}}}$. Отсюда, пользуясь леммами 3 и 5, получаем где ${{\delta }}(n) \to 0$ при n → ∞.

С другой стороны, в силу леммы 13

Из (2.3)–(2.5) следует утверждение доказываемой леммы. Лемма 14 доказана.

Аналогично лемме 14 доказываются приводимые ниже леммы 15–17.

Лемма 15. Если ${{m}^{a}} \leqslant n \leqslant {{k}^{{{{m}^{\beta }}}}},\,\,a > 1,\,\,{{\beta }} < 1$, то

Лемма16. Если ${{m}^{a}} \leqslant n,\,\,a > 1$, то

Лемма17. Если $n \leqslant m$, то

Пусть ${v} \in V_{r}^{m},~{{\sigma }} \in E_{k}^{r},w \in W_{r}^{n}$. На $\mathfrak{M}_{{mn}}^{k} = \left\{ L \right\}$ рассмотрим случайную величину ${{{{\xi }}}_{{\left( {{v},{{\sigma }},w} \right)}}}(L),~$ равную 1, если $L \in {{N}_{{\left( {{v},{{\sigma }},w} \right)}}}$, и равную 0 в противном случае. Положим

Лемма 18. Если $n \leqslant m \leqslant ~{{k}^{{{{n}^{{{\beta }}}}}}},\,\,{{\beta }} < 1{\text{/}}2$, то при n → ∞ для почти всех матриц L из $\mathfrak{M}_{{mn}}^{k}$ имеет место

Доказательство. Оценим вероятность события, ${{{{\xi }}}_{{\left( {{v},{{\sigma }},w} \right)}}}(L) = 1,{v} \in V_{r}^{m},{{\sigma }} \in E_{k}^{r},w \in W_{r}^{n}$, обозначаемую далее через $P({{{{\xi }}}_{{\left( {{v},{{\sigma }},w} \right)}}}\left( L \right) = 1)$. В силу леммы 1

Следовательно, согласно лемме 4,

Из (2.6) и леммы 6, используя схему доказательства леммы 14, получаем

Из (2.6), (2.7) и леммы 7 следует утверждение доказываемой леммы. Лемма 18 доказана.

Утверждения теоремы 1 следуют непосредственно из лемм 7, 10, 11, 13, 14–16, а утверждения теоремы 2 следуют непосредственно из лемм 7, 12, 17, 18 и неравенства .

3. Оценки типичных значений числа минимальных нечастых ЭФ и длины минимального нечастого ЭФ. Положим $L \in \mathfrak{M}_{{mn}}^{k},L = ({{a}_{{ij}}}),\,\,i = 1,~ \ldots ,~m,{\text{\;}}j = 1,~ \ldots ,~n$; ${{\sigma }} \in E_{k}^{r},{{\sigma }} = \left( {{{{{\sigma }}}_{1}},~ \ldots ,{{{{\sigma }}}_{r}}} \right);w \in W_{r}^{n}$, w = {j₁, ..., j_r}.

Набор w называется σ-покрытием матрицы L длины r, если для любого $i \in \left\{ {1,2, \ldots ,~m} \right\}$ найдется $j \in \left\{ {{{j}_{1}},~ \ldots ,~{{j}_{r}}} \right\}$, такое, что ${{a}_{{ij}}} \ne {{\sigma }_{j}}$. Будем говорить, что σ-покрытие w порождается набором σ.

Набор w, являющийся σ-покрытием матрицы L, называется тупиковым, если при любом $~t \in \left\{ {1,~2, \ldots ,{\text{\;}}r} \right\}$ набор $w{{\backslash }}\{ {{j}_{t}}\} $ не является ${{{{\gamma }}}_{t}}$-покрытием матрицы L, где ${{{{\gamma }}}_{t}} = \left( {{{{{\sigma }}}_{1}},~ \ldots ,~{{{{\sigma }}}_{{t - 1}}},~{{{{\sigma }}}_{{t + 1}}},~ \ldots ,~{{{{\sigma }}}_{r}}~} \right)$. Если w – тупиковое σ-покрытие матрицы L, то нетрудно видеть, что столбцы матрицы L с номерами из w содержат подматрицу, имеющую с точностью до перестановки строк вид

где ${{{{\beta }}}_{p}} \ne {{\sigma }_{p}}$ при $p = 1,~2, \ldots ,~r.~$ Такая подматрица называется σ-подматрицей.

Отметим, что в случае, когда в качестве строк матрицы L берутся описания объектов из выборки D, то набор $w \in W_{r}^{n},{\text{\;}}w = \left\{ {{{j}_{1}},~ \ldots ,~{{j}_{r}}} \right\}$, является тупиковым σ-покрытием матрицы L тогда и только тогда, когда ЭФ $\left( {{{\sigma }},~H} \right),{\text{\;}}H = \left\{ {{{x}_{{{{j}_{1}}}}}, \ldots ,~{{x}_{{{{j}_{r}}}}}} \right\}$ – минимальный нечастый в D.

Введем обозначения: , – множество всех тупиковых σ-покрытий матрицы , – множество всех σ-подматриц матрицы L; B_r(L, σ), $L \in \mathfrak{M}_{{mn}}^{k},{{\sigma }} \in E_{k}^{r}$, – множество всех наборов в длины , – множество всех подматриц в $S\left( {L,~\sigma } \right)$ порядка $r;{\text{\;}}B\left( L \right),{\text{\;}}L \in \mathfrak{M}_{{mn}}^{k}$, – совокупность всех тупиковых σ-покрытий матрицы L, в которой каждое покрытие встречается столько раз, сколькими наборами из $E_{k}^{r}$ оно порождается; $S\left( L \right),{\text{\;}}L \in \mathfrak{M}_{{mn}}^{k}$, – совокупность всех σ-подматриц матрицы L для всех σ из $E_{k}^{r}$;

${{r}_{3}} = \left] {{\text{lo}}{{{\text{g}}}_{k}}m + {\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}m} \right[;{\text{\;}}{{\phi }_{2}}$ – интервал [1, r₃]; ${{r}_{4}} = \left[ {0.~5{\text{lo}}{{{\text{g}}}_{k}}mn - 0.~5{\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}mn - {\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}n} \right]$; ${{r}_{5}} = \left] {0.~5{\text{lo}}{{{\text{g}}}_{k}}mn - 0.~5{\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}mn + {\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}n} \right[$; ϕ₃ – интервал [r₄, r₅]; r₆ = [log_km + log_klog_km + + ${\text{lo}}{{{\text{g}}}_{k}}{\text{lo}}{{{\text{g}}}_{k}}~{\text{lo}}{{{\text{g}}}_{k}}n[$; ϕ₄ – интервал [1, r₆].

Теорема 3 [3]. Если ${{m}^{a}} \leqslant n \leqslant {{k}^{m}},a > 1,{\text{\;}}k \geqslant 2$, то при n → ∞ для почти всех матриц L из $\mathfrak{M}_{{mn}}^{k}$ имеет место

и длины почти всех наборов из B(L) принадлежат интервалу ϕ₃.

Теорема 4. Если $n \leqslant m \leqslant {{k}^{{{{n}^{{{\beta }}}}}}},{{\beta }} < 1{\text{/}}2,k \geqslant 2$, то при n → ∞ для почти всех матриц L из $\mathfrak{M}_{{mn}}^{k}$ имеет место

и длины почти всех наборов из B(L) принадлежат интервалу ϕ₄.

Схема доказательства теоремы 4 аналогична схеме доказательства теоремы 2.

Таким образом, в каждом из двух рассмотренных случаев почти всегда типичная длина набора из U(L) и типичная длина набора из B(L) принадлежат одному интервалу. Результаты теорем 1, 3 и теорем 2, 4 проиллюстрированы ниже соответственно на рис. 1, 2.

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

Результаты проведенного в работе исследования важны и для ряда других прикладных областей, среди которых следует выделить нахождение в данных ассоциативных правил. В этом случае D называют базой данных, а каждый объект базы D – транзакцией. Ассоциативное правило устанавливает зависимость между двумя частыми ЭФ, согласно которой один частый ЭФ (посылка) с некоторой “достоверностью” влечет другой частый ЭФ (следствие). При этом посылка и следствие порождаются одним общим частым ЭФ. Вопросы синтеза ассоциативных правил возникли в связи с анализом потребительской корзины [11].