Algorytmy genetyczne w połączeniu z Random Forest

Zadaję w dziale Python, jako, że jest bardzo dużo bibliotek pythonowy do Data Science, więc większa szansa, że ktoś coś dłubał w temacie jak niżej:

Przypuśćmy, że mamy problem klasyfikacji i korzystamy z Random Forest. Po wygenerowaniu modelu jesteśmy go w stanie zmierzyć za pomocą jakiejś metryki i porównać z innymi modelami. Te inne możemy generować w ramach hyper parameter tuning (np. korzystając z grid searcha).

Czy ktoś próbował ożenić Random Forset z algorytmami genetycznymi?

np. do głowy przychodzi mi taki pomysł:
Funkcja celu = metryka
Mutacja lasu = wywalenie jednego z drzew i zastąpienie innym
Cross Over = wyjęcie N drzew z lasuA i M z lasuB

Warto? Nie warto?

Obczaj to: https://www.sciencedirect.com/science/article/abs/pii/S0020025516305783
Ale tak na oko, to ciężki temat

Dzięki @lion137, streszczenie publikacji wygląda interesująco, jednak 'moja instytucja' nie daje dostępu do pełnej wersji publikacji :( Z tego co czytam, to użyli GA z uwagi na to, że przestrzeń hyper parametrów dla GridSearcha była zbyt duża i szukali parametrów optymalizujących metrykę accuracy. Wygląda, że hodowali populację rozwiązującą problem doboru hyper parametrów, a ja myślałem o wykorzystaniu GA do hodowania populacji lasów, z których optymalny maxymalizowałby np. accuracy, czyli trochę inne podejście.

Random forest jest to implementacja decision tree, tylko że wielu drzew, a decision tree działa na zasadzie minimalizowania entropii dla jednej gałęzi i maksymalizowania information gain dla sumy wszystkich gałęzi.

Czyli losow splitujesz pod jakimś warunkiem dane wiele razy, za każdym razem jest inna wartość tego warunku i wybierasz ten gdzie pod gałęzie mają najmniejszą entropię i mają największy zysk informacyjny.
Kilka zmiennych usuwasz lub duplikujesz tak, żeby drzewa miały różną ilość informacji każdy trenujesz minimalizując entropię i na końcu decydujesz o wyniku za pomocą większości drzew.

Teraz jak byś chciał genetycznie to zrobić, to mógłbyś mutować warunki i liczby, gdzie warunek możesz zakodować jak > 0 i < 1, a liczbę z przedziału jako binary kod genetyczny.
Czyli jak przedział od 30-64, możesz zakodować jako liczba binarnie 0000 do 1111, to wychodzi ci 5 bitów na każdą podgałąź, 1 bit to warunek, reszta to wartość.

Teraz funkcja oceny to information gain i populacja, która ma najlepsze oceny może się krzyżować.
Np. za pomocą torunamnet lub roulletet.

Krzyżowanie robisz na tej podstawie, że losowe bity i losową ich ilość bierzesz z jednego i drugiego osobnika + 1% mutacji i tak tworzysz nowego, stare osobniki zachowujesz + nowe i zabijasz najsłabsze tak żeby zawsze mieć określoną liczbę osobników np. 10 czy 100.

Jeszcze każde drzewo musi mieć różna ilość zmiennych bo to też jest kluczowe i trochę trudniejsze do zakodowania binarnie, ale coś tam się by wymyśliło.

Samo random forest to i tak nie jest najlepszy algorytm, z genetycznym możliwe, że tam dużo nie poprawisz jego skuteczności po prostu to jak działa w bardzo skomplikowanych problemach nie poradzi sobie.

@tumor: o ile zrozumiałem Twój zamysł, to odnosisz się do tego jak kodować pojedyncze drzewo? Jeśli tak to jak miałaby logicznie (pomijając szczegóły implementacje) wyglądać:
a) operacja mutacji drzewa
b) operacja cross-over drzewa

features = [Wiek, Płeć, Wzrost]
target = [Klasa]

np. mamy drzewa 1 poziomowe:
a) Tree#1 - operujące na Wiek, "IF wiek<18 THEN A else B"
b) Tree#2 - operujące na Płeć, "if ... = K C else D"

O ile dla wartości "wiek" jestem sobie w stanie wyobrazić mutację (zmiana 18 na np. 21), to w przypadku drzewa wielopoziomowego (np. dla Wiek+Wzrost), co miałoby być mutowane?
Pojedynczy node (losowo wybrany)?

Jak miałby wyglądać Cross-over Tree#1 i Tree#2?

Ja bym w ogóle nie użył genetic algorytmu do drzewa, bo co najwyżej overfitting wyjdzie, ale można użyć, chodź użycie po prostu standardowego sposobu uczenia drzewa czyli maksymalizacja information gain to powszechnie używany sposób.

Zrobienie takich mutacji żeby ilość pod gałęzi też się czasem zwiększała lub redukowała to znacznie trudniejsze do zaimplementowania.
Ogólnie w genetycznym musisz w jakiś sposób zrobić kodowanie najlepiej do binarnego kodu, wtedy krzyżowanie jest proste do wykonania, bo tylko bierzesz powiedzmy kilka bitów od jednego i drugiego rodzica genów i razem masz nowy genom dziecka.

Każdy osobnik populacji to jedno drzewo, w sumie to by wyszło coś podobnego jakbyś wygenerował losowe 100 drzew i wyuczył, każde każde koduje wszystkie 3 feature, ale przy bootstrapowaniu features jak to jest w random forest czasem wartości się powtarzają.

Teoretycznie wyjdzie to coś podobnego do tego jakbyś po prostu wygenerował 100 drzew, dopasował do danych i wybrał 10 najlepszych.

Jeśli by drzewo zawsze przechodziło 3 rozgałęzienia.
To kodujesz bitowo np. operacja i wartość, potem dla następnego, potem dla następnego.
Funkcję oceny robisz tak, że pierwszy warunek sprawdzasz z pierwszym feature i jak true to 0 jak false to kolejne pod rozgałęzienie, jak true 0 jak false itp. i na końcu 1.
Ewentualnie możesz dodać dodatkowe bity, które by określały czy w prawo się rozrasta czy w lewo drzewo czy inaczej to zakodować, bo nie ma tu ograniczeń w kreatywności.

Ale ja tak tylko mówię jak to można zrobić, bo w matematyce to dowolny sposób jest prawidłowy nie ma żadnych ograniczeń musisz jakoś zakodować informacje tak, żeby łatwo można było modyfikować funkcję, którą potem odkodujesz z tych bitów.

I mutację dawaj nie większą niż 1%, czyli losowego flipnięcia bita bo to po prostu psuje już później wyniki.

yarel napisał(a):

Czy ktoś próbował ożenić Random Forset z algorytmami genetycznymi?

Pomijając debaty filozoficzne jak jedno ma się do drugiego – przy obecnym zapchaniu i zatłoczeniu "teh Academia" istnieje spore ryzyko, że próbowano łączyć ze sobą wszystko co się da, i jeszcze trochę co się nie da, z algorytmiki/struktur danych zwłaszcza jeśli dany koncept istnieje dłuższy czas. Dlatego przy tego typu rozważaniach warto udawać się w pierwszej kolejności do wyszukiwarek wszelkiej maści publikacji akademickich, technicznych czy nawet patentów. W przypadku zacytowanego pytania z tego co widzę po wynikach zapytania do wyszukiwarki internetowej ogólnego przeznaczenia – próbowano i opisywano różne testowane podejścia i wnioski autorów, są nawet projekty na githubie.