Multidimensional data frequent patterns discovery in CALS-systems

Berchun Yu.V.1,2
1 Московский государственный технический университет имени Н.Э. Баумана
2 Институт машиноведения им. А.А. Благонравова РАН

Journal paper

High-tech Enterprises Economy (РИНЦ, ВАК)
опубликовать статью | оформить подписку

Volume 1, Number 2 (April-June 2020)

Citation:

Indexed in Russian Science Citation Index: https://elibrary.ru/item.asp?id=44198490

Abstract:
There is a trend towards the development of analytical functions of information systems. The relevance of solving data analysis problems in integrated logistics support systems is shown. The authors consider the relevance of the problem of detecting stable patterns taking into account multiplicity, which is more general than the well-known problem of finding patterns used in algorithms for learning associative rules. The formalization of the problem statement in terms of set theory is performed. The principles of its solution based on iterative inclusion of previously discovered patterns in a set of objects and recalculation of the number of occurrences of objects in transactions are proposed. The possibilities of computational optimization of the proposed method are illustrated using a model in terms of graph theory based on connectivity analysis. The main features of the proposed algorithm and promising tasks for the development of the method are formulated.

Keywords: data analysis, machine learning, common patterns



Введение

Одним из глобальных трендов в развитии информационных технологий является развитие аналитических функций информационных систем. Качественное изменение структуры и параметров бизнес-процессов на основе технологий интеллектуального анализа данных является необходимым фактором построения цифровой экономики. Актуальность применения методов машинного обучения обуславливается потребностями бизнеса в поддержке принятия решений и обеспечивается большими объемами накапливаемых в информационных системах данных (в том числе за счет технологий «Интернета вещей»), ростом производительности вычислений, развитием технологии распределенной обработки информации и математических методов интеллектуального анализа данных [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). После этого исключим из рассмотрения те вершины, имеющие малый удельный вес (возможен адаптивный подбор). Вместе с вершинами исчезнут и инцидентные им ребра графа. Это также ведет к распаду графа на несколько независимых подграфов.

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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


References:

Agrawal Rakesh, Srikant Ramakrishnan (1994). Fast algorithms for mining association rules in large databases Very Large Data Bases (VLDB). 487-499.

Barsegyan A.A., Kupriyanov M.S., Stepanenko V.V., Kholod I.I. (2007). Tekhnologii analiza dannyh Data Mining, Visual Mining, Text Mining, OLAP [Data Mining, Visual Mining, Text Mining, OLAP technologies for data analysis] SPb.: BKhV-Peterburg. (in Russian).

Gevorgyan R.M., Martynov L.M., Starozhuk E.A. (2019). Tekhnologii sistem upravleniya polnym zhiznennym tsiklom vysokotekhnologichnoy produktsii [Technology systems for managing the entire life cycle of high-tech] Full life cycle management systems for high-tech products in mechanical engineering: new sources of growth. 43-50. (in Russian).

Jiawei Han, Jian Pei, Yiwen Yin (2000). Mining Frequent Patterns Without Candidate Generation Proceedings of the ACM SIGMOD. 1-12.

Karpenko A.P. (2016). Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy [Modern search engine optimization algorithms. Nature-inspired algorithms] M.: Izd-vo MGTU im. N.E. Baumana. (in Russian).

Konopatov S.N., Starozhuk E.A., Byshovets B.D. (2019). Podgotovka kadrov dlya tsifrovoy ekonomiki [Training for the digital economy] Teaching information technology in the Russian Federation. 112-116. (in Russian).

Mirotin L.B., Omelchenko I.N. (2015). Inzhenernaya logistika: logisticheski-orientirovannoe upravlenie zhiznennym tsiklom produktsii [Engineering logistics: logistics-oriented product lifecycle management] M.: Goryachaya liniya–Telekom. (in Russian).

Norenkov I.P., Kuzmik P.K. (2002). Informatsionnaya podderzhka naukoyomkikh izdeliy. CALS-tekhnologii [Information support for high-tech products. CALs technologies] M.: Izd-vo MGTU im. N.E. Baumana. (in Russian).

Nosko A.L., Safronov E.V. (2014). Imitatsionnoe modelirovanie dlya otsenki protsessa komplektatsii s ispolzovaniem avtomatizirovannyh sistem khraneniya [Simulation modelling to assess the kitting process using automated storage systems]. Logostics. (3(88)). 45-47. (in Russian).

Omelchenko I.N., Brom A.E., Lyakhovich D.G., Aleksandrov A.A., Vodchits A.S. (2019). Informatsionno-analiticheskoe obespechenie sistemy logisticheskoy podderzhki zhiznennogo tsikla produktsii predpriyatiya mashinostroeniya [Information and analytical support of the logistics support system for the life cycle of the mechanical engineering enterprise products] Full life cycle management systems for high-tech products in mechanical engineering: new sources of growth. 151-154. (in Russian).

Simchera V.M. (2008). Metody mnogomernogo analiza statisticheskikh dannyh [Methods of multidimensional analysis of statistical data] M.: Finansy i statistika. (in Russian).

Sinitsyn I.N., Shalamov A.S. (2019). Lektsii po teorii sistem integrirovannoy logisticheskoy podderzhki [Lectures on the theory of integrated logistics support systems] M.: Torus-Press. (in Russian).

Zakharov M.N., Omelchenko I.N., Sarkisov A.S. (2014). Situatsii inzhenerno-ekonomicheskogo analiza [Situations of engineering and economic analysis] M.: Izd-vo MGTU im. N.E. Baumana. (in Russian).

Zaki M.J.,Parthasarathy S., Ogihara M., Li W. (1997). New Algorithms for Fast Discovery of Association Rules Knowledge Discovery and Data Mining. 283-286.

Страница обновлена: 29.04.2025 в 05:22:57