-
Data: 2009-10-22 00:52:05
Temat: no i co z tymi algorytmami genetycznymi?
Od: Mariusz Marszałkowski <m...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 22.10.09 09:39 Filip Sielimowicz
- 22.10.09 10:27 Mariusz Marszałkowski
- 22.10.09 10:39 Filip Sielimowicz
- 22.10.09 10:46 Filip Sielimowicz
- 22.10.09 12:25 Mariusz Marszałkowski
- 22.10.09 14:53 Filip Sielimowicz
- 22.10.09 17:27 Mariusz Marszałkowski
- 23.10.09 11:05 Filip Sielimowicz
- 23.10.09 16:27 Mariusz Marszałkowski
- 26.10.09 11:23 Filip Sielimowicz
- 28.10.09 11:06 Filip Sielimowicz
- 28.10.09 12:18 Mariusz Marszałkowski
- 08.11.09 13:28 Mariusz Marszałkowski
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-26 O co chodzi?
- 2024-05-26 PJ autobus-tramwaj
- 2024-05-26 Renault Trafic i lampka z czerwonym STOP
- 2024-05-26 cena pięciocyfrowa
- 2024-05-26 Re: Jak dobra KE "okrada" złą Rosję "dla Ukrainy"
- 2024-05-25 supercap
- 2024-05-25 Sulzbach => Technischer Rollouter (d/m/w) <=
- 2024-05-25 Warszawa => Senior Account Manager <=
- 2024-05-25 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-25 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-25 Warszawa => Interactive/Experience Designer <=
- 2024-05-25 Warszawa => Key Account Manager <=
- 2024-05-25 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-25 Warszawa => Key Account Manager <=
- 2024-05-25 Re: znów ten wrocław