Труды КНЦ (Технические науки вып. 7/2023(14))

Труды Кольского научного центра РАН. Серия: Технические науки. 2023. Т. 14, № 7. С. 16-25. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2023. Vol. 14, No. 7. P. 16-25. • Еще одним широко распространенным ограничением является ограничение на пропуски. Последовательный паттерн с ограничением на пропуски Cgap = [M, N], обозначается p[M, N], это такой паттерн, что как минимум M элементов и как максимум N элементов могут находиться между каждыми двумя соседними элементами исходной последовательности. Вернемся к Примеру 2: пусть p[0, 2] = (c a) и p[1, 2] = (c a), это два паттерна с двумя разными ограничениями на пропуски, и рассмотрим последовательности табл. 2. Последовательности 1 и 4 поддерживают паттерн p [1, 2] (последовательность 1 содержит один элемент между ( с ) и ( а ), в то время как последовательность 4 не содержит элементов между (с) и (а)). Но только последовательность 1 поддерживает p[1, 2] (только последовательности с одним или двумя элементами между ( с ) и ( а ) поддерживают этот паттерн). • Ограничение, описываемое с помощью регулярных выражений CRE — это ограничение, определенное как регулярное выражение на множестве элементов. Последовательный паттерн удовлетворяет C re тогда и только тогда, когда он распознается некоторым детерминированным конечным автоматом [18]. Например, два последовательных паттерна (a b c ) и (a d c ) из табл. 2 Примера 2 удовлетворяют ограничению регулярное выражение C re = a*{bb\bc\dc}. • Ограничение на супер-паттерн находит паттерны, которые содержат определенную пользователем последовательность. • Ограничение на временной интервал. База данных транзакций содержит информацию о временных метках напротив меток событий. Ограничение на временной интервал или на продолжительность — это множество последовательностей со свойством, обозначающим, что временной интервал между первой и последней транзакцией меньше или больше определенного значения Cdur = D u r( а )@А , где &6 {<, >} и At — это заданные целые значения. Длина последовательного паттерна зависит от выбора исследуемого временного интервала. Пусть в T 6 At , ts — начальное время, а te — конечное время для изучения паттернов транзакции. Тогда интервал времени/события для изучения паттернов задается как: ts-te для данной информационной системы S. Если сгруппировать информацию о транзакции 1 с At , соответствующую одному x, то получим альтернативное представление информационной системы S . Если наложить ограничение на временной интервал, то получим базу данных последовательностей с ограничением на временной интервал. Максимальную длину можно контролировать соответствующей настройкой ограничения на временной интервал. • Совокупное ограничение — это ограничение на совокупность элементов в паттерне, где функция агрегации может быть суммой, средним, максимумом, минимумом, среднеквадратичным отклонением, и т. д. Например, в случае с анализом потребительской корзины покупателя могут интересовать товары, сумма в чеке за которые превышает некоторое заданное значение. Естественным выводом из частых паттернов являются ассоциативные правила, выражающие ассоциацию между двумя паттернами. Ассоциативным правилом называется импликация X * Y, где X с I, Y с I и X П Y = 0 . Правило X * Y имеет поддержку s, если s процентов транзакций из D содержат X u Y, supp(X * Y) = supp(X u Y). Достоверность правила показывает вероятность того, что из X следует Y. Правило X ^ Y справедливо с достоверностью c, если c процентов транзакций из D, содержащих X, conf (X * Y ) . Ш Щ и і также содержат suPP(X ) . Иными словами, требуется выявить зависимость: если в транзакции присутствует паттерн X , то на основании этого можно сделать вывод, что паттерн Y также должен присутствовать в данной транзакции. Выбор значений минимальной поддержки и минимальной достоверности имеет большое значение. При очень высокой поддержке алгоритм будет выявлять правила, которые являются слишком очевидными, чтобы на их основе проводить анализ. С другой стороны, очень маленькая поддержка может привести к выявлению слишком большого числа правил, которые могут оказаться статистически необоснованными, что потребует много вычислительных ресурсов. Несмотря на это, наиболее интересные и неожиданные правила зачастую можно выявить именно при низкой поддержке. © Зуенко А. А., Зуенко О. Н., 2023 22