Classification, game theory and feature engineering: new models and applications

Articles

Suciu, M., Lung, R.I. (2023). A New Filter Feature Selection Method Based on a Game Theoretic Decision Tree. In: Abraham, A., Hong, TP., Kotecha, K., Ma, K., Manghirmalani Mishra, P., Gandhi, N. (eds) Hybrid Intelligent Systems. HIS 2022. Lecture Notes in Networks and Systems, vol 647. Springer, Cham. https://doi.org/10.1007/978-3-031-27409-1_50

Suciu, MA., Lung, R.I. (2023). Feature Selection Based on a Decision Tree Genetic Algorithm. In: García Bringas, P., et al. Hybrid Artificial Intelligent Systems. HAIS 2023. Lecture Notes in Computer Science(), vol 14001. Springer, Cham. https://doi.org/10.1007/978-3-031-40725-3_37

Lung, R. I., Suciu, M.-A. (2024). An Evolutionary Approach to Feature Selection and Classification. Machine Learning, Optimization, and Data Science: 9th International Conference, LOD 2023, Grasmere, UK, September 22–26, 2023, Revised Selected Papers, Part I, 333–347. https://doi.org/10.1007/978-3-031-53969-5\_25

Mihai Suciu, Rodica Ioana Lung. A game theoretic decision forest for feature selection and classificatio. Logic Journal of the IGPL. (articol acceptat 2023)

Bándi, N., Gaskó, N. (2024). Nested Markov chain hyper-heuristic (NMHH): A hybrid hyper-heuristic framework for single-objective continuous problems. PeerJ Computer Science, 10, e1785. https://doi.org/10.7717/peerj-cs.1785

Nándor Bándi, Noémi Gaskó. Improved Nested Markov Chain Hyper-heurisitic framework. A clustering application. Expert Systems with Applications. (articol în evaluare)

Noémi Gaskó. Feature selection based on Banzhaf index. A cooperative game theory approach. Neurocomputing (articol în evaluare)

Main results (rezumat executiv)

În prima fază, proiectul se axează pe combinarea arborilor de decizie cu modele din teoria jocurilor pentru a rezolva problema selecției atributelor relevante pentru problema de clasificare binară. Problema selecției atributelor a devenit o activitate cheie în cadrul învățării automate. Pentru problemele de clasificare, se știe că reduce complexitatea de calcul a estimării parametrilor, dar adaugă și o contribuție importantă la aspectele de înțelegere și explicare a rezultatelor.

Un arbore de decizie bazat pe un model de joc este utilizat pentru selecția atributelor. În timpul fazei de inducție a arborelui, atributul utilizat la împărțirea datelor este ales pe baza unui joc între instanțe din aceeași clasă. Presupunerea abordării este: componenta de joc va indica cele mai importante atribute. O măsură pentru importanța unui atribut este calculată pe baza numărului de apariții a unui atribut și a adâncimii nodului în arbore. Rezultatele sunt comparabile și mai bune în unele cazuri decât cele raportate printr-o abordare standard bazată și pe arbori de decizie.

A doua abordare analizată propune un algoritm genetic pentru selecția atributelor. Importanța, precum și eficacitatea atributelor alese de fiecare individ, este evaluată prin utilizarea arborilor de decizie. Importanța atributului indicată de arborele de decizie este utilizată în faza de selecție și recombinare a algoritmului genetic. Arborele indus de cel mai bun individ din populație este folosit pentru clasificare. Experimentele numerice ilustrează comportamentul abordării.

Datorită legăturii structurale naturale dintre arborii de decizie și rețelele neuronale (NN), în ultimii ani s-au dezvoltat un tip de arbori de clasificare și regresie care folosesc pentru separarea datelor din noduri funcții împrumutate din NN, cum ar fi funcția sigmoid. Urmând direcția folosirii arborilor de decizie pentru selecția de atribute, se studiază efectul folosirii FROG/probit pentru separarea datelor în construcția arborelui și eficiența acestei abordări în identificarea importanței atributelor. O altă direcție studiată constă în folosirea unui algoritm random forest pentru extragerea atributelor, prin agregarea datelor din frunze și folosirea unei variante extinse FROG pentru probleme de clasificare cu mai multe clase împreuna cu un mecanism de boosting pentru atribute.

Arborii de decizie pentru clasificare sunt în general construiți într-o manieră recursivă, ”top-down”, pornind de la nodul rădăcină. Într-o abordare opusă, construcția arborilor se poate face și ”bottom-up”, prin popularea inițială a frunzelor cu date și agregarea lor mergând către rădăcină. Această abordare folosește un algoritm de clustering pentru a crea frunzele, împreună cu un algoritm care reprezintă separarea sub forma unui hiper-plan, cum ar fi SVM pentru a agrega datele. În cadrul proiectului se explorează folosirea jocului propus în prima lucrare pentru construirea unui arbore de decizie de tip bottom-up pornind de la datele din frunze. Distanța minimă dintre clusterii din frunze (sau fiecare nivel de nod) este calculată și clusterii cei mai apropiați sunt agregați, generându-se o regulă de separare a datelor agregare folosind echilibrul Nash. Importanța atributelor se calculează pe baza arborelui astfel construit. Avantajul acestei abordări constă în controlul mai mare asupra mărimii arborelui și a purității datelor din frunze.

O altă direcție de cercetare se axează pe găsirea unor moduri optime de evaluare a valorii sau a contribuției atributelor bazate pe concepte de teoria jocurilor astfel încât acestea să reflecte cât mai eficient caracteristicile datelor. în acest sens s-a studiat efectul mai multor modele de evaluare și s-au explorat mai multe variante de funcții de câstig în vederea dezvoltării de algoritmi de selecție de atribute în explicarea datelor.

Se studiază o metodă de clasificare bazată pe selecția atributelor care evoluează ponderile atributelor folosind arbori de decizie care utilizează conceptul de echilibru Nash pentru a-și împărți datele din noduri. Se propune o strategie evolutivă pentru selecția atributelor. Indivizii reprezintă vectori de importanță a atributelor, evoluați cu scopul de a identifica cele mai relevante atribute din setul de date care pot explica problema de clasificare. Un arbore de decizie care folosește echilibrul Nash este utilizat în scopuri de clasificare și evaluare. Abordarea propusă nu implică mecanisme de selecție, arborii sunt crescuți împreună și formează un ecosistem în care toți sunt implicați în sarcina de predicție. Un individ se oprește din evoluție atunci când nu mai există variații în probabilitățile pe care le oferă pentru selectarea atributelor pentru inducerea arborelui său.

O altă abordare analizează interpretarea informațiilor furnizate de arborii de decizie și metode random forest pentru clasificare și selecția atributelor. Un arbore de decizie bazat pe concepte din teoria jocurilor este utilizat pentru a construi o pădure care rezolvă problema clasificării și pentru a evalua importanța atributelor. La construirea pădurii, informațiile despre selecția anterioară a atributelor sunt folosite pentru a îmbunătăți căutarea. Arborele de decizie și random forest reprezintă date sub formă de subseturi: partiții în cazul arborilor de decizie și seturi de partiții în cazul random forest. Aceste seturi oferă informații locale despre datele care pot fi utilizate în continuare pentru a face predicții pentru datele de test care se potrivesc în acea regiune specială a spațiului de căutare. Datele locale furnizate de random forest sunt agregate, iar un clasificator este folosit pentru a face predicții pentru probleme de clasificare.

În continuarea demersului de a folosi elemente oferite de mechanism design în problema de clasificare s-au explorat variante de a selecta atribute bazate pe contribuția marginală la valoarea unui indicator consacrat în această problemă. Deoarece în cele mai multe situații problema este de a găsi un compromis între mai multe valori (de ex. corelații între atribute/clase), o abordare bazată pe contribuție marginală poate conduce la soluții de echilibru cu valoare practică mai stabilă decât cele obținute prin combinarea aritmetică indicatorilor utilizați. O astfel de abordare este testată folosind ca și indicator meritul unei mulțimi de atribute și un algoritm genetic standard. Rezultatele preliminare indică o acuratețe superioară raportata de varianta bazată pe contribuții marginale.

O aplicație practică care analizează clasificarea țărilor în grupe de venit pe baza indicatorilor de dezvoltare mondială prezintă o interpretare a abordării selecției atributelor este folosită pentru a ilustra metodele propuse și a evidenția caracterul explicativ al acestora.

Obiectivul de a automatiza procesul de generare de forme de jocuri ale căror echilibre conduc la clasificarea corectă a datelor este atins prin explorarea folosirii de metode ale programării genetice pentru a separa instanțe în clasificarea binară. Se folosește o funcție obiectiv care poate reprezenta funcția de câștig a unui joc corespunzător cu sumă nulă (sau constantă), astfel încât metoda propusă să modeleze jocuri în selecția de atribute. Folosirea soluțiilor oferite de teoria jocurilor crește robustețea metodei și poate îmbunătăți explicabilitatea abordării.

Pe o altă direcție se explorează folosirea mecanismelor oferite de teoria grafelor pentru identificarea atributelor importante dintr-un set de date pentru clasificare nesupervizată cu mai multe clase. Astfel, setul de date este codificat ca și rețea multipartită, în care fiecare nivel corespunde unui atribut. Nivelele cele mai importante au un grad mai mic; eliminarea nivelelor cu grad (total) mai ridicat conduce la o clasificare mai bună a datelor cu diferite metode consacrate de clustering.

Rapoarte: an 1, an 2, an 3.