Mining serial positioning episode rules by natural exponent inertia weight based swallow swarm optimization algorithm with constraint based event sequences

Abstract

The Frequent Episode Mining (FEM) is a challenging framework to identify frequent episodes from a sequence database. In a sequence, an ordered collection of events defines an episode, and frequent episodes are only considered by the earlier studies. Also, it doesn’t support for the serial based episode rule mining. In this work, the episode rules are mined with precise and serial based rule mining considering the temporal factor, so that, the occurrence time of the consequent is specified in contrast to the traditional episode rule mining. The proposed work has a larger number of candidates and specific time constraints to generate the fixed-gap episodes, and mining such episodes from whole sequence where the time span between any two events is a constant which is utilized to improve the proposed framework’s performance. In order to improve the efficiency, an Optimal Fixed-gap Episode Occurrence (OFEO) is performed using the Natural Exponent Inertia Weight based Swallow Swarm Optimization (NEIWSSO) algorithm. The temporal constraints significantly evaluate the effectiveness of episode mining, and a noticeable advantage of the present work is to generate optimal fixed-gap episodes for better prediction. The effective use of memory consumption and performance enhancement is achieved by developing new trie-based data structure for Mining Serial Positioning Episode Rules (MSPER) using a pruning method. The position of frequent events is updated in the precise-positioning episode rule trie instead of frequent events to reduce the memory space. The benchmark datasets Retail, Kosarak, and MSNBC is used to evaluate the proposed algorithm’s efficiency. Eventually, it is found that it outperforms the existing techniques with respect to memory consumption and execution time. On an average, the proposed algorithm achieves 28 times lesser execution time and consumes 45.5% less memory space for the highest minimum support value on the Retail dataset compared to existing methods.

Keywords

Frequent episode mining fixed-gap episode occurrence natural exponent inertia weight support of fixed-gap episode

Get full access to this article

View all access options for this article.

References

Mannila

, Toivonen

and Inkeri Verkamo

, Discovery of frequent episodes in event sequences, Data Mining and Knowledge Discovery 1(3) (1997), 259–289.

Tatti

, Discovering episodes with compact minimal windows, Data Mining and Knowledge Discovery 28(4) (2014), 1046–1077.

Fournier-Viger

, Lin

J.C.W.

, Vo

, Chi

T.T.

, Zhang

and Le

H.B.

, A survey of itemset mining, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 7(4) (2017), e1207.

Zhou

, Liu

and Cheng

, Mining closed episodes from event sequences efficiently, In Pacific-Asia Conference on Knowledge Discovery and Data Mining 2018 June 21 (pp. 310–318).

Huang

K.Y.

and Chang

C.H.

, Efficient mining of frequent episodes from complex sequences, Information Systems 33(1) (2008), 96–114.

Fahed

, Brun

and Boyer

, DEER: Distant and Essential Episode Rules for early prediction, Expert Systems 93 (2018), 283–298.

Tatti

and Cule

, Mining closed episodeswith simultaneous events, In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery in Data Mining 2011 August 21 (pp. 1172–1180).

Achar

, Ibrahim

and Sastry

, Pattern-growth based frequent serial episode discovery, Data & Knowledge Engineering 87 (2013), 91–108.

Agrawal

and Srikant

, Mining sequential patterns, In Proceedings of the IEEE Eleventh International Conference on Data Engineering 1995 March 6 (pp. 3–14).

10.

Casas-Garriga

, Discovering unbounded episodes in sequential data, In European Conference on Principles of Data Mining and Knowledge Discovery 2003 September 22 (pp. 83–94).

11.

, Wang

, Ren

, Ding

and Wu

, Mining sequential patterns with periodic wildcard gaps, Applied Intelligence 41(1) (2014), 99–116.

12.

Achar

, Laxman

, Viswanathan

and Sastry

P.S.

, Discovering injective episodes with general partial orders, Data Mining and Knowledge Discovery 25(1) (2012), 67–108.

13.

Achar

, Laxman

and Sastry

P.S.

, A unified view of the apriori-based algorithms for frequent episode discovery, Knowledge and Information Systems 31(2) (2012), 223–250.

14.

Lin

Y.F.

, Wu

C.W.

, Huang

C.F.

and Tseng

V.S.

, Discovering utility-based episode rules in complex event sequences, Expert Systems with Applications 42(12) (2015), 5303–5314.

15.

Laxman

, Sastry

and Unnikrishnan

, Discovering frequent generalized episodes when events persist for different durations, IEEE Transactions on Knowledge and Data Engineering 19(9) (2007), 1188–1201.

16.

Segura-Delgado

, Gacto

M.J.

, Alcala

and Alcala-Fdez

, Temporal association rule mining: An overview considering the time variable as an integral or implied component, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 10(4) (2020), e1367.

17.

Leemans

and van der Aalst

W.M.

, Discovery of frequent episodes in event logs, In International Symposium on Data-Driven Process Discovery and Analysis 2014 November 19 (pp. 1–31).

18.

Cule

, Tatti

and Goethals

, Marbles: Mining association rules buried in long event sequences, Statistical Analysis and Data Mining: The ASA Data Science Journal 7(2) (2014), 93–110.

19.

Ibrahim

, Sastry

and Sastry

P.S.

, Discovering compressing serial episodes from event sequences, Knowledge and Information Systems 47(2) (2016), 405–432.

20.

, Shi

, Wang

, Zuo

, Li

and He

, Large-Scale Frequent Episode Mining from Complex Event Sequences with Hierarchies, ACM Transactions on Intelligent Systems and Technology (TIST) 10(4) (2019), 36.

21.

, Luo

, Wang

, Zhuang

and He

, Mining precise-positioning episode rules from event sequences, IEEE Transactions on Knowledge and Data Engineering 30(3) (2017), 530–543.

22.

Neshat

, Sepidnam

and Sargolzaei

, Swallow swarm optimization algorithm: a new method to optimization, Neural Computing and Applications 23(2) (2013), 429–454.

23.

Kaveh

, Bakhshpoori

and Afshari

, An efficient hybrid particle swarm and swallow swarm optimization algorithm, Computers & Structures 143 (2014), 40–59.

24.

Revathi

and Krishnamoorthy

, The performance analysis of swallow swarm optimization algorithm, In Second IEEE International Conference on Electronics and Communication Systems (ICECS) 2015 (pp. 558–562).

25.

Poongodi

and Manzoor

A.S.

, Mining Entropy Optimized Parameter based Precise positioning Episode Rules from Event Sequences, In 2019 11th IEEE International Conference on Advanced Computing (ICoAC) 2019 December 18 (pp. 225–231).