Algoritam slučajnih šuma jedan je od najboljih trenutno poznatih algoritama za klasifikaciju (i regresijsku analizu), sposoban klasificirati ogromne količine podataka s velikom točnošću. Također, to je algoritam koji je inherentno paralelizabilan. Izvorno algoritam je napisan u programskom jeziku Fortran 77, koji je zastario i ne pruža mnoge mogućnosti koje moderniji jezici pružaju; također, originalni kôd nije primjer "urednog" programiranja, te ga je vrlo teško primijeniti u edukativne svrhe.

U sklopu ovog projekta predlaže se adaptacija algoritma glede prikladne primjenjivosti, prevođenjem ovog algoritma u Fortran 90. Za razliku od Fortrana 77, Fortran 90 je strukturirirani paralelni programski jezik, pa je program pisan u njemu lako pokrenuti na paralelnoj infrastrukturi, te je lako čitljiv, kako istraživačima tako i studentima. Osim toga, odnedavno je puštena u opticaj (za nekomercijalne potrebe) besplatna implementacija, čije je nepostojanje bilo jedna od većih prepreka pri originalnoj implementaciji algoritma, zbog straha da neće biti prihvaćen u akademskoj zajednici. Stvoritelj algoritma, profesor emeritus Leo Breiman pri Berkeleyu, izrazio je u korespondenciji velik interes za ovu zamisao. Potvrdio je da još nitko nije radio na paralelnoj implementaciji njegovog algoritma, te obećao svoju podršku i pomoć. Leo Breiman jedan je od začetnika područja machine learning-a i data mining-a, te ko-autor prvog značajnog programa (CART – Classification and Regression Trees) u području.

Izvorni kod PARF-a može se naći ovdje. Za stvaranje izvršnog koda potreban je Fortran 90 prevodilac. Podržani su: Intel Fortran, Portland Group Fortran i GNU g95.

RFiRandom Forestssu zaštićeni znakovi Lea Breimana i Adele Cutler.

PARF je razvijen u Centru za informatiku i računarstvo Instituta Ruđer Bošković, pod financijskom podrškom Ministarstva znanosti obrazovanja i športa, i-Projekt 2004-111.

Format podataka

PARF koristi izmijenjeni ARFF format za podatke, koji je većinom kompatibilan s originalnim formatom koji koristi Weka projekt. Ukratko: Datoteka počinje imenom relacije, slijedi definicija atributa, te na kraju dolazi blok s podacima. Definicija jednog atributa daje mu ime i moguće vrijednosti: numeric (brojčane), string (tekstualne) ili skup kategorija u vitičastim zagradama. Kad god koja vrijednost sadrži razmak, potrebno ju je staviti u navodnike.

Važne razlike od ARFF specifikacije:

• Podržani su samo numerički, tekstualni i nominalni atributi — datum nije prihvaćena vrsta atributa.
• Gdje god ARFF sintaksa zahtijeva zarez, običan razmak je također u redu. Uz to, na takvim se mjestima može umetnuti ampersand (&) da bi se nastavilo u sljedećoj liniji.
• Znak za nastavak linije je posebno važan u širokim skupovima podataka, budući da je iz tehničkih razloga duljina retka ograničena, i postavljena na 1024 znaka.
• Prihvaćaju se i jednostruki i dvostruki navodnici. Ako se jednostruki navodnik treba upisati u tekstualnu vrijednost, treba koristiti dvostruke navodnike, i obratno.
• Rijetki ARFF nije podržan.
• Tekstualne vrijednosti se ignoriraju u obradi. Dodatni načini da se atribut ignorira su da se@attributepromijeni u@ignored, te da se odrede korišteni/nekorišteni atributi iz naredbenog retka (-u[u]opcija).
• Nominalnim se atributima može zadati težina za svaku kategoriju u zagradama neposredno nakon imena kategorije. Ako se težina ne zada, podrazumijeva se 1. Težine se koriste samo za atribut kojeg se odabere kao klasu.

Osnove

Ako imate podatke za učenje u ARFF formatu, možete istrenirati šumu tako da pokrenete sljedeću naredbu:

parf --verbose -t trainset.arff

Kako nije drugačije navedeno, program će uzeti posljednji atribut kao klasu.

Samo po sebi ovo nije korisno, budući da se šuma ni na koji način ne koristi, no možete vidjeti (zahvaljujući --verbose opciji, koja inače nije potrebna) da program radi. Možemo pokušati iskoristiti stvorenu šumu za klasifikaciju drugog skupa podataka (ili čak istog tog, ako još nemate drugi skup podataka):

parf --verbose -t trainset.arff -a dataset.arff

Skup podataka koji se klasificira može imati istu specifikaciju atributa kao onaj koji se koristio za treniranje šume, ili mu može biti ispušten atribut klase, sa svim drugim jednakim atributima.

Popis svih podržanih opcija može se dobiti pokretanjem sljedeće naredbe:

parf -h

Gdje se god koristi ime datoteke kao argument, može se staviti crtica (-) da bi se zadao standardni izlaz. Tamo gdje se takav argument može izostaviti, crtica se podrazumijeva. Ako se za izlaznu datoteku navede postojeća datoteka, stari će sadržaj biti izbrisan i zamijenjen novim bez upozorenja.

Gdje je god argument neki atribut, može se koristiti bilo njegovo ime ili redni broj. Ako argument sadrži razmake, mora se staviti u navodnike. Za razliku od ARFF datoteka, jedini dozvoljeni separator unutar jedne opcije je zarez - razmaci prije i poslije bit će zanemareni; također, treba staviti u navodnike cijele liste, a ne pojedina imena. (Napomena: navodnike ovdje interpretira korisnička ljuska, a ne parf, te se to odražava i na njihovu semantiku). Primjerice:

parf -t test.arff -fd "test forest.txt" -c 3 -u 'marital status, height'

Opcije za rast šume

-t datoteka

Određuje ARFF datoteku iz koje će se učiti.

-tv [datoteka]

Ispisuje glasove za out-of-bag instance pri učenju.

-tc [file]

Ispisuje matricu zabune pri učenju. Svaki redak je jedna klasa kako je navedena u datoteci; svaka kolona je jedna klasa kako ju program klasificira. Redak obilježen s "NoTag" sadrži retke čija je klasa navedena kao nepoznata (?); kolona obilježena s "NotCl" sadrži instance koje nisu mogle biti klasificirane zato što su uzete u bootstrap za svako stablo (te tako nikad nisu bile out-of-bag).

-c atribut

Određuje atribut koji će biti korišten kao atribut klase. Umjesto imena ili rednog broja atributa mogu se koristiti i posebne vrijednosti last ili new. Prva od njih se podrazumijeva ako nije drugačije određeno, i uzima posljednji atribut kao atribut klase. Druga služi za samostalno učenje: stvara se novi atribut s vrijednostima { original, constructed } (izvorni, umjetni), te se broj instanci udvostručuje: polovica će biti originalni podaci, dok će se druga polovica stvoriti nasumičnom permutacijom svake kolone originalnih podataka.

-cp kategorija

Određuje kategoriju u atributu klase koja će se smatrati pozitivnom. Sve ostale kategorije smatraju se negativnima. Ako se ne navede, neće se niti jedna kategorija izdvojiti za pozitivnu.

-n broj

Određuje broj stabala koji treba stvoriti. Ako se ništa ne navede, podrazumijeva se 100 (ili jedan po procesoru, ako je procesora kojim slučajem više). Za ozbiljne analize, preporuča se da se koristi još više stabala. Više stabala — točniji rezultati.

-m broj

Određuje broj nasumično odabranih atributa koji se razmatra na svakom čvoru u potrazi za najboljim kriterijem diobe podataka. Ako se ne navede drugačije, ovaj broj je kvadratni korijen od broja korištenih atributa, i obično je "dovoljno dobar", no optimalna vrijednost može se dobiti samo iz eksperimentacije.

-xs broj[%]

Određuje minimalni broj instanci koji čvor mora imati da bi se nastavilo s diobom. Ako se vrijednost navede kao postotak, označava postotak ukupnog broja instanci. Podrazumijeva se vrijednost 2 — tj. svaki čvor koji se uopće može podijeliti analizirat će se za diobu.

-xr omjer[%]

Određuje najmanji omjer diobe za koji se isplati dijeliti čvor. Ako je podjela neuravnoteženija od toga, ta se podjela neće desiti. Postotak označava postotak instanci u čvoru; ako se znak postotka ne navede, onda broj označava čisti omjer (broj između 0 i 1). Ako se ova opcija ne navede, uzima se 0 — bilo koja podjela koja nije trivijalna (0 : all) bit će uzeta u obzir.

-b broj

Određuje broj kategorija koji čini granicu između iscrpne i nasumične potrage za najboljom podjelom kategoričkih varijabli ("veliki" atributi). Ako je broj kategorija atributa jednak ovom broju ili veći, izvršit će se slučajna potraga, jer je iscrpna potraga eksponencijalno zavisna o broju kategorija. U odsustvu ove opcije granica je 12, što znači da će se iscrpna potraga vršiti samo ako ima 2047 kombinacija kategorija ili manje.

-bi broj

Određuje broj iteracija nasumične potrage, tamo gdje se ista koristi.

-u(u) atribut,...

Navodi atribute koji će se koristiti (ili koji se neće koristiti) pri učenju. Ova opcija nadjačava deklaraciju @ignore u ARFF datoteci. Ne smije se zadati da se koriste string (tekstualni) atributi. Prije ove opcije, svi su atributi osim onih označenih s @ignore i onih označenih kao string (tekstualni) uzeti kao korišteni, osim kad se opcija -u koristi bez opcije -uu, kad se uzima da se niti jedan atribut osim onih eksplicitno navedenih u opciji neće koristiti.

-w broj,...

Nadjačava specifikaciju težina klasa. Ako se ova opcija zada, program ignorira težine dane u ARFF datoteci (ako su uopće zadane) i koristi ove vrijednosti umjesto njih. Broj težinskih vrijednosti mora odgovarati broju kategorija atributa klase.

-r broj

Zadaje sjeme generatoru slučajnih brojeva. Ako se program pokrene s istim ulaznim podacima i istim opcijama, zadajući isto sjeme, rezultat bi trebao biti isti u svakom pokretanju. Ako ova opcija nije zadana, generator slučajnih brojeva dobiva svaki put drugo sjeme, prema sistemskom satu.

-f broj

Zadaje broj prolaza za popunjavanje nedostajućih vrijednosti. Ako je ovaj broj 0, nedostajuće vrijednosti neće biti popunjavane, a instance gdje se nedostajuće vrijednosti nalaze sudjelovat će u učenju šume samo pri atributima koji su poznati. Inače se u prvom prolazu računaju grube procjene, i sve nedostajuće vrijednosti u jednoj koloni pune se istom vrijednošću. U svakom narednom prolazu nedostajuće se vrijednosti pune prema matrici bliskosti. Ako se ništa ne zada, radi se samo grubo popunjavanje nedostajućih vrijednosti (vrijednost 1).

-v broj

Ako je ova opcija zadana, nakon što je šuma stvorena (sa svim prolazima za popunjavanje nedostajućih vrijednosti), svi osimbrojnajvažnijih atributa bit će zanemareni, i postupak rasta šume bit će ponovljen.

-mv broj

Ova je opcija jedino smislena ako se koristi uz opciju -v, i onda djeluje kao opcija -m za drugi prolaz (kad se koriste samo najvažniji atributi). Ako se ništa ne navede, uzima se kvadratni korijen broja atributa koji se koristi u drugom prolazu.

Dodatne opcije za analizu pri učenju

-p [broj[%]]

Kad se računa bliskost (što je preduvjet za neke od narednih proračuna), zadaje broj najbližih instanci koje će se za svaku instancu zadržati. Ovisno o broju instanci, matrica bliskosti može postati tako velika da se račun ne može izvesti. U takvim slučajevima treba smanjiti vrijednost ovog parametra. U njegovom odsustvu, uzima se vrijednost 100%. Kako se mnogi od narednih proračuna baziraju na matrici bliskosti, ova opcija donekle utječe na njihovu točnost; no budući da se zanemaruju najdalji slučajevi, time uvedena greška nije velika.

-if [datoteka]

Zahtijeva brzi izračun značaja atributa.

-i [datoteka]

Zahtijeva puni izračun značaja atributa.

-ic [datoteka]

Zahtijeva izračun značaja atributa za svaku instancu.

-ii [datoteka]

Zahtijeva izračun interakcija atributa. Eksperimentalni postupak.

-y [datoteka]

Zahtijeva izračun prototipova klasa, i prikazuje njihova središta u ARFF formatu.

-ya [datoteka]

Zahtijeva izračun prototipova klasa, i prikazuje sve podatke o njima.

-yn broj

Zadaje najveći broj prototipova koji će se računati po klasi. Broj izračunatih prototipova može biti manji za pojedinu klasu ako izračunati prototipovi pokriju sve njene instance.

-yp broj[%]

Zadaje broj instanci koje će se smatrati "bliskima", u svrhu određivanja pripadnosti prototipu. Broj mora biti manji ili jednak vrijednosti opcije -p. Ako se ne navede drugačije, vrijednost ove opcije je 50% ili jednaka opciji -p, što god bilo niže.

-s [broj]

Zadaje broj koordinata za skaliranje. Podrazumijeva se 2, ako ova opcija nije navedena.

-sd [broj]

Zadaje granicu uzastopno divergentnih iteracija u izračunu skaliranja prije odustajanja. Podrazumijeva se 10. Ako se argument ispusti, divergencija se u potpunosti zabranjuje (jednako kao -sd 0).

-st [datoteka]

Zahtijeva izračun skaliranja za skup podataka za učenje. Svaka instanca bit će projicirana u nižedimenzionalni prostor.

-sa [datoteka]

Zahtijeva izračun skaliranja za skup podataka za klasifikaciju. Svaka instanca bit će projicirana u nižedimenzionalni prostor.

-sy [datoteka]

Zahtijeva izračun skaliranja za skup središta prototipova. Svaka instanca bit će projicirana u nižedimenzionalni prostor.

-o broj

Zadaje graničnu vrijednost outlier mjere; samo instance s outlier mjerom jednakom ili većom od ovog broja bit će ispisane u popisu outliera. Ako se ova vrijednost ne navede, bit će ispisane sve instance.

-ot [datoteka]

Zahtijeva izračun outlier mjere za skup podataka za učenje.

-oa [file]

Zahtijeva izračun outlier mjere za skup podataka za klasifikaciju.

Opcije za klasifikaciju

-a datoteka

Određuje koju ARFF datoteku će se klasificirati.

-av [datoteka]

Ispisuje glasove pri klasifikaciji.

-ar [datoteka]

Ispisuje rezultate klasifikacije. Ako je skup neobilježen (ispušten je atribut klase), ispisat će se klase svih instanci; ako je obilježen, prikazat će se samo neodgovarajuće klasificirane instance.

-ac [datoteka]

Ispisuje matricu zabune pri klasifikaciji. Svaki redak je jedna klasa kako je navedena u datoteci; svaka kolona je jedna klasa kako ju program klasificira. Redak obilježen s "NoTag" sadrži retke čija je klasa navedena kao nepoznata (?); "NotCl" kolona je uvijek jednaka nuli, a ostavljena je radi kompatibilnosti formata s ispisom opcije -tc.

-aa [datoteka]

Ispisuje klasificirane podatke u ARFF formatu.

-ta [datoteka]

Ispisuje zajedno podatke za učenje i klasificirane podatke u ARFF formatu.

Opcije za baratanje šumom

-fs datoteka

Snima šumu za kasniju klasifikaciju u danu datoteku, te u po jednu dodatnu datoteku za svako stablo. Imenu se podrazumijeva sufiks ".forest".

-fl datoteka

Koristi snimljenu šumu. Opcije za rast šume, kao ni opcije za analizu pri učenju osim bliskosti, outliera i skaliranja, nisu dostupne. Napomena: sve datoteke stvorene opcijom -fs moraju biti prisutne na istom mjestu. Imenu se podrazumijeva sufiks ".forest".

-fd [datoteka]

Ispisuje šumu u čovjeku čitljivom obliku.

Opcije za gnuplot

-g [datoteka]

Stvara gnuplot skriptu. Ispis nekoliko drugih opcija se mijenja zbog kompatibilnosti s formatom čitljivim za gnuplot (točnije: -i, -if, -ic, -ii i -s). Stvorena skripta može se proslijediti gluplot-u kao argument, ili se može učitati iz gnuplot-ovog naredbenog retka koristeći njegovu naredbu load. Ako je terminal (vidi -gt) postavljen da stvara datoteke (npr. -gt png), tada najjednostavniji način leži u direktbom preusmjeravanju izlaza u gnuplot (piping). Slike će imati isto ime kao i odgovarajuće datoteke, s primjerenom ekstenzijom; ako izračunati podaci nisu snimani u datoteke, slike će dobiti predodređena imena. Napomena: Ako se uključi koji 3D grafikon, nije dobro koristiti piping metodu, jer gnuplot 4.0 (trenutna verzija, u vrijeme razvoja parfa) ima grešku, zbog kojega gnuplot ne učitava ispravno 3D podatke iz standardnog ulaza.

-gt terminal

Određuje terminal za ispis gnuplot skripte. Vidjeti naredbuset terminal gnuplot-a za podrobnije objašnjenje. Ako se ne odabere niti jedan terminal, koristi se višeprozorni X11.

Više primjera o korištenju gnuplot-a može se naći na stranici posvećenoj gnuplot-u.