1. Home
  2. Issues
  3. Volume 35, Issue 3 (2024)
  4. An Improved Algorithm for Extracting Fre ...

Informatica


An Improved Algorithm for Extracting Frequent Gradual Patterns
Volume 35, Issue 3 (2024), pp. 577–600
Pub. online: 24 July 2024      Type: Research Article      Open accessOpen Access
Received
1 April 2023
Accepted
1 June 2024
Published
24 July 2024

Abstract

Frequent gradual pattern extraction is an important problem in computer science widely studied by the data mining community. Such a pattern reflects a co-variation between attributes of a database. The applications of the extraction of the gradual patterns concern several fields, in particular, biology, finances, health and metrology. The algorithms for extracting these patterns are greedy in terms of memory and computational resources. This clearly poses the problem of improving their performance. This paper proposes a new approach for the extraction of gradual and frequent patterns based on the reduction of candidate generation and processing costs by exploiting frequent itemsets whose size is a power of two to generate all candidates. The analysis of the complexity, in terms of CPU time and memory usage, and the experiments show that the obtained algorithm outperforms the previous ones and confirms the interest of the proposed approach. It is sometimes at least 5 times faster than previous algorithms and requires at most half the memory.

References

 
Agrawal, R., Srikant, R. (1994). Fast algorithms for mining association rules in large databases. In: International Conference On Very Large Data Bases (VLDB ‘94). Morgan Kaufmann Publishers, Inc., San Francisco, CA, USA, pp. 487–499. 1-55860-153-8.
 
Al-Jammali, K. (2023). Prediction of heart diseases using data mining algorithms. Informatica (Slovenia), 47(5). https://doi.org/10.31449/INF.V47I5.4467.
 
Ayouni, S., Yahia, S.B., Laurent, A., Poncelet, P. (2010). Motifs graduels clos. In: Extraction et Gestion des Connaissances (EGC’2010), Actes, 26 au 29 janvier 2010, Hammamet, Tunisie, pp. 211–216. http://editions-rnti.fr/?inprocid=1001293.
 
Belise, K.E. (2011). Algorithmes des motifs séquentiels et temporels : Etat de l’art et étude comparative. Master’s thesis, Université de Dschang.
 
Belise, K.E., Calvin, T., Nkambou, R. (2017). A pattern growth-based sequential pattern mining algorithm called prefixSuffixSpan. EAI Endorsed Transactions on Scalable Information Systems, 4(12), 4. https://doi.org/10.4108/eai.18-1-2017.152103.
 
Belise, K.E., Fotso, L.C.T., Djamégni, C.T. (2023). A novel algorithm for mining maximal frequent gradual patterns. Engineering Applications of Artificial Intelligence, 120, 105939. https://doi.org/10.1016/j.engappai.2023.105939.
 
Belise, K.E., Roger, N., Calvin, T., Nguifo, E.M. (2018). A parallel pattern-growth algorithm. In: CARI’2018, South Africa, pp. 245–256.
 
Berzal, F., Cubero, J.C., Sánchez, D., Miranda, M.A.V., Serrano, J. (2007). An alternative approach to discover gradual dependencies. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 15(5), 559–570. https://doi.org/10.1142/S021848850700487X.
 
Chicco, D., Jurman, G. (2020). Machine learning can predict survival of patients with heart failure from serum creatinine and ejection fraction alone. BMC Medical Informatics and Decision Making, 20(1), 1–16.
 
Clémentin, T.D., Cabrel, T.F.L., Belise, K.E. (2021). A novel algorithm for extracting frequent gradual patterns. Machine Learning with Applications, 5, 100068.
 
Côme, A., Lonlac, J. (2021). Extracting frequent (closed) seasonal gradual patterns using closed itemset mining. In: 33rd IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2021, Washington, DC, USA, November 1–3, 2021. IEEE, pp. 1442–1448. https://doi.org/10.1109/ICTAI52525.2021.00229.
 
Di-Jorio, L., Laurent, A., Teisseire, M. (2009a). Extraction efficace de règles graduelles. In: Ganascia, J.-G., Gançarski, P. (Eds.), Extraction et gestion des connaissances (EGC’2009), Actes, Strasbourg, France, 27 au 30 janvier 2009. Revue des Nouvelles Technologies de l’Information, Vol. RNTI-E-15. Cépaduès-Éditions, pp. 199–204. 978-2-85428-878-0. http://editions-rnti.fr/?procid=4591.
 
Di-Jorio, L., Laurent, A., Teisseire, M. (2009b). Mining frequent gradual itemsets from large databases. In: International Symposium on Intelligent Data Analysis, pp. 297–308.
 
Di-Jorio, L., Laurent, A., Teisseire, M. (2009c). Mining frequent gradual itemsets from large databases. In: Adams, N.M., Robardet, C., Siebes, A., Boulicaut, J.-F. (Eds.), Advances in Intelligent Data Analysis VIII, 8th International Symposium on Intelligent Data Analysis, IDA 2009, Lyon, France, August 31–September 2, 2009. Proceedings. Lecture Notes in Computer Science, Vol. 5772. Springer, pp. 297–308. 978-3-642-03914-0.
 
Frawley, W.J., Piatetsky-Shapiro, G., Matheus, C.J. (1992). Knowledge discovery in databases: an overview. AI Magazine, 13(3), 57–70. http://www.aaai.org/ojs/index.php/aimagazine/article/view/1011.
 
Ham, N., Nguyen, L., Huong, B., Tuong, L. (2022). A new approach for efficiently mining frequent weighted utility patterns. Applied Intelligence, 53(1), 121–140. https://doi.org/10.1007/s10489-022-03580-7.
 
Hüllermeier, E. (2002). Association RUles for expressing gradual dependencies. In: Principles of Data Mining and Knowledge Discovery, 6th European Conference, PKDD 2002, Helsinki, Finland, August 19–23, 2002, Proceedings, pp. 200–211. https://doi.org/10.1007/3-540-45681-3_17.
 
Islam, T., Chisty, T.A., Roy, P. (2018). A Deep Neural Network Approach for Intelligent Crop Selection and Yield Prediction Based on 46 Parameters for Agricultural Zone-28 in Bangladesh. PhD thesis, BRAC University.
 
Jabbour, S., Lonlac, J., Saïs, L. (2019). Mining gradual itemsets using sequential pattern mining. In: 2019 IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2019, New Orleans, LA, USA, June 23–26, 2019. IEEE, pp. 1–6. https://doi.org/10.1109/FUZZ-IEEE.2019.8858864.
 
Kenmogne, E.B. (2016). The impact of the pattern-growth ordering on the performances of pattern growth-based sequential pattern mining algorithms. Computer and Information Science, 10(1), 23–33.
 
Kenmogne, E.B. (2018). Contribution to the Sequential and Parallel Discovery of Sequential Patterns with an Application to the Design of e-Learning Recommenders. PhD thesis, University of Dschang.
 
Kenmogne, E.B., Djamegni, C.T., Nkambou, R., Tabueu Fosto, L.C., Tadmon, C. (2022). Efficient mining of intra-periodic frequent sequences. Array, 16, 100263. https://doi.org/10.1016/j.array.2022.100263.
 
Kononenko, I., Bevk, M. (2009). Extended symbolic mining of textures with association rules. Informatica (Slovenia), 33(4), 487–497. http://www.informatica.si/index.php/informatica/article/view/266.
 
Laurent, A., Lesot, M.-J., Rifqi, M. (2009). GRAANK: exploiting rank correlations for extracting gradual itemsets. In: Andreasen, T., Yager, R.R., Bulskov, H., 0001, H.C., Larsen, H.L. (Eds.), Flexible Query Answering Systems, 8th International Conference, FQAS 2009, Roskilde, Denmark, October 26–28, 2009. Proceedings. Lecture Notes in Computer Science, Vol. 5822. Springer, pp. 382–393. 978-3-642-04956-9.
 
Laurent, A., Negrevergne, B., Sicard, N., Termier, A. (2010). PGP-mc: extraction parallèle efficace de motifs graduels. In: EGC: Extraction et Gestion des Connaissances, pp. 453–464. Cépaduès.
 
Laurent, A., Négrevergne, B., Sicard, N., Termier, A. (2012). Efficient parallel mining of gradual patterns on multicore processors. In: Advances in Knowledge Discovery and Management. Springer, pp. 137–151.
 
Li, J., Liu, X. (2021). Fetal health classification based on machine learning. In: 2021 IEEE 2nd International Conference on Big Data, Artificial Intelligence and Internet of Things Engineering (ICBAIE). IEEE, pp. 899–902.
 
Lonlac, J., Nguifo, E.M. (2020). A novel algorithm for searching frequent gradual patterns from an ordered data set. Intelligent Data Analysis, 24(5), 1029–1042. https://doi.org/10.3233/IDA-194644.
 
Lonlac, J., Doniec, A., Lujak, M., Lecoeuche, S. (2020). Mining frequent seasonal gradual patterns. In: Song, M., Song, I., Kotsis, G., Tjoa, A.M., Khalil, I. (Eds.), Big Data Analytics and Knowledge Discovery – 22nd International Conference, DaWaK 2020, Bratislava, Slovakia, September 14–17, 2020, Proceedings. Lecture Notes in Computer Science, Vol. 12393. Springer, pp. 197–207. https://doi.org/10.1007/978-3-030-59065-9_16.
 
Negrevergne, B., Termier, A., Rousset, M.-C., Méhaut, J.-F. (2014). Para miner: a generic pattern mining algorithm for multi-core architectures. Data Mining and Knowledge Discovery, 28(3), 593–633.
 
Ser, S., Saïs, F., Teisseire, M. (2018). Découverte de motifs graduels partiellement ordonnés: application aux données d’expériences scientifiques. In: Extraction et Gestion des Connaissances, EGC 2018, Paris, France.
 
Vera, J.C.D., Ortiz, G.M.N., Molina, C., Vila, M.A. (2020). Knowledge redundancy approach to reduce size in association rules. Informatica (Slovenia), 44(2). https://doi.org/10.31449/inf.v44i2.2839.

Biographies

Kenmogne Edith Belise
ebkenmogne@gmail.com

E.B. Kenmogne received her master and PhD degrees in computer science at the Department of Mathematics and Computer Science of the Faculty of Sciences of the University of Dschang (Cameroon) in 2012 and 2018, respectively. Her current research interests include data mining and artificial intelligence. In January 2020, she started working at the University of Dschang as a lecturer. In December 2021, she was promoted to the rank of senior lecturer.

Tetakouchom Idriss
https://orcid.org/0000-0003-3413-0981
itetakouchom@gmail.com

I. Tetakouchom received his master degree in computer science from the Department of Mathematics and Computer Science at the Faculty of Sciences of the University of Dschang in 2019, where he is now a PhD candidate. His main research topic is knowledge discovery.

Tayou Djamegni Clémentin
dtayou@gmail.com

C. Tayou Djamegni is a full professor of computer science at the University of Dschang (Uds). He obtained the DEA, the Doctorat de Troisième Cycle, and the Doctorat d’État at the Department of Computer Science of the Faculty of Sciences of the University of Yaoundé I in 1995, 1997 and 2005, respectively. From December 2007 to March 2018, he headed the Department of Mathematics and Computer Science at the Faculty of Sciences of the Uds. In this position, he initiated and coordinated the design and implementation of the first Master’s and doctoral programs of the Uds in computer science and mathematics. He also launched and coordinated the creation of the first computer science research laboratory at Uds LIFA, later renamed URIFIA. From March 2018 to this day, he is head of the Computer Engineering Department at the Fotso Victor University Institute of Technology. He supervised fifteen doctoral theses in computer science. He is a member of the Editorial Board of Informatics in Medicine Unlocked and African Revue in Informatics and Mathematics Applied. He won four third prizes, one second prize and four first prizes at SAT competitions, and one third prize at EDA CHALLENGE 2021. His research interests include sensor networks, knowledge discovery, distributed algorithms, cloud computing, artificial intelligence and security.

Nkambou Roger
nkambou.roger@uqam.ca

R. Nkambou received his PhD degree in computer science from the Université de Montréal in 1996. He is a full professor of computer science at the Université du Québec à Montréal and the Director of the Artificial Intelligence Research Center (http://gdac.uqam.ca/CRIA). His research interests include machine learning, knowledge representation, intelligent tutoring systems, ontology engineering, data mining, and affective computing. He is an associate editor of Frontiers in Artificial Intelligence. He also serves as a senior member of the program committees for important international conferences such as EDM, ITS and AIED.

Tabueu Fotso Laurent Cabrel
laurent.tabueu@gmail.com

L. Tabueu Fotso received his master and PhD degree in computer science from the Department of Mathematics and Computer Science at the Faculty of Sciences of the University of Dschang in 2017 and 2023, respectively. His main research topic is knowledge discovery.


Full article PDF XML
Full article PDF XML

Copyright
© 2024 Vilnius University
Open access article under the CC BY license.

Keywords
gradual pattern frequent pattern candidate binary matrix mining

Metrics
since January 2020
311

Article info
views

149

Full article
views

116

PDF
downloads

35

XML
downloads


Share


RSS