Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Using BTA Algorithm for finding Nash equilibrium problem aiming the extraction of rules in rule learning

  • Data analytics and machine learning
  • Published:
Soft Computing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • Bodaghi M, Samieefar K (2019) Meta-heuristic bus transportation algorithm. Iran J Comput Sci 2(1):23–32

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Durkin J, Durkin J (1998) Expert systems: design and development, 1st edn. Prentice Hall PTR, New York

    MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • Han J, Pei J, Yin Y (2000) Mining frequent patterns without candidate generation. SIGMOD Rec 29(2):1–12

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Liu H, Chen S-M (2019) Multi-stage mixed rule learning approach for advancing performance of rule-based classification. Inf Sci 495:65–77

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Chapter  Google Scholar 

  • 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

    Chapter  Google Scholar 

  • 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

    MATH  Google Scholar 

  • Novak PK, Lavrač N, Webb GI (2010) Supervised descriptive rule induction. Springer, Boston, pp 938–941

    Google Scholar 

  • Palshikar GK, Kale MS, Apte MM (2007) Association rules mining using heavy itemsets. Data Knowl Eng 61(1):93–113 (Business Process Management)

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Telikani A, Gandomi AH, Shahbahrami A (2020) A survey of evolutionary computation for association rule mining. Inf Sci 524:318–352

    Article  MathSciNet  MATH  Google Scholar 

  • Thakur S, Ninoria SZ (2017) An improved progressive sampling based approach for association rule mining. Int J Comput Appl 165:27–35

    Google Scholar 

  • Theocharopoulou G, Bobori C, Vlamos P (2017) Formal models of biological systems. In: Panayiotis V (ed) GeNeDis 2016. Springer, Cham, pp 325–338

    Chapter  Google Scholar 

  • Triantaphyllou E, Felici G (2006) Data mining and knowledge discovery approaches based on rule induction. Techniques 6:06

    MATH  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    MathSciNet  MATH  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Zeng Y, Yin S, Liu J, Zhang M (2015) Research of improved fp-growth algorithm in association rules mining. Sci Program 2015:910281

    Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to F. Mahan.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-021-06432-7

Keywords

Navigation