Abstract
It is crystal clear that discovering the rules for finding a specific pattern among given data for extraction of association rules in rule-based learning systems has been defined in previous researches. Making use of game theory for the processes contributing to discovery of rules can be seen in numerous researches. In recent years, modeling based on game theory in rule learning sphere has gained much more attention for computer scientists. When two or more players use different strategies independently, the strategy game modeling could be used. In this view, strategic play is a desirable model for situations with no permanent strategic relationship among interactions. In addition, Nash equilibrium is the most widely used solution concept in game theory. This concept is a state-of-the-art interpretation of a strategy game. Each player has an accurate prediction of other players’ behavior and acts according to such a rational prediction. In the present study, by extracting rules from frequent patterns we have presented a model that can extract learning rules by abstraction based on game theory, which can be used not only for association rules but also for rule-based learning systems. Also, the introduced method can be easily generalized to fuzzy data. To find Nash equilibrium (FNE) in the proposed method, we used meta-heuristic bus transportation algorithm. The results indicated that the method reduces computational complexity in the associate rule discovery process and rule learning, provided that FNE is solved.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proceedings of the 20th international conference on very large data bases, VLDB ’94, San Francisco. Morgan Kaufmann Publishers Inc, pp 487–499
Ai D, Pan H, Li X, Gao Y, He D (2018) Association rule mining algorithms on high-dimensional datasets. Artif Life Robot 23(3):420–427
Ait-Mlouk A, Agouti T, Gharnati F (2017) Mining and prioritization of association rules for big data: multi-criteria decision analysis approach. J Big Data 4(1):42
Asghar M, Subhan F, Ahmad H, Khan W, Hakak S, Gadekallu T (2020) Senti-esystem: a sentiment-based esystem-using hybridized fuzzy and deep neural network for measuring customer satisfaction. Softw Pract Exp 51:06
Bell J (2020) Association rules learning, pp 129–142.02
Bhagat A, Sanjay S, Pardasani K (2010) Feed forward neural network algorithm for frequent patterns mining. Int J Comput Sci Inf Secur 8:11
Bodaghi M, Samieefar K (2019) Meta-heuristic bus transportation algorithm. Iran J Comput Sci 2(1):23–32
Carmona CJ, del Jesus MJ, Herrera F (2018) A unifying analysis for the supervised descriptive rule discovery via the weighted relative accuracy. Knowl Based Syst 139:89–100
Chakaravarthy V, Pandit V, Sabharwal Y (2009) Analysis of sampling techniques for association rule mining, pp 276–283, 01
Chakraborty M, Biswas S, Purkayastha B (2020) Rule extraction from neural network trained using deep belief network and back propagation. Knowl Inf Syst 62:09
Cheng X, Sen S, Shengzhi X, Li Z (2015) Dp-apriori: a differentially private frequent itemset mining algorithm based on transaction splitting. Comput Secur 50:74–90
Cózar J, delaOssa LG, ámez José A (2018) Learning compact zero-order tsk fuzzy rule-based systems for high-dimensional problems using an apriori + local search approach. Inf Sci 433–434:1–16
Daskalakis C, Goldberg PW, Papadimitriou CH (2006) The complexity of computing a nash equilibrium. In: Proceedings of the thirty-eighth annual ACM symposium on theory of computing, STOC ’06, pp 71–78, New York. Association for Computing Machinery
Djenouri Y, Comuzzi M (2017) Combining apriori heuristic and bio-inspired algorithms for solving the frequent itemsets mining problem. Inf Sci 420:1–15
Durkin J, Durkin J (1998) Expert systems: design and development, 1st edn. Prentice Hall PTR, New York
Durlauf Steven N, Blume Lawrence E (2010) Learning and Evolution in Games: An Overview, pages 184–190. Palgrave Macmillan UK, London
Fürnkranz J, Gamberger D, Lavrac N (2012) Supervised descriptive rule learning, pp 247–265.09
Fürnkranz J, Kliegr T (2015) A brief overview of rule learning. 08
Gan W, Lin C-W, Viger PF, Chao H-C, Philip Yu (2019) A survey of parallel sequential pattern mining. ACM Trans Knowl Discov Data 13:1–34, 06
Han J, Pei J, Yin Y (2000) Mining frequent patterns without candidate generation. SIGMOD Rec 29(2):1–12
Hoque S, Mustafa R, Mondal S, Bhuiyan Md (2015) A fuzzy frequent pattern-growth algorithm for association rule mining. Int J Data Min Knowl Manag Process 5:21–33, 09
Huiqi Q (2020) Improvement parallelization in apriori algorithm. In: Proceedings of the 2020 international conference on computers, information processing and advanced education, CIPAE, New York 2020. Association for Computing Machinery, pp 235–238
Iancu I, Gabroveanu M (2010) Fuzzy logic controller based on association rules. Analele Universităţii din Craiova. Seria Matematică Informatic, 37, 01
Isazadeh A, Pedrycz W, Mahan F (2014) Eca rule learning in dynamic environments. Expert Syst Appl 41(17):7847–7857
Lin K-C, Liao I-E, Chen Z-S (2011) An improved frequent pattern growth method for mining association rules. Expert Syst Appl 38:5154–5161, 05
Liu H, Chen S-M (2019) Multi-stage mixed rule learning approach for advancing performance of rule-based classification. Inf Sci 495:65–77
Mangalampalli A, Pudi V (2009) Fuzzy association rule mining algorithm for fast and efficient performance on very large datasets. In: 2009 IEEE international conference on fuzzy systems, pp 1163–1168
Millette L (2012) Improving the knowledge-based expert system lifecycle. UNF Grad Theses Diss 407:01
Miyaji A, Rahman MS (2011) Privacy-preserving data mining: a game-theoretic approach. In: Li Y (ed) Data and applications security and privacy XXV. Springer, Berlin, Heidelberg, pp 186–200
Narahari Y (2010) Game theoretic approaches to knowledge discovery and data mining. In: Zaki MJ, Xu J, Yu BR, Pudi V (eds) Advances in Knowledge discovery and data mining. Springer, Berlin, Heidelberg, p 3
Novak PK, Lavrac N, Webb G (2009) Supervised descriptive rule discovery: a unifying survey of contrast set, emerging pattern and subgroup mining. J Mach Learn Res 10:377–403, 01
Novak PK, Lavrač N, Webb GI (2010) Supervised descriptive rule induction. Springer, Boston, pp 938–941
Palshikar GK, Kale MS, Apte MM (2007) Association rules mining using heavy itemsets. Data Knowl Eng 61(1):93–113 (Business Process Management)
Papadimitriou C (2015) Chapter 14—the complexity of computing equilibria. Volume 4 of Handbook of game theory with economic applications. Elsevier, pp 779–810
Piatetsky-Shapiro G (1991) Discovery, analysis, and presentation of strong rules. In: Piatetsky-Shapiro G, Frawley WJ (eds) Knowledge discovery in databases. AAAI/MIT Press, London, pp 229–248
Pierrard R, Poli J-P, Hudelot C (2018) A fuzzy close algorithm for mining fuzzy association rules. Working paper or preprint
Rathinasabapathy R, Bhaskaran R (2009) Performance comparison of hashing algorithm with apriori. In: 2009 International conference on advances in computing, control, and telecommunication technologies, pp 729–733
Saabith S, Sundararajan E, Abu BA (2016) Parallel implementation of apriori algorithms on the Hadoop-Mapreduce platform—an evaluation of literature. J Theor Appl Inf Technol 85(321–351):03
Sabita B, Mishra D, Shruti M, Satapathy S, Rath A, Acharya M (2010) Pattern discovery using fuzzy fp-growth algorithm from gene expression data. Int J Adv Comput Sci Appl 5:11
Shabtay L, Fournier-Viger P, Yaari R, Dattner I (2021) A guided fp-growth algorithm for mining multitude-targeted item-sets and class association rules in imbalanced data. Inf Sci 553:353–375
Singh S, Garg R, Mishra P (2015) Performance analysis of apriori algorithm with different data structures on hadoop cluster. Int J Comput Appl 128:975–8887, 10
Sowan B, Keshav Dahal MA, Hossain LZ, Spencer L (2013) Fuzzy association rule mining approaches for enhancing prediction performance. Expert Syst Appl 40(17):6928–6937
Soysal ÖM, Gupta E, Donepudi H (2016) A sparse memory allocation data structure for sequential and parallel association rule mining. J Supercomput 72(2):347–370
Stahl D (1997) Rule learning in symmetric normal-form games: theory and evidence. Care working papers, The University of Texas at Austin, Center for Applied Research in Economics
Stahl DO (2000) Rule learning in symmetric normal-form games: theory and evidence. Games Econom Behav 32(1):105–138
Telikani A, Gandomi AH, Shahbahrami A (2020) A survey of evolutionary computation for association rule mining. Inf Sci 524:318–352
Thakur S, Ninoria SZ (2017) An improved progressive sampling based approach for association rule mining. Int J Comput Appl 165:27–35
Theocharopoulou G, Bobori C, Vlamos P (2017) Formal models of biological systems. In: Panayiotis V (ed) GeNeDis 2016. Springer, Cham, pp 325–338
Triantaphyllou E, Felici G (2006) Data mining and knowledge discovery approaches based on rule induction. Techniques 6:06
Vasoya A, Koli N (2016) Mining of association rules on large database using distributed and parallel computing. Procedia Computer Science, 79:221–230, 2016. Proceedings of international conference on communication, computing and virtualization (ICCCV)
Vijayalakshmi V, Pethalakshmi A (2015) An efficient count based transaction reduction approach for mining frequent patterns. Procedia Comput Sci, 47:52–61. Graph Algorithms, high performance implementations and its applications (ICGHIA 2014)
Wang Y (2006) Integration of data mining with game theory. In: Wang K, Kovacs GL, Wozny M, Fang M (eds) Knowledge enterprise: intelligent strategies in product design, manufacturing, and management. Springer, Boston, pp 275–280
Wang C, Zheng X (2020) Application of improved time series apriori algorithm by frequent itemsets in association rule data mining based on temporal constraint. Evol Intel 13(1):39–49
Wang K, Kovács G, Wozny M, Fang M (2006) Knowledge enterprise: intelligent strategies in product design, manufacturing, and management: proceedings of PROLAMAT 2006, IFIP TC5 international conference, June 15–17, 2006, Shanghai, China, vol 207. 01
Wang C-H, Zheng L, Yu X, Zheng X (2017) Using fuzzy fp-growth for mining association rules. In: Proceedings of the 2017 international conference on organizational innovation (ICOI 2017). Atlantis Press, 2017/07, pp 275–279
Wu Z, Dang C, Karimi HR, Zhu C, Gao Q (2014) A mixed 0–1 linear programming approach to the computation of all pure-strategy nash equilibria of a finite n-person game in normal form. Math Prob Eng 2014:640960
Xiangyang S, Ling Z (2016) Apriori parallel improved algorithm based on mapreduce distributed architecture, pp 517–521
Yu X, Zhan R, Tan G, Chen L, Tian B (2020) An improved apriori algorithm research in massive data environment. In: Xu Z, Raymond CKK, Ali D, Reza P, Mohammad H (eds) Cyber security intelligence and analytics. Springer, Cham, pp 843–851
Yin M, Wang W, Liu Y, Jiang D (2018) An improvement of fp-growth association rule mining algorithm based on adjacency table. MATEC Web Conf 189:10012
Yuan X (2017) An improved apriori algorithm for mining association rules. AIP Conf Proc 1820(1):080005
Zeng Y, Yin S, Liu J, Zhang M (2015) Research of improved fp-growth algorithm in association rules mining. Sci Program 2015:910281
Zhu W, Chang L, Sun J, Wu G, Xu X, Xu X(2021) Parallel multipopulation optimization for belief rule base learning. Inf Sci 556:436–458
Zou L, Lin H, Song X, Feng K, Liu X (2021) Rule extraction based on linguistic-valued intuitionistic fuzzy layered concept lattice. Int J Approx Reason 133:1–16
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Boudaghi, M., Mahan, F. & Isazadeh, A. Using BTA Algorithm for finding Nash equilibrium problem aiming the extraction of rules in rule learning. Soft Comput 26, 439–462 (2022). https://doi.org/10.1007/s00500-021-06432-7
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-021-06432-7