Arbori de Decizie in Recunoasterea Modelului

1.Introducere

O metoda interesanta si eleganta din punct de vedere estetic si intuitiv in luarea unei decizii este aceea de a actiona pe mai multe etape, luand decizii partiale pe parcurs. Astfel de proceduri au cateva caracteristici atractive, cea mai importanta dintre acestea fiind, poate, intelegerea. Cel care ia decizia are sentimentul ca el sau ea (sau algoritmul, daca este implementat pe o masina de calcul) are controlul asupra situatiei astfel incat unele erori in deciziile partiale pot fi corectate in etape ulterioare sau chiar luand-o de la capat spre inceput. In multe situatii, luarea unor astfel de decizii partiale este simpla deoarece ele cer examinarea informatiei relevante doar pentru etapa curenta. Acest lucru ar salva cheltuiala de a aduna informatii ce nu sunt necesare pentru etapa curenta. Aceste aspecte au contribuit la popularitatea luarii deciziei in etape multiple in cateva probleme de tehnologie, recunoasterea formelor devenind una majora.

O definitie aproximativa a recunoasterii formelor in contextul unor metode cu etape multiple este atribuirea unui obiect fizic sau a unui eveniment la una dintre categoriile specificate inainte. Problema principala in sistemele cu mai multe etape este proiectarea unei scheme de clasificare. Alte probleme importante sunt definirea informatiilor potrivite avand elemente pentru clasificare, specificarea metodelor pentru extragerea lor, modelarea si validarea datelor si estimarea performantei schemei proiectate. Destul de des, doar o multime finita de informatii este data pentru a ajuta proiectarea si acest lucru ar putea necesita sa faci presupuneri rapide asupra structurii statistice a datelor. Arborii de decizie ofera avantaje diferite cand reprezentarea foarte variata este nerealista pentru cantitatea limitata de date. Daca un arbore de decizie este bine proiectat, rezultatul este o schema de clasificare care este precisa, flexibila si eficienta din punct de vedere al calculului. Flexibilitatea in luarea deciziei asupra modelului mareste aplicabilitatea sa intr-o gama larga de probleme. Totusi, aceasta reprezentare mai putin restrictiva deschide atat de multe posibilitati in construirea unei scheme cu mai multe nivele astfel incat nu exista metoda directa pentru a proiecta arborii de decizie. Proiectantul poate permite schite care au functii de decizie extrem de complexe pentru fiecare nod sau foarte simple precum deciziile binare avand ca punct de plecare comparatia unei singure variabile. Mai mult, un arbore care este simplu de schitat poate sa nu fie simplu in operarea asupra (exemplelor-modelelor de teste) testelor exemplu si vice versa. Aceste aspecte tind sa-l incurce pe proiectant, care ar putea sfarsi cu un arbore de decizie fara sa poata specifica de ce sau cum clasificatorul particular este potrivit pentru aceasta problema. Obiectivele acestei analize sunt :

-(I) sa consolideze metodologiile majore pentru schitarea arborelui de

decizie ;

-(II) sa prezinte lucrurile pe care le au in comun ;

-(III) sa dea o semnificatie in mecanismul de clasificare in mai multe

etape;

-(IV) sa discrediteze anumite mituri precum ideea ca arborii de decizie sunt intotdeauna simplu de proiectat si folosit ;

-(V) sa mentioneze ariile lor de aplicare ;

-(VI) in general sa ajute proiectantul in selectarea unei tehnici adecvate sau in elaborarea uneia potrivite pentru problema particulara in cauza.

Nevoia unei analize noi apare din trei motive. Primul, cresterea recunoasterii ca in ansamblu schemele optime pe mai multe etape nu sunt nici necesare, nici utile pentru aplicatiile practice de scurta durata. Al doilea,ezitanta a faptului ca marimea setului testului proba este intotdeauna mai mica decat se doreste. Si in sfarsit, ca o consecinta, dezvoltarea unor tehnici destul de variate in proiectarea arborilor de decizie.

Principala dificultate in atingerea scopurilor de mai sus este imposibilitatea virtuala de a descrie pe scurt munca diferitilor autori intr-o insemnare comuna. Sectiunea 2, dupa prezentarea principalei insemnari, stabileste nevoia si descrie o metoda pentru luarea unei decizii pe mai multe etape pentru anumite probleme de recunoastere a modelului. Sectiunea 3 clasifica o multime a scheletelor arborelui de decizie in trei mari grupe. Dificultatea chiar si numai in folosirea arborelui, ce are o structura pe mai multe etape cu trasaturi si clase specifice, este infatisata in mod clar. Un tur al principalelor metode de proiectare este realizat in Sectiunea 4. Nu s-au raportat prea multe despre analiza performantei arborilor de decizie. Marea majoritate a metodelor de proiectare se bazeaza pe antrenament si preciziile setului de teste. Sectiunea 5 atinge acest aspect. Sectiunea 6 este devotata unei discutii comparative a tuturor metodelor si a unor probleme specifice care nu sunt altfel acoperite. Cateva aplicatii sunt indicate in Sectiunea 7 si Sectiunea 8 rezuma concluziile majore.

O referinta avantajoasa pentru a incepe discutia despre recunoasterea modelului arborilor este Kanal [35], care studiaza abordari demersuri interactive ale analizei modelului. Pe atunci, era notat ca performanta datelor testului independent ale invatarii singure si alte noi demersuri cad nu departe de asteptare. Acest lucru a dus la recunoasterea ca solutia problemelor de clasificare ale modelului nu se afla in intregime in echipamentele de invatare, demersuri statistice, filtrarea spatiala, programare euristica, demersuri lingvistice formale sau in orice alta solutie particulara sustinuta viguros de unul sau alt grup din acel timp. Analiza interactiva a modelului este un mod de a permite examinarea structurii datelor modelului. Structurile ierarhice formeaza o importanta categorie a reprezentarii datelor si arborii de decizie sunt potriviti in mod natural pentru recunoasterea modelului cu o astfel de reprezentare a datelor. Wu [63] descrie apropierea arborelui de decizie de clasificarea datelor multivariate in mod normal, distribuite multispectral. Avantajele majore considerate aici sunt imbunatatirea in acuratetea clasificarii cu modele finite, eficienta calculului si oportunitatea in aplicatii. Ele furnizeaza perspicacitate in problema dimensionalitatii si propun abordarea arborelui pentru a o invinge. Interpretarea histograma, gruparea secventiala si apropierea optima de model sunt descrise.

Kulkarni [40] investigheaza proprietatile teoretice ale unui model general de scheme de recunoastere cu mai multe etape si clase. Modelul permite o larga clasa de scheme parametrice si nonparametrice in interiorul scheletului. El propune doua clase de strategii de cautare pentru a obtine decizii optime. Clasificatorii ierarhici sunt tipuri speciale mult mai practice de scheme de recunoastere a modelului pe mai multe etape. O interpretare de trei faze este propusa pentru schema clasificatorilor ierarhici. Fazele individuale sunt proiectarea scheletului arborelui, caracteristica selectiei la nodurile sale si expresia functiei de decizie la fiecare nod. Aceste metode optime de proiectare sunt grele din punct de vedere al calculului pentru probleme medii si mari. Cateva metode euristice sunt explorate pentru a reduce complexitatea modelului. Unele dintre ele sunt:

(I) gruparea regulilor de decizie si eliminarea multimilor de reguli

suboptimale fara sa le evalueze individual si

(II) ordonarea trasaturilor si metode ramificate si marginite. Mai este examinata si relatia dintre performanta, dimensiunea modelului si numarul nivelelor de cuantificare. Anderson si Fu [1] in dezvoltarea arborilor liniari binari pentru clasificarea leucocita, revizuiesc alte metode precum spatiul de stari, arborele-joc si abordarile de partitionare.

In descrierea muncii anterioare, Bell [4] propune ajungerea la un tabel de decizie cu reguli initiale de inceput si interactiv schimband regulile de la nu-mi pasa la da sau nu si vice versa. Tabelul de decizie astfel obtinut este convertit in arbori binari de una din cele cateva metode sugerate. Payne si Preece [53] incearca o sinteza a unei literaturi mari si destul de dispersate in identificarea cheilor si tabelelor diagnostic. Ei definesc cheia ca un tabel cu doua coloane. Prima coloana este un set de teste. A doua este identificarea sau indexul pentru testul urmator de a fi condus. Pe de alta parte, un tabel diagnostic este definit ca avand atatea randuri ca numarul de identificari (clase). Intrari corespunzatoare coloanei a doua de aici inainte sunt proprietatile reprezentand identificarile. Autorii discuta despre meritele relative a celor doua tipuri de reprezentari si recunoasterea modelului citat ca o aplicatie pentru folosirea lor. Ei ating concepte optime si probabilistice si interpretari teoretice de decizie pentru selectia testelor (caracteristicilor). Ei mai mentioneaza aplicatii botanice, codate, electronice, medicale, microbiologice si zoologice, cat si aplicatii ale tabelelor de decizie si prime implicants. Moret [48] studiaza arborii de decizie si diagramele avand aplicatii raspandite oriunde functiile discrete trebuie sa fie evaluate secvential. El stabileste o schema comuna a definitiilor si revizuieste contributiile de la cateva campuri de aplicatii precum bazele de date, programarea tabelului de decizie, teoria complexitatii concrete, teoria schimbarii si recunoasterea modelului. Cartea recenta a lui Bretman [6] dezvolta clasificarea si progresul arborilor ca o unealta pentru analiza statistica a datelor. Metodologia lor principala este impartirea de sus in jos pentru a structura si clasifica datele. Acest lucru este mai potrivit pentru analiza datelor si regresiunea nonlineara decat pentru problemele curente de recunoastere a modelului. Prezenta lucrare subliniaza arborii de decizie si aplicatiile lor la recunoasterea modelului.

2. O baza formala pentru Arborii de Decizie

Un mod convenabil de a introduce arborii de decizie consta in considerarea unei probleme pentru care clasificatorul optim pare sa fie o decizie pe mai multe etape pentru realizarea unei scheme. Incorporarea costurilor caracteristicilor stabilite ca parte a costului total pentru minimizare asigura o astfel de baza.

Problema fundamentala in recunoasterea statistica a modelului este design-ul clasificatorului de risc minim al lui Bayes. Schema diminueaza costul asteptat al clasificarii atunci cand valorile costului general sunt asociate cu combinatii posibile de clasificari corecte si gresite. O tratare excelenta a acestei probleme este disponibila in Duda si Hart [21]. Daca costul fiecarei clasificari gresite este unitatea si cel al fiecarei clasificari corecte este zero, schema de decizie este identica cu aceea a probabilitatii minime de eroare. O extindere a problemei de clasificare de risc minim este permiterea masurarii caracteristicilor pentru a crea costuri.

Intr-un asemenea mediu de recunoastere a modelului, cel care ia decizia sau schema de clasificare ar trebui sa evalueze valoarea informatiei ce trebuie descoperita de catre o masurare a caracteristicii relationata cu costul sau. Reducerea posibila a riscului clasificarii folosind rezultatul masuratorii poate fi neinsemnata in comparatie cu costul masurarii caracteristicii. Cel mai bun exemplu pentru a ilustra acest lucru este in diagnosticul medical. Pentru a diagnostica intre orice multime de presupuse tulburari, exista de obicei un set mare de teste disponibile. Unele pot fi foarte costisitoare, vatamatoare sau poate chiar potential fatale pentru pacient. Astfel, daca nu este necesar, nu toate testele vor fi realizate. Intuitiv, este mai bine sa incepem cu teste simple. Bazat pe rezultatele acestor teste, este posibil, in anumite instante, sa poata fi luata o decizie. Chiar daca mai multe teste sunt necesare, rezultatele observate anterior pot indica care din teste costisitoare este posibil sa ofere informatia ceruta pentru diagnostic. Astfel, luarea unei decizii se realizeaza in mai multe etape. La fiecare etapa schema presupune doua optiuni principale: Decizia asupra unei etichete de clasa si terminarea procesului sau masurarea unei caracteristici pentru a aduna mai multe informatii. Ar trebui notat ca daca masuratorile nu costa nimic, nu se obtine nimic daca nu se masoara caracteristica, asa ca cea mai buna schema ar conduce toate masuratorile si decide asupra etichetei clasei intr-un singur mod. Acest lucru reduce schema la clasificatorul de risc minim.

2.1 Costul minim al problemei de recunoastere a modelului

Argumentele calitative de mai sus sunt dezvoltate prin studierea proprietatilor schemei optime pentru urmatoarea problema. Se da

(I) O multime Ω de M clase ω_i cu probabilitatile lor a priori P (ω_i),

i = 1, , M,

(II) Un vector de N caracteristici , F = (f ₁, , f_N) in care

caracteristicile sunt ordonate arbitrar, cu costurile lor corespunzatoare

masurarii c_i, i = 1, , N,

(III) M functii de densitate ale probabilitatii conditionate pentru clasele complet cunoscute (sau functii concentrate) p (x | ω_i), i = 1,, M, unde x = (x₁, .., x_N) este un rezultat N-variabil al celor N caracteristici si

(IV) Matricea A de dimensiune M x M a pierderilor cu λ_ij 0 reprezentand costul creat daca se hotaraste ca o mostra a modelului de la o clasa adevarata ω_i apartine lui ω_j.

Se cere sa se ajunga la construirea unei scheme de decizie cu un cost total minim asteptat, in care costul total este suma dintre costul masuratorii si riscul clasificarii.

Evident, pe orice mostra a modelului, folosind mai multe caracteristici va micsora riscul de clasificare gresita, dar va creste costul masuratorii. Posibilitatile extreme sunt :

(I)               De a nu realiza nici o masuratoare si de a clasifica mostra la o baza minima de risc a priori si

(II)             De a realiza masuratorile tuturor caracteristicilor (creand costurile lor) si dinimuarea riscului a posteriori.

Cea mai buna alegere se gaseste undeva la mijloc si dificultatea este ca variaza de la mostra la mostra, facand ca desenul schemei optime sa fie foarte complex.Argumentele anterioare dau niste idei despre comportamentul schemei optime. Aceste idei sunt perfectionate in continuare prin revizuirea unor fapte elementare, dar interesante despre recunoasterea modelului.

Cel mai important dintre toate este faptul ca, clasificatorul optim pentru problema costului minim este o decizie pe mai multe etape de realizare a schemei. Prin realizarea etapelor multiple, schema retine optiunea de a se imprastia-raspandi si fara o particularitate costisitoare nemasurata inca, daca masuratorile deja realizate indica (din punct de vedere statistic) non-optimalitatea sa. Daca, totusi, rezultatele observate indica faptul ca masuratori viitoare sunt necesare, una sau mai multe dintre caracteristicile ramase pot fi masurate. Extinzand acest argument in continuare, este mai usor de aratat ca masurarea unei singure caracteristici dintr-o etapa este optima. Dovezi exacte sunt disponibile la Dattatreya [18]. Wald [62] considera o problema si mai generala unde costurile masuratorilor caracteristicilor sunt functii ale rezultatelor lor si ale secventelor in care sunt masurate. In unele dintre aceste cazuri, masuratoarea a mai mult de o caracteristica la o etapa pare sa fie optima. Totusi, pentru recunoasterea practica a modelului, costurile caracteristicilor sunt cel mai bine modelate ca si constante permitand unei caracteristici pe etapa sa fie optima.

Daca caracteristicile sunt cerute sa fie masurate pe rand, o solutie directa este o secventa optima a masuratorilor caracteristicii. Se poate ajunge la cea mai buna secventa a unei probleme date. Schema de decizie gaseste urmatoarea caracteristica specificata pentru masurare daca precizia asteptata (sau riscul de clasificare) este imbunatatita. Aceasta este recunoasterea secventiala a modelului studiata intensiv de Fu [25]. O secventa de caracteristici care nu se schimba cand masuratorile sunt facute nu este optima asa cum arata urmatorul exemplu; la orice etapa intermediara, cea mai buna caracteristica pentru urmatoarea masuratoare este o functie a tuturor masuratorilor disponibile.

Exemplu: Un clasificator al modelului de doua clase masoara o caracteristica f ₁ la prima etapa. Costul masuratorii a inca doua caracteristici disponibile f ₂ si f ₃ sunt egale si sunt suficient de mari pentru a opri o masuratoare viitoare, dupa masurarea unei dintre ele la o a doua etapa. Toate caracteristicile sunt binare si sunt clase in mod conditionat independente statistic. Clasa functiilor concentrate de probabilitati conditionate ale lui f ₂ si f ₃ sunt date in Tabelul 1. Probabilitatile modificate ale clasei ω₁ la sfarsitul primei etape, P (ω₁| x₁) sunt date in Tabelul 2. Obiectivul acestui exemplu este aceea de a arata ca f ₂ este mai bun decat f ₃ pentru un rezultat al lui f si f ₃ este mai bun decat f ₂ pentru celalalt rezultat al lui f ₁. Probabilitatile de erori pentru cele doua scheme sunt reprezentate in Tabelul 2 ca si functii ale rezultatelor lui f ₁. In mod clar f ₂ da o rata mai mica de eroare daca x₁ = 0 si f ₃, daca x₁ = 1. Astfel schema de decizie aratata in Fig. 1 (c) este mai buna decat cele din Figurile 1 (a) si 1 (b). In figura, nodurile neterminale conduc la masuratori de caracteristici specificate si lasa ca in schema de decizie sa intre nodurile descendente bazate pe rezultatul caracteristicii masurate. Rezultatele sunt indicate pe ramurile relevante.

2.2 Solutii de programare dinamica

S-a aratat in mod logic nevoia teoretica pentru arborii de decizie pentru o clasa a problemelor de recunoastere a modelului (cele ce implica costuri de masurare a caracteristicilor), decat recurgerea la arbori de decizie ca o alternativa la alta schema. Exemplul este trivial din moment ce este stiut ca folosirea tuturor celor trei masuratori este extrem de costisitoare. Daca ar fi fost mai multe caracteristici de costuri tolerate, ar trebui sa punem doua intrebari:

(I)           Care este costul asteptat daca masuratoarea viitoare este abandonata in favoarea deciderii asupra etichetei clasei cel mai putin riscante?

(II)         Care este costul asteptat (suma dintre costul masuratorii si riscul de clasificare) daca schema masoara o caracteristica candidata f _i si foloseste metoda optima dupa aceea?

Pentru a raspunde la aceste intrebari, avem nevoie de o nota pentru a face structuri de decizie pe mai multe etape. Multi termeni, de ex. noduri, ramuri, si descendenti directi se presupune ca nu sunt ambigui.

TABELUL 1 TABELUL 2

Functiile concentrate de probabilitate P(eroare | x₁) ca functie a 

-------- ----- ------ ------- caracteristicii utilizata la

P(x_i |_j etapa a doua 

----- ----- --------- ----- -------- -------- ----- ------ -------

Clasa x x Eroare

----- ----- --------- ----- -------- x P( |x ) ----- ----- --------

0 1 0 1 f f

-------- ----- ------ ------- -------- ----- ------ -------

0.6 0.4 0.2 0.8 0 0.4 0.22 0.26

0.1 0.9 0.7 0.3 1 0.6 0.28 0.24

-------- ----- ------ ------- -------- ----- ------ --------

0/1 0/1

0 1 0 1

(a) (b

0 1

0 1 0 1

(c)

Fig.1 Schemele de alternare pentru exemplul dat.

n_i este al i-ulea nod neterminal in stuctura luarii deciziei. Neterminal, in sensul ca exista o masuratoare a caracteristicii la n_i. Felul in care aceste noduri sunt numerotate nu este inca specificat. Un nod terminal este un descendent direct al unui nod neterminal si corespunde unei decizii de clasa ω_j. In general, n_i are atat multimi de noduri direct descendente terminale cat si multimi de noduri direct descendente neterminale..

D(n_i) este multimea nodurilor neterminale direct descendente (daca exista) ale nodului neterminal n_i.

Daca n_j este descendentul neterminal al lui n_i, f(n_i n_j) este caracteristica care va fi masurata la n_j, daca schema de decizie coboara de la n_i la n_j. In mod natural, f (n_i n_j) . c (n_i n_j) este costul masurarii f (n_i n_j). z (n_i n_j) este rezultatul obtinut la masurarea lui f (n_i n_j).

F(n_i) este o submultime a multimii de caracteristici F si cuprinde toate caracteristicile masurate pana la, si incluzand, nodul n_i. y (n_i ) este rezultatul obtinut dupa masurarea tuturor F (n_i). y (n_i) este | F(n_i ) | - variabila in cadrul careia rezultatele individuale sunt ordonate ca in vectorul x = (x , , x_N ) .

Dupa masuratoarea caracteristicii la nodul n_i, riscul sau costul asteptat al clasificarii (a fi creat daca se decide ca sa se clasifice mostra ca apartinand lui ω_j) este dat de

R ω_j y (n_i)) = λ_kj P(ω_k | y (n_i) (2.1)

folosind notatia de mai sus si terminologia problemei definite mai devreme.

R* y (n_i)) = R(ω_j | y (n_i) (2.2)

este riscul minim (conditionat de y (n_i), observatiile facute) daca se decide sa se termine masurarea caracteristicii si sa se faca o clasificare dupa nodul n_i.

Totusi, daca nodul neterminal n_i are decendenti care sunt ei insisi neterminali, masurarea caracteristicii este posibila in continuare. Pentru a decide intre masurarea caracteristicii in continuare si clasificare, este nevoie sa se astepte crearea costului daca o sa se faca in continuare masuratori. Fie n_j un descendent direct al lui n_i ; E*( y (n_j )), costul optim asteptat ce va fi creat dupa observarea lui z (n_i n_j) la nodul n_j. Retinem ca z (n_i n_j) si y (n_i) impreuna (ordonate corespunzator) constituie y (n_j ). De asemenea E*(y (n_j)) insusi depinde de deciziile optime la n_j si descendentii lui. Costul asteptat inca sa fie creat dupa n_i la deciderea de a cobori la n_j este costul asteptat sa fie creat la si dupa n_j.Acesta este costul masurarii caracteristicii la n_j, c(n_i n_j), plus costul optim asteptat a fi creat ulterior. Aceasta ar trebui sa fie in mod corespunzator totalizata intr-o medie a tuturor rezultatelor lui f (n_i n_j), deoarece nu am observat z (n_i n_j), dar doar studiem mutarea de la n_j la n_i. Asadar,

E(n_i y (n_i)) = c (n_i n_j) + E*(y (n_j)) p( z(n_i n_j) | y (n_i)) dz (n_i n_j) (2.3)

este costul optim asteptat, conditionat de rezultatele observate y (n_i), inca de a fi creat daca este luata o decizie de a cobori la nodul n_j de la n_i . Dar coborarea la n_j in particular poate sa nu fie optima daca sunt alte elemente in

D (n_i ). Deci,

E*(y (n_i)) min (2.4)

este costul minim asteptat al tuturor deciziilor posibile la nodul n_i, conditionate de toate observatiile facute pana la acel stadiu, y (n_i).

La unele noduri din graful caracteristicilor, nu vor mai fi alte caracteristici pentru a fi masurate in continuare. Asemenea noduri au doar noduri terminale ca descendenti. Daca n_k este un asemenea nod, F (n_k) = F,

multimea totala de caracteristici si y (n_k) = x, rezultatul N-variabil. Costul minim asteptat (inca de a fi creat) intr-un asemenea nod este dat de insusi riscul minim al clasificarii.

E*(n_k | x) = λ_ij P(ω_i | x) (2.5)

Deci, fiind data o structura a luarii unei decizii cu mai multe etape ca cea din Fig.1 (c), este posibil prin procedura de programare dinamica recursiva sa calculezi costul minim asteptat al intregului arbore. Un produs secundar al unui asemenea calcul il reprezinta regulile optime de decizie in fiecare etapa, pentru fiecare rezultat. Dar daca ne sunt date doar statisticile si costurile, cum procedam? Proprietatile clasificatorului optim discutat mai devreme ne ajuta. In orice etapa, consideram masurarea unei caracteristici, pe rand, din toate caracteristicile inca nemasurate. Aceasta este prea greoaie pentru a fi folositoare in practica, in special daca numarul caracteristicilor este prea mare si caracteristicile sunt continue. Cu toate acestea, este folositor sa studiezi un asemenea mecanism al schemei construirii unei decizii optime si design-ului ei.

2.3 Reprezentarea grafului deciziei

Structura luarii unei decizii (numita de acum inainte graful caracteristicilor) pe care pot fi scrise ecuatiile de programare dinamica cuprinde :

(I) Un nod radacina ce corespunde etapei zero cu nici o caracteristica

atribuita;

(II) N nivele de noduri sub nodul radacina, ce corespund celor N

etape posibile de masurari ale caracteristicilor;

(III) N-i noduri direct descendente pentru fiecare al i-ulea nod al

etapei (conectat prin legaturi unidirectionale); fiecare nod direct

descendent masoara o caracteristica ce nu a fost deja masurata la

primele i etape pe drumul ce conduce la al i-ulea nod al etapei

considerate, si

(IV) N! drumuri distincte dar suprapuse de la etapa zero, ce corespund

celor N! ordonari ale caracteristicilor.

Doua sau mai multe drumuri se unesc intr-un nod la etapa i daca ele masoara aceeasi multime de i caracteristici pana la, si incluzand nodul de unire. Asadar, exista un nod ce corespunde fiecarei submultimi de caracteristici. In total, sunt 2^N noduri, incluzand nodul radacina ce corespunde multimii vide de caracteristici.

Un graf al caracteristicilor cu patru caracteristici este desenat in Fig. 2. Nodurile sunt numerotate intr-o ordine anume. Observati ca daca n_j este descendentul lui n_i, atunci n_i >n_j. Cu o asemenea numerotare, costurile optime in timpul procedurii de programare dinamica sunt evaluate pornind de la primul nod si urcand in concordanta cu numerele atasate nodurilor, pana la nodul radacina. Aceasta asigura utilitatea costurilor optimale ale tuturor descendentilor unui nod cand acestea sunt necesare pentru a evalua costul optim al nodului in discutie.

Fig.2 Graful caracteristicilor al unei probleme cu patru caracteristici.

Numerotarea nodurilor din Fig. 2 este specifica si nu avanseaza cu un rand la o extindere. Aceasta este facuta pentru a simplifica calcularea numerelor nodurilor tuturor descendentilor directi ale unui nod arbitrar in timpul calcularii costului sau optim. Matematic, fie

L( n_i ) = ( (n_i ) , , _N ( n_i )) (2.6)

o formula binara ce corespunde fiecarui nod n_i in graful caracteristicilor astfel incat

0, daca f_j F( n_i

_j (n_i =

1, altfel (2.7)

L (n_i) denota caracteristicile masurate pana la, si inluzand, nodul n_i. Apoi numarul nodului (sau index-ul nodului) i al nodului n_i, este dat de

i = 1 + _j (n_i ^j-1 (2.8)

Aceasta permite calcularea numarului unui nod dand caracteristicile masurate si vice versa. Se observa ca indexul nodului radacina (stadiul zero) este 2^N, la care nicio caracteristica nu este masurata. Numarul descendentilor directi ai nodului n_i este doar numarul celor din formula binara L (n_i), deoarece γ_j = daca f _j nu a fost masurat. Asadar

| D(n_i) | = _j (n_i (2.9)

Fie d_k (n_i) al k-lea descendent direct al nodului n_i, adica

D(n_i) = , k= 1, , _j (n_i (2.10)

Suntem interesati de calcularea numarului nodului pentru d_k (n_i). Fie d_k (n_i) = n_j. Se observa ca L (n_i ) este obtinut prin inlocuirea celui de-al k-lea cu zero in L (n_i). Prin urmare,

j = i - 2^m-1 

unde m este cel mai mic numar intreg ce satisface

_t (n_i ) = k (2.12)

Este acum posibil sa rezolvam sistematic procedura de programare dinamica pe graful caracteristicilor cu noduri numerotate (sau indexate) pornind de la primul nod in care toate caracteristicile ar fi fost masurate. Metodologia completa este conturata mai jos.

Pasul 1: pentru nodul n₁ se evalueaza

E*(y (n₁)) λ_kj P(ω_k | x)

Aceasta, de asemenea, da regulile de decizie adecvate pentru toti y (n ). Se retine ca: y (n ) = x .

Pasul 2: Pentru n_i, i = 2, , (2^N - 1), se evalueaza

R*(y (n_i)) λ_kj P(ω_k | y( n_i ))

Pentru n_j = d_k (n_i), k = 1, , | D (n_i ) |, se evalueaza

E(n_j | y (n_i)) = c(n_i n_j ) + E y n_j p z n_i n_j y n_i dz n_i n_j

E*(y (n_i)) min

Aceasta de asemenea da regulile de decizie pentru toti y (n_i).

Pasul 3: La nodul radacina, n_i , i = 2^N , y (n_i) = ø este vid ; se evalueaza

R*(n_i | λ_kj P(ω_k | ø)

Pentru n_j = d_k (n_i ), k = 1, , | D (n_i) | se evalueaza

E(n_j | ) = c(n_i n_j ) + E y n_j p z n_i n_j dz n_i n_j

E* min

Regula optima de decizie este doar caracteristica optima care sa fie masurata in prima etapa, mai putin atunci cand se dovedeste ca problema este una patologica, in cazul in care metoda optima este de a decide o eticheta a clasei bazandu-se pe riscul a priori.

Imposibilitatea procedurii de mai sus pentru problemele practice de recunoastere a modelului, chiar avand un numar moderat de caracteristici, este imediat evidenta. In primul rand, pentru caracteristicile continue nu este posibil sa se obtina expresii inchise pentru E (n_j | y (n_i)) chiar si cu cele mai simple functii de densitate a probabilitatii. Aceasta, precum si faptul ca diferitele regiuni ale deciziei dau functii diferite pentru integrarea peste spatiul caracteristicilor masurate, face calcularea unei medii pentru a obtine costurile optime si regulile de decizie pentru toate valorile variabilelor continue y (n_i) virtual imposibila. Independenta conditionata statistic de clasa a caracteristicilor nu simplifica procedura, deoarece densitatea conditionata p (z ( n_i n_j ) | y (n_i)) folosita in expresia (2.3) este un amestec al tuturor claselor. Densitatile amestecului nu pot avea niciodata componente statistic independente. Daca

p ( x₁x₂) = P(₁) p (x₁x₂ | ₁) + P(₂) p (x₁x₂ | ₂) (2.13)

poate fi factorizat ca g₁(x₁) g₂(x₂), atunci p (x₁x₂ | ₁) si p (x₁x₂ | ₂) trebuie sa aiba aceiasi factori (din moment ce acestea sunt functii nenegative ce integreaza aceeasi valoare, adica unitatea) cauzand caracteristicilor sa degenereze in aceeasi functie de densitate pentru ambele clase.

Pentru caracteristicile discrete, procedura optima poate fi perfectionata pentru design-ul masinilor arborilor de decizie, dar doar pentru un numar redus de caracteristici cu cel mult cateva nivele discrete pentru fiecare. Metoda descrisa in [19] si [20] ordoneaza toate rezultatele ale tuturor caracteristicilor masurate pana in stadiul actual (in graful caracteristicilor, de exemplu, in Fig, 2) intr-un mod special convenabil. Un calcul recurent al costurilor optime este apoi implementat pe computer.

Un alt neajuns al acestui schelet teoretic este ca cere specificarea completa a structurii probabilistice fundamentale. In practica, o problema de recunoastere a modelului este de obicei definita pornind de la o multime de probe experimentate (etichetate). Numarul probelor va fi inadecvat pentru a modela sau estima dependenta caracteristicilor prin mijloace pur statistice. Alte particularitati precum incapacitatea modelului formal de a incorpora sarcina de calculare a dus la modele alternative pentru recunoasterea modelului in mai multe etape.

3. Modele pentru recunoasterea modelelor cu mai multe etape

Fu [25], vazand problema costului minim ca o versiune generalizata a recunoasterii secventiale a modelului, a propus un algoritm atat pentru ordonarea caracteristicilor cat si pentru clasificarea acestora. Dar schema rezultata nu a fost interpretata ca simplificata la un arbore de decizie aplicabil in practica. Ulterior, cateva schelete de arbori de decizie, care in principiu incearca sa exploateze proprietatile favorabile si sa usureze unele probleme asociate cu schema costului minim al deciziei, au evoluat. Modelele individuale se concentreaza pe sub-seturi ale aspectelor proprietatilor de atractie si folosesc de asemenea tehnici pentru a depasi dezavantajele specifice. Desi o astfel de abordare nu este recomandabila din punct de vedere al dezvoltarii unei teorii generale, ar trebui sa retinem ca pentru o problema data cu un numar finit de probe de instruire si cu resurse de calculare limitate, nu este nici posibil, nici necesar sa fie incercate solutii foarte generale. Concentrarea asupra particularitatilor specifice problemei este de ajutor in realizarea celor mai bune rezultate.

La particularitati si regularitati specifice ale unei probleme particulare de recunoastere a modelului se ajunge prin analiza modelului. Analiza interactiva a modelului (Kanal [36], [37]) este un mod de a permite examinarea structurii de date intr-un spatiu de mare dimensiune. Oamenii sunt superiori in recunoasterea anumitor tipuri de structuri. Examinarea umana este in general facilitata de expunerea grafica a diferitelor trasformari de date. Procedura consta in folosirea oricarei informatii despre problema in discutie pentru a ghida strangerea datelor despre modelele si clasele de modele care pot exista in mediul ce este examinat, si apoi a supune datele la o varietate de proceduri pentru a deduce structurile deterministe si probabiliste care sunt prezente in date. Aceasta se mai numeste si analiza de exploatare a datelor si include graficele de histograme, de dispersie, rutinele de analiza a grupurilor, analiza lineara diferentiata, aplicatia nelineara, analiza variatiei, etc. Un exemplu relevant al unui sistem de analiza interactiva a modelului este ISPAHAN (Gelsema [26]). Acest sistem permite utilizatorului sa investigheze interactiv structura datelor multidimensionale folosind un meniu de optiuni, incluzand clasificarea supervizata si non-supervizata, aplicarea algoritmilor si transformarea caracteristicilor. De asemenea, suporta analiza interactiva si design-ul sistemelor de clasificare cu mai multe etape. Intr-un alt studiu recent, Friedman si Stuetzle [24] raporteaza niste scheme de urmarire a proiectiei pentru detectarea, descrierea si validarea structurii in multimi de puncte

p-dimensionale. Acestea, precum si multe alte metode de analiza a datelor ajuta in selectarea unui model in mai multe etape deja existent sau in dezvoltarea unui nou model pentru problema de recunoastere a modelui in discutie.

3.1 Modelele spatiului de stari.

O structura de decizie schitata pentru problema costului minim arata in mod obisnuit precum cea prezentata in Fig. 3. Caracteristica ce trebuie masurata initial in prima etapa este specificata. Ulterior, nodurile ce trebuie traversate depind de rezultatele observate. Precum este explicat in Sectiunea 2, este foarte greu sa tii socoteala sau sa precizezi regulile optime de decizie, deoarece acest lucru implica realizarea unei medii a tuturor costurilor la nodurile descendente.

Fig. 3 o stuctura a decizei schitate (ipotetic)

Deoarece nu este posibil sa ne conformam la reguli optime de decizie globale in practica, problema poate fi modificata pentru a cauta un nod tinta care minimizeaza suma costurilor masuratorilor la toate nodurile ce duc la nodul tinta particular, si riscul conditionat de aceste masuratori. Procedura implica masurarea caracteristicilor nu doar de-a lungul drumului spre nodul terminal decis in final, ci si la cateva alte noduri intr-o incercare de a reduce costul total cat mai mult cu putinta. Daca se da costul optim asteptat care va fi creat dupa etapa actuala, doar acele noduri de-a lungul drumului catre nodul final ce va fi decis trebuie traversate, reducand schema la aceea a costului minim. Aceasta sugereaza ca folosirea unei limite inferioare estimeaza asemanator cu acelea folosite de Hart [28] in cautarea in graf, pentru a reduce devierile de la drum care conduc la un nod tinta necunoscut. Aceasta este filizofia din spatele modelelor spatiului de stari propuse si studiate de grupul lui Kanal [38]-[43]. Notatia introdusa in Sectiunea 2 este folosita aici mai degraba decat cea folosita in referintele originale.

Un graf al spatiului de stari G este asemanator cu un subgraf (Fig. 3) al grafului caracteristicilor cu diferenta ca nodurile neterminale din G pot masura mai mult de o caracteristica la un nod si ca fiecare nod neterminal n_i tine socoteala multimii de clase care apar ca nodurile sale descendente terminale (nu neaparat descendente direct). Nodurile terminale cu etichete de clasa sunt de asemenea explicit incluse in graful spatiului de stari, lucru care nu se intampla si in cazul grafului caracteristicilor. Matematic, G este format din sapte componente:

G

unde:

(i)      S = este mutimea nodurilor (starilor);

(ii)            E = este multimea arcelor . Exista arc de la nodul n_i la

nodul n_j doar daca n_j este un descendent direct al lui n_i ;

(iii)          F este multimea totala a caracteristicilor;

(iv)          este multimea totala a claselor;

(v)            C este o functie reala nenegativa de evaluare a costului pe arce;

c (n_i n_j) este costul caracteristicilor masurate cu o tranzitie de la

n_i la unul dintre descendentii sai directi, n_j.

(vi)          R este o functie cu valoare reala definita pe multimea nodurilor

tinta (terminale) ce reprezinta valoarea asteptata a costului sau

pierderii creata in realizarea clasificarii deciziei asociate cu

nodul tinta si

(vii)        T este strategia folosita in deciderea caror noduri vor fi

traversate in graf.

Diferenta esentiala intre aceasta formulare si graful deciziei din Fig. 3 este ca f (n_i n_j), caracteristica masurata intr-o singura tranzitie de la n_i la n_j nu este in mod necesar unica. f (n_i n_j) este o submultime a lui F. Similar, c (n_i n_j) este suma costurilor tuturor caracteristicilor in f (n_i n_j) si z (n_i n_j) este mai degraba un vector variabil decat un scalar. Aceste definitii sunt extinse pentru cazul in care n_j nu este un descendent direct, dar este un descendent oarecare al lui n_i. Adica, f (n_i n_j) este multimea caracteristicilor masurate dupa n_i pana la, si inclusiv n_j. De asemenea, Ω (n_j) este o submultime a lui este setul claselor in discutie la n_j.

Daca n_j este un nod terminal, | Ω (n_j)|= . In afara de aceste adaptari, notatia este esential aceeasi ca cea din Sectiunea 2. Cativa termeni noi sunt introdusi atunci cand este nevoie. Nu este bine ca complexitatea situatiilor posibile in recunoasterea modelului pe mai multe etape sa nu permita folosirea unei notatii simple.

O importanta clasa de scheme in interiorul modelului spatiului de stari este clasificatorul ierarhic in care grupuri de clase formeaza o ierarhie. Astfel de scheme au avantajul de a putea folosi o cunostinta a priori in ceea ce priveste relatiile fizice si biologice dintre subgrupurile multimii de clase. Chiar si in situatii fara astfel de relatii, o analiza explorativa a datelor poate sa scoata in evidenta usurinta distingerii diferitelor submultimi de clase folosind diferite submultimi de trasaturi. Aceasta abordare va reduce de asemenea complexitatea clasificatorului rezultat. Cel mai lung drum in graful spatiului de stari nu va fi mai mare decat numarul claselor, din moment ce, cel putin o clasa este eliminata la o etapa. Astfel, Ω (n_j) este o sbumultime potrivita a lui Ω (n_i) daca n_j este un descendent al lui n_i. La nodul radacina (sau starea initiala) nicio caracteristica nu este masurata si este considerata multimea tuturor claselor. De asemenea, in clasificatorii ierarhici fiecare nod are un parinte unic.

Un proces de clasificare este o strategie pentru cautarea in graf a unui nod terminal cu costul cel mai mic. Acest proces depinde de formularea costului. Costul unui nod tinta n_i este suma dintre costurile masuratorilor si riscul clasificarii. Riscul poate fi o functie de observatii doar de-a lungul drumului catre nodul tinta acceptat sau pe toate masuratorile. Strategia de cercetare depinde in mod natural de acest lucru. In primul caz, costul total al nodului terminal n_i este

s (n_i) = C (n_i) + R ( (n_i) | y (n_i))

unde y (n_i) reprezinta observatiile facute de-a lungul drumului doar catre n_i . In al doilea caz

s (n_i) = C (n_i) + R ( (n_i) | x) (3.2)

unde x este observatia datorata tuturor masuratorilor posibile. Urmatorii algoritmi, Algoritm-S si Algoritm-B, corespund celor doua cazuri.

Algoritm-S

Pasul 1: Pune nodul radacina intr-o mutime OPEN. Goleste o multime numita CLOSED.

Pasul 2 Pentru fiecare n_i OPEN, se evalueaza

s (n_i) = C (n_i) + h (n_i) + r (n_i)

unde h (n_i) = 0 daca n_i este un nod tinta

min_{njT (ni} C (n_i n_j) daca n_i nu este un nod tinta

r (n_i) = R ( (n_i) | y (n_i)) daca n_i este un nod tinta

=min _{njT (ni} min _{z(ni nj)} R( (n_j), z (n_i n_j)] daca n_i nu este

un nod tinta

Pasul 3: Fie n_k un nod care apartine multimii OPEN avand s () minim. Se elimina n_k din multimea OPEN si se adauga la multimea CLOSED. Se adauga toti descendentii directi ai lui n_k in multimea OPEN. Daca n_k este un not teminal, se accepta eticheta corespunzatoare clasei si se iese din algoritm. Altfel se merge la Pasul 2.

In algoritmul de mai sus, functia s (n_i) calculata este o limita inferioara a costului total care ar fi creat de un exemplu de model dat care ar fi intrat in nodul n_i cu caracteristica de observare y (n_i). Daca aceasta limita inferioara este suficient de aproximativa pentru a egala costul actual, exemplul de model va ajunge la nodul tinta adecvat fara sa se faca masuratori inutile. Altfel, schema va conduce masuratoarea nu numai pe drumul catre tinta finala acceptata, dar si la mai multe noduri. Totusi, ceea ce este minimizata este suma dintre riscul de clasificare la nodul tinta si costul doar acelor caracteristici masurate de-a lungul drumului catre nodul tinta.

Presupunerea ca riscul este o functie a observatiilor de-a lungul drumului catre nodul tinta (si nu catre alte noduri) poate fi valabila in problemele in care diferite multimi de caracteristici sunt cunoscute a fi folositoare pentru clase diferite. In cazuri extreme densitati conditionate ale claselor anumitor caracteristici pot sa nu fie definite sau pot degenera sa fie egale pentru anumite clase. In general, totusi, riscul este o functie a tuturor masuratorilor (vezi expresia 3.2) pentru care este relevanta urmatoarea procedura.

Algoritm-B

Pasul 1: Se pune starea initiala in multimea OPEN. Multimea

CLOSED se face vida .

Pasul 2 Pentru fiecare nod n_i OPEN, se evalueaza

s (n_i) = C (n_i) + h (n_i) + r (n_i)

unde h (n_i) = 0, daca n_i este un nod tinta

min_njT(nj) C (n_i n_j), daca n_i nu este un nod tinta

r (n_i ) min _v R ( (n_i) | y (n_i) , v) daca n_i este un nod tinta

min _v min _{njT (ni} R( (n_j) | y (n_i) , v) daca n_i nu este

un nod tinta

unde v este rezultatul tuturor caracteristicilor care nu apartin lui F (n_i).

Pasul 3 Fie n_k nodul care apartine multimii OPEN cu s () minima. Se muta n_k din multimea OPEN in multimea CLOSED si se pun toti descendentii directi al lui n_k (daca exista vreunul) in multimea OPEN.

Pasul 4 Pentru fiecare nod tinta n_i CLOSED, se evalueaza limita superioara a lui b (n_i) unde

b (n_i) = C (n_i ) + max _v R ( (n_i) | y (n_i) , v)

Fie n_k nodul terminal care apartine multimii CLOSED pentru care b ( ) este minima. Daca pentru toate nodurile n_j OPEN CLOSED, n_j ≠ n_k ,

b (n_k) ≤ s (n_j), atunci se iese cu n_k ca si tinta optima B; Altfel se merge la Pasul 2.

Cand riscul este o functie a tuturor masuratorilor, se poate termina cautarea doar atunci cand este sigur ca masuratori aditionale nu vor conduce spre o oricare alta tinta clasificata mai sus decat nodul tinta deja aflat in multimea CLOSED. Acest lucru este indeplinit prin folosirea unei limitei superioare a functiei b (n_i). Dovezi exacte ca acesti algoritmi sunt admisibili in respectivele lor sensurile sunt disponibile in Kulkarni [40]. El mai discuta de asemenea despre modelele spatiului de stari pentru recunoasterea modelului nonparametric ca scheme vecine cele mai apropiate in care costurile masuratorii caracteristicilor dau nastere din nou la scheme pe mai multe etape. Tipic, costul ce trebuie minimizat este suma dintre costul masuratorii si distanta dintre modelul test si cel mai apropiat vecin. Schema de recunoastere poate fi implementata ca o strategie de cautare similara cu cea discutata mai sus. Aceste strategii de cautare presupun existenta unui graf al spatiului de stari adecvat problemei respective. Design-ul unor astfel de structuri de decizie este discutat in Sectiunea 4.

3.2 Modele independente de subrecunoastere

Una din modalitatile de simplificare a recunoasterii modelului este impartirea problemei in alte cateva probleme mai mici. Daca una urmareste o schema optima din punct de vedere global, interactiunea acestor subscheme devine inadmisibil de complexa si design-ul lor chiar si mai complex. O schimbare practica ar fi sa se faca design-ul subschemelor ignorand interdependenta lor. O combinatie logica a rezultatelor acestor subscheme ar trebui atunci sa fie corespunzatoare pentru clasificarea finala a exemplului de model dat.

Ichino [33]-[35] studiaza cateva modele de acest tip. Specificatii majore ale unor astfel de modele sunt tipurile de subscheme ce trebuie folosite si metoda combinarii rezultatelor lor. Primul tip este sistemul dual de recunoastere de clasa. In aceasta metoda, un clasificator este proiectat pentru fiecare pereche de clase folosind o submultime de caracteristici pentru fiecare pereche. Rezultatul fiecarui subclasificator este eticheta uneia sau a doua clase considerate. Fie ca numarul claselor sa fie M. Pentru a ajunge la eticheta clasei finale, se face o contorizare a fiecarei clase din rezultatul subsistemelor M (M-1)/2. Numarul maxim pentru orice clasa este M-1, deoarece M-1 clasificatori sunt considerati pentru orice clasa particulara. De asemenea, daca contorizarea unei clase este M-1, nici o alta clasa nu poate sa aiba aceeasi proprietate, deoarece orice alta clasa ar fi fost eliminata de cel putin un clasificator care considera acea clasa si pe aceea a carei contorizare a fost M-1. Asadar, Ichino sugereaza faptul ca un model este decis in final ca apartinand unei clase daca si numai daca acea clasa are contorizarea M- . Altfel, modelul este respins ca fiind neclasificat. Totusi, ar trebui notat ca alte combinatii precum majoritatea deciziilor de calcul sunt posibile. Aceasta metoda are unele avantaje cand analiza a priori a cunostintelor sau datelor indica posibilitatea distingerii intre perechi de clase diferite si submultimi mici de caracteristici. Dar daca numarul claselor este mare, numarul schemelor de subrecunoastere, M(M-1)/2, tinde sa fie impracticabil.

Alternativ, subschemele pot considera o clasa in defavoarea restului, caz in care vor exista doar M subscheme. Aceasta se numeste sub-recunoastere simetrica a "clasei intelepte". Clasificarea finala este facuta doar daca o schema accepta acea clasa. In aceasta metoda exista doua tipuri de eliminare. Primul tip, cand doua sau mai multe scheme de subrecunoastere accepta clasele lor respective. Celalalt tip, cand nicio schema nu-si accepta clasa sa. O modalitate de a evita primul tip de respingere este aceea de a accepta prima clasa pe care schema de subrecunoastere o accepta. Dar, atunci, este importanta ordonarea claselor intr-un anume mod.

Cand un numar mare de clase formeaza o multime omogena de puncte intr-un spatiu metric, cea mai buna metoda este aceea de a realiza un clasificator bun pentru o multime mica de etichete ale clasei desenate la intamplare din multimea mare originala. Acest clasificator poate fi folosit ca ultima etapa a unei scheme cu mai multe etape in care multe clase sunt eliminate cu o acuratete mare in etapele initiale. Acest model este propus si folosit pentru recunoasterea vorbirii la populatii mari de catre Dante [12] si de catre Dante si Sarma [13], [14]. Tehnica pe care ei o folosesc pentru a simplifica modelul este de a presupune, pentru scopuri analitice, ca insasi eticheta clasei este o variabila continua dintre variabilele continue de caracteristici. Starea sistemului de clasificare in orice etapa este definita ca un numar de vorbitori luati inca in calcul. Problema realizarii clasificatorului pare atunci sa fie alocarea caracteristicilor la etape potrivite si definirea metodelor pentru tranzitiile starilor. Problema este rezolvata prin folosirea tehnicilor stochastice de control optim.

3.3 Modele top- down

Discutia de pana acum clarifica faptul ca singura modalitate de a obtine decizii optime in recunoasterea modelului pe mai multe etape este de a folosi costurile optime ale posibilelor cursuri ale actiunii dupa etapa prezenta. Aceasta procedura "bottom-up" necesita calcul si memorie enorme. In practica, utilizatorul poate fi mai interesat de scheme simple ce duc la un compromis intre complexitatea operatiei si performanta in termeni a costurilor. Un model evident pentru acest scop este acela in care schema de decizie specifica explicit actiunea ca o functie a caracteristicii masurate in etapa in discutie. Acesta este un avantaj doar din punctul de vedere al operatiei clasificatorului si se adauga la complexitatea design-ului. Dattatreya si Sarma [18] propun o astfel de metoda si o demonstreaza pentru o problema foarte mica cu trei caracteristici Gaussiene . Metoda implica realizarea schemei costului minim si modificarea ei intr-un arbore de decizie care ia decizii prin comparatii initiale cu caracteristica masurata la orice etapa. Fie n_j un descendent direct al nodului n_i din prima etapa, si n_k descendentul direct al lui n_j. Cu terminologia uzuala (considerand doar o caracteristica pe etapa), costul optim ce trebuie sa fie creat daca este luata o decizie de a cobori la nodul n_k

E* (n_k | y (n_j))

este o functie a observatiei z (n_i n_j) la nodul n_j , la fel ca si singura observatie anterioara y (n_i). Cea mai buna modalitate de a scapa de y (n_i) este de a calcula o medie a lui y (n_i).

E (n_k | z (n_i n_j)) = E* n_k | y (n_j), z(n_i n_j)) p(y (n_i)) dy (n_i) (3.3)

unde regiunea de integrare se extinde doar peste acele valori ale lui y (n_i) pentru care un exemplu al modelului ajunge la nodul n_j. Acesta, facut din toti descendentii directi n_k ai lui n_j, faciliteaza luarea deciziei la n_j bazata pe functia unei singure variabile z (n_i n_j). Schema de decizie ce rezulta poate fi implementata folosind comparatii initiale. Calculul mediei trebuie sa fie facut de sus in jos, dupa realizarea schemei costului minim si implica eliminarea unei singure variabile la un moment dat. Aceasta este o tehnica pentru a modifica regiunile complexe de decizie in regiuni hiper rectangulare pentru a ajunge la o schema foarte simpla pentru operatie. Totusi, dincolo de asigurarea perspicacitatii in mecanismul clasificarii pe mai multe etape, metoda este putin folosita pentru probleme practice. In general, simplitatea design-ului este de asemenea foarte importanta.

Metodele top-down" in realizarea arborilor de decizie de obicei implica in mod repetat selectarea unei caracteristici si segmentarea regiunii sale. De obicei aceste metode realizeaza scheme de clasificare de la o multime relativ mica de modele etichetate si foloseste reguli nonparametrice de impartire. Doua clase distincte ale acestor metode sunt:

(I)      Partitionarea intregului spatiu caracteristic de intrare si convertirea schemei de decizie rezultate intr-un arbore. Convertirea acestor tabele in arbori poate fi realizata de sus in jos sau de jos in sus. Henrichon si Fu [30] prezinta o astfel de procedura care in general nu clasifica in mod corect toate modelele design-ului. Meisel si Michalopoulos [47] prezinta o alta procedura pentru o clasificare suta la suta corecta.

(II)            Partitionarea caracteristicilor pe rand si repetarea acestui lucru asupra subregiunilor rezultate in vederea dezvoltarii dinamice a unui arbore.

Amintim ca un clasificator poate fi intotdeauna realizat astfel incat sa clasifice corect toate modelele etichetate date. Din moment ce acesta va avea un efect advers asupra modelelor test ce vor fi clasificate (vezi Hughes [31]), multe din metodele de mai sus incorporeaza reguli de oprire pentru a preveni impartiri prea fine ale spatiului caracteristic.

Unele scheme folosesc o privire inainte cu un pas sau functii simple de evaluare pentru costuri dupa etapa prezenta, decat sa fie pur si simplu de sus in jos. Brelman [6], [7] foloseste o functie a complexitatii arborelui aditionala preciziei de clasificare. Aceste modele de design al arborilor de sus in jos nu considera costurile masuratorilor caracteristicilor cum au fost definite in Sectiunea 2. Intrebarea evidenta, asadar, este de ce folosim arborii de decizie ? Wu [63] scoate in evidenta nevoia ca clasificatorii de arbori de decizie sa rezolve problemele dimensionalitatii si dimensiunii mici a modelului. Alte avantaje precum eficienta calculului pe durata operarii asupra arborilor de decizie si intelegerea procesului de clasificare justifica folosirea lor. Sectiunea urmatoare discuta despre metodologii de design pentru arborii de decizie.