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

Введение

Одним из глобальных трендов в развитии информационных технологий является развитие аналитических функций информационных систем. Качественное изменение структуры и параметров бизнес-процессов на основе технологий интеллектуального анализа данных является необходимым фактором построения цифровой экономики. Актуальность применения методов машинного обучения обуславливается потребностями бизнеса в поддержке принятия решений и обеспечивается большими объемами накапливаемых в информационных системах данных (в том числе за счет технологий «Интернета вещей»), ростом производительности вычислений, развитием технологии распределенной обработки информации и математических методов интеллектуального анализа данных [1] (Konopatov, Starozhuk, Byshovets, 2019).

Тренд на развитие аналитических функций актуален и для систем непрерывной информационной поддержки поставок и жизненного цикла изделий [2–5] (Sinitsyn, Shalamov, 2019; Norenkov, Kuzmik, 2002; Omelchenko, Brom, Lyakhovich, Aleksandrov, Vodchits, 2019; Gevorgyan, Martynov, Starozhuk, 2019). В частности, технологии компьютерного моделирования и машинного обучения все шире применяются в распределительной логистике [6] (Mirotin, Omelchenko, 2015), интралогистике [7] (Nosko, Safronov, 2014), а также в других задачах инженерно-экономического анализа на всех стадиях жизненного цикла продукции [8] (Zakharov, Omelchenko, Sarkisov, 2014).

Одной из прикладных задач, возникающих в рамках реализации концепции интегрированной логистической поддержки, является задача обнаружения устойчивых (часто встречающихся) сочетаний компонентов транзакций на основе статистики, накапливаемой в базах данных. Одним из подходов к решению таких задач является применение методов факторного анализа [9] (Simchera, 2008). Однако все эти методы искажают дискретную природу исходных данных. В то же время известно, что ограничение дискретности при решении многих классов задач способно резко усложнить их решение, в том числе переводя их в класс NP-полных [10] (Karpenko, 2016).

Среди типовых задач интеллектуального анализа данных известна типовая задача обучения ассоциативных правил [11] (Barsegyan, Kupriyanov, Stepanenko, Kholod, 2007). Наиболее известными методами ее решения являются Apriori [12] (Agrawal Rakesh, Srikant Ramakrishnan, 1994), ECLAT (Equivalence Class Transformation, кластеризация классов эквивалентности) [13] (Zaki, Parthasarathy, Ogihara, Li, 1997), FP-growth (Frequent Pattern-Growth, «выращивание популярных (часто встречающихся) предметных наборов») [14] (Jiawei Han, Jian Pei, Yiwen Yin, 2000). Одним из этапов решения во всех указанных алгоритмах является поиск часто встречающихся сочетаний (шаблонов). Однако в данном случае задача сводится не к дискретной, а к булевой. А например, для прикладных задач интралогистики для принятия решений является выявление устойчивых (часто встречающихся) количественных соотношений между компонентами транзакции.

Таким образом, появляется класс задач, постановка которых отличается от известных. Поэтому проведем формальное математическое описание указанной задачи.

Постановка задачи

Существует множество I = {i₁, i₂, …,i_n} атрибутов (характеристик, измерений). Название I – от англ. itemset, таким образом, каждый элемент этого множества – item. Например, для прикладной области складской логистики – это множество типов хранимых объектов (единиц складского учета), которые обычно обозначаются аббревиатурой SKU (Store Keeping Unit).

Существует множество DB = {t₁, t₂, …, t_m} транзакций (DB – от англ. database, t – от англ. transaction), каждая из которых характеризуется n-мерным вектором натуральных чисел C_i = {c_i1, c_i2,…, c_in} (c – от англ. count), компоненты которого соответствуют числу объектов (компонент) того или иного типа в рамках транзакции.

Требуется выявить подмножества объектов PÌI, которые достаточно устойчиво (очевидно, для этого потребуется ввести меру, по сути, определяющую признак окончания итераций алгоритма) встречаются в транзакциях из множества DB в одних и тех же пропорциях. Искомые подмножества в задачах обучения ассоциативных правил называют шаблонами (P – от англ. pattern). В рамках данной задачи каждому компоненту шаблона также ставится в соответствие и кратность его вхождения.

Следует сделать ряд замечаний:

1. Векторы типа С являются разреженными. Число ненулевых элементов в них как минимум на порядок меньше n. Например, для задач складской логистики число ненулевых элементов оценивается величиной порядка 10¹, в то время как n представляет собой величину порядка 10³-10⁴, а в некоторых случаях и больше.

2. Векторы типа C являются векторами натуральных чисел (т.е. CÎNⁿ), в то время как в типовой задаче обучения ассоциативных правил аналогичные векторы носят логический (бинарный) характер (т.е. CÎBⁿ).

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

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

Исходные данные для задач поиска ассоциативных правил часто также представляются в виде множества транзакций с учетом числа единиц каждого типа объектов. Но затем задача упрощается за счет приведения всех коэффициентов к бинарному виду.

Основные принципы метода решения

Сформулируем базовый алгоритм решения задачи.

Для доступа к компонентам вектора C_i, соответствующего транзакции t_i и объекту itemÎ I, будем использовать функцию count(t_i, item).

Для упрощения записи будем cчитать выражение (itemÍ t_i) равным 1, если в транзакции t_i встречается хотя бы 1 один объект item, и 0 в противном случае.

1. Сгенерируем возможные пары (на данном этапе можно полагать, что речь идет обо всех возможных парах, но в дальнейшем следует отказываться от заведомо неперспективных вариантов) объектов (или ранее сформированных подмножеств) из множества I. Обозначим компоненты пары как XÌI и YÌI, при этом XÇY=Æ.

2. Для каждой транзакции посчитаем число пар X и Y, которые в нее входят: count(t_i, X, Y) = min [count(t_i,X), count(t_i,Y)]

3. Для каждой пары X и Y рассчитаем коэффициент ранжирования. В общем случае он представляет собой функцию:

R_XY = f(S_{iÎ [1;m]}count(t_i,X,Y), S_{iÎ [1;m]}count(t_i,X), S_{iÎ [1;m]}count(t_i,Y), |tÎDB; XÍ t, YÍ t|, |tÎDB; YÍ t|, |tÎDB; XÍ t|, total),

где total=S_itemÎIS_{iÎ [1;m]}count(t_i,item).

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

R_XY =S_{iÎ [1;m]}count(t_i,X,Y) / min (S_{iÎ [1;m]}count(t_i,X), S_{iÎ [1;m]}count(t_i,Y)).

При этом устанавливается порог для знаменателя – если он слишком мал по сравнению с total (связь через коэффициент, являющийся параметром метода), то R_XY принимается равным 0.

4. Если максимальный коэффициент ранжирования меньше порогового значения threshold (является параметром метода), то итерации алгоритма завершаются.

В противном случае пару X и Y (имеющую наибольший индекс ранжирования) удобно рассматривать как новый объект («комплексный», «виртуальный») в составе множества I. При этом корректируются численности объектов X и Y в каждой транзакции на величину, равную count(t_i, X, Y). После чего возвращаемся к шагу 1.

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

Вычислительные затраты в основном определяются числом просматриваемых пар X и Y. Можно исключить из рассмотрения все объекты item, для которых S_{iÎ [1;m]}count(t_i,item)<threshold.

Оставшиеся объекты упорядочиваются в порядке уменьшения их суммарного вхождения S_{iÎ [1;m]}count(t_i,item).

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

При проведении коррекций, описанных в п.4 базового алгоритма, увеличивается число нулей в таблице транзактов. Используем этот факт для декомпозиции задачи.

Построим граф, вершинами которого являются объекты itemÎI. Ребрами свяжем те вершины, которые соответствуют объектам, встречающимся в одной транзакции. По мере увеличения числа нулей в таблице транзактов число ребер в графе сокращается. Это может привести к распаду графа на несколько подграфов, каждый из которых можно дальше обрабатывать независимо. Это создает предпосылки для распараллеливания алгоритма.

Однако распараллеливание наиболее интересно не на поздних, а на, возможно, более ранних итерациях алгоритма. В этой связи каждой вершине исходного графа припишем вес, вычисляемый как S_{iÎ [1;m]}count(t_i,item). После этого исключим из рассмотрения те вершины, имеющие малый удельный вес (возможен адаптивный подбор). Вместе с вершинами исчезнут и инцидентные им ребра графа. Это также ведет к распаду графа на несколько независимых подграфов.

Заключение

Предложенные принципы метода решения позволяют сформулировать основные особенности алгоритма:

· найденные на каждой итерации шаблоны расширяют множество объектов на следующих итерациях;

· число столбцов таблицы транзакций (вершин графа) увеличивается на каждой итерации;

· при заполнении ячейки в новом столбце в соответствующей строке образуется по крайней мере один ноль;

· разреженность таблицы транзакций на каждой итерации увеличивается;

· промежуточные шаблоны формируются как пара объектов, каждый из которых может быть составным (т.е. ранее найденным шаблоном);

· один и тот же исходный объект может входить в оба элемента пары, что приводит к его кратному включению в новый шаблон.

К числу перспективных задач по развитию метода можно отнести следующие:

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

· партиционирование данных для распределенной обработки;

· применение ранжирования для сокращения числа рассчитываемых уровней поддержки на каждой итерации;

· анализ причин возникновения коллизий при принятии решений;

· уточнение расчета уровня поддержки в случае, когда одна транзакция включает несколько шаблонов;

· применение дополнительных метрик для разрешения коллизий.