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

Берчун Ю.В.1
1 Московский государственный технический университет имени Н.Э. Баумана; Институт машиноведения им. А.А. Благонравова РАН

Статья в журнале

Экономика высокотехнологичных производств
Том 1, Номер 2 (Апрель-июнь 2020)

Цитировать:
Берчун Ю.В. Поиск устойчивых шаблонов в многомерных данных в системах интегрированной логистической поддержки // Экономика высокотехнологичных производств. – 2020. – Том 1. – № 2. – С. 91-100. – doi: 10.18334/evp.1.2.110969.

Эта статья проиндексирована РИНЦ, см. https://elibrary.ru/item.asp?id=44198490

Аннотация:
Констатируется тренд на развитие аналитических функций информационных систем. Показывается актуальность решения задач анализа данных в системах интегрированной логистической поддержки. Рассматривается актуальность задачи обнаружения устойчивых шаблонов с учётом кратности, которая является более общей, чем известная задача поиска шаблонов, используемая в алгоритмах обучения ассоциативных правил. Выполнена формализация постановки указанной задачи в терминах теории множеств. Предложены принципы её решения, основанные на итерационном включении ранее обнаруженных шаблонов в множество объектов и перерасчёте числа вхождений объектов в транзакции. Возможности вычислительной оптимизации предложенного метода проиллюстрированы с использованием модели в терминах теории графов, основанная на анализе связности. Сформулированы основные особенности предложенного алгоритма и перспективные задачи по развитию метода.

Ключевые слова: анализ данных, машинное обучение, часто встречающиеся шаблоны



Введение

Одним из глобальных трендов в развитии информационных технологий является развитие аналитических функций информационных систем. Качественное изменение структуры и параметров бизнес-процессов на основе технологий интеллектуального анализа данных является необходимым фактором построения цифровой экономики. Актуальность применения методов машинного обучения обуславливается потребностями бизнеса в поддержке принятия решений и обеспечивается большими объемами накапливаемых в информационных системах данных (в том числе за счет технологий «Интернета вещей»), ростом производительности вычислений, развитием технологии распределенной обработки информации и математических методов интеллектуального анализа данных [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 = {i1, i2, …,in} атрибутов (характеристик, измерений). Название I – от англ. itemset, таким образом, каждый элемент этого множества – item. Например, для прикладной области складской логистики – это множество типов хранимых объектов (единиц складского учета), которые обычно обозначаются аббревиатурой SKU (Store Keeping Unit).

Существует множество DB = {t1, t2, …, tm} транзакций (DB – от англ. database, t – от англ. transaction), каждая из которых характеризуется n-мерным вектором натуральных чисел Ci = {ci1, ci2,…, cin} (c – от англ. count), компоненты которого соответствуют числу объектов (компонент) того или иного типа в рамках транзакции.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RXY = f(SiÎ [1;m]count(ti,X,Y), SiÎ [1;m]count(ti,X), SiÎ [1;m]count(ti,Y), |tÎDB; XÍ t, YÍ t|, |tÎDB; YÍ t|, |tÎDB; XÍ t|, total),

где total=SitemÎISiÎ [1;m]count(ti,item).

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

RXY =SiÎ [1;m]count(ti,X,Y) / min (SiÎ [1;m]count(ti,X), SiÎ [1;m]count(ti,Y)).

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Источники:

1. Конопатов С.Н., Старожук Е.А., Бышовец Б.Д. Подготовка кадров для цифровой экономики // Преподавание информационных технологий в Российской Федерации: Материалы XVII открытой Всероссийской конференции. Новосибирск, 2019. – c. 112-116.
2. Синицын И.Н., Шаламов А.С. Лекции по теории систем интегрированной логистической поддержки. - М.: Торус-Пресс, 2019. – 1072 c.
3. Норенков И.П., Кузьмик П.К. Информационная поддержка наукоёмких изделий. CALS-технологии. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. – 320 c.
4. Омельченко И.Н., Бром А.Е., Ляхович Д.Г., Александров А.А., Водчиц А.С. Информационно-аналитическое обеспечение системы логистической поддержки жизненного цикла продукции предприятия машиностроения // Системы управления полным жизненным циклом высокотехнологичной продукции в машиностроении: новые источники роста: Материалы II Всероссийской научно-практической конференции. М., 2019. – c. 151-154.
5. Геворгян Р.М., Мартынов Л.М., Старожук Е.А. Технологии систем управления полным жизненным циклом высокотехнологичной продукции // Системы управления полным жизненным циклом высокотехнологичной продукции в машиностроении: новые источники роста: Материалы II Всероссийской научно-практической конференции. М., 2019. – c. 43-50.
6. Миротин Л.Б., Омельченко И.Н. Инженерная логистика: логистически-ориентированное управление жизненным циклом продукции. - М.: Горячая линия–Телеком, 2015. – 644 c.
7. Носко А.Л., Сафронов Е.В. Имитационное моделирование для оценки процесса комплектации с использованием автоматизированных систем хранения // Логистика. – 2014. – № 3(88). – c. 45-47.
8. Захаров М.Н., Омельченко И.Н., Саркисов А.С. Ситуации инженерно-экономического анализа. / Монография. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 432 c.
9. Симчера В.М. Методы многомерного анализа статистических данных. - М.: Финансы и статистика, 2008. – 400 c.
10. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2016. – 448 c.
11. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Технологии анализа данных Data Mining, Visual Mining, Text Mining, OLAP. / 2-е изд., перераб. и доп. - СПб.: БХВ-Петербург, 2007. – 384 c.
12. Agrawal Rakesh, Srikant Ramakrishnan Fast algorithms for mining association rules in large databases // Very Large Data Bases (VLDB): Proceedings of the 20th International Conference. Santiago, Chile, 1994. – p. 487-499.
13. Zaki M.J.,Parthasarathy S., Ogihara M., Li W. New Algorithms for Fast Discovery of Association Rules // Knowledge Discovery and Data Mining: Proceedings of the 3rd International Conference. 1997. – p. 283-286.
14. Jiawei Han, Jian Pei, Yiwen Yin Mining Frequent Patterns Without Candidate Generation // Proceedings of the ACM SIGMOD: international Conference on Management. 2000. – p. 1-12.

Страница обновлена: 16.11.2020 в 11:57:52