Powitać

Jest dana macierz M, co ma R wierszy i C kolumn.
Kolumny mają średnio V różnych wartości.
Jest dana funkcja F odwzorowująca iloczyn kartezjański
wierszy i klas RxK w zbiór liczb całkowitych.

Szukane: drzewo klasyfikujące, binarne, składające się z N węzłów
decyzyjnych (i N+1 liści), które przypisze wierszom takie klasy,
alby
suma F po wszystkich wierszach była bliska maksymalnej.

Upraszczając, warunki w węzłach drzewa ograniczmy do M_ij <= C_j,
gdzie C_j jest jedną z wartości kolumny j.
Kolejne uproszczenie, niech drzewo składa się tylko z jednego
węzła N=1 decyzyjnego i dwóch liści.

Podejście bardzo naiwne:
1) Weź wszystkie warunki, których jest VxC
2) Każdy warunek sprawdź na wszystkich rekordach R, czyli
VxCxR operacji
3) Uwzględnij wszystkie kombinacje liści: K^(N+1)=KxK, razem
VxCxRxKxK operacji

Podejście mniej naiwne:
1) Zbuduj sumy częściowe F dla każdej wartości w kolumnie i dla
każdego sposobu przypisania jej do klasy: CxRxK operacji
2) Posortuj sumy częsciowe po wartościach kolumny, mamy
Cx(RxK+V*LG(V)) operacji
3) Wybierz maksymalną sumę sum częściowych dla kombinacji
klas (liści), mamy Cx(RxK+VxLg(V)+VxK) operacji

Porównujemy jeden wzór z drugim:
Cx(RxK+VxLg(V)+VxK)
----------------------------------
VxCxRxKxK

Co w przybliżeniu równa się:
R + V*Lg(V) + V
------------------------
VxRxK

1 Lg(V) 1
----- + ---------- + ---------
VxK RxK RxK

Dla dużej ilości rekordów można zaokrąglić do
1
-----
VxK

Co przykładowo przy 5 klasach i 50 wartościach
w kolumnie daje około: 1/50/5, czyli jedną dwieście
pięćdziesiątą czasu wykonania "algorytmu bardzo
naiwnego". Jeśli drzewo ma więcej węzłów niż
jeden, stosunek obu czasów wykonania maleje
wykładniczo.

Jak działa algorytm genetyczny na dwóch
powyżej opisanych algorytmów? Otóż działa
tak jak pierwszy, czyli "bardzo naiwny". Algorytm
genetyczny losuje (poniekąd to nie jest losowanie,
ale inteligentny dobór) kombinacje reguł dla
drzewa decyzyjnego a następnie testuje drzewo
na wszystkich rekordach.

Uważam że porównanie czasów obu algorytmów
stawia algorytm genetyczny w bardzo niekorzystnej
sytuacji. Testy które wykonałem zdają się to
potwierdzać. W zależności od danych, dobrym
algorytmem wyczerpującego przeszukania da
się zbudować optymalne drzewo decyzyjne
składające się 2-4 węzłowe. Algorytmem
genetycznym też można, ale znalezienie równie
dobrego rozwiązania przez algorytm genetyczny w
tym samym czasie, jest znacznie mniej prawdopodobne,
właśnie rzędu (1/250)^2 - (1/250)^4.

Pozdrawiam serdecznie