-
Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!new
s.nask.pl!news.nask.org.pl!newsfeed00.sul.t-online.de!t-online.de!border2.nntp.
dca.giganews.com!nntp.giganews.com!postnews.google.com!g23g2000vbr.googlegroups
.com!not-for-mail
From: Mariusz Marszałkowski <m...@g...com>
Newsgroups: pl.sci.ai,pl.comp.programming
Subject: no i co z tymi algorytmami genetycznymi?
Date: Wed, 21 Oct 2009 17:52:05 -0700 (PDT)
Organization: http://groups.google.com
Lines: 83
Message-ID: <6...@g...googlegroups.com>
NNTP-Posting-Host: 89.229.16.190
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1256172725 26726 127.0.0.1 (22 Oct 2009 00:52:05 GMT)
X-Complaints-To: g...@g...com
NNTP-Posting-Date: Thu, 22 Oct 2009 00:52:05 +0000 (UTC)
Complaints-To: g...@g...com
Injection-Info: g23g2000vbr.googlegroups.com; posting-host=89.229.16.190;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.7)
Gecko/2009021910 Firefox/3.0.7,gzip(gfe),gzip(gfe)
Xref: news-archive.icm.edu.pl pl.sci.ai:10914 pl.comp.programming:183856
[ ukryj 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-18 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-18 Warszawa => Software .Net Developer <=
- 2024-05-18 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-18 Ulm => Solution Architect (sichere Kommunikation und IoT-Loesungen <=
- 2024-05-18 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-05-18 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-18 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-18 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-18 Warszawa => Account Manager (Recruitment Services) <=
- 2024-05-18 Łódź => Salesperson - CRM Systems <=
- 2024-05-18 Łódź => Handlowiec - Systemy CRM <=
- 2024-05-17 ZŁOMNIK o pracy w TVN TURBO, nowych przepisach i współczesnej motoryzacji. Turbo Taryfa!
- 2024-05-17 Białystok => DevOps Engineer Conexa First (Contractor) <=
- 2024-05-17 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-17 Zabrze => Junior HelpDesk <=